View source for Combinatorics (Fall 2010)/Ramsey theory

== Ramsey's Theorem ==
=== Ramsey's theorem for graph ===
{{Theorem|Ramsey's Theorem|
:Let <math>k,\ell</math> be positive integers. Then there exists an integer <math>R(k,\ell)</math> satisfying:
:If <math>n\ge R(k,\ell)</math>, for any coloring of edges of <math>K_n</math> with two colors red and blue, there exists a red <math>K_k</math> or a blue <math>K_\ell</math>.
}}
{{Proof|
We show that <math>R(k,\ell)</math> is finite by induction on <math>k+\ell</math>. For the base case, it is easy to verify that
:<math>R(k,1)=R(1,\ell)=1</math>.
For general <math>k</math> and <math>\ell</math>, we will show that 
:<math>R(k,\ell)\le R(k,\ell-1)+R(k-1,\ell)</math>.
Suppose we have a two coloring of <math>K_n</math>, where <math>n=R(k,\ell-1)+R(k-1,\ell)</math>. Take an arbitrary vertex <math>v</math>, and split <math>V\setminus\{v\}</math> into two subsets <math>S</math> and <math>T</math>, where
:<math>\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}</math>
Since 
:<math>|S|+|T|+1=n=R(k,\ell-1)+R(k-1,\ell)</math>,
we have either <math>|S|\ge R(k,\ell-1)</math> or <math>|T|\ge R(k-1,\ell)</math>. By symmetry, suppose <math>|S|\ge R(k,\ell-1)</math>. By induction hypothesis, the complete subgraph defined on <math>S</math> has either a red <math>K_k</math>, in which case we are done; or a blue <math>K_{\ell-1}</math>, in which case the complete subgraph defined on <math>S\cup{v}</math> must have a blue <math>K_\ell</math> since all edges from <math>v</math> to vertices in <math>S</math> are blue.
}}

{{Theorem|Ramsey's Theorem (graph, multicolor)|
:Let <math>r, k_1,k_2,\ldots,k_r</math> be positive integers. Then there exists an integer <math>R(r;k_1,k_2,\ldots,k_r)</math> satisfying:
:For any <math>r</math>-coloring of a complete graph of <math>n\ge R(r;k_1,k_2,\ldots,k_r)</math> vertices, there exists a monochromatic <math>k_i</math>-clique with the <math>i</math>th color for some <math>i\in\{1,2,\ldots,r\}</math>.
}}

{{Theorem|Lemma (the "mixing color" trick)|
:<math>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))</math>
}}
{{Proof|
We transfer the <math>r</math>-coloring to <math>(r-1)</math>-coloring by identifying the <math>(r-1)</math>th and the <math>r</math>th colors. 

If <math>n\ge R(r-1;k_1,k_2,\ldots,k_{r-2},R(2;k_{r-1},k_r))</math>, then for any <math>r</math>-coloring of <math>K_n</math>, there either exist an <math>i\in\{1,2,\ldots,r-2\}</math> and a <math>k_i</math>-clique which is monochromatically colored with the <math>i</math>th color; or exists clique of <math>R(2;k_{r-1},k_r)</math> vertices which is monochromatically colored with the mixed color of the original <math>(r-1)</math>th and <math>r</math>th colors, which again implies that there exists either a <math>k</math>-clique which is monochromatically colored with the original <math>(r-1)</math>th color, or a <math>\ell</math>-clique which is monochromatically colored with the original <math>r</math>th color. This implies the recursion.
}}

=== Ramsey number ===
The smallest number <math>R(k,\ell)</math> satisfying the condition in the Ramsey theory is called the '''Ramsey number'''. 

Alternatively, we can define <math>R(k,\ell)</math> as the smallest <math>N</math> such that if <math>n\ge N</math>, for any 2-coloring of <math>K_n</math> in red and blue, there is either a red <math>K_k</math> or a blue <math>K_\ell</math>. The Ramsey theorem is stated as:
:"''<math>R(k,\ell)</math> is finite for any positive integers <math>k</math> and <math>\ell</math>.''"

The core of the inductive proof of the Ramsey theorem is the following recursion
:<math>\begin{align}
R(k,1) &=R(1,\ell)=1\\
R(k,\ell) &\le R(k,\ell-1)+R(k-1,\ell).
\end{align}</math>

From this recursion, we can deduce an upper bound for the Ramsey number.
{{Theorem|Theorem|
:<math>R(k,\ell)\le{k+\ell-2\choose k-1}</math>.
}}
{{Proof|It is easy to verify the bound by induction.
}}

=== Lovász local lemma===
Consider a set of "bad" events <math>A_1,A_2,\ldots,A_n</math>. Suppose that <math>\Pr[A_i]\le p</math> for all <math>1\le i\le n</math>. 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
:<math>
\Pr\left[\bigwedge_{i=1}^n\overline{A_i}\right]>0.
</math>
;Case 1<nowiki>: mutually independent events.</nowiki>
If all the bad events <math>A_1,A_2,\ldots,A_n</math> are mutually independent, then
:<math>
\Pr\left[\bigwedge_{i=1}^n\overline{A_i}\right]\ge(1-p)^n>0,
</math>
for any <math>p<1</math>.

;Case 2<nowiki>: arbitrarily dependent events.</nowiki>
On the other hand, if we put no assumption on the dependencies between the events, then by the union bound (which holds unconditionally),
:<math>
\Pr\left[\bigwedge_{i=1}^n\overline{A_i}\right]=1-\Pr\left[\bigvee_{i=1}^n A_i\right]\ge 1-np,
</math>
which is not an interesting bound for <math>p\ge\frac{1}{n}</math>. 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'''.

{{Theorem
|Definition|
:Let <math>A_1,A_2,\ldots,A_n</math> be a set of events. A graph <math>D=(V,E)</math> on the set of vertices <math>V=\{1,2,\ldots,n\}</math> is called a '''dependency graph''' for the events <math>A_1,\ldots,A_n</math> if for each <math>i</math>, <math>1\le i\le n</math>, the event <math>A_i</math> is mutually independent of all the events <math>\{A_j\mid (i,j)\not\in E\}</math>.
}}

;Example
:Let <math>X_1,X_2,\ldots,X_m</math> be a set of ''mutually independent'' random variables. Each event <math>A_i</math> is a predicate defined on a number of variables among <math>X_1,X_2,\ldots,X_m</math>. Let <math>v(A_i)</math> be the unique smallest set of variables which determine <math>A_i</math>. The dependency graph <math>D=(V,E)</math> is defined by 
:::<math>(i,j)\in E</math> iff <math>v(A_i)\cap v(A_j)\neq \emptyset</math>.

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.

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

We will prove a general version of the local lemma, where the events <math>A_i</math> are not symmetric. This generalization is due to Spencer.
{{Theorem
|Lovász Local Lemma (general case)|
:Let <math>D=(V,E)</math> be the dependency graph of events <math>A_1,A_2,\ldots,A_n</math>. Suppose there exist real numbers <math>x_1,x_2,\ldots, x_n</math> such that <math>0\le x_i<1</math> and for all <math>1\le i\le n</math>,
::<math>\Pr[A_i]\le x_i\prod_{(i,j)\in E}(1-x_j)</math>.
:Then 
::<math>\Pr\left[\bigwedge_{i=1}^n\overline{A_i}\right]\ge\prod_{i=1}^n(1-x_i)</math>.
}}
{{Proof|
We can use the following probability identity to compute the probability of the intersection of events:
{{Theorem|Lemma 1|
:<math>\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]</math>.
}}
{{Proof|
By definition of conditional probability,
:<math>
\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]}</math>,
so we have
:<math>\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]</math>.
The lemma is proved by recursively applying this equation.
}}

Next we prove by induction on <math>m</math> that for any set of <math>m</math> events <math>i_1,\ldots,i_m</math>,
:<math>\Pr\left[A_{i_1}\mid \bigwedge_{j=2}^m\overline{A_{i_j}}\right]\le x_{i_1}</math>.
The local lemma is a direct consequence of this by applying Lemma 1.

For <math>m=1</math>, this is obvious. For general <math>m</math>, let <math>i_2,\ldots,i_k</math> be the set of vertices adjacent to  <math>i_1</math> in the dependency graph. Clearly <math>k-1\le d</math>. And it holds that
:<math>
\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]}
</math>,
which is due to the basic conditional probability identity
:<math>\Pr[A\mid BC]=\frac{\Pr[AB\mid C]}{\Pr[B\mid C]}</math>.
We bound the numerator
:<math>
\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}
</math>
The equation is due to the independence between <math>A_{i_1}</math> and <math>A_{i_k+1},\ldots,A_{i_m}</math>.

The denominator can be expanded using Lemma 1 as
:<math>
\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]
</math>
which by the induction hypothesis, is at least 
:<math>
\prod_{j=2}^k(1-x_{i_j})=\prod_{\{i_1,i_j\}\in E}(1-x_j)
</math>
where <math>E</math> is the edge set of the dependency graph.

Therefore,
:<math>
\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}.
</math>
Applying Lemma 1, 
:<math>
\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}
</math>
}}

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

If the following conditions are satisfied:
:#for all <math>1\le i\le n</math>, <math>\Pr[A_i]\le p</math>;
:#<math>ep(d+1)\le 1</math>;
then for all <math>1\le i\le n</math>,
:<math>\Pr[A_i]\le p\le\frac{1}{e(d+1)}<\frac{1}{d+1}\left(1-\frac{1}{d+1}\right)^d\le x_i\prod_{(i,j)\in E}(1-x_j)</math>.
Due to the local lemma for general cases, this implies that
:<math>\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>0</math>.
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|Theorem|
:<math>R(k,k)\ge Ck2^{k/2}</math> for some constant <math>C>0</math>.
}}
{{Proof|
To prove a lower bound <math>R(k,k)>n</math>, it is sufficient to show that there exists a 2-coloring of <math>K_n</math> without a monochromatic <math>K_k</math>. We prove this by the probabilistic method.

Pick a random 2-coloring of <math>K_n</math> by coloring each edge uniformly and independently with one of the two colors. For any set <math>S</math> of <math>k</math> vertices, let <math>A_S</math> denote the event that <math>S</math> forms a monochromatic <math>K_k</math>. It is easy to see that <math>\Pr[A_s]=2^{1-{k\choose 2}}=p</math>.

For any <math>k</math>-subset <math>T</math> of vertices, <math>A_S</math> and <math>A_T</math> are dependent if and only if <math>|S\cap T|\ge 2</math>. For each <math>S</math>, the number of <math>T</math> that <math>|S\cap T|\ge 2</math> is at most <math>{k\choose 2}{n\choose k-2}</math>, so the max degree of the dependency graph is <math>d\le{k\choose 2}{n\choose k-2}</math>.

Take <math>n=Ck2^{k/2}</math> for some appropriate constant <math>C>0</math>.
:<math>
\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}
</math>
Applying the local lemma, the probability that there is no monochromatic <math>K_k</math> is 
:<math>\Pr\left[\bigwedge_{S\in{[n]\choose k}}\overline{A_S}\right]>0</math>.
Therefore, there exists a 2-coloring of <math>K_n</math> which has no monochromatic <math>K_k</math>, which means
:<math>R(k,k)>n=Ck2^{k/2}</math>.
}}

{{Theorem|Theorem|
:<math>\Omega\left(k2^{k/2}\right)\le R(k,k)\le{2k-2\choose k-1}=O\left(k^{-1/2}4^{k}\right)</math>.
}}

{| class="wikitable"
! ''<math>k</math>'',''<math>l</math>''
! 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 ===
{{Theorem|Ramsey's Theorem (hypergraph, multicolor)|
:Let <math>r, t, k_1,k_2,\ldots,k_r</math> be positive integers. Then there exists an integer <math>R_t(r;k_1,k_2,\ldots,k_r)</math> satisfying:
:For any <math>r</math>-coloring of <math>{[n]\choose t}</math> with <math>n\ge R_t(r;k_1,k_2,\ldots,k_r)</math>,  there exist an <math>i\in\{1,2,\ldots,r\}</math> and  a subset <math>X\subseteq [n]</math> with <math>|X|\ge k_i</math> such that all members of <math>{X\choose t}</math> are colored with the <math>i</math>th color.
}}

<math>n\rightarrow(k_1,k_2,\ldots,k_r)^t</math>

{{Theorem|Lemma (the "mixing color" trick)|
:<math>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))</math>
}}

It is then sufficient to prove the Ramsey's theorem for the two-coloring of a hypergraph, that is, to prove <math>R_t(k,\ell)=R_t(2;k,\ell)</math> is finite.

{{Theorem|Lemma|
:<math>R_t(k,\ell)\le R_{t-1}(R_t(k-1,\ell),R_t(k,\ell-1))+1</math>
}}
{{Proof|
Let <math>n=R_{t-1}(R_t(k-1,\ell),R_t(k,\ell-1))+1</math>. Denote <math>[n]=\{1,2,\ldots,n\}</math>.

Let <math>f:{[n]\choose t}\rightarrow\{{\color{red}\text{red}},{\color{blue}\text{blue}}\}</math> be an arbitrary 2-coloring of <math>{[n]\choose t}</math>. It is then sufficient to show that there either exists an <math>X\subseteq[n]</math> with <math>|X|=k</math> such that all members of <math>{X\choose t}</math> are colored red by <math>f</math>; or exists an <math>X\subseteq[n]</math> with <math>|X|=\ell</math> such that all members of <math>{X\choose t}</math> are colored blue by <math>f</math>.

We remove <math>n</math> from <math>[n]</math> and define a new coloring <math>f'</math> of <math>{[n-1]\choose t-1}</math> by
:<math>f'(A)=f(A\cup\{n\})</math> for any <math>A\in{[n-1]\choose t-1}</math>.
By the choice of <math>n</math> and by symmetry, there exists a subset <math>S\subseteq[n-1]</math> with <math>|X|=R_t(k-1,\ell)</math> such that all members of <math>{S\choose t-1}</math> are colored with red by <math>f'</math>. Then there either exists an <math>X\subseteq S</math> with <math>|X|=\ell</math> such that <math>{X\choose t}</math> is colored all blue by <math>f</math>, in which case we are done; or exists an <math>X\subseteq S</math> with <math>|X|=k-1</math> such that <math>{X\choose t}</math> is colored all red by <math>f</math>. Next we prove that in the later case <math>{X\cup{n}\choose t}</math> is all red, which will close our proof. Since all <math>A\in{S\choose t-1}</math> are colored with red by <math>f'</math>, then by our definition of <math>f'</math>, <math>f(A\cup\{n\})={\color{red}\text{red}}</math> for all <math>A\in {X\choose t-1}\subseteq{S\choose t-1}</math>. Recalling that <math>{X\choose t}</math> is colored all red by <math>f</math>, <math>{X\cup\{n\}\choose t}</math> is colored all red by <math>f</math> and we are done.
}}

==  Applications of Ramsey Theorem ==
=== The "Happy Ending" problem ===
{{Theorem|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
[http://www.maa.org/mathland/mathtrek_10_3_00.html] for the proof.

We say a set of points in the plane in [http://en.wikipedia.org/wiki/General_position '''general positions'''] if no three of the points are on the same line.

{{Theorem|Theorem (Erdős-Szekeres 1935)|
:For any positive integer <math>m\ge 3</math>, there is an <math>N(m)</math> such that any set of at least <math>N(m)</math> points in general position in the plane (i.e., no three of the points are on a line) contains <math>m</math> points that are the vertices of a convex <math>m</math>-gon.
}}
{{Proof|
Let <math>N(m)=R_3(m,m)</math>. For <math>n\ge N(m)</math>, let <math>X</math> be an arbitrary set of <math>n</math> points in the plane, no three of which are on a line. Define a 2-coloring of the 3-subsets of points <math>f:{X\choose 3}\rightarrow\{0,1\}</math> as follows: for any <math>\{a,b,c\}\in{X\choose 3}</math>, let <math>\triangle_{abc}\subset X</math> be the set of points covered by the triangle <math>abc</math>; and <math>f(\{a,b,c\})=|\triangle_{abc}|\bmod 2</math>, that is, <math>f(\{a,b,c\})</math> indicates the oddness of the number of points covered by the triangle <math>abc</math>.

Since <math>|X|\ge R_3(m,m)</math>, there exists a <math>Y\subseteq X</math> such that <math>|Y|=m</math> and all members of <math>{Y\choose 3}</math> are colored with the same value by <math>f</math>. 

We claim that the <math>m</math> points in <math>Y</math> are the vertices of a convex <math>m</math>-gon. If otherwise, by the definition of convexity, there exist <math>\{a,b,c,d\}\subseteq Y</math> such that <math>d\in\triangle_{abc}</math>. Since no three points are in the same line, 
:<math>\triangle_{abc}=\triangle_{abd}\cup\triangle_{acd}\cup\triangle_{bcd}\cup\{d\}</math>,
where all unions are disjoint. Then <math>|\triangle_{abc}|=|\triangle_{abd}|+|\triangle_{acd}|+|\triangle_{bcd}|+1</math>, which implies that <math>f(\{a,b,c\}), f(\{a,b,d\}), f(\{a,c,d\}), f(\{b,c,d\})\,</math> cannot be equal, contradicting that all members of <math>{Y\choose 3}</math> have the same color.
}}

=== Yao's lower bound on implicit data structures ===
{{Theorem|Lemma|
:Let <math>n\ge 2</math> be a power of 2 and <math>N\ge 2n</math>. Suppose the universe is <math>[N]</math> and the size of the data set is <math>n</math>.
:If the data structure is a sorted table, any search algorithm requires at least <math>\log n</math> accesses to the data structure in the worst case.
}}
{{Proof|
We will show by an adversarial argument that <math>\log n</math> accesses are required to search for the key value <math>x=n</math> from the universe <math>[N]=\{1,2,\ldots,N\}</math>. The construction of the adversarial data set <math>S</math> is by induction on <math>n</math>.

For <math>n=2</math> and <math>N\ge 2n-1=3</math> it is easy to see that two accesses are necessary.

Let <math>n>2</math>. Assume the induction hypothesis to be true for all smaller <math>n</math>; we will prove it for the size of data set <math>n</math>, size of universe <math>N\ge 2n</math> and the search key <math>x=n</math>.

Suppose that the first access position is <math>k</math>. The adversary chooses the table content <math>T[k]</math>. The adversary's strategy is:
:<math>
\begin{align}
T[k]=
\begin{cases}
k & k\le \frac{n}{2},\\
N-(n-k) & k> \frac{n}{2}.
\end{cases}
\end{align}
</math>
By symmetry, suppose it is the first case that <math>k\le \frac{n}{2}</math>.  Then the key <math>x=n</math> may be in any position <math>i</math>, where <math>n/2+1\le i\le n</math>. In fact, <math>T[ n/2+1]</math> through <math>T[n]</math> is a sorted table of size <math>n'=n/2</math> which may contain any <math>n'</math>-subset of <math>\{n/2+1, n/2+2,\ldots,N\}</math>, and hence, in particular, any <math>n'</math>-subset of the universe
:<math>U'=\{n/2+1, n/2+2,\ldots,N-n/2\}</math>.
The size <math>N'</math> of <math>U'</math> satisfies
:<math>N'=N-n/2-n/2\ge 2n-n\ge 2n'</math>,
and the desired key <math>n</math> has the relative value <math>x'=n- n/2=n'</math> in the universe <math>U'</math>. 

By the induction hypothesis, <math>\log n'=-1+\log n</math> more accesses will be required. Hence the total number of accesses is at least <math>1+\log n'=\log n</math>.

If the first access is <math>k> \frac{n}{2}</math>, we symmetrically get that <math>T[1]</math> through <math>T[n/2]</math> is a sorted table of size <math>n'=n/2</math> which may contain any <math>n'</math>-subset of the universe
:<math>U'=\{n/2+1, n/2+2,\ldots,N-n/2\}</math>.
The rest is the same.
}}


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
:<math>f:{U\choose n}\rightarrow[n!]</math>,
where each <math>\pi\in[n!]</math> specify a permutation of the sorted table. Thus, the sorted table is the simplest implicit data structure, in which <math>f(S)</math> is the identity for all <math>S\in{U\choose n}</math>.

== Ramsey-like Theorems ==
=== Van der Waerden's Theorem ===
{{Theorem|Theorem (Van der Waerden 1927)|
:For every choice of positive integers <math>r</math> and <math>t</math>, there exists an integer <math>W(r,t)</math> such that for every <math>r</math>-coloring of <math>[n]</math> where <math>n\ge W(r,t)</math>, there exists a monochromatic arithmetic progression of length <math>t</math>.
}}

=== Hales–Jewett Theorem ===
{{Theorem|Theorem (Hales-Jewett 1963)|
:Let <math>A</math> be a finte alphabet of <math>t</math> symbols and let <math>r</math> be a positive integer. Then there exists an integer <math>\mathrm{HJ}(r,t)</math> such that for every <math>r</math>-coloring of the cube <math>A^n</math> where <math>n\ge \mathrm{HJ}(r,t)</math>, there exists a combinatorial line, which is monochromatic.
}}

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