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

72 Róka Sándor A független metszőrendszer fogalma kapcsolódik egy régen ismert fogalomhoz, a kölcsönösen szeparáló rendszerekéhez. Legyen H egy n elemű halmaz, Ai, A

2,.. ., A

m ennek részhalmazai. Ez utóbbi rendszer szeparáló rendszer, ha H bármely x,y elemeihez van olyan A{, hogy vagy x £ Ai és y £ Ai, vagy x £ A( és y ^ A{. Ezt a fogalmat Rényi [2] vezette be, és Katona [3] megmutatta, hogy m > [log

2 n]. Dickson a szeparáló rendszer definícióját módosította. Az Ai, A

2,..., A

m rendszert kölcsönösen szeparáló rendszernek nevezi, ha H bármely x, y elemeihez van olyan A{ és Aj, hogy x £ Ai és y (fc A{, továbbá x (£ Aj és y £ Aj. Dickson [4], majd Spencer [5] megmutatja, hogy erre a rendszerre is m > log

2 n. Katona fogalmazta meg a teljes szeparáló rendszer fogalmát. Az A\, A2,..., A

m rendszert akkor tekintjük ilyennek, ha II bármely x,y elemeihez van olyan Ai és Aj, hogy x £ A

l és y £ Aj, és Ai fi Aj = 0. Erre a rendszerre az előbbiekhez hasonló becslést ad Yao [7] és tőle függetlenül Cai Mao-cheng [8]. Látható, hogy egy teljesen független rendszer egyúttal kölcsönösen szeparáló, és egy kölcsönösen szeparáló pedig szeparáló. 5. Tétel. A független metszörendszer (1) feltétele azonos a kölcsönös szeparáló rendszer definíciójával. Bizonyítás. Ha egy halmazrendszerre teljesül az (1) feltétel, akkor az kölcsönösen szeparáló. Ugyanis vegyük II két x,y elemét. Ekkor x is y is előáll néhány Ai metszeteként. Ezért van olyan Ai melynek x eleme, de y nem, és van olyan Aj melynek y eleme, de x nem. Ha egy halmazrendszer kölcsönösen szeparáló, akkor kielégíti az (1) feltételt, hiszen már az akikötés, hogy H bármely x,y eleméhez van olyan Ai, hogy x £ Ai és y Aj, garantálja azt, hogy x előálh'tható néhány Ai metszeteként. • Ezt a tételt figyelembe véve nevezzük az n-elemű H halmaz A\, A2,..., A

m részhalmazait t-szeparálónak, ha kielégíti az (1') feltételt. Látható, hogy egy /-szeparáló rendszer egyúttal /'-szeparáló is, ahol t > t' > 1. Az is könnyen ellenőrizhető, ha a H halmaznak A\, A

2,.. . ,A

m 1-szeparáló rendszere, akkor az U Ai, i C {1, 2,..., m}, |/| = t halmazokból álló rendszer í-szeparáló. Ha az n elemű II halmazon Ai, A

2,..., A

m /-szeparáló rendszert alkot, akkor (j-^j) > ("). Ez ugyanúgy bizonyítható, mint ahogy a hasonló állítást igazoltuk a 2. Tétel esetén. Hálával tartozom Katona Gyulának a tőle kapott segítségért és biztatásáért, melyet ezúton szeretnék megköszönni.