Gestreckte Exponenten und darüber hinaus

Viele mathematische Probleme beginnen mit einer einfachen Frage: Wie viele gibt es? Ihr unschuldiger und zum Teil naiv wirkender Charakter verbirgt die Tatsache, dass ihre Beantwortung häufig nicht nur schwierig sondern sogar unmöglich ist. Mathematisch ist diese Frage der abzählenden Kombinatorik zuzuordnen, jedoch taucht sie in vielen unterschiedlichen Disziplinen auf, welche von der Informatik (z.B. Analyse von Algorithmen) bis zur Biologie (z.B. phylogenetische Bäume) reichen. Von vordergründigem Interesse sind universelle Phänomene in großen zufälligen Strukturen. Diese beschreiben die Beobachtung, dass viele kombinatorische Strukturen nur von wenigen globalen Eigenschaften beeinflusst werden und nicht von konkreten Details abhängen. Dieses Projekt widmet sich einem solchen Phänomen: dem Auftreten von gestreckten Exponenten in der asymptotischen Abzählung. Doch was bedeutet das? Eine Zahlenfolge ist asymptotisch äquivalent zu einer anderen, wenn ihr gemeinsamer Quotient gegen 1 strebt. Hierbei ist die Idee, dass für eine gegebene komplexe Zahlenfolge die schwierig zu berechnen ist, eine einfachere Darstellung gefunden wird, die deren Größenordnung widerspiegelt. Dadurch lassen sich effizient Approximationen berechnen und verschiedene Zahlenfolgen miteinander vergleichen. Zum Beispiel gibt es n!=n*(n-1)*...*2*1 viele Möglichkeiten n unterschiedliche Spielkarten anzuordnen. Eine asymptotische Formel ist hier durch die Stirlingformel gegeben, die zeigt, dass n! superexponentiell wächst. Asymptotische Formeln können aus verschiedenen Komponenten bestehen, die zum Beispiel das polynomiale oder das exponentielle Wachstum darstellen. Gestreckte Exponenten sind eine bisher selten beobachtete Komponente, die grob gesagt zwischen polynomialem und exponentiellem Wachstum liegt. Sie haben die Form a^(n^s) für reelle Zahlen a und s sowie eine natürliche Zahl n. Kürzlich sind einige offene Probleme gelöst worden, in denen schlussendlich die Existenz von gestreckten Exponenten für deren Schwierigkeit verantwortlich war. Das Ziel dieses Projekts ist es generische Methoden zu entwickeln um solche gestreckten Exponenten nachzuweisen und zu berechnen. Weiters werden wir eine möglichst allgemeine Klasse von 2-parametrigen Rekursionen klassifizieren, die gestreckte Exponenten besitzen. Diese wollen wir dann auf offene Fragestellungen in der Mathematik, Biologie, Physik oder Chemie anwenden und hoffentlich viele neue Beispiele für das Auftreten von gestreckten Exponenten finden. Konkret handelt es sich um Probleme in der Automatentheorie, der Kompression von Datenstrukturen, der Phylogenetik, der algebraischen Gruppentheorie, der Warteschlangentheorie und vielen mehr. Unsere Methode zeichnet sich durch ihre Interdisziplinarität aus und vereint die Gebiete der Kombinatorik, der Computeralgebra und der komplexen Analysis. Unsere Ergebnisse erlauben weiterführend die tiefergehende Analyse von weiteren Parametern wie der typischen Laufzeit von Algorithmen.

Diskrete Strukturen spielen in vielen Bereichen unserer modernen Welt eine wichtige Rolle. In diesem Projekt haben wir Netzwerke untersucht, die von Datennetzwerken in der Informatik bis hin zu phylogenetischen Netzwerken (Modelle evolutionärer Bäume mit Rekombination) in der Biologie reichen. Unser Hauptinteresse galt ihren typischen Eigenschaften, wenn sie extrem groß werden. Wie sieht ein typischer Vertreter aus? Das Wort "typisch" bezieht sich hier auf ein Objekt, das gleichverteilt zufällig aus allen Objekten derselben Größe ausgewählt wird. Um diese Frage zu beantworten, müssen wir zunächst bestimmen, wie viele Objekte dieser Größe existieren. Während man bei kleinen Größen im Prinzip alle Möglichkeiten auflisten könnte, wird dies mit zunehmender Größe schnell unmöglich, und das Zählen wird äußerst aufwendig. Um die Anzahl zu bestimmen hätte man idealerweise gerne eine Formel, die sich leicht berechnen lässt. In vielen Fällen ist jedoch keine solche Formel bekannt und oft existiert sie gar nicht oder ist zu kompliziert. Deshalb interessieren wir uns für die bestmögliche Annäherung, wenn sich die Größe der Objekte gegen unendlich nähert und dies wird als asymptotische Formel bezeichnet. Dieser asymptotische Ansatz ermöglicht es uns, uns auf die dominierenden Strukturen zu konzentrieren und seltene auszublenden. Betrachten wir ein Netzwerk mit n Knoten. Wir könnten uns beispielsweise alle Graphen mit n Knoten vorstellen und fragen, wie viele solcher Graphen es gibt und wie ein typischer aussieht. Zu den klassischen Beispielen gehören dann polynomielles Wachstum wie n^2 oder exponentielles Wachstum wie 2^n. In einigen Fällen reichen diese Typen jedoch nicht aus, da bestimmte Klassen zusätzlich Faktoren enthalten, die schneller als jedes Polynom, aber langsamer als jede Exponentialfunktion wachsen. Solche Phänomene werden als "gestreckte Exponenten" bezeichnet und haben die Form exp(c*n^s), wobei c eine Konstante und s eine Zahl zwischen 0 und 1 ist. Bis vor kurzem waren nur wenige Fälle bekannt, die ein solches Phänomen aufweisen. In unserem Projekt konnten wir zeigen, dass dieses Phänomen in vielen diskreten Strukturen auftritt. Unter anderem konnten wir es in einer unendlichen Anzahl von Klassen phylogenetischer Netzwerke sowie in Modellen der theoretischen Physik, den sogenannten Young-Tableaux mit Wänden, nachweisen. Mit Hilfe dieser Ergebnisse gelang es uns zudem erstmals, die typischen Eigenschaften dieser Modelle erfolgreich zu untersuchen. So haben wir beispielsweise ermittelt, wie häufig Muster wie die Anzahl der Kirschen ("cherries") in phylogenetischen Netzwerken auftreten. Zudem haben wir über bijektive Abbildungen auf gewichtete Gitterpfadmodelle neue strukturelle Verbindungen zwischen verschiedenen Modellen identifiziert. All dies ermöglicht es uns nun, die Fragen adressieren, die den Ausgangspunkt dieser Arbeit bildeten, und das typische Verhalten großer diskreter Systeme besser zu verstehen.