On Partial Permutations and Alternating Sign Matrices: Bijections and Polytopes

Abstract

Motivated by the study of chained permutations and alternating sign matrices, we investigate partial permutations and alternating sign matrices. We give a length generating function for partial permutations and show bijections relating certain subsets to decorated permutations and set partitions. We prove bijections among partial alternating sign matrices and several other combinatorial objects as well as results related to their dynamics, analogous to those in the usual alternating sign matrix setting. We also study families of polytopes which are the convex hulls of these matrices. We determine inequality descriptions, facet enumerations, and face lattice descriptions. Finally, we study partial permutohedra which arise naturally as projections of these polytopes, revealing connections to graph associahedra.