**Tuesday, 15:45 - 16:10 h, Room: H 3004**

**Thomas Rothvoss**

Some 0/1 polytopes need exponential size extended formulations

**Abstract:**

We prove that there are *0/1* polytopes *P ⊆ ***R**^{n} that do not

admit a compact LP formulation. More precisely we show that for every *n*

there is a set *X ⊆ { 0,1}*^{n}

such that **conv***(X)* must have extension complexity

at least *2*^{n/2·(1-o(1))}. In other words, every polyhedron *Q* that can

be linearly projected on **conv***(X)* must have exponentially many facets.

In fact, the same result also applies if **conv***(X)* is restricted to be a matroid polytope.

The paper is available under:, http://arxiv.org/abs/1105.0036

Talk 2 of the invited session Tue.3.H 3004

**"Extended formulations in discrete optimization I"** [...]

Cluster 2

**"Combinatorial optimization"** [...]