A Note on Distances on the Permutohedron

J. Landers

1. Setup

Given real numbers \((x_1,\dots,x_n)\), the permutohedron \(\Pi(x_1,\dots,x_n) \subset \mathbb{R}^n\) is the convex polytope with vertices

\[ v_\sigma = (x_{\sigma(1)},\dots,x_{\sigma(n)}), \] \[ \sigma \in S_n. \]

Two vertices are connected by an edge precisely when they differ by an adjacent transposition. Thus, the 1-skeleton of the permutohedron is the Cayley graph of \(S_n)\) generated by adjacent swaps. This leads to three natural distance notions between vertices \(v_\sigma\) and \(v_\tau\).

(i) Combinatorial distance. The graph distance \(d_{\mathrm{graph}}(\sigma,\tau)\) is the minimal number of adjacent transpositions required to transform \(\sigma\) into \(\tau\). Equivalently,

\[ d_{\mathrm{graph}}(\sigma,\tau) = \operatorname{inv}(\sigma^{-1}\tau), \]

the inversion number of the relative permutation.

(ii) Geometric edge distance. The edge distance \(d_{\mathrm{edge}}(\sigma,\tau)\) is the minimal Euclidean length of a path between \(v_\sigma\) and \(v_\tau\) that uses only edges of the permutohedron. If a path consists of edges \(e_1,\dots,e_k\) with Euclidean lengths \(L(e_i)\), then

\[ d_{\mathrm{edge}}(\sigma,\tau) = \min \sum_{i=1}^k L(e_i). \]

Swapping positions \(i\) and \(i{+}1\) changes two coordinates and produces an edge of length

\[ L = \sqrt{2} \, \lvert x_a - x_b \rvert. \]

Thus the geometry depends on the spread of the values \(x_i\).

(iii) Direct Euclidean distance. The ambient Euclidean distance between vertices is simply

\[ d_{\mathrm{Euclid}}(\sigma,\tau) = \lVert v_\sigma - v_\tau \rVert_2. \]

This is the straight-line chord length inside \(\mathbb{R}^n\), and is always no greater than any path constrained to lie within the permutohedron.

2. Main Bounds

Theorem 1 (Edge vs. Graph Distance). Let \[ \alpha = \min_{i \neq j} \lvert x_i - x_j \rvert, \] \[ \beta = \max_{i \neq j} \lvert x_i - x_j \rvert. \] Then for any vertices \(v_\sigma, v_\tau\) of the permutohedron, \[ \sqrt{2}\,\alpha\, d_{\mathrm{graph}}(\sigma,\tau) \;\le\; \] \[ d_{\mathrm{edge}}(\sigma,\tau) \;\le\; \] \[ \sqrt{2}\,\beta\, d_{\mathrm{graph}}(\sigma,\tau). \]

Proof. Each edge arises from swapping adjacent coordinates and has \[ \sqrt{2}\,\alpha \;\le\; L \;\le\; \sqrt{2}\,\beta. \] Any path between the vertices must use at least \(k = d_{\mathrm{graph}}(\sigma,\tau)\) edges, giving \(d_{\mathrm{edge}} \ge k\sqrt{2}\,\alpha\). A reduced word gives a path of exactly \(k\) edges, each of length at most \(\sqrt{2}\,\beta\), yielding the upper bound. \(\square\)

Theorem 2 (Euclidean vs. Edge Distance). For any vertices \(v_\sigma, v_\tau\) of the permutohedron, \[ d_{\mathrm{Euclid}}(\sigma,\tau) \;\le\; d_{\mathrm{edge}}(\sigma,\tau). \]

Proof. Any edge-path stays entirely within the 1-skeleton of the permutohedron, which is a subset of the polytope surface, whereas the Euclidean segment joining \(v_\sigma\) and \(v_\tau\) lies in the convex hull. By convexity of Euclidean norm and the fact that a straight line is the shortest path in \(\mathbb{R}^n\), the ambient Euclidean distance can only be shorter than any path constrained to piecewise-linear edges. \(\square\)

Comment. In the canonical permutohedron \((x_1,\dots,x_n)=(1,2,\dots,n)\), all edge lengths equal \(\sqrt{2}\), so Theorem 1 becomes the identity \[ d_{\mathrm{edge}}(\sigma,\tau) = \sqrt{2}\, d_{\mathrm{graph}}(\sigma,\tau). \] Theorem 2 additionally shows that the straight-line distance \(d_{\mathrm{Euclid}}(\sigma,\tau)\) is strictly smaller except when the vertices lie on a common edge.