# Is the following generalization of the Caratheodory theorem true?

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.

• 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)$. – Jan Kyncl Jul 23 '20 at 0:37
• 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)\}$. – Jan Kyncl Jul 23 '20 at 1:07
• @JanKyncl Indeed this is what I meant. Thanks for the counter-example – Erel Segal-Halevi Jul 23 '20 at 6:27
• 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)$. – Erel Segal-Halevi Jul 23 '20 at 7:38
• 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 – 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)\}$$.