Delta-rendszer lemma

A szócikk címe technikai okok miatt pontatlan. A helyes cím: Δ-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. Radoval 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

$C n! \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)