Ramsey's Theorem

This is a generalized version of pigeonhole principle.

For all integers \(n\), \(m\), and \(c\), there exists an integer \(g(n,m,c)\) with the following property. For every set \(S\) of size at least \(g(n,m,c)\), and any coloring of the $n$-subsets of \(S\) with at most \(c\) colors, there is some subset \(C\) of \(S\) of size \(m\) that has all of its $n$-subsets colored the same color.

Let \(n = 2\), \(m = 3\), and \(c = 2\). Then \(g(2,3,2) = 6\). This means that if we have a set of size at least 6, and we color the 2-subsets of the set with 2 colors, then there is a subset of size 3 that has all of its 2-subsets colored the same color.

Ramsey’s Theorem (in one of its most famous forms) says that if you color the edges of a sufficiently large complete graph using only a few colors, you are guaranteed to find a smaller complete subgraph all of whose edges are the same color.

A classic, everyday way to phrase this is:

At any party with at least 6 people, you can always find three people who all know each other or three people who are all mutual strangers.

Intuitive takeaway: In any sufficiently large structure colored in a small number of ways, some kind of organized or homogeneous substructure (all edges one color) must appear. You can’t avoid “order” altogether by random coloring once the set is large enough.