## Pages

### Best combinatorial bound for extension complexity

The following is a well-known and easy fact.

Proposition. For every 0/1-matrix M, the number

$\min \{ \mbox{rk}_+(A) \mid \mbox{supportmatrix}(A) = M \}$

is equal to the Boolean rank of M.

For a polytope P, let xc(P) denote its extension complexity, i.e., the smallest number of facets of a polytope Q which can be mapped onto P by a projective mapping. Moreover, let S(P) denote the support matrix of the vertex-facet slack matrix of P. The proposition above motivates the following question.

 Question 1. Let M be the support matrix of the vertex-facet slack matrix of a polytope. Is it true that the number $\min \{ \mbox{xc}(P) \mid S(P) = M \}$ is equal to the Boolean rank of M?

The answer is most probably no, at least not for all P''. However, let's look at what we get if we restrict P to a special family of polytopes. My all-time favourite: the Matching polytopes. Here Question 1 gives rise to the following.

 Question 2. Is there a polytope which is combinatorially equivalent to the matching polytope and whose extension complexity is $O(n^4)$?

And we might want to relax that further to the following.

 Question 3. Is there a polytope which is combinatorially equivalent to the matching polytope and whose extension complexity is polynomial in n?

We know that the question corresponding to Question 3 for Max-Cut and Traveling Salesman polytopes has a negative answer -- but only because the lower bound proof works combinatorially.

In general, it may be a good idea to start by looking at 3-polytopes, because in that case the realization space is comparatively easy. Some other time.