HEXAGONbeta

An exact computer-assisted certificate for R(5,6)≤84

Primarily AI-generated textHuman understanding: some partsmath.CO — Combinatoricsmath.AP — Analysis of PDEs

Contributed by Dr. András Pongrácz ↗

Version 1 / Oct 31, 2026 / CC BY 4.0

Abstract

We give an exact computer-assisted proof of R(5,6)≤84. We derive a system of linear inequalities that must be satisfied by any graph on 84 vertices containing neither a five-vertex clique nor a six-vertex independent set. We provide explicit nonnegative rational weights for which adding these inequalities yields a contradiction. Published small Ramsey bounds and complete catalogues of smaller Ramsey graphs supply the external inputs. The accompanying verification programs check the derivation of the inequalities and their weighted sum using exact arithmetic. Two supplements give a worked local calculation and a detailed mathematical specification of the complete proof.

Provenance statement

AI assistance was used in developing the computational argument, verification programs, and exposition. I have revised the notation and explanations and have reviewed parts of the mathematical argument. The computational certificates have been checked by the supplied exact-arithmetic verification programs. Human review of the complete argument is ongoing.

Tools used

OpenAI
ChatGPTVersion GPT-6 Astra

References

  1. S. P. Radziszowski, Small Ramsey Numbers , Electronic Journal of Combinatorics, Dynamic Survey DS1, revision 18, 24 April 2026, especially Table Ib, p. 7. https://doi.org/10.37236/21; https://www.cs.rit.edu/~spr/ElJC/ejcram18.pdfDOI
  2. V. Angeltveit and B. D. McKay, R(5,5)≤46R(5,5)\leq46 , Journal of Graph Theory 112 (2026), 198--208. Theorem 1.1; Appendix A, Table 1. https://doi.org/10.1002/jgt.70029; https://arxiv.org/html/2409.15709v2DOI
  3. B. D. McKay and S. P. Radziszowski, Subgraph counting identities and Ramsey numbers , J. Combinatorial Theory, Ser. B 69 (1997), 193--209. https://users.cecs.anu.edu.au/~bdm/papers/r55.pdflink
  4. B. D. McKay, Ramsey Graphs , complete graph catalogues. https://users.cecs.anu.edu.au/~bdm/data/ramsey.htmllink
  5. V. Angeltveit and B. D. McKay, R(5,5)≤48R(5,5)\leq48 . Journal of Graph Theory 89 (2018), 5--13. https://arxiv.org/abs/1703.08768link
  6. J. Goedgebeur and S. P. Radziszowski, New Computational Upper Bounds for Ramsey Numbers R(3,k)R(3,k) , Electronic Journal of Combinatorics 20 (1) (2013), P30. Theorem 2. https://doi.org/10.37236/2824.DOI
  7. Electronic supplement to the present paper: exact local Ramsey-profile certificates (2026). Mathematical description and provenance: LOCAL_CERTIFICATES.txt . Counting model: recursive_profiles_v4.py . Certificate index: edge_certification_summary.json . Independent verifier: replay_required_local_certificates.py .
  8. B. D. McKay and S. P. Radziszowski, Subgraph counting identities and Ramsey numbers , Journal of Combinatorial Theory, Series B 69 (1997), 193--209. https://users.cecs.anu.edu.au/~bdm/papers/r55.pdflink
  9. S. P. Radziszowski, Small Ramsey Numbers , Electronic Journal of Combinatorics, Dynamic Survey DS1, revision 18, 24 April 2026, Table Ib. https://www.cs.rit.edu/~spr/ElJC/ejcram18.pdflink
  10. B. D. McKay and S. P. Radziszowski, Subgraph counting identities and Ramsey numbers , Journal of Combinatorial Theory, Series B 69 (1997), 193--209. https://users.cecs.anu.edu.au/~bdm/papers/r55.pdf.link
Show all 12 referencesShow fewer references
  1. B. D. McKay, Ramsey Graphs , catalogue collection and descriptions. https://users.cecs.anu.edu.au/~bdm/data/ramsey.html.link
  2. Electronic verification supplement to the accompanying manuscript (2026). Local mathematical input is documented in LOCAL_CERTIFICATES.txt ; the 18-job verification driver is verify_all.py ; the packaged launcher is verify_package.py ; the final weighted sum is exact_separation_certificate.json . The package README specifies installation and the archived layout.

Version history

  1. v1Submitted by Dr. András PongráczInitial depositCurrentOct 30, 2026