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

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

**Note**: The material here is meant as an overview, so many details are missing.

## Introduction

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.

## Homogeneous Tournaments

**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).

**Exercise**. Show that the class of ordered finite tournaments is a Ramsey class.

**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.

**Theorem (Ngyuen van The)**. Adding the partition to the language of makes it a Ramsey structure.

**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.

### Other classifications

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.

**Lemma**. If are homogeneous Ramsey structures with the

**SAP**then is Ramsey.

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.

**Corollary**. is a Ramsey structure.

**Proof of Lemma**.

[I don’t really understand this proof. It uses products.]

This result mirrors the following:

**Theorem (Sokic, 2012)**. The class of all structures , where is a poset and are linear extensions of is a Ramsey class.

**Theorem (Solecki-Zhao, 2014)**. Sokic’s result but for three linear extensions.

**Exercise**. Use the interposition lemma to prove Sokic’s result. Use Ramsey to ignore the additional partial order relation.

### 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.

**Theorem (NVT, 2009)**. The class is Ramsey.

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“.

**Theorem (Nešetřil-Tardif, 2002)**. There is a duality between the class and , when is a directed graph that is a tree.

### Distinguished points

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.

**Lemma**. Let be an -categorical Ramsey structure. Let be the structure created by distinguishing a finite number of points from . Then is also a Ramsey structure.

Here it is useful to think about “closed” substructures and the idea of closure.

**Definition**. Let be a class of finite structures and let . We say that is a

**family of strong substructures (of )**if it is closed under isomorphic images and it is transitive.

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.

### Steiner systems

A good example of the use of strong substructures comes from Steiner Systems.

**Definition**. Fix . A

**(partial) Steiner system**is an -regular hypergraph where every set of points of cardinality is in at most one hyperedge.

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 .

**Exercise**. Show that the Fraïssé limit along these strong substructures is not universal for countable Steiner Systems by showing that it does not contain an infinite hyperpath. It will however by universal for all locally finite Steiner systems.

**Definition**. A hypergraph is

**locally finite**if every vertex is contained in only finitely many vertices.

### Unary functions

Finally we look at the class of unary functions, recently (2016) investigated by Sokic in “Unary functions“.

**Definition**. Consider the functions . We interpret them as directed graphs with loops and out-degree 1.

**Theorem (Sokic 2016)**. The class of unary functions is a Ramsey class.

**Sketch of proof**. For visualization we consider the classes and as follows:

[PICTURE]

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 .

[PICTURE]

Identify vertices of the same closure, where the closure is defined as [???]. After closure we get the desired graph .

### Dual Ramsey

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.

**Definition**. Let be an alphabet.

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.)

**Theorem (Graham-Rothschild)**. an alphabet, there is an such that if is an -parameter word and is coloured with colours, then there is an parameter word such that is monochromatic.

This is a dual Ramsey theorem because we are colouring subspaces, not words.

**Exercise**. Check that Hales-Jewett is a special case of this theorem by using the alphabet .

**Corollary**. This shows that Boolean Algebras with atoms are Ramsey.

**Corollary**. This shows that Finite fields over finite sets are Ramsey.

Hi, in the definiton of (2), (2)=(ℚ,⪯, the “)” is missing.

LikeLike

Good eye!

LikeLike