2021 Combinatorics Workshop (2021 조합론 학술대회)

Fractional Helly theorem for Cartesian products of convex sets

21 Dec 2021, 15:00

25m

Yangpyeong The Bloomvista

Contributed talk Session

Speaker

Minki Kim (IBS DIMAG)

Description

Helly's theorem and its variants asserts 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-parallel boxes, which are Cartesian products of line segments. Answering a question raised by Barany and Kalai, and independently by Lew, we generalize Eckhoff's result to Cartesian products of convex sets in all dimensions. Namely, we prove that, given $\alpha \in (1-\frac{1}{t^d},1]$ and a finite family of Cartesian products of convex sets $\prod _{i\in [t]}{A}_i$ in ${\mathbb{R}}^{td}$ with $A_i\subset {\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 the sets in $\mathcal{F}$ are intersecting.