A Purely Combinatorial Proof of the Hadwiger Debrunner (p, q) Conjecture

N. Alon ^{∗} , Department of Mathematics, Raymond and Beverly Sackler Faculty of Exact

Sciences, Tel Aviv University, Tel Aviv, Israel and Institute for Advanced Study, Princeton, NJ 08540, USA. Email: noga@math.tau.ac.il.

D.J. Kleitman ^{†} ,Department of Mathematics, MIT, Cambridge, MA, 02139. Email:

djk@math.mit.edu. Submitted: July, 1996; Accepted: December, 1996.

Abstract A family of sets has the (p, q) property if among any p members of the family some q have a nonempty intersection. The authors have proved that for every p ≥ q ≥ d + 1 there is a c = c(p, q, d) < ∞ such that for every family F of compact, convex sets in R^{d} which has the (p, q) property there is a set of at most c points in R^{d} that intersects each member of F, thus settling an old problem of Hadwiger and Debrunner. Here we present a purely combinatorial proof of this result. AMS Subject Classification: 52A35

1. Introduction

The purpose of this note is to present an elementary and self contained description of the authors’ recent proof^{1} of the Hadwiger-Debrunner (p, q) conjecture.

The content of the proof below is almost the same as that previously given. The main difference is that several steps in which bounds were obtained by state of the art arguments using deep results, are here replaced by easily obtained, if somewhat looser bounds. The most significant loss to the final bound comes from replacing a result of Bárány, applied by the authors, him and Füredi^{2} by a simple geometric argument. Two other steps are also modified as will be noted below.

Helly’s Theorem tells us that given any finite collection of bounded and closed convex sets in the d dimensional Euclidean space, if any d+1 of them have a point in common, then they all have one. (We use the words, “have a point in common”, “meet” and “intersect” interchangeably below.)

In the 1950’s, Hadwiger and Debrunner^{3} raised the question:

Suppose the convex sets here have the property that out of any set of p of them, some q have a point in common. Does this imply that there is a set of f(d, p, q) points that meet them all? (With f independent of the number, N, of convex sets in the collection.)

∗Research supported in part by a USA-Israel BSF grant, by a Sloan Foundation grant No. 96-6-2 and by an NEC Research Institute grant.

†Research supported in part by an NSA grant and by a USA-Israel BSF grant

The present authors proved that the answer to this question is “yes” when q > d, in 1992. (It is trivially “no” when q ≤ d.) We give here a purely combinatorical proof in four (easy) steps. Here are the steps, presented in the following lemmas in backward order, for pedagogical purposes. We first define a term, the cloning of a set, which permits the argument to be stated succinctly.

To clone a set means to replace it by two copies of itself. Lemma 1. For every dimension d and every g > 0 there is a finite f = f(d, g) so that in order to find f points meeting all the convex sets it is sufficient to find a (possibly large) finite collection, Q, of points such that each of the convex sets contains at least g|Q| of them.

Lemma 2. For every h > 0 there is a g = g(h) > 0 so that in order to find a collection Q of points such that each convex set contains at least g|Q| of them it is sufficient that, after an arbitrary sequence of clonings of our original convex sets so that the original N have become M, there is always a point in at least hM of the resulting M convex sets.

Lemma 3. For every i > 0 and d there is an h = h(d, i) > 0 so that the following holds. To assure that there is a point in hM of the M convex sets obtained as in Lemma 2, it is sufficient that either one of the original convex sets has at least hM clones, or a proportion of at least i of the (d + 1)-element collections among the M convex sets have points in common.

Lemma 4. For every p, q, d there are h > 0 and i > 0 so that the given (p, q) condition assures us that at least a proportion i of the (d+1)-element collections among the M convex sets obtained as in Lemma 2 have points in common when no convex set has more than hM clones.

The first argument uses the concept of a “net” discussed by Alon, Bárány, Füredi, and Kleitman^{2}. The second uses a cloning argument due to Welzl^{7}. The third uses Wegner’s^{6} well known generalization of Helly’s theorem, proved in 1975, while the fourth involves easy counting only. It is easy to check that the four lemmas together imply the desired result.

2. Proofs

Since we are interested only whether a given collection of our convex sets have a point in common or not, it will be useful to us to simplify matters, by replacing each of the convex sets by a polytope that lies inside it. This is accomplished by choosing a single point in each collection of the N sets that have a point in common, and replacing each convex set by the convex hull of the points thus chosen that are within it. Obviously a set of points that meets every one of the resulting polytopes will meet each of the original sets. Proof of Lemma 1. If we can find a set of f(d, g) points that meets the convex hull of every subset of g|Q| of the elements of Q, it will meet every one of our polytopes.

In one dimension, we can choose every g|Q|-th point of Q, which involves using [1/g] points. This will include one of every set of g|Q| consecutive points, and hence will meet the convex hull of any set of g|Q| points. This means

f(1, g) = [1/g] .

We construct a set of f(d, g) points that meets the convex hull of every combination of g|Q| of the elements of Q in higher dimensions by induction on dimension, using the following procedure:

1. Find a hyperplane H such that half the points of Q are on each of its sides.

2. Consider the |Q|^{2}/4 points of intersection of line segments joining points on opposite sides of H with H itself.

3. Since H has dimension d − 1, we can find f(d − 1, 9g^{2}/25) points on H that meet the convex hull of every set of 9g^{2}|Q|^{2}/100 of these intersection points, by an appropriate induction hypothesis.

4. Every set of g|Q| points of Q that has at least g|Q|/10 points on each side of H will have convex hull that contains at least 9g^{2}|Q|^{2}/100 of these intersection points, and will therefore meet our set of f(d − 1, 9g^{2}/25) points in H. (We use the fact that the function x(1 − x) has a maximum at x = 1/2 and decreases symmetrically on either side of this maximum; its value at x = 1/10 is 9/100.)

5. We need only concern ourselves further with sets of g|Q| points which have at least 9g|Q|/10 of these on one side or the other of H. But there are only |Q|/2 points of Q on each side. If we let the points of Q on the two sides of H be Q_{L} and Q_{R}, we only need meet the convex hulls of proportions 9g/5 of each of these to meet each such set of g|Q| points of Q.

(If 9g/5 is at least 1, this cannot happen at all.)

6. By iterating the procedure outlined above we get the terminating series f(d, g) < f(d − 1, 9g^{2}/25) + 2f(d − 1, 9((9/5)g)^{2}/25) + 4f(d − 1, 9((9/5)^{2}g)^{2}/25) + ⋯

7. We may obtain a bounding series that is geometric and terminates after a finite number (log_{9/5}(1/g)) steps. It obviously gives a finite expression for f(d, g).

8. For d = 2, the series becomes (25/9)g^{−2} (1 + (50/81) + (50/81)^{2} + ⋯) and we find f(2, g) < (225/31)g^{−2}. In higher dimensions the argument works equally well, and the series converges even more rapidly than in two dimensions, but the bound obtained is not very good; it has the form

f(d, g) = c_{d}g^{−2^{d}} .

9. This concludes proof of the lemma. The bound in two dimensions is close to the best known. In general a bound of the form c_{d}g^{−d−1}, holds in any dimension, but this seems to require a deeper argument. □

Proof of Lemma 2. We give a constructive procedure for obtaining Q under these circumstances:

1. Choose a point, q_{1}, in at least hN of the original polytopes.

2. Clone each polytope not containing q_{1}.

3. Repeat these two steps on the resulting collection of polytopes |Q| times. We get the desired set, Q, Q = {q_{1}, q_{2}, ..., q_{|Q|}}.

4. At every stage of this construction the number of polytopes grows by the number of clonings; if at that stage one had R polytopes the point chosen will be in at least hR of them and there will be at most (1 − h)R clonings. The number of polytopes in that stage will grow to at most (2 − h)R.

5. Thus the final number of polytopes will be at most N(2 − h)^{|Q|}.

6. We will use the fact that the number of clone descendants of any one of our original polytopes cannot exceed this number.

7. Each original polytope that contains fewer than g|Q| of these points will clone to at least 2^{(1−g)|Q|} final polytopes.

8. We must therefore have 2^{(1−g)|Q|} < N(2 − h)^{|Q|}.

9. If we choose |Q| so large that the factor N is insignificant here, we can ignore it and take |Q|-th roots obtaining the condition:

2^{(1−g)} < (2 − h), or g > − log_{2}(1 − h/2) .

10. Thus if g is less than − log_{2}(1 − h/2), every one of our original polytopes will have to contain a proportion g of our points. This concludes our proof of the second lemma. □

Proof of Lemma 3. If one of our polytopes has hM clones, then the fact that it is non-empty implies that any point in it lies in at least hM of our resulting polytopes.

We suppose therefore that no polytope has hM clones, but at least i\binom{M}{d+1} of the \binom{M}{d+1} subsets of our collection of cardinality d + 1 have points in common.

Our argument is essentially that of Wegner, which he used to prove a generalization of Helly’s Theorem to the case in which its premise: that every d + 1 sets meet, does not hold. His argument is a generalization of the simple proof of Helly’s Theorem in one dimension. We digress to give this proof.

Lemma 3A. Given a set of closed finite intervals on a line, if any two meet they all meet. (The one dimensional Helly Theorem.)

Proof: Start on one end of the line, and move along it until the first interval to end ends. Its endpoint must lie in every interval: no interval could have ended before it, by its definition, and none begins after it lest it fails to intersect the one that ended there. □

We now give Wegner’s generalization of this argument: We use the fact that our convex sets, and all the intersections thereof, are bounded polytopes. We choose a direction such that no two vertices of any intersections among our polytopes are both in the same hyperplane normal to this direction. We start with a hyperplane off at infinity normal to this direction. We move the hyperplane along in this direction sweeping it past each of the vertices of the polytopes and their intersections.

As we sweep across our system of polytopes with our hyperplane, to each set, S, of polytopes with a point in common, we associate the last vertex encountered, v(S), that lies in all of the elements of S.

Let y be a point at which some intersection ends. We make two observations about the sets S for which v(S) = y.

1. There is a unique maximal set, S_{max}(y), whose intersection ends at y, which consists of all polytopes that contain the point y.

2. Every minimal set, say S_{min}(y), whose intersection ends at y, has cardinality at most d.

Proof of 2: The set S_{min}(y) has intersection ending at y and no subset of it does so. Thus every proper subset of S_{min}(y) has intersection that meets a hyperplane H immediately beyond y. If any proper subset has cardinality d, then Helly’s Theorem on H implies that S_{min}(y) meets H as well, which contradicts the definition of S_{min}(y).

These two facts tell us that any set, T, of polytopes having cardinality d+1 with a point in common, with v(T) = y, is contained in a unique S_{max}(y) and contains some d-element set, T′, that also ends at y.

This means we can bound the number of intersecting (d + 1)-sets of polytopes by counting, for every possible d-element set T′, the maximum number of d+1 element sets between T′ and the S_{max}(y) containing it that ends at the same vertex.

Suppose now that no point lies in hM of our sets. Then we have |S_{max}(y)| < hM, and at most (hM − d − 1) (d + 1)-element sets lie between T′ and S_{max}(y). There are at most \binom{M}{d} possible sets T′. We deduce that there are at most (hM − d − 1) \binom{M}{d} possible intersecting (d + 1)-sets of polytopes. But \binom{M}{d+1} = \binom{M}{d}(M − d)/(d + 1), and we therefore have a contradiction if (hM − d − 1)(d + 1)/(M − d) < i, thus, if h(d + 1) < i.

(Wegner’s argument proves Helly’s theorem inductively since if every (d+1)-set is intersecting, for y the first end vertex crossed by our hyperplane, every (d + 1)-element superset of S_{min}(y) must be intersecting and therefore end at y, which means that every polytope must contain y.)

Proof of Lemma 4. Suppose first that we have done no cloning. Then the given condition tells us that within every p element sets of polytopes there is a q element intersecting set and hence at least \binom{q}{d+1} (d + 1)-element intersecting sets of polytopes. In all we get at least \binom{N}{p} \binom{q}{d+1} (d + 1)-element intersecting sets of polytopes in this way. Now any one such (d + 1)-element set can occur in this way at most \binom{N−d−1}{p−d−1} times, which tells us we must have at least \binom{N}{p}\binom{q}{d+1}/\binom{N−d−1}{p−d−1} different intersecting (d+1)-element sets, which rearranges to \binom{N}{d+1}\binom{q}{d+1}/\binom{p}{d+1} of them.

Thus without cloning we get i = \binom{q}{d+1}/\binom{p}{d+1}.

With cloning we can employ a parallel argument but can use it only when our p element sets come from distinct original polytopes. Since each original polytope may have up to hM clones, the factor here which is N(N −1) … (N −p+1)/p! must become M(M(1−h))(M(1− 2h) … M(1 − (p − 1)h)/p!; everything else in the argument is the same with N replaced by M. Thus cloning degrades i here by no more than a factor (1 − h)(1 − 2h) … (1 − (p − 1)h). We exaggerate this factor by replacing it by (1 − hp^{2}/2); if we use Lemma 3, and set h = i/(d + 1), we obtain

i = (\binom{q}{d+1}/\binom{p}{d+1})(1 − ip^{2}/(2(d + 1))) or

i = \frac{\binom{q}{d+1}/\binom{p}{d+1}}{1 + (\binom{q}{d+1}/\binom{p}{d+1})p^{2}/(2(d + 1))},

so long as hp^{2} < 2.

We find therefore that our conclusion holds for every i less than the minimum of the expression here and 2(d + 1)p^{−2}. This concludes our argument. □

3. Comments

The main differences between the argument here and that of the original paper are as follows:

1. In the proof of Lemma 1, the more sophisticated methods of Bárány and their application in our paper^{2} were used in the previous paper; these give much stronger results in dimensions 3 or more.

2. In the proof of Lemma 2, an argument based on linear programming was used. It is slightly more powerful than the cloning here.

3. In the proof of Lemma 3, a more sophisticated argument due to Kalai^{4}, based on Wegner’s Theorem (which is essentially the contents of the two observations in the proof of this remark), was used. It does not affect the conclusion. Katchalski and Liu^{5} first proved a version of this result.

4. We make no attempt to put the results here together to make an estimate for any particular p and q; in the simplest previously open case, d = 2, p = 4, q = 3, the available bounds yield a bound on the order of 350 on the number of points needed to meet each polytope. (We leave this computation as an exercise for the reader.) On the other hand, the true answer may well be 3.

We refer the reader for fuller references to the previous literature and previous results on this problem to our original paper.

This paper is dedicated to Herb Wilf, whose remarkable success at making powerful mathematics appear simple was the inspiration for it.

4. References

1. Alon N. and Kleitman, D. J., Piercing Convex Sets and the Hadwiger-Debrunner (p, q) Problem, Advances in Math., 96, 103-112, 1992.

2. Alon, N., Bárány, I., Füredi, Z. and Kleitman, D.J., Point Selection and Weak ϵ-Nets for Convex Hulls, Combinatorics, Probability and Computing 1, 169-200, 1992.

3. Hadwiger, H. and Debrunner, H.,Über eine Variante zum Helly‘schen Satz, Arch. Math. 8, 309-313, 1957.

4. Kalai, G., Intersection Patterns of Convex Sets, Israel Journal of Math, 48, 161-174, 1984.

5. Katchalski, M. and Liu, A., A Problem of Geometry in R^{n}, Proc. AMS 75, 284-288, 1979.

6. Wegner, G., d-collapsing and Nerves of Families of Convex Sets, Arch. Math. 26, 317-321, 1975.

7. Welzl. E., Partition Trees for Triangle Counting and Other Range Searching Problems, Proceedings of 4th ACM Symposium on Computational Geometry, 23-33, 1988.