{
  "id": "2108.09962",
  "version": "v1",
  "published": "2021-08-23T06:22:11.000Z",
  "updated": "2021-08-23T06:22:11.000Z",
  "title": "Fractional Helly theorem for Cartesian products of convex sets",
  "authors": [
    "Debsoumya Chakraborti",
    "Jaehoon Kim",
    "Jinha Kim",
    "Minki Kim",
    "Hong Liu"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "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. We generalize Eckhoff's result to Cartesian products of convex sets in all dimensions. This answers a question of B\\'ar\\'any and Kalai. 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_{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 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 that 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$, 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 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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-08-23T06:22:11.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05E45",
      "52A35"
    ],
    "keywords": [
      "fractional helly theorem",
      "convex sets",
      "cartesian products",
      "intersection patterns influence global intersection",
      "local intersection patterns influence global"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}