5
$\begingroup$

How many extreme rays are there on the polytopal cone formed by all semimetrics on a set with $n$ elements?

Some background. Given a set $X$ with $n$ elements, the set of all semimetrics $d:X \times X \rightarrow [0,\infty)$ can be seen as the cone of symmetric matrices $(d_{i,j})$ with zeroes on the diagonal and satifying the system of linear inequalities $d_{i,j} \geq 0$, $d_{i,j} + d_{j,k} - d_{i,k} \geq 0$. The polytopal cone defined by this finite system of inequalities can also be described (at least in principle) by exhibiting its extreme rays. Some extreme semimetrics are easy to describe. Here is a class of examples: if $Y$ is a subset of $X$, define the cut semimetric $d_Y$ by setting the distance between two points to be equal to $1$ if one of the points is in $Y$ and the other in its complement, otherwise the distance between the two points is zero. Another example, given by Avis, of an extreme metric is the length metric of the graph $K_{3,2}$ on the cone of semimetrics on a set with $5$ elements.

More elaborate question. It may be hard to know exactly how many extremal rays there are on the semimetric cone, but I'm interested in a good estimate (some asymptotic estimate would also be nice). I'm also interested in knowing about classes of examples of extremal semimetrics other than the cut semimetrics and the examples given by Avis in his 1980 paper On the extreme rays of the metric cone.

$\endgroup$

1 Answer 1

4
$\begingroup$

There has been quite a bit of work done since 1980 on this. Did you check the book by M. Deza and M. Laurent "Geometry of cuts and metrics", Springer 1997 ?

There was a quite a bit of computer search done to go beyond $n=5$ in Avis' paper. E.g. I think here you can find results for $n=7$. There are more links on a page maintained by A.Deza.

I admit I don't recall asymptotic results, although it has been a while.

$\endgroup$
4
  • $\begingroup$ Yes, I actually started from Deza and Laurent. $\endgroup$ Dec 28, 2012 at 13:19
  • $\begingroup$ Thanks for the reference to the paper by Deza, Deza, and Fukuda. For the casual reader: They show that "the metric cone on seven nodes has exactly 55 226 extreme rays." $\endgroup$ Dec 28, 2012 at 13:24
  • $\begingroup$ Prop. 3 in link.springer.com/content/pdf/10.1007%2F3-540-47738-1_10 gives an upper bound (conjecturally tight) for $n=8$. $\endgroup$ Dec 28, 2012 at 13:51
  • 1
    $\begingroup$ you get at least 119269588 extreme rays for $n=8$. $\endgroup$ Dec 28, 2012 at 13:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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