Quantitative fractional Helly and (p,q)-theorems
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\).
- A generalization of Caratheodory's theorem
- A Generalization of Radon's Theorem
- A generalization of Radon's theorem II
- A Problem of Geometry in R n
- An upper-bound theorem for families of convex sets
- Brascamp-Lieb inequality and quantitative versions of Helly's theorem
- Colorful Helly-type theorems for the volume of intersections of convex bodies
- scientific article; zbMATH DE number 1149836 (Why is no real title available?)
- scientific article; zbMATH DE number 1749054 (Why is no real title available?)
- Intersection patterns of convex sets
- Large cliques in hypergraphs with forbidden substructures
- Piercing convex sets and the Hadwiger-Debrunner \((p,q)\)-problem
- Point Selections and Weak ε-Nets for Convex Hulls
- Proof of a conjecture of Bárány, Katchalski and Pach
- Quantitative \((p, q)\) theorems in combinatorial geometry
- Quantitative combinatorial geometry for concave functions
- Quantitative combinatorial geometry for continuous parameters
- Quantitative Helly-Type Theorems
- The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
- The number of triangles covering the center of an \(n\)-set
- Transversal numbers for hypergraphs arising in geometry
- Über eine Variante zum Hellyschen Satz
- Bounded VC-dimension implies a fractional Helly theorem
- Quantitative \((p, q)\) theorems in combinatorial geometry
- Quantitative combinatorial geometry for concave functions
- Brascamp-Lieb inequality and quantitative versions of Helly's theorem
- scientific article; zbMATH DE number 6008343 (Why is no real title available?)
- A note on the colorful fractional Helly theorem
- Quantitative Helly-type theorem for the diameter of convex sets
- Continuous quantitative Helly-type results
- Proof of a conjecture of Bárány, Katchalski and Pach
- Fractional Helly theorem for Cartesian products of convex sets
- Quantitative Helly-type theorems via sparse approximation
- Quantitative Helly-type theorems via hypergraph chains
- Helly numbers for quantitative Helly-type results
- The quantitative fractional Helly theorem
- Quantitative transversal theorems in the plane
This page was built for publication: Quantitative fractional Helly and \((p,q)\)-theorems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2237860)
