Structural Ramsey theory explained

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.

History

is given credit 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.[2] Key development of these ideas was done by Nešetřil and Rödl in their series of 1977[3] and 1983[4] papers, including the famous Nešetřil–Rödl theorem. This result was reproved independently by Abramson and Harrington,[5] and further generalised by .[6] More recently, Mašulović[7] [8] [9] and Solecki[10] [11] [12] have done some pioneering work in the field.

Motivation

This article will use the set theory convention that each natural number

n\inN

can be considered as the set of all natural numbers less than it: i.e.

n=\{0,1,\ldots,n-1\}

. For any set

A

, an

r

-colouring of

A

is an assignment of one of

r

labels to each element of

A

. This can be represented as a function

\Delta:A\tor

mapping each element to its label in

r=\{0,1,\ldots,r-1\}

(which this article will use), or equivalently as a partition of

A=A0\sqcup\sqcupAr-1

into

r

pieces.

Here are some of the classic results of Ramsey theory:

k\leqm,r\inN

, there exists

n\inN

such that for every

r

-colouring

\Delta:[n](k)\tor

of all the

k

-element subsets of

n=\{0,1,\ldots,n-1\}

, there exists a subset

A\subseteqn

, with

|A|=m

, such that

[A](k)

is

\Delta

-monochromatic.

m,r\inN

, there exists

n\inN

such that for every

r

-colouring

\Delta:n\tor

of

n

, there exists a

\Delta

-monochromatic arithmetic progression

\{a,a+d,a+2d,\ldots,a+(m-1)d\}\subseteqn

of length

m

.

L=\{a0,a1,\ldots,ad-1\}

. A

k

-parameter word of length

n

over

L

is an element

w\in(L\cup\{x0,x1,\ldots,xk-1\})n

, such that all of the

xi

appear, and their first appearances are in increasing order. The set of all

k

-parameter words of length

n

over

L

is denoted by

style[L]\binom{n}{k}

. Given

stylew\in[L]\binom{n}{m}

and

stylev\in[L]\binom{m}{k}

, we form their composition

stylew\circv\in[L]\binom{n}{k}

by replacing every occurrence of

xi

in

w

with the

i

th entry of

v

.
Then, the Graham–Rothschild theorem states that for every

k\leqm,r\inN

, there exists

n\inN

such that for every

r

-colouring

style\Delta:[L]\binom{n}{k}\tor

of all the

k

-parameter words of length

n

, there exists

stylew\in[L]\binom{n}{m}

, such that

stylew\circ[L]\binom{m}{k}=\{w\circv:v\in[L]\binom{m}{k}\}

(i.e. all the

k

-parameter subwords of

w

) is

\Delta

-monochromatic.

m,r\inN

, there exists

n\inN

such that for every

r

-colouring

\Delta:n\tor

of

n

, there exists a subset

A\subseteqn

, with

|A|=m

, such that

style(\sumkk)<n

, and

style\operatorname{FS}(A)=\{\sumkk:B\inl{P}(A)\setminus\varnothing\}

is

\Delta

-monochromatic.

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

C

be a category.

C

has the Ramsey property if for every natural number

r

, and all objects

A,B

in

C

, there exists another object

D

in

C

, such that for every

r

-colouring

\Delta:\operatorname{Hom}(A,D)\tor

, there exists a morphism

f:B\toD

which is

\Delta

-monochromatic, i.e. the set

f\circ\operatorname{Hom}(A,B)=\{f\circg:g\in\operatorname{Hom}(A,B)\}

is

\Delta

-monochromatic.[9]

Often,

C

is taken to be a class of finite

l{L}

-structures over some fixed language

l{L}

, with embeddings as morphisms. In this case, instead of colouring morphisms, one 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 this 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;

C

has the dual Ramsey property if its dual category

Cop

has the Ramsey property as above. More concretely,

C

has the dual Ramsey property if for every natural number

r

, and all objects

A,B

in

C

, there exists another object

D

in

C

, such that for every

r

-colouring

\Delta:\operatorname{Hom}(D,A)\tor

, there exists a morphism

f:D\toB

for which

\operatorname{Hom}(B,A)\circf

is

\Delta

-monochromatic.

Examples

x\mapstoa+dx

for

a,d\inN

,

d0

, the Ramsey property holds for

A=1

.

let

L

be a finite alphabet, and for each

k\inN

, let

Xk=\{x0,\ldots,xk-1\}

be a set of

k

variables. Let

GR

be the category whose objects are

Ak=L\cupXk

for each

k\inN

, and whose morphisms

An\toAk

, for

n\geqk

, are functions

f:Xn\toAk

which are rigid and surjective on

Xk\subseteqAk=\operatorname{codom}f

. Then,

GR

has the dual Ramsey property for

A=A0

(and

B=A1

, depending on the formulation).

GR

defined above has the dual Ramsey property.

The Kechris–Pestov–Todorčević correspondence

In 2005, Kechris, Pestov and Todorčević[13] discovered the following correspondence (hereafter called the KPT correspondence) between structural Ramsey theory, Fraïssé theory, and ideas from topological dynamics.

Let

G

be a topological group. For a topological space

X

, a

G

-flow
(denoted

G\curvearrowrightX

) is a continuous action of

G

on

X

. We say that

G

is extremely amenable if any

G

-flow

G\curvearrowrightX

on a compact space

X

admits a fixed point

x\inX

, i.e. the stabiliser of

x

is

G

itself.

F

, its automorphism group

\operatorname{Aut}(F)

can be considered a topological group, given the topology of pointwise convergence, or equivalently, the subspace topology induced on

\operatorname{Aut}(F)

by the space

FF=\{f:F\toF\}

with the product topology. The following theorem illustrates the KPT correspondence:
Theorem (KPT). For a Fraïssé structure

F

, the following are equivalent:
  1. The group

\operatorname{Aut}(F)

of automorphisms of

F

is extremely amenable.
  1. The class

\operatorname{Age}(F)

has the Ramsey property.

See also

Notes and References

  1. Van Thé. Lionel Nguyen. 2014-12-10. A survey on structural Ramsey theory and topological dynamics with the Kechris–Pestov–Todorcevic correspondence in mind. 1412.3254. math.CO.
  2. Graham . R. L.. Leeb . K.. Rothschild . B. L.. 1972. Ramsey's theorem for a class of categories. Advances in Mathematics. 8. 3. 417–433. 10.1016/0001-8708(72)90005-9. free. 0001-8708.
  3. Nešetřil. Jaroslav. Rödl. Vojtěch. May 1977. Partitions of finite relational and set systems. Journal of Combinatorial Theory, Series A. 22. 3. 289–312. 10.1016/0097-3165(77)90004-8. 0097-3165. free.
  4. Nešetřil. Jaroslav. Rödl. Vojtěch. 1983-03-01. Ramsey classes of set systems. Journal of Combinatorial Theory, Series A. 34. 2. 183–201. 10.1016/0097-3165(83)90055-9. 0097-3165. free.
  5. Abramson. Fred G.. Harrington. Leo A.. September 1978. Models Without Indiscernibles. The Journal of Symbolic Logic. 43. 3. 572. 10.2307/2273534. 0022-4812. 2273534. 1101279.
  6. Prömel. Hans Jürgen. July 1985. Induced partition properties of combinatorial cubes. Journal of Combinatorial Theory, Series A. 39. 2. 177–208. 10.1016/0097-3165(85)90036-6. 0097-3165. free.
  7. Masulovic . Dragan. Scow . Lynn. 2017. Categorical equivalence and the Ramsey property for finite powers of a primal algebra. Algebra Universalis. 78. 2. 159–179. 10.1007/s00012-017-0453-0. 1506.01221. 125159388.
  8. Masulovic . Dragan. 2018. Pre-adjunctions and the Ramsey property. European Journal of Combinatorics. 70. 268–283. 10.1016/j.ejc.2018.01.006. 1609.06832. 19216185.
  9. Mašulović . Dragan. 2020. On Dual Ramsey Theorems for Relational Structures. Czechoslovak Mathematical Journal. 70. 2. 553–585. 10.21136/CMJ.2020.0408-18. 1707.09544. 125310940.
  10. Solecki. Sławomir. August 2010. A Ramsey theorem for structures with both relations and functions. Journal of Combinatorial Theory, Series A. 117. 6. 704–714. 10.1016/j.jcta.2009.12.004. 0097-3165. free.
  11. Solecki. Slawomir. 2011-04-20. Abstract approach to finite Ramsey theory and a self-dual Ramsey theorem. 1104.3950. math.CO.
  12. Solecki. Sławomir. 2015-02-16. Dual Ramsey theorem for trees. 1502.04442. math.CO.
  13. Kechris. A. S.. Pestov. V. G.. Todorcevic. S.. February 2005. Fraïssé Limits, Ramsey Theory, and topological dynamics of automorphism groups. Geometric and Functional Analysis. 15. 1. 106–189. 10.1007/s00039-005-0503-1. 6937893. 1016-443X.