Various bijections between maps and tree-like structures

Abstract

This thesis investigates bijections between planar maps and tree-like structures, an essential concept in modern combinatorics with connections to probability theory and statistical physics. Since Tutte’s pioneering work on the enumeration of planar maps, many bijective approaches have been developed by different authors, and here we collect and present a variety of them, with the aim of highlighting their common principles and distinctive features. To this end, we introduce a unified notation and distinguish two main categories of bijections: (A) blossoming-tree bijections, where maps are encoded by decorated spanning trees, and (B) non-spanning-tree bijections, where encodings rely on alternative structures such as well-labeled trees or mobiles. For each category, we describe a unified scheme that captures the essence of the bijective constructions and illustrates how different results fit into this broader picture. Applications of these bijections to enumeration purposes are then discussed in detail. First, we revisit classical results as the enumeration of rooted Eulerian maps and quadrangulations that have already been derived using other approaches. The bijections not only recover known counting formulas, but also provide a deeper conceptual understanding of the specific structural form of these formulas. Finally, we briefly touch upon geometric aspects, in particular, how bijections such as the Cori–Vauquelin–Schaeffer correspondence serve as a starting point for the analysis of distances in random planar maps and for scaling-limit results leading to the Brownian map. Rather than giving full proofs of these probabilistic results, the thesis focuses on providing the combinatorial background needed to understand how bijective methods support the study of random geometry.

Diese Arbeit befasst sich mit Bijektionen zwischen planaren maps und baumartigen Strukturen, ein essentielles Konzept der modernen Kombinatorik mit Verbindungen zur Wahrscheinlichkeitstheorie und zur statistischen Physik. Seit Tuttes bahnbrechenden Arbeiten zur Enumeration planarer Maps wurden von verschiedenen Autoren zahlreiche bijektive Methoden entwickelt. In dieser Arbeit werden diese Ansätze gesammelt und präsentiert, mit dem Ziel, ihre gemeinsamen Prinzipien und charakteristischen Unterschiede hervorzuheben.Zu diesem Zweck führen wir einheitliche Notationen ein und unterscheiden zwei Hauptkategorien von Bijektionen: (A) Blossoming-Tree-Bijektionen, bei denen Karten durch de-korierte Spannbäume codiert werden, und (B) Nicht-Spannbaum-Bijektionen, bei denen alternative Strukturen wie well-labeled Bäume oder Mobiles verwendet werden. Für jede Kategorie beschreiben wir ein vereinheitlichtes Schema, das die Essenz der bijektiven Konstruktionen erfasst und aufzeigt, wie verschiedene Resultate in dieses Gesamtbild passen. Anwendungen dieser Bijektionen zur Enumeration werden anschließend im Detail diskutiert. Zunächst betrachten wir klassische Resultate wie die Enumeration gewurzelter Eulerscher Maps und Quadrangulierungen, die bereits mit anderen Methoden hergeleitet wurden.Die Bijektionen liefern dabei nicht nur bekannte Abzählformeln, sondern ermöglichen auch ein tieferes konzeptionelles Verständnis der speziellen Struktur dieser Formeln. Abschließend gehen wir kurz auf geometrische Aspekte ein, insbesondere darauf, wie Bijektionen wie die Korrespondenz von Cori–Vauquelin–Schaeffer als Ausgangspunkt für die Analyse von Abständen in zufälligen planaren Maps und für Resultate zu Skalierungs-Limits dienen, die zur sogenannten Brown’schen Map konvergieren. Anstelle vollständiger Beweise dieser probabilistischen Resultate liegt der Fokus der Arbeit auf dem kombinatorischen Hintergrund, der notwendig ist, um zu verstehen, wie bijektive Methoden das Studium der Zufallsgeometrie unterstützen.