Loading...
Projekti / Programi vir: ARRS

Prehodnost v točkovno tranzitivnih grafih

Raziskovalna dejavnost

Koda Veda Področje Podpodročje
1.01.00  Naravoslovje  Matematika   

Koda Veda Področje
P110  Naravoslovno-matematične vede  Matematična logika, teorija množic, kombinatorika 

Koda Veda Področje
1.01  Naravoslovne vede  Matematika 
Ključne besede
hamiltonska pot, hamiltonski cikel, točkovno tranzitiven graf, Cayleyev graf, grupa avtomorfizmov
Vrednotenje (pravilnik)
vir: COBISS
Raziskovalci (16)
št. Evidenčna št. Ime in priimek Razisk. področje Vloga Obdobje Štev. publikacij
1.  36182  dr. Michael David Burnard  Gozdarstvo,  lesarstvo in papirništvo  Raziskovalec  2018 - 2021  138 
2.  37715  dr. Slobodan Filipovski  Matematika  Raziskovalec  2018 - 2020  29 
3.  24999  dr. Boštjan Frelih  Matematika  Raziskovalec  2018 - 2021  14 
4.  32518  dr. Ademir Hujdurović  Matematika  Raziskovalec  2018 - 2021  93 
5.  38347  dr. György Kiss  Matematika  Raziskovalec  2018 - 2021  35 
6.  50985  dr. Miklos Kresz  Računalništvo in informatika  Raziskovalec  2018 - 2021  85 
7.  24997  dr. Klavdija Kutnar  Matematika  Vodja projekta/programa  2018 - 2021  240 
8.  02507  dr. Aleksander Malnič  Matematika  Raziskovalec  2019 - 2021  243 
9.  21656  dr. Štefko Miklavič  Matematika  Raziskovalec  2018 - 2021  183 
10.  30211  dr. Martin Milanič  Matematika  Raziskovalec  2018 - 2021  295 
11.  37553  dr. Safet Penjić  Matematika  Mladi raziskovalec  2018 - 2020  42 
12.  50673  Nevena Pivač  Matematika  Mladi raziskovalec  2018 - 2021  23 
13.  32026  dr. Rok Požar  Matematika  Raziskovalec  2018 - 2021  37 
14.  51192  dr. Tamas Istvan Szonyi  Matematika  Raziskovalec  2018 - 2021  59 
15.  23341  dr. Primož Šparl  Matematika  Raziskovalec  2018 - 2021  175 
16.  50720  dr. Žiga Velkavrh  Matematika  Mladi raziskovalec  2018 - 2021  10 
Organizacije (4)
št. Evidenčna št. Razisk. organizacija Kraj Matična številka Štev. publikacij
1.  0588  Univerza v Ljubljani, Pedagoška fakulteta  Ljubljana  1627082  31.309 
2.  1669  Univerza na Primorskem, Inštitut Andrej Marušič  Koper  1810014007  10.043 
3.  2790  Univerza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologije  Koper  1810014009  18.003 
4.  3770  InnoRenew CoE Center odličnosti za raziskave in inovacije na področju obnovljivih materialov in zdravega bivanjskega okolja  Izola  7233817000  2.514 
Povzetek
Projekt obravnava dobro poznano odprto domnevo, ki jo je leta 1969 postavil Lovász in povezuje dva navidezno nepovezana pojma - prehodnost in simetrijo: Ali ima vsak povezan točkovno tranzitiven graf (graf X, katerega grupa avtomorfizmov Aut(X) deluje tranzitivno na množici točk V(X) ali TTG na kratko) hamiltonsko pot (enostavno pot, ki vsebuje vse točke grafa)? Protiprimera za zapisano domnevo ne poznamo. Poleg tega so izmed vseh znanih povezanih točkovno tranzitivnih grafov znani le štirje grafi na vsaj treh točkah, ki nimajo hamiltonskega cikla - enostavenega cikla, ki vsebuje vse točke grafa. Dejstvo, da noben izmed teh štirih grafov ni Cayleyev (t.j. TTG, katerega grupa avtomorfizmov premore regularno podgrupo (Cayleyevo grupo)), je pripeljalo do splošne domneve, da ima vsak povezan Cayleyev graf hamiltonski cikel. V projektu bo problem obstoja hamiltonskih poti in ciklov v povezanih TTG-ih poimenovan HPC problem. Ta problem je bil/je eden izmed glavnih katalizatorjev razvoja algebraične teorije grafov, ki je ena od najhitreje rastočih raziskovalnih področij v diskretni matematiki. Kubični TTG imajo osrednji položaj v trenutnih raziskavah tega problema, in sicer zaradi očitnega razloga: pomanjkanje povezav intuitivno otežuje iskanje poti ali ciklov, kar podpira dejstvo, da so vsi znani TTG brez hamiltonskih ciklov kubični. Cilj projekta je narediti pomemben prispevek v smeri popolne rešitve HPC problema, s posebnim poudarkom na Cayleyevih grafih.
Pomen za razvoj znanosti
V večini predlagani projekt sestoji iz posebnih delov projektne prijave na javni razpis ERC Consolidator Grant 2017, ki je prejela oceno B. Prvotna ERC prijava je bila 5 letni predlog v obsegu 1.3 milijonov EUR, medtem ko je tu predlagana prijava 3 letni predlog v obsegu 300.000 EUR. Zaradi tega predlagani projekt vsebuje le posebne dele prvotne prijave na ERC Consolidator Grant. S financiranje predlaganega projekta bo ARRS omogočil izboljšanje omenjene ERC prijave za enega izmed razpisov za ERC Grant v prihadnjih letih. Obenem bodo znanstveno-raziskovalni rezultati v okviru tega projekta odprli nove usmeritve pri iskanju rešitve enega izmed najpomembnejših odprtih problemov v algebraični teoriji grafov.
Pomen za razvoj Slovenije
This proposal draws from certain parts of the PI application for the ERC Consolidator Grant Open Call 2017 which on the interval A-B-C received a B mark. The original ERC proposal was a 5-year proposal with a total budget of 1.3 million EUR, whereas this ARRS project proposal is a 3-year proposal with a budget of 300.000 EUR. This explains why only parts of the original ERC Consolidator Grant proposal are included in this proposal. Among other the ARRS support for this project will enable us to improve on the PI application to ERC Grant Open Call in the future. Furthermore, the results obtained within this project will serve as a basis for new directions in the pursuit of the solution to one of the most important open problems in algebraic graph theory.
Najpomembnejši znanstveni rezultati Vmesno poročilo
Najpomembnejši družbeno–ekonomsko in kulturno relevantni rezultati Vmesno poročilo
Zgodovina ogledov
Priljubljeno