A locally sparse graph with superlinear Ramsey growth
Version 1 / Nov 21, 2026 / CC BY 4.0
Abstract
We construct a fixed finite bipartite graph such that every set of at least two vertices spans at most twice its cardinality minus three edges, while the ratio is unbounded as ranges over graphs without isolated vertices. For all sufficiently large , . This gives a negative answer to Erdős problem 566. The construction uses a layered two-parent graph and a random subset of a Hamming cube. A conditional-entropy inequality excludes the fixed graph. A bound on the negative Krawtchouk spectrum and an independent-set encoding exclude large independent sets.
Provenance statement
References
- J. Balogh, A. Treglown, and A. Z. Wagner, Applications of graph containers in the Boolean lattice , Random Structures Algorithms 49 (2016), no. 4, 845--872. doi:10.1002/rsa.20666 (https://doi.org/10.1002/rsa.20666).DOI
- T. F. Bloom, Erdős problems, Problem 566 , https://www.erdosproblems.com/566, accessed November 11, 2026.link
- P. Erdős, R. J. Faudree, C. C. Rousseau, and R. H. Schelp, Ramsey size linear graphs , Combin. Probab. Comput. 2 (1993), no. 4, 389--399. doi:10.1017/S096354830000078X (https://doi.org/10.1017/S096354830000078X).DOI
- OpenAI, Ten advances in mathematics and theoretical computer science , preprint, updated August 6, 2026, Chapter 10, pp. 236--248. https://cdn.openai.com/pdf/ten-proofs-oai.pdf.link
Version history
- v1 · 12 pagesSubmitted by Liam KruerManuscript accompanying Justin Sun Prize submission JSP-000456. Pinned source and Lean verification materials: https://github.com/Ghuffy1/erdos-566/tree/ac0b12b5cb264a092ef1cdf6304760dcdc4b6328CurrentNov 21, 2026