Лемма Шпернера

Лемма Шпернера — комбинаторный аналог теоремы Брауэра о неподвижной точке, один из основных результатов топологической комбинаторики. Утверждает, что при любой Шпернеровской раскраске вершин в триангуляции n-мерного симплекса найдётся ячейка триангуляции, вершины которой покрашены во все цвета. Первый результат подобного типа был доказан Эмануэлем Шпернером^[англ.].

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

В одномерном случае лемма Шпернера может рассматриваться как дискретный аналог теоремы Больцано — Коши. Она утверждает, что если большой отрезок разбит на подотрезки и в вершинах отрезков расставлены единицы и двойки, то при условии, что в вершинах большого отрезка стоят разные значения, существует отрезок подразбиения, в вершинах которого стоят разные значения.

Двумерный случай

Этот вариант является самым распространённым. Формулируется он следующим образом:

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

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

В общем случае лемма касается триангуляции n-мерного симплекса

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

Рассмотрим его триангуляцию T, являющуюся разбиением ${\mathcal {A}}$ на меньшие n-мерные симплексы. Обозначим функцию цвета вершины как $f\colon S\rightarrow \left\{1,2,3,\dots ,n,n+1\right\}$ , где S обозначает множество вершин триангуляции T. Раскраска называется Шпернеровской, если выполнены следующие правила:

Вершины большого симплекса покрашены в разные цвета, то есть: f(A_i) = i for 1 ≤ i ≤ n+1.
Те вершины T, что лежат в одной k-мерной грани большого симплекса

A_{i_{1}}A_{i_{2}}\ldots A_{i_{k}}

покрашены в цвета образующих её вершин

f(A_{i_{1}}),f(A_{i_{2}}),\ldots ,f(A_{i_{k}}).

В случае, если раскраска оказалась Шпернеровской, существует симплекс триангуляции T, вершины которого покрашены во все цвета.

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

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

Рассмотрим граф G, построенный по триангуляции T следующим образом:

Вершинами G будут треугольники T и область за пределами большого треугольника. Две вершины соединим ребром, если соответствующие им области имеют общий отрезок, вершины которого покрашены в 1 и 2. На стороне, соединяющей две вершины большого треугольника, покрашенные в 1 и 2, есть нечётное число отрезков с вершинами 1 и 2, а значит степень вершины, соответствующей внешней области нечётна. Так как в графе должно быть чётное число вершин нечётной степени, то существует нечётное число (а значит хотя бы одна) вершин нечётной степени, соответствующих треугольникам T.

Легко проверить, что возможные степени вершин, соответствующих треугольникам, это 0, 1 или 2, и 1 соответствует треугольнику, вершины которого покрашены во все три цвета.

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