Pattern occurrences in random planar maps and catalytic functional equations

Abstract

Eine planare Karte ist ein zusammenhängender planarer Graph (mit erlaubten Schleifen und mehreren Kanten), der in die Ebene eingebettet ist. Nach dem Einbetten von Karten zählen wir Karten aus auf Isomorphismen auf der Kugel. Das Studium der Planaren Karten geht auf Tutte zurück. In den letzten 10 oder 15 Jahren gab es jedoch ein Wiederbelebungsinteresse an planaren Karten, das hauptsächlich aufgrund der Arbeiten von Schaeffer begann und in der Identifizierung der Brownschen Karte als Skalierungsgrenze für große ebene Karten gipfelte. Vor kurzem gab es auch eine wachsendes Interesse an lokaler Konvergenz (zum Beispiel für Vierecke), die bedeutet, dass die lokale Struktur um die Wurzel (oder um einen zufälligen Scheitelpunkt) eine Wahrscheinlichkeitsverteilung, die sich stabilisiert, hat. Insbesondere zeigte Stephenson mit die Hilfe der Bouttier-Di Francesco-Guitter-Bijektion, dass zufällige planare Karten lokal konvergieren. Motiviert durch diese Ergebnisse präsentieren wir einige explizite Konvergenzresultate. Diese Ergebnisse basieren auf einem kombinatorischen Ansatz. Sie geben nicht ein vollständiges Bild, aber ergänzen die Ergebnisse von Stephenson und bilden eine direkte und explizite Analyse, die auch auf andere Situationen verallgemeinert werden kann, Das Problem des Auftretens von Mustern kann in zwei Kategorien eingeteilt werden, in ein Mustervorkommen um die Wurzel, also ein lokales Problem, und in das globale Vorkommen von Mustern. In dieser Arbeit präsentieren wir Ergebnisse für lokale und globale Muster. Während das lokale Problem vollständig gelöst werden kann, kann das globale Problem nur in erster Ordnung allgemein gelöst werden. Das bedeutet, dass wir den Erwartungswert der Anzahl eines gegebenen Musters bestimmen. Im globalen Kontext wird allgemein angenommen, dass die Zufallsvariable, die die Anzahl des Vorkommen eines Musters zählt, einen zentralen Grenzwertsatz erfüllt. Ein Hauptteil der Dissertation widmet sich der positiven Lösung dieses Problems in mehreren Sonderfällen. Die Nachweismethode basiert auf einem Ansatz für erzeugende Funktionen und ist unterteilt in zwei Hauptschritte, in ein kombinatorisches Problem, das zu einer katalytischen Gleichung führt, udn in ein asymptotisches Problem, das auf einer ausgeklügelten Analyse der katalytischen Funktionsgleichung beruht und schließlich zu einem zentralen Grenzwertsatz führt.

A planar map is a connected planar graph (with loops and multiple edges allowed) embedded in the plane. We count maps up to isomorphism after embedding maps on the sphere. The study of planar maps goes back to Tutte. However, within the last 10 or 15 years there has been a revival interest in planar maps which started mainly due to the work by Schaeffer and culminated in the identification of the Brownian map as the scaling limit of large planar maps. Recently there has also been a growing interest in local convergence (for example, for quadrangulations) which means that the local structure around the root (or around a random vertex) has a probability distribution that stabilizes. In particular, Stephenson showed with the help of the Bouttier-Di Francesco-Guitter bijection that random planar maps converge locally. Motivated by these results we present some explicit results on the local convergence. These results are based on a combinatorial approach. They do not give a full picture but complement the Stephensons results and constitute a direct and explicit analysis that can be also generalized to situations, where the approach cannot be applied, for example, to 2-connected maps. The problem of pattern occurrences can be classified into two categories. One is pattern occurrences around the root which is a local problem, the other is global pattern occurrences. In this thesis we present results for local and global pattern occurrences. Whereas the local problem can be completely solved, the global problem is solved in general only in first order, which means that we can characterize the expected number of occurrences of a given pattern. In the global context it is widely believed that the random variable that counts the number of occurrences of a pattern satisfies a central limit theorem. The main part of the thesis is devoted to the positive solution of this problem in several special cases. The proof method is based on a generating function approach and is divided into two major steps, into a combinatorial problem that leads to a catalytic functional equation and into an asymptotic problem that relies on a sophisticated analysis of the catalytic functional equation and leads finally to a central limit theorem.