imported>WikiSysop |
imported>Etone |
Line 1: |
Line 1: |
| == Ramsey's Theorem ==
| | * 课程主页 |
| === Ramsey's theorem for graph ===
| | ** Main_Page|首页 |
| {{Theorem|Ramsey's Theorem|
| | ** 组合数学 (Spring 2014)|组合数学 |
| :Let <math>k,\ell</math> be positive integers. Then there exists an integer <math>R(k,\ell)</math> satisfying:
| | ** 随机算法 (Spring 2014)|随机算法 |
| :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>.
| | * 讨论班 |
| }}
| | ** 近似算法讨论班 (Fall 2011)|近似算法讨论班 |
| {{Proof|
| | * SEARCH |
| 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
| | * links |
| :<math>R(k,1)=R(1,\ell)=1</math>.
| | ** mainpage|EtoneWiki |
| For general <math>k</math> and <math>\ell</math>, we will show that
| | ** http://eddy.nju.edu.cn/wiki|EddyWiki |
| :<math>R(k,\ell)\le R(k,\ell-1)+R(k-1,\ell)</math>.
| | ** http://en.wikipedia.org/wiki/Main_Page|Wikipedia |
| 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
| | ** http://mathworld.wolfram.com/|MathWorld |
| :<math>\begin{align}
| | ** http://www.nestia.com/|Nestia.com |
| S&=\{u\in V\setminus\{v\}\mid uv \text{ is blue }\}\\
| | ** http://www.mediawiki.org/wiki/Help:Contents|help |
| 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.
| |
| }}
| |
| | |
| ------
| |
| | |
| The following theorem is due to Spencer in 1975, which is the best known lower bound for diagonal Ramsey number.
| |
| | |
| {{Theorem|Theorem (Spencer 1975)|
| |
| :<math>R(k,k)\ge Ck2^{k/2}</math> for some constant <math>C>0</math>.
| |
| }}
| |
| | |
| Its proof uses the Lovász local lemma in the probabilistic method.
| |
| {{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>;
| |
| :# each event <math>A_i</math> is independent of all but at most <math>d</math> other events, and
| |
| :::<math>ep(d+1)\le 1</math>.
| |
| :Then
| |
| ::<math>\Pr\left[\bigwedge_{i=1}^n\overline{A_i}\right]>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>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.
| |
| }}
| |