组合数学 (Fall 2011)/Extremal set theory and 组合数学 (Fall 2011)/Ramsey theory: Difference between pages

From TCS Wiki
(Difference between pages)
Jump to navigation Jump to search
VisualWikitext
imported>Etone
 
imported>WikiSysop
 
Line 1: Line 1:
== Sperner system ==
== Ramsey's Theorem ==
A set family <math>\mathcal{F}\subseteq 2^X</math> with the relation <math>\subseteq</math> define a poset. Thus, a '''chain''' is a sequence <math>S_1\subseteq S_2\subseteq\cdots\subseteq S_k</math>.
=== Ramsey's theorem for graph ===
 
{{Theorem|Ramsey's Theorem|
A set family <math>\mathcal{F}\subseteq 2^X</math> is an '''antichain''' (also called a '''Sperner system''') if for all <math>S,T\in\mathcal{F}</math> that <math>S\neq T</math>, we have <math>S\not\subseteq T</math>.
: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>.
The <math>k</math>-uniform <math>{X\choose k}</math> is an antichain. Let <math>n=|X|</math>. The size of <math>{X\choose k}</math> is maximized when <math>k=\lfloor n/2\rfloor</math>. We wonder whether this is also the largest possible size of any antichain <math>\mathcal{F}\subseteq 2^X</math>.
}}
 
{{Proof|
In 1928, Emanuel Sperner proved a theorem saying that it is indeed the largest possible antichain. This result, called Sperner's theorem today, initiated the studies of extremal set theory.
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>.
{{Theorem|Theorem (Sperner 1928)|
For general <math>k</math> and <math>\ell</math>, we will show that
:Let <math>\mathcal{F}\subseteq 2^X</math> where <math>|X|=n</math>. If <math>\mathcal{F}</math> is an antichain, then
:<math>R(k,\ell)\le R(k,\ell-1)+R(k-1,\ell)</math>.
::<math>|\mathcal{F}|\le{n\choose \lfloor n/2\rfloor}</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.
}}
}}


=== First proof (shadows)===
{{Theorem|Ramsey's Theorem (graph, multicolor)|
We first introduce the original proof by Sperner, which uses concepts called '''shadows''' and '''shades''' of set systems.
: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|Definition|
:Let <math>|X|=n\,</math> and <math>\mathcal{F}\subseteq {X\choose k}</math>, <math>k<n\,</math>.  
:The '''shade''' of <math>\mathcal{F}</math> is defined to be
::<math>\nabla\mathcal{F}=\left\{T\in {X\choose k+1}\,\,\bigg|\,\, \exists S\in\mathcal{F}\mbox{ such that } S\subset T\right\}</math>.
:Thus the shade <math>\nabla\mathcal{F}</math> of <math>\mathcal{F}</math> consists of all subsets of <math>X</math> which can be obtained by adding an element to a set in <math>\mathcal{F}</math>.
:Similarly, the '''shadow''' of <math>\mathcal{F}</math> is defined to be
::<math>\Delta\mathcal{F}=\left\{T\in {X\choose k-1}\,\,\bigg|\,\, \exists S\in\mathcal{F}\mbox{ such that } T\subset S\right\}</math>.
:Thus the shadow <math>\Delta\mathcal{F}</math> of <math>\mathcal{F}</math> consists of all subsets of <math>X</math> which can be obtained by removing an element from a set in <math>\mathcal{F}</math>.
}}
}}


Next lemma bounds the effects of shadows and shades on the sizes of set systems.
{{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>
{{Theorem|Lemma (Sperner)|
:Let <math>|X|=n\,</math> and <math>\mathcal{F}\subseteq {X\choose k}</math>. Then
::<math>
\begin{align}
&|\nabla\mathcal{F}|\ge\frac{n-k}{k+1}|\mathcal{F}| &\text{ if } k<n\\
&|\Delta\mathcal{F}|\ge\frac{k}{n-k+1}|\mathcal{F}| &\text{ if } k>0.
\end{align}
</math>
}}
}}
{{Proof|
{{Proof|
The lemma is proved by double counting. We prove the inequality of <math>|\nabla\mathcal{F}|</math>. Assume that <math>0\le k<n</math>.
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.  
 
Define
:<math>\mathcal{R}=\{(S,T)\mid S\in\mathcal{F}, T\in\nabla\mathcal{F}, S\subset T\}</math>.
We estimate <math>|\mathcal{R}|</math> in two ways.
 
For each <math>S\in\mathcal{F}</math>, there are <math>n-k</math> different <math>T\in\nabla\mathcal{F}</math> that <math>S\subset T</math>.
:<math>|\mathcal{R}|=(n-k)|\mathcal{F}|</math>.
For each <math>T\in\nabla\mathcal{F}</math>, there are <math>k+1</math> ways to choose an <math>S\subset T</math> with <math>|S|=k</math>, some of which may not be in <math>\mathcal{F}</math>.
:<math>|\mathcal{R}|\le (k+1)|\nabla\mathcal{F}|</math>.
 
Altogether, we show that <math>|\nabla\mathcal{F}|\ge\frac{n-k}{k+1}|\mathcal{F}|</math>.


The inequality of <math>|\Delta\mathcal{F}|</math> can be proved in the same way.
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.
}}
}}


An immediate corollary of the previous lemma is as follows.
=== Ramsey number ===
The smallest number <math>R(k,\ell)</math> satisfying the condition in the Ramsey theory is called the '''Ramsey number'''.  


{{Theorem|Proposition 1|
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:
:If <math>k\le \frac{n-1}{2}</math>, then <math>|\nabla\mathcal{F}|\ge|\mathcal{F}|</math>.
:"''<math>R(k,\ell)</math> is finite for any positive integers <math>k</math> and <math>\ell</math>.''"
:If <math>k\ge \frac{n-1}{2}</math>, then <math>|\Delta\mathcal{F}|\ge|\mathcal{F}|</math>.
}}


The idea of Sperner's proof is pretty clear:  
The core of the inductive proof of the Ramsey theorem is the following recursion
* we "push up" all the sets in <math>\mathcal{F}</math> of size <math><\frac{n-1}{2}</math> replacing them by their shades;
:<math>\begin{align}
* and also "push down" all the sets in <math>\mathcal{F}</math> of size <math>\ge\frac{n+1}{2}</math> replacing them by their shadows.  
R(k,1) &=R(1,\ell)=1\\
Repeat this process we end up with a set system <math>\mathcal{F}\subseteq{X\choose \lfloor n/2\rfloor}</math>. We need to show that this process does not decrease the size of <math>\mathcal{F}</math>.
R(k,\ell) &\le R(k,\ell-1)+R(k-1,\ell).
\end{align}</math>


{{Theorem|Proposition 2|
From this recursion, we can deduce an upper bound for the Ramsey number.
:Suppose that <math>\mathcal{F}\subseteq2^X</math> where <math>|X|=n</math>. Let <math>\mathcal{F}_k=\mathcal{F}\ap{X\choose k}</math>. Let <math>k_\min</math> be the smallest <math>k</math> that <math>|\mathcal{F}_k|>0</math>, and let
{{Theorem|Theorem|
::<math>
:<math>R(k,\ell)\le{k+\ell-2\choose k-1}</math>.
\mathcal{F}'=\begin{cases}
\mathcal{F}\setminus\mathcal{F}_{k_\min}\cup \nabla\mathcal{F}_{k_\min} & \mbox{if }k_\min<\frac{n-1}{2},\\
\mathcal{F} & \mbox{otherwise.}
\end{cases}
</math>
:Similarly, let <math>k_\max</math> be the largest <math>k</math> that <math>|\mathcal{F}_k|>0</math>, and let
::<math>
\mathcal{F}''=\begin{cases}
\mathcal{F}\setminus\mathcal{F}_{k_\max}\cup \Delta\mathcal{F}_{k_\max} & \mbox{if }k_\max\ge\frac{n+1}{2},\\
\mathcal{F} & \mbox{otherwise.}
\end{cases}
</math>
:If <math>\mathcal{F}</math> is an antichain, <math>\mathcal{F}'</math> and <math>\mathcal{F}''</math> are antichains, and we have <math>|\mathcal{F}'|\ge|\mathcal{F}|</math> and <math>|\mathcal{F}''|\ge|\mathcal{F}|</math>.
}}
}}
{{Proof|
{{Proof|It is easy to verify the bound by induction.
We show that <math>\mathcal{F}'</math> is an antichain and <math>|\mathcal{F}'|\ge|\mathcal{F}|</math>.
 
First, observe that <math>\nabla\mathcal{F}_k\cap\mathcal{F}=\emptyset</math>, otherwise <math>\mathcal{F}</math> cannot be an antichain, and due to Proposition 1, <math>|\nabla\mathcal{F}_k|\ge|\mathcal{F}_k|</math> when <math>k\le \frac{n-1}{2}</math>, so <math>|\mathcal{F}'|=|\mathcal{F}|-|\mathcal{F}_k|+|\nabla\mathcal{F}_k|\ge |\mathcal{F}|</math>.
 
Now we prove that <math>\mathcal{F}'</math> is an antichain . By contradiction, assume that there are <math>S, T\in \mathcal{F}'</math>, such that <math>S\subset T</math>. One of the <math>S,T</math> must be in <math>\nabla\mathcal{F}_{k_\min}</math>, or otherwise <math>\mathcal{F}</math> cannot be an antichain. Recall that <math>k_\min</math> is the smallest <math>k</math> that <math>|\mathcal{F}_k|>0</math>, thus it must be <math>S\in \nabla\mathcal{F}_{k_\min}</math>, and <math>T\in\mathcal{F}</math>. This implies that there is an <math>R\in \mathcal{F}_{k_\min}\subseteq \mathcal{F}</math> such that <math>R\subset S\subset T</math>, which contradicts that <math>\mathcal{F}</math> is an antichain.
 
The statement for <math>\mathcal{F}''</math> can be proved in the same way.
}}
}}


Applying the above process, we prove the Sperner's theorem.
------
{{Prooftitle|Proof of Sperner's theorem | (original proof of Sperner)
Let <math>\mathcal{F}_k=\{S\in\mathcal{F}\mid |S|=k\}</math>, where <math>0\le k\le n</math>.
 
We change <math>\mathcal{F}</math> as follows:
* for the smallest <math>k</math> that <math>|\mathcal{F}_k|>0</math>, if <math>k<\frac{n-1}{2}</math>, replace <math>\mathcal{F}_k</math> by <math>\nabla\mathcal{F}_k</math>.
 
Due to Proposition 2, this procedure preserves <math>\mathcal{F}</math> as an antichain and does not decrease <math>|\mathcal{F}|</math>. Repeat this procedure, until <math>|\mathcal{F}_k|=0</math> for all <math>k<\frac{n-1}{2}</math>, that is, there is no member set of <math>\mathcal{F}</math> has size less than <math>\frac{n-1}{2}</math>.


We then define another symmetric procedure:
The following theorem is due to Spencer in 1975, which is the best known lower bound for diagonal Ramsey number.
* for the largest <math>k</math> that <math>|\mathcal{F}_k|>0</math>, if <math>k\ge\frac{n+1}{2}</math>, replace <math>\mathcal{F}_k</math> by <math>\Delta\mathcal{F}_k</math>.
Also due to Proposition 2, this procedure preserves <math>\mathcal{F}</math> as an antichain and does not decrease <math>|\mathcal{F}|</math>. After repeatedly applying this procedure, <math>|\mathcal{F}_k|=0</math> for all <math>k\ge\frac{n+1}{2}</math>.  


The resulting <math>\mathcal{F}</math> has <math>\mathcal{F}\subseteq{X\choose \lfloor n/2\rfloor}</math>, and since <math>|\mathcal{F}|</math> is never decreased, for the original <math>\mathcal{F}</math>, we have
{{Theorem|Theorem (Spencer 1975)|
:<math>|\mathcal{F}|\le {n\choose \lfloor n/2\rfloor}</math>.
:<math>R(k,k)\ge Ck2^{k/2}</math> for some constant <math>C>0</math>.
}}
}}


=== Second proof (counting)===
Its proof uses the Lovász local lemma in the probabilistic method.
We now introduce an elegant proof due to Lubell. The proof uses a counting argument, and tells more information than just the size of the set system.
{{Theorem
 
|Lovász Local Lemma (symmetric case)|
{{Prooftitle|Proof of Sperner's theorem | (Lubell 1966)
:Let <math>A_1,A_2,\ldots,A_n</math> be a set of events, and assume that the following hold:
Let <math>\pi</math> be a permutation of <math>X</math>. We say that an <math>S\subseteq X</math> '''prefixes''' <math>\pi</math>, if <math>S=\{\pi_1,\pi_2,\ldots, \pi_{|S|}\}</math>, that is, <math>S</math> is precisely the set of the first <math>|S|</math> elements in the permutation <math>\pi</math>.
:#for all <math>1\le i\le n</math>, <math>\Pr[A_i]\le p</math>;
 
:# each event <math>A_i</math> is independent of all but at most <math>d</math> other events, and
Fix an <math>S\subseteq X</math>. It is easy to see that the number of permutations <math>\pi</math> of <math>X</math> prefixed by <math>S</math> is <math>|S|!(n-|S|)!</math>.  Also, since <math>\mathcal{F}</math> is an antichain, no permutation <math>\pi</math> of <math>X</math> can be prefixed by more than one members of <math>\mathcal{F}</math>, otherwise one of the member sets must contain the other, which contradicts that <math>\mathcal{F}</math> is an antichain. Thus, the number of permutations <math>\pi</math> prefixed by some <math>S\in\mathcal{F}</math> is
:::<math>ep(d+1)\le 1</math>.
:<math>\sum_{S\in\mathcal{F}}|S|!(n-|S|)!</math>,
:Then
which cannot be larger than the total number of permutations, <math>n!</math>, therefore,
::<math>\Pr\left[\bigwedge_{i=1}^n\overline{A_i}\right]>0</math>.
:<math>\sum_{S\in\mathcal{F}}|S|!(n-|S|)!\le n!</math>.
Dividing both sides by <math>n!</math>, we have
:<math>\sum_{S\in\mathcal{F}}\frac{1}{{n\choose |S|}}=\sum_{S\in\mathcal{F}}\frac{|S|!(n-|S|)!}{n!}\le 1</math>,
where <math>{n\choose |S|}\le {n\choose \lfloor n/2\rfloor}</math>, so
:<math>\sum_{S\in\mathcal{F}}\frac{1}{{n\choose |S|}}\ge \frac{|\mathcal{F}|}{{n\choose \lfloor n/2\rfloor}}</math>.
Combining this with the above inequality, we prove the Sperner's theorem.
}}
}}


=== The LYM inequality ===
We can use the local lemma to prove a lower bound for the diagonal Ramsey number.
Lubell's proof proves the following inequality:
{{Proof|
:<math>\sum_{S\in\mathcal{F}}\frac{1}{{n\choose |S|}}\le 1</math>
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.
which is actually stronger than Sperner's original statement that <math>|\mathcal{F}|\le{n\choose \lfloor n/2\rfloor}</math>.
 
This inequality is independently discovered by Lubell-Yamamoto, Meschalkin, and Bollobás, and is called the LYM inequality today.


{{Theorem|Theorem (Lubell, Yamamoto 1954; Meschalkin 1963)|
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>.
:Let <math>\mathcal{F}\subseteq 2^X</math> where <math>|X|=n</math>. If <math>\mathcal{F}</math> is an antichain, then
::<math>\sum_{S\in\mathcal{F}}\frac{1}{{n\choose |S|}}\le 1</math>.
}}


In Lubell's counting argument proves the LYM inequality, which implies the Sperner's theorem. Here we give another proof of the LYM inequality by the probabilistic method,  due to Noga Alon.
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>.


{{Prooftitle|Third proof (the probabilistic method)| (Due to Alon.)
Take <math>n=Ck2^{k/2}</math> for some appropriate constant <math>C>0</math>.
Let <math>\pi</math> be a uniformly random permutation of <math>X</math>. Define a random maximal chain by
:<math>\mathcal{C}_\pi=\{\{\pi_i\mid 1\le i\le k\}\mid 0\le k\le n\}</math>.
For any <math>S\in\mathcal{F}</math>, let <math>X_S</math> be the 0-1 random variable which indicates whether <math>S\in\mathcal{C}_\pi</math>, that is
:<math>
:<math>
X_S=\begin{cases}
\begin{align}
1 & \mbox{if }S\in\mathcal{C}_\pi,\\
\mathrm{e}p(d+1)
0 & \mbox{otherwise.}
&\le \mathrm{e}2^{1-{k\choose 2}}\left({k\choose 2}{n\choose k-2}+1\right)\\
\end{cases}
&\le 2^{3-{k\choose 2}}{k\choose 2}{n\choose k-2}\\
&\le 1
\end{align}
</math>
</math>
Note that for a uniformly random <math>\pi</math>, <math>\mathcal{C}_\pi</math> has exact one member set of size <math>|S|</math>, uniformly distributed over <math>{X\choose |S|}</math>, thus
Applying the local lemma, the probability that there is no monochromatic <math>K_k</math> is
:<math>\mathbf{E}[X_S]=\Pr[S\in\mathcal{C}_\pi]=\frac{1}{{n\choose |S|}}</math>.
:<math>\Pr\left[\bigwedge_{S\in{[n]\choose k}}\overline{A_S}\right]>0</math>.
Let <math>X=\sum_{S\in\mathcal{F}}X_S</math>. Note that <math>X=|\mathcal{F}\cap\mathcal{C}_\pi|</math>. By the linearity of expectation,
Therefore, there exists a 2-coloring of <math>K_n</math> which has no monochromatic <math>K_k</math>, which means
:<math>\mathbf{E}[X]=\sum_{S\in\mathcal{F}}\mathbf{E}[X_S]=\sum_{S\in\mathcal{F}}\frac{1}{{n\choose |S|}}</math>.
:<math>R(k,k)>n=Ck2^{k/2}</math>.
On the other hand, since <math>\mathcal{F}</math> is an antichain, it can never intersect a chain at more than one elements, thus we always have <math>X=|\mathcal{F}\cap\mathcal{C}_\pi|\le 1</math>. Therefore,
:<math>\sum_{S\in\mathcal{F}}\frac{1}{{n\choose |S|}}\le \mathbf{E}[X] \le 1</math>.
}}
}}


The Sperner's theorem is an immediate consequence of the LYM inequality.
{{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>.
{{Theorem|Proposition|
:<math>\sum_{S\in\mathcal{F}}\frac{1}{{n\choose |S|}}\le 1</math> implies that <math>|\mathcal{F}|\le{n\choose \lfloor n/2\rfloor}</math>.
}}
{{Proof|
It holds that <math>{n\choose k}\le {n\choose \lfloor n/2\rfloor}</math> for any <math>k</math>. Thus,
:<math>1\ge \sum_{S\in\mathcal{F}}\frac{1}{{n\choose |S|}}\ge \frac{|\mathcal{F}|}{{n\choose \lfloor n/2\rfloor}}</math>,
which implies that <math>|\mathcal{F}|\le {n\choose \lfloor n/2\rfloor}</math>.
}}
}}


== Sunflowers ==
{| class="wikitable"
An set system is a '''sunflower''' if all its member sets intersect at the same set of elements.
! ''<math>k</math>'',''<math>l</math>''
{{Theorem|Definition (sunflower)|
! 1
: A set family <math>\mathcal{F}\subseteq 2^X</math> is a '''sunflower''' of size <math>r</math> with a '''core''' <math>C\subseteq X</math> if
! 2
::<math>\forall S,T\in\mathcal{F}</math> that <math>S\neq T</math>, <math>S\cap T=C</math>.
! 3
}}
! 4
Note that we do not require the core to be nonempty, thus a family of disjoint sets is also a sunflower (with the core <math>\emptyset</math>).
! 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
|}


The next result due to Erdős and Rado, called the sunflower lemma, is a famous result in extremal set theory, and has some important applications in Boolean circuit complexity.
=== Ramsey's theorem for hypergraph ===
{{Theorem|Sunflower Lemma (Erdős-Rado)|
{{Theorem|Ramsey's Theorem (hypergraph, multicolor)|
:Let <math>\mathcal{F}\subseteq {X\choose k}</math>. If <math>|\mathcal{F}|>k!(r-1)^k</math>, then <math>\mathcal{F}</math> contains a sunflower of size  <math>r</math>.
: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.
}}
}}
{{Proof|
We proceed by induction on <math>k</math>. For <math>k=1</math>, <math>\mathcal{F}\subseteq{X\choose 1}</math>, thus all sets in <math>\mathcal{F}</math> are disjoint. And since <math>|\mathcal{F}|>r-1</math>, we can choose <math>r</math> of these sets and form a sunflower.
Now let <math>k\ge 2</math> and assume the lemma holds for all smaller <math>k</math>. Take a maximal family <math>\mathcal{G}\subseteq \mathcal{F}</math> whose members are disjoint, i.e. for any <math>S,T\in \mathcal{G}</math> that <math>S\neq T</math>, <math>S\cap T=\emptyset</math>.
If <math>|\mathcal{G}|\ge r</math>, then <math>\mathcal{G}</math> is a sunflower of size at least <math>r</math> and we are done.


Assume that <math>|\mathcal{G}|\le r-1</math>, and let <math>Y=\bigcup_{S\in\mathcal{G}}S</math>. Then <math>|Y|=k|\mathcal{G}|\le k(r-1)</math> (since all members of <math>\mathcal{G}</math>) are disjoint). We claim that <math>Y</math> intersets all members of <math>\mathcal{F}</math>, since if otherwise, there exists an <math>S\in\mathcal{F}</math> such that <math>S\cap Y=\emptyset</math>, then we can enlarge <math>\mathcal{G}</math> by adding <math>S</math> into <math>\mathcal{G}</math> and still have all members of <math>\mathcal{G}</math> disjoint, which contradicts the assumption that <math>\mathcal{G}</math> is the maximum of such families.
<math>n\rightarrow(k_1,k_2,\ldots,k_r)^t</math>


By the pigeonhole principle, some elements <math>y\in Y</math> must contained in at least
{{Theorem|Lemma (the "mixing color" trick)|
:<math>\frac{|\mathcal{F}|}{|Y|}>\frac{k!(r-1)^k}{k(r-1)}=(k-1)!(r-1)^{k-1}</math>
:<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>
members of <math>\mathcal{F}</math>. We delete this <math>y</math> from these sets and consider the family
:<math>\mathcal{H}=\{S\setminus\{y\}\mid S\in\mathcal{F}\wedge y\in S\}</math>.
We have <math>\mathcal{H}\subseteq {X\choose k-1}</math> and <math>|\mathcal{H}|>(k-1)!(r-1)^{k-1}</math>, thus by the induction hypothesis, <math>\mathcal{H}</math>contains a sunflower of size <math>r</math>. Adding <math>y</math> to the members of this sunflower, we get the desired sunflower in the original family <math>\mathcal{F}</math>.
}}
}}


==The Erdős–Ko–Rado Theorem ==
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.
A set family <math>\mathcal{F}\subseteq 2^X</math> is called '''intersecting''', if for any <math>S,T\in\mathcal{F}</math>, <math>S\cap T\neq\emptyset</math>. A natural question of extremal favor is: "how large can an intersecting family be?"


Assume <math>|X|=n</math>. When <math>n<2k</math>, every pair of <math>k</math>-subsets of <math>X</math> intersects. So the non-trivial case is when <math>n\le 2k</math>. The famous Erdős–Ko–Rado theorem gives the largest possible cardinality of a nontrivially intersecting family.
According to Erdős, the theorem itself was proved in 1938, but was not published until 23 years later.
{{Theorem|Erdős–Ko–Rado theorem (proved in 1938, published in 1961)|
:Let <math>\mathcal{F}\subseteq {X\choose k}</math> where <math>|X|=n</math> and <math>n\ge 2k</math>. If <math>\mathcal{F}</math> is intersecting, then
::<math>|\mathcal{F}|\le{n-1\choose k-1}</math>.
}}
=== Katona's proof ===
We first introduce a proof discovered by Katona in 1972. The proof uses double counting.
Let <math>\pi</math> be a '''cyclic permutation''' of <math>X</math>, that is, we think of assigning <math>X</math> in a circle and ignore the rotations of the circle. It is easy to see that there are <math>(n-1)!</math> cyclic permutations of an <math>n</math>-set (each cyclic permutation corresponds to <math>n</math> permutations).
Let
:<math>\mathcal{G}_\pi=\{\{\pi_{(i+j)\bmod n}\mid j\in[k]\}\mid i\in [n]\}</math>.
The next lemma states the following observation: in a circle of <math>n</math> points, supposed <math>n\ge 2k</math>, there can be at most <math>k</math> arcs, each consisting of <math>k</math> points, such that every pair of arcs share at least one point.
{{Theorem|Lemma|
{{Theorem|Lemma|
:Let <math>\mathcal{F}\subseteq {X\choose k}</math> where <math>|X|=n</math> and <math>n\ge 2k</math>. If <math>\mathcal{F}</math> is intersecting, then for any cyclic permutation <math>\pi</math> of <math>X</math>, it holds that <math>|\mathcal{G}_\pi\cap\mathcal{F}|\le k</math>.
:<math>R_t(k,\ell)\le R_{t-1}(R_t(k-1,\ell),R_t(k,\ell-1))+1</math>
}}
}}
{{Proof|
{{Proof|
Fix a cyclic permutation <math>\pi</math> of <math>X</math>. Let <math>A_i=\{\pi_{(i+j+n)\bmod n}\mid j\in[k]\}</math>. Then <math>\mathcal{G}_\pi</math> can be written as <math>\mathcal{G}_\pi=\{A_i\mid i\in [n]\}</math>.  
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>.


Suppose that <math>A_t\in\mathcal{F}</math>. Since <math>\mathcal{F}</math> is intersecting, the only sets <math>A_i</math> that can be in <math>\mathcal{F}</math> other than <math>A_t</math> itself are the <math>2k-2</math> sets <math>A_i</math> with <math>t-(k-1)\le i\le t+k-1, i\neq t</math>. We partition these sets into <math>k-1</math> pairs <math>\{A_i,A_{i+k}\}</math>, where <math>t-(k-1)\le i\le t-1</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>.


Note that for <math>n\ge 2k</math>, it holds that <math>A_i\cap C_{i+k}=\emptyset</math>. Since <math>\mathcal{F}</math> is intersecting, <math>\mathcal{F}</math> can contain at most one set of each such pair. The lemma follows.
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.
}}
}}


The Katona's proof of Erdős–Ko–Rado theorem is done by counting in two ways the pairs of member <math>S</math> of <math>\mathcal{F}</math> and cyclic permutation <math>\pi</math> which contain <math>S</math> as a continuous path on the circle (i.e., an arc).
==  Applications of Ramsey Theorem ==
 
=== The "Happy Ending" problem ===
{{Prooftitle|Katona's proof of Erdős–Ko–Rado theorem|(double counting)
{{Theorem|The happy ending problem|
Let
: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.
:<math>\mathcal{R}=\{(S,\pi)\mid \pi \text{ is a cyclic permutation of }X, \text{and }S\in\mathcal{F}\cap\mathcal{G}_\pi\}</math>.
}}
We count <math>\mathcal{R}</math> in two ways.
See the article
 
[http://www.maa.org/mathland/mathtrek_10_3_00.html] for the proof.
First, due to the lemma, <math>|\mathcal{F}\cap\mathcal{G}_\pi|\le k</math> for any cyclic permutation <math>\pi</math>. There are <math>(n-1)!</math> cyclic permutations in total. Thus,
:<math>|\mathcal{R}|=\sum_{\text{cyclic }\pi}|\mathcal{F}\cap\mathcal{G}_\pi|\le k(n-1)!</math>.


Next, for each <math>S\in\mathcal{F}</math>, the number of cyclic permutations <math>\pi</math> in which <math>S</math> is continuous is <math>|S|!(n-|S|)!=k!(n-k)!</math>. Thus,
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.
:<math>|\mathcal{R}|=\sum_{S\in\mathcal{F}}k!(n-k)!=|\mathcal{F}|k!(n-k)!</math>.


Altogether, we have
{{Theorem|Theorem (Erdős-Szekeres 1935)|
:<math>|\mathcal{F}|\le\frac{k(n-1)!}{k!(n-k)!}=\frac{(n-1)!}{(k-1)!(n-k)!}={n-1\choose k-1}</math>.
: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>.


=== Erdős' shifting technique ===
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 now introduce the original proof of the Erdős–Ko–Rado theorem, which uses a technique called '''shifting''' (originally called '''compression''').


Without loss of generality, we assume <math>X=[n]</math>, and restate the Erdős–Ko–Rado theorem as follows.
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,
{{Theorem|Erdős–Ko–Rado theorem|
:<math>\triangle_{abc}=\triangle_{abd}\cup\triangle_{acd}\cup\triangle_{bcd}\cup\{d\}</math>,
:Let <math>\mathcal{F}\subseteq {[n]\choose k}</math> and <math>n\ge 2k</math>. If <math>\mathcal{F}</math> is intersecting, then <math>|\mathcal{F}|\le{n-1\choose k-1}</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.
}}
}}


We define a '''shift operator''' for the set family.
=== Yao's lower bound on implicit data structures ===
{{Theorem|Definition (shift operator)|
{{Theorem|Lemma|
: Assume <math>\mathcal{F}\subseteq 2^{[n]}</math>, and <math>0\le i<j\le n-1</math>. Define the '''<math>(i,j)</math>-shift''' <math>S_{ij}</math> as an operator on <math>\mathcal{F}</math> as follows:
: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>.
:*for each <math>T\in\mathcal{F}</math>, write <math>T_{ij}=(T\setminus\{j\})\cup\{i\} </math>, and let
: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.
::<math>S_{ij}(T)=
\begin{cases}
T_{ij} & \mbox{if }j\in T, i\not\in T, \mbox{ and }T_{ij} \not\in\mathcal{F},\\
T & \mbox{otherwise;}
\end{cases}</math>
:* let <math>S_{ij}(\mathcal{F})=\{S_{ij}(T)\mid T\in \mathcal{F}\}</math>.
}}
 
It is easy to verify the following propositions of shifts.
 
{{Theorem|Proposition|
# <math>|S_{ij}(T)|=|T|\,</math> and <math>|S_{ij}(\mathcal{F})|=\mathcal{F}</math>;
# if <math>\mathcal{F}</math> is intersecting, then so is <math>S_{ij}(\mathcal{F})</math>.
}}
}}
{{Proof|
{{Proof|
(1) is immediate. Now we prove (2).
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>.


Let <math>A,B\in\mathcal{F}</math>. All the cases are easy to dealt with except when <math>A\cap B=\{j\}</math>, <math>i\in A</math>, and <math>i\not\in B</math>. Denote <math>A_{ij}=A\setminus\{j\}\cup\{i\}</math>. It holds that <math>A_{ij}\cap B=(A\cap B)\setminus\{j\}=\emptyset</math>. Since <math>\mathcal{F}</math> is intersecting, it must hold that <math>A_{ij}\not\in\mathcal{F}</math>. Thus, <math>S_{ij}(A)=A_{ij}</math> and clearly <math>S_{ij}(B)=B_{ij}=B\setminus\{j\}\cup\{i\}</math>. Therefore, <math>i\in S_{ij}(A)\cap S_{ij}(B)</math> thus <math>S_{ij}(A)\cap S_{ij}(B)\neq \emptyset</math>.
For <math>n=2</math> and <math>N\ge 2n-1=3</math> it is easy to see that two accesses are necessary.
}}


Repeatedly applying <math>S_{ij}(\mathcal{F})</math> for any <math>0\le i<j\le n-1</math>, since we only replace elements by smaller elements, eventually <math>\mathcal{F}</math> will stop changing, that is, <math>S_{ij}(\mathcal{F})=\mathcal{F}</math> for all <math>0\le i<j\le n-1</math>. We call such an <math>\mathcal{F}</math> '''shifted'''.
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>.


The idea behind the shifting technique is very natural: by applying shifting, all intersecting families are transformed to some ''special forms'', and we only need to prove the theorem for these special form of intersecting families.
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>.  


{{Prooftitle|Proof of Erdős-Ko-Rado theorem| (The original proof of Erdős-Ko-Rado by shifting)
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>.
By the above lemma, it is sufficient to prove the Erdős-Ko-Rado theorem holds for shifted <math>\mathcal{F}</math>. We assume that <math>\mathcal{F}</math> is shifted.


First, it is trivial to see that the theorem holds for <math>k=1</math> (no matter whether shifted).
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.
}}


Next, we show that the theorem holds when <math>n=2k</math>  (no matter whether shifted). For any <math>S\in{X\choose k}</math>, both <math>S</math> and <math>X\setminus S</math> are in <math>{X\choose k}</math>, but at most one of them can be in <math>\mathcal{F}</math>. Thus,
:<math>|\mathcal{F}|\le\frac{1}{2}{n\choose k}=\frac{n!}{2k!(n-k)!}=\frac{(n-1)!}{(k-1)!(n-k)!}={n-1\choose k-1}</math>.


We then apply the induction on <math>n</math>. For <math>n> 2k</math>, the induction hypothesis is stated as:
We have seen that on a sorted table, there is no search algorithm outperforming the binary search in the worst case.
* the Erdős-Ko-Rado theorem holds for any smaller <math>n</math>.
Our question is:
Define
:''Is there any other order than the increasing order, on which there is a better search algorithm?''
:<math>\mathcal{F}_0=\{S\in\mathcal{F}\mid n\not\in S\}</math> and <math>\mathcal{F}_1=\{S\in\mathcal{F}\mid n\in S\}</math>.
Clearly, <math>\mathcal{F}_0\subseteq{[n-1]\choose k}</math> and <math>\mathcal{F}_0</math> is intersecting. Due to the induction hypothesis, <math>|\mathcal{F}_0|\le{n-2\choose k-1}</math>.


In order to apply the induction, we let
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>\mathcal{F}_1'=\{S\setminus\{n\}\mid S\in\mathcal{F}_1\}</math>.
:<math>f:{U\choose n}\rightarrow[n!]</math>,
Clearly, <math>\mathcal{F}_1'\subseteq{[n-1]\choose k-1}</math>. If only it is also intersecting, we can apply the induction hypothesis, and indeed it is. To see this, by contradiction we assume that <math>\mathcal{F}_1'</math> is not intersecting. Then there must exist <math>A,B\in\mathcal{F}</math> such that <math>A\cap B=\{n\}</math>, which means that <math>|A\cup B|\le 2k-1<n-1</math>. Thus, there is some <math>0\le i\le n-1</math> such that <math>i\not\in A\cup B</math>. Since <math>\mathcal{F}</math> is shifted, <math>A_{in}=A\setminus\{n\}\cup\{i\}\in\mathcal{F}</math>. On the other hand it can be verified that <math>A_{in}\cap B=\emptyset</math>, which contradicts that <math>\mathcal{F}</math> is intersecting.  
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>.


Thus, <math>\mathcal{F}_1'\subseteq{[n-1]\choose k-1}</math> and <math>\mathcal{F}_1'</math> is intersecting. Due to the induction hypothesis, <math>|\mathcal{F}_1'|\le{n-2\choose k-2}</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>.
}}


Combining these together,
=== Hales–Jewett Theorem ===
:<math>|\mathcal{F}|=|\mathcal{F}_0|+|\mathcal{F}_1|=|\mathcal{F}_0|+|\mathcal{F}_1'|\le {n-2\choose k-1}+{n-2\choose k-2}={n-1\choose k-1}</math>.
{{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.
}}
}}


== References ==
{{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.
:('''Disclaimer:''' The following copyrighted materials are meant for educational uses only.)
}}
 
* van Lin and Wilson. ''A course in combinatorics.'' Cambridge Press. Chapter 6.
* Aigner and Ziegler. ''Proofs from THE BOOK, 4th Edition.'' Springer-Verlag. [[media:PFTB_chap27.pdf| Chapter 27]].

Revision as of 06:23, 17 August 2011

Ramsey's Theorem

Ramsey's theorem for graph

Ramsey's Theorem
Let [math]\displaystyle{ k,\ell }[/math] be positive integers. Then there exists an integer [math]\displaystyle{ R(k,\ell) }[/math] satisfying:
If [math]\displaystyle{ n\ge R(k,\ell) }[/math], for any coloring of edges of [math]\displaystyle{ K_n }[/math] with two colors red and blue, there exists a red [math]\displaystyle{ K_k }[/math] or a blue [math]\displaystyle{ K_\ell }[/math].
Proof.

We show that [math]\displaystyle{ R(k,\ell) }[/math] is finite by induction on [math]\displaystyle{ k+\ell }[/math]. For the base case, it is easy to verify that

[math]\displaystyle{ R(k,1)=R(1,\ell)=1 }[/math].

For general [math]\displaystyle{ k }[/math] and [math]\displaystyle{ \ell }[/math], we will show that

[math]\displaystyle{ R(k,\ell)\le R(k,\ell-1)+R(k-1,\ell) }[/math].

Suppose we have a two coloring of [math]\displaystyle{ K_n }[/math], where [math]\displaystyle{ n=R(k,\ell-1)+R(k-1,\ell) }[/math]. Take an arbitrary vertex [math]\displaystyle{ v }[/math], and split [math]\displaystyle{ V\setminus\{v\} }[/math] into two subsets [math]\displaystyle{ S }[/math] and [math]\displaystyle{ T }[/math], where

[math]\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} }[/math]

Since

[math]\displaystyle{ |S|+|T|+1=n=R(k,\ell-1)+R(k-1,\ell) }[/math],

we have either [math]\displaystyle{ |S|\ge R(k,\ell-1) }[/math] or [math]\displaystyle{ |T|\ge R(k-1,\ell) }[/math]. By symmetry, suppose [math]\displaystyle{ |S|\ge R(k,\ell-1) }[/math]. By induction hypothesis, the complete subgraph defined on [math]\displaystyle{ S }[/math] has either a red [math]\displaystyle{ K_k }[/math], in which case we are done; or a blue [math]\displaystyle{ K_{\ell-1} }[/math], in which case the complete subgraph defined on [math]\displaystyle{ S\cup{v} }[/math] must have a blue [math]\displaystyle{ K_\ell }[/math] since all edges from [math]\displaystyle{ v }[/math] to vertices in [math]\displaystyle{ S }[/math] are blue.

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

We transfer the [math]\displaystyle{ r }[/math]-coloring to [math]\displaystyle{ (r-1) }[/math]-coloring by identifying the [math]\displaystyle{ (r-1) }[/math]th and the [math]\displaystyle{ r }[/math]th colors.

If [math]\displaystyle{ 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]\displaystyle{ r }[/math]-coloring of [math]\displaystyle{ K_n }[/math], there either exist an [math]\displaystyle{ i\in\{1,2,\ldots,r-2\} }[/math] and a [math]\displaystyle{ k_i }[/math]-clique which is monochromatically colored with the [math]\displaystyle{ i }[/math]th color; or exists clique of [math]\displaystyle{ R(2;k_{r-1},k_r) }[/math] vertices which is monochromatically colored with the mixed color of the original [math]\displaystyle{ (r-1) }[/math]th and [math]\displaystyle{ r }[/math]th colors, which again implies that there exists either a [math]\displaystyle{ k }[/math]-clique which is monochromatically colored with the original [math]\displaystyle{ (r-1) }[/math]th color, or a [math]\displaystyle{ \ell }[/math]-clique which is monochromatically colored with the original [math]\displaystyle{ r }[/math]th color. This implies the recursion.

[math]\displaystyle{ \square }[/math]

Ramsey number

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

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

"[math]\displaystyle{ R(k,\ell) }[/math] is finite for any positive integers [math]\displaystyle{ k }[/math] and [math]\displaystyle{ \ell }[/math]."

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

[math]\displaystyle{ \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
[math]\displaystyle{ R(k,\ell)\le{k+\ell-2\choose k-1} }[/math].
Proof.
It is easy to verify the bound by induction.
[math]\displaystyle{ \square }[/math]

The following theorem is due to Spencer in 1975, which is the best known lower bound for diagonal Ramsey number.

Theorem (Spencer 1975)
[math]\displaystyle{ R(k,k)\ge Ck2^{k/2} }[/math] for some constant [math]\displaystyle{ C\gt 0 }[/math].

Its proof uses the Lovász local lemma in the probabilistic method.

Lovász Local Lemma (symmetric case)
Let [math]\displaystyle{ A_1,A_2,\ldots,A_n }[/math] be a set of events, and assume that the following hold:
  1. for all [math]\displaystyle{ 1\le i\le n }[/math], [math]\displaystyle{ \Pr[A_i]\le p }[/math];
  2. each event [math]\displaystyle{ A_i }[/math] is independent of all but at most [math]\displaystyle{ d }[/math] other events, and
[math]\displaystyle{ ep(d+1)\le 1 }[/math].
Then
[math]\displaystyle{ \Pr\left[\bigwedge_{i=1}^n\overline{A_i}\right]\gt 0 }[/math].

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

Proof.

To prove a lower bound [math]\displaystyle{ R(k,k)\gt n }[/math], it is sufficient to show that there exists a 2-coloring of [math]\displaystyle{ K_n }[/math] without a monochromatic [math]\displaystyle{ K_k }[/math]. We prove this by the probabilistic method.

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

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

Take [math]\displaystyle{ n=Ck2^{k/2} }[/math] for some appropriate constant [math]\displaystyle{ C\gt 0 }[/math].

[math]\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} }[/math]

Applying the local lemma, the probability that there is no monochromatic [math]\displaystyle{ K_k }[/math] is

[math]\displaystyle{ \Pr\left[\bigwedge_{S\in{[n]\choose k}}\overline{A_S}\right]\gt 0 }[/math].

Therefore, there exists a 2-coloring of [math]\displaystyle{ K_n }[/math] which has no monochromatic [math]\displaystyle{ K_k }[/math], which means

[math]\displaystyle{ R(k,k)\gt n=Ck2^{k/2} }[/math].
[math]\displaystyle{ \square }[/math]
Theorem
[math]\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) }[/math].
[math]\displaystyle{ k }[/math],[math]\displaystyle{ 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

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

[math]\displaystyle{ n\rightarrow(k_1,k_2,\ldots,k_r)^t }[/math]

Lemma (the "mixing color" trick)
[math]\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)) }[/math]

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

Lemma
[math]\displaystyle{ R_t(k,\ell)\le R_{t-1}(R_t(k-1,\ell),R_t(k,\ell-1))+1 }[/math]
Proof.

Let [math]\displaystyle{ n=R_{t-1}(R_t(k-1,\ell),R_t(k,\ell-1))+1 }[/math]. Denote [math]\displaystyle{ [n]=\{1,2,\ldots,n\} }[/math].

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

We remove [math]\displaystyle{ n }[/math] from [math]\displaystyle{ [n] }[/math] and define a new coloring [math]\displaystyle{ f' }[/math] of [math]\displaystyle{ {[n-1]\choose t-1} }[/math] by

[math]\displaystyle{ f'(A)=f(A\cup\{n\}) }[/math] for any [math]\displaystyle{ A\in{[n-1]\choose t-1} }[/math].

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

[math]\displaystyle{ \square }[/math]

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 [math]\displaystyle{ m\ge 3 }[/math], there is an [math]\displaystyle{ N(m) }[/math] such that any set of at least [math]\displaystyle{ N(m) }[/math] points in general position in the plane (i.e., no three of the points are on a line) contains [math]\displaystyle{ m }[/math] points that are the vertices of a convex [math]\displaystyle{ m }[/math]-gon.
Proof.

Let [math]\displaystyle{ N(m)=R_3(m,m) }[/math]. For [math]\displaystyle{ n\ge N(m) }[/math], let [math]\displaystyle{ X }[/math] be an arbitrary set of [math]\displaystyle{ 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]\displaystyle{ f:{X\choose 3}\rightarrow\{0,1\} }[/math] as follows: for any [math]\displaystyle{ \{a,b,c\}\in{X\choose 3} }[/math], let [math]\displaystyle{ \triangle_{abc}\subset X }[/math] be the set of points covered by the triangle [math]\displaystyle{ abc }[/math]; and [math]\displaystyle{ f(\{a,b,c\})=|\triangle_{abc}|\bmod 2 }[/math], that is, [math]\displaystyle{ f(\{a,b,c\}) }[/math] indicates the oddness of the number of points covered by the triangle [math]\displaystyle{ abc }[/math].

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

We claim that the [math]\displaystyle{ m }[/math] points in [math]\displaystyle{ Y }[/math] are the vertices of a convex [math]\displaystyle{ m }[/math]-gon. If otherwise, by the definition of convexity, there exist [math]\displaystyle{ \{a,b,c,d\}\subseteq Y }[/math] such that [math]\displaystyle{ d\in\triangle_{abc} }[/math]. Since no three points are in the same line,

[math]\displaystyle{ \triangle_{abc}=\triangle_{abd}\cup\triangle_{acd}\cup\triangle_{bcd}\cup\{d\} }[/math],

where all unions are disjoint. Then [math]\displaystyle{ |\triangle_{abc}|=|\triangle_{abd}|+|\triangle_{acd}|+|\triangle_{bcd}|+1 }[/math], which implies that [math]\displaystyle{ 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]\displaystyle{ {Y\choose 3} }[/math] have the same color.

[math]\displaystyle{ \square }[/math]

Yao's lower bound on implicit data structures

Lemma
Let [math]\displaystyle{ n\ge 2 }[/math] be a power of 2 and [math]\displaystyle{ N\ge 2n }[/math]. Suppose the universe is [math]\displaystyle{ [N] }[/math] and the size of the data set is [math]\displaystyle{ n }[/math].
If the data structure is a sorted table, any search algorithm requires at least [math]\displaystyle{ \log n }[/math] accesses to the data structure in the worst case.
Proof.

We will show by an adversarial argument that [math]\displaystyle{ \log n }[/math] accesses are required to search for the key value [math]\displaystyle{ x=n }[/math] from the universe [math]\displaystyle{ [N]=\{1,2,\ldots,N\} }[/math]. The construction of the adversarial data set [math]\displaystyle{ S }[/math] is by induction on [math]\displaystyle{ n }[/math].

For [math]\displaystyle{ n=2 }[/math] and [math]\displaystyle{ N\ge 2n-1=3 }[/math] it is easy to see that two accesses are necessary.

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

Suppose that the first access position is [math]\displaystyle{ k }[/math]. The adversary chooses the table content [math]\displaystyle{ T[k] }[/math]. The adversary's strategy is:

[math]\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} }[/math]

By symmetry, suppose it is the first case that [math]\displaystyle{ k\le \frac{n}{2} }[/math]. Then the key [math]\displaystyle{ x=n }[/math] may be in any position [math]\displaystyle{ i }[/math], where [math]\displaystyle{ n/2+1\le i\le n }[/math]. In fact, [math]\displaystyle{ T[ n/2+1] }[/math] through [math]\displaystyle{ T[n] }[/math] is a sorted table of size [math]\displaystyle{ n'=n/2 }[/math] which may contain any [math]\displaystyle{ n' }[/math]-subset of [math]\displaystyle{ \{n/2+1, n/2+2,\ldots,N\} }[/math], and hence, in particular, any [math]\displaystyle{ n' }[/math]-subset of the universe

[math]\displaystyle{ U'=\{n/2+1, n/2+2,\ldots,N-n/2\} }[/math].

The size [math]\displaystyle{ N' }[/math] of [math]\displaystyle{ U' }[/math] satisfies

[math]\displaystyle{ N'=N-n/2-n/2\ge 2n-n\ge 2n' }[/math],

and the desired key [math]\displaystyle{ n }[/math] has the relative value [math]\displaystyle{ x'=n- n/2=n' }[/math] in the universe [math]\displaystyle{ U' }[/math].

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

If the first access is [math]\displaystyle{ k\gt \frac{n}{2} }[/math], we symmetrically get that [math]\displaystyle{ T[1] }[/math] through [math]\displaystyle{ T[n/2] }[/math] is a sorted table of size [math]\displaystyle{ n'=n/2 }[/math] which may contain any [math]\displaystyle{ n' }[/math]-subset of the universe

[math]\displaystyle{ U'=\{n/2+1, n/2+2,\ldots,N-n/2\} }[/math].

The rest is the same.

[math]\displaystyle{ \square }[/math]


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]\displaystyle{ f:{U\choose n}\rightarrow[n!] }[/math],

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

Ramsey-like Theorems

Van der Waerden's Theorem

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

Hales–Jewett Theorem

Theorem (Hales-Jewett 1963)
Let [math]\displaystyle{ A }[/math] be a finte alphabet of [math]\displaystyle{ t }[/math] symbols and let [math]\displaystyle{ r }[/math] be a positive integer. Then there exists an integer [math]\displaystyle{ \mathrm{HJ}(r,t) }[/math] such that for every [math]\displaystyle{ r }[/math]-coloring of the cube [math]\displaystyle{ A^n }[/math] where [math]\displaystyle{ n\ge \mathrm{HJ}(r,t) }[/math], there exists a combinatorial line, which is monochromatic.
Theorem (Hales-Jewett 1963)
Let [math]\displaystyle{ A }[/math] be a finte alphabet of [math]\displaystyle{ t }[/math] symbols and let [math]\displaystyle{ m,r }[/math] be positive integers. Then there exists an integer [math]\displaystyle{ \mathrm{HJ}(m,r,t) }[/math] such that for every [math]\displaystyle{ r }[/math]-coloring of the cube [math]\displaystyle{ A^n }[/math] where [math]\displaystyle{ n\ge \mathrm{HJ}(r,t) }[/math], there exists a combinatorial [math]\displaystyle{ m }[/math]-space, which is monochromatic.
Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=组合数学_(Fall_2011)/Extremal_set_theory&oldid=4924"