En matemáticas, el lema de Sperner es un resultado combinatorio sobre el coloreado de triangulaciones, análoga al teorema del punto fijo de Brouwer, que es equivalente. Establece que cada coloración de Sperner (descrita más adelante) de una triangulación formada por símplices contiene una celda cuyos vértices tienen colores diferentes.
El resultado inicial de este tipo fue demostrado por Emanuel Sperner, en relación con las demostraciones de invarianza del dominio. Las coloraciones de Sperner se han utilizado para el cálculo efectivo del punto fijo y para la resolución numérica de ecuaciones no lineales, y se aplican en los algoritmos de división justa (de corte de pastel).
Según la Enciclopedia Matemática Soviética (ed. Iván Vinográdov), un teorema relacionado de 1929 (de Knaster, Borsuk y Mazurkiewicz) también se conoció como el lema de Sperner. Este punto se analiza en la traducción al inglés (ed. M. Hazewinkel). Actualmente se conoce comúnmente como lema de Knaster-Kuratowski-Mazurkiewicz.
Enunciado Caso unidimensional
En una dimensión, el lema de Sperner puede considerarse una versión discreta del teorema del valor intermedio. En este caso, básicamente establece que si una función discreta toma solo los valores 0 y 1, comienza en el valor 0 y termina en el valor 1, debe cambiar de valor un número impar de veces.
Caso bidimensional El caso bidimensional es el que se menciona con mayor frecuencia. Se enuncia de la siguiente manera:
Subdividir un triángulo arbitrariamente en una triangulación compuesta por triángulos más pequeños que se unen arista con arista. Entonces, la coloración de Sperner de la triangulación se define como la asignación de tres colores a los vértices de la triangulación, de modo que: Cada uno de los tres vértices , y del triángulo inicial tiene un color distinto. Los vértices que se encuentran en cualquier arista del triángulo tienen solo dos colores: los dos colores en los extremos de la arista. Por ejemplo, cada vértice de debe tener el mismo color que o . Entonces, cada coloración de Sperner de cada triangulación tiene al menos un triángulo arcoíris, un triángulo más pequeño en la triangulación cuyos vértices están coloreados con los tres colores diferentes. Más precisamente, debe haber un número impar de triángulos arcoíris.
Caso multidimensional En el caso general, el lema se refiere a un símplex de dimensión :
Considérese cualquier triangulación , una división disjunta de en símplices de dimensión más pequeños, que nuevamente se encuentran cara a cara. Denótese la función de coloración como:
donde es el conjunto de vértices de . Una función de coloración define una coloración de Sperner cuando: Los vértices del símplex grande se colorean con diferentes colores, es decir, sin pérdida de generalidad, para . Vértices de ubicados en cualquier subcara de dimensión del símplex grande están coloreados solo con los colores
Entonces, cada coloración de Sperner de cada triangulación del símplex de dimensión tiene un número impar de instancias de un símplex arcoíris, es decir, un símplex cuyos vértices están coloreados con todos los colores de . En particular, debe haber al menos un símplex arcoíris.
Demostraciones
Demostración por inducción Primero se abordar el caso bidimensional. Considérese un grafo construido a partir de la triangulación de la siguiente manera:
Los vértices de son los miembros de más el área exterior del triángulo. Dos vértices están conectados por una arista si sus áreas correspondientes comparten una arista común con un extremo de color 1 y el otro de color 2.
Obsérvese que en el intervalo hay un número impar de aristas de color 1-2 (simplemente porque A tiene el color 1 y B el 2; y a medida que se avanza por , debe haber un número impar de cambios de color para obtener colores diferentes al principio y al final). En los intervalos BC y CA, no hay aristas de color 1-2. Por lo tanto, el vértice de correspondiente al área exterior tiene un grado impar. Pero se sabe (por el lema del apretón de manos) que en un grafo finito hay un número par de vértices con grado impar. Por lo tanto, el grafo restante, excluyendo el área exterior, tiene un número impar de vértices con grado impar correspondientes a los miembros de .
Se puede ver fácilmente que el único grado posible de un triángulo de es 0, 1 o 2, y que el grado 1 corresponde a un triángulo coloreado con los tres colores 1, 2 y 3.
Así, se ha obtenido una conclusión ligeramente más sólida: en una triangulación hay un número impar (y al menos uno) de triángulos con todos los colores.
Un caso multidimensional puede demostrarse por inducción sobre la dimensión de un símplex. Se aplica el mismo razonamiento que en el caso bidimensional para concluir que en una triangulación -dimensional hay un número impar de símplex con todos los colores.
Comentario
A continuación, se presenta una explicación de la demostración dada anteriormente, para quienes no conocen la teoría de grafos.
Este diagrama numera los colores de los vértices del ejemplo dado anteriormente. Los triángulos pequeños cuyos vértices tienen números diferentes están sombreados en el gráfico. Cada triángulo pequeño se convierte en un nodo en el nuevo gráfico derivado de la triangulación. Las letras minúsculas identifican las áreas, ocho dentro de la figura, y el área designa el espacio exterior.
Como se describió anteriormente, los nodos que comparten una arista cuyos extremos están numerados 1 y 2 se unen en el grafo derivado. Por ejemplo, el nodo comparte una arista con el área exterior , y sus vértices tienen números diferentes, por lo que también está sombreado. El nodo no está sombreado porque dos vértices tienen el mismo número, pero está unido al área exterior.
Se podría añadir un nuevo triángulo con numeración completa, por ejemplo, insertando un nodo numerado 3 en la arista entre 1 y 1 del nodo , y uniendo ese nodo al otro vértice de . Para ello, se tendría que crear un par de nodos nuevos, como en el caso de los nodos y .
Demostración sin inducción Andrew McLennan y Rabee Tourky presentaron una demostración diferente, utilizando el nodo símplex. Se realiza en un solo paso, sin inducción.
Cálculo de un símplex de Sperner Supóngase que existe un símplex de dimensión d con un lado N, y que se triangula en subsímplex de lado 1. Existe una función que, dado cualquier vértice de la triangulación, devuelve su color. Se garantiza que la coloración satisface la condición de contorno de Sperner. ¿Cuántas veces se debe llamar a la función para encontrar un símplex arcoíris? Obviamente, se pueden recorrer todos los vértices de la triangulación, cuyo número es O(Nd), que es polinomial en N cuando la dimensión es fija. Pero, ¿puede hacerse en un tiempo O(poly(log N)), que es polinomial en la representación binaria de N?
Este problema fue estudiado por primera vez por Christos Papadimitriou. Introdujo una clase de complejidad llamada PPAD, que contiene este y otros problemas relacionados (como el hallazgo de un punto fijo de Brouwer). Demostró que encontrar un símplex de Sperner es PPAD-completo incluso para d = 3. Unos 15 años después, Chen y Deng demostraron la completitud de PPAD incluso para d = 2. Se cree que los problemas PPAD-difíciles no pueden resolverse en un tiempo O(poly(log N)).
Generalizaciones Subconjuntos de etiquetas Supóngase que cada vértice de la triangulación puede etiquetarse con múltiples colores, de modo que la función de coloración es .
Para cada subsímplex, el conjunto de etiquetas en sus vértices es una familia de conjuntos sobre el conjunto de colores. Esta familia de conjuntos puede considerarse como un hipergrafo.
Si, para cada vértice en una cara del símplex, los colores en son un subconjunto del conjunto de colores en los extremos de la cara, entonces existe un subsímplex con un etiquetado equilibrado, es decir, un etiquetado en el que el correspondiente hipergrafo admite una coincidencia fraccionaria perfecta. Para ilustrarlo, se presentan algunos ejemplos de etiquetado equilibrado para :
- equilibrado por los pesos . - equilibrado por los pesos . - equilibrado por los pesos .
Esto fue demostrado por Shapley en 1973, y es un análogo combinatorio del lema KKMS.
Variantes con politopos Supóngase que se tiene un politopo de dimensión con vértices. está triangulado y cada vértice de la triangulación está etiquetado con una etiqueta de . Cada vértice principal está etiquetado como . Un subsímplex se denomina completamente etiquetado si es -dimensional y cada uno de sus vértices tiene una etiqueta diferente. Si cada vértice de una cara de está etiquetado con una de las etiquetas de los extremos de , entonces hay al menos símplex completamente etiquetados. Algunos casos especiales son:
. En este caso, es un símplex. El lema de Sperner politópico garantiza que exista al menos un símplex completamente etiquetado. Es decir, se reduce al lema de Sperner. . Supóngase que un polígono bidimensional con vértices se triangula y se etiqueta utilizando las etiquetas de modo que, en cada cara entre los vértices y , solo se utilizan las etiquetas y . Entonces, existen al menos subtriángulos en los que se utilizan tres etiquetas diferentes.
El enunciado general fue conjeturado por Atanassov en 1996, quien lo demostró para el caso . La demostración del caso general fue presentada por primera vez por de Loera, Peterson y Su en 2002. Proporcionan dos demostraciones: la primera es no constructiva y utiliza la noción de conjuntos de guijarros; la segunda es constructiva y se basa en argumentos de seguimiento de caminos en grafos.
Meunier extendió el teorema de los politopos a los cuerpos politópicos, que no necesitan ser convexos ni simplemente conexos. En particular, si es un politopo, entonces el conjunto de sus caras es un cuerpo politópico. En cada etiquetado de Sperner de un cuerpo politópico con vértices , hay al menos:
símplices completamente etiquetados, de modo que cualquier par de estos símplices recibe dos etiquetados diferentes. El grado es el número de aristas de a las que pertenece . Dado que el grado es al menos , el límite inferior es al menos . Sin embargo, puede ser mayor. Por ejemplo, para un politopo cíclico en 4 dimensiones con vértices , el límite inferior es:
Musin extendió aún más el teorema al caso variedades lineales por partes] -dimensionales, con o sin límite.
Asada, Frick, Pisharody, Polevy, Stoner, Tsang y Wellner extendieron aún más el teorema a seudovariedades con límite y mejoraron el límite inferior del número de facetas con etiquetas distintas por pares.
Variantes cúbicas Supóngase que, en lugar de un símplex triangulado en subsímplices, se tiene un cubo de dimensión dividido en cubos de dimensión más pequeños.
Harold W. Kuhn demostró el siguiente lema. Supóngase que el cubo , para algún entero , se divide en cubos unitarios . Supóngase también que cada vértice de la partición está etiquetado con una etiqueta de tal que, para cada vértice : (1) si , entonces la etiqueta de es como máximo ; (2) si , entonces la etiqueta de no es . Entonces existe un cubo unitario con todas las etiquetas (algunas de ellas más de una vez). El caso especial es: considérese que un cuadrado se divide en subcuadrados y cada vértice se etiqueta con una etiqueta de . El borde izquierdo se etiqueta con (= máximo 1); el borde inferior se etiqueta con o (= máximo 2); el borde superior se etiqueta con o (= distinto de 2); y el borde derecho se etiqueta con o (= distinto de 1). Entonces, hay un cuadrado etiquetado con .