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

68 Róka Sándor Következmény. Az Ai, A

2,..., A

m független metszörendszeren nem oldható meg az (3) A,= f]Ai IC {1,2,..., m} \I\ / 1 egyenlet. Bizonyítás. A definícióból következik, hogy A\ — U Aj, továbbá / C {1,2,... ,m} és az \I\ ^ 1 egyenlet nem oldható meg, s így az előbbi tétel miatt nem oldható meg a (3) egyenlet sem. • 2. Tétel. Az A\, A

2,..., A

m az n-elemű H halmazon független metszőrendszer, akkor C\ log

2 n < m < c

2n

2, és ezek a korlátok nagyságrendjükben pontosak. Bizonyítás. Legyen Xk = U \X

k\ = 1, k = 1,2, ...,n. Az Ii, I

2,..., I

n C {1,2,..., m} rendszer Sperner-rendszer, így a Sperner-lemma [1] miatt n < (^mj), azaz m > c\ log

2 n. Megmutatjuk, hogy az alsó korlát pontos, vagyis, ha (rSj) < n, akkor van egy legfeljebb m halmazból álló A\, A

2,..., A

m független metszőrendszer az n elemű H halmazon. Tekintsük azt az A m X (j-mj)-es 0-1 mátrixot, amelynek oszlopai az {1,2, ...,ra} halmaz egy-egy [y]-elemű részét reprezentálják. Az A mátrix soraival megadott m db halmazból néhányat választva az (jmj) elemű halmaz bármely elemét kimetszhetjük. A felső korlát igazolása. Legyen x E H, s tekintsük azon Aj-ket, melyek szükségesek az (1) és (2) szerinti előállításhoz. A^-kből hagyjuk el az x elemet. Az így kapott halmazokat jelölje A\. Ezen A[-k száma s. Most bármely 5 — 1 db A[ metszete ^ 0, míg az összes A\ metszete = 0. így minden A\-hez hozzárendelhetünk egy olyan elemet a H \ {a:} halmazból, mely a #többi A'j-nek nem eleme. Ezért s < n — 1. így leszámolva az A\, A

2,..., A

m halmazokat, azt kapjuk, hogy m < n(n — 1). Megadunk olyan független metszőrendszert a H = {x\, x

2,..., x

n } halmazon, mely c

2n

2 halmazból áll. Legyen r = [y], R = {x\, x

2,..., x

r}, Ai = R\ {x;}, i = 1,2,..., r; A

i}

j = {XÍ} U Aj, i = r + 1, r + 2,..., n j = l,2,...,r. Az Aíj halmazok független metszőrendszert alkotnak, s a -halmazok száma több, mint \n

2 — 1. • Vizsgáljuk most azon független metszőrendszereket, melyek uniform rendszerek.