# 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 SzemerediTrotterTheorem 2013-03-22 13:21:30 2013-03-22 13:21:30 bbukh (348) bbukh (348) 7 bbukh (348) Theorem msc 51A20 msc 05C10