Bootcamp 5 – Ramsey DocCourse Prague 2016 – Mike Pawliuk

The following notes are from the Ramsey DocCourse in Prague 2016. The notes are taken by me and I have edited them. In the process I may have introduced some errors; email me or comment below and I will happily fix them.

Title: Bootcamp 5 (of 8)

Lecturer: Jan Hubička

Date: Friday September 30, 2016.

Main Topics: Rado Graph, Fraïssé’s Theorem, Examples of Fraïssé classes, Ramsey implies Amalgamation, Lifts and Reducts, Ramsey classes have linear orders

Definitions: Extension Property, Ultrahomogeneous, Universal, $\text{Age}(A)$ , Fraïssé class, irreducible structure, Lifts/Expansions and Shadows/reducts.

Bootcamp 1 – Bootcamp 2 – Bootcamp 3 – Bootcamp 4 – Bootcamp 5 – Bootcamp 6 – Bootcamp 7 – Bootcamp 8

Review from Bootcamp 1

In Bootcamp 1 [Link up soon], we looked at the Rado graph $R$ , which can be constructed in numerous ways. We’d like to focus on the extension property of this graph.

Definition. A structure $H$ has the extension property, if for all $A, B$ finite substructures of $H$ with $A \longrightarrow B$ an embedding, and for all finite substructures $A^\prime$ of $H$ with $A \cong A^\prime$ , there is a substructure $B^\prime$ of $H$ such that $B \cong B^\prime$ , and these maps commute.

Fact. The Rado graph has the extension property.

When we specialize to a particular class, the extension property can often be rephrased.

Exercise 1. Show that the extension property for the Rado graph is equivalent to the 1-point extension property: ( $\forall A, B \subset H$ finite and disjoint, $\exists x \in H$ such that there is an edge from $x$ to every vertex in $A$ , and no edge from $x$ to any vertex in $B$ .)

Exercise 2. Give the correct statement of the 1-point extension property for the analogous random Triangle-free graph.

In Bootcamp 1 [Link up soon] we saw that the extension property is enough to prove that the Rado graph has all sorts of nice properties.

Corollary. If $G$ is a countable graph with the extension property, then $G$ is

unique (up to isomorphism),
ultrahomogeneous,
universal.

Definition. A graph $G$ is ultrahomogeneous if $\forall A,B$ finite subgraphs of $G$ with $f: A \longrightarrow B$ an isomorphism, then there is an automorphism $\overline{f}: G \longrightarrow G$ such that $\overline{f}\upharpoonright A = f$ . Sometimes this property is called being homogeneous.

Definition. A graph $G$ is universal (with respect to finite graphs), if every finite graph embeds into $G$ .

Note. All of these definitions can be generalized to a structure $K$ (in a language $L$ ), and the class $\mathcal{C}$ of finite structures in the language $L$ . The corollary holds in this more general setting. See these notes on the Urysohn space as an example of how this works for metric spaces.

Definition. If a countable structure $K$ is the unique countable structure that is ultrahomogeneous and universal with respect to a class $\mathcal{C}$ , we say that $K$ is the generic (countable) structure $K$ (with respect to $\mathcal{C}$ ).

Constructing generic objects

The extension property is one way to construct an ultrahomogeneous, universal object. In Bootcamp 1 [Link soon] we saw that a random process could also generate these objects (and with probability 1 it will have the extension property, and so will be isomorphic to our construction). This is where the name “generic” comes from. We will also see that in some cases, there is an explicit model for these objects.

A random process

For the Rado graph, it is easy to see that starting with a countable vertex set and then assigning each pair an edge with probability $\frac{1}{2}$ will (with probability 1) produce a graph with the extension property.

For other structures, like the generic Triangle-free graph, it is not obvious how this can be achieved through a random process. To see the generic Triangle-free graph achieved through a random process, see this 2008 paper by Vershik-Petrov.

Exercise. Show that the generic (countable) metric space can be achieved through a random process. Hint. Consider $\mathbb{N}\times\mathbb{N}$ matrices.

Two explicit models

The Rado graph has many explicit models. We show one coded by binary strings and another coded by hereditarily finite sets.

Example 1. Let $V = \mathbb{N}$ . We say that there is an edge between $n <m$ iff the $n^{th}$ digit of the binary representation of $m$ is $1$ . For example, there is an edge between 1 and 6 because $6=0\underline{1}1$ and there is an edge between 2 and 6 because $6=01\underline{1}$ , but there is no edge between $0$ and $6$ .

Exercise. Prove that this graph has the extension property, and so is isomorphic to the Rado graph.

Example 2. Let $\mathcal{F}$ be the collection of all hereditarily finite sets. That is, $\mathcal{F} = \bigcup_{n \in \mathbb{N}} H_n$ where $H_0 = \emptyset$ and $H_{n+1} := \mathcal{P}(H_n)$ .

Let $V = \mathcal{F}$ , and say that there is an edge between $A$ and $B$ if $A \in B$ or $B \in A$ .

Exercise. Prove that this graph has the extension property, and so is isomorphic to the Rado graph.

Open Quesiton (Vershik). Give an “explicit” model for the Uryoshn space. (The difficulty here is that the generic metric space for rational distances has an explicit model, but then you complete it to get the Urysohn space.)

The Fraïssé construction

Here we will talk about the construction of these generic structures in general using the Fraïssé construction (or limit).

Definition. Given a (usually countable) structure $A$ , $\text{Age}(A)$ is the class of all finite structures isomorphic to a substructure of $A$ .

Theorem (Fraïssé 1954). A class of finite structures $\mathcal{C}$ is the age of a countable ultrahomogeneous structure $H$ if and only if $\mathcal{C}$

has countably many mutually non-isomorphic structures,
is closed under taking isomorphisms,
is closed under taking substructures (Hereditary Property – HP),
has the Amalgamation Property (AP).

Moreover, if these conditions are satisfied then $H$ is unique up to isomorphism and is called the Fraïssé limit of the class $\mathcal{C}$ , which we denote by $\text{Flim}(\mathcal{C})$ .

Historically we also ask for the JEP (see Bootcamp 4) in this theorem, but this follows from the AP (Exercise). The only non-trivial condition in the list of conditions is the AP.

Definition. A class of finite structures $\mathcal{F}$ with properties (1), (2), HP, JEP and AP is called a Fraïssé class (or an amalgamation class).

The proof of Fraïssé’s Theorem

We give a proof of this theorem using rich sequences, which will explain why we call $\text{Flim}(\mathcal{F})$ a limit. We will describe it as an inverse limit.

In what follows we will fix a Fraïssé class $\mathcal{F}$ .

Definition. An increasing (in terms of substructure) sequence $(A_i)$ of elements of $\mathcal{F}$ is rich if for every $i \in \mathbb{N}$ , $B \in \mathcal{F}$ and embedding $e: A_i \longrightarrow B$ , there is a $j>i$ and an embedding $f: B \longrightarrow A_j$ such that $f \uphookright A_i$ is the identity on $A_i$ .

Exercise (easy). Prove that without loss of generality, a rich sequence contains the empty structure.

Exercise (easy). Prove that for a rich sequence $(A_i)$ , its inverse limit has the extension property. Conclude that any two rich sequences give the same limit.

Exercise (medium). Prove that every Fraïssé class has a rich sequence.

Exercise (easy). Prove the forward direction of Fraïssé’s theorem.

From these four exercises we can conclude Fraïssé’s theorem.

Examples of Fraïssé classes

We now list some examples of Fraïssé classes. Note that because of Fraïssé’s theorem we can give the class of finite structures or equivalently give the Fraïssé limit; it is often convenient to conflate these two notions rather than be completely precise.

Finite linear orders. The limit is $(\mathbb{Q}, \leq)$ . Fraïssé’s theorem can be used to show that this is the unique, countable, dense-in-itself linear order without endpoints.
Rado graph, the generic triangle-free graph.
If $\mathcal{F}$ is a class of irreducible (see below) structures in a language $L$ , then $\text{Forb}(\mathcal{F})$ is the class of finite structures in the language $L$ that don’t have any embeddings of structures from $\mathcal{F}$ . The class $\text{Forb}(\mathcal{F})$ is a Fraïssé class. Henson used this to show that there are uncountably many distinct ultrahomogeneous graphs.
The class of finite metric spaces (with rational distances). To amalgamate and along , take the distance to be . The Fraïssé limit is the rational Urysohn space, whose completion is the universal, ultrahomogeneous separable complete metric space.
1. Exercise 1. Prove that this is a distance.
2. Exercise 2. Prove that in the class of real-valued metric spaces you can amalgamate along compact metric spaces.
The class of complete graphs with edges coloured red, blue or green, with forbidden triangles: red-red-red, red-red-blue, red-green-green.

Exercise. Prove that these classes have the AP.

Definition. A structure $F$ is irreducible if every pairs of points in $F$ is in some relation. (For example, a complete graph is irreducible in the language of graphs.)

Ramsey and the AP (again)

In Bootcamp 4 we gave an indirect proof that every Ramsey class (with JEP and HP) has the AP. That proof went through $\langle A,B,C \rangle$ hypergraphs. Here we provide a more direct proof.

Theorem (Nešetřil, 1980s). Let $\mathcal{K}$ be a Ramsey class (with JEP and HP), then it has the AP.

Proof. Let $A, B, B^\prime \in \mathcal{K}$ such that $A$ embeds into $B$ and $B^\prime$ . Let $B_1$ witness the JEP for $B, B^\prime$ .

Let $C \longrightarrow (B_1)^A_2$ . For $A^\prime \in \binom{C}{A}$ , say that $A^\prime$ has colour 1 if and only if there is an isomorphic copy of $B$ in $C$ that contains $A^\prime$ as a substructure.

Find a monochromatic copy of $B_1$ . Its copy of $B$ guarantees that it will be monochromatic in colour 1. Its copy of $B^\prime$ contains an $A$ , which must also be contains in a copy of $B$ (by virtue of the colouring).

[QED]

The bigger picture

So far we have the following set of loose implications:

Ramsey Class $\longrightarrow$ Amalgamation class $\longrightarrow$ Homogeneous Structure

Here the first association is from Nešetřil’s theorem above. The second association is from Fraïssé’s theorem. Our first question is about whether any of these arrows reverse:

Naïve question. Is every Fraïssé class a Ramsey class?

In Bootcamp 4 we saw that the answer to this is “no” as the class of graphs fails to be Ramsey. Instead we ask the following high-level question:

High-level question. Is there a way to associate to every homogeneous structure a Ramsey class?

This is partly answered by the following observation:

Theorem. Ordered Graphs (i.e. graphs whose vertices are ordered) form a Ramsey class, even though the class of graphs is not.

This lead to the following concrete question:

Question. Which Fraïssé classes become Ramsey when the structures are imbued with arbitrary linear orders?

This lead to Nešetřil’s classification program (see this 2005 paper) of Ramsey classes. While adding linear orders works for many classes, there are many examples where it doesn’t quite work.

Exercise. Prove that the following classes of finite structures are not Ramsey when arbitrary linear orders are added.

Bipartite graphs.
Partial orders.
Acyclic graphs.

Broad question. Is there a way to fix this situation?

Lifts and Reducts

One useful notion is that of a lift and that of a reduct. A lift of a structure is an additional information on that structure, like adding a linear order to the vertices of a graph. A reduct goes the other way and ignores additional information.

Definition. Let $A$ be an $L$ -structure and $L \subseteq L^+$ be a language extending $L$ . Then an $L^+$ structure $A^+$ is a lift (or expansion) of $A$ if

$\mathfrak{dom}(A) = \textrm{dom}(A^+)$ ,
$\forall R \in L, \overline{a} \in R^A$ iff $\overline{a} \in R^{A^+}$ , and
$\forall f \in L, f^A(\overline{a})$ iff $f^{A^+}(\overline{a})$ .

We call $A$ a reduct (or shadow) of $A^+$ .

Lifts allow a more nuanced approach to making a class Ramsey. No longer does one have to only use arbitrary linear orders, as the following theorems show.

Theorem. The following classes of finite structures are Ramsey classes:

Bipartite graphs together with a unary predicate for each part of the bipartition and a linear order that is convex with respect to the parts of the bipartition.
Partial orders together with a linear order that extends the partial order.
Acyclic graphs (i.e. Trees) together with a linear order that extends a tree order.

The following question emerged from many people independently in a Ramsey meeting in Bertruve in 2010.

Question. Does every Fraïssé class have a lift that makes it a Ramsey class?

Observation 1. By adding different unary predicates on every point, every Fraïssé structure has a lift that makes its Age a Ramsey class.

Observation 2. Consider the Fraïssé structure $(\mathbb{N}, d, \leq)$ with its usual distance and ordering. By taking $A$ to be a point and $B$ to be a two point set of distance one, there is no Ramsey structure $C$ because even and odd distance must always appear (Exercise). Adding a lift to this structure that is basically a linear order will not make it a Ramsey class.

Why linear orders?

A natural question is “Why do lifts seem to always be kinds of linear orders?”. The following theorem shows that it is no accident.

Theorem (Kechris-Pestov-Todorcevic, 2005). Let $H$ be an ultrahomogeneous structure in a finite language $L$ such that $\text{Age}(H)$ has the RP. There is a formula (definable from $L$ ) that defines a linear order on $H$ .

Lemma. Every structure in $\text{Age}(H)$ on 2 points is rigid (i.e. its only automorphism is the identity).

Proof of lemma. By contrapositive. Our version of the Ramsey property colours embedings, not substructures. So if a two-point structure is not rigid, it and its reverse are always present when one is. A structure can never be monochromatic in only one of these types.

Proof of theorem. The original proof goes through the extreme amenability of the automorphism group of $H$ . This will be a more direct proof.
Note that since the language is finite, there are only finitely many non-isomorphic structures on two points; call this set $\mathcal{T} = \{T_1, \ldots, T_n\}$ . By the lemma, for each $T_i \in \mathcal{T}$ there is a way to define a linear order $\leq_i$ on it (either the relation itself, or its negation).

We start by defining a linear order on each finite structure $A \in \text{Age}(H)$ , then we will use a compactness argument to extend it to all of $H$ .
[Finite structure] Fix $A \in \text{Age}(H)$ . We use Ramsey $n$ times:

Find $C_1 \longrightarrow (A)_2^{T_1}$ .
Find $C_{k} \longrightarrow (C_{k-1})_2^{T_k}$ , for $2 \leq k \leq n$ .

Now we use the Sierpinski colouring (see Bootcamp 4). Let $\leq$ be an arbitrary linear order on $C_n$ . Consider the Sierpinski colouring on $\binom{C_n}{T_n}$ where a copy of $T_n$ gets the colour $1$ if and only if $\leq = \leq_n$ on $T_n$ . Find a D_{n-1} that is monochromatic with this colouring. Repeat one-by-one until we have a $D_1$ (isomorphic to $A$ ) that is monochromatic with respect to $T_1$ (and all the other $T_k$ ).

Now $D_1$ will be monochromatic with respect to all of the colourings. To define a formula that gives the linear order $\leq$ on $D_1$ it suffices to take (as appropriate for each pair of points) either $\leq_k$ or its reverse, depending on which of the Sierpinski colours $D_k$ was monochromatic with.

Depending on the structure $A$ , there are at most $2^n$ many such formulas might be produced.

[All of $H$ ] To get a linear order on all of $H$ , enumerate the points of $H$ and let $A_i$ be the substructure on the first $i$ points. Since there are only $2^n$ different formulas possible, one formula must appear for infinitely many $i$ . This formula will define a linear order on all of $H$ .

[QED]

In the case that the language $L$ is infinite, we get theorem of a slightly different flavour.

Theorem. Let $H$ be an ultrahomogeneous structure in a (possibly infinite) language $L$ such that $\text{Age}(H)$ has the RP. There is a linear order on $H$ that is fixed by every automorphism.

Proof. This proof will use König’s Lemma to prove a compactness argument.

As in the previous proof, enumerate the points of $H$ to get structures $A_i$ on the first $i$ points. A vertex in the tree is an $A_i$ together with a linear order on it that is fixed by all automorphisms of $H$ . The tree ordering is substructure and order extension.

Since each $A_i$ is finite, there are only finitely many linear orders on it. So each tree level is finite.

Also, each $A_i$ only uses a finite piece of $L$ . So the previous theorem applies, and there is a linear order on $A_i$ that is fixed by all automorphisms, (since the linear order is defined from the structure of $A_i$ , and automorphisms preserve the structure).

So by König’s lemma, there is an infinite branch through this tree, and that gives the desired linear order on all of $H$ .

[QED]

2 thoughts on “Bootcamp 5 – Ramsey DocCourse Prague 2016”

Pingback: Bootcamp 6 – Ramsey DocCourse Prague 2016
Pingback: Bootcamp 3 – Ramsey DocCourse Prague 2016

Review from Bootcamp 1

Constructing generic objects

A random process

Two explicit models

The Fraïssé construction

The proof of Fraïssé’s Theorem

Examples of Fraïssé classes

Ramsey and the AP (again)

The bigger picture

Lifts and Reducts

Why linear orders?

Share this:

Like this:

Related

2 thoughts on “Bootcamp 5 – Ramsey DocCourse Prague 2016”

Leave a Reply Cancel reply