Abstract | ||
---|---|---|
A family of sets F is said to satisfy the (p, q) property if among any p sets in F some q have a non-empty intersection. Hadwiger and Debrunner (1957) conjectured that for any p ≥ q ≥ d + 1 there exists an integer c = H Dd(p, q), such that any finite family of convex sets in Rd that satisfies the (p, q) property can be pierced by at most c points. In a celebrated result from 1992, Alon and Kleitman proved the conjecture. However, obtaining sharp bounds on H Dd(p, q), known as 'the Hadwiger-Debrunner numbers', is still a major open problem in discrete and computational geometry.
The best currently known upper bound on the Hadwiger-Debrunner numbers in the plane is [MATH HERE] (for any δ > 0 and p ≥ q ≥ q0(δ)), obtained by combining results of Keller, Smorodinsky, and Tardos (SODA 2017) and of Rubin (FOCS 2018). The best lower bound is [MATH HERE], obtained by Bukh, Matoušek and Nivasch more than 10 years ago.
In this paper we improve the lower bound significantly by showing that H D2(p, q) ≥ p1+Ω(1/q). Furthermore, the bound is obtained by a family of lines and is tight for all families that have a bounded VC-dimension. Unlike previous bounds on the Hadwiger-Debrunner numbers, which mainly used the weak epsilon-net theorem, our bound stems from a surprising connection of the (p, q) problem to an old problem of Erdős on points in general position in the plane. We use a novel construction for Erdős' problem, obtained recently by Balogh and Solymosi using the hypergraph container method, to get the lower bound on H D2(p, 3). We then generalize the bound to H D2(p, q) for q ≥ 3.
|
Year | DOI | Venue |
---|---|---|
2018 | 10.5555/3381089.3381159 | SODA '20: ACM-SIAM Symposium on Discrete Algorithms
Salt Lake City
Utah
January, 2020 |
DocType | Volume | Issue |
Journal | abs/1809.06451 | 3 |
ISSN | Citations | PageRank |
0231-6986 | 0 | 0.34 |
References | Authors | |
0 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Chaya Keller | 1 | 3 | 4.52 |
Shakhar Smorodinsky | 2 | 422 | 43.47 |