Sperner tétele

A kombinatorikában Sperner tétele 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|$ $\le$ ${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