Fractional Helly Theorem for Cartesian Products of Convex Sets

Abstract

© 2022, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.Helly’s theorem and its variants show that for a family of convex sets in Euclidean space, local intersection patterns influence global intersection patterns. A classical result of Eckhoff in 1988 provided an optimal fractional Helly theorem for axis-aligned boxes, which are Cartesian products of line segments. Answering a question raised by Bárány and Kalai, and independently Lew, we generalize Eckhoff’s result to Cartesian products of convex sets in all dimensions. In particular, we prove that given α∈ (1 - 1 / td, 1] and a finite family F of Cartesian products of convex sets ∏ i∈[t]Ai in Rtd with Ai⊂ Rd, if at least α-fraction of the (d+ 1) -tuples in F are intersecting, then at least (1-(td(1-α))1/(d+1))-fraction of sets in F are intersecting. This is a special case of a more general result on intersections of d-Leray complexes. We also provide a construction showing that our result on d-Leray complexes is optimal. Interestingly, the extremal example is representable as a family of Cartesian products of convex sets, implying that the bound α> 1 - 1 / td and the fraction (1-(td(1-α))1/(d+1)) above are also best possible. The well-known optimal construction for fractional Helly theorem for convex sets in Rd does not have (p, d+ 1) -condition for sublinear p, that is, it contains a linear-size subfamily with no intersecting (d+ 1) -tuple. Inspired by this, we give constructions showing that, somewhat surprisingly, imposing an additional (p, d+ 1) -condition has a negligible effect on improving the quantitative bounds in neither the fractional Helly theorem for convex sets nor Cartesian products of convex sets. Our constructions offer a rich family of distinct extremal configurations for fractional Helly theorem, implying in a sense that the optimal bound is stable.