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.

Znění lemmatu

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

Důkaz

Nechť X je množina bodů ze znění lemmatu. n\geq d+2, tedy X je afinně závislá množina. +more Tedy existují \alpha_1,\alpha_2,\dots,\alpha_n\in\mathbb{R},\sum_{i=1}^n\alpha_i=0 takové, že \sum_{i=1}^n\alpha_i x_i=0 je netriviální kombinace.

Definujme A=\{x_i\,|\,\alpha_i>0\},B=X\setminus A a hodnotu S=\sum_{x_i\in A}\alpha_i\neq 0. Potom také platí -S=\sum_{x_i\in B}\alpha_i, protože \sum_{i=1}^n\alpha_i=0.

Potom bod z=\sum_{x_i\in A}\frac{\alpha_i}{S}x_i je konvexní kombinací bodů v A, protože \forall i\in J_A=\{j\in\{1,2,\dots,n\}\,|\,x_j\in A\}:\frac{\alpha_i}{S}\geq 0 a platí \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 z=\sum_{x_i\in B}\frac{-\alpha_i}{S}x_i, což je opět konvexní kombinace bodů v B z analogických důvodů. Tedy z je v konvexním obalu A i B a proto \mathrm{conv}(A)\cap\mathrm{conv}(B)\supseteq\{z\}\neq\emptyset.

Kategorie:Matematické věty a důkazy