Lines, betweenness and metric spaces

DOI10.1007/S00454-016-9806-2zbMATH Open1364.51007arXiv1412.8283OpenAlexW1885355001MaRDI QIDQ312159FDOQ312159

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)

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}.

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

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?

zbMATH Keywords

metric spaceslinesgraph metricpseudometric betweennessChen-Chvátal conjecture

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (21)

• A de Bruijn-Erdős theorem for \((q,q-4)\)-graphs
• De Bruijn-Erdős-type theorems for graphs and posets
• 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
• Lines in the plane with the \(L_1\) metric
• Multidimensional Lines II: Proximity and Applications
• Sylvester-Gallai theorem and metric betweenness
• Title not available (Why is that?)
• Betweenness structures of small linear co-size
• Graph metric with no proper inclusion between lines
• Metric spaces in which many triangles are degenerate

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)