## You are here

HomeSzemer\'edi-Trotter theorem

## Primary tabs

# 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\crn(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. arXiv:CO/0305283, May 2003.

Type of Math Object:

Theorem

Major Section:

Reference

## Mathematics Subject Classification

51A20*no label found*05C10

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections