Karl-Franzens-Universität Graz & Technische Universität Graz

SPEZIALFORSCHUNGSBEREICH F 003

OPTIMIERUNG

und

KONTROLLE

Projektbereich DISKRETE OPTIMIERUNG

Tamás Fleiner  Volker Kaibel  Günter Rote

Upper Bounds on the

Maximal Number of Facets of 0/1-Polytopes

Bericht Nr. 122, endgültige Fassung — Jänner 1999

1’01

1’02

1’03

1’04

1’05 1’06 1’07 1’08 1’09

1’10

1’11 1’12 1’13 1’14 1’15 1’16 1’17 1’18 1’19 1’20 1’21 1’22 1’23 1’24 1’25 1’26 1’27 1’28 1’29 1’30 1’31 1’32

1’33 1’34 1’35 1’36 1’37 1’38 1’39 1’40

Upper ^{to appear in the European Journal of Combinatorics} Bounds on the Maximal Number of Facets of 0/1-Polytopes

Tamás Fleiner^{∗}  Volker Kaibel^{†}  Günter Rote^{‡}

January 27, 1999

Abstract We prove two new upper bounds on the number of facets that a d-dimensional 0/1-polytope can have. The first one is 2(d − 1)! + 2(d − 1) (which is the best one currently known for small dimensions), while the second one of O((d − 2)!) is the best known bound for large dimensions.

1 Introduction

Polytopes whose vertices have only coordinates 0 and 1 (0/1-polytopes) have been investigated in combinatorial optimization: to any set system over which one wants to optimize, one can naturally associate the 0/1-polytope which is the convex hull of the incidence vectors of all feasible sets. In trying to attack combinatorial optimization problems by linear programming, one needs a description of the facets of the corresponding polytopes. For several 0/1-polytopes coming from combinatorial optimization problems, most notably the traveling salesman polytope, the cut polytope, or the linear ordering polytope, many large classes of facet-defining inequalities have been identified.

So it seems interesting to ask how many facets a d-dimensional 0/1-polytope can have at all [14, Problem 0.15]. A complete census of all 0/1-polytopes with up to 5 dimensions with regard to various properties was done by Aichholzer [2]. The d-dimensional cross-polytope can be realized (combinatorially) as the 0/1-polytope conv{ e_{i}, 1 − e_{i} : 1 ≤ i ≤ d }, where e_{i} is the i-th canonical unit-vector and 1 is the all-ones vector, showing that d-dimensional 0/1-polytopes can have as many as 2^{d} facets. Starting with a special randomly generated 0/1-polytope of dimension 13 with more than 17 million facets (found by Christof [7]), and using some inductive construction due to Kortenkamp, Richter-Gebert, Sarangarajan, and Ziegler [11], one can show that the maximal numbers of facets of d-dimensional 0/1-polytopes grow at least as fast as 3.6^{d}.

On the other hand, Imre Bárány gave a nice argument that a d-dimensional 0/1polytope cannot have more than d! + 2d facets, which we will briefly review below

∗CWI, Kruislaan 413, 1098 SJ, Amsterdam, The Netherlands. Supported by the Netherlands Organization for Scientific Research (NWO). tamas@cwi.nl

†Universität zu Köln, Institut für Informatik, Pohligstr. 1, 50969 Köln, Germany. Partially supported by EU Esprit Long Term Research Project Nr. 20244 (ALCOM-IT).

kaibel@informatik.uni-koeln.de

‡Institut für Mathematik, Technische Universität Graz, Steyrergasse 30, A-8010 Graz, Austria. rote@opt.math.tu-graz.ac.at. Supported by the Spezialforschungsbereich Optimierung und Kontrolle, Projektbereich Diskrete Optimierung.

2’01 2’02 2’03 2’04

2’05 2’06 2’07 2’08 2’09 2’10 2’11 2’12 2’13 2’14 2’15 2’16 2’17 2’18 2’19 2’20 2’21 2’22 2’23 2’24

2’25 2’26 2’27 2’28 2’29 2’30 2’31

2’32

2’33 2’34

2’35

2’36 2’37

2’38 2’39 2’40 2’41 2’42 2’43

2’44

(Lemma 2) since we will need it in one of our proofs. Let f(d) be the maximal number of facets that a d-dimensional 0/1-polytope can have. Thus, we know that asymptotically

2^{const·d} ≤ f(d) ≤ 2^{const·d log d}

holds. The most interesting question (in this context) is whether there is an exponential upper bound on f(d) or whether f(d) grows faster than exponentially. In fact, the growth of f(d) in low dimensions indicates that an exponential upper bound is unlikely to exist ([7, 10], see also Table 1).

This paper contains two improved upper bounds. The first one in Section 2 is obtained very easily by a simple observation on projections of 0/1-polytopes and gives an upper bound of 2(d−1)!+2(d−1). The second one in Section 3 is obtained by a refinement of the first one and yields a bound of O((d − 2)!), which is a better bound for higher dimensions. Actually, the arguments that we use there also apply (slightly modified) to integer convex polytopes (i.e., polytopes with integral vertex coordinates) with vertex coordinates in {0, …, k} for a constant k ∈ ℕ. Therefore, we prove a more general theorem that bounds the number of facets (and even the numbers of i-dimensional faces for all 0 ≤ i ≤ d − 1) of integer convex polytopes with (vertex) coordinates bounded by a constant. In particular, this generalization will enable us also to give some non-trivial upper bounds on the number of i-faces of 0/1-polytopes for intermediate values of i via some kind of “detour” through more general integer polytopes. In Section 4 we calculate explicit bounds for the number of facets of 0/1-polytopes in low dimensions. Finally, in Section 5 we compare our bounds to some results from the literature, where the number of facets of an integer polytope is bounded in terms of its surface area or of its volume.

Some definitions and facts. By a polytope we will always mean a convex polytope, i.e., the convex hull of a finite set of points. An i-face is the short name of an i-dimensional face of a polytope. The 0-faces are the vertices and the (d−1)-faces of a d-dimensional polytope are the facets. For background information on polytopes we refer to Ziegler’s book [14].

We denote the d-dimensional unit hypercube by C^{d}. The d-dimensional crosspolytope with diameter 2r (or equivalently the l_{1}-ball of radius r) is

B^{d}(r) := conv{ re_{i}, −re_{i} : 1 ≤ i ≤ d } .

The ith coordinate hyperplane, which is orthogonal to e_{i}, is denoted by H_{i}. The orthogonal projection to H_{i} is

pr_{i}: (x_{1}, …, x_{d}) ↦ (x_{1}, …, x_{i−1}, 0, x_{i+1}, …, x_{d}) .

By C_{i}^{d} := pr_{i}(C^{d}) we denote the (d − 1)-dimensional unit hypercube in the coordinate hyperplane H_{i}.

The Euclidean length of a vector n = (n_{1}, n_{2}, …, n_{d}) is ∥n∥_{2} := \sqrt{∑_{i=1}^{d} n_{i}^{2}}, while its l_{1}-norm is ∥n∥_{1} := ∑_{i=1}^{d} |n_{i}|.

The Minkowski sum of sets A, B ⊂ ℝ^{d} is A + B := { x_{a} + x_{b} : x_{a} ∈ A, x_{b} ∈ B }; for k ∈ ℝ the k-blow up of A is k · A := { k · x : x ∈ A} and finally Vol^{d}(A) denotes the d-dimensional volume of A. The d-dimensional volume of a parallelotope P spanned by vectors x_{1}, x_{2}, …, x_{d} is

Vol^{d}(P) = |det(x_{1}, x_{2}, …, x_{d})| .

3’01

3’02

3’03

3’04

3’05

3’06 3’07

3’08 3’09 3’10 3’11

3’12 3’13

3’14

3’15

3’16

3’17 3’18 3’19 3’20 3’21 3’22 3’23

3’24 3’25

3’26 3’27 3’28 3’29 3’30 3’31 3’32 3’33

3’34 3’35 3’36 3’37 3’38

The volumes of the hypercubes and the cross-polytope are

Vol^{d}(C^{d}) = Vol^{d−1}(C_{i}^{d}) = 1

(for 1 ≤ i ≤ d) and

Vol^{d}(B^{d}(r)) = \frac{2^{d}r^{d}}{d!} .

Moreover for x ∈ ℝ^{d} we have Vol^{d}(k · A + x) = k^{d} Vol^{d}(A).

Observation 1. The volume Vol^{d}(P) of any d-dimensional integer polytope P is an integer multiple of \frac{1}{d!}. In particular, Vol^{d}(P) is at least \frac{1}{d!}.

Proof. A d-dimensional integer polytope can be subdivided into d-dimensional integer simplices, and every d-dimensional integer simplex is the image of the ddimensional standard simplex (having volume \frac{1}{d!}) under an affine transformation with integer coefficients.

Finally, we need a simple estimate for \sqrt[d]{d!}, which we obtain with the help of the inequality between the geometric and harmonic mean.

\sqrt[d]{d!} = (\sqrt[d]{\sqrt{1}\sqrt{2} … \sqrt{d}} )^{2} ≥ (\frac{d}{∑{d \atop i=1} \frac{1}{\sqrt{i}}} )^{2} ≥ (\frac{d}{∫_{0}^{d} \frac{1}{\sqrt{t}}dt})^{2} = (\frac{d}{2\sqrt{d}})^{2} = \frac{d}{4} (1)

(Stirling’s formula yields the more precise estimate \sqrt[d]{d!} = \frac{d}{e} + O(log d).)

2 A Simple Upper Bound by Projection

Let P be a d-dimensional 0/1-polytope. First note that we can assume that P lies in ℝ^{d}, since every d-dimensional 0/1-polytope P′ ⊂ ℝ^{d′} (with d′ > d) is affinely isomorphic to a d-dimensional 0/1-polytope P ⊂ ℝ^{d} by simply “projecting out” all coordinates that belong to a basis of a non-redundant and complete equation system describing the affine hull of P′. The analogous statement holds for integer polytopes with vertex coordinates in {0, …, k}.

The following lemma is due to Imre Bárány (see also [14, Problem 0.15], [11]).

Lemma 2. A d-dimensional 0/1-polytope P ⊂ ℝ^{d} has at most d!(1 − Vol^{d}(P)) + 2d facets.

Proof. If v ∈ {0, 1}^{d} \ P is a vertex of the hypercube that is not a vertex of P, then conv(P ∪ {v}) is a 0/1-polytope that can be subdivided into P and pyramids with apex v, whose bases are those facets of P which are deleted by the addition of v (i.e., in the terminology of Ziegler [14], the bases are those facets of P beyond which v lies). Iterating this process until all vertices of the hypercube are in the convex hull destroys all facets of P except the “trivial” ones (i.e., the ones that lie in facets of the hypercube). Thus the total number of facets of P cannot be larger than d!(1 − Vol^{d}(P)) + 2d.

Every facet of P is defined by an inequality which is uniquely determined up to multiplication by positive scalars. With respect to some coordinate i ∈ {1, …, d}, a facet of P that is defined by an inequality a^{T} x ≤ a_{0} is called a vertical facet of P if a_{i} = 0, an upper facet if a_{i} < 0, and a lower facet if a_{i} > 0. The following facts are well-known.

4’01 4’02 4’03 4’04

4’05

4’06 4’07

4’08

4’09

4’10

4’11 4’12 4’13 4’14 4’15 4’16 4’17 4’18 4’19

4’20

4’21

4’22

4’23

4’24

4’25 4’26 4’27 4’28 4’29

4’30

4’31

4’32

Lemma 3. Let P ⊂ ℝ^{d} be a d-dimensional polytope with facets F^{1}, …, F^{t}, and let i ∈ {1, …, d}. Then the projections of the lower (respectively upper) facets of P with respect to i form a subdivision of pr_{i}(P), i.e., their union is pr_{i}(P) and they have no common interior points. In particular, we have

∑_{j=1}^{t} Vol^{d−1}(pr_{i}(F^{j})) = 2 · Vol^{d−1}(pr_{i}(P)) .  (2)

We derive from Lemma 3 a simple new upper bound on the number of facets of a 0/1-polytope.

Theorem 4. A d-dimensional 0/1-polytope has at most

A_{d} := 2(d − 1)! + 2(d − 1)

facets, i.e., f(d) ≤ 2(d − 1)! + 2(d − 1) holds for every d.

Proof. Let P ⊂ ℝ^{d} be a d-dimensional 0/1-polytope in ℝ^{d}. For every lower or upper facet F of P the projection pr_{d}(F) is a (d − 1)-dimensional 0/1-polytope, which (by Observation 1) has volume at least \frac{1}{(d−1)!}. Thus, from Lemma 3 it follows that P cannot have more than 2(d − 1)! Vol^{d−1}(P′) lower and upper facets, where P′ := pr_{d}(P).

Vertical facets of P are projected to facets of P′. Since distinct vertical facets of P are projected to distinct facets of P′, the number of vertical facets of P is bounded from above by the number of facets of P′. But by Bárány’s argument (Lemma 2), P′ has at most

(d − 1)!(1 − Vol^{d−1}(P′)) + 2(d − 1)

facets. Summing up, this yields an upper bound of

f(d) ≤ 2(d − 1)! Vol^{d−1}(P′) + (d − 1)!(1 − Vol^{d−1}(P′)) + 2(d − 1)
= (d − 1)! Vol^{d−1}(P′) + (d − 1)! + 2(d − 1)
≤ 2(d − 1)! + 2(d − 1)

on the number of facets of P.

3 An Improved Upper Bound

In this section we refine the upper bound A_{d} of Theorem 4 using two ideas. Instead of projecting only along the d-th coordinate we project along all coordinate directions, and we try to exploit the fact that the projection of a non-vertical facet typically has larger (d − 1)-volume than 1/(d − 1)!. We need the following fact from linear algebra.

Lemma 5. If H is a hyperplane with normal vector n = (n_{1}, n_{2}, …, n_{d}), then

|n_{i}| = ∥n∥_{2} · Vol^{d−1}(pr_{H}(C_{i}^{d})),

where pr_{H} denotes the orthogonal projection to H.

5’01 5’02

5’03

5’04 5’05

5’06

5’07

5’08

5’09

5’10

5’11

5’12 5’13 5’14 5’15

5’16 5’17

5’18 5’19

5’20

5’21

5’22

5’23

5’24 5’25 5’26 5’27

5’28

5’29

5’30

Proof. Choose λ_{j} ∈ ℝ such that pr_{H}(e_{j}) = e_{j} + λ_{j}n. Consider the parallelotope P_{i} spanned by C_{i}^{d} and n. Clearly

|n_{i}| = Vol^{d}(P_{i}) = |det(n, e_{1}, e_{2}, …, e_{i−1}, e_{i+1}, …, e_{d})|
= |det(n, e_{1} + λ_{1}n, …, e_{i−1} + λ_{i−1}n, e_{i+1} + λ_{i+1}n, …, e_{d} + λ_{d}n)|
= |det(n, pr_{H}(e_{1}), …, pr_{H}(e_{i−1}), pr_{H}(e_{i+1}), …, pr_{H}(e_{d}))|
= ∥n∥_{2} · Vol^{d−1}(pr_{H}(C_{i}^{d}))

Corollary 6. If A lies in a hyperplane H and Vol^{d−1}(A) is finite and non-zero, then H has a normal vector n of the form

n = (± Vol^{d−1}(pr_{1}(A)), ± Vol^{d−1}(pr_{2}(A)), …, ± Vol^{d−1}(pr_{d}(A))) .

Proof. Lemma 5 implies that there is a normal vector of H of the form

n′ = (± Vol^{d−1}(pr_{H}(C_{1}^{d})), ± Vol^{d−1}(pr_{H}(C_{2}^{d})), …, ± Vol^{d−1}(pr_{H}(C_{d}^{d}))) .

On the other hand,

\frac{Vol^{d−1}(pr_{H}(C_{i}^{d}))}{Vol^{d−1}(C_{i}^{d})} = \frac{Vol^{d−1}(pr_{i}(A))}{Vol^{d−1}(A)} ,

since there is an isometry exchanging the role of H and H_{i}. The result follows.

We prove our main result in a slightly more general setting by extending our subject from 0/1-polytopes to polytopes whose vertices have coordinates in {0, …, k} for some constant k ∈ ℕ. This will enable us to derive some other interesting consequences for 0/1-polytopes later.

Theorem 7. There is a constant c ∈ ℝ such that if P ⊂ ℝ^{d} is a convex polytope with vertex coordinates in {0, 1, …, k} for some k ≥ 1, then

(a) P has at most

c · (d − 2)! · k^{d(d−1)/(d+1)}

facets, for d ≥ 2, and

(b) for every i with 0 ≤ i < d − 1, P has at most

c · (d − 2)! · (2(i + 1)k)^{d(d−1)/(d+1)}

i-dimensional faces.

Proof. (a) According to the remark at the beginning of Section 2 we can assume that P is d-dimensional, since the claimed bound is increasing in d. Let F^{1}, F^{2}, …, F^{t} be the facets of P, and define F_{i}^{j} := pr_{i}(F^{j}). Corollary 6 implies that each facet F^{j} has an outer normal vector n_{j} of the form

n_{j} = (d − 1)! · (± Vol^{d−1}(F_{1}^{j}), ± Vol^{d−1}(F_{2}^{j}), …, ± Vol^{d−1}(F_{d}^{j})) ,

which is integral, by Observation 1. Thus,

∑_{j=1}^{t} ∥n_{j}∥_{1} = (d − 1)! · ∑_{j=1}^{t} ∑_{i=1}^{d} Vol^{d−1}(F_{i}^{j}) .  (3)

6’01

6’02

6’03

6’04

6’05 6’06 6’07 6’08 6’09

6’10

6’11 6’12

6’13

6’14

6’15

6’16

6’17

6’18

6’19

6’20

6’21 6’22

6’23

6’24

6’25

Applying Lemma 3 we get

∑_{j=1}^{t} Vol^{d−1}(F_{i}^{j}) ≤ 2 · Vol^{d−1}(k · C_{i}^{d}) = 2 · k^{d−1} .

Summation over all coordinate directions i gives an upper bound for (3):

∑_{j=1}^{t} ∥n_{j}∥_{1} ≤ 2d! · k^{d−1}  (4)

From this relation we will derive our result, using only the fact that n_{1}, …, n_{t} are distinct nonzero integer vectors. For a given small dimension, the largest possible number t of such vectors can be worked out directly. This is done in Section 4 for k = 1 (i.e. for 0/1-polytopes). To get the general bound that we want to prove, we shall show that

t ≥ (d − 2)! · k^{d(d−1)/(d+1)}  (5)

implies that the average l_{1}-norm of n_{1}, …, n_{t} is Ω(d^{2} · k^{(d−1)/(d+1)}), see (7) and (9). Let us define

I^{d}(r) := B^{d}(r) ∩ ℤ^{d}
S^{d}(r) := I^{d}(r) \ I^{d}(r − 1)
Σ^{d}(r) := ∑_{x∈I^{d}(r)} ∥x∥_{1} = ∑_{i=0}^{r} i · |S^{d}(i)|

Observe that |I^{d}(r)| = Vol^{d}(I^{d}(r) + C^{d}) and I^{d}(r) + C^{d} ⊂ B^{d}(r + \frac{d}{2}) + \frac{1}{2} · 1, yielding

|I^{d}(r)| ≤ \frac{(2r + d)^{d}}{d!} .  (6)

Observe moreover that for r_{1} < r_{2} we have |S^{d}(r_{1})| ≤ |S^{d}(r_{2})|, implying

\begin{aligned}Σ^{d}(r) & = \frac{1}{2} ∑_{i=0}^{r} [i · |S^{d}(i)| + (r − i) · |S^{d}(r − i)|] \\ & ≥ \frac{1}{2} ∑_{i=0}^{r} \frac{r}{2}(|S^{d}(i)| + |S^{d}(r − i)|) = \frac{r}{2} ∑_{i=0}^{r} |S^{d}(i)| = \frac{r}{2}|I^{d}(r)| \end{aligned}

So we have

Σ^{d}(r) ≥ \frac{r}{2}|I^{d}(r)|  (7)

for r ∈ ℕ. (A more careful estimation shows that the constant \frac{1}{2} can be replaced by \frac{d}{d+1}.) Choose R ∈ ℕ such that

|I^{d}(R)| ≤ t < |I^{d}(R + 1)|  (8)

Using (5), (6), and (8), we get

(d − 2)! · k^{d(d−1)/(d+1)} < \frac{(2R + d + 2)^{d}}{d!} .

7’01

7’02

7’03

7’04

7’05 7’06 7’07

7’08

7’09

7’10 7’11

7’12 7’13

7’14 7’15

7’16

7’17 7’18 7’19 7’20 7’21 7’22 7’23 7’24 7’25

7’26

7’27 7’28 7’29

By (1), this implies

\begin{aligned}R & > \frac{1}{2} \sqrt[d]{d!(d − 2)!} · k^{(d−1)/(d+1)} − \frac{d}{2} − 1 \\ & > \frac{d}{8} (\frac{d − 2}{4})^{\frac{d−2}{d}} · k^{(d−1)/(d+1)} − \frac{d}{2} − 1 > c′d^{2} · k^{(d−1)/(d+1)} , \end{aligned}  (9)

for a certain 1 > c′ > 0 and large enough d. (A more careful analysis reveals that

\frac{R}{d^{2} · k^{(d−1)/(d+1)}} ≥ \frac{1}{2e^{2}} − O(\frac{log d}{d}) ,  (10)

as d → ∞.)

To finally estimate t, we bound the left hand side of inequality (4), using (8), (9), and (7):

2d! · k^{d−1} ≥ ∑_{j=1}^{t} ∥n_{j}∥_{1} ≥ Σ^{d}(R) + R · (t − |I^{d}(R)|)

≥ \frac{R}{2}|I^{d}(R)| + R · (t − |I^{d}(R)|) ≥ \frac{R}{2}(|I^{d}(R)| + t − |I^{d}(R)|)

≥ \frac{c′d^{2} · k^{(d−1)/(d+1)}}{2} · t

So, there is a d_{0} ∈ ℕ such that for d ≥ d_{0}, (5) implies

t ≤ \frac{4d!}{c′d^{2}} · k^{d(d−1)/(d+1)} ≤ \frac{4}{c′} (d − 2)! · k^{d(d−1)/(d+1)} .

Since c′ < 1, we get

t ≤ c(d − 2)! · k^{d(d−1)/(d+1)}

for c := \frac{4}{c′} and d ≥ d_{0}. By increasing the constant c if necessary, the inequality can be made true for all d ≥ 2.

(b) First we prove the case i = 0, using a construction which is similar to a trick of Andrews [3]. We construct from P another polytope

P′ := conv \{ \frac{1}{2}(x + y) : x and y are different vertices of P \} .

No vertex x of P belongs to P′, and any facet of P′ that separates x from P′ does not separate any other vertex z of P from P′. Thus the polytope P′ has at least as many facets as P has vertices, and the case i = 0 follows from part (a) of the theorem because 2·P′ ⊂ 2k ·C^{d} is an integer polytope. (Andrews [3] used a blow-up factor of 3 instead of 2.)

We reduce the case 1 ≤ i < d − 1 to the case i = 0 by selecting i + 1 affinely independent vertices x_{1}, x_{2}, …, x_{i+1} from each i-face F of P. The point x_{F} := \frac{1}{i+1} · ∑_{j=1}^{i+1} x_{j} lies in the relative interior of F, and therefore all points x_{F} are distinct. The points x_{F} are the vertices of the polytope

P′′ := conv{ x_{F} : F is an i-face of P },

since every i-face F of P has a hyperplane H with H ∩ P = F; it follows that H ∩ P′′ = {x_{F} }. Thus P′′ has a vertex for every i-face of P, and since (i + 1) · P′′ ⊂ (i + 1)k · C^{d} is an integer polytope, the result follows from the case i = 0.

8’01 8’02 8’03 8’04 8’05 8’06

8’07 8’08 8’09

8’10

8’11

8’12

8’13 8’14 8’15 8’16 8’17 8’18

8’19

8’20 8’21 8’22

8’23

8’24 8’25 8’26 8’27 8’28 8’29 8’30 8’31 8’32 8’33 8’34 8’35

8’36

8’37 8’38

For d = 2, i. e., for polygons, the precise asymptotic bound of Theorem 7(a) is not difficult to derive, see Thiele [13] or Acketa and Žunić [1]; see also [14, Exercise 4.15, p. 122]. (For the case when the circumference of the polygon is bounded instead of the bounding box, as in Theorem 9 (a),(b) in Section 5 below, the precise asymptotic bound is given in Jarník [8].)

If we set k = 1 in Theorem 7 then we get O((d − 2)!) bounds for 0/1-polytopes:

Corollary 8. There is a constant c ∈ ℝ such that for d ≥ 2, every d-dimensional 0/1-polytope has at most

c · (d − 2)!

facets (i.e., f(d) ∈ O((d − 2)!)) and at most

c · (2(i + 1))^{d(d−1)/(d+1)} · (d − 2)!

i-faces, for every i with 0 ≤ i < d − 1.

For small values of i (e.g., i = 0, 1) this is not very interesting, since the maximum number of vertices of a 0/1-polytope is of course 2^{d}, and the number of i-faces is trivially bounded by \binom{2^{d}}{i+1}. But for larger intermediate values of i we get non-trivial bounds.

For the constant c in the bounds of Theorem 7 and Corollary 8, a more thorough analysis shows that, for large dimensions d, one can take

c = 4e^{2} + O(\frac{log d}{d}) ≈ 29.55 .

For the number of facets of 0/1-polytopes, the resulting bound in Corollary 8 should therefore be better than the easy bound A_{d} of Theorem 4 as soon as d is larger than c/2 ≈ 15.

4 Explicit Bounds in Low Dimensions

Table 1 gives numerical values of various lower and upper bounds on the number f(d) of facets of a d-dimensional 0/1-polytope. The first column of numbers contains the largest known examples, in terms of the number of facets, for all dimensions up to d = 13, from [7]. For d ≤ 5, these are known to be the true maxima (Aichholzer [2]). The second column gives the easy bound A_{d} = 2(d − 1)! + 2(d − 1) of Theorem 4. We see that it is precise for d ≤ 3, but departs more and more from the lower bounds as d gets higher. The third column U_{d} is a precise version of the bound in Corollary 8, which is obtained directly from (4). Instead of using the estimates that lead to the proof of Theorem 7, we can enumerate the integer vectors in the successive l_{1}-spheres S^{d}(1), S^{d}(2), S^{d}(3), … as long as their total l_{1}-length does not exceed the bound 2d! from (4). The number of points in these spheres is given by the formula

|S^{d}(r)| = ∑_{k=1}^{d} 2^{k}\binom{d}{k}\binom{r − 1}{k − 1} .

The k-th term of this sum is the number of vectors x ∈ S^{d}(r) with k nonzero coefficients.

9’01 9’02 9’03 9’04 9’05 9’06

9’07

9’08 9’09 9’10 9’11 9’12 9’13 9’14 9’15 9’16 9’17

9’18

9’19 9’20

d  best lower bound  f(d) ≤ A_{d}  f(d) ≤ U_{d} R U_{d}/A_{d}
1  f(d) = 2 = 2^{d}  2  2 1 1.000
2  = 4 = 2^{d}  4  4 2 1.000
3  = 8 = 2^{d}  8  9 2 1.125
4  = 16 = 2^{d}  18  28 2 1.555
5  = 40 ≥ 2.091^{d}  56  100 3 1.785
6 f(d) ≥ 121 ≥ 2.223^{d}  250  469 4 1.876
7  ≥ 432 ≥ 2.379^{d}  1,452  2,570 5 1.769
8  ≥ 1675 ≥ 2.529^{d}  10,094  16,328 6 1.617
9  ≥ 6875 ≥ 2.669^{d}  80,656  118,404 7 1.468
10  ≥ 41,591 ≥ 2.896^{d}  725,778  983,516 8 1.355
11  ≥ 250,279 ≥ 3.095^{d}  7,257,620  9,044,131 10 1.246
12 ≥ 1,975,935 ≥ 3.346^{d}  79,833,622  92,580,349 11 1.159
13 ≥ 17,464,356 ≥ 3.606^{d}  958,003,224  1,028,972,176 13 1.074
14  12,454,041,626  12,499,470,015 15 1.003
15  174,356,582,428  164,305,261,217 17 0.942
16  2,615,348,736,030 2,324,510,568,224 19 0.888
17  41,845,579,776,032 35,227,585,773,379 22 0.841
18  711,374,856,192,034 565,675,688,445,291 24 0.795

Table 1: Lower and Upper Bounds for f(d)

The bound can be slightly improved by taking into account that we only have to consider primitive vectors as normal vectors of facets, i. e., vectors where the greatest common divisor of its components is one. Each imprimitive vector is a positive multiple of some shorter primitive vector and does therefore not correspond to a new facet direction. The number of nonzero primitive vectors in the l_{1}-ball B^{d}(r) can be computed conveniently by the inclusion-exclusion formula

(|I^{d}(r)| − 1) − ∑_{p_{i}≤r}(|I^{d}(⌊\frac{r}{p_{i}} ⌋)| − 1) + ∑_{p_{i}<p_{j}≤r}(|I^{d}(⌊\frac{r}{p_{i}p_{j}} ⌋)| − 1) − ⋯,

where p_{1}, p_{2}, … is an enumeration of the primes. The number of primitive vectors in S^{d}(r) is computed easily from these formulas. If the imprimitive vectors were not excluded, the bound on f(5) would be 103 instead of 100. For smaller d, this has no effect, and for larger d it usually means an improvement in U_{d} somewhere around the middle digit of each figure.

The column titled ‘R’ specifies the l_{1}-radius R of the U_{d}-th primitive vector. One can check that this value is roughly in accordance with the estimate R ≈ \frac{d^{2}}{2e^{2}} from (10). The last column is the quotient of the bounds U_{d} and A_{d}. The asymptotically stronger bound is never much worse than the easy bound of Theorem 4 and starts to beat it for d ≥ 15 as predicted at the end of the previous section.

5 Conclusion

Our results are related to a classical theorem of Andrews about vertex numbers of integral polytopes with bounded volume or surface area.

10’01 10’02

10’03

10’04

10’05

10’06

10’07

10’08

10’09

10’10 10’11 10’12

10’13 10’14 10’15 10’16 10’17 10’18 10’19 10’20 10’21 10’22 10’23 10’24 10’25 10’26 10’27 10’28 10’29 10’30 10’31 10’32 10’33 10’34 10’35 10’36 10’37 10’38

Theorem 9. (Andrews [3, 4]) Let P be a d-dimensional convex polytope with integral vertices.

(a) If P has surface area S and t facets, then

t ≤ c_{d} · S^{d/(d+1)}.

(b) If P has surface area S and n vertices, then

n ≤ c′_{d} · S^{d/(d+1)}.

(c) If P has volume V and n vertices, then

n ≤ c′′_{d} · V^{(d−1)/(d+1)}.

Here, c_{d}, c′_{d}, and c′′_{d} are constants that depend on the dimension d.

For fixed dimension d, the growth in terms of the “size” k in our Theorem 7 is of the same order of magnitude as in Theorem 9: the volume and surface area of k · C_{d}, and hence of P, is bounded by k^{d} and by 2d · k^{d−1}, respectively.

The proofs of Theorem 9 in the literature pay no attention to the dependence of the bounds on d, although it is not hard to work out expressions for the constants c_{d}, c′_{d}, and c′′_{d} from these proofs. (By considering the standard simplex conv({0}∪{ e_{i} : 1 ≤ i ≤ d }), one sees immediately that the constants c_{d} and c′_{d} have to be at least (d − 1)!/2; thus, for varying dimensions d, the bounds on the number of facets that one can derive from Theorem 9(a) are weaker than Theorem 7 and Corollary 8.)

The proof of Theorem 9 (a) [3] uses a straightforward argument about the area of facets: if a facet F of P has a primitive normal vector n, then its area Vol^{d−1}(F) is at least ∥n∥_{2}/(d − 1)!. Our proofs of Theorems 4 and 7 use area arguments in a similar way. However, in order to get a better dependence on d, it has been advantageous to consider the norm ∥n∥_{1} of normal vectors instead of their Euclidean norm (see Lemma 6).

Andrews [3] derives Theorem 9 (b) from Theorem 9 (a) by constructing from a given polytope P another polytope P′ which has at least as many facets as P has vertices. Schmidt [12, pp. 66–68] and Bárány and Larman [6] considered also bounds on the number of i-faces for i other than 0 and d − 1, by using extensions of Andrews’ construction. Our proof of Theorem 7(b) uses a similar construction, but we tried to keep the dependence on d low.

The proof of Theorem 9 (c) is based on Theorem 9 (b), but it is much harder. Different proofs are due to Andrews [4], Konyagin and Sevast′yanov [9], Schmidt [12, pp. 64–66], and Bárány and Larman [6]. Bárány and Larman [6] have also proved that the bounds of Theorem 9 are asymptotically tight, by showing that the convex hull of the integer points in a ball of radius k has Ω(k^{d(d−1)/(d+1)}) vertices (and facets), for fixed d and k → ∞. For Theorem 9 (c), there was already an easy lowerbound example of Arnol′d [5]: the convex hull of integral points in the paraboloid x_{1}^{2} + ⋯ + x_{d−1}^{2} ≤ x_{d} ≤ k.

11’01

11’02 11’03 11’04

11’05 11’06 11’07 11’08

11’09 11’10 11’11

11’12 11’13 11’14

11’15 11’16 11’17

11’18 11’19

11’20 11’21 11’22

11’23 11’24

11’25 11’26 11’27 11’28

11’29 11’30

11’31 11’32 11’33

11’34 11’35

11’36 11’37

11’38 11’39 11’40

References

[1] Dragan M. Acketa and Joviša D. Žunić. On the maximal number of edges of convex digital polygons included into an m × m-grid, J. Combinatorial Theory Ser. A 69 (1995), 358–368.

[2] Oswin Aichholzer. Extremal properties of 0/1-polytopes of dimension 5. SFB Report 132, Technische Universität Graz, 1998. To appear in: Polytopes — Combinatorics and Computation (G. Kalai and G. M. Ziegler, eds.), DMV-Seminars, Birkhäuser-Verlag Basel.

[3] George E. Andrews. An asymptotic expression for the number of solutions of a general class of Diophantine equations. Trans. Amer. Math. Soc. 99 (1961), 272–277.

[4] George E. Andrews. A lower bound for the volume of strictly convex bodies with many boundary lattice points. Trans. Amer. Math. Soc. 106 (1963), 270–279.

[5] V. I. Arnol′d. Statistics of integral convex polygons (in Russian). Funktsionalnyǐ Analiz i ego Prilozheniya 14 (1980), no. 2, 1–3. English translation: Funct. Anal. Appl. 14 (1980), 79–81.

[6] Imre Bárány and David G. Larman. The convex hull of the integer points in a large ball. Math. Annalen 312 (1998), 167–181.

[7] Thomas Christof. SMAPO — “Small” 0/1-polytopes in combinatorial opti-

mization. World-Wide-Web page, http://www.iwr.uni-heidelberg.de/iwr/
comopt/soft/SMAPO/SMAPO.html, July 1997.

[8] V. Jarník. Über die Gitterpunkte auf konvexen Kurven. Mathematische Zeitschrift 24 (1926), 500–518.

[9] S. V. Konyagin and K. A. Sevast′yanov. A bound, in terms of its volume, for the number of vertices of a convex polyhedron when the vertices have integer coordinates (in Russian). Funktsionalnyǐ Analiz i ego Prilozheniya 18 (1984), no. 1, 13–15. English translation: Funct. Anal. Appl. 18 (1984), 11–13.

[10] Ulrich Kortenkamp. 0/1-Polytopes with many facets. World-Wide-Web page,

http://www.math.tu-berlin.de/~hund/01-Olympics.html, 1997.

[11] Ulrich Kortenkamp, Jürgen Richter-Gebert, Aravamuthan Sarangarajan, and Günter M. Ziegler. Extremal properties of 0/1-polytopes. Discrete & Computational Geometry 17 (1997), 439–448.

[12] Wolfgang M. Schmidt. Integer points on curves and surfaces. Monatsh. Math. 99 (1985), 45–72.

[13] Torsten Thiele. Extremalprobleme für Punktmengen. Diplomarbeit, Institut für Informatik, Freie Universität Berlin (1991).

[14] Günter M. Ziegler. Lectures on Polytopes. Graduate Texts in Mathematics, volume 152, Springer-Verlag, New York, Berlin, Heidelberg, 1995. Revised printing, 1998.