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 structures.
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[1] 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.
Leeb [de] is given credit[2] for inventing the idea of a Ramsey property in the early 70s.
The first publication of this idea appears to be Graham, Leeb and Rothschild's 1972 paper on the subject.
[3] Key development of these ideas was done by Nešetřil and Rödl in their series of 1977[4] and 1983[5] papers, including the famous Nešetřil–Rödl theorem.
This result was reproved independently by Abramson and Harrington,[6] and further generalised by Prömel [de].
[7] More recently, Mašulović[8][9][10] and Solecki[11][12][13] have done some pioneering work in the field.
This article will use the set theory convention that each natural number
can be considered as the set of all natural numbers less than it: i.e.
labels to each element of
This can be represented as a function
mapping each element to its label in
(which this article will use), or equivalently as a partition of
Here are some of the classic results of Ramsey theory: These "Ramsey-type" theorems all have a similar idea: we fix two integers
-colouring of the "substructures" of size
, we can find a suitable "structure"
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).
has the Ramsey property if for every natural number
In this case, instead of colouring morphisms, one can think of colouring "copies" of
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;
has the dual Ramsey property if its dual category
has the dual Ramsey property if for every natural number
In 2005, Kechris, Pestov and Todorčević[14] discovered the following correspondence (hereafter called the KPT correspondence) between structural Ramsey theory, Fraïssé theory, and ideas from topological dynamics.
admits a fixed point
can be considered a topological group, given the topology of pointwise convergence, or equivalently, the subspace topology induced on
The following theorem illustrates the KPT correspondence:Theorem (KPT).