Radonovo lemma

Radonovo lemma je tvrzení v kombinatorické geometrii, které říká, že dostatečně velkou množinu bodů v prostoru lze rozdělit na dvě části tak, aby se jejich konvexní obaly protínaly. Toto lemma se používá například v důkazu Hellyho věty a je elementárním výsledkem kombinatorické geometrie. Johann Radon je formuloval v roce 1921.

Nechť ${\displaystyle X=\{x_{1},x_{2},\dots x_{n}\}\subset \mathbb {R} ^{d}}$ a ${\displaystyle n\geq d+2}$. Potom existuje rozdělení ${\displaystyle A,B\subset X:A\cap B=\emptyset \wedge A\cup B=X}$ takové, že ${\displaystyle \mathrm {conv} (A)\cap \mathrm {conv} (B)\neq \emptyset }$.

Nechť ${\displaystyle X}$ je množina bodů ze znění lemmatu. ${\displaystyle n\geq d+2}$, tedy ${\displaystyle X}$ je afinně závislá množina. Tedy existují ${\displaystyle \alpha _{1},\alpha _{2},\dots ,\alpha _{n}\in \mathbb {R} ,\sum _{i=1}^{n}\alpha _{i}=0}$ takové, že ${\displaystyle \sum _{i=1}^{n}\alpha _{i}x_{i}=0}$ je netriviální kombinace.

Definujme ${\displaystyle A=\{x_{i}\,|\,\alpha _{i}>0\},B=X\setminus A}$ a hodnotu ${\displaystyle S=\sum _{x_{i}\in A}\alpha _{i}\neq 0}$. Potom také platí ${\displaystyle -S=\sum _{x_{i}\in B}\alpha _{i}}$, protože ${\displaystyle \sum _{i=1}^{n}\alpha _{i}=0}$.

Potom bod ${\displaystyle z=\sum _{x_{i}\in A}{\frac {\alpha _{i}}{S}}x_{i}}$ je konvexní kombinací bodů v ${\displaystyle A}$, protože ${\displaystyle \forall i\in J_{A}=\{j\in \{1,2,\dots ,n\}\,|\,x_{j}\in A\}:{\frac {\alpha _{i}}{S}}\geq 0}$ a platí ${\displaystyle \sum _{i\in J_{A}}{\frac {\alpha _{i}}{S}}={\frac {1}{S}}\sum _{i\in J_{A}}\alpha _{i}={\frac {1}{S}}S=1}$.

Zároveň ale ${\displaystyle z=\sum _{x_{i}\in B}{\frac {-\alpha _{i}}{S}}x_{i}}$, což je opět konvexní kombinace bodů v ${\displaystyle B}$ z analogických důvodů. Tedy ${\displaystyle z}$ je v konvexním obalu ${\displaystyle A}$ i ${\displaystyle B}$ a proto ${\displaystyle \mathrm {conv} (A)\cap \mathrm {conv} (B)\supseteq \{z\}\neq \emptyset }$.