Title: Symmetry Matters for Sizes of Extended Formulations
Author: Volker Kaibel
Abstract:
In 1991, Yannakakis proved that no symmetric extended formulation for
the matching polytope of the complete graph K_n with n nodes has a
number of variables and constraints that is bounded subexponentially
in n. Here, symmetric means that the formulation remains invariant
under all permutations of the nodes of K_n. Yannakakis also
conjectured that ``asymmetry does not help much,'' but no
corresponding result for general extended formulations has been found
so far. In this talk, we show that for the polytopes associated with
the matchings in K_n with log(n) (rounded down) edges there are
non-symmetric extended formulations of polynomial size, while
nevertheless no symmetric extended formulation of polynomial size
exists. Similar results hold true for the polytopes associated with
cycles of log(n). Thus, with respect to the question for smallest
possible extended formulations, in general symmetry requirements may
matter a lot.
The talk is based on joint work with Kanstantsin Pashkovich and Dirk
Oliver Theis.