Given $d+1$ sets of points, or colours, $S_1,\ldots,S_{ d+1}$ in $\mathbb R^d$, a colourful simplex is a set $T\subseteq\bigcup_{ i=1}^{ d+1}S_i$ such that $|T\cap S_i|\leq 1$, for all $i\in\{ 1,\ldots,d+1\}$. The colourful Carath\'eodory theorem states that, if $\mathbf 0$ is in the convex hull of each $S_i$, then there exists a colourful simplex $T$ containing $\mathbf 0$ in its convex hull. Deza, Huang, Stephen, and Terlaky (Colourful simplicial depth, Discrete Comput. Geom., 35, 597--604 (2006)) conjectured that, when $|S_i|=d+1$ for all $i\in\{ 1,\ldots,d+1\}$, there are always at least $d^2+1$ colourful simplices containing $\mathbf 0$ in their convex hulls. We prove this conjecture via a combinatorial approach.
Categories: math.CO