Lema de Sperner

El lema de Sperner es un análogo combinatorio del teorema del punto fijo de Brouwer , uno de los principales resultados de la topología combinatoria. Afirma que para cualquier coloración de vértice de Sperner en una triangulación de un símplex n - dimensional , existe una celda de triangulación cuyos vértices están coloreados en todos los colores. El primer resultado de este fue probado por Sperner

Caso unidimensional

En el caso unidimensional, el lema de Sperner puede verse como un análogo discreto del teorema de Bolzano-Cauchy . Ella afirma que si un segmento grande se divide en subsegmentos y se colocan 1 y 2 en los vértices de los segmentos, entonces, siempre que haya diferentes valores en los vértices del segmento grande, hay un segmento de la subdivisión, en los vértices de los cuales hay diferentes valores.

Caso bidimensional

Esta opción es la más común. Está formulado de la siguiente manera:

Dado un triángulo cuyos vértices están rotulados 0, 1 y 2, y su triangulación. Los vértices de la triangulación se etiquetaron con los mismos valores para que cualquier vértice del lado del triángulo original se etiquetara con una de las etiquetas de vértice de ese lado. Entonces necesariamente existe un triángulo de partición etiquetado como 0, 1, 2.

Caso multidimensional

En general, el lema se refiere a la triangulación de un simplex n -dimensional

{\mathcal {A}}=A_{1}A_{2}\ldots A_{{n+1}}.

Considere su triangulación T , que es una partición en simples n -dimensionales más pequeños. Denote la función de color de vértice como , donde S denota el conjunto de vértices de la triangulación T . Una coloración se denomina coloración de Sperner si se cumplen las siguientes reglas: $\mathcal{A}$ ${\displaystyle f\colon S\rightarrow \left\{1,2,3,\dots,n,n+1\right\))$

Los vértices del símplex grande están coloreados de manera diferente, es decir: f ( A i ) = i for 1 ≤ i ≤ n +1.
Esos vértices T que se encuentran en una cara dimensional k del símplex grande

A_{{i_{1}}}A_{{i_{2}}}\ldots A_{{i_{k}}}

pintado en los colores de los vértices que lo forman

f(A_{{i_{1}}}),f(A_{{i_{2}}}),\ldots,f(A_{{i_{k}}}).

Si el coloreado resulta ser Sperner, entonces existe una triangulación simplex T cuyos vértices están coloreados con todos los colores.

Prueba

Si bien el caso unidimensional es obvio, probaremos el caso bidimensional generalizando primero la afirmación. La prueba del caso multidimensional se obtiene de manera similar por inducción.

Considere un gráfico G construido a partir de una triangulación T de la siguiente manera:

Los vértices de G serán los triángulos T y el área fuera del triángulo grande. Conectamos dos vértices con una arista si las regiones que les corresponden tienen un segmento común, cuyos vértices están coloreados 1 y 2. En el lado que conecta los dos vértices de un triángulo grande, coloreado 1 y 2, hay un número impar de segmentos con vértices 1 y 2, lo que significa que , correspondiente a la región exterior es impar. Dado que el gráfico debe tener un número par de vértices de grado impar, hay un número impar (y por lo tanto al menos uno) de vértices de grado impar correspondientes a los triángulos T.

Es fácil comprobar que los posibles grados de los vértices correspondientes a los triángulos son 0, 1 o 2, y 1 corresponde a un triángulo cuyos vértices están coloreados en los tres colores.

En el caso multidimensional, se debe probar exactamente de la misma manera la existencia de un número impar de simples de partición cuyos vértices están coloreados en todos los colores.

Aplicaciones

Sobre la base del lema de Sperner, se construye una de las demostraciones del teorema del punto fijo de Brouwer
Teorema sobre la división de un cuadrado en triángulos de igual área

Literatura

Shashkin Yu. A. Puntos fijos. - Moscú: Nauka, 1989. - 80 p. — (Conferencias populares sobre matemáticas). — ISBN 5-02-013922-X .

Véase también

Enlaces

Prueba del lema (inglés) , Cut-the-knot .
E. Epifanov, Pirate's share , Elementy.ru , 2014. (un ejemplo de la aplicación del lema de Sperner)
O Lema de Musin Sperner: Aplicaciones y generalizaciones. Escuela de Verano "Matemáticas Modernas", 2015, Dubna.