Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 42 (2001), No. 2, 431-437.

The Upper Bound Conjecture for Arrangements of Halfspaces

Gerhard Wesp^{1}

Institut für Mathematik, Universität Salzburg Hellbrunnerstr. 34, A-5020 Salzburg e-mail: gwesp@cosy.sbg.ac.at

Abstract. Let A be an arrangement of n open halfspaces in ℝ^{r−1}. In [2], Linhart proved that for r ≤ 5, the numbers of vertices of A contained in at most k halfspaces are bounded from above by the corresponding numbers of C(n, r), where C(n, r) is an arrangement realizing the alternating oriented matroid of rank r on n elements. In the present paper Linhart’s result is generalized to faces of dimension s − 1 for 1 ≤ s ≤ 4.

1. Introduction

An arrangement of halfspaces is an n-tuple of open halfspaces A = (H_{e}^{+})_{e=1}^{n} in ℝ^{r−1}. By H_{e} we denote the bounding hyperplane of H_{e}^{+} and by H_{e}^{−} the complementary open halfspace such that ℝ^{r−1} is the disjoint union H_{e}^{+} ∪ H_{e} ∪ H_{e}^{−}. For each x ∈ ℝ^{r−1} the position vector σ(x) with respect to the arrangement is defined as follows: σ(x) = (σ_{1}(x), …, σ_{n}(x)), where

σ_{e}(x) = \begin{cases}+ & if x ∈ H_{e}^{+} \\ 0 & if x ∈ H_{e} \\ - & if x ∈ H_{e}^{−}. \end{cases}

If two points have the same position vector, call them equivalent. We call the corresponding equivalence classes the (relatively open) faces of A. For two faces F and G, we write F ≤ G if F is a face of G in the usual convex-geometric sense. Together with elements ˆ0 and ˆ1 such

1Research supported by the Austrian Science Fund under grants P12313-MAT and S8303-MAT 0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix} 2001 Heldermann Verlag

\begin{matrix}s & r & g_{s,k}(n, r) \\ 1 & 2 & 2(1 + k) \\ 2 & 2 & 1 + 2k \\ 1 & 3 & (1 + k)n \\ 2 & 3 & n + 2kn \\ 3 & 3 & 1 + kn \\ 1 & 4 & (1 + k)(2 + k)(3n − 6 − 2k)/3 \\ 2 & 4 & (1 + k)(3(1 + k)n − 6 − 7k − 2k^{2}) \\ 3 & 4 & k(1 + k)(3n − 4 − 2k) + n \\ 4 & 4 & 1 − k(k(3 + 2k − 3n) − 5)/3 \\ 1 & 5 & n(1 + k)(2 + k)(3n − 9 − 2k)/12 \\ 2 & 5 & n(1 + k)(3(1 + k)n − 9 − 10k − 2k^{2})/3 \\ 3 & 5 & n(n − 1 − k(1 + k)(7 + 2k − 3n))/2 \\ 4 & 5 & n(3 + k(5 + k(3n − 6 − 2k)))/3 \end{matrix}

Table 1: Values of g_{s,k}(n, r), valid for 0 ≤ k < n − (r − s)

that ˆ0 < F < ˆ1 for all faces F of A, the set of faces forms a graded lattice under this order, denoted by L̂(A) and called the face lattice of A. We will also refer to the face lattice as the combinatorial structure of A. If the arrangement is essential, i.e. it has at least one vertex, then the rank of a face in L̂(A) is equal to its dimension plus one.

The weight weightF of a face F is the number of positive halfspaces which contain F, or, equivalently, the number of plus signs in its position vector. By g_{s,k}(A) we denote the number of faces of A having rank s and weight at most k. The Upper Bound Conjecture for arrangements of halfspaces can then be stated as follows:

Conjecture 1. For 1 ≤ s ≤ r, and all k ≤ n − (r − s),

g_{s,k}(A) ≤ g_{s,k}(n, r),

where g_{s,k}(n, r) is the number of rank s and weight at most k covectors of the alternating oriented matroid C(n, r) of rank r on n elements.

C(n, r) and the corresponding quantities g_{s,k}(n, r) are discussed in more detail in [5]. Here we just quote Table 1 which lists the g_{s,k}(n, r) for those r and s we’re concerned with in this paper.

A halfspace arrangement A is called polyhedral if

P (A) = ⋂_{e=1}^{n} cl H_{e}^{−}

is a (possibly unbounded) polyhedron with n facets.

In [5], the author also investigated a generalisation of Conjecture 1 for oriented matroids. Conjecture 1 in turn is a generalisation of McMullen’s [3] celebrated Upper Bound Theorem for convex polytopes, since for polyhedral arrangements g_{s,0}(A) is the number of (s − 1)- dimensional faces of P (A) and C(n, r) can be realized by a halfspace arrangement C(n, r) such that P (C(n, r)) is the dual of a cyclic polytope.

Historically, Conjecture 1 seems first to be mentioned in Eckhoff’s Handbook article [1], where the case s = r is stated in the dual language of point sets and semispaces. Then Linhart [2] solved the case s = 1 for r ≤ 5, and the author of the present paper extended his ideas in order to prove it for 1 ≤ s ≤ min(r, 4) in his thesis [5]. Since this thesis is of very limited distribution only, this paper serves the purpose of making the result available to a wider audience.

2. Statement of the result and proof

Theorem 2. Let A be an arrangement of n halfspaces in ℝ^{r−1}, r ≤ 5. Then for 1 ≤ s ≤ min(r, 4) and k ≤ n − (r − s),

g_{s,k}(A) ≤ g_{s,k}(n, r).

The proof requires a few lemmas which we state and prove before the proof of the theorem.

Lemma 3. For each polyhedral arrangement in ℝ^{r−1}, r ≤ 4, the assertion of Theorem 2 is true.

This lemma is a straightforward extension of Lemma 1 in [2] (using [4, Equation (6.106)]), so we don’t need to repeat the proof here.

Lemma 4. Let i, j, p, q be integers with p ≥ q ≥ 0 and j ≥ i ≥ 0. Then

\binom{q}{i}\binom{p}{j} ≥ \binom{p}{i}\binom{q}{j}.  (1)

Proof. If

\binom{q}{i}\binom{p}{j} = 0,

then either i > q or j > p. In both cases it follows that j > q and the right hand side of (1) is zero.

If the right hand side of (1) is zero, then there is nothing to prove. Otherwise, we have j ≤ q and therefore i ≤ j ≤ q ≤ p. Hence the left hand side is also nonzero. If i = j, then there is nothing to prove. Otherwise we consider the quotient

\binom{q}{i}\binom{p}{j} \{\binom{p}{i}\binom{q}{j}\}^{−1} = \frac{p(p − 1) ⋯ (p − j + 1)q(q − 1) ⋯ (q − i + 1)}{p(p − 1) ⋯ (p − i + 1)q(q − 1) ⋯ (q − j + 1)}
= \frac{(p − i)(p − i − 1) ⋯ (p − j + 1)}{(q − i)(q − i − 1) ⋯ (q − j + 1)}.

This quotient is ≥ 1, because all factors in the last line are positive and p ≥ q.

A halfspace arrangement in ℝ^{r−1} is called simple if each r-subset of the hyperplanes H_{e}^{0} determines an (r − 1)-simplex. It is sufficient to prove Theorem 2 for simple arrangements, since otherwise the arrangement may be transformed into a simple one by small perturbations of the hyperplanes such that none of the g_{s,k} decreases.

For faces F, G in L̂(A), we denote by [F, G] the closed interval between F and G, i.e. the set {F′ ∈ L̂(A): F ≤ F′ ≤ G}.

By f_{s,k}(A), we denote the number of rank s faces of A with weight equal to k. In the following lemma, the weight of a face is considered with respect to different arrangements. We use the notations _{S}weightF, _{S}f_{s,k} and _{S}g_{s,k} in order to specify the arrangement which determines the weights, f_{s,k} or g_{s,k} in question.

It is clear that each simple arrangement of r halfspaces has a unique bounded (r − 1)- simplex in its face lattice.

Lemma 5. Let S = (H_{1}^{+}, …, H_{r}^{+}) be a simple arrangement of halfspaces in ℝ^{r−1} with bounded (r − 1)-simplex T, and let p = _{S}weightT. Let S′ be the arrangement obtained from S by reversing the orientation of all r hyperplanes and let q = _{S′}weightT = r − p. If q ≤ p, then

Sg_{s,k}([ˆ0, T]) ≤ _{S′}g_{s,k}([ˆ0, T])

for 1 ≤ s ≤ r, 0 ≤ k ≤ r.

Proof. First, we compute the value of _{S}f_{s,k}([ˆ0, T]). The weight of a rank s face of T can be at most s, so _{S}f_{s,k}([ˆ0, T]) = 0 if k > s. Let k ≤ s. We count the number of rank s weight k faces of T in S. In order to obtain an s-face F with weight k, we have to choose k out of p hyperplanes such that F lies in the positive halfspace defined by each of them and then s − k out of the remaining q = r − p hyperplanes such that F lies in their negative halfspaces. (Because T is a simplex, all these possibilities indeed define a face!) Then F is the intersection of the above chosen halfspaces and the remaining r − s hyperplanes. It follows that

Sf_{s,k}([ˆ0, T]) = \binom{p}{k}\binom{q}{s − k}

if k ≤ s. Analogously, we can compute

S′f_{s,k}([ˆ0, T]) = \binom{q}{k}\binom{p}{s − k}

for k ≤ s. Both formulas are also valid for k > s, because then s − k < 0 and the second binomial is zero by definition. It follows that

Sg_{s,k}([ˆ0, T]) = ∑_{i=0}^{k} \binom{p}{i}\binom{q}{s − i}

and

S′g_{s,k}([ˆ0, T]) = ∑_{i=0}^{k} \binom{q}{i}\binom{p}{s − i}.

Let Δ = _{S′}g_{s,k}([ˆ0, T]) −_{S}g_{s,k}([ˆ0, T]). Then

Δ = ∑_{i=0}^{k} \binom{q}{i}\binom{p}{s − i} − \binom{p}{i}\binom{q}{s − i}.

By substituting s − i for i in the above expression, we get

Δ = ∑_{i=s−k}^{s} \binom{p}{i}\binom{q}{s − i} − \binom{q}{i}\binom{p}{s − i}.

Adding the above two expressions for Δ, we get with m = min(k, s − k − 1)

2Δ = ∑_{i=0}^{m} \binom{q}{i}\binom{p}{s − i} − \binom{p}{i}\binom{q}{s − i}

+ ∑_{i=s−m}^{s} \binom{p}{i}\binom{q}{s − i} − \binom{q}{i}\binom{p}{s − i}.

Because m ≤ (s − 1)/2, we have i ≤ s − i in the first sum and i ≥ s − i in the second one. By (1), we conclude that 2Δ ≥ 0.

Lemma 6. The bounded (r − 1)-simplex of each r-subarrangement (a subarrangement consisting of exactly r halfspaces) S of a simple polyhedral arrangement has weight at most r − 2 (with respect to S).

We omit the proof, because this lemma is the same as Lemma 2 in [2] if we note that the weight of the bounded (r − 1)-simplex coincides with the notion of “total weight” used in [2].

Let u be a nonzero vector in ℝ^{r−1} and let β, γ be two real numbers. If we associate to each t ∈ [0, 1] the halfspace

H^{+}(t) = {x ∈ ℝ^{r−1} : u · x > β + γt}

we call H^{+} a constantly moving halfspace (with velocity γ). An n-tuple of constantly moving halfspaces will shortly be called a moving arrangement. The velocities of the individual halfspaces may of course be different.

We say that an r-subarrangement (H_{e_{1}}^{+}, …, H_{e_{r}}^{+}) of a moving arrangement is switched at t_{0} ∈ (0, 1) if the hyperplanes H_{e_{1}}(t_{0}), …, H_{e_{r}}(t_{0}) intersect in a point (the switching point). The following is Lemma 3 in [2]:

Lemma 7. Each r-subarrangement of a moving arrangement is switched at most once.

Let A(t) = (H_{1}^{+}(t), …, H_{n}^{+}(t)) be a moving arrangement. In the following we use the abbreviation g_{s,k}(t) for g_{s,k}(A(t)).

Lemma 8. Let S(t) be an r-subarrangement of a moving arrangement A(t). Denote by T (t) the unique bounded (r − 1)-simplex of S(t). Let S(t) be switched at t_{0}, and let no other switching occur in A(t) at t_{0}. Then there is an ϵ > 0 such that, if _{S(t_{0}+ϵ)}weight(T (t_{0} + ϵ)) ≤ r/2, then

g_{s,k}(t_{0} − ϵ) ≤ g_{s,k}(t_{0} + ϵ)

for all s = 1, …, r and k = 0, …, n − (r − s).

Proof. Let

p = _{S(t_{0}−ϵ)}weight(T (t_{0} − ϵ))

and

q = _{S(t_{0}+ϵ)}weight(T (t_{0} + ϵ)).

Then p + q = r, because in S the switching corresponds to a reorientation of all of the hyperplanes in S.

We can choose ϵ so small that for all t ∈ [t_{0} − ϵ, t_{0} + ϵ], the simplex T (t) is a face of A(t) and the faces of A(t) outside T (t) are continuously deformed throughout this time interval such that their combinatorial structure, in particular their weights, remain constant.

Let m be the weight in A(t_{0}) of the switching point at t_{0} and let t ∈ [t_{0} − ϵ, t_{0} + ϵ] \ {t_{0}}. Then all faces of T (t) have weight at least m in A(t). Therefore for k < m we have

g_{s,k}(t_{0} + ϵ) = g_{s,k}(t_{0} − ϵ).

On the other hand, we have

g_{s,k}(t) = _{A(t)}g_{s,k}([ˆ0, T (t)]) +_{A(t)}g_{s,k}(A(t) \ [ˆ0, T (t)]).

Because of the continuous deformation outside of T (t), _{A(t)}g_{s,k}(A(t) \ [ˆ0, T (t)]) remains constant. Noting that for k ≥ m we have

A(t)g_{s,k}([ˆ0, T (t)]) = _{S(t)}g_{s,k−m}([ˆ0, T (t)]),

and that q ≤ p, we can apply Lemma 5 with S = S(t_{0} − ϵ) and S′ = S(t_{0} + ϵ) and get the result.

Proof of Theorem 2. We first consider the case r ≤ 4. Let A_{0} = (H_{1}^{+}, …, H_{n}^{+}) be an arbitrary simple arrangement of halfspaces in ℝ^{r−1} and let A_{1} be the polyhedral arrangement obtained from A_{0} by translating the halfspaces such that they support the unit sphere S^{r−2}, that is A_{1} = (H′_{1}^{+}, …, H′_{n}^{+}) with H′_{e}^{−} ⊃ S^{r−2}, H′_{e} parallel to H_{e} and tangent to S^{r−2} for each e ∈ {1, …, n}. A_{0} and A_{1} uniquely determine a moving arrangement A with A(0) = A_{0} and A(1) = A_{1}.

A switching in A(t) is determined by the r participating moving hyperplanes. Because of this and of Lemma 7, there can only be finitely many switchings and hence only finitely many different switching times.

It is easy to see that the time of a switching linearly depends on the β_{e}’s of the participating moving hyperplanes. Therefore, by one or more arbitrarily small changes in the β_{e}’s (corresponding to translations of the hyperplanes in A(0) and A(1) by the same amount), we can perturb the moving arrangement in such a way that the switching times are distinct. Because A(0) is simple, we can choose the perturbations so small that its combinatorial structure remains intact. Because A(1) is polyhedral, we can choose the perturbations so small that it remains polyhedral.

By Lemma 6, the bounded (r − 1)-simplex of each r-subarrangement of A(1) has weight at most r − 2, which is ≤ r/2 for r ≤ 4. Thus by Lemmas 7 and 8, g_{s,k}(0) ≤ g_{s,k}(1) for all s and k. Finally, by Lemma 3, the upper bounds of the theorem are valid for g_{s,k}(1) and hence also for g_{s,k}(0).

For r = 5, we first remark that it can be shown using Theorem 3.4 in [5] that for odd r ≥ 3 and 1 ≤ s ≤ r − 1 we have

(r − s)g_{s,k}(n, r) = ng_{s,k}(n − 1, r − 1)  (2)

(the sceptical reader may also check this equation directly for r = 5 by using Table 1). Let A = (H_{1}^{+}, …, H_{n}^{+}) be a simple arrangement of halfspaces in ℝ^{4}. For each e ∈ {1, …, n}, consider

A_{e} = (H_{f}^{+} ∩ H_{e})_{f∈{1,...,n}\{e}},

which is a simple arrangement of n − 1 halfspaces in ℝ^{3}. Since the theorem is already proved for r = 4, we have

g_{s,k}(A_{e}) ≤ g_{s,k}(n − 1, 4)

for each e and 1 ≤ s ≤ 4 and hence

∑_{e=1}^{n} g_{s,k}(A_{e}) ≤ ng_{s,k}(n − 1, 4) = (5 − s)g_{s,k}(n, 5).

Each s-face of A belongs to exactly 5 − s hyperplanes, so the above sum equals (5 − s)g_{s,k}(A) and the result

g_{s,k}(A) ≤ g_{s,k}(n, 5)

follows.

Acknowledgements. The author wishes to thank Peter Hellekalek for the opportunity to write this paper and Johann Linhart as well as the anonymous referee for valuable comments and suggestions.

References

[1] Eckhoff, Jürgen: Helly, Radon, and Carathéodory type theorems. In: Handbook of convex geometry, volume A, pages 389–448. North-Holland 1993.

[2] Linhart, Johann: The Upper Bound Conjecture for arrangements of halfspaces. Beiträge Algebra Geom. 35(1) (1994), 29–35.

[3] McMullen, P.: The maximum numbers of faces of a convex polytope. Mathematika 17 (1970), 179–184.

[4] Philipp, Martin: Combinatorial Properties of Arrangements of Halfspaces. PhD thesis, Universität Salzburg 1994.

[5] Wesp, Gerhard: Counting Certain Covectors in Oriented Matroids. PhD thesis, Universität Salzburg 1999.

Received January 31, 2000