Sharp fractional Helly bounds for common affine flats

Introduction

Background and the source problem

Helly’s theorem says that a finite family of convex sets in the plane has a common point whenever every three or fewer members do; in $\mathbb{R}^{d}$, the corresponding number is $d+1$ [7]. The fractional question is what remains true if only a proportion $\alpha$ of those small subfamilies intersect. The fractional Helly theorem guarantees a point belonging to a positive fraction of all the sets [3]. Its sharp form gives the fraction $1-(1-\alpha)^{1/(d+1)}$ [4, 5]. Thus local intersection data forces a large subfamily with a common point. As the proportion of intersecting tuples tends to one, the guaranteed fraction of sets sharing a point also tends to one.

Here the object to be shared is a whole affine flat. An affine $k$-flat is a translate of a $k$-dimensional linear subspace: a point when $k=0$, a line when $k=1$, and a plane when $k=2$. We ask for such a flat to be contained in every set of a subfamily. This is stronger than asking the intersection to have dimension at least $k$: a disk has dimension two but contains no whole line. It also differs from finding a flat that merely meets each set, the transversal problem discussed, for example, in [16 Section 6].

Parallel strips in the plane give the simplest picture. Their intersection contains a line exactly when their projected intervals on the common normal line intersect. This reduces the question to one dimension. Two strips with different directions, however, can have a two-dimensional bounded intersection and still share no line; see Figure 1. In a general family the directions may vary, so there need not be a single projection that works for all subfamilies.

Nevertheless, the correct dimension is the codimension $q=d-k$. De Santis [2], restated in [1 Theorem 1], proved that if every $q+1$ or fewer members of a finite family of closed convex sets contain a common $k$-flat, then the entire family does. Ludwigson and Soberón [1 Theorem 5] established a fractional version: if an $\alpha$ fraction of the $(q+1)$-tuples have this property, at least an $\alpha/(q+1)$ fraction of the sets share a $k$-flat. Their Section 6 asks for the optimal coefficient.

Question 1.1 ([1 Section 6]). For closed convex sets in $\mathbb{R}^{d}$, does the fractional De Santis theorem hold with the sharp ordinary fractional Helly coefficient in dimension $q=d-k$, namely

The difference is substantial when most tuples are good. For common lines in the plane, $q = 1$: if 99% of the pairs contain a common line, the proposed coefficient guarantees one line contained in at least 90% of all sets. The earlier coefficient guarantees only 49.5%. More generally, the proposed bound tends to one as $\alpha\to1$, as the non-fractional De Santis theorem suggests.

Contribution

The sharp coefficient is valid. In fact, the intersection patterns have a stronger combinatorial property that explains the dimension reduction and gives an exact finite counting bound.

1. Theorem 1.2 answers Question 1.1. Theorem 4.2 gives its exact finite form, and Theorem 5.1 supplies matching examples with distinct closed convex sets.

2. Theorem 3.2 proves that the complex of common-$k$-flat subfamilies is $q$-collapsible. This answers the closed-convex version of the second question in [1 Section 6].

A subfamily with a common flat will be called a face. Its subfamilies are again faces, so these faces form a simplicial complex. To be $q$-collapsible means that this complex can be removed in stages, each stage starting from a face of size at most $q$ that belongs to only one maximal remaining face. At that stage one removes the starting face and all faces containing it. The formal convention, including the final empty face, is given in § 3.

Theorem 3.2 proves precisely this statement. Theorem 5 of [1] assumes closedness; its concluding collapsibility question says only “convex sets.” We retain the closedness assumption throughout. Its role is geometric: a whole line in a closed convex set forces translation invariance in that direction, whereas this fails for nonclosed convex sets (§ 2). The unrestricted nonclosed version is therefore not asserted here. When $k = d$, the only possible flat is $\mathbb{R}^d$ itself, and the fractional statement reduces to counting members equal to $\mathbb{R}^d$.

Why the dimension drops

The proof starts with the preceding translation observation. Each set $C$ has a linear space $L(C)$ of directions along which every translate of every point stays in $C$. If an intersection is nonempty, it contains a $k$-flat exactly when the participating sets have at least $k$ linearly independent common translation directions (Lemma 2.1). Equivalently, their normal spaces $L(C)^\perp$ together span at most $q$ dimensions. The relevant quotient space is therefore small, but it depends on the subfamily.

Ludwigson and Soberón already use a small geometric certificate: for a nonempty intersection they select a contained flat of largest dimension, and among those the one closest to the origin. Their Lemma 2 shows that, if the selected flat has dimension $\ell$, at most $d-\ell$ members determine it [1]. Assigning each good tuple to such a small subfamily gives their fractional bound by counting preimages. The sharp coefficient will follow from controlling the whole complex through a compatible sequence of removals starting from small faces.

For families of convex sets in $\mathbb{R}^q$, Wegner’s proof of collapsibility [6, 10] sweeps a linear functional across the sets. A generic extremal point is determined by at most $q$ constraints, and those constraints identify a face that can be removed. For common flats, performing unrelated sweeps in the different quotient spaces would not by itself give a valid global order of removals.

We first replace the given family by polyhedral cylinders with compact bases, preserving exactly which subfamilies contain a common flat. Their feasible intersections become compact polytopes in their respective normal spaces. A generic linear functional then chooses an extremal vertex for each face. Faces with the same normal space and extremal vertex form a single interval, whose smallest face has at most $q$ members. The ordering is the crucial step: process larger normal spaces first, and then vertices in increasing functional value within each space. This makes every interval a valid collapse. Lemma 3.1 justifies the reduction and perturbations even when the original sets are unbounded or have empty interior.

Relation to the Helly literature

The general context is surveyed in [8, 9]; Tancer [10] explains how convex intersection patterns are studied through simplicial complexes. For $k=0$, the common-flat complex is just the ordinary nerve, and our collapsibility statement is Wegner’s theorem [6]. The new geometric step is the compatibility of the quotient-space sweeps when $k>0$.

The counting step is established topology. A $q$-collapsible complex is $q$-Leray: every induced subcomplex has zero reduced homology in degrees at least $q$. Kalai’s upper-bound theorem, in the integral formulation of Alon, Kalai, Matoušek and Meshulam [13], Section 6 and Theorems 12 and 13, then gives the exact finite inequality and the coefficient (1). Accordingly, the coefficient itself is classical; the contribution is to place the common-flat complex in the class to which that coefficient applies. The equality construction is the classical hyperplane pattern, realized here by distinct sets and lifted by taking products with $\mathbb{R}^k$.

Kalai and Meshulam’s topological colorful Helly theorem [11] and their work on Leray numbers under projections [12] provide related ways to derive Helly consequences from intersection topology. More recent optimal colorful fractional theorems for collapsible complexes [14], Theorems 1.4 and 1.5, and Leray complexes [15], Theorem 1.9 also apply once the geometric property is established. Ludwigson and Soberón already give a selection-structure theorem for common flats [1], Theorem 6, extending the framework of [16], Theorem 6. Results prescribing only the dimension of an intersection, such as [17], Theorem 1.5, concern a different geometric condition, as the strip example shows.

Translation invariance

For a nonempty closed convex set $C$, define its linearity space by

The space $L(C)$ is linear. Scalar closure follows from the definition, and if $v,w \in L(C)$ then translating first by $tv$ and then by $tw$ shows $v+w \in L(C)$.

The translation statement in the next lemma is a special case of the cone-translation observation in [19 Lemma 4.1].

For a concrete instance of (2), take the three coordinate slabs $C_i=\{x\in\mathbb{R}^3: |x_i|\le1\}$, $i=1,2,3$, and ask for common lines. Here $L(C_i)^\perp$ is spanned by the $i$th coordinate vector. Every pair has a common line in the remaining coordinate direction, but the triple intersection is a bounded cube. All ordinary intersections are nonempty; it is the growth of the sum of normal spaces from dimension two to dimension three that destroys the common line. This is exactly the additional information that the common-flat complex must record.

Remark 2.2. Closedness in Lemma 2.1 cannot simply be omitted. The convex set

contains the horizontal line at height one, but horizontal translation does not preserve its boundary point $(0,0)$. Convexity follows because every nontrivial convex combination involving a point with positive second coordinate still has positive second coordinate. This example explains the use of the closedness assumption in [1 Theorem 5].

Polyhedral cylinders and collapsibility

Fix integers $0\le k\le d$ and put $q=d-k$. Families are indexed by $[n]=\{1,\ldots,n\}$; repetitions and empty members are allowed. Their common-$k$-flat complex is

The empty intersection is $\mathbb{R}^d$, so the empty face belongs to $\mathcal{K}$. A label whose set contains no $k$-flat is not a vertex.

An elementary $q$-collapse removes an interval $[B,T]=\{I:B\subseteq I\subseteq T\}$, where $B$ is contained in the unique maximal face $T$ of the current complex and $|B|\le q$. A complex is $q$-collapsible if such removals reduce it to the void complex. The empty face is allowed as $B$; in particular, a simplex is 0-collapsible. This is the convention in [10 Section 2]. For $k = 0$ the theorem below is Wegner’s convex-nerve theorem; the proof coordinates the usual polyhedral sweep across different normal spaces when $k > 0$.

Proof. Discard labels which are not vertices of the common-flat complex. For each nonempty face $I$, choose a contained flat $x_I + V_I$ with $\dim V_I = k$. For each remaining label put

Lemma 2.1 gives $L_i \subseteq L(C_i)$, so $D_i^0 \subseteq C_i$. Every chosen witness flat is retained. Consequently these cylinders have exactly the original common-flat complex. The sum of a compact polytope and a subspace is closed: it is the inverse image of a compact polytope under projection onto $L_i^\perp$. Its lineality is exactly $L_i$.

We justify small perturbations without an assumption of boundedness in the ambient space. Put $A_i = L_i^\perp$. For a subfamily $I$ write $W_I = \sum_{i \in I} A_i$. The linear map

is injective: a vector in its kernel lies both in $W_I$ and in $\bigcap_{i \in I} L_i = W_I^\perp$. In finite dimensions its inverse on its image is bounded. Thus bounded projections onto all $A_i$ bound the norm of a vector in $W_I$.

The ordinary nerve records subfamilies with nonempty intersection. Replace $D_i^0$ by $D_i^0 + \varepsilon[-1,1]^d$. For all sufficiently small common $\varepsilon> 0$, this preserves that nerve. Indeed, if an originally empty intersection became nonempty for $\varepsilon_j \downarrow0$, project witnesses onto $W_I$. Their projections onto each $A_i$ remain bounded, because $\pi_{A_i}D_i^0$ is compact. The preceding injectivity makes the witnesses bounded. A convergent subsequence would give a point of the originally empty intersection. There are only finitely many subfamilies. Existing intersections remain nonempty and now contain an open ball, since any old common point has an $\varepsilon$-ball in every thickened member. Lineality spaces stay equal to $L_i$. The lineality criterion therefore preserves the common-flat complex.

Each thickened member has a full-dimensional compact polytope as its quotient by $L_i$, so it has a finite description (4), with nonzero normals in $A_i$. Those normals span $A_i$, and their common recession cone is $L_i$. There is an open neighborhood of the right-hand-side vector in which the entire ordinary nerve is constant. Feasible intersections retain a point satisfying all inequalities strictly. Infeasible intersections cannot become feasible along a sequence converging to the original right-hand side: the quotient of each member is uniformly bounded in such a sequence. To verify this last assertion, an unbounded sequence in $A_i$ with bounded right-hand sides would, after normalization and passage to a subsequence, give a nonzero recession vector in $A_i$, contradicting boundedness of the quotient. The injective projection map above then bounds joint witnesses in $W_I$, and a limit gives the claimed contradiction.

Finally choose the right-hand sides generically inside this open neighborhood. For each linearly dependent collection $J$ of normals, choose a nonzero vector $(c_h)_{h\in J}$ with $\sum_{h\in J} c_h a_h = 0$ and avoid the proper hyperplane $\sum_{h\in J} c_h b_h = 0$ in parameter space. Finitely many proper hyperplanes cannot cover an open set. The resulting bounding hyperplanes of a dependent collection have no common point. Recession and lineality depend only on the normals, so they are unchanged. The nerve and common-flat complex are unchanged as well.

Proof. Use Lemma 3.1 and its labelled inequalities. For each nonempty feasible subfamily $I$, put

Then $P_I$ is a full-dimensional compact polytope in $W_I$. Boundedness follows from the injective projection argument in the lemma, and full dimension follows by projecting an interior point of the intersection onto $W_I$. Moreover $\bigcap_{i\in I} D_i = P_I + W_I^\perp$. The common-flat faces are precisely the feasible $I$ with $\dim W_I \le q = d-k$. Include $I = \emptyset$ with $W_I = 0$ and $P_I = \{0\}$.

At a vertex of $P_I$, the active labelled normals are linearly independent by general position. They span $W_I$, since otherwise a nonzero direction in $W_I$ perpendicular to all active normals could be followed a short distance in both directions while preserving every inequality, contrary to extremality. Thus exactly $r = \dim W_I$ labelled inequalities are active at each vertex.

Choose a vector $u \in\mathbb{R}^{d}$ with two generic properties. First, for each fixed space $W$, require $u \cdot v \ne u \cdot w$ for any distinct vertices $v,w$ among all polytopes $P_I$ with $W_I = W$. Second, for every independent collection of active normals spanning a space $W$, $\pi_W u$ does not belong to the span of any proper subcollection. Each forbidden condition is a proper linear subspace or hyperplane; there are finitely many, so such $u$ exists. Let $v_I$ be the unique vertex maximizing $u \cdot x$ on $P_I$.

Fix a possible pair $(W,v) = (W_I,v_I)$, with $r = \dim W$. Let $J$ be the $r$ active inequalities of $I$ at $v$, and let $B$ be the set of their owner labels. Then $|B| \le r \le q$ and $\sum_{i\in B} A_i = W$. Write

Every coefficient is positive. For if $w_h \in W$ is dual to the active normals, so that $a_j \cdot w_h = 1_{j=h}$, then $v - t w_h$ is feasible for small positive $t$. Optimality forces $\lambda_h \ge0$, and the second generic property rules out zero.

No additional labelled inequality with its normal in $W$ can be active at $v$: together with $J$ it would be a dependent collection of hyperplanes through the same point. Define

The faces with pair $(W,v)$ are exactly the interval $[B,T]$. To prove one inclusion, if $B \subseteq S \subseteq T$, the active normals force $W_S = W$ and $v \in P_S$. For every $x \in P_S$,

Equality forces all $r$ active equations, and hence $x = v$. Thus $v_S = v$. Conversely, a face $S$ with the same pair is contained in $T$. Its optimum must use all $r$ active inequalities in $J$; these are the only possible active inequalities with normals in $W$. If one were absent, the corresponding dual direction would give a feasible local increase of the objective, since the missing coefficient $\lambda_h$ is positive. Therefore $B \subseteq S$. The interval description also shows that $B,T$ do not depend on the initial choice of $I$ with this pair.

Order these pairs first by decreasing $\dim W$, then by any fixed order among spaces of the same dimension, and finally, for a fixed $W$, by increasing $u \cdot v$. Remove their intervals in this order. At the moment $[B,T]$ is removed, any remaining face $S$ containing $B$ has $W \subseteq W_S$. A larger dimension has already been removed, so $W_S = W$. The intersection for $S$ is contained in that for $B$, giving $u \cdot v_S \le u \cdot v$. A strict inequality has also already been processed. Equality identifies the same vertex, by the first generic property; hence $S \subseteq T$. Thus $T$ is the unique maximal remaining face containing $B$. Each interval removal is an elementary $q$-collapse. The intervals partition all faces, so the procedure reaches the void complex. The last, zero-dimensional interval consists of the simplex on whole-space members and uses $B = \varnothing$.

For a complex $X$ on a specified ground set, write $X[S] = \{I \in X : I \subseteq S\}$ for its induced subcomplex. It is $q$-Leray if $\widetilde{H}_j(X[S]; \mathbb{Z}) = 0$ for all $j \ge q$ and all $S$. Only nonnegative homological degrees enter this definition. The following standard implication is included with integral coefficients, as required by the formulation of the upper-bound theorem in [13 Section 6].

The finite bound and fractional coefficient

Write $g_{q+1}$ for the number of $(q + 1)$-element subfamilies with a common $k$-flat, and $M$ for the largest cardinality of a subfamily with that property. We use $\binom{a}{b} = 0$ when $0 \le a < b$.

The formulation in [13 Theorem 13] says that exceeding $\binom{n}{q+1} - \binom{n-r}{q+1}$ forces a face of dimension $q + r$. Set $r = M - q$ to obtain (5); such a face would have $M + 1$ vertices. If $M = q$, the inequality simply says $f_q(X) = 0$.

If $q=0$, then $g_1=M$. In all cases, for $0<\alpha\le1$,

Proof. Suppose $q\ge1$. Theorem 3.2 and Lemma 3.3 make $\mathcal{K}$ $q$-Leray. For any original index not already a vertex, add it as an isolated vertex. On every induced subcomplex, this changes no positive-degree homology. It therefore preserves $q$-Lerayness, the number of faces of size $q+1\ge2$, and the largest face size $M\ge1$. Now the complex has exactly $n$ vertices, and Theorem 4.1 gives (6). Under the hypothesis of (7), at least one good tuple exists, so $M\ge q+1$. Combining that hypothesis with (6) yields

Every factor in the following product is nonnegative, and each numerator is at least $n-M$ while each denominator is at most $n$:

The denominators are positive because $n\ge q+1$. The identity remains valid at $M=n$, when the last numerator is zero. Taking the $(q+1)$st root proves (7).

If $q=0$, then $k=d$, and the only affine $d$-flat is $\mathbb{R}^{d}$ itself. Precisely the members equal to $\mathbb{R}^{d}$ qualify, and all of them have a common $d$-flat. Thus $g_1=M$, and (7) reduces to $M\ge\alpha n$.

Equality and optimality

Proof. Put $t=m-q$ and $N=n-m+q$, so $t\ge0$, $N\ge q$ and $t+N=n$. Choose distinct real numbers $a_1,\ldots,a_N$. In $\mathbb{R}^{q}$, define

Every $q$ hyperplanes have a unique common point, since their coefficient matrix is Vandermonde and invertible. No $q+1$ have a common point: otherwise the monic polynomial

would have $q+1$ distinct roots. These hyperplanes are distinct. For $q=1$ they are the distinct points $a_j$; for $q\ge2$, the first coefficient is one and the second coefficient determines $a_j$, so their equations cannot be scalar multiples.

Choose $t$ concentric closed balls with distinct sufficiently large positive radii, all containing every intersection point of $q$ hyperplanes. These are distinct from one another and from the hyperplanes. A subfamily of these $N+t$ sets intersects if and only if it contains at most $q$ hyperplanes. More than $q$ is impossible by construction. For at most $q$, extend the selected hyperplanes to $q$ of them, possible since $N\ge q$; their common point lies in all the selected hyperplanes and all the balls. The largest intersecting subfamily has all $t$ balls and $q$ hyperplanes, hence size $m$. Among subfamilies of size $q+1$, precisely those consisting entirely of hyperplanes fail to intersect; this gives (8). Replace each set $D$ by $D \times\mathbb{R}^{k}$. These products remain distinct, closed and convex. An intersection of products is nonempty exactly when the corresponding intersection in $\mathbb{R}^{q}$ is nonempty; in that event it contains a fiber $\{x\} \times\mathbb{R}^{k}$. Thus the counts and maximum size are preserved for common $k$-flats.

Proof. Validity follows from Theorem 4.2. For $\alpha=1$, coefficient one is valid and cannot be exceeded. Suppose $0<\alpha<1$ and put $b=1-(1-\alpha)^{1/(q+1)}$. For sufficiently large $n$, let

Since $b<1$, eventually $N_n\ge q$ and $m_n\le n$. Theorem 5.1 gives a distinct family with good-tuple density

For the first inequality, each factor $(N_n-j)/(n-j)$, $0\le j\le q$, is nonnegative and at most $N_n/n$; this follows from $N_n\le n$. The second uses $t_n\ge bn$. The largest qualifying subfamily nevertheless has relative size

Every proposed coefficient greater than $b$ therefore fails for sufficiently large $n.

Proof of Theorem 1.2. The implication (7) in Theorem 4.2 gives the asserted common-flat subfamily. Corollary 5.2 proves that no larger coefficient works uniformly, including for distinct families.

For $q=0$, the coefficient $\alpha$ is optimal when repetitions are allowed, by taking $\lceil\alpha n\rceil$ copies of $\mathbb{R}^{d}$ and empty sets in the remaining positions. With distinct members, at most one set equals $\mathbb{R}^{d}$, so that sharpness assertion does not apply; this is why Theorem 1.2 assumes $k<d$.