WikiDer > Лемма Ки Фана

В математика, Лемма Кая Фана (KFL) комбинаторная лемма о разметках триангуляций. Это обобщение Лемма Такера. Это было доказано Кай Фан в 1952 г.^[1]

В этом примере, где п = 2, двумерного знакопеременного симплекса не существует (так как метки всего 1,2). Следовательно, должно существовать дополнительное ребро (отмечено красным).

Определения

KFL использует следующие концепции.

• ${ displaystyle B_ {n}}$: закрытый п-размерный мяч.
  • ${ displaystyle S_ {n-1}}$: его граница сфера.
• Т: а триангуляция из ${ displaystyle B_ {n}}$.
  • Т называется граница антиподально симметричная если подмножество симплексы из Т которые находятся в ${ displaystyle S_ {n-1}}$ обеспечивает триангуляцию ${ displaystyle S_ {n-1}}$ где если σ - симплекс, то −σ тоже.
• L: а маркировка вершин Т, который присваивает каждой вершине ненулевое целое число: ${ Displaystyle L: V (T) к mathbb {Z} setminus {0 }}$.
  • L называется граница нечетная если для каждой вершины ${ displaystyle v in S_ {n-1}}$, ${ Displaystyle L (-v) = - L (v)}$.
• Край Т называется дополнительный край из L если метки двух его конечных точек имеют одинаковый размер и противоположные знаки, например {−2, +2}.
• An п-мерный симплекс Т называется чередующийся симплекс из Т если его метки имеют разные размеры с чередующимися знаками, например {- 1, +2, −3} или {+3, −5, +7}.

Заявление

Позволять Т - гранично-антиподально-симметричная триангуляция ${ displaystyle B_ {n}}$ и L гранично-нечетная маркировкаТ.

Если L не имеет дополнительного ребра, то L имеет нечетное количество п-мерные знакопеременные симплексы.

Следствие: Лемма Такера

По определению п-мерный знакопеременный симплекс должен иметь метки с п + 1 разные размеры.

Это означает, что если маркировка L использует только п разные размеры (т.е. ${ Displaystyle L: V (T) к {+ 1, -1, + 2, -2, ldots, + n, -n }}$) не может иметь п-мерный знакопеременный симплекс.

Следовательно, согласно KFL, L должен иметь дополнительный край.

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

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

Доказательство проводится индукцией по п.

Основа ${ Displaystyle п = 1}$. В этом случае, ${ displaystyle B_ {n}}$ это интервал ${ displaystyle [-1,1]}$ а его границей является множество ${ displaystyle {- 1,1 }}$. Маркировка L гранично-нечетное, поэтому ${ Displaystyle L (-1) = - L (+1)}$. Без ограничения общности предположим, что ${ Displaystyle L (-1) = - 1}$ и ${ Displaystyle L (+1) = + 1}$. Начните с -1 и идите направо. На каком-то краю е, маркировка должна измениться с отрицательной на положительную. С L не имеет дополнительных ребер, е должен иметь отрицательную метку и положительную метку другого размера (например, -1 и +2); это означает, что е - одномерный знакопеременный симплекс. Более того, если в какой-то момент маркировка снова изменится с положительной на отрицательную, тогда это изменение приведет к созданию второго альтернативного симплекса, и по тем же соображениям, что и раньше, позже должен быть третий альтернативный симплекс. Следовательно, число чередующихся симплексов нечетное.

Следующее описание иллюстрирует этап индукции для ${ displaystyle n = 2}$. В этом случае ${ displaystyle B_ {n}}$ это диск, а его граница - окружность. Маркировка L гранично-нечетное, поэтому, в частности ${ Displaystyle L (-v) = - L (v)}$ в какой-то момент v на границе. Разделите граничный круг на два полукруга и рассматривайте каждый полукруг как интервал. По основанию индукции этот интервал должен иметь знакопеременный симплекс, например ребро с метками (+ 1, −2). Причем количество таких ребер на обоих интервалах нечетное. Используя критерий границы, на границе у нас есть нечетное количество ребер, где меньшее число положительно, а большее отрицательное, и нечетное количество ребер, где меньшее число отрицательно, а большее положительное. Мы называем первое уменьшение, последний увеличение.

Есть два вида треугольников.

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

По индукции это доказательство распространяется на любую размерность.

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