Matematikai Lapok 2012/1 [antikvár]

Részlet: MAXIMÁLIS HALMAZRENDSZEREK KIZÁRT POSETEKKEL BURCSI PÉTER, NAGY T. DÁNIEL Ha P egy véges poset (részbenrendezett halmaz), akkor La (n,P) jelöli az [n] alaphalmaz részhalmazaiból álló legnagyobb olyan T halmazrendszer elemszámát, ami nem tartalmazza P-t részposetként. Meghatározzuk La(n, P) értékét végtelen sok P esetén. Ezek olyan posetek lesznek, amelyek hét elemi posetből építhetők fel két művelet segítségével. Felső korlátot adunk La (n, P)-re tetszőleges P esetén, ez P elemszámától és a leghosszabb láncának méretétől függ majd. Mindezekhez bevezetünk egy új módszert, .F-nek nem a láncokkal, hanem az úgynevezett vastag láncokkal vett metszeteit vizsgáljuk. 1. Bevezetés Az [n] = {1.2, , n} véges alaphalmaz részhalmazaiból álló, valamilyen tartalma-zási konfigurációtól mentes T halmazrendszereket vizsgálunk. Definíció. Legyen P egy véges poset, T pedig az [n] részhalmazaiból álló halmazrendszer. Azt mondjuk, hogy T tartalmazza F-t, ha valamilyen / : P —» T injektív leképezésre teljesül a < b =4> /(a) C f(b) minden a,b € P esetén. Ha J- nem tartalmazza P-t, akkor P-mentesnek nevezzük. Legyen La (n, P) az [n] részhalmazaiból álló legnagyobb P-mentes halmazrendszer elemszáma. Ne feledjük, hogy P-t nem feszített részposetként keressük, tehát T elemei több relációt is teljesíthetnek, mint P elemei. A célunk az, hogy meghatározzuk La (n,P) értékét minél több poset esetén. Az első ilyen jellegű tétel Spernertől származik, amit Erdős általánosított. 1.1. tétel (Sperner) [8]. Legyen T az [n] alaphalmaz részhalmazaiból álló halmazrendszer. Ha T egyik eleme sem részhalmaza egy másiknak, akkor 1.2. tétel (Erdős) [3]. Legyen T az [n] alaphalmaz részhalmazaiból álló halmazrendszer. Ha nincs T-nek k + 1 olyan eleme, amelyekre A1 C A2 C C Ak+Í teljesül (k < n), akkor |J"| legfeljebb annyi, mint a k legnagyobb n szerinti binomiális együttható összege. Ez a korlát nem javítható, hiszen választhatjuk azokat az F halmazokat, amikre [^Mpt1] < \F\ < [j10^1 j • (1) 1