An Upper Bound on the Number of Facets of a 0-1-Polytope

G. Rote^{∗}

April 16, 1997

Theorem 1 A 0-1-polytope in d dimensions has at most 6.4 d!/\sqrt{d} facets.

Ziegler [3, Exercise 0.15^{∗}, p. 25] mentions an upper bound of d! + 2d, which follows from a simple volume argument due to Imre Bárány. By slightly refining this argument and trading the volume inside the polytope against the volume outside, several people [2] could improve this bound to d! − (d − 1)!.

The known lower bounds are exponential, the current record being 3.6^{d} for d → ∞ [1]. By a construction of [2], any d-dimensional 0-1-polytope with C^{d} vertices, for some constant C, gives rise to an infinite family of such polytopes for infinitely many d. Thus any particular 0-1-polytope gives rise to an exponential lower bound, and the best lower bound follows from a random polytopes in 13 dimensions whose facets were enumerated by computer.

Lemma 1 The surface area of a 0-1-polytope in d dimensions is at most 2d.

Proof. If a convex polytope A contains another convex polytope B then the surface area of A is bigger than that of B. This follows for example from Cauchy’s surfacearea formula, which represents the surface area of A as an integral of the (d − 1)- dimensional volumes of the orthogonal projections of A onto all (d − 1)-dimensional hyperplanes. Any 0-1-polytope is contained in the d-dimensional unit hypercube, which has surface area 2d. □

We assume that the given polytope is full-dimensional. Then each facet has a defining inequality ∑_{i=1}^{d} a_{i}x_{i} ≤ b which is unique up to multiplication with a positive constant.

Definition 1 A k-facet is a facet with exactly k nonzero coefficients a_{i} in the defining inequality. (1 ≤ k ≤ d)

∗Technische Universität Graz, Institut für Mathematik, Steyrergasse 30, A-8010 Graz, AUS-TRIA. (++43)316-873-5355 (office) -5351 (secretary) (43)316-382411 (home) FAX (43)316-873-5369. Electronic mail: rote@opt.math.tu-graz.ac.at World-wide-web home-page: http://www.tu-graz.ac.at/Rote

(Distinguish this from the notion of a k-face, which is usually taken to be a k-dimensional face.)

Lemma 2 The area of a k-facet of a d-dimensional 0-1-polytope is at least

\frac{\sqrt{k}}{(d − 1)!}.

Proof. Suppose without loss of generality that |a_{1}| ≤ |a_{2}| ≤ ⋯ ≤ |a_{k}| and a_{k+1} = ⋯ = a_{d} = 0. If we project the facet ortogonally onto the hyperplace x_{1} = 0 we get a (d − 1)-dimensional polytope, since a_{1} ≠ 0. It is a 0-1-polytope, and hence its volume is at least 1/(d − 1)!. When projecting from a hyperplane ∑_{i=1}^{d} a_{i}x_{i} = b with defining vector a orthogonally to the hyperplane x_{1} = 0 with defining vector e_{1} = (1, 0, …, 0)^{T}, the volume of each set is reduced by a constant factor, which is the cosine between the two normal vectors,

\frac{⟨a, e_{1}⟩}{∥a∥ · ∥e_{1}∥} = \frac{a_{1}}{\sqrt{a_{1}^{2} + a_{2}^{2} + ⋯ + a_{d}^{2}}} ≤ \frac{1}{\sqrt{k}} .

Hence the area of the original facet was at least \sqrt{k}/(d − 1)!. □

Let us denote by B_{k} the number of k-facets of the given polytope.

Lemma 3 The number B_{d} of d-facets in a d-dimensional 0-1-polytope is at most

\frac{2 d!}{\sqrt{d}}.

Proof. This follows from Lemmas 2 and 1. □

Lemma 4 The number B_{k} of k-facets in a d-dimensional 0-1-polytope is at most

\frac{2 d!}{(d − k)!\sqrt{k}} .

Proof. Consider a k-facet with defining inequality ∑_{i=1}^{d} a_{i}x_{i} ≤ b, with a_{1}, a_{2}, …, a_{k} ≠ 0 and a_{k+1} = ⋯ = a_{d} = 0. When we project the whole polytope onto the subspace spanned by the first k coordinate directions, we get a k-dimensional 0-1-polytope, for which the inequality ∑_{i=1}^{k} a_{i}x_{i} ≤ b defines a facet. By Lemma 3, the number of these facets is at most 2 k!/\sqrt{k}. This is the maximum number of k-facets with nonzero coefficients in the first k positions, and also the maximum number of k-facets with nonzero coefficients in any specified set of k positions. There are \binom{d}{k} choices for the positions of the nonzero coefficients, and this gives a total of

\binom{d}{k} · \frac{2 k!}{\sqrt{k}} = \frac{2 d!}{(d − k)!\sqrt{k}} .

□

Now we can complete the proof of the theorem. The total number of facets is

B_{d} + B_{d−1} + ⋯ + B_{2} + B_{1}

≤ ∑_{i=0}^{d−1} \frac{2 d!}{i!\sqrt{d − i}} = \frac{2 d!}{\sqrt{d}} · (∑_{i=0}^{d−1} \frac{\sqrt{1 + i/(d − i)}}{i!})

The last sum is monotonically decreasing for d ≥ 4, as can be easily checked. In fact, it takes its maximum of approximately 3.19514 at d = 4 and it converges to e. (This maximum is a remarkably close approximation to π, except that the digits are not quite in order.) This gives the bound of the theorem.

Remark. By bounding the total number of all k-facets with k ≥ d − log d by 2d!/\sqrt{d − log d} as in Lemma 3, and using Lemma 4 for the k-facets with k < d−log d, one can improve the constant in Theorem 1 from 6.4 to 2 + O(\frac{log d}{d}).

References

[1] Thomas Christof and Gerhard Reinelt, Efficient parallel facet enumeration for 0/1-polytopes. Preprint IWR Heidelberg, March 1997.

[2] Ulrich H. Kortenkamp, Jürgen Richter-Gebert, A. Sanangarajan, and Günter Ziegler, Extremal properties of 0/1-polytopes. Preprint TU Berlin, June 1996. to appear in Discrete and Computational Geometry 16 (no. 4) (1997).

[3] Günter Ziegler, Lectures on Polytopes. Springer-Verlag, 1995.