Slučajni Cayleyevi grafovi

diplomski rad

• Autor: Lugo Mihovilić
• Mentor: Nina Kamčev (mentor)
• Mentor: Rudi Mrazović (mentor)
• Član povjerenstva: Rudi Mrazović (predsjednik povjerenstva)
• Član povjerenstva: Nina Kamčev (član povjerenstva)
• Član povjerenstva: Vjekoslav Kovač (član povjerenstva)
• Član povjerenstva: Igor Ciganović (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2023-08-31, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

Cilj ovog rada je upoznati čitatelja s važnošću i raznim svojstvima ekspander grafova i slučajnih Cayleyevih grafova. Kroz prva poglavlja iznosimo i dokazujemo rezultate potrebne za glavni teorem ovog rada, Alon-Roichmanov teorem. Taj teorem omogućava nam konstrukciju slučajnih Cayleyevih grafova koju su s velikom vjerojatnosti ekspanderi. Za kraj, demonstriramo kako ekspander grafove možemo koristiti za smanjenje pogreške u nekim vjerojatnosnim algoritmima.

Sažetak (engleski)

The focus of this thesis was to showcase the significance and remarkable properties of expander graphs, along with random Cayley graphs. In the initial chapters, we furnish the reader with all the necessary results to establish the central theorem of this thesis, namely, the Alon-Roichman theorem. This theorem provides us with an efficient tool for the successful generation of expander graphs. Afterwards, we elaborate on how expander graphs can be leveraged to minimize the quantity of random bits required in certain probabilistic algorithms.

• Ključne riječi: ekspander grafovi; Cayleyevi grafovi; Alon-Roichmanov teorem
• Ključne riječi (engleski): expander graphs; Cayley graphs; Alon-Roichman theorem
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:545134
• Studijski program: Naziv: Matematička statistika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: sveučilišni magistar matematike (univ. mag. math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2024-02-14 10:33:25