The colorful Carathéodory theorem (Bárány, 1982) considers $d+1$ "colors" $X_1,\ldots,X_{d+1}\subseteq \mathbb{R}^d$, and a point $x$ in the convex hull of each color ($x\in \text{conv}(X_i)$ for each $i\in[d+1]$). It says that there exists a set of $d+1$ points of distinct colors, such that $x$ is in their convex hull.

Suppose that, instead of a single point $x$, there are $d+1$ points $x_1\in \text{conv}(X_1),\ldots,x_{d+1}\in \text{conv}(X_{d+1})$. Let $\bar{x} := (x_1+\cdots+x_{d+1})/(d+1) = $ the average of these points. Is it true that there exists a set of $d+1$ points of distinct colors, such that $\bar{x}$ is in their convex hull?

Note that the Bárány's theorem is implied by this claim.

The motivation comes from this paper: https://dx.doi.org/10.1007/s00493-019-4019-y it says that a special case of Theorems 1.6 and 1.7 can be proved the the colorful Carathéodory theorem, and I wondered if the general case could be proved by a generalization of it.

  • $\begingroup$ The answer seems trivially true, since $\bar{x}$ is in the convex hull of the points $x_1, \dots, x_{n+1}$ and they have distinct colors. The question might be more interesting if the assumption was weakened to $x_i \in \mathrm{conv}(X_i)$. $\endgroup$ – Jan Kyncl Jul 23 '20 at 0:37
  • $\begingroup$ In such a case there would be a counterexample in the plane, for example: $X_1=(0,0), X_2=(0,1), X_3=\{(10,0),(10,10)\}$. $\endgroup$ – Jan Kyncl Jul 23 '20 at 1:07
  • $\begingroup$ @JanKyncl Indeed this is what I meant. Thanks for the counter-example $\endgroup$ – Erel Segal-Halevi Jul 23 '20 at 6:27
  • $\begingroup$ An even simpler example is $X_1 = X_2 = \{(0,0)\}$ and $X_3 = \{(-3,3),(3,3)\}$. Taking $x_1=x_2 =(0,0)$ and $x_3 = (0,3)$ gives $\bar{x} = (0,1)$, but for any selection of 3 points of different colors, their convex hull is an $45^{\circ}$ line that does not cross $(0,1)$. $\endgroup$ – Erel Segal-Halevi Jul 23 '20 at 7:38
  • $\begingroup$ I tried to avoid degeneracies and find an example in general position. I got an inspiration from the following paper, which may be relevant: doi.org/10.1016/j.comgeo.2012.01.006 $\endgroup$ – Jan Kyncl Jul 23 '20 at 12:14

There is a counterexample in the plane, for example the following four points in convex position: $X_1=(0,0), X_2=(0,1), X_3=\{(10,0),(10,10)\}$.

(This was originally posted as a comment to a previous version of the question).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.