On permutation polytopes (Q838132)

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.