Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Fractional Helly Theorem says the following:

For every $0<\alpha\leq 1$ there exists $\beta = \beta(d, \alpha)$ with the following property. Let $C_1 , C_2 , ..., C_n$ be convex sets in $R^d$, $n \geq d + 1$, and at least $\alpha {n \choose d+1}$ of the collection of sets of size $d + 1$ have non-empty intersection, so there exists a point contained in at least $\beta n$ sets. Where $\beta(\alpha)=1-(1-\alpha)^\frac{1}{(d+1)}$.

Now, my question is whether the fractional Helly is true for more than one piercing also? More precisely, if at least $0<\alpha'\leq 1$ fraction of ${n \choose k(d+1)}$ sets are pierced by at most $k$ points, then at least $\beta'n$ sets are pierced by at most $k$ points. Where $\beta'=\beta'(\alpha',k,d)$ and $\beta'$ approaches to $1$ as $\alpha'$ approaches to $1$.

I have asked the same question in math.stackexchange also. Sorry for repeating the question here.

share|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.