2 Corrected distance to be longer between high dimensional faces

Strict weak orders are in bijection with the faces of a permutohedron whose $1$-skeleton is identified with the Cayley graph of adjacent transpositions (by inverting the permutations). The dimension of a face is the number of equalities. The distance you want might be the distance in a graph on $G$ whose vertices are the faces of the permutohedron where each face is adjacent to the faces of one lower dimension it contains and the faces of one higher dimension which contain it.

This doubles the distance between permutations compared with on $G$, restricted to the distance in $0$-dimensional faces, is at most twice the Cayley graphdistance, since instead of you can achieve a transposition in two steps, moving directly from the vertex $a \lt b \lt c$ to $a \lt b = c$ to $a \lt c \lt b$. However, the macroscopic properties of this distance are quite different from those of the Cayley graph because you move can take big shortcuts through the high dimensional faces. To reverse $1$-dimensional face a \lt b \lt c$takes$3$transpositions but only$4$steps in$G$:$a \lt b \lt c$,$a \lt b = c.$c$, $a=b=c$, $b=c\lt a$, $c \lt b \lt a$. Every face is of distance at most $2(n-1)$ from every other face since every face is of distance at most $n-1$ from the $n-1$-dimensional face in which all coordinates are equal.

So, another possible distance on $G$ is to declare that the length of an edge is the number of pairwise inequalities added or subtracted. Adjacent faces are related by merging two equivalence classes or dividing one into two. If an edge merges two equivalence classes of sizes $m_1$ and $m_2$, then let the length of that edge be $m_1\times m_2$. So, the distance between $a\lt b=c$ and $a=b=c$ is $2$, and the path of $4$ edges from $a\lt b\lt c$ to $c \lt b \lt a$ has length $6$. If you restrict this distance to the vertices of the permutohedron, you get twice the Cayley distance.

1

I think the generalization you want is a total preorder, or equivalently a strict weak ordering. On finite sets, these correspond to the orderings of values of a function from the set to $\mathbb{R}$. In a total preorder, if $f(x) = f(y)$ then you say $x \le y$ and $y \le x$. In a strict weak order, if $f(x) = f(y)$ then you say neither $x \lt y$ nor $y \lt x$.

Strict weak orders are in bijection with the faces of a permutohedron whose $1$-skeleton is identified with the Cayley graph of adjacent transpositions (by inverting the permutations). The distance you want might be the distance in a graph on the faces where each face is adjacent to the faces of one lower dimension it contains and the faces of one higher dimension which contain it. This doubles the distance between permutations compared with the distance in the Cayley graph, since instead of moving directly from the vertex $a \lt b \lt c$ to $a \lt c \lt b$, you move through the $1$-dimensional face $a \lt b = c.$