Spernerovo lemma

Spernerovo lemma je kombinatorickou analogií Brouwerovy věty o pevném bodě , jednoho z hlavních výsledků kombinatorické topologie. Tvrdí, že pro každé vybarvení Spernerova vrcholu v triangulaci n - rozměrného simplexu existuje triangulační buňka, jejíž vrcholy jsou obarveny všemi barvami. První výsledek tohoto dokázal Sperner

Jednorozměrný případ

V jednorozměrném případě lze na Spernerovo lemma pohlížet jako na diskrétní analog Bolzano–Cauchyho věty . Uvádí, že pokud je velký segment rozdělen na podsegmenty a 1s a 2s jsou umístěny ve vrcholech segmentů, pak za předpokladu, že ve vrcholech velkého segmentu jsou různé hodnoty, existuje segment segmentu pododdělení, na jehož vrcholech jsou různé hodnoty.

Dvourozměrné pouzdro

Tato možnost je nejběžnější. Je formulován následovně:

Je dán trojúhelník, jehož vrcholy jsou označeny 0, 1 a 2, a jeho triangulace. Triangulační vrcholy byly označeny stejnými hodnotami, takže jakýkoli vrchol na straně původního trojúhelníku by byl označen jedním ze štítků vrcholu na této straně. Pak nutně existuje dělicí trojúhelník označený 0, 1, 2.

Vícerozměrné pouzdro

Obecně se lemma týká triangulace n - rozměrného simplexu

{\mathcal {A}}=A_{1}A_{2}\ldots A_{{n+1}}.

Uvažujme jeho triangulaci T , což je rozdělení na menší n - rozměrné zjednodušení. Označte funkci barvy vrcholu jako , kde S označuje množinu vrcholů triangulace T . Barvení se nazývá Spernerovo zbarvení, pokud jsou splněna následující pravidla: $\mathcal{A}$ ${\displaystyle f\colon S\rightarrow \left\{1,2,3,\tečky ,n,n+1\right\))$

Vrcholy velkého simplexu jsou obarveny odlišně, to znamená: f ( A i ) = i pro 1 ≤ i ≤ n +1.
Ty vrcholy T , které leží v jedné k -rozměrné ploše velkého simplexu

A_{{i_{1}}}A_{{i_{2}}}\ldots A_{{i_{k}}}

malované v barvách vrcholů, které jej tvoří

f(A_{{i_{1}}}),f(A_{{i_{2}}}),\ldots ,f(A_{{i_{k}}}).

Pokud se ukáže, že zbarvení je Sperner, pak existuje triangulační simplex T , jehož vrcholy jsou obarveny všemi barvami.

Důkaz

Zatímco jednorozměrný případ je zřejmý, prokážeme dvourozměrný případ nejprve zobecněním tvrzení. Důkaz vícerozměrného případu se získá podobným způsobem indukcí.

Uvažujme graf G sestrojený z triangulace T takto:

Vrcholy G budou trojúhelníky T a plocha vně velkého trojúhelníku. Dva vrcholy spojíme hranou, jestliže jim odpovídající oblasti mají společnou úsečku, jejíž vrcholy jsou obarveny 1 a 2. Na straně spojující dva vrcholy velkého trojúhelníku obarvené 1 a 2 je liché číslo segmentů s vrcholy 1 a 2, což znamená , že odpovídající vnější oblasti je liché. Protože graf musí mít sudý počet vrcholů lichého stupně, existuje lichý počet (a tedy alespoň jeden) vrcholů lichého stupně odpovídající trojúhelníkům T .

Je snadné zkontrolovat, že možné stupně vrcholů odpovídajících trojúhelníkům jsou 0, 1 nebo 2 a 1 odpovídá trojúhelníku, jehož vrcholy jsou obarveny všemi třemi barvami.

V multidimenzionálním případě je třeba přesně stejným způsobem prokázat existenci lichého počtu rozdělovacích simplicí, jejichž vrcholy jsou obarveny všemi barvami.

Aplikace

Na základě Spernerova lemmatu je sestaven jeden z důkazů Brouwerovy věty o pevném bodě
Věta o rozřezání čtverce na trojúhelníky o stejné ploše

Literatura

Shashkin Yu. A. Pevné body. - Moskva: Nauka, 1989. - 80 s. — (Populární přednášky z matematiky). — ISBN 5-02-013922-X .

Viz také

Odkazy

Proof of the lemma (anglicky) , Cut-the-knot .
E. Epifanov, Pirate's share , Elementy.ru , 2014. (příklad aplikace Spernerova lemmatu)
NEBO Lemma Musina Spernera: Aplikace a zobecnění. Letní škola "Moderní matematika", 2015, Dubna.