# 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 $$ then we are done. If $e\ge 4n$ then by crossing lemma

$${m}^{2}\ge \mathrm{cr}(G)\ge \frac{1}{64}\frac{{(I-m)}^{3}}{{n}^{2}},$$ |

and the theorem follows.

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