On permutation polytopes

In this paper we lay the foundations for the study of permutation polytopes: the convex hull of a group of permutation matrices.We clarify the relevant notions of equivalence, prove a product theorem, and discuss centrally symmetric permutation polytopes. We provide a number of combinatorial properties of (faces of) permutation polytopes. As an application, we classify ⩽4-dimensional permutation polytopes and the corresponding permutation groups. Classification results and further examples are made available online.We conclude with several questions suggested by a general finiteness result.