# Category Archives: Ramsey theory

## On unabridged versions of Ramsey’s theorem

In continuation of our discussions on Ramsey theory in this post we plan to prove the unabridged versions of Ramsey’s theorem. While the abridged versions dealt with graphs, unabridged versions deals with hypergraphs. A hypergraph, is a set of vertices $V$ together with a set of subsets of $V$ of a fixed order $n$. If $n=2$ then we get back the ordinary definition of a graph.

An example of a hypergraph of order 3 is given below:

The vertex set $V=\{a,b,c,d,e\}$ and the hyperedges are given by: $\{a,b,c\}$, $\{b,d,e\}$ and $\{a,b,d\}$.

The infinite unabridged version of Ramsey’s theorem may now be described as follows: Given a complete infinite hypergraph of order $n$ with vertex set $\mathbb{N}$, and a $r$-coloring of its hyperedges we are guaranteed a infinite complete monochromatic subgraph.

Let us try to express this more succinctly. We will extend the previously defined arrows notation as follows: The notation $\alpha\rightarrow (\beta)^n_r$ will mean that every $r$-colored complete hypergraph of order $n$ on $\alpha$ vertices contains a monochromatic complete subgraph with $\beta$ vertices. Since hypergraphs do not seem to be as picturesque as graphs, so maybe the idea will be better expressed in terms of sets: $\alpha\rightarrow (\beta)^n_r$ equivalently means that for any assignment of $r$-colors to the $n$-subsets of $\alpha$, there is a particular color (say red) and a subset $X$ of $\alpha$ of size $\beta$ such that all $n$-subsets of $X$ are red. (Note that $\alpha,\beta$ etc can be any cardinal numbers.)

With the notation that $\omega$ stands for the cardinality of $\mathbb{N}$ the infinite version of Ramsey’s theorem now is:

Theorem: $\forall n,r\in\mathbb{N}, \omega\rightarrow(\omega)^n_r$.

The proof is essentially on the same lines as in the abridged case, with the addition that we induct on $n$. ($n$ may intuitively be thought of as the “hyper-ness” of our hypergraph.)

Proof: By induction on $n$. If $n=1$ we just get the infinite pigeonhole principle: Any finite partitioning of $\mathbb{N}$ contains an infinite part. Indeed, both the infinite and finite Ramsey theorems may be thought of as gigantic generalizations of the pigeonhole principle.

Now suppose that for a fixed $n,r$ we have $\omega\rightarrow(\omega)^n_r$. Now consider any $r$-coloring $f$ of the $n+1$-subsets of $\omega$. Just like in the proof of the abridged case we build a sequence $(w_k)$. In the abridged case we applied the infinite pigeonhole principle repeatedly at this point. Here we will use the induction hypothesis repeatedly. Let $w_1=1$. Consider the $r$-coloring $f_{w_1}$ of all $n$-subsets of $\omega-\{1\}$ given by $f_{w_1}(X)=f(\{1\}\cup X)$. By the induction hypothesis there will be a countable subset of $\omega$ whose all $n$-subsets will be monochromatic. Call that subset $V_1$. Let the least element of $V_1$ be designated as $w_2$.

The construction of $(w_k)$ follows by induction: If the set $V_k$ and its least element $w_{k+1}$ have been found, consider the $r$-coloring $f_{w_{k+1}}$ of the $n$-subsets of $V_k$ given by $f_{w_{k+1}}(X)=f(\{w_{k+1}\}\cup X)$. By the induction hypothesis it contains a countable set all of whose $n$-subsets are monochromatic. Call that subset $V_{k+1}$. Its least element is designated as $w_{k+2}$.

The sequence $(w_k)$ has the property that given any $w_i$ the union of $\{w_i\}$ with any $n$-order subset containing elements from $w_{i+1},w_{i+2},w_{i+3}\cdots$ has the same color (with respect to the the original coloring $f$). Let us call $w_i$ as $c_j$-based if this color is $c_j$. The fact that all the members of the sequence $(w_k)$ are based in any of $r$-ways induces a partitioning of the sequence $(w_k)$. By the infinite pigeonhole principle we are guaranteed an infinite part. Now, by ordering the terms appropriately in this infinite part we have a subsequence $(w_{k_j})$ of $(w_k)$ in which all vertices are the same color base, say $c_1$. It is now easy to observe that all the $n+1$-subsets of this infinite part are colored $c_1$, which proves the theorem.$\Box$

We now turn to the finite version. In our arrows notation, the natural generalization from the abridged analogue reads:

Theorem: $\forall l,n,r\in\mathbb{N}, \exists m\in\mathbb{N}$ such that $m\rightarrow (l)_r^n$.

Proof: The proof is identical to the abridged case with cosmetic changes. By way of contradiction assume that there is an $l$ such that for all $m\in\mathbb{N}$ we have $m\nrightarrow (l)_r^n$. We will use the notation $\hat{K_i}$ for a hypergraph on $i$ vertices where all possible $n$-subsets of the vertices are the hyperedges. Also let $G$ be a hypergraph with vertices $V=\{v_i:i\in\mathbb{N}\}$ and let the hyperedges of $G$ be enumerated by $E=\{E_i:E_i\subset\mathbb{N}, |E_i|=n\}$. We construct a (rooted) tree $T$ as follows:

1. First introduce a root vertex $rt$.

2. Each vertex is allowed to have at most $r$ children which correspond to the $r$-colors, subject to it satisfying the criteria below. A child is always labeled by one among the $r$-colors. (Call the colors $c_1,c_2\cdots c_r$ for convenience).

3. A child $c_i$ is permitted if and only if its introduction creates a path of some finite length $k$ starting from the root, so that if the hyperedges $E_1,E_2\cdots E_k$ are colored by the colors used in the path in the same order, then the corresponding subgraph in $G$ does not contain a monochromatic $\hat{K_l}$. For example if the introduction of a child $c_i$ creates the $k$ length path $rt,c_a,c_b\cdots ,c_i$ and the hyperedges $E_1,E_2,\cdots E_k$ when colored $c_a,c_b\cdots c_i$ don’t contain a monochromatic $\hat{K_l}$ the child $c_i$ is permitted to be added to $T$.

Note that for all $m$, there always exists a coloring of $\hat{K_m}$ such that no monochromatic $\hat{K_l}$ exists within. So the situation that a child cannot be added to any vertex at a given level $k$ cannot arise. For we can always take a coloring of $\hat{K_{k+n}}$ containing no monochromatic $\hat{K_l}$. Since any $k$ hyperedges in it would yield a sequence of colors already existing in $T$, we know which vertex to add the child to. We give the child the color corresponding to any other edge. Hence we can forever keep adding children and so $T$ is infinite. It is also obvious that each level $k$ of $T$ has at most $r^k$ vertices and so each level is finite.

Now by Konig’s lemma there will be an infinite path in $T$. This infinite path provides a $r$-coloring of $G$ that contains no monochromatic $\hat{K_i}$ and hence no monochromatic infinite hypergraph which contradicts the infinite Ramsey theorem proved above. This contradiction proves the theorem.$\Box$

The astute reader may have noted that we have used weak versions of the axiom of choice occasionally in the proof. Ramsey himself was aware of this and remarked so in his original paper. In fact, it can be proved that Ramsey’s theorem cannot ever be proved without using some form of the axiom of choice. Moreover it can be shown that a weak form of the axiom of choice is equivalent to Ramsey’s theorem. Hence Ramsey’s theorem may be interpreted as a choice axiom.

1 Comment

Filed under Combinatorics, Graph theory, Ramsey theory

## Arrows, Ramsey numbers and the Party Problem

Here come the arrows! The notation $\alpha\rightarrow (\beta)^2_r$ means that every $r$-colored complete graph on $\alpha$ vertices contains a monochromatic complete subgraph with $\beta$ vertices. Using the notation $\omega$ for the cardinality of the natural numbers the abridged Ramsey theorems state that $\omega\rightarrow (\omega)^2_r$ and that $\forall n\exists m,m\rightarrow (n)^2_r$.

Now let us take a particular case: $n=3,r=2$. Our objective here is to prove that $6\rightarrow (3)^2_2$. In other words, if the edges of $K_6$ are $2$-colored then there exists a monochromatic $K_3$. Fix a vertex $v$ in $K_6$. From the $5$ edges emanating from $v$, at least three must share a color: call it $c$. Now if all the edges in triangle made by those three vertices are not colored $c$, we are done for we have found a monochromatic $K_3$ in the other color. If even one edge, say $xy$ among the triangle made by those three vertices is of color $c$ then we have a monochromatic $K_3$ colored $c$ with vertices $x,y$ and $v$.

The fact that $6\rightarrow (3)^2_2$ is also referred to as the solution of the party problem: Prove that in any gathering of six people there are three mutual friends, or three mutual strangers. By representing the people as vertices and their relationships via the colors on the edges connecting them we easily see that a monochromatic triangle is guaranteed and therefore the result holds. It is also obvious that the gathering may contain more then six people, a monochromatic triangle is still guaranteed within (in fact, it will only become more likely with more people). In other words: $m\rightarrow (3)^2_2\forall m\ge 6$.

Is six the least such number? Indeed it is as the following graph demonstrates:

We note that there is no monochromatic triangle in the above $2$-colored $K_5$.

For a given $n$ the least such number $m,m\rightarrow (n)^2_r$ is called the diagonal Ramsey number $R(n,n)$. While such numbers are guaranteed to exist by Ramsey’s theorem, actually finding them is hard indeed. It is trivial to see that $R(1,1)=1$ and $R(2,2)=2$. Our proof above illustrates that $R(3,3)=6$. It has also been proven that $R(4,4)=18$. However all efforts to find out the exact value of any other diagonal Ramsey number have failed. It is one of those problems, which are easily stated but extremely difficult to attack.

Regarding $R(5,5)$, Joel Spencer comments in his book, Ten lectures on the Probabilistic Method:

Erdős asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of $R(5,5)$ or they will destroy our planet. In that case, he claims, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for $R(6,6)$. In that case, he believes, we should attempt to destroy the aliens.

In closing it may be remarked that the Ramsey number $R(m,n)$ is defined to be the least positive integer such that any $2$-coloring of $K_{R(m,n)}$ in two colors, say red and blue, contains either a red $K_m$ or a blue $K_n$. This definition also has the natural generalization for more then two colors. Although the existence of all Ramsey numbers is guaranteed by Ramsey’s theorem, only few have been discovered so far.

1 Comment

Filed under Combinatorics, Miscellaneous, Ramsey theory

## On abridged versions of Ramsey’s theorem

This post will aim to prove two abridged versions of Ramsey’s theorem, the result which gave its name to the area of mathematics now known as Ramsey theory. Ramsey theory may be understood as ramifications of a philosophical principal. The principle may be summarized as: “Complete disorder is an impossibility. Any structure will necessarily contain an orderly substructure.” Ramsey’s theorem is an example of this principle. Van der Waerden’s theorem is another example.

First a bit of history regarding this theorem. Frank Ramsey, a 25 year old British mathematician, proved this result in 1928 as a part of his investigations in mathematical logic. Unfortunately he passed away in 1930 (even before his theorem was formally published) and did not prove anything else related to this. In 1933, Skolem published another proof of the theorem, and then in 1934, Erdos and Szekeres found yet another. It was the Erdos and Szekeres paper which gave Ramsey’s theorem a wide audience. Further work by Erdos in this area led mathematicians to consider other Ramsey type theorems.

Here we consider abridged versions of Ramsey’s theorem which can be easily understood in the context of graphs. We will imitate Ramsey’s original approach (though not his proof) to first prove an infinite version (which deals with infinite graphs) and then proceed towards the finite analogue.

So what is the infinite version. Briefly it says that if we have an infinite complete graph on countable vertices and if we use $r$ colors $c_1,c_2\cdots c_r$ to arbitrarily color the edges then we are guaranteed an infinite monochromatic subgraph. Here our usage of coloring an edge is just a fanciful way to describe partitioning the edge set into finitely many parts. More formally, by a $r$-coloring of the edges of a graph $G$ we mean any function with domain $E(G)$ and range $\{1,2\cdots r\}$ which induces such a partitioning. The colors are the labels that we may use for this partitioning.

Theorem: Let $G$ be the complete infinite graph with vertices $V=\{v_i:i\in\mathbb{N}\}$. Given any $r$-coloring of the edges, $G$ will contain an infinite complete monochromatic subgraph.

Ramsey’s original formulation was more general. He considered the set of vertices to be any infinite set (and not just countable). That is not much gained because a coloring of an uncountable vertex graph induces a coloring of a countable vertex subgraph. Within this countable subgraph we can find a monochromatic infinite complete graph, which is also a subgraph of the original. However he also generalized in another sense: Instead of coloring edges he considered colorings of hyperedges of a fixed order (an edge is a special case: it is a hyperedge of order 2). This too can be overcome by induction on the “hyper-ness” of the graph. We choose to postpone such discussions.

Proof: Suppose the edges of $G$ have been colored using the colors $c_1,c_2,\cdots c_r$. We will build an infinite subsequence of the vertices in $V$ by applying the infinite pigeonhole principle. Let $w_1=v_1$. Now $w_1$ is connected with every other vertex in $G$ and the edges making this connection are colored in any of $r$-ways. We partition the set of all these vertices in this fashion: If $v$ is connected to $w_1$ via an edge colored $c_i$ we consider it to be a member of the set $P_i$. Clearly, $\{P_i:i=1,2\cdots r\}$ is a partitioning of $V-\{w_1\}$. Now, since $\cup P_i$ is infinite so one of the $P_i$ must also be infinite. (Here we are using the infinite pigeonhole principle.) Note that there may be more then one infinite $P_i$. At any rate choose the “smallest” vertex among the infinite parts (or the vertex with the least $i$ in $\{v_i:i\in P_j, P_j$ is infinite $\}$. Rename that particular $P_i$ as $V_1$ and that vertex as $w_2$.

At this point the construction of the sequence becomes obvious. If for some $n$ we have already found a $w_n$ and and a $V_n$ then we can partition the vertices in $V_n$ connected to $w_n$ into $r$-parts depending on how they are connected with $w_n$. Choosing the smallest vertex among the infinite parts yields $w_{n+1}$ and the part it belongs to yields $V_{n+1}$. Since $V_{n+1}$ is infinite so we have no fear of running out of vertices.

Now note an important property of the sequence $(w_n)$. Given any $w_i$ its connections with $w_{i+1},w_{i+2},w_{i+3}\cdots$ are all of the same color by definition. Let us call $w_i$ as $c_j$-based if the edges $w_iw_{i+1},w_iw_{i+2},w_iw_{i+3}\cdots$ are all colored $c_j$. The fact that all the members of the sequence $(w_n)$ are based in any of $r$-ways induces a partitioning of the sequence $(w_n)$. As before by the pigeonhole principle we are guaranteed an infinite part. Now, by ordering the terms appropriately in this infinite part we have a subsequence $(w_{n_k})$ of $(w_n)$ in which all vertices are the same color base, say $c_1$. It is now easy to observe that the subgraph induced by these vertices has all edges colored $c_1$, which proves the theorem.$\Box$

We now turn our attention to the finite analogue. The infinite version guarantees an infinite monochromatic complete graph within an arbitrarily colored infinite countable graph (with countable vertices). The finite version guarantees a finite monochromatic complete graph of desired size within an arbitrarily colored finite countable graph (with suitable number of vertices). More formally the theorem states:

Theorem: Let $r,l_1,l_2,\cdots l_r$ be natural numbers. Then there exists an $m\in \mathbb{N}$ such that any $r$-coloring of $K_m$ contains a monochromatic $K_{l_i}$ for some $i$ entirely colored in color $i$.

We will prove the theorem with $l_1=l_2=\cdots =l_r=n$. This is because no loss of generality occurs by assuming this. To see this suppose $r=2,l_1=5$ and $l_2=7$. Now if we have proved the theorem for $r=2,l_1=l_2=7$ we have also guaranteed the existence of an $m$ such that any $2$-coloring of $K_m$ contains a $K_7$ colored in either of the two colors. Clearly the same $m$ works for $l_1=5,l_1=7$ as a $1$-colored $K_7$ would contain a $1$-colored $K_5$.

Proof: Our modified claim is that for all $r,n\in\mathbb{N}$ there is an $m\in\mathbb{N}$ such that any $r$-coloring of $K_m$ contains a monochromatic $K_n$. By way of contradiction assume that there is an $n\in\mathbb{N}$ such that for every $m\in \mathbb{N}$ there is a $r$-coloring of $K_m$ containing no monochromatic $K_n$. Now let $G$ be a complete graph with vertices $V=\{v_i:i\in\mathbb{N}\}$ and let the edges of $G$ be enumerated by $E=\{e_i:i\in\mathbb{N}\}$. We construct a (rooted) tree $T$ as follows:

1. First introduce a root vertex $rt$.

2. Each vertex is allowed to have at most $r$ children (a child of a vertex $x$ is defined to be an adjacent vertex $y$ so that $d(rt,x)+1=d(rt,y)$) which correspond to the $r$-colors, subject to it satisfying the criteria below. A child is always labeled by one among the $r$-colors. (Call the colors $c_1,c_2\cdots c_r$ for convenience).

3. A child $c_i$ is permitted if and only if its introduction creates a path of some finite length $k$ starting from the root, so that if the edges $e_1,e_2\cdots e_k$ are colored by the colors used in the path in the same order, then the corresponding subgraph in $G$ does not contain a monochromatic $K_n$. For example if the introduction of a child $c_i$ creates the $k$ length path $rt,c_a,c_b\cdots ,c_i$ and the edges $e_1,e_2,\cdots e_k$ when colored $c_a,c_b\cdots c_i$ don’t contain a monochromatic $K_n$ the child $c_i$ is permitted to be added to $T$.

Note that for all $m$, there always exists a coloring of $K_m$ such that no monochromatic $K_n$ exists within. So the situation that a child cannot be added to any vertex at a given level $k$ cannot arise. For we can always take a coloring of $K_k$ containing no monochromatic $K_n$. Since any $k$ edges in it would yield a sequence of colors already existing in $T$, we know which vertex to add the child to. We give the child the color corresponding to any other edge. Hence we can forever keep adding children and so $T$ is infinite. It is also obvious that each level $k$ of $T$ has at most $r^k$ vertices and so each level is finite.

Now by Konig’s lemma there will be an infinite path in $T$. This infinite path provides a $r$-coloring of $G$ that contains no monochromatic complete graph and hence no monochromatic infinite complete graph which contradicts the infinite Ramsey theorem proved above. This contradiction proves the theorem.$\Box$

Filed under Combinatorics, Graph theory, Ramsey theory

## The van der Waerden theorem

In this post I aim to prove van der Waerden’s theorem on arithmetic progressions.

The theorem states that $\forall k,r\in\mathbb{N}\exists W(k,r)\in\mathbb{N}$ so that if the set $\{1,2\cdots W(k,r)\}$ is partitioned into $r$ classes, one of the classes is guaranteed to contain an arithmetic progression of length $k$.

Before proceeding further, lets look at a bit of history regarding this result. As per a recent book the theorem was conjectured independently by the mathematicians Schur and Baudet sometime around the 1920’s. (The exact dates are unknown). In 1926 van der Waerden, then a young scholar in Hamburg, heard of this conjecture (he believed it to be solely by Baudet) and proved it in the course of a remarkable discussion with his teacher Emil Artin and the mathematician Otto Schreier. The beauty of the proof was that it did not use any tools of advanced mathematics and yet was not simple by any means. Khinchin has referred to it as one of the three pearls of number theory.

Our proof here is not the same proof as originally given by van der Waerden, but a slightly slicker version based on the same idea. We start by making some preparations for the proof. For convenience we will take $[n]=\{1,2\cdots n\}$. Further we can very well uniquely identify a partitioning $\{W_1,W_2,\cdots W_r\}$ of a set $[W(k,r)]=\cup_{i=1}^rW_i$ by a function $f$ with domain $[W(k,r)]$ and range $[r]$ where $f^{-1}(i)$ equals $W_i$. Traditionally the numbers $\{1,2\cdots r\}$ are called colors, every such function is called a $r$-coloring and the sets $f^{-1}(i)$ are referred to as being colored $i$. Given a $r$-coloring a subset of $[W(k,r)]$ is called monochromatic if every element in it corresponds with the same color. With these new definitions the van der Waerden theorem takes the form:

Theorem: $\forall k,r\in\mathbb{N}\exists W(k,r)\in\mathbb{N}$ so that if $[W(k,r)]$ is $r$-colored then there is a monochromatic arithmetic progression of length $k$.

We shall also use the notation $a + [0,k)d$ for the arithmetic progression of length $k$ (also abbreviated as a $k$-AP) given by the ordered set $\{a

And now, on to the proof. As a first step towards proving the result we shall first introduce the concept of wheels. The next step will establish some technical lemmas concerning them and after that we will prove the van der Waerden theorem.

A wheel of radius $k$, degree $n$ and base point or origin $a$ is a $n$ tuple: $W= (a + [0,k) d_1,\cdots, a + [0,k)d_n)$ of $k$-AP's each of which has base point $a$. The AP's $a + [1,k)d_i, 1 \le i \le n$ are called the spokes of the wheel. Assuming that all numbers under consideration have been colored a wheel is weakly polychromatic if all of it’s $n$ spokes are monochromatic with distinct colors, and strongly polychromatic if it’s $n$ spokes and origin are all monochromatic with distinct colors.

An example of a strongly polychromatic wheel of degree $8$ and radius $5$ is given below. In case of a weakly polychromatic wheel the origin, i.e. $1$, can be of any of the colors of the spokes.

The $8$ AP’s are:
$1,2,3,4,5$
$1,10,19,28,37$
$1,4,7,10,13$
$1,7,13,19,25$
$1,6,11,16,21$
$1,8,15,22,29$
$1,5,9,13,17$
$1,3,5,7,9$

A translation of a wheel $W$ by a number $r$ defined as the wheel obtained by adding $a$ to each number in $W$.

We now move on to the next stage in our proof, where we shall establish some technical lemmas concerning wheels.

Lemma 1: If $W= (a + [0,k) r_1,\cdots, a + [0,k)r_n)$ is a wheel of radius $k$ and degree $n$ and the $k-1$ translations $W + r ,\cdots W+(k-1)r$ of $W$ are all strongly polychromatic with the same colors, then the wheel $\hat{W} = (a + [0,k)r , a + [0,k)(r_1 + r),\cdots a + [0,k)(r_n + r))$ of radius $k$ and degree $n+1$ is weakly polychromatic.

Proof: The integers $a + (r_i + r), a + 2(r_i + r), \cdots a + (k-1)(r_i + r)$ respectively picked from $W+r, W + 2r ,\cdots W+(k-1)r$ are identical in color because the ith component of each translation is colored identically. So $\forall i, 1 \le i \le n, a + [1,k)(r_i + r)$ is monochromatically colored and distinct from others. Similarly the AP of the base points $a+r,a+2r,\cdots a+(k-1)r$ also has a distinct color. Thus we have a $n+1$ tuple of AP’s each of which is distinctly monochromatic if we ignore the base point $a$, or that $\hat{W}$ is weakly polychromatic.

Two more lemmas whose proofs are obvious are:

Lemma 2: If $W$ is a weakly polychromatic wheel of radius $k$, then either $W$ is strongly polychromatic, or contains a monochromatic AP of length $k$.

Lemma 3: A strongly polychromatic wheel cannot have degree $r$ where $r$ is the total number of colors.

With the necessary machinery in our arsenal we now attack the van der Waerden theorem proper.

Proof of the van der Waerden theorem: We shall use double induction. The first (outer) induction is on $k$. Clearly for $k = 1,2$ and any $r$ the result holds. Let us suppose that $W(k-1,r)$ exists for all r. Now we

Claim: For any $n\in\mathbb{N},\exists N=N(k-1,r,n)\in\mathbb{N}$ such that given any $r$-coloring of $[N]$, there exists either a monochromatic AP of length $k$, or there exists a strongly polychromatic wheel of radius $k$ and degree $n$.

To prove the claim we use (an inner) induction on $n$. The case $n = 1$ is trivial if we use the outer induction hypothesis. Suppose the result holds for $n-1$, that is, $N_1 = N(k-1,r,n-1)$ exists. Now by the inner hypothesis any block of integers of length $N_1$ contains either a monochromatic AP of length $k$ (in which case we are done) or a strongly polychromatic wheel of radius $k$ and degree $n-1$. In the second case let $N_2 = 2W(k-1, r^{N_1})$ which exists by the outer hypothesis, color the first $N_1N_2$ integers and consider $N_2$ consecutive blocks of length $N_1$. Since there are $r^{N_1}$ colorings of each block, by the outer hypothesis there must be an AP of $k-1$ identically colored blocks: $B+d, B+2d,\cdots B+(k-1)d$.

Now as $|B| = N_1 = N(k-1,r,n-1)$ so inside each block, there is either a monochromatic AP of length $k$ in it, (which proves the theorem) or a strongly polychromatic wheel of radius $k$ and degree $n-1$. Ruling out the former case means that each block $B + d, \cdots B +(k-1)d$ contains a strongly polychromatic wheel of degree $n-1$. Since these blocks are identical in color so we have a AP of strongly polychromatic identical wheels. In this case, by lemma 1, the AP of blocks contains a weakly polychromatic wheel $W$ of radius $k$ and degree $n$. By lemma 2, $W$ is either strongly polychromatic or contains a monochromatic AP of length k. In either case we have proved our claim.

The proof of van der Waerden’s theorem is trivial now. Choose $W(k,r) = N(k-1,r,r)$. Now an $r$-coloring of $[W(k,r)]$ contains either a monochromatic AP of length $k$ or a strongly polychromatic wheel of degree $r$. The latter case is not possible due to lemma 3.$\Box$

1 Comment

Filed under Combinatorics, Ramsey theory