Definierbare Graphen und ihre Anwendungen

Ein wiederkehrendes Thema in der Mathematik ist das Zusammenspiel von Diskretem und Kontinuier- lichem. Es ist nicht uberraschend, dass unendlich große Objekte durch große endliche Objekte approx- imiert werden konnen. Als noch sinnvoller erweist sich jedoch die Annaherung großer endlicher Objekte durch Unendliche. In den letzten funfzig Jahren, vielleicht aufgrund der revolutionaren Veranderungen der Informationstechnologie, hat die Untersuchung großer Netzwerke an Bedeutung gewonnen. Die math- ematischen Modelle fur diese Netzwerke sind Graphen. Zentrale Begriffe der Graphentheorie spielen eine entscheidende Rolle in Informationstechnologie, Programmierung und Komplexitatstheorie. Wenn man versucht graphentheoretische Begriffe in naive Weiser vom endlichen auf den unendlichen Fall zu ubertragen, zeigen letztere oft ein unintuitives, fast paradoxes Verhalten, das sich ganz von dem der ersten unterscheidet. Der Grund fur dieses gegensatzliche Verhalten liegt darin, dass Beweise fur The- orien uber endliche Graphen typischerweise in konkrete Prozeduren oder Algorithmen ubersetzt werden konnen, wohingegen analogen Argumenten in Bezug auf unendlichen Graphen diese Konstruierbarkeit oft fehlt. Wenn es unser Ziel ist, durch die Untersuchung unendlicher Graphen ein besseres Verstandnis der großen endlichen Graphen zu erlangen, ist es vernunftig, eine gewisse Konstruierbarkeit der fraglichen Objekte zu verlangen. Der naturliche Weg, dies zu erreichen, besteht darin, den unendlichen graphenthe- oretischen Begriffen Definierbarkeitsbeschrankungen aufzuerlegen. Hier treffen klassische Kombinatorik und Algorithmen auf die deskriptive Mengenlehre, die Untersuchung der Komplexitat von Teilmengen der reellen Zahlen. Unsere Forschung wird die Struktur definierbarer Graphen untersuchen. Insbesondere werden wir uns auf chromatische Zahlen und Hyperendlichkeit konzentrieren. Im Wesentlichen ist die definierbare chromatische Zahl eines Graphen die minimale Anzahl definierbarer Teile, in die der Graph zerlegt werden kann, so dass keine zwei Knoten desselben Stucks eine Kante bilden. Unser Ziel ist es zu verstehen, ob es fur eine gegebene Anzahl von Stucken ein kanonisches Hindernis fur das Auffinden einer solchen Zerlegung gibt. Die Hyperendlichkeit eines Graphen stellt sicher, dass seine Knotenmenge besonders schon in endliche Teile zerlegt werden kann. In dieser Richtung mochten wir gerne wissen, ob es moglich eine solche Zerlegung zu finden, die einen gegebenen Graphen bis auf eine kleine Ausnahme approximiert - und zwar fur verschiedene Interpretation des Begriffs kleine Ausnahme.

Die wichtigste Leistung des Projekts ist der entwickelte Zusammenhang zwischen dem Verhalten großer endlicher und definierbarer unendlicher Netzwerke.Im endlichen Fall haben wir mit dem LOCAL-Modell des verteilten Rechnens gearbeitet. In diesem Modell stellt man sich die Knoten als Computer vor, die Entscheidungen treffen müssen (z. B. eine Farbe ausgeben, damit benachbarte Knoten unterschiedliche Farben ausgeben), ohne das gesamte Netzwerk zu erkunden da es sich als extrem groß vorstellt nur zu schauen in ihren kleinen Nachbarschaften. Dadurch wird sichergestellt, dass es keinen speziellen Knoten oder Origo gibt. Die Effizienz eines Entscheidungsfindungsalgorithmus wird an der Größe der Nachbarschaft gemessen, die ein bestimmter Knoten erkunden muss. Im unendlichen Fall können die Netzwerke als kontinuierliche Analoga der endlichen betrachtet werden. In dieser Situation fordern wir, dass die Entscheidungen auf kontinuierliche oder allgemeiner definierbare Weise getroffen werden. Dies ergibt das gleiche Phänomen wie in der endlichen Situation: Man wird nicht in der Lage sein, einen einzelnen Punkt aus einer gegebenen verbundenen Komponente des Netzwerks auszuwählen. Dies ist die Intuition hinter der Tatsache, dass sich diese Objekte auf ähnliche Weise verhalten. Während diese intuitive Analogie lange Zeit klar war, war es Bernshteyns Arbeit, die eine Brücke zwischen den beiden Welten schlug. In unserem Projekt haben wir weitere Aspekte dieser Zusammenhänge untersucht. Eines unserer Ziele war es, die berühmte unendliche spieltheoretische Methode von Marks auf die endliche Welt zu übertragen. Um dies zu erreichen, mussten wir nicht-triviale Ideen aus dem verteilten Rechnen nutzen, was wiederum im unendlichen Kontext neue Ergebnisse lieferte. Dies führte auch zu einer neuen Art, unendliche Graphen mit interessanten Eigenschaften zu konstruieren.Außerdem stellte sich heraus, dass einige Klassen, die in den beiden Feldern auf völlig unterschiedliche Weise definiert sind, zusammenfallen.Wir glauben, dass wir hinter den entdeckten Zusammenhängen nur an der Oberfläche einer tiefen Theorie