Izredno veliki grafi in omrežja

V raziskavi se bomo posvetili študiju velikih grafov, kjer je pomemben predvsem odnos med lokalnimi in globalnimi lastnostmi. Najprej bomo razvili osnovne teoretične rezultate. Pri tem želimo nadgraditi obstoječe rezultate, ki so znani za goste grafe (Lovasz, Szegedy, Borgs, Chayes, Sos, Vesztergombi) in za ravninske grafe (Schramm, Angel, LeGall, Marckert in Mokkadem). Usmerili se bomo na več področij in bomo iskali predvsem povezave med analitičnim, algebrajskim in topološkim pristopom. Obdelati nameravamo naslednja področja: študij konvergence in limit grafov, ki so vloženi v sklenjene ploskve, posplošitve na minorno zaprte družine, uporaba nestandardne analize (metrika Gromova in Hausdorffa) za primerjavo velikih objektov, razvoj teorije (verjetnostnih) algoritmov za take družine, študij ustreznih produktov in svežnjev ter razvoj splošnih algoritmov za zelo velike grafe, kjer je dosegljiva samo lokalna informacija.

Projekt spada med bazne raziskave s področja matematike. Problemi, ki si jih zastavljamo, so fundamentalni za razvoj področja in za njegovo uporabo. Pomembnost dokazuje naša bibliografija iz zadnjega obdobja in odmevnost rezultatov. Obravnavani problemi so osrednji v moderni teoriji grafov. Rezultate tega raziskovalnega projekta smo objavili v uglednih znanstvenih revijah in predstavili na mednarodnih znanstvenih konferenceh. V naslednjem obodbju pričakujemo, do bomo imeli večje število vabljenih, med njimi tudi plenarnih predavanj, kar bo še povečalo vidnost naših raziskovalnih dosežkov. S tem bomo okrepili že sedaj zavidljiv ugled slovenske šole teorije grafov.

Doseženi 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. Področje velikih podatkovnih baz in s tem tudi osrednje teme tega projekta je eno od prioritetnih razvojno-raziskovalnih področij na svetu.