Лемма Кнастера – Куратовского – Мазуркевича. - Knaster–Kuratowski–Mazurkiewicz lemma

В Лемма Кнастера – Куратовского – Мазуркевича. это основной результат математической теория неподвижной точки опубликовано в 1929 г. Knaster, Куратовски и Мазуркевич.^[1]

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

Заявление

Позволять ${\displaystyle \Delta _{n-1}}$ быть ${\displaystyle (n-1)}$-размерный симплекс с п вершины помечены как ${\displaystyle 1,\ldots ,n}$.

А ККМ покрытие определяется как набор ${\displaystyle C_{1},\ldots ,C_{n}}$ из закрытые наборы такой, что для любого ${\displaystyle I\subseteq \{1,\ldots ,n\}}$, то выпуклый корпус вершин, соответствующих ${\displaystyle I}$ является покрытый к ${\displaystyle \bigcup _{i\in I}C_{i}}$.

Лемма ККМ утверждает, что ККМ-покрытие имеет непустое пересечение, то есть:

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

Пример

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

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

Лемма ККМ утверждает, что множества ${\displaystyle C_{1},C_{2},C_{3}}$ имеют хотя бы одну общую черту.

Пример покрытия, удовлетворяющего требованиям леммы ККМ

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

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

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

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

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

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

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

Обобщения

Лемма Радуга ККМ (Гейл)

Дэвид Гейл доказал следующее обобщение леммы ККМ.^[3] Предположим, что вместо одного ККМ-покрытия имеем п различные покрытия ККМ: ${\displaystyle C_{1}^{1},\ldots ,C_{n}^{1},\ldots ,C_{1}^{n},\ldots ,C_{n}^{n}}$. Тогда существует перестановка ${\displaystyle \pi }$ покрытий с непустым пересечением, т.е.

${\displaystyle \bigcap _{i=1}^{n}C_{i}^{\pi (i)}\neq \emptyset }$.

Название «радужная лемма KKM» навеяно описанием своей леммы Гейлом:

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

Лемму о радуге ККМ можно доказать с помощью радужное обобщение леммы Спернера.^[4]

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

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

Иллюстрация обобщенной леммы Бапата о ККМ

А соединитель симплекса - это подключенный набор это касается всех п грани симплекса.

А покрытие без разъемов это покрытие ${\displaystyle C_{1},\ldots ,C_{n}}$ в котором нет ${\displaystyle C_{i}}$ содержит разъем.

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

Теорема о Равиндра Бапат, обобщая Лемма Спернера,^{[5]:Глава 16, стр. 257–261} следует, что лемма ККМ распространяется на покрытия без коннекторов (он доказал свою теорему для ${\displaystyle n=3}$).

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

KKMS теорема

В KKMS теорема является обобщением леммы ККМ формулой Ллойд Шепли. Это полезно в экономика, особенно в кооперативная теория игр.^[6]

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

${\displaystyle \operatorname {conv} (\{v_{i}:i\in I\})\subseteq \bigcup _{J\subseteq I}C_{J}}$.

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

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

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

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

Из теоремы KKMS следует лемма KKM.^[7] Предположим, что у нас есть ККМ-покрытие ${\displaystyle C_{i}}$, за ${\displaystyle i=1,\ldots ,n}$. Построить покрытие ККМС ${\displaystyle C'_{J}}$ следующее:

• ${\displaystyle C'_{J}=C_{i}}$ в любое время ${\displaystyle J=\{i\}}$ (${\displaystyle J}$ синглтон, содержащий только элемент ${\displaystyle i}$).
• ${\displaystyle C'_{J}=\emptyset }$ иначе.

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

Теорема KKMS имеет различные доказательства.^[8][9][10]

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

Чжоу доказал вариант теоремы KKMS, в котором покрытие состоит из открытые наборы а не закрытые наборы.^[12]

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

Хидетоши Комия обобщил теорему KKMS с симплексов на многогранники.^[9] Позволять п - любой компактный выпуклый многогранник. Позволять ${\displaystyle {\textrm {Faces}}(P)}$ - множество непустых граней п. А Комия покрытие из п семейство замкнутых множеств ${\displaystyle \{C_{F}:F\in {\textrm {Faces}}(P)\}}$ так что для каждого лица ${\displaystyle F\in {\textrm {Faces}}(P)}$:

${\displaystyle F\subseteq \bigcup _{G\subseteq F,~G\in {\textrm {Faces}}(P)}C_{G}}$.

Теорема Комии гласит, что для каждого покрытия Комии п, Существует сбалансированная коллекция ${\displaystyle B\subseteq {\textrm {Faces}}(P)}$, такое, что пересечение множеств, индексированных ${\displaystyle B}$ непусто:^[7]

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

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

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

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

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

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

1. Кнастер, Б.; Куратовский, К.; Мазуркевич, С. (1929), "Ein Beweis des Fixpunktsatzes für п-dimensionale Simplexe ", Fundamenta Mathematicae (на немецком), 14 (1): 132–137, Дои:10.4064 / FM-14-1-132-137.
2. Nyman, Kathryn L .; Су, Фрэнсис Эдвард (2013), «Эквивалент Борсука – Улама, из которого непосредственно следует лемма Спернера», Американский математический ежемесячный журнал, 120 (4): 346–354, Дои:10.4169 / amer.math.monthly.120.04.346, МИСТЕР  3035127
3. Гейл, Д. (1984). «Равновесие в дискретной меновой экономике с деньгами». Международный журнал теории игр. 13: 61–64. Дои:10.1007 / BF01769865.
4. Бапат, Р. Б. (1989). «Конструктивное доказательство основанного на перестановках обобщения леммы Спернера». Математическое программирование. 44 (1–3): 113–120. Дои:10.1007 / BF01587081.
5. Бапат, Равиндра (3 апреля 2009 г.). Моделирование, вычисления и оптимизация. World Scientific. ISBN  9789814467896.
6. Шепли, Ллойд; Вохра, Раджив (1991). «О теореме Какутани о неподвижной точке, теореме K-K-M-S и сути сбалансированной игры». Экономическая теория. 1: 108–116. Дои:10.1007 / BF01210576.
7. Итииси, Тацуро (1981). "О теореме Кнастера-Куратовского-Мазуркевича-Шепли". Журнал математического анализа и приложений. 81 (2): 297–299. Дои:10.1016 / 0022-247X (81) 90063-9.
8. Краса, Стефан; Яннелис, Николас С. (1994). «Элементарное доказательство теоремы Кнастера-Куратовского-Мазуркевича-Шепли». Экономическая теория. 4 (3): 467. Дои:10.1007 / BF01215384.
9. Комия, Хидетоши (1994). «Простое доказательство теоремы K-K-M-S». Экономическая теория. 4 (3): 463–466. Дои:10.1007 / BF01215383.
10. Херингс, П. Жан-Жак (1997). «Чрезвычайно простое доказательство теоремы K-K-M-S». Экономическая теория. 10 (2): 361–367. Дои:10.1007 / s001990050161.
11. Рени, Филип Дж .; Хольц Вудерс, Мирна (1998). «Расширение теоремы KKMS». Журнал математической экономики. 29 (2): 125. Дои:10.1016 / S0304-4068 (97) 00004-9.
12. Чжоу, Лин (1994). «Теорема об открытых покрытиях симплекса и теорема существования ядра шарфа через теорему Брауэра о неподвижной точке». Экономическая теория. 4 (3): 473–477. Дои:10.1007 / BF01215385. ISSN  0938-2259. JSTOR  25054778.
13. Мусин, Олег Р. (2015). «Теоремы типа ККМ с граничными условиями». arXiv:1512.04612 [math.AT ].
14. Мусин, Олег Р. (2016). «Гомотопические инварианты накрытий и леммы типа ККМ». Алгебраическая и геометрическая топология. 16 (3): 1799–1812. arXiv:1505.07629. Дои:10.2140 / agt.2016.16.1799.

внешняя ссылка

• См. Доказательство леммы ККМ в Планета Математика.