Permutation polytopes and indecomposable elements in permutation groups (Q855825)

Let \(G\) be a group of \(n \times n\) permutation matrices. The authors study the permutation polytope \(P(G) = \text{ conv} (G) \subset {\mathbb R}^{ n \times n }\), in particular, they relate the geometric structure of \(P(G)\) to the transitivity of~\(G\). Using a new theorem for transitive groups, the authors show that the diameter of \(P(G)\) is bounded by \(\text{ min} \left\{ 2t, \lfloor {n \over 2} \rfloor \right\}\), where \(t\) is the number of nontrivial orbits of \(G\). In particular, if \(G\) is transitive, then the diameter of \(P(G)\) is bounded by 2. This and many other theorems in the paper constitute a considerable generalization on previous work for \(G = S_n\); in this special case \(P(S_n)\) is the \(n\)'th Birkhoff polytope, the set of all doubly stochastic matrices. As an example, we state another theorem of the authors: The dimension of \(P(G)\) is bounded by \((n-1)^2\), with equality if and only if \(G\) is 2-transitive.