Combinatorics of the Lipschitz polytope

Abstract

Let $\ddot{I}$ be a metric on the set $X=\{1,2,\dots ,n+1\}$. Consider the $n$-dimensional polytope of functions $f:X\to \mathbb{R}$, which satisfy the conditions $f(n+1)=0$, $|f(x)-f(y)|\le \ddot{I}(x,y)$. The question on classifying metrics depending on the combinatorics of this polytope have been recently posed by A. M. Vershik \cite{V}. We prove that for any "generic" metric the number of $(n-m)$-dimensional faces, $0\le m\le n$, equals $\left(\genfrac{}{}{0ex}{}{n+m}{m,m,n-m}\right)=(n+m)!/m!m!(n-m)!$. This fact is intimately related to regular triangulations of the root polytope (the convex hull of the roots of $A_n$ root system). Also we get two-sided estimates for the logarithm of the number of Vershik classes of metrics: $n^3\log n$ from above and $n^2$ from below.