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.
INCOMPLETE: One dimensional proof of copies of , copies of .
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.
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.
This leads to one possible fix:
The answer to this is “No”, as we saw with the example in Bootcamp 5. So we alter the question again.
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.
The following theorem refines our search a little bit.
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 -free graph (for ).
- copies of (where )
- Complements of these graphs. (Omitting independent sets, -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 . 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 -free graphs
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.
This uses the free-amalgamation property of hypergraphs, and to a certain extent is all it needs.
For example, the class of 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 -free graphs are both Free-amalgamation classes.
We distinguish the cases of copies of and copies of .
One copy of is covered by a single linear order. (This is the classical Ramsey theorem.)
Let’s call two copies of the structure . First, it’s straightforward to check that adding arbitrary linear orders does not produce a Ramsey class
Proof. Let be the equivalence relation in of “there is an edge between and “.
Let where and . Let where , the only relation is , and .
Let be an ordered subgraph of . Enumerate the equivalence classes of by . Define as follows (Increasing and Decreasing). For with , define if and only if $x^\prime
Let where where , and .
Note that so and are in the same equivalence class. Therefore .
This proof actually showed a more general fact.
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 is an equivalence formula if it is symmetric, transitive and reflexive on all tuples where is true.
We say that two tuples have the same strong type if they have the same type and for all equivalence formulas we have that .
Now we know that arbitrary linear orders don’t work, we modify this slightly.
Definition. In a graph , we say that two vertices if there is no edge between and .
Let be an equivalence relation defined on a structure . A linear order defined on the domain of is convex (with respect to ) if whenever and then . In this case, with a fixed convex order , it is well defined to say that one equivalence class comes before another.
Proof of theorem using one-dimensional Ramsey. We present an alternative proof that does not use the product argument.
The arguments above clearly extend to copies of .
In this case we can just use our previous cases as follows.
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 convex ordered subgraphs of . Let be the number of edge-equivalence classes of .
- Find an such that .
- Construct as a union of complete graphs, each of size .
- Enumerate by the edge-equivalence classes of .
- Add unary predicates to and .
In this case the size of will be a fixed finite number. Call this class . 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 .
In the case of a finite substructure in , completes every vertex to a copy of , so that is a union of . Note that in this class, if is finite, then is finite. This is not true in the class of copies of .
To prove ordered Ramsey we will assume our underlying graphs are equivalence closed.
Proof. Start with expansions . 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 .
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.
Summary of Ramsey expansions for graphs
- The Rado graph. Expansion is arbitrary linear orders.
- The random -free graph (for ). Expansion is arbitrary linear orders.
- copies of (where ). 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.
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.
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.