Lema de Tucker

Análogo combinatorio del teorema de Borsuk-Ulam

En este ejemplo, donde n=2, el 1-simplex rojo tiene vértices etiquetados con el mismo número con signos opuestos. El lema de Tucker establece que para tal triangulación debe existir al menos uno de esos 1-símplex.

En matemáticas , el lema de Tucker es un análogo combinatorio del teorema de Borsuk-Ulam , que lleva el nombre de Albert W. Tucker .

Sea T una triangulación de la bola cerrada de n dimensiones . Supongamos que T es antípodamente 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 dónde si σ es un simplex, entonces también lo es −σ. Sea un etiquetado de los vértices de T que es una función impar en , es decir, para cada vértice . Entonces, el lema de Tucker establece que T contiene una arista complementaria : una arista (un 1-símplex) cuyos vértices están etiquetados con el mismo número pero con signos opuestos. ^[1] ${\displaystyle B_{n}}$ ${\displaystyle S_{n-1}}$ ${\displaystyle S_{n-1}}$ ${\displaystyle S_{n-1}}$ ${\displaystyle L:V(T)\to \{+1,-1,+2,-2,...,+n,-n\}}$ ${\displaystyle S_{n-1}}$ ${\displaystyle L(-v)=-L(v)}$ ${\displaystyle v\in S_{n-1}}$

Pruebas

Las primeras pruebas fueron no constructivas, por vía de contradicción. ^[2]

Posteriormente se encontraron pruebas constructivas, que también proporcionaron algoritmos para encontrar la arista complementaria. ^{[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 según reglas prescritas, hasta que ya no es posible continuar. Se puede demostrar que el camino debe terminar en un simplex que contenga una arista complementaria.

Una prueba más sencilla del lema de Tucker utiliza el lema más general de Ky Fan , 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 arriba a la derecha. ${\displaystyle n=2}$ ${\displaystyle B_{n}}$ ${\displaystyle -2,-1,1,2}$

Comience fuera de la pelota y considere las etiquetas de los vértices del límite. 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. ${\displaystyle \pm 1}$ ${\displaystyle \pm 2}$
• De lo contrario, el límite debe contener aristas. Además, el número de aristas del límite debe ser impar. ${\displaystyle (+1,-2)}$ ${\displaystyle (+1,-2)}$

Seleccione un borde y revíselo. Hay tres casos: ${\displaystyle (+1,-2)}$

• Ahora estás en un simplex. Hecho. ${\displaystyle (+1,-2,+2)}$
• Ahora estás en un simplex. Hecho. ${\displaystyle (+1,-2,-1)}$
• Estás en un simplex con otra ventaja. Revíselo y continúe. ${\displaystyle (+1,-2)}$

El último caso puede llevarte fuera de la pelota. Sin embargo, dado que el número de aristas en el límite debe ser impar, debe haber una nueva arista no visitada en el límite. Revíselo y continúe. ${\displaystyle (+1,-2)}$ ${\displaystyle (+1,-2)}$

Este paseo debe terminar dentro de la pelota, ya sea en a o en simplex. Hecho. ${\displaystyle (+1,-2,+2)}$ ${\displaystyle (+1,-2,-1)}$

tiempo de ejecución

El tiempo de ejecución del algoritmo descrito anteriormente es polinómico 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 completo incluso para las dimensiones. Esto implica que no hay demasiadas esperanzas de encontrar un algoritmo rápido. ^[6] ${\displaystyle n=2}$

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 demostrar por separado utilizando argumentos totalmente diferentes, pero cada variante también se puede reducir a las demás variantes de su fila. Además, cada resultado de la fila superior se puede deducir del que se encuentra debajo en la misma columna. ^[7]

Ver también

• Combinatoria topológica

Referencias

1. Matoušek, Jiří (2003), Uso del teorema de Borsuk-Ulam , Springer-Verlag , págs. 34–45, ISBN 3-540-00362-2
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
3. 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
4. Freund, Robert M.; Todd, Michael J. (1980), Una prueba constructiva del lema combinatorio de Tucker, archivado desde el original el 22 de junio de 2015.
5. Meunier, Frédéric (2010), Lemas de Sperner y Tucker (PDF) , Blog de algoritmos y teoremas bonitos, págs. 46–64 , consultado el 25 de mayo de 2015
6. Aisenberg, James; Bonet, María Luisa ; Buss, Sam (2015), 2-D Tucker es PPA completo , ECCC  TR15-163
7. Nyman, Kathryn L.; Su, Francis Edward (2013), "Un equivalente de Borsuk-Ulam que implica directamente el lema de Sperner", The American Mathematical Monthly , 120 (4): 346–354, doi :10.4169/amer.math.monthly.120.04.346, JSTOR  10.4169/amer.math.monthly.120.04.346, MR  3035127