Size Ramsey numbers at high average degree
Version 1 / Nov 21, 2026 / CC BY 4.0
Abstract
We prove that there is a function with such that every finite simple graph of positive order with satisfies for all sufficiently large . 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.
Provenance statement
References
- 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
- 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
- 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
- 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.
- 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
- 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.
- Erdős Problem a Day, Erdős problem 911: working report , July 27, 2026, accessed November 5, 2026. https://erdosproblemaday.com/report/911.link
- D. Gavinsky, S. Lovett, M. Saks and S. Srinivasan, A tail bound for read- families of functions , Random Structures Algorithms 47 (2015), 99--108. arXiv:1205.1478 (https://arxiv.org/abs/1205.1478).arXiv
- C. Karoubi, Erdős problem 911: public working notes , contribution to the GPT-Erdos project, January 19, 2026.
- 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
- 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