gpt 6 astra ultra attempt on Math-366

Asymptotic Turan Numbers of Even Cycles

Definitions and mathematical statement

For a finite graph $H$, define its Turán number by \[ \operatorname{ex}(n,H)=\max\{|E(G)|:|V(G)|=n,\ G\text{ simple and }H\text{-free}\}. \] Here $H$-free means no subgraph isomorphic to $H$, not just no induced copy. For each fixed $k\ge2$, determine the asymptotic order of $\operatorname{ex}(n,C_{2k})$ as $n\to\infty$: find a function $f_k(n)$ with upper and lower bounds by positive constant multiples depending only on $k$. Only the length-$2k$ cycle is forbidden; shorter cycles may occur. This differs from the simultaneous high-girth condition. The target is order of magnitude, not an exact leading constant or a finite table of extremal values.

Formulation and concept references: [S1].

Short English statement

For each fixed even cycle, what is the correct growth rate of the largest edge count in a graph that avoids that cycle?

Research attempt

Status: UNRESOLVED. The asymptotic order for every fixed even cycle is not determined here. This attempt completely proves the order for $C_4$, gives an elementary general lower bound by alteration, and explains why a large-girth breadth-first-search argument cannot be applied to graphs excluding just one specified cycle. The exponents on the two sides of the general problem remain separated.

Source audit and scope.

The source [S1], checked on 27 September 2026, studies an improved leading constant for the hexagon $C_6$. Its introduction records the classical bound $\operatorname{ex}(n,C_{2k})=O_k(n^{1+1/k})$ of Bondy and Simonovits, and matching orders for $k=2,3,5$. Its new hexagon constant is a more specific question than the order sought for every fixed $k$. I use the classical upper bound as an external theorem, rather than pretending to derive it below. I do not assume a universal leading constant of $1/2$: the same source explains why that stronger proposed constant already fails in particular lengths.

All graphs in the attempt are finite and simple. A copy of $C_{2k}$ need not be induced. Chords do not invalidate a forbidden cycle, and shorter cycles are allowed. The constant implicit in $O_k$ or $\Omega_k$ may depend on the fixed integer $k$; the limit concerns $n\to\infty$ with $k$ held fixed.

1. A complete $C_4$ upper bound.

In a $C_4$-free graph, two distinct vertices have at most one common neighbor. Count pairs of neighbors around each vertex. If the degrees are $d_1,\ldots,d_n$ and the edge count is $m$, then \[ \sum_{i=1}^n\binom{d_i}{2}\le\binom n2. \] This is valid even if the two endpoints are adjacent: two distinct common neighbors still create a four-cycle, possibly with extra chords. Since $\sum_i d_i=2m$ and Cauchy--Schwarz gives $\sum_i d_i^2\ge4m^2/n$, \[ \frac{2m^2}{n}-m\le\frac{n(n-1)}2. \] Solving the quadratic inequality for its positive root yields \[ m\le\frac n4\left(1+\sqrt{4n-3}\right) =\frac12n^{3/2}+O(n). \] No minimum-degree or bipartiteness assumption was used. The argument works because the forbidden cycle has exactly two length-two paths with the same endpoints and distinct middle vertices; counting such pairs directly detects a four-cycle.

2. A finite-field construction proving the matching order.

Let $q$ be a prime power. Make one vertex class the $q^2$ points $(x,y)\in\mathbb F_q^2$ and the other the $q^2$ ordered pairs $(a,b)$ representing nonvertical affine lines $y=ax+b$. Join a point to a line when the equation holds. Each line contains exactly $q$ points, so the graph has \[ n_q=2q^2,\qquad m_q=q^3. \] Two distinct points lie on at most one of these lines. If their $x$-coordinates differ, the slope and intercept are uniquely determined; if their $x$-coordinates agree, no nonvertical line contains both. Thus there is no four-cycle, because such a cycle would give two points incident with two different common lines.

To obtain a lower bound for every sufficiently large $n$, choose a power of two $q$ satisfying \[ \frac12\sqrt{n/2}<q\le\sqrt{n/2}. \] For $n\ge8$, such a power exists and is at least two. Add isolated vertices to the construction until it has exactly $n$ vertices. This cannot create a cycle. Consequently, \[ \operatorname{ex}(n,C_4)\ge q^3> \frac{1}{16\sqrt2}\,n^{3/2}. \] Together with the upper bound this proves $\operatorname{ex}(n,C_4)=\Theta(n^{3/2})$, which is the entire order question for $k=2$. The constant from this elementary bipartite construction is not the sharp leading constant, and no sharpness claim is made for it.

For longer cycles, this construction cannot simply be reused. Over a field with at least three elements, choose three points with distinct $x$-coordinates which are not collinear; for instance $(0,0),(1,0),(2,1)$ in $\mathbb F_3^2$. Their three pairwise connecting lines are distinct and nonvertical. Alternating between the three points and these lines produces a six-cycle. Thus being $C_4$-free is not a certificate of being $C_6$-free.

3. An elementary lower bound for every fixed $k$.

Let $G$ be the random graph on $n$ vertices with independent edge probability \[ p=\frac12 n^{-(2k-2)/(2k-1)}. \] Let $X$ be its number of edges and $Y$ its number of copies of $C_{2k}$. The exact expectations are \[ \mathbb E X=\binom n2p,\qquad \mathbb E Y=\frac{(n)_{2k}}{4k}p^{2k}, \] where $(n)_{2k}=n(n-1)\cdots(n-2k+1)$, interpreted as zero when $n<2k$. The divisor $4k$ accounts for a cyclic choice of starting vertex and two directions.

Put $a=2k/(2k-1)$. For $n\ge2$, using $\binom n2\ge n^2/4$ and $(n)_{2k}\le n^{2k}$ gives \[ \mathbb E(X-Y) \ge\left(\frac18-\frac{1}{4k\,2^{2k}}\right)n^a \ge\frac1{16}n^a. \] The last inequality holds for every $k\ge2$. Some realization therefore has $X-Y\ge n^a/16$. From that realization repeatedly delete an edge belonging to a remaining $C_{2k}$ until no such cycle remains. Deleting edges never creates cycles, so the number of deletions is at most the initial $Y$: charge each deletion to the then chosen original cycle, which is destroyed and cannot be chosen again. The resulting graph has at least $X-Y$ edges.

This proves the unconditional estimate \[ \operatorname{ex}(n,C_{2k})\ge\frac1{16}n^{1+1/(2k-1)} \qquad(n\ge2,k\ge2). \] The estimate is intentionally elementary and generally not the strongest known lower bound. Its value here is that the proof is complete and the exponent loss is explicit. Combining it with the external Bondy--Simonovits theorem leaves \[ n^{1+1/(2k-1)}\ll_k\operatorname{ex}(n,C_{2k}) \ll_k n^{1+1/k}. \] For $k=2$ the finite-field construction closes this gap; the alteration calculation alone does not.

4. What breadth-first search actually requires.

Suppose instead that a graph has minimum degree $\delta\ge2$ and girth greater than $2k$, meaning that it has no cycle of any length at most $2k$. Start breadth-first search from a vertex. To construct levels through $k$, each nonroot vertex at a level from $1$ through $k-1$ has at least $\delta-1$ new children, and children reached from different earlier vertices cannot coincide. Otherwise the two tree paths to a collision, together with the offending edge or pair of edges, give a cycle of length at most $2k$. Therefore \[ n\ge1+\delta\sum_{j=0}^{k-1}(\delta-1)^j. \] The resulting relation $\delta=O_k(n^{1/k})$ is a valid large-girth estimate.

It is not a proof for graphs excluding only $C_{2k}$. Such a graph may have triangles, four-cycles, or other shorter cycles; breadth-first branches may merge along precisely those shorter cycles. For a stark example, $K_{2k-1}$ is $C_{2k}$-free simply because it has too few vertices, but contains abundant short cycles and does not have the asserted tree expansion. Disjoint unions of these cliques produce arbitrarily large examples of the same local failure. The example does not contradict the correct extremal upper bound; it contradicts the extra girth hypothesis tacitly inserted into the attempted proof.

A related error is to count all length-$k$ walks between two vertices and assert that two such walks form a $C_{2k}$. Walks may repeat vertices, two simple paths may share internal vertices, and their union may yield only shorter cycles. One needs to control overlaps and degeneracies before extracting a simple cycle of the desired length. This is a substantive part of the general even-cycle upper-bound problem, not a negligible endpoint correction.

5. Maximum cuts and the direction of comparison.

Every graph with $m$ edges has a bipartite subgraph with at least $m/2$ edges: independently put each vertex into one of two classes, so each edge crosses with probability $1/2$, and use expectation. Removing the noncrossing edges preserves $C_{2k}$-freeness. Hence an upper bound for all bipartite $C_{2k}$-free graphs implies an upper bound, with at most a factor two loss, for all graphs.

For lower bounds, a bipartite construction is automatically an admissible general graph, but the reverse assertion is false: an arbitrary extremal graph need not be bipartite. This distinction is harmless for some order estimates and decisive for a proposed leading constant. It is another reason not to identify the order problem in the catalogue with a conjecture about one specific sharp coefficient.

6. Checks and the remaining construction problem.

The offline diagnostics enumerate all simple graphs through six vertices, determine whether they contain $C_4$ or $C_6$ as non-induced subgraphs, and record the exact extremal values in that finite range. They verify the common-neighbor inequality and the derived $C_4$ upper bound using integer arithmetic. They also construct the affine incidence graphs over the prime fields of sizes $2,3,5,7$, check their vertex and edge counts, test for repeated common neighbors, and exhibit a six-cycle when $q=3$. The alteration coefficient inequality is checked as an exact rational inequality for a finite range of $k$, alongside its general proof above.

These checks do not establish an asymptotic exponent for a missing length. To finish the expected order statement at an arbitrary fixed $k$, one needs a family of $C_{2k}$-free graphs with $\Omega_k(n^{1+1/k})$ edges, or a different analysis establishing the correct order if that expected lower exponent fails. A construction with sufficiently large girth would suffice, but the stronger girth condition is not part of the target. The elementary alteration loses density, while the $C_4$ incidence geometry contains some longer even cycles. Neither supplies the missing general family. Thus the full catalogue problem remains unresolved by this attempt despite the complete $k=2$ case.

Sources

• S1 Das, Islam, Mohapatra and Sen, An Improved Upper Bound for the Turan Number of the Hexagon $2026$. https://arxiv.org/html/2609.10003. Formulation source.