Delta-rendszer lemma

A Wikipédiából, a szabad enciklopédiából
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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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[1] 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.[2] Ezt A. V. Kosztocska továbbjavította[3] a

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

értékre.

A végtelen Δ-rendszer lemma[szerkesztés | forrásszöveg szerkesztése]

Véges halmazok[szerkesztés | forrásszöveg szerkesztése]

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 | forrásszöveg szerkesztése]

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

Hivatkozások[szerkesztés | forrásszöveg szerkesztése]

  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.