• ŠIFRA PROJEKTA: J1-70047
• NASLOV PROJEKTA: Krepko regularni grafi in CFSG prosto argumentiranje v algebraični teoriji grafov
• PROJEKTNA EKIPA: dr. Balazs David, dr. Dragan Marušič
• TRAJANJE: 1. 3. 2026 – 28. 2. 2029
• SREDSTVA: 450,000,00 EUR
• FINANCIRANJE: Javna agencija za znanstvenoraziskovalno in inovacijsko dejavnost Republike Slovenije (ARIS)
• KOORDINATOR PROJEKTA: Univerza na Primorskem, Inštitut Andrej Marušič (Slovenija)
• PARTNERJI: InnoRenew CoE, UP IAM (Slovenija); Pedagoška fakulteta Univerze v Ljubljani (Slovenija)

Krepko regularni grafi so kot stična točka kombinatorike, geometrije in algebre predmet številnih raziskav že več desetletij. S stališča algebraične kombinatorike jih lahko smatramo kot kombinatorično aproksimacijo ranga 3 grafov, to je, orbitalnih grafov tranzitivnih permutacijskih grup ranga 3 (t.j. grup, katerih točkovni stabilizator ima poleg fiksne točke dve dodatni orbiti). Medtem ko so slednji seveda popolnoma klasificirani kot posledica Klasifikacije končnih enostavnih grup (CFSG), je klasifikacija celotnega razreda krepko regularnih grafov trenutno še izven našega dosega. Pri obravnavi posebnih razredov krepko regularnih grafov lahko uberemo različne smeri. Eden od pristopov je koncept t-točkovnega pogoja, kjer se zahteva, da so števila določenih podgrafov, ki vsebujejo dani par točk, invariantna grafa. Druga pomembna lastnost krepko regularnih grafih je koncept k-izoregularnosti, kjer se zahteva, da imata poljubni dve podmnožici kardinalnosti največ k, ki inducirata izomorfna podgrafa, enako število sosedov. Oba koncepta pa se srečata pri (m,n)-regularnosti. Grafi, ki zadoščajo t-točkovnemu pogoju soupadajo z (2,t)-regularnimi grafi in kizoregularni grafi soupadajo s (k,k+1)-regularnimi grafi. Dodatna motivacija za predlagani projekt izhaja iz povezave krepko regularnih grafov s tranzitivnimi permutacijskimi grupami ranga 3, ki so zahvaljujoč CFSG znane, kot je omenjeno zgoraj. Toda mnogi, ki se ukvarjajo s permutacijskimi grupami (in posledično algebrajično teorijo grafov), so mnenja, da je treba CFSG uporabljati nekoliko bolj previdno in konzervativno in da je treba, kadar koli je to mogoče, poiskati neposreden dokaz, ki ne vsebuje CFSG. V ta namen bosta skupaj z različnimi drugimi teoretičnimi in kombinatoričnimi orodji v predlaganem projektu bistveno vlogo igrala zgoraj omenjena koncepta – t-točkovni pogoj in k-izoregularnost – in sicer z namenom, da se doseže naslednje tri glavne cilje: (1) Pridobiti strukturne rezultate o krepko regularnih grafih (in bolj splošno, o asociativnih shemah), zlasti o tistih, ki so (2,4)-regularni oziroma (3,4)-regularni. (2) Dokazati (brez uporabe CFSG), da za sodo število n>8 ne obstaja netrivialni 3-izoregularni (krepko regularen) n-bicirkulant. (3) Dokazati (brez uporabe CFSG), da za liho število n netrivialen krepko regularen n-bicirkulant X ne izpolnjuje 4-točkovnega pogoja, razen, če je n=5 in je X Petersenov graf ali njegov komplement.