Funktionalgleichung für Gitterwege und Baumstrukturen

Dieses Projekt widmet sich zwei fundamentalen kombinatorischen Strukturen: Gitterwegen und baumähnlichen Strukturen. Diese kommen nicht nur in der Mathematik vor, sondern sind auch in anderen Disziplinen weit verbreitet. Bäume dienen in der Informatik unter anderem als Datenstrukturen und Modelle für Algorithmen. Gitterwege finden Verwendung in der Chemie, wo sie als Modelle für Polymere dienen, oder in der Warteschlangentheorie, in der sie Geburts- und Todesprozess modellieren. Diesen Modellen ist gemein, dass sie durch (unendliche) Familien von Objekten bestimmter Größe beschrieben werden. Diese Größe ist im Fall von Gitterwegen durch die Anzahl der Schritte und im Fall von Bäumen durch die Anzahl der Knoten gegeben. Das wichtigste Konzept in diesem Zusammenhang sind erzeugende Funktionen. Dies sind (formale) Potenzreihen, deren Koeffizienten diese Anzahlen darstellen. Durch diese werden die Modelle in Funktionalgleichungen von erzeugenden Funktionen übergeführt, deren Analyse der Schlüssel zum Verständnis der jeweiligen Modelle ist. Die auftretenden Gleichungen sind von algebraischer Natur oder lineare Differentialgleichungen mit polynomiellen Koeffizienten. Mit Hilfe der Konzepte der "Analytischen Kombinatorik" können erzeugende Funktionen als Reihenentwicklungen komplexer Funktionen interpretiert werden. Dies ermöglicht den Zugang zu Methoden der komplexen Analysis, sowie fortgeschrittenen Methoden, wie der Kernmethode und der Theorie holonomischer Funktionen. Dieses Projekt untergliedert sich in drei Teilprojekte. Im Ersten werden Gitterwege unter einer Geraden mit irrationaler Steigung analysiert. Dabei werden Pfade der Dimension zwei betrachtet, welche im Ursprung beginnen und sich durch Sprünge der Länge eins nach Norden und Osten bewegen. Diese dürfen jedoch niemals über die gegebene Gerade springen. Wie oben ausgeführt, ist die (asymptotische) Anzahl dieser Pfade von Interesse. Die Fälle einer Geraden mit ganzzahliger beziehungsweise rationaler Steigung sind klassische Themen der Kombinatorik und Wahrscheinlichkeitstheorie. Im zweiten Teilprojekt werden Gitterwege mit Katastrophen in höheren Dimensionen behandelt. In Dimension zwei beginnen diese Pfade erneut im Ursprung und sind nun darauf beschränkt im ersten Quadranten zu verweilen. Weiters werden Sprünge, wie zum Beispiel nach Norden, Osten, Süden und Westen fixiert, und zusätzlich Katastrophen erlaubt. Dies sind Sprünge von beliebigem Ort an jeweils eine der Achsen. Neben deren Anzahl sind auch weitere Parameter, wie die durchschnittliche Anzahl von Katastrophen, von Interesse. Solche Pfade können als Modelle für Warteschlangen verstanden werden, in denen ein Reset, wie zum Beispiel der Absturz eines Computerprogramms, möglich ist. Das dritte Teilprojekt widmet sich kompakten Bäumen. Dies sind Bäume in denen redundante Informationen in Form von wiederholt auftretenden Teilbäumen gelöscht und durch Zeiger ersetzt wurden. Insbesondere ist wieder deren (asymptotische) Anzahl von Interesse. Diese Strukturen finden Anwendung im Design von Compilern und ermöglichen effizienteren und kompakteren Code, sowie in der Kompression von Daten.

Mathematische Modelle sind in der Wissenschaft allgegenwärtig. Unter anderem erlauben sie die Analyse von Algorithmen in der Informatik, die Erforschung von Polymeren in der Chemie oder die Beschreibung von evolutionären Beziehungen in der Biologie. Dieses Projekt beschäftigte sich mit zwei Klassen solch fundamentaler Modelle: Gitterwegen und Baumstrukturen. Die einfachsten Bespiele für Gitterwege sind Pfade, die sich vom Ursprung aus mit Sprüngen der Länge eins in Richtung Norden, Osten, Süden oder Westen fortbewegen, und für Baumstrukturen sind dies binäre oder phylogenetische Bäume. Unsere Hauptresultate erweitern diese beiden Klassen um neue Modelle, welche natürlich auftretende, jedoch schwer modellierbare Phänomene aufweisen. Allgemein ist meine Forschung der enumerativen und analytischen Kombinatorik zuzuordnen, welche von den grundlegenden Fragen "Wie viele gibt es?" und "Was ist typisch?" getrieben wird. In Bezug auf die obigen Modelle beantworteten wir die Fragen, wie viele Gitterwege mit einer gewissen Anzahl von Schritten und wie viele Bäume mit einer gewissen Anzahl von Knoten es gibt, und darauf aufbauend, wie ein typischer Vertreter aussieht. Im Bereich der Gitterwege beschäftigten wir uns mit Wegen in nicht-konvexen Gebieten, welche in letzter Zeit immer wichtiger wurden, über welche jedoch noch sehr wenig bekannt war. Wir konnten das Zählproblem der Königsschritte (wie ein König im Schach) lösen und zeigen, dass es eine tiefe Verbindung zum gleichen Problem in konvexen Gebieten gibt. Dies erlaubte uns zu zeigen, dass die zu Grunde liegende erzeugende Funktion eine lineare Differentialgleichung mit polynomiellen Koeffizienten erfüllt, jedoch keine algebraische Gleichung, was wiederum erlaubt diese Wege schnell und effizient zu erzeugen. Im Bereich der Baumstrukturen untersuchten wir kompakte Bäume, wie sie in Kompressionsverfahren in der Informatik auftreten. In diesen Bäumen werden wiederholt auftretende Teilbäume gelöscht und durch Pointer ersetzt um Speicherplatz zu sparen. Im asymptotischen Zählproblem konnten wir ein bisher sehr selten beobachtetes Phänomen beweisen: das Auftauchen von gestreckten Exponenten. Für Bäume mit n Knoten, sind dies Terme der Form a^(n^s) mit reellen Konstanten a und s. Wir konnten eine neue Methode entwickeln, die solche Terme beweist und lediglich Information über die zu Grunde liegende Rekursionsgleichung benötigt. Weiters konnten wir diese Methode auch auf das offene Problem der Abzählung von minimalen deterministischen Automaten mit binärem Alphabet anwenden und ebenfalls einen gestreckten Exponenten nachweisen. All dies stimmt uns optimistisch, dass diese Methode auch in Zukunft viele offene Abzählprobleme lösen wird.