Лемма Кай Фана

В математике — лемма Кай Фана (KFL) это комбинаторная лемма о маркировке триангуляций. Это обобщение леммы Такера . Это было доказано Кай Фаном в 1952 году.

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

Определения

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

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

Заявление

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

Если L не имеет дополнительных ребер, то L имеет нечетное число n -мерных чередующихся симплексов.

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

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

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

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

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

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

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

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

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

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

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

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