Lema de Tucker

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 13 de febrero de 2021; la verificación requiere 1 edición .

El lema de Tucker es un análogo combinatorio del teorema de Borsuk-Ulam , llamado así por Albert W. Tucker .

La esencia del lema es la siguiente:

Sea T una triangulación de una bola cerrada de n dimensiones . Suponga que T es antípoda simétrica en el límite de la esfera . Esto quiere decir que el subconjunto de triangulación simplex yaciendo sobre forma una triangulación de la esfera , y si el simplex σ pertenece a esta triangulación, entonces -σ también le pertenece (para la figura de la derecha, los simples sobre el círculo son arcos, por lo que la condición descrita anteriormente significa que para cada arco tiene un arco simétrico con respecto al centro del círculo). $B_{n}$ $S_{{n-1}}$ $S_{{n-1}}$ $S_{{n-1}}$

Sea el etiquetado de los vértices de la triangulación T que satisface la condición de paridad en , es decir, para cualquier vértice . Entonces el lema de Tucker establece que la triangulación T contiene una arista con etiquetas opuestas , es decir, una arista (1-simplex) cuyos vértices están etiquetados con el mismo número pero con diferente signo [1] . ${\displaystyle L:V(T)\to \{+1,-1,+2,-2,...,+n,-n\))$ $S_{{n-1}}$ $L(-v)=-L(v)$ $v\en S_{n-1}$

Evidencia

La primera prueba era no constructiva (prueba por contradicción) [2] .

Posteriormente se encontró una prueba constructiva, la cual viene dada por un algoritmo que encuentra una arista con etiquetas opuestas [3] [4] . Esencialmente, los algoritmos se basan en rutas: comienzan en algún punto o borde de la triangulación y proceden de símplex a símplex de acuerdo con las reglas prescritas mientras el proceso aún está en curso. Se puede demostrar que el camino debe terminar en un símplex que contiene una arista con etiquetas opuestas.

Una prueba simple del lema de Tucker utiliza el lema de Ki 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 con 4 etiquetas posibles: , como en la figura anterior. $n=2$ $B_{n}$ ${\ estilo de visualización -2, -1,1,2}$

Comencemos fuera de la pelota y miremos las etiquetas en el límite. Dado que la etiqueta es una función impar en el límite, el límite debe contener etiquetas positivas y negativas:

Si el límite contiene solo o solo , entonces el límite debe contener un borde con etiquetas opuestas. QED $\pm 1$ $\pm2$
De lo contrario, el borde debe contener bordes. Además, el número de tales aristas en el límite debe ser impar. ${\ estilo de visualización (+1, -2)}$ ${\ estilo de visualización (+1, -2)}$

Seleccionemos un borde y vayamos a través de él. Puede haber tres casos: ${\ estilo de visualización (+1, -2)}$

Llegamos al simplex . QED ${\ estilo de visualización (+1, -2, +2)}$
Llegamos al simplex . QED ${\ estilo de visualización (+1,-2,-1)}$
Estamos en un simplex con otra arista . Pasamos por este borde y continuamos el proceso. ${\ estilo de visualización (+1, -2)}$

Como resultado, podemos terminar fuera del círculo. Sin embargo, dado que el número de aristas en el límite es impar, debe haber una nueva arista no visitada anteriormente en el límite. Lo revisamos y continuamos el proceso. ${\ estilo de visualización (+1, -2)}$ ${\ estilo de visualización (+1, -2)}$

El viaje debe terminar dentro del círculo ya sea en el simplex a o en el simplex . QED ${\ estilo de visualización (+1, -2, +2)}$ ${\ estilo de visualización (+1,-2,-1)}$

Horario de apertura

El tiempo de ejecución del algoritmo descrito es polinomial en las dimensiones de la triangularización. Esto se considera inválido porque la triangularización puede ser muy grande. Sería bueno encontrar un algoritmo que funcione en el tiempo logarítmico del tamaño de la triangularización. Sin embargo, el problema de encontrar un borde con etiquetas opuestas es PPA-hard incluso para dimension . De ello se deduce que encontrar tal algoritmo es poco probable [6] . $n=2$

Resultados equivalentes

Hay varios teoremas de punto fijo que vienen en tres versiones equivalentes: la variante de topología algebraica , la variante combinatoria y la variante de cobertura de conjuntos. Cada opción se puede probar por separado usando argumentos completamente diferentes, pero cada opción se puede reducir a otra opción en la misma línea. Además, cada resultado de la fila superior se puede inferir del resultado de la fila inferior en la misma columna [7] .

topología aglebraica	combinatoria	Juegos de revestimiento
Teorema del punto fijo de Brouwer	Lema de Sperner	Lema de Knaster-Kuratovsky-Mazurkiewicz
Teorema de Borsuk-Ulam	Lema de Tucker	Teorema de Lyusternik-Shnirelman

Véase también

Combinatoria topológica

Notas

↑ Matousek, 2003 , pág. 34–45.
↑ Tucker, 1946 , pág. 285–309.
↑ Freund, Todd, 1981 , pág. 321–325.
↑ Freund, Todd, 1980 .
↑ Meunier, 2010 , pág. 46–64.
↑ Aisenberg, Bonet, Buss, 2015 .
↑ Kathryn L. Nyman, Francis Edward Su. Un equivalente de Borsuk-Ulam que implica directamente el lema de Sperner // American Mathematical Monthly . - 2013. - T. 120 , núm. 4 . — S. 346–354 . -doi : 10.4169 / amer.math.monthly.120.04.346 .

Literatura

Matousek Jiri. Usando el teorema de Borsuk-Ulam. — Springer-Verlag , 2003. — ISBN 3-540-00362-2 .
Albert W. Tucker . Algunas propiedades topológicas del disco y la esfera // Proc. Primera matemática canadiense. Congreso, Montreal, 1945. - Toronto: University of Toronto Press , 1946.
Robert M. Freund, Michael J. Todd. Una prueba constructiva del lema combinatorio de Tucker // Journal of Combinatorial Theory . - 1981. - T. 30 , núm. 3 . - doi : 10.1016/0097-3165(81)90027-3 .
Robert M. Freund, Michael J. Todd. Una demostración constructiva del lema combinatorio de Tucker . — 1980.
Federico Meunier. Lemas de Sperner y Tucker . — Blog de algoritmos y teoremas bonitos, 2010.
James Aisenberg, María Luisa Bonet, Sam Buss. 2-D Tucker es PPA completo. — 2015.