Bootcamp 7 – 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 7 (of 8)

Lecturer: Jan Hubička

Date: Monday October 10, 2016.

Main Topics: “Correct” definition of Ramsey expansion, Ramsey lifts/expansions of graphs, Ramsey lifts/expansions of posets.

Definitions: Precompact expansion, Expansion property, Free Amalgamation, strong type, equivalence formula, equivalence closure, interpretation in a model.

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

INCOMPLETE: One dimensional proof of $t$ copies of $K_\omega$ , $\omega$ copies of $K_\omega$ .

Introduction

Today’s lecture will be a continuation of Bootcamp 5. In that lecture we saw the concept of an expansion of a class that makes it into a Ramsey class. For example, the class of graphs is not Ramsey (for paths of length 2) but the class of ordered graphs is.

We will also discuss what definition of Ramsey expansion is appropriate for the question “Does every homogeneous class have a Ramsey expansion?”. As we saw last time, this question can have a trivial “Yes” answer if we also infinitely many unary predicates.

After that we will see what the Ramsey expansions are for all possible homogeneous classes of graphs and all possible homogeneous classes of posets.

The correct definition for Ramsey expansion

We saw that the class of graphs is not Ramsey, but the class of ordered graphs is. This leads to a general question.

Question 0. Does every homogeneous structure have a Ramsey expansion?

Morally, this is the correct question, but it has a trivial answer of “Yes”. We can add a unary predicate to each point and kill Ramsey. This guides us towards being more careful about our definition of an acceptable expansion.

Fix (Bodirsky, Pinsker). We should look at languages with only finitely many relations.

Definition (Nyguen van Thé). Let $\mathcal{C}^\star$ be an expansion of the class $\mathcal{C}$ . We say that $\mathcal{C}^\star$ is a precompact expansion of $\mathcal{C}$ if every structure $C \in \mathcal{C}$ has only finitely many expansions in $\mathcal{C}^\star$ .

This leads to one possible fix:

Question 1. Does every homogeneous structure have a precompact Ramsey expansion?

The answer to this is “No”, as we saw with the example $(\mathbb{N}, d)$ in Bootcamp 5. So we alter the question again.

Question 2. Does every homogeneous structure in a finite language have a Ramsey expansion?

Main Question. Does every homogeneous $\omega$ -categorical structure have a precompact Ramsey expansion?

So far the answer to Question 2 is “Maybe” and the answer to the Main Question is a subtle “No”. We will see a construction of the counterexample in one of the later talks.)

We will also have need for the following definition which generalizes the Ordering property we saw in Bootcamp 4.

Definition . Let $\mathcal{C}^\star$ be an expansion of the class $\mathcal{C}$ . We say that $\mathcal{C}^\star$ has the expansion property (with respect to $\mathcal{C}$ ) if for every $A \in \mathcal{C}$ there is a $B \in \mathcal{C}^\star$ such that every expansion $B^\star\in \mathcal{C}^\star$ of $B$ contains a copy of every expansion $A^\star \in \mathcal{C}^\star$ of $A$ .

The following theorem refines our search a little bit.

Theorem (KPT 2005). For every homogeneous structure $H$ there is at most one precompact Ramsey expansion with the expansion property (up to bi-definability).

This was first proved using topological dynamics. We will see a proof of this in one of the later lectures.

The classification of homogeneous graphs

Theorem (Lauchlan-Woodrow 1984). Every infinite countable homogeneous graph is isomorphic to one of the following:

The Rado graph.
The random $K_n$ -free graph (for $n \geq 3$ ).
$t$ copies of $K_n$ (where $t,k \leq \omega$ )
Complements of these graphs. (Omitting independent sets, $n$ -partite graphs)

Note that this also gives a complete classification of all Fraïssé classes of graphs, from the correspondence of Fraïssé’s theorem of homogeneous structures and their $\text{Age}$ . We will freely confuse these two notions when it is convenient.

We can now ask our main question about these graphs.

The class of all finite graphs, and $K_n$ -free graphs

Theorem (Abramson-Harrington 1978, Nešetřil-Rödl 1977). Ordered finite graphs are a Ramsey class.

The proofs were discovered independently and are from different perspectives. We saw a proof of this theorem in Bootcamp 4. The Nešetřil-Rödl construction uses the bipartite construction. The Nešetřil-Rödl paper actually says something more.

Theorem (Nešetřil-Rödl 1977). For ordered finite hypergraphs $A,B$ there is an ordered finite hypergraph $C$ such that $C \longrightarrow (B)^A_2$ . Moreover, if $B$ omits some irreducible hypergraph $F$ then $C$ can be constructed to omit $F$ .

This uses the free-amalgamation property of hypergraphs, and to a certain extent is all it needs.

Definition. Let $\mathcal{C}$ be a relational class. We say that $\mathcal{C}$ has the Free-Amalgamation Property (FAP) if, as in the amalgamation property, you can always amalgamate $B_1, B_2$ to $C$ along a common $A$ , but in addition $C$ has no new relations. That is, all relations in the amalgam come from $B_1$ or $B_2$ .

For example, the class of $\{K_n : n \in \omega\}$ has (AP) but not (FAP). If you amalgamate two edges along a common point you will need to add a third edge to stay in the class.

Note that the class of all graphs, and the class of all $K_n$ -free graphs are both Free-amalgamation classes.

Theorem (Nešetřil-Rödl 1977). If $\mathcal{C}$ is a free-amalgamation class, then $\mathcal{C}$ with arbitrary linear orders is a (precompact) Ramsey class.

Copies of $K_n$

We distinguish the cases of $t$ copies of $K_\omega$ and $\omega$ copies of $K_n$ .

$t$ copies of $K_\omega$

One copy of $K_\omega$ is covered by a single linear order. (This is the classical Ramsey theorem.)

Let’s call two copies of $K_\omega$ the structure $C_2$ . First, it’s straightforward to check that adding arbitrary linear orders does not produce a Ramsey class

Fact. Show that ordered graphs from $\text{Age}(C_2)$ is not a Ramsey class.

Proof. Let $R(a,b)$ be the equivalence relation in $C_2$ of “there is an edge between $a$ and $b$ “.

Let $\mathbb{A} = (A, R^A, \leq^A)$ where $A = \{x,y\}, x R^A y$ and $x <^A y$ . Let $\mathbb{B} = (B, R^B, \leq^B)$ where $B = \{a,b,c\}$ , the only relation is $a R^B c$ , and $a \leq^B b \leq^B c$ .

Let $\mathbb{C}$ be an ordered subgraph of $C_2$ . Enumerate the equivalence classes of $\mathbb{C}$ by $<_R$ . Define $\chi: \binom{\mathbb{C}}{\mathbb{A}} \longrightarrow \{I,D\}$ as follows (Increasing and Decreasing). For $A^\prime = \{x^\prime, y^\prime\}$ with $x^\prime <^{A^\prime} y^\prime$ , define $\chi(\mathbb{A}^\prime) := I$ if and only if $x^\prime

Let $\mathbb{B}^\prime \leq \mathbb{C}$ where $\mathbb{B} \cong \mathbb{B}^\prime = (B^\prime, R^{B^\prime}, \leq^{B^\prime})$ where $B^\prime = (a^\prime,b^\prime,c^\prime)$ , $a^\prime R^{B^\prime} c^\prime$ and $a^\prime \leq^{B^\prime} b^\prime \leq^{B^\prime} c^\prime$ .

Note that $a^\prime R c^\prime$ so $a^\prime$ and $c^\prime$ are in the same equivalence class. Therefore $\chi(\mathbb{B}^\prime \upharpoonright \{a^\prime,b^\prime\}) \neq \chi(\mathbb{B}^\prime \upharpoonright \{b^\prime,c^\prime\})$ .

This proof actually showed a more general fact.

Fact. Let $\mathcal{C}$ be a structure with a definable equivalence relation. The class of (arbitrarily) ordered structures from $\mathcal{C}$ is not a Ramsey class.

We use this opportunity to describe strong types of a structure. The motivating observation is that in a homogeneous structure the type of a structure depends only on its isomorphism class.

Definition. Fix a class. A formula $\phi(\overline{a}, \overline{b})$ is an equivalence formula if it is symmetric, transitive and reflexive on all tuples where $\phi(\overline{a}, \overline{b})$ is true.

We say that two tuples $\overline{a}, \overline{b}$ have the same strong type if they have the same type and for all equivalence formulas $\phi$ we have that $\phi(\overline{a}, \overline{b})$ .

Fact. In a Ramsey class, strong types are given by isomorphism types.

Now we know that arbitrary linear orders don’t work, we modify this slightly.

Theorem. The Ramsey expansion of $C_2$ is convex linear orders with a unary predicate for each of the two edge-equivalence classes.

Definition. In a graph $G = (V,E)$ , we say that two vertices $v_1 \perp v_2$ if there is no edge between $v_1$ and $v_2$ .

Let $R$ be an equivalence relation defined on a structure $A$ . A linear order $\leq$ defined on the domain of $A$ is convex (with respect to $R$ ) if whenever $a \leq b \leq c$ and $R(a,c)$ then $R(a,b)$ . In this case, with a fixed convex order $\leq$ , it is well defined to say that one equivalence class comes before another.

Proof of theorem using products. One approach to proving this result is to use a product argument (as in the proof of Hilbert’s theorem). The proof is very similar to the proof of Hilbert’s theorem, chain-Ramsey for posets and the use in Hales-Jewett. In particular, since the linear order is convex (and fixed) there is only one way to append an additional equivalence class.

Proof of theorem using one-dimensional Ramsey. We present an alternative proof that does not use the product argument.

[INCOMPLETE]

The arguments above clearly extend to $t$ copies of $K_\omega$ .

$\omega$ copies of $K_\omega$

In this case we can just use our previous cases as follows.

Theorem. The Ramsey expansion of $C_\omega$ is a convex linear orders.

Proof. The idea is that unary predicates, in the limit, just becomes an ordering on the equivalence classes. We can use an ordering on the equivalence classes to induce unary predicates on a finite substructure. This allows us to find Ramsey witnesses without increasing the dimension (i.e. number of equivalence classes).

Fix $A,B$ convex ordered subgraphs of $C_\omega$ . Let $p(A), p(B)$ be the number of edge-equivalence classes of $A,B$ .

Find an $N$ such that $N \longrightarrow (p(B))_2^{p(A)}$ .
Construct $B^\prime$ as a union of $N$ complete graphs, each of size $\vert B \vert$ .
Enumerate by $A_1, A_2, \ldots, A_n$ the edge-equivalence classes of $A$ .
Add unary predicates to $B^\prime$ and $A_1, \ldots, A_n$ .

[INCOMPLETE]

$\omega$ copies of $K_n$

In this case the size of $n$ will be a fixed finite number. Call this class $\mathcal{C}_{\omega, n}$ . Before we describe the Ramsey expansion, it we be useful to describe a closure operator that fills in disjoint unions of graphs to disjoint unions of $K_n$ .

Definition. Let $\mathcal{C}$ be a class with an equivalence formula $\phi$ . The equivalence closure $\text{alc}_\mathcal{C}(S)$ is the unique substructure induced by the set of vertices $\{h : \exists s \in S, \phi(s,h)\}$ .

In the case of a finite substructure $S$ in $\mathcal{C}_{\omega, n}$ , $\text{alc}(A)$ completes every vertex to a copy of $K_n$ , so that $\text{alc}(A)$ is a union of $K_n$ . Note that in this class, if $A$ is finite, then $\text{alc}(A)$ is finite. This is not true in the class of $t$ copies of $K_\omega$ .

To prove ordered Ramsey we will assume our underlying graphs are equivalence closed.

Theorem. The Ramsey expansion of $\mathcal{C}_{\omega, n}$ is the an ordering of the equivalence classes together with at most $n$ distinct unary predicates on each equivalence class.

Proof. Start with expansions $A,B$ . Assume without loss of generality that they are equivalence closed (where, if needed, the unary predicates are added to the closure in an injective way).

Now quotient by each equivalence class, so that we are left with a linear order on an independent set. Use classical Ramsey here then project back up to ordered $\mathcal{C}_{\omega, n}$ .

Complements

The only thing left to do is deal with the complements of the previous classes. However, this is immediate from the way Ramsey theorems behave on complements.

Exercise. If $\mathcal{C}$ is a Ramsey class of graphs, and $\mathcal{D}$ is the collection of complement graphs of $\mathcal{C}$ , then $\mathcal{D}$ is also a Ramsey class.

Summary of Ramsey expansions for graphs

The Rado graph. Expansion is arbitrary linear orders.
The random $K_n$ -free graph (for $n \geq 3$ ). Expansion is arbitrary linear orders.
$t$ copies of $K_n$ (where $t,k \leq \omega$ ). Convex linear orders (infinite parts) and unary predicates (finite parts).
Complements of these graphs. Same as their complement.

The classification of homogeneous posets

Theorem (Schur ??). Every infinite countable homogeneous poset is isomorphic to one of the following:

An infinite antichain.
An antichain of chains.
A chain of antichains.
The generic poset.

Rather than prove everything by hand we will use the notion of interpretation in a model to transfer the Ramsey expansions of graphs to Ramsey expansions of posets.

Definition. An $L$ -structure $A$ has interpretation in $B$ if there is a $\phi(\overline{a})$ from the domain of $A$ to the domain of $B$ such that for every $R \in L$ the formula $\phi_R (a_1, \ldots, a_n)$ defines the relation in $B$ .

Fact. If $A$ is $\omega$ -categorical and has a precompact Ramsey expansion, then all structures interpreted in $A$ have a precompact Ramsey expansion.

This will allow us to think of posets as graphs for the second and third example.

Theorem. The Ramsey expansion for each homogeneous poset:

An infinite antichain. Expansion is arbitrary linear orders.
An antichain of chains. Expansion is convex linear orders.
A chain of antichains. Expansion is convex linear orders.
The generic poset. Expansion is linear extensions of the poset ordering. (Nešetřil-Rödl 1984, Paoli-Trotter-Walker 1985, [another recent proof])

Now we will use interpretation the other way (thinking of graphs as posets) to get another Ramsey expansion. We first introduced interval graphs in Bootcamp 3.

Corollary. The class of all interval graphs has a precompact Ramsey expansion.

To see this we interpret each interval graph in a linear order, whose Ramsey expansion we know by above. This is kind of surprising since the natural attempt to give a Ramsey expansion of this class results in an infinite language.

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

Pingback: Bootcamp 4 – Ramsey DocCourse Prague 2016
Pingback: Bootcamp 8 – Ramsey DocCourse Prague 2016

Introduction

The correct definition for Ramsey expansion

The classification of homogeneous graphs

The class of all finite graphs, and -free graphs

Copies of

copies of

copies of

copies of

Complements

Summary of Ramsey expansions for graphs

The classification of homogeneous posets

Share this:

Like this:

Related

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

Leave a Reply Cancel reply

The class of all finite graphs, and $K_n$ -free graphs

Copies of $K_n$

$t$ copies of $K_\omega$

$\omega$ copies of $K_\omega$

$\omega$ copies of $K_n$