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
70 Róka Sándor 4. Tétel. k(n - k) < F k(n) < kn, 1 < k < f. Bizonyítás. Legyen H = {xi,x2i... Ä = {^x, . ..,»*}, Ai = R \ {zj, i = 1,2,..., k\ Aij = {XÍ} U Aj, i = k + 1, k + 2,..., n, j = 1,2,..., k. Az Aij halmazok független metszőrendszert alkotnak, a halmazok száma k(n — k), és \AÍJ\ = k így valóban > k(n — k). A felső korlát igazolása. Legyen A\, A2,..., A m az n-elemű H halmazon független metszőrendszer, \Ai \ = k, i = 1, 2,..., m. Legyen x E H, s tekintsük azon Ai-ket, melyek szükségesek az (1) és (2) szerinti előállításához. Aj-kből hagyjuk el az x elemet. Az így kapott halmazokat jelölje A[. Ezen A\-k száma s. Most bármely s — 1 db A\ metszete / 0, míg az összes A\ metszete = 0. így minden ^4' rhez megadható olyan elem, mely neki nem eleme, de a többi A^-nek igen. Rögzített A'- mellet sorra véve a többi A[-1, A^-nek 5 — 1 különböző eleme jelölhető így ki, azaz s - 1 < | A'-1 = k — 1. Tehát II egy tetszőlegesen kiválasztott x eleméhez legfeljebb k db A\ rendelhető, így m < nk. m Már eddig is több független metszőrendszerre láttunk példát, most még további két rendszert konstruálunk. 1. konstrukció. Tekintsük egy N pontú teljes gráfot, s minden élére helyezzünk újabb pontot. A H halmaz ezen „régi" és „új" pontokból áll, tehát \H\ = N -f (^). A metszőrendszer a „fél-élekből" áll, tehát olyan kételemű halmazokból, melyek egyik eleme egy „régi" és egy „új" pont, és közös az az él a teljes gráfban, melyre ez a két pont illeszkedik. A metszőrendszer elemeinek m száma itt nagyságában 2|//|-hoz közelít. 2. konstrukció. Vegyünk egy N elemű X halmazt, ennek elemeit nevezzük „régi" pontoknak, az „új" pontok az N elemű halmaz [y]-elemű részei. így elkészítettük a II halmazt, mely ezen „régi" és „új" pontokból áll, tehát \H\ — N + (j^j). A metszőrendszer egy-egy halmaza egy „új" pontból és a hozzá tartozó [~] „régi" pontból [y] — 1 választva — ezt az összes lehetséges módon megtesszük — áll. Itt m = [y] Qjvj), vagyis m nagyságában \H\ log\H |-hoz közelít. A dolgozatban megadott független metszőrendszerek mindegyike Sperner-rendszer volt. Ez azonban nem szükségszerű, mint az alábbi példa mutatja.
