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
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.
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