témavezető: Katona Gyula Y.
helyszín (magyar oldal): Számítástudományi és Információelméleti Tanszék helyszín rövidítés: SZIT
A kutatási téma leírása:
A Hamilton-kör fogálmát többféleképp is lehet általánosítani hipergráfokra. Az egyik érdekesnek tűnő ilyen definíció Katona-Kirstead 1999-ben megjelent cikkében található:
Egy r-uniform hipergráf Hamilton-köre a hipergráf pontjainak olyan ciklikus sorrendbe való elrendezése, hogy bármely r szomszédos pont ebben a sorrendben a hipergáfnak éle.
Az első eredmény evvel kapcsolatban egy Dirac-típusú elégséges feltétel bizonyítása volt, melyet később Rödl, Rucsinski és Szemerédi javítottak meg. Az eltelt 18 évben több mint 50 cikket írtak a témakörben. Mivel a problémák általában nehezebbnek bizonyultak, mint gráfok esetén, a legtöbb esetben az eredmények nem élesek még, vagy van lehetőség még más jellegű javításra. Ezen kívül még számtalan olyan kérdés is van, amivel nem foglalkoztak érdemben.
A példa kedvéért pár konkrét megoldandó feladat:
• Ore-típusú feltétel Hamilton-kör létezésére
• Legfeljebb hány éle lehet egy Hamilton-kört nem tartalmazó hipergráfnak?
• Particionálható-e a teljes gráf élhalmaza Hamilton-körök uniójára?
előírt nyelvtudás: angol további elvárások: gráfelméleti ismeretek