Permutation polytopes and indecomposable elements in permutation groups (Q855825): Difference between revisions

From MaRDI portal
Set OpenAlex properties.
Importer (talk | contribs)
Changed an Item
Property / arXiv ID
 
Property / arXiv ID: math/0503015 / rank
 
Normal rank

Revision as of 17:22, 18 April 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
    0 references
    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
    0 references
    permutation polytopes
    0 references
    permutation groups
    0 references
    diameter
    0 references
    transitivity
    0 references
    Birkhoff polytope
    0 references
    0 references
    0 references

    Identifiers