Asymptotic study of families of unlabelled trees and other unlabelled graph structures

Abstract

Die vorliegende Dissertation beschäftigt sich mit der asymptotischen Analyse von zufälligen Graphenstrukturen, besonders Zufallsbäumen. Wir betrachten dazu die Menge von Objekten einer festen Größe (=Anzahl der Knoten) n und wählen daraus ein bezüglich der Gleichverteilung zufälliges Objekt aus. Wir untersuchen Eigenschaften solcher zufälliger Vertreter, wobei die Größe n gegen Unendlich strebt.<br />Wir zeigen für die Klasse der Polya-Bäume, dass die Größe eines Ward-Baumes asymptotisch von Ordnung \sqrt{n} ist, wobei ein Ward-Baum ein Unterbaum ist, der am Vater eines Blattes verwurzelt ist. Weiters zeigen wir, dass der Gradprofilprozess von Polya Bäumen schwach gegen die lokale Zeit einer Brown'schen Exkursion konvergiert.<br />Für verschiedene Modelle Boole'scher Bäume erhalten wir Resultate über die auf der Menge der Boole'schen Funktionen induzierte Wahrscheinlichkeitsverteilung. Genauer zeigen wir, dass die Wahrscheinlichkeit einer Funktion in direktem Zusammenhang mit ihrer Komplexität steht und das die verschiedenen Modelle verschiedene Wahrscheinlichkeitsverteilungen induzieren.<br />Im letzten Kapitel zeigen wir einen zentralen Grenzwertsatz für die Gradverteilung in unmarkierten subkritschen planaren Graphenklassen, sowohl für allgemeine Graphen als auch für ihre 2-zusammenhängenden Subklassen.<br />Alle Ergebnisse werden mithilfe von erzeugenden Funktionen und ihrer Singularitätenstruktur gewonnen, ein sehr mächtiges Werkzeug aus der analytischen Kombinatorik.<br />

This thesis deals with the asymptotic analysis of random graph structures, especially random trees. We consider the set of objects of fixed size (=number of vertices) n and choose an object from it uniformly at random. We study properties of such a random representative, when the size n tends to infinity. We show for the class of Polya trees that the size of a Ward-tree is asymptotically of order \sqrt{n}, where a Ward-tree is a subtree rooted at a parent node of a leaf. We further show that the degree profile process of Polya trees converges weakly to the local time of a Brownian excursion. For several models of Boolean trees we obtain results on the probability distribution they induce on the set of Boolean functions. To be more precise, we show that the probability of a function is in relation to its complexity and that different models induce different probability distributions.<br />In the last chapter we show a central limit theorem for the degree distribution in unlabelled planar subcritical graphs, as well for general graphs as for their 2-connected subclasses.<br />All results are obtained via generating functions and their singularity analysis, a very powerful tool from analytic combinatorics.<br />