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 8 (of 8)
Lecturer: Jan Hubička
Date: Wednesday October 12, 2016.
Main Topics: Ramsey lifts, Classification results, Tournaments, Digraphs, Permutations, unary functions, Steiner Systems, Dual Ramsey, Graham-Rothschild.
Definitions: Digraph, Tournament, Interposition, , Strong substructure, unary function, Steiner System
Note: The material here is meant as an overview, so many details are missing.
In Bootcamp 7 we looked at the Ramsey Expansions of homogeneous graphs and posets. Today we will look at more classes. First we look at classes with classification theorems (tournaments, directed graphs). After that we will look at more general constructions (disjoint unions and interpositions). We will then look at a couple of examples that don’t fit into classifications. Finally we will introduce dual Ramsey theorems.
Definition. A directed graph is a structure where is a set and with no loops. (In other words it is an asymmetric, irreflexive, binary relation.)
A tournament is a directed graph where for all precisely one of of .
Theorem (Lauchlan 1984). Every infinite countable homogeneous tournament is one of the following:
- with its usual order.
- The generic tournament (the limit of the class of finite tournaments)
- the generic local order (defined below).
Definition. Define the structure where are unary predicates that partition (in a dense, co-dense way) and if both have the same colour (L,R) and (in the order), if they have different colour and .
That is, the order is the same on things of the same colour, but reversed if the colours are different.
Note that the structure does not contain the partition in its language.
Proof. This is a “projection argument” similar to the case for copies of seen in Bootcamp 7. This argument better suited as a picture; words are not good at explain the rather simple idea.
Fix in this expanded language. Find a number such that .
Consider the structure given by with the odd numbers getting the unary predicate . We claim that is the Ramsey witness.
Fix a -colouring of . Consider only the structures in that don’t use the same second coordinate twice, and where the vertices are all before the vertices. There is a canonical correspondence between these structures and subsets of of cardinality . In particular induces a colouring on , the subsets of the indices of size .
So there is a set of indices in of cardinality . Consider the partition and .
We create a copy of by giving putting the first coordinates of in the coordinate, and the rest in the coordinate. Note that all substructures of don’t use the same second coordinate, so all copies of are captured by the colouring. All these are monochromatic, as desired.
We are now in a position where we have two (seemingly) different expansions to the structure , which is two disjoint copies of . We can take an arbitrary linear order, or we can use this expansion (by twisting the order). It is an exercise (we have already discussed) that does not have the order property.
In this way, there are two other notable classification results, Cherlin’s 1998 classification of all homogeneous directed graphs, and Cherlin’s 2014(+) classification of homogeneous ordered graphs.
Classification of digraphs
Mike’s comment. Honza mentioned in class that he was impressed with my ability to put the entire Cherlin’s classification into one slide. So I’ve included a picture of that slide instead of stating the classification result more formally.
Since this classification result was a key motivator of my thesis, I’m going to shamelessly promote one of my paper’s as a reference for an explanation of these classes. I like the pictures in it!
More detailed descriptions of these classes can be found in pages 18-26 of this Pawliuk-Sokic paper.
The Ramsey expansions of these classes were detailed in the 2014 paper of Jasinski-Laflamme-Nguyen Van Thé-Woodrow. They mostly follow the pattern that we have established (convex linear orders). The major exception is the semi-generic digraph which is much more subtle. Its Ramsey expansion includes a unary predicate that indicates how to amalgamate a structure with an imaginary transversal. See the Pawliuk-Sokic paper for more details (pages 24-26).
Permutations and interpositions
In 2002 Cameron published “Homogeneous Permutations” a classification of all Fraïssé classes of permutations (as explained below).
After an earlier Ramsey DocCourse, Böttcher and Foniok (in the 2012 “Ramsey Properties of Permutations“) studied the class of sets with two (independent) linear orderings on them . The intuition is that the first linear order is the “original” and the second is a permutation. This class was proved to be Ramsey and used the following general lemma about interpositions.
Definition. Let be a relational class with relation , and be a relational class with relation . The interposition is the class of structures where and .
The definition extends to more classes with more relations in the obvious way. The definition also extends to the product of structures (not classes) in the obvious way.
The first appearance of this Lemma seems to be Bodirsky’s 2012 paper “New Ramsey classes from Old“. The proof presented there goes through topological groups and the tools of dynamics. Another (purely combinatorial) proof appears in Bodirsky’s 2015 survey “Ramsey classes: Examples and Constructions“.
By taking both structures to be we get the result mentioned at the beginning of this section.
Proof of Lemma.
[I don’t really understand this proof. It uses products.]
This result mirrors the following:
Bipartite graphs and forbidden graphs
Consider the class of (not necessarily complete) bipartite graphs. It’s Ramsey expansion is a bit subtle.
Exercise. Show that does not have the ordering property.
[Too vague] It might help to think of Alice and Bob playing a game where Bob creates a graph and tries to make sure Alice’s ordered graph can’t live inside a ordered version of it. Use the fact that Alice cannot specify which part of the bipartition her vertices should live in.
To fix this we add two unary predicates to indicate which part of the bipartition a vertex is in. In this way the expansion can be thought of as the graphs which red or blue vertices, but we forbid edges with both vertices blue or both red.
Definition. Let be a (finite) graph. The class is the class of all finite graphs that are homomorphic to .
Recall that a graph homomorphism must send edges to edges, but is free to send non-edges to edges.
We also have the following duality theorem. See the paper for more details. Also see Foniok’s 2014 paper “On Ramsey properties of classes with forbidden trees“.
One way to construct a Ramsey class from an old one is to add some of the points of the space into the language, that is we distinguish some points.
Here it is useful to think about “closed” substructures and the idea of closure.
A class is transitive if for all whenever embeds into which embeds into , then embeds into .
In the case where is a Fraïssé class we can take the limit and in general we expect this to differ from the Fraïssé limit of . We also expect to satisfy something other than the -point extension property, as a single point extension might not be in .
Martin Ziegler has a good one page introduction to Strong Fraïssé classes.
A good example of the use of strong substructures comes from Steiner Systems.
In the class of partial Steiner systems amalgamation is an obstacle. For example consider Steiner systems. How do you amalgamate two edges over the structure which is two points? Doing the usual free amalgamation along those two points violates the Steiner system condition.
We fix this by considering a family of strong substructures. Take to be a strong substructure of if every edge of containing a subset of size of is also in .
Finally we look at the class of unary functions, recently (2016) investigated by Sokic in “Unary functions“.
Find an such that . Add levels above vertices and add copies of on those levels. Specifically, is constructed as a disjoint union of copies of above every .
Identify vertices of the same closure, where the closure is defined as [???]. After closure we get the desired graph .
In preparation for some of the later talks, we briefly introduce the notion of Dual Ramsey theorems. Roughly it corresponds to reversing all the arrows between in a usual Ramsey theorem. We end up colouring subspaces, not points. We introduce the Graham-Rothschild theorem which is dual to Hales-Jewett.
A one parameter word is a word in the alphabet .
An parameter word is a word in the alphabet . We also require that the first appearance of is before the first appearance of for all .
For an parameter word , and , in this context is the collection of all parameter words in (using the first parameters). (This is why we have the condition on which order the variables show up.)
This is a dual Ramsey theorem because we are colouring subspaces, not words.