Teorija grafov

Raziskovalni program naše skupine je, da ostanemo v ospredju raziskav na področju teorije grafov. Nadaljevali bomo z raziskovanjem osrednjih, standardnih področij teorije grafov. Poleg tega nameravamo biti korak pred konkurenco ter raziskati in predstaviti nove koncepte, tehnike in aplikacije. Med področji, ki jih še posebej načrtujemo, so teorija dominacije, metrična teorija grafov, barvanja grafov, kemijska teorija grafov, grafovski produkti, hamiltonskost, topološka in geometrijska teorija grafov ter aplikacije teh področij. Sledi kratek povzetek nekaterih problemov in tem, ki jih bomo raziskali. V teoriji dominacije bomo raziskali število optimalnih množic za dominacijske invariante, problem iskanja grafov z enoličnimi optimalnimi množicami, različne igre dominacije in Grundy-jeve invariante. V metrični teoriji grafov se bomo osredotočili na raznolikost metrično definiranih podrazredov hiperkock, Hausdorffovo razdaljo, Wienerjev indeks grafov in povezavo med metrično teorijo grafov ter usmerjenimi matroidi. Posebej bomo raziskali marjetične kocke in marjetične grafe grafov s korenom, Pell-ove grafe, kockaste komplemente grafov in povezavo med statističnim učenjem in geometrijskimi lastnostmi podgrafov hiperkock. Glavne teme barvanj grafov bodo pakirna barvanja in S-pakirna barvanja ter različna razdaljna barvanja. V kemijski teoriji grafov načrtujemo razvoj splošnega pristopa za določanje ekstremnih struktur za nekatere topološke indekse, ki temeljijo na stopnji vozlišča, raziskave resonančnih grafov in določitev najučinkovitejšega modela za napovedovanje fizikalno-kemijskih lastnosti nenasičenih ogljikovodikov. Za produkte grafov nameravamo preučiti nekatere posebne problem ter poglobljeno raziskati lastnosti direktnega-ko-direktnega produkta in modularnega produkta. Za hamiltonskost bomo raziskali problem, ali je mogoče Thomassenov rezultat izboljšati za (seznamska) barvanja Eulerjevih triangulacij, raziskati problem, ali Chvatalova domneva velja za dvodelne grafe, in raziskati, ali so vsi 1-togi dvodelni grafi prizmično-hamiltonski. Na področju topološke in geometrijske teorije grafov bomo preučevali strukturo prekrižno kritičnih grafov, rod in prekrižno število redkih, gostih in naključnih objektov, grafovski izomorfizem geometrijsko predstavljenih grafov ter uporabo algebrskih tehnik v geometrijskih in topoloških grafih. Skupaj z mnogimi od naštetih tem bomo raziskovali tudi algoritmične vidike.

Program spada med temeljne raziskave s področja matematike in povezanih področij kot je računalništvo. Problemi, ki jih rešujemo in si jih zastavljamo, so mednarodno pomembni, kar med drugim dokazuje naša bibliografija iz zadnjega obdobja in odmevnost rezultatov. Bibliografija izpričuje, da smo po eni strani uspeli rešiti številne probleme, med katerimi so bili nekateri odprti daljše obdobje in so jih (neuspešno) poskušale reševati druge skupine raziskovalcev. Po drugi strani smo zastavili več novih problemov in smeri raziskovanja, ki so v svetu naleteli na velik odmev; naj omenimo teorijo igre dominacije, koncept najmanjših po poteh k-vozliščnih pokritij, koncept M-polinoma, krepkih geodetskih množic in grafovskega problema vozlišč v splošni legi. Naš cilj je nadaljevati raziskave v obeh smereh, torej reševanje pomembnih odprtih problemov in odpiranje novih področij raziskovanja. Obravnavani problemi so osrednji v teoriji grafov, hkrati pa imajo aplikacije v drugih znanostih. Tako na primer rezultati o ogljikovih nanoocevkah lahko pripomorejo pri sintezi nanomolekul in pospešijo razvoju nanomaterialov. Razdalja med grafi se uporablja na različnih znanstvenih področjih, kjer se proučujejo podobnosti med objekti. Nov pogled na te probleme s stališča razdalje med grafi pripomore k nadaljnjemu razvoju in novemu pogledu na obstoječe probleme, predvsem s področja biologije, računalništva, kemije, socioloških znanosti in lingvistike. Študija grafovskih invariant obravnava nekatere pomembne realne probleme. Tako na primer pri problemu dodeljevanja frekvenc iščemo optimalno dodelitev frekvenc za oddajnike v brezžičnem omrežju. Pričakujemo, da bomo rezultate tega raziskovalnega programa objavili v vodilnih mednarodnih revijah s področja diskretne matematike in predstavili na mednarodnih znanstvenih konferencah. Pričakujemo, da bomo imeli večje število vabljenih plenarnih predavanj, kar bo še povečalo pomen naših raziskovalnih dosežkov. S tem bomo še okrepili že sedaj zavidljiv mednarodni ugled slovenske šole teorije grafov.

Program deluje na področju čiste matematike, zato je težko izmeriti njegov neposredni vpliv na gospodarstvo in družbo. Vendar pa je raziskovalni program usmerjen k spodbujanju vključevanja najbolj perspektivnih mladih raziskovalcev in s tem omogoča dolgoročno ohranjanje kvalitetnega raziskovalnega dela s področja matematike, kar ima pozitiven vpliv na kvaliteto univerzitetnih programov matematike in drugih znanosti. V obdobju 2016-2021 smo v našem programu mentorirali 5 doktorskih študentov iz ARRS programa mladih raziskovalcev in dodatnih 14 doktorskih študentov, ki niso bili financirani v okviru tega ARRS programa. Naši doktoranti se po koncu usposabljanja zaposlujejo tudi v gospodarstvu, kar ima pozitiven vpliv na gospodarstvo. Ker je matematika prisotna na mnogih drugih področjih, kvalitetno raziskovanje matematike posredno vpliva tudi na razvoj vrste drugih disciplin. Znotraj matematike pa program predvsem razvija teorijo grafov in s tem ohranja in krepi njen svetovni nivo. Pričakovani rezultati so predvsem teoretični. Kljub temu pa imajo veliko potencialno uporabo v praksi, kar se posebej nanaša na naša algoritmična in optimizacijska raziskovanja. To dobro potrjujejo dosedanje raziskave, ki so pripeljale do sodelovanja s slovensko industrijo s področja tehnološkega razvoja, predvsem v informacijskih in telekomunikacijskih tehnologijah. Natančneje, bili smo soustanovitelji zagonskega podjetja DataBitLab d.o.o. (2018) in sodelovali v svetovalni skupini Ministrstva za zdravje o modeliranju COVID-19. Delovali smo tudi kot mentorji študentskim inovacijskim projektom za družbeno korist, kar je privedlo do spletnih aplikacij. Člani programa so bili tudi med glavnimi organizatorji 9. slovenske mednarodne konference o teoriji grafov v letu 2019, ki je bila s 300+ udeleženci največji dogodek v teoriji grafov v letu 2019. Če povzamemo, podprli smo dolgoročno nadaljevanje kakovosti raziskav v matematiki, kar pomembno vpliva na kakovost univerzitetnih programov iz matematike in drugih znanosti. Kot neposreden vpliv projekta lahko navedemo tudi dejstvo, da podpira nadaljevanje raziskovalnih stikov slovenskih znanstvenikov z najsodobnejšim razvojem. To vključuje tudi v zadnjem obdobju vzpostavljeno sodelovanje s priznanimi raziskovalci, ki predstavljajo svetovno priznano madžarsko kombinatorično šolo.