Raziskovalni projekt (so)financira Javna agencija za raziskovalno dejavnost RS.
Članica UL: Fakulteta za matematiko in fiziko
Šifra projekta: N1-0218
Naziv projekta: Prepletanje geometrije, topologije in algebre v strukturni in topološki teoriji grafov
Obdobje: 1. 4. 2022 - 31. 3. 2025
Letni obseg: 0,7 FTE cenovna kategorija: C
Vodja: Bojan Mohar
Veda: Naravoslovje
Sodelujoče RO, sestava projektne skupine in bibliografske reference
Vsebinski opis projekta:
Hadwigerjeva hipoteza iz leta 1943 trdi, da vsak graf s kromatičnim številom k vsebuje poln graf reda k kot minor. Številni menijo, da je ta hipoteza iz strukturalne teorije grafov najbolj izstopajoč problem v teoriji grafov, njegova rešitev pa bi pomembno vplivala na teorijo algoritmov. Hipoteza Hilla in Turana iz petdesetih let 20. stoletja govori o najbolj "učinkovitem" načinu risanja polnih grafov in polnih dvodelnih grafov v ravnini, kar pomeni, da želimo imeti čim manjše število križanj v risbi. Tretji glavna smer projekta je problem izomorfizma grafov, ki igra temeljno vlogo v teoretičnem računalništvu in za katerega ne poznamo niti približne računske zahtevnosti. Ta tri temeljna vprašanja v teoriji grafov in teoretičnem računalništvu so dolgoletni odprti problemi in predstavljajo dolgoročne cilje naših raziskav.
Ti problemi imajo zelo enostavno formulacijo, vendar jih še zdaleč ne razumemo, kljub temu, da je bilo razvitih ogromno matematičnih orodij za njihovo reševanje. Za nadaljnji napredek pri razumevanju teh problemov in njihovih variacij bomo uporabili metode iz geometrije, topologije in algebre, ki se pojavljajo v teoriji grafov in algoritmov. Čeprav se problemi zdijo povsem različni, imajo metode za delni napredek pri reševanju veliko skupnega. S proučevanjem grafov na ploskvah, limit risb grafov, naključnih vložitev, algoritmov za konjugacijo v simetrični grupi ter algebrajskih in topoloških mej za kromatično število in za polne minorje v grafih upamo, da bomo bolje razumeli temeljne probleme ter nekatere izmed njih tudi dokončno rešili.
