Лемма Такера

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

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

Сущность леммы заключается в следующем:

Пусть T — триангуляция замкнутого n-мерного шара $\text{[math]}$ $\text{[math]}$ $B_{n}$ $B_{n}$ . Предположим, что T антиподально симметрична на границе сферы $\text{[math]}$ $\text{[math]}$ $S_{n-1}$ $S_{{n-1}}$ . Это означает, что подмножество симплексов триангуляции, лежащих на $\text{[math]}$ $\text{[math]}$ $S_{n-1}$ $S_{{n-1}}$ , образуют триангуляцию сферы $\text{[math]}$ $\text{[math]}$ $S_{n-1}$ $S_{{n-1}}$ , при этом если симплекс σ принадлежит этой триангуляции, то ей принадлежит и -σ (для рисунка справа симплексы на окружности — это дуги, так что описанное выше условие означает, что для каждой дуги имеется симметричная относительно центра окружности дуга).

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

ДоказательстваПравить

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

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

Простое доказательство леммы Такера использует более общую лемму Ки Фана^[en], которая имеет простое алгоритмическое доказательство.

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

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

Если граница содержит только $\text{[math]}$ $\text{[math]}$ $\pm 1$ или только $\text{[math]}$ $\text{[math]}$ $\pm 2$ , то на границе должно находиться ребро с противоположными метками. Что и требовалось доказать.
В противном случае граница должна содержать $\text{[math]}$ $\text{[math]}$ $(+1,-2)$ рёбра. Более того, число таких рёбер $\text{[math]}$ $\text{[math]}$ $(+1,-2)$ на границе должно быть нечётным.

Выберем ребро $\text{[math]}$ $\text{[math]}$ $(+1,-2)$ и пройдём через него. Может быть три случая:

Мы попали в симплекс $\text{[math]}$ $\text{[math]}$ $(+1,-2,+2)$ . Что и требовалось доказать.
Мы попали в симплекс $\text{[math]}$ $\text{[math]}$ $(+1,-2,-1)$ . Что и требовалось доказать.
Мы попали в симплекс с другим ребром $\text{[math]}$ $\text{[math]}$ $(+1,-2)$ . Проходим через это ребро и продолжаем процесс.

Мы в результате можем оказаться вне круга. Однако, поскольку число рёбер $\text{[math]}$ $\text{[math]}$ $(+1,-2)$ на границе нечётно, должно быть новое не посещённое ранее ребро $\text{[math]}$ $\text{[math]}$ $(+1,-2)$ на границе. Проходим через него и продолжаем процесс.

Путешествие должно завершиться внутри круга либо в симплексе a $\text{[math]}$ $\text{[math]}$ $(+1,-2,+2)$ , либо в симплексе $\text{[math]}$ $\text{[math]}$ $(+1,-2,-1)$ . Что и требовалось доказать.

Время работыПравить

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

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

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

Аглебраическая топология	Комбинаторика	Накрытие множеств
Теорема Брауэра о неподвижной точке	Лемма Шпернера	Лемма Кнастера — Куратовского — Мазуркевича^[en]
Теорема Борсука — Улама	Лемма Такера	Теорема Люстерника — Шнирельмана^[en]

См. такжеПравить

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

ПримечанияПравить

↑ Matoušek, 2003, с. 34–45.
↑ Tucker, 1946, с. 285–309.
↑ Freund, Todd, 1981, с. 321–325.
↑ Freund, Todd, 1980.
↑ Meunier, 2010, с. 46–64.
↑ Aisenberg, Bonet, Buss, 2015.
↑ Kathryn L. Nyman, Francis Edward Su. A Borsuk–Ulam equivalent that directly implies Sperner's lemma // American Mathematical Monthly. — 2013. — Т. 120, вып. 4. — С. 346–354. — doi:10.4169/amer.math.monthly.120.04.346.

ЛитератураПравить

Matoušek Jiří. Using the Borsuk–Ulam Theorem. — Springer-Verlag, 2003. — ISBN 3-540-00362-2.
Albert W. Tucker. Some topological properties of disk and sphere // Proc. First Canadian Math. Congress, Montreal, 1945. — Toronto: University of Toronto Press, 1946.
Robert M. Freund, Michael J. Todd. A constructive proof of Tucker's combinatorial lemma // Journal of Combinatorial Theory. — 1981. — Т. 30, вып. 3. — doi:10.1016/0097-3165(81)90027-3.
Robert M. Freund, Michael J. Todd. A constructive proof of Tucker's combinatorial lemma. — 1980.
Frédéric Meunier. Sperner and Tucker lemmas. — Algorithms and Pretty Theorems Blog, 2010.
James Aisenberg, Maria Luisa Bonet, Sam Buss. 2-D Tucker is PPA complete. — 2015.

[_0d01042b6c2ceb7d-1] Matoušek, 2003, с. 34–45.

[_40b1220e8193789b-2] Tucker, 1946, с. 285–309.

[_2ae1edf8a69c2996-3] Freund, Todd, 1981, с. 321–325.

[_c02839c26247c3be-4] Freund, Todd, 1980.

[_fb56c239c20429f6-5] Meunier, 2010, с. 46–64.

[_ce94b2d452469f96-6] Aisenberg, Bonet, Buss, 2015.

[7] Kathryn L. Nyman, Francis Edward Su. A Borsuk–Ulam equivalent that directly implies Sperner's lemma // American Mathematical Monthly. — 2013. — Т. 120, вып. 4. — С. 346–354. — doi:10.4169/amer.math.monthly.120.04.346.

[1]

[2]

[3]

[4]

[5]

[6]

[7]