Sperner-tétel

A kombinatorikában a Sperner-tétel a hipergráfokra vonatkozó extremális tételek közül az egyik legfontosabb és legrégibb. Sperner 1928-ban igazolt tétele olyan halmazrendszerek méretére ad éles korlátot, melyekben egyik halmaz sem részhalmaza másiknak. Tiszteletére az ilyen rendszereket ma Sperner-rendszereknek nevezzük.

A tétel állítása

Ha $ℱ$ egy n elemű halmaz S részhalmazaiból álló halmazrendszer, hogy $A,B\in ℱ$, $A\ne B$ esetén $A\subseteq ̸B$, akkor

$\left|ℱ\right|$ $\le$ $(\genfrac{}{}{0ex}{}{n}{\lfloor \frac{n}{2}\rfloor }).$

Ekkora Sperner-rendszer van, ilyen S összes $\lfloor \frac{n}{2}\rfloor$ vagy összes $\lceil \frac{n}{2}\rceil$ elemű részhalmazából álló rendszer.

Itt $\lfloor \frac{n}{2}\rfloor$ és $\lceil \frac{n}{2}\rceil$ az $\frac{n}{2}$ szám alsó és felső egészrészét jelenti, azaz $n=2k$ esetén k-t, $n=2k+1$ esetén pedig k-t és k+1-et.

A tétel bizonyítása

Soroljuk fel S elemeit valamilyen sorrendben:$x_1,\dots ,x_n$. Az $ℱ$ halmazrendszernek csak egy olyan tagja lehet, ami $A=\{x_1,\dots ,x_k\}$ alakú, hiszen az ilyen kezdőszeletek egymást kölcsönösen tartalmazzák. Ebből, mivel az S-nek $n!$ felsorolása van, az $|ℱ|\le n!$ becslés adódik, ami használhatatlan. Egy $A\in ℱ$ halmaz azonban több felsorolásban is szerepel kezdőszeletként, mégpedig $|A|=a$ esetén ezek száma $a!b!$, ahol $b=n-a$, hiszen az alaphalmaz elemeinek ennyi permutációja van, amiben az első a helyen A elemei szerepelnek.

Az $a+b=n$ feltétel mellett $a!b!$ értéke akkor a legkisebb, ha a, b azonosak vagy szomszédosak. Valóban, ha $b>a+1$, akkor az $(a+1)!(b-1)!$ szorzat kisebb, mint $a!b!$, mivel

$\frac{(a+1)!(b-1)!}{a!b!}=\frac{a+1}{b}<1.$

Innen adódik, hogy $a+b=n$ esetén $a!b!\ge \lfloor \frac{n}{2}\rfloor !\lceil \frac{n}{2}\rceil !$. Ezért a fenti összeszámlálásnál $ℱ$ elemeit legfeljebb $n!$-szor számoltuk, mindegyiket legalább $\lfloor \frac{n}{2}\rfloor !\lceil \frac{n}{2}\rceil !$-szor, ezért

$|ℱ|\le \frac{n!}{\lfloor \frac{n}{2}\rfloor !\lceil \frac{n}{2}\rceil !}=(\genfrac{}{}{0ex}{}{n}{\lfloor \frac{n}{2}\rfloor }).$

Lásd még

• LYM-egyenlőtlenség