Novi trendi v kromatični teoriji grafov
natisniNaslov projekta:
Novi trendi v kromatični teoriji grafov
izr. prof. dr. Riste Škrekovski
UP FAMNIT
Javna agencija RS za raziskovalno dejavnost (ARRS)
Znanstveno-raziskovalno sodelovanje med RS in ZDA
1.01.05 - Naravoslovje / Matematika / Teorija grafov
1.2.2017 - 31.12.2018
Predstavitev projekta:
Teorija grafov je mlada veja matematike. Njeni začetki segajo v 18. stoletje, ko je Euler postavil temelje z rešitvijo problema K\"{o}nigsbergških mostov. Kasneje, okrog leta 1852, se je pojavil Problem štirih barv in postal eden izmed osrednjih problemov na tem področju. Več kot sto let je bilo potrebnih za dokaz pozitivnega odgovora na vprašanje problema, edini znani dokazi pa temeljijo na pomoči računalnikov. Problem je pritegnil znanstvenike z vseh področij matematike in prispeval k razvoju novih metod ne le v diskretni matematiki, temveč tudi v algebri, topologiji, računalništvu in drugih. Kromatična teorija grafov je še vedno ena izmed najpomembnejših vej teorije grafov, veji pa se na veliko število raziskovalnih smeri oziroma tipov problemov.
Osnovni problem v kromatični teoriji grafov je določitev najmanjšega števila barv, s katerimi lahko označimo vozlišča grafa tako, da imajo sosednja vozlišča različne barve. V splošnem, pa tudi v mnogih posebnih primerih, je problem NP-težek. S poznavanjem dodatnih strukturnih lastnosti, kot so na primer vložitve na ploskve, omejene minimalne stopnje ali prepovedane podstrukture, pa lahko problem poenostavimo.
Skozi čas se je razvilo veliko število različic barvanj grafov, motiviranih tako s problemi iz vsakdanjega življenja kot tudi s teoretično uporabo. Med najbolj raziskovanimi so različni tipi seznamskih barvanj in barvanj povezav.
Seznamsko barvanje je naravna posplošitev običajnega barvanja, kjer vsakemu vozlišču priredimo seznam razpoložljivih barv namesto univerzalnega seznama barv, ki so na voljo vsem vozliščem. Prav Thomassenov rezultat o seznamskih barvanjih ravninskih grafov je eden izmed najbolj odmevnih rezultatov v kromatični teoriji grafov. Pri reševanju problemov seznamskih barvanj se uporabljajo različne napredne algebraične tehnike, kot na primer metoda Alon-Tarsi, ki uporablja orientacije.
Barvanje povezav je vrsta barvanja, pri katerem namesto vozlišč barvamo povezave. Temeljni rezultat na tem področju je Vizingov izrek, ki pravi, da potrebujemo vsaj toliko barv kot je maksimalna stopnja grafa in največ eno več. Čeprav je barvanje povezav grafa ekvivalentno barvanju vozlišč njegovega povezavnega grafa, je problem sam po sebi zelo atraktiven, zaradi posebnih lastnosti teh grafov. To je tudi eden izmed poglavitnih razlogov, zakaj so kromatične invariante, ki imajo v svoji domeni vozlišča, dobile svoje ekvivalente tudi v domeni povezav.
Temeljni rezultati v kromatični teoriji grafov so dokazi natančnih mej za kromatična števila. Za splošen graf $G$ je Brooks dokazal, da vedno zadošča $\Delta(G)$ barv, kjer je $\Delta(G)$ maksimalna stopnja $G$, razen v primerih, ko je $G$ poln graf ali lih cikel. V razredu ravninskih grafov se meja ustavi že pri štirih barvah, kar pove slavni, zgoraj omenjeni, Izrek o štirih barvah. Natančna zgornja meja je prav tako določena pri barvanju povezav, medtem ko za mnogo različic z dodatnimi predpostavkami poznamo le zelo grobe ocene.
Krepko barvanje povezav je barvanje povezav, pri katerem povezavam priredimo barve tako, da je par povezav na medsebojni razdalji kvečjemu dva, obarvan različno. Trideset let stara domneva, ki sta jo postavila Erd\"{o}s in Ne\v{s}et\v{r}il, je, da za takšno barvanje zadošča $1.25 \ \Delta(G)^2$ barv, trenutno najboljša zgornja meja pa je $1.83 \ \Delta(G)^2$ iz leta 2015, dokazana s pomočjo verjetnostne metode in še ta velja le za grafe z dovolj visoko maksimalno stopnjo. Podobno daleč oziroma še precej dlje smo pri dokazovanju domnevane meje $\Delta(G) + 2$ za aciklično barvanje povezav, pri katerem povezave barvamo tako, da v grafu ne nastane dvobarvni cikel in pogojem, da so dotikajoče se povezave obarvane različno. Tudi pri tej invarianti se dokaz trenutno najboljše meje, $4 \ (\Delta(G)-1)$, opira na uporabo verjetnosti s tako imenovano metodo stiskanja entropije. V obeh opisanih primerih, se številu barv z verjetnostno metodo približujemo z izboljševanjem konstante pri vodilnem členu, medtem ko je red velikosti letega že pravi. Obstajajo pa še težji primeri: v letu 2012, so se Dvo\v{r}\'{a}k, Mohar in \v{S}am\'{a}l ukvarjali z zvezdnim barvanjem povezav, to je pravilno barvanje povezav, z dodatno predpostavko, da v grafu ne nastanejo dvobarvne poti oziroma cikli na štirih povezavah. Dokazali so, da za takšno barvanje polnega grafa na $n$ vozliščih potrebnih največ $n^{1+\epsilon}$ barv in vprašali ali morda ne zadošča število barv, ki je linearno v številu vozlišč. Problem je še vedno široko odprt.
Zgoraj našteti problemi so si na videz podobni, pa vendar vsaka dodatna predpostavka zahteva poglobljeno razumevanje novih lastnosti grafov. Vsem razlikam navkljub, se pri reševanju teh problemov za splošne grafe običajno izkaže, da je pristop z uporabo orodij teorije verjetnosti najbolj učinkovit. Po drugi strani, omejitev na ožje razrede grafov pokaže, da verjetnostna orodja ne premorejo primerne natančnosti, ko se želimo približati pravim mejam. V teh primerih je v veliki meri potrebno odlično razumevanje strukture grafov, kar se je lepo pokazalo pri dokazovanju Izreka štirih barv in večini rezultatov v razredu kubičnih grafov.
Problemi, ki jih rešujemo raziskovalci na tem bogatem področju so temeljne narave. Razširiti želimo razumevanje lastnosti kromatičnih invariant, razviti metode, s katerimi bomo te lastnosti lažje odkrili in posledično izboljšati obstoječe rezultate. Poskusili bomo določiti nove meje za zgoraj naštete in sorodne probleme, najverjetneje z dodatnimi predpostavkami o strukturi grafov.
Obe projektni skupini študirata podobne probleme, vendar pa se razlikujeta v osnovnih področjih. Medtem ko se slovenska skupina osredotoča na probleme barvanj povezav, se skupina iz ZDA posveča seznamskim barvanjem vozlišč. Skupaj se želimo lotiti problemov seznamskih barvanj povezav kot močnejše verzije barvanj povezav, pri čemer bomo lahko uporabili orodja kot npr. izrek Alon-Tarsi ali razširitve predbarvanj, ki niso na voljo brez uporabe seznamov.
Osnovni problem v kromatični teoriji grafov je določitev najmanjšega števila barv, s katerimi lahko označimo vozlišča grafa tako, da imajo sosednja vozlišča različne barve. V splošnem, pa tudi v mnogih posebnih primerih, je problem NP-težek. S poznavanjem dodatnih strukturnih lastnosti, kot so na primer vložitve na ploskve, omejene minimalne stopnje ali prepovedane podstrukture, pa lahko problem poenostavimo.
Skozi čas se je razvilo veliko število različic barvanj grafov, motiviranih tako s problemi iz vsakdanjega življenja kot tudi s teoretično uporabo. Med najbolj raziskovanimi so različni tipi seznamskih barvanj in barvanj povezav.
Seznamsko barvanje je naravna posplošitev običajnega barvanja, kjer vsakemu vozlišču priredimo seznam razpoložljivih barv namesto univerzalnega seznama barv, ki so na voljo vsem vozliščem. Prav Thomassenov rezultat o seznamskih barvanjih ravninskih grafov je eden izmed najbolj odmevnih rezultatov v kromatični teoriji grafov. Pri reševanju problemov seznamskih barvanj se uporabljajo različne napredne algebraične tehnike, kot na primer metoda Alon-Tarsi, ki uporablja orientacije.
Barvanje povezav je vrsta barvanja, pri katerem namesto vozlišč barvamo povezave. Temeljni rezultat na tem področju je Vizingov izrek, ki pravi, da potrebujemo vsaj toliko barv kot je maksimalna stopnja grafa in največ eno več. Čeprav je barvanje povezav grafa ekvivalentno barvanju vozlišč njegovega povezavnega grafa, je problem sam po sebi zelo atraktiven, zaradi posebnih lastnosti teh grafov. To je tudi eden izmed poglavitnih razlogov, zakaj so kromatične invariante, ki imajo v svoji domeni vozlišča, dobile svoje ekvivalente tudi v domeni povezav.
Temeljni rezultati v kromatični teoriji grafov so dokazi natančnih mej za kromatična števila. Za splošen graf $G$ je Brooks dokazal, da vedno zadošča $\Delta(G)$ barv, kjer je $\Delta(G)$ maksimalna stopnja $G$, razen v primerih, ko je $G$ poln graf ali lih cikel. V razredu ravninskih grafov se meja ustavi že pri štirih barvah, kar pove slavni, zgoraj omenjeni, Izrek o štirih barvah. Natančna zgornja meja je prav tako določena pri barvanju povezav, medtem ko za mnogo različic z dodatnimi predpostavkami poznamo le zelo grobe ocene.
Krepko barvanje povezav je barvanje povezav, pri katerem povezavam priredimo barve tako, da je par povezav na medsebojni razdalji kvečjemu dva, obarvan različno. Trideset let stara domneva, ki sta jo postavila Erd\"{o}s in Ne\v{s}et\v{r}il, je, da za takšno barvanje zadošča $1.25 \ \Delta(G)^2$ barv, trenutno najboljša zgornja meja pa je $1.83 \ \Delta(G)^2$ iz leta 2015, dokazana s pomočjo verjetnostne metode in še ta velja le za grafe z dovolj visoko maksimalno stopnjo. Podobno daleč oziroma še precej dlje smo pri dokazovanju domnevane meje $\Delta(G) + 2$ za aciklično barvanje povezav, pri katerem povezave barvamo tako, da v grafu ne nastane dvobarvni cikel in pogojem, da so dotikajoče se povezave obarvane različno. Tudi pri tej invarianti se dokaz trenutno najboljše meje, $4 \ (\Delta(G)-1)$, opira na uporabo verjetnosti s tako imenovano metodo stiskanja entropije. V obeh opisanih primerih, se številu barv z verjetnostno metodo približujemo z izboljševanjem konstante pri vodilnem členu, medtem ko je red velikosti letega že pravi. Obstajajo pa še težji primeri: v letu 2012, so se Dvo\v{r}\'{a}k, Mohar in \v{S}am\'{a}l ukvarjali z zvezdnim barvanjem povezav, to je pravilno barvanje povezav, z dodatno predpostavko, da v grafu ne nastanejo dvobarvne poti oziroma cikli na štirih povezavah. Dokazali so, da za takšno barvanje polnega grafa na $n$ vozliščih potrebnih največ $n^{1+\epsilon}$ barv in vprašali ali morda ne zadošča število barv, ki je linearno v številu vozlišč. Problem je še vedno široko odprt.
Zgoraj našteti problemi so si na videz podobni, pa vendar vsaka dodatna predpostavka zahteva poglobljeno razumevanje novih lastnosti grafov. Vsem razlikam navkljub, se pri reševanju teh problemov za splošne grafe običajno izkaže, da je pristop z uporabo orodij teorije verjetnosti najbolj učinkovit. Po drugi strani, omejitev na ožje razrede grafov pokaže, da verjetnostna orodja ne premorejo primerne natančnosti, ko se želimo približati pravim mejam. V teh primerih je v veliki meri potrebno odlično razumevanje strukture grafov, kar se je lepo pokazalo pri dokazovanju Izreka štirih barv in večini rezultatov v razredu kubičnih grafov.
Problemi, ki jih rešujemo raziskovalci na tem bogatem področju so temeljne narave. Razširiti želimo razumevanje lastnosti kromatičnih invariant, razviti metode, s katerimi bomo te lastnosti lažje odkrili in posledično izboljšati obstoječe rezultate. Poskusili bomo določiti nove meje za zgoraj naštete in sorodne probleme, najverjetneje z dodatnimi predpostavkami o strukturi grafov.
Obe projektni skupini študirata podobne probleme, vendar pa se razlikujeta v osnovnih področjih. Medtem ko se slovenska skupina osredotoča na probleme barvanj povezav, se skupina iz ZDA posveča seznamskim barvanjem vozlišč. Skupaj se želimo lotiti problemov seznamskih barvanj povezav kot močnejše verzije barvanj povezav, pri čemer bomo lahko uporabili orodja kot npr. izrek Alon-Tarsi ali razširitve predbarvanj, ki niso na voljo brez uporabe seznamov.
Oddelek za matematiko
