8
$\begingroup$

Szemerédi–Trotter theorem asserts that given $n$ points and $m$ lines in the plane, the number of incidences (i.e., the number of point-line pairs, such that the point lies on the line) is:

$O((mn)^{\frac{2}{3}}+m+n).$

I was wondering how many different proofs are known for this theorem? Is there any survey or references for these proofs? I know there are two proofs here https://www.cs.princeton.edu/~zdvir/papers/Dvir-survey.pdf

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

I can think of at least three proofs:

  1. The original cell decomposition proof of Szemerédi-Trotter

  2. The proof via the Crossing Lemma given by Székely

  3. The proof using the polynomial ham sandwich theorem

Adam Sheffer has an early draft of a book on incidence theory and the polynomial method, which mentions all three proofs.

Improve this answer
$\endgroup$
2
  • $\begingroup$ The two proofs in Dvir's survey mentioned in the question appear to be (1) and (2) in this answer. $\endgroup$
    – j.c.
    Commented Apr 12, 2018 at 3:46
  • 1
    $\begingroup$ @j.c. Actually I think all three proofs are in Dvir's book: Cell Decomposition method is section 2.1.1, Crossing Lemma proof is section 2.1.2, and polynomial ham sandwich theorem is section 2.5.2. $\endgroup$
    – David
    Commented Apr 12, 2018 at 3:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .