Spernerova lemma

V matematiky je lemma Sperner kvůli Emanuela Sperner je podobný kombinace z pevného bodu věta Brouwer . Lemma Sperner říká každému obarvení Sperner na triangulaci o jednostranném rozměru n obsahuje barevnou buňku všechny n + 1 barvy. První výsledek tohoto typu demonstroval Emanuel Sperner v roce 1928 ve vztahu k důkazům věty o doménové invariance . Spernerovy omalovánky byly použity pro skutečné stanovenípevné body , v algoritmech řešení rovnic , a jsou používány v postupech spravedlivého sdílení .

V dimenzi 1

V dimenzi 1 lze Spernerovo lemma považovat za diskrétní verzi věty o střední hodnotě . V zásadě tvrdí, že funkce definovaná v konečném počtu bodů, která přijímá pouze hodnoty 0 a 1, počínaje hodnotou 0 a končící 1, musí svou hodnotu změnit lichým počtem opakování. Na obrázku vpravo je to znázorněno dvěma barvami s 5 barevnými změnami shora dolů.

V dimenzi 2

Případ dimenze 2 je ten, na který odkazujeme nejčastěji. Zní takto:

Dáme si trojúhelník ABC a triangulaci T tohoto trojúhelníku. Sada S vrcholů T je zbarvena 3 barvami, takže

A, B a C jsou vybarveny barvami 1, 2 a 3.
Vrcholy na jedné straně ABC jsou zbarveny jednou ze dvou koncových barev na této straně. Například každému vrcholu na AC musí být přiřazena barva 1 nebo 3.

Pak existuje trojúhelník T , jehož vrcholy jsou zbarveny třemi barvami. Přesněji řečeno, takových trojúhelníků je lichý počet.

Obecný případ

Obecně se lemma týká simplexu dimenze n

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

Nechť T je triangulace, tj. Rozdělení do jednoduchých dimenzí n , menších a disjunktních. Dovolme být barvicí funkcí f : S → {1, 2, 3,…, n , n + 1}, kde S je množina vrcholů T , při respektování následujících pravidel barvení: ${\ mathcal {A}}$

Vrcholy velkého simplexu jsou zbarveny odlišnými barvami a přesněji f ( A i ) = i pro 1 ≤ i ≤ n + 1;
Vrcholy T umístěné na podhledu dimenze k

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

jsou vybarveny pouze barvami

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

Pak existuje lichý počet jednoduchých T , jejichž vrcholy jsou obarveny n + 1 barvami; zejména je alespoň jeden.

Demonstrace

Uvažujme nejprve případ dimenze 2. Nechť G je (neorientovaný) graf sestrojený z triangulace T takto:

Vrcholy G jsou oblasti T a oblast mimo trojúhelník. Dva vrcholy jsou spojeny, pokud mají odpovídající oblasti společnou hranici, z nichž jeden je barevný 1 a druhý 2.

Na intervalu AB je lichý počet barevných segmentů 1–2 (protože A je vybarveno 1 a B je vybarveno 2, při přechodu z A do B by se měl setkat s lichým počtem barevných změn). Vrchol G odpovídající vnějšku trojúhelníku má tedy lichý stupeň. V konečném grafu je počet vrcholů lichého stupně sudý ( lemma potřesení rukou ), takže existuje lichý počet vrcholů odpovídajících trojúhelníkům T a mající lichý stupeň. Nyní můžeme snadno vidět, že jediné možné stupně těchto trojúhelníků jsou 0, 1 nebo 2 a že stupeň 1 odpovídá trojúhelníkům obarveným 3 barvami 1, 2 a 3.

Obecný případ (dimenze n ) je pak prokázán indukcí na n , použitím stejného argumentu: dva vrcholy grafu G jsou spojeny, pokud mají odpovídající oblasti společnou plochu (dimenze n - 1), jejichž vrcholy jsou jsou různé barvy.

Zobecnění

Spernerovo lemma bylo zobecněno na zbarvení trojúhelníkového mnohostoru s n vrcholy. V tomto případě existují alespoň nk plně barevných simplexů , kde k je rozměr polytopu a „plně barevné“ znamená, že každý z vrcholů simplexu má jinou barvu. Například pokud je mnohoúhelník s n vrcholy triangulován a zbarven podle Spernerova pravidla, budou existovat alespoň n - 2 trojúhelníky, jejichž tři vrcholy budou mít jiné zbarvení. Obecný výsledek předpokládal Krassimir Atanassov (en) v roce 1996, který to prokázal pro případ k = 2. Důkaz o obecném případě obdrželi de Loera, Peterson a Su v roce 2002.

Aplikace

Spernerovo zbarvení se používá k efektivnímu určení pevných bodů : spojíme danou funkci f se Spernerovým zbarvením a výběrem jemnějších a jemnějších triangulací ukážeme, že úplně zbarvené simplexy konvergují k pevnému bodu f (to je zejména jak dokážeme Brouwerovu větu o pevném bodě ). Jelikož určování plně barevného simplexu je nejen efektivní, ale jsou k dispozici i rychlé algoritmy, poskytuje tato technika pohodlnou metodu pro získání přibližných hodnot pevných bodů.

Ze stejného důvodu platí tyto omalovánky pro řešení rovnic a mohli bychom je také použít pro konstrukci postupů spravedlivého sdílení .

A konečně, Spernerovo lemma je zásadní při studiu problémů s ekvidisekcí , zejména při dokazování Monskyho věty .

Poznámky a odkazy

(fr) Tento článek je částečně nebo zcela převzat z anglického článku Wikipedie s názvem „ Spernerovo lemma “ ( viz seznam autorů ) .

Podle sovětské matematické encyklopedie (editoval Ivan Vinogradov ) byla příbuzná věta, kterou v roce 1929 získali Knaster , Borsuk a Mazurkiewicz , známá také jako Spernerovo lemma . Nyní se častěji označuje jako lemma Knaster-Kuratowski-Mazurkiewicz .
(in) KT Atanassov , „ We Sperner's Lemma “ , Stud. Sci. Matematika. Hungarica , sv. 32,1996, str. 71-74
(in) Jesus A. Od Loeraa Elisha Peterson a Francis Edward Su , „ Zevšeobecnění Lemmy Polytopala Spernera “ , JCTA , sv. 100,2002, str. 1–26 ( DOI 10.1006 / jcta.2002.3274 )
(in) Francis Edward Su , „ Lema Harmony Sperner ve Fair Division “ , Amer. Matematika. Měsíc. , sv. 106,1999, str. 930-942 ( číst online )

Podívejte se také

Související článek

Borsuk-Ulamova věta

externí odkazy

(in) Důkaz Lemmy Spernerové na webu cut-the-uzel
(en) Chcete-li rozdělit nájemné, začněte s trojúhelníkem , článek Alberta Sun, v New York Times (28.dubna 2014), úvod do Spernerova lemma příkladem kolokace.