Dirac's Conjecture

Importance: Medium ✭✭
Author(s): Dirac, Gabriel
Subject: Geometry
Keywords: point set
Recomm. for undergrads: no
Posted by: David Wood
on: January 22nd, 2014

\begin{conjecture} For every set $P$ of $n$ points in the plane, not all collinear, there is a point in $P$ contained in at least $\frac{n}{2}-c$ lines determined by $P$, for some constant $c$. \end{conjecture}

In 1983, Beck[B], and independently Szemerédi and Trotter [ST], proved that for every set $P$ of $n$ points in the plane, not all collinear, there is a point in $P$ contained in at least $\frac{n}{c}$ lines determined by $P$, for some large unspecified constant $c$. Payne and Wood [PW] proved this result with $c=37$.

% You may use many features of TeX, such as % arbitrary math (between $...$ and $$...$$) % \begin{theorem}...\end{theorem} environment, also works for question, problem, conjecture, ... % % Our special features: % General web links: \href [The On-Line Encyclopedia of Integer Sequences]{http://www.research.att.com/~njas/sequences/}

Bibliography

[B] Jozsef Beck On the lattice property of the plane and some problems of Dirac, Motzkin and Erdős in combinatorial geometry. Combinatorica, 3(3-4):281–297, 1983.

*[D] Gabriel A. Dirac. \href[Collinearity properties of sets of points]{http://www.doi.org/10.1093/qmath/2.1.221}. Quart. J. Math., Oxford Ser. (2), 2:221–227, 1951. MR: 0043485.

[PW] Michael S. Payne and David R. Wood. \href[Progress on Dirac's Conjecture]{http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i2p12}. Electronic J. Combinatorics 21.2:P2.12, 2014. \arxiv[arXiv:1207.3594]{1207.3594}.

[ST] Endre Szemerédi and William T. Trotter, Jr., Extremal problems in discrete geometry. Combinatorica 3.3-5:381-392, 1983.


* indicates original appearance(s) of problem.