Кнастера-Kuratowski-Мазуркевич лемма является основным результатом в математической теории с фиксированной точкой , опубликованной в 1929 году Кнастера , Куратовским и Мазуркевич . [1]
Лемма KKM может быть доказана с помощью леммы Спернера и может использоваться для доказательства теоремы Брауэра о неподвижной точке .
Заявление
Позволять быть -мерный симплекс с n вершинами, помеченными как.
КОЕ покрытие определяются как набориз замкнутых множеств , что для любого, То выпуклая оболочка вершин , соответствующихбудет покрыт путем.
Лемма KKM гласит, что в любом покрытии KKM общее пересечение всех n множеств непусто , т.е.
Пример
Когда , лемма ККМ рассматривает симплекс который представляет собой треугольник, вершины которого можно обозначить цифрами 1, 2 и 3. Нам даны три замкнутых множества такой, что:
- покрывает вершину 1, покрывает вершину 2, покрывает вершину 3.
- Ребро 12 (от вершины 1 до вершины 2) покрыто множествами а также , ребро 23 покрыто множествами а также , край 31 покрывается множествами а также .
- Объединение всех трех наборов покрывает весь треугольник
Лемма ККМ утверждает, что множества имеют хотя бы одну общую черту.
Лемма проиллюстрирована рисунком справа, на котором набор # 1 - синий, набор # 2 - красный, а набор # 3 - зеленый. Требования ККМ выполнены, так как:
- Каждая вершина покрыта уникальным цветом.
- Каждое ребро покрыто двумя цветами своих двух вершин.
- Треугольник покрыт всеми тремя цветами.
Лемма ККМ утверждает, что существует точка, покрытая всеми тремя цветами одновременно; такая точка хорошо видна на картинке.
Отметим, что важно, чтобы все множества были замкнутыми, т. Е. Содержали свою границу. Если, например, красный набор не замкнут, то возможно, что центральная точка содержится только в синем и зеленом наборах, и тогда пересечение всех трех наборов может быть пустым.
Эквивалентные результаты
Существует несколько теорем о неподвижной точке, которые представлены в трех эквивалентных вариантах: вариант алгебраической топологии , комбинаторный вариант и вариант покрытия множества. Каждый вариант можно доказать отдельно, используя совершенно разные аргументы, но каждый вариант также можно свести к другим вариантам в своем ряду. Кроме того, каждый результат в верхней строке можно вывести из результата, находящегося под ним в том же столбце. [2]
Алгебраическая топология | Комбинаторика | Установить покрытие |
---|---|---|
Теорема Брауэра о неподвижной точке | Лемма Спернера | Лемма Кнастера – Куратовского – Мазуркевича. |
Теорема Борсука – Улама. | Лемма Такера | Теорема Люстерника – Шнирельмана. |
Обобщения
Лемма Радуга ККМ (Гейл)
Дэвид Гейл доказал следующее обобщение леммы KKM. [3] Предположим, что вместо одного ККМ-покрытия у нас есть n различных ККМ-покрытий:. Тогда существует перестановка покрытий с непустым пересечением, т.е.
- .
Название «радужная лемма KKM» навеяно описанием его леммы Гейлом:
"В разговорной речи этот результат таков ... если каждый из трех человек раскрасит треугольник в красный, белый и синий цвета в соответствии с правилами KKM, тогда будет точка, которая находится в красном наборе одного человека, белом наборе другой, синий из третьего ». [3]
Радужная лемма KKM может быть доказана с помощью радужного обобщения леммы Спернера . [4]
Исходная лемма KKM следует из леммы KKM о радуге простым выбором n одинаковых покрытий.
Лемма без коннекторов (Бапат)
Разъем симплекса является связным множеством , что касается всех п граней симплекса.
Разъем свободного покрытие представляет собой покрытие в котором нет содержит разъем.
Любое покрытие ККМ является бесконтактным покрытием, так как в покрытии ККМ нет даже касается всех n лиц. Однако есть покрытия без разъемов, которые не являются покрытиями KKM. Пример показан справа. Там красный набор касается всех трех граней, но он не содержит никакой соединительной линии, так как ни один его связанный компонент не касается всех трех граней.
Из теоремы Равиндры Бапата , обобщающей лемму Спернера , [5] : глава 16, стр. 257–261, следует, что лемма KKM распространяется на покрытия без коннекторов (он доказал свою теорему для).
Вариант без соединителя также имеет вариант с перестановкой, так что оба эти обобщения могут использоваться одновременно.
KKMS теорема
Теорема KKMS является обобщением леммы KKM Ллойда Шепли . Это полезно в экономике , особенно в теории кооперативных игр . [6]
В то время как покрытие KKM содержит n замкнутых множеств, покрытие KKMS содержит закрытые множества - индексируются непустыми подмножествами (эквивалентно: непустыми гранями ). Для любой, То выпуклая оболочка вершин , соответствующихдолжны быть покрыты объединением множеств, соответствующих подмножествам , это:
.
Любое покрытие KKM является частным случаем покрытия KKMS. В KKM-покрытии n множеств, соответствующих синглетонам, непусты, а остальные множества пусты. Однако есть много других покрытий KKMS.
в общем, это не верно , что общее пересечение всехмножества в покрытии KKMS непусты; это иллюстрируется частным случаем покрытия ККМ, в котором большинство множеств пусто.
Теорема KKMS гласит, что в каждом покрытии KKMS есть сбалансированный набор из , такое, что пересечение множеств, индексированных непусто : [7]
Осталось объяснить, что такое «сбалансированная коллекция». Коллекция подмножеств называется сбалансированным, если на (присвоение веса каждому ), что для каждого элемента , сумма весов всех подмножеств, содержащих равно 1. Например, предположим . Потом:
- Коллекция {{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}} сбалансирована: выберите .
В терминологии гиперграфа набор B сбалансирован относительно своего основного множества V , если и только если гиперграф с множеством вершин V и множеством ребер B допускает совершенное дробное сопоставление.
Из теоремы KKMS следует лемма KKM. [7] Предположим, что у нас есть ККМ-покрытие, для . Построить покрытие ККМС следующим образом:
- в любое время ( синглтон, содержащий только элемент ).
- иначе.
Условие ККМ на исходное покрытие следует условие ККМС на новое покрытие . Следовательно, существует сбалансированный набор такой, что соответствующие множества в новом покрытии имеют непустое пересечение. Но единственно возможный сбалансированный набор - это совокупность всех одиночек; следовательно, исходное покрытие имеет непустое пересечение.
Теорема KKMS имеет различные доказательства. [8] [9] [10]
Рени и Вудерс доказали, что сбалансированный набор также может быть выбран для партнерства . [11]
Чжоу доказал вариант теоремы KKMS, в котором покрытие состоит из открытых, а не замкнутых множеств. [12]
Многогранная теорема KKMS (Комия)
Хидетоши Комия обобщил теорему KKMS с симплексов на многогранники . [9] Пусть P - любой компактный выпуклый многогранник. Позволятьмножество непустых граней P . Komiya покрытия из P представляет собой семейство замкнутых множеств так что для каждого лица :
.
Теорема Комии гласит, что для каждого комийского покрытия P существует сбалансированный набор , такое, что пересечение множеств, индексированных непусто: [7]
Теорема Комии также обобщает определение сбалансированного набора: вместо того, чтобы требовать наличия весовой функции на такой, что сумма весов около каждой вершины P равна 1, мы начинаем с выбора любого набора точек. Коллекцияназывается сбалансированным по если только , То есть точка назначается всем многоугольник Р является выпуклой комбинацией точек , назначенных граней в коллекции B .
Теорема KKMS является частным случаем теоремы Комии, в которой многогранник а также - барицентр грани F (в частности, барицентр , в чем суть ).
Граничные условия (Мусин)
Олег Р. Мусин доказал несколько обобщений леммы KKM и теоремы KKMS с граничными условиями на покрытиях. Граничные условия связаны с гомотопией . [13] [14]
Смотрите также
- Общее обобщение теоремы KKMS и теоремы Каратеодори . [15]
Рекомендации
- ^ Knaster, Б .; Куратовски, К .; Мазуркиевич, С. (1929), "Эйн Beweis де Fixpunktsatzes für н -dimensionale Simplexe" , Fundamenta Mathematicae (на немецком языке ), 14 (1): 132-137, DOI : 10,4064 / FM-14-1-132-137.
- ^ Nyman, Kathryn L .; Су, Фрэнсис Эдвард (2013), «Эквивалент Борсука – Улама, который непосредственно следует из леммы Спернера», American Mathematical Monthly , 120 (4): 346–354, doi : 10.4169 / amer.math.monthly.120.04.346 , MR 3035127
- ^ а б Гейл, Д. (1984). «Равновесие в дискретной меновой экономике с деньгами». Международный журнал теории игр . 13 : 61–64. DOI : 10.1007 / BF01769865 .
- ^ Бапат, РБ (1989). «Конструктивное доказательство основанного на перестановках обобщения леммы Спернера». Математическое программирование . 44 (1–3): 113–120. DOI : 10.1007 / BF01587081 .
- ^ Бапат, Равиндра (3 апреля 2009 г.). Моделирование, вычисления и оптимизация . World Scientific. ISBN 9789814467896.
- ^ Шепли, Ллойд; Вохра, Раджив (1991). «О теореме Какутани о неподвижной точке, теореме KKMS и сути сбалансированной игры». Экономическая теория . 1 : 108–116. DOI : 10.1007 / BF01210576 .
- ^ а б в Итииси, Тацуро (1981). «О теореме Кнастера-Куратовского-Мазуркевича-Шепли» . Журнал математического анализа и приложений . 81 (2): 297–299. DOI : 10.1016 / 0022-247X (81) 90063-9 .
- ^ Краса, Стефан; Яннелис, Николас С. (1994). «Элементарное доказательство теоремы Кнастера-Куратовского-Мазуркевича-Шепли». Экономическая теория . 4 (3): 467. DOI : 10.1007 / BF01215384 .
- ^ а б Комия, Хидетоши (1994). «Простое доказательство теоремы KKMS». Экономическая теория . 4 (3): 463–466. DOI : 10.1007 / BF01215383 .
- ^ Херингс, П. Жан-Жак (1997). «Чрезвычайно простое доказательство теоремы KKMS». Экономическая теория . 10 (2): 361–367. DOI : 10.1007 / s001990050161 .
- ^ Рени, Филип Дж .; Хольц Вудерс, Мирна (1998). «Расширение теоремы KKMS». Журнал математической экономики . 29 (2): 125. DOI : 10.1016 / S0304-4068 (97) 00004-9 .
- ^ Чжоу, Лин (1994). "Теорема об открытых покрытиях симплекса и теорема о существовании ядра шарфа через теорему Брауэра о неподвижной точке". Экономическая теория . 4 (3): 473–477. DOI : 10.1007 / BF01215385 . ISSN 0938-2259 . JSTOR 25054778 .
- ^ Мусин, Олег Р. (2015). «Теоремы типа ККМ с граничными условиями». arXiv : 1512.04612 [ math.AT ].
- ^ Мусин, Олег Р. (2016). «Гомотопические инварианты накрытий и леммы типа ККМ». Алгебраическая и геометрическая топология . 16 (3): 1799–1812. arXiv : 1505.07629 . DOI : 10,2140 / agt.2016.16.1799 .
- ^ Фрик, Флориан; Зербиб, Шира (2019-06-01). «Цветные покрытия многогранников и проникающие числа красочных d-интервалов» . Combinatorica . 39 (3): 627–637. arXiv : 1710.07722 . DOI : 10.1007 / s00493-018-3891-1 . ISSN 1439-6912 .
Внешние ссылки
- См доказательство леммы ККМ в Planet Math .