The pigeonhole principle says that a large enough collection cannot be distributed without repetition. Ramsey theory asks for a much richer unavoidable pattern: however the edges of a large complete graph are colored with two colors, some set of vertices has all of its connecting edges in a single color. This unit proves that such sets exist, bounds how large the graph must be, and determines the first nontrivial value exactly. It uses induction, binomial coefficients, and the double-counting techniques of the earlier counting units.
Definitions
Definition 2.11.1
(Monochromatic cliques and Ramsey numbers)
Let be the complete graph on vertices. A red–blue coloring of assigns one of the colors red or blue to each edge. A set of vertices is a red clique if every edge with both endpoints in is red, and a blue clique is defined likewise; a clique of vertices is an -clique. For integers , the Ramsey number is the least such that every red–blue coloring of contains a red -clique or a blue -clique. The statement that this least exists is part of the theorem below. A coloring of with no red -clique and no blue -clique is a witness that .
Two immediate properties follow. Because red and blue can be exchanged, . A -clique has no edges, so any single vertex is both a red and a blue -clique: .
Concept lensStructural
Cliques and independent sets in one graph
Keep only the red edges. A red–blue coloring of is then the same thing as a graph on vertices: red edges are edges of , blue edges are non-edges. A red -clique is a clique of size in , and a blue -clique is an independent set of size , that is, vertices with no edge of among them. Hence is the least such that every graph on vertices has a clique of size or an independent set of size . In this language the symmetry is passage to the complement graph, and the witness for below is the -cycle, which has no triangle and whose complement is again a -cycle.
Existence and the binomial upper bound
Theorem 2.11.2
(Ramsey's theorem for two colors)
For all integers the number exists, and
Moreover, for all ,
Proof
(Induction on through one vertex)
We argue by induction on , and assume that and exist (the base cases with or are known: they equal ). Put and take any red–blue coloring of . Fix a vertex . It has neighbors, split into the set joined to by red edges and the set joined by blue edges. If and then , a contradiction. So or .
Case . Inside there is a red -clique or a blue -clique. In the second case we are done. In the first, adding gives a red -clique, since is joined to every vertex of by a red edge.
Case . Symmetrically, contains a red -clique, or a blue -clique to which is added to form a blue -clique.
In every case the coloring has a red -clique or a blue -clique, so exists and is at most .
Proof X-ray
Two jobs for one vertex
The fixed vertex does two jobs. First, its edges are split by color into and , and the choice is exactly what forces one side to be large: if both sides were below their thresholds, then . This is the pigeonhole principle with the unequal capacities and . Second, is the vertex added to a clique found inside its color class, and the extension works only when the clique's color matches the color of the edges from : a red -clique in extends, while a blue -clique in needs no extension.
The induction hypothesis is applied to the subgraph induced on or on , which is again a complete graph with a red–blue coloring; this is why and , not , are compared with Ramsey numbers. Each step lowers by one and ends at the base cases or , so the induction closes. The contradiction uses only , so the argument says nothing about vertices; for , nine vertices already suffice.
Proof
(Induction with Pascal's rule)
For or the bound reads or , which is true. For , assume the bound for and . The recursion and Pascal's rule give
For example and .
Lower bounds by witnesses and by counting
A lower bound needs a single coloring of with no red -clique and no blue -clique. The first family is easy: . A red edge is a red -clique, so a coloring with no red -clique has all edges blue, and then with all edges blue has no blue -clique; hence , which together with the upper bound gives .
For general explicit witnesses are hard to find, and a probabilistic counting argument gives a lower bound with no construction.
Theorem 2.11.3
(A counting lower bound)
Let . If , then .
Proof
(Union bound over all -sets)
Color each edge of red or blue independently, so that all colorings are equally likely. A fixed set of vertices spans edges. It is a red clique in exactly colorings, and a blue clique in the same number, so the probability that it is monochromatic is . By the union bound over the sets, the probability that some -set is monochromatic is at most . Hence some coloring has no monochromatic -clique, which is a witness for .
Worked examples
Worked example 2.11.4
()
Upper bound: the theorem gives . Direct reading: in any coloring of , a vertex has five neighbors, so at least three of its edges have the same color, say red, going to . If one of is red, it forms a red triangle with . Otherwise is a blue triangle.
Lower bound: color on vertices so that the edge is red when and blue when . The red edges form the -cycle , the blue edges form the -cycle . A -cycle contains no triangle, so there is no monochromatic triangle. Thus , and : among any six people, three are mutual acquaintances or three are mutual strangers.
Worked example 2.11.5
(An upper bound for )
The recursion gives . The binomial bound gives as well. These are upper bounds only. The exact value is known to be , but proving that requires a sharper argument than the recursion, which is not given here.
Worked example 2.11.6
(Counting lower bounds for and )
For the factor is . For , and , so . For , and , so the argument stops. For the factor is . For , and , so ; for , and the argument stops. These bounds are weak for small ; the point of the method is that it works for every , as the next example shows.
Worked example 2.11.7
(The exponent in the counting bound)
Take and . Using we get . For this is , and for it is even smaller since grows faster than . So for all . For this reads .
Common mistakes and subtle points
Common mistake
(The recursion is an inequality)
The recursion is an inequality, not an equality: is not claimed to equal . The proof only shows that vertices suffice.
Common mistake
(One coloring settles only one direction)
Determining needs both directions. An upper bound shows every coloring of has a clique; a lower bound needs a specific coloring of a smaller complete graph without one. Showing only that some particular coloring of has a triangle proves nothing about .
Common mistake
(The color of the clique must match the edges from )
A monochromatic clique means all edges among its vertices have the same color, not that the vertices are joined to some outside vertex by edges of that color. In the proof of the recursion, red edges from to and edges inside are different roles: the clique found inside is extended by only when its color matches the color of the edges from .
Counterexample mode
Six vertices do not suffice for three colors
Claim: since , every coloring of the edges of , with any number of colors, has a monochromatic triangle. Take the red and blue -cycles on vertices from the worked example, add a vertex , and color its five edges green. Red and blue have no triangle, as before, and the green edges all meet at vertex , so no three of them form a triangle. The theorem is about two colors. The same vertex argument repairs it for three: a vertex of has edges, so some color reaches neighbors, and among them an edge of that color closes a triangle, while otherwise they are -colored and applies.
The counting argument shows existence without exhibiting a coloring. It shows that some coloring avoids monochromatic -cliques, but does not say which one.
Ramsey numbers are defined by a minimum over . If every coloring of has a monochromatic clique, then so does every coloring of for (restrict to vertices), so the property is monotone in and "least " is well defined.
Exercises
Quick check
(Prove that for every .)
Solution · Answer
Take any red–blue coloring of . If some edge is blue, it is a blue -clique. Otherwise every edge is red and all vertices form a red -clique. So . The coloring of with all edges red has no blue edge and fewer than vertices, so it has neither a red -clique nor a blue -clique; hence and .
Quick check
(Color the edges of on the vertex set , , so that an edge is red when it joins to and blue when both endpoints lie in or both lie in . Find all monochromatic triangles, and explain how the result is consistent with .)
Solution · Answer
Red edges join to , so the red graph is bipartite and has no triangle. A triangle with all edges blue must lie inside or inside (a triangle meeting both sides contains an – edge, which is red). Both and are blue triangles, and there are no others. So there are exactly two monochromatic triangles, both blue. Since , at least one must exist in every coloring of , and indeed two do.
Quick check
(Use the recursion and the bound to prove , and compute the binomial upper bound for .)
Solution · Answer
By the recursion , using from the text. The binomial bound is .
Quick check
(Apply the counting lower bound with : show that holds for but not for , and compare the conclusion with the true value .)
Solution · Answer
For , , so . For , , which is not less than , so the argument stops. It proves only , while the true value is ; the counting method is far from sharp for small .
Quick check
(Call two people acquaintances or strangers. Prove directly that among any people there are three mutual acquaintances or four mutual strangers.)
Solution · Answer
Let acquaintances be joined by red edges and strangers by blue edges in the complete graph on people, and fix a person . Let be the number of acquaintances of and the number of strangers. If , then among the acquaintances either two are acquaintances of each other (they form, with , three mutual acquaintances) or all pairs are strangers (at least four mutual strangers). If , then , and among six or more strangers of , since , there are three mutual acquaintances or three mutual strangers; three mutual strangers together with give four mutual strangers. In every case the claim holds.