El lema de Sperner

En una dimensión, el lema de Sperner puede considerarse una versión discreta del teorema del valor intermedio . En este caso, básicamente afirma que si una función discreta solo toma los valores 0 y 1, comienza en el valor 0 y termina en el valor 1, entonces debe cambiar de valor un número impar de veces.

El caso bidimensional es al que se hace referencia con mayor frecuencia. Se enuncia de la siguiente manera:

Subdividimos arbitrariamente un triángulo ABC en una triangulación que consta de triángulos más pequeños que se unen borde con borde. Entonces, una coloración de Sperner de la triangulación se define como una asignación de tres colores a los vértices de la triangulación tal que

1. Cada uno de los tres vértices A , B y C del triángulo inicial tiene un color distinto.
2. Los vértices que se encuentran a lo largo de cualquier arista del triángulo ABC tienen solo dos colores, los dos colores en los extremos de la arista. Por ejemplo, cada vértice en AC debe tener el mismo color que A o C.

Entonces, cada coloración de Sperner de cada triangulación tiene al menos un "triángulo arcoíris", un triángulo más pequeño en la triangulación cuyos vértices están coloreados con los tres colores diferentes. Más precisamente, debe haber un número impar de triángulos arcoíris.

En el caso general, el lema se refiere a un simplex n -dimensional :

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

Consideremos cualquier triangulación T , una división disjunta de${\displaystyle {\mathcal {A}}}$en símplices n- dimensionales más pequeños, que se encuentran de nuevo cara a cara. Denotemos la función de coloración como:

${\displaystyle f:S\to \{1,2,3,\dots ,n,n+1\},}$

donde S es el conjunto de vértices de T. Una función de coloración define una coloración de Sperner cuando:

1. Los vértices del simplex grande están coloreados con diferentes colores, es decir, sin pérdida de generalidad , f ( A _i ) = i para 1 ≤ i ≤ n + 1 .
2. Vértices de T ubicados en cualquier subcara k- dimensional del símplex grande

${\displaystyle A_{i_{1}}A_{i_{2}}\ldots A_{i_{k+1}}}$

están coloreados únicamente con los colores

${\displaystyle i_{1},i_{2},\ldots ,i_{k+1}.}$

Entonces, cada coloración de Sperner de cada triangulación del símplex n- dimensional tiene un número impar de instancias de un símplex arcoíris , es decir, un símplex cuyos vértices están coloreados con los n + 1 colores. En particular, debe haber al menos un símplex arcoíris.

Primero abordaremos el caso bidimensional. Consideremos un grafo G construido a partir de la triangulación T de la siguiente manera:

Los vértices de G son los elementos de T más el área fuera del triángulo. Dos vértices están conectados por una arista si sus áreas correspondientes comparten un borde común, con un extremo coloreado de 1 y el otro de 2.

Nótese que en el intervalo AB hay un número impar de bordes coloreados 1-2 (simplemente porque A está coloreado 1, B está coloreado 2; y a medida que avanzamos a lo largo de AB , debe haber un número impar de cambios de color para obtener colores diferentes al principio y al final). En los intervalos BC y CA, no hay bordes coloreados 1-2 en absoluto. Por lo tanto, el vértice de G correspondiente al área exterior tiene un grado impar. Por el lema del apretón de manos , G tiene un número par de vértices con grado impar. Por lo tanto, el grafo restante, excluyendo el área exterior, tiene un número impar de vértices con grado impar correspondientes a miembros de T.

Se puede ver fácilmente que el único grado posible de un triángulo de T es 0, 1 o 2, y que el grado 1 corresponde a un triángulo coloreado con los tres colores 1, 2 y 3.

De este modo, hemos obtenido una conclusión ligeramente más contundente, que afirma que en una triangulación T hay un número impar (y al menos uno) de triángulos completamente coloreados.

Un caso multidimensional puede demostrarse por inducción sobre la dimensión de un símplex. Aplicamos el mismo razonamiento que en el caso bidimensional para concluir que en una triangulación n- dimensional existe un número impar de símplex completamente coloreados.

Aquí se presenta una ampliación de la demostración dada anteriormente, para un lector que se inicia en la teoría de grafos .

Este diagrama numera los colores de los vértices del ejemplo anterior. Los triángulos pequeños cuyos vértices tienen números diferentes aparecen sombreados en el gráfico. Cada triángulo pequeño se convierte en un nodo del nuevo gráfico derivado de la triangulación. Las letras minúsculas identifican las áreas: ocho dentro de la figura y el área i designa el espacio fuera de ella.

Como se describió anteriormente, los nodos que comparten una arista cuyos extremos están numerados como 1 y 2 se unen en el grafo derivado. Por ejemplo, el nodo d comparte una arista con el área exterior i , y sus vértices tienen números diferentes, por lo que también se sombrea. El nodo b no se sombrea porque dos de sus vértices tienen el mismo número, pero se une al área exterior.

Se podría añadir un nuevo triángulo numerado, por ejemplo, insertando un nodo numerado 3 en la arista entre 1 y 1 del nodo a , y uniendo ese nodo al otro vértice de a . Para ello, habría que crear un par de nodos nuevos, como en el caso de los nodos f y g .

Andrew McLennan y Rabee Tourky presentaron una demostración diferente, utilizando el volumen de un simplex . Se lleva a cabo en un solo paso, sin inducción. ^{[ 2 ] [ 3 ]}

Supongamos que cada vértice de la triangulación puede ser etiquetado con múltiples colores, de modo que la función de coloración sea F  : S → 2 ^{[ n +1]} .

Para cada subsímplex, el conjunto de etiquetas en sus vértices es una familia de conjuntos sobre el conjunto de colores [ n + 1] . Esta familia de conjuntos puede verse como un hipergrafo .

Si, para cada vértice v en una cara del símplex, los colores en f ( v ) son un subconjunto del conjunto de colores en los extremos de la cara, entonces existe un subsímplex con un etiquetado equilibrado , es decir, un etiquetado en el que el hipergrafo correspondiente admite un emparejamiento fraccional perfecto . Para ilustrarlo, aquí hay algunos ejemplos de etiquetado equilibrado para n = 2 :

• ({1}, {2}, {3}) - equilibrado por los pesos (1, 1, 1) .
• ({1,2}, {2,3}, {3,1}) - equilibrado por los pesos (1/2, 1/2, 1/2) .
• ({1,2}, {2,3}, {1}) - equilibrado por los pesos (0, 1, 1) .

Esto fue demostrado por Shapley en 1973. ^{[ 5 ]} Es un análogo combinatorio del lema KKMS .

Supongamos que tenemos un politopo P de dimensión d con n vértices. P está triangulado, y cada vértice de la triangulación está etiquetado con una etiqueta del conjunto {1, …, n }. Cada vértice principal i está etiquetado con i . Un subsímplex se denomina completamente etiquetado si es de dimensión d , y cada uno de sus d + 1 vértices tiene una etiqueta diferente. Si cada vértice de una cara F de P está etiquetado con una de las etiquetas de los extremos de F , entonces existen al menos n – d símplices completamente etiquetados. Algunos casos especiales son:

• d = n – 1. En este caso, P es un símplex. El lema de Sperner politópico garantiza que existe al menos un símplex completamente etiquetado. Es decir, se reduce al lema de Sperner.
• d = 2 . Supongamos que un polígono bidimensionalcon n vértices se triangula y se etiqueta usando las etiquetas 1, …, n de tal manera que, en cada cara entre el vértice i y el vértice i + 1 (mod n ) , solo se usan las etiquetas i e i + 1. Entonces, hay al menos n – 2 subtriángulos en los que se usan tres etiquetas diferentes.

La afirmación general fue conjeturada por Atanassov en 1996, quien la demostró para el caso d = 2. [ ^{6 ] La} demostración del caso general fue dada por primera vez por de Loera, Peterson y Su en 2002. ^{[ 7 ]} Proporcionan dos demostraciones: la primera no es constructiva y utiliza la noción de conjuntos de guijarros ; la segunda es constructiva y se basa en argumentos de seguimiento de caminos en grafos .

Meunier ^{[ 8 ]} extendió el teorema de politopos a cuerpos politópicos, que no necesariamente son convexos o simplemente conexos. En particular, si P es un politopo, entonces el conjunto de sus caras es un cuerpo politópico. En cada etiquetado de Sperner de un cuerpo politópico con vértices v1 _, …, vn _, hay al menos:

${\displaystyle nd-1+\left\lceil {\frac {\min _{i=1}^{n}\deg _{B(P)}(v_{i})}{d}}\right\rceil }$

Símplices completamente etiquetados de tal manera que cualquier par de estos símplices recibe dos etiquetas diferentes. El grado deg _{B ( P )} ( v _i ) es el número de aristas de B ( P ) a las que pertenece v _i . Dado que el grado es al menos d , el límite inferior es al menos n – d . Pero puede ser mayor. Por ejemplo, para el politopo cíclico en 4 dimensiones con n vértices, el límite inferior es:

${\displaystyle n-4-1+\left\lceil {\frac {n-1}{4}}\right\rceil \approx {\frac {5}{4}}n.}$

Musin ^{[ 9 ]} extendió aún más el teorema a variedades lineales por partes de dimensión d , con o sin frontera.

Asada, Frick, Pisharody, Polevy, Stoner, Tsang y Wellner ^{[ 10 ]} extendieron aún más el teorema a pseudovariedades con frontera y mejoraron la cota inferior del número de facetas con etiquetas distintas por pares.

Supongamos que, en lugar de un símplex triangulado en subsímplices, tenemos un cubo n- dimensional particionado en cubos n- dimensionales más pequeños.

Harold W. Kuhn ^{[ 11 ]} demostró el siguiente lema. Supongamos que el cubo [0, M ] ⁿ , para algún entero M , se particiona en M ⁿ cubos unitarios. Supongamos que cada vértice de la partición se etiqueta con una etiqueta de {1, …, n + 1}, de tal manera que para cada vértice v : (1) si v _i = 0 entonces la etiqueta en v es como máximo i ; (2) si v _i = M entonces la etiqueta en v no es i . Entonces existe un cubo unitario con todas las etiquetas {1, …, n + 1} (algunas de ellas más de una vez). El caso especial n = 2 es: supongamos que un cuadrado se particiona en subcuadrados, y cada vértice se etiqueta con una etiqueta de {1,2,3}. La arista izquierda se etiqueta con 1 (= como máximo 1); la arista inferior se etiqueta con 1 o 2 (= como máximo 2); El borde superior está etiquetado con 1 o 3 (= no 2); y el borde derecho está etiquetado con 2 o 3 (= no 1). Luego hay un cuadrado etiquetado con 1, 2, 3.

Otra variante, relacionada con el teorema de Poincaré-Miranda , ^{[ 12 ]} es la siguiente. Supongamos que el cubo [0, M ] ⁿ se particiona en M ⁿ cubos unitarios. Supongamos que cada vértice está etiquetado con un vector binario de longitud n , tal que para cada vértice v : (1) si v _i = 0 entonces la coordenada i de la etiqueta en v es 0; (2) si v _i = M entonces la coordenada i de la etiqueta en v es 1; (3) si dos vértices son vecinos, entonces sus etiquetas difieren como máximo en una coordenada. Entonces existe un cubo unitario en el que todas las 2 ⁿ etiquetas son diferentes. En dos dimensiones, otra forma de formular este teorema es: ^{[ 13 ]} en cualquier etiquetado que satisfaga las condiciones (1) y (2), hay al menos una celda en la que la suma de las etiquetas es 0 [una celda unidimensional con etiquetas (1,1) y (-1,-1) , o una celda bidimensional con las cuatro etiquetas diferentes].

Wolsey ^{[ 14 ]} reforzó estos dos resultados al demostrar que el número de cubos completamente etiquetados es impar.

Musin ^{[ 13 ]} extendió estos resultados a cuadrangulaciones generales .

Supongamos que, en lugar de un único etiquetado, tenemos n etiquetados de Sperner diferentes. Consideramos pares (símplex, permutación) tales que la etiqueta de cada vértice del símplex se elige de un etiquetado diferente (por lo que para cada símplex hay n ! pares diferentes). Entonces hay al menos n ! ​​pares completamente etiquetados. Esto fue demostrado por Ravindra Bapat ^{[ 15 ]} para cualquier triangulación. Una demostración más simple, que solo funciona para triangulaciones específicas, fue presentada posteriormente por Su. ^{[ 16 ]}

Otra forma de enunciar este lema es la siguiente. Supongamos que hay n personas, cada una de las cuales produce una etiqueta de Sperner diferente para la misma triangulación. Entonces, existe un simplex y una correspondencia entre las personas y sus vértices, de tal manera que cada vértice es etiquetado de forma diferente por su propietario (una persona etiqueta su vértice con 1, otra con 2, etc.). Además, existen al menos n ! ​​de estas correspondencias. Esto puede utilizarse para encontrar un método de corte de pastel sin envidia con piezas conectadas.

Asada, Frick, Pisharody, Polevy, Stoner, Tsang y Wellner ^{[ 10 ]} extendieron este teorema a pseudovariedades con frontera.

De forma más general, supongamos que tenemos m etiquetas de Sperner diferentes, donde m puede ser diferente de n . Entonces: ^{[ 17 ] : Teorema 2.1}

1. Para cualesquiera enteros positivos k ₁ , …, k _m cuya suma sea m + n – 1 , existe un baby-símplex en el que, para cada i ∈ {1, …, m }, el etiquetador número i utiliza al menos k _i (de un total de n ) etiquetas distintas. Además, cada etiqueta es utilizada por al menos un (de un total de m ) etiquetador.
2. Para cualesquiera enteros positivos I ₁ , …, I _m cuya suma sea m + n – 1 , existe un baby-simplex en el que, para cada j ∈ {1, …, n }, , la etiqueta j es utilizada por al menos l _j (de m ) etiquetados diferentes.

Ambas versiones se reducen al lema de Sperner cuando m = 1 , o cuando todos los m etiquetados son idénticos.

Véase ^{[ 18 ]} para generalizaciones similares.

Brown y Cairns ^{[ 19 ]} reforzaron el lema de Sperner al considerar la orientación de los símplices. Cada subsímplice tiene una orientación que puede ser +1 o -1 (si está completamente etiquetado), o 0 (si no lo está). Demostraron que la suma de todas las orientaciones de los símplices es +1. En particular, esto implica que existe un número impar de símplices completamente etiquetados.

Como ejemplo para n = 3 , supongamos que se triangula un triángulo y se etiqueta con {1,2,3}. Consideremos la secuencia cíclica de etiquetas en el borde del triángulo. Definimos el grado de la etiquetación como el número de cambios de 1 a 2, menos el número de cambios de 2 a 1. Véanse los ejemplos en la tabla de la derecha. Nótese que el grado es el mismo si contamos los cambios de 2 a 3 menos los de 3 a 2, o de 3 a 1 menos los de 1 a 3.

Musin demostró que el número de triángulos completamente etiquetados es al menos igual al grado del etiquetado . ^{[ 20 ]} En particular, si el grado es distinto de cero, entonces existe al menos un triángulo completamente etiquetado.

Si una etiqueta satisface la condición de Sperner, entonces su grado es exactamente 1: solo existen intercambios 1-2 y 2-1 en el lado entre los vértices 1 y 2, y el número de intercambios 1-2 debe ser uno más que el número de intercambios 2-1 (al caminar del vértice 1 al vértice 2). Por lo tanto, el lema original de Sperner se deduce del teorema de Musin.

Existe un lema similar sobre árboles y ciclos finitos e infinitos . ^{[ 21 ]}