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

Erdős problem #571 — wave9q report

Date of investigation: 2026-07-28 (UTC).

Claim labels used throughout:

(a) elementary-rigorous: proved here from definitions and exact integer

arithmetic;

(b) rigorous-modulo-named-theorem: the deduction is rigorous assuming

the cited published theorem or identified preprint theorem;

(c) plausible/structural-unverified: an observation or literature-search

miss, not a theorem;

(d) computational-only: established by the supplied finite computation,

not asserted uniformly beyond its checked range.

0. Mandatory live-page gate

I fetched the protected origin https://www.erdosproblems.com/571 through the Bright Data browser at the end of the investigation, at approximately 2026-07-28 15:27 UTC. The page title was 571 | Erdős Problems; this was the live origin, not a search cache or a third-party mirror.

The exact displayed problem statement, in the site's LaTeX, is:

Show that for any rational $\alpha \in [1,2)$ there exists a bipartite graph $G$ such that\[\mathrm{ex}(n;G)\asymp n^{\alpha}.\]

The same live fetch gave all of the following:

status: OPEN;
page last edited: 07 March 2026;
0 comments on this problem;
0 claimed proofs for this problem;
Likes this problem: None;
Interested in collaborating: None;
Currently working on this problem: None;
difficult/tractable/formalisable/formalising markers: all None.

Thus the mandatory collision gate passes: there is neither a claimed proof nor a current worker. (d: direct live-page observation.)

The live page attributes the problem to Erdős and Simonovits and records Erdős's comment in [Er78], “I am not entirely sure that a trivial counterexample can not be found.” It says that Bukh and Conlon proved the finite-family relaxation. Its displayed list of single-graph Turán exponents is:

\begin{gathered} \frac32-\frac1{2s}\quad(s\ge2),\\ \frac43-\frac1{3s},\quad \frac54-\frac1{4s}\quad(s\ge2),\\ 2-\frac ab\quad\text{when}\quad \left\lfloor\frac ba\right\rfloor^3 \le a\le\frac{b}{\lfloor b/a\rfloor+1}+1,\\ 2-\frac ab\quad\text{when}\quad b>a\ge1,\ b\equiv\pm1\pmod a,\\ 1+\frac ab\quad\text{when}\quad b>a^2,\\ 2-\frac2{2b+1}\quad(b\ge2),\quad\text{and }7/5,\\ 2-\frac ab\quad\text{when}\quad b\ge(a-1)^2. \end{gathered}

It also points to problem #713 and calls this problem #45 in the Extremal Graph Theory graph collection. These bullets are page metadata, not the statement.

1. Primary-source audit and what is newer than the tracker

I checked the arXiv abstract record and the relevant theorem/proposition text in the PDF or TeX source for each paper used below. The central sources are:

Bukh and Conlon,

Rational exponents in extremal graph theory, arXiv:1506.06406, especially their balanced-rooted-tree construction, lower bound, and $T_{a,b}$ (Definition 1.5 and Lemmas 1.2–1.3).

Kang, Kim, and Liu,

On the rational Turán exponents conjecture, arXiv:1811.06916, especially Proposition 4.2 and Lemma 4.3 (densification).

Jiang and Qiu,

Many Turan exponents via subdivisions, arXiv:1908.02385, especially Theorem 1.2, Corollary 1.4, and Proposition 1.8.

Jiang, Jiang, and Ma,

Negligible obstructions and Turán exponents, arXiv:2007.02975, Corollary 10.

Conlon and Janzer,

Rational exponents near two, arXiv:2203.03375.

Jiang, Longbrake, and Yepremyan,

Rational exponents near $3/2$, arXiv:2607.19607v1, submitted 2026-07-21, especially Theorem 1.7.

The tracker is current as to its March edit, but not as to the literature on the date of this run:

(b) The full Jiang–Qiu Theorem 1.2 is stronger than the simplified

tracker bullet. It proves that \[ 1+\frac{p}{kp+b} \] is a Turán exponent for positive $p,k,b$ with $k\ge b$.

(b) Jiang–Longbrake–Yepremyan (JLY), posted only seven days before this

run, proves that \[ 1+\frac{rt-1}{2rt+2r} \tag{1} \] is a single-graph Turán exponent whenever $t\ge2$ and $r\ge2t+3$. This paper is necessarily absent from the page last edited 2026-03-07.

I also verified the page's other named families against the primary arXiv records: Conlon–Janzer–Lee (arXiv:1903.10631), Jiang–Qiu (arXiv:1905.08994), and Jiang–Ma–Yepremyan (arXiv:1806.02838). Their abstracts state the subdivision and exponent results attributed to them on the tracker.

Exact web/arXiv searches for "18/13" "Turán exponent", `"29/18" "Turán exponent"`, and recent rational-exponent papers found JLY26 but no primary source explicitly treating either fraction. (c) This is only a documented search miss. It is not a novelty claim and is not evidence that no unindexed argument realizes either number.

2. A new corollary obtained by densifying the JLY family

This section is (b): it combines named theorems, with all intervening algebra (a).

Let $T_{r,t}$ be the height-two tree with center $w$, vertices $y_1,\ldots,y_r$, and $t$ leaf children $z_{i,j}$ at every $y_i$. Let $T'_{r,t}$ subdivide every edge once and root it at all $rt$ leaves $z_{i,j}$. It has

u=|V(T'_{r,t})\setminus R|=rt+2r+1,\qquad e=e(T'_{r,t})=2rt+2r. \tag{2}

JLY Theorem 1.7 gives, for every positive $\ell$,

\operatorname{ex}\!\left(n,(T'_{r,t})^\ell_R\right) =O\!\left(n^{\,1+(rt-1)/(2rt+2r)}\right) \tag{3}

when $t\ge2,\ r\ge2t+3$. The paper explicitly interprets this as verifying the Bukh–Conlon conjecture for these rooted subdivisions. Their balancedness and the Bukh–Conlon lower theorem therefore give the matching lower bound for all sufficiently large fixed $\ell$. Notice directly from (2) that

2-\frac{u}{e} =2-\frac{rt+2r+1}{2rt+2r} =1+\frac{rt-1}{2rt+2r},

as required.

Kang–Kim–Liu Lemma 4.3 says that if $2-a/b$ is balancedly realizable, then so is

2-\frac{a}{a+b}. \tag{4}

Their construction $F_*(1)$ adds one new root in each bipartition class, joins it to every nonroot on the opposite side, and deletes all root–root edges. Proposition 4.2 proves that balancedness is preserved and that the rooted density increases by exactly one. Repeating (4) $m$ times proves:

Densified-JLY corollary

For every $t\ge2,\ r\ge2t+3,\ m\ge0$,

\boxed{\quad \gamma_{r,t,m} =2-\frac{rt+2r+1} {\,2rt+2r+m(rt+2r+1)\,} \quad} \tag{5}

is a single-graph Turán exponent. (b)

An explicit rooted template for (5) is obtained from $T'_{r,t}$ by adding $m$ new roots in each bipartition class, each adjacent to all old nonroots in the opposite class. It has

rt+2m\text{ roots},\qquad u=rt+2r+1\text{ nonroots},\qquad e+mu=2rt+2r+m(rt+2r+1)\text{ edges}.

For every sufficiently large fixed $\ell$, its $\ell$-th rooted power is a concrete bipartite witness for (5). Repeating $F_*(1)$ is the same graph as adding the $m$ pairs of roots at once, since root–root edges are deleted.

There is an important effectiveness caveat: the Bukh–Conlon lower theorem provides an existential threshold $\ell_0$, and none of the cited theorem statements supplies a numerical value for this template. Thus (5) is a rigorous single-graph existence theorem and an explicit graph schema, but this report does not name one certified numerical $\ell$.

Smallest useful seed in this run

Take $(r,t)=(11,3)$, which satisfies $11=2\cdot3+5$. Then

rt=33,\quad u=56,\quad e=88,\quad \rho=\frac{88}{56}=\frac{11}{7},

and the $m=0$ exponent is

2-\frac7{11}=\frac{15}{11}.

After one densification the template has 35 roots, 56 nonroots, 91 total vertices, and $88+56=144$ edges. Its density and exponent are

\rho=\frac{144}{56}=\frac{18}{7}, \qquad 2-\frac1\rho=2-\frac7{18}=\frac{29}{18}.

Consequently,

\boxed{\quad 2-\frac7{11+7m}\quad(m\ge0)\quad} \tag{6}

is an infinite sequence of Turán exponents; it begins

\frac{15}{11},\quad \frac{29}{18},\quad \frac{43}{25},\quad \frac{57}{32},\ldots.

The standalone checker constructs both rooted graphs from their edge sets, recomputes their bipartitions, counts, densities, and powers, and checks the seed's balancedness by exact tree dynamic programming. For densification it checks the stronger edge-set identity

\rho_{F_*(1)}(S)=\rho_F(S)+1

simultaneously for every nonempty set of nonroots $S$. These structural checks are (a); the extremal conclusion is (b).

3. Exact denominator-$\le12$ coverage

This section converts the strongest cited theorem statements into exact integer predicates, avoiding a loose search over nonreduced parameters.

Write fractions in lowest terms. For a target $\alpha=1+A/B$, Jiang–Qiu Theorem 1.2 applies exactly when there is an integer $k\ge1$ such that

c=B-kA,\qquad 1\le c\le k. \tag{7}

Indeed, (7) gives their parameters $p=A,b=c$. Conversely, any nonreduced representation has $p=\lambda A$ and $b=\lambda(B-kA)$; the condition $k\ge b$ then implies (7), so scaling cannot create a missed certificate. This equivalence is (a).

For a target deficiency $2-\alpha=A/B$, Jiang–Qiu Corollary 1.4 applies exactly when there are $s\ge1,\ k\ge0$ for which

P=B-sA\ge1,\qquad c=A-kP\ge1,\qquad k\ge c-1. \tag{8}

These are precisely the parameters in

\frac{kp+c}{s(kp+c)+p}=\frac AB

with $p=P$. As above, a common scaling only makes $k\ge c-1$ harder, so (8) loses nothing. This equivalence is (a).

The other exact predicates implemented by the checker are:

KKL: $B\equiv\pm1\pmod A$;
Conlon–Janzer: $B\ge\max\{A,(A-1)^2\}$;
Jiang–Jiang–Ma: with $h=\lfloor B/A\rfloor$, test every possible scale

$\lambda$ satisfying \[ h^3\le\lambda A,\qquad \lambda\big((h+1)A-B\big)\le h+1. \tag{9} \] The second inequality makes this a finite exact search.

For the new JLY family there is also an exact inverse. If $\alpha=1+P/Q<3/2$ is reduced, equality with (1) is equivalent to

r\big((Q-2P)t-2P\big)=Q.

Thus one need only test divisors $d\mid Q$:

r=\frac Qd,\qquad t=\frac{d+2P}{Q-2P}, \tag{10}

and retain integer $t\ge2,\ r\ge2t+3$. A target is a densification lift exactly when, for some $m\ge0$ with $B-mA>A$, the base exponent

2-\frac{A}{B-mA} \tag{11}

passes (10). Equations (7)–(11) are elementary exact equivalences, (a). Their conclusions invoke the corresponding source theorems, (b).

The exhaustive result is:

| reduced denominator $q$ | candidates in $[1,2)$ | gaps before JLY26 | gaps after JLY26 + densification | |---:|---:|:---|:---| | 1 | 1 | none | none | | 2 | 1 | none | none | | 3 | 2 | none | none | | 4 | 2 | none | none | | 5 | 4 | none | none | | 6 | 2 | none | none | | 7 | 6 | none | none | | 8 | 4 | none | none | | 9 | 6 | none | none | | 10 | 4 | none | none | | 11 | 10 | $15/11$ | none | | 12 | 4 | none | none | | total through 12 | 46 | one | none | | 13 | 12 | $18/13$ | $18/13$ |

Here “before JLY26” includes the full Jiang–Qiu theorem, not merely the weaker summary shown on the tracker. Of the 46 fractions through denominator 12, the deterministic certificate selector uses Jiang–Qiu Theorem 1.2 for 32, Jiang–Qiu Corollary 1.4 for 12, the classical exponent $1$ once, and JLY for $15/11$. For the endpoint $1$, take $G=P_3$: a $P_3$-free graph has maximum degree at most one, so its extremal number is $\lfloor n/2\rfloor$. This endpoint check is (a). Therefore:

\boxed{\text{Every rational }\alpha\in[1,2) \text{ of reduced denominator at most }12 \text{ is a Turán exponent.}} \tag{12}

Statement (12) is (b) modulo the named theorems and (d) as a finite machine enumeration. The predicates and the complete enumeration are in the standalone checker. To guard against an error in (10), it separately:

enumerates every allowed pair $(r,t)$ forward;
enumerates every reduced rational and applies the divisor inverse;
verifies equality of the two sets through denominator 200;
repeats the comparison after every possible densification lift.

It found 364 direct JLY values and 900 JLY-or-lift values through that cross-check bound. These two counts are (d) only. No denominator-200 uniform mathematical claim is based on the counts.

4. The first checked-suite wall: $18/13$

The phrase “first wall” here means first by reduced denominator among the theorem families actually audited above. It does not mean that a theorem elsewhere cannot realize $18/13$.

Put

\frac{18}{13}=1+\frac5{13}=2-\frac8{13}.

Every failure below is exact:

In the near-one Jiang–Qiu test (7), $k=1$ gives $c=8>1$ and

$k=2$ gives $c=3>2$; $k\ge3$ makes $c\le-2$.

In the near-two test (8), only $s=1$ is possible, giving $P=5$.

Then $k=0,c=8$ fails, and $k=1,c=3$ fails $1\ge2$.

$13\bmod8=5$, neither $1$ nor $-1=7\bmod8$, so KKL's congruence

family fails.

Conlon–Janzer requires $13\ge(8-1)^2=49$, which fails.
For Jiang–Jiang–Ma, $h=\lfloor13/8\rfloor=1$. At any scale

$\lambda\ge1$, the second condition in (9) is $3\lambda\le2$, which is impossible.

For direct JLY, (10) has $Q-2P=3$ and $d\in\{1,13\}$, giving

$t=11/3$ or $23/3$, neither integral.

A positive densification step would replace the base deficiency by

$8/(13-8)=8/5>1$, outside the exponent interval. Thus (11) gives no lift.

This list is (a) arithmetic; saying that the named results therefore do not certify $18/13$ is (b).

A canonical balanced tree and the exact missing lemma

The required rooted density is

\rho=\frac1{2-18/13}=\frac{13}{8}.

Bukh–Conlon Definition 1.5 gives a canonical balanced rooted tree $T_{8,13}$. Start with a path on eight unrooted vertices. Since $i=13-8=5$, attach six rooted leaves at path positions

1,\ 2,\ 4,\ 5,\ 7,\ 8.

There are $8$ unroots, $6$ roots, and $7+6=13$ edges, so its density is $13/8$. Bukh–Conlon Lemma 1.3 proves it balanced. Independently, the checker enumerates all $2^8-1=255$ nonempty unroot subsets and obtains

\min_{\varnothing\ne S\subseteq V\setminus R} \bigl(8e(S)-13|S|\bigr)=0.

It obtains the same minimum from a separate tree dynamic program. This structural certificate is (a) and (d).

The Bukh–Conlon lower theorem now gives, for every sufficiently large fixed $\ell$,

\operatorname{ex}\!\left(n,(T_{8,13})^\ell_R\right) =\Omega(n^{18/13}). \tag{13}

The exact missing lemma on this canonical route is:

\boxed{\quad \operatorname{ex}\!\left(n,(T_{8,13})^\ell_R\right) =O_\ell(n^{18/13}) \quad} \tag{14}

for at least one $\ell$ at or above the lower-bound threshold. The full Bukh–Conlon conjecture predicts (14) for every positive $\ell$. Proving (14), rather than finding another lower construction, would settle $18/13$ by this route. This reduction is (b).

Why the established spider route cannot have this density

There is also a clean elementary obstruction. Suppose a spider has $s$ legs, total $e$ edges, and all $s$ leaves rooted. It has $e-(s-1)$ unroots. Density $13/8$ would imply

\frac{e}{e-(s-1)}=\frac{13}{8} \quad\Longrightarrow\quad 5e=13(s-1).

Hence $e=13h$ and $s-1=5h$ for some $h\ge1$. Jiang–Qiu Proposition 1.8 says such a rooted spider is balanced exactly when

e\ge(s-1)L,

where $L$ is its longest leg. This forces $L\le2$. But then

e\le2s=10h+2<13h=e,

a contradiction. Therefore no balanced leaf-rooted spider has density $13/8$. This obstruction is (b) only for the quoted characterization and otherwise (a). It identifies why the standard balanced-spider machinery stalls at this fraction.

5. Computation, reproducibility, and cost wall

The standalone verifier is runs/erdos571_wave9q_reverify.py. It uses only the Python standard library and exact fractions.Fraction arithmetic. Its SHA-256 in this run is:

41f422aea7b4519ce37f34a256ba6d3cb65dbfcdcc986ebe552ea5b574bdaf05

Run it from the repository root:

python3 runs/erdos571_wave9q_reverify.py --cross-bound 200 --ell 2

On this VM the final cold command used 0.74 seconds and 21,124 KB peak RSS. Its terminal JSON includes:

"status": "ALL EXACT CHECKS PASSED"
"legacy_gaps_through_12": ["15/11"]
"updated_gaps_through_12": []
"updated_gaps_through_13": ["18/13"]
"direct_jly_values_through_bound": 364
"jly_plus_lift_values_through_bound": 900

From raw edge sets, it also reports:

T'_{11,3}:       vertices=89 roots=33 unroots=56 edges=88
                 density=11/7 exponent=15/11 balance minimum=0
one densification:
                 vertices=91 roots=35 unroots=56 edges=144
                 density=18/7 exponent=29/18
T_{8,13}:        vertices=14 roots=6 unroots=8 edges=13
                 density=13/8 exponent=18/13
                 DP minimum=0, exhaustive-255-subset minimum=0

No heavy computation was run. More brute force is not the missing ingredient: the needed statement (14) is uniform in $n$. Even the $\ell=2$ forbidden graph already has $6+2\cdot8=22$ vertices. Naively enumerating all host graphs on 22 labeled vertices would inspect

2^{\binom{22}{2}}=2^{231}\approx3.45\cdot10^{69}

graphs, about $1.1\cdot10^{53}$ core-years even at $10^9$ graphs per second, and an exact value at $n=22$ would not prove (14). (a) The arithmetic cost estimate is elementary; (c) smarter finite computation may provide experimental guidance, but it cannot supply the missing asymptotic embedding lemma by itself.

6. Scope

(b) The densified-JLY family (5), including $29/18$, follows

rigorously from JLY Theorem 1.7, Bukh–Conlon's lower theorem, and KKL Proposition 4.2/Lemma 4.3.

(b,d) Every reduced rational in $[1,2)$ with denominator at most 12 is

certified by the audited theorem suite.

(b) The canonical $18/13$ route has the lower bound and reduces

exactly to the upper bound (14).

(a,b) No balanced rooted spider can have the needed density $13/8$.
(c) No claim of historical novelty is made for the densified corollary,

and no claim is made that $18/13$ is globally unresolved. The only literature assertion is the documented primary-source search miss.

The general Erdős–Simonovits problem remains open; none of the finite

checks supplies the uniform construction for all rational $\alpha$.

PARTIAL: combining the 2026 JLY theorem with KKL densification proves the family (5), including $29/18$, and certifies all 46 reduced rationals of denominator at most 12; the first gap in the audited suite is $18/13$, reduced to the explicit upper bound (14) for powers of the balanced tree $T_{8,13}$.

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