Question

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

Answer 1

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!