组合数学 (Spring 2013)/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 }$

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

 Theorem (Spencer 1975) ${\displaystyle R(k,k)\geq Ck2^{k/2}}$ for some constant ${\displaystyle C>0}$.

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

 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}$; each event ${\displaystyle A_{i}}$ is independent of all but at most ${\displaystyle d}$ other events, and ${\displaystyle ep(d+1)\leq 1}$. Then ${\displaystyle \Pr \left[\bigwedge _{i=1}^{n}{\overline {A_{i}}}\right]>0}$.

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

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}}$.