most recent 30 from http://mathoverflow.net 2013-05-20T14:26:00Z http://mathoverflow.net/feeds/question/117399 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/117399/extreme-rays-in-the-cone-of-semimetrics alvarezpaiva 2012-12-28T10:58:41Z 2012-12-28T13:14:37Z

<p><em>How many extreme rays are there on the polytopal cone formed by all semimetrics on a set with $n$ elements?</em></p> <p><strong>Some background.</strong> 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.</p> <p><strong>More elaborate question.</strong> 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 <em>On the extreme rays of the metric cone.</em></p>

http://mathoverflow.net/questions/117399/extreme-rays-in-the-cone-of-semimetrics/117405#117405 Dima Pasechnik 2012-12-28T13:14:37Z 2012-12-28T13:14:37Z

<p>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 ?</p> <p>There was a quite a bit of computer search done to go beyond $n=5$ in Avis' paper. E.g. I think <a href="http://www.cas.mcmaster.ca/~deza/lncs1996.pdf" rel="nofollow">here</a> you can find results for $n=7$. There are more links on a <a href="http://www.cas.mcmaster.ca/~deza/metric.html" rel="nofollow">page</a> maintained by A.Deza.</p> <p>I admit I don't recall asymptotic results, although it has been a while.</p>