On permutation polytopes

DOI10.1016/J.AIM.2009.05.003MaRDI QIDQ838132zbMATH OpenOpenAlexFDO

Authors Barbara Baumeister, Christian Haase, Benjamin Nill, Andreas Paffenholz

Publication date 21 August 2009

Published in Advances in Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

convex hullface structurepermutation grouppermutation matrixpermutation polytope

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Determinants, permanents, traces, other special matrix functions (15A15) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Special polytopes (linear programming, centrally symmetric, etc.) (52B12)

Abstract: A permutation polytope is the convex hull of a group of permutation matrices. In this paper we investigate the combinatorics of permutation polytopes and their faces. As applications we completely classify permutation polytopes in dimensions 2,3,4, and the corresponding permutation groups up to a suitable notion of equivalence. We also provide a list of combinatorial types of possibly occuring faces of permutation polytopes up to dimension four.

Review text

The paper under review studies permutation polytopes, i.e., convex hulls of groups of permutation matrices. This class of polytopes, whose most famous members are the Birkhoff polytopes (each of which is the convex hull of the full group of permutation matrices), appear naturally in combinatorics, optimization, statistics, and representation theory. One of the main questions in the paper is, which polytopes can be realized as faces of permutation polytopes. For example, the authors prove that pyramids over faces of permutation polytopes appear again as faces of permutation polytopes. They also show that if a permutation polytope is combinatorially a product, then the permutation group has a natural product structure, and they investigate centrally symmetric permutation polytopes. As an application, the authors classify up to effective equivalence (a term that is developed in the paper) all permutation representations whose polytopes have dimension \(\leq 4\). The paper concludes with a number of open questions and conjectures.

Recommendations

• Permutation polytopes of cyclic groups
• On permutation polytopes: notions of equivalence
• Geometry, complexity, and combinatorics of permutation polytopes
• On volumes of permutation polytopes
• scientific article; zbMATH DE number 848091

Cites work

• Convex polyhedra of doubly stochastic matrices. I: Applications of the permanent function
• Ehrhart polynomials, simplicial polytopes, magic squares and a conjecture of Stanley
• Finding possible permutation characters
• Four questions on Birkhoff polytopes
• Geometry, complexity, and combinatorics of permutation polytopes
• Graph isomorphism and theorems of Birkhoff type
• scientific article; zbMATH DE number 3983158 (Why is no real title available?)
• scientific article; zbMATH DE number 4081295 (Why is no real title available?)
• scientific article; zbMATH DE number 1538119 (Why is no real title available?)
• scientific article; zbMATH DE number 1538123 (Why is no real title available?)
• scientific article; zbMATH DE number 1857822 (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?)
• Lectures on Polytopes
• On the Assignment Polytope
• On the Volume of a Certain Polytope
• Permutation polytopes and indecomposable elements in permutation groups
• Polytopal resolutions for finite groups
• Proof of a conjecture of Chan, Robbins, and Yuen
• Simple 0/1-polytopes
• Some facets of the polytope of even permutation matrices.
• The Distribution of Values in the Quadratic Assignment Problem
• The polytope of even doubly stochastic matrices

Cited in

(36)

• Convex hulls of orbits of representations of finite groups and combinatorial optimization
• Polytopes, permutation shapes and bin packing
• Faces of Birkhoff Polytopes
• polyDB: a database for polytopes and related objects
• Classification of affine symmetry groups of orbit polytopes
• A property of the Birkhoff polytope
• Permutation polytopes corresponding to strongly supermodular functions
• On the even permutation polytope
• Permutations with forbidden patterns and polyominoes on a twisted cylinder of width 3
• Foundations of space-time finite element methods: polytopes, interpolation, and integration
• Finite groups as prescribed polytopal symmetries
• On lattice-free orbit polytopes
• On the topology of the permutation pattern poset
• On permutation polytopes: notions of equivalence
• 12, 24 and beyond
• Polygons drawn from permutations
• On volumes of permutation polytopes
• Reconstructing convex permutominoes
• Quantum sign permutation polytopes
• Polytopes associated to dihedral groups
• scientific article; zbMATH DE number 5525323 (Why is no real title available?)
• Permutohedra, Associahedra, and Beyond
• Lifted generalized permutahedra and composition polynomials
• scientific article; zbMATH DE number 848091 (Why is no real title available?)
• scientific article; zbMATH DE number 7639902 (Why is no real title available?)
• A convex polytope and an antimatroid for any given, finite group
• scientific article; zbMATH DE number 5174291 (Why is no real title available?)
• Permutation polytopes of cyclic groups
• scientific article; zbMATH DE number 4187754 (Why is no real title available?)
• The equivariant volumes of the permutahedron
• c-Birkhoff polytopes
• Geometry, complexity, and combinatorics of permutation polytopes
• On the permutation polytopes of some cyclic groups
• Permutation polytopes and indecomposable elements in permutation groups
• Affine symmetries of orbit polytopes
• Equivalence of permutation polytopes corresponding to strictly supermodular functions

Describes a project that uses

Uses Software

• GAP
• polymake
• 01poly

This page was built for publication: On permutation polytopes

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