3
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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]]
$\endgroup$
  • 1
    $\begingroup$ Nice. I double-checked (by hand), and it looks correct. $\endgroup$ – Tony Huynh May 19 '16 at 23:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.