A metric on $n$ points $N$ can be represented as a vector $x \in \mathbb{R}_+^{n \choose 2}$.

For each pair of distinct $i, j \in N$, we have $d(i,j) = d(j,i) = x_{i,j}$. The set of all metrics is the set of points which lie inside the cone defined by the (triangle) inequalities: $$x_{i,j} - x_{i,k} - x_{j,k} \leq 0$$
for each distinct triple $\{i,j,k\} \subset N$. If we bound the cone by the inequalities $x_{i,j} + x_{i,k} + x_{j,k} \leq 2$, then we have the metric polytope.

Question: Are there any (lower or upper) bounds known on the volume of the metric polytope, for general n?

In the end, I am interested in estimating the size of the smallest $\epsilon$-net for the set of bounded metrics on $n$ points, which I asked about here. I would also be interested in estimates for polytopes that result in other ways of bounding the metric cone -- for example, by including the inequalities $x_{i,j} \leq 1$ for all $i,j$.


Some googling reveals:

  1. What you call a metric polytope is also called a semimetric polytope (see for example the standard reference: Geometry of cuts and metrics )

  2. In the same book, see here, the authors say that the volume of the rooted semimetric polytope in dimension $n+1$ is: $$\frac{n!}{(2n)!}2^n$$

EDIT: Further web searching (not googling) showed up the paper: On Skeletons, Diameters and Volumes of Metric Polyhedra. In this paper, the authors give explicit volumes for $n=3$ to $n=6$, and given those volumes it seems that the volume goes very rapidly to zero (e.g., $vol_4=2/45$, $vol_5=4/1701$, $vol_6=71936/1477701225$).

At this point, my current knowledge of the volume ends!

  • $\begingroup$ Hi Suvrit -- Thanks for the reference. However, the quantity you mention seems to be the volume for the -rooted- semimetric polytope. This is the polytope that only contains the triangle inequalities that relate to element $n \in N$, and contains the semimetric polytope. This is a useful answer, because it is an upper bound on the volume of the semimetric polytope, but I'd still love tighter bounds. $\endgroup$ – Aaron Jan 21 '11 at 0:37
  • $\begingroup$ But Aaron, there it says that this is the volume of $\text{MET}_{n+1}^\square$, and in the book, they say that $\text{MET}_n^\square$ is the semimetric polytope (although the result seems to be derived using the rooted polytope $\text{RMET}$ ), or am I missing something? $\endgroup$ – Suvrit Jan 21 '11 at 7:39
  • $\begingroup$ I might be wrong, but I think what you have found is a typo in the proof of theorem 27.2.2 (which is proving that the volume of $\textrm{RMET}_{n+1}$ is $\frac{n!}{(2n)!}2^n$.) From earlier lines in the proof this appears to be a typo, as well as the fact that $\textrm{MET}_{n+1} \subset \textrm{RMET}_{n+1}$, and so they should not have the same volume. $\endgroup$ – Aaron Jan 21 '11 at 13:54
  • $\begingroup$ Thanks for checking Aaron. That is indeed a typo in the book. However, as you mentioned in your first comment, you still have an upper bound thanks to the $MET \subset RMET$ inclusion. $\endgroup$ – Suvrit Jan 21 '11 at 14:37
  • $\begingroup$ Which also goes to say that I should also READ the proof, not merely google! ;-) $\endgroup$ – Suvrit Jan 21 '11 at 14:38

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.