Volume 4, Issue 1
Some Exact Results on 4-Cycles: Stability and Supersaturation

Jialin He, Jie Ma & Tianchi Yang

CSIAM Trans. Appl. Math., 4 (2023), pp. 74-128.

Published online: 2023-01

Export citation
  • Abstract

Extremal problems on the 4-cycle $C_4$ played a heuristic important role in the development of extremal graph theory. A fundamental theorem of Füredi states that the Turán number ${\rm ex}(q^2+q+1,C_4)≤(1/2)q(q+1)^2$ holds for every $q≥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^2+q+1)$-vertex $C_4$-free graph with more than $(1/2)q(q+1)^2−0.2q$ edges must be a spanning subgraph of a unique polarity graph. 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)^2−(1/2)q+o(q).$ Among other applications, this gives an immediate improvement on the upper bound of ${\rm ex}(n,C_4)$ for infinite many integers $n.$ A longstanding conjecture of Erdös and Simonovits states that every $n$-vertex graph with ${\rm ex}(n,C_4)+1$ edges contains at least $(1+o(1))\sqrt{n}$ 4-cycles. We proved an exact result and confirmed Erdös-Simonovits conjecture for infinitely many integers $n$. As the second main result of this paper, we further characterize all extremal graphs for which achieve the $ℓ$-th least number of copies of $C_4$ for any fixed positive integer $ℓ.$ This can be extended to more general settings and provides enhancements on the understanding of the supersaturation problem of $C_4.$

  • AMS Subject Headings

05C35, 05C75, 51A45, 51E15

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address
  • BibTex
  • RIS
  • TXT
@Article{CSIAM-AM-4-74, author = {He , JialinMa , Jie and Yang , Tianchi}, title = {Some Exact Results on 4-Cycles: Stability and Supersaturation}, journal = {CSIAM Transactions on Applied Mathematics}, year = {2023}, volume = {4}, number = {1}, pages = {74--128}, abstract = {

Extremal problems on the 4-cycle $C_4$ played a heuristic important role in the development of extremal graph theory. A fundamental theorem of Füredi states that the Turán number ${\rm ex}(q^2+q+1,C_4)≤(1/2)q(q+1)^2$ holds for every $q≥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^2+q+1)$-vertex $C_4$-free graph with more than $(1/2)q(q+1)^2−0.2q$ edges must be a spanning subgraph of a unique polarity graph. 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)^2−(1/2)q+o(q).$ Among other applications, this gives an immediate improvement on the upper bound of ${\rm ex}(n,C_4)$ for infinite many integers $n.$ A longstanding conjecture of Erdös and Simonovits states that every $n$-vertex graph with ${\rm ex}(n,C_4)+1$ edges contains at least $(1+o(1))\sqrt{n}$ 4-cycles. We proved an exact result and confirmed Erdös-Simonovits conjecture for infinitely many integers $n$. As the second main result of this paper, we further characterize all extremal graphs for which achieve the $ℓ$-th least number of copies of $C_4$ for any fixed positive integer $ℓ.$ This can be extended to more general settings and provides enhancements on the understanding of the supersaturation problem of $C_4.$

}, issn = {2708-0579}, doi = {https://doi.org/10.4208/csiam-am.SO-2021-0006}, url = {http://global-sci.org/intro/article_detail/csiam-am/21336.html} }
TY - JOUR T1 - Some Exact Results on 4-Cycles: Stability and Supersaturation AU - He , Jialin AU - Ma , Jie AU - Yang , Tianchi JO - CSIAM Transactions on Applied Mathematics VL - 1 SP - 74 EP - 128 PY - 2023 DA - 2023/01 SN - 4 DO - http://doi.org/10.4208/csiam-am.SO-2021-0006 UR - https://global-sci.org/intro/article_detail/csiam-am/21336.html KW - Extremal graph theory, 4-cycles, stability, supersaturation, projective plane. AB -

Extremal problems on the 4-cycle $C_4$ played a heuristic important role in the development of extremal graph theory. A fundamental theorem of Füredi states that the Turán number ${\rm ex}(q^2+q+1,C_4)≤(1/2)q(q+1)^2$ holds for every $q≥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^2+q+1)$-vertex $C_4$-free graph with more than $(1/2)q(q+1)^2−0.2q$ edges must be a spanning subgraph of a unique polarity graph. 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)^2−(1/2)q+o(q).$ Among other applications, this gives an immediate improvement on the upper bound of ${\rm ex}(n,C_4)$ for infinite many integers $n.$ A longstanding conjecture of Erdös and Simonovits states that every $n$-vertex graph with ${\rm ex}(n,C_4)+1$ edges contains at least $(1+o(1))\sqrt{n}$ 4-cycles. We proved an exact result and confirmed Erdös-Simonovits conjecture for infinitely many integers $n$. As the second main result of this paper, we further characterize all extremal graphs for which achieve the $ℓ$-th least number of copies of $C_4$ for any fixed positive integer $ℓ.$ This can be extended to more general settings and provides enhancements on the understanding of the supersaturation problem of $C_4.$

He , JialinMa , Jie and Yang , Tianchi. (2023). Some Exact Results on 4-Cycles: Stability and Supersaturation. CSIAM Transactions on Applied Mathematics. 4 (1). 74-128. doi:10.4208/csiam-am.SO-2021-0006
Copy to clipboard
The citation has been copied to your clipboard