Why does Radon's 8 theorem not work for $n+1$

74 Views Asked by At

Radon's Theorem Given any set $P$ of $d+2$ points in $\mathbb{R}^d$, one can partition $P$ into two $P_1$, $P_2$, such that $\text{conv}(P_1)\cap\text{conv}(P_2)\neq0$.

Why is the theorem not necessarily true if we only have $n+1$ vectors?

If we were to take some simple example, like $n=2$, then a set could be $$\binom{0}{0},\binom{0}{1},\binom{1}{0}$$ Then we can see geometrically that no matter what subsets $P_1$, $P_2$ we take, there are no intersections

enter image description here

But how would we prove this more formally?

1

There are 1 best solutions below

0
On

You example answers the question.

The theorem states that any set of $d + 2$ points in $\mathbb{R}^d$ can be partitioned into two sets whose convex hulls intersect. In your exmple this can't be done.

Generally speaking, for $d+1$ vectors in $\mathbb{R}^d$ you can take the $\{0\} \cup \{e_i\}_{i=1}^d$ vectors, where $e_i = [0, ... , 1, ..., 0]$ and you won't have any intersections. You can prove this by induction. So $d+1$ vectors is not sufficient.