Quadratically Many Colorful Simplices
Imre Bárány, Jiřı́ Matoušek · SIAM Journal on Discrete Mathematics · 2007
The colorful Carathéodory theorem asserts that if $X_1,X_2,\ldots,X_{d+1}$ are sets in ${\bf R}^d$, each containing the origin 0 in its convex hull, then there exists a set $S \subseteq X_1 \cup \cdots \cup X_{d+1}$ with $|S \cap X_i| = 1$ for all $i=1,2,\ldots,d+1$ and $0 \in conv(S)$ (we call $conv(S)$ a colorful covering simplex). Deza et al. [Discrete Comput. Geom., 35 (2006), pp. 597–615] proved that if the $X_i$ are in general position with respect to 0 (consequently, each $X_i$ has at least $d+1$ points), then there are at least $2d$ colorful covering simplices, and they constructed an example with no more than $d^2+1$ such simplices. Under the same assumption, we show that there are at least $\frac{1}{5}d(d+1)$ colorful covering simplices, thus determining the order of magnitude. A similar result was proved independently by Stephen and Thomas [http://www.arxiv.org/abs/math.CO/0512400 (2005)]. We also obtain a lower bound of $3d$ for $d \geq 3$, which is better for small d and, in particular, together with a parity argument it settles the case $d=3$, where the minimum possible number of colorful covering simplices is 10.