Detailansicht

Margulis' expanders and Ramanujan graphs
Georg Ehling
Art der Arbeit
Masterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Mathematik
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Masterstudium Mathematik
Betreuer*in
Goulnara Arzhantseva
Volltext herunterladen
Volltext in Browser öffnen
Alle Rechte vorbehalten / All rights reserved
DOI
10.25365/thesis.71592
URN
urn:nbn:at:at-ubw:1-13204.49029.744435-1
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)

Abstracts

Abstract
(Deutsch)
Expander sind dünn besetzte Graphen mit starken Konnektivitätseigenschaften. Sie stellen einen zentralen Forschungsgegenstand im Gebiet der Graphentheorie mit vielfältigen Anwendungen in Mathematik und Informatik dar. Die vorliegende Arbeit soll eine Einführung in die Theorie der Expander-Graphen geben, wobei insbesondere auf das erste explizite Beispiel einer solchen Familie von Graphen von Margulis sowie auf den Optimalfall der Ramanujan-Graphen genauer eingegangen werden soll. Nach einer Wiederholung graphentheoretischer Grundbegriffe führen wir Expansion als kombinatorische Eigenschaft einer Familie von Graphen ein und geben eine äquivalente Charakterisierung in algebraischen Begriffen. Wir untersuchen das erste explizite Beispiel einer Familie von Expandern von Margulis [Mar73] sowie einige seiner Varianten und geben einen praktischen Beweis ihrer Expander-Eigenschaft. Ein konzeptuellerer Beweis desselben Resultats ergibt sich dann beim Studium der Verbindung zwischen Expandern und Gruppen, die Kazhdans Eigenschaft (T) erfüllen. In weiterer Folge stellen wir einen Beweis für den Satz von Alon-Boppana vor, der eine theoretische Grenze für Expansion angibt. Daraus motiviert sich die Definition von Ramanujan-Graphen als bestmögliche Expander. Wir begründen, warum Margulis' Expander kein Beispiel für eine Familie von Ramanujan-Graphen sind und skizzieren die Konstruktion des Beispiels von Lubotzky, Phillips und Sarnak [LPS88] bzw. Margulis [Mar88]. Abschließend geben wir einen kurzen Einblick in das Gebiet der Near-Ramanujan-Graphen, ein Thema, dem in den letzten Jahren verstärkt Aufmerksamkeit gewidmet wurde.
Abstract
(Englisch)
Expanders are sparse graphs with strong connectivity properties. They represent a central object of study in graph theory with various applications in both mathematics and computer science. This thesis aims to give an introduction to expander graphs, focusing on the first explicit example of such a family of graphs due to Margulis as well as the optimal case of Ramanujan graphs. After a recapitulation of the basic concepts of graph theory, we introduce expansion as a combinatorial property of a family of graphs and give an equivalent characterisation in more algebraic terms. The first explicit example of a family of expanders due to Margulis [Mar73] and some of its variants are studied, including a hands-on proof of their expansion property. A more conceptual proof of the same result arises as we investigate the connection of expanders and groups that have Kazhdan's property (T). Subsequently, we present a proof of the Alon-Boppana Theorem, which gives a theoretical limit to expansion. This motivates the definition of Ramanujan graphs as the best possible expanders. We give a reason why Margulis' expanders are not an example for a family of Ramanujan graphs and sketch the construction of the example given by Lubotzky, Phillip and Sarnak [LPS88] and, independently, Margulis [Mar88]. Finally, we give a brief insight to near-Ramanujan graphs, a topic that has received increased attention in recent years.

Schlagwörter

Schlagwörter
(Deutsch)
Expander-Graphen Ramanujan-Graphen Eigenschaft (T)
Schlagwörter
(Englisch)
expander graphs Ramanujan graphs Kazhdan's property (T)
Autor*innen
Georg Ehling
Haupttitel (Englisch)
Margulis' expanders and Ramanujan graphs
Paralleltitel (Deutsch)
Margulis-Expander und Ramanujan-Graphen
Publikationsjahr
2022
Umfangsangabe
iii, 58 Seiten : Illustrationen
Sprache
Englisch
Beurteiler*in
Goulnara Arzhantseva
Klassifikation
31 Mathematik > 31.12 Kombinatorik, Graphentheorie
AC Nummer
AC16567288
Utheses ID
62823
Studienkennzahl
UA | 066 | 821 | |
Universität Wien, Universitätsbibliothek, 1010 Wien, Universitätsring 1