Caratheodory's theorem with two vectors

233 Views Asked by At

Let $S\subset \mathbb R^n$ be given.

Take $x\in conv(S)$. Then by Caratheodory's theorem, we can find $n+1$ vectors in $S$ such that $x$ is in the convex hull of these vectors, i.e., there is $S'\subset S$ with $|S'|\le n+1$ such that $x\in conv(S')$.

Now suppose we have $x,y\in conv(S)$. Then Caratheodory's theorem implies there is $S'\subset S$ with $|S'|\le 2n+2$ such that $x,y\in conv(S')$.

My question is: can this upper bound on $|S'|$ be reduced to $2n+1$ or $2n$?

If $n=1$ then clearly $|S'|=2=2n$ suffices. For $n=2$ it seems to be the case, too (no proof).

The example in the answer to the question Generalization of Caratheodory's theorem shows that $|S'|< 2n$ is not possible in general.

1

There are 1 best solutions below

8
On BEST ANSWER

The upper bound of $2n+2$ can be reduced.

From Caratheodory's theorem we can find vectors $u_i,v_i$ in $S$ such that $$x\in \text{conv}(u_1,u_2, ... u_{n+1}),$$$$y\in \text{conv}(v_1,v_2, ... v_{n+1}).$$

Consider the vectors $v_1-u_1,v_2-u_1,,...,v_{n+1}-u_1.$ These are $n+1$ vectors and so are linearly dependent. Hence there are $a_i$, not all zero, such that $\sum a_i(v_i-u_1)=0$. If $\sum a_i=0$, then (as in the proof of Caratheodory's theorem) one of the $v_i$ is not needed for $y$ and only $2n+1$ vectors would be required. We can therefore suppose $\sum a_i \ne 0$.

We now have $(\sum a_i)u_1- \sum a_iv_i=0$ and so there are $b_i$ such that $\sum b_i=1$ and $u_1= \sum b_iv_i$.

Let a convex combination representing $y$ be $y= \sum c_iv_i$ (where we can assume that all $c_i$ are non-zero) and let $t$ be the least positive $\frac{c_i}{b_i}$. Then $$y=tu_1+\sum v_i(c_i-tb_i).$$

Thus $2n+1$ vectors suffice since the coefficient of one of the $v_i$ is zero.

The 'new' upper bound of $2n+1$ can be reduced

We can suppose that $S$ contains $2n+1$ vectors. As in the reduction from $2n+2$ we can suppose that $$x\in \text{conv}(u_1,u_2, ... u_{n+1}),$$$$y\in \text{conv}(u_1,v_2, ... v_{n+1}).$$ Let $P$ be $\text{conv}(S-\{u_1\})$.

If both $x$ and $y$ are in $P$ then we can simply take $S'=S-\{u_1\}$. So, without loss of generality suppose $x$ is not in $P$.

As in the reduction from $2n+2$, we can now replace one of the $u_i$s by $v_2$. We are finished unless it is $u_1$ which gets replaced. But this is impossible because $x$ is not a convex combination of vectors in $S-\{u_1\}$.