Introduction to Ramsey Theory

Combinatorics · Axiom Academy

LESSON Introduction to Ramsey Theory Discovering why complete disorder is impossible in sufficiently large structures 1. The Pigeonhole Principle: A Starting Point Before we explore Ramsey theory, let's revisit the pigeonhole principle. If you place n + 1 pigeons into n holes, at least one hole must contain more than one pigeon. This simple observation is the foundation of Ramsey theory. Watch as we demonstrate with 7 pigeons and 6 holes: 2. The Party Problem: Ramsey's Classic Example Consider a party with 6 people. Between any two people, they are either friends (blue edge) or strangers (red edge). Ramsey theory proves that you must have either 3 mutual friends or 3 mutual strangers. This is expressed as R(3,3) = 6 , meaning 6 is the minimum number of people needed to guarantee a monochromatic triangle in a 2-coloring of the complete graph. The Ramsey number R(m, n) is the smallest number of vertices such that any 2-coloring (red/blue) of the complete graph contains either: While we know R(3,3) = 6, finding exact Ramsey numbers becomes incredibly difficult. Even R(5,5) is unknown! Paul Erdős famously said: "Imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of R(5,5) or they will destroy our planet... we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for R(6,6). In that case, we should attempt to destroy the aliens."

This is the written version of the interactive lesson above. See the full Combinatorics course.