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

**Lecturer**: Jaroslav Nesetril

**Date**: Monday October 3, 2016.

**Main Topics**: Other applications of the “product argument”, Chain-Ramsey for Posets, Proof of edge-Ramsey for Graphs, Proof of Hales-Jewett

**Definitions:** Structural pigeonhole principle, Poset, Graph product, Combinatorial line

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

## From last time

This lecture continues from Bootcamp 4 which introduced the “product argument” as seen in the proof of Hilbert’s Theorem. In this lecture we have in mind three direct applications of the product argument. For this lecture it is very important that you understand the proof of Hilbert’s theorem!

- Chain-Ramsey for partial orders.
- Edge-Ramsey for graphs.
- Hales-Jewett Theorem.

The first two arguments will go as follows:

**Overview**.

- Use an embedding theorem which says that every structure is contained in a product structure.
- Without loss of generality we may construct a product structure.
- The special case of only one factor is usually a classical theorem.
- At the inductive stage, use the product argument to create the newest factor.
- Depending on the structure, care must be taken to ensure that the “cross edges” between the old structure and the new factor remain monochromatic.

## The Product Pigeonhole Principle

**Definition**. Let be a class such that such that . We say that

**satisfies the pigeonhole principle (for )**.

Let us first state a general version of the Pigeonhole Principle which we will find useful. The proof is the product argument.

**Theorem (Product Pigeonhole)**. Let . There are finite sets such that for all partitions , there are of cardinality , and an such that .

Finite sets hide some of what is going on, so let us state this for classes of finite structures. The first theorem will be a corollary of the second.

**Theorem (Product-Pigeonhole for a class of finite structures)**. Let be a class of finite structures with the vertex-Ramsey property (i.e. the Pigeonhole principle). Let . There are such that for all partitions , there are isomorphic copies in , and an such that .

We denote the conclusion .

**Proof**. This is by induction on , the number of factors. Suppose this theorem is true for factors (all substructures, all colourings) and we will show it for factors.

Fix structures , the “extra” structure and .

By the pigeonhole principle for , there is a such that . (We think of this as a “small” factor.)

Let k_1 = .

By the inductive hypothesis, there are such that . (We think of as “big”.)

Let be an arbitrary colouring. We give relating colourings on the big part , then the small part .

Consider the colouring . For , .

Find in (for ) such that is -monochromatic.

We now define the second colouring. Let be fixed, (any point will work because of the previous colouring). Define by .

There is a in that is $\chi_{small}-monochromatic.

**Exercise**. Convince yourself that is -monochromatic.

## Chain-Ramsey for Partial Orders

**Definition**. We refer to a set with a partial order as a

**poset**. A set , a poset, is a

**chain**if is a linear order with the inherited order.

Our proof of Hilbert’s theorem actually proves a Ramsey result about posets.

**Theorem (Chain-Ramsey for Posets)**. For , for a chain, a finite poset, then there is a poset such that .

We will use the following embedding theorem, which will allow us to assume without loss of generality that is a product of linear orders.

**Theorem (Dushnik-Miller)**. For every poset , there are linear orders such that . The minimal such is called the

**Dushnik-Miller dimension of**.

**Definition**. The product of two linear orders is the set together with the coordinate-wise order iff and .

**Proof of Chain-Ramsey for Posets**. As an exercise, use the proof of the Product-Pigeonhole for a class of finite structures to prove the desired result.

There is only one step that will be specific to posets. If you can’t find it, then look to our later proof of the graph type lemma.

## Edge-Ramsey for Graphs

**Theorem (Edge-Ramsey for Graphs)**. For every graph , there is a graph such that .

### Embedding theorem and graph products

Our embedding theorem will be the following:

**Theorem**. For every graph , there is a finite index set and , such that embeds into .

**Definition**. The product of two graphs is the graph with vertex set and edges where , .

Define such that is given by the above theorem.

We give an example of graph product below. In regards to the dimension of a graph, here are two nice facts (which are unrelated to our theorem at hand).

**Fact**. .

Of course the upperbound is obvious, but the lower bound is interesting!

**Fact (Lovász-Nešetřil-Pultr 1980)**. The dimension of disjoint edges is .

This is the first use of the algebraic method in combinatorics.

**Proof of embedding theorem.**

Fix with . Let be the collection of all graph homomorphisms .

Define the map , where the -coordinate is , for .

**Claim**. preserves edges.**Claim**. preserves non-edges.**Claim**. is injective.

Conclude that embeds into .

### Taking care of cross-edges

The proof will be comparable to the chain-Ramsey for posets, but will introduce an additional complication. In the poset case, given and there is one way to get a pair of points in that respect the order and . Namely . This was possible because the poset relation is antisymmetric.

In the graph case, the edge relation is symmetric, so there won’t be a canonical way to get elements of the large product. So we have to work harder and take this into account when arguing.

A typical example is the product of two edges. Let with the edge . Let with the edge . In this case the product is the graph on the four points with the two edges and .[Picture]

The issue is that every pair of edges gives rise to two edges in the product. We will use -types to figure out which one to take.

**Definition**. For let be a linear order on the vertices of . For an edge in , with lexicographically less than , we say

**the type**where if and if .

**Exercise**.

- Compute the types of the “typical example” that appears before the definition. Do the same for the product of three edges.
- Every type starts with a .
- There are at most many types (in a product of dimension ).
- Every product of of dimension contains all possible types.
- Every product of of dimension contains every type exactly once.
- Use types to show that there is an edge colouring of that does not admit a monochromatic . Conclude that the desired Ramsey witness might have higher dimension than our starting graph.

### Embeddings

It is worth examining how embeddings work in big products, because they can be a little counterintuitive.

**Exercise**. Show that does not embed into .

The above exercise shows that you might not have embeds into . Fortunately, this can be fixed.

**Lemma**. Let be a graph with vertices, and suppose . Then embeds into .

**Proof**. Assume is defined on the set . Let be defined by the diagonal map . Note that this is an embedding (

**Exercise**).

**Corollary**. Let be a graph with vertices, and suppose . Then embeds into .

### A type lemma

The exercise 4 above points out that we cannot hope to only have one type of edge, so instead we need to make sure that all types receive the same colour. We do this in two stages by first making sure that all edges of the same type have the same colour; that is the content of the next lemma.

**Lemma**. Fix a finite set , and a type of dimension . There are such that for every type--edge partition , there is a colour and a subgraph all of whose edges of type are in .

**Corollary**. There is a large enough such that you can always find a such that each edge type is monochromatic in colour (but different types might have different colours).

**Note**. In this lemma the dimension does not increase.

**Proof of corollary**. There are at most many different types, so we just apply the lemma that many times. Take .

**Proof of lemma**. This will be a product argument very similar to the poset argument, inducting by dimension. Since we are fixing the type ahead of time, there is no difficulty with the “cross-edges”.

[Dimension ] This is the classical Ramsey Theorem.

[] Fix structures , the “extra” structure and .

By the case, there is a such that .

Let k_1 = .

By the inductive hypothesis, there are such that .

Let be an arbitrary type--edge colouring. We give relating colourings on the big part , then the small part .

Consider the colouring . For , define .

**Key step**. This previous step is the only step that is different from the poset case.

Find (for ) such that is -monochromatic.

We now define the second colouring. Let be fixed. Define by where we only take the one edge from of type .

There is a \chi_{small}-monochromatic.

Thus is our desired structure, and are -monochromatic.

### The proof of edge-Ramsey

**Overview of proof**.

- Because of our embedding theorem, without loss of generality we may assume our graph is a product of .
- Because of our corollary, extend each to a large enough (so each edge type individually is monochromatic).
- Use Hilbert’s Theorem (on the index set) to extend the dimension to (to make sure all edge types have the same colour).

**Proof of edge-Ramsey**. Without loss of generality we may instead prove the following: For all , there is a graph such that .

Let .

We apply Hilbert’s Theorem to the index set. That is, there is a sufficiently large so that any partition of into parts yields a lattice mutually disjoint and nonempty, such that is always in the same part (regardless of the set ).

Extend each to a suitably large (as in the corollary for the index set , applied for all many types).

** Claim**. is the desired Ramsey witness.

Fix an edge colouring of . From the choice of we can stabilize the colouring on each edge type, and get the graph .

From the choice of , consider the following -colouring of . For consider the type that is on the points in and off of it. Assign the colour that receives above.

Find as in Hilbert’s theorem. Note that (as in the embedding section) each contains a copy of . So embeds into .

We claim that our copy of is edge-monochromatic. We already know that each type of edge is monochromatic, so it will be enough to show that different edge types get the same colour.

We note that each type of this copy can be described using an , for a . Also note that each of these types will be of the same colour. Also remark that must be in each of these unions, and this corresponds to the fact that each type starts with a .

## Hales-Jewett

**Definition**. For a fixed alphabet and a variable a

**constant word (of length )**is an element of . A

**variable word**

is an element of , where shows up at least once. The (constant) word is the word with all replaced by . The positions of the variable are refered to as **the moving part**.

A **combinatorial line** for a fixed variable word .

**Example**. Consider the alphabet and . There are seven variable words: which correspond to the seven combinatorial lines: and . The moving part of the is the second coordinate.

**Theorem (Hales-Jewett, 1964)**. Fix a finite alphabet , with . For all , there is an such that for all partitions , there is an and a combinatorial line in such that .

**Notation**. We abbreviate this theorem above as HJ(), where is the length of the alphabet, is the number of colours and refers to the dimension of the combinatorial line (more on that in a moment). Sometimes we also abuse notation and use HJ() to refer to the least number that works for the theorem.

In order to prove the Hales-Jewett Theorem for all sizes of alphabet, we will actually need to induct with a stronger, higher-dimension theorem. First a simple example.

**Fact**. HJ() is true for all .

Let . For colours, we claim that suffices.

Take the words , for . If they are -coloured, then two of the words (given by ) must be the same colour. So the combinatorial line given by the word is monochromatic.

We now introduce the higher-dimensional version of Hales-Jewett.

**Definition**. For a fixed alphabet and variables a **multi-variable word** is an element of , where each shows up at least once.

A **combinatorial subspace (of dimension )** is for a fixed multi-variable word .

**Theorem (Higher dimensional Hales-Jewett)**. Fix a finite alphabet , with . For all , there is an such that for all partitions , there is an and a combinatorial subspace of dimension in such that .

**Notation**. We abbreviate this theorem above as HJ(), where is the length of the alphabet, is the number of colours and refers to the dimension of the combinatorial subspace. Sometimes we also abuse notation and use HJ() to refer to the least number that works for the theorem

### The proof of Hales-Jewett

**Overview of proof**.

- Fix . Observe that trivially HJ().
- Fix . Show HJ(). (
*Already done.*) - Fix . Show HJ() implies HJ(). (
*Product argument.*) - Fix . Show HJ() (and previous implication) implies HJ(). (
*Fancy version of second obersavation.*)

**Exercise**. Show that these four steps are enough to prove the Hales-Jewett theorem .

**Proof that for fixed that HJ() implies HJ()**.

This is precisely a product argument, as in the proof of Hilbert’s Theorem. Assume we have HJ() and HJ(), we will show HJ(). Take

- to be the number given by .
- to be the number given by .

We claim that Ark\xiA^N$.

We induce a colouring as follows. For , take the vector of -colours that each gives to the concatenated word .

**Definition**. The **concatenation** of two words , amd is the word achieved by writing followed by . In general this operation is not commutative.

For example concatenated with is the word .

Concatenate comes from the Latin “con” (with, together) and “caten” (chain). It literally means “chain together”.

Since was chosen large enough, there is a monochromatic combinatorial subspace of of dimension .

Now induce a colouring as follows. Fix a word . For , take the -colour that is assigned to the concatenated word . (By choice of , every word induces the same colouring .)

Since was chosen large enough, there is a monochromatic combinatorial line of .

Our desired monochromatic subspace of dimension is the subspace which is achieved by concatenating each element of with each element of .

**Proof that for fixed HJ() implies HJ()**.

Fix . Our goal is to go up a colour.

We will be assuming that HJ() for all (but fixed ). (That is, for alphabets of length and using colours we can find a monochromatic subspace of dimension ).

We also assume HJ(). (That is, for alphabets of length and using colours, we can find a monochromatic line.)

**Claim**. We want HJ(). (That is for alphabets of length and using colours, we can find a monochromatic line.)

Assume that our alphabet is where .

Let . We will show that HJ() HJ() =: N.

Fix a -colouring on the words of . This also colours the words of .

There is a monochromatic combinatorial subspace of dimension in , call it i\leq d. Say that every word here gets colour .

Now consider the words , which are achieved by substituting the first coordinate of the word with , and the rest from . Note that if any single one of these words is assigned the colour , then we can create a monochromatic combinatorial line in . (** Exercise**.)

So now suppose that doesn’t use the colour . So this is a colouring on the words . By assumption we can find a monochromatic line here. This will also be a monochromatic line in (since the alphabet is not changing).

Let us prove Van der Waerden’s theorem as a corollary.

**Theorem (Van der Waerden)**. For all there is an such that for every colouring there is a monochromatic arithmetic progression of length .

**Proof**. Fix a number , let HJp,kkN$.

We describe the numbers from to in a way that makes Hales-Jewett applicable. We want combinatorial lines to correspond to arithmetic progressions.

For each word associate to it the number . (We are identifying words with their representation in base .)

Now a combinatorial line will correspond to an arithmetic progression of length . (**Exercise**.)

**Example**. For an arithmetic progression of length , consider the words in base . Hales-Jewett with tell you how big you need to take the largest power to be. A combinatorial line might look like this (with ).

The word is , and the line is . This can be seen as an arithmetic progression as: where .

I would say in the application of hilbert lemma, you partitions subset of the index sets into k parts and look for monochromatic lattice. Let N be the number given by hilbert lemma.

You build product of N copies of complete graph and by the previous lemma any edge coloring gives you a produced of N copies of (smaller) complete graphs such that the coloring depends only on the type. To complete the proof we need to find a product of d complete graphs as a monochromatic subgraph of this.

Type is a sequence of -1s and 1s of length N and the coloring induces coloring of types. On this you apply hilbert lemma (set corresponds to a sequence where 1s represent elements of the set) and the monochromatic cube will then give you the monochromatic copy.

I think it is easier to see with d-dimensional hales jewett cube, but with hilbert lemma it is essentially the same.

LikeLike

Hi, the link for bootcamp 4 is not working.

LikeLike

Fixed! Thank you.

LikeLike