Structural Ramsey theory

In mathematics, structural Ramsey theory is a categorical generalisation of Ramsey theory, rooted in the idea that many important results of Ramsey theory have "similar" logical structure. The key observation is noting that these Ramsey-type theorems can be expressed as the assertion that a certain category (or class of finite structures) has the Ramsey property (defined below).
Structural Ramsey theory began in the 1970s with the work of Nešetřil and Rödl, and is intimately connected to Fraïssé theory. It received some renewed interest in the mid-2000s due to the discovery of the Kechris–Pestov–Todorčević correspondence, which connected structural Ramsey theory to topological dynamics.
History.
 is given credit for inventing the idea of a Ramsey property in the early 70s, and the first publication of this idea appears to be Graham, Leeb and Rothschild's 1972 paper on the subject. Key development of these ideas was done by Nešetřil and Rödl in their series of 1977 and 1983 papers, including the famous Nešetřil–Rödl theorem. This result was reproved independently by Abramson and Harrington, and further generalised by . More recently, Mašulović and Solecki have done some pioneering work in the field.
Motivation.
This article will use the set theory convention that each natural number formula_1 can be considered as the set of all natural numbers less than it: i.e. formula_2. For any set formula_3, an "formula_4-colouring of formula_3" is an assignment of one of formula_4 labels to each element of formula_3. This can be represented as a function formula_8 mapping each element to its label in formula_9 (which this article will use), or equivalently as a partition of formula_10 into formula_4 pieces.
Here are some of the classic results of Ramsey theory:
These "Ramsey-type" theorems all have a similar idea: we fix two integers formula_16 and formula_29, and a set of colours formula_4. Then, we want to show there is some formula_26 large enough, such that for every formula_4-colouring of the "substructures" of size formula_16 inside formula_26, we can find a suitable "structure" formula_3 inside formula_26, of size formula_29, such that all the "substructures" formula_78 of formula_3 with size formula_16 have the same colour.
What types of structures are allowed depends on the theorem in question, and this turns out to be virtually the only difference between them. This idea of a "Ramsey-type theorem" leads itself to the more precise notion of the Ramsey property (below).
The Ramsey property.
Let formula_81 be a category. formula_81 has the "Ramsey property" if for every natural number formula_4, and all objects formula_84 in formula_81, there exists another object formula_86 in formula_81, such that for every formula_4-colouring formula_89, there exists a morphism formula_90 which is formula_21-monochromatic, i.e. the set
is formula_21-monochromatic.
Often, formula_81 is taken to be a class of finite formula_95-structures over some fixed language formula_95, with embeddings as morphisms. In this case, instead of colouring morphisms, one can think of colouring "copies" of formula_3 in formula_86, and then finding a copy of formula_78 in formula_86, such that all copies of formula_3 in this copy of formula_78 are monochromatic. This may lend itself more intuitively to the earlier idea of a "Ramsey-type theorem".
There is also a notion of a dual Ramsey property; formula_81 has the dual Ramsey property if its dual category formula_104 has the Ramsey property as above. More concretely, formula_81 has the "dual Ramsey property" if for every natural number formula_4, and all objects formula_84 in formula_81, there exists another object formula_86 in formula_81, such that for every formula_4-colouring formula_112, there exists a morphism formula_113 for which formula_114 is formula_21-monochromatic.
The Kechris–Pestov–Todorčević correspondence.
In 2005, Kechris, Pestov and Todorčević discovered the following correspondence (hereafter called the KPT correspondence) between structural Ramsey theory, Fraïssé theory, and ideas from topological dynamics.
Let formula_135 be a topological group. For a topological space formula_136, a "formula_135-flow" (denoted formula_138) is a continuous action of formula_135 on formula_136. We say that formula_135 is "extremely amenable" if any formula_135-flow formula_138 on a compact space formula_136 admits a fixed point formula_145, i.e. the stabiliser of formula_146 is formula_135 itself.
For a Fraïssé structure formula_148, its automorphism group formula_149 can be considered a topological group, given the topology of pointwise convergence, or equivalently, the subspace topology induced on formula_149 by the space formula_151 with the product topology. The following theorem illustrates the KPT correspondence:Theorem (KPT). For a Fraïssé structure formula_148, the following are equivalent: