Knowledge base: Warsaw University of Technology

Settings and your account

Back

Numerical verification of sharpness of bounds in construction of expander graphs due to Margulis

Jarosław Piotr Rolski

Abstract

The purpose of this work is to numerically estimate the isoperimetric constant in the construction of Margulis expanders. Expanders are sparse, highly connected graphs, and the isoperimetric constant is a constant describing graph connectedness. Such graphs have numerous applications in mathematics and computer science. It is highly desirable to have a direct construction of those, as well as description of their properties. Through the thesis, we will examine the direct construction of Margulis expanders. It is an algebraic construction of graphs from the group SL(3Z) in the form of Cayley graphs. This group has the Kazdan property (T), which gives us a an estimation of the isomerimetric constant of graphs from Margulis' construction. Numerical verification of expander estimates is extremely difficult due to computational complexity, Margulis expanders form an infinite series of graphs, where the number of vertices tends to infinity. In order to obtain the most accurate results, we tested two methods for calculating the constant: sampling and greedy algorithm. The greedy algorithm gave us a better estimate, but we were only able to get results for two graphs.
Diploma type
Engineer's / Bachelor of Science
Diploma type
Bachelor thesis
Author
Jarosław Piotr Rolski (FMIS) Jarosław Piotr Rolski,, Faculty of Mathematics and Information Science (FMIS)
Title in Polish
Numeryczna weryfikacja optymalności oszacowań w konstrukcji ekspanderów Margulisa
Supervisor
Paweł Józiak (FMIS/DPMS) Paweł Józiak,, Department of Probability and Mathematical Statistics (FMIS/DPMS)Faculty of Mathematics and Information Science (FMIS)
Certifying unit
Faculty of Mathematics and Information Science (FMIS)
Affiliation unit
Department of Probability and Mathematical Statistics (FMIS/DPMS)
Study subject / specialization
, Matematyka
Language
(pl) Polish
Status
Finished
Defense Date
21-10-2019
Issue date (year)
2019
Reviewers
Paweł Naroski (FMIS/DAC) Paweł Naroski,, Department of Algebra and Combinatorics (FMIS/DAC)Faculty of Mathematics and Information Science (FMIS) Paweł Józiak (FMIS/DPMS) Paweł Józiak,, Department of Probability and Mathematical Statistics (FMIS/DPMS)Faculty of Mathematics and Information Science (FMIS)
Keywords in Polish
Ekspander, Margulis, własność Kazdana (T), graf Cayleya, stała izoperymetryczna.
Keywords in English
Expander, Margulis, Kazdan property (T), Cayley graph, isoperimetric constant.
Abstract in Polish
Celem niniejszej pracy jest numeryczne oszacowanie stałej izoperymetrycznej w konstrukcji ekspanderów Margulisa. Ekspandery to rzadkie, silnie spójne grafy, a stała izoperymetryczna to stała opisująca spójność grafu. Takie grafy mają liczne zastosowania w matematyce jak i informatyce. Tak więc uzyskanie ich bezpośredniej konstrukcji oraz poznanie ich własności jest bardzo pożądane. W pracy będziemy badać bezpośrenią konstrukcję ekspanderów Margulisa. Jest to algebraiczna konstrukcja grafów z grupy SL(3Z) w postaci grafów Cayleya. Grupa ta posiada własność Kazdana (T), która to daje nam pewne oszacowanie stałej izoperymetrycznej grafów z konstrukcji Margulisa. Numeryczna weryfikacja oszacowań ekspanderów jest niezwykle trudna ze względu na złożoność obliczeniową, ekspandery Margulisa tworzą nieskończony ciąg grafów, gdzie liczba wierzchołków dąży do nieskończoności. W celu uzyskania jak najdokładniejszych wyników testowaliśmy dwie metody obliczania stałej: próbkowanie i algorytm zachłanny. Algorytm zachłanny dał nam lepsze oszacowanie, ale udało nam się uzyskać wyniki jedynie dla dwóch grafów.
File
  • File: 1
    Jarosław_Rolski_-_Praca_Licencjacka.pdf
Request a WCAG compliant version
Local fields
Identyfikator pracy APD: 31124

Uniform Resource Identifier
https://repo.pw.edu.pl/info/bachelor/WUTc8b70636502d471193ac84473e660cad/
URN
urn:pw-repo:WUTc8b70636502d471193ac84473e660cad

Confirmation
Are you sure?
Report incorrect data on this page