Permutation polytopes and indecomposable elements in permutation groups

DOI10.1016/J.JCTA.2005.11.004zbMATH Open1108.52014arXivmath/0503015OpenAlexW2033864528MaRDI QIDQ855825FDOQ855825

Authors: Robert Guralnick, David Perkinson 

Publication date: 7 December 2006

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

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.

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

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

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)

Cites Work

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

Cited In (12)

• Groups of piecewise isometric permutations of lattice points, or Finitary rearrangements of tessellations
• On permutation polytopes
• 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
• Good clusterings have large volume
• On the width of transitive sets: bounds on matrix coefficients of finite groups
• Semi-magic matrices for dihedral groups
• Faces of Birkhoff Polytopes
• Finite groups as prescribed polytopal symmetries

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)