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. 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$.

Portály: Matematika