Strong version of Caratheodory lemma

353 Views Asked by At

Let $X = \{ x_{1}, x_{2}, \ldots, x_{n} \}$ be any finite $n$-element set $X \subset \mathbb{R}^{n-1}$ and let $X' = \text{conv}{X}$ be the convex hull of $X$.

The Caratheodory theorem states that if a point $x$ lies in the convex hull of a set $P \subset \mathbb{R}^{d}$, then it can be written as the convex combination of at most $d+1$ points from $P$.

I would like to prove a kind of 'stronger' result, namely, let $x$ lie in the convex hull of a set $S \subset \mathbb{R}^{n-1}$, where $|S| > n$. How to prove that there exist at least two subsets $S_{1}, S_{2}$ such that $|S_{1}| = |S_{2}| = n$ and $x \in \text{conv}(S_{1}), x \in \text{conv}(S_{2})$?

(for instance, if $n=2$, let $S = \{ a, b, c \} \subset \mathbb{R}$ and clearly if $x \in \text{conv}(S)$, then $x$ is contained in at least two intervals with endpoints $a, b, c$)

Are there any possibilities to find some tricky applications of Radon/Helly theorems?

1

There are 1 best solutions below

0
On BEST ANSWER

This is a byproduct of the proof of the theorem, so let's look at it. We start with $x = \sum_{j\in J} c_j p_j$ where $c_j>0$, $\sum_{j\in J} c_j = 1$, and the index set $J$ has $|J|>n$. Consider the vectors $v_j = p_j + e_n\in\mathbb{R}^n$ where $e_n$ is the $n$th standard basis vectors. Since they are linearly dependent, there exist coefficients $b_j$, not all zero, such that $\sum_{j\in J} b_j v_j=0$. This means $$ \sum_{j\in J} b_j p_j = 0\quad \text{and}\quad \sum_{j\in J} b_j = 0 $$ Then we consider the coefficients $c_j(t) = c_j + t b_j$ where $t\in\mathbb R$. By construction, $\sum_{j\in J} c_j(t) = 1$ and $\sum_{j\in J} c_j(t)p_j = x$ for all $t$. The function $$ m(t) = \min_{j\in J} c_j(t) $$ is continuous with respect to $t$ and positive at $0$. On the other hand, it is negative when $|t|$ is sufficiently large, because among the numbers $b_j$ there are both positive and negative ones. Hence, there exist $t_1<0$ and $t_2>0$ such that $m(t_1)=0$ and $m(t_2)=0$. So, the sets $S_1 = \{p_j: c_j(t_1) > 0\}$ and $S_2 = \{p_j: c_j(t_2) > 0\}$ have cardinality less than $|J|$, and $x$ is contained in the convex hull of either.

These two sets are not equal, because it's impossible to have $c_j(t_1)=0=c_j(t_2)$ in view of $c_j(t)$ being linear, with $c_j(0)>0$.