Bootcamp 7 – Ramsey DocCourse Prague 2016

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 3Bootcamp 4Bootcamp 5Bootcamp 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:

  1. The Rado graph.
  2. The random K_n -free graph (for n \geq 3 ).
  3. t copies of K_n (where t,k \leq \omega )
  4. 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 .

ab_noedges

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 .

  1. Find an N such that N \longrightarrow (p(B))_2^{p(A)} .
  2. Construct B^\prime as a union of N complete graphs, each of size \vert B \vert .
  3. Enumerate by A_1, A_2, \ldots, A_n the edge-equivalence classes of A .
  4. 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

  1. The Rado graph. Expansion is arbitrary linear orders.
  2. The random K_n -free graph (for n \geq 3 ). Expansion is arbitrary linear orders.
  3. t copies of K_n (where t,k \leq \omega ). Convex linear orders (infinite parts) and unary predicates (finite parts).
  4. 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:

  1. An infinite antichain.
  2. An antichain of chains.
  3. A chain of antichains.
  4. 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:

  1. An infinite antichain. Expansion is arbitrary linear orders.
  2. An antichain of chains. Expansion is convex linear orders.
  3. A chain of antichains. Expansion is convex linear orders.
  4. 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”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s