Tuyển tập các báo cáo nghiên cứu khoa học hay nhất của tạp chí toán học quốc tế đề tài: A Purely Combinatorial Proof of the Hadwiger Debrunner (p, q) Conjecture. | A Purely Combinatorial Proof of the Hadwiger Debrunner p q Conjecture N. Alon 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@. . Kleitman y Department of Mathematics MIT Cambridge MA 02139. Email djk@. Submitted July 1996 Accepted December 1996. 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 q d 1 there is a c c p q d 1 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. AMS Subject Classification 52A35 1. Introduction The purpose of this note is to present an elementary and self contained description of the authors recent proof1 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árány applied by the authors him and Fiiredi2 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 Debrunner3 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 .
