Szemerédi–Trotter theorem

Szemerédi–Trotter theorem
Name	Szemerédi–Trotter theorem
Field	Paul Erdős-style Combinatorics; Discrete geometry
Statement	Incidence bound between points and lines in the plane
First proved	1983
Authors	Endre Szemerédi, William T. Trotter Jr.

Szemerédi–Trotter theorem The Szemerédi–Trotter theorem gives a near-optimal bound on the number of incidences between a finite set of points and a finite set of lines in the Euclidean plane. It was proved by Endre Szemerédi and William T. Trotter Jr. in 1983 and has become central to problems in Paul Erdős-style combinatorial geometry, influencing work by Elekes, Székely, Guth, and Katz.

Statement

Let P be a set of m distinct points and L be a set of n distinct lines in the real plane ℝ^2. The theorem asserts that the number I(P,L) of incidences (point-line containment pairs) satisfies the bound I(P,L) = O(m^{2/3} n^{2/3} + m + n). This quantitative form was established by Endre Szemerédi and William T. Trotter Jr. and is tight up to constant factors via lattice constructions related to work of Paul Erdős and explicit grid examples used by Elekes and József Beck.

History and context

The theorem arose amid a surge of interest in discrete configuration counts in the 20th century, building on combinatorial questions posed by Paul Erdős and structural methods developed by Pál Erdős-adjacent researchers. The 1983 paper by Szemerédi and Trotter unified earlier combinatorial observations with geometric incidence counting. Subsequent context includes applications and connections to results by János Pach, Pankaj Agarwal, Endre Sós, Imre Z. Ruzsa, and computational perspectives from Michael Paterson and Ravi Kannan. The Szemerédi–Trotter bound sharpened prior estimates implicit in work on the Erdős distance problem and on discrete analogues of the Sylvester–Gallai theorem.

Proofs and methods

Original proofs combine combinatorial double-counting and planar graph embeddings, a strategy related to the crossing number inequality used by László Lovász and Miklós Ajtai. Alternative proofs use the polynomial partitioning method pioneered later by László Székely and adapted in higher-dimensional settings by Larry Guth and Katz. Combinatorial proofs draw on extremal graph methods associated with Paul Erdős and incidence decompositions reminiscent of techniques used in the Szemerédi regularity lemma context by Endre Szemerédi. Algebraic approaches exploit polynomial ham-sandwich and partitioning ideas developed by Guth and Katz and applied to planar incidences by Boris Bukh and Joshua Zahl.

Applications

The theorem has wide-ranging consequences across problems studied by Paul Erdős, Elekes, József Beck, and researchers in computational geometry like Bernard Chazelle and Timothy Chan. It yields near-optimal bounds for the number of distinct distances determined by point sets, informs sum-product estimates investigated by Jean Bourgain and Terence Tao, and underpins incidence-based proofs in additive combinatorics tied to Miklós Szemerédi-style results. Algorithmic applications appear in range searching and arrangements work by Pankaj Agarwal and Jeff Erickson. The theorem also impacts discrete harmonic analysis studied by Charles Fefferman and geometric measure theory influenced by Pertti Mattila.

Variants and generalizations

Numerous variants extend the planar result: higher-dimensional incidence bounds studied by Larry Guth and Katz using polynomial partitioning; incidences between points and algebraic curves addressed by György Elekes and Miklós Székely; and incidence theorems over finite fields developed by Jean Bourgain, Alex Iosevich, and Igor Shparlinski. Quantitative improvements for restricted line families relate to results by József Beck and structural decompositions akin to work of Tao and Vu. Other generalizations consider incidences in projective geometries analyzed using methods from Hillel Furstenberg-style combinatorics and connections to Sylvester–Gallai variants studied by Gábor Tardos.

Related problems and bounds

Closely related problems include the Erdős distance problem advanced by Paul Erdős, sum-product estimates by Jean Bourgain and Terence Tao, and combinatorial geometry questions posed by János Pach and Péter Frankl. The crossing number inequality approach ties to graph-theoretic bounds by Székely and extremal graph questions investigated by Paul Erdős and Turán. Tightness constructions use lattice and grid arrangements reminiscent of extremal examples studied by Elekes and Beck, while algebraic lower bounds interact with finite-field incidence results of Bourgain and Iosevich.

Category:Theorems in combinatorial geometry