Problem 573

Is it true that

\mathrm{ex}(n;\{C_3,C_4\})\sim (n/2)^{3/2}?

Source: erdosproblems.com/573

Graph theory
Turán numbers

Wiki page

Status

Open

No claim settles this problem.

Open. The lower bound is the bipartite one, $\mathrm{ex}(n;\{C_3,C_4\})\ge z(n,C_4)\ge(n/2)^{3/2}-cn^{4/3}$ , improved for every $n\ge7$ by $cn^{5/4}$ (Ma and Yang 2025, Theorem 1.3, refereed); at the orders $n=2(q^2+q+1)$ , $q$ a prime power, and for almost all $n$ , $\mathrm{ex}(n;\{C_3,C_4\})=(n/2)^{3/2}+\Omega(n^{5/4})$ (their Corollary 1.4), so the second-order term is not $O(n)$ , but the leading term is untouched. The upper bound is the trivial $\mathrm{ex}(n;\{C_3,C_4\})\le\mathrm{ex}(n;C_4)=\tfrac12n^{3/2}+O(n)$ , which Ma and Yang (p. 2) call the best known; so the ratio $\mathrm{ex}(n;\{C_3,C_4\})/(n/2)^{3/2}$ is confined to $[1,\sqrt2]$ in the limit and nothing more is proved. The variant with the five-cycle in place of the triangle is settled: $\mathrm{ex}(n;\{C_4,C_5\})=(n/2)^{3/2}+O(n)$ (Erdős and Simonovits 1982, Theorem 2). An opposite conjecture, that the ratio's lower limit exceeds $1$ , is attributed by Ma and Yang to Allen, Keevash, Sudakov and Verstraëte (2014). No proof or disproof was found in the search whose scope the Current assessment records; this is a bounded negative finding, not a certificate of openness.

KST54: Kövari, T. and Sós, V. T. and Turán, P., On a problem of K. Zarankiewicz. Colloq. Math. 3 (1954), no. 1, 50--57; doi:10.4064/cm-3-1-50-57. Displays (1.3) and (1.5), p. 50; (3.1), p. 52. Library home: Kövari, Sós and Turán 1954; paged at Kövari, Sós and Turán 1954, Inequality (1.5).
MaYa25: Ma, Jie and Yang, Tianchi, On extremal numbers of the triangle plus the four-cycle. Forum of Mathematics, Sigma 13 (2025), e154, 1--7; doi:10.1017/fms.2025.10100 (received 6 December 2022, accepted 13 August 2025, published online 23 September 2025; open access). Conjecture 1.1 and Problem 1.2, p. 2; Theorem 1.3 and Corollary 1.4, p. 3. Not cited by the site. Library home: Ma and Yang 2025 (the journal's open-access article).
ErSi82: Erdős, P. and Simonovits, M., Compactness results in extremal graph theory. Combinatorica 2 (1982), no. 3, 275--288 (the journal and pages as the site's reference text gives them). Theorem 2, p. 278; proof, pp. 285--286. Library home: Erdős and Simonovits 1982; paged at Erdős and Simonovits 1982, Theorem 2.
GJJV25: Goedgebeur, Jan, Jooken, Jorik, Joret, Gwenaël and Van den Eede, Tibo, Improved lower bounds on the maximum size of graphs with girth 5. arXiv:2508.05562v1 (7 August 2025), 17 pp.; published in Experimental Mathematics (online 21 September 2026), 1--12, doi:10.1080/10586458.2026.2731953; the locators below are the arXiv version's. Table 1, p. 4; the introduction, p. 2. Not cited by the site. Library home: Goedgebeur et al. 2025.
Er71: Erdős, P., Some unsolved problems in graph theory and combinatorial analysis. Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969) (1971), 97--109; item 15, p. 103. Library home: Erdős 1971 (the card quotes the passage).
Er75: Erdős, P., Some recent progress on extremal problems in graph theory. Congr. Numer. XIV (1975), 3--14; Chapter 1, printed p. 7. Library home: Erdős 1975; paged at Erdős 1975, Conjecture (Chapter 1, printed p. 7 = PDF p. 5).
Er93: Erdős, Paul, Some of my favorite solved and unsolved problems in graph theory. Quaestiones Math. 16 (1993), 333--350; the site cites p. 336. Chapter I, the $\{C_3,C_4\}$ -free question with the constant $\tfrac1{2\sqrt2}$ , printed p. 336 (the passage is quoted under Erdős's statements). Library home: Erdős 1993. - OEIS A006856, "Maximal number of edges in n-node graph of girth at least 5", https://oeis.org/A006856, accessed: terms $a(1)$ to $a(53)$ , with $a(50)=175$ (the Hoffman--Singleton graph, unique) and $a(53)=181$ .

Problem 573

Status

Proof claims

Discussion