Four-cycles one edge above the extremal threshold

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

Let h(n)h(n) be the minimum number of four-cycles in an nn-vertex graph with ex⁡(n,C4)+1\operatorname{ex}(n,C_4)+1 edges. We prove that h(nj)=o(nj)h(n_j)=o(\sqrt{n_j}) for a sequence nj=qj2+qj+2n_j=q_j^2+q_j+2, where the qjq_j are powers of four tending to infinity. Consequently, no positive constant gives a universal square-root lower bound one edge above the extremal number. The proof combines a polarity-graph construction with a structural analysis of extremal graphs. Signed deficiencies and a secondary degree-and-triangle minimization produce an open packing of size qq. Completing its adjacency matrix reduces the argument to a trace inequality for a symmetric binary matrix whose residual graph is a union of cycles.

Author comments: Manuscript accompanying Justin Sun Prize submission JSP-000079. Pinned source and Lean proof materials: https://github.com/Ghuffy1/erdos60-jsp-submission/tree/62aa60b23089cbd4729f1fc4cc850620228c9038

Provenance statement

OpenAI AI systems assisted with developing and checking intermediate arguments and with the exposition. The linked formal verification covers the exact challenge result.

References

  1. W. G. Brown, On graphs that do not contain a Thomsen graph , Canad. Math. Bull. 9 (1966), 281--285. doi:10.4153/CMB-1966-036-2 (https://doi.org/10.4153/CMB-1966-036-2).DOI
  2. P. Erdős, A. Rényi, and V. T. Sós, On a problem of graph theory , Studia Sci. Math. Hungar. 1 (1966), 215--235.
  3. P. Erdős and M. Simonovits, Cube-supersaturated graphs and related problems , in Progress in Graph Theory , Academic Press, 1984, 203--218.
  4. Z. Füredi, On the number of edges of quadrilateral-free graphs , J. Combin. Theory Ser. B 68 (1996), 1--6. doi:10.1006/jctb.1996.0052 (https://doi.org/10.1006/jctb.1996.0052).DOI
  5. J. He, J. Ma, and T. Yang, Stability and supersaturation of 44-cycles , preprint, first version, 2019. :1912.00986v1 (https://arxiv.org/abs/1912.00986v1).link
  6. J. He, J. Ma, and T. Yang, Some exact results on 44-cycles: stability and supersaturation , CSIAM Trans. Appl. Math. 4 (2023), no. 1, 74--128. doi:10.4208/csiam-am.SO-2021-0006 (https://doi.org/10.4208/csiam-am.SO-2021-0006).DOI
  7. B. Ning and M. Zhai, Counting substructures and eigenvalues II: quadrilaterals , preprint, first version, 2021. arXiv:2112.15279v1 (https://arxiv.org/abs/2112.15279v1).arXiv

Version history

  1. v1 · 15 pagesSubmitted by Liam KruerManuscript accompanying Justin Sun Prize submission JSP-000079. Pinned source and Lean proof materials: https://github.com/Ghuffy1/erdos60-jsp-submission/tree/62aa60b23089cbd4729f1fc4cc850620228c9038CurrentNov 20, 2026