Raziskovalni projekt (so)financira Javna agencija za raziskovalno dejavnost RS.
Članica UL: Fakulteta za matematiko in fiziko
Šifra projekta: N1-0216
Naziv projekta: Simetrije, negibnost in prožnost grafov
Obdobje: 1. 10. 2021 - 30. 9. 2024
Letni obseg: 0,8 FTE cenovna kategorija: B
Vodja: Primož Potočnik
Veda: Naravoslovje
Sodelujoče RO, sestava projektne skupine, bibliografske reference
Vsebinski opis projekta:
Projekt govori o simetriji. Ohlapno povedano, obravnavati nameravamo naslednja vprašanja: Kako simetričen je lahko matematični objekt? Kako visoka stopnja simetrije vpliva na lastnosti objekta? Katere strukturne lastnosti objekta mu preprečujejo visoko simetričnost in katere jo zagotavljajo?
V matematiki pravimo, da je objekt visoko simetričen, kadar ima "bogato" grupo avtomorfizmov. Pri tem lahko pojem "bogat" pomeni bodisi "ima velik red" ali pa "deluje na nek poseben način" (na primer: tranzitivno) na sestavljajočih delih objekta. Naš projekt pa se bo osredotočil na manj raziskana vidika simetrije, ki ju bomo imenovali "prožnost" in "negibnost".
Negibnost diskretnega objekta (kot je, na primer, graf) je definirana kot maksimalno število točk objekta, ki jih lahko pribije netrivialna simetrija. Objektu rečemo, da je "prožen", če ima "veliko" negibnost (kjer se pomen pridevnika "velik" spreminja glede na konkretni kontekst). Raziskovanje negibnosti ima dolgo zgodovino na področju permutacijskih grup, presenetljivo pa je, da je zelo malo znanega na področju diskretnih objektov.
Cilj projekta je pričeti s sistematičnim in poglobljenim raziskovanjem teh pojavov s poudarkom na povezavi med negibnostjo in strukturnimi omejitvami objektov. Poleg radovednosti in splošne želje po razumevanju teh konceptov pa je najpomembnejša gonilna sila naših raziskav želja po napredku pri nekaterih težkih in dolgo znanih odprtih problemih teorije grafov, kot je, na primer, domneva o policirkulantih. Verjamemo, da bo koncept negibnosti grafov pomagal pri spopadanju z nekaterimi od teh problemov.
Rezultati in dosežki projekta:
- faza projekta, je vsebovala tri cilje:
Cilj 1: Uporaba znanih rezultatov o primitivnih permutacijskih grupah pri dokazovanju rezultatov o negibnosti grafov, ki premorejo primitivno grupo avtomorfizmov.
V prvi fazi smo pregledali rezultate o primitivnih permutacijskih grupah in identificirali družine vozliščno tranzitivnih grafov, ki premorejo primitivno grupo avtomorfizmov. Mednje sodijo polni grafi, Kneserjevi grafi ter Johnsonovi grafi. Polna klasifikacija še ni povsem izdelana zaradi tehničnih težav, ki se pojavljajo pri produktnem tipu primitivnih grup.
Cilj 2: Raziskovanje negibnosti nepremitivnih permutacijskih grup. Karakteriziranje neprimitivne permutacijske grupe z veliko negibnostjo v duhu Jordanovih rezultatov za primitivne grupe.
S podoktorskim raziskovalcem Antoniom Monterom smo raziskali situacijo, ko neprimitivna permutacijska grupa vsebuje element, ki pribije vse razen 4 točk. Gre za prvi dokazani rezultat tega tipa. Karakterizacija je presenetljivo natančna. Metode, ki smo jih razvili bomo v nadaljevanju projekta uporabili v splošnejšem kontekstu permutacijskih grup, ki premorejo permutacijo, ki se zapiše kot produkt k ciklov praštevilske dolžine. Delne rezultate [1] pripravljamo za objavo.
Cilj 3: Raziskovanje povezave med negibnostjo grupe avtomorfizmov, ki se dvigne vzdolž regularnega krova grafa in pripadajoče dvignjene grupe.
Začetne ugotovitve v zvezi s tem ciljem, smo objavili v članku [2], kjer smo dokazali tesno povezavo med negibnostjo grupe in njenega dviga v primeru krovov grafov Praegerja in Xuja. Tehnike, razvite v tem članku, so bile uporabljene tudi v člankih [3,4], kjer se negibnost grafov pojavlja v implicitni obliki.
Reference:
[1] P. Potočnik, A. Montero, Permutation Groups of Small Minimal Degree, v pripravi.
[2] P. Potočnik, P. Spiga, On the number of fixed points of automorphisms of vertex-transitive graphs, Combinatorica vol. 41 (2021), 703--747.
[3] R. Jajcay, P. Potočnik, S. Wilson, On the Cayleyness of Praeger-Xu graphs, J. Combin. Theory Ser. B. vol. 152 (2022), 55--79.
[4] P. Potočnik, J. Vidali, Cubic vertex-transitive graphs of girth 6, Discrete Mathematics, vol. 345 (2022), 112734.
