expander graphs; high-dimensional expansion; discrete laplacians; random complexes; isoperimetric inequalities
en
Abstract:
Expansion als Eigenschaft von Graphen und im Besonderen Expander-Graphen mit beschränktem Knotengrad sind ein zentrales Forschungsthema in der Kombinatorik und in den theoretischen Computerwissenschaften mit vielen Anwendungen und Verbindungen zu anderen Gebieten der Mathematik. In den letzten Jahren gab es gemeinsame Bemühungen, diese reichhaltige und fruchtbare Theorie auf höherdimensionale Fragestellungen zu erweitern und zu verallgemeinern. In dieser Arbeit werden einige der aktuellen Entwicklungen und Ergebnisse beschrieben. Verschiedene Begriffe von höherdimensionaler Expansion, speziell Coboundary Expansion (zurückgehend auf die Arbeiten von Linial–Meshulam und Gromov) einerseits und spektrale Expansion, definiert mithilfe der Eigenwerte höherdimensionaler Laplace-Operatoren (eingeführt in den Arbeiten von Eckmann und Garland), andererseits, werden näher beschrieben und die Unterschiede zwischen den einzelnen Ansätzen werden diskutiert. Zusätzlich wird eine Auswahl aus der Vielzahl an Anwendungen von höherdimensionaler Expansion, beispielsweise das Topological Overlap Theorem von Gromov, präsentiert.
de
Expansion properties of graphs and, in particular, bounded degree expander graphs, are a central research topic in combinatorics and theoretical computer science, with many applications and connections to other areas of mathematics. In recent years, there has been a concerted effort to generalize and extend this rich and fruitful theory to higher dimensions. In this thesis, some of these recent developments and results are surveyed. Several notions of higher-dimensional expansion, in particular coboundary expansion (introduced in the work of Linial–Meshulam and Gromov) on the one hand and spectral expansion formulated in terms of the eigenvalues of higher-dimensional Laplacians (going back to the work of Eckmann and Garland) on the other hand, are described and connections and differences between these are discussed. Moreover, several applications of higher-dimensional expansion, e.g., Gromov’s topological overlap theorem are presented.