Ramsey Number

A Ramsey number R(s,t) is the smallest integer n such that every graph with n vertices contains either a clique of size s or an independent set of size t. These numbers are the quantitative face of Ramsey theory: they measure exactly how large a structure must be before order becomes unavoidable.

Despite their simple definition, Ramsey numbers are notoriously difficult to compute. R(3,3) = 6 and R(4,4) = 18 are known exactly, but R(5,5) remains unknown — bounded between 43 and 48 — and R(6,6) is known only to lie between 102 and 165. The gap between what Ramsey theory proves must exist and what mathematicians can construct is one of the most dramatic in mathematics. The probabilistic method provides lower bounds; constructive upper bounds require ingenuity that has resisted systematic capture. The probabilistic method demonstrates existence without construction, and Ramsey numbers are where that demonstration is most painfully disconnected from what we can actually find.