Введение
Теорема о раскрасках триангуляционных графов – теорема в экстремальной теории множеств.
the theorem in extremal set theory
В математике, лемма Спернера – это комбинаторный результат о раскрасках триангуляций, аналогичный теореме Брауэра о неподвижной точке, которая эквивалентна ей. Она утверждает, что любая раскраска Спернера (описанная ниже) триангуляции n-мерного симплекса содержит ячейку, вершины которой окрашены в разные цвета. Первоначальный результат такого рода был доказан Эммануэлем Спернером в связи с доказательствами инвариантности области. Раскраски Спернера используются для эффективного вычисления неподвижных точек и в алгоритмах поиска корней, а также применяются в алгоритмах справедливого разделения (разрезания торта). Согласно Советской математической энциклопедии (под ред. И. М. Виноградова), связанная с ней теорема 1929 года (Кнастера, Борсука и Мазуркевича) также стала известна как лемма Спернера – этот момент обсуждается в английском переводе (под ред. М. Хазевинкеля). В настоящее время она обычно известна как лемма Кнастера–Куратовского–Мазуркевича.
Одномерный корпус
В одном измерении лемму Спернера можно рассматривать как дискретную версию теоремы о промежуточных значениях. В этом случае она, по сути, утверждает, что если дискретная функция принимает только значения 0 и 1, начинается со значения 0 и заканчивается значением 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-мерной триангуляции содержится нечетное число полностью окрашенных симплексов.
The vertices of G are the members of T plus the area outside the triangle. Two vertices are connected with an edge if their corresponding areas share a common border with one endpoint colored 1 and the other colored 2. Note that on the interval AB there is an odd number of borders colored 1 2 (simply because A is colored 1, B is colored 2; and as we move along AB, there must be an odd number of color changes in order to get different colors at the beginning and at the end). Therefore, the vertex of G corresponding to the outer area has an odd degree. But it is known (the handshaking lemma) that in a finite graph there is an even number of vertices with odd degree. Therefore, the remaining graph, excluding the outer area, has an odd number of vertices with odd degree corresponding to members of T.
It can be easily seen that the only possible degree of a triangle from T is 0, 1, or 2, and that the degree 1 corresponds to a triangle colored with the three colors 1, 2, and 3. Thus we have obtained a slightly stronger conclusion, which says that in a triangulation T there is an odd number (and at least one) of full colored triangles. A multidimensional case can be proved by induction on the dimension of a simplex. We apply the same reasoning, as in the two dimensional case, to conclude that in a n dimensional triangulation there is an odd number of full colored simplices.
Комментарии
Вот более подробное изложение доказательства, представленного ранее, для читателя, не знакомого с теорией графов. На этой диаграмме пронумерованы цвета вершин примера, приведенного ранее. Малые треугольники, вершины которых имеют различные номера, заштрихованы на графе. Каждый малый треугольник становится узлом в новом графе, полученном из триангуляции. Маленькие буквы обозначают области: восемь внутри фигуры, а область i – пространство за её пределами. Как описано ранее, узлы, имеющие общий край, конечные точки которого пронумерованы 1 и 2, соединяются в полученном графе. Например, узел d имеет общий край с внешней областью i, и все его вершины имеют разные номера, поэтому он также заштрихован. Узел b не заштрихован, поскольку две вершины имеют одинаковый номер, но он соединен с внешней областью. Можно добавить новый полный пронумерованный треугольник, например, вставив узел с номером 3 в ребро между 1 и 1 узла a и соединив этот узел с другой вершиной a. Это должно привести к созданию пары новых узлов, как в случае с узлами f и g.
Вычисление простого спинера
Предположим, что существует d-мерный симплекс с длиной стороны N, и он триангулирован на симплексы длины стороны 1. Существует функция, которая, получив любую вершину триангуляции, возвращает её цвет. Гарантируется, что раскраска удовлетворяет граничному условию Спернера. Сколько раз необходимо вызвать эту функцию, чтобы найти радужный симплекс? Очевидно, можно перебрать все вершины триангуляции, число которых составляет O(Nd), что является полиномиальной функцией от N при фиксированной размерности. Но возможно ли решить эту задачу за время O(poly(log N)), то есть полиномиальное время относительно двоичного представления N? Эта проблема была впервые изучена Христосом Пападимитриу. Он ввел класс сложности PPAD, который включает в себя эту и связанные с ней задачи (например, поиск фиксированной точки Брауэра). Он доказал, что задача поиска симплекса Спернера является PPAD-полной даже для d=3. Примерно через 15 лет Чен и Дэн доказали PPAD-полноту даже для d=2. Считается, что задачи, являющиеся PPAD-трудными, не могут быть решены за время O(poly(log N)).
Подмножества этикеток
Предположим, что каждая вершина триангуляции может быть помечена несколькими цветами, так что функция раскраски для каждого подсимплекса, множество пометок на его вершинах является семейством множеств над множеством цветов [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 году. Это комбинаторный аналог леммы KKMS.
For every sub simplex, the set of labelings on its vertices is a set family over the set of colors [n + 1]. This set family can be seen as a hypergraph. If, for every vertex v on a face of the simplex, the colors in f(v) are a subset of the set of colors on the face endpoints, then there exists a sub simplex with a balanced labeling – a labeling in which the corresponding hypergraph admits a perfect fractional matching. To illustrate, here are some balanced labeling examples for 1=n = 2:
({1}, {2}, {3}) balanced by the weights (1, 1, 1). ({1,2}, {2,3}, {3,1}) balanced by the weights (1/2, 1/2, 1/2). ({1,2}, {2,3}, {1}) balanced by the weights (0, 1, 1). This was proved by Shapley in 1973. It is a combinatorial analogue of the KKMS lemma.
Политопальные варианты
Предположим, что у нас есть d-мерный политоп P с n вершинами. P триангулируется, и каждая вершина триангуляции помечена меткой из множества {1, …, n}. Каждая главная вершина i помечена меткой i. Субсимплекс называется полностью помеченным, если он d-мерный, и каждая из его d + 1 вершин имеет различную метку. Если каждая вершина в грани F политопа P помечена одной из меток, соответствующих вершинам F, то существует по крайней мере n – d полностью помеченных симплексов. Некоторые особые случаи:
1 = d = n – 1. В этом случае P является симплексом. Политопальная лемма Спернера гарантирует существование как минимум 1 полностью помеченного симплекса. То есть, она сводится к лемме Спернера. 1 = d = 2. Предположим, что двумерный многоугольник с n вершинами триангулирован и помечен метками 1, …, n таким образом, что на каждой грани между вершиной i и вершиной i + 1 (mod n) используются только метки i и i + 1. Тогда существует по крайней мере n – 2 подтреугольника, в которых используются три различные метки. Общее утверждение было сформулировано Атанасовым в 1996 году, который доказал его для случая 1 = d = 2. Доказательство общего случая впервые было дано де Лоэрой, Петерсоном и Су в 2002 году. Они приводят два доказательства: первое неконструктивно и использует понятие множеств камешков; второе конструктивно и основано на аргументах, связанных с прослеживанием путей в графах. Мюнье расширил теорему с политопов на политопальные тела, которые не обязаны быть выпуклыми или просто связными. В частности, если P является политопом, то множество его граней является политопальным телом. В каждой раскраске Спернера политопального тела с вершинами, существует по крайней мере:
полностью помеченных симплексов, таких, что любая пара этих симплексов имеет две различные раскраски. Степень – это количество ребер B(P), к которым принадлежит . Поскольку степень не меньше d, нижняя граница не меньше n – d. Но она может быть больше. Например, для циклического политопа в 4 измерениях с n вершинами, нижняя граница равна:
Мусин далее расширил теорему на d-мерные кусочно-линейные многообразия, с границей или без нее. Асада, Фрик, Пишароди, Полеви, Стонер, Цанг и Веллнер дополнительно расширили теорему на псевдо-многообразия с границей и улучшили нижнюю границу на число граней с попарно различными метками.
Кубические варианты
Предположим, что вместо симплекса, разбитого на симплексы меньшего порядка, у нас есть n-мерный куб, разбитый на меньшие n-мерные кубы. Гарольд Кун доказал следующую лемму. Предположим, что куб, для некоторого целого числа M, разбит на единичные кубы. Предположим, что каждая вершина разбиения помечена меткой из множества {1, …, n + 1}, так что для каждой вершины v: (1) если x_i = 0, то метка на v не превосходит i; (2) если x_i = 1, то метка на v не равна i. Тогда существует единичный куб, содержащий все метки {1, …, n + 1} (некоторые из них могут повторяться). Частный случай, когда n = 2, выглядит следующим образом: предположим, что квадрат разбит на подквадраты, и каждая вершина помечена меткой из множества {1, 2, 3}. Левое ребро помечено меткой 1 (то есть не более 1); нижнее ребро помечено меткой 1 или 2 (то есть не более 2); верхнее ребро помечено меткой 1 или 3 (то есть не 2); и правое ребро помечено меткой 2 или 3 (то есть не 1). Тогда существует квадрат, помеченный метками 1, 2, 3. Другой вариант, связанный с теоремой Пуанкаре — Миранды, формулируется следующим образом. Предположим, что куб разбит на единичные кубы. Предположим, что каждой вершине соответствует бинарный вектор длины n, такой что для каждой вершины v: (1) если x_i = 0, то i-я координата метки вершины v равна 0; (2) если x_i = 1, то i-я координата метки вершины v равна 1; (3) если две вершины являются соседними, то их метки различаются не более чем по одной координате. Тогда существует единичный куб, в котором все метки различны. В двух измерениях эту теорему можно сформулировать иначе: усилив эти два результата, доказав, что количество полностью помеченных кубов нечётно. Мусин распространил эти результаты на общие квадрангуляции.
Деревья и циклы
Есть аналогичная лемма о конечных и бесконечных деревьях и циклах.
Сопутствующие результаты
Мирзахани и Вондрак изучают более слабый вариант маркировки Спернера, в котором единственным требованием является то, что метка i не используется на грани, противоположной вершине i. Они называют это допустимой с точки зрения Спернера маркировкой. Они показывают, что существуют допустимые с точки зрения Спернера маркировки, в которых каждая ячейка содержит не более 4 меток. Они также доказывают оптимальную нижнюю оценку на число ячеек, которые должны содержать по крайней мере две различные метки в любой допустимой с точки зрения Спернера маркировке. Они также доказывают, что для любого допустимого с точки зрения Спернера разбиения регулярного симплекса общая площадь границы между частями минимизируется разбиением Вороного.
Приложения
Для эффективного вычисления неподвижных точек использовались раскраски Спернера. Раскраску Спернера можно построить таким образом, чтобы полностью размеченные симплексы соответствовали неподвижным точкам заданной функции. Уменьшая триангуляцию, можно показать, что предел полностью размеченных симплексов является точно неподвижной точкой. Следовательно, этот метод предоставляет способ приближенного определения неподвижных точек. Связанное применение – численное обнаружение периодических орбит и символическая динамика. Лемма Спернера также может использоваться в алгоритмах поиска корней и алгоритмах справедливого разделения; см. протоколы Симмонса — Су. Лемма Спернера является одним из ключевых элементов доказательства теоремы Монски о том, что квадрат нельзя разрезать на нечетное число треугольников равной площади. Лемма Спернера может быть использована для нахождения конкурентного равновесия в экономике обмена, хотя существуют более эффективные способы его нахождения. Через пятьдесят лет после первой публикации Спернер представил обзор развития, влияния и применений своей комбинаторной леммы.