\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)|<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$.)
\paragraph{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) \ldots (N-p+1)/p!$
must become $M(M(1-h))(M(1-2h) \ldots 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) \ldots (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
\begin{center}
$i= ({\binom{q}{d+1}} / 
{\binom{p}{d+1}} )(1-ip^2/(2(d+1))) ~~~\mbox{or}$
\end{center}
$$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. $\Box$
\begin{center}
\section{Comments}
\end{center}
\hspace*{\parindent}
The main differences between the argument here and that of 
the original paper are as follows:
\begin{enumerate}
\item
In the proof of Lemma 1, the more sophisticated methods of 
B\'ar\'any and their application in our paper$^2$ 
were used in the previous paper; these give much stronger 
results in dimensions 3 or more.
\item
In the proof of Lemma 2, an argument based on linear 
programming was used.  It is slightly more powerful than the 
cloning here.
\item
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.
\item
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.	
\end{enumerate}

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.
 
\begin{center}
\section{References}
\end{center}
\begin{enumerate}
\item
Alon N. and Kleitman, D. J., Piercing Convex Sets and the 
Hadwiger-Debrunner $(p,q)$ Problem, Advances in Math., 96, 
103-112, 1992.
\item
Alon, N.,  B\'ar\'any, I.,  F\"uredi, Z. and Kleitman, D.J., Point 
Selection and Weak $\epsilon$-Nets for Convex Hulls, 
Combinatorics, Probability and Computing 1, 169-200, 1992.
\item
Hadwiger, H. and Debrunner, H.,\"Uber eine Variante 
zum Helly`schen Satz,
Arch. Math. 8, 309-313, 1957.
\item
Kalai, G., Intersection Patterns of Convex Sets, Israel 
Journal of Math, 48, 161-174, 1984.
\item
Katchalski, M. and Liu, A., A Problem of Geometry in 
$R^n$, Proc. AMS 75, 284-288, 1979.
\item
Wegner, G., d-collapsing and Nerves of Families of  Convex  Sets, 
Arch. Math. 26, 317-321, 1975.
\item
Welzl. E., Partition Trees for Triangle Counting and Other 
Range Searching Problems, Proceedings of 4th ACM Symposium on  
Computational Geometry, 23-33, 1988.
\end{enumerate}
\end{document}


.
