Temeljni projekt J1-9110
Prehodnost v točkovno tranzitivnih grafih
Naslov projekta: Prehodnost v točkovno tranzitivnih grafih
Vodja projekta: Klavdija Kutnar
Šifra projekta: J1-9110.
Tip projekta: temeljni projekt.
Financer: Javna agencija RS za raziskovalno dejavnost (ARRS).
Raziskovalno področje (ARRS): 1.01.00 - Naravoslovno-matematične vede / Matematika.
Trajanje projekta: 1. 7. 2018 - 30. 6. 2021.
Cenovna kategorija projekta: B.
Letni obseg projekta: 0.86 FTE (1.468 raziskovalnih ur).
Sicris profil projekta je dostopen tukaj.
Raziskovalne organizacije v okviru katere se izvaja projekt:
Univerza na Primorskem, Inštitut Andrej Marušič
Univerza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologije,
Univerza v Ljubljani, Pedagoška fakulteta.
InnoRenew CoE
Člani raziskovalnega projekta:
| Kutnar Klavdija (vodja, ARRS šifra: 24997) |
| Hujdurović Ademir (ARRS šifra: 32518) Miklavič Štefko (ARRS šifra: 21656) |
| Požar Rok (ARRS šifra: 32026) |
| Milanič Martin (ARRS šifra: 30211) |
| Frelih Boštjan (ARRS šifra: 24999) Šparl Primož (ARRS šifra: 23341) |
| Kiss Gyorgy (ARRS šifra: 38347) |
| Szonyi Tamas (ARRS šifra: 51192) |
| Burnard Michael (ARRS šifra: 36182) |
| Kresz Miklos (ARRS šifra: 50985) |
| Filipovski Slobodan (ARRS šifra: 37715) |
| Nevena Mitrović (ARRS šifra: 50673) |
| Penjić Safet (ARRS šifra: 37553) |
| Žiga Velkavrh (ARRS šifra: 50720) |
Povzetek projekta:
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.