New Lower Bounds for Tverberg Partitions with Tolerance in the Plane

Abstract

Let $P$ be a set $n$ points in a $d$-dimensional space. Tverberg's theorem says that, if $n$ is at least $(k-1)(d+1)+1$, then $P$ can be partitioned into $k$ sets whose convex hulls intersect. Partitions with this property are called {\em Tverberg partitions}. A partition has tolerance $t$ if the partition remains a Tverberg partition after removal of any set of $t$ points from $P$. Tolerant Tverberg partitions exist in any dimension provided that $n$ is sufficiently large. Let $N(d,k,t)$ be the smallest value of $n$ such that tolerant Tverberg partitions exist for any set of $n$ points in ${\mathbb{R}}^d$. Only few exact values of $N(d,k,t)$ are known. In this paper we establish a new tight bound for $N(2,2,2)$. We also prove many new lower bounds on $N(2,k,t)$ for $k\ge 2$ and $t\ge 1$.

10 figures