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? |
Question 2. Is there a polytope which is combinatorially equivalent to the matching polytope and whose extension complexity is $O(n^4)$? |
Question 3. Is there a polytope which is combinatorially equivalent to the matching polytope and whose extension complexity is polynomial in n? |