0-1 polytopes with many facets

Imre Bárány^{∗} Rényi Institute of Mathematics Hungarian Academy of Sciences POB 127, Budapest, 1364 Hungary

and

Department of Mathematics University College London

Gower Street, London, WC1E 6BT, UK

barany@renyi.hu

Attila Pór^{†} Department of Geometry

Eötvös University Kecskeméti u. 11–13, Budapest, 1053 Hungary

porati@cs.elte.hu

July 27, 2000

Abstract

There exist n-dimensional 0-1 polytopes with as many as (\frac{cn}{log n})^{\frac{n}{4}} facets. This is our main result. It answers a question of Komei Fukuda and Günter M. Ziegler.

∗Partially supported by Hungarian National Foundation Grants T 029255 and T 032452 †Partially suppotred by the Soros Foundation, grant 2223886

1 Introduction

A 0-1 polytope is, by definition, the convex hull of some 0-1 vectors from n-space. Properties of 0-1 polytopes, especially structured ones, play an important role in combinatorial optimization where the target is, quite often, a complete or concise description of the facets of the polytope. This task turned out to be difficult for several classes of 0-1 polytopes, most notably for the traveling salesman polytope [GP], [ABCC] and for the cut polytope [DL]. We don’t know for instance the answer to the innocent question ”How many facets has the traveling salesman polytope? or the cut polytope?” It was K. Fukuda and G. M. Ziegler who, in several lectures and papers [F], [KRSZ],

[Z] have drawn attention to this attractive and important problem, and asked for good estimates for the maximum number of facets an n-dimensional 0-1 polytope can have. Write g(n) for this maximum. It is almost elementary to see that 2n! is an upper bound for g(n). Stronger is the result of Fleiner, Kaibel, and Rote [FKR]:

g(n) ≤ 30(n − 2)!

for large enough n. Using the blowing up technique [KRSZ] and T. Christof’s construction of a 13-dimensional 0-1 polytope with more than 3.6^{13} facets, it can be shown that, again for large enough n,

g(n) > 3.6^{n}.

Earlier, Fukuda gave a similar example with 3.26^{n} facets (see [KRSZ]), based on the computational experience [F] concerning the behaviour of the number of facets in random 0-1 polytopes, as the number of vertices changes. The main result of this paper is that g(n) grows superexponentially:

Theorem 1.1. There is a positive constant c such that

g(n) > (\frac{c n}{log n})^{\frac{n}{4}} .

The construction giving this lower bound is random. It is perhaps instructive to see here how the number of facets of random polytopes behave. The best analogy comes from the random polytope P_{N} = P_{N}^{n} whose vertices v_{1}, …, v_{N} are chosen randomly, independently and uniformly from the sphere S^{n−1}. The expected number of facets, E[f_{n−1}(P_{N})], of P_{N} is asymptotically constN when n is fixed and N → ∞. But here we are interested in the case when n → ∞ and N < 2^{n}. There is a simple formula in Buchta et al. [BMT] which can be used to show that in the range 2n < N < 1.5^{n}, say,

(c_{1} log \frac{N}{n} )^{\frac{n}{2}} < E[f_{n−1}(P_{N})] < (c_{2} log \frac{N}{n} )^{\frac{n}{2}}

with suitable positive constants c_{1} and c_{2}.

Note that a 0-1 polytope has all of its vertices on a sphere. It is tempting to believe that a random 0-1 polytope, K_{N}, on N vertices behaves similarly. This may be even true for arbitrary 0-1 polytopes as well. In particular, it seems likely that

g(n) < (c_{3}n)^{\frac{n}{2}} .

Here and throughout the paper c, c_{1}, … and b, b_{1}, … denote positive constants that are independent of n and N. For further information on 0-1 polytopes the reader is advised to consult G. M. Ziegler’s thorough and recent survey [Z].

2 The model, the result, the idea

Write C = C^{n} = [−1, 1]^{n} for the n-dimensional ±1 cube. (This is more convenient to work with.) Let Z be a random variable distributed uniformly over {−1, 1}, and let Z_{1}, …, Z_{n} be independent random variables each distributed like Z. Set \underline{Z} = (Z_{1}, …, Z_{n}). Thus \underline{Z} is uniformly distributed over the 2^{n} vertices of C. Take N independent copies of \underline{Z}, namely \underline{Z}_{1}, …, \underline{Z}_{N} and define

K_{N} = conv\{\underline{Z}_{1}, …, \underline{Z}_{N}\} ,

the convex hull of the vectors \underline{Z}_{1}, …, \underline{Z}_{N}. This is going to be our random 0-1, or rather ±1, polytope on N vertices. Note, however, that some vertices may be repeated. (K_{N} is one of the usual models of random ±1 polytopes.)

We can state our main result now. Assume

(∗) exp\{c_{4}(log n)^{2}\} < N < exp \{c_{5} \frac{n}{log n}\} .

Here one can take any constants c_{4} ≤ 1 and c_{5} ≥ 1.

Theorem 2.1. Under condition (∗)

E[f_{n−1}(K_{N})] > (c_{6} log N)^{\frac{n}{4}} .

If the expected number of facets is large, then, of course, there has to be an example where the number of facets is large. We will, in fact, prove this stronger statement in a form that implies Theorem 2.1.

Theorem 2.2. Under condition (∗), there exists a polytope K_{N} with

f_{n−1}(K_{N}) > (c_{7} log N)^{\frac{n}{4}} .

The proof of this result is based on several lemmas, some of them quite involved. So we first present the basic idea, which is simple, rather informally. Assume x ∈ C and define

p(x, N) = Prob[x ∈ K_{N}].

General principles would tell that, for most x ∈ C, p(x, N) is either close to one or close to zero. To be more specific, set

P (t) = {x ∈ C : p(x, N) ≥ t}.

Our approach is based on the fact that for all small ε > 0 and large n P (1 − ε) ⊂ P (ε), of course, but the drop from 1 − ε to ε is very abrupt: P (ε) is in a small neighbourhood of P (1−ε). This shows that P (1−ε) ⊂ K_{N} with high probability. But only a tiny fraction of K_{N} lies outside P (ε) : most of the boundary of P (ε) is outside K_{N}. Thus most of the boundary of P (ε) is cut off by facets of K_{N}. These facets lie outside P (1 − ε). Comparing the surface area of P (ε) with the amount a facet can cut off from it gives the lower bound.

But how to find the sets P (1 − ε) and P (ε)? This is the point where we extensively use a beautiful result of Dyer, Füredi, and McDiarmid [DFM]. Their target was to determine the threshold N = N(n) such that K_{N} contains most of the volume of C. As they prove, this happens at N = (\frac{2}{\sqrt{e}})^{n}. Their method describes where p(x, N) drops from one to zero as n → ∞ and N = e^{αn}. The analysis carries over for other values of N. In our case higher precision is required as we need a good estimate on how fast p(x, N) drops from one to zero. We were able to control this only where the curvature of the boundary of P (ε) behaves nicely. This is perhaps the spot where the exponent n/2 for P_{N} (the random spherical polytope) is lost and we only get n/4 for K_{N}.

The paper is organized the following way. The next section is a slight digression where we give another upper bound on the number of facets of a 0-1 polytope. Then we state four lemmas related to p(x, N). Section 5 gives some geometric background, together with the proof of Theorems 2.1 and 2.2. The proofs of the probabilistic lemmas is in Sections 7 and 8. Geometric lemmas are proved in Section 9. Some auxiliary material is given in Section 6, their proofs are postponed to the last part.

3 Another upper bound

In the range given by condition (∗) we can improve the bound of Fleiner, Kaibel, and Rote [FKR]. In fact, the bound below is better as long as N is less than exponential in n.

Theorem 3.1. Every n-dimensional 0-1 polytope with N vertices has at most

(c_{8}n log \frac{N}{n} )^{\frac{n}{2}}

facets.

Proof. We are going to use the following volume estimate from [BáF] and [CP]. Given points x_{1}, …, x_{N} from B^{n}, the euclidean unit ball of R^{n},

\frac{vol conv\{x_{1}, …, x_{N}\}}{volB^{n}} ≤ (\frac{c_{0}}{n} log \frac{N}{n} )^{\frac{n}{2}} ,

where c_{0} is a universal constant.

Now let z_{1}, …, z_{N} be some vertices of the cube. Define the polytope P as P = conv{z_{1}, …, z_{N}}. Let π_{i} stand for the projection onto the subspace x_{i} = 0. Note that all the vertices of π_{i}(P) lie in an (n − 1)-dimensional ball of radius \sqrt{n − 1} (actually, on its boundary). The above estimate gives then

\frac{vol_{n−1}π_{i}(P)}{vol_{n−1} \sqrt{n − 1}B^{n−1}} ≤ (\frac{c_{0}}{n − 1} log \frac{N}{n − 1})^{\frac{n−1}{2}} .

Let L_{1}, … L_{m} be the facets of P. Note that vol_{n−1}π_{i}(L_{j}) cannot be zero for all i, and it is at least 1/(n−1)! if it is nonzero. So summing the equalities ∑_{1}^{m} vol_{n−1}π_{i}(L_{j}) = 2vol_{n−1}π_{i}(P) for all i we get

\frac{m}{(n − 1)!} ≤ ∑_{i=1}^{n} ∑_{j=1}^{m} vol_{n−1}π_{i}(L_{j}) = ∑_{i=1}^{n} ∑_{j=1}^{m} vol_{n−1}π_{i}(L_{j})

= 2 ∑_{1}^{n} vol_{n−1}π_{i}(P)

≤ 2nvol_{n−1} \sqrt{n − 1}B^{n−1} (\frac{c_{0}}{(n − 1)} log \frac{N}{n − 1})^{\frac{n−1}{2}} .

The estimate in the theorem follows now readily.

4 Dyer, Füredi, McDiarmid

From now on we will denote vectors (or points) by underlining in order to distinguish them from scalars. (We actually used this notation for the random vertex \underline{Z}.) So given a vector \underline{x} ∈ C define

q(\underline{x}) = inf\{Prob[\underline{Z} ∈ H] : \underline{x} ∈ H, H a halfspace\}

and for β > 0 define

Q^{β} = \{\underline{x} ∈ C : q(\underline{x}) ≥ exp\{−βn\}\}.

Note that Q^{β} is a convex polytope. In fact, it is the k-core of the vertices of C (with k = 2^{n}e^{−βn}), see [BP] and [E]. We introduce the function

f(x) = \frac{1}{2}(1 + x) log(1 + x) + \frac{1}{2}(1 − x) log(1 − x),

defined for x ∈ (−1, 1); at x = ±1 the limit exists and equals log 2. For \underline{x} = (x_{1}, …, x_{n}) we set

F (\underline{x}) = \frac{1}{n} ∑_{1}^{n} f(x_{i}).

Again, for positive β we define

F^{β} = \{\underline{x} ∈ C : F (\underline{x}) ≤ β\}.

f and consequently F are nicely behaving, strictly convex functions whose connection to K_{N} will become clear soon. To explain how q and F are related we are going to show, following [DFM],

Lemma 4.1. For \underline{x} ∈ (−1, 1)^{n}, we have q(\underline{x}) ≤ exp\{−nF (\underline{x})\}.

Proof. (from [DFM]) Check, first, that K(t), the so-called cumulant generating function equals

K(t) = log E[exp{tZ}] = log cosh t.

Then K′(t) = tanh t and for each x ∈ (−1, 1) there is a unique t with x = K′(t) = tanh t, and

t = h(x) = \frac{1}{2} log \frac{1 + x}{1 − x}.

Note, further, that

f(x) = −K(h(x)) + xh(x) and h(x) = f′(x).

Assume now that F (\underline{x}) = β (β > 0). Then \underline{x} is on the boundary of F^{β}. In order to estimate q(\underline{x}) we need to find a halfspace H of the form \{\underline{z} : \underline{t}(\underline{z} − \underline{x}) ≥ 0\} with Prob[\underline{Z} ∈ H] as small as possible. Consider the halfspace H(\underline{x}) (with \underline{0} ∉ H(\underline{x})) whose bounding hyperplane is tangent to F^{β} at \underline{x}. So

H(\underline{x}) = \{\underline{z} : \underline{t}(\underline{z} − \underline{x}) ≥ 0\}

with t_{j} = f′(x_{j}) j = 1, …, n. Markov’s inequality says Prob[X ≥ 0] ≤ E[e^{X}]. Using this

q(\underline{x}) ≤ Prob[\underline{Z} ∈ H(\underline{x})] = Prob [∑_{j=1}^{n} t_{j}(Z_{j} − x_{j}) ≥ 0]

≤ E [exp {∑_{j=1}^{n} t_{j}(Z_{j} − x_{j})}] = ∏_{j=1}^{n} E[exp{t_{j}(Z_{j} − x_{j})}]

= ∏_{j=1}^{n} exp{K(t_{j}) − x_{j}t_{j}} = exp {− ∑_{j=1}^{n}(x_{j}t_{j} − K(t_{j}))}

= exp\{−nF (\underline{x})\}.

It is surprising that this trivial estimate is sharp. Dyer, Füredi, and McDiarmid show, for certain values of \underline{x}, that

q(\underline{x}) ≥ exp\{−n(F (\underline{x}) + Δ)\}

with Δ ”small”. We will make this statement quantitative in Lemma 4.3. We have to set a few parameters next. Let α be defined as

α = \frac{log N}{n} or N = e^{αn}.

Then condition (∗) reads as

c_{4} \frac{(log n)^{2}}{n} < α < c_{5} \frac{1}{log n}.

We will need several small ε_{i} that are all of the form (with constant b_{i} > 0)

ε_{i} = b_{i}\sqrt{\frac{α}{n}} = b_{i} \frac{\sqrt{log N}}{n} .

The main discovery of Dyer, Füredi, and McDiarmid is that Q^{α} and F^{α} are close to each other and both of them approximate K_{N} quite well as N = e^{βn} (β a constant) and n → ∞. We will use several results from [DFM]. The next one is essentially part (b) of Lemma 2.1 of [DFM].

Lemma 4.2. For large enough n

Prob[Q^{α−ε_{1}} ⊂ K_{N}] > 0.99.

Define C^{∗} = \frac{1}{10}C, this is a shrunk copy of C. Dyer, Füredi and McDiarmid prove (the proof is hard) that F^{β} ⊆ Q^{α} for every α > β if n is large. We make this statement quantitative within C^{∗}.

Lemma 4.3. For large enough n

F^{α−ε_{2}} ∩ C^{∗} ⊆ Q^{α−ε_{1}}.

The next result is simple and is related to part (a) of Lemma 2.1 [DFM]

Lemma 4.4. For large enough n, at least half of the surface area of F^{α+ε_{3}} lying in C^{∗} is missed by K_{N} with probability at least 0.99.

One of our targets will be achieved once the last three Lemmas have been proved. Namely, the part of K_{N} lying in C^{∗} is weakly sandwiched between F^{α−ε_{2}} and F^{α+ε_{3}} with high probability. Here ”weakly sandwiched” means that

F^{α−ε_{2}} ∩ C^{∗} ⊆ K_{N}

and K_{N} misses half of C^{∗} ∩ ∂F^{α+ε_{3}}.

5 Geometric lemmas, proof of Theorem 2.2

We will need some geometric properties of

C^{∗} ∩ ∂F^{β}

where β = α ± ε_{i}.

Lemma 5.1. vol_{n−1}(C^{∗} ∩ ∂F^{β}) ≥ \frac{1}{2}(0.99\sqrt{2nβ})^{n}vol_{n−1}S^{n−1}

Lemma 5.2. Let H be a closed halfspace which is disjoint from C^{∗} ∩ F^{α−ε_{2}}. Then H contains at most

(3n(ε_{2} + ε_{3}))^{\frac{n−1}{2}} vol_{n−1}S^{n−1}

of the surface area of C^{∗} ∩ ∂F^{α+ε_{3}}.

Using Lemmas 4.2, 4.4, 5.1, 5.2 we can now give the proof of Theorem 2.2.

Proof. As we have seen, K_{N} is weakly sandwiched between F^{α−ε_{2}} and F^{α+ε_{3}} with probability 0.98. Let K_{N} be such a ±1 polytope. Each facet of K_{N} cuts off at most

(3n(ε_{2} + ε_{3}))^{\frac{n−1}{2}} vol_{n−1}S^{n−1}

of the surface area of C^{∗} ∩ ∂F^{α+ε_{3}}. In view of weak sandwiching, at least half of the surface area is cut off. Thus there are at least

\frac{0.5(0.99\sqrt{2n(α + ε_{3})})^{n}}{(3n(ε_{2} + ε_{3}))^{\frac{n−1}{2}}} ≥ (c_{7} log N)^{\frac{n}{4}}

facets.

Of course this proves Theorem 2.1 as well : The random ±1 polytope K_{N} is weakly sandwiched with high probability so

E[f_{n−1}(K_{N})] ≥ 0.98(c_{7} log N)^{\frac{n}{4}} .

6 Auxiliary lemmas

We fix the one-to-one correspondence between x ∈ (−1, 1) and t ∈ R via

t = f′(x) = h(x) = \frac{1}{2} log \frac{1 + x}{1 − x} and x = K′(t) = tanh t

throughout the paper. This induces a one-to-one correspondence between \underline{x} ∈ intC and \underline{t} ∈ R^{n} with

\underline{t} = n gradF (\underline{x}).

Lemma 6.1. The function

g(t) = \frac{f(tanh t)}{t^{2}} = −\frac{1}{t^{2}} log cosh t + \frac{tanh t}{t}

is strictly decreasing on [0, ∞). Its limit at t = 0 is 1/2.

The value of g(t) is 0.497... when tanh t = 0.1 implying

\frac{1}{2.02}t^{2} ≤ f(tanh t) ≤ \frac{1}{2}t^{2}, for t ∈ [−0.1, 0.1].

The last inequality shows that, when \underline{x} = (x_{1}, …, x_{n}) ∈ int C^{∗} , and \underline{t} = (t_{1}, …, t_{n}) with x_{j} = tanh t_{j},

\frac{1}{2.02n}|\underline{t}|^{2} ≤ F (\underline{x}) ≤ \frac{1}{2n}|\underline{t}|^{2}.

Let \underline{ω} ∈ S^{n−1} be a unit vector and define \underline{x}(\underline{ω}, β) as the unique point (if exists) on the boundary of F^{β} where

\underline{t}(\underline{ω}, β) = n gradF (\underline{x}(\underline{ω}, β)) = ϑ(\underline{ω}, β)\underline{ω}

for some positive ϑ(\underline{ω}, β). Define supp \underline{ω} = \{i ∈ \{1, …, n\} : ω_{i} ≠ 0\}. We have

Lemma 6.2. \underline{x}(\underline{ω}, β) is welldefined when

0 < β < \frac{|supp \underline{ω}|}{n} log 2

and ϑ(\underline{ω}, β) is strictly increasing in β.

Define

Ω = \{\underline{ω} ∈ S^{n−1} : \sqrt{\frac{n}{3 log n}} \underline{ω} ∈ C\}.

It is simple consequence of Dvoretzky’s theorem [D] that for large enough n,

Prob[\underline{ω} ∈ Ω|\underline{ω} ∈ S^{n−1}] > 0.99.

We will use this in the proof of

Lemma 6.3. Assume \underline{ω} ∈ Ω, and β < \frac{1}{606 log n}. Then \underline{x}(\underline{ω}, β) ∈ C^{∗}.

7 Proof of lemmas 4.2 and 4.4

Proof. (Lemma 4.2) This is a copy of the proof of Lemma 2.1(b) from [DFM] with the parameters adjusted properly. Suppose K_{N} is full-dimensional and there exists a point \underline{x} ∈ Q^{β}\K_{N} (where β = α − ε_{1} ). Then there is a facet of K_{N}, spanned by \underline{Z}_{i_{1}}, …, \underline{Z}_{i_{n}}, such that the corresponding halfspace contains K_{N} but excludes \underline{x}. Let J = \{j_{1}, …, j_{n}\} and define the event E_{J}:

The points \underline{Z}_{j_{1}}, …, \underline{Z}_{j_{n}} span a hyperplane and for one of the two corresponding halfspaces H both Prob[\underline{Z} ∉ H] ≥ e^{−βn} and the event \{\underline{Z}_{j} : j ∉ J} ⊂ H occurs.

It is clear that in our case the event E_{I} with I = {i_{1}, …, i_{n}} occurs. Let E denote the event that K_{N} is not full dimensional. Then

{Q^{β} ⊈ K_{N}} ⊂ E ∪ ⋃_{all J} E_{J}.

Thus, with notation D = {1, …, n},

Prob[Q^{β} ⊈ K_{N}] ≤ Prob[E] + ∑_{all J} Prob[E_{J}]

= Prob[E] + \binom{N}{n}Prob[E_{D}].

For any fixed set S of dimension less than n, Prob[\underline{Z} ∈ S] ≤ \frac{1}{2}, so Prob[E] ≤ \binom{N}{n}2^{−(N−n)} < 0.001 if n is large enough.

To bound Prob[E_{D}] suppose \underline{Z}_{1}, …, \underline{Z}_{n} are affinely independent. Let H_{1} and H_{2} be the two halfspaces they determine. If Prob[\underline{Z} ∉ H_{1}] ≥ e^{−βn}, then

Prob[\underline{Z}_{j} ∈ H_{1} : j = n + 1, …, N] ≤ (1 − e^{−βn})^{N−n}

and similarly for H_{2}. Hence

Prob[E_{D}|\underline{Z}_{1}, …, \underline{Z}_{n} aff. indep.] ≤ 2(1 − e^{−βn})^{N−n} < 2 exp\{−(N − n)e^{−βn}\}.

By removing the conditioning we get the same bound on Prob(E_{D}). Hence

Prob[Q^{β} ⊈ K_{N}] ≤ Prob(E) + \binom{N}{n}Prob[E_{D}]
< 0.001 + 2 exp{n log N − (N − n)e^{−βn}}
< 0.001 + 2 exp {n(e^{−βn} + log N) − Ne^{−βn}} .

Here β = α − ε_{1}, N = e^{αn}, ε_{1} = b_{1} \frac{\sqrt{log N}}{n}, and consequently Ne^{−βn} = e^{ε_{1}n} = exp\{b_{1}\sqrt{log N}\}. By condition (∗) this is much larger than the other term n(e^{−βn} + log N) in the exponent if b_{1} is chosen large enough. For instance, with b_{1} ≥ 3/\sqrt{c_{4}} and large enough n

Prob[Q^{β} ⊈ K_{N}] < 0.001 + 2 exp{−n^{2}} < 0.01.

Proof. (Lemma 4.4) Let \underline{x} be any point of the boundary of F^{β} (where β = α + ε_{3}). Then, using 4.1

Prob[\underline{x} ∈ K_{N}] ≤ Nq(\underline{x}) ≤ N exp\{−nF (\underline{x})\} ≤
≤ exp{αn − βn} = exp{−ε_{3}n} < 0.001

if n is large enough. Then the expectation of the surface area of C^{∗} ∩ ∂F^{β} contained in K_{N} is at most

∫_{C^{∗}∩∂F^{β}} Prob[\underline{x} ∈ K_{N}]d\underline{x} ≤ 0.001vol_{n−1}(C^{∗} ∩ ∂F^{β}).

So the probability that half of C^{∗}∩∂F^{β} is missed by K_{N} is at least 0.998.

8 The proof of lemma 4.3

The target is to show that the inequality q(\underline{x}) ≤ exp\{−nF (\underline{x})\} in Lemma 4.1 is rather sharp. First we need a quantitative version of Lemma 4.4 of [DFM]. We assume β = α ± ε.

Lemma 8.1. For every positive integer n the following holds. If 0 ≤ x_{i} ≤ 0.1, t_{i} = h(x_{i}) (i = 1, …, n) and nF (\underline{x}) ≥ 10, then

Prob [∑_{i=1}^{n} t_{i}(Z_{i} − x_{i}) ≥ 0] ≥ exp \{−nF (\underline{x}) − 3\sqrt{nF (\underline{x})}\} .

Proof. (It goes via exponential centering and a Berry-Esséen type theorem, just like in [DFM].) Let X_{1}, …, X_{n} be independent discrete random variables and set X = ∑ X_{i}. Define new random variables W_{i} with distribution

Prob[W_{i} = y] = e^{y} \frac{Prob[X_{i} = y]}{E[e^{X_{i}}]}.

Set W = ∑ W_{i} and observe

Prob[W = y] = ∑ ; y_{i}:∑ y_{i}=y ∏_{i=1}^{n} e^{y_{i}} \frac{Prob[X_{i} = y_{i}]}{E[e^{X_{i}}]}

= (∏_{1}^{n} E[e^{X_{i}}])^{−1} e^{y} Prob[X = y].

Apply this with X_{i} = t_{i}Z_{i} where, as usual, Z_{i} is uniform over {−1, 1}

Prob [∑_{1}^{n} t_{i}Z_{i} = w] = exp {∑_{1}^{n} K(t_{i})} e^{−w} Prob[W = w].

It is easy to check that E[W_{i}] = t_{i} tanh t_{i} = t_{i}x_{i}. Let Y = W − E[W] = W − ∑ t_{i}x_{i}. With this notation

Prob [∑_{1}^{n} t_{i}(Z_{i} − x_{i}) ≥ 0] = exp {∑_{1}^{n} K(t_{i})} ∑ ; w≥∑ t_{j}x_{j} e^{−w} Prob[W = w]

= exp {∑_{1}^{n}(K(t_{i}) − t_{i}x_{i})} ∑_{y≥0} e^{−y} Prob[Y = y].

Here ∑(K(t_{i})−t_{i}x_{i}) = − ∑ f(x_{i}) so we have to show that ∑_{y≥0} e^{−y}Prob[Y = y] is not too small. Setting Y_{j} = W_{j} − E(W_{j}) we have Y = ∑ Y_{j} and E(Y_{j}) = 0. Easy calculations give

σ_{j}^{2} = E[Y_{j}^{2}] = \frac{t_{j}^{2}}{cosh^{2} t_{j}} and E[|Y_{j}^{3}|] = (2 cosh t_{j} − \frac{1}{cosh t_{j}} ) σ_{j}^{3}.

We need a few simple estimates: when 0 ≤ x_{i} ≤ 0.1,

0 ≤ t_{i} ≤ h(0.1) = 0.1003353 … and 1 ≤ cosh t_{i} ≤ 1.00503 ….

It is easy to check that

\frac{E[|Y_{j}|^{3}]}{E[Y_{j}^{2}]} = t_{j}(1 + tanh^{2} t_{j})

is an increasing function in t_{j}. Thus, in the given range,

M = max_{j} \frac{E[|Y_{j}|^{3}]}{E[Y_{j}^{2}]} ≤ 0.102 ….

Define σ = \sqrt{∑ σ_{j}^{2}}. Now Berry’s theorem (see [Fe]) says that, under the present conditions, for all n, the distribution of \frac{1}{\sqrt{σ}} ∑_{1}^{n} Y_{j} differs from that of the standard normal by at most

\frac{33}{4} \frac{M}{σ} .

Now

σ = \sqrt{∑_{1}^{n} σ_{j}^{2}} = \sqrt{∑_{1}^{n} \frac{t_{j}^{2}}{cosh^{2} t_{j}}} ≥ \frac{1}{1.00503 …}\sqrt{∑_{1}^{n} t_{j}^{2}} ≥
≥ 0.99\sqrt{2nF (\underline{x})} ≥ 0.99\sqrt{20} > 4.427.

Since the standard normal between 0 and \sqrt{σ} > \sqrt{4.427} > 2.1 is larger than 0.49, Berry’s theorem implies that,

Prob [0 ≤ \frac{∑_{j}^{n} Y_{j}}{\sqrt{σ}} ≤ \sqrt{σ}] > 0.49 − 2\frac{33}{4} \frac{M}{σ} > \frac{1}{10}.

With this

∑_{y≥0} e^{−y} Prob[Y = y] ≥ ∑_{0≤y≤σ} e^{−y} Prob[Y = y]

≥ e^{−σ} Prob[0 ≤ ∑_{1}^{n} Y_{j} ≤ σ] ≥ \frac{1}{10}e^{−σ} ≥ e^{−3\sqrt{nF (\underline{x})}},

since σ = \sqrt{∑ σ_{j}^{2}} ≤ \sqrt{∑ t_{j}^{2}} ≤ \sqrt{2.02nF (\underline{x})} < 3\sqrt{nF (\underline{x})} − log 10, because nF (\underline{x}) ≥ 10.

Lemma 8.2. Assume α_{i} > 0 for i = 1, …, m. Then

Prob [∑_{1}^{m} α_{i}(Z_{i} − 0.1) ≥ 0] ≥ \frac{1}{m^{2}} exp\{−mf(0.1)\}.

Proof. Let H^{∗}, H respectively be the halfspaces

H^{∗} = \{\underline{x} ∈ R^{m} : ∑_{1}^{m} α_{i}(x_{i} − 0.1) ≥ 0\} ,

H = \{\underline{x} ∈ R^{m} : ∑_{1}^{m}(x_{i} − 0.1) ≥ 0\} .

Define σ : R^{m} → R^{m} to be the cyclic shift of the components of x, that is, σ(x_{1}, …, x_{m}) = (x_{m}, x_{1}, …, x_{m−1}). The orbit of \underline{x} under σ is, by definition, \{\underline{x}, σ(\underline{x}), σ^{2}(\underline{x}), … \}. As σ^{m}(\underline{x}) = \underline{x}, any orbit has at most m elements. If \underline{x} ∈ H then so is σ(\underline{x}). At least one element of each orbit with \underline{x} ∈ H is in H^{∗} as otherwise

∑_{j=1}^{m} α_{j}(σ^{k}(\underline{x})_{j} − 0.1) < 0 for all k = 0, 1, …, m − 1.

Summing these inequalities for all k we get

∑_{j=1}^{m}(α_{1} + … + α_{m})(x_{j} − 0.1) < 0,

a contradiction. Now we see that

Prob [∑_{1}^{m} α_{i}(Z_{i} − 0.1) ≥ 0] = Prob[\underline{Z} ∈ H^{∗}]

≥ \frac{1}{m}Prob [|\{i : Z_{i} = 1\}| ≥ 0.55m]

= \frac{1}{m} \frac{1}{2^{m}} ∑_{k=0.55m}^{m} \binom{m}{k} ≥ \frac{1}{m^{2}} exp\{−mf(0.1)\}

as a simple calculation using Stirling formula reveals.

Proof. (Lemma 4.3) We have to show that q(\underline{x}) ≥ exp\{−(α − ε_{1})n\} for each \underline{x} ∈ F^{α−ε_{2}} ∩C^{∗}, or, in other words, every halfspace H intersecting F^{α−ε_{2}} ∩C^{∗} contains at least 2^{n} exp{−(α − ε_{1})n} vertices of C. It suffices to show this for halfspaces H whose bounding hyperplane H^{o} is tangent to F^{α−ε_{2}} ∩ C^{∗}.

We show first, that H contains a point \underline{x} with F (\underline{x}) = α − ε_{2} on its boundary. If H^{o} touches F^{α−ε_{2}} then the point of tangency satisfies this condition. If not, then H contains a point \underline{y} with F (\underline{y}) < α − ε_{2} and there is a smallest face of C^{∗} containing \underline{y}. Since the vertices of C^{∗} are not contained in F^{α−ε_{2}} there is a point \underline{x} on this face with F (\underline{x}) = α − ε_{2}.

By symmetry we can suppose that all components of \underline{x} are nonnegative and in increasing order. Let n_{1} ∈ {1, …, n} be such that x_{n_{1}} < 0.1 and x_{n_{1}+1} = 0.1. Set \underline{t} = n gradF (\underline{x}) and let \underline{t}^{∗} be the normal to H^{o}. We will prove the lemma assuming that \underline{t}^{∗} is in the relative interior of the normal cone to F^{α−ε_{2}} ∩ C^{∗} at the point \underline{x}; this assumtion means that

t_{i}^{∗} = t_{i}  for i = 1, …, n_{1}
t_{i}^{∗} > t_{i}  for i = n_{1} + 1, …, n.

The statement of the lemma for general \underline{t}^{∗} follows from this easily.

Next we have to consider cases according to where the terms of the sum ∑_{1}^{n} f(x_{i}) = n(α − ε_{2}) are concentrated. If n_{1} ≥ n − 2000, then Lemma 8.1 applies: check that ∑_{1}^{n_{1}} f(x_{i}) ≥ n(α − ε_{2}) − 2000f(0.1) > 10 if n is large. Choose the last, at most 2000, Z_{i} to be 1 (i = n_{1} + 1, …, n). We get

Prob [∑_{i=1}^{n} t_{i}^{∗}(Z_{i} − x_{i}) ≥ 0] ≥ 2^{−2000}Prob [∑_{i=1}^{n_{1}} t_{i}(Z_{i} − x_{i}) ≥ 0]

≥ 2^{−2000} exp \{− ∑_{i=1}^{n_{1}} f(x_{i}) − 3\sqrt{∑_{i=1}^{n_{1}} f(x_{i})}\}

≥ exp \{−n(α − ε_{2}) − 3\sqrt{n(α − ε_{2})} − 2000 log 2\}

≥ exp {−n(α − ε_{1})} .

The last inequality follows when n and thus N is large enough if one chooses here, with ε_{i} = b_{i} \frac{\sqrt{log N}}{n}, i = 1, 2,

b_{2} ≥ 2b_{1} + 3.

If n_{1} < n − 2000, then set n_{2} = n_{1} + 2000 and write

Prob [∑_{i=1}^{n} t_{i}^{∗}(Z_{i} − x_{i}) ≥ 0] ≥ Prob [∑_{i=1}^{n_{2}} t_{i}(Z_{i} − x_{i}) ≥ 0] ×

×Prob [ ∑_{i=n_{1}+1}^{n_{2}}(t_{i}^{∗} − t_{i})(Z_{i} − x_{i}) + ∑_{i=n_{2}+1}^{n} t_{i}^{∗}(Z_{i} − x_{i}) ≥ 0] .

Lemma 8.1 applies to the first probability since ∑_{i=1}^{n_{2}} f(x_{i}) ≥ 2000f(0.1) > 10. It gives

Prob [∑_{i=1}^{n_{2}} t_{i}(Z_{i} − x_{i}) ≥ 0] ≥ exp \{− ∑_{i=1}^{n_{2}} f(x_{i}) − 3 \sqrt{∑_{i=1}^{n_{2}} f(x_{i})}\} .

Lemma 8.2 works for the second factor and shows that it is at least

\frac{1}{(n − n_{1})^{2}} exp\{−(n − n_{1})f(0.1)\}.

The last two inequalities combine to

Prob [∑_{i=1}^{n} t_{i}^{∗}(Z_{i} − x_{i}) ≥ 0]
≥ exp \{−nF (\underline{x}) − 3\sqrt{nF (\underline{x})} − 2000f(0.1) − 2 log(n − n_{1})\} .

The exponent here is −n(α − ε_{2}) − 3\sqrt{n(α − ε_{2})} − 2000f(0.1) − 2 log(n − n_{1}) which is larger than −n(α − ε_{1}), if in the definition of ε_{2}, the constant b_{2} is chosen large enough.

9 Proof of the geometric lemmas

Proof. (Lemma 5.1) A routine argument shows how to compute the product curvature κ(\underline{x}) of the surface given implicitly by F (\underline{x}) = β: it gives, at the point \underline{x}

\frac{1}{κ(\underline{x})} = \frac{|gradF (\underline{x})|^{n}}{detF′′} = \frac{|\underline{t}|^{n}}{∏{n \atop i=1} \frac{1}{1−x_{i}^{2}}} ≥ \frac{(2nβ)^{\frac{n}{2}}}{(0.99)^{−n}} ≥ (0.99\sqrt{2nβ})^{n}

since \underline{x} ∈ C^{∗} implies x_{i}^{2} ≤ 0.01. We use this in the well-known formula [BF] giving the surface area as the integral of \frac{1}{κ(\underline{x})} on S^{n−1}. Now with β = α + ε_{3}

vol_{n−1}(∂F^{β} ∩ C^{∗}) = ∫_{\underline{ω}∈S^{n−1}} \frac{1}{κ(\underline{x})}d\underline{ω}

≥ ∫_{\underline{ω}∈Ω}(0.99\sqrt{2nβ})^{n}d\underline{ω} ≥ \frac{1}{2}(0.99\sqrt{2nβ})^{n}vol_{n−1}S^{n−1}.

Proof. (Lemma 5.2) We can assume that the touching hyperplane H^{o} of the halfspace H is tangent to F^{α−ε_{2}} ∩ C^{∗} at the point \underline{x} with F (\underline{x}) = α − ε_{2}.

We assume, by symmetry, that all x_{i} ≥ 0. If \underline{x} is in int C^{∗} then H is welldefined with normal \underline{t} = n gradF (\underline{x}).

If \underline{x} is not in int C^{∗} then we can assume (as in the proof of Lemma 4.3) that the outer normal \underline{t}^{∗} of H is in the relative interior of the normal cone to C^{∗} ∩ F^{α−ε_{2}} at \underline{x}. Then \underline{t}^{∗} can be chosen so that

t_{i}^{∗} = t_{i} = f′(x_{i})  for 0 ≤ x_{i} ≤ 0.1, and
t_{i}^{∗} ≥ t_{i} = f′(0.1) for x_{i} = 0.1

Assume \underline{y} ∈ H ∩ C^{∗}. Then, as y_{i} − x_{i} ≤ 0 if x_{i} = 0.1,

∑_{i=1}^{n} t_{i}(y_{i} − x_{i}) ≥ ∑_{i=1}^{n} t_{i}^{∗}(y_{i} − x_{i}) ≥ 0,

showing that H ∩ C^{∗} ⊂ \{\underline{z} : \underline{t}(\underline{z} − \underline{x}) ≥ 0\}. So we may assume that the normal vector of H is just \underline{t} = n gradF (\underline{x}).

Now let \underline{w} ∈ H ∩ F^{α+ε_{3}} ∩ C^{∗}. Set \underline{u} = \underline{w} − \underline{x} which is clearly in 2C^{∗}. Then with suitable ζ_{i} ∈ [0, x_{i}] we have

F (\underline{w}) = F (\underline{x}) + (\underline{w} − \underline{x})gradF (\underline{x}) + \frac{1}{2}(\underline{w} − \underline{x})^{T}F′′(\underline{x})(\underline{w} − \underline{x})

+ \frac{1}{6} ∑_{i=1}^{n} \frac{f′′′(ζ_{i})}{n}(w_{i} − x_{i})^{3}

≥ α − ε_{2} + \frac{1}{2n} ∑_{i=1}^{n} \frac{1}{1 − x_{i}^{2}} u_{i}^{2} + \frac{1}{6n} ∑_{i=1}^{n} \frac{2ζ_{i}}{(1 − ζ_{i}^{2})^{2}} u_{i}^{3}

≥ α − ε_{2} + \frac{1}{2n} ∑_{i=1}^{n} u_{i}^{2} (\frac{1}{1 − x_{i}^{2}} − \frac{2x_{i}}{3(1 − x_{i}^{2})^{2}} u_{i}) ≥ α − ε_{2} + \frac{|\underline{u}|^{2}}{3n} .

On the other hand \underline{w} ∈ F^{α+ε_{3}}, so

α + ε_{3} ≥ F (\underline{w}) ≥ α − ε_{2} + \frac{|\underline{u}|^{2}}{3n}

implying

|\underline{u}| ≤ \sqrt{3n(ε_{2} + ε_{3})}.

This shows that the cut-off from ∂F^{α+ε_{3}} by the halfspace H is contained in a ball of radius \sqrt{3n(ε_{2} + ε_{3})} so its surface area is at most

(3n(ε_{2} + ε_{3}))^{\frac{n−1}{2}} vol_{n−1}S^{n−1}.

10 Proof of the auxiliary results

Proof. (Lemma 6.1) It is elementary to see that lim_{t→0} g(t) = 1/2. We have to show that, for all t ∈ (0, ∞), g′(t) ≤ 0, or, what is the same, t^{3}g′(t) ≤ 0. Direct computation gives

h(t) = t^{3}g′(t) = 2 log cosh t − 2t tanh t + \frac{t^{2}}{cosh^{2} t}.

As lim_{t→0} h(t) = 0, it is enough to see that h′(t) is nonpositive:

h′(t) = −\frac{2t^{2} sinh t}{cosh^{3} t} ≤ 0.

Proof. (Lemma 6.2) Fix \underline{ω}. Let ϑ ∈ (0, ∞) and define

x_{i} = tanh ϑω_{i} i = 1, …, n.

This gives a point \underline{x} ∈ C with ngradF (\underline{x}) = ϑ\underline{ω}. For fixed \underline{ω} ∈ S^{n−1}, the mapping ϑ ⟶ F (\underline{x}) = \frac{1}{n} ∑_{i=1}^{n} f(tanh ϑω_{i}) is strictly increasing and continuous, it is 0 at ϑ = 0 and its limit at ϑ → ∞ is \frac{1}{n}|supp \underline{ω}| log 2. This proves the first part of the statement. The second part follows from the monotonicity of ϑ ⟶ \frac{1}{n} ∑_{i=1}^{n} f(tanh ϑω_{i}).

Proof. (Lemma 6.3) Define λ = \sqrt{\frac{n}{3 log n}}. As \underline{ω} ∈ Ω, λ\underline{ω} ∈ C and \frac{λ}{10} \underline{ω} ∈ C^{∗},

so there is a point \underline{x} ∈ C with n gradF (\underline{x}) = \frac{λ}{10} \underline{ω}. We may assume, by symmetry, that all ω_{i} ≥ 0. Of course x_{i} = tanh \frac{λ}{10}ω_{i}. At this point

F (\underline{x}) ≥ \frac{1}{2.02n}|\frac{λ}{10}\underline{ω}|^{2} > \frac{1}{606 log n}.

Monotonicity implies then, that

0 ≤ x(\underline{ω}, β)_{i} = tanh ϑ(\underline{ω}, β)ω_{i} <
< tanh \frac{λ}{10}ω_{i} ≤ tanh 0.1 < 0.1

for all i = 1, …, n.

References

[ABCC] D. Applegate, R. Bixby, V. Chvátal, W. Cook: On the solution of traveling salesman problems, in: ”International Congress of Mathematics” (Berlin 1998), Documenta Math., Extra Volume ICM 1998, Vol. III, 645–656.

[BP] I. Bárány, M. Perles: The Carathéodory number for the k-core, Combinatorica, 10 (1990), 185–194.

[BáF] I. Bárány, Z. Füredi: Computing the volume is difficult, Discrete Comp. Geom., 2 (1987), 319–326.

[BF] T. Bonnesen, W. Fenchel: Theorie der konvexen Körper, Berlin, Springer 1934.

[BMT] C. Buchta, J. Müller, R. F. Tichy: Stochastical approximation of convex bodies, Math. Ann. 271 (1985), 225–235.

[CP] B. Carl, A. Pajor: Gelfand numbers of operators with values in a Hilbert space, Invent. Math., 94 (1988), 479–504.

[DL] M. M. Deza, M. Laurent: Geometry of Cuts and Metrics, Algorithms and Combinatorics 15, Springer-Verlag, Berlin Heidelberg 1997.

[D] A. Dvoretzky: Some near-sphericity results, Proc. Sympos. Pure Math. Vol VII. 203–210 AMS., Providence, R.I., 1963.

[DFM] M. E. Dyer, Z. Füredi, C. McDiarmid: Volumes spanned by random points in the hypercube, Random Structures and Algorithms, 3 (1992), 91–106.

[E] J. Eckhoff: Helly, Radon, and Carathéodory type theorems, in: Handbook of Convex Geometry, (d. P.M. Gruber, J. Wills), North Holland, (1993), 389–448.

[Fe] W. Feller: An Introduction to Probability Theory and Its Applications, Vol. II, Wiley, New York, 1971.

[FKR] T. Fleiner, V. Kaibel, G. Rote: Upper bounds on the maximal number of facets of 0/1-polytopes, European J. Combinatorics, 21 (2000), 121–130.

[F] K. Fukuda: Lecture in Oberwolfach, 1995.

[GP] M. Grötschel, M. Padberg: Polyhedral Theory/Polyhedral Computations, in: E.L. Lawler, J.K. Lenstra, A.H.G. Rinnoy Kan, D.B. Schmoys (eds.), ”The traveling salesman problem”, Wiley 1988, 251–360.

[KRSZ] U. Kortenkamp, J. Richter-Gebert, A. Sarangarajan, G. M. Ziegler: Extremal properties of 0/1-polytopes, Discrete Comput. Geometry, 17 (1997), 439–448.

[Z] G. M. Ziegler Lectures on 0/1 polytopes, in: “Polytopes — Combinatorics and Computation” (G. Kalai and G. M. Ziegler, eds.), DMV-Seminars, Birkhäuser-Verlag Basel, 2000, 1–44, in print.