# 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\geq 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 )\leq 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{aligned}S&=\{u\in V\setminus \{v\}\mid uv{\text{ is blue }}\}\\T&=\{u\in V\setminus \{v\}\mid uv{\text{ is red }}\}\end{aligned}}} Since ${\displaystyle |S|+|T|+1=n=R(k,\ell -1)+R(k-1,\ell )}$, we have either ${\displaystyle |S|\geq R(k,\ell -1)}$ or ${\displaystyle |T|\geq R(k-1,\ell )}$. By symmetry, suppose ${\displaystyle |S|\geq 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\geq 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})\leq 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\geq 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\geq 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{aligned}R(k,1)&=R(1,\ell )=1\\R(k,\ell )&\leq R(k,\ell -1)+R(k-1,\ell ).\end{aligned}}}

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

 Theorem ${\displaystyle R(k,\ell )\leq {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}]\leq p}$ for all ${\displaystyle 1\leq i\leq 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]>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]\geq (1-p)^{n}>0,}$

for any ${\displaystyle p<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]\geq 1-np,}$

which is not an interesting bound for ${\displaystyle p\geq {\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\leq i\leq 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\leq i\leq n}$, ${\displaystyle \Pr[A_{i}]\leq 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)\leq 1}$. Then ${\displaystyle \Pr \left[\bigwedge _{i=1}^{n}{\overline {A_{i}}}\right]>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\leq x_{i}<1}$ and for all ${\displaystyle 1\leq i\leq n}$, ${\displaystyle \Pr[A_{i}]\leq x_{i}\prod _{(i,j)\in E}(1-x_{j})}$. Then ${\displaystyle \Pr \left[\bigwedge _{i=1}^{n}{\overline {A_{i}}}\right]\geq \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]\leq 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\leq 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{aligned}\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]&\leq \Pr \left[A_{i_{1}}\mid \bigwedge _{j=k+1}^{m}{\overline {A_{i_{j}}}}\right]\\&=\Pr[A_{i_{1}}]\\&\leq x_{i_{1}}\prod _{(i_{1},j)\in E}(1-x_{j}).\end{aligned}}}

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]\leq {\frac {x_{i_{1}}\prod _{(i_{1},j)\in E}(1-x_{j})}{\prod _{\{i_{1},i_{j}\}\in E}(1-x_{j})}}\leq x_{i_{1}}.}$

Applying Lemma 1,

{\displaystyle {\begin{aligned}\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)\\&\geq \prod _{i=1}^{n}\left(1-x_{i}\right).\end{aligned}}}
${\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}>{\frac {1}{\mathrm {e} }}}$.

If the following conditions are satisfied:

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

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

${\displaystyle \Pr[A_{i}]\leq p\leq {\frac {1}{e(d+1)}}<{\frac {1}{d+1}}\left(1-{\frac {1}{d+1}}\right)^{d}\leq 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]\geq \prod _{i=1}^{n}(1-x_{i})=\left(1-{\frac {1}{d+1}}\right)^{n}>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)\geq Ck2^{k/2}}$ for some constant ${\displaystyle C>0}$.
Proof.
 To prove a lower bound ${\displaystyle R(k,k)>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|\geq 2}$. For each ${\displaystyle S}$, the number of ${\displaystyle T}$ that ${\displaystyle |S\cap T|\geq 2}$ is at most ${\displaystyle {k \choose 2}{n \choose k-2}}$, so the max degree of the dependency graph is ${\displaystyle d\leq {k \choose 2}{n \choose k-2}}$. Take ${\displaystyle n=Ck2^{k/2}}$ for some appropriate constant ${\displaystyle C>0}$. {\displaystyle {\begin{aligned}\mathrm {e} p(d+1)&\leq \mathrm {e} 2^{1-{k \choose 2}}\left({k \choose 2}{n \choose k-2}+1\right)\\&\leq 2^{3-{k \choose 2}}{k \choose 2}{n \choose k-2}\\&\leq 1\end{aligned}}} 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]>0}$. Therefore, there exists a 2-coloring of ${\displaystyle K_{n}}$ which has no monochromatic ${\displaystyle K_{k}}$, which means ${\displaystyle R(k,k)>n=Ck2^{k/2}}$.
${\displaystyle \square }$
 Theorem ${\displaystyle \Omega \left(k2^{k/2}\right)\leq R(k,k)\leq {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\geq 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|\geq 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})\leq 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 )\leq 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\geq 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\geq 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|\geq 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\geq 2}$ be a power of 2 and ${\displaystyle N\geq 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\geq 2n-1=3}$ it is easy to see that two accesses are necessary. Let ${\displaystyle n>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\geq 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{aligned}T[k]={\begin{cases}k&k\leq {\frac {n}{2}},\\N-(n-k)&k>{\frac {n}{2}}.\end{cases}}\end{aligned}}} By symmetry, suppose it is the first case that ${\displaystyle k\leq {\frac {n}{2}}}$. Then the key ${\displaystyle x=n}$ may be in any position ${\displaystyle i}$, where ${\displaystyle n/2+1\leq i\leq 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\geq 2n-n\geq 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>{\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\geq 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\geq \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\geq \mathrm {HJ} (r,t)}$, there exists a combinatorial ${\displaystyle m}$-space, which is monochromatic.