IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Two Equators of the Permutohedron

  • Sept. 10, 2021
  • 2:30 p.m.

Abstract

Consider permutations $\sigma : [n] \rightarrow [n]$ written in one-line notation as a vector $\vec{\sigma} = (\sigma(1),\ldots,\sigma(n))$. The permutohedron $\mathcal{P} _ n$ (in one standard presentation) is the convex hull of all such $\vec{\sigma}$, with center $\vec{p} = ((n+1)/2,\ldots,(n+1)/2)$. Then $\mathcal{P} _ n$ has a geometric equator: permutations $\tau$ so that $(\vec{\tau}-\vec{p}) \cdot (\vec{\text{id}} _ n-\vec{p}) = 0$, where $\text{id} _ n$ is the identity permutation. But $\mathcal{P} _ n$ also has a combinatorial equator: permutations $\tau$ in the middle level of the weak Bruhat order, i.e., for which $\text{inv}(\tau) = \frac{1}{2} \binom{n}{2}$. We ask: how close are these two equators to each other? This question arose in connection with a problem in machine learning concerned with estimating so-called Shapley values by sampling families of permutations efficiently.

The most interesting special case of our main result is that, for permutations $\tau$ close to the geometric equator, i.e., for which $(\vec{\tau}-\vec{p}) \cdot (\vec{\text{id}} _ n-\vec{p}) = o(1)$, the number of inversions satisfies

$$ \left | \frac{\text{inv}(\tau)}{\binom{n}{2}} - \frac{1}{2} \right | \leq \frac{1}{4} + o(1) $$

and, furthermore, the quantity $1/4$ above cannot be improved beyond $1/2 - 2^{-5/3} \approx 0.185$. The proof is not difficult but uses an amusing application of bubble sorting. We discuss this and a more general and precise version of the result for any ratio $\text{inv}(\tau)/\binom{n}{2}$.

Joint work with: Rory Mitchell of Nvidia, and Eibe Frank and Geoffrey Holmes of University of Waikato, NZ

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC