Szemerédi-Trotter theorem

The number of incidences of a set of $n$ points and a set of $m$ lines in the real plane $\mathbb{R}^{2}$ is

$I=O(n+m+(nm)^{\frac{2}{3}}).$

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 $e\geq 4n$ then by crossing lemma

$m^{2}\geq\operatorname{cr}(G)\geq\frac{1}{64}\frac{(I-m)^{3}}{n^{2}},$

and the theorem follows.

Recently, Tóth[1] extended the theorem to the complex plane $\mathbb{C}^{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