Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer
    
Yes, I actually started from Deza and Laurent. –  alvarezpaiva Dec 28 '12 at 13:19
    
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." –  alvarezpaiva Dec 28 '12 at 13:24
    
Prop. 3 in link.springer.com/content/pdf/10.1007%2F3-540-47738-1_10 gives an upper bound (conjecturally tight) for $n=8$. –  Dima Pasechnik Dec 28 '12 at 13:51
    
you get at least 119269588 extreme rays for $n=8$. –  Dima Pasechnik Dec 28 '12 at 13:52
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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