Extremal Graph Theory

Beyond Turán-type problems, extremal graph theory encompasses a wide range of questions about graph parameters under forbidden substructure conditions. This includes Ramsey multiplicity, Zarankiewicz problems, and the study of graph homomorphism densities.

Zarankiewicz Problem

Definition4.9Zarankiewicz Number

The Zarankiewicz number $z(m, n; s, t)$ is the maximum number of ones in an $m \times n$ binary matrix that contains no $s \times t$ all-ones submatrix. Equivalently, it is the maximum number of edges in a bipartite graph with parts of sizes $m$ and $n$ that contains no complete bipartite subgraph $K_{s,t}$ .

Definition4.10Forbidden Bipartite Subgraph

For the Zarankiewicz problem with $s = t$ , the Kovári-Sós-Turán theorem gives $z(n, n; t, t) \leq \frac{1}{2}\left(1 + \sqrt{4n - 3}\right) \cdot n^{1 - 1/t} + \frac{t-1}{2} n.$ More precisely, $\operatorname{ex}(n, K_{s,t}) = O(n^{2 - 1/s})$ for $s \leq t$ , and this bound is known to be tight for $s = 2, 3$ using algebraic constructions.

Szemerédi Regularity

Definition4.11Regular Pair

For disjoint vertex sets $A, B$ in a graph $G$ , the edge density is $d(A, B) = \frac{e(A, B)}{|A| \cdot |B|}$ . The pair $(A, B)$ is $\varepsilon$ -regular if for every $A' \subseteq A$ with $|A'| \geq \varepsilon |A|$ and $B' \subseteq B$ with $|B'| \geq \varepsilon |B|$ , we have $|d(A', B') - d(A, B)| < \varepsilon$ .

ExampleCounting Triangles via Regularity

If $(A, B)$ is $\varepsilon$ -regular with density $d_1$ , $(B, C)$ is $\varepsilon$ -regular with density $d_2$ , and $(A, C)$ is $\varepsilon$ -regular with density $d_3$ , then the number of triangles with one vertex in each part is approximately $d_1 d_2 d_3 |A| |B| |C|$ , with an error that can be bounded in terms of $\varepsilon$ .

RemarkRegularity Lemma Overview

Szemerédi's regularity lemma guarantees that for every $\varepsilon > 0$ , every sufficiently large graph can be partitioned into at most $M(\varepsilon)$ parts such that all but at most $\varepsilon \binom{k}{2}$ pairs of parts are $\varepsilon$ -regular. The function $M(\varepsilon)$ grows as a tower of exponentials, and Gowers showed this tower growth is necessary.

VC Dimension and Extremal Functions

Definition4.12VC Dimension

Let $\mathcal{F} \subseteq 2^X$ be a set family. A set $A \subseteq X$ is shattered by $\mathcal{F}$ if $\{F \cap A : F \in \mathcal{F}\} = 2^A$ . The Vapnik-Chervonenkis (VC) dimension of $\mathcal{F}$ is the maximum cardinality of a shattered set: $\operatorname{VC}(\mathcal{F}) = \max\{|A| : A \subseteq X, \, A \text{ is shattered by } \mathcal{F}\}.$

The Sauer-Shelah lemma states that if $\operatorname{VC}(\mathcal{F}) = d$ , then $|\mathcal{F}| \leq \sum_{i=0}^{d} \binom{|X|}{i}$ . This polynomial bound (as opposed to the exponential $2^{|X|}$ ) has applications throughout combinatorics, computational geometry, and learning theory.

ExampleVC Dimension of Half-Planes

Let $X$ be a finite point set in $\mathbb{R}^2$ and let $\mathcal{F}$ consist of all subsets of $X$ obtained by intersecting with half-planes. Then $\operatorname{VC}(\mathcal{F}) = 3$ , since any 3 points in general position are shattered but no 4 points can be shattered by half-planes.