Sperner-tétel

A Wikipédiából, a szabad enciklopédiából
Jump to navigation Jump to search

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]

Ha egy n elemű halmaz S részhalmazaiból álló halmazrendszer, hogy , esetén , akkor

Ekkora Sperner-rendszer van, ilyen S összes vagy összes elemű részhalmazából álló rendszer.

Itt és az szám alsó és felső egészrészét jelenti, azaz esetén k-t, esetén pedig k-t és k+1-et.

A tétel bizonyítása[szerkesztés]

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

Az feltétel mellett értéke akkor a legkisebb, ha a, b azonosak vagy szomszédosak. Valóban, ha , akkor az szorzat kisebb, mint , mivel

Innen adódik, hogy esetén . Ezért a fenti összeszámlálásnál elemeit legfeljebb -szor számoltuk, mindegyiket legalább -szor, ezért

Lásd még[szerkesztés]