40.05.02 · combinatorics / extremal-ramsey

Bipartite Extremal Problems: the Kővári-Sós-Turán Theorem

shipped3 tiersLean: none

Anchor (Master): Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) Ch. 7 (the degenerate extremal problem, the Bondy-Simonovits even-cycle bound, the Kővári-Sós-Turán theorem and the cage / incidence connections); Bollobás 1978 *Extremal Graph Theory* (Academic Press) Ch. VI (the Zarankiewicz problem and degenerate extremal numbers); the original sources Kővári-Sós-Turán 1954 (the Zarankiewicz upper bound), Erdős-Rényi 1962 and Brown 1966 (the polarity / projective-plane lower bound for C_4), Kollár-Rónyai-Szabó 1996 and Alon-Rónyai-Szabó 1999 (the norm-graph tightness for K_{s,t}), Bondy-Simonovits 1974 (the even-cycle bound)

Intuition Beginner

Imagine a town where every pair of houses is allowed to share at most one common friend. If two houses both knew the same two people, those four people would form a little rectangle of friendships, and the rule forbids that rectangle. How many friendships can the town hold before some rectangle is forced? This is the gentler cousin of the triangle question from the previous unit. There you forbade a clump where everyone knows everyone; here you forbid a rectangle, a four-cycle, and the answer turns out to be far smaller.

When you forbade a triangle, you could keep about a quarter of all possible friendships. When you forbid a rectangle, you can keep only about the square root of that many per person. The reason is a counting squeeze. Each person's circle of friends produces pairs of friends, and the no-rectangle rule says no pair of townspeople can sit inside two different circles. There are only so many pairs to go around, so nobody's circle can grow too large. The friendships thin out, and the record count grows like $n$ times the square root of $n$ rather than like $n$ times $n$ .

The surprise is that this thin record is essentially achievable. Using a clever map of points and lines — the kind a geometer draws — you can build a network that packs in almost exactly the allowed number of friendships with no rectangle anywhere. So the counting squeeze is not wasteful: it names the true ceiling.

Visual Beginner

Picture seven points and seven lines arranged so that every two points lie on exactly one common line and every two lines meet in exactly one common point. This is the smallest finite "plane." Now build a friendship network: each point becomes a person, and two people are friends when one person's point lies on the line matched to the other. The one-common-line rule turns directly into a no-rectangle rule for the friendships.

The table beside the drawing checks the no-rectangle rule by listing, for each pair of people, how many common friends they share. Every entry is zero or one — never two — so no rectangle of friendships can form.

pair of people	common friends	rectangle?
any two	at most 1	no

Because each pair shares at most one common friend, the count of "friend-pairs inside a single circle" can never reuse the same pair twice. That single constraint is the whole engine of the square-root ceiling.

Worked example Beginner

Count how large a single person's friend-circle can grow in a no-rectangle network on $n = 50$ people, using the pair-counting squeeze. A person with $d$ friends has $(2 d) = d (d - 1) /2$ pairs of friends sitting inside their circle.

Step 1. Set up the squeeze. Every pair of friends inside one person's circle is a pair of people sharing that person as a common friend. The no-rectangle rule says no pair of people sits inside two different circles, so when you add up the pairs across all $50$ circles, you can use each of the available pairs of people at most once.

Step 2. Count the available pairs of people. With $50$ people there are $(2 50) = \frac{50 \times 49}{2} = 1225$ pairs in total.

Step 3. Suppose everyone had the same circle size $d$ . Then the total of in-circle pairs is $50 \times (2 d)$ , and this cannot exceed $1225$ . So $50 \times \frac{d ( d - 1 )}{2} \leq 1225$ , giving $d (d - 1) \leq 49$ .

Step 4. Solve. The largest whole number with $d (d - 1) \leq 49$ is $d = 7$ , since $7 \times 6 = 42 \leq 49$ while $8 \times 7 = 56 > 49$ . So each person can have at most about $7$ friends.

What this tells us: with $50$ people and at most $7$ friends each, the friendship count is at most about $50 \times 7/2 = 175$ — far below the $1225$ pairs available. The ceiling grew like $n$ times the square root of $n$ : here $50 \times 50 \approx 354$ , and our careful count landed below that. Forbidding a rectangle is a much heavier restriction than forbidding a triangle.

Check your understanding Beginner

Formal definition Intermediate+

Fix integers $1 \leq s \leq t$ . The complete bipartite graph $K_{s, t}$ has parts of sizes $s$ and $t$ with every cross pair joined; a graph $G$ contains $K_{s, t}$ when there are disjoint vertex sets $S, T \subseteq V (G)$ with $∣ S ∣ = s$ , $∣ T ∣ = t$ , and every vertex of $S$ adjacent to every vertex of $T$ . Following 40.05.01, the extremal number $ex (n, K_{s, t})$ is the maximum number of edges in a $K_{s, t}$ -free graph on $n$ vertices ^{[Diestel 2017 §7.1]}. Because $χ (K_{s, t}) = 2$ , the Erdős-Stone-Simonovits formula from the prerequisite unit gives only $ex (n, K_{s, t}) = o (n^{2})$ ; the leading term vanishes, and the genuine order of growth is the object of study. This is the degenerate (or bipartite) regime of extremal graph theory.

The matrix form is the Zarankiewicz problem. The function $z (m, n; s, t)$ is the maximum number of $1$ 's in an $m \times n$ zero-one matrix containing no all-ones $s \times t$ submatrix — no choice of $s$ rows and $t$ columns whose intersection is entirely $1$ 's. Reading the matrix as the bipartite adjacency between $m$ "row vertices" and $n$ "column vertices", $z (m, n; s, t)$ is the maximum number of edges in a bipartite graph with parts of sizes $m, n$ that omits $K_{s, t}$ with the $s$ -side in the row part. The general graph problem $ex (n, K_{s, t})$ and the bipartite Zarankiewicz problem $z (n, n; s, t)$ differ by constant factors and share the same counting engine.

The counting engine is the $s$ -star (or $s$ -cherry): a vertex $v$ together with an $s$ -element subset $S \subseteq N (v)$ of its neighbourhood, i.e. an embedded $K_{1, s}$ centred at $v$ . The number of $s$ -stars centred at $v$ is $(s d ( v ))$ , where $d (v)$ is the degree. The $K_{s, t}$ -free condition is exactly a ceiling on how many vertices can share a common $s$ -set as neighbours: no $s$ -set has $t$ or more common neighbours.

Counterexamples to common slips

The bound $O (n^{2 - 1/ s})$ depends on $s$ , the smaller side, not on $t$ . Increasing $t$ only changes the constant: forbidding $K_{2, 100}$ still gives $O (n^{3/2})$ , the same order as forbidding $K_{2, 2} = C_{4}$ . The exponent is set by the side whose stars you count.
$K_{s, t}$ -freeness forbids the subgraph, not the induced subgraph. A graph may contain dense bipartite-looking patches; what is banned is $s$ vertices with $t$ common neighbours, regardless of edges among those $t$ .
The four-cycle $C_{4}$ is $K_{2, 2}$ . The no-rectangle picture and the $K_{2, 2}$ -free condition are the same statement; "two vertices with two common neighbours" is precisely a $C_{4}$ .
Order $o (n^{2})$ does not mean $O (n)$ . The degenerate number sits strictly between linear and quadratic; for $C_{4}$ it is $Θ (n^{3/2})$ , neither sparse nor dense.

Key theorem with proof Intermediate+

Theorem (Kővári-Sós-Turán 1954). For integers $1 \leq s \leq t$ and every $n$ , $$ \operatorname{ex}(n, K_{s,t}) ;\le; \tfrac{1}{2}\Big( (t-1)^{1/s},(n - s + 1), n^{1 - 1/s} + (s-1),n \Big) ;=; \tfrac{1}{2}(t-1)^{1/s}, n^{2 - 1/s} + O(n). $$ (See ^{[Kővári, Sós, Turán 1954]}, ^{[Diestel 2017 §7.1]}, ^{[Bollobás 1978 Ch. VI]}.)

Proof (double-counting $s$ -stars). Let $G$ be $K_{s, t}$ -free on $n$ vertices with $m$ edges and degree sequence $(d (v))_{v \in V}$ . Count incidences $(S, v)$ in which $S$ is an $s$ -element set of vertices and $v$ is adjacent to every vertex of $S$ — equivalently $S \subseteq N (v)$ , an $s$ -star centred at $v$ .

Counting by the centre $v$ , each $v$ contributes $(s d ( v ))$ such pairs, since $S$ ranges over $s$ -subsets of the neighbourhood. So the total is $\sum_{v} (s d ( v ))$ .

Counting instead by the set $S$ : for a fixed $s$ -set $S$ , the vertices $v$ adjacent to all of $S$ are precisely the common neighbours of $S$ . If some $S$ had $t$ or more common neighbours, those $t$ vertices together with $S$ would form a $K_{s, t}$ . Since $G$ is $K_{s, t}$ -free, every $s$ -set has at most $t - 1$ common neighbours, so the total number of pairs is at most $(t - 1) (s n)$ . Combining the two counts, $$ \sum_{v \in V} \binom{d(v)}{s} ;\le; (t-1)\binom{n}{s}. $$ The function $φ (x) = (s x) = \frac{x ( x - 1 ) \dots ( x - s + 1 )}{s !}$ , extended to real $x \geq 0$ and set to $0$ on $[0, s - 1]$ , is convex. By Jensen's inequality applied to the $n$ degrees with average $\overset{ˉ}{d} = \frac{1}{n} \sum_{v} d (v) = \frac{2 m}{n}$ , $$ \frac{1}{n}\sum_{v} \binom{d(v)}{s} ;\ge; \binom{\bar d}{s}, \qquad\text{so}\qquad n\binom{\bar d}{s} ;\le; (t-1)\binom{n}{s}. $$ Now $(s d ˉ) \geq \frac{( d ˉ - s + 1 ) ^{s}}{s !}$ and $(s n) \leq \frac{n ^{s}}{s !}$ , so $n (\overset{ˉ}{d} - s + 1)^{s} \leq (t - 1) n^{s}$ , giving $\overset{ˉ}{d} - s + 1 \leq (t - 1)^{1/ s} n^{1 - 1/ s}$ and hence $\overset{ˉ}{d} \leq (t - 1)^{1/ s} n^{1 - 1/ s} + s - 1$ . Since $m = \frac{1}{2} n \overset{ˉ}{d}$ , $$ m ;\le; \tfrac12 n\Big( (t-1)^{1/s} n^{1-1/s} + s - 1 \Big) ;=; \tfrac12 (t-1)^{1/s} n^{2-1/s} + O(n). \qquad \square $$

Bridge. The Kővári-Sós-Turán bound builds toward the entire degenerate theory of forbidden bipartite subgraphs and appears again in incidence geometry, the cage problem, and the Szemerédi-Trotter point-line bound, because it converts a single local prohibition — no $s$ -set with $t$ common neighbours — into a global cap on average degree by the convexity of the $s$ -star count. The foundational reason the proof works is exactly the averaging principle of the prerequisite Turán argument 40.05.01: where Turán shifted edges toward a balanced multipartite optimum, here Jensen pushes the degree sequence toward its mean, and this is the same convexity that drove the Mantel cherry count. The matching lower bound is dual to the upper bound — the upper bound counts $s$ -stars to cap edges, while the projective-plane and norm-graph constructions engineer incidence structures that saturate the count — and putting these together, the true order of $ex (n, K_{s, t})$ is pinned at $Θ (n^{2 - 1/ s})$ exactly when an algebraic construction meets the counting ceiling. The bridge to the rest of extremal theory is the recognition that the convexity squeeze, not the chromatic number, governs the degenerate regime.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Prove the four-cycle bound $ex (n, C_{4}) \leq \frac{1}{2} (1 + 4 n - 3) \frac{n}{2}$ by carrying the cherry count through exactly (no asymptotic rounding).

Hint

Use $\sum_{v} (2 d ( v )) \leq (2 n)$ and convexity to get $n (2 d ˉ) \leq (2 n)$ , then solve the quadratic in $\overset{ˉ}{d}$ .

Answer

A $C_{4}$ -free graph has every vertex pair with at most one common neighbour, so $\sum_{v} (2 d ( v )) \leq (2 n)$ . By convexity of $x \mapsto (2 x)$ and Jensen with $\overset{ˉ}{d} = 2 m / n$ , $n (2 d ˉ) \leq (2 n)$ , i.e. $n \cdot \frac{d ˉ ( d ˉ - 1 )}{2} \leq \frac{n ( n - 1 )}{2}$ , so $\overset{ˉ}{d}^{2} - \overset{ˉ}{d} - (n - 1) \leq 0$ . The positive root of $x^{2} - x - (n - 1) = 0$ is $\frac{1 + 1 + 4 ( n - 1 )}{2} = \frac{1 + 4 n - 3}{2}$ , so $\overset{ˉ}{d} \leq \frac{1 + 4 n - 3}{2}$ . Then $m = \frac{n d ˉ}{2} \leq \frac{n}{2} \cdot \frac{1 + 4 n - 3}{2} = \frac{1}{2} (1 + 4 n - 3) \frac{n}{2}$ , of order $\frac{1}{2} n^{3/2}$ . Rubric: full credit for the cherry bound, the convexity step, solving the quadratic, and the conclusion.

Exercise 5 (medium, short-answer).

Explain why the Kővári-Sós-Turán exponent depends on $s$ but not on $t$ , and what role $t$ plays.

Hint

Look at where $s$ and $t$ enter the inequality $n (s d ˉ) \leq (t - 1) (s n)$ .

Answer

In $n (s d ˉ) \leq (t - 1) (s n)$ , the binomial $(s \cdot)$ on both sides is a degree- $s$ polynomial, so solving for $\overset{ˉ}{d}$ takes an $s$ -th root: $\overset{ˉ}{d} ≲ (t - 1)^{1/ s} n^{1 - 1/ s}$ . The exponent $1 - 1/ s$ of $n$ comes entirely from the order $s$ of the star being counted; raising $t$ only enlarges the allowed multiplicity per $s$ -set, which scales the constant by $(t - 1)^{1/ s}$ but leaves the power of $n$ fixed. So $s$ — the smaller side, whose neighbourhoods are being subsetted — controls the growth rate, while $t$ controls only the leading constant. Rubric: full credit for identifying the $s$ -th-root mechanism for the exponent and $t$ as the multiplicity setting the constant.

Exercise 6 (medium, short-answer).

Derive the Zarankiewicz bound $z (n, n; 2, 2) \leq \frac{1}{2} (1 + 4 n - 3) n$ for an $n \times n$ zero-one matrix with no all-ones $2 \times 2$ submatrix.

Hint

Let $r_{i}$ be the number of $1$ 's in row $i$ . Count pairs of columns sharing a $1$ in a common row; no column pair is shared twice.

Answer

Let $r_{i}$ be the row sums and $N = \sum_{i} r_{i}$ the total number of $1$ 's. Count pairs $({c, c^{'}}, i)$ where columns $c \neq = c^{'}$ both carry a $1$ in row $i$ : row $i$ contributes $(2 r _{i})$ , so the total is $\sum_{i} (2 r _{i})$ . No all-ones $2 \times 2$ submatrix means no column pair is shared by two rows, so each of the $(2 n)$ column pairs is counted at most once: $\sum_{i} (2 r _{i}) \leq (2 n)$ . By convexity, $n (2 r ˉ) \leq (2 n)$ with $\overset{r}{ˉ} = N / n$ , giving $\overset{r}{ˉ}^{2} - \overset{r}{ˉ} \leq n - 1$ and $\overset{r}{ˉ} \leq \frac{1 + 4 n - 3}{2}$ . Hence $N = n \overset{r}{ˉ} \leq \frac{1}{2} (1 + 4 n - 3) n = O (n^{3/2})$ . Rubric: full credit for the row-pair count, the no-repeat bound, convexity, and the conclusion.

Exercise 7 (hard, short-answer).

Prove the Bondy-Simonovits bound in the case $C_{6}$ : a $C_{6}$ -free graph (no cycle of length exactly $6$ , and assume also $C_{4}$ -free for the clean count) on $n$ vertices has $O (n^{4/3})$ edges, via counting paths of length three (or via the even-cycle / theta-graph argument). Give the counting skeleton.

Hint

For the $C_{2 k}$ bound, count walks/paths of length $k$ from a fixed vertex; a graph of minimum degree $δ$ and girth $> 2 k$ has at least $δ (δ - 1)^{k - 1}$ vertices, forcing $δ = O (n^{1/ k})$ .

Answer

Pass to a subgraph $H$ of minimum degree $δ \geq m / n$ (delete vertices of degree below the average; this loses fewer than $m$ edges, and a standard iteration gives $δ (H) \geq m / n$ ). The Bondy-Simonovits theorem states that a $C_{2 k}$ -free graph has $ex (n, C_{2 k}) \leq \frac{1}{2} ((2 k - 1) n^{1 + 1/ k} + O (n))$ . For $k = 3$ this is $O (n^{4/3})$ . The mechanism: if the girth exceeds $2 k$ , then the breadth-first neighbourhoods $N_{0}, N_{1}, \dots, N_{k}$ of any vertex are pairwise disjoint and each vertex in $N_{i}$ has at least $δ - 1$ neighbours in $N_{i + 1}$ , so $∣ N_{k} ∣ \geq δ (δ - 1)^{k - 1}$ ; since $\sum_{i} ∣ N_{i} ∣ \leq n$ , this forces $δ (δ - 1)^{k - 1} \leq n$ , hence $δ = O (n^{1/ k})$ and $m = O (n^{1 + 1/ k})$ . Forbidding $C_{2 k}$ rather than assuming large girth needs the theta-graph refinement of Bondy-Simonovits: too many length- $k$ paths between a fixed pair force two paths to share only endpoints, creating a $C_{2 k}$ . Rubric: full credit for the minimum-degree reduction, the disjoint-neighbourhood expansion giving $δ = O (n^{1/ k})$ , and the resulting $O (n^{1 + 1/ k})$ with $k = 3$ .

Exercise 8 (hard, short-answer).

Show that the Kővári-Sós-Turán bound is tight in order for $K_{2, 2} = C_{4}$ : construct, from a projective plane of order $q$ , a $C_{4}$ -free graph on $n = q^{2} + q + 1$ vertices with $(\frac{1}{2} + o (1)) n^{3/2}$ edges (the Erdős-Rényi polarity graph). Describe the construction and the edge count.

Hint

Take the points of $P G (2, q)$ as vertices; join two points $x, y$ when $x$ lies on the polar line of $y$ (a symmetric incidence via a polarity). Two points have at most one common neighbour because two lines meet in one point.

Answer

Let $π$ be a projective plane of order $q$ with $n = q^{2} + q + 1$ points and the same number of lines, each line carrying $q + 1$ points and each point on $q + 1$ lines (cross-ref 40.06.03). Fix a polarity $σ$ , a bijection between points and lines reversing incidence with $σ^{2} = id$ ; write $ℓ_{x} = σ (x)$ for the polar line of $x$ . Build the polarity graph $G$ on the $n$ points by joining $x \sim y$ iff $x \in ℓ_{y}$ (equivalently $y \in ℓ_{x}$ , by the polarity). $G$ is $C_{4}$ -free: two distinct points $x, y$ have a common neighbour $z$ iff $z \in ℓ_{x} \cap ℓ_{y}$ , and two distinct lines meet in exactly one point, so there is at most one such $z$ — never the two needed for a $C_{4}$ . Each point $x$ has degree $q + 1$ (the points on $ℓ_{x}$ ), except the $q + 1$ absolute points $x \in ℓ_{x}$ , which lose one; so $∣ E (G) ∣ = \frac{1}{2} ((q + 1) n - (q + 1)) = \frac{1}{2} q (q + 1)^{2} \cdot (1 + o (1))$ . Since $n = q^{2} + q + 1 \sim q^{2}$ , we have $q \sim n^{1/2}$ and $∣ E (G) ∣ \sim \frac{1}{2} n \cdot n^{1/2} = \frac{1}{2} n^{3/2}$ . This matches the Kővári-Sós-Turán upper bound $ex (n, C_{4}) \leq \frac{1}{2} n^{3/2} (1 + o (1))$ , so $ex (n, C_{4}) = (\frac{1}{2} + o (1)) n^{3/2}$ . Rubric: full credit for the polarity-graph definition, the one-common-point $C_{4}$ -free argument, the degree- $(q + 1)$ count, and the asymptotic match.

Advanced results Master

Theorem (Kővári-Sós-Turán, asymptotic form). For fixed $2 \leq s \leq t$ , $ex (n, K_{s, t}) \leq \frac{1}{2} (t - 1)^{1/ s} n^{2 - 1/ s} + O (n)$ , and in particular $ex (n, K_{s, t}) = O (n^{2 - 1/ s})$ . (Kővári-Sós-Turán ^{[Kővári, Sós, Turán 1954]}; Diestel ^{[Diestel 2017 §7.1]}.) The upper bound is the convexity count of the Key theorem. The whole content of the degenerate problem is whether this exponent is correct — whether a matching $Ω (n^{2 - 1/ s})$ construction exists. For $s = 2$ and $s = 3$ it is, by algebraic constructions; for the diagonal $K_{t, t}$ with $t$ growing, the truth is unknown.

Theorem (Erdős-Rényi-Brown; $C_{4}$ exactness). $ex (n, C_{4}) = ex (n, K_{2, 2}) = (\frac{1}{2} + o (1)) n^{3/2}$ . (Erdős-Rényi ^{[Erdős, Rényi 1962]}; Diestel ^{[Diestel 2017 §7.1]}.) The lower bound is the polarity graph of $P G (2, q)$ of Exercise 8: each pair of points has at most one common neighbour because two lines meet in exactly one point, so the incidence axiom of a projective plane is the $C_{4}$ -free certificate. The construction is essentially optimal — Füredi later determined the exact extremal number $ex (n, C_{4}) = \frac{1}{2} q (q + 1)^{2}$ for $n = q^{2} + q + 1$ and $q$ a prime power — matching the cherry-count ceiling to the leading constant $\frac{1}{2}$ .

Theorem (Kollár-Rónyai-Szabó / Alon-Rónyai-Szabó; norm-graph tightness). For every $s \geq 2$ and every $t \geq (s - 1)! + 1$ , $ex (n, K_{s, t}) = Θ (n^{2 - 1/ s})$ . (Kollár-Rónyai-Szabó ^{[Kollár, Rónyai, Szabó 1996]}.) The lower bound is the norm-graph: with $q$ a prime power, take vertices $F_{q^{s}}$ and join $a \sim b$ when the field norm $N (a + b) = 1$ , where $N : F_{q^{s}} \to F_{q}$ is $N (x) = x^{1 + q + \dots + q^{s - 1}}$ . For distinct $b_{1}, \dots, b_{s}$ the system $N (a + b_{i}) = 1$ is a system of $s$ algebraic equations in $a$ whose solution set has size at most $(s - 1)!$ by a resultant / Bézout count, so no $s$ -set has $\geq (s - 1)! + 1$ common neighbours and the graph is $K_{s, t}$ -free for $t > (s - 1)!$ . The construction has $Θ (q^{2 s - 1}) = Θ (n^{2 - 1/ s})$ edges, certifying the Kővári-Sós-Turán exponent is correct in this range. The Alon-Rónyai-Szabó variant lowers the threshold to $t > (s - 1)!$ .

Theorem (Bondy-Simonovits even cycles). For every $k \geq 2$ , $ex (n, C_{2 k}) \leq \frac{1}{2} (2 k - 1) n^{1 + 1/ k} + O (n) = O (n^{1 + 1/ k})$ . (Bondy-Simonovits ^{[Bondy, Simonovits 1974]}.) Forbidding a single even cycle, not the whole bipartite graph, already forces sparsity of order $n^{1 + 1/ k}$ ; the proof passes to a subgraph of large minimum degree and counts paths of length $k$ , where an excess of paths between a fixed pair of vertices builds a $C_{2 k}$ . Matching lower-order constructions are known only for $C_{4}$ , $C_{6}$ , $C_{10}$ — the cage problem, where the incidence graphs of generalised polygons (projective planes, generalised quadrangles, generalised hexagons) supply the extremal girth- $g$ graphs. For other $2 k$ the order is open, the most studied open problem in degenerate extremal theory.

Theorem (incidence-geometry application; Szemerédi-Trotter preview). A set of $P$ points and $L$ lines in the real plane has at most $O ((P L)^{2/3} + P + L)$ incidences. The crude Kővári-Sós-Turán bound already gives $O (P L^{1/2} + L)$ incidences, since the point-line incidence bipartite graph is $K_{2, 2}$ -free (two points determine at most one line). This is weaker than the optimal Szemerédi-Trotter exponent, which needs the cell decomposition or the polynomial method, but it is the entry point: the same $C_{4}$ -free counting that bounds $ex (n, C_{4})$ bounds point-line incidences, and through them the unit-distance and distinct-distances problems of Erdős — the number of unit distances among $n$ points is $O (n^{3/2})$ by exactly the Kővári-Sós-Turán argument applied to the unit-distance graph.

Synthesis. Putting these together, the degenerate extremal number $ex (n, K_{s, t})$ is the meeting point of a single counting ceiling and a family of algebraic constructions, and the central insight is that the convexity of the $s$ -star count caps the average degree at $O (n^{1 - 1/ s})$ while incidence geometry decides whether the cap is reached. The foundational reason the upper bound is uniform — one convexity inequality covering every $K_{s, t}$ — is exactly the reason the lower bound is hard: the bound discards all structure beyond average degree, so certifying tightness demands an explicit incidence object, the projective-plane polarity graph for $s = 2$ and the norm-graph for general $s$ with $t > (s - 1)!$ . This is dual to the dense theory of 40.05.01, where the chromatic number alone pins the leading term and the construction is the routine Turán graph; in the degenerate regime the leading term vanishes and the construction carries all the information. The even-cycle bound generalises the four-cycle count one cycle length at a time, and the cage problem is the same question read as girth, where generalised polygons supply the rare exact extremisers; the bridge from extremal graph theory to incidence geometry, the Erdős distinct-distances problem, and the Szemerédi-Trotter theorem is the recognition that "two points lie on at most one line" is the $K_{2, 2}$ -free hypothesis, so the cherry count is simultaneously a graph theorem and a theorem about points and lines.

Full proof set Master

Proposition 1 (the $s$ -star counting inequality). If $G$ on $n$ vertices is $K_{s, t}$ -free, then $\sum_{v} (s d ( v )) \leq (t - 1) (s n)$ .

Proof. Count incidences $(S, v)$ with $S$ an $s$ -subset of $V$ and $S \subseteq N (v)$ . By centre, $v$ contributes $(s d ( v ))$ , giving the left side. By set, $S$ contributes the number of common neighbours of $S$ ; if this were $\geq t$ for some $S$ , the $s$ vertices of $S$ and $t$ of those common neighbours would span $K_{s, t}$ , against hypothesis. So each $S$ contributes at most $t - 1$ , and there are $(s n)$ choices of $S$ . Equating the two counts gives the inequality. $□$

Proposition 2 (Kővári-Sós-Turán bound). Under the hypothesis of Proposition 1, $m = ∣ E (G) ∣ \leq \frac{1}{2} (t - 1)^{1/ s} n^{2 - 1/ s} + O (n)$ .

Proof. The map $φ (x) = (s x)$ (with $φ (x) = 0$ for $0 \leq x \leq s - 1$ ) is convex on $[0, \infty)$ , being a product of the increasing nonnegative factors $(x - j) / (s - j)$ for $0 \leq j \leq s - 1$ on $x \geq s - 1$ with matching value and derivative at the junction. Jensen on the degrees gives $\sum_{v} φ (d (v)) \geq n φ (\overset{ˉ}{d})$ with $\overset{ˉ}{d} = 2 m / n$ . With Proposition 1, $n (s d ˉ) \leq (t - 1) (s n)$ . Bound $(s d ˉ) \geq (\overset{ˉ}{d} - s + 1)^{s} / s!$ and $(s n) \leq n^{s} / s!$ to get $n (\overset{ˉ}{d} - s + 1)^{s} \leq (t - 1) n^{s}$ , hence $\overset{ˉ}{d} \leq (t - 1)^{1/ s} n^{1 - 1/ s} + s - 1$ . Then $m = \frac{1}{2} n \overset{ˉ}{d} \leq \frac{1}{2} (t - 1)^{1/ s} n^{2 - 1/ s} + \frac{s - 1}{2} n$ . $□$

Proposition 3 (Zarankiewicz bipartite form). $z (m, n; s, t) \leq (t - 1)^{1/ s} (n - s + 1) m^{1 - 1/ s} + (s - 1) m$ , hence $z (n, n; s, t) = O (n^{2 - 1/ s})$ .

Proof. Let $A$ be an $m \times n$ zero-one matrix with no all-ones $s \times t$ submatrix. Count pairs $(R, j)$ where $R$ is an $s$ -subset of rows and column $j$ has a $1$ in every row of $R$ . By column, column $j$ with sum $c_{j}$ contributes $(s c _{j})$ ; by row-set, each $s$ -set $R$ of rows has at most $t - 1$ columns that are all-ones on $R$ (else an all-ones $s \times t$ submatrix), so $\sum_{j} (s c _{j}) \leq (t - 1) (s m)$ . Convexity in the column sums $c_{j}$ (there are $n$ of them, total $N = \sum_{j} c_{j} = z$ ) gives $n (s c ˉ) \leq (t - 1) (s m)$ with $\overset{c}{ˉ} = N / n$ , and solving as in Proposition 2 yields $\overset{c}{ˉ} \leq (t - 1)^{1/ s} m^{1 - 1/ s} + s - 1$ , so $N = n \overset{c}{ˉ} \leq (t - 1)^{1/ s} n m^{1 - 1/ s} + (s - 1) n$ ; symmetrising the roles of $m, n$ gives the stated mixed bound, and $m = n$ yields $O (n^{2 - 1/ s})$ . $□$

Proposition 4 ( $C_{4}$ lower bound; polarity graph). For $q$ a prime power and $n = q^{2} + q + 1$ , there is a $C_{4}$ -free graph on $n$ vertices with $\frac{1}{2} q (q + 1)^{2} - \frac{1}{2} (q + 1) \geq (\frac{1}{2} - o (1)) n^{3/2}$ edges.

Proof. Take the points of $P G (2, q)$ as vertices and fix a polarity $σ$ (e.g. the orthogonal polarity $x \mapsto {y : x^{⊤} y = 0}$ for the standard bilinear form). Join $x \sim y$ iff $x$ is incident to the polar line $σ (y)$ ; by $σ^{2} = id$ and the symmetry of the bilinear form this relation is symmetric. A common neighbour $z$ of distinct $x, y$ satisfies $z \in σ (x) \cap σ (y)$ ; two distinct lines of $P G (2, q)$ meet in exactly one point, so $∣ σ (x) \cap σ (y) ∣ = 1$ and $x, y$ have at most one common neighbour, hence no $C_{4}$ . Each point $x$ is adjacent to the $q + 1$ points of $σ (x)$ , minus $1$ when $x$ is an absolute point ( $x \in σ (x)$ ); there are exactly $q + 1$ absolute points for an orthogonal polarity in odd characteristic. So $∣ E ∣ = \frac{1}{2} ((q + 1) n - (q + 1)) = \frac{1}{2} q (q + 1)^{2}$ . Since $q \sim n^{1/2}$ , this is $(\frac{1}{2} - o (1)) n^{3/2}$ . $□$

Proposition 5 (unit distances). The number of pairs of points at distance exactly $1$ among $n$ points in the plane is $O (n^{3/2})$ .

Proof. Form the unit-distance graph $G$ on the $n$ points, joining two points iff they are at distance $1$ . Two distinct points $p, q$ have at most two common neighbours, since a common neighbour lies on both unit circles centred at $p$ and at $q$ , and two distinct circles meet in at most two points. So $G$ is $K_{2, 3}$ -free. By the Kővári-Sós-Turán bound with $s = 2, t = 3$ , $∣ E (G) ∣ = ex (n, K_{2, 3}) \leq \frac{1}{2} 2 n^{3/2} + O (n) = O (n^{3/2})$ . $□$

Proposition 6 (even-cycle bound, girth form). A graph with minimum degree $δ$ and girth greater than $2 k$ has at least $1 + δ \sum_{i = 0}^{k - 1} (δ - 1)^{i}$ vertices; hence a $C_{2 k}$ -free graph with no shorter even cycle has $δ = O (n^{1/ k})$ and $O (n^{1 + 1/ k})$ edges.

Proof. Fix a vertex $v$ and let $N_{i}$ be the set of vertices at distance exactly $i$ from $v$ . Girth exceeding $2 k$ forces the breadth-first tree to be genuinely tree-like up to depth $k$ : every vertex in $N_{i}$ ( $1 \leq i \leq k - 1$ ) has exactly one neighbour in $N_{i - 1}$ (a second would close a cycle of length $\leq 2 i \leq 2 k$ ), so it has at least $δ - 1$ neighbours in $N_{i + 1}$ , and these are distinct across vertices of $N_{i}$ (a shared neighbour would again close a short cycle). Thus $∣ N_{0} ∣ = 1$ , $∣ N_{1} ∣ = δ$ , and $∣ N_{i + 1} ∣ \geq (δ - 1) ∣ N_{i} ∣$ , giving $\sum_{i = 0}^{k} ∣ N_{i} ∣ \geq 1 + δ \sum_{i = 0}^{k - 1} (δ - 1)^{i} \geq (δ - 1)^{k}$ . Since this is at most $n$ , $δ - 1 \leq n^{1/ k}$ , so $δ = O (n^{1/ k})$ . Passing any graph to a subgraph of minimum degree $\geq m / n$ (iteratively delete below-average-degree vertices) bounds $m / n = O (n^{1/ k})$ , i.e. $m = O (n^{1 + 1/ k})$ ; the Bondy-Simonovits theorem removes the auxiliary girth hypothesis by the theta-graph path count. $□$

Connections Master

Turán and Erdős-Stone-Simonovits 40.05.01. This unit is the degenerate half of the extremal dichotomy proved there: $ex (n, H) = Θ (n^{2})$ when $χ (H) \geq 3$ and $o (n^{2})$ when $χ (H) = 2$ . The convexity squeeze here is the same averaging principle that drove the Mantel cherry count and the Turán symmetrisation, now resolving the regime where the chromatic-number formula returns only a vanishing leading term. The Erdős-Stone embedding lemma even uses a defect form of the Kővári-Sós-Turán count to extract a thick complete multipartite core, so the two units share their analytic engine.
Projective and affine planes, MOLS 40.06.03. The matching lower bound $ex (n, C_{4}) = (\frac{1}{2} + o (1)) n^{3/2}$ is the Erdős-Rényi polarity graph built from a finite projective plane defined in that unit; the incidence axiom "two points determine exactly one line" is the $C_{4}$ -free certificate, and the generalised polygons (quadrangles, hexagons) that supply the rare exact extremisers for $C_{6}$ and $C_{10}$ are the higher analogues of the plane. The cage problem and the bipartite extremal problem are read off the same incidence geometry.
The probabilistic method: first moment and deletion 40.07.01. Where an algebraic construction is unavailable — the diagonal $K_{t, t}$ for large $t$ , or general $C_{2 k}$ — the lower bounds matching the Kővári-Sós-Turán ceiling come from the deletion method developed there: take a random graph of the target density and delete one edge from each forbidden copy. Extremal upper bound and probabilistic lower bound are the two halves of pinning down $ex (n, K_{s, t})$ , and the deletion method is the existence companion to the counting argument here.
The incidence algebra and Möbius inversion 40.02.02. The double-counting of $s$ -stars and the inclusion-exclusion behind the even-cycle and incidence bounds are the same lattice-counting machinery; counting common neighbours of an $s$ -set and sieving forbidden configurations are evaluations of an incidence function, and the convexity (Jensen) steps are the analytic shadow of that combinatorial bookkeeping.
Szemerédi regularity and Ramsey [co-produced 40.05.03, 40.05.04]. The Szemerédi regularity lemma 40.05.03 gives the modern proof of Erdős-Stone and, through the removal lemma, controls the supersaturation of $C_{4}$ and other bipartite graphs above the degenerate threshold; Ramsey theory 40.05.04 is the dual phenomenon where the same incidence and counting constructions that build $C_{4}$ -free graphs also furnish lower bounds for off-diagonal Ramsey numbers.

Historical & philosophical context Master

The degenerate extremal problem was opened by Tamás Kővári, Vera T. Sós, and Pál Turán in their 1954 paper On a problem of K. Zarankiewicz (Colloquium Mathematicum 3) ^{[Kővári, Sós, Turán 1954]}, answering a question Kazimierz Zarankiewicz had posed in 1951 about the maximum number of $1$ 's in a zero-one matrix with no all-ones $s \times t$ submatrix. Their double-counting of $s$ -subsets in neighbourhoods gave the bound $O (n^{2 - 1/ s})$ that still carries the three authors' names and remains the only general upper bound known. The result sits historically just after Turán's own 1941 founding of extremal graph theory, and it marks the moment the subject split into a dense theory governed by the chromatic number and a degenerate theory governed by incidence and algebra.

The lower-bound side developed through finite geometry. Paul Erdős and Alfréd Rényi in 1962 (On a problem in the theory of graphs, Publ. Math. Inst. Hungar. Acad. Sci. 7A) ^{[Erdős, Rényi 1962]}, and independently W. G. Brown in 1966, constructed the polarity graph of a finite projective plane to show $ex (n, C_{4}) = (\frac{1}{2} + o (1)) n^{3/2}$ , matching the $s = 2$ case exactly. The general tightness for $K_{s, t}$ with $t > s!$ waited until the 1996 norm-graph construction of János Kollár, Lajos Rónyai, and Tibor Szabó (Norm-graphs and bipartite Turán numbers, Combinatorica 16) ^{[Kollár, Rónyai, Szabó 1996]}, refined by Noga Alon, Rónyai, and Szabó in 1999 to the threshold $t > (s - 1)!$ . The even-cycle bound $ex (n, C_{2 k}) = O (n^{1 + 1/ k})$ is due to John Adrian Bondy and Miklós Simonovits in 1974 (Cycles of even length in graphs, J. Combin. Theory Ser. B 16) ^{[Bondy, Simonovits 1974]}, and its exact-construction cases coincide with the known generalised polygons of finite geometry — a coincidence that ties extremal graph theory, the cage problem, and the classification of generalised $n$ -gons into a single thread.

Bibliography Master

@book{Diestel2017,
  author    = {Diestel, Reinhard},
  title     = {Graph Theory},
  edition   = {5th},
  series    = {Graduate Texts in Mathematics},
  volume    = {173},
  publisher = {Springer},
  year      = {2017}
}

@book{Bollobas1978,
  author    = {Bollob\'as, B\'ela},
  title     = {Extremal Graph Theory},
  publisher = {Academic Press},
  year      = {1978}
}

@article{KovariSosTuran1954,
  author  = {K\H{o}v\'ari, Tam\'as and S\'os, Vera T. and Tur\'an, P\'al},
  title   = {On a problem of K. Zarankiewicz},
  journal = {Colloquium Mathematicum},
  volume  = {3},
  year    = {1954},
  pages   = {50--57}
}

@article{ErdosRenyi1962,
  author  = {Erd\H{o}s, Paul and R\'enyi, Alfr\'ed},
  title   = {On a problem in the theory of graphs},
  journal = {Publ. Math. Inst. Hungar. Acad. Sci.},
  volume  = {7A},
  year    = {1962},
  pages   = {623--641}
}

@article{Brown1966,
  author  = {Brown, William G.},
  title   = {On graphs that do not contain a Thomsen graph},
  journal = {Canadian Mathematical Bulletin},
  volume  = {9},
  year    = {1966},
  pages   = {281--285}
}

@article{KollarRonyaiSzabo1996,
  author  = {Koll\'ar, J\'anos and R\'onyai, Lajos and Szab\'o, Tibor},
  title   = {Norm-graphs and bipartite Tur\'an numbers},
  journal = {Combinatorica},
  volume  = {16},
  year    = {1996},
  pages   = {399--406}
}

@article{AlonRonyaiSzabo1999,
  author  = {Alon, Noga and R\'onyai, Lajos and Szab\'o, Tibor},
  title   = {Norm-graphs: variations and applications},
  journal = {Journal of Combinatorial Theory, Series B},
  volume  = {76},
  year    = {1999},
  pages   = {280--290}
}

@article{BondySimonovits1974,
  author  = {Bondy, John Adrian and Simonovits, Mikl\'os},
  title   = {Cycles of even length in graphs},
  journal = {Journal of Combinatorial Theory, Series B},
  volume  = {16},
  year    = {1974},
  pages   = {97--105}
}

@article{Furedi1996,
  author  = {F\"uredi, Zolt\'an},
  title   = {New asymptotics for bipartite Tur\'an numbers},
  journal = {Journal of Combinatorial Theory, Series A},
  volume  = {75},
  year    = {1996},
  pages   = {141--144}
}

Prerequisites

40.05.01

Tier anchors

beginner: Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) §7.1 (the degenerate case, forbidding a four-cycle) read for the no-rectangle picture and the square-root growth; West 2001 *Introduction to Graph Theory* (2nd ed., Prentice Hall) §5.2 (the Zarankiewicz problem and the friendship-network reading) for the hand-drawn common-neighbour count; Aigner-Ziegler 2018 *Proofs from THE BOOK* (6th ed., Springer) Ch. on the Kővári-Sós-Turán cherry-counting for the small worked cases
intermediate: Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) §7.1 (the bound ex(n,K_{s,t}) = O(n^{2-1/s}) via the convexity of the s-star count, the four-cycle case ex(n,C_4) and the incidence-geometry lower bound); Bollobás 1998 *Modern Graph Theory* (Springer GTM 184) Ch. IV (degenerate extremal numbers, the Zarankiewicz function z(m,n;s,t)); the original Kővári-Sós-Turán 1954 counting
master: Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) Ch. 7 (the degenerate extremal problem, the Bondy-Simonovits even-cycle bound, the Kővári-Sós-Turán theorem and the cage / incidence connections); Bollobás 1978 *Extremal Graph Theory* (Academic Press) Ch. VI (the Zarankiewicz problem and degenerate extremal numbers); the original sources Kővári-Sós-Turán 1954 (the Zarankiewicz upper bound), Erdős-Rényi 1962 and Brown 1966 (the polarity / projective-plane lower bound for C_4), Kollár-Rónyai-Szabó 1996 and Alon-Rónyai-Szabó 1999 (the norm-graph tightness for K_{s,t}), Bondy-Simonovits 1974 (the even-cycle bound)

References

Diestel 2017 — Graph Theory (5th edition) · Springer Graduate Texts in Mathematics 173, 2017, Ch. 7 (§7.1 the extremal number for bipartite forbidden subgraphs, the Kővári-Sós-Turán bound ex(n,K_{s,t}) = O(n^{2-1/s}), the four-cycle case and the incidence-geometry lower bound, the Bondy-Simonovits even-cycle theorem)
Bollobás 1978 — Extremal Graph Theory · Academic Press, 1978, Ch. VI (the Zarankiewicz problem, the function z(m,n;s,t), degenerate extremal numbers and the Kővári-Sós-Turán theorem)
Kővári, Sós, Turán 1954 — On a problem of K. Zarankiewicz · Colloquium Mathematicum 3 (1954) 50-57; the upper bound z(m,n;s,t) and ex(n,K_{s,t}) = O(n^{2-1/s}) via counting s-subsets in neighbourhoods
Erdős, Rényi 1962 — On a problem in the theory of graphs · Publ. Math. Inst. Hungar. Acad. Sci. 7A (1962) 623-641; the polarity graph of a finite projective plane giving ex(n,C_4) = (1/2 + o(1)) n^{3/2}
Kollár, Rónyai, Szabó 1996 — Norm-graphs and bipartite Turán numbers · Combinatorica 16 (1996) 399-406; the norm-graph construction showing ex(n,K_{s,t}) = Theta(n^{2-1/s}) for t > s!
Bondy, Simonovits 1974 — Cycles of even length in graphs · Journal of Combinatorial Theory Series B 16 (1974) 97-105; ex(n,C_{2k}) = O(n^{1+1/k})

Estimated time

beginner: 18m
intermediate: 50m
master: 90m