En matemáticas , el lema de Tucker es un análogo combinatorio del teorema de Borsuk-Ulam , llamado así por Albert W. Tucker .
Sea T una triangulación de la bola cerrada n- dimensional . Suponga que T es antipodalmente simétrico en la esfera límite . Eso significa que el subconjunto de simples de T que están en proporciona una triangulación de donde si σ es un simplex, entonces también lo es −σ. Dejarser un etiquetado de los vértices de T que es una función impar en, es decir, para cada vértice . Luego, el lema de Tucker establece que T contiene una arista complementaria , una arista (1-simplex) cuyos vértices están etiquetados con el mismo número pero con signos opuestos. [1]
Pruebas
Las primeras demostraciones fueron no constructivas, a modo de contradicción. [2]
Posteriormente, se encontraron pruebas constructivas, que también proporcionaron algoritmos para encontrar el borde complementario. [3] [4] Básicamente, los algoritmos se basan en rutas: comienzan en un cierto punto o borde de la triangulación, luego van de simplex a simplex de acuerdo con reglas prescritas, hasta que ya no es posible continuar. Se puede demostrar que el camino debe terminar en un símplex que contenga un borde complementario.
Una prueba más fácil del lema de Tucker usa el lema Ky Fan más general , que tiene una prueba algorítmica simple.
La siguiente descripción ilustra el algoritmo para . [5] Tenga en cuenta que en este caso es un disco y hay 4 etiquetas posibles: , como la figura de la parte superior derecha.
Comience fuera de la pelota y considere las etiquetas de los vértices de los límites. Debido a que el etiquetado es una función impar en el límite, el límite debe tener etiquetas tanto positivas como negativas:
- Si el límite contiene solo o solo , debe haber un borde complementario en el límite. Hecho.
- De lo contrario, el límite debe contener bordes. Además, el número de los bordes del límite deben ser impares.
Seleccione un borde y atravesarlo. Hay tres casos:
- Ahora estás en un simplex. Hecho.
- Ahora estás en un simplex. Hecho.
- Estás en un simplex con otro borde. Revísalo y continúa.
El último caso puede llevarte fuera de la pelota. Sin embargo, dado que el número de bordes en el límite deben ser impares, debe haber un nuevo, no visitado borde en el límite. Revísalo y continúa.
Esta caminata debe terminar dentro de la pelota, ya sea en un o en un simplex. Hecho.
Tiempo de ejecución
El tiempo de ejecución del algoritmo descrito anteriormente es polinomial en el tamaño de triangulación. Esto se considera malo, ya que las triangulaciones pueden ser muy grandes. Sería deseable encontrar un algoritmo que sea logarítmico en el tamaño de triangulación. Sin embargo, el problema de encontrar una ventaja complementaria es PPA -completo incluso paradimensiones. Esto implica que no hay demasiadas esperanzas de encontrar un algoritmo rápido. [6]
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. [7]
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
Referencias
- ^ Matoušek, Jiří (2003), Usando el teorema de Borsuk-Ulam , Springer-Verlag , págs. 34-45, ISBN 3-540-00362-2
- ^ Tucker, Albert W. (1946), "Algunas propiedades topológicas del disco y la esfera", Proc. Primera matemática canadiense. Congreso, Montreal, 1945 , Toronto: University of Toronto Press , págs. 285–309, MR 0020254
- ^ Freund, Robert M .; Todd, Michael J. (1981), "Una prueba constructiva del lema combinatorio de Tucker", Journal of Combinatorial Theory , Serie A, 30 (3): 321–325, doi : 10.1016 / 0097-3165 (81) 90027-3 , Señor 0618536
- ^ Freund, Robert M .; Todd, Michael J. (1980), Una prueba constructiva del lema combinatorio de Tucker
- ^ Meunier, Frédéric (2010), Lemas de Sperner y Tucker (PDF) , Blog Algorithms and Pretty Theorems, págs. 46–64 , consultado el 25 de mayo de 2015
- ^ Aisenberg, James; Bonet, María Luisa; Buss, Sam (2015), 2-D Tucker es PPA completo , ECCC TR15-163
- ^ 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