A new lower bound on Hadwiger-Debrunner numbers in the plane
Acta mathematica Universitatis Comenianae, Tome 88 (2019) no. 3, pp. 855-860
Chaya Keller; Shakhar Smorodinsky; Chaya Keller; Shakhar Smorodinsky. A new lower bound on Hadwiger-Debrunner numbers in the plane. Acta mathematica Universitatis Comenianae, Tome 88 (2019) no. 3, pp. 855-860. http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a76/
@article{AMUC_2019_88_3_a76,
     author = {Chaya Keller and Shakhar Smorodinsky and Chaya Keller and Shakhar Smorodinsky},
     title = { A new lower bound on {Hadwiger-Debrunner} numbers in the plane},
     journal = {Acta mathematica Universitatis Comenianae},
     pages = {855--860},
     year = {2019},
     volume = {88},
     number = {3},
     url = {http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a76/}
}
TY  - JOUR
AU  - Chaya Keller
AU  - Shakhar Smorodinsky
AU  - Chaya Keller
AU  - Shakhar Smorodinsky
TI  - A new lower bound on Hadwiger-Debrunner numbers in the plane
JO  - Acta mathematica Universitatis Comenianae
PY  - 2019
SP  - 855
EP  - 860
VL  - 88
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a76/
ID  - AMUC_2019_88_3_a76
ER  - 
%0 Journal Article
%A Chaya Keller
%A Shakhar Smorodinsky
%A Chaya Keller
%A Shakhar Smorodinsky
%T A new lower bound on Hadwiger-Debrunner numbers in the plane
%J Acta mathematica Universitatis Comenianae
%D 2019
%P 855-860
%V 88
%N 3
%U http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a76/
%F AMUC_2019_88_3_a76

Voir la notice de l'article provenant de la source Comenius University

A family of sets $\mathcal{F}$ is said to satisfy the $(p,q)$ property if among any $p$ sets in $\mathcal{F}$ some $q$ have a non-empty intersection. Hadwiger and Debrunner (1957) conjectured that for any $p \geq q \geq d+1$ there exists $c=c_d(p,q)$, such that any family of compact convex sets in $\mathcal{R}^d$ 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 $c_d(p,q)$, known as the `the Hadwiger-Debrunner numbers,' is still a major open problem in combinatorial geometry. The best currently known lower bound on the Hadwiger-Debrunner numbers in the plane is $c_2(p,q) = \Omega( \frac{p}{q}\log(\frac{p}{q}))$, while the best known upper bound is $O(p^{(1.5+\delta)(1+\frac{1}{q-2})})$. In this paper we improve the lower bound significantly by showing that $c_2(p,q) \geq p^{1+\Omega(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\H{o}s on points in general position in the plane. We use a novel construction for the Erd\H{o}s' problem, obtained recently by Balogh and Solymosi using the \emph{hypergraph container method}, to get the lower bound on $c_2(p,3)$. We then generalize the bound to $c_2(p,q)$ for any $q \geq 3$.