Una familia de conjuntos en la que ninguno de los conjuntos es un subconjunto estricto de otro se denomina clutter, una anticadena de conjuntos o un conjunto desordenado. 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 demás, ya que un conjunto contenedor debe 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 sobre un conjunto de n elementos. Formalmente, el teorema establece que,

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

El teorema de Sperner también puede enunciarse en términos del teorema de Dilworth. La familia de todos los subconjuntos de un conjunto de n elementos (su conjunto potencia) puede ser parcialmente ordenado por inclusión de conjuntos. En este orden parcial, se dice que dos elementos distintos son incomparables cuando ninguno de ellos contiene al otro. La anchura 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 conjuntos, una anticadena es simplemente una familia de Sperner, y la anchura 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 la anchura 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.

Existen muchas demostraciones 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, se puede sumar sobre la desigualdad anterior desde k = 0 hasta n y luego aplicar la desigualdad de Lubell-Yamamoto-Meshalkin 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 que

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

Esto completa la demostración de la parte 1.

Para que haya igualdad, todas las desigualdades en la demostración anterior deben ser igualdades. Dado que

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

si y solo si ${\displaystyle k=\lfloor {n/2}\rfloor }$  o ${\displaystyle \lceil {n/2}\rceil ,}$ , se concluye que la igualdad implica que S consiste únicamente en conjuntos de tamaños ${\displaystyle \lfloor {n/2}\rfloor }$  o ${\displaystyle \lceil {n/2}\rceil .}$ . Para n par, con esto concluye la demostración de la parte 2.

Para n impar hay más trabajo por hacer, que se omite aquí por su complicación (véase Anderson (1987), págs. 3-4).

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

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

En el conjunto ${\displaystyle {\mathcal {P}}(E)^{p}}$  de p-tuplas de subconjuntos de E, se dice que una p-tupla ${\displaystyle (S_{1},\dots ,S_{p})}$  es ≤ que otra, ${\displaystyle (T_{1},\dots ,T_{p}),}$ , si ${\displaystyle S_{i}\subseteq T_{i}}$  para cada i = 1, 2,..., p. Se denomina a ${\displaystyle (S_{1},\dots ,S_{p})}$  una p-composición de E si los conjuntos ${\displaystyle S_{1},\dots ,S_{p}}$  forman una partición de E. Meshalkin (1963) demostró que el tamaño máximo de una anticadena de p-composiciones es el mayor coeficiente p-multinomial ${\displaystyle {\binom {n}{n_{1}\ n_{2}\ \dots \ n_{p}}},}$  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 de Lubell-Yamamoto-Meshalkin generalizada.

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

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

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

Además, demostraron que el mayor tamaño de una familia sin cadenas r en ${\displaystyle {\mathcal {L}}(p,F_{q})}$  es la suma de los r coeficientes gaussianos más grandes. Su demostración se basa en un análogo proyectivo de la desigualdad de Lubell-Yamamoto-Meshalkin.

Beck y Zaslavsky (2003) obtuvo una generalización similar a la de Meshalkin del teorema de Rota-Harper. En PG(d, F_q), una secuencia de Meshalkin de longitud p es una secuencia ${\displaystyle (A_{1},\ldots ,A_{p})}$  de subespacios proyectivos tal que ningún subespacio propio de PG(d, F_q) los contiene a todos y sus dimensiones suman ${\displaystyle d-p+1}$ . El teorema establece que una familia de secuencias de 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 ${\displaystyle i=1,2,\dots ,p-1,}$  no es mayor que la suma de la mayor ${\displaystyle r^{p-1}}$  de las cantidades

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

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

${\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},}$ 

es el segundo polinomio simétrico elemental de los números ${\displaystyle n_{1},n_{2},\dots ,n_{p}.}$ 

• Teorema de Dilworth
• Teorema de Erdös-Ko-Rado

• Anderson, Ian (1987), Combinatorics of Finite Sets, Oxford University Press ..
• Beck, Matthias; Zaslavsky, Thomas (2002), «A shorter, simpler, stronger proof of the Meshalkin-Hochberg-Hirsch bounds on componentwise antichains», Journal of Combinatorial Theory, Series A 100 (1): 196-199, MR 1932078, S2CID 8136773, arXiv:math/0112068, doi:10.1006/jcta.2002.3295 ..
• Beck, Matthias; Zaslavsky, Thomas (2003), «A Meshalkin theorem for projective geometries», Journal of Combinatorial Theory, Series A 102 (2): 433-441, MR 1979545, S2CID 992137, arXiv:math/0112069, doi:10.1016/S0097-3165(03)00049-9 ..
• Engel, Konrad (1997), Sperner theory, Encyclopedia of Mathematics and its Applications 65, Cambridge: Cambridge University Press, p. x+417, ISBN 0-521-45206-6, MR 1429390, doi:10.1017/CBO9780511574719 ..
• Engel, K. (2001), «Teorema de Sperner», en Hazewinkel, Michiel, ed., Encyclopaedia of Mathematics (en inglés), Springer, ISBN 978-1556080104 ..
• Erdős, P. (1945), «On a lemma of Littlewood and Offord», Bulletin of the American Mathematical Society 51 (12): 898-902, MR 0014608, doi:10.1090/S0002-9904-1945-08454-7 .
• Lubell, D. (1966), «A short proof of Sperner's lemma», Journal of Combinatorial Theory 1 (2): 299, MR 0194348, doi:10.1016/S0021-9800(66)80035-2 ..
• Meshalkin, L.D. (1963), «Generalization of Sperner's theorem on the number of subsets of a finite set», Theory of Probability and Its Applications (en russian) 8 (2): 203-204, doi:10.1137/1108023 ..
• Rota, Gian-Carlo; Harper, L. H. (1971), «Matching theory, an introduction», Advances in Probability and Related Topics, Vol. 1, New York: Dekker, pp. 169-215, MR 0282855 ..
• Sperner, Emanuel (1928), «Ein Satz über Untermengen einer endlichen Menge», Mathematische Zeitschrift (en german) 27 (1): 544-548, JFM 54.0090.06, S2CID 123451223, doi:10.1007/BF01171114, hdl:10338.dmlcz/127405 .X.

•   Portal:Matemática. Contenido relacionado con Matemática.
• Teorema de Sperner en alexander Bogomolny
• Teorema de Sperner en la wiki de polymath1