Tucker Lemma

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. február 13-án felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

A Tucker-lemma az Albert W. Tuckerről elnevezett Borsuk-Ulam-tétel kombinatorikus analógja .

A lemma lényege a következő:

Legyen T egy zárt n - dimenziós golyó háromszögelése . Tételezzük fel, hogy T antipodálisan szimmetrikus a gömb határán . Ez azt jelenti, hogy a háromszögelési egyszerűségek ezen fekvő részhalmaza a gömb háromszögletét alkotja , és ha ehhez a háromszögeléshez tartozik a σ szimplex, akkor a -σ is hozzátartozik (a jobb oldali ábrán a kör egyszerűsítései ívek, tehát a fent leírt feltétel azt jelenti, hogy minden ívhez a kör középpontjára szimmetrikus ív tartozik). $B_{n}$ $S_{{n-1}}$ $S_{{n-1}}$ $S_{{n-1}}$

Legyen a T háromszögelés azon csúcsainak címkézése, amely teljesíti a paritási feltételt -on , azaz bármely csúcsra . Ekkor Tucker-lemmája kimondja, hogy a T háromszögelés egy ellentétes címkékkel rendelkező élt tartalmaz , azaz egy (1-szimplex) élt, amelynek csúcsai ugyanazzal a számmal, de különböző előjelekkel vannak felcímkézve [1] . ${\displaystyle L:V(T)\to \{+1,-1,+2,-2,...,+n,-n\))$ $S_{{n-1}}$ $L(-v)=-L(v)$ $v\in S_{n-1}$

Bizonyíték

Az első bizonyítás nem konstruktív volt (ellentmondásos bizonyítás) [2] .

Később találtak egy konstruktív bizonyítást, amelyet egy olyan algoritmus ad meg, amely ellentétes címkékkel rendelkező élt talál [3] [4] . Az algoritmusok alapvetően útvonal-alapúak – a háromszögelés valamely pontján vagy szélén indulnak, és az előírt szabályok szerint szimplexből szimplexbe haladnak, miközben a folyamat még folyamatban van. Bizonyítható, hogy az útnak egy ellentétes címkés élt tartalmazó szimplexen kell végződnie.

A Tucker-lemmának egyszerű bizonyítása az általánosabb Ki Fan-lemmát használja , amelynek egyszerű algoritmikus bizonyítása van.

A következő leírás az [5] algoritmusát szemlélteti . Vegye figyelembe, hogy ebben az esetben egy lemez 4 lehetséges címkével: , mint a fenti ábrán. $n=2$ $B_{n}$ $-2,-1,1,2$

Kezdjük a labdán kívül, és nézzük meg a határon lévő címkéket. Mivel a címke páratlan függvény a határon, a határnak tartalmaznia kell pozitív és negatív címkéket:

Ha a határ csak vagy csak tartalmaz , akkor a határnak tartalmaznia kell egy élt, amelynek ellentétes címkéi vannak. Q.E.D. $\pm 1$ $\pm2$
Ellenkező esetben a szegélynek éleket kell tartalmaznia. Ezenkívül az ilyen élek számának a határon páratlannak kell lennie. $(+1,-2)$ $(+1,-2)$

Válasszunk ki egy élt , és menjünk végig rajta. Három eset lehet: $(+1,-2)$

Eltaláltuk a szimplexet . Q.E.D. $(+1,-2,+2)$
Eltaláltuk a szimplexet . Q.E.D. $(+1,-2,-1)$
Egy szimplexben vagyunk egy másik éllel . Átmegyünk ezen a szélen, és folytatjuk a folyamatot. $(+1,-2)$

Ennek eredményeként a körön kívülre kerülhetünk. Mivel azonban a határ éleinek száma páratlan, egy új, korábban nem látogatott élnek kell lennie a határon. Végigmegyünk rajta, és folytatjuk a folyamatot. $(+1,-2)$ $(+1,-2)$

Az utazásnak a körön belül kell végződnie az a szimplexben vagy a szimplexben . Q.E.D. $(+1,-2,+2)$ $(+1,-2,-1)$

Nyitva tartás

A leírt algoritmus futási ideje a háromszögelés dimenzióiban polinomiális. Ez érvénytelennek tekinthető, mert a háromszögelés nagyon nagy lehet. Jó lenne találni egy olyan algoritmust, amely a háromszögelés méretének logaritmikus idejében működik. Az ellentétes címkékkel rendelkező él megtalálásának problémája azonban PPA-kemény még a dimenzió esetében is . Ebből következik, hogy egy ilyen algoritmus megtalálása nem valószínű [6] . $n=2$

Egyenértékű eredmények

Számos fixpont-tétel létezik, amelyek három ekvivalens változatban kaphatók: az algebrai topológiaváltozat , a kombinatorikus változat és a halmazfedő változat. Mindegyik opció külön-külön is bizonyítható teljesen más érvekkel, de mindegyik opció leredukálható egy másik opcióra ugyanazon a sorban. Ezenkívül a felső sorban lévő minden egyes eredmény következtethető ugyanabban az oszlopban az alábbi sor eredményéből [7] .

Aglebrai topológia	Kombinatorika	Takarókészletek
Brouwer fixpont tétel	Sperner Lemmája	Knaster-Kuratovsky-Mazurkiewicz lemma
Borsuk-Ulam tétel	Tucker Lemma	Lyusternik-Shnirelman tétel

Lásd még

Topológiai kombinatorika

Jegyzetek

↑ Matousek, 2003 , p. 34–45.
↑ Tucker, 1946 , p. 285–309.
↑ Freund, Todd, 1981 , p. 321–325.
↑ Freund, Todd, 1980 .
↑ Meunier, 2010 , p. 46–64.
↑ Aisenberg, Bonet, Buss, 2015 .
↑ Kathryn L. Nyman, Francis Edward Su. A Borsuk–Ulam megfelelője, amely közvetlenül Sperner lemmáját jelenti // American Mathematical Monthly . - 2013. - T. 120 , sz. 4 . – S. 346–354 . - doi : 10.4169/amer.math.monthly.120.04.346 .

Irodalom

Matousek Jiri. A Borsuk–Ulam-tétel segítségével. — Springer-Verlag , 2003. — ISBN 3-540-00362-2 .
Albert W Tucker . A lemez és a gömb néhány topológiai tulajdonsága // Proc. Az első kanadai matematika. Kongresszus, Montreal, 1945. - Toronto: University of Toronto Press , 1946.
Robert M. Freund, Michael J. Todd. Tucker kombinatorikus lemmájának konstruktív bizonyítéka // Journal of Combinatorial Theory . - 1981. - T. 30 , sz. 3 . - doi : 10.1016/0097-3165(81)90027-3 .
Robert M. Freund, Michael J. Todd. Tucker kombinatorikus lemmájának építő bizonyítéka . – 1980.
Frederic Meunier. Sperner és Tucker lemmák . - Algoritmusok és szép tételek blog, 2010.
James Aisenberg, Maria Luisa Bonet, Sam Buss. A 2-D Tucker teljes PPA. — 2015.