Spektren und Topologie von Graphen und Simplizialkomplexen

Unser Projekt beschäftigt sich hauptsächlich mit sogenannten Graphen einer Menge von Knoten, die durch Kanten, d.h. Paare von Knoten, verbunden sind. Graphen dienen als einfaches Modell zur Beschreibung von paarweisen Relationen und Wechselwirkungen. Sie sind allgegenwärtig in der Wissenschaft wie auch in unserem Alltag. Wie gut wir uns ein Modell basierend auf Graphen zu Nutze machen können, hängt oft davon ab, wie genau wir die Struktur der unterliegenden Graphen verstehen. Angenommen, beispielsweise, dass die Kanten eine ungewünschte Relation beschreiben, möchten wir möglicherweise die Knoten so in kleinere Gruppen aufteilen, dass keine der Kanten innerhalb einer solchen Gruppe liegt. Eine solche Zerlegung der Knoten nennt man Färbung. Im Allgemeinen ist es ein schwieriges Problem eine Färbung mit so wenigen Gruppen wie möglich zu finden. Als weiteres Beispiel könnten wir für ein Modell eines Netzwerkes, wo Knoten mit anderen Knoten über Kanten kommunizieren, daran interessiert sein, zu verstehen, wie der Ausfall von Knoten oder Kanten die Kommunikationsfähigkeit der übrigen Knoten beeinflusst. Eine quantitative Garantie dafür, dass man einen großen Teil des Netzwerkes nur durch das Versagen einer großen Anzahl von Knoten abtrennen kann, ist die sogenannte Expansion eines Graphen. Viele strukturelle Eigenschaft wie Färbbarkeit und Expansion sind für einen gegebenen Graphen schwierig direkt auszurechen. Deshalb ist es interessant, ihre Beziehung zu anderen Eigenschaften zu verstehen, die vielleicht einfacher zu beschreiben sind. Eine Klasse solcher Eigenschaften relevant für unseres Project sind algebraische Eigenschaften. Diese werden üblicherweise durch G-Matrizen ausgedrückt, sprich einer Zuordnung von Zahlen zu den Knoten und Kanten eines gegebenen Graphen. Ein bekanntes Resultat im Forschungsgebiet sagt aus, dass die sogenannte Eigenwertlücke eines Graphen, welche eine Eigenschaft einer bestimmten G-Matrix ist, ein gutes Maß für die Expansion des Graphen ist. Eine weitere wichtige Art, mit Graphen zu arbeiten, ist die Visualisierung von Graphen. Dabei könnte man versuchen, den Graphen in der Ebene zu zeichnen, sodass die Knoten durch Punkte repräsentiert werden und die Kanten durch Streckensegmente, ohne dass sich zwei Kanten kreuzen. Dies ist allerdings nicht immer möglich. Man kann dann versuchen, den Graphen auf einem komplizierteren Objekt, wie zum Beispiel auf einem Donut, zu zeichnen. Die Existenz einer solchen Darstellung ist ein Beispiel für eine topologische Eigenschaft, die ein Graph haben kann. Es stellt sich heraus, dass manchmal strukturelle und algebraische Eigenschaften von Graphen mit topologischen zusammenhängen. Ziel unseres Projektes ist die bekannten Beziehungen zwischen strukturellen, algebraischen und topologischen Eigenschaften besser zu verstehen, aber auch neue derartige Verbindungen zu finden. Weiter möchten wir unsere Untersuchungen auf Simplizialkomplexe erweitern, was höherdimensionale Analoga von Graphen sind.

Dieses Projekt untersucht Graphen, eine grundlegende mathematische Struktur, die paarweise Beziehungen zwischen Objekten modelliert, z. B. ein Straßennetz, das eine Reihe von Städten verbindet. Wir können einen Graphen visualisieren, indem wir ihn auf Papier zeichnen und die Städte durch Punkte und die Straßen, die sie verbinden, durch Kurven darstellen. Eine Zeichnung eines Graphen, in der sich keine zwei Kurven kreuzen, wird als Einbettung bezeichnet. Wir stellen jedoch schnell fest, dass es Graphen gibt, die sich nicht einbetten lassen: Egal wie wir die Punkte platzieren und wie kurvig die Verbindungen zeichnen, es gibt immer einige Kurven, die sich kreuzen. Wenn wir Kreuzungen in einem physischen Straßennetz vermeiden wollen, können wir Brücken konstruieren. Eine analoge Konstruktion für Graphen, die auf einem Papier gezeichnet werden, führt zu zweidimensionalen Objekten, die Oberflächen genannt werden, zum Beispiel die Oberfläche eines Donuts oder einer Brezel. Versucht man, verschiedene Netze auf einem Donut zu zeichnen, so stellt man fest, dass sich dort mehr Netze einbetten lassen als auf einem flachen Stück Papier, während sich viele andere nicht einbetten lassen. Die gleiche Geschichte setzt sich mit einer Brezel fort. Es stellt sich heraus, dass jedes Netzwerk, egal wie komplex, in irgendeine Fläche eingebettet ist, aber keine Fläche lässt eine Einbettung für jedes Netzwerk zu. Zur Veranschaulichung eines anderen Untersuchungsgegenstandes unseres Projekts betrachten wir Graphen, die eine Reihe von Nägeln modellieren, von denen einige Paare durch ein Gummiband verbunden sind, jedes mit seiner eigenen Stärke. Wenn wir jeden Nagel irgendwo auf einem Brett feststecken, werden die Bänder gedehnt, was zu Kräften führt, die auf die Nägel entlang der Bänder wirken. Wenn man die Bedingungen aufschreibt, die ausdrücken, dass die auf einen Nagel wirkenden Kräfte im Gleichgewicht sind, erhält man ein Objekt, das als gewichteter Laplace-Operator des Graphen bekannt ist, und wir haben seine verschiedenen Eigenschaften untersucht. Um eine davon zu beschreiben, stellen wir fest, dass wir die Positionen der Nägel immer so wählen können, dass die gesamte Konfiguration nur um einen konstanten Faktor pro Sekunde schrumpft, wenn wir die Nägel gleichzeitig lösen und sie sich frei bewegen lassen, und ansonsten ihre Form beibehält. Normalerweise können solche Konfigurationen nur Nägeln entsprechen, die entlang einer einzigen Linie befestigt sind, und sind daher eindimensional. Manchmal, je nach Graph und Stärke der einzelnen Gummis, ist es jedoch möglich, solche Konfigurationen zu finden, die nicht an eine einzige Linie, sondern an eine Ebene oder sogar einen höherdimensionalen Raum gebunden sind. Die maximale Dimension, die wir auf diese Weise für einen gegebenen Graphen erhalten können, indem wir die Stärken der Gummis anpassen, ist eine Größe von besonderem Interesse. Es gab eine Vermutung, dass es eine obere Schranke für alle Graphen gibt, die eine Einbettung in eine feste Fläche haben. Wir haben diese Vermutung widerlegt.