Δ-rendszer-lemma

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

Δ-rendszer

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

A véges Δ-rendszer-lemma

Van olyan f(k,n) ($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 a

$(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 $f(3,n)<c^{n}$ alkalmas c-re. Joel Spencer 1977-ben a felső korlátot a $n!(1+o(1))^{n}$ értékre javította. Ezt A. V. Kosztocska továbbjavította a

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

értékre.

A végtelen Δ-rendszer-lemma

Véges halmazok

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

Végtelen halmazok

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