Лемма Кнастера – Куратовски – Мазуркевича

редактировать

Лемма Кнастера-Куратовски-Мазуркевича является основным результатом математической теории фиксированной точки, опубликованной в 1929 году Кнастером, Куратовским и Мазуркевич.

Лемма KKM может быть доказана из леммы Спернера и может использоваться для доказательства теоремы Брауэра о неподвижной точке.

Содержание

1 Утверждение
2 Пример
3 Эквивалентные результаты
4 Обобщения
- 4.1 Лемма Rainbow KKM (Gale)
- 4.2 Лемма без коннекторов (Bapat)
- 4.3 Теорема KKMS
- 4.4 Теорема Polytopal KKMS (Комия)
- 4.5 Граничные условия (Мусин)
5 Ссылки
6 Внешние ссылки

Оператор

Пусть $Δ n - 1 {\ displaystyle \ Delta _ {n-1}}$ ${\ displaystyle \ Delta _ {n-1}}$ быть $n - 1 {\ display style n-1}$ $n-1$ -мерный симплекс с n вершинами, помеченными как $1,…, n {\ displaystyle 1, \ ldots, n}$ $1, \ ldots, n$ .

A KKM, покрывающий, определяется как набор $C 1,…, C n {\ displaystyle C_ {1}, \ ldots, C_ {n}}$ $C_ {1}, \ ldots, C_ {n}$ из замкнутых множеств такой, что для любого $I ⊆ {1,…, n} {\ displaystyle I \ substeq \ {1, \ ldots, n \}}$ ${\ displaystyle I \ substeq \ {1, \ ldots, n \}}$ выпуклая оболочка вершин, соответствующих $I {\ displaystyle I}$ $I$ , покрыто $⋃ i ∈ IC i {\ displaystyle \ bigcup _ {i \ in I } C_ {i}}$ ${\ displaystyle \ bigcup _ {i \ in I} C_ {i}}$ .

Лемма KKM гласит, что покрытие KKM имеет непустое пересечение, то есть:

⋂ i = 1 n C i ≠ ∅ {\ displaystyle \ bigcap _ {i = 1} ^ {n} C_ {i} \ neq \ emptyset}

{\ displaystyle \ bigcap _ {i = 1} ^ {n} C_ {i} \ neq \ emptyset}

Пример

Когда $n = 3 {\ displaystyle n = 3}$ $n = 3$ , Лемма ККМ рассматривает симплекс $Δ 2 {\ displaystyle \ Delta _ {2}}$ $\ Delta _ {2}$ , который представляет собой треугольник, вершины которого могут быть помечены 1, 2 и 3. Нам даны три замкнутых множества $C 1, C 2, C 3 {\ displaystyle C_ {1}, C_ {2}, C_ {3}}$ $C_ {1}, C_ {2}, C_ {3}$ такие что:

$C 1 {\ displaystyle C_ {1}}$ $C_ {1}$ покрывает вершину 1, $C 2 {\ displaystyle C_ {2}}$ $C_ {2}$ покрывает вершину 2, $C 3 {\ displaystyle C_ {3}}$ $C_ {3}$ покрывает вершину 3.
Ребро 12 (от вершины 1 до вершины 2) покрывается наборами $C 1 {\ displaystyle C_ {1}}$ $C_ {1}$ и $C 2 {\ displaystyle C_ {2}}$ $C_ {2}$ , край 23 покрывается наборами $C 2 {\ displaystyle C_ {2}}$ $C_ {2}$ и $C 3 {\ displaystyle C_ {3}}$ $C_ {3}$ , край 31 покрывается наборами $C 3 {\ displaystyle C_ {3 }}$ $C_ {3}$ и $C 1 {\ displaystyle C_ {1}}$ $C_ {1}$ .
Объединение всех трех наборов покрывает весь треугольник

Лемма KKM утверждает, что наборы $C 1, C 2, C 3 {\ displaystyle C_ {1}, C_ {2}, C_ {3}}$ $C_ {1}, C_ {2}, C_ {3}$ имеют по крайней мере одну общую точку.

Лемма проиллюстрирована рисунком справа, на котором набор # 1 - синий, набор # 2 - красный, а набор # 3 - зеленый. Требования KKM выполнены, так как:

Каждая вершина покрыта уникальным цветом.
Каждое ребро покрыто двумя цветами своих двух вершин.
Треугольник покрыт все три цвета.

Лемма ККМ утверждает, что существует точка, покрытая всеми тремя цветами одновременно; такая точка хорошо видна на картинке.

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

Эквивалентные результаты

Существует несколько теорем о фиксированной точке, которые представлены в трех эквивалентных вариантах: вариант алгебраической топологии, комбинаторный вариант и вариант покрытия множества. Каждый вариант можно доказать отдельно, используя совершенно разные аргументы, но каждый вариант также можно свести к другим вариантам в своем ряду. Кроме того, каждый результат в верхней строке может быть выведен из результата под ним в том же столбце.

Алгебраическая топология	Комбинаторика	Множество, покрывающее
теорема Брауэра о неподвижной точке	Лемма Спернера	Лемма Кнастера – Куратовского – Мазуркевича
Теорема Борсука – Улама	Лемма Такера	Теорема Люстерника – Шнирельмана

Обобщения

Радужная лемма KKM <275 (Гейл)>Дэвид Гейл доказал следующее обобщение леммы ККМ. Предположим, что вместо одного покрытия KKM у нас есть n различных покрытий KKM: $C 1 1,…, C n 1,…, C 1 n,…, C nn {\ displaystyle C_ {1} ^ {1}, \ ldots, C_ {n} ^ {1}, \ ldots, C_ {1} ^ {n}, \ ldots, C_ {n} ^ {n}}$ ${\ displaystyle C_ {1} ^ {1}, \ ldots, C_ {n} ^ {1}, \ ldots, C_ {1 } ^ {n}, \ ldots, C_ {n} ^ {n}}$ . Тогда существует перестановка $π {\ displaystyle \ pi}$ $\ pi$ покрытий с непустым пересечением, то есть:
$⋂ i = 1 n C i π (i) ≠ ∅ {\ displaystyle \ bigcap _ {i = 1} ^ {n} C_ {i} ^ {\ pi (i)} \ neq \ emptyset}$ ${\ displaystyle \ bigcap _ {i = 1} ^ {n} C_ {i} ^ {\ pi (i)} \ neq \ emptyset}$ .
Название «радужная лемма KKM» вдохновлено описанием его леммы Гейлом :

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

Радужная лемма KKM может быть доказана с помощью радужного обобщения леммы Спернера.

Исходная лемма KKM следует из леммы о радужной KKM простым выбором n одинаковые покрытия.

Лемма без коннекторов (Bapat)

A коннектор симплекса - это связное множество, которое касается всех n граней симплекса.

A покрытие без соединителей - это покрытие $C 1,…, C n {\ displaystyle C_ {1}, \ ldots, C_ {n}}$ $C_ {1}, \ ldots, C_ {n}$ , в котором нет $C i {\ displaystyle C_ {i}}$ $C_ {i}$ содержит соединитель.

Любое покрытие KKM является покрытием без соединителей, поскольку в покрытии KKM никакое $C i {\ displaystyle C_ {i}}$ $C_ {i}$ даже не касается всех n граней. Однако есть покрытия без разъемов, которые не являются покрытиями KKM. Пример показан справа. Там красный набор касается всех трех граней, но он не содержит никакой соединительной линии, так как ни один связанный компонент не касается всех трех граней.

Теорема Равиндры Бапата, обобщающая лемму Спернера, влечет, что лемма KKM распространяется на покрытия без коннекторов (он доказал свою теорему для $n = 3 {\ displaystyle n = 3}$ $n = 3$ ).

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

Теорема KKMS

Теорема KKMS является обобщением леммы KKM, сформулированной Ллойдом Шепли. Это полезно в экономике, особенно в теории кооперативных игр.

. В то время как покрытие KKM содержит n замкнутых множеств, покрытие KKMS содержит $2 n - 1 { \ displaystyle 2 ^ {n} -1}$ $2 ^ {n} -1$ закрытые множества - индексируются непустыми подмножествами $[n] {\ displaystyle [n]}$ $[n]$ (эквивалентно: непустыми гранями из $Δ n - 1 {\ displaystyle \ Delta _ {n-1}}$ ${\ displaystyle \ Delta _ {n-1}}$ ). Для любого $I ⊆ [n] {\ displaystyle I \ substeq [n]}$ ${\ displaystyle I \ substeq [n]}$ выпуклая оболочка вершин, соответствующих $I {\ displaystyle I}$ $I$ должен быть покрыт объединением наборов, соответствующих подмножествам $I {\ displaystyle I}$ $I$ , то есть:

$conv ⁡ ({ vi: я ∈ I}) ⊆ ⋃ J ⊆ ICJ {\ displaystyle \ operatorname {conv} (\ {v_ {i}: i \ in I \}) \ substeq \ bigcup _ {J \ substeq I} C_ {J} }$ ${\ displaystyle \ operatorname {conv} (\ {v_ {i}: i \ in I \}) \ substeq \ bigcup _ {J \ substeq I} C_ {J}}$ .

Теорема KKMS гласит, что для любого покрытия KKMS существует сбалансированный набор $B {\ displaystyle B}$ $B$ из $2 [n] {\ displaystyle 2 ^ {[n ]}}$ ${\ displaystyle 2 ^ {[n]}}$ , так что пересечение множеств, проиндексированных $B {\ displaystyle B}$ $B$ , непусто:

⋂ J ∈ BCJ ≠ ∅ {\ displaystyle \ bigcap _ {J \ in B} C_ {J} \ neq \ emptyset}

{\ displaystyle \ bigcap _ {J \ in B} C_ {J} \ neq \ emptyset}

Осталось объяснить, что такое «сбалансированная коллекция». Коллекция $B {\ displaystyle B}$ $B$ подмножеств $[n] {\ displaystyle [n]}$ $[n]$ называется сбалансированной, если на $B {\ displaystyle B}$ $B$ (присвоение веса $w J ≥ 0 {\ displaystyle w_ {J} \ geq 0}$ ${\ displaystyle w_ {J} \ geq 0}$ каждому $J ∈ B {\ displaystyle J \ in B}$ ${\ displaystyle J \ in B}$ ), так что для каждого элемента $i ∈ [n] {\ displaystyle i \ in [n]}$ ${\ displaystyle i \ in [n]}$ сумма веса всех подмножеств, содержащих $i {\ displaystyle i}$ $i$ , равны точно 1. Например, предположим, $n = 3 {\ displaystyle n = 3}$ $n = 3$ . Затем:

Коллекция {{1}, {2}, {3}} сбалансирована: выберите все веса равными 1. То же самое верно для любой коллекции, в которой каждый элемент появляется ровно один раз, например коллекции { {1,2}, {3}} или коллекция {{1,2,3}}.
Коллекция {{1,2}, {2,3}, {3,1}} сбалансирован: выберите все веса равными 1/2. То же самое верно для любой коллекции, в которой каждый элемент встречается ровно дважды.
Коллекция {{1,2}, {2,3}} не сбалансирована, поскольку для любого выбора положительных весов сумма для элемента 2 будет больше, чем сумма для элемента 1 или 3, поэтому невозможно, чтобы все суммы были равны 1.
Коллекция {{1,2}, {2,3}, {1} } сбалансировано: выберите $w 1, 2 = 0, w 2, 3 = 1, w 1 = 1 {\ displaystyle w_ {1,2} = 0, w_ {2,3} = 1, w_ {1 } = 1}$ ${\ displaystyle w_ {1,2} = 0, w_ {2,3} = 1, w_ {1} = 1}$ .

В терминологии гиперграфа набор B сбалансирован относительно своего основного набора V, если и только если гиперграф с набором вершин V и набором ребер B допускает совершенное дробное сопоставление.

Из теоремы KKMS следует лемма KKM. Предположим, у нас есть KKM, покрывающий $C i {\ displaystyle C_ {i}}$ $C_ {i}$ , для $i = 1,…, n {\ displaystyle i = 1, \ ldots, n}$ $i = 1, \ ldots, n$ . Постройте KKMS, покрывающую $CJ ′ {\ displaystyle C '_ {J}}$ $C'_{J}$ следующим образом:

$CJ ′ = C i {\ displaystyle C' _ {J} = C_ {i} }$ $C'_{J}=C_{i}$ всякий раз, когда $J = {i} {\ displaystyle J = \ {i \}}$ ${\ displaystyle J = \ {i \}}$ ( $J {\ displaystyle J}$ $J$ является одноэлементным, содержащим только элемент $i {\ displaystyle i}$ $i$ ).
$CJ ′ = ∅ {\ displaystyle C '_ {J} = \ emptyset}$ $C'_{J}=\emptyset$ в противном случае.

Условие KKM для исходного покрытия $C i {\ displaystyle C_ {i}}$ $C_ {i}$ подразумевает условие KKMS для нового покрытия $CJ ′ {\ displaystyle C '_ {J}}$ $C'_{J}$ . Следовательно, существует сбалансированный набор такой, что соответствующие множества в новом покрытии имеют непустое пересечение. Но единственно возможный сбалансированный набор - это сбор всех одиночных экземпляров; следовательно, исходное покрытие имеет непустое пересечение.

Теорема KKMS имеет различные доказательства.

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

Чжоу доказал вариант теоремы KKMS, где покрытие состоит из открытых множеств, а не замкнутых множеств.

Многогранная теорема KKMS (Комия)

обобщила теорему KKMS с симплексов на многогранники. Пусть P - произвольный компактный выпуклый многогранник. Пусть $Faces (P) {\ displaystyle {\ textrm {Faces}} (P)}$ ${\ displaystyle {\ textrm {Fac es}} (P)}$ будет набором непустых граней P. A Комия, покрывающая P, является семейство замкнутых множеств ${CF: F ∈ Faces (P)} {\ displaystyle \ {C_ {F}: F \ in {\ textrm {Faces}} (P) \}}$ ${\ displaystyle \ {C_ {F}: F \ in {\ textrm {Faces}} (P) \}}$ такие что для каждого лица $F ∈ Faces (P) {\ displaystyle F \ in {\ textrm {Faces}} (P)}$ ${\ displaystyle F \ in {\ textrm {Faces}} (P)}$ :

$F ⊆ ⋃ G ⊆ F, G ∈ Faces (P) CG {\ displaystyle F \ substeq \ bigcup _ {G \ substeq F, ~ G \ in {\ textrm {Faces}} (P)} C_ {G}}$ ${\ displaystyle F \ substeq \ bigcup _ {G \ substeq F, ~ G \ in {\ textrm {Faces}} (P)} C_ {G}}$ .

Теорема Комии гласит, что для любого покрытия Комия P существует сбалансированное коллекция $B ⊆ Faces (P) {\ displaystyle B \ substeq {\ textrm {Faces}} (P)}$ ${\ displaystyle B \ substeq {\ textrm {Faces}} (P)}$ , так что пересечение наборов, проиндексированных $B {\ displaystyle B }$ $B$ непусто:

⋂ F ∈ BCF ≠ ∅ {\ displaystyle \ bigcap _ {F \ in B} C_ {F} \ neq \ emptyset}

{\ displaystyle \ bigcap _ {F \ in B} C_ {F} \ neq \ emptyset}

Теорема Комии также обобщает определение сбалансированная коллекция: вместо требования наличия весовой функции на $B {\ displaystyle B}$ $B$ такой, что сумма весов s возле каждой вершины P равно 1, мы начинаем с выбора любого набора точек $b = {b F: F ∈ Faces (P), b F ∈ F} {\ displaystyle {\ textbf {b}} = \ {b ^ {F}: F \ in {\ textrm {Faces}} (P), b ^ {F} \ in F \}}$ ${\ displaystyle {\ textbf {b}} = \ {b ^ {F}: F \ in {\ textrm {Faces}} (P), b ^ {F} \ in F \}}$ . Коллекция $B ⊆ Faces (P) {\ displaystyle B \ substeq {\ textrm {Faces}} (P)}$ ${\ displaystyle B \ substeq {\ textrm {Faces}} (P)}$ называется сбалансированной по отношению к $b {\ displaystyle {\ textbf {b}}}$ ${\ textbf {b}}$ , если $b P ∈ conv ⁡ {b F: F ∈ B} {\ displaystyle b ^ {P} \ in \ operatorname {conv} \ {b ^ {F} : F \ in B \}}$ ${\ displaystyle b ^ {P} \ in \ operatorname {conv} \ {b ^ {F}: F \ in B \}}$ , то есть точка, назначенная всему многоугольнику P, представляет собой выпуклую комбинацию точек, назначенных граням в наборе B.

Теорема KKMS является частным случаем теоремы Комии, в которой многогранник $P = Δ n - 1 {\ displaystyle P = \ Delta _ {n-1}}$ ${\ displaystyle P = \ Delta _ {n-1}}$ и $b F {\ displaystyle b ^ {F}}$ ${\ displaystyle b ^ {F}}$ - барицентр грани F (в частности, $b P {\ displaystyle b ^ {P}}$ ${\ displaystyle b ^ {P}}$ - центр масс $Δ n - 1 {\ displaystyle \ Delta _ {n-1}}$ ${\ displaystyle \ Delta _ {n-1}}$ , который является точкой $(1 / n,…, 1 / n) {\ displaystyle (1 / n, \ ldots, 1 / n)}$ ${\ displaystyle (1 / n, \ ldots, 1 / n)}$ ).

Граничные условия (Мусин)

Олег Р. Мусин доказал несколько обобщений леммы KKM и теоремы KKMS с граничными условиями на покрытиях. Граничные условия связаны с гомотопией.

Ссылки

Внешние ссылки

См. Доказательство леммы KKM в Planet Math.