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

Más nyelveken