2016/02/25 by Averkov, Gennadiy, Merino, Bernardo González, Henze, Matthias +2
#Combinatorics (math.CO) #FOS: Mathematics #Metric Geometry (math.MG) #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.1602.07839
Given a subset S of Rn, let c(S,k) be the smallest number t such that whenever finitely many convex sets have exactly k common points in S, there exist at most t of these sets that already have exactly k common points in S. For S = Zn, this number was introduced by Aliev et al. [2014] who gave an explicit bound showing that c(Zn,k) = O(k) holds for every fixed n. Recently, Chestnut et al. [2015] improved this to c(Zn,k) = O(k (log log k)(log k)-1/3 ) and provided the lower bound c(Zn,k) = Omega(k(n-1)/(n+1)). We provide a combinatorial description of c(S,k) in terms of polytopes with vertices in S and use it to improve the previously known bounds as follows: We strengthen the bound of Aliev et al. [2014] by a constant factor and extend it to general discrete sets S. We close the gap for Zn by showing that c(Zn,k) = Theta(k(n-1)/(n+1)) holds for every fixed n. Finally, we determine the exact values of c(Zn,k) for all k <= 4.