Motivation
An extremal graph theorem asks how many edges force a particular subgraph. A Ramsey question gives every edge a color and asks whether one color must contain a complete graph. Both colors can have many edges, so merely knowing the total number of edges does not settle the question. The useful information is how the two color classes interact around a vertex.
There are two different tasks. An upper bound must work for every coloring. A lower bound needs one coloring that avoids both forbidden cliques. We first build universal guarantees by repeatedly restricting to neighbors. We then construct an exact small obstruction and use a finite random experiment to prove larger obstructions exist. None of these existence statements supplies a fast algorithm for the best coloring or determines all Ramsey numbers.
The arguments below use only elementary counting and finite probability; no asymptotic Ramsey estimate is assumed.
Definitions
Definition 10.5.1
(A two-color threshold and its quantifiers)
For positive integers and , let be the least positive integer such that every red/blue coloring of the edges of the complete simple graph contains either a red clique on vertices or a blue clique on vertices. A one-vertex clique has no edges and satisfies either color requirement. The existence of this least integer will be proved below.
A coloring avoids the pair when neither specified clique occurs. Thus one avoiding coloring on vertices proves , whereas a universal argument on vertices proves .
Interchanging color names proves the symmetry . Restricting a coloring to a subset shows that once the universal property holds at , it holds at every larger order. The boundary values follow from the singleton convention. For two or more vertices, coloring an edge means choosing one of its two colors; there is no requirement that both colors occur.
Definition 10.5.2
(Multicolor edge colorings and monochromatic cliques)
For an integer , a -coloring of assigns to each edge one of colors. A set of distinct vertices spans a monochromatic -clique when all edges between them receive the same color.
A proper vertex coloring, where adjacent vertices must differ, is a separate notion; here colors belong to edges, and equal colors on edges that share a vertex are allowed.
Theorem/proposition
Theorem 10.5.3
(Neighborhood recursion proves finiteness and a binomial upper bound)
For ,
All these finite thresholds exist, and
In particular, for every .
Theorem 10.5.4
(A finite random experiment supplies avoiding colorings)
Let and be integers. If
then some edge coloring of contains no monochromatic -clique, so . The binomial coefficient is zero when .
For every , this implies
The criterion is sufficient; failure of its numerical inequality does not prove that every coloring contains a forbidden clique.
Theorem 10.5.5
(Repeated restriction also proves a multicolor guarantee)
For integers and , put . Every -coloring of the complete graph on
vertices contains a monochromatic -clique. This is a finite upper bound, not a claim of optimality. For the displayed sum is .
Concept lensCombinatorial
Universal restriction and finite averaging answer opposite quantifiers
The neighborhood induction handles an arbitrary coloring and forces a witness: it proves a statement of the form “for every coloring there is a clique”. Finite averaging ranges over all colorings and proves that at least one has no witness: “there is a coloring with no clique”. An upper bound, a lower bound and an exact threshold require different evidence even when they concern the same finite graph.
The proofs below follow this split: the first and third theorems are proved by restriction, the second by averaging.
Proof sketch or proof idea
One vertex turns the next smaller thresholds into a larger one
The induction runs on and uses one center vertex to pass from two smaller thresholds to the larger one.
Proof
(Proof of the neighborhood recursion and the binomial bound)
Prove finiteness by induction on , starting with either parameter equal to . Suppose the smaller thresholds and already exist. Consider any coloring of and select one vertex .
If has at least red neighbors, restrict to of them. The inductive property gives either a red clique of size , which becomes a red -clique after adjoining , or a blue -clique, which already answers the original question.
Otherwise has at most red neighbors. Since its incident edges are partitioned by color, it has at least blue neighbors. Their induced complete graph contains a red -clique or a blue clique of size ; in the latter case add . Every coloring of therefore has the required clique. The set of admissible positive orders is nonempty, so its least element exists and is at most , proving the recurrence.
For the explicit bound, use the same induction with boundary value . By Pascal's identity,
so the inductive bounds for and add to the displayed coefficient. On the diagonal, is one term of , which gives the coarser exponential upper bound.
Proof X-ray
Where the center vertex is spent
The hypothesis used is only the inductive one: every coloring on vertices contains a red -clique or a blue -clique, and every coloring on vertices contains a red -clique or a blue -clique. The one non-obvious move is a pigeonhole count on the edges at : failing to have red neighbors leaves at least blue ones. The proof closes because is joined in the right color to every vertex of the retained set, so adjoining it upgrades the smaller clique of that color by one vertex, while a clique of the other color already has full size.
The count is exact. On vertices the center has only neighbors, and a split into red and blue neighbors leaves neither retained set large enough for the inductive hypothesis. This is why the recurrence adds the two smaller thresholds rather than their predecessors. A computed upper bound is not automatically attained: the recursion discards everything about how the two neighborhoods are joined to each other.
Count bad cliques instead of assuming their events are independent
The lower bound comes from computing an average over all colorings and observing that an average below one forces a coloring with value zero.
Proof
(Proof of the first-moment lower bound)
Color every edge of independently, red or blue with probability each. This is a finite uniform probability space: all colorings have equal weight. A fixed -set spans exactly edges. The probability that all are red is ; the same holds for blue. For these two events are disjoint, so the -set is monochromatic with probability .
Let count monochromatic -sets. Writing as a sum of indicator variables and using linearity of finite expectation gives
This calculation does not require different -set events to be independent; overlapping cliques generally share edges. If every coloring had at least one bad clique, would always be at least one and so would its average. An average strictly below one therefore implies a coloring with . Strictness matters: an average equal to one does not by itself force a zero outcome.
To obtain the exponential lower bound, take , so . Since the number of -subsets is at most the number of ordered -tuples divided by ,
For , the final quantity is because . Increasing by one multiplies its numerator by and its denominator by , so it stays strictly below one. This proves the asserted bound for every , including any case with , where . The proof establishes existence among explicitly finite colorings and requires no infinite random construction.
Preserve one more vertex after every color restriction
The multicolor proof repeats the center-vertex step, but keeps a record of colors instead of recursing on two parameters.
Proof
(Proof of the multicolor guarantee)
For a nonnegative integer write . Start with vertices. Choose a center and partition its remaining neighbors by the color of their edge to . Because , one of the color classes has at least vertices. Retain such a class and record its color beside the center.
Repeat until centers have been chosen and one final vertex remains, which happens because the retained sets have at least vertices. Every selected center sends edges of its recorded color to all later selected vertices, because the retained sets are nested. Among recorded colors, at least are equal, by pigeonhole. Take those centers and the final vertex . Any edge between two chosen centers has the color recorded at the earlier center; edges from a center to have that same color. Thus all edges among these vertices agree.
This nested-set invariant is stronger than merely selecting many vertices with equal labels. The labels control actual edges to all later retained vertices. It also explains why we retain a final vertex without assigning it a label: it completes a clique from equal-colored centers.
Worked examples
Worked example 10.5.6
(The triangle threshold is exactly six)
In any red/blue coloring of , a selected vertex has five neighbors, so at least three in one color, say red. If any edge among those three neighbors is red, it forms a red triangle with the center. Otherwise their three edges are blue, giving a blue triangle. The blue-neighbor case is symmetric, so .
For the opposite inequality, color the edges of a five-cycle red and every remaining edge blue. The red graph is a cycle with no triangle. Label vertices by residues modulo . The blue edges join differences and form the cycle , also triangle-free. This one avoiding coloring proves . Together the arguments give .
Worked example 10.5.7
(Feed exact small values into the recurrence)
If a coloring has no red edge, all its edges are blue. Hence : vertices suffice, while the all-blue coloring on vertices avoids both requested cliques. Using the exact triangle threshold in the recurrence gives
Applying it again gives . These are proved universal bounds. No matching avoiding constructions have been given here, so neither inequality is being promoted to an exact value. The results coincide with the binomial formula, and , because the inputs and equal their binomial bounds; the recurrence beats the formula only once an exact value below the binomial coefficient is fed in. Symmetry gives the corresponding reversed-parameter bounds.
Worked example 10.5.8
(An expectation test proves existence and has a visible limitation)
For and , the expected number of monochromatic five-cliques is
Thus some ten-vertex coloring avoids both colors' five-cliques, proving . The proof need not identify which coloring it is.
For the edge case and , the same expectation equals , so this test gives no avoiding coloring. Yet the five-cycle construction above does avoid both triangles. Failure of a sufficient first-moment test is therefore different from failure of the desired construction.
Common mistakes
Counterexample mode
A dense color need not contain the specified clique
Claim to test: if one color receives at least half the edges of , that color contains a triangle. Take and color a five-cycle red. Red has of the edges, exactly half, and each vertex has red degree ; a red triangle would need three vertices pairwise adjacent on the cycle, and no three vertices of a five-cycle are. The blue complement is the cycle , with the same density and the same obstruction. The claim is false. Edge density alone forces a triangle only beyond an extremal threshold, which has to be proved separately; it cannot replace the Ramsey argument, which uses how the color classes meet at a vertex.
Common mistake
(Multiplying probabilities of overlapping cliques)
It is tempting to estimate the probability of no monochromatic -clique as , as if the events for different -sets were independent. They are not in general. For , two -sets sharing three vertices share three edges; each is monochromatic with probability , but both are with probability , not . The first-moment argument needs only independent edge colors and linearity of expectation.
Common mistake
(Confusing edge colorings with proper vertex colorings)
A Ramsey coloring assigns colors to edges and places no restriction on edges that share a vertex. A proper vertex coloring assigns colors to vertices and forbids equal colors at the ends of an edge. Statements about chromatic number say nothing directly about monochromatic cliques in an edge coloring.
Common mistake
(Reading a bound as a value or in the wrong direction)
An avoiding coloring on vertices proves ; it never proves . Conversely, the recurrence and the multicolor sum give upper bounds that need not be attained: is not a statement that . An exact value needs a universal argument and an avoiding coloring that meet, as for .
Summary
Neighborhood restriction proves finite two-color thresholds and explicit binomial bounds; nested restriction gives a multicolor guarantee. An exact five-cycle obstruction settles the triangle threshold. Finite expectation proves other obstructions exist, with strict inequalities and sufficient-test limitations kept explicit. These arguments leave most exact thresholds and efficient searches open within this chapter.
Exercises
Quick check
(Prove for every positive integer , explicitly handling .)
Separate the singleton convention from the absence of red edges.
Solution
For the boundary convention gives . For , any coloring on vertices either has a red edge, already a red two-clique, or has every edge blue and hence a blue -clique. This proves the upper bound .
Color every edge on vertices blue. There is no red edge and there are too few vertices for a blue -clique. Thus the threshold exceeds , proving equality. The argument works at as well: a singleton avoids both two-cliques.
Quick check
(Evaluate the multicolor theorem's bound for three colors and triangles. Explain exactly which selected vertices form the clique.)
Use and retain the final unlabeled vertex.
Solution
With and we have , and the guaranteed order is . Restriction selects six centers followed by one last vertex. Among six recorded colors from three, at least two centers have the same recorded color. Their mutual edge, determined by the earlier one's label, has that color, and both edges to the final vertex have that color too. These two centers and the final vertex form the required triangle.
The numerical guarantee is deliberately coarse. The proof gives no lower construction approaching and no claim that this is the actual three-color triangle threshold.
Quick check
(For prove the stronger lower estimate . State why it is still an existence bound.)
Compare the sum of logarithms with the integral from to before applying the first-moment test.
Solution
Because the logarithm is increasing, for , so
In particular, . Take ; it is positive for , and . The first-moment estimate gives
An avoiding coloring therefore exists, and its order proves the desired strict lower bound. We have averaged over all finite edge colorings; no efficient method for finding a successful coloring, optimal threshold or efficient certificate of avoidance for unbounded follows from this calculation alone.