Tight bounds on discrete quantitative Helly numbers
Tight bounds on discrete quantitative Helly numbers
复制标题
离散定量 Helly 数的严格界限
DOI：
10.1016/j.aam.2017.04.003
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Stefan Weltge
中科院分区：
文献类型：
--
作者：
G. Averkov;Bernardo González Merino;Ingo Paschke;Matthias Schymura;Stefan Weltge
令S为Rn的离散子集，并定义c(S,k)为具有以下性质的最小数：如果凸集的有限族恰好具有S的k个公共点，则该族中至多c(S,k)个凸集已经具有S的k个公共点。对于 S= Z n，这个数字反复出现在不同的上下文中，例如数字的优化和几何，最近，在 De Loera 等人（2015）的 Helly 和 Tverberg 定理的上下文中，对于一般集合 S。在这项工作中，我们用 S 中顶点的多面体对 c (S, k) 进行了有用的描述。从这个描述开始，我们回答了关于 c (S, k) 的几个基本问题。我们为每个离散 S 提供一般上限 c (S, k)≤⌊(k+ 1)/2⌋(c (S, 0)− 2)+ c (S, 0)。对于整数格 S= Z n，采用数几何技术，我们通过证明每个固定 n 的估计 c (Z n, k)= θ (k (n− 1)/(n+ 1)) 来解决渐近行为问题，我们计算 k= 0,…, 4 时的 c (Z n, k) 的精确值。
Let S be a discrete subset of R n and define c (S, k) as the smallest number with the property that if a finite family of convex sets has exactly k points of S in common, then at most c (S, k) convex sets in this family already have exactly k points of S in common. For S= Z n, this number repeatedly appeared in different contexts as, for instance, optimization and geometry of numbers and, very recently, for general sets S, in the context of Helly and Tverberg theorems in De Loera et al.(2015). In this work, we give a useful description of c (S, k) in terms of polytopes with vertices in S. Starting with this description, we answer several fundamental questions about c (S, k). We provide the general upper bound c (S, k)≤⌊(k+ 1)/2⌋(c (S, 0)− 2)+ c (S, 0) for every discrete S. For the integer lattice S= Z n, employing techniques from the geometry of numbers, we solve the question on the asymptotic behavior by proving the estimate c (Z n, k)= Θ (k (n− 1)/(n+ 1)) for every fixed n, and we compute the exact values of c (Z n, k) for k= 0,…, 4.