What does a typical metric space look like?

Abstract

The collection ${\mathcal{M}}_n$ of all metric spaces on $n$ points whose diameter is at most $2$ can naturally be viewed as a compact convex subset of ${\mathbb{R}}^{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}$, known as the metric polytope. In this paper, we study the metric polytope for large $n$ and show that it is close to the cube $[1,2{]}^{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}\subseteq {\mathcal{M}}_n$ in the following two senses. First, the volume of the polytope is not much larger than that of the cube, with the following quantitative estimates: \[ \left(\tfrac{1}{6}+o(1)\right)n^{3/2} \le \log \mathrm{Vol}(\mathcal{M}_n)\le O(n^{3/2}). \] Second, when sampling a metric space from ${\mathcal{M}}_n$ uniformly at random, the minimum distance is at least $1-n^{-c}$ with high probability, for some $c>0$. Our proof is based on entropy techniques. We discuss alternative approaches to estimating the volume of ${\mathcal{M}}_n$ using exchangeability, Szemerédi's regularity lemma, the hypergraph container method, and the Kővári--Sós--Turán theorem.

64 pages, 2 figures. v2: Swapped Sections 5 and 6 and added a reader's guide