Ugrás a tartalomhoz

Erdős–Ko–Rado-tétel

Ellenőrzött
A Wikipédiából, a szabad enciklopédiából

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 Csao és Richard Rado 1938-ban találta, de csak 1961-ben publikálta.

A tétel állítása

[szerkesztés]

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 (azaz metszőrendszer), akkor

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