Ehsan Chiniforooshan ; Vasek Chvatal - A de Bruijn - Erdos theorem and metric spaces

dmtcs:545 - Discrete Mathematics & Theoretical Computer Science, March 23, 2011, Vol. 13 no. 1 - https://doi.org/10.46298/dmtcs.545
A de Bruijn - Erdos theorem and metric spaces

Authors: Ehsan Chiniforooshan 1; Vasek Chvatal 2

  • 1 Google Inc.
  • 2 Department of Computer Science and Software Engineering [Montreal]

De Bruijn and Erdos proved that every noncollinear set of n points in the plane determines at least n distinct lines. Chen and Chvatal suggested a possible generalization of this theorem in the framework of metric spaces. We provide partial results in this direction.

https://doi.org/10.46298/dmtcs.545
Source: HAL:hal-00990496v1
Volume: Vol. 13 no. 1
Section: Combinatorics
Published on: March 23, 2011
Accepted on: June 9, 2015
Submitted on: May 23, 2009
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
Funding:
    Source : OpenAIRE Graph
  • Funder: Natural Sciences and Engineering Research Council of Canada

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo ARXIV 2005.09447
  • 2005.09447
Graphs with no induced house nor induced hole have the de Bruijn-Erd\H{o}s property

Share and export

Consultation statistics

This page has been seen 279 times.
This article's PDF has been downloaded 553 times.