Bootcamp 8 – Ramsey DocCourse Prague 2016 – Mike Pawliuk

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, $\text{CSP}(G)$ , 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 $(V, E)$ where $V$ is a set and $E \subseteq V^2$ with no loops. (In other words it is an asymmetric, irreflexive, binary relation.)

A tournament is a directed graph $(V,E)$ where for all $a,b \in V$ precisely one of $(a,b) \in E$ of $(b,a) \in E$ .

Theorem (Lauchlan 1984). Every infinite countable homogeneous tournament is one of the following:

$(\mathbb{Q}, <)$ with its usual order.
The generic tournament (the limit of the class of finite tournaments)
$S(2)$ the generic local order (defined below).

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

Definition. Define the structure $\mathbb{S}(2) = (\mathbb{Q}, \preceq)$ where $L,R$ are unary predicates that partition $\mathbb{Q}$ (in a dense, co-dense way) and $a \preceq b$ if both have the same colour (L,R) and $a \leq b$ (in the $\mathbb{Q}$ order), if they have different colour and $b \leq a$ .

That is, the order is the same on things of the same colour, but reversed if the colours are different.

Note that the structure $\mathbb{S}(2)$ does not contain the partition $L,R$ in its language.

Theorem (Ngyuen van The). Adding the partition $L,R$ to the language of $\mathbb{S}(2)$ makes it a Ramsey structure.

Proof. This is a “projection argument” similar to the case for $n$ copies of $K_\omega$ seen in Bootcamp 7. This argument better suited as a picture; words are not good at explain the rather simple idea.

Fix $A,B$ in this expanded language. Find a number $N$ such that $N \longrightarrow (\vert B \vert)_k^{\vert A \vert}$ .

Consider the structure $C$ given by $\{L,R\}\times\{1,2, \ldots, N\} \cong \{1,2, \ldots, 2N-1, 2N\} \subset \mathbb{Q}$ with the odd numbers getting the unary predicate $L$ . We claim that $C$ is the Ramsey witness.

Fix a $k$ -colouring $\chi$ of $\binom{C}{A}$ . Consider only the structures $A$ in $C$ that don’t use the same second coordinate twice, and where the $L$ vertices are all before the $R$ vertices. There is a canonical correspondence between these structures and subsets of $\{1,2, \ldots, N\}$ of cardinality $\vert A \vert$ . In particular $\chi$ induces a colouring $\chi_1$ on $\binom{N}{\vert A \vert}$ , the subsets of the indices of size $\vert A \vert$ .

So there is a set of indices $I$ in $N$ of cardinality $\vert B \vert$ . Consider the partition $B_L = \{b \in B : L(b)\}$ and $B_R = \{b \in B : R(b)\}$ .

We create a copy $B^\prime$ of $B$ by giving putting the first $\vert B_L\vert$ coordinates of $I$ in the $L$ coordinate, and the rest in the $R$ coordinate. Note that all substructures of $B^\prime$ don’t use the same second coordinate, so all copies of $A$ are captured by the $\chi_1$ colouring. All these are monochromatic, as desired.

We are now in a position where we have two (seemingly) different expansions to the structure $\Delta$ , which is two disjoint copies of $(\mathbb{Q}, <)$ . We can take an arbitrary linear order, or we can use this $\mathbb{S}(2)$ expansion (by twisting the order). It is an exercise (we have already discussed) that $\Delta$ 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!

Theorem (Cherlin 1998).

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 $(A, \leq_1, \leq_2)$ . 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 $\mathcal{C}_1$ be a relational class with relation $R_1$ , and $\mathcal{C}_2$ be a relational class with relation $R_2$ . The interposition is the class $\mathcal{C}_1 \star \mathcal{C}_2$ of structures $(A, R_1, R_2)$ where $(A, R_1) \in \mathcal{C}_1$ and $(A,R_2) \in \mathcal{C}_2$ .

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 $H_1, H_2$ are homogeneous Ramsey structures with the SAP then $H_1 \star H_2$ 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 $(\mathbb{Q}, <)$ we get the result mentioned at the beginning of this section.

Corollary. $(A, <_1, <_2)$ 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 $(A, \leq, \prec_1, \prec_2)$ , where $(A, \leq)$ is a poset and $\prec_1,\prec_2$ are linear extensions of $\leq$ 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 $\mathcal{B}$ of (not necessarily complete) bipartite graphs. It’s Ramsey expansion is a bit subtle.

Exercise. Show that $\mathcal{B}$ 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 $B$ 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 $G$ be a (finite) graph. The class $\text{CSP}(G)$ is the class of all finite graphs that are homomorphic to $G$ .

Recall that a graph homomorphism must send edges to edges, but is free to send non-edges to edges.

Theorem (NVT, 2009). The class $\text{CSP}(K_n)$ 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 $\text{Forb}(\mathcal{F})$ and $\text{CSP}(D)$ , when $F$ 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 $H$ be an $\omega$ -categorical Ramsey structure. Let $H^\prime$ be the structure created by distinguishing a finite number of points from $H$ . Then $H^\prime$ is also a Ramsey structure.

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

Definition. Let $\mathcal{C}$ be a class of finite structures and let $S \subset \mathcal{C}$ . We say that $S$ is a family of strong substructures (of $\mathcal{C}$ ) if it is closed under isomorphic images and it is transitive.

A class $S$ is transitive if for all $A,B,C \in S$ whenever $A$ embeds into $B$ which embeds into $C$ , then $A$ embeds into $C$ .

In the case where $\mathcal{C}$ is a Fraïssé class we can take the limit $\lim (\mathcal{C},S)$ and in general we expect this to differ from the Fraïssé limit of $\mathcal{C}$ . We also expect $S$ to satisfy something other than the $1$ -point extension property, as a single point extension might not be in $S$ .

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 $n,t \in \mathbb{N}$ . A (partial) $(t,n)$ Steiner system is an $n$ -regular hypergraph where every set of points of cardinality $t$ is in at most one hyperedge.

In the class of partial $(t,n)$ Steiner systems amalgamation is an obstacle. For example consider $(2,3)$ Steiner systems. How do you amalgamate two edges over the structure $A$ 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 $B$ to be a strong substructure of $A$ if every edge of $A$ containing a subset of size $\geq t$ of $B$ is also in $B$ .

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 $f:A \longrightarrow A$ . 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 $A$ and $B$ as follows:

[PICTURE]

Find an $N$ such that $N \longrightarrow (\vert B \vert)_2^{\vert A \vert}$ . Add levels above $N$ vertices and add copies of $B$ on those levels. Specifically, $B^\prime$ is constructed as a disjoint union of copies of $B$ above every $\binom{N}{\vert B \vert}$ .

[PICTURE]

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

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 $A,B,C$ 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 $A$ be an alphabet.

A one parameter word is a word in the alphabet $A \cup \{\Delta\}$ .

An $n$ parameter word is a word in the alphabet $A \cup \{\Delta_1, \ldots, \Delta_n\}$ . We also require that the first appearance of $\Delta_i$ is before the first appearance of $\Delta_j$ for all $i<j$ .

For an $n$ parameter word $C$ , and $0<p\leq n$ , in this context $\binom{C}{p}$ is the collection of all $p$ parameter words in $C$ (using the first $p$ parameters). (This is why we have the condition on which order the variables show up.)

Theorem (Graham-Rothschild). $\forall n,t > 0, p >0, A$ an alphabet, there is an $N = \text{GR}(A,p,t,n)$ such that if $C$ is an $n$ -parameter word and $\binom{C}{p}$ is coloured with $t$ colours, then there is an $n$ parameter word $B \in \binom{C}{n}$ such that $B$ 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 $A = \{0,1\}$ .

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

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

2 thoughts on “Bootcamp 8 – Ramsey DocCourse Prague 2016”

Yangjing says:

October 20, 2016 at 8:23 am

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

LikeLike

1. Micheal Pawliuk says:
  
  October 20, 2016 at 10:32 am
  
  Good eye!
  
  LikeLike