Teorema de Sperner

El teorema de Sperner , en matemáticas discretas , describe las familias más grandes posibles de conjuntos finitos , ninguna de las cuales contiene otros conjuntos en la familia. Es uno de los resultados centrales de la teoría de conjuntos extremos . Recibe su nombre en honor a Emanuel Sperner , quien lo publicó en 1928.

Este resultado se denomina a veces lema de Sperner, pero el nombre " lema de Sperner " también hace referencia a un resultado no relacionado sobre la coloración de triangulaciones. Para diferenciar los dos resultados, el resultado sobre el tamaño de una familia de Sperner se conoce ahora más comúnmente como teorema de Sperner.

Declaración

Una familia de conjuntos en la que ninguno de los conjuntos es un subconjunto estricto de otro se denomina familia de Sperner , o anticadena de conjuntos, o desorden. Por ejemplo, la familia de subconjuntos de k elementos de un conjunto de n elementos es una familia de Sperner. Ningún conjunto de esta familia puede contener a ninguno de los otros, porque un conjunto contenedor tiene que ser estrictamente mayor que el conjunto que contiene, y en esta familia todos los conjuntos tienen el mismo tamaño. El valor de k que hace que este ejemplo tenga tantos conjuntos como sea posible es n /2 si n es par, o cualquiera de los enteros más cercanos a n /2 si n es impar. Para esta elección, el número de conjuntos en la familia es . ${\displaystyle {\tbinom {n}{\lfloor n/2\rfloor }}}$

El teorema de Sperner establece que estos ejemplos son las familias de Sperner más grandes posibles en un conjunto de n elementos. Formalmente, el teorema establece que,

1. para cada familia de Sperner S cuya unión tiene un total de n elementos, y ${\displaystyle |S|\leq {\binom {n}{\lfloor n/2\rfloor }},}$
2. La igualdad se cumple si y sólo si S consta de todos los subconjuntos de un conjunto de n elementos que tienen tamaño o todos los que tienen tamaño . ${\displaystyle \lfloor n/2\rfloor }$ ${\displaystyle \lceil n/2\rceil }$

Órdenes parciales

El teorema de Sperner también puede enunciarse en términos de ancho de orden parcial . La familia de todos los subconjuntos de un conjunto de n elementos (su conjunto potencia ) puede ordenarse parcialmente por inclusión de conjuntos; en este orden parcial, se dice que dos elementos distintos son incomparables cuando ninguno de ellos contiene al otro. El ancho de un orden parcial es el mayor número de elementos en una anticadena , un conjunto de elementos incomparables por pares. Traduciendo esta terminología al lenguaje de los conjuntos, una anticadena es simplemente una familia de Sperner, y el ancho del orden parcial es el número máximo de conjuntos en una familia de Sperner. Por lo tanto, otra forma de enunciar el teorema de Sperner es que el ancho del orden de inclusión en un conjunto potencia es . ${\displaystyle {\binom {n}{\lfloor n/2\rfloor }}}$

Se dice que un conjunto parcialmente ordenado graduado tiene la propiedad de Sperner cuando una de sus anticadenas más grandes está formada por un conjunto de elementos que tienen todos el mismo rango. En esta terminología, el teorema de Sperner establece que el conjunto parcialmente ordenado de todos los subconjuntos de un conjunto finito, parcialmente ordenado por inclusión de conjuntos, tiene la propiedad de Sperner.

Prueba

Hay muchas pruebas del teorema de Sperner, cada una de las cuales conduce a diferentes generalizaciones (véase Anderson (1987)).

La siguiente demostración se debe a Lubell (1966). Sea s _k el número de k conjuntos en S . Para todo 0 ≤ k ≤ n ,

${\displaystyle {n \choose \lfloor {n/2}\rfloor }\geq {n \choose k}}$

y, por lo tanto,

${\displaystyle {s_{k} \over {n \choose \lfloor {n/2}\rfloor }}\leq {s_{k} \over {n \choose k}}.}$

Dado que S es una anticadena, podemos sumar la desigualdad anterior desde k = 0 hasta n y luego aplicar la desigualdad LYM para obtener

${\displaystyle \sum _{k=0}^{n}{s_{k} \over {n \choose \lfloor {n/2}\rfloor }}\leq \sum _{k=0}^{n}{s_{k} \over {n \choose k}}\leq 1,}$

lo que significa

${\displaystyle |S|=\sum _{k=0}^{n}s_{k}\leq {n \choose \lfloor {n/2}\rfloor }.}$

Esto completa la prueba de la parte 1.

Para que haya igualdad, todas las desigualdades en la prueba anterior deben ser igualdades.

${\displaystyle {n \choose \lfloor {n/2}\rfloor }={n \choose k}}$

si y sólo si o concluimos que la igualdad implica que S consiste únicamente en conjuntos de tamaños o Para n par, eso concluye la prueba de la parte 2. ${\displaystyle k=\lfloor {n/2}\rfloor }$ ${\displaystyle \lceil {n/2}\rceil ,}$ ${\displaystyle \lfloor {n/2}\rfloor }$ ${\displaystyle \lceil {n/2}\rceil .}$

Para n impar hay más trabajo por hacer, que omitimos aquí porque es complicado. Véase Anderson (1987), págs. 3-4.

Generalizaciones

Hay varias generalizaciones del teorema de Sperner para subconjuntos del conjunto aleatorio de todos los subconjuntos de E . ${\displaystyle {\mathcal {P}}(E),}$

Sin cadenas largas

Una cadena es una subfamilia que está totalmente ordenada, es decir, (posiblemente después de la renumeración). La cadena tiene r + 1 miembros y longitud r . Una familia r -libre de cadenas (también llamada r -familia ) es una familia de subconjuntos de E que no contiene ninguna cadena de longitud r . Erdős (1945) demostró que el tamaño más grande de una familia r -libre de cadenas es la suma de los r coeficientes binomiales más grandes . El caso r = 1 es el teorema de Sperner. ${\displaystyle \{S_{0},S_{1},\dots ,S_{r}\}\subseteq {\mathcal {P}}(E)}$ ${\displaystyle S_{0}\subset S_{1}\subset \dots \subset S_{r}}$ ${\displaystyle {\binom {n}{i}}}$

pag-composiciones de un conjunto

En el conjunto de p -tuplas de subconjuntos de E , decimos que una p -tupla es ≤ otra, si para cada i = 1,2,..., p . Llamamos p - composición de E a una de las combinaciones de los conjuntos que forman una partición de E . Meshalkin (1963) demostró que el tamaño máximo de una anticadena de p -composiciones es el coeficiente p -multinomial más grande , es decir, el coeficiente en el que todos los n _i son lo más iguales posible (es decir, difieren como máximo en 1). Meshalkin demostró esto demostrando una desigualdad LYM generalizada. ${\displaystyle {\mathcal {P}}(E)^{p}}$ ${\displaystyle (S_{1},\dots ,S_{p})}$ ${\displaystyle (T_{1},\dots ,T_{p}),}$ ${\displaystyle S_{i}\subseteq T_{i}}$ ${\displaystyle (S_{1},\dots ,S_{p})}$ ${\displaystyle S_{1},\dots ,S_{p}}$ ${\displaystyle {\binom {n}{n_{1}\ n_{2}\ \dots \ n_{p}}},}$

El caso p = 2 es el teorema de Sperner, porque entonces y las suposiciones se reducen a que los conjuntos son una familia de Sperner. ${\displaystyle S_{2}=E\setminus S_{1}}$ ${\displaystyle S_{1}}$

No se permiten cadenas largaspag-composiciones de un conjunto

Beck y Zaslavsky (2002) combinaron los teoremas de Erdös y Meshalkin adaptando la prueba de Meshalkin de su desigualdad LYM generalizada. Demostraron que el tamaño más grande de una familia de p -composiciones tales que los conjuntos en la posición i -ésima de las p -tuplas, ignorando las duplicaciones, están libres de r -cadenas, para cada (pero no necesariamente para i = p ), no es mayor que la suma de los coeficientes p -multinomiales más grandes . ${\displaystyle i=1,2,\dots ,p-1}$ ${\displaystyle r^{p-1}}$

Análogo de geometría proyectiva

En la geometría proyectiva finita PG( d , F _q ) de dimensión d sobre un cuerpo finito de orden q , sea la familia de todos los subespacios. Cuando está parcialmente ordenada por inclusión de conjuntos, esta familia es una red. Rota y Harper (1971) demostraron que el tamaño más grande de una anticadena en es el coeficiente gaussiano más grande ; este es el análogo de geometría proyectiva, o q -análogo , del teorema de Sperner. ${\displaystyle {\mathcal {L}}(p,F_{q})}$ ${\displaystyle {\mathcal {L}}(p,F_{q})}$ ${\displaystyle {\begin{bmatrix}d+1\\k\end{bmatrix}};}$

Demostraron además que el tamaño más grande de una familia sin cadenas r es la suma de los coeficientes gaussianos más grandes . Su prueba se basa en un análogo proyectivo de la desigualdad LYM. ${\displaystyle {\mathcal {L}}(p,F_{q})}$

No se permiten cadenas largaspag-composiciones de un espacio proyectivo

Beck y Zaslavsky (2003) obtuvieron una generalización similar a Meshalkin del teorema de Rota-Harper. En PG( d , F _q ), una secuencia Meshalkin de longitud p es una secuencia de subespacios proyectivos tal que ningún subespacio propio de PG( d , F _q ) los contiene a todos y sus dimensiones suman . El teorema es que una familia de secuencias Meshalkin de longitud p en PG( d , F _q ), tal que los subespacios que aparecen en la posición i de las secuencias no contienen ninguna cadena de longitud r para cada uno no es mayor que la suma de la mayor de las cantidades ${\displaystyle (A_{1},\ldots ,A_{p})}$ ${\displaystyle d-p+1}$ ${\displaystyle i=1,2,\dots ,p-1,}$ ${\displaystyle r^{p-1}}$

${\displaystyle {\begin{bmatrix}d+1\\n_{1}\ n_{2}\ \dots \ n_{p}\end{bmatrix}}q^{s_{2}(n_{1},\ldots ,n_{p})},}$

donde (en el que suponemos que ) denota el coeficiente p -gaussiano ${\displaystyle {\begin{bmatrix}d+1\\n_{1}\ n_{2}\ \dots \ n_{p}\end{bmatrix}}}$ ${\displaystyle d+1=n_{1}+\cdots +n_{p}}$

${\displaystyle {\begin{bmatrix}d+1\\n_{1}\end{bmatrix}}{\begin{bmatrix}d+1-n_{1}\\n_{2}\end{bmatrix}}\cdots {\begin{bmatrix}d+1-(n_{1}+\cdots +n_{p-1})\\n_{p}\end{bmatrix}}}$

y

${\displaystyle s_{2}(n_{1},\ldots ,n_{p}):=n_{1}n_{2}+n_{1}n_{3}+n_{2}n_{3}+n_{1}n_{4}+\cdots +n_{p-1}n_{p},}$

la segunda función simétrica elemental de los números ${\displaystyle n_{1},n_{2},\dots ,n_{p}.}$

Véase también

• Portal de matemáticas

• Teorema de Dilworth
• Teorema de Erdős–Ko–Rado

Referencias

• Anderson, Ian (1987), Combinatoria de conjuntos finitos , Oxford University Press.
• Beck, Matthias; Zaslavsky, Thomas (2002), "Una prueba más corta, más simple y más fuerte de los límites de Meshalkin-Hochberg-Hirsch en anticadenas por componentes", Journal of Combinatorial Theory , Serie A, 100 (1): 196–199, arXiv : math/0112068 , doi : 10.1006/jcta.2002.3295 , MR  1932078, S2CID  8136773.
• Beck, Matthias; Zaslavsky, Thomas (2003), "Un teorema de Meshalkin para geometrías proyectivas", Journal of Combinatorial Theory , Serie A, 102 (2): 433–441, arXiv : math/0112069 , doi : 10.1016/S0097-3165(03)00049-9 , MR  1979545, S2CID  992137.
• Engel, Konrad (1997), Teoría de Sperner , Enciclopedia de matemáticas y sus aplicaciones, vol. 65, Cambridge: Cambridge University Press, pág. x+417, doi :10.1017/CBO9780511574719, ISBN 0-521-45206-6, Sr.  1429390.
• Engel, K. (2001) [1994], "Teorema de Sperner", Enciclopedia de Matemáticas , EMS Press
• Erdős, P. (1945), "Sobre un lema de Littlewood y Offord" (PDF) , Boletín de la Sociedad Matemática Americana , 51 (12): 898–902, doi : 10.1090/S0002-9904-1945-08454-7 , MR  0014608
• Lubell, D. (1966), "Una breve prueba del lema de Sperner", Journal of Combinatorial Theory , 1 (2): 299, doi : 10.1016/S0021-9800(66)80035-2 , MR  0194348.
• Meshalkin, LD (1963), "Generalización del teorema de Sperner sobre el número de subconjuntos de un conjunto finito", Teoría de la probabilidad y sus aplicaciones (en ruso), 8 (2): 203–204, doi :10.1137/1108023.
• Rota, Gian-Carlo ; Harper, LH (1971), "Teoría de emparejamiento, una introducción", Advances in Probability and Related Topics, vol. 1 , Nueva York: Dekker, págs. 169–215, MR  0282855.
• Sperner, Emanuel (1928), "Ein Satz über Untermengen einer endlichen Menge", Mathematische Zeitschrift (en alemán), 27 (1): 544–548, doi :10.1007/BF01171114, hdl : 10338.dmlcz/127405 , JFM  54.0090. 06, S2CID  123451223.

Enlaces externos

• Teorema de Sperner al cortar el nudo
• Teorema de Sperner en la wiki de polymath1