Hellyho věta

Hellyho věta je základní výsledek kombinatorické geometrie. Popisuje způsob, jak se konvexní množiny protínají a jaké podmínky musí systém konvexních množin splňovat, abychom mohli zaručit, že existuje bod, který je obsažen v každé množině ze systému. Poprvé byla objevena Eduardem Hellym v roce 1913.

Znění věty

• Nechť $ℱ$ je konečný systém alespoň $d+1$ konvexních množin v ${ℝ}^d$. Pokud každých $d+1$ množin z $ℱ$ má neprázdný průnik, potom celá $ℱ$ má neprázdný průnik.

• Symbolicky zapsáno:

$(\mathrm{\forall }{ℱ}^{\prime }\subseteq ℱ,|{ℱ}^{\prime }|=d+1:\bigcap _{M\in {ℱ}^{\prime }}M\ne \mathrm{\varnothing })\Rightarrow \bigcap _{M\in ℱ}M\ne \mathrm{\varnothing }$

Důkaz

Označíme $ℱ=\{M_1,M_2,\dots ,M_n\}$ a zafixujeme $d$. Důkaz provedeme matematickou indukcí podle $n=|ℱ|$ a použijeme Radonovo lemma.

$n=d+1:$ Věta platí triviálně.

$n\ge d+2:$ Definuji $x_i\in \bigcap _{M\in (ℱ\setminus \{M_i\})}M=\bigcap _{j\ne i}{M}_j$.

Podle indukčního předpokladu věta platí pro $n-1$, tedy body $X=\{x_1,x_2,\dots ,x_n\}$ jsou dobře definované.

Potom podle Radonova lemmatu lze tyto body rozdělit do množin $A,B\subset X:A\cap B=\mathrm{\varnothing }\wedge A\cup B=X$ tak, že $\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{v}(A)\cap \mathrm{c}\mathrm{o}\mathrm{n}\mathrm{v}(B)\ne \mathrm{\varnothing }$.

Definuji $z\in \mathrm{c}\mathrm{o}\mathrm{n}\mathrm{v}(A)\cap \mathrm{c}\mathrm{o}\mathrm{n}\mathrm{v}(B)$ a tvrdím, že $z\in \bigcap _{M\in ℱ}M$:

Dokážu, že $\mathrm{\forall }i\in \{1,2,\dots ,n\}:z\in M_i$. Nechť $i\in \{1,2,\dots ,n\}$ libovolně. Potom platí buď $x_i\notin A$ nebo $x_i\notin B$. Bez újmy na obecnosti nechť $x_i\notin A$. Potom každý bod z $A$ leží v $M_i$, protože v $M_i$ leží každý bod z $X$ kromě $x_i$. Když tam leží každý bod z $A$, určitě tam leží i jejich konvexní obal, protože $M_i$ je konvexní. Takže $M_i\supseteq \mathrm{c}\mathrm{o}\mathrm{n}\mathrm{v}(A)$ a z definice $z$ platí $z\in \mathrm{c}\mathrm{o}\mathrm{n}\mathrm{v}(A)$. Tedy $z\in M_i$.

Nekonečná verze

Věta neplatí, pokud $ℱ$ je nekonečná. Protipříklad v ${ℝ}^1$ by byl například $ℱ=\{(0,1/n)|n\in \mathbb{N}\}$: $ℱ$ tvoří konvexní otevřené množiny, kde každé dvě mají neprázdný průnik, ale pro každý bod $x\in (0,1)$ bude existovat $n\in \mathbb{N}:1/n<x$.

Platí ovšem podobná věta, když budeme vyžadovat kompaktnost množin:

• Nechť $ℱ$ je libovolný systém alespoň $d+1$ kompaktních konvexních množin v ${ℝ}^d$. Pokud každých $d+1$ množin z $ℱ$ má neprázdný průnik, potom celá $ℱ$ má neprázdný průnik.

Toto tvrzení lehce vyplývá z konečné verze. Podle ní každá konečná podmnožina $ℱ$ má neprázdný průnik. Je základní vlastností kompaktních množin, že pokud každá její konečná podmnožina má neprázdný průnik, celá množina má neprázdný průnik (princip kompaktnosti).

Literatura

• Šablona:Citation.