Aplicaciones del lema de Sperner

Question

Siempre me fascinó este resultado. Lema de Sperner es un resultado combinatorio que puede demostrar algunos hechos bastante fuertes, como el teorema del punto fijo de Brouwer. Conozco al menos otra aplicación de este lema, a saber, el teorema de Monsky, que afirma que es imposible diseccionar un cuadrado en un número impar de triángulos que tengan áreas iguales.

Hojeando algunas preguntas esta tarde he encontrado dos referencias al lema de Sperner con respecto a aplicaciones totalmente diferentes. He buscado en el sitio y no he encontrado ninguna pregunta que se refiera a otras aplicaciones del lema de Sperner, así que he pensado en plantear la pregunta yo mismo.

¿Qué otras aplicaciones tiene el lema de Sperner?

(Hice la pregunta wiki de la comunidad).

Answer 1

Francis Su escribió un artículo titulado Alquiler Armonía: El lema de Sperner en la división equitativa que, como su nombre indica, utiliza el lema de Sperner para resolver algunos problemas de división justa. Es el trabajo ganador del premio Merten Hasse 2001, y como tal se puede encontrar gratuitamente aquí

Answer 2

Ron Aharoni y Penny Haxell han aplicado el lema de Sperner a complejos simpliciales asociados a familias de hipergrafos para demostrar varios resultados sobre transversales independientes. En particular, obtienen una demostración topológica del teorema de Hall. A continuación un papel y una visión general en el blog de Gil Kalai .

Answer 3

No estoy seguro de si esto es una "aplicación", pero el problema de encontrar un triángulo de Sperner es completo para la clase de complejidad PPAD que contiene los problemas de encontrar un punto fijo de Brouwer aproximado, calcular un equilibrio de Nash aproximado o un equilibrio de Arrow-Debreu aproximado, y muchos otros . Por lo tanto, un algoritmo para encontrar un triángulo de Sperner también permite calcular soluciones a estos otros problemas "con la misma rapidez". (Por ejemplo, el artículo publicado por Thierry puede interpretarse como una demostración de que el problema de la división justa considerado está en PPAD).

En particular, el Lemma de Sperner (el hecho de que exista tal triángulo) implica que existe una solución para cada problema en PPAD; así por ejemplo, el Lemma de Sperner implica la Borsuk-Ulam y el teorema sándwich de jamón teorema.

Se trata de un razonamiento un tanto retrógrado, ya que colocamos un problema en PPAD sólo después de saber que su solución (por ejemplo, el hiperplano de corte sándwich o el punto fijo de Brouwer) debe existir. Pero aún así, el Lemma de Sperner implica un teorema de existencia para cada problema en PPAD y la prueba se puede dar mediante la reducción de la cuestión de encontrar una solución a ese problema a la cuestión de encontrar un Triángulo de Sperner.

Answer 4

El teorema de Poincaré-Miranda es una aplicación de la versión cúbica o politópica del lema de Sperner. Para las pruebas, pueden consultarse los interesantes artículos siguientes, de C. Ahlbach: https://scholarship.claremont.edu/cgi/viewcontent.cgi?article=1048&context=hmc_theses

y por M. Müger: https://arxiv.org/pdf/1310.8090.pdf

Este último artículo también demuestra el teorema de la invariancia de dimensión (dos conjuntos abiertos en espacios euclidianos sólo pueden ser homeomórficos si ambas dimensiones coinciden) utilizando el lema de Sperner.

Answer 5

Tamás Király y Júlia Pap utilizaron el lema de Sperner para pruebe que todo grafo perfecto con orientación clico-cíclica tiene un núcleo. Clico-cíclico significa que ninguna camarilla contiene un ciclo dirigido propio o, lo que es lo mismo, que toda camarilla tiene un nodo origen. Un núcleo es un subconjunto dominante e independiente de los vértices.

En concreto, para un gráfico $G=(V,E)$ consideraron el politopo $P$ en las combinaciones lineales formales de los vértices $(v_1,v_2,...,v_n)$ definido como

$$P=\text{STAB}(G)-\mathbb{R}_+^n$$

donde $\text{STAB}(G)=\{x\in \mathbb{R}^n|\sum_{c \in C}x(c)\leq 1 \text{ for every clique } C\}$ .

Por un conocido resultado sobre grafos perfectos*, los vértices de $P$ corresponde a conjuntos máximos independientes. Colorearon las facetas de $P$ con el nodo origen de la camarilla definidora de la faceta. Encontrando un vértice multicolor de $P$ llegaron a la conclusión de que el vértice corresponde a un núcleo de $G$ .

Nótese que los autores utilizaron un dual polar del lema original de Sperner; por eso colorearon facetas y encontraron un vértice multicolor, y no al revés.

*Ver ce : "Las desigualdades (4.1) y (4.3) bastan para describir $\text{STAB}(G)$ si $G$ es perfecto".