Fractional Helly theorem for the diameter of convex sets

Abstract

We provide a new quantitative version of Helly's theorem: there exists an absolute constant $\alpha >1$ with the following property: if $\{P_i:i\in I\}$ is a finite family of convex bodies in ${\mathbb{R}}^n$ with $\mathrm{int}\left({\bigcap }_{i\in I}{P}_i\right)\ne \varnothing$, then there exist $z\in {\mathbb{R}}^n$, $s\le \alpha n$ and $i_1,\dots i_s\in I$ such that \begin{equation*} z+P_{i_1}\cap\cdots\cap P_{i_s}\subseteq cn^{3/2}\left(z+\bigcap_{i\in I}P_i\right), \end{equation*} where $c>0$ is an absolute constant. This directly gives a version of the "quantitative" diameter theorem of Bárány, Katchalski and Pach, with a polynomial dependence on the dimension. In the symmetric case the bound $O(n^{3/2})$ can be improved to $O(\sqrt{n})$.

arXiv commentarXiv admin note: text overlap with arXiv:1509.05783

References in corpus (1)

• Proof of a conjecture of Bárány, Katchalski and Pach