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.
Special thanks to Matěj Konečný for helpful feedback.
Title: Bootcamp 4 (of 8)
Lecturer: Jaroslav Nešetřil
Date: Monday September 26, 2016.
Main Topics: Graphs have the ordering property, Ordered Edge-Ramsey implies Ordering property, Graphs are not Ramsey, Amalgamation for Ramsey classes, the product argument, Hilbert’s Theorem.
Definitions: Joint Embedding Property, Amalgamation Property, statement of Hilbert’s Theorem.
The ordering property for some classes of graphs
In Bootcamp 3 we defined the ordering property. We will show that various classes of graphs have this property.
Let be one of the following classes of finite graphs:
- All graphs,
- all triangle-free graphs,
- all -free graphs,
- all graphs not containing any finite set of forbidden -connected (i.e. no cut points) subgraphs.
Much like the proof that these classes have the point-Ramsey property, will will need the existence of a hypergraph of large girth. This lemma is slightly different from the one presented in Bootcamp 3, but the proof is still probabilistic. In fact, no constructive proof is known. We will again omit the proof.
Lemma: Let . There is an (which is approximately ), and there is a hypergraph such that
- it is -uniform, and ,
- has girth at least . That is, it doesn’t contain cycles of length less than .
Proof of theorem. This proof is due to Nešetřil and Rödl, 1977. There is still no constructive proof known for this result. As in the proof of point-Ramsey for these classes, the proof of the forbidden graph case covers all other relevant cases and doesn’t make the proof any harder. Fix with and let . Let be a hypergraph from the lemma with .
Let be the class of all finite graphs which we get by replacing each hyperedge of with a (possibly different) copy of .
Note that , where .
Let be a fixed linear ordering. We will show that for a sufficiently large , there is a that appears in any ordering of .
How many orderings on a graph in are there that don’t admit an embedding of ? There are
ways. We observe that since , we must have
since taking logarithms gives
So for a sufficiently large , a suitable will exist. It will not contain any forbidden graphs, as in the argument for point-Ramsey.
Edge-Ramsey and the ordering property
As mentioned in Bootcamp 3, there is a heuristic in terms of the strength of the Ramsey properties. Here we show that “ordered” edge Ramsey can give us the ordering property.
We will need a slightly technical structural condition on in order to get the desired theorem.
Defintion. A class of finite structures is said to have the Joint Embedding Property (JEP) if such that and are both disjoint substructures of .
Definition. The class is the class of all structures where and is a linear order.
Proof. Fix an . Let be an arbitrary linear order (as in the ordering property).
We start by doing something clever that will help us at the end of the proof. Use the JEP to find an that contains a copy of and its reverse order.
Let be a witness to the edge-Ramsey property for with two colours. We claim that any order on will contain a copy of .
Consider the (Sierpinski) partition where is the collection of all edges where and agree.
By Ramsey, there is a monochromatic . Because of our clever “hedging” at the beginning, we will have a copy of in regardless of which colour is monochromatic in.
Observe: On first glance it might appear that Ordered Ramsey trivially implies the order property. This confusion comes from the fact that the witness to the Ramsey property comes with a linear order, and clearly this witness contains many copies of the desired ! But the problem is we need to show that no matter what order we place on it will have the we want. We have to forget about this nice order we got from Ramsey and give an arbitrary order.
A bad colouring
In the previous theorem we used the Sierpinski colouring to play two linear orders against each other. Here we use a linear order in a slightly different way to show that graphs cannot be stronger than edge-Ramsey.
Proof. Let be the path with two edges, and let be the cycle with 5 edges. We claim that there is no graph such that .
Let be a graph that contains a copy of . Here’s where we are clever: let be a linear order.
There are three non-isomorphic ways to linearly order (is the midpoint at the beginning, middle or end). Partition based on which order type inherits from .
Exercise. Show that any copy of with its inherited linear order will contain a copy of each of the three different ways to linearly order . (Use the -max and -min of .)
This shows that is not a witness to the Ramsey property.
Note that we could have done this with a two-colouring, instead of a three-colouring.
In addition to the JEP we will often have another property called amalgamation (which allows us to glue two stuctures together along a common structure). The Ramsey property will guarantee that we have amalgamation, as we will see shortly.
Definition. A class has the amalgamation property (AP) if for all and all embeddings and there is a and embeddings and with .
Proof. Let be a maximal independent subset of . Since the chromatic number is at least 3, is not a cover of .
Let be a maximal independent subset of . Since the chromatic number is at least 3, is not a cover of .
Take any . For , by maximality of , there is an such that . Moreover, .
This corollary actually applies to more than just classes of graphs, but we will not get in to that here.
The product argument
The following argument is standard, and nice. We will use it to prove Hilbert’s Theorem, which asserts that distributive lattices have the point-Ramsey property.
Note: In what follows we use the usual set-theoretic convention that for a natural number , we may think of it as a set . This allows us to take without confusion.
Hilbert’s Theorem. such that for every partition
- the are mutually disjoint, and
- , for all subsets of .
Proof. This will be by induction on (and arbitrary). The proof is quite visual.
[.] This is from Sperner’s Theorem, which bounds the size of antichains.
[Assume .] Fix , and define the following constants:
- is the Hilbert number for colours and width ,
- is the Hilbert number for colours and width . This is much larger than .
We will think of as having a large part (which will contribute a lattice of width ) and a small part (which will contribute a lattice of width ). We will combine them to get the desired lattice of width . In order to combine them we will need to make sure they agree on colours.
Fix a partition . (This is the one we want our eventual lattice of width to be monochromatic with.)
We first define a colouring on the large part. Define a colouring with colours on by keeping track of the opinion each has about each element .
That is iff , where .
Since we chose the large side to have size , it must contain a monochromatic lattice of width , say .
Put this to the side for a moment and we will define a colouring on the small part. Define a colouring based on the original partition by has colour if and only if .
Equivalently, because we already stabilized it, we could ask that for all subsets of .
By our choice of the size of the small part, there is a monochromatic lattice of width in , say .
Exercise: Show that is the desired monochromatic lattice of width .
Observe: The bounds on the Hilbert numbers grow very quickly. Perhaps we could slow it down by balancing the sizes of the “large set” and the “small set”.