Robust Tverberg and colorful Carathéodory results via random choice

2016/06/28 by Soberón, Pablo
#05D40 #52A35 #Combinatorics (math.CO) #FOS: Mathematics #Metric Geometry (math.MG)

paper · doi:10.48550/arxiv.1606.08790

Abstract

We use the probabilistic method to obtain versions of the colorful Carathéodory theorem and Tverberg's theorem with tolerance. In particular, we give bounds for the smallest integer N=N(t,d,r) such that for any N points in R^d, there is a partition of them into r parts for which the following condition holds: after removing any t points from the set, the convex hulls of what is left in each part intersect. We prove the bound N=rt+O(√(t)) for fixed r,d which is polynomial in each parameters. Our bounds extend to colorful versions of Tverberg's theorem, as well as Reay-type variations of this theorem.

Related

• Tolerance for colorful Tverberg partitions
• Quantitative Tverberg theorems over lattices and other discrete sets
• A generalization of Tverberg's Theorem
• Colorful Intersections and Tverberg Partitions
• Equal coefficients and tolerance in coloured Tverberg partitions