Permutation polytopes and indecomposable elements in permutation groups

DOI10.1016/J.JCTA.2005.11.004MaRDI QIDQ855825zbMATH OpenOpenAlexFDO

Authors Robert Guralnick, David Perkinson

Publication date 7 December 2006

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0503015

zbMATH Keywords

Birkhoff polytopediameterpermutation groupspermutation polytopestransitivity

Mathematics Subject Classification ID

Primitive groups (20B15) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20)

Abstract: Each group G of nxn permutation matrices has a corresponding permutation polytope, P(G):=conv(G) in R^{nxn}. We relate the structure of P(G) to the transitivity of G. In particular, we show that if G has t nontrivial orbits, then min{2t,floor(n/2)} is a sharp upper bound on the diameter of the graph of P(G); so if G is transitive, the diameter is at most 2. We also show that P(G) achieves its maximal dimension of (n-1)^2 precisely when G is 2-transitive. We then extend results of I. Pak on mixing times for a random walk on P(G). Our work depends on a new result for permutation groups involving writing permutations as products of indecomposable permutations.

Review text

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.

Recommendations

• On permutation polytopes
• Geometry, complexity, and combinatorics of permutation polytopes
• On the diameter of permutation groups
• On the diameter of permutation groups.
• Permutation polytopes of cyclic groups

Cites work

• Computing group resolutions.
• Convex hulls of orbits of representations of finite groups and combinatorial optimization
• Convex polyhedra of doubly stochastic matrices. I: Applications of the permanent function
• Four questions on Birkhoff polytopes
• Fuchsian groups, coverings of Riemann surfaces, subgroup growth, random quotients and random walks.
• Geometry, complexity, and combinatorics of permutation polytopes
• scientific article; zbMATH DE number 3828715 (Why is no real title available?)
• scientific article; zbMATH DE number 3659595 (Why is no real title available?)
• scientific article; zbMATH DE number 124861 (Why is no real title available?)
• scientific article; zbMATH DE number 1538119 (Why is no real title available?)
• scientific article; zbMATH DE number 848091 (Why is no real title available?)
• scientific article; zbMATH DE number 3212917 (Why is no real title available?)
• scientific article; zbMATH DE number 3095897 (Why is no real title available?)
• Maximal subgroups of finite groups
• On the Assignment Polytope
• On the minimal degree of a primitive permutation group
• polymake: a framework for analyzing convex polytopes
• Some subgroups of \(SI_ n(F_2)\)
• Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey
• The Ehrhart polynomial of the Birkhoff polytope
• The polytope of even doubly stochastic matrices
• The travelling salesman problem and a class of polyhedra of diameter two

Cited in

(13)

• Hypermaps and indecomposable permutations
• Faces of Birkhoff Polytopes
• Classification of affine symmetry groups of orbit polytopes
• A property of the Birkhoff polytope
• Finite groups as prescribed polytopal symmetries
• On the width of transitive sets: bounds on matrix coefficients of finite groups
• Semi-magic matrices for dihedral groups
• On the diameter of partition polytopes and vertex-disjoint cycle cover
• Good clusterings have large volume
• Groups of piecewise isometric permutations of lattice points, or Finitary rearrangements of tessellations
• On the permutation polytopes of some cyclic groups
• On permutation polytopes
• Affine symmetries of orbit polytopes

Describes a project that uses

Uses Software

• GAP
• polymake

This page was built for publication: Permutation polytopes and indecomposable elements in permutation groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q855825)