Korlátos fokszámú hipergráfok árnyéka Fizika, Földtudományok és Matematika

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

Korlátos fokszámú hipergráfok árnyéka

Helyezés: 3

Hallgató: Jung Attila
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 - kutató professzor emeritus, N N Rényi Alfréd Matematikai Kutatóintézet

Egy k-uniform hipergráf árnyéka az a (k-1)-uniform hipergráf, amely mindazokat a (k-1) elemű halmazokat tartalmazza, amelyek megkaphatók úgy, hogy az eredeti hipergráf egy hiperéléből kihagyunk egy elemet. Hipergráfok árnyékát vizsgáljuk abban az esetben, ha a hipergráf maximális fokszáma valamilyen korlát alatt marad. Az árnyék és a hipergráf méretének hányadosára, az árnyékhányadosra adunk alsó becslést különböző fokszámkorlátok esetén. Megvizsgáljuk a felmerülő egyenlőtlenségeket egyenlőséggel teljesítő extremális hipergráfok kérdését is. Fő eszközeink a Kruskal-Katona Árnyéktétel és Sperner egy lemmája az árnyékhányadosról.