A purely combinatorial proof of the Hadwiger Debrunner \((p,q)\) conjecture
The electronic journal of combinatorics, The Wilf Festschrift volume, Tome 4 (1997) no. 2
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.
DOI :
10.37236/1316
Classification :
52A35
Mots-clés : combinatorial proof, Hadwiger Debrunner \((p,q)\) conjecture
Mots-clés : combinatorial proof, Hadwiger Debrunner \((p,q)\) conjecture
@article{10_37236_1316,
author = {N. Alon and D. J. Kleitman},
title = {A purely combinatorial proof of the {Hadwiger} {Debrunner} \((p,q)\) conjecture},
journal = {The electronic journal of combinatorics},
year = {1997},
volume = {4},
number = {2},
doi = {10.37236/1316},
zbl = {0889.52008},
url = {http://geodesic.mathdoc.fr/articles/10.37236/1316/}
}
N. Alon; D. J. Kleitman. A purely combinatorial proof of the Hadwiger Debrunner \((p,q)\) conjecture. The electronic journal of combinatorics, The Wilf Festschrift volume, Tome 4 (1997) no. 2. doi: 10.37236/1316
Cité par Sources :