Sperner-tétel

A Wikipédiából, a szabad enciklopédiából
(Sperner tétele szócikkből átirányítva)

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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]