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.

Ha ${\displaystyle {\mathcal {F}}}$ egy n elemű halmaz S részhalmazaiból álló halmazrendszer, hogy ${\displaystyle A,B\in {\mathcal {F}}}$, ${\displaystyle A\neq B}$ esetén ${\displaystyle A\not \subseteq B}$, akkor

${\displaystyle \left|{\mathcal {F}}\right|}$ ${\displaystyle \leq }$ ${\displaystyle {n \choose \left\lfloor {\frac {n}{2}}\right\rfloor }.}$

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

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

Soroljuk fel S elemeit valamilyen sorrendben:${\displaystyle x_{1},\dots ,x_{n}}$. Az ${\displaystyle {\mathcal {F}}}$ halmazrendszernek csak egy olyan tagja lehet, ami ${\displaystyle 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 ${\displaystyle n!}$ felsorolása van, az ${\displaystyle |{\mathcal {F}}|\leq n!}$ becslés adódik, ami használhatatlan. Egy ${\displaystyle A\in {\mathcal {F}}}$ halmaz azonban több felsorolásban is szerepel kezdőszeletként, mégpedig ${\displaystyle |A|=a}$ esetén ezek száma ${\displaystyle a!b!}$, ahol ${\displaystyle b=n-a}$, hiszen az alaphalmaz elemeinek ennyi permutációja van, amiben az első a helyen A elemei szerepelnek.

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

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

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

${\displaystyle |{\mathcal {F}}|\leq {\frac {n!}{\left\lfloor {\frac {n}{2}}\right\rfloor !\left\lceil {\frac {n}{2}}\right\rceil !}}={n \choose \left\lfloor {\frac {n}{2}}\right\rfloor }.}$

• LYM-egyenlőtlenség