Δ-rendszer-lemma

(Delta-rendszer lemma szócikkből átirányítva)

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

Δ-rendszer szerkesztés

Halmazok egy   rendszerét Δ-rendszernek nevezzük, ha páronként azonos a metszetük:  .

A véges Δ-rendszer-lemma szerkesztés

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

 

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

 

értékre.

A végtelen Δ-rendszer-lemma szerkesztés

Véges halmazok szerkesztés

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 szerkesztés

Ha   végtelen számosság és adott   számosságú halmazoknak egy   számosságú rendszere, akkor az tartalmaz egy   számosságú Δ-részrendszert (Erdős-Rado, 1960).

Hivatkozások szerkesztés

  1. P. Erdős, R. Rado: Intersection theorems for systems of sets, Journal of London Math. Soc., 35(1960), 85-90.
  2. J. Spencer: Intersection theorems for systems of sets, Canad. Math. Bull., 20(1977), 249-254
  3. A. V. Kostochka: A bound of the cardinality of families not containing $\Delta$-systems, The mathematics of Paul Erdős, II, Algorithms Combin., 14, Springer, Berlin, 1997. 229-235.