Extensions of Discrete Helly Theorems for Boxes
Timothy Edwards, Pablo Soberón · SIAM Journal on Discrete Mathematics · 2025
Abstract. We prove extensions of Halman’s discrete Helly theorem for axis-parallel boxes in [Formula: see text]. Halman’s theorem says that, given a set [Formula: see text] in [Formula: see text], if [Formula: see text] is a finite family of axis-parallel boxes such that the intersection of any [Formula: see text] contains a point of [Formula: see text], then the intersection of [Formula: see text] contains a point of [Formula: see text]. We prove colorful, fractional, and quantitative versions of Halman’s theorem. For the fractional versions, it is enough to check that many [Formula: see text]-tuples of the family contain points of [Formula: see text]. Among the colorful versions, we include variants where the coloring condition is replaced by an arbitrary matroid. Our results generalize beyond axis-parallel boxes to H-convex sets.