Skip to main content
Post Made Community Wiki by Todd Trimble
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

Here is a generalization to arbitrary finite metric spaces. Recall that the Sylvester-Gallai theorem easily implies the following theorem.

Theorem to be generalized. Every non-collinear set of $n$ points in the plane determines at least $n$ lines.

Note that there is a definition of line in a metric space $(X, d)$ using the notion of betweenness, which I will now describe. We say that a point $b$ is between points $a$ and $c$ if $d(a,b)+d(b,c)=d(a,c)$. The line determined by two points $a$ and $b$ is then the set of points $c$ such that $c$ is between $a$ and $b$, or $a$ is between $c$ and $b$, or $b$ is between $a$ and $c$.

Chen-Chvatál Conjecture. Every finite metric space on $n \geq 2$ points either has at least $n$ distinct lines or a universal line.

This conjecture is still wide open, although there is a sort of industry of results proving it for restricted classes of metrics. For example, there is this paper of Aboulker and Kapadia which proves the Chen-Chvatál Conjecture for metrics coming from distance-hereditary graphs.

Interestingly, it turns out that the Sylvester-Gallai theorem does not hold for all finite metric spaces. However, there are no finite metric spaces for which it is known that the Chen-Chvatál Conjecture is false.