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}.

Folio Official

March 1, 2026

1 The Pigeonhole Principle

Theorem 1 (Pigeonhole principle).

n + 1

objects are placed into

n

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

n

, contradicting the assumption that there are

n + 1

objects. □

Theorem 2 (Generalized pigeonhole principle).

kn + 1

objects are placed into

n

boxes, then at least one box contains

k + 1

or more objects.

Proof.

If every box contained at most

k

objects, the total would be at most

kn

, a contradiction. □

2 The Erdős–Szekeres Theorem

Theorem 3 (Erd\H{o}s–Szekeres theorem).

Every sequence of length at least

rs + 1

contains a monotonically increasing subsequence of length

r + 1

or a monotonically decreasing subsequence of length

s + 1

Proof.

Let the sequence be

a_{1}, a_{2}, \dots, a_{rs + 1}

. For each

a_{i}

, let

ℓ_{i}

denote the length of the longest increasing subsequence starting at

a_{i}

. If

ℓ_{i} \geq r + 1

for some

i

, we are done.

Assume

ℓ_{i} \leq r

for all

i

. Then

ℓ_{i}

takes values in

{1, 2, \dots, r}

, and there are

rs + 1

indices. By the pigeonhole principle, at least

s + 1

indices share the same value of

ℓ_{i}

, say

ℓ_{i_{1}} = ℓ_{i_{2}} = \dots = ℓ_{i_{s + 1}}

with

i_{1} < i_{2} < \dots < i_{s + 1}

. The subsequence

a_{i_{1}}, a_{i_{2}}, \dots, a_{i_{s + 1}}

must be monotonically decreasing. Indeed, if

a_{i_{j}} \leq a_{i_{k}}

for some

j < k

, then the longest increasing subsequence starting at

a_{i_{j}}

would have length at least

ℓ_{i_{k}} + 1 > ℓ_{i_{j}}

, contradicting

ℓ_{i_{j}} = ℓ_{i_{k}}

. □

3 Ramsey Numbers

Definition 4 (Ramsey number).

The Ramsey number

R (s, t)

is the smallest positive integer

N

such that every

2

-coloring (red/blue) of the edges of

K_{N}

contains either a red

K_{s}

or a blue

K_{t}

Theorem 5 (Existence of Ramsey numbers).

For all positive integers

s, t \geq 2

R (s, t) \leq (s - 1 s + t - 2)

. In particular,

R (s, t)

is finite.

Proof.

We argue by induction on

s + t

Base cases.

R (s, 2) = s

and

R (2, t) = t

. Indeed, in any

2

-coloring of

K_{s}

, either there is a red edge (a red

K_{2}

) or all edges are blue, giving a blue

K_{s}

. The argument for

R (2, t) = t

is symmetric.

Inductive step. Let

s, t \geq 3

and assume

R (s - 1, t)

and

R (s, t - 1)

are finite. Set

N = R (s - 1, t) + R (s, t - 1)

and

2

-color the edges of

K_{N}

. Fix any vertex

v

and let

A

be the set of vertices joined to

v

by red edges and

B

the set joined by blue edges. Since

∣ A ∣ + ∣ B ∣ = N - 1 = R (s - 1, t) + R (s, t - 1) - 1

, the pigeonhole principle gives

∣ A ∣ \geq R (s - 1, t)

∣ B ∣ \geq R (s, t - 1)

∣ A ∣ \geq R (s - 1, t)

: by definition,

A

contains either a red

K_{s - 1}

or a blue

K_{t}

. A blue

K_{t}

finishes the proof. A red

K_{s - 1}

together with

v

(which is joined to every vertex of

A

by a red edge) forms a red

K_{s}

∣ B ∣ \geq R (s, t - 1)

: similarly,

B

contains a red

K_{s}

or a blue

K_{t - 1}

. In the latter case, adding

v

yields a blue

K_{t}

This establishes

R (s, t) \leq R (s - 1, t) + R (s, t - 1)

The upper bound. We prove

R (s, t) \leq (s - 1 s + t - 2)

by induction on

s + t

. The base cases are

R (s, 2) = s = (s - 1 s)

and

R (2, t) = t = (1 t)

. For the inductive step,

R (s, t) \leq R (s - 1, t) + R (s, t - 1) \leq (s - 2 s + t - 3) + (s - 1 s + t - 3) = (s - 1 s + t - 2),

where the last equality is Pascal's identity. □

4 Proof That $R (3, 3) = 6$

Theorem 6.

R (3, 3) = 6

Proof.

Upper bound.

R (3, 3) \leq R (2, 3) + R (3, 2) = 3 + 3 = 6

Lower bound. We exhibit a

2

-coloring of

K_{5}

with no monochromatic triangle. Color the edges of

C_{5}

(the

5

-cycle) red and the edges of the complement

\overline{C_{5}}

(which is isomorphic to

C_{5}

) blue. Since

C_{5}

contains no triangle, there is no red triangle. Since

\overline{C_{5}} ≅ C_{5}

, there is no blue triangle either. Hence

R (3, 3) > 5

. □

5 A Probabilistic Lower Bound

Theorem 7 (Erd\H{o}s, 1947).

(k N) 2^{1 - (2 k)} < 1

, then

R (k, k) > N

. In particular,

R (k, k) > 2^{k /2}

Proof.

Color each edge of

K_{N}

independently red or blue with equal probability

1/2

. For a fixed set

S

k

vertices, the probability that

S

induces a monochromatic complete graph is

2 \cdot 2^{- (2 k)}

. By the union bound,

Pr [a monochromatic K_{k} exists] \leq (k N) \cdot 2 \cdot 2^{- (2 k)} = (k N) 2^{1 - (2 k)} .

If this quantity is strictly less than

1

, then with positive probability no monochromatic

K_{k}

exists, so there is at least one coloring that avoids it. Hence

R (k, k) > N

. Taking

N = ⌊ 2^{k /2} ⌋

satisfies the condition, yielding

R (k, k) > 2^{k /2}

. □

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.

Combinatorics Discrete Mathematics Textbook Pigeonhole Principle Ramsey Theory

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

The Pigeonhole Principle and Ramsey Theory: Existential Combinatorics

Folio Official

March 1, 2026

1 The Pigeonhole Principle

Theorem 1 (Pigeonhole principle).

n + 1

objects are placed into

n

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

n

, contradicting the assumption that there are

n + 1

objects. □

Theorem 2 (Generalized pigeonhole principle).

kn + 1

objects are placed into

n

boxes, then at least one box contains

k + 1

or more objects.

Proof.

If every box contained at most

k

objects, the total would be at most

kn

, a contradiction. □

2 The Erdős–Szekeres Theorem

Theorem 3 (Erd\H{o}s–Szekeres theorem).

Every sequence of length at least

rs + 1

contains a monotonically increasing subsequence of length

r + 1

or a monotonically decreasing subsequence of length

s + 1

Proof.

Let the sequence be

a_{1}, a_{2}, \dots, a_{rs + 1}

. For each

a_{i}

, let

ℓ_{i}

denote the length of the longest increasing subsequence starting at

a_{i}

. If

ℓ_{i} \geq r + 1

for some

i

, we are done.

Assume

ℓ_{i} \leq r

for all

i

. Then

ℓ_{i}

takes values in

{1, 2, \dots, r}

, and there are

rs + 1

indices. By the pigeonhole principle, at least

s + 1

indices share the same value of

ℓ_{i}

, say

ℓ_{i_{1}} = ℓ_{i_{2}} = \dots = ℓ_{i_{s + 1}}

with

i_{1} < i_{2} < \dots < i_{s + 1}

. The subsequence

a_{i_{1}}, a_{i_{2}}, \dots, a_{i_{s + 1}}

must be monotonically decreasing. Indeed, if

a_{i_{j}} \leq a_{i_{k}}

for some

j < k

, then the longest increasing subsequence starting at

a_{i_{j}}

would have length at least

ℓ_{i_{k}} + 1 > ℓ_{i_{j}}

, contradicting

ℓ_{i_{j}} = ℓ_{i_{k}}

. □

3 Ramsey Numbers

Definition 4 (Ramsey number).

The Ramsey number

R (s, t)

is the smallest positive integer

N

such that every

2

-coloring (red/blue) of the edges of

K_{N}

contains either a red

K_{s}

or a blue

K_{t}

Theorem 5 (Existence of Ramsey numbers).

For all positive integers

s, t \geq 2

R (s, t) \leq (s - 1 s + t - 2)

. In particular,

R (s, t)

is finite.

Proof.

We argue by induction on

s + t

Base cases.

R (s, 2) = s

and

R (2, t) = t

. Indeed, in any

2

-coloring of

K_{s}

, either there is a red edge (a red

K_{2}

) or all edges are blue, giving a blue

K_{s}

. The argument for

R (2, t) = t

is symmetric.

Inductive step. Let

s, t \geq 3

and assume

R (s - 1, t)

and

R (s, t - 1)

are finite. Set

N = R (s - 1, t) + R (s, t - 1)

and

2

-color the edges of

K_{N}

. Fix any vertex

v

and let

A

be the set of vertices joined to

v

by red edges and

B

the set joined by blue edges. Since

∣ A ∣ + ∣ B ∣ = N - 1 = R (s - 1, t) + R (s, t - 1) - 1

, the pigeonhole principle gives

∣ A ∣ \geq R (s - 1, t)

∣ B ∣ \geq R (s, t - 1)

∣ A ∣ \geq R (s - 1, t)

: by definition,

A

contains either a red

K_{s - 1}

or a blue

K_{t}

. A blue

K_{t}

finishes the proof. A red

K_{s - 1}

together with

v

(which is joined to every vertex of

A

by a red edge) forms a red

K_{s}

∣ B ∣ \geq R (s, t - 1)

: similarly,

B

contains a red

K_{s}

or a blue

K_{t - 1}

. In the latter case, adding

v

yields a blue

K_{t}

This establishes

R (s, t) \leq R (s - 1, t) + R (s, t - 1)

The upper bound. We prove

R (s, t) \leq (s - 1 s + t - 2)

by induction on

s + t

. The base cases are

R (s, 2) = s = (s - 1 s)

and

R (2, t) = t = (1 t)

. For the inductive step,

R (s, t) \leq R (s - 1, t) + R (s, t - 1) \leq (s - 2 s + t - 3) + (s - 1 s + t - 3) = (s - 1 s + t - 2),

where the last equality is Pascal's identity. □

4 Proof That $R (3, 3) = 6$

Theorem 6.

R (3, 3) = 6

Proof.

Upper bound.

R (3, 3) \leq R (2, 3) + R (3, 2) = 3 + 3 = 6

Lower bound. We exhibit a

2

-coloring of

K_{5}

with no monochromatic triangle. Color the edges of

C_{5}

(the

5

-cycle) red and the edges of the complement

\overline{C_{5}}

(which is isomorphic to

C_{5}

) blue. Since

C_{5}

contains no triangle, there is no red triangle. Since

\overline{C_{5}} ≅ C_{5}

, there is no blue triangle either. Hence

R (3, 3) > 5

. □

5 A Probabilistic Lower Bound

Theorem 7 (Erd\H{o}s, 1947).

(k N) 2^{1 - (2 k)} < 1

, then

R (k, k) > N

. In particular,

R (k, k) > 2^{k /2}

Proof.

Color each edge of

K_{N}

independently red or blue with equal probability

1/2

. For a fixed set

S

k

vertices, the probability that

S

induces a monochromatic complete graph is

2 \cdot 2^{- (2 k)}

. By the union bound,

Pr [a monochromatic K_{k} exists] \leq (k N) \cdot 2 \cdot 2^{- (2 k)} = (k N) 2^{1 - (2 k)} .

If this quantity is strictly less than

1

, then with positive probability no monochromatic

K_{k}

exists, so there is at least one coloring that avoids it. Hence

R (k, k) > N

. Taking

N = ⌊ 2^{k /2} ⌋

satisfies the condition, yielding

R (k, k) > 2^{k /2}

. □

Combinatorics Discrete Mathematics Textbook Pigeonhole Principle Ramsey Theory

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

The Pigeonhole Principle and Ramsey Theory: Existential Combinatorics

1 The Pigeonhole Principle

2 The Erdős–Szekeres Theorem

3 Ramsey Numbers

4 Proof That $R (3, 3) = 6$

5 A Probabilistic Lower Bound

Share your expertise with the world

More from Folio Official

Recurrence Relations and Counting: Solving Linear Recurrences

The Inclusion--Exclusion Principle: Counting by Alternating Sums

Combinatorial Designs and Latin Squares: Balanced Arrangements

Burnside's Lemma and P\'olya Enumeration: Counting Under Symmetry

The Pigeonhole Principle and Ramsey Theory: Existential Combinatorics

1 The Pigeonhole Principle

2 The Erdős–Szekeres Theorem

3 Ramsey Numbers

4 Proof That $R (3, 3) = 6$

5 A Probabilistic Lower Bound

Share your expertise with the world

More from Folio Official

Recurrence Relations and Counting: Solving Linear Recurrences

The Inclusion--Exclusion Principle: Counting by Alternating Sums

Combinatorial Designs and Latin Squares: Balanced Arrangements

Burnside's Lemma and P\'olya Enumeration: Counting Under Symmetry

1 The Pigeonhole Principle

2 The Erdős–Szekeres Theorem

3 Ramsey Numbers

4 Proof ThatR(3,3)=6

5 A Probabilistic Lower Bound

Share your expertise with the world

More from Folio Official

Recurrence Relations and Counting: Solving Linear Recurrences

The Inclusion--Exclusion Principle: Counting by Alternating Sums

Combinatorial Designs and Latin Squares: Balanced Arrangements

Burnside's Lemma and P\'olya Enumeration: Counting Under Symmetry

1 The Pigeonhole Principle

2 The Erdős–Szekeres Theorem

3 Ramsey Numbers

4 Proof ThatR(3,3)=6

5 A Probabilistic Lower Bound

Share your expertise with the world

More from Folio Official

Recurrence Relations and Counting: Solving Linear Recurrences

The Inclusion--Exclusion Principle: Counting by Alternating Sums

Combinatorial Designs and Latin Squares: Balanced Arrangements

Burnside's Lemma and P\'olya Enumeration: Counting Under Symmetry

4 Proof That $R (3, 3) = 6$

4 Proof That $R (3, 3) = 6$