Abstract: In 1951, Gabriel Dirac conjectured that every set P of n non-collinear points in the plane contains a point in at least n/2-c lines determined by P, for some constant c. The following weakening was proved by Beck and Szemer'edi-Trotter: every set P of n non-collinear points contains a point in at least n/c lines determined by P, for some large unspecified constant c. We prove that every set P of n non-collinear points contains a point in at least n/37 lines determined by P. We also give the best known constant for Beck's Theorem, proving that every set of n points with at most k collinear determines at least n(n-k)/98 lines.
Recommendations
- Dirac's conjecture
- A note on a conjecture of Dirac
- A note on the weak Dirac conjecture
- scientific article; zbMATH DE number 3104091
- scientific article; zbMATH DE number 2237361
- scientific article; zbMATH DE number 1532125
- A generalization of Dirac's theorem
- scientific article; zbMATH DE number 1545438
- Progress towards a nonintegrality conjecture
- scientific article; zbMATH DE number 146256
Cites work
- scientific article; zbMATH DE number 3162927 (Why is no real title available?)
- scientific article; zbMATH DE number 3968770 (Why is no real title available?)
- scientific article; zbMATH DE number 2001186 (Why is no real title available?)
- scientific article; zbMATH DE number 3040001 (Why is no real title available?)
- A proof of a consequence of Dirac's conjecture
- A pseudoline counterexample to the strong Dirac conjecture
- Arrangements of \(n\) points whose incident-line-numbers are at most \(n/2\)
- COLLINEARITY PROPERTIES OF SETS OF POINTS
- Crossing Numbers and Hard Erdős Problems in Discrete Geometry
- Crossing-Free Subgraphs
- Extremal problems in discrete geometry
- Improving the crossing lemma by finding more crossings in sparse graphs
- On the Number of Ordinary Lines Determined by n Points
- On the lattice property of the plane and some problems of Dirac, Motzkin and Erdős in combinatorial geometry
- Some combinatorial problems in the plane
- Two combinatorial problems in the plane
Cited in
(10)- A pseudoline counterexample to the strong Dirac conjecture
- A solution to a problem of Grünbaum and Motzkin and of Erdős and Purdy about bichromatic configurations of points in the plane
- A note on the weak Dirac conjecture
- A note on the minimum number of red lines needed to pierce the intersections of blue lines
- Extremal problems in discrete geometry
- Hirzebruch-type inequalities viewed as tools in combinatorics
- The Dirac-Goodman-Pollack conjecture
- On visibility and blockers
- scientific article; zbMATH DE number 1382591 (Why is no real title available?)
- Crossing by lines all edges of a line arrangement
This page was built for publication: Progress on Dirac's conjecture
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q405200)
