Δ-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\ge 3,n\ge 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)\le (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).