CATS-Mar-10-2017
Title[edit]
Hadwiger Debrunner problem on convex sets, and a special case.
Abstract[edit]
A family of sets has the (p; q) property if among any p members of the family some q have a nonempty intersection. In this talk I will present a simple combinatorial proof from [2] that there is a constant, c = c(p, q, d), such that for every family F of compact, convex sets in R_d 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 conjecture of Hadwiger and Debrunner. I will introduce the relevant concepts, mention the recent results [3], and conclude with an extremely simple open problem, specifically the case of lines and pseudo-lines in R_2.
[1] Alon, Noga, and Daniel J. Kleitman. "A Purely Combinatorial Proof of the Hadwiger Debrunner $(p, q) $ Conjecture." the electronic journal of combinatorics 4.2 (1996): R1.
[2] Alon, Noga. "A non-linear lower bound for planar epsilon-nets." Discrete & Computational Geometry 47.2 (2012): 235-244.
[3] Keller, Chaya, Shakhar Smorodinsky, and Gábor Tardos. "On Max-Clique for intersection graphs of sets and the Hadwiger-Debrunner numbers." Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2017.
