Gráfok színezése általában a csúcshalmaz vagy az élhalmaz partícióját jelenti bizonyos feltételek betartásával. Számos érdekes gráfparaméter definiálható ilyenek által, a legalapvetőbb és legismertebb a kromatikus szám, de ennek számos változata, finomítása is megemlíthető a frakcionális kromatikus számtól a cirkuláris kromatikus számon át a lokális kromatikus számig. Kicsit más természetű, de szintén a gráfszínezési témakörökhöz sorolható a Ramsey elmélet gráfokat érintő része. Itt általában azt vizsgáljuk, hogy ha egy gráf éleit tetszőleges módon színezzük meg adott számú színnel, akkor milyen és mekkora valamilyen értelemben rendezett színezett részstruktúrák, például egyszínű, vagy éppenséggel teljesen tarka teljes részgráfok megjelenése garantált. Az említett színezési problémák mindkét típusa összefügg az információelméletnek a zéró-hibájú kommunikáció lehetőségeit vizsgáló ágával, melynek problémái gyakran vezetnek gráfelméleti kérdésekre. A híres és általában megoldatlan, gráfok Shannon kapacitásának értékét vizsgáló kérdés irányított gráfokra tekintett általánosításánál, az ún. Sperner kapacitásnál pl. az egyik legjobb ismert felső becslés a lokális kromatikus szám irányított változatának használatával kapható, míg az a kérdés, hogy egy háromszögmentes gráf (komplementerének) Shannon kapacitása lehet-e akármilyen nagy, Erdősnek egy híres és szintén máig megoldatlan Ramsey elméleti kérdésével ekvivalens. Gráfszínezésekkel és különösen a Ramsey elmélettel kapcsolatban számos kérdés különféle játékok formájában is felvethető, az ezek során megengedett kommunikáció pedig újabb kapocs lehet az információelmélet felé is.
A témára jelentkező hallgató feladata ilyen típusú kérdések vizsgálata, a hatalmas irodalom egy kiválasztott részének áttekintése után olyan részproblémák mélyebb tanulmányozása, ahol esély látszik a nyitott kérdések jobb megértésére, azokban való előrelépésre.
előírt nyelvtudás: angol felvehető hallgatók száma: 1
Jelentkezési határidő: 2024-05-31
2024. IV. 17. ODT ülés Az ODT következő ülésére 2024. június 14-én, pénteken 10.00 órakor kerül sor a Semmelweis Egyetem Szenátusi termében (Bp. Üllői út 26. I. emelet).
Bejelentkezés
