A locally sparse graph with superlinear Ramsey growth

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 construct a fixed finite bipartite graph GG such that every set of at least two vertices spans at most twice its cardinality minus three edges, while the ratio R(G,H)/e(H)R(G,H)/e(H) is unbounded as HH ranges over graphs without isolated vertices. For all sufficiently large mm, R(G,K2570m)>21144m−1R(G,K_{2^{570m}})>2^{1144m-1}. 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.

Author comments: Manuscript accompanying Justin Sun Prize submission JSP-000456. Pinned source and Lean verification materials: https://github.com/Ghuffy1/erdos-566/tree/ac0b12b5cb264a092ef1cdf6304760dcdc4b6328

Provenance statement

The manuscript acknowledges OpenAI ChatGPT assistance in development, checking and exposition. The linked verification records a successful formal target audit and fresh Lean kernel replay.

References

  1. 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
  2. T. F. Bloom, Erdős problems, Problem 566 , https://www.erdosproblems.com/566, accessed November 11, 2026.link
  3. 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
  4. 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

  1. 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