Bootcamp 4 – 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.

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.

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

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 $\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 ordering property.

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 $n, l, N \in \mathbb{N}$ . There is an $\epsilon>0$ (which is approximately $\frac{1}{l}$ ), and there is a hypergraph $(X, \mathcal{M})$ such that

$\vert X \vert \geq N$ ,
it is $n$ -uniform, and $\mathcal{M} \subseteq \binom{X}{n}$ ,
$(X, \mathcal{M})$ has girth at least $l$ . That is, it doesn’t contain cycles of length less than $l$ .
$\vert \mathcal{M} \vert \geq \vert X \vert^{1+\epsilon}$ .

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 $A = (V,E)$ with $\vert V \vert = n$ and let $l = \max_{F \in \mathcal{F}} \vert F \vert$ . Let $(X, \mathcal{M})$ be a hypergraph from the lemma with $\vert X \vert = N$ .

Let $\mathcal{G}$ be the class of all finite graphs which we get by replacing each hyperedge of $(X, \mathcal{M})$ with a (possibly different) copy of $A$ .

Note that $\vert \mathcal{G} \vert \geq a^{N^{1+\epsilon}}$ , where $a := \frac{n!}{\text{Aut}(A)}$ .

Let $(A, \leq)$ be a fixed linear ordering. We will show that for a sufficiently large $N$ , there is a $G \in \mathcal{G}$ that $(A, \leq)$ appears in any ordering of $G$ .

How many orderings on a graph in $\mathcal{G}$ are there that don’t admit an embedding of $(A, \leq)$ ? There are

$\leq N! (a-1)^{N^{1+\epsilon}}$

ways. We observe that since $\vert \mathcal{G} \vert \geq a^{N^{1+\epsilon}}$ , we must have

$N^N (a-1)^{N^{1+\epsilon}} << a^{N^{1+\epsilon}}$

since taking logarithms gives

$N \ln N + N^{1+\epsilon}\ln(a-1) << N^{1+\epsilon}\ln(a)$ .

So for a sufficiently large $N$ , a suitable $G$ will exist. It will not contain any forbidden graphs, as in the argument for point-Ramsey.

[QED]

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 $\mathcal{C}$ in order to get the desired theorem.

Defintion. A class of finite structures $\mathcal{C}$ is said to have the Joint Embedding Property (JEP) if $\forall A,B \in \mathcal{C}, \exists C \in \mathcal{C}$ such that $A$ and $B$ are both disjoint substructures of $C$ .

Definition. The class $\mathcal{OC}$ is the class of all structures $(C, \leq_C)$ where $C \in \mathcal{C}$ and $\leq_C$ is a linear order.

Theorem. If $\mathcal{C}$ is a class of finite graphs, and $\mathcal{OC}$ has the JEP and the edge-Ramsey property for two colours, then $\mathcal{C}$ has the ordering property.

Proof. Fix an $A = (V_A, E_A)$ . Let $(A, \prec_A)$ 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 $A^\prime = (V^\prime, E^\prime, \prec^\prime)$ that contains a copy of $(A, \prec_A)$ and its reverse order.

Let $B^\prime = (B, \prec_B) = (V_B, E_B, \prec_B)$ be a witness to the edge-Ramsey property for $A^\prime$ with two colours. We claim that any order on $B$ will contain a copy of $(A, \prec_A)$ .

Consider the (Sierpinski) partition $E_B = \mathcal{A}_1 \cup \mathcal{A}_2$ where $\mathcal{A}_1$ is the collection of all edges where $\leq_B$ and $\prec_B$ agree.

By Ramsey, there is a monochromatic $(A_0, \leq) \in \binom{B^\prime}{A^\prime}$ . Because of our clever “hedging” at the beginning, we will have a copy of $(A, \prec)$ in $(A_0, \leq)$ regardless of which colour $A_0$ is monochromatic in.

[QED]

Observe: On first glance it might appear that Ordered Ramsey trivially implies the order property. This confusion comes from the fact that the witness $(B, \prec_B)$ to the Ramsey property comes with a linear order, and clearly this witness contains many copies of the desired $(A, \prec_A)$ ! But the problem is we need to show that no matter what order we place on $B$ it will have the $(A, \prec_A)$ we want. We have to forget about this nice order we got from Ramsey and give $B$ 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.

Proposition. The class of all finite graphs is not a Ramsey class.

Proof. Let $A$ be the path with two edges, and let $B$ be the cycle with 5 edges. We claim that there is no graph $C$ such that $C \longrightarrow (B)^A_3$ .

Let $C$ be a graph that contains a copy of $B$ . Here’s where we are clever: let $(C, \leq)$ be a linear order.

There are three non-isomorphic ways to linearly order $A$ (is the midpoint at the beginning, middle or end). Partition $\binom{C}{A} = \mathcal{A}_1 \cup \mathcal{A}_2 \cup \mathcal{A}_3$ based on which order type $(A, \leq)$ inherits from $(C, \leq)$ .

Exercise. Show that any copy of $B^\prime \in \binom{C}{B}$ with its inherited linear order will contain a copy of each of the three different ways to linearly order $A$ . (Use the $\leq$ -max and $\leq$ -min of $B$ .)

This shows that $C$ is not a witness to the Ramsey property.

[QED]

Note that we could have done this with a two-colouring, instead of a three-colouring.

Amalgamation property

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 $\mathcal{C}$ has the amalgamation property (AP) if for all $A,B,C \in \mathcal{C}$ and all embeddings $f : A \rightarrow B$ and $g : A \rightarrow C$ there is a $D \in \mathcal{C}$ and embeddings $\overline{f} : B \rightarrow D$ and $\overline{g} : C \rightarrow D$ with $\overline{f} \circ f = \overline{g} \circ g$ .

Proposition. If $\chi(X, \mathcal{M}) > 2$ , then $\exists M \neq M^\prime \in \mathcal{M}$ such that $\vert M \cap M^\prime \vert = 1$ .

Proof. Let $C_1$ be a maximal independent subset of $X$ . Since the chromatic number is at least 3, $C_1$ is not a cover of $X$ .

Let $C_2$ be a maximal independent subset of $X \setminus C_1$ . Since the chromatic number is at least 3, $C_1 \cup C_2$ is not a cover of $X$ .

Take any $x \in X \setminus (C_1 \cup C_2)$ . For $i=1,2$ , by maximality of $C_i$ , there is an $M_i \in \mathcal{M}$ such that $M_i \subseteq C_i \cup \{x\}$ . Moreover, $M_1 \cap M_2 = \{x\}$ .

[QED]

Corollary. If $\mathcal{C}$ is a Ramsey class of graphs, with JEP, then it has AP.

Proof. Apply the previous proposition to an $\langle A,B,C\rangle$ hypergraph.

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 $n$ , we may think of it as a set $n = \{0,1,2, \ldots, n-1\}$ . This allows us to take $\mathcal{P}(n)$ without confusion.

Hilbert’s Theorem. $\forall n, \forall k, \exists N$ such that for every partition $\mathcal{P}(N) = \mathcal{A}_1 \cup \ldots \cup \mathcal{A}_k$

$\exists A_0, \ldots, A_n, \exists i_0$ ,
the $A_i$ are mutually disjoint, and
$A_0 \cup \bigcup_{j \in J} A_j \in \mathcal{A}_{i_0}$ , for all subsets $J$ of $\{1, \ldots, n\}$ .

Proof. This will be by induction on $n$ (and $k$ arbitrary). The proof is quite visual.

[ $n=1$ .] This is from Sperner’s Theorem, which bounds the size of antichains.

[Assume $n$ .] Fix $k$ , and define the following constants:

$H(k,1)$ is the Hilbert number for $k$ colours and width $1$ ,
$k_1 := k^{2^{H(k,1)}}$ ,
$H(k_1, n)$ is the Hilbert number for $k_1$ colours and width $n$ . This is much larger than $H(k,1)$ .
$N := H(k,1) + H(k_1, n)$ .

We will think of $N$ as having a large part $H(k_1, n)$ (which will contribute a lattice of width $n$ ) and a small part $H(k,1)$ (which will contribute a lattice of width $1$ ). We will combine them to get the desired lattice of width $n+1$ . In order to combine them we will need to make sure they agree on colours.

Claim: $H(k, n+1) \leq N$ .

Fix a partition $\mathcal{P}(N) = \mathcal{A}_1 \cup \ldots \cup \mathcal{A}_k$ . (This is the one we want our eventual lattice of width $n+1$ to be monochromatic with.)

We first define a colouring on the large part. Define a colouring with $k_1 = k^{2^{H(k,1)}}$ colours on $\mathcal{P}(H(k_1, n))$ by keeping track of the opinion each $M_2 \in \mathcal{P}(H(k_1, n))$ has about each element $M_1 \in \mathcal{P}(H(k,1))$ .

That is $M_2 \in \mathcal{A}_f$ iff $M_1 \cup M_2 \in \mathcal{A}_{f(M_1)}$ , where $f: \mathcal{P}(H(k,1)) \rightarrow \{1, \ldots, k\}$ .

Since we chose the large side to have size $H(k_1, n)$ , it must contain a monochromatic lattice of width $n$ , say $A_0, A_1, \ldots, A_n$ .

Put this to the side for a moment and we will define a colouring on the small part. Define a colouring $\mathcal{P}(H(k,1)) = \mathcal{A}_1^\prime \cup \ldots \cup \mathcal{A}_k^\prime$ based on the original partition by $M \in \mathcal{P}(H(k,1))$ has colour $\mathcal{A}_i^\prime$ if and only if $M \cup A_0 \in \mathcal{A}_i$ .

Equivalently, because we already stabilized it, we could ask that $M \cup A_0 \cup \bigcup_{j \in J} A_j \in \mathcal{A}_i$ for all subsets $J$ of $\{1, \ldots, n\}$ .

By our choice of the size of the small part, there is a monochromatic lattice of width $1$ in $H(k,1)$ , say $B_0, B_1$ .

Exercise: Show that $(B_0 \cup A_0), B_1, A_1, A_2, \ldots, A_n$ is the desired monochromatic lattice of width $n+1$ .

[QED]

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

5 thoughts on “Bootcamp 4 – Ramsey DocCourse Prague 2016”

Pingback: Bootcamp 5 – Ramsey DocCourse Prague 2016
Pingback: Bootcamp 5 – Ramsey DocCourse Prague 2016
Pingback: Bootcamp 3 – Ramsey DocCourse Prague 2016
Pingback: Bootcamp 6 – Ramsey DocCourse Prague 2016
Pingback: Bootcamp 7 – Ramsey DocCourse Prague 2016

The ordering property for some classes of graphs

Edge-Ramsey and the ordering property

A bad colouring

Amalgamation property

The product argument

Share this:

Like this:

Related

5 thoughts on “Bootcamp 4 – Ramsey DocCourse Prague 2016”

Leave a Reply Cancel reply