Four-cycles one edge above the extremal threshold
Version 1 / Nov 21, 2026 / CC BY 4.0
Abstract
Let be the minimum number of four-cycles in an -vertex graph with edges. We prove that for a sequence , where the 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 . Completing its adjacency matrix reduces the argument to a trace inequality for a symmetric binary matrix whose residual graph is a union of cycles.
Provenance statement
References
- 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
- 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.
- P. Erdős and M. Simonovits, Cube-supersaturated graphs and related problems , in Progress in Graph Theory , Academic Press, 1984, 203--218.
- 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
- J. He, J. Ma, and T. Yang, Stability and supersaturation of -cycles , preprint, first version, 2019. :1912.00986v1 (https://arxiv.org/abs/1912.00986v1).link
- J. He, J. Ma, and T. Yang, Some exact results on -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
- 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
- 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