Helly-type splitting theorems hold for k-flats of all dimensions, but not for general convex sets

What Helly's theorem and its transversal relatives actually guaranteed

Helly's theorem, as summarized in the classic Danzer–Grünbaum–Klee survey, states that a finite (or compact) family of at least d+1 convex sets in R^d has a common point if and only if every d+1 of them do [2]. The same survey frames the transversal problem explicitly: for m-flats with 1 ≤ m ≤ n−1, the manifold of m-flats is not contractible, and the authors note that 'herein lies part of the difficulty' of extending Helly-type criteria beyond points [2]. That structural obstacle is the baseline against which the new paper must be read.

The modern quantitative baseline is the (p,q)-theorem. Alon and Kleitman proved that a finite family of convex sets in R^d with the (p,q)-property with respect to points admits a transversal by C(p,q,d) points, provided p ≥ q ≥ d+1 [1]. Alon and Kalai proved the parallel statement for hyperplane transversals, again with p ≥ q ≥ d+1 [1]. The new paper's introduction stresses that these are the only two dimensions where such sufficient Helly-type criteria exist for general compact convex families, and that for intermediate k with 1 ≤ k ≤ d−2, Alon, Kalai, Matoušek and Meshulam constructed arbitrarily large convex families where any h members can be crossed by a k-flat but no h+4 can [1].

α-splitting, k-flat depth, and the Tukey-depth connection

The new paper's central definition is α-splitting. A finite point set P in R^d is α-split by a hyperplane h if each closed half-space bounded by h contains at least α|P| points of P; P is α-split by a k-flat τ if it is α-split by every hyperplane through τ [1]. The authors note that this coincides with Tukey depth for k = 0, and that in the notation of Bukh, Matoušek and Nivasch such k-flats are said to have depth α [1]. The depth of a k-flat is defined as the infimum of |H ∩ P| over closed half-spaces H containing τ [1].

This definition matters because it changes what a Helly-type condition is being asked to preserve. For points, the set of α-deep points is a convex polytope S_α(P), and the (p,q,α)-property for point splitting reduces to the ordinary (p,q)-property of the α-centersets, so Alon–Kleitman applies directly [1]. For hyperplanes and k-flats of positive dimension, that reduction fails: the paper gives an explicit planar example where a hyperplane h α-splits P but misses the α-centerset S_α(P) entirely [1]. The new work therefore has to build a different object, a robust analogue S̃_α(P) derived from Matoušek's simplicial partitions, such that any α-splitting k-flat crosses S̃_α(P) and, conversely, any k-flat crossing S̃_α(P) β-splits P for some β ∈ (0, α) [1].

The new splitting theorems and how far they extend

Theorem 1.3 of the new paper states that for any α ∈ (0, 1/2] and any integers p ≥ q ≥ d+1, there exist constants C = C(p,q,d) < ∞ and β = β(α,d) ∈ (0,α) such that every family of n ≥ p finite point sets in R^d with the (p,q,α)-property with respect to hyperplanes can be β-split by at most C hyperplanes [1]. The proof is deduced from Alon–Kalai's hyperplane (p,q)-theorem [1], so the hyperplane case inherits the earlier machinery but with a loss from α to β.

Theorem 1.4 is the stronger and more general statement. For every d, every 0 ≤ k ≤ d−1, every p ≥ q ≥ (k+1)(d−k)+1, and every α ∈ (0,1/2] and ε ∈ (0,α), there is an integer C = C(p,q,d,k,ε) < ∞ such that every family of n ≥ p finite point sets in R^d with the (p,q,α)-property with respect to k-flats can be (α−ε)-split by at most C k-flats [1]. For k = d−1 this recovers a stronger form of Theorem 1.3 with β = α−ε, at the cost of a constant that may grow as ε → 0 [1]. The threshold q ≥ (k+1)(d−k)+1 is the dimension of the Grassmannian of k-flats in R^d, and the proof passes to R^{(k+1)(d−k)}, uses ε-approximations to build semi-algebraic dual regions Λ_{α,ε,k}(P_i), and applies Matoušek's (p,q)-theorem for bounded VC-dimension [1].

How the splitting result compares with quantitative transversal work

The closest quantitative relative in the supplied evidence is the Axelrod-Freed–Carvalho–Takahashi work on quantitative transversal theorems in the plane [5]. That paper generalizes Hadwiger's theorem, proving that compact convex sets in R^2 with an (f,α)-consistent ordering admit an (f,α)-transversal, and it conjectures a higher-dimensional analogue for (f,α)-consistent k-orderings [5]. The new paper's Theorem 1.4 is not a special case of that conjecture: it concerns finite point sets, uses α-splitting rather than a monotone function on convex sets, and obtains a (p,q)-type conclusion rather than a consistent-ordering conclusion [1][5]. The two results are complementary rather than nested.

The validation evidence is also indirect. Nandi's survey of piercing and covering results in combinatorial geometry places Helly's theorem and Hadwiger–Debrunner (p,q)-problems in the same lineage [4], which is the lineage the new paper extends. But the new paper's own introduction is explicit that no comparable (p,q)-theorem exists for k-flat transversals to general convex sets when 1 ≤ k ≤ d−2 [1], citing Alon–Kalai–Matoušek–Meshulam. So the splitting result does not validate the convex-set conjecture; it identifies a different setting where the Helly-type phenomenon survives.

Where the conclusion stops, and what remains open

The evidence boundary is stated by the authors themselves. The theorems are limited to finite point sets being α-split by k-flats; they do not apply to general families of compact convex sets [1]. The paper's concluding remarks note that since no (p,q)-theorems can exist for k-flat transversals to general convex sets for 1 ≤ k ≤ d−2 [1], it seems unlikely that a general (p,q)-type statement similar to Theorem 1.4 can hold with ε = 0. The limitation evidence in the supplied set reinforces this: McGinnis's work on piercing families of convex sets in the plane that avoid a certain subfamily with lines [6] and Egyed's line-transversal algorithms [7] both operate in the convex-set transversal setting where the new paper's positive result does not reach.

Two open questions are flagged. First, whether Theorem 1.3 can be established with β = α rather than β < α [1]. Second, whether the general ideas in Sections 3 and 4 of the new paper can make progress on additional quantitative or approximate Helly-type problems [1]. The Tukey-depth precursor by Sinova and Cascos [3] is relevant here only as background on depth terminology in interval-valued settings; it does not bear on the k-flat splitting theorems themselves.

About These Sources

This research page is built on 7 peer-reviewed studies — published from 1963 to 2026, 5 from 2024 or later, collectively cited 1,186 times — selected as the most relevant from 7 studies that passed quality screening, drawn from 68 papers retrieved from a database of over 500 million.

Sources used in this answer