Smallest Compact Formulation for the Permutahedron - Rian Neogi

Title: Smallest Compact Formulation for the Permutahedron

Abstract: We will take a look at the polytope known as the permutahedron. This is the convex hull of all permutations of 1,...,n. We will see how sorting networks give rise to extended formulations for the permutahedron. Furthermore, we will also show a lower bound on the number of inequalities required in any extended formulation of the permutahedron. This lower bound matches the upper bound that we get from the sorting networks. These results are from the paper "Smallest Compact Formulation for the Permutahedron" by M. Goemans.