Size Ramsey numbers at high average degree

Primarily AI-generated textHuman understanding: no partsmath.CO — Combinatorics

Contributed by Will Howe, Grant Huffman, Jensen Kohlmeyer, Liam Kruer ↗

Version 1 / Nov 21, 2026 / CC BY 4.0

Abstract

We prove that there is a function ff with f(C)/C→∞f(C)/C\to\infty such that every finite simple graph GG of positive order with e(G)≥Cv(G)e(G)\ge C v(G) satisfies R^(G)>f(C)e(G)\widehat{R}(G)>f(C)e(G) for all sufficiently large CC. The estimate is uniform in the order, number of components, and component multiplicities of the target. The proof combines an entropy estimate for connected component types with adaptive sampling and sparse marks on intersections of host neighborhoods. Separate arguments handle targets with a narrow degree range and strongly unbalanced incidence targets. Dyadic degree reductions assemble the estimates without a loss depending on the number of degree scales.

Author comments: Manuscript accompanying Justin Sun Prize submission JSP-000756. Pinned manuscript, formal source, and verification records are listed at https://github.com/TheJustinSunPrize/awards/pull/5536

Provenance statement

The manuscript discloses assistance from OpenAI ChatGPT and Codex. The linked repository records the complete Lean target, a successful exact-revision build and a fresh kernel check.

References

  1. D. Conlon, J. Fox and Y. Wigderson, Three early problems on size Ramsey numbers , Combinatorica 43 (2023), 743--768. doi:10.1007/s00493-023-00034-7 (https://doi.org/10.1007/s00493-023-00034-7).DOI
  2. L. DeBiasio, A note on the multicolor size-Ramsey numbers of connected graphs , arXiv:2404.05856v3, 2026. Version of April 8, 2026 (https://arxiv.org/abs/2404.05856v3).arXiv
  3. P. Erdős, Some of my favourite problems which recently have been solved , in Proceedings of the International Mathematical Conference, Singapore, 1981, North-Holland Mathematics Studies 74 , North-Holland, Amsterdam, 1982, 59--79. doi:10.1016/S0304-0208(08)70415-8 (https://doi.org/10.1016/S0304-0208(08)70415-8).DOI
  4. P. Erdős and R. J. Faudree, Size Ramsey functions , in Sets, Graphs and Numbers (Budapest, 1991), Colloq. Math. Soc. János Bolyai 60 , North-Holland, Amsterdam, 1992, 219--238.
  5. P. Erdős, R. J. Faudree, C. C. Rousseau and R. H. Schelp, The size Ramsey number , Period. Math. Hungar. 9 (1978), 145--161. doi:10.1007/BF02018930 (https://doi.org/10.1007/BF02018930).DOI
  6. P. Erdős and L. Lovász, Problems and results on 3-chromatic hypergraphs and some related questions , in Infinite and Finite Sets, Vol. II, Colloq. Math. Soc. János Bolyai 10 , North-Holland, Amsterdam, 1975, 609--627.
  7. Erdős Problem a Day, Erdős problem 911: working report , July 27, 2026, accessed November 5, 2026. https://erdosproblemaday.com/report/911.link
  8. D. Gavinsky, S. Lovett, M. Saks and S. Srinivasan, A tail bound for read-kk families of functions , Random Structures Algorithms 47 (2015), 99--108. arXiv:1205.1478 (https://arxiv.org/abs/1205.1478).arXiv
  9. C. Karoubi, Erdős problem 911: public working notes , contribution to the GPT-Erdos project, January 19, 2026.
  10. O. Pikhurko, Asymptotic size Ramsey results for bipartite graphs , SIAM J. Discrete Math. 16 (2002), 99--113. doi:10.1137/S0895480101384086 (https://doi.org/10.1137/S0895480101384086).DOI

Version history

  1. v1 · 27 pagesSubmitted by Liam KruerManuscript accompanying Justin Sun Prize submission JSP-000756. Pinned manuscript, formal source, and verification records are listed at https://github.com/TheJustinSunPrize/awards/pull/5536CurrentNov 21, 2026