Ali so Ekstremalni Grafi res redki?
natisniPredstavitev projekta
Naslov: Ali so Ekstremalni Grafi res redki?
Šifra projekta: N1-0459
Vodilna institucija: UP FAMNIT
Partnerske institucije: /
Vodja projekta na UP FAMNIT: doc. dr. Slobodan Filipovski
Financer projekta: Javna agencija za znanstvenoraziskovalno in inovacijsko dejavnost Republike Slovenije (ARIS)
Raziskovalno področje (ARIS): 1.01 - Matematika
Vrsta projekta: Raziskovalni projekt
Trajanje projekta: 1. 6. 2026 – 31. 5. 2028
Opis projekta:
Topologija omrežja, ne glede na to, ali gre za telekomunikacijsko omrežje, multiprocesorsko omrežje ali lokalno omrežje, je pogosto modelirana zgrafom, kjer vozlišča predstavljajo naprave (kot so procesorji), robovi, bodisi neusmerjeni bodisi usmerjeni.
V tem modelu je treba upoštevati več ključnih lastnosti, med katerimi so najpogostejše omejitve stopnje vozlišč, premera in ožino. V omrežnih izrazihstopnja vozlišča predstavlja število povezav, ki jih ima vozlišče, medtem ko premer označuje največje število povezav, ki jih je treba prehoditi, da sepošlje sporočilo med katerima koli dvema vozliščema. To vodi do dveh temeljnih vprašanj: Kakšno je največje (najmanjše) število vozlišč, ki lahkoobstajajo v omrežju z omejenimi stopnjami in premerom (ožino)? Rešitev teh znanih problemov, znanih kot problem stopnje/premera in problemstopnje/ožine, temelji na tehnikah iz ekstremalne teorije grafov.
V okviru tega projekta bomo preučevali pet odprtih vprašanj v ekstremni teorijigrafov, pri čemer bomo uporabili različne tehnike, vključno s spektralno analizo, kombinatoričnimi metodami in preučevanjem asimptotskih gostotmnožic. Zelo smo optimistični glede našega potencialnega prispevka k reševanju manjkajočega (57, 2)-Moorejevega grafa. Poleg tega siprizadevamo zagotoviti dokaz za dolgoletno domnevo, ki sta jo predlagala Bermond in Bollobás, ki nakazuje, da je vrzel med ekstremnimi grafi inteoretičnimi največjimi grafi pomembna.
Poleg tega bomo pokazali, da ne obstajajo novi grafi brez trikotnikov, ki so močno povezani. V nasprotnem, pokazali bomo, da so najmanjši grafi, znani kot kletke, učinkoviti razširjevalci - grafi, ki jih odlikuje močna povezanost. Rezultati, dobljeni v okvirutega projekta, bi lahko pomembno vplivali na računalniške znanosti, zlasti pri gradnji optimalnih omrežij.
Oddelek UP FAMNIT, v okviru katerega se izvaja projekt:
Oddelek za matematiko
Project presentation
Title: Are Extremal Graphs really rare?
Project acronym: N1-0459
Leading institution: UP FAMNIT
Partner institutions: /
Principal investigator at UP FAMNIT: dr. Slobodan Filipovski
Funding organization: Slovenian Research and Innovation Agency (ARIS)
Research field (ARIS): 1.01 - Mathematics
Duration: 1. 6. 2026 – 31. 5. 2028
Description:
The topology of a network-whether it be a telecommunication, multiprocessor, or local area network-is often modeled by a graph,where vertices represent nodes (such as stations or processors), and edges, either undirected or directed, stand for links orconnections.
Several key features must be considered in this model, with the most common being limitations on vertex degrees,diameter and girth. In network terms, the degree of a vertex represents the number of connections a node has, while the diameterrefers to the maximum number of links that must be traversed to transmit a message between any two nodes.This leads to two fundamental questions:What is the largest (smallest) number of nodes that can exist in a network with constrained degree and diameter (girth)? The resolution of these famous problems, known as the Degree/Diameter Problem and Degree/Girth Problem, relies on techniquesfrom Extremal Graph Theory.
Within the scope of this project, we will explore five open questions in Extremal Graph Theory, utilizing various techniques,including spectral analysis, combinatorial methods, and the study of asymptotic densities of sets. We are highly optimistic about ourpotential contribution to resolving the missing (57, 2)-Moore graph. Additionally, we aim to provide a proof for the long-standingconjecture proposed by Bermond and Bollobás, which suggests that the gap between extremal graphs and the theoretical largestgraphs is significant.
Additionally, we will show that there are no new triangle-free strongly regular graphs. Conversely, we willdemonstrate that the smallest graphs, known as cages, serve as effective expanders-graphs characterized by strong connectivity.The results developed through this project could significantly impact in computer science, particularly in the construction of optimalnetworks.
Department:
Department of Mathematics
