The Pigeonhole Principle and Ramsey Theory: Existential Combinatorics
We develop the generalized pigeonhole principle, prove the Erd\H{o}s--Szekeres theorem on monotone subsequences, establish the existence of Ramsey numbers R(s,t), give a complete proof that R(3,3) = 6, and derive the probabilistic lower bound R(k,k) > 2^{k/2}.
1 The Pigeonhole Principle
Theorem 1 (Pigeonhole principle).
If objects are placed into boxes, then at least one box contains two or more objects.
Proof.
We prove the contrapositive. If every box contains at most one object, then the total number of objects is at most , contradicting the assumption that there are objects. □
Theorem 2 (Generalized pigeonhole principle).
If objects are placed into boxes, then at least one box contains or more objects.
Proof.
If every box contained at most objects, the total would be at most , a contradiction. □
2 The Erdős–Szekeres Theorem
Theorem 3 (Erd\H{o}s–Szekeres theorem).
Every sequence of length at least contains a monotonically increasing subsequence of length or a monotonically decreasing subsequence of length .
Proof.
Let the sequence be . For each , let denote the length of the longest increasing subsequence starting at . If for some , we are done.Assume for all . Then takes values in , and there are indices. By the pigeonhole principle, at least indices share the same value of , say with . The subsequence must be monotonically decreasing. Indeed, if for some , then the longest increasing subsequence starting at would have length at least , contradicting . □
3 Ramsey Numbers
Definition 4 (Ramsey number).
The Ramsey number is the smallest positive integer such that every -coloring (red/blue) of the edges of contains either a red or a blue .
Theorem 5 (Existence of Ramsey numbers).
For all positive integers , . In particular, is finite.
Proof.
We argue by induction on .Base cases. and . Indeed, in any -coloring of , either there is a red edge (a red ) or all edges are blue, giving a blue . The argument for is symmetric.Inductive step. Let and assume and are finite. Set and -color the edges of . Fix any vertex and let be the set of vertices joined to by red edges and the set joined by blue edges. Since , the pigeonhole principle gives or .If : by definition, contains either a red or a blue . A blue finishes the proof. A red together with (which is joined to every vertex of by a red edge) forms a red .If : similarly, contains a red or a blue . In the latter case, adding yields a blue .This establishes .The upper bound. We prove by induction on . The base cases are and . For the inductive step,
where the last equality is Pascal's identity. □
4 Proof That
Theorem 6.
.
Proof.
Upper bound..Lower bound. We exhibit a -coloring of with no monochromatic triangle. Color the edges of (the -cycle) red and the edges of the complement (which is isomorphic to ) blue. Since contains no triangle, there is no red triangle. Since , there is no blue triangle either. Hence . □
5 A Probabilistic Lower Bound
Theorem 7 (Erd\H{o}s, 1947).
If , then . In particular, .
Proof.
Color each edge of independently red or blue with equal probability . For a fixed set of vertices, the probability that induces a monochromatic complete graph is . By the union bound,
If this quantity is strictly less than , then with positive probability no monochromatic exists, so there is at least one coloring that avoids it. Hence . Taking satisfies the condition, yielding . □
The probabilistic method, pioneered by Erdős, is one of the most powerful techniques in combinatorics. It yields non-constructive existence proofs by showing that a randomly chosen object satisfies the desired property with positive probability.
FO
Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.
1 followers·105 articles