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 ${\mathcal {F}}$ egy n elemű halmaz S részhalmazaiból álló halmazrendszer, hogy $A,B\in {\mathcal {F}}$, $A\neq B$ esetén $A\not \subseteq B$, akkor

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

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

Itt $\left\lfloor {\frac {n}{2}}\right\rfloor$ és $\left\lceil {\frac {n}{2}}\right\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 ${\mathcal {F}}$ 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 $|{\mathcal {F}}|\leq n!$ becslés adódik, ami használhatatlan. Egy $A\in {\mathcal {F}}$ 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!\geq \left\lfloor {\frac {n}{2}}\right\rfloor !\left\lceil {\frac {n}{2}}\right\rceil !$. Ezért a fenti összeszámlálásnál ${\mathcal {F}}$ elemeit legfeljebb $n!$-szor számoltuk, mindegyiket legalább $\left\lfloor {\frac {n}{2}}\right\rfloor !\left\lceil {\frac {n}{2}}\right\rceil !$-szor, ezért

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

Lásd még

• LYM-egyenlőtlenség