Generalization of Caratheodory's theorem

169 Views Asked by At

Conjecture: Let $S\subseteq \mathbb{R}^d$ and let $x, y \in \text{conv}(S)$, the convex hull of $S$. Then, $x, y \in \text{conv}(S')$ for some $S' \subseteq S$ such that $|S'| \leq d+2$.

Basically, this is analogous to Caratheodory's theorem but with two points instead of one. If we consider the simple case of $d=2$ this would imply that any two points inside a convex polygone with vertices $(v_1, \ldots ,v_k)$ lie in the convex hull of four vertices. I think this is true in dimension $2$ (after doing some drawings) but I have hit a dead end trying to adapt the traditional proof for the original Caratheodory's theorem.

I will expand more on my findings but perhaps there is a known counterexample in higher dimensions?

1

There are 1 best solutions below

3
On BEST ANSWER

It is not true. Consider six points in three dimensions $S = \{u_1, v_1, w_1, u_2, v_2, w_2\}$, where $T_1 = \operatorname{conv}\{u_1, v_1, w_1\}$ and $T_2 = \operatorname{conv}\{u_2, v_2, w_2\}$ are two non-degenerate triangles in two distinct parallel planes $P_1$ and $P_2$ respectively. Choose a points $x_1, x_2$ in the relative interiors of $T_1$ and $T_2$ respectively.

Then, the only way we can express $x_i$ as a convex combination of points in $S$ is by using $u_i, v_i, w_i$ (with non-zero coefficients); given our construction, $T_i$ will be a face of $\operatorname{conv} S$, supported by $P_i$. This, of course, means that all $6$ points of $S$ will be required to include any convex subset containing both $x_1, x_2$, which makes it a counterexample.