A purely combinatorial proof of the Hadwiger Debrunner (p, q) conjecture

N. Alon, D. J. Kleitman

Research output: Contribution to journalArticlepeer-review

11 Scopus citations


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 Rd which has the (p, q) property there is a set of at most c points in Rd 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.

Original languageEnglish (US)
Article numberR1
Pages (from-to)1-8
Number of pages8
JournalElectronic Journal of Combinatorics
Issue number2 R
StatePublished - 1997
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'A purely combinatorial proof of the Hadwiger Debrunner (p, q) conjecture'. Together they form a unique fingerprint.

Cite this