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

transitivityBirkhoff polytopediameterpermutation groupspermutation polytopes

Mathematics Subject Classification ID

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

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.

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

• 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?)
• 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
• Maximal subgroups of finite groups
• On the Assignment Polytope
• On the minimal degree of a primitive permutation group
• 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
• polymake: a framework for analyzing convex polytopes

Cited in

(12)

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

Describes a project that uses

Uses Software

• polymake
• GAP

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)