Lines, betweenness and metric spaces

DOI10.1007/S00454-016-9806-2MaRDI QIDQ312159zbMATH OpenOpenAlexFDO

Authors Pierre Aboulker, Xiaomin Chen, Guangda Huzhang, Rohan Kapadia, Cathryn Supko

Publication date 14 September 2016

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

metric spaceslinesgraph metricpseudometric betweennessChen-Chvátal conjecture

Mathematics Subject Classification ID

Connectivity (05C40) Euclidean geometries (general) and generalizations (51M05) Metric geometry (51F99)

Abstract: A classic theorem of Euclidean geometry asserts that any noncollinear set of $n$ points in the plane determines at least $n$ distinct lines. Chen and Chv'atal conjectured that this holds for an arbitrary finite metric space, with a certain natural definition of lines in a metric space. We prove that in any metric space with $n$ points, either there is a line containing all the points or there are at least $Omega(sqrtn)$ lines. This is the first polynomial lower bound on the number of lines in general finite metric spaces. In the more general setting of pseudometric betweenness, we prove a corresponding bound of $Omega(n^{2/5})$ lines. When the metric space is induced by a connected graph, we prove that either there is a line containing all the points or there are $Omega(n^{4/7})$ lines, improving the previous $Omega(n^{2/7})$ bound. We also prove that the number of lines in an $n$-point metric space is at least $n/5w$, where $w$ is the number of different distances in the space, and we give an $Omega(n^{4/3})$ lower bound on the number of lines in metric spaces induced by graphs with constant diameter, as well as spaces where all the positive distances are from {1, 2, 3}.

Recommendations

• Towards a de Bruijn-Erdős theorem in the \(L_1\)-metric
• Solution of the Chen-Chvátal conjecture for specific classes of metric spaces
• A De Bruijn-Erdős theorem for \(1\)-\(2\) metric spaces.
• Sylvester-Gallai theorem and metric betweenness
• A de Bruijn-Erdős theorem in graphs?

Cites work

• scientific article; zbMATH DE number 3155900 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• scientific article; zbMATH DE number 3049937 (Why is no real title available?)
• A De Bruijn-Erdős theorem for \(1\)-\(2\) metric spaces.
• A de Bruijn-Erdős theorem and metric spaces
• A de Bruijn-Erdős theorem for chordal graphs
• A decomposition theorem for partially ordered sets
• Graph metric with no proper inclusion between lines
• Graph theory
• Lines in hypergraphs
• Number of lines in hypergraphs
• Problems related to a de Bruijn-Erdös theorem
• Sylvester-Gallai theorem and metric betweenness
• The Chen-Chvátal conjecture for metric spaces induced by distance-hereditary graphs
• Towards a de Bruijn-Erdős theorem in the \(L_1\)-metric

Cited in

(21)

• Metric spaces in which many triangles are degenerate
• De Bruijn-Erdős-type theorems for graphs and posets
• A de Bruijn-Erdős theorem for \((q,q-4)\)-graphs
• Solution of the Chen-Chvátal conjecture for specific classes of metric spaces
• Universal lines in graphs
• Metric and periodic lines in real inner product space geometries
• Lines in bipartite graphs and in 2‐metric spaces
• Metric hypergraphs and metric-line equivalences
• Chen and Chvátal's conjecture in tournaments
• Chen-Chvátal’s conjecture for graphs with restricted girth
• On a weighted generalization of Kendall's tau distance
• A new class of graphs that satisfies the Chen-Chvátal conjecture
• Graphs with no induced house nor induced hole have the de Bruijn–Erdös property
• A solution to two old problems by Menger concerning angle spaces
• The Chen-Chvátal conjecture for metric spaces induced by distance-hereditary graphs
• Multidimensional Lines II: Proximity and Applications
• Lines in the plane with the \(L_1\) metric
• Sylvester-Gallai theorem and metric betweenness
• scientific article; zbMATH DE number 3876071 (Why is no real title available?)
• Betweenness structures of small linear co-size
• Graph metric with no proper inclusion between lines

This page was built for publication: Lines, betweenness and metric spaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q312159)