@misc{AverkovGonzalezMerinoHenzeetal., author = {Averkov, Gennadiy and Gonz{\´a}lez Merino, Bernardo and Henze, Matthias and Paschke, Ingo and Weltge, Stefan}, title = {Tight bounds on discrete quantitative Helly numbers}, series = {arXiv.org : (math)}, journal = {arXiv.org : (math)}, pages = {19}, abstract = {Given a subset S of R^n, 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 = Z^n, this number was introduced by Aliev et al. [2014] who gave an explicit bound showing that c(Z^n,k) = O(k) holds for every fixed n. Recently, Chestnut et al. [2015] improved this to c(Z^n,k) = O(k (log log k)(log k)^{-1/3} ) and provided the lower bound c(Z^n,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 Z^n by showing that c(Z^n,k) = Theta(k^{(n-1)/(n+1)}) holds for every fixed n. Finally, we determine the exact values of c(Z^n,k) for all k <= 4.}, language = {en} } @misc{AverkovGonzalezMerinoPaschkeetal., author = {Averkov, Gennadiy and Gonz{\´a}lez Merino, Bernardo and Paschke, Ingo and Schymura, Matthias and Weltge, Stefan}, title = {Tight bounds on discrete quantitative Helly numbers}, series = {Advances in Applied Mathematics}, volume = {89}, journal = {Advances in Applied Mathematics}, issn = {0196-8858}, doi = {10.1016/j.aam.2017.04.003}, pages = {76 -- 101}, language = {en} }