Lema de Sperner

El Lema de Sperner en combinatoria extremal se refiere a un resultado clásico sobre subconjuntos de un conjunto finito, y se enuncia así:

Enunciado del Lema de Sperner:

Sea \(X\) un conjunto finito con \(|X| = n\). Consideremos una familia de subconjuntos \(\mathcal{F} \subseteq \mathcal{P}(X)\) (el conjunto de partes de \(X\)) tal que ningún subconjunto de \(\mathcal{F}\) está contenido en otro (es decir, \(A \nsubseteq B\) para cualesquiera \(A, B \in \mathcal{F}\) con \(A \ne B\)). Entonces: $$ \Large |\mathcal{F}| \leq \binom{n}{\lfloor n/2 \rfloor} $$

Explicación:

• A una familia de subconjuntos como la descrita se le llama familia de Sperner o anticadena.
• El máximo número de subconjuntos mutuamente no incluidos (ninguno contenido en otro) ocurre cuando todos los subconjuntos tienen el mismo tamaño, y ese tamaño óptimo es \(\lfloor n/2 \rfloor\) o \(\lceil n/2 \rceil\), que son los niveles más grandes del cubo de Hamming.
• La cota \(\binom{n}{\lfloor n/2 \rfloor}\) es exacta, y se alcanza, por ejemplo, cuando \(\mathcal{F}\) es el conjunto de todos los subconjuntos de tamaño \(\lfloor n/2 \rfloor\).

archivo