Two-Level Polytopes with a Prescribed Facet

Abstract

A (convex) polytope is said to be 2-level if for every facet-defining direction of hyperplanes, its vertices can be covered with two hyperplanes of that direction. These polytopes are motivated by questions, e.g., in combinatorial optimization and communication complexity. We study 2-level polytopes with one prescribed facet. Based on new general findings about the structure of 2-level polytopes, we give a complete characterization of the 2-level polytopes with some facet isomorphic to a sequentially Hanner polytope, and improve the enumeration algorithm of Bohn et al. (ESA 2015). We obtain, for the first time, the complete list of d-dimensional 2-level polytopes up to affine equivalence for dimension $d = 7$. As it turns out, geometric constructions that we call suspensions play a prominent role in both our theoretical and experimental results. This yields exciting new research questions on 2-level polytopes, which we state in the paper.

We acknowledge support from ERC grant FOREFRONT (grant agreement no. 615640) funded by the European Research Council under the EU’s 7th Framework Programme (FP7/2007-2013).

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

We start by giving a formal definition of 2-level polytopes and reasons why we find that they are interesting objects.

Definition 1

(2-level polytope). A polytope P is said to be 2-level if each hyperplane $\varPi$ defining a facet of P has a parallel $\varPi '$ such that every vertex of P is on either $\varPi$ or $\varPi '$.

Motivation. First of all, many famous polytopes are 2-level. To name a few, stable set polytopes of perfect graphs [3], twisted prisms over those — also known as Hansen polytopes [15] — Birkhoff polytopes, and order polytopes [21] are all 2-level polytopes. Of particular interest in this paper are a family of polytopes interpolating between the cube and the cross-polytope.

Definition 2

(sequentially Hanner polytope). We call a polytope $H \subseteq \mathbb {R}^d$ a sequentially Hanner polytope if either $H = H' \times [-1,1]$ or $H = \mathrm {conv}(H' \times \{0\} \cup \{-e_{d}, e_{d}\})$, where $H'$ is a sequentially Hanner polytope in $\mathbb {R}^{d-1}$ in case $d > 1$, or $H = [-1,1]$ in case $d= 1$. We call $H'$ the base of H.

The name comes from the fact that these polytopes are Hanner polytopes [14] but not all Hanner polytopes are sequentially Hanner. Hanner polytopes are related to some famous conjectures such as Kalai’s $3^d$ conjecture [16] and the Mahler conjecture [19].

More motivation for the study of 2-level polytopes comes from combinatorial optimization, since 2-level polytopes have minimum positive semidefinite extension complexity [9]. Moreover, a finite point set has theta rank 1 if and only if it is the vertex set of a 2-level polytope. This result was proved in [7], and answered a question of Lovász [17]. We already mentioned the stable set polytopes of perfect graphs as prominent examples of 2-level polytopes. To our knowledge, the fact that these polytopes have small positive semidefinite extended formulations is the only known reason why one can efficiently find a maximum stable set in a perfect graph [13]. Moreover, 2-level polytopes are also related to nice classes of matrices such as totally unimodular or balanced matrices that are central in integer programming, see e.g. [20].

Finally, 2-level polytopes are also of interest in communication complexity since they provide interesting instances to test the log-rank conjecture [18], one of the fundamental open problems in that area. Indeed, every d-dimensional 2-level polytope has a slack matrix that is a 0 / 1-matrix of rank $d+1$. If the log-rank conjecture were true, the communication problem associated to any such matrix should admit a deterministic protocol of complexity $\mathrm {polylog}(d)$, which is open. Returning to combinatorial optimization, the log-rank conjecture for slack matrices of 2-level polytopes is (morally) equivalent to the statement that every 2-level polytope has an extended formulation with only $2^{\mathrm {polylog}(d)}$ inequalities.

Goal. Despite the motivation described above, we are far from understanding the structure of general 2-level polytopes. This paper offers results in this direction. The recurring theme here is how much local information about the geometry of a given 2-level polytope determines its global structure. For instance, it is fairly easy to prove that if a 2-level polytope has a simple vertex, then it is necessarily isomorphic¹ to the stable set polytope of a perfect graph — this observation generalizes a result of [7]. Here, we study 2-level polytopes with a prescribed facet.

Prescribing facets of 2-level polytopes is a natural way to enumerate 2-level polytopes. Indeed, since every facet of a 2-level polytope is also 2-level, in order to enumerate all d-dimensional 2-level polytopes one could go through the list of all $(d-1)$-dimensional 2-level polytopes $P_0$ and enumerate all 2-level polytopes P having $P_0$ as a facet. The enumeration algorithm [2] builds on this strategy. It gave the complete list of 2-level polytopes up to dimension $d = 6$. However, the method in [2] was by far not able to compute the list of 2-level polytopes in $d=7$.

Contribution and Outline. The contribution of this paper is twofold.

First, we revisit the enumeration algorithm from [2] and propose a new and significantly more efficient variant based on a more geometric interpretation of the algorithm. We implemented the new algorithm and computed for the first time the complete list of 2-level polytopes up to isomorphism for $d=7$. The algorithm and the results are exposed in Sect. 2.

Second, we characterize 2-level polytopes with a cube or cross-polytope facet and more generally with a sequentially Hanner facet, see Sect. 3. We give an informal statement (Theorem 1) of the result there and illustrate the proof strategy with the special case of the cube and cross-polytope. The full statement and proof can be found in the appendix.

Our main tool to obtain these results is a certain polyhedral subdivision that one can define given any prescribed facet, see below in the present section. In addition to this, we make use of the lattice decomposition property, a general property of 2-level polytopes that is tightly related to the integer decomposition property.

Finally, in Sect. 4, we discuss suspensions of 2-level polytopes. A suspension of a polytope $P_0 \subseteq \{x \in \mathbb {R}^d \mid x_1 = 0\}$ is any polytope P obtained as the convex hull of $P_0$ and $P_1$, where $P_1 \subseteq \{x \in \mathbb {R}^d \mid x_1 = 1\}$ is the translate of some non-empty face of $P_0$. The prism and the pyramid over a polytope $P_0$ are special cases of suspensions. As an outcome of our results, we found that suspensions seem to play an important role in understanding the structure of general 2-level polytopes. We conclude Sect. 4 by stating promising new research questions on 2-level polytopes that are inspired by this.

Now, we describe our approach in more detail and then give further pointers to related work.

Approach. Given any 2-level $(d-1)$-polytope $P_0$ that we wish to prescribe as a facet of a 2-level d-polytope P, we define a new polytope that we call the “master polytope” and a polyhedral subdivision of this master polytope.

Fig. 1.

(a) The polyhedral subdivision $\mathcal {S}(P_0)$ in case $P_0$ is a triangle. Coloured sets correspond to the 2-level polytopes P computed by the enumeration algorithm. Red sets yield suspensions. (b) polyhedral subdivision $\mathcal {S}(P_0)$ in case $P_0$ is the 3-cross-polytope; the blue cells yield prisms, all the faces yield suspensions except from yellow cells that yield quasi-suspensions (figure from Wikipedia). (Color figure online)

Definition 3

(Master polytope, polyhedral subdivision). Let $P_0$ be a $(d-1)$-dimensional 2-level polytope embedded in $\{x \in \mathbb {R}^d \mid x_1 = 0\} \simeq \mathbb {R}^{d-1}$. Since $P_0$ is 2-level, each facet-defining hyperplane $\varPi ^-$ has a parallel hyperplane $\varPi ^+$ such that $\varPi ^-$ and $\varPi ^+$ together contain all the vertices of $P_0$. Let $v^-$ and $v^+$ be vertices of $P_0$ on $\varPi ^-$ and $\varPi ^+$ respectively. Consider the three hyperplanes $\varPi ^- - v^+$, $\varPi ^- - v^- = \varPi ^+ - v^+$ and $\varPi ^+ - v^-$. Let $Q(P_0) \subseteq \{x \in \mathbb {R}^d \mid x_1 = 0\}$ denote the polytope bounded by the “outer” hyperplanes $\varPi ^- - v^+$ and $\varPi ^+ - v^-$ obtained for each facet-defining direction. We call $Q = Q(P_0)$ the master polytope of $P_0$. The “middle” hyperplanes $\varPi ^- - v^- = \varPi ^+ - v^+$ define a polyhedral subdivision of the master polytope Q, which we denote by $\mathcal {S}(P_0)$. See Fig. 1 for an illustration for $d = 3, 4$.

The improved enumeration algorithm that we propose in Sect. 2 is based on three new ideas, two of which are related to the polyhedral subdivision $\mathcal {S}(P_0)$: (i) we enumerate the possible vertex sets of the top face $P_1$ in the whole polyhedral subdivision $\mathcal {S}(P_0)$, instead of branching prematurely and miss the opportunity to discard redundant computations; (ii) we exploit the fact that many possible vertex sets for $P_1$ are related to each other by translations within $\mathcal {S}(P_0)$, which further decreases the number of cases to consider; (iii) we use an ordering on the set of prescribed 2-level facets that allows the algorithm to compute significantly less convex hulls.

In order to prove our main theoretical result stated in Sect. 3, we embed the given sequentially Hanner facet $P_0 = H$ in $\{x \in \mathbb {R}^d \mid x_1 = 0\}$, and consider the polyhedral subdivision $\mathcal {S}(H)$. Up to isomorphism, every 2-level polytope P that has H as a facet is the convex hull of $P_0 = H$ and some 2-level (possibly low-dimensional) polytope $P_1$ in $\{x \in \mathbb {R}^d \mid x_1 = 1\}$. We prove that $P_1$ is always a translate of some face of $\mathcal {S}(H)$, a fact that we repeatedly use in our analysis. This uses the fact that for sequentially Hanner polytopes, facet directions exactly correspond to 2-level directions. Although the structure of $\mathcal {S}(H)$ for a sequentially Hanner facet H seems quite wild, we are able to characterize which points of $\{x \in \mathbb {R}^d \mid x_1 = 1\}$ can possibly appear as vertices of P, assuming that $e_1$ is a vertex of P. There, we use the lattice decomposition property.

Then, we analyse the vertex set of $P_1$ through an associated bidirected graph which determines the projection of $P_1$ to a subset of the coordinates, namely, those that correspond to prism operations in the sequentially Hanner facet H. We prove that this bidirected graph can always be assumed to be a star (possibly with some parallel edges). In order to reconstruct $P_1$ from its bidirected graph, we show that every bidirected edge of our bidirected graph has corresponding face in $P_1$, which is an axis-parallel cube. Next, we characterize the choices of cubes that lead to a 2-level polytope and conclude that P is a generalization of a suspension, which we call quasi-suspension. Finally, we complete the characterization by proving that quasi-suspensions of sequentially Hanner polytopes are always 2-level.

Related Work. The enumeration of all combinatorial types of point configurations and polytopes is a fundamental problem in discrete and computational geometry. Latest results in [4] report complete enumeration of polytopes for dimension $d=3,4$ with up to 8 vertices and $d=5,6,7$ with up to 9 vertices. For 0 / 1-polytopes this is done completely for $d \leqslant 5$ and $d=6$ with up to 12 vertices [1].

Regarding 2-level polytopes, recent related results include an excluded minor characterization of 2-level matroid base polytopes [12], a $O(c^d)$ lower bound on the number of 2-level matroid d-polytopes [11], and a complete classification of polytopes with minimum positive semidefinite rank, which generalize 2-level polytopes, in dimension 4 [8].

2 Enumeration of 2-Level Polytopes

Preliminaries. We start by sketching the main ideas of the algorithm of [2] along with definitions and useful tools.

Definition 4

(Slack matrix). The slack matrix of a polytope $P \subseteq \mathbb {R}^{d}$ with m facets $F_1$, ..., $F_m$ and n vertices $v_1$, ..., $v_n$ is the $m \times n$ nonnegative matrix $S = S(P)$ such that $S_{ij}$ is the slack of the vertex $v_j$ with respect to the facet $F_i$, that is, $S_{ij} = g_i(v_j)$ where $g_i : \mathbb {R}^{d} \rightarrow \mathbb {R}$ is any affine form such that $g_i(x) \geqslant 0$ is valid for P and $F_i = \{x \in P \mid g_i(x) = 0\}$. The slack matrix of a polytope is defined up to scaling its rows by positive reals.

A polytope is 2-level if and only if each row of its slack matrix takes exactly two values (namely, 0 and some positive number that can may vary from row to row). When dealing with 2-level polytopes, we will always assume the slack matrices to be 0 / 1, which may be always achieved by scaling the rows of the matrix with positive scalars.

Definition 5

(Simplicial core). A simplicial core for a d-polytope P is a $(2d+2)$-tuple $(F_1,\ldots ,F_{d+1};$ $v_1,\ldots ,v_{d+1})$ of facets and vertices of P such that each facet $F_i$ does not contain vertex $v_i$ but contains vertices $v_{i+1}$, ..., $v_{d+1}$.

Every d-polytope P admits a simplicial core and this fact can be proved by a simple induction on the dimension, see, e.g., [9, Proposition 3.2]. We use simplicial cores to define two types of embeddings that are full-dimensional. Let P be a 2-level d-polytope with m facets and n vertices, and let $\varGamma := (F_1,\ldots ,F_{d+1};v_1,\ldots ,v_{d+1})$ be a simplicial core for P. From now on, we assume that the rows and columns of the slack matrix S(P) are ordered compatibly with the simplicial core, so that the ith row of S(P) corresponds to facet $F_i$ for $1 \leqslant i \leqslant d+1$ and the j-th column of S(P) corresponds to vertex $v_j$ for $1 \leqslant j \leqslant d+1$.

Definition 6

( $\mathcal {V}$ - and $\mathcal {H}$ -embedding ). The $\mathcal {H}$-embedding with respect to $\varGamma$ is defined by mapping each $v_j$ to the unit vector $e_j$ of $\mathbb {R}^d$ for $1 \leqslant j \leqslant d$, and $v_{d+1}$ to the origin. In the $\mathcal H$-embedding of P, facet $F_i$ for $1 \leqslant i \leqslant m$ is defined by the inequality $\sum _{j\in [d], S_{ij}=1} x_j \geqslant 0$ if $v_{d+1} \in F_i$ and by $\sum _{j\in [d], S_{ij}=0} x_j \leqslant 1$ if $v_{d+1} \not \in F_i$. In the $\mathcal V$-embedding of P with respect to $\varGamma$, vertex $v_j$ is the point of $\mathbb {R}^d$ whose ith coordinate is $S_{ij}$, for $1 \leqslant j \leqslant n$ and $1 \leqslant i \leqslant d$.

Equivalently, the ${\mathcal V}$-embedding can be defined via the transformation $x \mapsto Mx,$ where the embedding matrix $M = M(\varGamma )$ is the top left $d \times d$ submatrix of S(P) and $x \in \mathbb {R}^d$ is a point in the $\mathcal H$-embedding.

The next result is fundamental for the enumeration algorithm.

Proposition 7

([2]). In the $\mathcal H$-embedding P of a 2-level d-polytope with respect to any simplicial core $\varGamma$, the vertex set of P equals $P \cap M^{-1} \cdot \{0,1\}^d\subseteq \mathbb {Z}^d$, where $M = M(\varGamma )$ is the embedding matrix of $\varGamma$.

The algorithm computes a complete set $L_d$ of non-isomorphic 2-level d-polytopes, from a similar set $L_{d-1}$ of 2-level $(d-1)$-polytopes. For a given polytope $P_0 \in L_{d-1}$, define $L(P_0)$ to be the set of all 2-level polytopes that have $P_0$ as a facet. Since every facet of a 2-level polytope is 2-level, the union of these sets $L(P_0)$ over all polytopes $P_0 \in L_{d-1}$ is our desired set $L_d$. The main loop of the algorithm is as follows (Algorithm 1, lines 2–18): given some $P_0 \in L_{d-1}$, embed it in the hyperplane $\{x \in \mathbb {R}^d \,|\, x_1 = 0\} \simeq \mathbb {R}^{d-1}$. Then compute a collection $\mathcal {A}\subseteq \{x \in \mathbb {R}^d \,|\, x_1=1\}$ of point sets, such that for each 2-level polytope $P \in L(P_0)$, there exists $A\in \mathcal {A}$ with $P \simeq \mathrm {conv}(P_0 \cup \{e_1\}\cup A)$. For each $A \in \mathcal {A}$, compute $P = \mathrm {conv}(P_0\cup \{e_1\} \cup A)$ and, in case it is 2-level and not isomorphic to any polytope in the current set $L_d$, add P to $L_d$ (Algorithm 1, lines 11–18).

The efficiency of this approach depends greatly on how the collection $\mathcal {A}$ is chosen. In [2], $\mathcal {A}$ is constructed using a proxy for 2-level polytopes in terms of closed sets with respect to a closure operator.

Definition 8

(Closure operator). An operator $\mathrm {cl}: 2^{\mathcal {X}} \rightarrow 2^{\mathcal {X}}$ over a ground set $\mathcal {X}$ is a closure operator if it is: (i) idempotent (i.e., $cl(cl(A) = cl(A)$), (ii) $(\preccurlyeq ,\sqsubseteq )$-monotone (i.e., $A \preccurlyeq B \Rightarrow cl(A) \sqsubseteq cl(B))$ and (iii) $\preccurlyeq$-expansive (i.e., $A \preccurlyeq cl(A)$), where $A,B\subseteq \mathcal {X}$, $A\preccurlyeq B \Leftrightarrow A=B \text { or } \max ((A\cup B)\smallsetminus (A\cap B))\in B$, $A\sqsubseteq B \Leftrightarrow A\subseteq B \text { and } \max (B\smallsetminus A)\leqslant \min A$, and $\subseteq$ is the usual containment.

The reader can verify that $A \sqsubseteq B \Rightarrow A \subseteq B \Rightarrow A \preccurlyeq B$. A set $A \subseteq \mathcal {X}$ is said to be closed with respect to $\mathrm {cl}$ if $\mathrm {cl}(A) = A$.

In [2] the closure operator $\mathrm {cl}_G \circ \mathrm {cl}_{(\mathcal {X},\mathcal {F})}$ is used, where $\mathcal {F} \subseteq \mathbb {R}^d$ is a finite set of points disjoint from $\mathcal {X}$ and G is an “incompatibility graph”. Then the algorithm of [5] is used, which is a polynomial delay algorithm for enumerating all the closed sets of a given closure operator.

New Enumeration Algorithm. We propose a new variant of the algorithm described above, Algorithm 1, inspired by a more geometric understanding of the enumeration method, relying on polyhedral subdivisions. There are three main improvements. They are described below.

In the first improvement we change the way the algorithm constructs the ground set $\mathcal {X}$ whose subsets are candidate point sets for the collection $\mathcal {A}$. In [2] $M_d$ is computed — using (1) — for each possible bit-vector $b \in \{0,1 \}^{d-2}$ and $\mathcal {X} := M_d^{-1} \cdot (\{1\} \times \{0,1\}^{d-1}) \smallsetminus \{ e_1\}$. Here we construct a larger ground set $\mathcal {X}$ as the union of all the old $\mathcal {X}$ sets. See Algorithm 1, lines 5–7.

To illustrate the difference of approaches in $d=2$ note that in Fig. 1 the old approach would construct two ground sets of four points each (corresponding to the two small squares to the right), while the new approach constructs a single ground set of six points. What we gain is that Algorithm 1 avoids enumerating many times a set A in the intersection of cells of $\mathcal {S}(P_0)$ (blue sets in Fig. 1). In this section, to simplify things, we translate the master polytope $Q(P_0)$ and its subdivision $\mathcal {S}(P_0)$ in the $\{x \in \mathbb {R}^d \mid x_1 = 1\}$ hyperplane, so that the origin is translated to $e_1$.

The second improvement is to exploit symmetries in a more sophisticated way. The symmetries we have in mind are translations “within” $\mathcal {S}(P_0)$. Note that the closure operator used in [2] satisfies stronger properties than those in Definition 8, in particular, it is idempotent, $(\subseteq ,\subseteq )$-monotone, and $\subseteq$-expansive. Letting $A \ddagger a := ((A \cup \{e_1\}) + e_1 - a ) \smallsetminus \{e_1\}$ for $a \in A$, we define a new closure operator as follows:

where $A \subseteq \mathcal {X}$. This new operator returns a single representative from an equivalence class of point sets A in the polyhedral subdivision $\mathcal {S}(P_0)$ (green sets in Fig. 1). The idea is that since all sets of points A in the equivalence class yield the same polytope, we only need a single representative, which we define as the maximum within the equivalence class with respect to $\preccurlyeq$. The new closure operator is used in line 10 of Algorithm 1.

The third improvement consists in considering a partial order on the set $L_{d-1}$ of $(d-1)$-dimensional 2-level polytopes, which is based on the number of vertices. The idea is that if the d-dimensional 2-level polytope P contains a facet having strictly more vertices than the current prescribed facet $P_0$, then it has been already enumerated before. We choose an ordering of $L_{d-1}$ that is consistent with this.

Table 1. Experimental results of enumeration algorithms (time is sequential).

Actually, the algorithm does not check that no facet of $P = \mathrm {conv}(A \cup \mathcal {F})$ has strictly more vertices than $P_0$, because we want to avoid unnecessary convex hull computations as much as possible. Instead, we check that this condition holds only for the facets of P that are adjacent to $P_0$, which is possible without computing any new convex hull, since we know already all facets of $P_0$. This improvement is implemented in line 12 of Algorithm 1.

Finally, in Theorem 9 we prove the correctness of Algorithm 1.

Theorem 9

Algorithm 1 outputs the list of all combinatorial types of 2-level d-polytopes, each with a simplicial core.

Implementation and Experiments. We implement the skeleton of Algorithm 1 in Perl. For demanding computations, such as isomorphism tests, convex hull computations, and linear algebra operations we use polymake [6], a standard library for polyhedral computation. The implementation is based upon and improves the implementation presented in [2]. The improvements described above in current section yield a significant speed-up in the algorithm, which is $\times 12$ for $d=6$. There are 447362 convex hulls (i.e. $96\,\%$ of total convex hulls) avoided in $d=6$ yielding a 0.065 ratio of the number of computed 2-level polytopes over the total number convex hulls computed. More interestingly, we enumerate all 2-level polytopes in one dimension higher than in [2], namely $d=7$. See Table 1 for more details on experimental results².

On the technical part, for $d=7$ we create 1150 jobs one for each 6-dimensional 2-level polytope and submit them to a computer cluster³. The vast majority of the jobs, namely 1132 finish in less than a day. The remaining 18 finished in a range from a week to a month. The use of high performance computing is crucial for this computation since the corresponding sequential time for this experiment is more than 5 years! The most time demanding job is the one corresponding to the simplex, which however corresponds to the known case of simplicial 2-level polytopes. Simplicial 2-level polytopes have been characterized in [10]. By applying the result in $d=7$ there exist exactly two simplicial 2-level 7-polytopes: the simplex and the cross-polytope.

3 Prescribing a Sequentially Hanner Facet

We start by the following property, which plays an important role in our analysis.

Definition 10

(Strong separation property). Let P be a d-dimensional polytope. We say that P satisfies the strong separation property if for every ordered pair $K_1$, $K_2$ of non-empty disjoint faces of P, there exists a facet F of P such that $F \supseteq K_1$ and $F \cap K_2 = \varnothing$.

In general, it is not true that all suspensions of a given 2-level polytope Q are 2-level. However, this is true when Q has the strong separation property.

Proposition 11

Let $Q \subseteq \mathbb {R}^{d-1}$ be a full-dimensional 2-level polytope that satisfies the strong separation property. Let G be one of its non-empty faces, and let $P \subseteq \mathbb {R}^d$ denote the suspension of Q with respect to G. Then every facet of P either is parallel to $\{0\} \times Q$ or intersects $\{0\} \times Q$ in a facet. In particular, P is a 2-level polytope.

All sequentially Hanner polytopes have the strong separation property.

Prescribing a Cubical Facet. Consider a 2-level d-polytope P one of whose facets is the $(d-1)$-cube $P_0 = \{0\} \times [-1,1]^{d-1} \subseteq \{x \in \mathbb {R}^d \mid x_1 = 0\}$. Let $P_1 \subseteq \{x \in \mathbb {R}^d \mid x_1 = 1\}$ denote the face of P opposite to $P_0$. Without loss of generality, assume that $e_1$ is a vertex of $P_1$. The master polytope $Q(P_0)$ is the cube $2P_0$. This larger cube is subdivided by the coordinate hyperplanes in the polyhedral subdivision $\mathcal {S}(P_0)$. The cells of $\mathcal {S}(P_0)$ are $2^{d-1}$ translated copies of $P_0$. It is easy to prove that $P_1$ is the translate of some face of $\mathcal {S}(P_0)$, and thus the translate of some face of $P_0$. In other words, P is a suspension. Combining this with Proposition 11, we obtain:

Proposition 12

A d-dimensional 2-level polytope P has a facet isomorphic to a $(d-1)$-cube if and only if it is isomorphic to some suspension of a $(d-1)$-cube.

Prescribing a Cross-Polytope Facet. This time, consider a 2-level d-polytope P one of whose facets is the $(d-1)$-cross-polytope $P_0 := \mathrm {conv}\{\pm e_2, \ldots , \pm e_d\} \subseteq \{x \in \mathbb {R}^{d} \mid x_1 = 0 \}$ and define $P_1 \subseteq \{x \in \mathbb {R}^{d} \mid x_1 = 1\}$ as before, so that $P = \mathrm {conv}(P_0 \cup P_1)$. Again, assume that $e_1$ is a vertex of $P_1$. Using the lattice decomposition property, we can prove that the vertices of $P_1$ are all of the form $e_1 + w_1 + w_2$ where $w_1$ and $w_2$ are vertices of the base $P_0$.

Using the properties of the embedding of P, we construct a bidirected graph $G = G(P)$ that encodes the vertices of the top face $P_1$. The node set of G is $V := \{2,\ldots ,d\}$, and for every vertex $x = e_1 \pm e_i \pm e_j$, $i,j \in V$, of $P_1$ that is distinct from $e_1$ we create an edge in G with endpoints i and j, each endowed with a sign that coincides with the signs of the corresponding coordinate of x.

The rest of the analysis is done by establishing properties of the bidirected graph G. The most important is the fact that G has no two disjoint edges. Next, we establish a form of sign-consistency for G: every two edges of G have the same sign at exactly one of their one or two common endpoints.

These two properties put extreme restrictions on the bidirected graph G. One possible case arises when all the edges of G have a common endpoint, which has the same sign in all the edges. This forces P to be a suspension. Moreover, the presence of a pair of parallel edges or loop automatically leads to the case of a prism. In the remaining case G is a triangle without pair of parallel edges or loop. This leads to the sporadic case of the hypersimplex $\varDelta (4,2)$. We obtain the following result.

Proposition 13

A d-dimensional 2-level polytope P has a facet isomorphic to a $(d-1)$-cross-polytope if and only if it is isomorphic to some suspension of a $(d-1)$-cross-polytope or to the hypersimplex $\varDelta (4,2)$.

Prescribing a Sequentially Hanner Facet. The following result generalizes Propositions 12 and 13.

Theorem 1

(Informal). The 2-level polytopes with a facet isomorphic to a sequentially Hanner polytope essentially coincide with the suspensions of sequentially Hanner polytopes.

4 Discussion

In this last section, we discuss suspensions of 2-level polytopes (called just suspensions below). As is supported by the theoretical and experimental results of this paper, suspensions seem to play an important role towards a broader understanding of the structure of general 2-level polytopes.

Since there are suspensions that are not 2-level, it is natural to ask what is the class of 2-level polytopes whose suspensions are always 2-level. Proposition 11 sheds some light in this direction by providing a sufficient condition for any suspension of a 2-level polytope to be 2-level. It remains open to find a necessary and sufficient condition.

Table 2. Number of 2-level suspensions s(d), 2-level polytopes $\ell (d)$, ratio of number of 2-level suspensions to 2-level polytopes, and maximum number of faces of 2-level polytopes f(d) for low dimensions d.

Another related question is the following: what fraction of 2-level d-polytopes are suspensions of $(d-1)$-polytopes? Table 2 gives the ratio for small dimension d. Excluding dimension 3, we observe that this fraction increases with the dimension. Using notation from Table 2, is true that $\ell (d) = O(s(d))$?

If one could prove that this is true, this would have strong consequences on $\ell (d)$. Let $c > 1$ be any constant such that $\ell (d) \leqslant c \cdot s(d)$. Since 2-level d-polytopes have at most $2^d$ vertices, each of them being affinely equivalent to 0 / 1-polytope, we have $f(d) \leqslant c^{d^2}$ provided we choose c large enough. Now assume that $\ell (d-1) \le c^{(d-1)^3}$ (this would be our induction hypothesis). Then we would have: $\ell (d) \leqslant c \cdot s(d) \leqslant c \cdot \ell (d-1) \cdot f(d-1) \leqslant c \cdot c^{(d-1)^3} \cdot c^{(d-1)^2} \leqslant c^{d^3}.$ In fact, a singly exponential upper bound on f(d) would imply $\ell (d) = 2^{O(d^2)}$. This would not contradict any known lower bound, since all known constructions of 2-level polytopes are ultimately based on graphs and do not imply more than a $2^{\varOmega (d^2)}$ lower bound on $\ell (d)$. For instance, stable sets of bipartite graphs show $\ell (d) \geqslant 2^{\frac{d^2}{4}-o(1)}$. Can one show at least $\ell (d) \leqslant 2^{\mathrm {poly}(d)}$? Independently of this, is it true that $f(d) = 2^{O(d)}$?