Bootcamp 3 – 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 (3 of 6)

Lecturer: Jaroslav Nešetřil

Date: Friday September 23, 2016.

Main Topics: Point Ramsey for graphs, $\langle A,B,C \rangle$ hypergraphs.

Definitions: Ramsey property for finite structures, Ramsey Class, point-Ramsey, edge-Ramsey, $\langle A,B,C \rangle$ hypergraphs, Chromatic number, Ordering Property.

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

Definitions and Examples

Structural classes, substructures and embeddings

Throughout the course we will make use of classes $\mathcal{C}$ of finite structures, such as the class $\mathcal{G}$ of all finite graphs or the class $\mathcal{AP}$ of all finite arithmetic progressions on $\mathbb{N}$ . We will also need to describe what we mean by “substructure” in the class $\mathcal{C}$ . For example in $\mathcal{G}$ , a substructure of a graph is an induced subgraph. Equivalently, we could instead describe what an “embedding” is in the class $\mathcal{C}$ . For example, in $\mathcal{AP}$ embeddings are increasing affine maps which means that the substructures are subsets that are also arithmetic progressions. Either way, it will usually be clear from context what we mean by substructure or embedding.

We will present more examples in a moment after introducing a key combinatorial property.

Definition. For $A,B \in \mathcal{C}$ , $\binom{B}{A} = \{A^\prime \in \mathcal{C} : A^\prime$ is a substructure of $B\}$ .

Structural Ramsey property

We say that a class $\mathcal{C}$ has the (structural) $A$ -Ramsey property, for a structure $A \in \mathcal{C}$ if

$\forall B \in \mathcal{C}, \forall k \in \mathbb{N}, \exists C \in \mathcal{C}$ such that $C \longrightarrow (B)_k^A$ .

This arrow notation means that for every partition $\binom{C}{A} = \mathcal{A}_1 \cup \ldots \cup \mathcal{A}_k$ there is a $B^\prime \in \binom{C}{B}$ and an $i_0$ such that $\binom{B^\prime}{A} \subseteq \mathcal{A}_{i_0}$ .

If a class $\mathcal{C}$ is $A$ -Ramsey for all $A \in \mathcal{C}$ then we say that it is a Ramsey class.

Intuition and mneumonics

To make this easier to process we usually refer to $A$ as small, $B$ as medium, and $C$ as large. It is interesting to look at this property even when $A$ is a single point, which corresponds to vertex partitions. (These are in fact the classical Ramsey theorems.) This is called the point-Ramsey property.

The case in $\mathcal{G}$ where $A$ is an edge is also interesting and corresponds to edge partitions.

Example classes

The first two classes are Ramsey classes, which is equivalent to the classical Ramsey theorem.
1. Finite sets where a substructure is a subset.
2. The class $\mathcal{LO}$ of finite linear orders where an embedding is a monotone injection.
The class $\mathcal{AP}$ of finite arithmetic progressions on $\mathbb{N}$ . Van der Waerden’s Theorem is equivalent to saying that $\mathcal{AP}$ has the point-Ramsey property.
The class $\mathcal{Fin}$ of finite subsets of $\mathbb{N}$ together with maps $f: A \rightarrow B$ where $f(x) + f(y) = f(z)$ whenever $x,y,z \in A$ with $x + y = z$ . Schur’s Theorem is equivalent to saying that $\mathcal{Fin}$ has the point-Ramsey property.
The class of all finite distributive lattices where a substructure is a sublattice. Hilbert’s Theorem is equivalent to saying that this class has the point-Ramsey property. (See Bootcamp 4 for a precise statement of Hilbert’s Theorem and a proof.)

Exercise: Prove that $\mathcal{AP}$ has no other Ramsey objects.

Van der Waerden has a very nice writeup of his thought process in trying to prove his theorem. It is contained in the Mathematical Coloring Book.

Hypergraphs of the form $\langle A,B,C \rangle$

We now introduce a special class of hypergraphs constructed from finite structures. These hypergraphs are well suited to capture Ramsey properties as chromatic numbers.

Definition: Let $A,B,C \in \mathcal{C}$ . Define the hypergraph $\langle A,B,C \rangle = (X, \mathcal{M})$ , where

$\mathcal{M} \subseteq \mathcal{P}(X)$ ,
$X = \binom{C}{A}$ , and
$M \in \mathcal{M}$ if and only if $\exists B^\prime \in \binom{C}{B}$ where $M = \binom{B^\prime}{A}$ .

Definition: A hypergraph $(X, \mathcal{M})$ has chromatic number $> k$ if every partition of $X$ into $\leq k$ parts contains a monochromatic $M \in \mathcal{M}$ . The chromatic number of $(X, \mathcal{M})$ is the least such $k$ and is denoted $\chi(X, \mathcal{M})$ .

The Ramsey property for $\langle A,B,C \rangle$ is closely related to its chromatic number.

Observation: $C \longrightarrow (B)_k^A$ if and only if $\chi(\langle A,B,C \rangle) > k$ .

It is tempting to try to find witnesses to the Ramsey property by using witnesses to the chromatic number. In practice this is difficult, as the next example shows.

Example. Let $k=2$ , $A$ be an edge, $B$ be a triangle and $C$ be $K_6$ . So $\langle A,B,C \rangle = (X, \mathcal{M})$ is 3-uniform and $\chi(X, \mathcal{M}) > 2$ (see here).

This hypergraph also has the peculiar property that if $M \neq M^\prime \in \mathcal{M}$ then $\vert M \cap M^\prime \vert \leq 1$ . This is because if two triangles share two sides, then they must also share the third side.

Other $\langle A,B,C \rangle$ graphs that have been studied

The following graphs can be expressed as $\langle A,B,C \rangle$ graphs, but many cannot be described by finitely many forbidden subgraphs.

Line graphs, (which can actually be described by nine forbidden subgraphs),
Interval graphs,
Kneser graphs,
Johnson graphs,
Shift graphs. Vertex set $\binom{n}{2}$ . Two vertices $(i,j), (k,l)$ of the shift graph are connected by an edge if $i < j = k < l$ . This has no triangles (exercise) but its chromatic number is $\log (n)$ since “it is coming from $K_n$ “. (See Theorem 5.6 on page 14 of these notes for example.)

Point-Ramsey for some classes of graphs

Let $\mathcal{C}$ be one of the following classes of finite graphs:

All graphs,
all triangle-free graphs,
all $K_n$ -free graphs,
all graphs not containing any finite set $\mathcal{F}$ of forbidden $2$ -connected (i.e. no cut points) subgraphs.

Theorem: If $\mathcal{C}$ is one of the above classes, then it has the point-Ramsey property.

The first proof of this was given by Folkman, and then was simplified later. We first state a lemma that will produce a hypergraph with large chromatic number and doesn’t contain short cycles. This type of hypergraph will be used in many arguments. The proof of its existence will be shown in a different lecture and is a hard, probabilistic proof due to Erdos-Hajnal in 1966. This exaplains why Folkman’s original proof was so difficult.

Lemma: Let $2 \leq l, k, n \in \mathbb{N}$ . There is a hypergraph $(X, \mathcal{M})$ such that

it is $n$ -uniform, and $\mathcal{M} \subseteq \binom{X}{n}$ ,
$\chi(X, \mathcal{M}) > k$ ,
$(X, \mathcal{M})$ has girth at least $l$ . That is, it doesn’t contain cycles of length less than $l$ .

Note that since $l \geq 2$ any two hyperedges can intersect in at most one point. This lemma also gives another construction for the following corollary.

Corollary. $\forall k, \exists G$ such that $G$ is triangle-free, but $\chi(G)>k$ .

Proof of theorem. Assume for now that $\mathcal{C}$ is the class of all finite graphs. The arguments for the others are similar and we will comment on the differences at the end.

Let $B = (V,E)$ and let $\vert V \vert = n$ . Use $l=2$ . To show point Ramsey, we will use the chromatic number equivalence given above.

Let $(X, \mathcal{M})$ be a hypergraph from the lemma. We create a graph $G$ on the vertex set $X$ by putting a copy of $B$ on each hyperedge in $\mathcal{M}$ . This is well defined since there are no 2-cycles in $(X, \mathcal{M})$ .

Observe that $G = \langle A,B,C \rangle$ . Since $(X, \mathcal{M})$ has high chromatic number, we must have the desired Ramsey property.

Proof for $K_n$ -free. This will be a special case of the next case.

Proof for forbidden $2$ -connected graphs. As before, except use $l = \max_{F \in \mathcal{F}} \vert F \vert$ .

We claim that $C$ contains no graph from $\mathcal{F}$ . Suppose that $F \in \mathcal{F}$ is a subgraph of $C$ . Consider the induced subhypergraph $(Y, \mathcal{N})$ of $(X, \mathcal{M})$ where $Y$ contains all hyperedges from $(X, \mathcal{M})$ that contain an element of $F$ .

Since $\vert F \vert \leq l$ and $(X, \mathcal{M})$ has no cycles of length $l$ , the subhypergraph $(Y, \mathcal{N})$ must be a tree. Since $F$ has no cutpoints, it must be contained completely within one hyperedge of $Y$ . This contradicts the fact that $B$ contained to copies of $F$ .

[QED]

Ordering property

We now introduce a Ramsey property for structures that heuristically fits between point-Ramsey and edge-Ramsey.

Point-Ramsey. Holds for many classes.
Ordering property.
Edge-Ramsey. Holds for some classes.

The ordering property will be stronger than point-Ramsey, but weaker than edge-Ramsey.

Definition. Let $A,B \in \mathcal{C}$ . We say that $B$ has the ordering property for $A$ if for all linear orders $(A, \leq_A)$ and $(B, \leq_B)$ there is a monotone $\mathcal{C}$ -embedding from $(A, \leq_A)$ into $(B, \leq_B)$ . We say that $\mathcal{C}$ has the ordering property if $\forall A \in \mathcal{C}, \exists B \in \mathcal{C}$ such that $B$ has the ordering property for $A$ .

Exercise. Find a $B_k$ that witnesses the ordering property for $A_k$ , with the given linear ordering $\leq_k$ .