Szemerédi-Trotter theorem


The number of incidences of a set of n points and a set of m lines in the real plane 2 is

I=O(n+m+(nm)23).

Proof. Let’s consider the points as vertices of a graph, and connect two vertices by an edge if they are adjacent on some line. Then the number of edges is e=I-m. If e<4n then we are done. If e4n then by crossing lemma

m2cr(G)164(I-m)3n2,

and the theorem follows.

Recently, Tóth[1] extended the theorem to the complex planeMathworldPlanetmath 2. The proof is difficult.

References

  • 1 Csaba D. Tóth. The Szemerédi-Trotter theorem in the complex plane. http://www.arxiv.org/abs/math.CO/0305283arXiv:CO/0305283, May 2003.
Title Szemerédi-Trotter theorem
Canonical name SzemerediTrotterTheorem
Date of creation 2013-03-22 13:21:30
Last modified on 2013-03-22 13:21:30
Owner bbukh (348)
Last modified by bbukh (348)
Numerical id 7
Author bbukh (348)
Entry type Theorem
Classification msc 51A20
Classification msc 05C10