**Originators:** X. Chen and V. Chvátal
(presented by Ida Kantor - REGS 2009)

**Definitions:**
In a metric space, a point *x* is *between* points *u* and
*v* if *d(u,v)=d(u,x)+d(x,v)*. The *line induced by* (or
*determined by*) points u and v consists of *u, v,* and all points
*x* such that one of *x,u,v* is between the other two. In a finite
metric space, we use the word *line* by itself as an abbreviation for
"a line induced by some pair of points". A set *S* of points is
*collinear* if some pair of points in *S* induce a line that contains
all of *S*.

**Background:** de Bruijn and Erdős [dBE] proved that every set
*S* of *n* points in the plane is either collinear or determines at
least *n* lines. We view this as a finite metric space whose points are
*S* and whose metric is inherited from the Euclidean metric in the plane.
No more than *n* lines are guaranteed, as seen by a set consisting of
*n-1* points on one geometric line and one point not on it.

As another example, any finite graph generates a metric space on its vertices
using the ordinary "shortest-path" distance in the graph. Consider the 5-cycle
with vertices *A,B,C,D,E* (in this order). By the definition of "between",
the point *C* is between *B* and *D*. The line induced by
*B,C* consists of *A,B,C,D*. The line induced by *B,D* consists
of *B,C,D*. Thus one line can contain another.

**Conjecture 1:** In any finite metric space consisting of *n*
points, if no line consists of the entire set, then at least *|X|* lines
are induced.

**Comments:**
The following weaker results are known:

- In every metric space on
*n*points where the points are not collinear, there are at least lg*n*distinct lines. ([CC1], easy to prove.) - In every metric space on
*n*points, there are*Ω((n/ρ)*distinct lines, where^{2/3})*ρ*is the ratio between the largest distance and the smallest nonzero distance. ([CC2]) - In every metric space generated by a connected graph on
*n*vertices, if the points are not collinear, then there are*Ω(n*distinct lines ([CC2]).^{2/7}) - In every metric space on
*n*points where each nonzero distance is 1 or 2, there are*Ω(n*distinct lines, and this is tight ([CC2]).^{4/3})

Chen and Chvátal [CC1] generalized the problem to a setting where the
desired bound here does not hold. The *betweenness hypergraph* of a
metric space is the 3-uniform hypergraph on the points such that three points
form an edge if one is between the other two. In any 3-uniform hypergraph, we
can define a *line* to be a set of edges with a common pair of vertices;
this reduces to the previous definition of line when the hypergraph is the
betweeness hypergraph of a metric space. Now we impose the condition on
3-uniform hypergraphs with *n* vertices that every line has at most
*n-1* vertices in its edges and ask what is the minimum number of lines in
such a hypergraph. The authors prove that this minimum is less than every
power of *n*, so this generalization will not prove Conjecture 1.
They also study the minimum number of lines in a 3-uniform *n*-vertex
hypergraph such that every line has at most *k* vertices in its edges.

**References:**

[CC1] X. Chen and V. Chvátal, Problems related to a de
Bruijn-Erdős theorem, Discrete Applied Mathematics 156 (2008), 2101-2108.

[CC2] E. Chiniforooshan and V. Chvátal, A de Bruijn - Erdős
theorem and metric spaces, arXiv:0906.0123v1.

[dBE] N.G. de Bruijn and P. Erdos, On a combinatorial problem,
Indagationes Mathematicae 10 (1948) 421-423.