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

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

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

Заявление

Пусть будет -мерным симплексом с n вершинами , обозначенными как . Δ н − 1 {\displaystyle \Дельта _{n-1}} ( н − 1 ) {\displaystyle (n-1)} 1 , … , н {\displaystyle 1,\ldots ,n}

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

Лемма KKM утверждает, что в каждом покрытии KKM общее пересечение всех n множеств непусто , то есть:

⋂ я = 1 н С я ≠ ∅ . {\displaystyle \bigcap _{i=1}^{n}C_{i}\neq \emptyset .}

Пример

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

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

Лемма ККМ утверждает, что множества имеют по крайней мере одну общую точку. С 1 , С 2 , С 3 {\displaystyle C_{1},C_{2},C_{3}}

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

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

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

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

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

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

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

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

Обобщения

Радужная лемма KKM (Гейл)

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

⋂ я = 1 н С я π ( я ) ≠ ∅ {\displaystyle \bigcap _{i=1}^{n}C_{i}^{\pi (i)}\neq \emptyset } .

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

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

Радужную лемму ККМ можно доказать, используя радужное обобщение леммы Шпернера . [4]

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

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

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

Соединитель симплекса — это связное множество , которое касается всех n граней симплекса.

Покрытие без разъемов — это покрытие , в котором нет разъемов. С 1 , … , С н {\displaystyle C_{1},\ldots ,C_{n}} С я {\displaystyle C_{i}}

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

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

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

Теорема ККМС

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

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

конв ⁡ ( { в я : я ∈ я } ) ⊆ ⋃ Дж. ⊆ я С Дж. {\displaystyle \operatorname {conv} (\{v_{i}:i\in I\})\subseteq \bigcup _{J\subseteq I}C_{J}} .

Любое покрытие KKM является частным случаем покрытия KKMS. В покрытии KKM n множеств, соответствующих синглтонам, непусты, в то время как остальные множества пусты. Однако существует много других покрытий KKMS.

В общем случае неверно , что общее пересечение всех множеств в покрытии KKMS непусто; это иллюстрируется частным случаем покрытия KKM, в котором большинство множеств пусты. 2 н − 1 {\displaystyle 2^{n}-1}

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

⋂ Дж. ∈ Б С Дж. ≠ ∅ {\displaystyle \bigcap _{J\in B}C_{J}\neq \emptyset }

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

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

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

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

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

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

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

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

Политопальная теорема ККМС (Комия)

Хидетоши Комия обобщил теорему KKMS с симплексов на многогранники . [9] Пусть P — любой компактный выпуклый многогранник. Пусть — множество непустых граней P. Покрытие Комия многогранника P — это семейство замкнутых множеств, такое что для каждой грани : Теорема Комия гласит, что для каждого покрытия Комия многогранника P существует сбалансированный набор , такой что пересечение множеств, индексированных по , непусто: [7] Лица ( П ) {\displaystyle {\textrm {Лица}}(P)} { С Ф : Ф ∈ Лица ( П ) } {\displaystyle \{C_{F}:F\in {\textrm {Лица}}(P)\}} Ф ∈ Лица ( П ) {\displaystyle F\in {\textrm {Лица}}(P)} Ф ⊆ ⋃ Г ⊆ Ф ,   Г ∈ Лица ( П ) С Г . F\subseteq \bigcup _{G\subseteq F,~G\in {\textrm {Лица}}(P)}C_{G}. Б ⊆ Лица ( П ) {\displaystyle B\subseteq {\textrm {Лица}}(P)} Б {\displaystyle Б}

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

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

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

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

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

Смотрите также

Ссылки

  1. ^ Кнастер, Б .; Куратовский, К. ; Мазуркевич, С. (1929), «Ein Beweis des Fixpunktsatzes für n- Dimensional Simplexe», Fundamenta Mathematicae (на немецком языке), 14 (1): 132–137 , doi : 10.4064/fm-14-1-132-137.
  2. ^ Найман, Кэтрин Л.; Су, Фрэнсис Эдвард (2013), «Эквивалент Борсука–Улама, который напрямую подразумевает лемму Шпернера», The American Mathematical Monthly , 120 (4): 346– 354, doi :10.4169/amer.math.monthly.120.04.346, JSTOR  10.4169/amer.math.monthly.120.04.346, MR  3035127
  3. ^ ab Gale, D. (1984). «Равновесие в дискретной экономике обмена с деньгами». International Journal of Game Theory . 13 : 61– 64. doi : 10.1007/BF01769865. S2CID  154888988.
  4. ^ Бапат, РБ (1989). «Конструктивное доказательство обобщения леммы Шпернера на основе перестановок». Математическое программирование . 44 ( 1– 3): 113– 120. doi :10.1007/BF01587081. S2CID  5325605.
  5. ^ Бапат, Равиндра (2009-04-03). Моделирование, вычисления и оптимизация. World Scientific. ISBN 9789814467896.
  6. ^ Шепли, Ллойд; Вохра, Раджив (1991). «О теореме Какутани о неподвижной точке, теореме KKMS и ядре сбалансированной игры». Экономическая теория . 1 : 108–116 . doi :10.1007/BF01210576. S2CID  121027709.
  7. ^ abc Ichiishi, Tatsuro (1981). «О теореме Кнастера-Куратовского-Мазуркевича-Шепли». Журнал математического анализа и приложений . 81 (2): 297– 299. doi : 10.1016/0022-247X(81)90063-9 .
  8. ^ Краса, Стефан; Яннелис, Николас К. (1994). «Элементарное доказательство теоремы Кнастера-Куратовского-Мазуркевича-Шепли». Экономическая теория . 4 (3): 467. doi :10.1007/BF01215384. S2CID  15004516.
  9. ^ ab Komiya, Hidetoshi (1994). "Простое доказательство теоремы KKMS". Economic Theory . 4 (3): 463– 466. doi :10.1007/BF01215383. S2CID  123150937.
  10. ^ Herings, P. Jean-Jacques (1997). «Чрезвычайно простое доказательство теоремы KKMS». Экономическая теория . 10 (2): 361– 367. doi :10.1007/s001990050161. S2CID  122754557.
  11. ^ Рени, Филип Дж.; Хольц Вудерс, Мирна (1998). «Расширение теоремы KKMS». Журнал математической экономики . 29 (2): 125. doi :10.1016/S0304-4068(97)00004-9.
  12. ^ Чжоу, Линь (1994). «Теорема об открытых покрытиях симплекса и основная теорема существования Скарфа через теорему Брауэра о неподвижной точке». Экономическая теория . 4 (3): 473– 477. doi :10.1007/BF01215385. ISSN  0938-2259. JSTOR  25054778. S2CID  120862302.
  13. ^ Мусин, Олег Р. (2017). «Теоремы типа ККМ с граничными условиями». Журнал теории неподвижных точек и приложений . 19 (3): 2037–2049 . arXiv : 1512.04612 . doi :10.1007/s11784-016-0388-7. S2CID  119619991.
  14. ^ Мусин, Олег Р. (2016). «Гомотопические инварианты покрытий и леммы типа ККМ». Алгебраическая и геометрическая топология . 16 (3): 1799– 1812. arXiv : 1505.07629 . doi :10.2140/agt.2016.16.1799. S2CID  119695004.
  15. ^ Фрик, Флориан; Зербиб, Шира (2019-06-01). «Цветные покрытия многогранников и пронзающие числа цветных d-интервалов». Combinatorica . 39 (3): 627– 637. arXiv : 1710.07722 . doi : 10.1007/s00493-018-3891-1. ISSN  1439-6912. S2CID  119176249.
  • Доказательство леммы KKM см. в Planet Math.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Knaster–Kuratowski–Mazurkiewicz_lemma&oldid=1174957949"