A further generalization of the colourful Carathéodory theorem
Academic Article

Overview

Research

Additional Document Info

View All

Overview

abstract

Given $d+1$ sets, or colours, $S_1, S_2,...,S_{d+1}$ of points in
$\mathbb{R}^d$, a {\em colourful} set is a set $S\subseteq\bigcup_i S_i$ such
that $|S\cap S_i|\leq 1$ for $i=1,...,d+1$. The convex hull of a colourful set
$S$ is called a {\em colourful simplex}. B\'ar\'any's colourful Carath\'eodory
theorem asserts that if the origin 0 is contained in the convex hull of $S_i$
for $i=1,...,d+1$, then there exists a colourful simplex containing 0. The
sufficient condition for the existence of a colourful simplex containing 0 was
generalized to 0 being contained in the convex hull of $S_i\cup S_j$ for $1\leq
i< j \leq d+1$ by Arocha et al. and by Holmsen et al. We further generalize the
sufficient condition and obtain new colourful Carath\'eodory theorems. We also
give an algorithm to find a colourful simplex containing 0 under the
generalized condition. In the plane an alternative, and more general, proof
using graphs is given. In addition, we observe that any condition implying the
existence of a colourful simplex containing 0 actually implies the existence of
$\min_i|S_i|$ such simplices.