Лемма Спернерса - Википедия - Sperners lemma

В математика, Лемма Спернера это комбинаторный аналог из Теорема Брауэра о неподвижной точке, что эквивалентно ему.^[1]

Лемма Спернера утверждает, что каждое Спернер окраска (описано ниже) триангуляция из п-размерный симплекс содержит ячейку, раскрашенную полным набором цветов.

Первоначальный результат такого рода был доказан Эмануэль Спернер, в связи с доказательствами неизменность домена. Раскраски Спернера использовались для эффективного вычисления фиксированные точки И в алгоритмы поиска корней, и применяются в справедливое деление (резка торта) алгоритмы. В настоящее время считается трудноразрешимой вычислительной задачей найти неподвижную точку Брауэра или, что то же самое, раскраску Спернера даже на плоскости в общем случае. Проблема в PPAD-полный, класс сложности, изобретенный Христос Пападимитриу.

Согласно советской Математическая энциклопедия (изд. Виноградов И. ), родственная теорема 1929 г. Knaster, Борсук и Мазуркевич ) также стали известны как Лемма Спернера - этот момент обсуждается в английском переводе (ред. М. Хазевинкель). Сейчас он широко известен как Лемма Кнастера – Куратовского – Мазуркевича..

Заявление

Одномерный случай

Пример одномерного случая

В одном измерении лемму Спернера можно рассматривать как дискретную версию теорема о промежуточном значении. В этом случае, по сути, говорится, что если дискретный функция принимает только значения 0 и 1, начинается со значения 0 и заканчивается значением 1, затем он должен переключать значения нечетное количество раз.

Двумерный корпус

Пример двумерного случая

Наиболее часто упоминается двумерный случай. Утверждается следующее:

Учитывая треугольник ABC и триангуляция Т треугольника множество S вершин Т раскрашивается тремя цветами таким образом, что

1. A, B и C имеют цвета 1, 2 и 3 соответственно.
2. Каждая вершина на ребре ABC должна быть окрашена только в один из двух цветов концов ее ребра. Например, каждая вершина на AC должна иметь цвет 1 или 3.

Тогда существует треугольник из Т, вершины которого раскрашены тремя разными цветами. Точнее, таких треугольников должно быть нечетное количество.

Многомерный случай

В общем случае лемма относится к п-размерный симплекс

${ displaystyle { mathcal {A}} = A_ {1} A_ {2} ldots A_ {n + 1}.}$

Мы рассматриваем триангуляцию Т которое является непересекающимся делением ${ displaystyle { mathcal {A}}}$ на меньшие п-мерные симплексы. Обозначим функцию окраски как ж : S → {1,2,3,...,п,п+1}, где S снова является множеством вершин Т. Правила раскраски:

1. Вершины большого симплекса раскрашены в разные цвета, т.е. е. ж(А_я) = я для 1 ≤ я ≤ п+1.
2. Вершины Т расположен на любом k-мерная подповерхность большого симплекса

${ displaystyle A_ {i_ {1}} A_ {i_ {2}} ldots A_ {i_ {k + 1}}}$

раскрашены только цветами

${ displaystyle i_ {1}, i_ {2}, ldots, i_ {k + 1}.}$

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

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

Сначала мы обратимся к двумерному случаю. Рассмотрим график грамм построенный на основе триангуляции Т следующее:

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

Обратите внимание, что на интервале AB есть нечетное количество границ, окрашенных в 1-2 (просто потому, что A окрашен в 1, B окрашен в 2; и когда мы движемся по AB, должно быть нечетное количество изменений цвета, чтобы получить разные цвета в начале и в конце). Следовательно, вершина грамм соответствующая внешней области имеет нечетную степень. Но известно ( лемма о рукопожатии ), что в конечном графе есть четное число вершин нечетной степени. Следовательно, оставшийся граф, исключая внешнюю область, имеет нечетное количество вершин с нечетной степенью, соответствующих членам Т.

Легко видеть, что единственно возможная степень треугольника из Т равно 0, 1 или 2, и что степень 1 соответствует треугольнику, раскрашенному тремя цветами 1, 2 и 3.

Таким образом, мы получили немного более сильный вывод, который говорит, что в триангуляции Т имеется нечетное количество (и хотя бы один) полноцветных треугольников.

Многомерный случай доказывается индукцией по размерности симплекса. Мы применяем те же рассуждения, что и в двумерном случае, чтобы заключить, что в п-мерной триангуляции существует нечетное количество полноцветных симплексов.

Комментарий

Простая двумерная триангуляция примерной фигуры, раскрашенная и названная в соответствии с условиями леммы Спернера

График, полученный из примера рисунка

Вот разработка доказательства, данного ранее, для читателя, плохо знакомого с теория графов.

На этой диаграмме нумеруются цвета вершин приведенного ранее примера. Маленькие треугольники, все вершины которых имеют разные номера, на графике заштрихованы. Каждый маленький треугольник становится узлом в новом графе, полученном в результате триангуляции. Маленькими буквами обозначены области, восемь внутри рисунка и площадь. я обозначает пространство за его пределами.

Как описано ранее, те узлы, которые имеют общее ребро, конечные точки которого пронумерованы 1 и 2, соединяются в производном графе. Например, узел d разделяет край с внешней областью я, и все его вершины имеют разные номера, поэтому он также закрашен. Узел б не затеняется, потому что две вершины имеют одинаковые номера, но присоединяется к внешней области.

Можно добавить новый треугольник с полным номером, скажем, вставив узел с номером 3 в край между 1 и 1 узла. а, и присоединяя этот узел к другой вершине а. Для этого потребуется создать пару новых узлов, как в случае с узлами. ж и грамм.

Обобщения

Подмножества этикеток

Предположим, что каждая вершина триангуляции может быть помечена несколькими цветами, так что функция окраски ж : S → 2^{[n + 1]}.

Для каждого суб-симплекса набор разметки на его вершинах является набором-семейством над набором цветов [п+1]. Это семейство наборов можно рассматривать как гиперграф.

Если для каждой вершины v на лицевой стороне симплекса цвета в ж(v) являются подмножеством множества цветов на концах граней, то существует под-симплекс с сбалансированная маркировка - маркировка, в которой соответствующий гиперграф допускает совершенное дробное соответствие. Вот несколько примеров сбалансированной маркировки для п=2:

• ({1}, {2}, {3}) - уравновешиваются весами (1, 1, 1).
• ({1,2}, {2,3}, {3,1}) - уравновешиваются весами (1/2, 1/2, 1/2).
• ({1,2}, {2,3}, {1}) - сбалансированы по весам (0, 1, 1).

Это было доказано Шепли в 1973 г.^[2] Это комбинаторный аналог Лемма KKMS.

Многогранники

Предположим, что вместо ${ displaystyle n-1}$-мерный симплекс, имеем ${ displaystyle d}$-размерный многогранник с ${ displaystyle n}$ вершины.

Тогда есть как минимум ${ displaystyle n-d}$ полностью маркированные симплексы, где «полностью маркированный» означает, что каждая метка на симплексе имеет свой цвет. Например, если (двумерный) многоугольник с п вершин триангулируется и раскрашивается по критерию Спернера, то имеется не менее ${ displaystyle n-2}$ полностью помеченные треугольники.

Общее утверждение было высказано Атанасов в 1996 году, который доказал это по делу ${ displaystyle d = 2}$.^[3] Доказательство общего случая впервые было дано де Лоэрой, Петерсоном и Вс в 2002.^[4]

Вариант радуги

Предположим, что вместо одной разметки у нас есть ${ displaystyle n}$ разные маркировки Sperner.

Мы рассматриваем пары (симплекс, перестановка) такие, что метка каждой вершины симплекса выбирается из разных разметок (так что для каждого симплекса есть ${ displaystyle n!}$ разные пары).

Тогда есть как минимум ${ displaystyle n!}$ полностью помеченные пары. Это было доказано Равиндра Бапат.^[5]

Другой способ сформулировать эту лемму заключается в следующем. Предположим, есть ${ displaystyle n}$ люди, каждый из которых производит разные разметки Спернера для одной и той же триангуляции. Тогда существует симплекс и соответствие людей его вершинам, так что каждая вершина помечена своим владельцем по-разному (один человек маркирует свою вершину цифрой 1, другой - 2 и т. Д.). Более того, есть как минимум ${ displaystyle n!}$ такие совпадения. Это можно использовать для поиска резка торта без зависти со связанными частями.

Множественные надписи

Предположим, что вместо одной разметки у нас есть ${ displaystyle m}$ разные маркировки Sperner. Потом:^{[6]:Thm 2.1}

1. Для любых положительных целых чисел ${ displaystyle k_ {1}, ldots, k_ {m}}$чья сумма ${ displaystyle m + n-1}$существует беби-симплекс, на котором для каждого ${ Displaystyle я в {1, ldots, м }}$, номер маркировки ${ displaystyle i}$ использует по крайней мере ${ displaystyle k_ {i}}$ (снаружи ${ displaystyle n}$) различные метки. Более того, каждая метка используется как минимум одним (из ${ displaystyle m}$) маркировка.
2. Для любых положительных целых чисел ${ Displaystyle l_ {1}, ldots, l_ {n}}$чья сумма ${ displaystyle m + n-1}$существует беби-симплекс, на котором для каждого ${ displaystyle j in {1, ldots, n }}$, наклейка ${ displaystyle j}$ используется по крайней мере ${ displaystyle l_ {j}}$ (снаружи ${ displaystyle m}$) разные маркировки.

Обе версии сводятся к лемме Спернера, когда ${ displaystyle m = 1}$, или когда все ${ displaystyle m}$ маркировка идентична.

Видеть ^[7] для подобных обобщений.

Градусы

Предположим, что треугольник триангулирован и помечен {1,2,3}. Рассмотрим циклическую последовательность меток на границе треугольника. Определить степень маркировки как разность между количеством переключателей от 1 до 2 и количеством переключателей от 2 до 1. См. примеры в таблице справа. Обратите внимание, что степень одинакова, если мы считаем переключатели от 2 до 3 минус 3 до 2 или от 3 до 1 минус 1 до 3.

Мусин доказал, что количество полностью помеченных треугольников не менее степени маркировки.^[8] В частности, если степень отлична от нуля, то существует хотя бы один полностью помеченный треугольник.

Если разметка удовлетворяет условию Спернера, то ее степень равна 1: переключатели 1-2 и 2-1 находятся только на стороне между вершинами 1 и 2, а количество переключателей 1-2 должно быть на единицу больше, чем число 2–1 переключений (при переходе от вершины 1 к вершине 2). Следовательно, первоначальная лемма Шпернера следует из теоремы Мусина.

Деревья и циклы

Есть аналогичная лемма о конечном и бесконечном деревья и циклы.^[9]

Кубическая лемма Шпернера

Вариант леммы Шпернера о кубе (вместо симплекса) доказал Гарольд В. Кун.^[10] Это связано с Теорема Пуанкаре – Миранды.^[11]

Приложения

Раскраски Спернера использовались для эффективного вычисления фиксированные точки. Раскраска Спернера может быть построена так, что полностью помеченные симплексы соответствуют неподвижным точкам данной функции. Делая триангуляцию все меньше и меньше, можно показать, что предел полностью помеченных симплексов и есть неподвижная точка. Следовательно, этот метод позволяет приблизить фиксированные точки.

По этой причине лемма Спернера также может быть использована в алгоритмы поиска корней и справедливое разделение алгоритмы; видеть Протоколы Симмонса – Су.

Лемма Спернера - одна из ключевых составляющих доказательства Теорема Монского, что квадрат нельзя разрезать на нечетное количество равновеликие треугольники.^[12]

Лемму Спернера можно использовать для нахождения конкурентное равновесие в биржевое хозяйство, хотя есть более эффективные способы его найти.^[13]:67

Спустя пятьдесят лет после первой публикации Спернер представил обзор развития, влияния и приложений своей комбинаторной леммы.^[14]

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

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

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

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

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

внешняя ссылка

• Доказательство леммы Спернера. в завязать узел
• Лемма Спернера и игра треугольников, на сайте n-rich.