# Estimating the Volume of the Metric Polytope

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!

• 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. – Aaron Jan 21 '11 at 0:37
• 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? – Suvrit Jan 21 '11 at 7:39
• 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. – Aaron Jan 21 '11 at 13:54
• 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. – Suvrit Jan 21 '11 at 14:37
• Which also goes to say that I should also READ the proof, not merely google! ;-) – Suvrit Jan 21 '11 at 14:38