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.
    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
    Apr 12, 2018 at 3:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.