Progress on Dirac's conjecture

zbMATH Open1297.52005arXiv1207.3594MaRDI QIDQ405200FDOQ405200

Authors: Michael S. Payne, David R. Wood 

Publication date: 4 September 2014

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1207.3594

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

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

zbMATH Keywords

Dirac's conjecture

Mathematics Subject Classification ID

Erd?s problems and related topics of discrete geometry (52C10) Planar arrangements of lines and pseudolines (aspects of discrete geometry) (52C30)

Cites Work

• Some combinatorial problems in the plane
• Title not available (Why is that?)
• Title not available (Why is that?)
• COLLINEARITY PROPERTIES OF SETS OF POINTS
• Crossing Numbers and Hard Erdős Problems in Discrete Geometry
• On the lattice property of the plane and some problems of Dirac, Motzkin and Erdős in combinatorial geometry
• Extremal problems in discrete geometry
• Improving the crossing lemma by finding more crossings in sparse graphs
• Crossing-Free Subgraphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the Number of Ordinary Lines Determined by n Points
• A proof of a consequence of Dirac's conjecture
• Two combinatorial problems in the plane
• A pseudoline counterexample to the strong Dirac conjecture
• Arrangements of \(n\) points whose incident-line-numbers are at most \(n/2\)

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
• Title not available (Why is that?)
• 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)