combinatorics / Graph theory

Erdős Problem #571: rational exponents for bipartite Turán numbers

For every rational α\alpha satisfying 1α<2, 1\le\alpha<2, the Lean theorem constructs some finite qq and a bipartite graph G:SimpleGraph(Finq) G:\operatorname{SimpleGraph}(\operatorname{Fin} q) such that ex(n;G)=Θ(nα) \operatorname{ex}(n;G)=\Theta(n^\alpha) as nn\to\infty. This resolves the single-graph rational-exponents conjecture. Earlier work of Bukh and Conlon proved the corresponding statement only for a finite family of forbidden bipartite graphs, and subsequent work realized many large classes of individual rational exponents. Astra's theorem covers every rational α[1,2)\alpha\in[1,2) with one forbidden graph for each exponent.

52Significance / 100
1Frontier events
0Verification tasks
0Recorded attempts

Temporal state

Current frontier

No reconciled state yet.

Append-only history

Frontier timeline

combinatoricsAug 26, 2026Significance 52/100Registry: lean verified

Erdős Problem #571: rational exponents for bipartite Turán numbers

Prior state unknownproved

For every rational α\alpha satisfying 1α<2, 1\le\alpha<2, the Lean theorem constructs some finite qq and a bipartite graph G:SimpleGraph(Finq) G:\operatorname{SimpleGraph}(\operatorname{Fin} q) such that ex(n;G)=Θ(nα) \operatorname{ex}(n;G)=\Theta(n^\alpha) as nn\to\infty. This resolves the single-graph rational-exponents conjecture. Earlier work of Bukh and Conlon proved the corresponding statement only for a finite family of forbid…

SourceReplayReproducedFormal proofStatement auditExternal checkExpert reviewPeer review

Research memory

Claims and attempts

Scoped claims

Source authenticated

For every rational α\alpha satisfying 1α<2, 1\le\alpha<2, the Lean theorem constructs some finite qq and a bipartite graph G:SimpleGraph(Finq) G:\operatorname{SimpleGraph}(\operatorname{Fin} q) such that ex(n;G)=Θ(nα) \operatorname{ex}(n;G)=\Theta(n^\alpha) as nn\to\infty. This resolves the single-graph rational-exponents conjecture. Earlier work of Bukh and Conlon proved the corresponding statement only for a finite family of forbidden bipartite graphs, and subsequent work realized many large classes of individual rational exponents. Astra's theorem covers every rational α[1,2)\alpha\in[1,2) with one forbidden graph for each exponent.

For every rational α\alpha satisfying 1α<2, 1\le\alpha<2, the Lean theorem constructs some finite qq and a bipartite graph G:SimpleGraph(Finq) G:\operatorname{SimpleGraph}(\operatorname{Fin} q) such that ex(n;G)=Θ(nα) \operatorname{ex}(n;G)=\Theta(n^\alpha) as nn\to\infty. This resolves the single-graph rational-exponents conjecture. Earlier work of Bukh and Conlon proved the corresponding statement only for a finite family of forbidden bipartite graphs, and subsequent work realized many large classes of individual rational exponents. Astra's theorem covers every rational α[1,2)\alpha\in[1,2) with one forbidden graph for each exponent.

Recorded attempts

Evidence graph

Connected research record