A regular polytope

Question

For positive integers $m$ and $n$, consider a regular polytope in ${\mathbb R}^{m+n+mn}$ with $2^{m+n}$ vertices, corresponding to each $\sigma \in \{-1,1\}^{m+n}$ as follows. The first $m+n$ coordinates are $\sigma_i$, and the last $mn$ are the products $\sigma_i \sigma_j$ for $i = 1 \ldots m$, $j = m+1 \ldots m+n$. For example, for $m=1$, $n=2$ the vertices are $$ \matrix{ ( 1 & 1 & 1 & 1 & 1) \cr ( 1 & 1 & -1 & 1 & -1) \cr ( 1 & -1 & 1 & -1 & 1) \cr ( 1 & -1 & -1 & -1 & -1) \cr ( -1 & 1 & 1 & -1 & -1) \cr ( -1 & 1 & -1 & -1 & 1) \cr ( -1 & -1 & 1 & 1 & -1) \cr ( -1 & -1 & -1 & 1 & 1) \cr}$$

How many facets does it have? For $(m,n) = (1,1)$, $(2,2)$ and $(3,3)$ it has $4$, $24$ and $684$ respectively. I'm especially interested in the case $(m,n) = (4,4)$ where I expect the number of facets to be at least a million.

Any other information about the geometry of this polytope (e.g. its volume) or its lattice of faces would be welcome.

Answer 1

Your polytope is the marginal polytope of the complete bipartite graph $K_{m,n}$ and almost a cut polytope. Let $G = (V,E)$ be an undirected graph. A cut is a bipartition of the vertex set into two sets. For each cut, an edge is either cut (its vertices are not in the same block of the partition), or not cut (its vertices are in the same block). The cut polytope has one vertex per cut. We can also write a cut as a binary string and you see those (encoded in ${-1,1}$) as the first three coordinates of your vertices. For each cut, make a vector of length $|E|$ whose $E \ni e$ coordinate is $1$ if the edge is cut and $0$ if not. The convex hull of the cut vectors is the cut polytope of G.

You have two differences to the cut situation. The first is that you are encoding indicators in $\{-1,1\}$ instead of $\{0,1\}$. If you homogenize your polytope by adding a coordinate that is $1$ for each vertex, then a linear change of coordinates makes the polytopes the same.

The second difference is that the vertices of the cut polytope do not have 'a copy of the cut' as its first $m+n$ coordinates. This can be rectified by considering instead of $G$, the cone over it. The cone is a graph with an extra vertex that is connected to every vertex in $G$.

This polytope appears also in algebraic statistics. There it is called the marginal polytope of a graph model. The construction is exactly like you describe it and your case is the complete bipartite graph. The only difference is again that indicators with values in $\{0,1\}$ are used. In algebraic statistics people are interested in the generating degree of the toric ideal of this polytope. For instance if $n=m=3$, then this degree is $6$: https://www.markov-bases.de/show.php?name=G175_bin. On this page, the "sufficient statistics matrix" has as its columns the vertices of your polytope, just with zeros and ones.

There are several hardness results about CUT polytopes, especially for the complete graph. A textbook reference would be "The geometry of cuts and metric" by Michel Deza and Monique Laurent. Googling brought up this paper on computational aspects of generating facets for cut polytopes of other graphs: http://arxiv.org/pdf/math/0601375v2.pdf.

Edit: One more remark: If $m<n$ then $K_m$ is a minor of $K_{m,n}$. Therefore the marginal polytope of $K_{m,n}$ has the marginal polytope of $K_m$ as a face. Consequently any badness result about exploding number of facets for $K_m$ also applies to $K_{m,n}$.