Problem 572

Show that for $k\geq 3$

\mathrm{ex}(n;C_{2k})\gg n^{1+\frac{1}{k}}.

Source: erdosproblems.com/572

Graph theory
Turán numbers
Cycles

Wiki page

Status

Open

No claim settles this problem.

Open. The answer is yes for $k=3$ and $k=5$ : Benson's incidence graphs of girth eight and twelve (1966) give $\mathrm{ex}(n;C_6)\gg n^{4/3}$ and $\mathrm{ex}(n;C_{10})\gg n^{6/5}$ , and Bondy and Simonovits (1974) record the matching constructions as known for $k=2,3,5$ ; Benson's result is the accepted partial claim Benson 1966, refereed in Canad. J. Math., which settles the instances $k=3$ and $k=5$ , and the instance $k=3$ is also the accepted partial claim Lazebnik, Ustimenko and Woldar 1995; neither settles the problem. For $k=4$ and every $k\ge6$ no construction reaching the exponent $1+1/k$ is known: the best general lower bound the site cites is $\mathrm{ex}(n;C_{2k})\gg n^{1+2/(3k-3+\nu)}$ ( $\nu=0$ for odd $k$ , $\nu=1$ for even $k$ ), of a smaller order than $n^{1+1/k}$ for every $k\ge4$ , from Lazebnik, Ustimenko and Woldar's 1995 paper (the site cites their 1999 paper for history), which at $k=3$ gives the instance itself; the parity term is the paper's own (Corollary 3.3), and Chung's 1997 survey quotes the bound without it. No proof or disproof for any $k$ outside $\{3,5\}$ was found in the search whose scope the Current assessment records. This is a bounded negative finding, not a certificate of openness.

Er64c: Erdős, P., Extremal problems in graph theory. Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963), Prague (1964), 29--36; p. 33, the unnumbered assertion after display (8). Library home: Erdős 1964; the passage is paged at Erdős 1964, Assertion (p. 33).
BoSi74: Bondy, J. A. and Simonovits, M., Cycles of even length in graphs. J. Combin. Theory Ser. B 16 (1974), no. 2, 97--105; doi:10.1016/0095-8956(74)90052-5. Theorem 1, Remark 1 and Theorem 1*, p. 98. Library home: Bondy and Simonovits 1974.
Be66: Benson, Clark T., Minimal regular graphs of girths eight and twelve. Canad. J. Math. 18 (1966), 1091--1094; doi:10.4153/CJM-1966-109-8. Theorems 1 and 2, p. 1091; the counts on pp. 1092--1093. Library home: Benson 1966.
Er38: P. Erdős, On sequences of integers no one of which divides the product of two others and on related problems. Tomsk. Gos. Univ. Ucen Zap. 2 (1938), 74--82; the graph theorem on p. 78 and Klein's lemma on p. 79. Library home: Erdős 1938.
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, display (4), p. 103. Library home: Erdős 1971 (the card quotes the passage).
Er74c: Erdős, Paul, Extremal problems on graphs and hypergraphs. Hypergraph Seminar, Lecture Notes in Math. 411 (1974), 75--84; display (5), p. 78. Library home: Erdős 1974; paged at Erdős 1974, Display (5) (p. 78).
Er75: Erdős, P., Some recent progress on extremal problems in graph theory. Congr. Numer. XIV (1975), 3--14; Chapter 1, printed pp. 4 and 7. Not cited by the site for this problem. Library home: Erdős 1975; the passage is paged at Erdős 1975, Conjecture (Chapter 1, printed p. 7 = PDF p. 5).
LUW95: Lazebnik, F. and Ustimenko, V. A. and Woldar, A. J., A new series of dense graphs of high girth. Bull. Amer. Math. Soc. (N.S.) 32 (1995), no. 1, 73--79; doi:10.1090/S0273-0979-1995-00569-0; arXiv:math/9501231 (1 January 1995). Corollary 3.3, p. 77, and the statement of the bound on p. 74; the accepted partial claim Lazebnik, Ustimenko and Woldar 1995. Not in the library.
LUW99: Lazebnik, Felix and Ustimenko, Vasiliy A. and Woldar, Andrew J., Polarities and $2k$ -cycle-free graphs. Discrete Math. 197/198 (1999), 503--513; doi:10.1016/S0012-365X(99)90107-3 (the Crossref record carries the publisher's open-archive license dated 17 July 2013). Not held; the site cites it for the history and further references.
Ch97: Chung, F. R. K., Open problems of Paul Erdős in graph theory. J. Graph Theory 25 (1997), 3--36; Problem (35), p. 9 of the author preprint. Not cited by the site; named in the discussion thread. Library home: Chung 1997; paged at Chung 1997, Problem (35).
LUW94b: Lazebnik, F., Ustimenko, V. A. and Woldar, A. J., Properties of certain families of $2k$ -cycle-free graphs. J. Combin. Theory Ser. B 60 (1994), 293--298; the Note added in proof, p. 297. Library home: Lazebnik, Ustimenko and Woldar 1994. Not cited by the site for this problem.
FuGu15: Füredi, Z. and Gunderson, D. S., Extremal numbers for odd cycles. Combin. Probab. Comput. 24 (2015), no. 4, 641--645; arXiv:1310.6766; Theorem 1. Not cited by the site; not in the library.
JaSu24: Janzer, O. and Sudakov, B., On the Turán number of the hypercube. Forum Math. Sigma 12 (2024), doi:10.1017/fms.2024.27; arXiv:2211.02015 (v3, 22 January 2024), p. 1. Library home: Janzer and Sudakov 2022. Not cited by the site.
CLWWY26: Chen, Yaobin, Liu, Hong, Wang, Xia, Wei, Xin and Yang, Fan, The Erdős--Gallai bound for consecutive even cycle lengths. arXiv:2608.27404 (v1 27 August 2026, 70 pp.; v2 7 September 2026, 39 pp. and a 5-page appendix). Preprint; not in the library. Adjacent; see below.

Problem 572

Status

Proof claims

Discussion