Lema de Tucker

Análogo combinatorio del teorema de Borsuk-Ulam

En este ejemplo, donde n=2, el 1-símplex rojo tiene vértices que están etiquetados con el mismo número con signos opuestos. El lema de Tucker establece que para que se produzca una triangulación de este tipo debe existir al menos un 1-símplex de este tipo.

En matemáticas , el lema de Tucker es un análogo combinatorio del teorema de Borsuk-Ulam , llamado así en honor a Albert W. Tucker .

Sea T una triangulación de la bola n -dimensional cerrada . Supongamos que T es antípoda simétrica en la esfera límite . Eso significa que el subconjunto de símplices de T que están en proporciona una triangulación de donde si σ es un símplex 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 por 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 no fueron constructivas, por contradicción. ^[2]

Más tarde se encontraron pruebas constructivas, que también proporcionaron algoritmos para encontrar la arista complementaria. ^{[3] [4]} Básicamente, los algoritmos se basan en trayectorias: comienzan en un cierto punto o arista de la triangulación, luego pasan de símplex a símplex según reglas prescritas, hasta que no es posible continuar más. Se puede demostrar que la trayectoria debe terminar en un símplex que contenga una arista complementaria.

Una prueba más sencilla del lema de Tucker utiliza el lema de Ky Fan más general , que tiene una prueba algorítmica simple.

La siguiente descripción ilustra el algoritmo para . ^[5] Nótese que en este caso es un disco y hay 4 etiquetas posibles: , como la figura en la parte superior derecha. ${\displaystyle n=2}$ ${\displaystyle B_{n}}$ ${\displaystyle -2,-1,1,2}$

Comience fuera de la bola 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 en el límite debe ser impar. ${\displaystyle (+1,-2)}$ ${\displaystyle (+1,-2)}$

Seleccione un borde y atraviéselo. Existen tres casos: ${\displaystyle (+1,-2)}$

• Ahora estás en un símplex. Listo. ${\displaystyle (+1,-2,+2)}$
• Ahora estás en un símplex. Listo. ${\displaystyle (+1,-2,-1)}$
• Estás en un símplex con otra arista. Recorre el mismo y continúa. ${\displaystyle (+1,-2)}$

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

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

Tiempo de ejecución

El tiempo de ejecución del algoritmo descrito anteriormente es polinomial en el tamaño de la 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 la triangulación. Sin embargo, el problema de encontrar una arista complementaria es PPA -completo incluso para las dimensiones. Esto implica que no hay demasiadas esperanzas de encontrar un algoritmo rápido. ^[6] ${\displaystyle n=2}$

Resultados equivalentes

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 se puede demostrar por separado utilizando argumentos totalmente diferentes, pero cada variante también se puede reducir a las otras 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]

Véase 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. First Canadian Math. Congress, 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 , MR  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) , Algorithms and Pretty Theorems Blog, págs. 46–64 , consultado el 25 de mayo de 2015
6. Aisenberg, James; Bonet, Maria 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