Personal tools
You are here: Home CG seminar 2019 From a (p,2) theorem to a tight (p,q) theorem
« October 2018 »
October
SuMoTuWeThFrSa
123456
78910111213
14151617181920
21222324252627
28293031
Log in


Forgot your password?
 

From a (p,2) theorem to a tight (p,q) theorem

Wednesday, October 24th, 2018, 16:10

Schreiber 309

underline

From a (p,2) theorem to a tight (p,q) theorem

Chaya Keller, BGU

Abstract:

A family F of sets is said to satisfy the (p, q)-property if among any p sets of F some q have a non-empty intersection. The celebrated (p, q)-theorem of Alon and Kleitman asserts that any family of compact convex sets in R^d that satisfies the (p, q)-property for some q ≥ d + 1, can be pierced by a fixed number (independent on the size of the family) f_d(p, q) of points. The minimum such piercing number is denoted by HD_d(p, q). Already in 1957, Hadwiger and Debrunner showed that whenever q > (d−1)p/d  + 1 the piercing number is HD_d(p, q) = p − q + 1; no exact values of HD_d(p, q) were found ever since. 

While for an arbitrary family of compact convex sets in R^d, d ≥ 2, a (p, 2)-property does not imply a bounded piercing number, such bounds were proved for numerous specific families. The best-studied among them is axis-parallel rectangles in the plane. Wegner and (independently) Dol’nikov used a (p, 2)-theorem for axis-parallel rectangles to show that HD_rect(p, q) = p−q + 1 holds for all q > sqrt(2p). In the talk we present a general method which allows using a (p, 2)-theorem as a bootstrapping to obtain a tight (p, q)-theorem, for families with Helly number 2. We demonstrate the power of this method by showing that HD_rect(p, q) = p−q + 1 holds for all q > 7 log p.

Based on a joint work with Shakhar Smorodinsky.

 
 
Document Actions