Incidence geometry: Szemerédi–Trotter theorem, the crossing lemma, and Zarankiewicz-type bounds

Statement

Incidence geometry studies how large a set of *incidences* (point-lies-on-curve type relations) can be between a set of $n$ points and a set of $m$ "simple" curves (lines, circles, etc.) in the plane (or higher dimensions), given that any two of the curves meet in a bounded number of points. The field's three interlocking core tools:

1. Szemerédi–Trotter theorem (1983). For $n$ points and $m$ lines in $\mathbb R^2$, the number of incidences $I(P,L)$ satisfies $$I(P,L) = O\!\left(n^{2/3}m^{2/3} + n + m\right).$$ When $n=m$ this is $O(n^{4/3})$. The bound is tight: taking $P=\{(a,b)\in\mathbb Z^2: 1\le a\le N,\ 1\le b\le 2N^2\}$ and $L=\{(x,mx+b): m,b\in\mathbb Z,\ 1\le m\le N,\ 1\le b\le N^2\}$ gives $|P|=2N^3$, $|L|=N^3$, each line hits $N$ points of $P$, for $I=N^4$ — exactly matching the upper bound (en.wikipedia.org/wiki/Szemerédi–Trotter_theorem). Equivalent $k$-rich-line corollary: the number of lines through $\ge k$ points of an $n$-point set is $O(n^2/k^3 + n/k)$.

2. The crossing lemma (crossing number inequality; Ajtai–Chvátal–Newborn–Szemerédi 1982, independently Leighton 1983). For a simple graph $G$ drawn in the plane with $n$ vertices and $e$ edges, $e\ge 4n$ $\Rightarrow$ the crossing number $\operatorname{cr}(G)\ge e^3/(64n^2)$ (classical form). Refinements sharpen the constant: $\operatorname{cr}(G)\ge e^3/(33.75n^2)$ for suitable thresholds, and the current best known constant is $\operatorname{cr}(G)\ge e^3/(29n^2)$ for $e>7n$ (Ackerman), per en.wikipedia.org/wiki/Crossing_number_inequality. The lemma is itself an easy corollary of $\operatorname{cr}(G)\ge e-3n$ (Euler's formula, valid for any planar-drawable simple graph) applied to a random edge-subsample.

3. Zarankiewicz problem / Kővári–Sós–Turán (KST) theorem (1954). $z(m,n;s,t)$ = the max edges in a bipartite graph on parts of size $m,n$ with no $K_{s,t}$ subgraph. KST bound: $$z(m,n;s,t) < (s-1)^{1/t}(n-t+1)m^{1-1/t} + (t-1)m,$$ giving $z(n,n;s,t)=O(n^{2-1/s})$ for $s\le t$ (en.wikipedia.org/wiki/Zarankiewicz_problem). For $s=t=2$ (the "no $K_{2,2}$" / no-repeated-pair case) this is $O(n^{3/2})$, and it is tight for $z(n;2)$: $(\tfrac12+o(1))n^{3/2}$, realized by point–line incidence graphs of finite projective planes of order $q$ ($n=q^2+q+1$). Recent work extends this to the unbalanced regime, e.g. $z(m,n;2,t)=(1+o(1))mn^{1/2}$ for $m\approx n^{t/2}$.

How the three fit together: any point set and line set has an incidence bipartite graph that is automatically $K_{2,2}$-free (two points determine at most one line, so two lines share at most one point) — so KST alone already gives the *generic* bound $I(P,L)=O(n^{3/2})$ for $n$ points and $n$ lines. Szemerédi–Trotter's $O(n^{4/3})$ is a genuine improvement over the generic $K_{2,2}$-free bound, obtained only by using the extra structure that lines in $\mathbb R^2$ are straight (Euclidean convexity / cell-decomposition structure), not just the abstract combinatorial no-$K_{2,2}$ constraint. Székely's proof makes this improvement mechanical via the crossing lemma (a purely graph-theoretic tool) — see Technique below.

Facts

- Two independent proofs of Szemerédi–Trotter. The 1983 original (Szemerédi–Trotter) used cell decomposition: partition $\mathbb R^2$ into $O(r^2)$ cells via $O(r)$ well-chosen lines so each cell meets only $O(m/r)$ of the remaining lines, then recurse/optimize over $r$ — a combinatorial partitioning technique (Clarkson–Edelsbrunner–Guibas–Sharir–Welzl 1990 gave a cleaner version), and it is genuinely combinatorial/probabilistic, not algebraic (terrytao.wordpress.com/2009/06/12, direct fetch). The 1997 Székely proof via the crossing lemma is much shorter and gives explicit constants (started at 2.5, later improved toward 2.44 as crossing-lemma constants improved) — this is now the standard textbook proof. - The Euclidean-convexity dependence is essential and a hard boundary, not incidental: the $O(n^{4/3})$ bound genuinely fails to hold uniformly over finite fields $\mathbb F_q$ (Tao's post, direct fetch) — this is exactly why finite-field incidence problems (e.g. the finite-field Kakeya problem) need the *polynomial method* rather than a direct transfer of Szemerédi–Trotter; see Polynomial method / slice rank (Croot-Lev-Pach, Ellenberg-Gijswijt). - Székely's crossing-lemma proof, step by step: build a plane graph $G$ with vertex set $P$ (the $n$ points) and an edge between two points iff they are *consecutive* along one of the $m$ lines. Then $|E(G)| = I(P,L) - m$ (each line with $k_i\ge1$ incident points contributes $k_i-1$ edges). $G$ is drawn with no crossings other than where two of the original lines cross, so $\operatorname{cr}(G)\le \binom{m}{2}$. Case split: if $e\le 7.5n$ (or the relevant crossing-lemma threshold), $I=e+m=O(n+m)$ directly; otherwise the crossing lemma forces $e^3/(64n^2) \le \binom m2 = O(m^2)$, i.e. $e=O(n^{2/3}m^{2/3})$, so $I=O(n^{2/3}m^{2/3}+m)$. Combine the two cases. - Sum-product application (Elekes 1997). For a finite $A\subset\mathbb R$, $|A+A|+|A\cdot A| \gg |A|^{5/4}$ (the Erdős–Szemerédi sum-product conjecture, still open at the optimal exponent $2-o(1)$). Elekes's proof: take $P = (A+A)\times(A\cdot A)$ and the $|A|^2$ lines $\ell_{a,b}(x) = a(x-b)$ for $a,b\in A$; each such line passes through the $|A|$ points $\{(a c+ (\text{shift}), \dots)\}_{c\in A}$ lying in $P$ by construction, so $I(P,L)\ge |A|^3$; Szemerédi–Trotter forces $|P|=|A+A|\,|A\cdot A|$ to be large enough to support that many incidences, giving the $5/4$ exponent after optimizing. This is the canonical worked example of "encode an algebraic quantity as a line-incidence count." - Unit-distance application (Spencer–Szemerédi–Trotter 1984). The analogous incidence bound for points vs. *unit circles* (rather than lines) — using the same no-$K_{2,3}$-style combinatorial argument (two unit circles meet in $\le2$ points) plus a Szemerédi–Trotter-style argument — gives the classical upper bound $O(n^{4/3})$ on the number of unit-distance pairs among $n$ planar points (Erdős's unit-distance problem, Erdős #90 — the unit distance conjecture (disproved 2026)-adjacent), unimproved in exponent for over 40 years until a 2026 disproof of a *related* strengthened conjecture via an unrelated algebraic-number-theoretic construction (Ellenberg–Venkatesh / Golod–Shafarevich towers), per wiki/problems/97.md. - Beck's theorem (on collinear points / how many distinct lines a non-collinear point set spans) also has a short crossing-lemma-based proof via Székely's method (en.wikipedia.org/wiki/Crossing_number_inequality, direct fetch). - Distinct-distances chain: the pre-Guth–Katz lower-bound history for Erdős #89 — distinct distances in the plane runs through this exact toolkit — Chung–Szemerédi–Trotter, Székely, Solymosi–Tóth, Tardos, culminating in Katz–Tardos's $n^{0.8641\ldots}$ (entropy-inequality refinement of the incidence-counting chain) — per wiki/problems/604.md and wiki/problems/89.md, which both cite Incidence geometry: Szemerédi–Trotter theorem, the crossing lemma, and Zarankiewicz-type bounds directly for this lineage. - Crossing-number method vs. polynomial method, by regime: wiki/problems/661.md documents a clean empirical lesson — for the *unbalanced* bipartite distinct-distances problem $D(m,n)$ with $m\le n^{1/3}$, Székely's elementary crossing-number method alone already achieves the tight answer $\Theta(\sqrt{mn})$ (Mathialagan 2019, arXiv:1912.01883); only in the balanced/diagonal regime $m\approx n$ is the heavier Guth–Katz polynomial method needed, and even then it only closes the gap up to a $\log n$ factor. This is a reusable regime-selection heuristic: try the crossing lemma first (cheap, often already tight in unbalanced regimes); escalate to the polynomial method only when it is not. - Unbalanced Zarankiewicz problems remain an active research area connecting directly back to incidence geometry: per the abstract of "A survey of Zarankiewicz problems in geometry" (arxiv.org/abs/2410.03702, fetched), "incidence geometry... can be viewed as a manifestation of Zarankiewicz's problem in geometrically defined graphs" — i.e. every incidence bound between points and some family of curves/surfaces is, at the combinatorial-graph level, an instance of asking for $\operatorname{ex}(n,K_{t,t})$ (or its unbalanced/geometric-graph variant), with the geometry supplying extra structure (semialgebraic, convex, low-degree) that beats the generic KST bound — the same mechanism as the Szemerédi–Trotter-over-KST improvement above, generalized.

Technique

How to apply this toolkit to a new incidence/counting problem (the reusable derivation recipe):

1. Phrase the target quantity as an incidence count $I(P,L)$ between a point set $P$ and a family $L$ of "simple" curves — the harder part of "recombination" is choosing *which* auxiliary points and curves encode your combinatorial object (Elekes's sum-product construction, Mathialagan's bipartite-distance construction, and the Elekes–Sharir rigid-motion reduction used by Guth–Katz Erdős #89 — distinct distances in the plane are the three canonical templates for this step). 2. Check the pairwise-intersection bound. If any two members of $L$ meet in $O(1)$ points (true for lines, unit circles, low-degree algebraic curves), the incidence bipartite graph is automatically $K_{2,t}$-free for small $t$ — this alone, via KST, gives a *generic* bound $I=O(n^{2-1/s})$ with no geometry-specific work at all. Always compute this baseline first — it is free. 3. Try to beat KST with the crossing lemma (Székely's method). Build the "consecutive points on a curve" graph, bound its edge count by $I-|L|$, bound its crossing number by $\binom{|L|}2$ (curve-pairs cross $O(1)$ times each), and invoke $\operatorname{cr}(G) \ge e^3/(cn^2)$. This mechanically recovers Szemerédi–Trotter's $O(n^{2/3}m^{2/3}+n+m)$ whenever the curve family has $O(1)$-bounded pairwise crossings and admits a planar-ish drawing — it is the "cheap tool," often already optimal in unbalanced parameter regimes (see Facts, #661 lesson). 4. If the crossing lemma is not tight (typically in the balanced/diagonal regime, or for higher-dimensional/algebraic curve families), escalate to the polynomial method: polynomial ham-sandwich cell decomposition + algebraic zero-set arguments (Guth–Katz), which exploits the *algebraic* structure of the curve family beyond just pairwise-intersection counts — see Polynomial method / slice rank (Croot-Lev-Pach, Ellenberg-Gijswijt). This is strictly more powerful but costs a $\log$-factor loss relative to conjectured-tight bounds in several open cases (Erdős #89 — distinct distances in the plane, Erdős #661 — bipartite distinct-distances o(n/√log n) question is OPEN ($50); the underlying two-set function D(m,n) is SOLVED up to a log factor (Elekes construction 1995/1999, matching lower bounds by Mathialagan 2019)). 5. For genuinely unbalanced point/curve-family sizes, check whether a sharper *unbalanced* Zarankiewicz-type bound (rather than the symmetric KST form) is already known for your specific forbidden-subgraph pattern — recent work (2024–2026) has pushed unbalanced bounds like $z(m,n;2,t)=(1+o(1))mn^{1/2}$ well beyond the naive symmetric KST specialization.

WHEN it applies: whenever a combinatorial quantity can be re-encoded as "how many times can $n$ points lie on $m$ curves from a family with bounded pairwise intersection." Classic transfer targets: sums/products of real sets (sum-product), distances between point sets (distinct/unit/bipartite distances), collinearity/richness statistics (Beck's theorem, $k$-rich lines, Erdős #588 — are $k$-rich lines $o(n^2)$ for $k\geq 4$?), Ramsey-type constructions via generalized-polygon incidence graphs (Erdős #159 — polynomial improvement to R(C4,Kn) upper bound, Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$), and forbidden-subgraph Turán-type extremal graph theory whenever the extremal graph can be realized geometrically (Erdős #86 — C4-free subgraphs of the hypercube density).

WHY it works (the mechanism): the crossing lemma converts "this graph has many edges" into "this graph, however it's drawn in the plane, must have many crossings" purely from Euler's formula ($e\le 3n$ for planar simple graphs $\Rightarrow$ any denser graph must cross itself a lot when forced into the plane) — an extremal-topology fact with *no* reference to the specific geometric meaning of the vertices/edges. Székely's insight is that a point-line incidence structure's "consecutive pairs" graph is drawn with a crossing count that is *externally* capped by $\binom{m}2$ (curves cross each other $O(1)$ times), so the crossing lemma's *lower* bound on crossings and the geometric problem's *upper* bound on crossings sandwich the edge count $e$ (hence $I$) into a tight range — the same two-sided-sandwich pattern as the polynomial method (cf. Polynomial method / slice rank (Croot-Lev-Pach, Ellenberg-Gijswijt)'s slice-rank sandwich), but the two bounding facts here are topological (Euler's formula) rather than algebraic (degree/monomial counts).

Related

- Polynomial method / slice rank (Croot-Lev-Pach, Ellenberg-Gijswijt) — the algebraic escalation when crossing-lemma/KST bounds are not tight (Guth–Katz cell decomposition via polynomial ham-sandwich); also the reason incidence bounds over finite fields need a genuinely different mechanism than Szemerédi–Trotter. - Erdős #89 — distinct distances in the plane — Erdős distinct-distances problem; the classical incidence-geometry lower-bound chain (Chung–Szemerédi–Trotter → Székely → Solymosi–Tóth → Katz–Tardos) that this concept underlies, superseded up to $\log$ factors by the polynomial method. - Erdős #604 — pinned distinct-distances at a single point — pinned distinct-distances; still stuck at the pre-polynomial-method Katz–Tardos $n^{0.8641\ldots}$ incidence-geometry bound because the Guth–Katz technique does not localize. - Erdős #661 — bipartite distinct-distances o(n/√log n) question is OPEN ($50); the underlying two-set function D(m,n) is SOLVED up to a log factor (Elekes construction 1995/1999, matching lower bounds by Mathialagan 2019) — bipartite distinct distances; documents the concrete regime-split lesson "crossing lemma tight for unbalanced $m$, polynomial method needed (with $\log$-loss) for balanced $m\approx n$." - Erdős #588 — are $k$-rich lines $o(n^2)$ for $k\geq 4$? — collinear-triple / $k$-rich-line counting; the direct Szemerédi–Trotter $k$-rich-line corollary $O(n^2/k^3+n/k)$ is the standard but (for fixed $k$) insufficient tool, motivating Elekes–Szabó-type escalations. - Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$, Erdős #159 — polynomial improvement to R(C4,Kn) upper bound — Turán/Ramsey-type extremal-graph problems where recent breakthroughs use Zarankiewicz-problem-style incidence graphs of generalized polygons (finite-geometry constructions) as the extremal/lower-bound witnesses. - Erdős #86 — C4-free subgraphs of the hypercube density — hypercube Turán problem, contrasted against the dense-host Kővári–Sós–Turán/Zarankiewicz extremal analogue.