Combinatorics (Fall 2010)/Ramsey theory
Ramsey's Theorem
Ramsey's theorem for graph
Ramsey's Theorem - Let be positive integers. Then there exists an integer satisfying:
- If , for any coloring of edges of with two colors red and blue, there exists a red or a blue .
Proof. We show that is finite by induction on . For the base case, it is easy to verify that
- .
For general and , we will show that
- .
Suppose we have a two coloring of , where . Take an arbitrary vertex , and split into two subsets and , where
Since
- ,
we have either or . By symmetry, suppose . By induction hypothesis, the complete subgraph defined on has either a red , in which case we are done; or a blue , in which case the complete subgraph defined on must have a blue since all edges from to vertices in are blue.
Ramsey's Theorem (graph, multicolor) - Let be positive integers. Then there exists an integer satisfying:
- For any -coloring of a complete graph of vertices, there exists a monochromatic -clique with the th color for some .
Lemma (the "mixing color" trick)
Proof. We transfer the -coloring to -coloring by identifying the th and the th colors.
If , then for any -coloring of , there either exist an and a -clique which is monochromatically colored with the th color; or exists clique of vertices which is monochromatically colored with the mixed color of the original th and th colors, which again implies that there exists either a -clique which is monochromatically colored with the original th color, or a -clique which is monochromatically colored with the original th color. This implies the recursion.
Ramsey number
The smallest number satisfying the condition in the Ramsey theory is called the Ramsey number.
Alternatively, we can define as the smallest such that if , for any 2-coloring of in red and blue, there is either a red or a blue . The Ramsey theorem is stated as:
- " is finite for any positive integers and ."
The core of the inductive proof of the Ramsey theorem is the following recursion
From this recursion, we can deduce an upper bound for the Ramsey number.
Theorem - .
Proof. It is easy to verify the bound by induction.
Lovász local lemma
Consider a set of "bad" events . Suppose that for all . We want to show that there is a situation that none of the bad events occurs. Due to the probabilistic method, we need to prove that
- Case 1: mutually independent events.
If all the bad events are mutually independent, then
for any .
- Case 2: arbitrarily dependent events.
On the other hand, if we put no assumption on the dependencies between the events, then by the union bound (which holds unconditionally),
which is not an interesting bound for . We cannot improve bound without further information regarding the dependencies between the events.
We would like to know what is going on between the two extreme cases: mutually independent events, and arbitrarily dependent events. The Lovász local lemma provides such a tool.
The local lemma is powerful tool for showing the possibility of rare event under limited dependencies. The structure of dependencies between a set of events is described by a dependency graph.
Definition - Let be a set of events. A graph on the set of vertices is called a dependency graph for the events if for each , , the event is mutually independent of all the events .
- Example
- Let be a set of mutually independent random variables. Each event is a predicate defined on a number of variables among . Let be the unique smallest set of variables which determine . The dependency graph is defined by
- iff .
The following lemma, known as the Lovász local lemma, first proved by Erdős and Lovász in 1975, is an extremely powerful tool, as it supplies a way for dealing with rare events.
Lovász Local Lemma (symmetric case) - Let be a set of events, and assume that the following hold:
- for all , ;
- the maximum degree of the dependency graph for the events is , and
- .
- Then
- .
- Let be a set of events, and assume that the following hold:
We will prove a general version of the local lemma, where the events are not symmetric. This generalization is due to Spencer.
Lovász Local Lemma (general case) - Let be the dependency graph of events . Suppose there exist real numbers such that and for all ,
- .
- Then
- .
- Let be the dependency graph of events . Suppose there exist real numbers such that and for all ,
Proof. We can use the following probability identity to compute the probability of the intersection of events:
Lemma 1 - .
Proof. By definition of conditional probability,
- ,
so we have
- .
The lemma is proved by recursively applying this equation.
Next we prove by induction on that for any set of events ,
- .
The local lemma is a direct consequence of this by applying Lemma 1.
For , this is obvious. For general , let be the set of vertices adjacent to in the dependency graph. Clearly . And it holds that
- ,
which is due to the basic conditional probability identity
- .
We bound the numerator
The equation is due to the independence between and .
The denominator can be expanded using Lemma 1 as
which by the induction hypothesis, is at least
where is the edge set of the dependency graph.
Therefore,
Applying Lemma 1,
To prove the symmetric case. Let for all . Note that .
If the following conditions are satisfied:
- for all , ;
- ;
then for all ,
- .
Due to the local lemma for general cases, this implies that
- .
This gives the symmetric version of local lemma.
Ramsey number (continued)
We can use the local lemma to prove a lower bound for the diagonal Ramsey number.
Theorem - for some constant .
Proof. To prove a lower bound , it is sufficient to show that there exists a 2-coloring of without a monochromatic . We prove this by the probabilistic method.
Pick a random 2-coloring of by coloring each edge uniformly and independently with one of the two colors. For any set of vertices, let denote the event that forms a monochromatic . It is easy to see that .
For any -subset of vertices, and are dependent if and only if . For each , the number of that is at most , so the max degree of the dependency graph is .
Take for some appropriate constant .
Applying the local lemma, the probability that there is no monochromatic is
- .
Therefore, there exists a 2-coloring of which has no monochromatic , which means
- .
Theorem - .
, | 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 be positive integers. Then there exists an integer satisfying:
- For any -coloring of with , there exist an and a subset with such that all members of are colored with the th color.
Lemma (the "mixing color" trick)
It is then sufficient to prove the Ramsey's theorem for the two-coloring of a hypergraph, that is, to prove is finite.
Lemma
Proof. Let . Denote .
Let be an arbitrary 2-coloring of . It is then sufficient to show that there either exists an with such that all members of are colored red by ; or exists an with such that all members of are colored blue by .
We remove from and define a new coloring of by
- for any .
By the choice of and by symmetry, there exists a subset with such that all members of are colored with red by . Then there either exists an with such that is colored all blue by , in which case we are done; or exists an with such that is colored all red by . Next we prove that in the later case is all red, which will close our proof. Since all are colored with red by , then by our definition of , for all . Recalling that is colored all red by , is colored all red by and we are done.
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 , there is an such that any set of at least points in general position in the plane (i.e., no three of the points are on a line) contains points that are the vertices of a convex -gon.
Proof. Let . For , let be an arbitrary set of points in the plane, no three of which are on a line. Define a 2-coloring of the 3-subsets of points as follows: for any , let be the set of points covered by the triangle ; and , that is, indicates the oddness of the number of points covered by the triangle .
Since , there exists a such that and all members of are colored with the same value by .
We claim that the points in are the vertices of a convex -gon. If otherwise, by the definition of convexity, there exist such that . Since no three points are in the same line,
- ,
where all unions are disjoint. Then , which implies that cannot be equal, contradicting that all members of have the same color.
Yao's lower bound on implicit data structures
Lemma - Let be a power of 2 and . Suppose the universe is and the size of the data set is .
- If the data structure is a sorted table, any search algorithm requires at least accesses to the data structure in the worst case.
Proof. We will show by an adversarial argument that accesses are required to search for the key value from the universe . The construction of the adversarial data set is by induction on .
For and it is easy to see that two accesses are necessary.
Let . Assume the induction hypothesis to be true for all smaller ; we will prove it for the size of data set , size of universe and the search key .
Suppose that the first access position is . The adversary chooses the table content . The adversary's strategy is:
By symmetry, suppose it is the first case that . Then the key may be in any position , where . In fact, through is a sorted table of size which may contain any -subset of , and hence, in particular, any -subset of the universe
- .
The size of satisfies
- ,
and the desired key has the relative value in the universe .
By the induction hypothesis, more accesses will be required. Hence the total number of accesses is at least .
If the first access is , we symmetrically get that through is a sorted table of size which may contain any -subset of the universe
- .
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
- ,
where each specify a permutation of the sorted table. Thus, the sorted table is the simplest implicit data structure, in which is the identity for all .
Ramsey-like Theorems
Van der Waerden's Theorem
Theorem (Van der Waerden 1927) - For every choice of positive integers and , there exists an integer such that for every -coloring of where , there exists a monochromatic arithmetic progression of length .
Hales–Jewett Theorem
Theorem (Hales-Jewett 1963) - Let be a finte alphabet of symbols and let be a positive integer. Then there exists an integer such that for every -coloring of the cube where , there exists a combinatorial line, which is monochromatic.
Theorem (Hales-Jewett 1963) - Let be a finte alphabet of symbols and let be positive integers. Then there exists an integer such that for every -coloring of the cube where , there exists a combinatorial -space, which is monochromatic.