Some Exact Results on 4-Cycles: Stability and Supersaturation

Abstract

Extremal problems on the 4 -cycle C₄ played a heuristic important role in the development of extremal graph theory. A fundamental theorem of Füredi states that the Turán number $\mathrm{e}\mathrm{x}\left({q}^{2}+q+1,{C}_{4}\right)\le (1/2)q(q+1{)}^{2}$ holds for every $q\ge 14$, which matches with the classic construction of Erdős-Rényi-Sós and Brown from finite geometry for prime powers q. Very recently, we obtained the first stability result on Füredi's theorem, by showing that for large even q, every (q²+q+1)-vertex C₄-free graph with more than (1/2)q(q+1)²-0.2q edges must be a spanning subgraph of a unique polarity graph [20]. Using new technical ideas in graph theory and finite geometry, we strengthen this by showing that the same conclusion remains true if the number of edges is lowered to (1/2)q(q+1)²-(1/2)q+o(q). Among other applications, this gives an immediate improvement on the upper bound of ex (n,C₄) for infinite many integers n. A longstanding conjecture of Erdős and Simonovits states that every n-vertex graph with ex (n,C₄)+1 edges contains at least $(1+o(1\left)\right)\sqrt{n}4$-cycles. We proved an exact result and confirmed Erdős-Simonovits conjecture for infinitely many integers n [20]. As the second main result of this paper, we further characterize all extremal graphs for which achieve the $\mathcal{l}$-th least number of copies of C₄ for any fixed positive integer $\mathcal{l}$. This can be extended to more general settings and provides enhancements on the understanding of the supersaturation problem of C₄.

Keywords

Extremal graph theory / 4-cycles / stability / supersaturation / projective plane

References

[1] R. Baer, Null systems in projective space, Bull. Amer. Math. Soc., 51:903-906, 1945.

[2] R. Baer, Polarities in finite projective planes, Bull. Amer. Math. Soc., 52:77-93, 1946.

[3] R. C. Baker, G. Harman, and J. Pintz, The difference between consecutive primes II, Proc. Lond. Math. Soc., 83(3):532-562, 2001.

[4] W. G. Brown, On graphs that do not contain a Thomsen graph, Canad. Math. Bull., 9:281-285, 1966.

[5] R. H. Bruck and H. J. Ryser, The non-existence of certain finite projective planes, Canad. J. Math., 1:88-93, 1949.

[6] F. Chung, Open problems of Paul Erdős in graph theory, J. Graph Theory, 25:3-36, 1997.

[7] S. Dow, An improved bound for extending partial projective planes, Discrete Math., 45:199-207, 1983.

[8] P. Erdős, On sequences of integers no one of which divides the product of two others and some related problems, Izvestiya Nautshno-Issl. Inst. Mat. i Meh. Tomsk, 2:74-82, 1938.

[9] P. Erdős,Extremal problems on graphs and hypergraphs, in:Hypergraph Seminar (Proc. First Working Sem., Ohio State Univ., 1972), Lecture Notes in Math., 411: 75-84, 1974.

[10] P. Erdős, Problems and results in combinatorial analysis and graph theory, Discrete Math., 72:8192, 1988.

[11] P. Erdős, Some of my favourite unsolved problems, in: A Tribute to Paul Erdős, Cambridge University Press, 467-478, 1990.

[12] P. Erdős, A. Rényi, and V. T. Sós, On a problem of graph theory, Studia Sci. Math. Hungar., 1:215-235, 1966.

[13] P. Erdős and M. Simonovits, Cube-supersaturated graphs and related problems, in: Progress in Graph Theory ( 1982), Academic Press, 203-218, 1984.

[14] F. A. Firke, P. M. Kosek, E. D. Nash and J. Williford, Extremal graphs without 4-cycles, J. Combin. Theory Ser. B, 103:327-336, 2013.

[15] Z. Füredi, Graphs without quadrilaterals, J. Combin. Theory Ser. B, 34:187-190, 1983.

[16] Z. Füredi, Quadrilateral-free graphs with maximum number of edges, preprint 1988, http://www.math.uiuc.edu/^-z-furedi/PUBS/furedi_C4from1988.pdf

[17] Z. Füredi,On the number of edges of quadrilateral-free graphs, J. Combin. Theory Ser. B, 68:1-6, 1996.

[18] Z. Füredi, Extremal quadrilater-free graphs, in: Lecture at the 1st Canadian Discrete and Algorithmic Mathematics Conference ( CanaDAM 2007), 2007.

[19] Z. Füredi and M. The history of degenerate (bipartite) extremal graph problems, in: Erdős centennial, Bolyai Soc. Math. Stud., 25:169-264, 2013.

[20] J. He, J. Ma, and T. Yang, Some extremal results on 4-cycles, J. Combin. Theory Ser. B, 149:92108, 2021.

[21] K. Metsch, Linear Spaces with Few Lines, Springer Lecture Notes in Math., 1991.

[22] K. Metsch, On the maximum size of a maximal partial plane, Rend. Mat. Appl. (7), 12:345-355, 1992.

[23] Z. Nagy, Supersaturation of C₄ : From Zarankiewicz towards Erdős-Simonovits-Sidorenko, European J. Combin., 75:19-31, 2019.

[24] I. Reiman, Über ein Problem von K. Zarankiewicz, Acta Math. Acad. Sci. Hungar., 9:269-273, 1958.