HEXAGONbeta

Four-cycle supersaturation and polarity stability at q2+qq^2+q vertices

A mix of human-written and AI-generated textHuman understanding: some partsmath.CO — Combinatorics

Contributed by Zhenyu Sun ↗

Version 1 / Nov 07, 2026 / CC BY 4.0

Abstract

Let m0=12q(q+1)2−qm_0=\frac12q(q+1)^2-q. For every even q≥1600q\ge1600, we prove that a graph on q2+qq^2+q vertices with at least m0+1m_0+1 edges contains at least ⌈(q−1)/12⌉\lceil(q-1)/12\rceil four-cycles. For powers of two in this range, m0m_0 is the extremal number and a polarity construction has exactly q−1q-1 four-cycles at m0+1m_0+1 edges. These bounds determine the order of magnitude of the minimum count on this sequence. We also prove a stability theorem: for every nonnegative integer bb and every even q≥1018(b+1)16q\ge10^{18}(b+1)^{16}, each C4C_4-free graph on q2+qq^2+q vertices with m0−bm_0-b edges is a spanning subgraph of an orthogonal polarity graph with one point deleted. The required degree bounds follow from the edge count. As a consequence, a graph on q2+qq^2+q vertices with m0+1m_0+1 edges has at least q−1q-1 four-cycles if an edge set of size t≥1t\ge1 meets every four-cycle and qq is even with q≥1018t16q\ge10^{18}t^{16}. The counting proof uses a codegree commutator; the stability proof combines degree-deficit concentration with incidence completion and polarity extension.

Author comments: 64 pages.

Provenance statement

The manuscript was revised using OpenAI Codex for mathematical and citation review, editorial refinement, and LaTeX checks. Python scripts were used for finite computations and exact polynomial checks. No formal proof-assistant verification is claimed.

References

  1. A. Beutelspacher. Linear spaces: history and theory. Le Matematiche , 45(1):25--38, 1990. Theorem 2.2.1. Published article (https://lematematiche.dmi.unict.it/index.php/lematematiche/article/download/657/625).link
  2. A. Beutelspacher and K. Metsch. Embedding finite linear spaces in projective planes, II . Discrete Mathematics , 66(3):219--230, 1987. doi:10.1016/0012-365X(87)90098-7 (https://doi.org/10.1016/0012-365X(87)90098-7).DOI
  3. A. A. Bruen. Baer subplanes and blocking sets. Bulletin of the American Mathematical Society , 76:342--344, 1970. doi:10.1090/S0002-9904-1970-12470-3 (https://doi.org/10.1090/S0002-9904-1970-12470-3).DOI
  4. P. Erd ő s and M. Simonovits. Supersaturated graphs and hypergraphs. Combinatorica , 3(2):181--192, 1983. doi:10.1007/BF02579292 (https://doi.org/10.1007/BF02579292).DOI
  5. P. Erd ő s and M. Simonovits. Cube-supersaturated graphs and related problems. In Progress in Graph Theory (Waterloo, Ont., 1982) , pages 203--218. Academic Press, Toronto, ON, 1984. Published chapter (https://users.renyi.hu/~p_erdos/1984-04.pdf).link
  6. F. A. Firke, P. M. Kosek, E. D. Nash, and J. Williford. Extremal graphs without 4-cycles. Journal of Combinatorial Theory, Series B , 103(3):327--336, 2013. doi:10.1016/j.jctb.2013.01.001 (https://doi.org/10.1016/j.jctb.2013.01.001).DOI
  7. Z. F ü redi. Graphs without quadrilaterals. Journal of Combinatorial Theory, Series B , 34(2):187--190, 1983. doi:10.1016/0095-8956(83)90018-7 (https://doi.org/10.1016/0095-8956(83)90018-7).DOI
  8. J. He, J. Ma, and T. Yang. Some extremal results on 4-cycles. Journal of Combinatorial Theory, Series B , 149:92--108, 2021. doi:10.1016/j.jctb.2021.01.007 (https://doi.org/10.1016/j.jctb.2021.01.007).DOI
  9. J. He, J. Ma, and T. Yang. Some exact results on 4-cycles: stability and supersaturation. CSIAM Transactions on Applied Mathematics , 4(1):74--128, 2023. doi:10.4208/csiam-am.SO-2021-0006 (https://doi.org/10.4208/csiam-am.SO-2021-0006).DOI
  10. B. Kivva. On the spectral gap and the automorphism group of distance-regular graphs. Journal of Combinatorial Theory, Series B , 149:161--197, 2021. Theorem 2.7. Published version (https://math.uchicago.edu/~bkivva/files/articles/drg-spectral-gap.pdf).link
Show all 12 referencesShow fewer references
  1. J. Ma and T. Yang. Upper bounds on the extremal number of the 4-cycle. Bulletin of the London Mathematical Society , 55(4):1655--1667, 2023. doi:10.1112/blms.12810 (https://doi.org/10.1112/blms.12810).DOI
  2. K. Metsch. A characterization of Grassmann graphs. European Journal of Combinatorics , 16(6):639--644, 1995. Result 2.2. doi:10.1016/0195-6698(95)90045-4 (https://doi.org/10.1016/0195-6698(95)90045-4).DOI

Version history

  1. v1 · 64 pagesSubmitted by Zhenyu Sun64 pages.CurrentNov 07, 2026