Permutation polytopes and indecomposable elements in permutation groups (Q855825): Difference between revisions
From MaRDI portal
Changed an Item |
Changed an Item |
||
Property / describes a project that uses | |||
Property / describes a project that uses: polymake / rank | |||
Normal rank |
Revision as of 19:33, 28 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Permutation polytopes and indecomposable elements in permutation groups |
scientific article |
Statements
Permutation polytopes and indecomposable elements in permutation groups (English)
0 references
7 December 2006
0 references
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.
0 references
permutation polytopes
0 references
permutation groups
0 references
diameter
0 references
transitivity
0 references
Birkhoff polytope
0 references