False statementConstruction: AI-adaptedVerification: AI-adaptedprecheck passaudited 2026-08-13

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Erdős–Stone–Simonovits determines the extremal number for every graph

False Statement

Erdős–Stone–Simonovits by itself determines $ex (n, H)$ , even up to its order of growth, for every finite graph $H$ with an edge.

Facts & Assumptions

Given: The hypotheses and notation of the statement above.

[F1]

The complete bipartite graph $K_{A, B}$ has exactly all edges joining a vertex of $A$ to a vertex of $B$ (Empty and complete graphs, complete bipartite graphs, and the convention that $P_{n}$ and $C_{n}$ have $n$ vertices).

[F2]

A proper $k$ -vertex-colouring is a map $c : V \to k$ with $c (u) \neq c (v)$ for every edge ${u, v}$ , its fibres are the colour classes, and $χ (G) = \min {k \in N : G is k -colourable}$ (Proper vertex colourings and chromatic number).

[F3]

If $H$ is a finite graph with an edge and $r = χ (H)$ , then $ex (n, H) = (1 - 1 / (r - 1) + o (1)) (\binom{n}{2})$ (Erdős–Stone–Simonovits: $ex (n, H) = (1 - 1 / (χ (H) - 1) + o (1)) (\binom{n}{2})$ for every graph with an edge).

[F4]

For $s, t \geq 1$ , the Kővári–Sós–Turán theorem gives $ex (N, K_{s, t}) = O_{s, t} (N^{2 - 1 / s})$ (Kővári–Sós–Turán: exact bipartite and ordinary-graph upper bounds for excluding $K_{s, t}$ ).

[F5]

$f = O (g)$ means an eventual constant upper bound, $f = o (g)$ means $f / g \to 0$ , and subscripts permit the constants and thresholds to depend on those parameters (Edge density and the asymptotic notations $O$ , $o$ , $Ω$ , and $Θ$ for extremal functions).

Refutation

technique · compare the quadratic-density conclusion with a sharper local bound

1.1givenF1F2F3F5

The graph $K_{2, 2}$ is bipartite, so $χ (K_{2, 2}) = 2$ . Applied to it, Erdős–Stone–Simonovits says only $ex (n, K_{2, 2}) = o (n^{2})$ .

1.2givenF4F5

The separate common-neighbour theorem gives the strictly sharper upper bound $O (n^{3 / 2})$ . Neither statement supplies a matching lower bound here, but the improvement already shows that the Erdős–Stone–Simonovits conclusion alone does not determine even the relevant subquadratic scale.

2.1step 1.1step 1.2∎

Therefore the claimed universal determination is false. Erdős–Stone–Simonovits determines the leading quadratic density, not every lower-order extremal problem.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

19 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Yufei Zhao, Graph Theory and Additive Combinatorics (standard reference, not scraped)