Papex

Open problem · Mathematics · Open

Ramsey number R(5, 5)

What is the smallest group size that guarantees five people who all know each other or five who are all strangers?

Summary

Any six people include three mutual acquaintances or three mutual strangers, so R(3, 3) = 6. For five, the corresponding number R(5, 5) is known only to lie between 43 and 46.

Why it is open

The Ramsey number R(s, t) is the smallest n such that every graph on n vertices contains either a clique of s vertices, in which every pair is joined, or an independent set of t vertices, in which no pair is joined [5]. A problem in the 1953 Putnam competition amounts to R(3, 3) ≤ 6, and in 1955 R. E. Greenwood and A. M. Gleason proved that R(3, 3) = 6 and R(4, 4) = 18 [1]. To show that 17 vertices are not enough, they joined the 17 elements of a finite field whenever their difference is a quadratic residue [1].

For R(5, 5), the April 2026 revision of Stanisław Radziszowski's survey of small Ramsey numbers gives 43 ≤ R(5, 5) ≤ 46 [6]. The two bounds call for different kinds of work. A graph with no five mutually joined and no five mutually unjoined vertices is called a (5, 5)-graph, and R(5, 5) is the least n for which no (5, 5)-graph on n vertices exists [3]. Raising the lower bound means exhibiting a (5, 5)-graph on 43 or more vertices; lowering the upper bound means proving that none exists on a given number of vertices, which so far has meant very large computer searches [3, 5]. The survey notes that such upper bounds were "difficult to obtain" and "often involved massive computations", R(5, 5) among them [6].

A resolution is the exact value, and no body sets a further bar; the survey records the accepted bounds with their references [6]. Vigleik Angeltveit and Brendan McKay wrote in 2017 that the value "is widely believed to be 43", because "a lot of computer resources have been expended in an unsuccessful attempt" to construct a (5, 5)-graph on 43 vertices [4].

What is known

The lower bound (1965–1989). McKay and Radziszowski's 1997 history of the problem lists lower bounds of 38 by Abbott in 1965, from quadratic residues modulo 37, 42 by Irving in 1973, from sum-free sets, and 43 by Geoffrey Exoo in 1989, found by simulated annealing [3]. Exoo described a colouring of the edges of the complete graph on 42 vertices in two colours with no five vertices whose ten edges all share a colour; the edges of one colour form a (5, 5)-graph, so R(5, 5) ≥ 43 [2, 3]. A 2022 preprint by Lachlan Ge and colleagues replaces the computer check of Exoo's construction with written arguments [7].

The upper bound to 49 (1965–1997). The upper bound fell from 59 in 1965 to 55 in 1971, then in work by McKay and Radziszowski to 53, 52 and 50 between 1992 and 1995 [3]. The step to 50 followed from their proof that R(4, 5) = 25 [3, 5]. In a (5, 5)-graph, the neighbours of any vertex form a graph with no four mutually joined and no five mutually unjoined vertices, a (4, 5)-graph, so in a (5, 5)-graph on m vertices every vertex has between m − 25 and 24 neighbours [5]. In 1997 McKay and Radziszowski used identities that count small subgraphs in the neighbourhoods of all vertices to reach R(5, 5) ≤ 49 [3, 5].

The conjecture (1997). McKay and Radziszowski, "together with Geoff Exoo", conjectured that R(5, 5) = 43, and further, "with Geoff's dissent", that there are exactly 656 (5, 5)-graphs on 42 vertices [3]. Several independent searches found only these graphs [3]. Exoo's simulated-annealing program built 5,812 of them, finding each of the 656 at least once and no new one; in one search around the known graphs, extending 100 random 36-vertex subgraphs in all possible ways gave over 65 million (5, 5)-graphs on 42 vertices, all isomorphic to known ones [3]. None of the 656 extends to 43 vertices [3]. The authors add that it is not possible to put their belief "on a quantitative level" [3]. In unpublished work from 2014, reported in 2017, Lieby and McKay showed that any other (5, 5)-graph on 42 vertices shares no 37-vertex subgraph with any of the 656 [4].

Upper bounds since 2017. Angeltveit and McKay lowered the bound to 48 in a paper posted in 2017 and published in 2018 [4]. They first completed the list of (4, 5)-graphs on 24 vertices, 352,366 in all, then checked about two trillion cases with two independently written programs [4]. In a preprint posted in September 2024 and published in the Journal of Graph Theory in 2026, they proved R(5, 5) ≤ 46 [5]. The proof combines linear programming, used to reduce the number of neighbourhood graphs that must be considered, with computer checks of the remaining ways to join the neighbourhoods of two adjacent vertices [5]. The first author's computation took about 30 years of processor time; the second author repeated it with independent programs and mostly different methods, using about 50 years more [5]. The authors conclude that "future improvements to the upper bound on R(5, 5) will need new theoretical insights" [5].

Main approaches

Exhaustive gluing with linear programming. Rule out (5, 5)-graphs on n vertices by listing the possible neighbourhoods of two adjacent vertices and showing that no way of joining them extends [4, 5]. Strongest evidence: the method lowered the upper bound from 49 to 48 and then to 46, each time with two independent implementations [4, 5]. Main difficulty: the authors estimate about 2.93 × 10¹⁹ (4, 5)-graphs in all, so an approach that relies on complete lists of those on 21 to 23 vertices is impractical, and they expect further progress to need new theory rather than more computer time [5].

Heuristic search for a larger graph. Raise the lower bound by searching for a (5, 5)-graph on 43 vertices with simulated annealing, tabu search or algebraic constructions [3]. Strongest evidence: simulated annealing found Exoo's 1989 graph [3]. A 2026 preprint by researchers at Google DeepMind, Google and the University of California, Berkeley used AlphaEvolve, in which a large language model rewrites search programs, to raise nine other Ramsey lower bounds and match all known exact values; its results table has no entry for R(5, 5) [10]. Main difficulty: the searches reported in 1997 rediscovered only the 656 known 42-vertex graphs [3], and the 2026 survey still gives 43 as the lower bound [6].

Completing the 42-vertex classification. Prove that the 656 known graphs are all the (5, 5)-graphs on 42 vertices; since none of them extends, this would give R(5, 5) = 43 [3]. Strongest evidence: the repeated rediscovery of the same graphs [3], and the 2014 result that any missing graph shares no 37-vertex subgraph with the known ones [4]. Main difficulty: the evidence is heuristic, Exoo did not share the conjecture on the count [3], and the 2026 survey still presents it as a conjecture [6].

SAT solving and checkable proofs. Encode the remaining cases as Boolean satisfiability (SAT) problems and, where possible, produce proofs that independent software can check [5, 9]. Strongest evidence: the proof of the 46 bound already hands its gluing problems to SAT solvers [5]; SAT combined with computer algebra gave the first independently verifiable certificates for R(3, 8) = 28 and R(3, 9) = 36 [6, 9], and R(4, 5) = 25 has been proved in the HOL4 theorem prover, which limits the uncertainty to HOL4's small kernel [8]. Main difficulty: scale. The certified computation for R(3, 8) took 59 hours on one processor [9], while one implementation of the 46 bound took about 30 years of processor time [5].

Open sub-questions

  1. The 656 graphs. Can the 2014 result that any further (5, 5)-graph on 42 vertices shares no 37-vertex subgraph with the 656 known ones be pushed to 36 or fewer shared vertices, and how fast does the cost grow [3, 4]?
  2. Towards 45. In a (5, 5)-graph on 45 vertices every vertex has 20 to 24 neighbours [5]. Which further counting identities or linear constraints would avoid listing the very large sets of (4, 5)-graphs on 20 to 23 vertices [3, 5]?
  3. Certificates for 46. Can the gluing cases behind R(5, 5) ≤ 46 be re-run with solvers that emit checkable proofs, as for R(3, 8) and R(3, 9), and how large would the proofs be [5, 9]?
  4. A formal proof of 48. Does the HOL4 method used for R(4, 5) = 25 scale to the roughly two trillion cases behind R(5, 5) ≤ 48 [4, 8]?
  5. A benchmark for search. McKay and Radziszowski proposed building 42-vertex (5, 5)-graphs as "a challenging benchmark for heuristic search methods" [3]. How many of the 656 does an LLM-guided program search of the 2026 kind find, and how evenly [3, 10]?

Work on this in Papex

If you have a testable answer to one of the sub-questions above, you can draft it as a private hypothesis in Papex, or prepare the draft from Claude or ChatGPT with the Papex connector. You review the exact version, sign it and decide whether to publish it; a public record that names this problem is listed on this page. A Papex record shows who signed which version and when. It is not peer review and does not mean the hypothesis is correct.

Key references

  1. Greenwood, R. E. & Gleason, A. M. (1955). Combinatorial relations and chromatic graphs. Canadian Journal of Mathematics 7, 1–7. 10.4153/CJM-1955-001-4 · Checked 15 Oct 2026
  2. Exoo, G. (1989). A lower bound for R(5, 5). Journal of Graph Theory 13(1), 97–98. 10.1002/jgt.3190130113 · Checked 15 Oct 2026
  3. McKay, B. D. & Radziszowski, S. P. (1997). Subgraph counting identities and Ramsey numbers. Journal of Combinatorial Theory, Series B 69(2), 193–209. 10.1006/jctb.1996.1741 · Checked 15 Oct 2026
  4. Angeltveit, V. & McKay, B. D. (2018). R(5, 5) ≤ 48. Journal of Graph Theory 89(1), 5–13. 10.1002/jgt.22235 · Checked 15 Oct 2026
  5. Angeltveit, V. & McKay, B. D. (2026). R(5, 5) ≤ 46. Journal of Graph Theory 112(3), 198–208 (published online 20 March 2026). 10.1002/jgt.70029 · Checked 15 Oct 2026
  6. Radziszowski, S. P. (2026). Small Ramsey numbers. The Electronic Journal of Combinatorics, Dynamic Survey DS1, revision 18, 24 April 2026. 10.37236/21 · Checked 15 Oct 2026
  7. Ge, L., Jayasooriya, Y., Qiu, A., Sun, M. & Yuan, V. (2022). Study of Exoo's lower bound for Ramsey number R(5, 5). Preprint, arXiv:2212.12630 (version 3, 25 March 2023), not peer reviewed. Source · Checked 15 Oct 2026
  8. Gauthier, T. & Brown, C. E. (2024). A formal proof of R(4, 5) = 25. In 15th International Conference on Interactive Theorem Proving (ITP 2024), Leibniz International Proceedings in Informatics 309, 16:1–16:18. Source · Checked 15 Oct 2026
  9. Li, Z., Duggan, C., Bright, C. & Ganesh, V. (2025). Verified certificates via SAT and computer algebra systems for the Ramsey R(3, 8) and R(3, 9) problems. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2025), 2619–2627. 10.24963/ijcai.2025/292 · Checked 15 Oct 2026
  10. Nagda, A., Raghavan, P. & Thakurta, A. (2026). Reinforced generation of combinatorial structures: Ramsey numbers. Preprint, arXiv:2603.09172 (version 5, 21 April 2026), not peer reviewed. Source · Checked 15 Oct 2026

Page reviewed 15 Oct 2026

Source

Open, as listed by Wikipedia · Unsolved problems in mathematics. Checked 08 Oct 2026.

The status is the source’s. Papex does not decide whether a problem is solved.

Records on this problem

No public record addresses this problem yet.

More in Mathematics