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.

  • $\begingroup$ What is $\sigma_i$? Apologies if this is standard notation... $\endgroup$ Apr 26, 2013 at 0:43
  • 1
    $\begingroup$ @Joseph O'Rourke: $\sigma$ is a sequence (of length $m+n$) and $\sigma_i$ is its $i$-th component. $\endgroup$ Apr 26, 2013 at 1:39
  • $\begingroup$ I guess you have already played around with polymake.org/doku.php ? $\endgroup$ Apr 26, 2013 at 12:04
  • $\begingroup$ I notice the claim of these being regular polytopes. Is there an easy way to verify this? It seems far from obvious (aside from the $(1,1)$ case which is just a simplex), and I find it dubious for even the $(1,2)$ case. (My evidence against: The only convex regular 5-polytopes are the 5-simplex, the 5-cube, and the 5-orthoplex. But these respectively have 6, 32, and 10 vertices, not 8.) $\endgroup$ Aug 2, 2021 at 3:32

1 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}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.