Projekti / Programi
Polregularni elementi v 2-zaprtjih rešljivih grup
| Koda |
Veda |
Področje |
Podpodročje |
| 1.01.00 |
Naravoslovje |
Matematika |
|
| Koda |
Veda |
Področje |
| P001 |
Naravoslovno-matematične vede |
Matematika |
| Koda |
Veda |
Področje |
| 1.01 |
Naravoslovne vede |
Matematika |
polregularni element, 2-zaprtje, rešljiva grupa, problem simultanega konjugiranja, kriptografija
Raziskovalci (12)
Organizacije (3)
Povzetek
Naj bo G permutacijska grupa na končni množici V. Netrivialen element grupe G je polregularen, če ima podgrupa grupe G, ki jo ta element generira, vse orbite enake dolžine. Znano je, da vsaka končna tranzitivna permutacijska grupa vsebuje element brez fiksnih točk, vendar ne nujno tudi takega elementa, ki ima praštevilski red, to je, polregularnega elementa praštevilskega reda. Permutacijski grupi brez polregularnih elementov praštevilskega reda pravimo izmuzljiva grupa, kar je ekvivalentno temu, da sploh nima polregularnih elementov.
Pričakovati je, da imajo “lepi” kombinatorični objekti, kot so na primer grafi, ne-izmuzljive grupe avtomorfizmov. Sploh se je problem prvič zastavil v jeziku teorije grafov, ko je leta 1981 vodja predlaganega projekta vprašal, ali ima vsak točkovno tranzitiven digraf polregularen avtomorfizem. Splošnejša različica tega vprašanja je znana kot policirkulantna domneva, ki vključuje celoten razred 2-zaprtih tranzitivnih grup. Postavil jo je Klin [7,31].
Pri obravnavi problemov iz algebraične teorije grafov, predvsem tistih o tranzitivnih grupnih delovanjih, najtežji del običajno predstavljajo nerešljive grupe, saj je v primeru rešljivih grup mogoče podati vsaj delne rezultate. Pri problemu polregularnosti je slika obrnjena. Tu glavno oviro za popolno rešitev problema predstavlja razred rešljivih grup.
Cilj predlaganega projekta je podati nove usmeritve, ki bi trasirale pot do popolne rešitve problema polregularnosti, pri čemer bomo posebej natančno obravnavali tranzitivne rešljive grupe. Začeli bomo z obravnavo dveh posebnih primerov, ki sta še vedno odprta, kljub temu, da so se z njima ukvarjali že številni matematiki. Vemo, da tranzitivne permutacijske grupe, katerih stopnja je prostih kvadratov, niso izmuzljive. Zato se kot naslednji korak ponuja obravnava tega problema za tranzitivne permutacijske grupe, katerih stopnja je prostih kubov. In drugič, smiselno se je tudi omejiti na posebne valence točkovno tranzitivnih grafov. Znano je namreč, da točkovno tranzitivni grafi stopnje 3 oziroma 4 premorejo polregularne avtomorfizme. Naslednji logični korak je obravnava grafov stopnje 5.
Rezultate o polregularnih avtomorfizmih bomo uporabili tudi pri raziskavah drugih aktualnih tem na področju algebraične teorije grafov: problem hamiltonskosti, obstoj lihih avtomorfizmov, strukturne lastnosti različnih družin grafov, kot so ločno tranzitivni grafi, Cayleyevi grafi, polločno tranzitivni grafi, (kvazi) m-Cayleyevi grafi, itd. Posebej pa izpostavljamo povezavo, ki je bila doslej neopažena in leži na presečišču diskretne matematike in teorije izračunljivosti: za dana končna niza elementov grupe ugotovi, ali obstaja tak grupni element, ki simultano konjugira dana niza. Ta problem je poznan kot problem simultanega konjugiranja. Eden izmed ciljev predlaganega projekta je razviti učinkovite algoritme za reševanje problema simultanega konjugiranja v simetričnih grupah in najti netrivialne spodnje meje za ta problem. Smiselnost obravnave tega problema v okviru predlaganega projekta, leži v dejstvu, da znani Sridharjev algoritem ne deluje, če so vse permutacije v danih nizih polregularne.
Pomen za razvoj znanosti
Eden ključnih konceptov, ki so bistveni za razumevanje naravnih pojavov in dinamiko družbenih sistemov, je koncept "odnosa": človeška prijateljstva, socialna in medsebojna povezovanja, prometni sistemi, kemične strukture, itd. Vse to so konkretni primeri relacijskih struktur. Posebej pomembne so relacijske strukture z visoko stopnjo simetrije, in sicer zato ker take strukture uspešno modelirajo optimalno vedenje in visoko zmogljivost. Matematični model, ki zajame bistvo te situacije, je graf z visoko stopnjo simetrije, osnovna matematična disciplina pa je algebraična teorija grafov. Algebraična teorija grafov je del diskretne matematike, ki vključuje širok spekter metod iz kombinatorike, linearne algebre, permutacijskih grup, reprezentacij grup, asociativnih shem, algoritmov, geometrije, topologije, itd. Medtem ko so nekatere simetrije očitne, so nekatere dodatne simetrije skrite oziroma jih je težko razumeti. Poznavanje celotnega (ali čim boljšega) nabora simetrij je pomembno, ker zagotavlja najbolj popoln opis strukture obravnavanega objekta.
Matematiko mnogi vidijo kot »nevidno mazivo«, ker omogoča učinkovit razvoj tehnološke družbe. Obstaja napačna predstava, da bo tehnologija rešila vse naše težave. Na primer, da po zaslugi zmogljivih računalniških programov uporabniki ne bodo več potrebovali matematičnega znanja. To preprosto ne drži, saj je za uspešno in učinkovito upravljanje novih tehnologij potrebnih vse več matematično in statistično izobraženih mladih. Predlagani projekt bo to idejo zelo učinkovito promoviral.
Pomen za razvoj Slovenije
One of the core concepts essential to understanding natural phenomena and the dynamics of social systems is the concept of “relation”. Human friendships, social and interconnection networks, traffic systems, chemical structures, etc. can be expressed as relational structures. Furthermore, scientists rely on relational structures with high levels of symmetry because of their optimal behavior and high performance. A mathematical model capturing the essence of this situation is a graph exhibiting a high level of symmetry, and the underlying mathematical discipline is algebraic graph theory which is the discipline considered in this proposal. Algebraic graph theory is a part of discrete mathematics involving a wide range of methods from combinatorics, linear algebra, permutation groups, group representations, association schemes, algorithms, geometry, topology, etc. While some symmetries are obvious, certain additional symmetries remain hidden or difficult to grasp. Knowing the full (or as near as possible) set of symmetries of an object is important because it provides the most complete description of that object's structure.
Mathematics has been called the “invisible oil” which keeps our technological society running efficiently. There is a common misunderstanding that technology has solved all our problems. For example, that the availability of powerful computer packages means that users do not require mathematical skills. This is simply untrue. More mathematically and statistically trained young people are needed to use new technology successfully and efficiently. The proposed project is going to spread this message effectively.
Najpomembnejši znanstveni rezultati
Vmesno poročilo
Najpomembnejši družbeno–ekonomsko in kulturno relevantni rezultati
Vmesno poročilo
