Projekti / Programi
Prehodnost v točkovno tranzitivnih grafih
| 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 |
hamiltonska pot, hamiltonski cikel, točkovno tranzitiven graf, Cayleyev graf, grupa avtomorfizmov
Raziskovalci (16)
Organizacije (4)
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
