Robust Tverberg and Colourful Carathéodory Results via Random Choice
Pablo Soberón · Combinatorics Probability Computing · 2017
We use the probabilistic method to obtain versions of the colourful 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 ℝ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 a bound N = rt + O( $\sqrt{t}$ ) for fixed r,d which is polynomial in each parameters. Our bounds extend to colourful versions of Tverberg's theorem, as well as Reay-type variations of this theorem.