Slučajni Cayleyevi grafovi

master's thesis

• Author: Lugo Mihovilić
• Mentor: Nina Kamčev (mentor)
• Mentor: Rudi Mrazović (mentor)
• Committee member: Rudi Mrazović (predsjednik povjerenstva)
• Committee member: Nina Kamčev (član povjerenstva)
• Committee member: Vjekoslav Kovač (član povjerenstva)
• Committee member: Igor Ciganović (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2023-08-31, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

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.

Abstract (english)

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.

• Keywords: ekspander grafovi; Cayleyevi grafovi; Alon-Roichmanov teorem
• Keywords (english): expander graphs; Cayley graphs; Alon-Roichman theorem
• Language: croatian
• URN:NBN: urn:nbn:hr:217:545134
• Study programme: Title: Mathematical Statistics; Study programme type: university; Study level: graduate; Academic / professional title: sveučilišni magistar matematike (sveučilišni magistar matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2024-02-14 10:33:25