The exact value of the Ramsey number R(5,5)
Difficulty 67: the upper bound moved 49 → 48 → 46 over 30 years with ever larger computations, the lower bound 43 has stood since 1989, and closing even one unit needs either a far larger certified search or a structural idea nobody has; harder than the finite seven-gon question (45) and kissing number five (64), below the asymptotic diagonal Ramsey problem (78), which needs new ideas at every k. Application value 4: a benchmark for SAT and certified-search methods. Leverage 12: determines one number with spillover to a few small Ramsey values, below the asymptotic question (46).
The problem
How many people guarantee five who all know each other or five who are all strangers? Between 43 and 46.
- 1Pairs know each other or not
- 2Which party size forces five-in-a-row?
- 342 can dodge it, 46 cannot
- 443 to 46 is open
Graphs. A graph is a set of points (vertices) with some pairs joined by edges. A clique is a set of vertices that are all joined to each other; an independent set is one with no edges among its vertices.
Definition. is the least such that every graph on vertices contains a -clique or an independent set of size (equivalently every red/blue colouring of the edges of has a red or a blue ).
Path to understanding
foundations → problemThe research entries this problem rests on, in the order to read them. Each links to its explainer.
- Start with
- Step 2
- Step 3
- SAT solving (CDCL)Algorithm
- Step 4
- Extremal and probabilistic combinatoricsTheory · host
- Then
- The exact value of the Ramsey number R(5,5)The problem
State of the art
Upper bound 46: Angeltveit and McKay (arXiv:2409.15709, 2024, revised September 2025) proved by combining linear programming with a large computer-checked case analysis, each author implementing the computation independently; the previous upper bound was 48 (Angeltveit and McKay, arXiv:1703.08768, 2017). Lower bound 43: an explicit 2-colouring of the edges of with no monochromatic is known (Exoo, 1989). McKay and Radziszowski conjectured on the evidence that many such colourings of exist but none appear to extend. The gap is closed from above by exhaustive search only if a very large search space shrinks, and from below only by an unexpected colouring of .
Realistic applications
None directly. Small Ramsey numbers are used as benchmarks for SAT and exhaustive-search methods, and the techniques (symmetry breaking, certified large case analyses) are reused in verification.
What counts as solved
A certificate: either an explicit graph on 43 vertices with no 5-clique and no independent 5-set (a lower-bound improvement, checkable by decide or reflection), or a Lean-checkable proof that every graph on 45 (or 44) vertices has one (an upper-bound improvement, plausibly via a verified SAT or LP certificate).
How it gets verified
Bound / recordA numeric bound or record checked from a certificate or recomputation.
Current record: (lower bound Exoo 1989, upper bound Angeltveit–McKay, arXiv:2409.15709, summarized in the Small Ramsey Numbers survey). An improvement is a finite certificate. Lower bound to 44: a graph on 43 vertices, given as an adjacency matrix, with no 5-clique in it or its complement; this is checkable by a short program and, in Lean, by a decision procedure on SimpleGraph (Fin 43) with decidable adjacency (the corpus states the current bound as ramsey_number_five_five_lower_bound on 42 vertices). Upper bound to 45: the Lean statement , where is defined in the corpus file from Mathlib's (); the current bound is , and lives in the corpus' . A claimed upper-bound proof must come with a machine-checkable certificate (for instance a verified SAT/DRAT or LP proof replayed in Lean, or checked by a verified checker); an independent recomputation by a second implementation, as Angeltveit and McKay did, is the minimum for acceptance.
Claims under verification
+ add a claimNo claimed results on the Verification board for this problem yet.
Where the work is
The upper bound came from LP plus a huge exhaustive case analysis; the lower bound would need a lucky colouring or a proof that none exists.
Bottlenecks
ranked by votes- #1ComputeExhaustive extension of (5,5)-graphs
Closing the gap means classifying all colourings on 43 to 45 vertices; the search space grows enormously and requires strong symmetry breaking.
Community grades
Sign in to add your own grade.
Connected problems
Progress
- Sep 24, 2024R(5,5) ≤ 46source
Angeltveit and McKay improve the upper bound from 48 by LP and large computer-checked case analysis (preprint; revised 1 September 2025).