Tuckerin Lemma

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 13. helmikuuta 2021 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Tuckerin lemma on Albert W. Tuckerin mukaan nimetyn Borsuk-Ulam-lauseen kombinatorinen analogi .

Lemman olemus on seuraava:

Olkoon T suljetun n - ulotteisen pallon kolmio . Oletetaan, että T on antipodaalisesti symmetrinen pallon rajalla . Tämä tarkoittaa, että kolmioyksinkertaisten osajoukko, joka makaa, muodostaa pallon kolmion , ja jos simpleksi σ kuuluu tähän kolmioon, niin siihen kuuluu myös -σ (oikealla olevalla kuviolla ympyrän yksinkertaiset ovat kaaria, joten yllä kuvattu ehto tarkoittaa, että jokaisella kaarella on kaari, joka on symmetrinen ympyrän keskipisteen suhteen). $B_{n}$ $S_{{n-1}}$ $S_{{n-1}}$ $S_{{n-1}}$

Antaa olla merkinnät vertics kolmio T, joka täyttää pariteetti ehto , Eli kaikki vertex . Sitten Tuckerin lemmassa todetaan, että kolmio T sisältää reunan, jolla on vastakkaiset nimikkeet , eli reunan (1-simplex), jonka kärjet on merkitty samalla numerolla, mutta eri etumerkeillä [1] . ${\displaystyle L:V(T)\to \{+1,-1,+2,-2,...,+n,-n\))$ $S_{{n-1}}$ $L(-v)=-L(v)$ $v\in S_{n-1}$

Todisteet

Ensimmäinen todistus oli ei-konstruktiivinen (todistus ristiriidalla) [2] .

Myöhemmin löydettiin konstruktiivinen todistus, joka on annettu algoritmilla, joka löytää reunan vastakkaisilla nimillä [3] [4] . Algoritmit ovat pohjimmiltaan polkupohjaisia - ne alkavat jostakin kolmion pisteestä tai reunasta ja etenevät simpleksistä simpleksiin määrättyjen sääntöjen mukaisesti prosessin ollessa vielä käynnissä. Voidaan todistaa, että polun on päätyttävä simpleksiin, joka sisältää reunan, jossa on vastakkaiset etiketit.

Yksinkertainen Tuckerin lemman todistus käyttää yleisempää Ki Fanin lemmaa , jolla on yksinkertainen algoritminen todistus.

Seuraava kuvaus havainnollistaa algoritmin [5] . Huomaa, että tässä tapauksessa on levy, jossa on 4 mahdollista otsikkoa: , kuten yllä olevassa kuvassa. $n = 2$ $B_{n}$ $-2,-1,1,2$

Aloitetaan pallon ulkopuolelta ja katsotaan rajojen tarroja. Koska nimiö on pariton funktio rajalla, rajan tulee sisältää positiiviset ja negatiiviset tunnisteet:

Jos raja sisältää vain tai vain , niin rajan tulee sisältää reuna, jossa on vastakkaiset tunnisteet. Q.E.D. $\pm 1$ $\pm2$
Muussa tapauksessa reunassa on oltava reunat. Lisäksi tällaisten reunojen määrän rajalla on oltava pariton. ${\näyttötyyli (+1,-2)}$ ${\näyttötyyli (+1,-2)}$

Valitaan reuna ja käydään sen läpi. Tapauksia voi olla kolme: ${\näyttötyyli (+1,-2)}$

Osuimme simpleksiin . Q.E.D. ${\näyttötyyli (+1,-2,+2)}$
Osuimme simpleksiin . Q.E.D. ${\näyttötyyli (+1,-2,-1)}$
Olemme simplexissä toisen reunan kanssa . Kuljemme tämän reunan läpi ja jatkamme prosessia. ${\näyttötyyli (+1,-2)}$

Tämän seurauksena saatamme päätyä ympyrän ulkopuolelle. Koska rajan reunojen määrä on kuitenkin pariton, rajalla täytyy olla uusi aiemmin vierailematon reuna . Käymme sen läpi ja jatkamme prosessia. ${\näyttötyyli (+1,-2)}$ ${\näyttötyyli (+1,-2)}$

Matkan tulee päättyä ympyrän sisällä joko simpleksiin a tai simpleksiin . Q.E.D. ${\näyttötyyli (+1,-2,+2)}$ ${\näyttötyyli (+1,-2,-1)}$

Aukioloajat

Kuvatun algoritmin ajoaika on polynominen kolmion mitoissa. Tätä pidetään virheellisenä, koska kolmiomittaus voi olla hyvin suuri. Olisi kiva löytää algoritmi, joka toimii kolmion koon logaritmisessa ajassa. Vastakkaisten merkintöjen reunan löytämisen ongelma on kuitenkin PPA-kova jopa dimensiolle . Tästä seuraa, että tällaisen algoritmin löytäminen on epätodennäköistä [6] . $n = 2$

Vastaavat tulokset

On olemassa useita kiinteän pisteen lauseita, joita on kolme samanarvoista versiota: algebrallinen topologian variantti, kombinatorinen variantti ja joukon peittävä variantti. Jokainen vaihtoehto voidaan todistaa erikseen täysin eri argumenteilla, mutta jokainen vaihtoehto voidaan pelkistää toiseksi samalla rivillä olevaksi vaihtoehdoksi. Lisäksi jokainen ylimmän rivin tulos voidaan päätellä saman sarakkeen alla olevan rivin tuloksesta [7] .

Aglebrallinen topologia	Kombinatoriikka	Peitesarjat
Brouwerin kiinteän pisteen lause	Spernerin Lemma	Knaster-Kuratovsky-Mazurkiewiczin Lemma
Borsuk-Ulam lause	Tuckerin Lemma	Lyusternik-Shnirelmanin lause

Katso myös

Topologinen kombinatoriikka

Muistiinpanot

↑ Matousek, 2003 , s. 34–45.
↑ Tucker, 1946 , s. 285–309.
↑ Freund, Todd, 1981 , s. 321-325.
↑ Freund, Todd, 1980 .
↑ Meunier, 2010 , s. 46–64.
↑ Aisenberg, Bonet, Buss, 2015 .
↑ Kathryn L. Nyman, Francis Edward Su. Borsuk-Ulam-vastine, joka viittaa suoraan Spernerin lemmaan // American Mathematical Monthly . - 2013. - T. 120 , no. 4 . — S. 346–354 . doi : 10.4169 / amer.math.monthly.120.04.346 .

Kirjallisuus

Matousek Jiri. Käyttämällä Borsuk–Ulam-lausetta. — Springer-Verlag , 2003. — ISBN 3-540-00362-2 .
Albert W Tucker . Jotkut levyn ja pallon topologiset ominaisuudet // Proc. Ensimmäinen kanadalainen matematiikka. kongressi, Montreal, 1945. - Toronto: University of Toronto Press , 1946.
Robert M. Freund, Michael J. Todd. Rakentava todiste Tuckerin kombinatorisesta lemmasta // Journal of Combinatorial Theory . - 1981. - T. 30 , no. 3 . - doi : 10.1016/0097-3165(81)90027-3 .
Robert M. Freund, Michael J. Todd. Rakentava todiste Tuckerin kombinatorisesta lemmasta . – 1980.
Frederic Meunier. Spernerin ja Tuckerin lemmat . - Algoritmit ja kauniit lauseet -blogi, 2010.
James Aisenberg, Maria Luisa Bonet, Sam Buss. 2-D Tucker on PPA-valmis. – 2015.