En matemáticas , el lema de Sperner es un análogo combinatorio del teorema del punto fijo de Brouwer , que es equivalente a él. [1]
El lema de Sperner establece que cada colorante de Sperner (descrito a continuación) de una triangulación de un simplex n- dimensional contiene una celda coloreada con un conjunto completo de colores.
El resultado inicial de este tipo fue probado por Emanuel Sperner , en relación con las pruebas de invariancia de dominio . Los colorantes 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). Ahora se cree que es un problema de cálculo insoluble encontrar un punto fijo de Brouwer o, de manera equivalente, una coloración de Sperner, incluso en el plano, en el caso general. El problema es PPAD-completo , una clase de complejidad inventada por Christos Papadimitriou .
Según la Enciclopedia Matemática Soviética (ed. IM Vinogradov ), un teorema de 1929 relacionado (de Knaster , Borsuk y Mazurkiewicz ) también se conocía como el lema de Sperner ; este punto se analiza en la traducción al inglés (ed. M. Hazewinkel). Ahora se conoce comúnmente como el lema Knaster-Kuratowski-Mazurkiewicz .
Declaración
Caso unidimensional
En una dimensión, el lema de Sperner se puede considerar como una versión discreta del teorema del valor intermedio . En este caso, esencialmente dice 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 valores un número impar de veces.
Caso bidimensional
El caso bidimensional es al que se hace referencia con mayor frecuencia. Se expresa de la siguiente manera:
Dado un triángulo ABC y una triangulación T del triángulo, el conjunto S de vértices de T se colorea con tres colores de tal manera que
- A, B y C tienen los colores 1, 2 y 3 respectivamente.
- Cada vértice en un borde de ABC debe ser coloreado solo con uno de los dos colores de los extremos de su borde. Por ejemplo, cada vértice de AC debe tener un color 1 o 3.
Luego existe un triángulo de T , cuyos vértices están coloreados con los tres colores diferentes. Más precisamente, debe haber un número impar de tales triángulos.
Caso multidimensional
En el caso general, el lema se refiere a un simplex n- dimensional
Consideramos una triangulación T que es una división disjunta deen simplices n- dimensionales más pequeños . Denotan la función de la coloración como f : S → {1,2,3, ..., n , n 1}, donde S es de nuevo el conjunto de vértices de T . Las reglas para colorear son:
- Los vértices del simplex grande están coloreados con diferentes colores, es decir, f ( A i ) = i para 1 ≤ i ≤ n +1.
- Vértices de T ubicados en cualquier subfaz k -dimensional del simplex grande
- están coloreados solo con los colores
Entonces existe un número impar de simples de T , cuyos vértices están coloreados con todos los colores n + 1 . En particular, debe haber al menos uno.
Prueba
Primero abordaremos el caso bidimensional. Considere un gráfico G construido a partir de la triangulación T de la siguiente manera:
- Los vértices de G son los miembros de T más el área fuera del triángulo. Dos vértices están conectados con un borde si sus áreas correspondientes comparten un borde común con un extremo de color 1 y el otro de color 2.
Tenga en cuenta que en el intervalo AB hay un número impar de bordes de color 1-2 (simplemente porque A es de color 1, B es de color 2; y a medida que avanzamos a lo largo de AB, debe haber un número impar de cambios de color para obtener diferentes colores al principio y al final). Por 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 gráfico finito hay un número par de vértices con grado impar. Por lo tanto, el gráfico restante, con exclusión de la zona exterior, tiene un número impar de vértices con grado impar correspondiente a los miembros de T .
Se puede ver fácilmente que el único grado posible de un triángulo a partir 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.
Por lo tanto, hemos obtenido una conclusión un poco más fuerte, que dice que en una triangulación T hay un número impar (y al menos uno) de triángulos a todo color.
Un caso multidimensional puede probarse por inducción en la dimensión de un simplex. Aplicamos el mismo razonamiento, como en el caso bidimensional, para concluir que en una triangulación n- dimensional hay un número impar de simplices a todo color.
Comentario
Aquí hay una elaboración de la prueba dada anteriormente, para un lector nuevo en la teoría de grafos .
Este diagrama numera los colores de los vértices del ejemplo dado anteriormente. Los pequeños triángulos cuyos vértices tienen números diferentes están sombreados en el gráfico. Cada pequeño triángulo 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 i designa el espacio fuera de ella.
Como se describió anteriormente, los nodos que comparten un borde cuyos extremos están numerados 1 y 2 se unen en el gráfico derivado. Por ejemplo, el nodo d comparte un borde 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 agregar un nuevo triángulo de número completo, por ejemplo, insertando un nodo con el número 3 en el borde entre 1 y 1 del nodo a , y uniendo ese nodo al otro vértice de a . Hacerlo tendría que crear un par de nuevos nodos, como la situación con los nodos f y g .
Generalizaciones
Subconjuntos de etiquetas
Suponga que cada vértice de la triangulación puede etiquetarse con varios colores, de modo que la función de coloración sea f : S → 2 [n + 1] .
Para cada sub-simplex, el conjunto de etiquetas en sus vértices es un conjunto-familia sobre el conjunto de colores [ n +1]. Esta familia de conjuntos puede verse como un hipergráfico .
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 sub-símplex con un etiquetado equilibrado , un etiquetado en el que el el hipergrama correspondiente admite una coincidencia fraccionaria perfecta . Para ilustrar, aquí hay algunos ejemplos de etiquetado equilibrado para n = 2:
- ({1}, {2}, {3}) - equilibrado por los pesos (1, 1, 1).
- ({1,2}, {2,3}, {3,1}) - equilibrado por los pesos (1/2, 1/2, 1/2).
- ({1,2}, {2,3}, {1}): equilibrado por los pesos (0, 1, 1).
Esto fue probado por Shapley en 1973. [2] Es un análogo combinatorio del lema KKMS .
Politopos
Suponga que, en lugar de un simplex dimensional, tenemos un -politopo dimensional con vértices.
Entonces hay al menos simples completamente etiquetados, donde "completamente etiquetado" indica que cada etiqueta en el símplex tiene un color diferente. Por ejemplo, si un polígono (bidimensional) con n vértices se triangula y se colorea de acuerdo con el criterio de Sperner, entonces hay al menos triángulos completamente etiquetados.
La declaración general fue conjeturada por Atanassov en 1996, quien lo demostró para el caso.. [3] La prueba del caso general fue presentada por primera vez por De Loera, Peterson y Su en 2002. [4]
Variante arcoiris
Supongamos que, en lugar de un solo etiquetado, tenemos diferentes etiquetas de Sperner.
Consideramos pares (simplex, 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 pares diferentes).
Entonces hay al menos pares completamente etiquetados. Esto fue probado por Ravindra Bapat . [5]
Otra forma de enunciar este lema es la siguiente. Supongamos que haypersonas, cada una de las cuales produce un etiquetado de Sperner diferente de la misma triangulación. Entonces, existe un simplex, y una coincidencia 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 por 1, otra persona etiqueta su vértice por 2, etc.). Además, hay al menostales emparejamientos. Esto se puede usar para encontrar un corte de pastel sin envidia con piezas conectadas.
Múltiples etiquetas
Supongamos que, en lugar de un solo etiquetado, tenemos diferentes etiquetas de Sperner. Entonces: [6] : Thm 2.1
- Para cualquier número entero positivo cuya suma es , existe un baby-simplex en el que, para cada , número de etiquetado usa al menos (fuera de ) etiquetas distintas. Además, cada etiqueta es utilizada por al menos uno (de) etiquetado.
- Para cualquier número entero positivo cuya suma es , existe un baby-simplex en el que, para cada , la etiqueta es utilizado por al menos (fuera de ) diferentes etiquetas.
Ambas versiones se reducen al lema de Sperner cuando , o cuando todos las etiquetas son idénticas.
Ver [7] para generalizaciones similares.
Grados
Secuencia | La licenciatura |
---|---|
123 | 1 (un interruptor 1-2 y ningún interruptor 2-1) |
12321 | 0 (un interruptor 1-2 menos un interruptor 2-1) |
1232 | 0 (como arriba; la secuencia de recuperación es cíclica) |
1231231 | 2 (dos interruptores 1-2 y ningún interruptor 2-1) |
Suponga 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 de etiquetado como la diferencia entre el número de interruptores de 1 a 2 y el número de interruptores de 2 a 1. Consulte 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 de etiquetado . [8] 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 conmutadores solo en el lado entre los vértices 1 y 2, y el número de 1-2 conmutadores debe ser uno más que el número de 2-1 conmutadores (al caminar del vértice 1 al vértice 2). Por tanto, el lema de Sperner original se deriva del teorema de Musin.
Árboles y ciclos
Hay un lema similar sobre árboles y ciclos finitos e infinitos . [9]
Lema de Sperner cúbico
Harold W. Kuhn demostró una variante del lema de Sperner en un cubo (en lugar de un simplex) . [10] Está relacionado con el teorema de Poincaré-Miranda . [11]
Aplicaciones
Los colorantes de Sperner se han utilizado para el cálculo eficaz de puntos fijos . Se puede construir una coloración de Sperner de manera que los simples completamente etiquetados correspondan a puntos fijos de una función dada. Al hacer una triangulación cada vez más pequeña, se puede mostrar que el límite de los simples completamente etiquetados es exactamente el punto fijo. Por tanto, la técnica proporciona una forma de aproximar puntos fijos.
Por esta razón, el lema de Sperner también puede ser utilizado en los algoritmos de búsqueda de raíz y división justa algoritmos; consulte los protocolos Simmons – Su .
El lema de Sperner es uno de los ingredientes clave de la prueba del teorema de Monsky , que un cuadrado no se puede cortar en un número impar de triángulos de igual área . [12]
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. [13] : 67
Cincuenta años después de su primera publicación, Sperner presentó una encuesta sobre el desarrollo, la influencia y las aplicaciones de su lema combinatorio. [14]
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. [15]
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 |
Ver también
- Combinatoria topológica
Referencias
- ^ Flegg, H. Graham (1974). De la geometría a la topología . Londres: English University Press. págs. 84–89. ISBN 0-340-05324-0.
- ^ Shapley, LS (1 de enero de 1973), Hu, TC; Robinson, Stephen M. (eds.), "Sobre juegos equilibrados sin pagos complementarios " , Programación matemática , Academic Press, págs. 261–290, ISBN 978-0-12-358350-5, consultado el 29 de junio de 2020
- ^ Atanassov, KT (1996), "Sobre el lema de Sperner", Studia Scientiarum Mathematicarum Hungarica , 32 (1-2): 71-74, MR 1405126
- ^ De Loera, Jesús A .; Peterson, Eliseo; Su, Francis Edward (2002), "Una generalización politopal del lema de Sperner" , Journal of Combinatorial Theory , Serie A, 100 (1): 1–26, doi : 10.1006 / jcta.2002.3274 , MR 1932067
- ^ 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 . S2CID 5325605 .
- ^ Meunier, Frédéric; Su, Francis Edward (6 de enero de 2018). "Versiones de etiquetas múltiples de lemas y aplicaciones de Sperner y Fan". arXiv : 1801.02044 [ math.CO ].
- ^ Asada, Megumi; Frick, Florian; Pisharody, Vivek; Polevy, Maxwell; Stoner, David; Tsang, Ling Hei; Wellner, Zoe (2018). "SIAM (Sociedad de Matemática Industrial y Aplicada)". Revista SIAM de Matemática Discreta . 32 : 591–610. arXiv : 1701.04955 . doi : 10.1137 / 17m1116210 . S2CID 43932757 .
- ^ Oleg R Musin (2014). "Alrededor del lema de Sperner". arXiv : 1405.7513 [ math.CO ].
- ^ Niedermaier, Andrew; Rizzolo, Douglas; Su, Francis Edward (2014), "Un árbol lema de Sperner", en Barg, Alexander; Musin, Oleg R. (eds.), Discrete Geometry and Algebraic Combinatorics , Contemporary Mathematics, 625 , Providence, RI: American Mathematical Society, págs. 77–92, arXiv : 0909.0339 , doi : 10.1090 / conm / 625/12492 , ISBN 9781470409050, MR 3289406 , S2CID 115157240
- ^ Kuhn, HW (1960), "Algunos lemas combinatorios en topología", IBM Journal of Research and Development , 4 (5): 518-524, doi : 10.1147 / rd.45.0518
- ^ Michael Müger (2016), Topología para el matemático en activo (PDF) , Borrador
- ^ Aigner, Martin ; Ziegler, Günter M. (2010), "Un cuadrado y un número impar de triángulos", Proofs from The Book (4ª ed.), Berlín: Springer-Verlag, págs. 131-138, doi : 10.1007 / 978-3- 642-00856-6_20 , ISBN 978-3-642-00855-9
- ^ Bufanda, Herbert (1967). "El núcleo de un juego de N Person". Econometrica . 35 (1): 50–69. doi : 10.2307 / 1909383 . JSTOR 1909383 .
- ^ Sperner, Emanuel (1980), "Cincuenta años de desarrollo ulterior de un lema combinatorio", Solución numérica de problemas altamente no lineales (Simpos. Algoritmos de punto fijo y problemas de complementariedad, Univ. Southampton, Southampton, 1979) , Holanda del Norte, Amsterdam- Nueva York, págs. 183–197, 199–217, MR 0559121
- ^ 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
enlaces externos
- Prueba del lema de Sperner al cortar el nudo
- El lema de Sperner y el juego del triángulo , en el sitio n-rich.
- El lema de Sperner en 2D , un juego basado en web en itch.io.