Erdős–Ko–Rado-tétel

Az Erdős–Ko–Rado-tétel a kombinatorika egyik fontos tétele, amely az ún. metszőrendszerekről szól. Erdős Pál, Ko Chao és Richard Rado 1938-ban találta, de csak 1961-ben publikálta.

A tétel állítása

Legyenek $n\geq 2k$ természetes számok. Ha S egy n-elemű alaphalmaz és az S k-elemű részhalmazaiból álló ${\mathcal H}$ halmazrendszer olyan, hogy bármely két eleme metszi egymást (azaz metszőrendszer), akkor

$|{\mathcal H}|\leq {{n-1}\choose{k-1}}.$

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