Generalized Pigeonhole Principle

We revisit PHP with a graph theory lens. Often, "pigeons" are edges and "holes" are vertices (or colors).

Ramsey Numbers (Intro)

R (3, 3) = 6

: In any group of 6 people (edges colored Red/Blue), there is either a Red triangle (3 mutual friends) or a Blue triangle (3 mutual strangers).

Geometric Applications

Placing points in a figure such that minimum distance is maximized.

Example

Given 5 points in an equilateral triangle of side 1, prove two are within distance

1/2

Proof. Divide the triangle into 4 smaller equilateral triangles of side $1/2$ . By PHP, 2 points lie in the same small triangle. Max distance is $1/2$ . ∎

Practice Problems

Exercise (Problem 1)

Show that if edges of

K_{6}

are colored with 2 colors, there exists a monochromatic triangle.

Exercise (Problem 2)

Given 9 lattice points in 3D space, prove the midpoint of some pair is also a lattice point.

Exercise (Problem 3)

Prove that any set of

n + 1

integers from

{1, \dots, 2 n}

contains two that are coprime.