Lines in metric spaces: universal lines counted with multiplicity

arXiv1803.07154MaRDI QIDQ6299282FDOQ6299282

Authors: Martin Matamala, José Zamora 

Publication date: 19 March 2018

Abstract: The line generated by two distinct points, $x$ and $y$, in a finite metric space $M=(V,d)$, denoted by $overline{xy}^M$, is the set of points given by ${\displaystyle }$overline{xy}^M:={zin V: d(x,y)=|d(x,z)pm d(z,y)|}.${\displaystyle }$ A 2-set $x,y$ such that $overline{xy}^M=V$ is called a universal pair and its associated line a universal line. Chen and Chv'atal conjectured that in any finite metric space either there is a universal line or there are at least $|V|$ different (non-universal) lines. Chv'atal proved that this is indeed the case when the metric space has distances in the set $0,1,2$. Aboulker et al. proposed the following strengthening for Chen and Chv'atal conjecture in the context of metric spaces induced by finite graphs. The number of lines plus the number of universal pairs is at least the number of point of the space. In this work we first prove that metric spaces with distances in the set $0,1,2$ satisfy this stronger conjecture. We also prove that for metric spaces induced by bipartite graphs the number of lines plus the number of bridges of the graph is at least the number its vertices, unless the graph is $C_4$ or $K_{2,3}$.

This page was built for publication: Lines in metric spaces: universal lines counted with multiplicity

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