Hellys 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 Barany and Kalai, and independently Lew, we generalize Eckhoffs result to Cartesian products of convex sets in all dimensions. In particular, we prove that given $alpha in (1-frac{1}{t^d},1]$ and a finite family $mathcal{F}$ of Cartesian products of convex sets $prod_{iin[t]}A_i$ in $mathbb{R}^{td}$ with $A_isubset mathbb{R}^d$ if at least $alpha$-fraction of the $(d+1)$-tuples in $mathcal{F}$ are intersecting then at least $(1-(t^d(1-alpha))^{1/(d+1)})$-fraction of sets in $mathcal{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 the bound $alpha>1-frac{1}{t^d}$ and the fraction $(1-(t^d(1-alpha))^{1/(d+1)})$ above are also best possible. The well-known optimal construction for fractional Helly theorem for convex sets in $mathbb{R}^d$ does not have $(p,d+1)$-condition for sublinear $p$. Inspired by this we give constructions showing that, somewhat surprisingly, imposing additional $(p,d+1)$-condition has 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.
تحميل البحث