Towards a de Bruijn-Erdős Theorem in the L1-Metric

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F13%3A10286266" target="_blank" >RIV/00216208:11320/13:10286266 - isvavai.cz</a>
Result on the web
<a href="http://www.researchgate.net/publication/257429129_Towards_a_de_BruijnErds_Theorem_in_the_L_1-Metric" target="_blank" >http://www.researchgate.net/publication/257429129_Towards_a_de_BruijnErds_Theorem_in_the_L_1-Metric</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/s00454-013-9496-y" target="_blank" >10.1007/s00454-013-9496-y</a>

Result language
angličtina
Original language name
Towards a de Bruijn-Erdős Theorem in the L1-Metric
Original language description
A well-known theorem of de Bruijn and Erdos states that any set of n non-collinear points in the plane determines at least n lines. Chen and Chvatal asked whether an analogous statement holds within the framework of finite metric spaces, with lines defined using the notion of betweenness. In this paper, we prove that the answer is affirmative for sets of n points in the plane with the L1 metric, provided that no two points share their x- or y-coordinate. In this case, either there is a line that contains all n points, or X induces at least n distinct lines. If points of X are allowed to share their coordinates, then either there is a line that contains all n points, or X induces at least n/37 distinct lines.
Czech name
—
Czech description
—

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—

Project
<a href="/en/project/GPP201%2F12%2FP288" target="_blank" >GPP201/12/P288: Graph representations</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2013
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)