组合数学 (Spring 2013)/Ramsey theory
Contents
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.
The following theorem is due to Spencer in 1975, which is the best known lower bound for diagonal Ramsey number.
Theorem (Spencer 1975) - for some constant .
Its proof uses the Lovász local lemma in the probabilistic method.
Lovász Local Lemma (symmetric case) - Let be a set of events, and assume that the following hold:
- for all , ;
- each event is independent of all but at most other events, and
- .
- Then
- .
- Let be a set of events, and assume that the following hold:
We can use the local lemma to prove a lower bound for the diagonal Ramsey number.
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 .