ERDŐS/DAILY ▸

← back to the ledger

ERDőS #572 · PARTIAL

Erdős problem #572 — wave9r

Date checked: 2026-07-28 UTC.

Claim labels used throughout:

external mathematical input.

direction, not asserted as a theorem.

computation.

Observations about a live page or a paper are marked “source check”; they are not being promoted to mathematical proofs.

0. Mandatory live-page gate

I fetched https://www.erdosproblems.com/572 through the Bright Data browser route on 2026-07-28. The returned page was the rendered problem page, not a Cloudflare challenge. I separately followed the linked discussion page, /forum/discuss/572, which resolved to /forum/thread/572, to read all three comments.

Verbatim live statement

Show that for \(k\geq 3\) \[ > \operatorname{ex}(n;C_{2k})\gg n^{1+\frac1k}. > \]

Here the intended asymptotic is for each fixed \(k\), with the positive implicit constant allowed to depend on \(k\).

Status and collision markers

Thus neither mandatory stop condition was triggered.

Results listed on the live page

The page attributes the question to [Er64c], [Er71, p.103], and [Er74c, p.78], and records the following.

\(\operatorname{ex}(n;C_{2k+1})=\lfloor n^2/4\rfloor\) for \(k\geq1\) and \(n>2k+1\), and it records \(\operatorname{ex}(n;C_4)\asymp n^{3/2}\), attributed to Erdős and Klein [Er38].

give \[ \operatorname{ex}(n;C_{2k})\ll k n^{1+1/k}. \]

for \(k=3\) and \(k=5\).

arbitrary \(k\geq3\), \[ \operatorname{ex}(n;C_{2k}) \gg n^{\,1+\frac{2}{3k-3+\nu}}, \qquad \nu=\begin{cases}0,&k\text{ odd},\\1,&k\text{ even}.\end{cases} \] The page points to [LUW99] for history and references.

this question as #46 in the older Extremal Graph Theory collection.

The three comments

The site explicitly warns that comments are user-provided and unverified.

estimates attributed to Verstraëte, Pikhurko, Bukh--Jiang, and He. I independently checked He's primary paper below; its displayed leading factor is \(16\sqrt5\sqrt{k\log k}+o(1)\).

second-order result for \(C_4\), Bondy--Murty, and surveys by Chung, Füredi--Simonovits, Verstraëte, and Lai--Liu. This comment does not claim a new lower exponent for any open \(k\geq3\).

\(\operatorname{ex}(n,C_k)\) into a more general cycle-count-distribution function and links a book. It does not claim a proof of #572.

1. Verified output

There is no asymptotic solution here. There are two concrete outputs.

1.1 Exact finite regime for every \(k\)

(b; Woodall's theorem) For every \(k\geq3\),

\[ \boxed{ \operatorname{ex}(n,C_{2k})= \begin{cases} \binom n2,&1\leq n<2k,\\[4pt] \displaystyle \binom{2k-1}{2}+\binom{n-2k+2}{2}, &2k\leq n\leq4k-3. \end{cases}} \tag{1} \]

The first line is elementary. The second is the sharp long-cycle range of Woodall's theorem, specialized carefully below. This is a known consequence of Woodall, not claimed as novel.

For the first open asymptotic case \(k=4\), (1) gives

| \(n\) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | |---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:| | \(\operatorname{ex}(n,C_8)\) | 0 | 1 | 3 | 6 | 10 | 15 | 21 | 22 | 24 | 27 | 31 | 36 | 42 |

1.2 Independent exhaustive recomputation at \(n=8,9,10\)

(d) A separate isomorph-free computation recomputed

\[ \operatorname{ex}(8,C_8)=22,\qquad \operatorname{ex}(9,C_8)=24,\qquad \operatorname{ex}(10,C_8)=27. \tag{2} \]

For each of these three orders it also found exactly one extremal isomorphism class:

\[ K_1\vee\bigl(K_6\mathbin{\cup}K_{n-7}\bigr). \tag{3} \]

This matches the public Afzaly--McKay table; it is an independent recomputation, not a new table entry.

2. Proof of the exact regime

2.1 The trivial range

(a) If \(n<2k\), no \(n\)-vertex graph can contain a cycle on \(2k\) distinct vertices. The complete graph \(K_n\) is therefore admissible and has every possible edge, proving the first line of (1).

2.2 Woodall's theorem and the upper bound

The version needed here is:

Woodall's long-cycle theorem. If \(G\) has \(N\geq2r+3\) vertices, \(r\geq0\), and \[ > e(G)\geq > \binom{N-r-1}{2}+\binom{r+2}{2}+1, > \] then \(G\) contains a \(C_\ell\) for every \(3\leq\ell\leq N-r\).

(b) This is Theorem 1.1 as quoted in Li--Ning, The stability method, eigenvalues and cycles of consecutive lengths, arXiv:2102.03855, which attributes it to D. R. Woodall, Maximal circuits of graphs I, Acta Math. Acad. Sci. Hungar. 28 (1976), 77--80, DOI 10.1007/BF01902497. The title, journal, volume, pages, year, and DOI were independently checked.

Set

\[ N=n,\qquad r=n-2k. \]

In the range \(2k\leq n\leq4k-3\), we have \(r\geq0\), and

\[ N\geq2r+3 \iff n\geq2(n-2k)+3 \iff n\leq4k-3. \]

Moreover \(N-r=2k\), and Woodall's edge threshold becomes

\[ \binom{n-(n-2k)-1}{2}+\binom{n-2k+2}{2}+1 = \binom{2k-1}{2}+\binom{n-2k+2}{2}+1. \]

Therefore any graph with one more edge than the value in (1) contains a \(C_{2k}\). This proves the upper bound in the second line of (1), rigorously modulo Woodall's theorem.

2.3 Matching construction

(a) Take a clique \(A\cong K_{2k-1}\) and a clique \(B\cong K_{n-2k+2}\), identifying exactly one vertex of \(A\) with one vertex of \(B\). The resulting graph has

\[ (2k-1)+(n-2k+2)-1=n \]

vertices and

\[ \binom{2k-1}{2}+\binom{n-2k+2}{2} \]

edges.

The shared vertex is a cut vertex. A simple cycle cannot use vertices on both sides of that cut: doing so would require visiting the cut vertex twice. Hence every cycle lies wholly in \(A\) or wholly in \(B\). The first clique has \(2k-1\) vertices. The range \(n\leq4k-3\) gives

\[ |B|=n-2k+2\leq2k-1. \]

Neither block has enough vertices for \(C_{2k}\), so this construction is \(C_{2k}\)-free and attains the upper bound. This completes (1).

2.4 Why this does not settle the live problem

(a) For each fixed \(k\), formula (1) covers only \(n\leq4k-3\), a finite interval. The live claim concerns arbitrarily large \(n\). No extrapolation from (1), (2), or the finite table supplies the required uniform asymptotic lower bound.

3. Exhaustive computation and verifier

The standalone verifier is erdos572_wave9r_verify.py.

3.1 Search reduction

(a) Let \(G\) be a graph on \(n\) vertices and \(H=\overline G\). Then \(G\) is \(C_8\)-free exactly when the missing-edge set \(E(H)\) meets the edge set of every \(8\)-cycle of \(K_n\). Thus proving that \(\operatorname{ex}(n,C_8)=M\) amounts to:

  1. exhibiting a \(C_8\)-free \(G\) with \(M\) edges; and
  2. checking every complement \(H\) with at most

\(\binom n2-M-1\) edges contains no valid hitting set, equivalently that \(\overline H\) contains a \(C_8\).

The verifier includes the equality layer as well, so that it can count extremal isomorphism classes.

3.2 Completeness boundary

(d) nauty-geng 2.8.8 generates one representative of every unlabelled simple graph in each requested complement-edge range. Since containing \(C_8\) is invariant under isomorphism, one representative per class is sufficient. The verifier itself, without a graph library:

exactly eight edges;

\(\binom n8\,7!/2\) undirected \(8\)-cycles as edge masks to cross-check samples and every purported survivor;

generator stream.

The reliance on nauty's isomorph-free generator is why (2) is labelled computational-only rather than elementary-rigorous.

3.3 Search sizes and result

The scan includes all complement sizes from zero through the equality layer.

| \(n\) | claimed \(M\) | max. complement size scanned | unlabelled complements checked | \(C_8\)-free equality classes | |---:|---:|---:|---:|---:| | 8 | 22 | 6 | 100 | 1 | | 9 | 24 | 12 | 12,256 | 1 | | 10 | 27 | 18 | 1,502,456 | 1 |

(d) Every graph strictly above \(M\) contained a checked \(C_8\). At equality, the sole survivor in each row had the form (3).

Run:

python3 runs/erdos572_wave9r_verify.py

Successful output:

Woodall substitution/lower construction: PASS (378 parameter pairs, 3 <= k <= 20)
Using exhaustive generator: /bin/nauty-geng
n=8: ex(n,C8)=22, 100 unlabelled complements checked, 1 extremal isomorphism class
n=9: ex(n,C8)=24, 12,256 unlabelled complements checked, 1 extremal isomorphism class
n=10: ex(n,C8)=27, 1,502,456 unlabelled complements checked, 1 extremal isomorphism class
C8 exhaustive check: PASS (1,514,812 unlabelled complements)
PASS: all checks completed in 36.83 seconds

The successful timed run used 36.88 seconds wall time, 37.67 CPU-seconds, and 26,128 KiB maximum resident memory. python3 -m py_compile passed. The verifier's SHA-256 is

b4b2617a0d1d3d2e1e2fb5ddac7c6dda8eb57706970a07a5149fb7ac6cc3c07c

4. Primary-source and current-state audit

4.1 Classical lower constructions

(a; source check) Lazebnik, Ustimenko, and Woldar's paper A new series of dense graphs of high girth, arXiv:math/9501231 exists with those authors and has journal reference Bull. Amer. Math. Soc. 32 (1995), 73--79. Its abstract states the order, regularity, girth, and edge exponent of the \(CD(k,q)\) construction.

(a; source check) Their paper Polarities and \(2k\)-cycle-free graphs, Discrete Mathematics 197/198 (1999), 503--513, DOI 10.1016/S0012-365X(99)90107-390107-3), exists and says explicitly:

\(1+2/(3k-3+\nu)\), with \(\nu=0\) for odd \(k\) and \(1\) for even \(k\);

established.

For \(k=4\), the general construction gives exponent

\[ 1+\frac{2}{3\cdot4-3+1}=\frac65, \]

whereas #572 asks for \(5/4\).

4.2 Explicit confirmation that \(C_8\) is the first open case

(a; source check) Jacques Verstraëte and Jason Williford, Graphs without theta subgraphs, J. Combin. Theory Ser. B 134 (2019), 76--87, DOI 10.1016/j.jctb.2018.05.003, states that the conjecture is known only for \(k\in\{2,3,5\}\), calls \(C_8\) the smallest open case, and records the then-current lower bound \(\operatorname{ex}(n,C_8)=\Omega(n^{6/5})\).

(a; source check) Zhiyang He's New Upper Bound on Extremal Number of Even Cycles, arXiv:2009.04590 exists and proves

\[ \operatorname{ex}(n,C_{2k}) \leq \bigl(16\sqrt5\sqrt{k\log k}+o(1)\bigr)n^{1+1/k}. \]

This improves the coefficient in the known upper bound; it does not provide the missing lower construction.

4.3 Recent adjacent papers checked

Two counterexamples to a conjecture about even cycles, arXiv:2603.24515, exists and studies robust \(C_8\)'s inside \(C_{10}\)-free constructions. Its conclusion discusses generalized hexagons and Wenger graphs, not an \(\Omega(n^{5/4})\) \(C_8\)-free construction.

The exact generalized Turán number for \(C_6\) in \(C_8\)-free graphs, arXiv:2607.03856, exists and determines the maximum number of \(C_6\) copies in a \(C_8\)-free graph. This is a different generalized Turán quantity and does not determine \(\operatorname{ex}(n,C_8)\).

(c; honest search report) Searches of arXiv, publisher records, and recent papers using the exact expressions ex(n,C_8), ex(n,C_{2k}), n^{5/4}, and “even cycle lower bound” found no primary source claiming the lower exponent requested by #572 for a new value of \(k\). A literature search cannot prove absence, but this miss is consistent with the live page's OPEN status and the 2019 primary statement.

4.4 Existing small-case data

(a; source check) The Afzaly--McKay Extremal Graphs and Turan numbers page lists exact \(C_8\) values and all extremal graphs through \(n=37\); at \(n=38\) it lists only a lower bound. In particular, its entries at \(n=8,9,10\) are exactly (2), each with one extremal graph. The computation in Section 3 independently rederives only those first three entries.

5. Precise wall and a clean sufficient target

5.1 Why naive random deletion stops at the wrong exponent

(a) In \(G(n,p)\), the expected edge count has order \(n^2p\), while the expected number of \(C_{2k}\)'s has order \(n^{2k}p^{2k}\). The crude alteration “delete one edge from every forbidden cycle” retains the edge order only when

\[ n^{2k}p^{2k}=O(n^2p), \]

or

\[ p=O\!\left(n^{-(2k-2)/(2k-1)}\right). \]

This yields only

\[ n^2p=O\!\left(n^{1+1/(2k-1)}\right), \]

not \(n^{1+1/k}\). At \(k=4\), choosing the desired density \(p\asymp n^{-3/4}\) gives \(\Theta(n^{5/4})\) edges but \(\Theta(n^2)\) expected \(8\)-cycles. One-edge-per-cycle deletion has no chance of preserving the target number of edges. A successful random approach would need a nontrivial small transversal or strong cycle clustering, not the standard first-moment alteration.

5.2 The generalized-polygon route and its exact obstruction

(b; Feit--Higman as quoted in LUW99) A regular generalized \((k+1)\)-gon of order \(q\) has an incidence graph of girth \(2k+2\), order \(\Theta(q^k)\), and size \(\Theta(q^{k+1})\). It is therefore \(C_{2k}\)-free with the desired exponent. This supplies the classical cases \(k=3\) and \(k=5\) through generalized quadrangles and hexagons.

The same route for \(C_8\) would require a thick finite regular generalized pentagon. The Feit--Higman restriction rules this out; LUW99 records that thick finite regular generalized \(m\)-gons occur only for \(m=3,4,6\). This explains exactly why the classical geometry pipeline hits \(k=3,5\) but skips \(k=4\). It does not rule out approximate geometries or completely different \(C_8\)-free constructions.

5.3 A sufficient construction lemma, including the all-\(n\) step

(a; conditional reduction) For a fixed \(k\), it would suffice to construct, for every \(q=2^t\), a simple \(C_{2k}\)-free graph \(G_q\) with

\[ |V(G_q)|\leq A_kq^k, \qquad |E(G_q)|\geq b_kq^{k+1}, \tag{4} \]

where \(A_k,b_k>0\) do not depend on \(q\).

Indeed, given large \(n\), choose \(q=2^t\) so that

\[ A_kq^k\leq n<A_k(2q)^k. \]

Pad \(G_q\) with isolated vertices to reach exactly \(n\) vertices. The graph remains \(C_{2k}\)-free, and

\[ |E(G_q)| \geq b_kq^{k+1} > \frac{b_k}{(A_k2^k)^{1+1/k}}\,n^{1+1/k}. \]

This explicitly supplies the bounded-gap/uniformity step needed to pass from a parameterized family to all sufficiently large \(n\).

For the first open case, the exact missing lemma in this template is:

construct \(C_8\)-free graphs on \(O(q^4)\) vertices with \(\Omega(q^5)\) edges for every \(q=2^t\).

(c) Such a family may be viewed as an “asymptotic generalized pentagon,” but no incidence-geometry axioms are required. Neither the finite computation nor Woodall's finite regime gives evidence strong enough to produce (4); this is the precise construction wall left by this run.

PARTIAL: Woodall gives the exact all-\(k\) range \(n<2k\) and \(2k\le n\le4k-3\), and an independent exhaustive check verifies the first three \(C_8\) cases, but the required asymptotic construction remains open.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger