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.

Introduction

Let us recall some of the classic results of Ramsey theory:

• (Finite) Ramsey's theorem: for every $k\leq m,r\in \mathbb {N}$, there exists $n\in \mathbb {N}$ such that for every $r$-colouring $\Delta :[n]^{(k)}\to r$ of all the $k$-element subsets of $n=\{0,1,\ldots ,n-1\}$, there exists a subset $A\subseteq n$, with $|A|=m$, such that $[A]^{(k)}$ is $\Delta$-monochromatic.
• (Finite) van der Waerden's theorem: for every $m,r\in \mathbb {N}$, there exists $n\in \mathbb {N}$ such that for every $r$-colouring $\Delta :n\to r$ of $n$, there exists a $\Delta$-monochromatic arithmetic progression $\{a,a+d,a+2d,\ldots ,a+(m-1)d\}\subseteq n$ of length $m$.
• Graham-Rothschild theorem: fix a finite alphabet $L=\{a_{0},a_{1},\ldots ,a_{d-1}\}$. A $k$-parameter word of length $n$ over $L$ is an element $w\in (L\cup \{x_{0},x_{1},\ldots ,x_{k-1}\})^{n}$, such that all of the $x_{i}$ appear, and their first appearances are in increasing order. $\textstyle [L]{\binom {n}{k}}$ denotes the set of all $k$-parameter words of length $n$ over $L$. Given $\textstyle w\in [L]{\binom {n}{m}}$ and $\textstyle v\in [L]{\binom {m}{k}}$, we form their composition $\textstyle w\circ v\in [L]{\binom {n}{k}}$ by replacing every occurrence of $x_{i}$ in $w$ with the $i$th entry of $v$. Then, the Graham-Rothschild theorem states that for every $k\leq m,r\in \mathbb {N}$, there exists $n\in \mathbb {N}$ such that for every $r$-colouring $\textstyle \Delta :[L]{\binom {n}{k}}\to r$ of all the $k$-parameter words of length $n$, there exists $\textstyle w\in [L]{\binom {n}{m}}$, such that $\textstyle w\circ [L]{\binom {m}{k}}=\{w\circ v:v\in [L]{\binom {m}{k}}\}$ (i.e. all the $k$-parameter subwords of $w$) is $\Delta$-monochromatic.
• (Finite) Folkman's theorem: for every $m,r\in \mathbb {N}$, there exists $n\in \mathbb {N}$ such that for every $r$-colouring $\Delta :n\to r$ of $n$, there exists a subset $A\subseteq n$, with $|A|=m$, such that $\textstyle {\big (}\sum _{k\in A}k{\big )}<n$, and $\textstyle \mathrm {FS} (A)=\{\sum _{k\in B}k:B\in {\mathcal {P}}(A)\setminus \varnothing \}$ is $\Delta$-monochromatic.

One can observe that these "Ramsey-type" theorems all have a similar idea: we fix two integers $k$ and $m$, and a set of colours $r$. Then, we want to show there is some $n$ large enough, such that for every $r$-colouring of the "substructures" of size $k$ inside $n$, we can find a suitable "structure" $A$ inside $n$, of size $m$, such that all the "substructures" $B$ of $A$ with size $k$ 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 $\mathbf {C}$ be a category. We say that $\mathbf {C}$ has the Ramsey property if for every natural number $r$, and all objects $A,B$ in $\mathbf {C}$, there exists another object $D$ in $\mathbf {C}$, such that for every $r$-colouring $\Delta :\mathrm {Hom} (A,D)\to r$, there exists a morphism $f:B\to D$ which is $\Delta$-monochromatic, i.e. the set

$f\circ \mathrm {Hom} (A,B)={\big \{}f\circ g:g\in \mathrm {Hom} (A,B){\big \}}$

is $\Delta$-monochromatic.

Often, $\mathbf {C}$ is taken to be a class of finite ${\mathcal {L}}$-structures over some fixed language ${\mathcal {L}}$, with embeddings as morphisms. In this case, instead of colouring morphisms, we can think of colouring "copies" of $A$ in $D$, and then finding a copy of $B$ in $D$, such that all copies of $A$ in our copy of $B$ 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; $\mathbf {C}$ has the dual Ramsey property if its dual category $\mathbf {C} ^{\mathrm {op} }$ has the Ramsey property as above. More concretely:

$\mathbf {C}$ has the dual Ramsey property if for every natural number $r$, and all objects $A,B$ in $\mathbf {C}$, there exists another object $D$ in $\mathbf {C}$, such that for every $r$-colouring $\Delta :\mathrm {Hom} (D,A)\to r$, there exists a morphism $f:D\to B$ for which $\mathrm {Hom} (B,A)\circ f$ is $\Delta$-monochromatic.

Examples

• Ramsey's theorem: the class of all finite chains, with order-preserving maps as morphisms, has the Ramsey property.
• van der Waerden's theorem: in the category whose objects are finite ordinals, and whose morphisms are affine maps $x\mapsto a+dx$ for $a,d\in \mathbb {N}$, $d\neq 0$, the Ramsey property holds for $A=1$.

History

Leeb 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 Prömel. More recently, Mašulović and Solecki have done some pioneering work in the field.

The Kechris-Pestov-Todorčević correspondence

In 2005, Kechris, Pestov and Todorčević discovered a correspondence (hereafter called the KPT correspondence) between structural Ramsey theory, Fraïssé theory, and ideas from topological dynamics, which we explain here.

Let $G$ be a topological group. For a topological space $X$, a $G$-flow (denoted $G\curvearrowright X$) is a continuous action of $G$ on $X$. We say that $G$ is extremely amenable if any $G$-flow $G\curvearrowright X$ on a compact space $X$ admits a fixed point $x\in X$, i.e. the stabiliser of $x$ is $G$ itself.

For a Fraïssé structure $\mathbf {F}$, its automorphism group $\mathrm {Aut} (\mathbf {F} )$ can be considered a topological group, given the topology of pointwise convergence, or equivalently, the subspace topology induced on $\mathrm {Aut} (\mathbf {F} )$ by the space $\mathbf {F} ^{\mathbf {F} }=\{f:\mathbf {F} \to \mathbf {F} \}$ with the product topology. The following theorem illustrates the KPT correspondence:

Theorem (KPT). For a Fraïssé structure $\mathbf {F}$, the following are equivalent:

1. The group $\mathrm {Aut} (\mathbf {F} )$ of automorphisms of $\mathbf {F}$ is extremely amenable.
2. The class $\mathrm {Age} (\mathbf {F} )$ has the Ramsey property.

See also

• Ramsey theory
• Fraïssé's theorem
• Age (model theory)

References

Category:Ramsey theory Category:Category theory Category:Model theory