Az Eszterházy Károly Tanárképző Főiskola Tudományos Közleményei. 1997. Sectio Mathematicae. (Acta Academiae Paedagogicae Agriensis : Nova series ; Tom. 24)

RÓKA S.: Független metszőrendszerek II

Független metszőrendszerek II. 69 Legyen A\, A

2,..., A

m az n-elemű H halmazon független metszőrendszer, és \A{\ = k

} i = 1,2,..., m. Jelölje m értékének legkisebb értékét /fc(n), legnagyobb értékét Fk(n). Az 1. Tétel miatt fk(n) = f

n~k{n) és Fk(n) = F

n-k(n)- Ezért fk(n) értékét elegendő 1 < k < j esetekben meghatározni. 3. TéteL (b) Ha k < k\2nésk páros, akkor f

k(n) = (c) f

k (Mífli) a k +1, azaz ha n * Mor f

k(n) = Bizonyítás. Legyen A\, A

2,..., A

m a H — {xi, X2,... 7 x

n] halmazon fíiggetlen metszörendszer, \A

t\ = k, i = 1, 2,..., ra, és Bi = {k\X{ E A-fc}, i = 1,2,.. .,n. Ekkor < 2. 77i n Mivel mk = £ |A<| - £ < 2rz, így m < . i=í j=i Belátjuk, ha A; < \/2n, & | 2n és k páros, akkor fk(n) < ^. Innen (a) felhasználásával adódik a (b) állítás. Készítsünk egy gráfot. Legyen a G gráf csúcsainak száma m — ^

1, és számozzuk meg a gráf csúcsait az 1, 2,..., m számokkal. A gráf minden csúcsára k él illeszkedjen. Ekkor a gráfnak n éle van. Ilyen gráf az Erdős— Gallai-tétel [9] szerint készíthető. Álljon most az n elemű H halmaz a gráf éleiből, az A\, A

2,..., A

m halmazokat pedig a következő módon kapjuk: A

t a gráf azon éleiből áll, amelyek illeszkednek a gráf i-edik csúcsára. 9 • • • • • • • • Legyen most n = (^

1). A H halmaz az ábrán látható pontokból áll, az Ai, A

2,..., Ak+i halmazokat pedig a háromszög átlóján levő pontok határozzák meg, egy-egy ilyen ponttal közös halmazba tartoznak a vele egy sorban és a vele egy oszlopban levő pontok, valamint egy további halmaz van még, mely az átlón levő pontokból áll. Ezen konstrukció miatt fk(n) < & + 1, ám (a) miatt fk(n) > k + 1, ezzel igazoltuk (c)-t is. •