Szemerédi–Trotter theorem

The Szemerédi–Trotter theorem bounds the number of incidences between a finite set of points and a finite set of lines in the real plane by a sharp expression in their cardinalities.

Incidence geometry: Incidence geometry studies which points lie on which geometric objects and how many such relationships occur. The theorem is a foundational bound in this broader study of point–line relationships.
Erdős distinct distances problem: The Erdős distinct distances problem asks for the minimum number of different distances determined by a finite planar point set. Incidence bounds help establish lower bounds on distinct distances among planar points.
Endre Szemerédi: Endre Szemerédi is a Hungarian mathematician known for work in combinatorics, number theory, and theoretical computer science. Szemerédi co-authored the 1983 proof that established the incidence bound.
Szemerédi–Trotter incidence bound: The Szemerédi–Trotter incidence bound is the explicit inequality controlling incidences for finite planar point and line sets. This formulation displays the theorem’s two competing terms and its dependence on set sizes.
Crossing number: The crossing number of a graph is the minimum number of edge crossings in any drawing of that graph. The crossing-number inequality is a standard route to the theorem’s incidence bound.
Unit distance problem: The unit distance problem asks how many pairs in a finite planar point set can be exactly one unit apart. Point–circle incidences and related arguments use bounds of Szemerédi–Trotter type.
William T. Trotter: William T. Trotter was an American mathematician whose work included combinatorics and order theory. Trotter co-authored the theorem with Szemerédi.
Kővári–Sós–Turán theorem: The Kővári–Sós–Turán theorem bounds the number of edges in a bipartite graph that excludes a fixed complete bipartite subgraph. Its graph-theoretic bound can estimate incidences, but is generally weaker than the geometric theorem.
Bipartite graph: A bipartite graph has vertices divided into two classes, with edges only between classes. Point–line incidences form a bipartite graph whose edges encode incidences.
Sum-product phenomenon: The sum-product phenomenon says a finite set of numbers cannot have both a small sumset and a small product set. Incidence bounds yield estimates showing additive and multiplicative structure cannot both be too concentrated.

Linked from 5 pages