В математике , лемма Шпернера является комбинаторным аналогом из теоремы Брауэра о неподвижной точке , которая является эквивалентной ей. [1]
Лемма состояние Шпернера , что каждые шпернеровы окраски ( как описано ниже) в триангуляции из п - мерного симплекса содержит ячейку окрашенную с полным набором цветов.
Первоначальный результат такого рода был доказан Эмануэлем Спернером в связи с доказательствами инвариантности области . Раскраски Спернера использовались для эффективного вычисления фиксированных точек и в алгоритмах поиска корня , а также в алгоритмах справедливого деления (вырезания торта). В настоящее время считается трудноразрешимой вычислительной задачей найти неподвижную точку Брауэра или, что эквивалентно, раскраску Спернера, даже на плоскости, в общем случае. Проблема заключается в том PPAD-полной , класс сложности изобретен Пападимитриу .
Согласно Советской математической энциклопедии (под ред. И. М. Виноградова ), родственная теорема 1929 г. ( Кнастера , Борсука и Мазуркевича ) также стала известна как лемма Спернера - этот момент обсуждается в английском переводе (под ред. М. Хазевинкеля). Сейчас она широко известна как лемма Кнастера – Куратовского – Мазуркевича .
Заявление
Одномерный случай
В одном измерении лемму Спернера можно рассматривать как дискретную версию теоремы о промежуточном значении . В этом случае, по сути, говорится, что если дискретная функция принимает только значения 0 и 1, начинается со значения 0 и заканчивается значением 1, то она должна переключать значения нечетное количество раз.
Двумерный корпус
Наиболее часто упоминается двумерный случай. Утверждается следующее:
Для треугольника ABC и триангуляции T треугольника множество S вершин графа T раскрашено в три цвета таким образом, что
- A, B и C имеют цвета 1, 2 и 3 соответственно.
- Каждая вершина на ребре ABC должна быть окрашена только в один из двух цветов концов этого ребра. Например, каждая вершина на AC должна иметь цвет 1 или 3.
Тогда существует треугольник из T , вершины которого раскрашены в три разных цвета. Точнее, таких треугольников должно быть нечетное количество.
Многомерный случай
В общем случае лемма относится к n -мерному симплексу
Рассмотрим триангуляцию T, которая является непересекающимся делениемна меньшие n -мерные симплексы. Обозначим красящего функцию как F : S → {1,2,3, ..., п , п + 1}, где S снова множество вершин Т . Правила раскраски таковы:
- Вершины большого симплекса раскрашены в разные цвета, т.е. f ( A i ) = i для 1 ≤ i ≤ n +1.
- Вершины T, расположенные на любой k -мерной подпространстве большого симплекса
- раскрашены только цветами
Тогда существует нечетное количество симплексов из T , вершины которых раскрашены во все n + 1 цвета. В частности, должен быть хотя бы один.
Доказательство
Сначала мы обратимся к двумерному случаю. Рассмотрим граф G, построенный из триангуляции T следующим образом:
- Вершины G - это элементы T плюс площадь вне треугольника. Две вершины соединяются ребром, если их соответствующие области имеют общую границу, причем одна конечная точка окрашена в 1, а другая - в 2.
Обратите внимание, что на интервале AB есть нечетное количество границ, окрашенных в 1-2 (просто потому, что A окрашен в 1, B окрашен в 2; и когда мы движемся по AB, должно быть нечетное количество изменений цвета, чтобы получить разные цвета в начале и в конце). Следовательно, вершина G, соответствующая внешней области, имеет нечетную степень. Но известно ( лемма о рукопожатии ), что в конечном графе есть четное число вершин нечетной степени. Таким образом, оставшийся граф, исключая внешнюю область, имеет нечетное число вершин с нечетной степенью , соответствующими членам T .
Легко видеть, что единственная возможная степень треугольника из T равна 0, 1 или 2, и что степень 1 соответствует треугольнику, раскрашенному тремя цветами 1, 2 и 3.
Таким образом, мы получили немного более сильный вывод, который говорит, что в триангуляции T существует нечетное количество (и по крайней мере один) полноцветных треугольников.
Многомерный случай доказывается индукцией по размерности симплекса. Мы применяем те же рассуждения, что и в двумерном случае, чтобы заключить, что в n- мерной триангуляции существует нечетное количество полноцветных симплексов.
Комментарий
Вот уточнение ранее приведенного доказательства для читателя, плохо знакомого с теорией графов .
На этой диаграмме нумеруются цвета вершин приведенного ранее примера. Маленькие треугольники, все вершины которых имеют разные номера, на графике заштрихованы. Каждый маленький треугольник становится узлом в новом графе, полученном в результате триангуляции. Маленькие буквы обозначают области, восемь внутри фигуры, а область i обозначает пространство за ее пределами.
Как описано ранее, те узлы, которые имеют общее ребро, конечные точки которого пронумерованы 1 и 2, соединяются в производном графе. Например, узел d имеет общее ребро с внешней областью i , а все его вершины имеют разные номера, поэтому он также закрашен. Узел b не закрашен, потому что две вершины имеют одинаковые номера, но он присоединен к внешней области.
Можно добавить новый треугольник с полным номером, скажем, вставив узел с номером 3 на ребро между 1 и 1 узла a и соединив этот узел с другой вершиной a . Для этого потребуется создать пару новых узлов, как в случае с узлами f и g .
Обобщения
Подмножества этикеток
Предположим, что каждая вершина триангуляции может быть помечена несколькими цветами, так что функция окраски будет f : S → 2 [n + 1] .
Для каждого суб-симплекса набор разметки на его вершинах является набором-семейством над набором цветов [ n +1]. Это семейство множеств можно рассматривать как гиперграф .
Если для каждой вершины v на грани симплекса цвета в f ( v ) являются подмножеством набора цветов на концах грани, то существует под-симплекс со сбалансированной разметкой - разметка, в которой соответствующий гиперграф допускает полное дробное сопоставление . Чтобы проиллюстрировать это, вот несколько примеров сбалансированной разметки для n = 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 .
Многогранники
Предположим, что вместо -мерный симплекс, имеем -мерный многогранник с вершины.
Тогда есть как минимум полностью маркированные симплексы, где «полностью маркированный» означает, что каждая метка на симплексе имеет свой цвет. Например, если (двумерный) многоугольник с n вершинами триангулирован и раскрашен в соответствии с критерием Спернера, то имеется не менее полностью помеченные треугольники.
Общее утверждение было выдвинуто Атанасовым в 1996 году, который доказал его на примере дела.. [3] Доказательство общего случая было впервые дано де Лоэрой, Петерсоном и Су в 2002 г. [4]
Вариант радуги
Предположим, что вместо единственной разметки у нас есть разные маркировки Спернера.
Мы рассматриваем пары (симплекс, перестановка) такие, что метка каждой вершины симплекса выбирается из разных разметок (так что для каждого симплекса есть разные пары).
Тогда есть как минимум полностью помеченные пары. Это доказал Равиндра Бапат . [5]
Другой способ сформулировать эту лемму состоит в следующем. Предположим, естьлюди, каждый из которых производит разные разметки Спернера для одной и той же триангуляции. Тогда существует симплекс и соответствие людей его вершинам, так что каждая вершина помечена своим владельцем по-разному (один человек маркирует свою вершину цифрой 1, другой человек маркирует ее вершину цифрой 2 и т. Д.). Более того, есть как минимумтакие совпадения. Это можно использовать, чтобы найти нарезанный торт без зависти с соединенными кусочками.
Множественные надписи
Предположим, что вместо единственной разметки у нас есть разные маркировки Спернера. Тогда: [6] : Теорема 2.1
- Для любых положительных целых чисел чья сумма существует беби-симплекс, на котором для каждого , номер маркировки использует по крайней мере (снаружи ) различные метки. Более того, каждая метка используется как минимум одним (из) маркировка.
- Для любых положительных целых чисел чья сумма существует беби-симплекс, на котором для каждого , этикетка используется по крайней мере (снаружи ) разные маркировки.
Обе версии сводятся к лемме Спернера, когда , или когда все маркировка идентична.
См. Аналогичные обобщения в [7] .
Градусы
Последовательность | Степень |
---|---|
123 | 1 (один переключатель 1-2 и нет переключателя 2-1) |
12321 | 0 (один переключатель 1-2 минус один переключатель 2-1) |
1232 | 0 (как указано выше; последовательность отзыва циклическая) |
1231231 | 2 (два переключателя 1-2 и нет переключателя 2-1) |
Предположим, что треугольник триангулирован и помечен {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]
Алгебраическая топология | Комбинаторика | Установить покрытие |
---|---|---|
Теорема Брауэра о неподвижной точке | Лемма Спернера | Лемма Кнастера – Куратовского – Мазуркевича. |
Теорема Борсука – Улама. | Лемма Такера | Теорема Люстерника – Шнирельмана. |
Смотрите также
- Топологическая комбинаторика
Рекомендации
- ^ Флегг, Х. Грэм (1974). От геометрии к топологии . Лондон: Издательство английского университета. С. 84–89. ISBN 0-340-05324-0.
- ^ Шепли, Л.С. (1973-01-01), Ху, ТС; Робинсон, Стивен М. (ред.), «О сбалансированных играх без дополнительных выплат» , « Математическое программирование» , Academic Press, стр. 261–290, ISBN 978-0-12-358350-5, дата обращения 29.06.2020
- ^ Атанасов, К.Т. (1996), "О лемме Спернера", Studia Scientiarum Mathematicarum Hungarica , 32 (1–2): 71–74, MR 1405126
- ^ Де Лоэра, Хесус А .; Петерсон, Елисей; Су, Фрэнсис Эдвард (2002), "А polytopal обобщение леммы Шпернера" , Журнал комбинаторной теории , серия А, 100 (1): 1-26, DOI : 10,1006 / jcta.2002.3274 , MR 1932067
- ^ Бапат, РБ (1989). «Конструктивное доказательство основанного на перестановках обобщения леммы Спернера». Математическое программирование . 44 (1–3): 113–120. DOI : 10.1007 / BF01587081 . S2CID 5325605 .
- ^ Менье, Фредерик; Су, Фрэнсис Эдвард (2018-01-06). «Многозначные версии лемм и приложений Спернера и Фана». arXiv : 1801.02044 [ math.CO ].
- ^ Асада, Мегуми; Фрик, Флориан; Пишароды, Вивек; Полевы, Максвелл; Стоунер, Дэвид; Цанг, Лин Хей; Веллнер, Зои (2018). "SIAM (Общество промышленной и прикладной математики)". Журнал СИАМ по дискретной математике . 32 : 591–610. arXiv : 1701.04955 . DOI : 10.1137 / 17m1116210 . S2CID 43932757 .
- ^ Олег Р Мусин (2014). «Вокруг леммы Спернера». arXiv : 1405.7513 [ math.CO ].
- ^ Нидермайер, Эндрю; Риццоло, Дуглас; Су, Фрэнсис Эдвард (2014), «Лемма Спернера о дереве», Барг, Александр; Мусин, Олег Р. (ред.), Дискретная геометрия и алгебраическая комбинаторика , Современная математика, 625 , Провиденс, Род-Айленд: Американское математическое общество, стр. 77–92, arXiv : 0909.0339 , doi : 10.1090 / conm / 625/12492 , ISBN 9781470409050, Руководство по ремонту 3289406 , S2CID 115157240
- ^ Kuhn, HW (1960), "Некоторые комбинаторные Леммы в топологии", IBM Журнал исследований и разработок , 4 (5): 518-524, DOI : 10,1147 / rd.45.0518
- ^ Михаэль Мюгер (2016), Топология для работающего математика (PDF) , черновик
- ^ Айгнер, Мартин ; Циглера, Гюнтер М. (2010), "Один квадратные и нечетное число треугольников", Доказательства из книги (4 - й изд.), Берлин:. Springer-Verlag, стр 131-138, DOI : 10.1007 / 978-3- 642-00856-6_20 , ISBN 978-3-642-00855-9
- ^ Шарф, Герберт (1967). «Суть игры N человек». Econometrica . 35 (1): 50–69. DOI : 10.2307 / 1909383 . JSTOR 1909383 .
- ^ Спернер, Эмануэль (1980), «Пятьдесят лет дальнейшего развития комбинаторной леммы», Численное решение сильно нелинейных задач (Симп. Алгоритмы с фиксированной точкой и проблемы дополнительности, Саутгемптонский университет, Саутгемптон, 1979) , Северная Голландия, Амстердам - Нью-Йорк, стр. 183–197, 199–217, MR 0559121
- ^ Nyman, Kathryn L .; Су, Фрэнсис Эдвард (2013), «Эквивалент Борсука – Улама, который непосредственно следует из леммы Спернера», American Mathematical Monthly , 120 (4): 346–354, doi : 10.4169 / amer.math.monthly.120.04.346 , MR 3035127
Внешние ссылки
- Доказательство леммы Шпернера в вырезе на-узле
- Лемма Спернера и игра треугольников на n-богатом сайте.
- Лемма Спернера в 2D , веб-игра на itch.io.