En matemáticas , el lema de Sperner es un resultado combinatorio sobre coloraciones de triangulaciones , análogo al teorema del punto fijo de Brouwer , que es equivalente a él. [1] Establece que cada coloración de Sperner (descrita a continuación) de una triangulación de un símplex -dimensional contiene una celda cuyos vértices tienen todos colores diferentes.
El resultado inicial de este tipo fue demostrado por Emanuel Sperner , en relación con las pruebas de invariancia del dominio . Las coloraciones de Sperner se han utilizado para el cálculo eficaz de puntos fijos y en algoritmos de búsqueda de raíces , y se aplican en algoritmos de división justa (corte de torta).
Según la Enciclopedia Matemática Soviética (ed. IM Vinogradov ), 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). Ahora se lo conoce comúnmente como el lema de Knaster–Kuratowski–Mazurkiewicz .
En una dimensión, el lema de Sperner puede considerarse como una versión discreta del teorema del valor intermedio . En este caso, dice básicamente que si una función discreta toma solo los valores 0 y 1, comienza en el valor 0 y termina en el valor 1, entonces debe cambiar de valor un número impar de veces.
El caso bidimensional es el que se menciona con más frecuencia y se enuncia de la siguiente manera:
Subdivida un triángulo ABC arbitrariamente en una triangulación que consista en triángulos más pequeños que se encuentran borde con borde. Luego, una coloración de Sperner de la triangulación se define como una asignación de tres colores a los vértices de la triangulación de manera que
Entonces, cada coloración de Sperner de cada triangulación tiene al menos un "triángulo arco iris", 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 iris.
En el caso general, el lema se refiere a un símplex n -dimensional :
Consideremos cualquier triangulación T , una división disjunta de en símplices n -dimensionales más pequeños, que nuevamente se encuentran cara a cara. Denotemos la función de coloración como:
donde S es el conjunto de vértices de T . Una función de coloración define una coloración de Sperner cuando:
están coloreados solo con los colores
Entonces, cada coloración de Sperner de cada triangulación del símplex de n dimensiones 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 n + 1. En particular, debe haber al menos un símplex arcoíris.
En primer lugar, abordaremos el caso bidimensional. Consideremos un grafo G construido a partir de la triangulación T de la siguiente manera:
Nótese que en el intervalo AB hay un número impar de bordes coloreados 1-2 (simplemente porque A está coloreado 1, B está coloreado 2; y a medida que nos movemos a lo largo de AB , debe haber un número impar de cambios de color para obtener diferentes colores al principio y al final). En los intervalos BC y CA, no hay bordes coloreados 1-2 en absoluto. Por lo tanto, el vértice de G correspondiente al área exterior tiene un grado impar. Pero se sabe (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 miembros de T.
Se puede ver fácilmente que el único grado posible de un triángulo de T 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í hemos obtenido una conclusión ligeramente más fuerte, que dice que en una triangulación T hay un número impar (y al menos uno) de triángulos completamente coloreados.
Un caso multidimensional puede demostrarse por inducción sobre la dimensión de un símplex. Aplicamos el mismo razonamiento que en el caso bidimensional para concluir que en una triangulación n -dimensional hay un número impar de símplex de color completo.
A continuación se presenta una elaboración de la prueba dada anteriormente, para un lector nuevo en la teoría de grafos .
En este diagrama se enumeran 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 pequeñas identifican las áreas, ocho dentro de la figura y el área i designa el espacio fuera de ella.
Como se describió anteriormente, aquellos nodos que comparten una arista cuyos puntos finales están numerados 1 y 2 se unen en el grafo derivado. Por ejemplo, el nodo d comparte una arista con el área exterior i y todos sus vértices tienen números diferentes, por lo que también está sombreado. El nodo b 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 a , y uniendo ese nodo al otro vértice de a . Para ello habría que crear un par de nodos nuevos, como en la situación con los nodos f y g .
Andrew McLennan y Rabee Tourky presentaron una prueba diferente, utilizando el volumen de un símplex . Se realiza en un solo paso, sin inducción. [2] [3]
Supongamos que existe un símplex de dimensión d con una longitud de lado N y que se triangula en subsímplices con una longitud 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 tenemos que llamar a la función para encontrar un símplex arcoíris? Obviamente, podemos recorrer todos los vértices de la triangulación, cuyo número es O( N d ), que es polinomial en N cuando la dimensión es fija. Pero, ¿se puede hacer 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 problema y otros relacionados (como encontrar 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 que la PPAD es completa incluso para d = 2. [4] Se cree que los problemas PPAD-completos no se pueden resolver en un tiempo O(poly(log N )).
Supongamos que cada vértice de la triangulación puede etiquetarse con múltiples colores, de modo que la función de coloración es F : S → 2 [ n +1] .
Para cada subsímplex, el conjunto de etiquetas en sus vértices es una familia de conjuntos sobre el conjunto de colores [ n + 1] . Esta familia de conjuntos puede verse como un hipergrafo .
Si, para cada vértice v en una cara del símplex, los colores en f ( v ) son un subconjunto del conjunto de colores en los extremos de la cara, entonces existe un subsímplex con un etiquetado equilibrado – un etiquetado en el que el hipergrafo correspondiente admite una correspondencia fraccionaria perfecta . Para ilustrarlo, aquí hay algunos ejemplos de etiquetado equilibrado para n = 2 :
Esto fue demostrado por Shapley en 1973. [5] Es un análogo combinatorio del lema KKMS .
Supongamos que tenemos un politopo P de dimensión d con n vértices. P está triangulado y cada vértice de la triangulación está etiquetado con una etiqueta de {1, …, n }. Cada vértice principal i está etiquetado i . Un subsímplex se denomina completamente etiquetado si es de dimensión d y cada uno de sus d + 1 vértices tiene una etiqueta diferente. Si cada vértice en una cara F de P está etiquetado con una de las etiquetas en los puntos finales de F , entonces hay al menos n – d símplex completamente etiquetados. Algunos casos especiales son:
El enunciado general fue conjeturado por Atanassov en 1996, quien lo demostró para el caso d = 2. [ 6] La prueba del caso general fue dada por primera vez por de Loera, Peterson y Su en 2002. [7] Proporcionan dos pruebas: la primera no es constructiva y utiliza la noción de conjuntos de guijarros ; la segunda es constructiva y se basa en argumentos de seguimiento de caminos en gráficos .
Meunier [8] extendió el teorema de los politopos a los cuerpos politópicos, que no necesitan ser convexos o simplemente conexos. En particular, si P 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 v 1 , …, v n , hay al menos:
Símplices completamente etiquetados de modo que cualquier par de estos símplices reciba dos etiquetados diferentes. El grado deg B ( P ) ( v i ) es el número de aristas de B ( P ) a las que pertenece v i . Dado que el grado es al menos d , el límite inferior es al menos n – d . Pero puede ser mayor. Por ejemplo, para el politopo cíclico en 4 dimensiones con n vértices, el límite inferior es:
Musin [9] extendió aún más el teorema a variedades lineales por partes de dimensión d , con o sin límite.
Asada, Frick, Pisharody, Polevy, Stoner, Tsang y Wellner [10] extendieron aún más el teorema a pseudovariedades con límite y mejoraron el límite inferior del número de facetas con etiquetas distintas por pares.
Supongamos que, en lugar de un símplex triangulado en subsímplices, tenemos un cubo n -dimensional particionado en cubos n -dimensionales más pequeños.
Harold W. Kuhn [11] demostró el siguiente lema. Supóngase que el cubo [0, M ] n , para algún entero M , está dividido en M n cubos unitarios. Supóngase que cada vértice de la partición está etiquetado con una etiqueta de {1, …, n + 1}, tal que para cada vértice v : (1) si v i = 0 entonces la etiqueta en v es como máximo i ; (2) si v i = M entonces la etiqueta en v no es i . Entonces existe un cubo unitario con todas las etiquetas {1, …, n + 1} (algunas de ellas más de una vez). El caso especial n = 2 es: supóngase que un cuadrado está dividido en subcuadrados, y cada vértice está etiquetado con una etiqueta de {1,2,3}. El borde izquierdo está etiquetado con 1 (= como máximo 1); el borde inferior está etiquetado con 1 o 2 (= como máximo 2); El borde superior está marcado con 1 o 3 (= no 2); y el borde derecho está marcado con 2 o 3 (= no 1). Luego hay un cuadrado marcado con 1,2,3.
Otra variante, relacionada con el teorema de Poincaré-Miranda , [12] es la siguiente. Supóngase que el cubo [0, M ] n está dividido en M n cubos unitarios. Supóngase que cada vértice está etiquetado con un vector binario de longitud n , de modo que para cada vértice v : (1) si v i = 0 entonces la coordenada i de la etiqueta en v es 0; (2) si v i = M entonces la coordenada i de la etiqueta en v es 1; (3) si dos vértices son vecinos, entonces sus etiquetas difieren como máximo en una coordenada. Entonces existe un cubo unitario en el que las 2 n etiquetas son diferentes. En dos dimensiones, otra forma de formular este teorema es: [13] en cualquier etiquetado que satisfaga las condiciones (1) y (2), hay al menos una celda en la que la suma de etiquetas es 0 [una celda unidimensional con etiquetas (1,1) y (-1,-1) , o una celda bidimensional con las cuatro etiquetas diferentes].
Wolsey [14] reforzó estos dos resultados al demostrar que el número de cubos completamente etiquetados es impar.
Musin [13] extendió estos resultados a cuadrangulaciones generales .
Supongamos que, en lugar de un único etiquetado, tenemos n etiquetados de Sperner diferentes. Consideramos pares (símplex, permutación) tales que la etiqueta de cada vértice del símplex se elige de un etiquetado diferente (por lo que para cada símplex, hay n ! pares diferentes). Entonces hay al menos n ! pares completamente etiquetados. Esto fue demostrado por Ravindra Bapat [15] para cualquier triangulación. Una prueba más simple, que solo funciona para triangulaciones específicas, fue presentada más tarde por Su. [16]
Otra forma de enunciar este lema es la siguiente. Supongamos que hay n personas, cada una de las cuales produce un etiquetado de Sperner diferente de la misma triangulación. Entonces, existe un símplex y una correspondencia de las personas con sus vértices, de modo que cada vértice es etiquetado por su propietario de manera diferente (una persona etiqueta su vértice con 1, otra persona etiqueta su vértice con 2, etc.). Además, hay al menos n ! de esas correspondencias. Esto se puede utilizar para encontrar un corte de pastel sin envidia con piezas conectadas.
Asada, Frick, Pisharody, Polevy, Stoner, Tsang y Wellner [10] extendieron este teorema a pseudovariedades con borde.
En términos más generales, supongamos que tenemos m diferentes etiquetados de Sperner, donde m puede ser diferente de n . Entonces: [17] : Teoría 2.1
Ambas versiones se reducen al lema de Sperner cuando m = 1 , o cuando todas las m etiquetas son idénticas.
Véase [18] para generalizaciones similares.
Brown y Cairns [19] reforzaron el lema de Sperner al considerar la orientación de los símplices. Cada subsímplex tiene una orientación que puede ser +1 o -1 (si está completamente etiquetado), o 0 (si no está completamente etiquetado). Demostraron que la suma de todas las orientaciones de los símplices es +1. En particular, esto implica que hay un número impar de símplices completamente etiquetados.
Como ejemplo para n = 3 , supongamos que un triángulo está triangulado y etiquetado con {1,2,3}. Considere la secuencia cíclica de etiquetas en el límite del triángulo. Defina el grado del etiquetado como el número de cambios de 1 a 2, menos el número de cambios de 2 a 1. Vea los ejemplos en la tabla de la derecha. Tenga en cuenta que el grado es el mismo si contamos los cambios de 2 a 3 menos 3 a 2, o de 3 a 1 menos 1 a 3.
Musin demostró que el número de triángulos completamente etiquetados es al menos el grado del etiquetado . [20] En particular, si el grado es distinto de cero, entonces existe al menos un triángulo completamente etiquetado.
Si un etiquetado satisface la condición de Sperner, entonces su grado es exactamente 1: hay 1-2 y 2-1 interruptores solo en el lado entre los vértices 1 y 2, y el número de interruptores 1-2 debe ser uno más que el número de interruptores 2-1 (al caminar del vértice 1 al vértice 2). Por lo tanto, el lema de Sperner original se deduce del teorema de Musin.
Existe un lema similar sobre árboles y ciclos finitos e infinitos . [21]
Mirzakhani y Vondrak [22] estudian una variante más débil de un etiquetado de Sperner, en la que el único requisito es que la etiqueta i no se use en la cara opuesta al vértice i . Lo llaman etiquetado admisible por Sperner . Muestran que hay etiquetados admisibles por Sperner en los que cada celda contiene como máximo 4 etiquetas. También prueban un límite inferior óptimo para el número de celdas que deben tener al menos dos etiquetas diferentes en cada etiquetado admisible por Sperner. También prueban que, para cualquier partición admisible por Sperner del símplex regular, el área total del límite entre las partes se minimiza por la partición de Voronoi .
Las coloraciones de Sperner se han utilizado para el cálculo eficaz de puntos fijos . Se puede construir una coloración de Sperner de modo que los símplices completamente etiquetados correspondan a puntos fijos de una función dada. Al hacer una triangulación cada vez más pequeña, se puede demostrar que el límite de los símplices completamente etiquetados es exactamente el punto fijo. Por lo tanto, la técnica proporciona una forma de aproximar puntos fijos. Una aplicación relacionada es la detección numérica de órbitas periódicas y dinámicas simbólicas . [23] El lema de Sperner también se puede utilizar en algoritmos de búsqueda de raíces y algoritmos de división justa ; consulte los protocolos Simmons-Su .
El lema de Sperner es uno de los ingredientes clave de la prueba del teorema de Monsky , que sostiene que un cuadrado no puede dividirse en un número impar de triángulos de igual área . [24]
El lema de Sperner se puede utilizar para encontrar un equilibrio competitivo en una economía de intercambio , aunque existen formas más eficientes de encontrarlo. [25] : 67
Cincuenta años después de su primera publicación, Sperner presentó un estudio sobre el desarrollo, la influencia y las aplicaciones de su lema combinatorio. [26]
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 puede demostrarse por separado utilizando argumentos totalmente diferentes, pero cada variante también puede reducirse a las otras variantes de su fila. Además, cada resultado de la fila superior puede deducirse del que se encuentra debajo en la misma columna. [27]
