Induced lines in metric spaces (2009)

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:

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.