Δ-rendszer-lemma

A véges és végtelen Δ-rendszer-lemma fontos szerepet játszik a kombinatorikában illetve a kombinatorikus halmazelméletben.

Halmazok egy ${\displaystyle \{A_{i}:i\in I\}}$ rendszerét Δ-rendszernek nevezzük, ha páronként azonos a metszetük: ${\displaystyle A_{i}\cap A_{j}=S}$.

Van olyan f(k,n) (${\displaystyle k\geq 3,n\geq 2}$) függvény, hogy a következő igaz: minden, legalább f(k,n) n elemű halmazból álló rendszernek van k halmazból álló Δ-részrendszere.

Erdős egyik kedvenc problémája volt f(k,n) nagyságrendjének meghatározása. Radóval igazolták^[1] a

${\displaystyle (k-1)^{n}<f(k,n)\leq (k-1)^{n}n!}$

becslést, a nyitott kérdés azonban, hogy van-e exponenciális felső korlát f(3,n)-re, azaz igaz-e ${\displaystyle f(3,n)<c^{n}}$ alkalmas c-re. Joel Spencer 1977-ben a felső korlátot a ${\displaystyle n!(1+o(1))^{n}}$ értékre javította.^[2] Ezt A. V. Kosztocska továbbjavította^[3] a

${\displaystyle Cn!\left({\frac {\log \log \log n}{\log \log n}}\right)^{n}}$

értékre.

Minden, véges halmazokból álló, megszámlálhatónál nagyobb halmazrendszer tartalmaz megszámlálhatónál nagyobb Δ-részrendszert.

Ezt az állítást többször is felfedezték: Nyikolaj A. Sanyin (1946), E. Szpilrajn-Marczewski (1947), M. Bockstein (1948), S. Mazur (1952).

Ha ${\displaystyle \kappa }$ végtelen számosság és adott ${\displaystyle \kappa }$ számosságú halmazoknak egy ${\displaystyle (2^{\kappa })^{+}}$ számosságú rendszere, akkor az tartalmaz egy ${\displaystyle (2^{\kappa })^{+}}$ számosságú Δ-részrendszert (Erdős-Rado, 1960).