Quantitative fractional Helly and \((p,q)\)-theorems (Q2237860): Difference between revisions

The classical Helly theorem states that the intersection of all members of a finite collection \(\mathcal{C}\) of convex sets in \(\mathbb{R}^d\) is non-empty if the intersection of any \(d+1\) of the members is non-empty. A ``quantiative'' version of the theorem states that, if any \(2d\) of the convex sets contain an ellipsoid of volume at least one, then the intersection of all the convex sets contains an ellipsoid of volume at least \(c^d d^{-3d/2}\). Here \(c>0\) is a universal constant. The main two results of the present paper give quantitative versions of ``\((p,q)\)'' and ``fractional'' variants of Helly's theorem, which are well-studied topics in their own right. For example, Theorem 1.3 shows that for any \(\alpha\in (0,1)\), there is a corresponding \(\beta\in (0,1)\) such that the following holds: Suppose that among all subfamilies of \(\mathcal{C}\) of size \(3d+1\), there are at least \(\alpha \binom{|\mathcal{C}|}{3d+1}\) for which the intersection of the \(3d+1\) members contains an ellipsoid of volume one. Then \(\mathcal{C}\) has a subfamily \(\mathcal{C}'\) of size at least \(\beta|\mathcal{C}|\) such that the intersection of all members of \(\mathcal{C}'\) contains an ellipsoid of volume at least \(c^{d^2}d^{-5d^2/2+d}\), where \(c\) is the consant above. By contrast to other quantitative \((p,q)\) theorems, the result is notable in that \(3d+1\) is linear in \(d\).