Erdős–Ko–Rado-tétel
A Wikipédiából, a szabad lexikonból.
Az Erdős–Ko–Rado-tétel a kombinatorika egyik fontos tétele. Erdős Pál, Chao Ko és Richard Rado 1938-ban találta, de csak 1961-ben publikálta.
[szerkesztés] A tétel állítása
Legyenek
természetes számok. Ha S egy n-elemű alaphalmaz és az S k-elemű részhalmazaiból álló
halmazrendszer olyan, hogy bármely két eleme metszi egymást, akkor

Egyenlőség lehet például akkor, ha S összes, adott elemet tartalmazó k-elemű részhalmazát vesszük.

