Discrete quantitative Helly-type theorems with boxes
Discrete quantitative Helly-type theorems with boxes
复制标题
带框的离散定量 Helly 型定理
DOI：
10.1016/j.aam.2021.102217
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Travis Dillon
中科院分区：
文献类型：
--
作者：
Travis Dillon
在组合凸几何中对Helly-型定理的研究已经利用见证集和Doignon定理的定量扩展产生了Helly定理的体积版本。本文将这些思想结合起来，给出了以轴平行盒为见证集的整数格的量化Helly-型定理。我们的主要结果表明，当整数格的数量Helly数在每个固定的维上以多项式增长时，它们以盒子为见证集的变体是一致有界的。我们证明了这一定理的几个丰富多彩的分数变形。证明了即使当A⊆Z是共集时，A×A⊆R2的Helly数也不必是有限的.
Research on Helly-type theorems in combinatorial convex geometry has produced volumetric versions of Helly's theorem using witness sets and quantitative extensions of Doignon's theorem. This paper combines these philosophies and presents quantitative Helly-type theorems for the integer lattice with axis-parallel boxes as witness sets. Our main result shows that, while quantitative Helly numbers for the integer lattice grow polynomially in each fixed dimension, their variants with boxes as witness sets are uniformly bounded. We prove several colorful and fractional variations on this theorem. We also prove that the Helly number for A× A⊆ R 2 need not be finite even when A⊆ Z is a syndetic set.
DOI：
10.1016/j.jcta.2021.105465
发表时间：
2021
期刊：
Series A
影响因子：
--
作者：
Sarkar, Sherry;Xue, Alexander;Soberón, Pablo
通讯作者：
Soberón, Pablo