# Combinatorics (Fall 2010)/Ramsey theory

## Ramsey's Theorem

### Ramsey's theorem for graph

 Ramsey's Theorem Let $\displaystyle{ k,\ell }$ be positive integers. Then there exists an integer $\displaystyle{ R(k,\ell) }$ satisfying: If $\displaystyle{ n\ge R(k,\ell) }$, for any coloring of edges of $\displaystyle{ K_n }$ with two colors red and blue, there exists a red $\displaystyle{ K_k }$ or a blue $\displaystyle{ K_\ell }$.
Proof.
 We show that $\displaystyle{ R(k,\ell) }$ is finite by induction on $\displaystyle{ k+\ell }$. For the base case, it is easy to verify that $\displaystyle{ R(k,1)=R(1,\ell)=1 }$. For general $\displaystyle{ k }$ and $\displaystyle{ \ell }$, we will show that $\displaystyle{ R(k,\ell)\le R(k,\ell-1)+R(k-1,\ell) }$. Suppose we have a two coloring of $\displaystyle{ K_n }$, where $\displaystyle{ n=R(k,\ell-1)+R(k-1,\ell) }$. Take an arbitrary vertex $\displaystyle{ v }$, and split $\displaystyle{ V\setminus\{v\} }$ into two subsets $\displaystyle{ S }$ and $\displaystyle{ T }$, where \displaystyle{ \begin{align} S&=\{u\in V\setminus\{v\}\mid uv \text{ is blue }\}\\ T&=\{u\in V\setminus\{v\}\mid uv \text{ is red }\} \end{align} } Since $\displaystyle{ |S|+|T|+1=n=R(k,\ell-1)+R(k-1,\ell) }$, we have either $\displaystyle{ |S|\ge R(k,\ell-1) }$ or $\displaystyle{ |T|\ge R(k-1,\ell) }$. By symmetry, suppose $\displaystyle{ |S|\ge R(k,\ell-1) }$. By induction hypothesis, the complete subgraph defined on $\displaystyle{ S }$ has either a red $\displaystyle{ K_k }$, in which case we are done; or a blue $\displaystyle{ K_{\ell-1} }$, in which case the complete subgraph defined on $\displaystyle{ S\cup{v} }$ must have a blue $\displaystyle{ K_\ell }$ since all edges from $\displaystyle{ v }$ to vertices in $\displaystyle{ S }$ are blue.
$\displaystyle{ \square }$
 Ramsey's Theorem (graph, multicolor) Let $\displaystyle{ r, k_1,k_2,\ldots,k_r }$ be positive integers. Then there exists an integer $\displaystyle{ R(r;k_1,k_2,\ldots,k_r) }$ satisfying: For any $\displaystyle{ r }$-coloring of a complete graph of $\displaystyle{ n\ge R(r;k_1,k_2,\ldots,k_r) }$ vertices, there exists a monochromatic $\displaystyle{ k_i }$-clique with the $\displaystyle{ i }$th color for some $\displaystyle{ i\in\{1,2,\ldots,r\} }$.
 Lemma (the "mixing color" trick) $\displaystyle{ R(r;k_1,k_2,\ldots,k_r)\le R(r-1;k_1,k_2,\ldots,k_{r-2},R(2;k_{r-1},k_r)) }$
Proof.
 We transfer the $\displaystyle{ r }$-coloring to $\displaystyle{ (r-1) }$-coloring by identifying the $\displaystyle{ (r-1) }$th and the $\displaystyle{ r }$th colors. If $\displaystyle{ n\ge R(r-1;k_1,k_2,\ldots,k_{r-2},R(2;k_{r-1},k_r)) }$, then for any $\displaystyle{ r }$-coloring of $\displaystyle{ K_n }$, there either exist an $\displaystyle{ i\in\{1,2,\ldots,r-2\} }$ and a $\displaystyle{ k_i }$-clique which is monochromatically colored with the $\displaystyle{ i }$th color; or exists clique of $\displaystyle{ R(2;k_{r-1},k_r) }$ vertices which is monochromatically colored with the mixed color of the original $\displaystyle{ (r-1) }$th and $\displaystyle{ r }$th colors, which again implies that there exists either a $\displaystyle{ k }$-clique which is monochromatically colored with the original $\displaystyle{ (r-1) }$th color, or a $\displaystyle{ \ell }$-clique which is monochromatically colored with the original $\displaystyle{ r }$th color. This implies the recursion.
$\displaystyle{ \square }$

### Ramsey number

The smallest number $\displaystyle{ R(k,\ell) }$ satisfying the condition in the Ramsey theory is called the Ramsey number.

Alternatively, we can define $\displaystyle{ R(k,\ell) }$ as the smallest $\displaystyle{ N }$ such that if $\displaystyle{ n\ge N }$, for any 2-coloring of $\displaystyle{ K_n }$ in red and blue, there is either a red $\displaystyle{ K_k }$ or a blue $\displaystyle{ K_\ell }$. The Ramsey theorem is stated as:

"$\displaystyle{ R(k,\ell) }$ is finite for any positive integers $\displaystyle{ k }$ and $\displaystyle{ \ell }$."

The core of the inductive proof of the Ramsey theorem is the following recursion

\displaystyle{ \begin{align} R(k,1) &=R(1,\ell)=1\\ R(k,\ell) &\le R(k,\ell-1)+R(k-1,\ell). \end{align} }

From this recursion, we can deduce an upper bound for the Ramsey number.

 Theorem $\displaystyle{ R(k,\ell)\le{k+\ell-2\choose k-1} }$.
Proof.
 It is easy to verify the bound by induction.
$\displaystyle{ \square }$

### Lovász local lemma

Consider a set of "bad" events $\displaystyle{ A_1,A_2,\ldots,A_n }$. Suppose that $\displaystyle{ \Pr[A_i]\le p }$ for all $\displaystyle{ 1\le i\le n }$. We want to show that there is a situation that none of the bad events occurs. Due to the probabilistic method, we need to prove that

$\displaystyle{ \Pr\left[\bigwedge_{i=1}^n\overline{A_i}\right]\gt 0. }$
Case 1: mutually independent events.

If all the bad events $\displaystyle{ A_1,A_2,\ldots,A_n }$ are mutually independent, then

$\displaystyle{ \Pr\left[\bigwedge_{i=1}^n\overline{A_i}\right]\ge(1-p)^n\gt 0, }$

for any $\displaystyle{ p\lt 1 }$.

Case 2: arbitrarily dependent events.

On the other hand, if we put no assumption on the dependencies between the events, then by the union bound (which holds unconditionally),

$\displaystyle{ \Pr\left[\bigwedge_{i=1}^n\overline{A_i}\right]=1-\Pr\left[\bigvee_{i=1}^n A_i\right]\ge 1-np, }$

which is not an interesting bound for $\displaystyle{ p\ge\frac{1}{n} }$. We cannot improve bound without further information regarding the dependencies between the events.

We would like to know what is going on between the two extreme cases: mutually independent events, and arbitrarily dependent events. The Lovász local lemma provides such a tool.

The local lemma is powerful tool for showing the possibility of rare event under limited dependencies. The structure of dependencies between a set of events is described by a dependency graph.

 Definition Let $\displaystyle{ A_1,A_2,\ldots,A_n }$ be a set of events. A graph $\displaystyle{ D=(V,E) }$ on the set of vertices $\displaystyle{ V=\{1,2,\ldots,n\} }$ is called a dependency graph for the events $\displaystyle{ A_1,\ldots,A_n }$ if for each $\displaystyle{ i }$, $\displaystyle{ 1\le i\le n }$, the event $\displaystyle{ A_i }$ is mutually independent of all the events $\displaystyle{ \{A_j\mid (i,j)\not\in E\} }$.
Example
Let $\displaystyle{ X_1,X_2,\ldots,X_m }$ be a set of mutually independent random variables. Each event $\displaystyle{ A_i }$ is a predicate defined on a number of variables among $\displaystyle{ X_1,X_2,\ldots,X_m }$. Let $\displaystyle{ v(A_i) }$ be the unique smallest set of variables which determine $\displaystyle{ A_i }$. The dependency graph $\displaystyle{ D=(V,E) }$ is defined by
$\displaystyle{ (i,j)\in E }$ iff $\displaystyle{ v(A_i)\cap v(A_j)\neq \emptyset }$.

The following lemma, known as the Lovász local lemma, first proved by Erdős and Lovász in 1975, is an extremely powerful tool, as it supplies a way for dealing with rare events.

 Lovász Local Lemma (symmetric case) Let $\displaystyle{ A_1,A_2,\ldots,A_n }$ be a set of events, and assume that the following hold: for all $\displaystyle{ 1\le i\le n }$, $\displaystyle{ \Pr[A_i]\le p }$; the maximum degree of the dependency graph for the events $\displaystyle{ A_1,A_2,\ldots,A_n }$ is $\displaystyle{ d }$, and $\displaystyle{ ep(d+1)\le 1 }$. Then $\displaystyle{ \Pr\left[\bigwedge_{i=1}^n\overline{A_i}\right]\gt 0 }$.

We will prove a general version of the local lemma, where the events $\displaystyle{ A_i }$ are not symmetric. This generalization is due to Spencer.

 Lovász Local Lemma (general case) Let $\displaystyle{ D=(V,E) }$ be the dependency graph of events $\displaystyle{ A_1,A_2,\ldots,A_n }$. Suppose there exist real numbers $\displaystyle{ x_1,x_2,\ldots, x_n }$ such that $\displaystyle{ 0\le x_i\lt 1 }$ and for all $\displaystyle{ 1\le i\le n }$, $\displaystyle{ \Pr[A_i]\le x_i\prod_{(i,j)\in E}(1-x_j) }$. Then $\displaystyle{ \Pr\left[\bigwedge_{i=1}^n\overline{A_i}\right]\ge\prod_{i=1}^n(1-x_i) }$.
Proof.

We can use the following probability identity to compute the probability of the intersection of events:

 Lemma 1 $\displaystyle{ \Pr\left[\bigwedge_{i=1}^n\overline{A_i}\right]=\prod_{i=1}^n\Pr\left[\overline{A_i}\mid \bigwedge_{j=1}^{i-1}\overline{A_{j}}\right] }$.
Proof.
 By definition of conditional probability, $\displaystyle{ \Pr\left[\overline{A_n}\mid\bigwedge_{i=1}^{n-1}\overline{A_{i}}\right] =\frac{\Pr\left[\bigwedge_{i=1}^n\overline{A_{i}}\right]} {\Pr\left[\bigwedge_{i=1}^{n-1}\overline{A_{i}}\right]} }$, so we have $\displaystyle{ \Pr\left[\bigwedge_{i=1}^n\overline{A_{i}}\right]=\Pr\left[\bigwedge_{i=1}^{n-1}\overline{A_{i}}\right]\Pr\left[\overline{A_n}\mid\bigwedge_{i=1}^{n-1}\overline{A_{i}}\right] }$. The lemma is proved by recursively applying this equation.
$\displaystyle{ \square }$

Next we prove by induction on $\displaystyle{ m }$ that for any set of $\displaystyle{ m }$ events $\displaystyle{ i_1,\ldots,i_m }$,

$\displaystyle{ \Pr\left[A_{i_1}\mid \bigwedge_{j=2}^m\overline{A_{i_j}}\right]\le x_{i_1} }$.

The local lemma is a direct consequence of this by applying Lemma 1.

For $\displaystyle{ m=1 }$, this is obvious. For general $\displaystyle{ m }$, let $\displaystyle{ i_2,\ldots,i_k }$ be the set of vertices adjacent to $\displaystyle{ i_1 }$ in the dependency graph. Clearly $\displaystyle{ k-1\le d }$. And it holds that

$\displaystyle{ \Pr\left[A_{i_1}\mid \bigwedge_{j=2}^m\overline{A_{i_j}}\right] =\frac{\Pr\left[ A_i\wedge \bigwedge_{j=2}^k\overline{A_{i_j}}\mid \bigwedge_{j=k+1}^m\overline{A_{i_j}}\right]} {\Pr\left[\bigwedge_{j=2}^k\overline{A_{i_j}}\mid \bigwedge_{j=k+1}^m\overline{A_{i_j}}\right]} }$,

which is due to the basic conditional probability identity

$\displaystyle{ \Pr[A\mid BC]=\frac{\Pr[AB\mid C]}{\Pr[B\mid C]} }$.

We bound the numerator

\displaystyle{ \begin{align} \Pr\left[ A_{i_1}\wedge \bigwedge_{j=2}^k\overline{A_{i_j}}\mid \bigwedge_{j=k+1}^m\overline{A_{i_j}}\right] &\le\Pr\left[ A_{i_1}\mid \bigwedge_{j=k+1}^m\overline{A_{i_j}}\right]\\ &=\Pr[A_{i_1}]\\ &\le x_{i_1}\prod_{(i_1,j)\in E}(1-x_j). \end{align} }

The equation is due to the independence between $\displaystyle{ A_{i_1} }$ and $\displaystyle{ A_{i_k+1},\ldots,A_{i_m} }$.

The denominator can be expanded using Lemma 1 as

$\displaystyle{ \Pr\left[\bigwedge_{j=2}^k\overline{A_{i_j}}\mid \bigwedge_{j=k+1}^m\overline{A_{i_j}}\right] =\prod_{j=2}^k\Pr\left[\overline{A_{i_j}}\mid \bigwedge_{\ell=j+1}^m\overline{A_{i_\ell}}\right] }$

which by the induction hypothesis, is at least

$\displaystyle{ \prod_{j=2}^k(1-x_{i_j})=\prod_{\{i_1,i_j\}\in E}(1-x_j) }$

where $\displaystyle{ E }$ is the edge set of the dependency graph.

Therefore,

$\displaystyle{ \Pr\left[A_{i_1}\mid \bigwedge_{j=2}^m\overline{A_{i_j}}\right] \le\frac{x_{i_1}\prod_{(i_1,j)\in E}(1-x_j)}{\prod_{\{i_1,i_j\}\in E}(1-x_j)}\le x_{i_1}. }$

Applying Lemma 1,

\displaystyle{ \begin{align} \Pr\left[\bigwedge_{i=1}^n\overline{A_i}\right] &=\prod_{i=1}^n\Pr\left[\overline{A_i}\mid \bigwedge_{j=1}^{i-1}\overline{A_{j}}\right]\\ &=\prod_{i=1}^n\left(1-\Pr\left[A_i\mid \bigwedge_{j=1}^{i-1}\overline{A_{j}}\right]\right)\\ &\ge\prod_{i=1}^n\left(1-x_i\right). \end{align} }
$\displaystyle{ \square }$

To prove the symmetric case. Let $\displaystyle{ x_i=\frac{1}{d+1} }$ for all $\displaystyle{ i=1,2,\ldots,n }$. Note that $\displaystyle{ \left(1-\frac{1}{d+1}\right)^d\gt \frac{1}{\mathrm{e}} }$.

If the following conditions are satisfied:

1. for all $\displaystyle{ 1\le i\le n }$, $\displaystyle{ \Pr[A_i]\le p }$;
2. $\displaystyle{ ep(d+1)\le 1 }$;

then for all $\displaystyle{ 1\le i\le n }$,

$\displaystyle{ \Pr[A_i]\le p\le\frac{1}{e(d+1)}\lt \frac{1}{d+1}\left(1-\frac{1}{d+1}\right)^d\le x_i\prod_{(i,j)\in E}(1-x_j) }$.

Due to the local lemma for general cases, this implies that

$\displaystyle{ \Pr\left[\bigwedge_{i=1}^n\overline{A_i}\right]\ge\prod_{i=1}^n(1-x_i)=\left(1-\frac{1}{d+1}\right)^n\gt 0 }$.

This gives the symmetric version of local lemma.

### Ramsey number (continued)

We can use the local lemma to prove a lower bound for the diagonal Ramsey number.

 Theorem $\displaystyle{ R(k,k)\ge Ck2^{k/2} }$ for some constant $\displaystyle{ C\gt 0 }$.
Proof.
 To prove a lower bound $\displaystyle{ R(k,k)\gt n }$, it is sufficient to show that there exists a 2-coloring of $\displaystyle{ K_n }$ without a monochromatic $\displaystyle{ K_k }$. We prove this by the probabilistic method. Pick a random 2-coloring of $\displaystyle{ K_n }$ by coloring each edge uniformly and independently with one of the two colors. For any set $\displaystyle{ S }$ of $\displaystyle{ k }$ vertices, let $\displaystyle{ A_S }$ denote the event that $\displaystyle{ S }$ forms a monochromatic $\displaystyle{ K_k }$. It is easy to see that $\displaystyle{ \Pr[A_s]=2^{1-{k\choose 2}}=p }$. For any $\displaystyle{ k }$-subset $\displaystyle{ T }$ of vertices, $\displaystyle{ A_S }$ and $\displaystyle{ A_T }$ are dependent if and only if $\displaystyle{ |S\cap T|\ge 2 }$. For each $\displaystyle{ S }$, the number of $\displaystyle{ T }$ that $\displaystyle{ |S\cap T|\ge 2 }$ is at most $\displaystyle{ {k\choose 2}{n\choose k-2} }$, so the max degree of the dependency graph is $\displaystyle{ d\le{k\choose 2}{n\choose k-2} }$. Take $\displaystyle{ n=Ck2^{k/2} }$ for some appropriate constant $\displaystyle{ C\gt 0 }$. \displaystyle{ \begin{align} \mathrm{e}p(d+1) &\le \mathrm{e}2^{1-{k\choose 2}}\left({k\choose 2}{n\choose k-2}+1\right)\\ &\le 2^{3-{k\choose 2}}{k\choose 2}{n\choose k-2}\\ &\le 1 \end{align} } Applying the local lemma, the probability that there is no monochromatic $\displaystyle{ K_k }$ is $\displaystyle{ \Pr\left[\bigwedge_{S\in{[n]\choose k}}\overline{A_S}\right]\gt 0 }$. Therefore, there exists a 2-coloring of $\displaystyle{ K_n }$ which has no monochromatic $\displaystyle{ K_k }$, which means $\displaystyle{ R(k,k)\gt n=Ck2^{k/2} }$.
$\displaystyle{ \square }$
 Theorem $\displaystyle{ \Omega\left(k2^{k/2}\right)\le R(k,k)\le{2k-2\choose k-1}=O\left(k^{-1/2}4^{k}\right) }$.
$\displaystyle{ k }$,$\displaystyle{ l }$ 1 2 3 4 5 6 7 8 9 10
1 1 1 1 1 1 1 1 1 1 1
2 1 2 3 4 5 6 7 8 9 10
3 1 3 6 9 14 18 23 28 36 40–43
4 1 4 9 18 25 35–41 49–61 56–84 73–115 92–149
5 1 5 14 25 43–49 58–87 80–143 101–216 125–316 143–442
6 1 6 18 35–41 58–87 102–165 113–298 127–495 169–780 179–1171
7 1 7 23 49–61 80–143 113–298 205–540 216–1031 233–1713 289–2826
8 1 8 28 56–84 101–216 127–495 216–1031 282–1870 317–3583 317-6090
9 1 9 36 73–115 125–316 169–780 233–1713 317–3583 565–6588 580–12677
10 1 10 40–43 92–149 143–442 179–1171 289–2826 317-6090 580–12677 798–23556

### Ramsey's theorem for hypergraph

 Ramsey's Theorem (hypergraph, multicolor) Let $\displaystyle{ r, t, k_1,k_2,\ldots,k_r }$ be positive integers. Then there exists an integer $\displaystyle{ R_t(r;k_1,k_2,\ldots,k_r) }$ satisfying: For any $\displaystyle{ r }$-coloring of $\displaystyle{ {[n]\choose t} }$ with $\displaystyle{ n\ge R_t(r;k_1,k_2,\ldots,k_r) }$, there exist an $\displaystyle{ i\in\{1,2,\ldots,r\} }$ and a subset $\displaystyle{ X\subseteq [n] }$ with $\displaystyle{ |X|\ge k_i }$ such that all members of $\displaystyle{ {X\choose t} }$ are colored with the $\displaystyle{ i }$th color.

$\displaystyle{ n\rightarrow(k_1,k_2,\ldots,k_r)^t }$

 Lemma (the "mixing color" trick) $\displaystyle{ R_t(r;k_1,k_2,\ldots,k_r)\le R_t(r-1;k_1,k_2,\ldots,k_{r-2},R_t(2;k_{r-1},k_r)) }$

It is then sufficient to prove the Ramsey's theorem for the two-coloring of a hypergraph, that is, to prove $\displaystyle{ R_t(k,\ell)=R_t(2;k,\ell) }$ is finite.

 Lemma $\displaystyle{ R_t(k,\ell)\le R_{t-1}(R_t(k-1,\ell),R_t(k,\ell-1))+1 }$
Proof.
 Let $\displaystyle{ n=R_{t-1}(R_t(k-1,\ell),R_t(k,\ell-1))+1 }$. Denote $\displaystyle{ [n]=\{1,2,\ldots,n\} }$. Let $\displaystyle{ f:{[n]\choose t}\rightarrow\{{\color{red}\text{red}},{\color{blue}\text{blue}}\} }$ be an arbitrary 2-coloring of $\displaystyle{ {[n]\choose t} }$. It is then sufficient to show that there either exists an $\displaystyle{ X\subseteq[n] }$ with $\displaystyle{ |X|=k }$ such that all members of $\displaystyle{ {X\choose t} }$ are colored red by $\displaystyle{ f }$; or exists an $\displaystyle{ X\subseteq[n] }$ with $\displaystyle{ |X|=\ell }$ such that all members of $\displaystyle{ {X\choose t} }$ are colored blue by $\displaystyle{ f }$. We remove $\displaystyle{ n }$ from $\displaystyle{ [n] }$ and define a new coloring $\displaystyle{ f' }$ of $\displaystyle{ {[n-1]\choose t-1} }$ by $\displaystyle{ f'(A)=f(A\cup\{n\}) }$ for any $\displaystyle{ A\in{[n-1]\choose t-1} }$. By the choice of $\displaystyle{ n }$ and by symmetry, there exists a subset $\displaystyle{ S\subseteq[n-1] }$ with $\displaystyle{ |X|=R_t(k-1,\ell) }$ such that all members of $\displaystyle{ {S\choose t-1} }$ are colored with red by $\displaystyle{ f' }$. Then there either exists an $\displaystyle{ X\subseteq S }$ with $\displaystyle{ |X|=\ell }$ such that $\displaystyle{ {X\choose t} }$ is colored all blue by $\displaystyle{ f }$, in which case we are done; or exists an $\displaystyle{ X\subseteq S }$ with $\displaystyle{ |X|=k-1 }$ such that $\displaystyle{ {X\choose t} }$ is colored all red by $\displaystyle{ f }$. Next we prove that in the later case $\displaystyle{ {X\cup{n}\choose t} }$ is all red, which will close our proof. Since all $\displaystyle{ A\in{S\choose t-1} }$ are colored with red by $\displaystyle{ f' }$, then by our definition of $\displaystyle{ f' }$, $\displaystyle{ f(A\cup\{n\})={\color{red}\text{red}} }$ for all $\displaystyle{ A\in {X\choose t-1}\subseteq{S\choose t-1} }$. Recalling that $\displaystyle{ {X\choose t} }$ is colored all red by $\displaystyle{ f }$, $\displaystyle{ {X\cup\{n\}\choose t} }$ is colored all red by $\displaystyle{ f }$ and we are done.
$\displaystyle{ \square }$

## Applications of Ramsey Theorem

### The "Happy Ending" problem

 The happy ending problem Any set of 5 points in the plane, no three on a line, has a subset of 4 points that form the vertices of a convex quadrilateral.

See the article [1] for the proof.

We say a set of points in the plane in general positions if no three of the points are on the same line.

 Theorem (Erdős-Szekeres 1935) For any positive integer $\displaystyle{ m\ge 3 }$, there is an $\displaystyle{ N(m) }$ such that any set of at least $\displaystyle{ N(m) }$ points in general position in the plane (i.e., no three of the points are on a line) contains $\displaystyle{ m }$ points that are the vertices of a convex $\displaystyle{ m }$-gon.
Proof.
 Let $\displaystyle{ N(m)=R_3(m,m) }$. For $\displaystyle{ n\ge N(m) }$, let $\displaystyle{ X }$ be an arbitrary set of $\displaystyle{ n }$ points in the plane, no three of which are on a line. Define a 2-coloring of the 3-subsets of points $\displaystyle{ f:{X\choose 3}\rightarrow\{0,1\} }$ as follows: for any $\displaystyle{ \{a,b,c\}\in{X\choose 3} }$, let $\displaystyle{ \triangle_{abc}\subset X }$ be the set of points covered by the triangle $\displaystyle{ abc }$; and $\displaystyle{ f(\{a,b,c\})=|\triangle_{abc}|\bmod 2 }$, that is, $\displaystyle{ f(\{a,b,c\}) }$ indicates the oddness of the number of points covered by the triangle $\displaystyle{ abc }$. Since $\displaystyle{ |X|\ge R_3(m,m) }$, there exists a $\displaystyle{ Y\subseteq X }$ such that $\displaystyle{ |Y|=m }$ and all members of $\displaystyle{ {Y\choose 3} }$ are colored with the same value by $\displaystyle{ f }$. We claim that the $\displaystyle{ m }$ points in $\displaystyle{ Y }$ are the vertices of a convex $\displaystyle{ m }$-gon. If otherwise, by the definition of convexity, there exist $\displaystyle{ \{a,b,c,d\}\subseteq Y }$ such that $\displaystyle{ d\in\triangle_{abc} }$. Since no three points are in the same line, $\displaystyle{ \triangle_{abc}=\triangle_{abd}\cup\triangle_{acd}\cup\triangle_{bcd}\cup\{d\} }$, where all unions are disjoint. Then $\displaystyle{ |\triangle_{abc}|=|\triangle_{abd}|+|\triangle_{acd}|+|\triangle_{bcd}|+1 }$, which implies that $\displaystyle{ f(\{a,b,c\}), f(\{a,b,d\}), f(\{a,c,d\}), f(\{b,c,d\})\, }$ cannot be equal, contradicting that all members of $\displaystyle{ {Y\choose 3} }$ have the same color.
$\displaystyle{ \square }$

### Yao's lower bound on implicit data structures

 Lemma Let $\displaystyle{ n\ge 2 }$ be a power of 2 and $\displaystyle{ N\ge 2n }$. Suppose the universe is $\displaystyle{ [N] }$ and the size of the data set is $\displaystyle{ n }$. If the data structure is a sorted table, any search algorithm requires at least $\displaystyle{ \log n }$ accesses to the data structure in the worst case.
Proof.
 We will show by an adversarial argument that $\displaystyle{ \log n }$ accesses are required to search for the key value $\displaystyle{ x=n }$ from the universe $\displaystyle{ [N]=\{1,2,\ldots,N\} }$. The construction of the adversarial data set $\displaystyle{ S }$ is by induction on $\displaystyle{ n }$. For $\displaystyle{ n=2 }$ and $\displaystyle{ N\ge 2n-1=3 }$ it is easy to see that two accesses are necessary. Let $\displaystyle{ n\gt 2 }$. Assume the induction hypothesis to be true for all smaller $\displaystyle{ n }$; we will prove it for the size of data set $\displaystyle{ n }$, size of universe $\displaystyle{ N\ge 2n }$ and the search key $\displaystyle{ x=n }$. Suppose that the first access position is $\displaystyle{ k }$. The adversary chooses the table content $\displaystyle{ T[k] }$. The adversary's strategy is: \displaystyle{ \begin{align} T[k]= \begin{cases} k & k\le \frac{n}{2},\\ N-(n-k) & k\gt \frac{n}{2}. \end{cases} \end{align} } By symmetry, suppose it is the first case that $\displaystyle{ k\le \frac{n}{2} }$. Then the key $\displaystyle{ x=n }$ may be in any position $\displaystyle{ i }$, where $\displaystyle{ n/2+1\le i\le n }$. In fact, $\displaystyle{ T[ n/2+1] }$ through $\displaystyle{ T[n] }$ is a sorted table of size $\displaystyle{ n'=n/2 }$ which may contain any $\displaystyle{ n' }$-subset of $\displaystyle{ \{n/2+1, n/2+2,\ldots,N\} }$, and hence, in particular, any $\displaystyle{ n' }$-subset of the universe $\displaystyle{ U'=\{n/2+1, n/2+2,\ldots,N-n/2\} }$. The size $\displaystyle{ N' }$ of $\displaystyle{ U' }$ satisfies $\displaystyle{ N'=N-n/2-n/2\ge 2n-n\ge 2n' }$, and the desired key $\displaystyle{ n }$ has the relative value $\displaystyle{ x'=n- n/2=n' }$ in the universe $\displaystyle{ U' }$. By the induction hypothesis, $\displaystyle{ \log n'=-1+\log n }$ more accesses will be required. Hence the total number of accesses is at least $\displaystyle{ 1+\log n'=\log n }$. If the first access is $\displaystyle{ k\gt \frac{n}{2} }$, we symmetrically get that $\displaystyle{ T[1] }$ through $\displaystyle{ T[n/2] }$ is a sorted table of size $\displaystyle{ n'=n/2 }$ which may contain any $\displaystyle{ n' }$-subset of the universe $\displaystyle{ U'=\{n/2+1, n/2+2,\ldots,N-n/2\} }$. The rest is the same.
$\displaystyle{ \square }$

We have seen that on a sorted table, there is no search algorithm outperforming the binary search in the worst case. Our question is:

Is there any other order than the increasing order, on which there is a better search algorithm?

An implicit data structure use no extra space in addition to the original data set, thus a data structure can only be represented implicitly by the order of the data items in the table. That is, each data set is stored as a permutation of the set. Formally, an implicit data structure is a function

$\displaystyle{ f:{U\choose n}\rightarrow[n!] }$,

where each $\displaystyle{ \pi\in[n!] }$ specify a permutation of the sorted table. Thus, the sorted table is the simplest implicit data structure, in which $\displaystyle{ f(S) }$ is the identity for all $\displaystyle{ S\in{U\choose n} }$.

## Ramsey-like Theorems

### Van der Waerden's Theorem

 Theorem (Van der Waerden 1927) For every choice of positive integers $\displaystyle{ r }$ and $\displaystyle{ t }$, there exists an integer $\displaystyle{ W(r,t) }$ such that for every $\displaystyle{ r }$-coloring of $\displaystyle{ [n] }$ where $\displaystyle{ n\ge W(r,t) }$, there exists a monochromatic arithmetic progression of length $\displaystyle{ t }$.

### Hales–Jewett Theorem

 Theorem (Hales-Jewett 1963) Let $\displaystyle{ A }$ be a finte alphabet of $\displaystyle{ t }$ symbols and let $\displaystyle{ r }$ be a positive integer. Then there exists an integer $\displaystyle{ \mathrm{HJ}(r,t) }$ such that for every $\displaystyle{ r }$-coloring of the cube $\displaystyle{ A^n }$ where $\displaystyle{ n\ge \mathrm{HJ}(r,t) }$, there exists a combinatorial line, which is monochromatic.
 Theorem (Hales-Jewett 1963) Let $\displaystyle{ A }$ be a finte alphabet of $\displaystyle{ t }$ symbols and let $\displaystyle{ m,r }$ be positive integers. Then there exists an integer $\displaystyle{ \mathrm{HJ}(m,r,t) }$ such that for every $\displaystyle{ r }$-coloring of the cube $\displaystyle{ A^n }$ where $\displaystyle{ n\ge \mathrm{HJ}(r,t) }$, there exists a combinatorial $\displaystyle{ m }$-space, which is monochromatic.