On Dirac and Motzkin problem in discrete geometry Journal: Graphs and Combinatorics

Jan Florek · 2025

Read On Dirac and Motzkin problem in discrete geometry Journal: Graphs and Combinatorics by Jan Florek (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-18406.txt.

Introduction

Jan Florek wrote a 2025 paper settling a case of a classic conjecture in discrete geometry. Dirac and Motzkin conjectured a neat claim about points in the plane. Given points not all on one line, some point should lie on at least half of the lines the set spans, rounded up. The claim has resisted proof in general for decades.

Florek proves it for a structured special case. The points sit on three lines that all pass through one common point. For any such set of n non-collinear points, some element lies on at least half of the spanned lines, again rounded up. Partial results like this map where the conjecture holds and hint at proof strategies. The paper appears in Graphs and Combinatorics. It adds one more confirmed family to a famous open problem.

Catalog record

CREATORJan Florek
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE9 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-18406

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On Dirac and Motzkin problem in discrete geometry Journal: Graphs and Combinatorics Jan Florek Abstract Dirac and Motzkin conjectured that any set 𝒳 \mathcal{X} of n n non-collinear points in the plane has an element incident with at least ⌈ n 2 ⌉ \lceil\frac{n}{2}\rceil lines spanned by 𝒳 \mathcal{X} . In this paper we prove that any set 𝒳 \mathcal{X} of n n non-collinear points in the plane, distributed on three lines passing through a common point, has an element incident with at least ⌈ n 2 ⌉ \lceil\frac{n}{2}\rceil lines spanned by 𝒳 \mathcal{X} . ∎ MSC 05B25, 51M16 1 Introduction We consider a set \mathcal{X} of n non-collinear points in the plane ( n\geqslant 3 ), and the set \mathcal{L} of lines spanned by \mathcal{X} , i.e., the lines passing through at least two points of \mathcal{X} . Let t(\mathcal{X}) be the maximum number of lines in \mathcal{L} incident with a point of \mathcal{X} . Dirac dirac4 and Motzkin motzkin9 conjectured that for any set \mathcal{X} of n non-collinear points in the plane, we have t(\mathcal{X})\geqslant\lceil\frac{n}{2}\rceil . Some counterexamples were shown for small values of n (9, 15, 19, 25, 31, 37) by Grünbaum grunbaum6 (pp. 24–25) (see also Grünbaum grunbaum7 ). An infinite family of counterexamples was given by Felsner brass3 (p. 313). He constructed a set \mathcal{X} of n=6k+7 ( k\geqslant 2 ) non-collinear points in the plane for which t(\mathcal{X})<\lceil\frac{n}{2}\rceil . Akiyama, Ito, Kobayashi and Nakamura akiyama1 constructed a set \mathcal{X} of n non-collinear points in the plane satisfying t(\mathcal{X})<\lceil\frac{n}{2}\rceil , for every n\geqslant 8 except possibly n=12k+11 where k\geqslant 4 . It is interesting that some of these sets (for n=4k+1 with k\geqslant 2 , see Fig. 1) are distributed on three lines without a common intersection point. Moreover, another one of these sets (for n=4k+1 with k\geqslant 2 , see Fig. 2) are distributed on three lines passing through a common point, except for one point (see also Florek florek5 ). \infty Figure 1: Akiyama, Ito, Kobayashi and Nakamura construction for n=17 points (including \infty ) \infty_{1} \infty_{2} Figure 2: Akiyama, Ito, Kobayashi and Nakamura construction for n=17 points (including \infty_{1} and \infty_{2} ) distributed, except for \infty_{2} , on three lines passing through \infty_{1} . In this paper we prove Theorem 1: any set \mathcal{X} of n non-collinear points in the plane, distributed on three lines passing through a common point, has an element incident with at least \lceil\frac{n}{2}\rceil lines spanned by \mathcal{X} . The construction of the set \mathcal{X} in the projective plane given in Fig. 1 and Fig. 2 is clear due to the following lemma (see Grünbaum grunbaum6 and Akiyama, Ito, Kobayashi and Nakamura akiyama1 (Lemma D )): Let \mathcal{X} be a finite set of points in the projective plane such that \mathcal{X} has points at infinity, and let \mathcal{L} be the set of lines spanned by \mathcal{X} . Then the arrangements (\mathcal{X},\mathcal{L}) can be transformed to an arrangement in the Euclidean plane. The “weak Dirac conjecture” proved by Beck beck2 and independently by Szemerédi and Trotter szemeredi10 states that there is a constant c>0 such that in every non-collinear set \mathcal{X} of n points in the plane some element is incident with at least cn lines spanned by \mathcal{X} . Brass, Moser and Pach brass3 (p. 313) proposed the following “strong Dirac conjecture”: there is a constant c>0 such that any set \mathcal{X} of n points in the plane, not all on a line, has an element which lies on at least \lceil\frac{n}{2}\rceil-c lines spanned by \mathcal{X} . Klee and Wagon klee8 (p. 29) conjectured that for any set \mathcal{X} of n non-collinear points in the plane, we have t(\mathcal{X})\geqslant\lceil\frac{n}{3}\rceil . 2 Main result Let \mathcal{X} be a set of n non-collinear points in the plane. A line passing through exactly two points of \mathcal{X} is called an ordinary line . A point of \mathcal{X} incident with at least \lceil\frac{n}{2}\rceil lines spanned by \mathcal{X} is called an ordinary point (Motzkin ( motzkin9 , p. 452) ). Let (A,B) denote an open segment of a line with end-vertices A and B . Theorem 2.1 Any set \mathcal{X} of n non-collinear points in the plane distributed on three lines passing through a point A ( A is not required to be in the set \mathcal{X} ) has an ordinary point. Proof Let p , q , r be three lines passing through a common point A and suppose p_{1} , p_{2}\subset p ( q_{1} , q_{2}\subset q and r_{1} , r_{2}\subset r ) are open half lines originating at the point A . We can assume that p_{1} , q_{1} , r_{1} , p_{2} , q_{2} , r_{2} are successive half lines around the point A . On every half line p_{1} , q_{1} , r_{1} , p_{2} , q_{2} , r_{2} passing through a point of \mathcal{X} , we choose respectively a point P_{1} , Q_{1} , R_{1} , P_{2} , Q_{2} , R_{2} of \mathcal{X} , different from A , which is closest to A . The points P_{1} and P_{2} ( Q_{1} and Q_{2} , R_{1} and R_{2} , respectively) does not exist simultaneously. Suppose that there are three non-successive in pairs half lines (say p_{1},r_{1},q_{2} ) such that \mathcal{X}\subseteq{p_{1}}\cup{r_{1}}\cup{q_{2}}\cup\{A\} . Notice that p_{1} and r_{1} are lying on different sides of the line q . Similarly, r_{1} and q_{2} ( q_{2} and p_{1} ) are lying on different sides of the line p ( r , respectively). Hence every line spanned by \mathcal{X} , except for p , q , r , is ordinary. Notice that at least two half lines (say p_{1} , r_{1} ) pass through an element of \mathcal{X} , because \mathcal{X} is not on a line. Hence, points P_{1} and R_{1} exist. Notice that if p_{1} has at least \lceil\frac{n}{2}\rceil points of \mathcal{X} , then the point R_{1} is ordinary. Otherwise {r_{1}}\cup{q_{2}}\cup\{A\} has at least \lceil\frac{n}{2}\rceil points of \mathcal{X} and the point P_{1} is ordinary. Suppose now that there are two successive half lines (say p_{1} and q_{1} ) each of which cross the set \mathcal{X} . Hence, the points P_{1} and Q_{1} exist. Certainly, if p and q are both not spanned by \mathcal{X} , then points P_{1} and Q_{1} are ordinary. Let p or q be spanned by \mathcal{X} . Suppose that q is spanned by \mathcal{X} and P_{1} is the only element of \mathcal{X} incident with p . Then, A\notin\mathcal{X} . Hence, if sets \mathcal{X}\cap q , \mathcal{X}\cap r are of the same (different) cardinality, then the point Q_{1} ( P_{1} , respectively) is ordinary. By analogy, if p is spanned by \mathcal{X} and Q_{1} is the only element of \mathcal{X} incident with q , then P_{1} or Q_{1} is ordinary. Hence, we may assume that ( i ) p and q are both spanned by \mathcal{X} . Let us consider the following cases: ( a ) the line P_{1}Q_{1} crosses the half line r_{1} , ( b ) the line P_{1}Q_{1} crosses the half line r_{2} , ( c ) the lines P_{1}Q_{1} and r are parallel. Case ( a ). We prove, by induction on |\mathcal{X}| , that P_{1} or Q_{1} is ordinary. Let B be the intersection

Read the complete text