Kleitman egy tételének általánosítása Fizika, Földtudományok és Matematika

35 OTDK, Fizika, Földtudományok és Matematika Szekció, Kombinatorika és gráfelmélet Tagozat.

Kleitman egy tételének általánosítása

Hallgató: Nagy Kartal Dávid
Szak: Matematikus, Képzés típusa: msc, Intézmény: Eötvös Loránd Tudományegyetem, Kar: Természettudományi Kar

Témavazető: Katona Gyula - egyetemi tanár, Eötvös Loránd Tudományegyetem Természettudományi Kar

Az extremális problémák egyik fajtája, amikor egy n elemű halmaz részhalmazai közül akarunk minél többet kiválasztani úgy, hogy egy adott feltétel teljesüljön rájuk. Az ilyen típusú tételek közül az egyik legismertebb az Erdős-Ko-Rado tétel, amely felső becslést ad az olyan részhalmazok számára, melyben bármely két részhalmaznak a metszete nem üres. Ennek a tételnek rengeteg változata és általánosítása ismert. Közülük az egyik Kleitman tétele, melyben azt kívánjuk meg, hogy semelyik három kiválasztott halmaz metszete ne legyen üres, vagyis bármely három kiválasztott halmazra a páronkénti metszetek összege legalább 1 legyen.

A dolgozat arra a kérdésre keresi a választ, hogy mi történik akkor, ha az 1-es értéket lecseréljük egy másik számra, vagyis legfeljebb hány halmaz adható meg akkor, ha bármely három kiválasztott halmazban a páronkénti metszetösszeg legalább t. Először az uniform esetet vizsgálom meg: egy felső becslést adok t=2 esetén, majd alsó becslésként mutatok egy konstrukciót, és kellően nagy n esetén belátom, hogy ez a konstrukció optimális, vagyis nem adható meg ennél több halmaz. Végezetül a nem-uniform esetet vizsgálom meg, melynek végén egy pontos értéket adok a kiválasztható halmazok maximális számára akkor, ha a t felírható 3n-6p alakban, ahol az n kellően nagy a p-hez képest.