Abstrakt
Let P subset of R-d be a polytope with coordinates labeled x(1),..., x(d). Define perm(I)(P) to be the polytope obtained by taking every permutation sigma whose set of fixed-points is [d] \ I, permuting the coordinates of every point in P according to sigma and taking the convex hull of all such points.
Also, define sort(P) to be the polytope obtained by taking each vertex of P in "sorted order". In this article we study the extension complexity of perm(I)(P) and sort(P) in terms of the extension complexity of P.
A result by Kaibel and Pashkovich states that if sort(P) subset of P and I = [d] then the extension complexity of perm(I)(P) is bounded above by a polynomial of the extension complexity of P. We show that the extension complexity of permI (P) can increase exponentially if I not equal [d] even if the vertices of P contain only three values, say 0, 1, or 2 at each of the coordinates xi for i is an element of I.
Furthermore, the extension complexity of sort(P) can be exponentially larger than that of P. We also discuss the implications for the 0/1 case.