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

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 \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.