Combinatorics (Fall 2010)/Ramsey theory: Difference between revisions
Jump to navigation
Jump to search
imported>WikiSysop |
imported>WikiSysop No edit summary |
||
| Line 1: | Line 1: | ||
== Ramsey's Theorem == | == Ramsey's Theorem == | ||
{{Theorem|Ramsey's Theorem| | |||
:Let <math>k,\ell</math> be positive integers. Then there exists an integer <math>R(k,\ell)</math> satisfying: | |||
:In any graph of <math>n\ge R(k,\ell)</math> vertices, there exists a clique of <math>k</math> vertices or an independent set of <math>\ell</math> vertices. | |||
}} | |||
{{Theorem|Ramsey's Theorem (graph, multicolor)| | {{Theorem|Ramsey's Theorem (graph, multicolor)| | ||
:Let <math> | :Let <math>t, k_1,k_2,\ldots,k_t</math> be positive integers. Then there exists an integer <math>R_t(k_1,k_2,\ldots,k_t)</math> satisfying: | ||
:For any <math> | :For any <math>t</math>-coloring of a complete graph of <math>n\ge R_t(k_1,k_2,\ldots,k_t)</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,t}</math>. | ||
}} | }} | ||
{{Theorem|Ramsey's Theorem (hypergraph, multicolor)| | |||
:Let <math>r, t, k_1,k_2,\ldots,k_t</math> be positive integers. Then there exists an integer <math>R_t(r;k_1,k_2,\ldots,k_t)</math> satisfying: | |||
:For any <math>t</math>-coloring of <math>{[n]\choose r}</math> with <math>n\ge R_t(r;k_1,k_2,\ldots,k_t)</math>, there exist an <math>i\in\{1,2,\ldots,t\}</math> and a subset <math>X\subseteq [n]</math> with <math>|X|\ge k_i</math> such that all members of <math>{X\choose r}</math> are colored with the <math>i</math>th color. | |||
}} | |||
{{Theorem| | {{Theorem|Lemma| | ||
: | :<math>R_t(r;k_1,k_2,\ldots,k_t)\le R_{t-1}(r;k_1,k_2,\ldots,k_{t-2},R_2(r;k_{t-1},k_t))</math> | ||
}} | }} | ||
It is then sufficient to prove the Ramsey's theorem for the two-coloring of a hypergraph, that is, to prove <math>R(r;k,\ell)=R_2(r;k,\ell)</math> is finite. | |||
: | {{Theorem|Lemma| | ||
:<math>R(r;k,\ell)\le R(r-1;R(r;k-1,\ell),R(r;k,\ell-1))+1</math> | |||
}} | }} | ||
| Line 32: | Line 41: | ||
=== Yao's lower bound on implicit data structures === | === Yao's lower bound on implicit data structures === | ||
{{Theorem|Lemma| | |||
:Let <math>n\ge 2</math> and <math>N\ge 2n-1</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>\lceil\log(n+1)\rceil</math> accesses to the data structure in the worst case. | |||
}} | |||
{{Proof| | |||
We will show by an adversarial argument that <math>\lceil\log(n+1)\rceil</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_0>2</math>. Assume the induction hypothesis to be true for all <math>n<n_0</math>; we will prove it for <math>n=n_0, m\ge 2n_0-1</math> and <math>x=n_0</math>. | |||
By symmetry, assume that the first access position <math>\ell</math> satisfies <math>\ell\le\lceil n_0/2\rceil</math>. The adversary answers <math>T[\ell]=\ell</math>. Then the key <math>x=n_0</math> may be in any position <math>i</math>, where <math>\lceil n_0/2\rceil+1\le i\le n_0</math>. In fact, <math>T[\lceil n_0/2\rceil+1]</math> through <math>T[n_0]</math> is a sorted table of size <math>n'=\lfloor n_0/2\rfloor</math> which may contain any <math>n'</math>-subset of <math>\{\lceil n_0/2\rceil+1,\lceil n_0/2\rceil+2,\ldots,N\}</math>, and hence, in particular, any subset of the universe | |||
:<math>U'=\{\lceil n_0/2\rceil+1,\lceil n_0/2\rceil+2,\ldots,N-\lceil n_0/2\rceil\}</math>. | |||
The size <math>N'</math> of <math>U'</math> satisfies | |||
:<math>N'=N-2\lceil n_0/2\rceil\ge (2n_0-1)-2\lceil n_0/2\rceil\ge 2\lfloor n_0/2\rfloor-1=2n'-1</math>, | |||
and the desired key <math>n_0</math> has the relative value <math>x'=n_0-\lceil n_0/2\rceil=n'</math> in the universe <math>U'</math>. | |||
By the induction hypothesis, <math>\lceil\log(n'+1)\rceil</math> more accesses will be required. Hence the total number of accesses is at least | |||
:<math>1+\lceil\log(n'+1)\rceil=1+\lceil\log(\lfloor n_0/2\rfloor+1)\rceil\ge\lceil\log(n_0+1)\rceil</math>. | |||
}} | |||
=== Linial's lower bound on local computations === | === Linial's lower bound on local computations === | ||
| Line 37: | Line 66: | ||
== Ramsey-like Theorems == | == Ramsey-like Theorems == | ||
=== Van der Waerden's Theorem === | === 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 === | === Hales–Jewett Theorem === | ||
{{Theorem|Theorem (Hales-Jewett 1963)| | |||
:Let <math>\Sigma</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>\Sigma^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>\Sigma</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>\Sigma^n</math> where <math>n\ge \mathrm{HJ}(r,t)</math>, there exists a combinatorial <math>m</math>-space, which is monochromatic. | |||
}} | |||
Revision as of 03:51, 18 November 2010
Ramsey's Theorem
Ramsey's Theorem - Let [math]\displaystyle{ k,\ell }[/math] be positive integers. Then there exists an integer [math]\displaystyle{ R(k,\ell) }[/math] satisfying:
- In any graph of [math]\displaystyle{ n\ge R(k,\ell) }[/math] vertices, there exists a clique of [math]\displaystyle{ k }[/math] vertices or an independent set of [math]\displaystyle{ \ell }[/math] vertices.
Ramsey's Theorem (graph, multicolor) - Let [math]\displaystyle{ t, k_1,k_2,\ldots,k_t }[/math] be positive integers. Then there exists an integer [math]\displaystyle{ R_t(k_1,k_2,\ldots,k_t) }[/math] satisfying:
- For any [math]\displaystyle{ t }[/math]-coloring of a complete graph of [math]\displaystyle{ n\ge R_t(k_1,k_2,\ldots,k_t) }[/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,t} }[/math].
Ramsey's Theorem (hypergraph, multicolor) - Let [math]\displaystyle{ r, t, k_1,k_2,\ldots,k_t }[/math] be positive integers. Then there exists an integer [math]\displaystyle{ R_t(r;k_1,k_2,\ldots,k_t) }[/math] satisfying:
- For any [math]\displaystyle{ t }[/math]-coloring of [math]\displaystyle{ {[n]\choose r} }[/math] with [math]\displaystyle{ n\ge R_t(r;k_1,k_2,\ldots,k_t) }[/math], there exist an [math]\displaystyle{ i\in\{1,2,\ldots,t\} }[/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 r} }[/math] are colored with the [math]\displaystyle{ i }[/math]th color.
Lemma - [math]\displaystyle{ R_t(r;k_1,k_2,\ldots,k_t)\le R_{t-1}(r;k_1,k_2,\ldots,k_{t-2},R_2(r;k_{t-1},k_t)) }[/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(r;k,\ell)=R_2(r;k,\ell) }[/math] is finite.
Lemma - [math]\displaystyle{ R(r;k,\ell)\le R(r-1;R(r;k-1,\ell),R(r;k,\ell-1))+1 }[/math]
Ramsey number
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{ n\ge 3 }[/math], there is an [math]\displaystyle{ N(n) }[/math] such that any set of at least [math]\displaystyle{ N(n) }[/math] points in general position in the plane (i.e., no three of the points are on a line) contains [math]\displaystyle{ n }[/math] points that are the vertices of a convex [math]\displaystyle{ n }[/math]-gon.
Yao's lower bound on implicit data structures
Lemma - Let [math]\displaystyle{ n\ge 2 }[/math] and [math]\displaystyle{ N\ge 2n-1 }[/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{ \lceil\log(n+1)\rceil }[/math] accesses to the data structure in the worst case.
Proof. We will show by an adversarial argument that [math]\displaystyle{ \lceil\log(n+1)\rceil }[/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_0\gt 2 }[/math]. Assume the induction hypothesis to be true for all [math]\displaystyle{ n\lt n_0 }[/math]; we will prove it for [math]\displaystyle{ n=n_0, m\ge 2n_0-1 }[/math] and [math]\displaystyle{ x=n_0 }[/math].
By symmetry, assume that the first access position [math]\displaystyle{ \ell }[/math] satisfies [math]\displaystyle{ \ell\le\lceil n_0/2\rceil }[/math]. The adversary answers [math]\displaystyle{ T[\ell]=\ell }[/math]. Then the key [math]\displaystyle{ x=n_0 }[/math] may be in any position [math]\displaystyle{ i }[/math], where [math]\displaystyle{ \lceil n_0/2\rceil+1\le i\le n_0 }[/math]. In fact, [math]\displaystyle{ T[\lceil n_0/2\rceil+1] }[/math] through [math]\displaystyle{ T[n_0] }[/math] is a sorted table of size [math]\displaystyle{ n'=\lfloor n_0/2\rfloor }[/math] which may contain any [math]\displaystyle{ n' }[/math]-subset of [math]\displaystyle{ \{\lceil n_0/2\rceil+1,\lceil n_0/2\rceil+2,\ldots,N\} }[/math], and hence, in particular, any subset of the universe
- [math]\displaystyle{ U'=\{\lceil n_0/2\rceil+1,\lceil n_0/2\rceil+2,\ldots,N-\lceil n_0/2\rceil\} }[/math].
The size [math]\displaystyle{ N' }[/math] of [math]\displaystyle{ U' }[/math] satisfies
- [math]\displaystyle{ N'=N-2\lceil n_0/2\rceil\ge (2n_0-1)-2\lceil n_0/2\rceil\ge 2\lfloor n_0/2\rfloor-1=2n'-1 }[/math],
and the desired key [math]\displaystyle{ n_0 }[/math] has the relative value [math]\displaystyle{ x'=n_0-\lceil n_0/2\rceil=n' }[/math] in the universe [math]\displaystyle{ U' }[/math].
By the induction hypothesis, [math]\displaystyle{ \lceil\log(n'+1)\rceil }[/math] more accesses will be required. Hence the total number of accesses is at least
- [math]\displaystyle{ 1+\lceil\log(n'+1)\rceil=1+\lceil\log(\lfloor n_0/2\rfloor+1)\rceil\ge\lceil\log(n_0+1)\rceil }[/math].
- [math]\displaystyle{ \square }[/math]
Linial's lower bound on local computations
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{ \Sigma }[/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{ \Sigma^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{ \Sigma }[/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{ \Sigma^n }[/math] where [math]\displaystyle{ n\ge \mathrm{HJ}(r,t) }[/math], there exists a combinatorial [math]\displaystyle{ m }[/math]-space, which is monochromatic.