El lema Knaster-Kuratowski-Mazurkiewicz es un resultado básico en la teoría matemática del punto fijo publicada en 1929 por Knaster , Kuratowski y Mazurkiewicz . [1]
El lema KKM se puede demostrar a partir del lema de Sperner y se puede utilizar para demostrar el teorema del punto fijo de Brouwer .
Declaración
Dejar frijol -dimensional simplex con n vértices etiquetados como.
Un revestimiento KKM se define como un conjuntode conjuntos cerrados de tal manera que para cualquier, el casco convexo de los vértices correspondientes aestá cubierto por.
El lema de KKM dice que en cada cobertura de KKM, la intersección común de todos los n conjuntos no está vacía , es decir:
Ejemplo
Cuándo , el lema KKM considera el simplex que es un triángulo, cuyos vértices se pueden etiquetar como 1, 2 y 3. Se nos dan tres conjuntos cerrados tal que:
- cubre el vértice 1, cubre el vértice 2, cubre el vértice 3.
- El borde 12 (del vértice 1 al vértice 2) está cubierto por los conjuntos y , el borde 23 está cubierto por los conjuntos y , el borde 31 está cubierto por los conjuntos y .
- La unión de los tres conjuntos cubre todo el triángulo.
El lema KKM establece que los conjuntos tienen al menos un punto en común.
El lema está ilustrado por la imagen de la derecha, en la que el conjunto n. ° 1 es azul, el conjunto n. ° 2 es rojo y el conjunto n. ° 3 es verde. Se cumplen los requisitos de KKM, ya que:
- Cada vértice está cubierto por un color único.
- Cada borde está cubierto por los dos colores de sus dos vértices.
- El triángulo está cubierto por los tres colores.
El lema KKM establece que hay un punto cubierto por los tres colores simultáneamente; tal punto es claramente visible en la imagen.
Tenga en cuenta que es importante que todos los conjuntos estén cerrados, es decir, que contengan su límite. Si, por ejemplo, el conjunto rojo no está cerrado, entonces es posible que el punto central esté contenido solo en los conjuntos azul y verde, y entonces la intersección de los tres conjuntos puede estar vacía.
Resultados equivalentes
Hay varios teoremas de punto fijo que vienen en tres variantes equivalentes: una variante de topología algebraica , una variante combinatoria y una variante de cobertura de conjuntos. Cada variante se puede probar por separado utilizando argumentos totalmente diferentes, pero cada variante también se puede reducir a las otras variantes en su fila. Además, cada resultado en la fila superior se puede deducir del que está debajo en la misma columna. [2]
Topología algebraica | Combinatoria | Establecer cobertura |
---|---|---|
Teorema del punto fijo de Brouwer | Lema de Sperner | Lema de Knaster – Kuratowski – Mazurkiewicz |
Teorema de Borsuk-Ulam | Lema de Tucker | Teorema de Lusternik-Schnirelmann |
Generalizaciones
Lema arco iris KKM (vendaval)
David Gale demostró la siguiente generalización del lema KKM. [3] Supongamos que, en lugar de un revestimiento KKM, tenemos n revestimientos KKM diferentes:. Entonces, existe una permutación de los revestimientos con una intersección no vacía, es decir:
- .
El nombre "lema KKM arcoíris" está inspirado en la descripción de Gale de su lema:
"Una afirmación coloquial de este resultado es ... si cada una de las tres personas pinta un triángulo rojo, blanco y azul de acuerdo con las reglas de KKM, entonces habrá un punto que estará en el conjunto rojo de una persona, el conjunto blanco de otro, el azul del tercero ". [3]
El lema arco iris KKM se puede probar utilizando una generalización arcoíris del lema de Sperner . [4]
El lema KKM original se deriva del lema KKM del arco iris simplemente eligiendo n revestimientos idénticos.
Lema sin conector (Bapat)
Un conector de un simplex es un conjunto conectado que toca todas las n caras del símplex.
Una cubierta sin conector es una cubierta. en el que no contiene un conector.
Cualquier revestimiento KKM es un revestimiento sin conectores, ya que en un revestimiento KKM, no incluso toca las n caras. Sin embargo, existen revestimientos sin conectores que no son revestimientos KKM. Un ejemplo se ilustra a la derecha. Allí, el conjunto rojo toca las tres caras, pero no contiene ningún conector, ya que ningún componente conectado toca las tres caras.
Un teorema de Ravindra Bapat , generalizando el lema de Sperner , [5] : capítulo 16, págs. 257-261 implica que el lema KKM se extiende a revestimientos sin conectores (demostró su teorema para).
La variante sin conector también tiene una variante de permutación, de modo que ambas generalizaciones se pueden usar simultáneamente.
Teorema de KKMS
El teorema KKMS es una generalización del lema KKM por Lloyd Shapley . Es útil en economía , especialmente en teoría de juegos cooperativos . [6]
Mientras que una cubierta KKM contiene n conjuntos cerrados, una cubierta KKMS contiene conjuntos cerrados - indexados por los subconjuntos no vacíos de (equivalentemente: por caras no vacías de ). Para cualquier, el casco convexo de los vértices correspondientes adebe estar cubierto por la unión de conjuntos correspondientes a subconjuntos de , es decir:
.
Cualquier revestimiento KKM es un caso especial de revestimiento KKMS. En una cobertura KKM, los n conjuntos correspondientes a singletons no están vacíos, mientras que los otros conjuntos están vacíos. Sin embargo, existen muchos otros revestimientos KKMS.
en general, es no cierto que la intersección común de todoslos juegos en KKMS que cubren no están vacíos; esto se ilustra con el caso especial de una cubierta KKM, en la que la mayoría de los juegos están vacíos.
El teorema de KKMS dice que, en cada cobertura de KKMS, hay una colección equilibrada de , tal que la intersección de conjuntos indexados por no está vacío : [7]
Queda por explicar qué es una "colección equilibrada". Una colección de subconjuntos de se llama equilibrado si hay una función de ponderación en (asignando un peso a cada ), de modo que, para cada elemento , la suma de los pesos de todos los subconjuntos que contienen es exactamente 1. Por ejemplo, suponga . Luego:
- La colección {{1}, {2}, {3}} está equilibrada: elija que todos los pesos sean 1. Lo mismo ocurre con cualquier colección en la que cada elemento aparezca exactamente una vez, como la colección {{1,2} , {3}} o la colección {{1,2,3}}.
- La colección {{1,2}, {2,3}, {3,1}} está equilibrada: elija que todos los pesos sean 1/2. Lo mismo es cierto para cualquier colección en la que cada elemento aparezca exactamente dos veces.
- La colección {{1,2}, {2,3}} no está equilibrada, ya que para cualquier elección de pesos positivos, la suma del elemento 2 será mayor que la suma del elemento 1 o 3, por lo que no es posible que todas las sumas son iguales a 1.
- La colección {{1,2}, {2,3}, {1}} está equilibrada: elija .
En terminología hipergráfica , una colección B está equilibrada con respecto a su conjunto básico V , si el hipergráfico con conjunto de vértices V y conjunto de bordes B admite una coincidencia fraccionaria perfecta.
El teorema KKMS implica el lema KKM. [7] Supongamos que tenemos una cobertura de KKM, por . Construya una cubierta KKMS como sigue:
- cuando sea ( es un singleton que contiene solo un elemento ).
- de lo contrario.
La condición KKM en la cubierta original. implica la condición KKMS en la nueva cubierta . Por lo tanto, existe una colección equilibrada de tal manera que los conjuntos correspondientes en la nueva cubierta no tienen intersección vacía. Pero la única colección equilibrada posible es la colección de todos los singleton; por lo tanto, la cubierta original tiene una intersección no vacía.
El teorema de KKMS tiene varias pruebas. [8] [9] [10]
Reny y Wooders demostraron que el conjunto equilibrado también se puede elegir para asociarse . [11]
Zhou demostró una variante del teorema de KKMS donde la cobertura consiste en conjuntos abiertos en lugar de conjuntos cerrados. [12]
Teorema politopal KKMS (Komiya)
Hidetoshi Komiya generalizó el teorema de KKMS de simples a politopos . [9] Sea P cualquier politopo convexo compacto. Dejarser el conjunto de caras no vacío de P . Una cubierta de Komiya de P es una familia de conjuntos cerrados. tal que para cada rostro :
.
El teorema de Komiya dice que por cada cobertura de Komiya de P , hay una colección equilibrada , tal que la intersección de conjuntos indexados por no está vacío: [7]
El teorema de Komiya también generaliza la definición de una colección equilibrada: en lugar de requerir que haya una función de ponderación en tal que la suma de pesos cerca de cada vértice de P es 1, comenzamos eligiendo cualquier conjunto de puntos. Una colecciónse llama equilibrado con respecto a si , Es decir, el punto asignado a la totalidad del polígono P es una combinación convexa de los puntos asignados a las caras de la colección B .
El teorema de KKMS es un caso especial del teorema de Komiya en el que el politopo y es el baricentro de la cara F (en particular, es el baricentro de , cual es el punto ).
Condiciones de contorno (Musin)
Oleg R. Musin demostró varias generalizaciones del lema KKM y el teorema KKMS, con condiciones de contorno en las cubiertas. Las condiciones de contorno están relacionadas con la homotopía . [13] [14]
Ver también
- Una generalización común del teorema KKMS y el teorema de Carathéodory . [15]
Referencias
- ^ Knaster, B .; Kuratowski, C .; Mazurkiewicz, S. (1929), "Ein Beweis des Fixpunktsatzes für n -dimensionale Simplexe" , Fundamenta Mathematicae (en alemán), 14 (1): 132-137, doi : 10.4064 / fm-14-1-132-137.
- ^ Nyman, Kathryn L .; Su, Francis Edward (2013), "Un equivalente de Borsuk-Ulam que implica directamente el lema de Sperner", American Mathematical Monthly , 120 (4): 346–354, doi : 10.4169 / amer.math.monthly.120.04.346 , MR 3035127
- ^ a b Gale, D. (1984). "Equilibrio en una economía de cambio discreto con dinero". Revista Internacional de Teoría de Juegos . 13 : 61–64. doi : 10.1007 / BF01769865 .
- ^ Bapat, RB (1989). "Una prueba constructiva de una generalización basada en permutación del lema de Sperner". Programación matemática . 44 (1-3): 113-120. doi : 10.1007 / BF01587081 .
- ^ Bapat, Ravindra (3 de abril de 2009). Modelado, Computación y Optimización . World Scientific. ISBN 9789814467896.
- ^ Shapley, Lloyd; Vohra, Rajiv (1991). "En el teorema de punto fijo de Kakutani, el teorema de KKMS y el núcleo de un juego equilibrado". Teoría económica . 1 : 108-116. doi : 10.1007 / BF01210576 .
- ^ a b c Ichiishi, Tatsuro (1981). "Sobre el teorema de Knaster-Kuratowski-Mazurkiewicz-Shapley" . Revista de Análisis y Aplicaciones Matemáticas . 81 (2): 297–299. doi : 10.1016 / 0022-247X (81) 90063-9 .
- ^ Krasa, Stefan; Yannelis, Nicholas C. (1994). "Una prueba elemental del teorema de Knaster-Kuratowski-Mazurkiewicz-Shapley". Teoría económica . 4 (3): 467. doi : 10.1007 / BF01215384 .
- ^ a b Komiya, Hidetoshi (1994). "Una simple prueba del teorema de KKMS". Teoría económica . 4 (3): 463–466. doi : 10.1007 / BF01215383 .
- ^ Herings, P. Jean-Jacques (1997). "Una prueba extremadamente simple del teorema KKMS". Teoría económica . 10 (2): 361–367. doi : 10.1007 / s001990050161 .
- ^ Reny, Philip J .; Holtz Wooders, Myrna (1998). "Una extensión del teorema KKMS". Revista de Economía Matemática . 29 (2): 125. doi : 10.1016 / S0304-4068 (97) 00004-9 .
- ^ Zhou, Lin (1994). "Un teorema sobre las cubiertas abiertas de un simplex y el teorema de la existencia del núcleo de la bufanda a través del teorema del punto fijo de Brouwer". Teoría económica . 4 (3): 473–477. doi : 10.1007 / BF01215385 . ISSN 0938-2259 . JSTOR 25054778 .
- ^ Musin, Oleg R. (2015). "Teoremas de tipo KKM con condiciones de contorno". arXiv : 1512.04612 [ math.AT ].
- ^ Musin, Oleg R. (2016). "Invariantes de homotopía de cubiertas y lemas tipo KKM". Topología algebraica y geométrica . 16 (3): 1799–1812. arXiv : 1505.07629 . doi : 10.2140 / agt.2016.16.1799 .
- ^ Frick, Florian; Zerbib, Shira (1 de junio de 2019). "Cubiertas coloridas de politopos y números penetrantes de intervalos d coloridos" . Combinatorica . 39 (3): 627–637. arXiv : 1710.07722 . doi : 10.1007 / s00493-018-3891-1 . ISSN 1439-6912 .
enlaces externos
- Vea la prueba de KKM Lemma en Planet Math .