Zufällige rekursive Strukturen mit kleinem Durchmesser

Die vorrangigen Ziele des Projekts sind wie folgt: (1) Erlangen eines tieferen Verständnisses der stochastischen Natur von Zufallsbäumen und allgemeineren Strukturen mit kleinem Durchmesser. (2) Entwicklung und Erweiterung von allgemeinen analytischen Methoden. (3) Stimulieren interdisziplinärer Forschung auf internationalem Niveau. Baumstrukturen spielen eine wichtige Rolle in vielen Bereichen wie z.B. Informatik, Quantenmechanik, Biologie und viele mehr, aber auch in vielen Teilgebieten der Mathematik. Sie dienen z.B. als Datenstrukturen. Falls man mit zufällig erzeugten Daten zu tun hat und diese in einer Baumstruktur speichert, dann wird der entstehende Baum ein Zufallsbaum. Um zu verstehen, wie so ein Baum tyischer Weise aussieht (z.B. um effiziente Algorithmen zum Wiederfinden der Daten zu designen), muss man große Zufallsbäume systematisch analysieren. Bäume treten auch oft als Modell für Phänomene der realen Welt auf. Um so ein Modell zu analysieren, beginnt man mit einfachen Modellen wie z.B. Verzweigungsprozessen. Diese versteht man mittlerweile schon sehr gut. Der Nachteil ist, dass sie für viele moderne Anwendungen aus Informatik und Biologie nur ein sehr unrealistisches Modell liefern. Es gibt bessere Modelle, die sich von ersteren auf den ersten Augenblick durch die Größe ihres Durchmessers klar unterscheiden. Im Gegensatz zu Verzweigungsprozessen und ähnlichen Baumfamilien gibt es für Bäume mit kleinem Durchmesser keinen allgemeinen Rahmen, sondern nur viele verschiedene Modelle und partielle Resultate. Oft taucht in der Analyse die Riccati- Differentialgleichung oder eine dazu ähnlich Differentialgleichung auf. Im Projekt soll dieses Phänomen erforscht werden und existierende Methode zur Gewinnung von Informationen aus solchen Gleichungen erweitert werden. Ein weiteres Ziel des Projekts ist die Vertiefung des Verständnisses für die typische Form von Zufallsbäumen für verschiedene Baumklassen. Dazu kann man z.B. das Profil des Baumes analysieren und in weiterer Folge die Abhängigkeit von mehreren Formparametern von einander. In Anwendungen tritt oft das Problem auf, wie viele Möglichkeiten es gibt, ein komplexes System in lauter voneinander verschiedene Einzelteile zu zerlegen. Das ist ein schwieriges Problem, aber wir hoffen, dass die Methoden, die wir im Laufe des Projekts entwickeln, uns tiefe Resultate zu diesen Fragen zu liefern. In diesem Kontext gibt es Beispiele aus der Biologie (Baummodelle), aber auch andere interessante Strukturen aus anderen Bereichen der Mathematik. Weiters soll noch ein konkretes Problem aus der Informationstheorie behandelt werden, wo man Bäume bzgl. der Pfadlänge zählen muss, was zu kleinem Durchmesser und vermutlich vielen ungewöhnlichen Eigenschaften führt.

Baumartige Strukturen (man denke an Stammbäume oder Darwins Baum des Lebens) sind grundlegende mathematische Objekte. Mit dem Aufkommen der Informatik dienen Bäume als Datenstrukturen und viele neue Baummodelle wurden entwickelt. Ebenso ist Darwins Baum des Lebens nicht mehr der Weisheit letzter Schluss, wenn man z.B. Evolution von Bakterien betrachtet. Daher werden laufend neue Modelle entwickelt, um Evolution in verschiedenen Kontexten zu verstehen. Diese Modelle sind oft nicht baumartig, sondern netzwerkförmig. In der Vergangenheit wurden Zufallsgraphen untersucht, da sie einfach, aber dennoch reich an Struktur sind. Jene im klassischen Modell haben jedoch einen großen Durchmesser im Gegensatz zu vielen realen Netzwerken. Daher wurden viele neue Graphenmodelle vorgeschlagen, um die Formation solcher Netzwerke zu verstehen. Eines dieser Modelle basiert auf sogenannten Hypergraphen. Das Projekt zielte darauf ab, das Verständnis (die typische Gestalt) von zufälligen Strukturen wie den oben erwähnten zu erweitern. Der Projektablauf war vielfältig: Zum einen haben wurden viele Strukturen aus der Literatur ausgewählt, wo bestimmte strukturelle Parameter unbekannt waren, um die offenen Probleme mit unseren Methoden anzugehen und die Lücken zu füllen. Weiters haben wir die Methodik selbst untersucht und versucht, sie zu erweitern. Unter den behandelten Strukturen waren digitale Suchbäume, mehrere Klassen von phylogenetischen Netzwerken und eine Klasse von Hypergraphen. Ein wichtiger Parameter digitaler Suchbäume ist ihr Profil, eine detaillierte Beschreibung der Form, die man sieht, wenn man die Breitenveränderung des Baumes von der Wurzel bis zum Wipfel betrachtet. Trotz jahrzehntelangen Untersuchungen war ziemlich wenig bekannt, da sich das Problem nur durch eine sehr komplizierte Gleichung beschreiben lässt. Durch die gemeinsame Anstrengung der beiden Teams und einer Kombination verschiedener Methoden konnten wir die Kenntnisse wesentlich erweitern und vollständige Beschreibungen mehrerer verwandter Parameter erzielen. Die vollständige Beschreibung des Profils wird in naher Zukunft gelingen. Für Hypergraphen sind die strukturellen Veränderungen während Phasenübergängen wichtige Stukturparameter. Struktur, Kantendichte und Größe der größten Komponenten konnten für eine Teilklasse von Hypergraphen vollständig beschrieben werden. Sowohl die asymptotische und als auch die exakte Anzahl phylogenetischer Netzwerke mit gegebener Größe wurde für einige Klassen solcher Netzwerke bestimmt. Dies legte den Grundstein für die Analyse von Formparametern, die auch schon für grundlegende Parameter einiger dieser Klassen umgesetzt wurde. Auf der methodischen Seite gelang die vollständige asymptotische Entwicklung für sogenannte Lagrange-Formen. Darüberhinaus konnte die Sattelpunktmethode auf erzeugende Funktionen erweitert werden, die bei der Abzählung von Fishburn-Matrizen auftreten. Das ist ein Durchbruch, da die Methode konzeptionell einfacher ist als die bisher verwendeten Methoden. Und im Gegensatz zu diesen speziell an das Problem angepassten Methoden kann sie auf zahlreiche Probleme ähnlicher Art verallgemeinert werden. Dies half uns, mehrere in diesem Forschungsgebiet aufgestellte Vermutungen zu beweisen.