Lema de Knaster-Kuratowski-Mazurkiewicz

David Gale demostró la siguiente generalización del lema KKM. ^{[ 4 ]} Supongamos que, en lugar de una única cobertura KKM, tenemos n coberturas KKM diferentes:${\displaystyle C_{1}^{1},\ldots ,C_{n}^{1},\ldots ,C_{1}^{n},\ldots ,C_{n}^{n}}$. Entonces, existe una permutación${\displaystyle \pi }$de las cubiertas con una intersección no vacía, es decir:

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

El nombre "lema KKM arcoíris" está inspirado en la descripción que Gale hizo de su lema:

"Una forma coloquial de expresar 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 pertenecerá al conjunto rojo de una persona, al conjunto blanco de otra y al conjunto azul de la tercera". ^{[ 4 ]}

El lema KKM arcoíris se puede demostrar utilizando una generalización arcoíris del lema de Sperner . ^{[ 5 ]}

El lema KKM original se deduce del lema KKM arcoíris simplemente eligiendo n recubrimientos idénticos.

Un conector de un simplex es un conjunto conexo que toca todas las n caras del simplex.

Un revestimiento sin conectores es un revestimiento${\displaystyle C_{1},\ldots ,C_{n}}$en el que no${\displaystyle C_{i}}$contiene un conector.

Cualquier cubierta KKM es una cubierta sin conectores, ya que en una cubierta KKM no hay conectores.${\displaystyle C_{i}}$Incluso toca las n caras. Sin embargo, existen recubrimientos sin conectores que no son recubrimientos 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 del mismo toca las tres caras.

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

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

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 . ^{[ 7 ]}

Mientras que una cobertura KKM contiene n conjuntos cerrados, una cobertura KKMS contiene${\displaystyle 2^{n}-1}$conjuntos cerrados - indexados por los subconjuntos no vacíos de${\displaystyle [n]}$(equivalentemente: por caras no vacías de${\displaystyle \Delta _{n-1}}$). Para cualquier${\displaystyle I\subseteq [n]}$, la envoltura convexa de los vértices correspondientes a${\displaystyle I}$debe estar cubierto por la unión de conjuntos correspondientes a subconjuntos de${\displaystyle I}$, eso es:

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

Cualquier recubrimiento KKM es un caso especial de un recubrimiento KKMS. En un recubrimiento KKM, los n conjuntos correspondientes a los singletons no están vacíos, mientras que los demás 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${\displaystyle 2^{n}-1}$Los conjuntos en una cobertura KKMS no son vacíos; esto se ilustra con el caso especial de una cobertura KKM, en la que la mayoría de los conjuntos están vacíos.

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

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

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

• La colección {{1}, {2}, {3}} está equilibrada: elija todos los pesos como 1. Lo mismo es cierto para cualquier colección en la que cada elemento aparece 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: se eligen todos los pesos iguales a 1/2. Lo mismo ocurre con 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 de pesos para el elemento 2 será igual a la suma para el 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: elige${\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 si y solo si el hipergrafo con conjunto de vértices V y conjunto de aristas B admite un emparejamiento fraccional perfecto.

El teorema KKMS implica el lema KKM. ^{[ 8 ]} Supongamos que tenemos una cobertura KKM${\displaystyle C_{i}}$, para${\displaystyle i=1,\ldots ,n}$Construir una cubierta KKMS${\displaystyle C'_{J}}$como sigue:

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

El estado del KKM en la cubierta original${\displaystyle C_{i}}$implica la condición KKMS en la nueva cobertura${\displaystyle C'_{J}}$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 conjuntos unitarios; por consiguiente, la cobertura original tiene una intersección no vacía.

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

Reny y Wooders demostraron que el conjunto equilibrado también puede ser elegido para ser emparejado . ^{[ 12 ]}

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

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

${\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 requerir que exista una función de peso en${\displaystyle B}$De tal manera que la suma de los pesos cerca de cada vértice de P sea 1, comenzamos eligiendo cualquier conjunto de puntos.${\displaystyle {\textbf {b}}=\{b^{F}:F\in {\textrm {Faces}}(P),b^{F}\in F\}}$Una colección${\displaystyle B\subseteq {\textrm {Faces}}(P)}$se denomina equilibrado con respecto a${\displaystyle {\textbf {b}}}$si y solo si${\displaystyle b^{P}\in \operatorname {conv} \{b^{F}:F\in B\}}$, es decir, el punto asignado a todo el polígono P es una combinación convexa de los puntos asignados a las caras en la colección B.

El teorema KKMS es un caso especial del teorema de Komiya en el que el politopo${\displaystyle P=\Delta _{n-1}}$y${\displaystyle b^{F}}$es el baricentro de la cara F (en particular,${\displaystyle b^{P}}$es el baricentro de${\displaystyle \Delta _{n-1}}$, que es el punto${\displaystyle (1/n,\ldots ,1/n)}$).

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