A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
The Ramsey number R(r, b) is the minimum n such that any 2-coloring of Kₙ contains either a red Kᵣ or a blue Kᵦ. Computing Ramsey numbers is notoriously difficult; even R(5,5) is unknown. Known bounds come from probabilistic methods and explicit constructions, illustrating the power and limits of combinatorial techniques.
Compute small Ramsey numbers (R(3,3), R(3,4)) by explicit case analysis and exhaustive search on small graphs.
Ramsey numbers grow very rapidly; even computing R(4,5) is computationally hard. Not all pairs of numbers have easy closed forms.
From Ramsey theory foundations, you know the central theme: complete disorder is impossible — any large enough structure must contain some organized substructure. Ramsey numbers make this precise and quantitative. The Ramsey number R(r, b) asks: what is the smallest n such that every 2-coloring of the edges of Kₙ (the complete graph on n vertices) must contain either a red Kᵣ or a blue Kᵦ? In other words, R(r, b) is the threshold beyond which you cannot avoid a monochromatic complete subgraph.
The canonical example is R(3, 3) = 6. To see why 5 is not enough, you can exhibit a 2-coloring of K₅ with no monochromatic triangle. To see why 6 works, pick any vertex v in K₆: it has 5 edges. By the pigeonhole principle, at least 3 of those edges share the same color — say red. Now look at the 3 vertices on the other ends of those red edges. If any edge among these 3 is also red, that edge together with two red edges from v forms a red triangle. If none are red, all three edges among those vertices are blue, forming a blue triangle. Either way, K₆ forces a monochromatic triangle. This is the Ramsey argument in miniature: contradiction through exhaustion of cases.
The difficulty of Ramsey numbers becomes apparent quickly. R(4, 4) = 18, R(3, 5) = 14, and R(5, 5) is unknown — it is known only to lie between 43 and 48. The rapid growth is captured by the diagonal Ramsey bound: R(k, k) ≤ C(2k−2, k−1) ≈ 4ᵏ / √k (proved by the binomial coefficient bound), but probabilistic lower bounds (introduced by Erdős) show R(k, k) ≥ 2k/2, meaning the true value is somewhere in an exponentially wide window.
The probabilistic method used for lower bounds is itself a landmark technique: randomly 2-color each edge of Kₙ with equal probability, then compute the expected number of monochromatic Kₖ subgraphs. If this expectation is less than 1, there must exist a coloring with none — but we cannot easily find it. This "non-constructive" lower bound, which proves existence of good colorings without building one, was revolutionary in combinatorics. The challenge of closing the gap between upper and lower bounds for R(k, k) remains one of the most notorious open problems in the field.