$k$-Dimensional Transversals for Fat Convex Sets

We say that a family $𝒯$ of geometric objects hits or pierces another family $ℱ$ if for every $F\in ℱ$ there is a $T\in 𝒯$ such that $T\cap F\ne \mathrm{\varnothing }$. If $𝒯$ consists of a single $k$-flat ($k$-dimensional affine subspace), then we say that $ℱ$ has a $k$-transversal. In this language, Helly’s theorem [10] states, that for a finite family $ℱ$ of convex sets in ${ℝ}^d$, if every subfamily of size $d+1$ has a $0$-transversal, i.e., a point contained in all $d+1$ sets, then the whole family has a $0$-transversal, i.e., a point contained in all the sets. Vicensini [21] asked whether one can generalize Helly’s theorem to $k$-transversals for , but this was shown to be false by Santaló [19], who constructed arbitrarily large families of convex sets in the plane without a $1$-transversal whose every proper subfamily has a $1$-transversal.

A natural next question in this direction is whether the following fractional Helly theorem of Katchalski and Liu has any analog for $k$-transversals.

Alon and Kalai showed that it can indeed be generalized to $(d-1)$-transversals (hyperplanes) intersecting convex sets.

Later, Alon, Kalai, Matoušek and Meshulam showed that the above statement does not generalize to $1$-flats (lines) intersecting convex sets in ${ℝ}^3$.

By a suitable lifting argument this implies that there are no fractional Helly theorems for $k$-flats intersecting convex sets if . Following this example it is natural to look for fractional Helly-type theorems for special kinds of sets and $k$-flats with . For example, Matoušek proved, that $k$-flats intersecting a family of sets with bounded description complexity admit a fractional Helly theorem [16]. A family of sets is said to have bounded description complexity, if each of the sets can be described using a bounded number of bounded degree polynomial inequalities.

We prove a fractional Helly theorem for $\rho$-fat convex sets. A family $ℱ$ of sets is $\rho$-fat, if for every $K\in ℱ$ there exist $x_K\in {ℝ}^d$ and $r_K,R_K\in ℝ$ such that $R_K\le \rho r_K$ and $K$ contains a ball of radius $r_K$ centered at $x_k$ and is contained in a ball of radius $R_K$ centered at $x_k$.¹¹1Note that requiring these balls to be concentric is not a significant restriction; if $K$ is contained in some ball of radius $R$, then it is contained in a ball of radius $2R$ centered at any point of $K$.

As discussed above, the $k=d-1$ case is known to hold even without the fatness assumption [1], but the case is known to be false without fatness, even if we replace the $(k+2)$-tuples in the assumption with $m$-tuples for any finite $m$ [2].

Note that as any convex body in ${ℝ}^d$ can be made $d$-fat with an affine transformation by John’s theorem [12], our result also holds for the family of homothets of any fixed convex body. For these, Matoušek’s result would only work if the convex body has bounded union complexity, like a ball or a polyhedron, and even in this case would only give $((k+1)(d-k)+1)$-size subfamilies, which is improved by our $(k+2)$-size subfamilies for all . (This is an improvement because by averaging if some $\alpha$ fraction of the $((k+1)(d-k)+1)$-tuples intersect, then also some $\alpha$ fraction of the $(k+2)$-tuples intersect.)

The proof of our main Theorem 5 can be found in Section 2. Along the way we prove spherical and colorful variants of the result as well.

Now we turn to the history of our other main result. A celebrated generalization of Helly’s theorem is the following $(p,q)$-theorem of Alon and Kleitman.

The fractional Helly theorem of Katchalski and Liu plays a crucial role in the proof of Theorem 6. It would be very interesting to know whether our fractional Helly theorem for $k$-flats intersecting $\rho$-fat convex sets has such a corollary.

We do not even know whether the statement holds if we replace $k+2$ by any $m>k+2$ which does not depend on $ℱ$. The missing ingredient is a weak $\epsilon$-net theorem for $k$-flats intersecting $\rho$-fat convex bodies. In Section 4, we discuss how two of the main approaches used to prove the existence of (weak) $\epsilon$-nets fails in our case. As one of the standard approaches can be used if we replace $\rho$-fat convex sets with balls ($1$-fat convex sets), we obtain the following corollary.

Theorem 8 follows from results in Section 4. We show spherical and colorful variants of this result as well. Note that a weaker version of Theorem 8, where we replace $k+2$ by $(k+1)(d-k)+1$ follows from the more general results of Matoušek [16].

Keller and Perles showed that if $ℱ$ is an infinite family of $d$-dimensional balls, and among any ${\mathrm{\aleph }}_0$ balls some $k+2$ balls have a $k$-transversal, then the whole family can be pierced with finitely many $k$-dimensional affine subspaces [15]. In a forthcoming paper [13] it is shown that this infinite variant follows from our Theorems 5 and 8 with a purely combinatorial proof.

Our Theorem 8 generalizes to certain uniformly fat families as follows. A family $ℱ$ of sets in ${ℝ}^d$ is called $(r,R)$-fat if for every $K\in ℱ$ there is an $x_K\in {ℝ}^d$ such that $B(x_K,r)\subseteq K\subseteq B(x_K,R)$. Note that an $(r,R)$-fat family is $\rho$-fat with $\rho =\frac{R}{r}$ but a $\rho$-fat family might not be $(r,R)$-fat for any fixed $r,R$ as it can contain arbitrarily small and large sets. Because of this, the argument described in the next paragraph, does not apply directly to $\rho$-fat sets in ${ℝ}^d$.

Fractional Helly and $(p,q)$-type results about $k$-transversals of (congruent) balls generalize easily to (not necessarily convex) $(r,R)$-fat sets as were described in [6, 15].

We give a short summary of the argument here. If among every $p$ members of an $(r,R)$-fat family $ℱ$, there are $k+2$ which have a $k$-transversal, then so do the $(k+2)$-tuples of balls of radius $R$ containing them. We can apply Theorem 8 to the family of $R$-balls to obtain a bounded size family $𝒯$ of $k$-flats hitting all the balls. By considering parallel $k$-flats close to members of $𝒯$, we can conclude that a bounded number of them stab the $r$-balls contained in the members of $ℱ$. Therefore, there is a bounded size family of $k$-flats hitting every member of $ℱ$. This argument works even in the case when the members of $ℱ$ are not convex. Not even connectedness is required, only $(r,R)$-fatness.

Holmsen and Matoušek asked whether a fractional Helly theorem exists for disjoint translates of a convex set in ${ℝ}^3$ with respect to lines [11]. As any convex body in ${ℝ}^3$ can be made $3$-fat with an affine transformation, our Theorem 5 answers their question. But we cannot really take credit for this, as a positive answer already follows from a result of Matoušek [16] combined with the trick of making the set $(1,3)$-fat with an affine transformation, and then using the reduction to balls that we sketched earlier. This method would only give a fractional Helly theorem where the assumption is about lines intersecting $5$-tuples of sets (without using our Theorem 5); it was observed by Dobbins and Holmsen a few years ago (personal communication), independently of us, that this can be improved to the optimal $3$, and they have also obtained fractional Helly theorems for $(r,R)$-fat sets with respect to $k$-flats (unpublished).

As another direction generalizing Helly-type theorems to $k$-transversals, we mention a result of Hadwiger which shows that although Helly’s theorem does not generalize directly to $1$-transversals, a finite family of pairwise disjoint convex sets in the plane has a $1$-transversal if and only if the family has a linear ordering such that any $3$-tuple of convex sets has a $1$-transversal which is consistent with the ordering [8] (see the definition there). Hadwiger’s result has been generalized to $(d-1)$-transversals by Goodman, Pollack and Wenger [7], and very recently to $k$-transversals for any by McGinnis and Sadovek [17].

In this section we prove Theorem 5 in the below more general, colorful form, an analog of a colorful version of the fractional Helly theorem due to Bárány, Fodor, Montejano, Oliveros, and Pór [5]. Note that our Theorem 5 is a special case of Theorem 10 with ${ℱ}_i=ℱ$ for all $i$.

Our inductive proof of Theorem 10 also requires a spherical analog, for which we need the following definitions. A cap of the sphere ${𝕊}^d$ is the intersection of ${𝕊}^d$ with a ball in ${ℝ}^{d+1}$ (we can assume that the center of the ball is on ${𝕊}^d$), a great $k$-sphere is the intersection of ${𝕊}^d$ with a $(k+1)$-dimensional linear subspace of ${ℝ}^{d+1}$ (assuming that the origin is the center of ${𝕊}^d$), and a spherical $k$-transversal for a spherical family is a great $k$-sphere intersecting all members of the family. We can describe caps as subsets of ${𝕊}^d$ of the form $B(x,\epsilon )=\{y\in {𝕊}^d:\mathrm{\angle }(x,y)={\cos }^{-1}(xy)\le \epsilon \}$ where $x\in {𝕊}^d$. Beware that the definition of $B(x,r)$ implicitly depends on the space we are working in! We intentionally do not use a different notation so that our argument can be described more generally, but it will be always clear from the context in which space we are in. A $\rho$-fat family of spherical sets can be defined analogously to the Euclidean case, with the existence of caps $B(x_K,r_K)$ and $B(x_K,R_K)$ for every $K\in ℱ$ with the property that $B(x_K,r_K)\subset K\subset B(x_K,R_K)$ and $R_K\le \rho r_K$. A set $K\subset {𝕊}^d$ is (spherically) convex, if either $K={𝕊}^d$, or for no $v\in {𝕊}^d$ we have both $v,-v\in K$, and $K$ contains the shorter great circle arc connecting any two points from $K$.

Notice that in fact Theorem 11 implies Theorem 10 as any counterexample in ${ℝ}^d$ would also give a counterexample on the surface of a large enough sphere ${𝕊}^d$ with small (compared to the radius of the sphere) $\rho$-fat sets on it. However, we prove both Theorems 10 and 11 as we believe that our argument is easier to understand in the more natural setting of ${ℝ}^d$, and then think it through that it also works in ${𝕊}^d$ without much change. We mark the differences in our simultaneous proof for both theorems with brackets [ ].

The following is a key property of $\rho$-fat convex sets.

In this section, we prove the claims about spherical sets that were used in the proof of Theorem 11. All the arguments are fairly straight-forward modifications of the simple proofs used in the Euclidean case, but more tedious calculations are required.

Recall that $B(v,\epsilon )$ is the spherical cap centered at $v$ with angle $\epsilon$, and a great $k$-sphere of ${𝕊}^d$ is the intersection of ${𝕊}^d$ with a $(k+1)$-dimensional linear subspace of ${ℝ}^{d+1}$ [4]. A great $1$-sphere is called a great circle.

For $u\in {𝕊}^d\setminus \{v,-v\}$, let $\mathrm{rot}(u,v)$ be the rotation $r$ with $r(u)=v$ which is constant on $\mathrm{span}{(\{u,v\})}^{⟂}$, so we rotate with the $uov$ angle $\mathrm{\angle }(u,v)$ around the center $o$, keeping $\mathrm{span}{(\{u,v\})}^{⟂}$ fixed. If $u\notin \{v,-v\}$, the projection of $u\in {𝕊}^d$ onto the boundary $\partial B(v,\epsilon )$ of the cap $B(v,\epsilon )$ is the intersection of $\partial B(v,\epsilon )$ with the halfplane embedded in ${ℝ}^{d+1}$ containing $o$ and $v$ on its boundary, and $u$ in its interior. In other words, if $u\notin B(v,\epsilon )$, then the projection is the point of $\partial B(v,\epsilon )$ that is hit when we rotate $u$ to $v$. It is denoted by ${\mathrm{proj}}_B(u)$, or simply $\mathrm{proj}(u)$ if $B$ is clear from the context. For any set $X$ and cap $B=B(v,\epsilon )$, let ${\mathrm{proj}}_{B}X=\{{\mathrm{proj}}_B(u):u\in X\}$ if $X\cap \{v,-v\}=\mathrm{\varnothing }$, and let ${\mathrm{proj}}_{B}X=B$ if $X\cap \{v,-v\}\ne \mathrm{\varnothing }$.

The specific $\rho =1$ case of the fractional Helly results of Section 2 implies $(p,q)$-type results for $k$-flats intersecting balls. In this section we summarize arguments showing that Theorem 10 implies Theorem 8. The following colorful generalization can also be proved with a variant of this method. To keep the presentation simple, we only describe the arguments in a non-colorful setting. The interested reader can find a version of the colorful arguments in [5].

By the same method, the following is a corollary of Theorem 11.

Note that the case where the families of balls (caps) can be infinite follows from the finite case by a standard compactness argument. The proofs of the finite versions are simple applications of the Alon-Kleitman method established in [3], later described in a more general setting in [2], and adapted to colorful variants in [5]. The abstract (purely combinatorial) proof described in [2] has two main steps. To state them, we phrase the fractional Helly and $(p,q)$-theorems in an abstract, purely combinatorial language as follows.

Let $\mathscr{H}$ be a set system over the base set $V$. For an integer $q$ and a function $\beta :(0,1]\to (0,1]$, the set system $\mathscr{H}$ satisfies the fractional Helly property FH($q,\beta$) if the following holds. For every $\alpha >0$ and every finite family $𝒢\subset \mathscr{H}$, if $\alpha \left(\genfrac{}{}{0pt}{}{|𝒢|}{q}\right)$ of the $q$-tuples of $𝒢$ has a nonempty intersection, then there exists a subfamily ${𝒢}^{\prime }\subset 𝒢$ of size $\beta (\alpha )|𝒢|$ such that all the members of ${𝒢}^{\prime }$ have an element of $V$ in common. The fractional Helly theorem of Katchalski and Liu (Theorem 1) states that if $V={ℝ}^d$, and $\mathscr{H}$ consists of all the convex sets, then there exists $\beta$ such that $\mathscr{H}$ satisfies FH($d+1,\beta$). Our Theorem 5 states that if $V=\{k\text{-flats of }{ℝ}^d\}$ and $\mathscr{H}$ consists of families of $k$-flats intersecting a common $\rho$-fat convex set, then $\mathscr{H}$ satisfies FH($k+2,\beta$) with some $\beta$.

A set system $\mathscr{H}$ satisfies the $(p,q)$-condition if among any $p$ members of $\mathscr{H}$, some $q$ intersect. Note that for $p\ge q\ge r$, the $(p,q)$-condition implies the $(p,r)$-condition. The transversal number $\tau (\mathscr{H})$ denotes the minimum size of a set $T\subset V$ with $T\cap H\ne \mathrm{\varnothing }$ for all $H\in \mathscr{H}$. The fractional transversal number ${\tau }^{\ast }(\mathscr{H})$ is the minimum ${\sum }_{v\in V}t(v)$ over functions $t:V\to [0,1]$ with ${\sum }_{v\in H}t(v)\ge 1$ for all $H\in \mathscr{H}$. Alon, Kalai, Matoušek and Meshulam proved the following two theorems.

Let ${\mathscr{H}}^{\cap }$ be the family of all sets that are the intersections of some members of $\mathscr{H}$.

Note that if ${\mathscr{H}}^{\cap }$ satisfies $F(q,\beta )$ and $\mathscr{H}$ satisfies the $(p,q)$ condition, then its transversal number is bounded by a function of $p,q$ and $\beta$ as a consequence of the above two theorems. As the family of convex sets of ${ℝ}^d$ is closed under intersection, and satisfies $FH(d+1,\beta )$, this provides an alternative proof of Theorem 6 of Alon and Kleitman. But the same reasoning is usually not applicable to questions about $k$-transversals with $k>0$, as the corresponding ${\mathscr{H}}^{\cap }\ne \mathscr{H}$ is hard to analyze, for example, for balls the intersections are no longer fat. However, in this special case, another proof method works.

If we restrict the question to $k$-transversals of balls [caps], as in Theorem 21 [Theorem 22], then we can bound $\tau$ as a function of ${\tau }^{\ast }$ and thus prove our $(p,k+2)$-theorems. The bound on $\tau$ follows from a classical result of Haussler and Welzl [9] . The VC-dimension of $\mathscr{H}$ is the supremum of the sizes of subsets $S\subseteq V$ such that for every $X\subseteq S$ there is an $H\in \mathscr{H}$ satisfying $H\cap S=X$.

The VC-dimension of $k$-flats intersecting balls [caps] is bounded by the Milnor-Thom theorem on sign patterns of polynomials [18, 20], because a family of $k$-flats intersecting a given ball [cap] can be described by a bounded number of polynomial inequalities of bounded degree.