Lema lui Tucker

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 13 februarie 2021; verificarea necesită 1 editare .

Lema lui Tucker  este un analog combinatoriu al teoremei Borsuk-Ulam , numită după Albert W. Tucker .

Esența lemei este următoarea:

Fie T o triangulație a unei bile n - dimensionale închise . Să presupunem că T este simetric antipodal la limita sferei . Aceasta înseamnă că submulțimea simplexelor de triangulație care se află pe formează o triangulație a sferei , iar dacă simplexul σ aparține acestei triangulații, atunci îi aparține și -σ (pentru figura din dreapta, simplexele de pe cerc sunt arce, deci conditia descrisa mai sus inseamna ca pentru fiecare arc are un arc simetric fata de centrul cercului).

Fie etichetarea vârfurilor triangulației T care satisface condiția de paritate pe , adică pentru orice vârf . Atunci lema lui Tucker afirmă că triangulația T conține o muchie cu etichete opuse , adică o muchie (1-simplex) ale cărei vârfuri sunt etichetate cu același număr, dar cu semne diferite [1] .

Dovezi

Prima demonstrație a fost neconstructivă (dovada prin contradicție) [2] .

Ulterior, s-a găsit o dovadă constructivă, care este dată de un algoritm care găsește o muchie cu etichete opuse [3] [4] . În esență, algoritmii sunt bazați pe cale - ei încep la un punct sau la marginea triangulației și merg de la simplex la simplex conform regulilor prescrise în timp ce procesul este încă în desfășurare. Se poate dovedi că calea trebuie să se termine pe un simplex care conține o margine cu etichete opuse.

O demonstrație simplă a lemei lui Tucker folosește lema mai generală a lui Ki Fan , care are o demonstrație algoritmică simplă.

Următoarea descriere ilustrează algoritmul pentru [5] . Rețineți că în acest caz este un disc cu 4 etichete posibile: , ca în figura de mai sus.

Să începem din afara mingii și să ne uităm la etichetele de pe graniță. Deoarece eticheta este o funcție ciudată pe graniță, granița trebuie să conțină etichete pozitive și negative:

Să selectăm o margine și să o parcurgem. Pot exista trei cazuri:

Ca rezultat, putem ajunge în afara cercului. Cu toate acestea, deoarece numărul de muchii de pe graniță este impar, trebuie să existe o nouă muchie nevizitată anterior pe graniță. Trecem prin asta și continuăm procesul.

Călătoria trebuie să se termine în interiorul cercului fie în simplex a fie în simplex . Q.E.D.

Orele de deschidere

Timpul de rulare al algoritmului descris este polinom în dimensiunile triunghiulării. Acest lucru este considerat invalid deoarece triunghiularea poate fi foarte mare. Ar fi bine să găsim un algoritm care să funcționeze în timpul logaritmic al mărimii triunghiulării. Cu toate acestea, problema găsirii unei margini cu etichete opuse este PPA-hard chiar și pentru dimensiune . Rezultă că găsirea unui astfel de algoritm este puțin probabilă [6] .

Rezultate echivalente

Există mai multe teoreme de punct fix care vin în trei versiuni echivalente: varianta topologiei algebrice , varianta combinatorie și varianta de acoperire a mulțimii. Fiecare opțiune poate fi demonstrată separat folosind argumente complet diferite, dar fiecare opțiune poate fi redusă la o altă opțiune pe aceeași linie. În plus, fiecare rezultat din rândul de sus poate fi dedus din rezultatul din rândul de mai jos în aceeași coloană [7] .

Topologie aglebrică Combinatorică Seturi de acoperire
Teorema punctului fix Brouwer Lema lui Sperner Lema lui Knaster-Kuratovsky-Mazurkiewicz
Teorema Borsuk-Ulam Lema lui Tucker Teorema Lyusternik-Shnirelman

Vezi și

Note

  1. ↑ Matousek, 2003 , p. 34–45.
  2. ↑ Tucker, 1946 , p. 285–309.
  3. ↑ Freund, Todd, 1981 , p. 321–325.
  4. ↑ Freund, Todd, 1980 .
  5. ↑ Meunier, 2010 , p. 46–64.
  6. ↑ Aisenberg, Bonet, Buss, 2015 .
  7. ↑ Kathryn L. Nyman, Francis Edward Su. Un echivalent Borsuk–Ulam care implică direct lema lui Sperner // American Mathematical Monthly . - 2013. - T. 120 , nr. 4 . — S. 346–354 . - doi : 10.4169/amer.math.monthly.120.04.346 .

Literatură