gpt pro 5.2 attempt on Math-5744

1) FORMAL RESTATEMENT

Fix an integer $k\ge 2$. Let $C_\ell$ denote the cycle of length $\ell$. Define $\mathrm{ex}(n;\{C_{2k-1},C_{2k}\})$ as the maximum number of edges in an $n$-vertex simple graph containing no cycle of length $2k-1$ and no cycle of length $2k$.

The question is whether \[ \mathrm{ex}(n;\{C_{2k-1},C_{2k}\}) = (1+o(1))(n/2)^{1+1/k} \quad\text{as }n\to\infty. \] Equivalently, whether \[ \frac{\mathrm{ex}(n;\{C_{2k-1},C_{2k}\})}{n^{1+1/k}}\to 2^{-(1+1/k)}. \]

2) QUICK LITERATURE/CONTEXT CHECK

The source file states this as a problem of Erdős and Simonovits, and points to #573 as the case $k=2$. The Erdős Problems website still lists #574 as open as of the access date shown there $2025-11-19$.

3) ATTACK PLAN

Proof-track ideas: - Show an upper bound $O(n^{1+1/k})$ by controlling the number of length-$2k$ cycles forced by high average degree, and then use forbidding $C_{2k-1}$ to force near-bipartiteness. - Try to reduce to the "bipartite $C_{2k}$" extremal problem by proving a stability/regularity statement.

Construction-track ideas: - Take bipartite graphs with many edges and no $C_{2k}$ (then automatically no $C_{2k-1}$), aiming for the constant $2^{-(1+1/k)}$. - Try to beat the bipartite constant by adding odd-cycle structure that still avoids $C_{2k-1}$.

I establish two basic structural lemmas and compute tiny cases for $k=3$; no asymptotic resolution follows.

4) WORK

FAST REALITY CHECK (exact brute force for $k=3$, forbidding $C_5$ and $C_6$). Exact maxima for graphs with no $C_5$ and no $C_6$ for $n\le 7$ (labeled enumeration): \[ \mathrm{ex}(3;\{C_5,C_6\})=3,\ \mathrm{ex}(4;\{C_5,C_6\})=6,\ \mathrm{ex}(5;\{C_5,C_6\})=7,\ \mathrm{ex}(6;\{C_5,C_6\})=9,\ \mathrm{ex}(7;\{C_5,C_6\})=12. \] (For $n<5$ the $C_5,C_6$ constraints are vacuous.)

Lemma 574.1 (neighborhood cycle lifting). Let $G$ be a graph and $v\in V(G)$. If the induced subgraph $G[N(v)]$ contains a cycle $C_\ell$, then $G$ contains a cycle $C_{\ell+1}$.

In particular, if $G$ is $\{C_{2k-1},C_{2k}\}$-free, then for every vertex $v$, \[ G[N(v)]\text{ is }\{C_{2k-2},C_{2k-1}\}\text{-free}. \] Proof. Suppose $G[N(v)]$ contains a cycle with vertex sequence $u_1-u_2-\cdots-u_\ell-u_1$. By definition of $N(v)$, each $u_i$ is adjacent to $v$. Then in $G$ the vertices \[ v,u_1,u_2,\dots,u_\ell \] form the cycle \[ v-u_1-u_2-\cdots-u_\ell-v, \] which has length $\ell+1$. Therefore presence of $C_{2k-2}$ in $G[N(v)]$ would create $C_{2k-1}$ in $G$, and presence of $C_{2k-1}$ in $G[N(v)]$ would create $C_{2k}$ in $G$. $\square$

Lemma 574.2 (bipartite reduction gives a universal lower bound). Let $k\ge 2$. If $H$ is a bipartite graph with no $C_{2k}$, then $H$ is automatically $\{C_{2k-1},C_{2k}\}$-free. Consequently, \[ \mathrm{ex}(n;\{C_{2k-1},C_{2k}\})\ge \mathrm{ex}_{\mathrm{bip}}(n;C_{2k}), \] where $\mathrm{ex}_{\mathrm{bip}}(n;C_{2k})$ denotes the maximum number of edges in an $n$-vertex bipartite $C_{2k}$-free graph. Proof. A bipartite graph contains no odd cycle of any length, so in particular it contains no $C_{2k-1}$. If it is also $C_{2k}$-free, then it contains neither $C_{2k-1}$ nor $C_{2k}$. The inequality follows because the class of bipartite $C_{2k}$-free graphs on $n$ vertices is a subclass of all $\{C_{2k-1},C_{2k}\}$-free graphs on $n$ vertices. $\square$

What these lemmas do (and do not) give. Lemma 574.1 provides a recursive obstruction: a very dense neighborhood would force a forbidden long cycle. Lemma 574.2 shows that any good bipartite $C_{2k}$-free construction is also a construction for this problem. However, neither lemma alone yields the conjectured constant $2^{-(1+1/k)}$ nor an upper bound of order $n^{1+1/k}$ without additional input.

5) VERIFICATION

- Lemma 574.1: the constructed $C_{\ell+1}$ is a simple cycle because the $u_i$ are distinct in $C_\ell$ and none equals $v$. - Lemma 574.2: uses only the definition of bipartite (no odd cycles) and the subgraph notion. - The small-$n$ computations for $k=3$ were checked by exhaustive enumeration of all labeled graphs on $n\le 7$ vertices and direct cycle detection for lengths 5 and 6.

6) FINAL

UNRESOLVED

(i) Strongest fully proved partial result: For any fixed $k\ge 2$, forbidding $C_{2k-1}$ and $C_{2k}$ implies the neighborhood recursion of Lemma 574.1, and there is always the bipartite lower bound of Lemma 574.2.

(ii) First gap (crisp): Prove an upper bound of the correct order, e.g. show $\mathrm{ex}(n;\{C_{2k-1},C_{2k}\})=O_k(n^{1+1/k})$.

(iii) Top 3 next moves (concrete): 1. Prove (or find a counterexample to) a stability statement: any near-extremal $\{C_{2k-1},C_{2k}\}$-free graph must be close to bipartite. 2. Use Lemma 574.1 to bound $\sum_v e(G[N(v)])$ and relate it to the total number of short cycles / walks; attempt to force a $C_{2k}$ when $e(G)$ is too large. 3. Computation for fixed $k$ (say $k=3,4$): exact optimization for $n=8,9,10$ to guess extremal examples and test whether the extremal graphs appear bipartite.

(iv) Minimal counterexample structure: A disproof would require fixed $k$ and an infinite sequence of graphs $G_n$ with no $C_{2k-1}$ and no $C_{2k}$ but $e(G_n)\ge (1+\varepsilon)(n/2)^{1+1/k}$. Such a family would have to exploit the freedom to contain many shorter cycles (including $C_3$ and $C_4$) while carefully avoiding just the two consecutive lengths $2k-1,2k$.