Kővári–Sós–Turán theorem: the double-counting bound ex(n,K_{s,t}) = O(n^{2-1/s})

Statement

Setup. For a bipartite graph on parts of size $m,n$, the Zarankiewicz function $z(m,n;s,t)$ is the maximum number of edges (equivalently, the max number of 1s in an $m\times n$ 0/1-matrix) such that no $s$ rows and $t$ columns are *all* pairwise connected — i.e. the graph contains no $K_{s,t}$ with the $s$-side in the $m$-part and the $t$-side in the $n$-part. For ordinary (non-bipartite) $n$-vertex graphs, $\mathrm{ex}(n,K_{s,t})$ is the corresponding Turán number: the max edges with no $K_{s,t}$ subgraph at all (Turán number ex(n,H): extremal edge-count for forbidden subgraphs). The two quantities agree up to a factor of $2$: $z(n,n;s,t) \le \mathrm{ex}(2n,K_{s,t})$, etc.

Kővári–Sós–Turán theorem (1954). For all $2\le s\le t$ and all $m,n$: $$z(m,n;s,t) \;<\; (s-1)^{1/t}(n-t+1)\,m^{1-1/t} \;+\; (t-1)m.$$ (en.wikipedia.org/wiki/Kővári–Sós–Turán_theorem; en.wikipedia.org/wiki/Zarankiewicz_problem — both give this exact inequality; note the exponent is $1/t$ against the $m$-side count because of which parameter plays which role, so watch the $s\leftrightarrow t$ convention when citing this bound from different sources.)

In the balanced/symmetric case $m=n$, with $s\le t$ this specializes to the asymptotic form most often quoted and used downstream: $$\boxed{\;\mathrm{ex}(n,K_{s,t}) = z(n,n;s,t) = O\big(n^{2-1/s}\big)\;}$$ with the implied constant depending only on $t$ (indeed only on $s,t$ together). The fully symmetric diagonal case $s=t$ gives $z(n;t) < (t-1)^{1/t}n^{2-1/t} + \tfrac12(t-1)n + 1$, later sharpened in the lower-order term by Znám (1963).

Special case worth memorizing ($s=t=2$, no $K_{2,2}=C_4$): $\mathrm{ex}(n,C_4) = O(n^{3/2})$, in fact $\le \tfrac12\big(1+\sqrt{4n-3}\big)\cdot n/2 \sim \tfrac12 n^{3/2}$, and this exact constant is tight — see Facts.

Facts

- Origin. Kazimierz Zarankiewicz posed the $z(m,n;s,t)$ problem in 1951 (a matrix/incidence question); Tamás Kővári, Vera T. Sós, and Pál Turán proved the bound above "shortly after," published 1954 as "On a problem of K. Zarankiewicz," *Acta Math. Acad. Sci. Hungar.* 3, 50–57. Hyltén-Cavallius (1958) extended the argument to the fully asymmetric $m\ne n$ form. (en.wikipedia.org/wiki/Kővári–Sós–Turán_theorem) - This is literally a Zarankiewicz-problem statement: $\mathrm{ex}(n,K_{s,t})$ for ordinary graphs and $z(n,n;s,t)$ for bipartite host graphs are the same problem up to a factor of 2 in $n$ — KST is simultaneously "the" extremal-graph-theory bound on complete-bipartite-free graphs and "the" combinatorial-matrix bound on all-1s-submatrix-free 0/1 matrices (en.wikipedia.org/wiki/Zarankiewicz_problem; concepts/turan-number.md). - Tightness is a hard open problem in general. Whether $\mathrm{ex}(n,K_{s,t})=\Theta(n^{2-1/s})$ (i.e. whether the exponent $2-1/s$ is *sharp*, not just an upper bound) is known only in special regimes: - $s=t=2$: Reiman (1958) proved $z(n;2) = (\tfrac12+o(1))n^{3/2}$ using the incidence (Levi) graph of a finite projective plane of order $q$ — a $K_{2,2}$-free bipartite graph on $q^2+q+1$ points and $q^2+q+1$ lines with $(q^2+q+1)(q+1)$ incidences — matching the KST upper bound exactly at leading order. The non-bipartite analogue is the Erdős–Rényi polarity graph, used e.g. as the extremal witness in Erdős #552 — Ramsey number R(C4,Sn), dip below n+√n? (Parsons's $R(C_4,S_n)$ upper bound, problems/552.md). - $t > s!$: Kollár–Rónyai–Szabó (1996) and the refinement Alon–Rónyai–Szabó (1999) construct algebraic norm graphs over finite fields $\mathbb F_p^s$ (via the field-norm map) that are $K_{s,t}$-free with $\Omega(n^{2-1/s})$ edges, proving $z(n,n;s,t)=\Theta(n^{2-1/s})$ whenever $t$ is sufficiently large relative to $s$ (specifically $t\ge (s-1)!+1$ in the sharpened Alon–Rónyai–Szabó / Alon–Krivelevich–Sudakov form — see problems/kst-one-sided-degree-turan.md, Facts). (en.wikipedia.org/wiki/Kővári–Sós–Turán_theorem) - For $s$ fixed and $t$ small relative to $s$ (in particular $s=t$ for $s\ge 3$), tightness is OPEN. This is exactly the gap that the Erdős–Simonovits $r$-degenerate bipartite-Turán program (Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$) is trying to close for *general* bipartite $H$, of which $K_{s,t}$ is the founding special case. - KST as the "free baseline" in incidence geometry. Any point set and line set in the plane has an incidence bipartite graph that is automatically $K_{2,2}$-free (two points determine at most one line), so KST alone gives the *generic* bound $I(P,L)=O(n^{3/2})$ for $n$ points and $n$ lines with zero geometry-specific work. The Szemerédi–Trotter theorem's $O(n^{4/3})$ is a genuine improvement obtained only by exploiting that lines in $\mathbb R^2$ are straight (Euclidean convexity), via Székely's crossing-lemma proof — see Incidence geometry: Szemerédi–Trotter theorem, the crossing lemma, and Zarankiewicz-type bounds for the full mechanism. This "compute the KST baseline first, it's free" move generalizes: any incidence problem between $n$ points and $m$ curves with $O(1)$-bounded pairwise intersections is automatically $K_{2,t}$-free for small $t$, so KST supplies an instant generic bound before any geometry-specific argument is attempted. - Generalizes to arbitrary bipartite $H$ via dependent random choice. Alon–Krivelevich–Sudakov (2003) proved $\mathrm{ex}(n,H)=O(n^{2-1/r})$ for *any* bipartite $H$ with max degree $\le r$ on one side (not just $H=K_{r,t}$) — a strictly more general statement that specializes to KST when $H=K_{r,t}$, replacing KST's direct double-count with a probabilistic "dependent random choice" first-moment/alteration lemma (Lemma 2.1 of that paper); see problems/kst-one-sided-degree-turan.md for the full worked proof. This is the standard *first* recombination move when a target bipartite graph is "$K_{s,t}$-like but not literally complete bipartite." - The fully general degenerate-bipartite case is still open. The natural further generalization — replacing "bounded degree on one side" with the strictly weaker "$r$-degenerate" — is the still-open Erdős–Simonovits conjecture Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$ ($500 prize); Erdős #113 — bipartite ex(n,G)≪n^{3/2} iff 2-degenerate: DISPROVED by Janzer 2021 and Erdős #147 — min-degree-$r$ bipartite $H$ forces a Turán lower bound $n^{2-1/(r-1)+\\epsilon}$, adjacent biconditional/converse strengthenings, have both been disproved (Janzer, arXiv:2109.06110 and arXiv:2109.06110-adjacent 2023 IMRN paper). See r-degeneracy — bounded induced-subgraph minimum degree (Lick–White; coloring number, Erdős–Hajnal) for the full landscape. - Recurs as a plug-in double-counting tool outside pure Turán-number questions. T. D. Parsons's 1975 upper bound on the Ramsey number $R(C_4,S_n)$ (Erdős #552 — Ramsey number R(C4,Sn), dip below n+√n?) is exactly a KST-style double-count of paths-of-length-2 bounding the max degree of a $C_4$-free graph, with a matching lower bound from the Erdős–Rényi polarity graph of $\mathrm{PG}(2,q)$ — the *same* projective-plane construction that proves KST tight at $s=t=2$ (problems/552.md).

The proof (double counting + convexity — the reusable engine)

1. Let $G$ be an $n$-vertex, $K_{s,t}$-free graph with $e$ edges and average degree $d=2e/n$. 2. Count "cherries" (or more generally $s$-stars): for each vertex $v$, count the number of $s$-subsets of $N(v)$, i.e. $\binom{\deg(v)}{s}$. Summing over all $v$ counts, for every $s$-subset $S$ of $V(G)$, the number of common neighbors of $S$ — i.e. $$\sum_{v\in V(G)} \binom{\deg(v)}{s} \;=\; \sum_{S\in\binom{V(G)}{s}} |N(S)|.$$ 3. Use $K_{s,t}$-freeness as an upper bound on the right-hand side: if any $s$-subset $S$ had $\ge t$ common neighbors, those $t$ common neighbors together with $S$ would form a $K_{s,t}$. So every $s$-subset has $\le t-1$ common neighbors, giving $$\sum_{v} \binom{\deg(v)}{s} \;\le\; (t-1)\binom{n}{s}.$$ 4. Use convexity (Jensen's inequality) as a lower bound on the left-hand side: $x\mapsto\binom{x}{s}$ is convex, so by Jensen, $\sum_v \binom{\deg(v)}{s} \ge n\binom{d}{s}$ where $d=2e/n$ is the average degree (a sum of a convex function is minimized, subject to fixed total degree $2e$, when all degrees are equal). 5. Combine and solve for $d$: $n\binom{d}{s} \le (t-1)\binom{n}{s}$ gives $d^s/s! \lesssim (t-1)n^{s-1}/s!$ to leading order, i.e. $d = O\big((t-1)^{1/s} n^{1-1/s}\big)$, hence $$e = \tfrac12 nd = O\big(n^{2-1/s}\big)$$ with the constant depending on $s,t$. This is the whole proof — no algebra beyond binomial-coefficient manipulation, no probabilistic or algebraic tools required.

WHEN it applies

whenever a problem reduces to bounding the edges of a graph (or 0/1-entries of a matrix, or incidences between two families of objects) that is known to avoid a complete bipartite pattern $K_{s,t}$ — i.e. avoid "$s$ objects on one side all simultaneously related to $t$ objects on the other side." Canonical trigger phrases: "no two [rows/points/vertices] share $\ge t$ common [columns/lines/neighbors]," "$s$-wise codegree is bounded," "bipartite incidence structure with bounded pairwise intersection." It is the first tool to reach for in the degenerate/bipartite regime of extremal graph theory, i.e. exactly where the Erdős–Stone theorem gives only the trivial $o(n^2)$ (see Turán number ex(n,H): extremal edge-count for forbidden subgraphs).

WHY it works (the mechanism)

the proof needs no structural information about $G$ beyond its degree sequence — it converts a *local* forbidden-pattern hypothesis ("no $s$ vertices share $t$ common neighbors") into a *global* bound on the degree sequence purely via double counting (count the same quantity — $s$-stars — two different ways) plus one application of convexity to pass from "the sum of a convex function of the degrees is small" to "the average degree is small." This is why it is so widely reusable: it needs only (a) a clean combinatorial reformulation of the forbidden pattern as a codegree bound, and (b) the convexity of $\binom{x}{s}$, which is free. The *cost* of this generality is that the bound is often not tight — norm graphs / projective-plane constructions supply matching lower bounds only in restricted parameter regimes (see Facts), and closing that gap for general bipartite $H$ is precisely the content of the still-open Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$.

Recombination recipe (how a solver uses this to prove something new)

1. Encode the target combinatorial object as a bipartite graph or matrix, and identify what "forbidding a $K_{s,t}$" would mean concretely in that encoding (e.g. "two points determine at most one line" $\Rightarrow$ the point–line incidence graph is $K_{2,2}$-free). 2. Apply the double-counting + convexity argument verbatim (steps 1–5 above) to get an instant $O(n^{2-1/s})$ bound — this costs nothing and should always be computed first, even if a sharper geometry- or structure-specific bound is the real goal (see the incidence-geometry "free baseline" pattern in Facts). 3. If the target graph $H$ is bipartite but not literally complete bipartite, check whether $H$ has bounded degree on one side — if so, the Alon–Krivelevich–Sudakov generalization (dependent random choice; problems/kst-one-sided-degree-turan.md) gives the same $O(n^{2-1/r})$ exponent directly, with $r=$ that bounded degree, no need to re-derive from scratch. 4. To assess whether the bound you just got is *tight*, check the parameter regime: $s=t=2$ is settled (projective planes); $t\gg s$ (specifically $t>(s-1)!$) is settled (norm graphs); genuinely small $t$ relative to $s\ge3$ is generally open — treat a mismatch here as the expected shape of an open problem, not a sign of a proof error. 5. When the double-counting bound is not tight and no matching algebraic construction is known, the standard next moves are: escalate to a crossing-lemma argument if the setting is genuinely geometric (Incidence geometry: Szemerédi–Trotter theorem, the crossing lemma, and Zarankiewicz-type bounds), or to dependent random choice / supersaturation for structural improvements (Turán number ex(n,H): extremal edge-count for forbidden subgraphs, r-degeneracy — bounded induced-subgraph minimum degree (Lick–White; coloring number, Erdős–Hajnal)).

Related

- Turán number ex(n,H): extremal edge-count for forbidden subgraphs — the general Turán-number framework $\mathrm{ex}(n,H)$; KST is the founding result of its "degenerate/bipartite" branch ($\chi(H)=2$), where Erdős–Stone gives nothing and KST-style double counting is the primary upper-bound tool. - Incidence geometry: Szemerédi–Trotter theorem, the crossing lemma, and Zarankiewicz-type bounds — treats KST as the free, purely-combinatorial baseline bound that the Szemerédi–Trotter theorem (via Székely's crossing-lemma proof) genuinely improves upon by exploiting Euclidean straightness; also the source of the sum-product and distinct-distances applications built on top of this baseline. - r-degeneracy — bounded induced-subgraph minimum degree (Lick–White; coloring number, Erdős–Hajnal) — the $r$-degeneracy structural parameter that controls the conjectured (often open) generalization of KST's exponent from $K_{s,t}$ to arbitrary bipartite $H$. - Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$ — Erdős–Simonovits conjecture ($500 prize, OPEN) that $r$-degenerate bipartite $H$ forces $\mathrm{ex}(n,H)=O(n^{2-1/r})$; the natural, still-unresolved full generalization of this page's theorem beyond complete bipartite $H$. - Erdős #147 — min-degree-$r$ bipartite $H$ forces a Turán lower bound $n^{2-1/(r-1)+\\epsilon}$ — companion converse-direction conjecture, disproved by Janzer (2023 IMRN, even $r\ge4$ and $r=3$) using KST-adjacent Turán-number machinery. - Erdős #552 — Ramsey number R(C4,Sn), dip below n+√n? — Ramsey number $R(C_4,S_n)$: Parsons's upper bound is a direct KST-style double-count of length-2 paths bounding max degree of a $C_4$-free graph; matching lower bound from the same projective-plane (polarity-graph) construction that proves KST tight at $s=t=2$. - Erdős #86 — C4-free subgraphs of the hypercube density — $C_4$-free subgraph density of the hypercube; a structured/host-graph-restricted variant of the same "$K_{2,2}$-free $\Rightarrow$ few edges" question KST answers for the complete host graph. - Erdős #89 — distinct distances in the plane — Erdős distinct-distances problem; the incidence-geometry lower-bound chain this problem sits in starts from the same KST-style $K_{2,2}$-freeness observation before escalating to Szemerédi–Trotter and the polynomial method. - problems/kst-one-sided-degree-turan.md (solved/kst-one-sided-degree-turan) — Alon–Krivelevich–Sudakov (2003): generalizes this exact theorem from $H=K_{s,t}$ to arbitrary bipartite $H$ with bounded degree on one side, via dependent random choice; explicitly names this page as "the classical $H=K_{r,t}$ special case."