Does the Chen-Chvátal Conjecture on metric spaces hold for maximal lines?
A conjecture by Chen and Chvátal asks for the minimum number of induced "lines" in a metric space, in the same spirit as the De Bruijn–Erdős theorem.
Though the statement of this problem on Douglas West's page on the conjecture asked about lines, I was wondering if any work had been done on the problem with maximal lines (which are not a proper subset of another line) but lack the resources to check. It would be easier to disprove than the original conjecture, but I was wondering if there was an easy counterexample before hitting it over the head with a computer?
co.combinatorics metric-spaces
Tony Huynh
ybermanyberman
The following is the distance function for a metric space with five points.
$$ \begin{array}{r|cccc} d & 0& 1& 2& 3& 4\\ \hline 0& 0& 3& 2& 3& 2\\ 1& 3& 0& 3& 2& 3\\ 2& 2& 3& 0& 5& 4\\ 3& 3& 2& 5& 0& 3\\ 4& 2& 3& 4& 3& 0\\ \end{array} $$
It has the following three maximal lines: $$\{\{0, 2, 3, 4\}, \{1, 4\}, \{0, 1, 2, 3\}\}$$
For example the line of $1$ and $2$ is $\{1,2,3\} \subset \{0, 1, 2, 3\}$.
For those who wish to test this digitally, here is the distance function as a list of lists.
[[0,3,2,3,2], [3,0,3,2,3], [2,3,0,5,4], [3,2,5,0,3], [2,3,4,3,0]]
$\begingroup$ Nice. I double-checked (by hand), and it looks correct. $\endgroup$ – Tony Huynh May 19 '16 at 23:06
Not the answer you're looking for? Browse other questions tagged co.combinatorics metric-spaces or ask your own question.
Are all homogeneous metric spaces bihomogeneous?
End point compactification for metric spaces
Classes of metric spaces with additional structure
Does the Hirsch conjecture hold for $n < 2d$?
Quotient of metric spaces
A circulant coin weighing problem
Diameter of the modified bubble-sort graph
Distance between two metric spaces
Is the Erdős–Rényi giant component result applicable here?
Does Vizing's conjecture hold for the infinite graphs?