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.
@article{10_37236_3722,
author = {Michael S. Payne and David R. Wood},
title = {Progress on {Dirac's} conjecture},
journal = {The electronic journal of combinatorics},
year = {2014},
volume = {21},
number = {2},
doi = {10.37236/3722},
zbl = {1297.52005},
url = {http://geodesic.mathdoc.fr/articles/10.37236/3722/}
}
TY - JOUR
AU - Michael S. Payne
AU - David R. Wood
TI - Progress on Dirac's conjecture
JO - The electronic journal of combinatorics
PY - 2014
VL - 21
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/3722/
DO - 10.37236/3722
ID - 10_37236_3722
ER -
%0 Journal Article
%A Michael S. Payne
%A David R. Wood
%T Progress on Dirac's conjecture
%J The electronic journal of combinatorics
%D 2014
%V 21
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/3722/
%R 10.37236/3722
%F 10_37236_3722
Michael S. Payne; David R. Wood. Progress on Dirac's conjecture. The electronic journal of combinatorics, Tome 21 (2014) no. 2. doi: 10.37236/3722
