The colourful simplicial depth conjecture

Abstract

Given $d+1$ sets of points, or colours, $S_1,\dots ,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|\le 1$, for all $i\in \{1,\dots ,d+1\}$. The colourful Carathéodory theorem states that, if $0$ is in the convex hull of each $S_i$, then there exists a colourful simplex $T$ containing $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,\dots ,d+1\}$, there are always at least $d^2+1$ colourful simplices containing $0$ in their convex hulls. We prove this conjecture via a combinatorial approach.