gpt 6 astra ultra attempt on Math-324

Erdős Girth Conjecture

Definitions and mathematical statement

For a finite simple graph $G$, its girth is the length of its shortest cycle, with girth $+\infty$ for a forest. Fix an integer $k\ge2$. The Erdős girth conjecture asks for constants $c_k>0$ and $N_k$ such that for every $n\ge N_k$ there is a graph on $n$ vertices satisfying \[ \operatorname{girth}(G)>2k, \qquad |E(G)|\ge c_k n^{1+1/k}. \] Thus every cycle of length at most $2k$ is forbidden simultaneously, not just the cycle $C_{2k}$. The constants may depend on the fixed parameter $k$, but not on $n$. The quantifiers seek families at the indicated density scale for each $k$, rather than a single exceptionally large graph.

Formulation and concept references: [S1].

Short English statement

For every fixed forbidden short-cycle length, can graphs have no such cycles while retaining the conjecturally optimal power-law number of edges?

Research attempt

Status: UNRESOLVED. A matching-order upper bound is proved for every fixed $k$, and explicit constructions prove the required lower exponent for $k=2$ and $k=3$, including the quantifier "every sufficiently large $n$." An elementary probabilistic construction gives a weaker lower exponent for general $k$. The gap between those exponents is not closed.

Source audit and the simultaneous cycle prohibition.

The survey [S1], published in February 2026 and consulted on 27 September 2026, records the girth conjecture as a problem about excluding all short cycles. This is stronger than forbidding just $C_{2k}$. In particular, a dense graph with no $2k$-cycle can still have triangles or shorter even cycles. The constructions and breadth-first arguments below check the full girth condition. The constants are allowed to depend on $k$, but not on the number of vertices.

A graph can be padded with isolated vertices without creating a cycle. This observation is useful only when the available construction sizes are sufficiently close multiplicatively; an arbitrarily sparse infinite sequence of good orders does not alone supply the required density for every large order.

1. A complete upper bound from breadth-first search.

Let $G$ have $n$ vertices, $m$ edges and girth greater than $2k$. Put $a=m/n$. Repeatedly delete a vertex whose current degree is less than $a$. If every vertex were deleted, the sum of the numbers of edges removed at the deletion steps would be strictly less than $na=m$, a contradiction. Thus a nonempty subgraph $H$ survives with minimum degree $\delta\ge a$.

If $a<2$, the desired upper estimate below is immediate. Otherwise choose a root in $H$ and explore to distance $k$. Its first level has at least $\delta$ vertices. A vertex at any level from one through $k-1$ has at least $\delta-1$ neighbors other than its parent. These neighbors must be distinct new vertices: a second path to an existing vertex or a collision of two branches would produce a cycle of length at most $2k$. Edges wholly between vertices at the last level are irrelevant to this count.

Consequently \[ n\ge |V(H)|\ge1+\delta\sum_{j=0}^{k-1}(\delta-1)^j \ge(\delta-1)^k. \] Hence $a\le\delta\le1+n^{1/k}$ and \[ m\le n^{1+1/k}+n. \] Thus the exponent requested in the conjecture is an upper limit up to a constant. The pruning argument is needed: applying a minimum-degree tree count directly to a graph known only to have many edges would skip a hypothesis.

2. An elementary lower bound for arbitrary fixed $k$.

Take a random graph on $n\ge2$ vertices with independent edge probability \[ p=\frac14 n^{-1+1/(2k-1)}. \] Let $X$ count edges and let $Y_j$ count cycles of length $j$. Then \[ \mathbb EX=\binom n2p\ge\frac1{16}n^{1+1/(2k-1)}, \qquad \mathbb EY_j\le\frac{n^jp^j}{2j}. \] For $3\le j\le2k$ we have $n^{j/(2k-1)}\le n^{1+1/(2k-1)}$. Therefore \[ \sum_{j=3}^{2k}\mathbb EY_j \le n^{1+1/(2k-1)}\sum_{j=3}^{\infty}\frac{4^{-j}}{2j} \le\frac1{288}n^{1+1/(2k-1)}. \] Some graph has $X-\sum_{j=3}^{2k}Y_j$ at least its expectation, which exceeds $n^{1+1/(2k-1)}/32$. Delete one edge from each remaining short cycle, charging it to a distinct original short cycle. Deletions cannot create cycles, and there are at most $\sum Y_j$ such charges. The resulting graph has girth greater than $2k$ and at least \[ \frac1{32}n^{1+1/(2k-1)} \] edges. This proves an unconditional all-$n$ construction by the probabilistic method, but $1/(2k-1)<1/k$ for every $k\ge2$.

3. An affine incidence construction for $k=2$.

Over a finite field $\mathbb F_q$, use points $(x,y)$ and lines described by parameters $(a,b)$, with incidence $y=ax+b$. There are $q^2$ vertices in each part, and each point lies on exactly $q$ of these nonvertical lines. The graph has $2q^2$ vertices and $q^3$ edges.

It is simple and bipartite, so has no triangles. Two distinct points lie on at most one common line: if their first coordinates differ, the slope and intercept are uniquely determined; if their first coordinates agree, they cannot both lie on such a line. Thus there is no 4-cycle, and the girth is at least six. This proves the desired $n^{3/2}$ density at these orders.

For an arbitrary $n\ge8$, choose the largest power of two $q\le(n/2)^{1/2}$. Then $q>(n/2)^{1/2}/2$, the construction has at most $n$ vertices, and \[ q^3>\frac{n^{3/2}}{16\sqrt2}>\frac{n^{3/2}}{32}. \] Pad with isolated vertices. Finite fields exist at every prime-power order, so this proves the catalogue's full quantifier for $k=2$, with an explicit constant independent of $n$.

4. A three-coordinate construction for $k=3$.

Take point vertices $P=(x_1,x_2,x_3)\in\mathbb F_q^3$ and line vertices $L=[a,b,c]\in\mathbb F_q^3$, with adjacency defined by \[ b+x_2=ax_1,\qquad c+x_3=ax_1^2. \] For each point and each value of $a$ there is exactly one adjacent line, and for each line and each value of $x_1$ there is exactly one adjacent point. Thus the graph is $q$-regular, with $2q^3$ vertices and $q^4$ edges.

Two distinct points with the same first coordinate cannot have a common line, because the two equations would force their remaining coordinates to agree. Two points with different first coordinates have at most one common line, because the first equation determines $a$ and then $b,c$. Hence there is no 4-cycle.

Suppose there were a 6-cycle, with consecutive points $P_1,P_2,P_3$ and lines $L_1,L_2,L_3$, where $L_i$ joins $P_i$ to $P_{i+1}$ with indices modulo three. Write $x_i$ for the first coordinate of $P_i$ and $a_i$ for the first coordinate of $L_i$. Adjacent point pairs force $x_1,x_2,x_3$ to be pairwise distinct. Summing the coordinate differences around the cycle gives \[ a_1(x_1-x_2)+a_2(x_2-x_3)+a_3(x_3-x_1)=0, \] \[ a_1(x_1^2-x_2^2)+a_2(x_2^2-x_3^2)+a_3(x_3^2-x_1^2)=0. \] Set $(d_1,d_2,d_3)=(a_1-a_3,a_2-a_1,a_3-a_2)$. These equations, together with $d_1+d_2+d_3=0$, say that the Vandermonde matrix with columns $(1,x_i,x_i^2)^{\mathsf T}$ annihilates $d$. Its determinant is a product of nonzero differences, so it is invertible over the field, including in characteristic two. Consequently $a_1=a_2=a_3$.

But at a given point there is only one incident line with a given first coordinate $a$. The two cycle lines meeting that point would coincide, contradicting that the cycle has six distinct vertices. There is therefore no 6-cycle. Bipartiteness excludes odd cycles, so the girth is at least eight, as required for $k=3$.

5. Extending that construction to every large order.

For $n\ge16$, choose the largest power of two $q\le(n/2)^{1/3}$. The preceding graph has at most $n$ vertices and \[ q^4>\frac{n^{4/3}}{16\,2^{4/3}}>\frac{n^{4/3}}{64} \] edges. Again add isolated vertices. This proves the requested exponent and all-large-order quantifier for $k=3$ without needing a prime in a specially prescribed interval. The graph need not be connected; connectivity is not part of the catalogue demand.

The exponent improvements come from exact incidence identities, not merely from deleting short cycles from a random graph. Adding still more moment coordinates in the same style does not by itself establish the absence of every longer even cycle. At each new length one would need a valid argument about all alternating incidence equations, including repetitions among coordinate values that do not make the graph vertices equal.

6. Two shortcuts that do not extend the proof.

First, a bound for graphs excluding just one even cycle cannot be inserted into the breadth-first proof: a collision could create a shorter cycle still allowed by that weaker assumption. Conversely, a graph with high girth certainly avoids that one cycle, so its existence is a sufficient construction for the weaker problem, but the implication goes only one way.

Second, deleting one vertex from each short cycle in an already dense algebraic graph can cost too much. A large number of overlapping short cycles does not give a useful deletion bound unless one proves a small hitting set or a sufficiently small total count. The random alteration calculation supplies an explicit count, and its exponent records exactly the loss incurred by that method.

7. Exact diagnostics and the general gap.

The offline script constructs the affine incidence graphs for primes $q\le11$ and the three-coordinate graphs for $q=2,3,5$. It checks vertex and edge counts, degrees and simplicity, then computes shortest cycles by breadth-first search to verify the claimed girth lower bounds. Exact finite-field arithmetic is used in the construction. It also checks the rational constants in the alteration estimate and the padding inequalities. These finite checks test the coordinate formulas; the field-independent proofs establish the stated two subcases.

For general fixed $k$, the argument gives an upper exponent $1+1/k$ and a lower exponent $1+1/(2k-1)$, without proving a construction at the upper exponent. The remaining task is a family excluding every cycle of length at most $2k$ with the denser edge count, together with enough control of its available orders to cover all sufficiently large $n$. That task remains unresolved here.

Sources

• S1 Dániel Gerbner and Cory Palmer, Survey of Generalized Turán Problems—Counting Subgraphs, EJC Dynamic Survey 27 $2026$, Conjecture 1.8. https://www.combinatorics.org/ojs/index.php/eljc/article/download/ds27/pdf. Formulation source.