Лемма Таккерса - Tuckers lemma

В этом примере, где n = 2, красный 1-симплекс имеет вершины, которые помечены одним и тем же номером с противоположными знаками. Лемма Такера утверждает, что для такой триангуляции должен существовать хотя бы один такой 1-симплекс.

В математика, Лемма Такера это комбинаторный аналог Теорема Борсука – Улама., названный в честь Альберт В. Такер.

Пусть T - триангуляция закрытых п-размерный мяч ${\displaystyle B_{n}}$. Предположим, что T антиподально симметричен на границе сфера ${\displaystyle S_{n-1}}$. Это означает, что подмножество симплексы из T, которые находятся в ${\displaystyle S_{n-1}}$ обеспечивает триангуляцию ${\displaystyle S_{n-1}}$ где если σ - симплекс, то и −σ тоже. ${\displaystyle L:V(T)\to \{+1,-1,+2,-2,...,+n,-n\}}$ - разметка вершин графа T, являющаяся нечетная функция на ${\displaystyle S_{n-1}}$, т.е. ${\displaystyle L(-v)=-L(v)}$ для каждой вершины ${\displaystyle v\in S_{n-1}}$.Тогда лемма Такера утверждает, что T содержит дополнительный край - ребро (1-симплекс), вершины которого помечены одним и тем же номером, но разными знаками.^[1]

Доказательства

Первые доказательства были неконструктивными из-за противоречия.^[2]

Позже были найдены конструктивные доказательства, которые также предоставили алгоритмы нахождения дополнительного ребра.^[3][4] По сути, алгоритмы основаны на путях: они начинаются с определенной точки или края триангуляции, затем переходят от симплекса к симплексу в соответствии с предписанными правилами, пока дальнейшая работа не становится невозможной. Можно доказать, что путь должен заканчиваться симплексом, содержащим дополнительное ребро.

В более простом доказательстве леммы Такера используется более общий Лемма Ки Фана, имеющий простое алгоритмическое доказательство.

Следующее описание иллюстрирует алгоритм для ${\displaystyle n=2}$.^[5] Обратите внимание, что в этом случае ${\displaystyle B_{n}}$ это диск, и есть 4 возможных метки: ${\displaystyle -2,-1,1,2}$, как на рисунке вверху справа.

Начните за пределами шара и рассмотрите метки граничных вершин. Поскольку маркировка является нечетной функцией на границе, граница должна иметь как положительные, так и отрицательные метки:

• Если граница содержит только ${\displaystyle \pm 1}$ или только ${\displaystyle \pm 2}$, на границе должно быть дополнительное ребро. Выполнено.
• В противном случае граница должна содержать ${\displaystyle (+1,-2)}$ края. Более того, количество ${\displaystyle (+1,-2)}$ ребра на границе должны быть нечетными.

Выберите ${\displaystyle (+1,-2)}$ край и пройти через него. Есть три случая:

• Вы сейчас в ${\displaystyle (+1,-2,+2)}$ симплекс. Выполнено.
• Вы сейчас в ${\displaystyle (+1,-2,-1)}$ симплекс. Выполнено.
• Вы в симплексе с другим ${\displaystyle (+1,-2)}$ край. Пройдите и продолжайте.

Последний случай может вывести вас за пределы шара. Однако, поскольку количество ${\displaystyle (+1,-2)}$ края на границе должны быть нечетными, должен быть новый, непосещенный ${\displaystyle (+1,-2)}$ край на границе. Пройдите и продолжайте.

Эта прогулка должна заканчиваться внутри мяча либо в ${\displaystyle (+1,-2,+2)}$ или в ${\displaystyle (+1,-2,-1)}$ симплекс. Выполнено.

Время выполнения

Время выполнения описанного выше алгоритма полиномиально от размера триангуляции. Это считается плохим, поскольку триангуляции могут быть очень большими. Было бы желательно найти алгоритм, логарифмический по размеру триангуляции. Однако проблема поиска дополнительного ребра заключается в следующем. PPA -полный даже для ${\displaystyle n=2}$ размеры. Это означает, что нет особых надежд на поиск быстрого алгоритма.^[6]

Эквивалентные результаты

Существует несколько теорем о неподвижной точке, которые представлены в трех эквивалентных вариантах: алгебраическая топология вариант, комбинаторный вариант и вариант покрытия множества. Каждый вариант можно доказать отдельно, используя совершенно разные аргументы, но каждый вариант также можно свести к другим вариантам в своем ряду. Кроме того, каждый результат в верхней строке может быть выведен из результата под ним в том же столбце.^[7]

Алгебраическая топология	Комбинаторика	Установить покрытие
Теорема Брауэра о неподвижной точке	Лемма Спернера	Лемма Кнастера – Куратовского – Мазуркевича.
Теорема Борсука – Улама.	Лемма Такера	Теорема Люстерника – Шнирельмана.

Смотрите также

• Топологическая комбинаторика

Рекомендации

1. Матушек, Иржи (2003), Использование теоремы Борсука – Улама., Springer-Verlag, стр. 34–45, ISBN  3-540-00362-2
2. Такер, Альберт В. (1946), «Некоторые топологические свойства диска и сферы», Proc. Первая канадская математика. Конгресс, Монреаль, 1945 г., Торонто: University of Toronto Press, стр. 285–309, МИСТЕР  0020254
3. Freund, Robert M .; Тодд, Майкл Дж. (1981), "Конструктивное доказательство комбинаторной леммы Такера", Журнал комбинаторной теории, Серия А, 30 (3): 321–325, Дои:10.1016/0097-3165(81)90027-3, МИСТЕР  0618536
4. Freund, Robert M .; Тодд, Майкл Дж. (1980), Конструктивное доказательство комбинаторной леммы Такера
5. Менье, Фредерик (2010), Леммы Спернера и Такера (PDF), Блог об алгоритмах и красивых теоремах, стр. 46–64., получено 25 мая 2015
6. Айзенберг, Джеймс; Бонет, Мария Луиза; Басс, Сэм (2015), 2-D Tucker завершен PPA, ECCC  TR15-163
7. Nyman, Kathryn L .; Су, Фрэнсис Эдвард (2013), «Эквивалент Борсука – Улама, из которого непосредственно следует лемма Спернера», Американский математический ежемесячный журнал, 120 (4): 346–354, Дои:10.4169 / amer.math.monthly.120.04.346, МИСТЕР  3035127