Teorema di Sperner §

Detto $M(n):=\{|\mathcal{F}|:\mathcal{F}\subseteq 2^{[n]}\}$ che ha la proprietà di Sperner, (ovvero nessun insieme è contenuto nell’altro). Allora $M(n)=\left(\genfrac{}{}{0ex}{}{n}{\lfloor \frac{n}{2}\rfloor }\right)$.

Oss Se $\mathcal{F}$ ha la proprietà di Sperner, è un’anticatena in $(2^{[n]},\subseteq )$.

Lemma (LYM inequality) §

Se $\mathcal{F}$ è una famiglia di Sperner di $[n]$ allora

$$\sum _{E\in \mathcal{F}}{\left(\genfrac{}{}{0ex}{}{n}{|E|}\right)}^{-1}\le 1$$

Dimostrazione Idea della catena satura di lunghezza massima di $(2^{[n]},\subseteq )$, una successione: $D_0=\varnothing \subset D_1\subset D_2\cdots \subset D_n=[n]$. Se voglio massimizzare la lunghezza, è ovvio che aggiungo ad ogni passo solo un elemento $a_i$.

1. Quante sono le catene sature da $\varnothing$ a $[n]$? Ovviamente corrispondono alle permutazioni di $n$ elementi, e sono $n!$
2. Quante sono le catene $\varnothing \subset \cdots \subset E\subset \cdots \subset [n]$ che passano per il sottoinsieme $E\subseteq [n]$ con $|E|$ elementi? Ho $|E|!$ modi per arrivare da $\varnothing$ ad $E$, e dopo $(n-|E|)!$ per terminare la catena, quindi ho $|E|!(n-|E|)!$

Chiamo le catene sature che passano per l’insieme $E$ ${\mathcal{D}}_E$ che avrà cardinalità come detto sopra. 3. $\mathcal{F}$ è una famiglia di sperner. Se $E,E^{\prime }\in \mathcal{F}$, $E^{\prime }\ne E$, allora ${\mathcal{D}}_E\cap {\mathcal{D}}_F=\varnothing$. Infatti se esistesse una catena che compare in entrambe le famiglie, supponiamo s.p.g che $E$ compaia prima di $F$ nella catena: $\varnothing \subset \cdots \subset E\cdots \subset F\cdots \subset [n]$. Ma allora $E\subset F$ contro l’ipotesi di famiglia di sperner. Essendo disgiunte è facile calcolare la cardinalità dell’unione, che deve essere più piccola della cardinalità di tutte le catene:

$$\left|\bigcup _{E\in \mathcal{F}}{\mathcal{D}}_E\right|=\sum _{E\in \mathcal{F}}|{\mathcal{D}}_E|=\sum _{E\in \mathcal{F}}|E|!(n-|E|)!\le n!$$

dividendo per $n!$ ottengo la tesi. $\square$

Dimostrazione (Sperner)

1. $M(n)\ge \left(\genfrac{}{}{0ex}{}{n}{\lfloor \frac{n}{2}\rfloor }\right)$

Sia ${\mathcal{F}}_k=\left(\genfrac{}{}{0ex}{}{[n]}{k}\right)$ la famiglia uniforme. Soddisfa la proprietà di Sperner, infatti avendo tutti la stessa cardinalità, per valere $A\subseteq B$ si deve avere $A=B$. Ovviamente vale:

$$|{\mathcal{F}}_k|=\left(\genfrac{}{}{0ex}{}{n}{k}\right)$$

Basta prendere ${\mathcal{F}}_{\lfloor \frac{n}{2}\rfloor }$ per concludere che $M(n)$ deve essere maggiore o uguale. 2. Sia $\mathcal{F}$ qualunque con la proprietà di Sperner, facciamo vedere che $|\mathcal{F}|\le \left(\genfrac{}{}{0ex}{}{n}{\lfloor \frac{n}{2}\rfloor }\right)$. Osservazione La successione dei coffefficienti binomiali è bimodale (la binomiale):

$$\left(\genfrac{}{}{0ex}{}{n}{\lfloor \frac{n}{2}\rfloor }\right)=\left(\genfrac{}{}{0ex}{}{n}{\lceil \frac{n}{2}\rceil }\right)$$

e qui assume il valore massimo. Ho finito, uso il lemma LYM:

$$1\ge \sum _{E\in \mathcal{F}}{\left(\genfrac{}{}{0ex}{}{n}{|E|}\right)}^{-1}\ge \sum _{E\in \mathcal{F}}{\left(\genfrac{}{}{0ex}{}{n}{\lfloor \frac{n}{2}\rfloor }\right)}^{-1}={\left(\genfrac{}{}{0ex}{}{n}{\lfloor \frac{n}{2}\rfloor }\right)}^{-1}|\mathcal{F}|$$

$\square$