Erdős #713 — does every bipartite graph have a Turán exponent?

Statement

Is it true that, for every bipartite graph $G$, there exists some $\alpha\in[1,2)$ and $c>0$ such that \[\mathrm{ex}(n;G)\sim cn^\alpha?\] Must $\alpha$ be rational? (Erdős sometimes asked the weaker version with just $\mathrm{ex}(n;G)\asymp n^\alpha$, i.e. dropping the requirement of a matching constant $c$.)

Facts

- Prize $500; status open, and the site's own tooltip states this "cannot be resolved with a finite computation" (erdosproblems.com/713, fetched directly). - Falsifiability: not finite. The claim quantifies over *every* bipartite graph $G$ and *all* sufficiently large $n$; no finite computation on any bounded set of graphs/$n$ can prove or refute it. (A finite computation *could* in principle disprove it by producing, for one specific small $G$, provably non-power-law growth of $\mathrm{ex}(n;G)$ — but no such $G$ is known, and proving non-power-law growth rigorously is itself generally as hard as the asymptotic questions this conjecture is about.) - Origin: a problem of Erdős and Simonovits. Refs: [ErSi70, p.379], [Er74c, p.78], [Er75], [Er78, p.30], [Er81, p.30], [ErSi84], [Er91] (all fetched from erdosproblems.com/bibs/*). - History of the conjecture, verified from Füredi–Simonovits arXiv:1306.5167 (their Conjecture 1.6, read directly): - Erdős [Er67d] originally conjectured something *stronger and false*: that for every bipartite $G$, $\mathrm{ex}(n;G)\sim cn^\alpha$ with $\alpha$ necessarily of the form $1+\frac1k$ or $2-\frac1k$, $k\ge2$ integer. - This was disproved by Erdős & Simonovits [ErSi70]. Füredi–Simonovits (arXiv:1306.5167, p.64, read directly) explain the disproof is *not* via the 3-cube $Q_8$ itself — "there is no good lower bound for the cube: even $\mathrm{ex}(n,Q_8)/n^{3/2}\to\infty$ is not known" (this exact open question is now erdos/576) — but via a more complicated graph family $H(t,\ell)$ (a theta graph $\Theta(3,\ell)$ glued to $K(t,t)$) whose random-graph lower bound and Cube-theorem-style upper bound sandwich $\mathrm{ex}(n,H)$ around exponent $8/5-\epsilon(H)$, giving accumulation points at $2-\tfrac{2}{2t+3}$ that are *not* of the $1+\frac1k,2-\frac1k$ form. - After this, Erdős & Simonovits reformulated the *weaker* conjecture stated on erdosproblems.com/713: exponent exists, possibly any rational in $[1,2)$, no constraint on its form. This is the currently open problem. - Known results / best bounds: - Erdős–Stone–Simonovits gives $\mathrm{ex}(n,G)=O(n^{2-\delta})$ for bipartite $G$ (chromatic number 2), but only via crude arguments; matching lower bounds of the *same* order, let alone a clean limit $\sim cn^\alpha$, are known only for special $G$ (Bukh & Conlon, arXiv:1506.06406, Introduction, read directly). - The conjecture is verified case-by-case only for narrow families: complete bipartite $K_{s,t}$ with $t$ large relative to $s$ (Kővári–Sós–Turán upper bound + Kollár–Rónyai–Szabó / Alon–Rónyai–Szabó norm-graph lower bound, both cited in Bukh–Conlon's intro); $K_{2,2}=C_4$ (Erdős–Klein/Kővári–Sós–Turán, exponent $3/2$, exact constant known, erdosproblems.com/714); $C_6,C_{10}$ via Benson's generalized-quadrangle/hexagon incidence graphs (erdosproblems.com/572, [Be66]); trees and "theta graphs" $\Theta_{m,\ell}$ (exponent $1+1/m$); a handful of "balanced rooted-tree power" families. - The single most classical unresolved sub-case is even cycles: for $C_{2k}$, $k\ge3$, only the upper bound $\mathrm{ex}(n,C_{2k})\ll kn^{1+1/k}$ is known in general (Erdős/Bondy–Simonovits); the matching lower bound $\gg n^{1+1/k}$ (needed to pin down $\alpha=1+1/k$) is *only proved for $k=3,5$* (Benson [Be66]); the best general lower bound (Lazebnik–Ustimenko–Woldar) gives exponent only $1+\frac{2}{3k-3+\nu}$, strictly below the conjectured $1+1/k$ for $k\ge6$ — i.e. it is *open whether $\mathrm{ex}(n,C_{2k})$ even has the conjectured exponent* for most $k$ (erdosproblems.com/572, fetched directly — this is literally problem #713 restricted to $G=C_{2k}$, and it is unsolved). - The hypercube $Q_3$ (cube graph): Erdős–Simonovits [ErSi70] proved $(\tfrac12+o(1))n^{3/2}\le \mathrm{ex}(n,Q_3)\ll n^{8/5}$; whether $\mathrm{ex}(n,Q_3)\asymp n^{8/5}$ (i.e. whether $Q_3$ even has a well-defined exponent) is *itself open* (erdosproblems.com/576, fetched directly) — and $Q_3=Q_8$-graph is the very graph appearing in #713's own reference list [ErSi84]. Best current upper bound for general $Q_k$: Janzer & Sudakov [JaSu22], improving Sudakov & Tomon [SuTo22]. - $K_{r,r}$ lower bound: proved matching for $r=2,3$ (Brown; Erdős–Rényi–Sós), open for $r\ge4$ (erdosproblems.com/714, fetched directly) — this is a special case of exactly the phenomenon #713 asks about in general. - The hypergraph analogue is FALSE, a crucial negative data-point: Frankl & Füredi [FrFu87] (J. Combin. Theory Ser. A, 1987) constructed a 5-uniform hypergraph $H$ on 8 vertices (edges $\{12346,12457,12358\}$) with $\mathrm{ex}(n;H)=o(n^5)$ but $\mathrm{ex}(n;H)\ne O(n^c)$ for any $c<5$ — i.e. $H$ has no exponent at all. Füredi & Gerbner [FuGe21] = arXiv:1906.06657 (abstract fetched via arXiv API) gave a short simplified proof and extended it to every $k$-uniform hypergraph for all $k\ge5$; $k=3,4$ remain open (conjectured also to have no-exponent examples). Füredi–Simonovits (arXiv:1306.5167, §2.7, read directly) confirm this construction crucially uses the Behrend construction (dense subsets of $[N]$ free of 3-term APs) via the Ruzsa–Szemerédi (6,3)-theorem erdos/716, and state explicitly: "for hypergraphs this does not hold... Yet, Erdős and Simonovits conjectured that for ordinary [2-uniform] graphs there is [an exponent]." This is the strongest concrete evidence *against* #713's own conjecture being automatically "safe," and the reason $k=3,4$ hypergraphs remain open is directly germane to whether an analogous graph counterexample to #713 could exist. - Companion/converse problem: erdos/571 — "for every *rational* $\alpha\in[1,2)$, does some bipartite $G$ realize it?" (the existence-of-realizer direction, vs. #713's "does every $G$ have *some* exponent" direction). Kang, Kim, Liu (arXiv:1811.06916, abstract fetched) state precisely: "despite decades of effort, the only known realisable numbers are $0,1,\frac75,2$, and numbers of the form $1+\frac1m,2-\frac1m,2-\frac2m$ for integer $m\ge1$" — i.e. even the *existence* direction is barely scratched; #713 (does EVERY $G$ have an exponent) is strictly harder to attack since it quantifies over all $G$, not just asks for one witness per rational. - Related problems: erdos/571, erdos/572, erdos/576, erdos/714, erdos/716.

Literature state

Not resolved anywhere, confirmed open as of 2026-07-02 (erdosproblems.com/713 direct fetch: status OPEN, problem-status widget shows 0 comments incorporated/no claimed partial solution). The forum thread (erdosproblems.com/forum/thread/713, 2 comments, Aug 2025) contains no attempted resolution — both comments (Zach Hunter, DesmondWeisenberg) are corrections to the page's cross-reference to the Ruzsa–Szemerédi problem erdos/716, not mathematical progress. No AI-system contribution found for #713 specifically (github.com/teorth/erdosproblems wiki "AI-contributions" page returns 404 at the URL checked — could not locate an alternate path in this search).

What the literature *does* establish, precisely delimiting the difficulty: 1. It is not even known, in general, that $\lim \log \mathrm{ex}(n,G)/\log n$ exists for arbitrary bipartite $G$ (this is weaker than what #713 asks — #713 additionally wants the constant $c$ and rationality of $\alpha$). Füredi & Simonovits (arXiv:1306.5167) call the general determination of Turán exponents for bipartite graphs one of the hardest and most persistent open areas in extremal graph theory, citing "lack of good constructive lower bounds" as the central obstruction. 2. The one adjacent conjecture that HAS seen a real breakthrough is the converse/family version erdos/571: Bukh & Conlon (arXiv:1506.06406, JEMS 2018, read in full) proved that for every rational $r\in(1,2)$ there is a finite family $\mathcal{H}_r$ of graphs with $\mathrm{ex}(n,\mathcal{H}_r)=\Theta(n^r)$, via the random algebraic method: take a random low-degree polynomial $f:\mathbb F_q^s\times\mathbb F_q^s\to\mathbb F_q$ and let $G$ join $x,y$ iff $f(x,y)=0$; combined with "rooted tree power" families $T^p_{a,b}$ (unions of $p$ labelled copies of a rooted tree $T_{a,b}$ glued at roots) chosen to be "balanced" (density of every subtree $\ge$ density of the whole tree) so that a matching algebraic lower bound $\Omega(n^{2-1/\rho_T})$ can be proved. Their paper's closing remark states explicitly: solving the conjecture for a single graph $H$ (not a family) — i.e. the flavor of question #713 needs — "even this seems surprisingly difficult, and the only known cases are $a=1$ (complete bipartite graphs) or $b-a=1$ (theta graphs)" (direct quote, read from PDF). 3. Single-graph progress since Bukh–Conlon (all found via arXiv/web search, cross-checked against arXiv API where possible): Kang, Kim, Liu, arXiv:1811.06916, show $2-a/b$ is realisable by a single graph whenever $b>a$, $b\equiv\pm1\pmod a$ — extending, but the abstract itself states the full realisable set is still just $\{0,1,\frac75,2\}\cup\{1+\frac1m,2-\frac1m,2-\frac2m\}$ decades in. Further constructions (Jiang–Qiu [JiQi20]; Jiang–Jiang–Ma [JJM20]) push specific new rational exponents, per erdosproblems.com/571's own literature summary (fetched directly). These all attack the *existence-of-a-realizer* direction (erdos/571), not #713's *every-graph-has-an-exponent* direction — genuine progress on #713 itself (proving existence/rationality for a graph not already known to have one) appears not to exist in the literature surveyed. 4. The technique family behind matching lower bounds for specific $G$ (K_{s,t}, generalized-polygon incidence graphs for $C_6,C_{10}$, norm graphs) is uniformly algebraic/finite-geometric constructions (Kővári–Sós–Turán upper bound + Kollár–Rónyai–Szabó/Alon–Rónyai–Szabó norm graphs, Benson's generalized quadrangles/hexagons — capped at exactly 3 cases by the Feit–Higman finiteness theorem on generalized polygons, which is *why* $C_{2k}$ for general $k$ resists this method). Upper bounds beyond the trivial Erdős–Stone–Simonovits bound generically use dependent random choice (Fox–Sudakov survey, arXiv:0909.3271) or iterated Cauchy–Schwarz/"weakly-norming-graph" arguments controlled via finite reflection groups (Conlon & Lee, "Finite reflection groups and graph norms"; extended by Conlon, Janzer & Lee to subdivisions, per web-search corroboration — full text not independently re-verified here beyond secondary-source description, flagged as lower confidence). 5. The hypergraph disproof machinery (Frankl–Füredi 1987, Füredi–Gerbner 2021, arXiv:1906.06657) is the field's one fully worked example of what a *counterexample* to a rational-exponents-type conjecture looks like, and it runs through the Behrend construction/Ruzsa–Szemerédi (6,3)-theorem erdos/716 — i.e. corner-free/AP-free set constructions producing genuinely non-power-law (quasi-polynomial gap) extremal functions. No one has produced a 2-uniform (graph) analogue, and Füredi–Simonovits explicitly flag that Erdős–Simonovits believed (without proof) that ordinary graphs avoid this pathology.

Attack surface

- Mode: literature-resolution + derivation (primary), NOT finite-search for the $500 question itself. The statement quantifies over all bipartite $G$ and asymptotic $n\to\infty$, so no computation settles it; but finite computation IS a legitimate *exploration* tool for the sub-conjectures (e.g. numerically testing whether $\mathrm{ex}(n,C_{12})$-type data is consistent with exponent $1+1/6$ at accessible $n$, or hunting for a graph analogue of the Frankl–Füredi hypergraph counterexample among small bipartite graphs, which would *disprove* #713 outright if found and proved rigorously). - Concrete first experiment: (1) Pick the smallest genuinely open single-graph sub-case with no known matching bound — e.g. $C_{2k}$ for $k=4$ or $k=6$ (erdosproblems.com/572) or $Q_3$ the cube (erdosproblems.com/576) — and attempt to push the Lazebnik–Ustimenko–Woldar algebraic (Cayley-graph-on-$\mathbb F_q$-based) lower-bound construction closer to $n^{1+1/k}$, since this is a well-scoped, well-precedented construction problem (not a from-scratch derivation). (2) In parallel, attempt to adapt the Bukh–Conlon random-algebraic-method + balanced-tree-power framework (arXiv:1506.06406, full construction reconstructed above) to a *single* rooted tree $T_{a,b}$ with $a\nmid b$ and $b-a>1$ (the acknowledged-hard case per their closing remark) — even a partial/conditional result here (single-graph realizer for one new exponent form) would be a genuine, citable contribution to the companion problem erdos/571 and would sharpen the toolkit relevant to #713. - Oracle: for #713's actual asymptotic claim, no finite oracle exists — only human/peer proof-checking. For the *exploratory* sub-tasks: (a) a claimed matching lower-bound construction for $C_{2k}$/$Q_k$/other specific $G$ is mechanically checkable by exact edge-count verification on the constructed graph family for concrete $q$ (finite-field/algebraic constructions are exact, not asymptotic, and can be brute-force verified for small $q$); (b) a candidate graph counterexample to #713 (no exponent) requires proving *both* an $o(n^{c})$ upper bound and an $\Omega(n^{c'})$-for-all-$c'<c$ lower bound simultaneously — structurally hard to verify even computationally, since it is itself an asymptotic double-sided claim (this is exactly why the hypergraph case [FrFu87]/[FuGe21] required real proof, not search). - Feasibility: famous and hard for the actual $500 question — this is a 50+ year old conjecture (first posed in the 1960s–70s per [Er67d],[ErSi70]) that has resisted the field's best modern tools (random algebraic method, dependent random choice, reflection-group Cauchy–Schwarz, finite geometry) even for single named small graphs like $C_8,C_{12},Q_3$. A realistic non-full-resolution contribution: incremental progress on a *named* open sub-case ($C_{2k}$ general $k$ erdos/572, $Q_k$ erdos/576, $K_{r,r}$ erdos/714, or a new single-graph realizer for erdos/571) is the standard mode by which this literature has advanced (one new rational exponent / one new $k$ at a time) — a full resolution of #713 itself would be a landmark result, not a tractable target for a scoped project.

Related

- erdos/571 — the converse/companion conjecture (does *every* rational $\alpha\in[1,2)$ get *realized* by some bipartite graph?), explicitly cross-linked on erdosproblems.com/713 ("See also [571]") and vice versa; Bukh–Conlon (arXiv:1506.06406) resolved the finite-family version of #571, the field's main breakthrough adjacent to #713. - erdos/572 — even-cycle lower bound $\mathrm{ex}(n;C_{2k})\gg n^{1+1/k}$; the single most classical *named* open instance of #713 (open for all $k\notin\{3,5\}$). - erdos/576 — hypercube Turán number $\mathrm{ex}(n;Q_k)$; whether $Q_3$ has exponent $8/5$ is open, and $Q_3/Q_8$ is literally the graph in #713's own reference [ErSi84] "Cube-supersaturated graphs." - erdos/714 — $\mathrm{ex}(n;K_{r,r})\gg n^{2-1/r}$; the matching-lower-bound instance of #713 for complete bipartite graphs, open for $r\ge4$. - erdos/716 — the Ruzsa–Szemerédi (6,3)-problem; supplies the Behrend-construction technology that makes the *hypergraph* analogue of #713 false (Frankl–Füredi), the field's cautionary precedent. - concept/random-algebraic-method — Bukh/Blagojević–Bukh–Karasev/Bukh–Conlon technique: random low-degree polynomial over $\mathbb F_q$ defining a bipartite graph, used for matching lower bounds on $\mathrm{ex}(n,G)$. - concept/rooted-tree-power-construction — Bukh–Conlon's $T^p_{a,b}$ family construction and the "balanced tree" density condition ($\rho_S\ge\rho_T$ for every subtree $S$) that makes the algebraic lower bound match the upper bound. - concept/norm-graphs-finite-geometry — Kollár–Rónyai–Szabó norm graphs, Alon–Rónyai–Szabó variants, Benson's generalized-quadrangle/hexagon incidence graphs; the finite-geometry toolkit giving exact matching constructions for $K_{s,t}$ ($t$ large) and $C_6,C_{10}$, capped by the Feit–Higman theorem. - Dependent random choice — pick a small random test-tuple, take its common neighborhood; the resulting set is large and almost every small subset of it still has a large common neighborhood, giving a workhorse for embedding sparse/bipartite graphs into dense hosts — standard technique (Fox–Sudakov, arXiv:0909.3271) for proving upper bounds on $\mathrm{ex}(n,G)$ for bipartite/degenerate $G$. - concept/graph-norms-reflection-groups — Conlon–Lee's finite-reflection-group control of iterated Cauchy–Schwarz, extended by Conlon–Janzer–Lee to subdivisions; generates many new provable Turán exponents (secondary-source corroborated, not independently re-verified in full here). - concept/behrend-construction — dense 3-AP-free set construction; via the Ruzsa–Szemerédi (6,3)-theorem it is the mechanism producing the (proved) hypergraph counterexample to the analogue of #713, Frankl–Füredi [FrFu87]/Füredi–Gerbner [FuGe21]=arXiv:1906.06657. - concept/kovari-sos-turan-bound — the classical $\mathrm{ex}(n,K_{s,t})=O(n^{2-1/s})$ upper bound underlying essentially every upper-bound half of a Turán-exponent result in this cluster.