# Extreme rays in the cone of (semi)metrics

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.

-

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.
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