BROWSE

Related Scientist

chakraborti,debsoumya's photo.

chakraborti,debsoumya
이산수학그룹
more info

ITEM VIEW & DOWNLOAD

Fractional Helly Theorem for Cartesian Products of Convex Sets

Cited 0 time in webofscience Cited 0 time in scopus
92 Viewed 0 Downloaded
Title
Fractional Helly Theorem for Cartesian Products of Convex Sets
Author(s)
Debsoumya Chakraborti; Kim, Jaehoon; Jinha Kim; Kim, Minki; Hong Liu
Publication Date
2022-12
Journal
Discrete and Computational Geometry, v.70, pp.1631 - 1651
Publisher
Springer
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.
URI
https://pr.ibs.re.kr/handle/8788114/14312
DOI
10.1007/s00454-022-00468-8
ISSN
0179-5376
Appears in Collections:
Pioneer Research Center for Mathematical and Computational Sciences(수리 및 계산과학 연구단) > Discrete Mathematics Group(이산 수학 그룹) > 1. Journal Papers (저널논문)
Files in This Item:
There are no files associated with this item.

qrcode

  • facebook

    twitter

  • Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
해당 아이템을 이메일로 공유하기 원하시면 인증을 거치시기 바랍니다.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse