Progress on Dirac's Conjecture

Abstract

In 1951, Gabriel Dirac conjectured that every non-collinear set $P$ of $n$ points in the plane contains a point incident to at least $\frac{n}{2}-c$ of the lines determined by $P$, for some constant $c$. The following weakened conjecture was proved by Beck and by Szemerédi and Trotter: every non-collinear set $P$ of $n$ points in the plane contains a point in at least $\frac{n}{c'}$ lines determined by $P$, for some constant $c'$. We prove this result with $c'= 37$. We also give the best known constant for Beck's Theorem, proving that every set of $n$ points with at most $\ell$ collinear determines at least $\frac{1}{98} n(n-\ell)$ lines.

Locations

• The Electronic Journal of Combinatorics - View - PDF
• arXiv (Cornell University) - View - PDF