Two celebrated extensions of Helly’s theorem are the fractional Helly theorem of Katchalski and Liu (1979) and the quantitative volume theorem of Bárány, Katchalski, and Pach (1982). Improving on several recent works, we prove an optimal combination of these two results. We show that given a family <InlineEquation ID="IEq1"> <EquationSource Format="TEX">${\cal F}$</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mrow> <mi mathvariant="script">F</mi> </mrow> </math></EquationSource> </InlineEquation> of n convex sets in ℝd such that at least <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\alpha\left(\begin{array}{c}n\\ {d+1}\end{array}\right)$</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mi>α</mi> <mrow> <mo>(</mo> <mtable columnspacing="1em" rowspacing="4pt"> <mtr> <mtd> <mi>n</mi> </mtd> </mtr> <mtr> <mtd> <mrow> <mi>d</mi> <mo>+</mo> <mn>1</mn> </mrow> </mtd> </mtr> </mtable> <mo>)</mo> </mrow> </math></EquationSource> </InlineEquation> of the (d + 1)-tuples of <InlineEquation ID="IEq3"> <EquationSource Format="TEX">${\cal F}$</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mrow> <mi mathvariant="script">F</mi> </mrow> </math></EquationSource> </InlineEquation> have an intersection of volume at least 1, then one can select Ωd,α(n) members of <InlineEquation ID="IEq4"> <EquationSource Format="TEX">${\cal F}$</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mrow> <mi mathvariant="script">F</mi> </mrow> </math></EquationSource> </InlineEquation> whose intersection has volume at least Ωd(1).Furthermore, with the help of this theorem, we establish a quantitative version of the (p, q) theorem of Alon and Kleitman. Let p ≥ q ≥ d + 1 and let <InlineEquation ID="IEq5"> <EquationSource Format="TEX">${\cal F}$</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mrow> <mi mathvariant="script">F</mi> </mrow> </math></EquationSource> </InlineEquation> be a finite family of convex sets in ℝd such that among any p elements of <InlineEquation ID="IEq6"> <EquationSource Format="TEX">${\cal F}$</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mrow> <mi mathvariant="script">F</mi> </mrow> </math></EquationSource> </InlineEquation>, there are q that have an intersection of volume at least 1. Then, we prove that there exists a family T of Op,q(1) ellipsoids of volume Ωd(1) such that every member of <InlineEquation ID="IEq7"> <EquationSource Format="TEX">${\cal F}$</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mrow> <mi mathvariant="script">F</mi> </mrow> </math></EquationSource> </InlineEquation> contains at least one element of T.Finally, we present extensions about the diameter version of the quantitative Helly theoerm.

The quantitative fractional Helly theorem

期刊论文
发表日期：

2025年11月25日

查看全文

Nóra Frankl,
Attila Jung,
István Tomon

摘要

Two celebrated extensions of Helly’s theorem are the fractional Helly theorem of Katchalski and Liu (1979) and the quantitative volume theorem of Bárány, Katchalski, and Pach (1982). Improving on several recent works, we prove an optimal combination of these two results. We show that given a family ${\cal F}$ $F$ of n convex sets in ℝ^d such that at least $\alpha\left(\begin{array}{c}n\\ {d+1}\end{array}\right)$ $α (\begin{matrix} n \\ d + 1 \end{matrix})$ of the (d + 1)-tuples of ${\cal F}$ $F$ have an intersection of volume at least 1, then one can select Ω_d,α(n) members of ${\cal F}$ $F$ whose intersection has volume at least Ω_d(1).

Furthermore, with the help of this theorem, we establish a quantitative version of the (p, q) theorem of Alon and Kleitman. Let p ≥ q ≥ d + 1 and let ${\cal F}$ $F$ be a finite family of convex sets in ℝ^d such that among any p elements of ${\cal F}$ $F$ , there are q that have an intersection of volume at least 1. Then, we prove that there exists a family T of O_p,q(1) ellipsoids of volume Ω_d(1) such that every member of ${\cal F}$ $F$ contains at least one element of T.

Finally, we present extensions about the diameter version of the quantitative Helly theoerm.