Лемма Такера

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

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

Пусть T — триангуляция замкнутого n-мерного шара ${\displaystyle B_{n}}$. Предположим, что T антиподально симметрична на границе сферы ${\displaystyle S_{n-1}}$. Это означает, что подмножество симплексов триангуляции, лежащих на ${\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)}$ на границе. Проходим через него и продолжаем процесс.

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

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

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

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

• 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.