Перейти к содержанию

Лемма Такера

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Время работы

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

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

Шаблон:Аналоги теорем о фиксированной точке

См. также

Примечания

Литература