Lemat Tuckera

W tym przykładzie, gdzie n=2, czerwony 1-simplex ma wierzchołki, które są oznaczone tą samą liczbą z przeciwnymi znakami. Lemat Tuckera mówi, że dla takiej triangulacji musi istnieć co najmniej jeden taki 1-simplex.

W matematyce lemat Tuckera jest kombinatorycznym odpowiednikiem twierdzenia Borsuka-Ulama , nazwanego na cześć Alberta W. Tuckera .

Niech T będzie triangulacją zamkniętej n -wymiarowej kuli ${\ displaystyle B_ {n}}$ . Załóżmy, że T jest antypodalnie symetryczny na sferze granicznej ${\ Displaystyle S_ {n-1}}$ . $Displaystyle S_$ to, że podzbiór uproszczeń $n-1}}$ które są w , zapewnia triangulację gdzie jeśli σ jest simpleksem, to także −σ. Niech ${\ Displaystyle L: V (T) \ do \ {+ 1, -1, + 2, -2, ..., + n, - n \}} być$ etykietą wierzchołków T, która jest nieparzystą funkcją na ${\ Displaystyle S_ {n-1}}$$= - L (v)}$ ) dla każdego wierzchołka ${\ Displaystyle v \ w S_ {n-1} }$ . Następnie lemat Tuckera stwierdza, że ​​T zawiera krawędź komplementarną - krawędź (1-simplex), której wierzchołki są oznaczone tą samą liczbą, ale o przeciwnych znakach.

Dowody

Pierwsze dowody były niekonstruktywne, na zasadzie sprzeczności.

Później znaleziono konstruktywne dowody, które dostarczyły również algorytmów znajdowania krawędzi dopełniającej. Zasadniczo algorytmy są oparte na ścieżce: rozpoczynają się w pewnym punkcie lub na krawędzi triangulacji, a następnie przechodzą od simplex do simplex zgodnie z ustalonymi regułami, aż nie można kontynuować. Można udowodnić, że ścieżka musi kończyć się simpleksem, który zawiera krawędź dopełniającą.

Łatwiejszy dowód lematu Tuckera wykorzystuje bardziej ogólny lemat Ky Fana , który ma prosty dowód algorytmiczny.

Poniższy opis ilustruje algorytm dla ${\ displaystyle n = 2}$ . $Zauważ$ , że w tym przypadku i istnieją 4 możliwe etykiety: ${\ Displaystyle -2, -1,1,2}$ , jak rysunek w prawym górnym rogu.

Zacznij poza piłką i rozważ etykiety wierzchołków granicznych. Ponieważ etykietowanie jest nieparzystą funkcją na granicy, granica musi mieć zarówno etykiety dodatnie, jak i ujemne:

• Jeśli granica zawiera tylko lub tylko $, na$${\ displaystyle \ pm 2}$ musi znajdować się dopełniająca krawędź Zrobione.
• $_$ granica _ $_$ liczba na

Wybierz $_$ _ Istnieją trzy przypadki:

• Jesteś $_$ _ Zrobione.
• Jesteś $_$ _ Zrobione.
• $_$ simpleksie _ Przejdź przez nie i kontynuuj.

Ostatni przypadek może zabrać cię poza piłkę. $1$ jednak liczba krawędzi $+1,-2)}$ , musi istnieć nowy, nieodwiedzony $\$ krawędź na granicy. Przejdź przez nie i kontynuuj.

Ten spacer musi kończyć się wewnątrz piłki, albo w za ${\ Displaystyle (+1, -2, + 2)}$ lub w ${\ styl wyświetlania (+1,-2,-1)}$ simplex. Zrobione.

Czas działania

Czas wykonania algorytmu opisanego powyżej jest wielomianowy w rozmiarze triangulacji. Jest to uważane za złe, ponieważ triangulacje mogą być bardzo duże. Pożądane byłoby znalezienie algorytmu, który jest logarytmiczny w rozmiarze triangulacji. $Jednak$ problem znalezienia komplementarnej krawędzi jest -kompletny dla . Oznacza to, że nie ma zbyt wielu nadziei na znalezienie szybkiego algorytmu.

Równoważne wyniki

Istnieje kilka twierdzeń o punkcie stałym, które występują w trzech równoważnych wariantach: wariancie topologii algebraicznej , wariancie kombinatorycznym i wariancie obejmującym zbiór. Każdy wariant można udowodnić oddzielnie, używając zupełnie innych argumentów, ale każdy wariant można również sprowadzić do innych wariantów w swoim rzędzie. Dodatkowo każdy wynik w górnym rzędzie można wywnioskować z wyniku znajdującego się pod nim w tej samej kolumnie.

Topologia algebraiczna	Kombinatoryka	Ustaw pokrycie
Twierdzenie Brouwera o punkcie stałym	Lemat Spernera	Lemat Knastera-Kuratowskiego-Mazurkiewicza
Twierdzenie Borsuka-Ulama	Lemat Tuckera	Twierdzenie Lusternika-Schnirelmanna

Zobacz też

• Kombinatoryka topologiczna