6
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

A fractional Helly for more than one piercing is true, but $\beta '$ does not approach $1$ if $\alpha '$ approaches $1$.

The existence of $\beta '$ actually follows from the usual fractional Helly theorem. Given a subfamily of size $k(d+1)$, if it has piercing number at most $k$, there must be an intersecting $(d+1)$-tuple. Every intersecting $(d+1)$-tuple can be counted at most $\binom{n-d-1}{kd}$ times. Thus, there are at least $$ \alpha' \frac{\binom{n}{k(d+1)}}{\binom{n-d-1}{kd}} \sim \alpha \binom{n}{d+1} $$ different intersecting $(d+1)$-tuples for some other $\alpha$ not depending on $n$. The large intersecting subfamily that comes from fractional Helly has in particular piercing number at most $k$.

I currently have only one example showing that $\beta' \not\rightarrow 1$, if $d=2$ and $k=2$. The main reason why it fails is that "having piercing number at most $2$" is not a Helly-type property.

Let $m$ be a positive integer and consider a set $S$ of $2m+1$ points in the plane in convex position. The family $\mathcal{F}$ is formed by taking the convex hull of any $(m+1)$-tuple of points of $S$. This set is known to have piercing number three (it is used to construct large families of convex sets in the plane satisfying the $(4,3)$ property with piercing number three).

However, if we take any six sets in $\mathcal{F}$, we are using $6n+6 > 3(2n+1)$ points of $S$. Thus, there are four of them which have a point of intersection. The other two sets are using $2n+2 >2n+1$ points of $S$, so they intersect. Thus $\alpha' = 1$ for this example, but $\beta' \le \left({\binom{2m+1}{m+1}-1}\right)/{\binom{2m+1}{m+1}}$.

Your conjecture might be saved by asking to find a set of size $\lfloor \beta' n \rfloor$ with piercing number at most $k$ instead of $\beta' n$. In the example above I do not know if it is always possible to remove one of the sets so that the piercing number of the resulting family is two.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .