TheoremStatement: Literature-sourcedProof: 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.

Kővári–Sós–Turán: exact bipartite and ordinary-graph upper bounds for excluding $K_{s, t}$

Statement

For $m, n \in N$ and $s, t \geq 1$ ,

$z (m, n; s, t) \leq (t - 1)^{1 / s} m n^{1 - 1 / s} + (s - 1) n .$

Consequently every $N$ -vertex ordinary graph containing no $K_{s, t}$ satisfies

$e (G) \leq \frac{1}{2} (t - 1)^{1 / s} N^{2 - 1 / s} + \frac{1}{2} (s - 1) N,$

and therefore

$ex (N, K_{s, t}) = O_{s, t} (N^{2 - 1 / s}) .$

For $s = 1$ , the first inequality reads $z (m, n; 1, t) \leq (t - 1) m$ .

Facts & Assumptions

Given: The hypotheses and notation of the statement above.

[F1]

For a bipartite graph with parts of sizes $m, n$ containing no oriented $K_{s, t}$ with its $s$ vertices on the $m$ -side, the common-neighbour count is at most $(t - 1) (\binom{m}{s})$ ; for nonnegative integer degrees of total $E$ with $E / n \geq s - 1$ , smoothing gives the lower bound $n (E / n - s + 1)^{s} / s!$ (The Kővári–Sós–Turán common-neighbour count and the discrete convexity lower bound for degree sums).

[F2]

In $z (m, n; s, t)$ , the $s$ -vertex part of the forbidden $K_{s, t}$ lies on the left and the $t$ -vertex part lies on the right (The Zarankiewicz number $z (m, n; s, t)$ for a forbidden $K_{s, t}$ in a bipartite graph).

[F3]

$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).

Proof

technique · compare the upper and lower common-neighbour counts

1.1

Let $E = e (G)$ in the bipartite problem. If $m = 0$ or $n = 0$ , then $E = 0$ and the first bound is immediate. Assume $m, n \geq 1$ . If $E / n < s - 1$ , the bound is again immediate. Otherwise the preceding lemma gives $n (E / n - s + 1)^{s} / s! \leq (t - 1) (\binom{m}{s}) \leq (t - 1) m^{s} / s!$ . Taking nonnegative $s$ th roots and rearranging yields $E \leq (t - 1)^{1 / s} m n^{1 - 1 / s} + (s - 1) n$ .

givenF1

2.1

For an ordinary $K_{s, t}$ -free graph on $N$ vertices, form a bipartite incidence graph between two copies of its vertex set, joining the left copy of $u$ to the right copy of $v$ exactly when $u v$ is an edge. It is oriented- $K_{s, t}$ -free and has $2 e (G)$ edges. Apply step 1.1 with $m = n = N$ and divide by $2$ .

step 1.1givenF2

3.1

The displayed ordinary bound is $O_{s, t} (N^{2 - 1 / s})$ , since its linear term has no larger order. At $s = 1$ , step 1.1 uses the same algebra and gives the stated exact specialization.

step 1.1step 2.1givenF3∎

Depends on

Used by

Dependency tree · two levels

8 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)

Kővári–Sós–Turán: exact bipartite and ordinary-graph upper bounds for excluding Ks,tKs,t​