\documentstyle[11pt]{article} %\usepackage{amssymb,psfig,epsfig} \setlength{\textwidth}{6in} \setlength{\textheight}{9in} \setlength{\oddsidemargin}{.2in} \setlength{\topmargin}{-0.25in} %\setlength{\headheight}{0in} \def\binom#1#2{{#1}\choose{#2}} \newtheorem{remark}{Remark} \newtheorem{lemma}{Lemma} \makeatletter \def\section{\@startsection {section}{1}{\z@}{-3.5ex plus -1ex minus -.2ex}{2.3ex plus .2ex}{\normalsize\bf}} \def\subsection{\@startsection {subsection}{1}{\z@}{-3.5ex plus -1ex minus -.2ex}{2.3ex plus .2ex}{\normalsize\bf}} \def\subsubsection{\@startsection {subsection}{1}{\z@}{-3.5ex plus -1ex minus -.2ex}{2.3ex plus .2ex}{\normalsize\em}} \def\@sect#1#2#3#4#5#6[#7]#8{\ifnum #2>\c@secnumdepth \def\@svsec{}\else \refstepcounter{#1}\edef\@svsec{\csname the#1\endcsname.\hskip .75em }\fi \@tempskipa #5\relax \ifdim \@tempskipa>\z@ \begingroup #6\relax \@hangfrom{\hskip #3\relax\@svsec}{\interlinepenalty \@M #8\par}% \endgroup \csname #1mark\endcsname{#7}\addcontentsline {toc}{#1}{\ifnum #2>\c@secnumdepth \else \protect\numberline{\csname the#1\endcsname}\fi #7}\else \def\@svsechd{#6\hskip #3\@svsec #8\csname #1mark\endcsname {#7}\addcontentsline {toc}{#1}{\ifnum #2>\c@secnumdepth \else \protect\numberline{\csname the#1\endcsname}\fi #7}}\fi \@xsect{#5}} \def\@begintheorem#1#2{\it \trivlist \item[\hskip \labelsep{\bf #1\ #2.}]} \makeatother \renewcommand{\thefootnote}{\fnsymbol{footnote}} \pagestyle{myheadings} \markright{\sc the electronic journal of combinatorics 4 (no. 2) (1997), \#R1 \hfill} \thispagestyle{empty} \begin{document} \begin{center} {\Large {\bf A Purely Combinatorial Proof of the Hadwiger Debrunner $(p,q)$ Conjecture}} \\ \vspace*{1\baselineskip} {\em N. Alon \footnote{ 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. } , 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 \footnote{ Research supported in part by an NSA grant and by a USA-Israel BSF grant} ,Department of Mathematics, MIT, Cambridge, MA, 02139. Email: djk@math.mit.edu. \\ Submitted: July, 1996; Accepted: December, 1996. } \\ \end{center} \setlength{\baselineskip}{1.5\baselineskip} \begin{abstract} A family of sets has the {\em $(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 \geq q \geq d+1$ there is a $c=c(p,q,d) < \infty$ such that for every family ${\cal 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 ${\cal F}$, thus settling an old problem of Hadwiger and Debrunner. Here we present a purely combinatorial proof of this result. \noindent AMS Subject Classification: 52A35 \end{abstract} \begin{center} \section{Introduction} \end{center} \hspace*{\parindent} 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\'ar\'any, applied by the authors, him and F\"uredi$^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.) The present authors proved that the answer to this question is ``yes'' when $q>d$, in 1992. (It is trivially ``no'' when $q \leq 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 {\em clone} a set means to replace it by two copies of itself. \begin{lemma} 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. \end{lemma} \begin{lemma} 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. \end{lemma} \begin{lemma} 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. \end{lemma} \begin{lemma} 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. \end{lemma} The first argument uses the concept of a ``net" discussed by Alon, B\'ar\'any, F\"uredi, 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. \begin{center} \section{Proofs} \end{center} \hspace*{\parindent} 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. \paragraph{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: \begin{enumerate} \item Find a hyperplane $H$ such that half the points of $Q$ are on each of its sides. \item Consider the $|Q|^2/4$ points of intersection of line segments joining points on opposite sides of $H$ with $H$ itself. \item 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. \item 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.) \item 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.) \item By iterating the procedure outlined above we get the terminating series $f(d,g)< f(d-1,9g^2/25) + 2 f(d-1, 9((9/5)g)^2/25) + 4f(d-1, 9((9/5)^2g)^2/25) + \cdots$ \item 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)$. \item For $d=2$, the series becomes $(25/9)g^{-2}$ $(1 + (50/81) + (50/81)^2 + \cdots)$ 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_dg^{-2^d}~. $$ \item 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. $\Box$ \end{enumerate} \paragraph{Proof of Lemma 2.} We give a constructive procedure for obtaining $Q$ under these circumstances: \begin{enumerate} \item Choose a point, $q_1$, in at least $hN$ of the original polytopes. \item Clone each polytope not containing $q_1$. \item 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|}\}$. \item 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$. \item Thus the final number of polytopes will be at most $N(2-h)^{|Q|}$. \item We will use the fact that the number of clone descendants of any one of our original polytopes cannot exceed this number. \item Each original polytope that contains fewer than $g|Q|$ of these points will clone to at least $2^{(1-g)|Q|}$ final polytopes. \item We must therefore have $2^{(1-g)|Q|} < N(2-h)^{|Q|}$. \item 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), ~~~\mbox{or}~~~ g>-\log_2(1-h/2)~. $$ \item 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. $\Box$ \end{enumerate} \paragraph{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{M \choose {d+1}}$ of the ${M \choose {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. \paragraph{Lemma 3A.} {\em Given a set of closed finite intervals on a line, if any two meet they all meet.} (The one dimensional Helly Theorem.) \paragraph{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. $\Box$ We now give Wegner's generalization of this {\em 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$. \begin{enumerate} \item There is a unique maximal set, $S_{\max}(y)$, whose intersection ends at $y$, which consists of all polytopes that contain the point $y$. \item Every minimal set, say $S_{\min}(y)$, whose intersection ends at $y$, has cardinality at most $d$. \end{enumerate} \paragraph{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)|