Pattern-Avoiding Polytopes

Robert Davis, Bruce Sagan

Published 2016-09-06Version 1

The permutohedron and the Birkhoff polytope are two well-studied polytopes related to many areas of mathematics. In this paper, we generalize these polytopes by considering convex hulls of subsets of their vertices. The vertices chosen correspond to avoidance classes of permutations. We explore the combinatorial structure of certain special cases of these polytopes as well as their Ehrhart polynomials and Ehrhart series. Additionally, we find cases when the polytopes have palindromic and/or unimodal $h^*$-vectors. In particular, we explore connections between subpolytopes of the Birkhoff polytope, order complexes, standard Young tableaux, and $(P,\omega)$-partitions. Multiple questions and conjectures are provided throughout.