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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.