Lema de Knaster-Kuratowski-Mazurkiewicz

El lema de Knaster-Kuratowski-Mazurkiewicz es un resultado básico de la teoría matemática del punto fijo publicado 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 de punto fijo de Brouwer .

Declaración

Sea un símplex -dimensional con n vértices etiquetados como . ${\displaystyle \Delta _{n-1}}$ ${\displaystyle (n-1)}$ ${\displaystyle 1,\ldots ,n}$

Una cubierta KKM se define como un conjunto de conjuntos cerrados tales que para cualquier , la envoltura convexa de los vértices correspondientes a está cubierta por . ${\displaystyle C_{1},\ldots ,C_{n}}$ ${\displaystyle I\subseteq \{1,\ldots ,n\}}$ ${\displaystyle I}$ ${\displaystyle \bigcup _{i\in I}C_{i}}$

El lema KKM dice que en cada cobertura KKM, la intersección común de todos los n conjuntos no está vacía , es decir:

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

Ejemplo

Cuando , el lema KKM considera el símplex que es un triángulo, cuyos vértices pueden etiquetarse como 1, 2 y 3. Se nos dan tres conjuntos cerrados tales que: ${\displaystyle n=3}$ ${\displaystyle \Delta _{2}}$ ${\displaystyle C_{1},C_{2},C_{3}}$

• ${\displaystyle C_{1}}$cubre el vértice 1, cubre el vértice 2, cubre el vértice 3. ${\displaystyle C_{2}}$ ${\displaystyle C_{3}}$
• La arista 12 (del vértice 1 al vértice 2) está cubierta por los conjuntos y , la arista 23 está cubierta por los conjuntos y , la arista 31 está cubierta por los conjuntos y . ${\displaystyle C_{1}}$ ${\displaystyle C_{2}}$ ${\displaystyle C_{2}}$ ${\displaystyle C_{3}}$ ${\displaystyle C_{3}}$ ${\displaystyle C_{1}}$
• 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. ${\displaystyle C_{1},C_{2},C_{3}}$

Un ejemplo de una cubierta que satisface los requisitos del lema KKM

El lema se ilustra en la imagen de la derecha, en la que el conjunto n.° 1 es azul, el n.° 2 es rojo y el n.° 3 es verde. Se cumplen los requisitos de KKM, ya que:

• Cada vértice está cubierto por un color único.
• Cada arista está cubierta 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; dicho punto es claramente visible en la imagen.

Es importante tener en cuenta que todos los conjuntos son cerrados, es decir, que contienen su límite. Si, por ejemplo, el conjunto rojo no es cerrado, entonces es posible que el punto central esté contenido únicamente en los conjuntos azul y verde, y entonces la intersección de los tres conjuntos puede estar vacía.

Resultados equivalentes

Existen varios teoremas de punto fijo que se presentan en tres variantes equivalentes: una variante de topología algebraica , una variante combinatoria y una variante de recubrimiento de conjuntos. Cada variante se puede demostrar por separado utilizando argumentos totalmente diferentes, pero cada variante también se puede reducir a las otras variantes de su fila. Además, cada resultado de la fila superior se puede deducir del que se encuentra debajo en la misma columna. ^[2]

Generalizaciones

Lema KKM del arco iris (Gale)

David Gale demostró la siguiente generalización del lema KKM. ^[3] Supongamos que, en lugar de una cobertura KKM, tenemos n coberturas KKM diferentes: . Entonces, existe una permutación de las coberturas con una intersección no vacía, es decir: ${\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 }$.

El nombre "lema arco iris KKM" está inspirado en la descripción que Gale hace de su lema:

"Una expresión coloquial de este resultado es... si cada una de tres personas pinta un triángulo de rojo, blanco y azul según las reglas del KKM, entonces habrá un punto que estará en el conjunto rojo de una persona, en el conjunto blanco de otra y en el azul de la tercera". ^[3]

El lema KKM arco iris se puede demostrar utilizando una generalización arco iris del lema de Sperner . ^[4]

El lema KKM original se deriva del lema KKM del arco iris simplemente eligiendo n recubrimientos idénticos.

Lema sin conector (Bapat)

Una ilustración del lema KKM generalizado de Bapat

Un conector de un símplex es un conjunto conexo que toca todas las n caras del símplex.

Una cubierta sin conector es una cubierta que no contiene ningún conector. ${\displaystyle C_{1},\ldots ,C_{n}}$ ${\displaystyle C_{i}}$

Cualquier recubrimiento KKM es un recubrimiento sin conector, ya que en un recubrimiento KKM, ningún componente conectado toca las n caras. Sin embargo, hay recubrimientos sin conector que no son recubrimientos KKM. A la derecha se muestra un ejemplo. Allí, el conjunto rojo toca las tres caras, pero no contiene ningún conector, ya que ningún componente conectado toca las tres caras. ${\displaystyle C_{i}}$

Un teorema de Ravindra Bapat , que generaliza el lema de Sperner , ^{[5] : capítulo 16, págs. 257-261,} implica que el lema KKM se extiende a recubrimientos sin conectores (demostró su teorema para ). ${\displaystyle n=3}$

La variante sin conector también tiene una variante de permutación, de modo que ambas generalizaciones se pueden utilizar simultáneamente.

Teorema KKMS

El teorema KKMS es una generalización del lema KKM de Lloyd Shapley . Es útil en economía , especialmente en la 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 las caras no vacías de ). Para cualquier , la envoltura convexa de los vértices correspondientes a debe estar cubierta por la unión de los conjuntos correspondientes a los subconjuntos de , es decir: ${\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}}$.

Cualquier recubrimiento KKM es un caso especial de recubrimiento KKMS. En un recubrimiento 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 recubrimientos KKMS.

En general, no es cierto que la intersección común de todos los conjuntos en una cubierta KKMS no esté vacía; esto se ilustra con el caso especial de una cubierta KKM, en el que la mayoría de los conjuntos están vacíos. ${\displaystyle 2^{n}-1}$

El teorema KKMS dice que, en cada cobertura KKMS, hay una colección equilibrada de , tal que la intersección de conjuntos indexados por no está vacía ${\displaystyle B}$ ${\displaystyle 2^{[n]}}$ ${\displaystyle B}$ : ^[7]

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

Queda por explicar qué es una "colección balanceada". Una colección de subconjuntos de se llama balanceada si existe una función de peso en (que asigna un peso a cada ), tal que, para cada elemento , la suma de los pesos de todos los subconjuntos que contienen es exactamente 1. Por ejemplo, supongamos . Entonces: ${\displaystyle B}$ ${\displaystyle [n]}$ ${\displaystyle B}$ ${\displaystyle w_{J}\geq 0}$ ${\displaystyle J\in B}$ ${\displaystyle i\in [n]}$ ${\displaystyle i}$ ${\displaystyle n=3}$

• La colección {{1}, {2}, {3}} está equilibrada: elija que todos los pesos sean 1. Lo mismo se aplica a 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 se aplica a 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 sean iguales a 1.
• La colección {{1,2}, {2,3}, {1}} está equilibrada: elija . ${\displaystyle w_{1,2}=0,w_{2,3}=1,w_{1}=1}$

En la terminología de hipergrafos , una colección B está equilibrada con respecto a su conjunto base V , solo si el hipergrafo con conjunto de vértices V y conjunto de aristas B admite una correspondencia fraccionaria perfecta.

El teorema KKMS implica el lema KKM. ^[7] Supongamos que tenemos una cobertura KKM , para . Construya una cobertura KKMS de la siguiente manera: ${\displaystyle C_{i}}$ ${\displaystyle i=1,\ldots ,n}$ ${\displaystyle C'_{J}}$

• ${\displaystyle C'_{J}=C_{i}}$siempre que ( sea un singleton que contiene solo el elemento ). ${\displaystyle J=\{i\}}$ ${\displaystyle J}$ ${\displaystyle i}$
• ${\displaystyle C'_{J}=\emptyset }$de lo contrario.

La condición KKM en la cobertura original implica la condición KKMS en la nueva cobertura . Por lo tanto, existe una colección equilibrada tal que los conjuntos correspondientes en la nueva cobertura tienen una intersección no vacía. Pero la única colección equilibrada posible es la colección de todos los singletons; por lo tanto, la cobertura original tiene una intersección no vacía. ${\displaystyle C_{i}}$ ${\displaystyle C'_{J}}$

El teorema KKMS tiene varias demostraciones. ^{[8] [9] [10]}

Reny y Wooders demostraron que el conjunto equilibrado también puede elegirse para formar pareja . ^[11]

Zhou demostró una variante del teorema KKMS donde la cobertura consiste en conjuntos abiertos en lugar de conjuntos cerrados. ^[12]

Teorema politópico KKMS (Komiya)

Hidetoshi Komiya generalizó el teorema KKMS de los símplices a los politopos . ^[9] Sea P cualquier politopo compacto convexo. Sea el conjunto de caras no vacías de P. Una cubierta de Komiya de P es una familia de conjuntos cerrados tales que para cada cara : El teorema de Komiya dice que para cada cubierta de Komiya de P , existe una colección balanceada , tal que la intersección de los conjuntos indexados por no está vacía: ^[7] ${\displaystyle {\textrm {Faces}}(P)}$ ${\displaystyle \{C_{F}:F\in {\textrm {Faces}}(P)\}}$ ${\displaystyle F\in {\textrm {Faces}}(P)}$ $F\subseteq \bigcup _{G\subseteq F,~G\in {\textrm {Faces}}(P)}C_{G}.$ ${\displaystyle B\subseteq {\textrm {Faces}}(P)}$ ${\displaystyle B}$

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

El teorema de Komiya también generaliza la definición de una colección equilibrada: en lugar de exigir que exista una función de peso en tal que la suma de pesos cerca de cada vértice de P sea 1, empezamos eligiendo cualquier conjunto de puntos . Una colección se denomina equilibrada con respecto a sólamente , es decir, el punto asignado a todo el polígono P es una combinación convexa de los puntos asignados a las caras de la colección B . ${\displaystyle B}$ ${\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\}}$

El teorema 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 , que es el punto ). ${\displaystyle P=\Delta _{n-1}}$ ${\displaystyle b^{F}}$ ${\displaystyle b^{P}}$ ${\displaystyle \Delta _{n-1}}$ ${\displaystyle (1/n,\ldots ,1/n)}$

Condiciones de contorno (Musin)

Oleg R. Musin demostró varias generalizaciones del lema KKM y del teorema KKMS, con condiciones de contorno sobre los recubrimientos. Las condiciones de contorno están relacionadas con la homotopía . ^{[13] [14]}

Véase también

• Una generalización común del teorema KKMS y el teorema de Carathéodory . ^[15]

Referencias

1. 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.
2. Nyman, Kathryn L.; Su, Francis Edward (2013), "Un equivalente de Borsuk-Ulam que implica directamente el lema de Sperner", 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. Gale, D. (1984). "Equilibrio en una economía de intercambio discreto con dinero". Revista internacional de teoría de juegos . 13 : 61–64. doi :10.1007/BF01769865. S2CID  154888988.
4. Bapat, RB (1989). "Una prueba constructiva de una generalización basada en permutaciones del lema de Sperner". Programación matemática . 44 (1–3): 113–120. doi :10.1007/BF01587081. S2CID  5325605.
5. Bapat, Ravindra (3 de abril de 2009). Modelado, cálculo y optimización. World Scientific. ISBN 9789814467896.
6. Shapley, Lloyd; Vohra, Rajiv (1991). "Sobre el teorema del punto fijo de Kakutani, el teorema KKMS y el núcleo de un juego equilibrado". Teoría económica . 1 : 108–116. doi :10.1007/BF01210576. S2CID  121027709.
7. Ichiishi, Tatsuro (1981). "Sobre el teorema de Knaster-Kuratowski-Mazurkiewicz-Shapley". Revista de análisis matemático y aplicaciones . 81 (2): 297–299. doi : 10.1016/0022-247X(81)90063-9 .
8. 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. S2CID  15004516.
9. Komiya, Hidetoshi (1994). "Una prueba simple del teorema KKMS". Teoría económica . 4 (3): 463–466. doi :10.1007/BF01215383. S2CID  123150937.
10. Herings, P. Jean-Jacques (1997). "Una prueba extremadamente simple del teorema KKMS". Teoría económica . 10 (2): 361–367. doi :10.1007/s001990050161. S2CID  122754557.
11. 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.
12. Zhou, Lin (1994). "Un teorema sobre recubrimientos abiertos de un símplex y el teorema de existencia del núcleo de Scarf 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. S2CID  120862302.
13. Musin, Oleg R. (2017). "Teoremas de tipo KKM con condiciones de contorno". Revista de teoría y aplicaciones del punto fijo . 19 (3): 2037–2049. arXiv : 1512.04612 . doi :10.1007/s11784-016-0388-7. S2CID  119619991.
14. Musin, Oleg R. (2016). "Invariantes de homotopía de cubiertas y lemas de tipo KKM". Topología algebraica y geométrica . 16 (3): 1799–1812. arXiv : 1505.07629 . doi :10.2140/agt.2016.16.1799. S2CID  119695004.
15. Frick, Florian; Zerbib, Shira (1 de junio de 2019). "Coberturas 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. S2CID  119176249.

Enlaces externos

• Vea la prueba del Lema KKM en Planet Math.