Tight Lower Bounds on the Sizes of Symmetric Extensions of Permutahedra and Similar Results

Source abstract

It is well known that the permutahedron Π n has 2 n − 2 facets. The Birkhoff polytope provides a symmetric extended formulation of Π n of size Θ(n 2 ). Recently, Goemans described a non-symmetric extended formulation of Π n of size Θ(n log n). In this paper, we prove that Ω(n 2 ) is a lower bound for the size of symmetric extended formulations of Π n . Moreover, we prove that the cardinality indicating polytope has the same tight lower bounds for the sizes of symmetric and nonsymmetric extended formulations as the permutahedron.