témavezető: Simonyi Gábor
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 kromatikus szám az egyik legtöbbet vizsgált gráfparaméter. Irodalma óriási, viselkedése egyes helyzetekben ismert, másokban megértetlen. A rokon paraméterek száma is igen nagy. A jelen témakiírásra jelentkezők első számú feladata a hatalmas irodalom valamely olyan szeletének (témavezetői segítséggel történő) kiválasztása, melyben szívesen elmélyednek, majd ennek áttekintése után közösen kiválasztott nyitott problémákon való gondolkodás. Példa a gráfszínezéseken belüli részterületre a következő. Gráfoknak sokféle szorzatát szokás definiálni, s ha a gráfot többször önmagával szorozzuk, az eredményt a gráf hatványának hívjuk. A különböző szorzások, illetve hatványozások által létrejövő gráfok kromatikus számának értéke rendszerint szoros kapcsolatban áll az összeszorzott gráfok kromatikus számának értékével. Ezt a kapcsolatot esetenként szép tételek fejezik ki, máskor csak bizonyítatlan sejtések ismertek. Az egyik ilyen, Hedetniemitől származó, több, mint ötven éves sejtést nemrégiben cáfolták meg, megmutatva, hogy két gráf ún. tenzorszorzatának kromatikus száma lehet kisebb a szorzatban szereplő mindkét gráf kromatikus számánál. Hamarosan kiderült az is, hogy két n-kromatikus gráf szorzatának lehetséges minimális kromatikus száma és n hányadosa határértékben legfeljebb 1/2. Továbbra is nyitott kérdés, hogy valójában hova tart ez a hányados, könnyen lehet, hogy 0-hoz. Ez a kérdés még mindig lehet nagyon nehéz, de 2019-ben felgyorsultak körülötte az események és nem kizárható, hogy ezáltal sikerrel támadhatóvá váljon.
Számos kérdés nyitott az utóbbi másfél évtizedben többek által vizsgált lokális kromatikus számmal kapcsolatban. Ez a paraméter mindig a hagyományos és az annál sosem nagyobb, ún. tört kromatikus szám közé esik, különösen olyan gráfokra viselkedik tehát érdekesen, amiknél e kettő távol esik egymástól. Az ilyen gráfok között alapvetőek a Kneser gráfok. Miközben tisztázott, hogy az ezek színkritikus részgráfjaiként megjelenő Schrijver gráfok lokális kromatikus száma megfelelően nagy paraméterek esetén a kromatikus számnak körülbelül a fele, még mindig nyitott, hogy egy Kneser gráf lokális kromatikus száma lehet-e a kromatikus számánál kisebb. Szintén izgalmas kérdés, hogy egy gráf Descartes hatványainak lokális kromatikus száma tart-e mindig a gráf kromatikus számához.
A kromatikus szám és különböző változatainak vizsgálatát számos esetben motiválják a gyakorlatból származó, tipikusan valamiféle időbeosztás elkészítésével kapcsolatos problémák. Mindemellett, a jelen témakiírás elsősorban olyanoknak szól, akiket ezen kérdések elméleti oldala érdekel, és egy-egy tisztán gráfelméleti problémán önmagáért is szívesen gondolkoznak.
felvehető hallgatók száma: 1
Jelentkezési határidő: 2020-06-15
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
