Erdoes #713 - working report - Erdős Problem a Day

Erdős problem #713 — wave w011

Live-page check, literature audit, elementary reductions, and exact computation: 2026-07-28 (UTC).

Claim labels used throughout:

[a] elementary-rigorous;
[b] rigorous modulo the explicitly named published theorem;
[c] plausible/structural-unverified;
[d] computational-only.

0. Mandatory live-page gate

I fetched the rendered live problem page and its discussion thread through the Bright Data browser route. I did not use the stale tracker YAML as a statement or as a status source.

[d] Live state. At access time the page was marked OPEN - $500, was last edited 07 March 2026, and displayed:

2 comments on this problem;
0 claimed proofs for this problem;
Interested in collaborating: None;
Currently working on this problem: None;
no difficult, tractable, or formalisation-worker marker.

Thus none of the mandatory stop conditions fired.

The exact current problem statement, verbatim, is:

Is it true that, for every bipartite graph $G$, there exists some $\alpha\in[1,2)$ and $c>0$ such that \[ > \operatorname{ex}(n;G)\sim cn^\alpha? > \] Must $\alpha$ be rational?

Here $\operatorname{ex}(n;G)$ is the maximum number of edges in an $n$-vertex graph containing no (not necessarily induced) copy of $G$.

[b] Results listed on the live page.

The problem is attributed to Erdős and Simonovits. Erdős also asked the

weaker order-of-magnitude version $\operatorname{ex}(n;G)\asymp n^\alpha$.

Erdős initially proposed that the exponent should have the form

$1+1/k$ or $2-1/k$, $k\geq2$; the page says Erdős and Simonovits disproved that restriction in [ErSi70].

The analogous hypergraph assertion is false. The page gives the

Frankl--Füredi 5-uniform, 8-vertex example with edges $\{12346,12457,12358\}$, whose extremal number is $o(n^5)$ but is not $O(n^c)$ for any $c<5$.

The page says Füredi--Gerbner simplified and extended the hypergraph

counterexample to every uniformity $k\geq5$; uniformities 3 and 4 remain open and are conjectured false. This is corroborated by their primary preprint, Hypergraphs without exponents, arXiv:1906.06657.

The page points to problem #571.

[d] Comments read in full. Both comments are from 19 August 2025 and concern a formerly incorrect hypergraph example, not a graph solution. Zach Hunter explains that forbidding the single hypergraph encoding 3-term arithmetic progressions does not work (all edges through one vertex avoid it), points to the genuine Frankl--Füredi construction and arXiv:1906.06657, and notes that the page was corrected. Desmond Weisenberg identifies #716 as the Ruzsa--Szemerédi problem and says that its correct formulation makes it less applicable here. Neither comment claims a proof, counterexample to the graph question, or current work.

1. A literal counterexample on the live statement

Proposition 1.1 [a]. The statement exactly as displayed on the live page is false.

Proof. Let $G=K_2$. This is a bipartite graph, and

\operatorname{ex}(n;K_2)=0

for every $n$: a $K_2$-free graph has no edges. For every allowed $\alpha$ and every $c>0$, however, $cn^\alpha>0$, and $\operatorname{ex}(n;K_2)/(cn^\alpha)=0$, not $1$. Hence $\operatorname{ex}(n;K_2)\not\sim cn^\alpha$. $\square$

This is a quantifier/boundary defect, not a claimed solution of the intended $500 research question. In fact, Ferber--McKinley--Samotij's modern formulation quoted below says “nonempty bipartite graph” and therefore retains the same $K_2$ defect. The natural intended version excludes graphs with zero extremal density constant; for connected graphs it is enough to start with graphs having at least three vertices. Every claim below addresses that nondegenerate version. I do not claim that the intended version is settled.

2. Primary-source literature audit

2.1 The direct conjecture

[b] In the original Erdős--Simonovits paper, Some extremal problems in graph theory, printed pp. 378--379, equation (6) asks for an exponent for which $\operatorname{ex}(n;L)/n^\alpha$ has a limit when $\chi(L)=2$; equation (7) proposes the special exponent forms. The paper's constructions rule out the special-form restriction. They do not resolve the existence of a power-law limit for every fixed bipartite graph.

[b] Ferber, McKinley, and Samotij restate the strong assertion as Conjecture 3 in Supersaturated Sparse Graphs and Hypergraphs, IMRN 2020, 378--402:

\frac{\operatorname{ex}(n,H)}{n^\alpha}\longrightarrow c>0

for a rational $\alpha\in[1,2)$ and every nonempty bipartite $H$. Their Conjecture 4 is only the two-sided $\Theta(n^\alpha)$ assertion. They explicitly distinguish this direct problem (given $H$, determine its behavior) from inverse exponent problems (given $\alpha$, construct some $H$).

[c] Search result, not a theorem. A title/abstract/full-text search of the original formulation, the modern Conjectures 3 and 4, Turán exponents, and the individual first obstruction $C_6$, through 2026-07-28 found no paper claiming the direct strong conjecture for all fixed bipartite graphs. Bibliographic non-discovery is not a proof of openness.

2.2 Very recent work does not supply the missing limit

[b] Liu and Yang, On Turán Number of Graphs with Small Minimum Feedback Vertex Numbers, arXiv:2607.07157v1 (submitted 8 July 2026), prove that if a connected bipartite $H$ has minimum feedback vertex number one and shortest cycle $2k^\ast$, then

\operatorname{ex}(n,H)=O(n^{1+1/k^\ast}).

They also obtain exact $\Theta$-exponents for certain other constructed families. This is a recent unrefereed v1, and its displayed theorem is an upper bound, not a positive leading-limit theorem.

[b] Jiang, Longbrake, and Yepremyan, Rational exponents near $3/2$, arXiv:2607.19607v1 (submitted 21 July 2026), realize many specified rational numbers as $\Theta$-exponents of some single bipartite graph. That advances the inverse rational-exponents conjecture; it neither handles each prescribed $H$ nor proves a leading constant.

[b] Similarly, Bukh--Conlon's random-algebraic result concerns a finite forbidden family for each rational exponent, and the subsequent single-graph inverse results concern specially constructed graphs. None of these logical quantifiers implies the direct assertion in #713.

2.3 Two published asymptotics used below

[b] Füredi's theorem. For each fixed integer $t\geq2$,

\operatorname{ex}(n,K_{2,t}) =\frac{\sqrt{t-1}}2\,n^{3/2}+O(n^{4/3}). \tag{2.1}

Source: Z. Füredi, New Asymptotics for Bipartite Turán Numbers, J. Combin. Theory Ser. A 75 (1996), 141--144, DOI 10.1006/jcta.1996.0067.

[b] The current $C_6$ gap. Füredi, Naor, and Verstraëte, On the Turán number for the hexagon, Adv. Math. 203 (2006), 476--496, DOI 10.1016/j.aim.2005.04.011, prove, for infinitely many $n$, a $C_6$-free construction with

\operatorname{ex}(n,C_6)\geq (A-o(1))n^{4/3}, \qquad A=\frac{3(\sqrt5-2)}{(\sqrt5-1)^{4/3}} =0.533869602182\ldots , \tag{2.2}

and the uniform upper bound

\operatorname{ex}(n,C_6)\leq(\lambda+o(1))n^{4/3}, \qquad \lambda=0.627110780292\ldots , \tag{2.3}

where $\lambda$ is the unique real root of

16\lambda^3-4\lambda^2+\lambda-3=0.

The paper explicitly says there is little evidence as to whether $\operatorname{ex}(n,C_6)/n^{4/3}$ has a limit. Its construction disproves an older proposed specific leading coefficient $1/2$; it does not disprove the existence of some other leading coefficient, which is what #713 asks.

[c] Current-best qualification. Targeted searches for the displayed constants, the paper title, and a later $C_6$ asymptotic found later papers still calling the ordinary $C_6$ Turán problem unsolved and found no improved ordinary-graph leading-limit theorem. This is a careful literature miss, not a proof that no unindexed result exists.

3. Elementary reductions

These reductions are useful because their error is only $O_H(n)$, so they preserve every superlinear leading asymptotic, including its constant.

3.1 Adding one leaf changes the extremal number by only $O(n)$

Lemma 3.1 [a] (rooted leaf extension). Let $F$ have $q$ vertices and no isolated vertices, fix a vertex $x\in V(F)$, and let $F^+$ be obtained by adding one new leaf adjacent to $x$. For every $n$,

\operatorname{ex}(n,F) \leq \operatorname{ex}(n,F^+) \leq \operatorname{ex}(n,F)+(q-1)n. \tag{3.1}

Proof. Since $F\subset F^+$, every $F$-free graph is $F^+$-free, giving the lower bound.

For the upper bound, start with an arbitrary $F^+$-free $n$-vertex graph $X$. Repeatedly delete a vertex whose current degree is less than $q$. At most $q-1$ edges are charged at each of at most $n$ deletions, so fewer than $qn$, and in fact at most $(q-1)n$, edges are deleted.

The remaining graph has minimum degree at least $q$. It cannot contain a copy of $F$: in such a copy the image of $x$ has at most $q-1$ neighbors inside the copy and hence has a neighbor outside it, which extends the copy to $F^+$. Thus the remainder is $F$-free and has at most $\operatorname{ex}(n,F)$ edges: padding it to $n$ vertices with isolates cannot create $F$, because $F$ has no isolated vertex. Adding back the charged edges proves (3.1). $\square$

Corollary 3.2 [a] (2-core reduction). If $H$ is connected and contains a cycle, and $K$ is its 2-core, then

0\leq\operatorname{ex}(n,H)-\operatorname{ex}(n,K) \leq C_Hn \tag{3.2}

for a constant $C_H<h^2$, where $h=v(H)$.

Proof. The vertices outside a nonempty 2-core form rooted trees attached to it. Reverse a leaf-stripping order and apply Lemma 3.1 once per added vertex. Every intermediate graph has at most $h$ vertices, so the sum of all coefficients is less than $h^2$. $\square$

Consequently, if $\operatorname{ex}(n,K)\sim c n^\alpha$ with $\alpha>1$, then

\operatorname{ex}(n,H)\sim c n^\alpha. \tag{3.3}

Both the exponent and the leading constant survive.

3.2 Components also cost only $O(n)$

For a graph with at least one nonisolated vertex, isolated vertices cause no asymptotic difficulty: if $H'$ is obtained from $H$ by deleting all $s$ isolated vertices, then for every $n\geq v(H)$, a copy of $H'$ can be extended to a copy of $H$ using any $s$ unused host vertices. Hence $\operatorname{ex}(n,H)=\operatorname{ex}(n,H')$ in that range. In the component lemma we may therefore assume every component has an edge.

Lemma 3.3 [a] (component sandwich). If the connected components of $H$ are $H_1,\ldots,H_r$ and $h=v(H)$, then

\max_i\operatorname{ex}(n,H_i) \leq\operatorname{ex}(n,H) \leq\max_i\operatorname{ex}(n,H_i)+hn. \tag{3.4}

Proof. An $H_i$-free graph is $H$-free, proving the lower bound. For an $H$-free host $X$, greedily seek vertex-disjoint copies of $H_1,H_2,\ldots,H_r$. The process must fail at some $H_i$, or their union would be a copy of $H$. Delete the vertices used before that failure. Fewer than $h$ vertices, incident with at most $hn$ edges, were deleted, and the remainder is $H_i$-free. This proves the upper bound. $\square$

In particular, if at least one component has a superlinear power-law asymptotic and all components with the largest exponent $\beta>1$ have leading constants $c_i$, then

\operatorname{ex}(n,H) \sim \left(\max_{\alpha_i=\beta}c_i\right)n^\beta. \tag{3.5}

The $hn$ error is $o(n^\beta)$.

3.3 Connected trees have a positive linear limit

Proposition 3.4 [a]. If $T$ is a connected tree on $t\geq3$ vertices, then

\operatorname{ex}(n,T)\sim c_Tn

for a constant

\frac{t-2}{2}\leq c_T\leq t-2.

Thus #713 has the rational exponent $\alpha=1$ for every nondegenerate connected tree.

Proof.

A disjoint union of $T$-free graphs is $T$-free because $T$ is

connected. Hence $a_n=\operatorname{ex}(n,T)$ is superadditive: $a_{m+n}\geq a_m+a_n$.

Repeatedly delete vertices of current degree at most $t-2$. If a graph

initially has more than $(t-2)n$ edges, this cannot delete every vertex; the nonempty remainder has minimum degree at least $t-1$. The standard greedy leaf order embeds every $t$-vertex tree in such a graph. Therefore $a_n\leq(t-2)n$.

Disjoint copies of $K_{t-1}$, plus isolated leftover vertices, avoid

$T$ and give \[ a_n\geq \left\lfloor\frac n{t-1}\right\rfloor\binom{t-1}{2} =\frac{t-2}{2}n-O_T(1). \]

Fekete's lemma applied to the finite, linearly bounded superadditive

sequence $a_n$ gives $\lim_n a_n/n=\sup_n a_n/n=:c_T$. The two bounds make $c_T$ positive and give the displayed interval. $\square$

This proof deliberately excludes $T=K_2$, whose limiting coefficient is zero and supplied the literal counterexample.

4. A complete infinite class with its exact leading constant

Theorem 4.1 [b]. Let $H$ be any graph with at least one cyclic component. Suppose the 2-core of every cyclic component is $K_{2,t_i}$ for some fixed $t_i\geq2$; arbitrary tree components are allowed. Put $t_{\max}=\max_i t_i$. Then

\boxed{\displaystyle \operatorname{ex}(n,H) \sim \frac{\sqrt{t_{\max}-1}}2\,n^{3/2}.} \tag{4.1}

In particular #713 holds for this infinite class, with rational exponent $\alpha=3/2$, and the leading constant is explicit.

Proof. Füredi's theorem (2.1), followed by the elementary 2-core reduction (3.2), gives

\operatorname{ex}(n,H_i) =\frac{\sqrt{t_i-1}}2\,n^{3/2}+o(n^{3/2})

for each cyclic component. Proposition 3.4 makes every tree component only $O(n)$. Apply the component sandwich (3.4); among the $n^{3/2}$ terms the greatest coefficient is the one with greatest $t_i$, and its difference from the upper bound is $O_H(n)$.

$\square$

This is more than an exponent transfer: the additive error in the two elementary lemmas is small enough to preserve Füredi's exact coefficient.

4.1 All connected bipartite graphs on three through five vertices

Theorem 4.2 [b]. Every connected bipartite graph $H$ with $3\leq v(H)\leq5$ satisfies the intended strong assertion:

if $H$ is a tree, $\alpha=1$ and

$\operatorname{ex}(n,H)\sim c_Hn$ for the positive constant in Proposition 3.4;

if its 2-core is $C_4=K_{2,2}$, then

\[ \operatorname{ex}(n,H)\sim\tfrac12n^{3/2}; \]

if its 2-core is $K_{2,3}$, then

\[ \operatorname{ex}(n,H)\sim\tfrac1{\sqrt2}n^{3/2}. \]

Proof. It remains only to classify the nonempty 2-core. A bipartite core has minimum degree at least two and at least four vertices. On four vertices its bipartition must be $2+2$, forcing $K_{2,2}$. On five vertices, either the core still has four vertices, or its bipartition is $2+3$; minimum degree two forces each vertex in the part of size three to meet both vertices in the other part, giving $K_{2,3}$. Now use Proposition 3.4 and Theorem 4.1. $\square$

At six vertices $C_6$ already occurs as a 2-core, so the same classification route reaches a genuinely unresolved leading-limit problem. There are other six-vertex cores as well; no claim is made that $C_6$ is the only obstruction at that order.

5. Exact finite computation for the first obstruction $C_6$

The standalone checker is erdos713_wavew011_reverify.py. It uses the Python standard library and nauty's geng (/bin/nauty-geng on this VM). All graph6 decoding, edge counting, bipartiteness, 2-core stripping, and $C_6$ detection are implemented in the script rather than delegated to a graph library.

5.1 Exact table

[d] Exhaustive nonisomorphic generation gives:

| $n$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:| | $\operatorname{ex}(n,C_6)$ | 0 | 1 | 3 | 6 | 10 | 11 | 13 | 16 | 20 | 21 |

For $n<6$ the complete graph is $C_6$-free. For $6\leq n\leq10$, the following graph6 records are lower-bound witnesses:

| $n$ | edges | graph6 | |---:|---:|:---| | 6 | 11 | ETnw | | 7 | 13 | FQinw | | 8 | 16 | GQhTV{ | | 9 | 20 | HQhTQj~ | | 10 | 21 | ICQQShI~w |

[d]/[a] Structural witness check. Direct decoding shows that these witnesses are windmills: their blocks are complete graphs of order at most five meeting in a single cut vertex. Elementary block theory then says every cycle is contained in one block, so none contains $C_6$. The checker does not rely on this description: it decodes each record, recounts its edges, and tests it using two independently written cycle enumerators.

[d] Exhaustive upper certificate. For a claimed value $e$, geng generates one representative of every isomorphism class with exactly $e+1$ edges, and the from-scratch depth-first detector finds a $C_6$ in every representative. This exact edge level suffices: if a $C_6$-free graph had more than $e$ edges, arbitrary edge deletions would leave a spanning $C_6$-free graph with exactly $e+1$ edges. The numbers of classes rejected were:

| $n$ | tested edge count | nonisomorphic classes rejected | |---:|---:|---:| | 6 | 12 | 5 | | 7 | 14 | 65 | | 8 | 17 | 980 | | 9 | 21 | 21,933 | | 10 | 22 | 1,358,852 |

The trust boundary is explicit: nauty is trusted to exhaust isomorphism classes and emit valid graph6; every property of each emitted graph is recomputed locally. The fast detector was compared with a separate six-subset/cyclic-order detector on all 208 nonisomorphic graphs through six vertices. The slow detector also independently rejects a $C_6$ in each explicit witness.

5.2 Small-core enumeration

[d] The same run independently enumerates all connected bipartite isomorphism classes through six vertices. Grouping by

(v(\operatorname{core}_2),e(\operatorname{core}_2), \text{sorted core degrees})

gives:

| $n$ | total | empty core | $C_4$ | $K_{2,3}$ | $C_6$ | other | |---:|---:|---:|---:|---:|---:|---:| | 1 | 1 | 1 | 0 | 0 | 0 | 0 | | 2 | 1 | 1 | 0 | 0 | 0 | 0 | | 3 | 1 | 1 | 0 | 0 | 0 | 0 | | 4 | 3 | 2 | 1 | 0 | 0 | 0 | | 5 | 5 | 3 | 1 | 1 | 0 | 0 | | 6 | 17 | 6 | 4 | 2 | 1 | 4 |

The four other six-vertex core signatures are

\begin{split} &(6,7;(2,2,2,2,3,3)),\\ &(6,8;(2,2,2,2,4,4))\quad(=K_{2,4}),\\ &(6,8;(2,2,3,3,3,3)),\\ &(6,9;(3,3,3,3,3,3))\quad(=K_{3,3}). \end{split}

This computational classification is an independent audit of the elementary five-vertex proof, not an extrapolation to arbitrary order.

5.3 Reproduction

Run:

python3 runs/erdos713_wavew011_reverify.py

The full run performs the exhaustive $n=10$ certificate, not a cached lookup. A quicker smoke test is available as:

python3 runs/erdos713_wavew011_reverify.py --max-n 6

The script also recomputes $A$, the real root $\lambda$, and the rational exponent arithmetic quoted in the report.

[d] Measured full-run result. On this VM the final clean run ended with ALL CHECKS PASSED after 26.09 wall seconds, with maximum resident set size 14,284 KB. Of that time, 25.64 seconds was the $n=10$ upper certificate.

6. Exact wall

[b] The first concrete missing lemma is already:

Prove that \[ > \lim_{n\to\infty} > \frac{\operatorname{ex}(n,C_6)}{n^{4/3}} > \] exists and is positive.

The rational order $4/3$ is known, but (2.2)--(2.3) only imply

0.533869602182\ldots \leq \limsup_{n\to\infty} \frac{\operatorname{ex}(n,C_6)}{n^{4/3}} \leq 0.627110780292\ldots .

They do not identify a common liminf and limsup. The construction is available only on an infinite subsequence, and the upper estimate has a different leading coefficient. Neither bound supplies an interpolation or near-superadditivity theorem on the $n^{4/3}$ scale.

[a] Why the standard disjoint-union limit argument fails. For a connected forbidden graph $H$, $\operatorname{ex}(m+n,H)\geq\operatorname{ex}(m,H)+ \operatorname{ex}(n,H)$. Fekete therefore controls $\operatorname{ex}(n,H)/n$, which solved trees. It says nothing about $\operatorname{ex}(n,H)/n^{4/3}$: ordinary superadditivity is on the wrong normalization, and disjoint union loses the convex-scale cross term. The needed new ingredient would be a scale-compatible interpolation, stability, or blow-up lemma with $o(n^{4/3})$ loss. No such lemma follows from the known $C_6$ bounds.

[d] Why more finite search is not the missing computation. The $n\leq10$ table is exact but cannot prove convergence. Extending it one or several orders would be much more expensive—the $n=10$ upper certificate already examines 1.36 million classes—and, even if completed, would still leave the uniform $n\to\infty$ step untouched. I therefore did not spend multi-core hours on a finite extension that cannot address the identified lemma. A computation capable of closing the problem would need a rigorously parameterized structural certificate valid for every $n$, not merely a larger lookup table.

7. Verified outcome

[a] The live statement is literally falsified by $G=K_2$.
[a]/[b] After excluding that degenerate case, leaf and component

reductions transfer any superlinear leading asymptotic with only $O_H(n)$ error.

[b] This proves the full strong assertion, including explicit

constants, for the infinite class in Theorem 4.1, and for every connected bipartite graph on three through five vertices.

[d] The exact values of $\operatorname{ex}(n,C_6)$ through

$n=10$ and the small-core classification are reproducibly certified.

[b] The intended general problem remains blocked already by the

existence of the $C_6$ leading limit; no finite computation or inverse exponent theorem supplies that missing uniformity.

FOUND: The authoritative live statement is literally false for $G=K_2$ since $\operatorname{ex}(n,K_2)=0$; for the intended nondegenerate problem, the report proves an explicit infinite $K_{2,t}$-core class and exact small cases, while isolating the unresolved $C_6$ leading-limit lemma.

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