Projekti / Programi
Razdaljno-regularni grafi: nerazcepni T-moduli s krajiščem 1 in delovanje grupe automorfizmov
| Koda |
Veda |
Področje |
Podpodročje |
| 1.01.05 |
Naravoslovje |
Matematika |
Teorija grafov |
| 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 |
razdaljno-regularni graf, nerazcepni T-modul, grupno delovanje, grupa avtomorfizmov
Raziskovalci (12)
Organizacije (2)
Povzetek
V našem raziskovanju se ukvarjamo s kombinatoričnimi objekti, znanimi kot grafi. Graf sestavljata končna množica vozlišč, skupaj z množico povezav. Vsaka povezava povezuje dve različni vozlišči. Za vozlišči x, y rečemo, da sta sosednji, če sta povezani s povezavo. Koncept grafa je zelo uporaben, saj se mnoge tako matematične kot tudi druge relacije dajo modelirati s pomočjo grafov. V predlaganem projektu bomo raziskovali tako imenovane razdaljno-regularne grafe. Ogrodja petih platonskih teles so primeri takšnih grafov. Izkaže se, da je teorija razdaljno-regularnih grafov povezana tudi z mnogimi drugimi področji matematike, kot so na primer teorija kodiranja, teorija reprezentacij in teorija ortogonalnih polinomov.
Da bi opisali glavne cilje našega projekta se najprej spomnimo definicije razdaljno-regularnega grafa. Naj bo Γ = (X, R) graf z množico vozlišč X, množico povezav R, razdaljno funkcijo d in premerom D. Rečemo, da je Γ razdaljno-regularen, če za vsa cela števila h, i, j (0 ≤ h, i, j ≤ D) in vsa vozlišča x, y grafa Γ z d(x, y) = h velja, da je število vozlišč, ki so na razdalji i od vozlišča x in na razdalji j od vozlišča y, odvisno samo od števil i, j, h (in neodvisno od izbire vozlišč x, y).
Naš projekt je sestavljen iz dveh glavnih delov: študija Terwilliger-jevih algeber razdaljno-regularnih grafov (preko nerazcepnih modulov), ter študija delovanj grup avtomorfizmov razdaljno-regularnih grafov. Da bi opisali glavni cilj prvega dela našega projekta, se najprej spomnimo definicije Terwilligerjeve algebre razdaljno-regularnega grafa Γ. Naj bo Γ razdaljno-regularen graf premera D. Izberimo si vozlišče x grafa Γ. Za 0 ≤ i ≤ D definirajmo diagonalne matrike E_i^*=E_i^*(x), ki imajo vrstice in stolpce indeksirane z vozlišči grafa Γ. Za vozlišče y grafa Γ naj bo (y,y)-koordinata matrike E_i^* enaka 1, če je d(x,y)=i, in enaka 0 sicer. Matrike E_i^* imenujemo dualni idempotenti grafa Γ (glede na x). Terwilligerjeva algebra T=T(x) grafa Γ je matrična algebra, generirana z matriko sosednosti grafa Γ in z dualnimi idempotenti grafa Γ. V prvem delu našega projekta bo naš glavni cilj rešiti naslednji problem.
Problem Naj bo Γ razdaljno-regularen graf. Izberimo si vozlišče x grafa Γ in naj bo T=T(x) pripadajoča Terwilligerva algebra. Privzemimo, da ima Γ do izomorfizma natančno tri nerazcepne T-module s krajiščem 1, od katerih so vsi tanki. Poišči kombinatorične posledice tega algebraičnega pogoja.
Da bi opisali naš glavni cilj v drugem delu projekta, se najprej spomnimo definicije Cayleyevega grafa. Naj bo H končna grupa in naj bo S podmnožica grupe H, ki je zaprta za inverze, ne vsebuje identitete grupe H, in generira grupo H. Cayley-ev graf grupe H glede na množico S, ki ga označimo s Cay(H; S), je graf z množico vozlišč H, kjer je element x grupe H povezan z elementom y grupe H natanko takrat, ko je produkt elementa x z inverzom elementa y vsebovan v množici S. V drugem delu projekta bo naš glavni cilj rešiti naslednji problem.
Problem Za nekatere razrede grup H klasificiraj vse razdaljno-regularne grafe, ki so Cayley-evi grafi za grupo iz razreda H. Razreda grup, ki nas bosta v zvezi s tem problemom še posebej zanimala, sta razred grup, ki so direktni produkt dveh cikličnih grup(vsaj za nekatere posebne rede teh dveh cikličnih grup), ter razred posplošenih
diedrskih grup.
Tekom projekta bomo skušali rešiti še vrsto drugih problemov, ki so povezani z zgoraj navedenima glavnima problemoma.
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
