Peeling Random Planar Maps: École d’Été de Probabilités de Saint-Flour XLIX – 2019 (Lecture Notes in Mathematics, 2335)

These Lecture Notes provide an introduction to the study of those discrete surfaces which are obtained by randomly gluing polygons along their sides in a plane. The focus is on the geometry of such random planar maps (diameter, volume growth, scaling and local limits...) as well as the behavior of statistical mechanics models on them (percolation, simple random walks, self-avoiding random walks...). A “Markovian” approach is adopted to explore these random discrete surfaces, which is then related to the analogous one-dimensional random walk processes. This technique, known as "peeling exploration" in the literature, can be seen as a generalization of the well-known coding processes for random trees (e.g. breadth first or depth first search). It is revealed that different types of Markovian explorations can yield different types of information about a surface. Based on an École d'Été de Probabilités de Saint-Flour course delivered by the author in 2019, the book is aimed at PhD students and researchers interested in graph theory, combinatorial probability and geometry. Featuring open problems and a wealth of interesting figures, it is the first book to be published on the theory of random planar maps. Introduction These Lecture Notes (Do Not) Contain Contents Part I (Planar) Maps 1 Discrete Random Surfaces in High Genus 1.1 What Is a Map? Different Points of View 1.1.1 Gluing of Polygons and a First Exploration Genus 1.1.2 Other Definitions of Maps Via Permutations Embedded Graphs 1.1.3 Duality 1.2 Geometry and Topology of Uniform Maps 1.2.1 Enumeration ``à la Tutte'' 1.2.2 Uniform Maps Are Almost Uniform Permutations Geometric and Topological Properties of a Uniform Map 1.3 Exploring Random Maps with Prescribed Faces and a Conjecture 1.3.1 Random Gluing of Prescribed Polygons 1.3.2 Peeling Explorations of MP 1.3.3 Examples of Peeling Explorations Conclusion: Impose Topological Constraints! 2 Why Are Planar Maps Exceptional? 2.1 Finite and Infinite Planar Maps 2.1.1 Finite Planar Maps 2.1.2 Local Topology and Infinite Maps 2.1.3 Infinite Maps of the Plane and the Half-Plane 2.2 Euler's Formula and Applications 2.2.1 k-Angulations and Bipartite Maps 2.2.2 Platonic Solids 2.2.3 Fàry Theorem 2.2.4 6–5–4 Color Theorem 2.2.5 Moser's circle 2.3 Faithful Representations of Planar Maps 2.3.1 Tutte's Barycentric Embedding 2.3.2 Circle Packing 3 The Miraculous Enumeration of Bipartite Maps 3.1 Maps with a Boundary and a Target 3.1.1 Maps with a Boundary 3.1.2 Maps with a Target 3.2 Counting Planar Maps and Tutte's Equation 3.2.1 The Case of Quadrangulations 3.2.2 Boltzmann Maps and Tutte Slicing Formula 3.3 Formulas for Disk Partition Functions 3.3.1 Boltzmann Measure 3.3.2 Admissibility 3.4 Getting Our Hands on W() 3.4.1 Towards an Expression for W() 3.4.2 Back to the Admissibility Criterion 3.5 Examples 3.5.1 2p-Angulations 3.5.2 Uniform Bipartite Maps 3.5.3 Triangulations 3.5.4 Canonical Stable Maps Part II Peeling Explorations 4 Peeling of Finite Boltzmann Maps 4.1 Peeling Processes 4.1.1 Gluing Maps with a Boundary 4.1.2 Peeling Process 4.1.3 Peeling Process with a Target and Filled-in Explorations 4.2 Law of the Peeling Under the Boltzmann Measures 4.2.1 q-Boltzmann Maps 4.2.2 q-Boltzmann Maps Without Target 4.2.3 q-Boltzmann Maps with Target 4.3 Simple Submaps and Simple Peeling Explorations 4.3.1 Maps with Simple Boundary 4.3.2 Simple Submaps 4.3.3 Simple Peeling Exploration 4.3.4 Law of the Simple Peeling Under the Boltzmann Measure 5 Classification of Weight Sequences 5.1 The ν-Random Walk 5.1.1 The Step Distribution ν 5.1.2 Probabilistic Interpretation of the h↓p-Transformation 5.2 Critical Weight Sequences 5.2.1 Equivalent Definitions of Criticality 5.2.2 h↑-Transform 5.3 Discrete Stable Weight Sequences 5.3.1 Subcritical Case: a= 32 5.3.2 Critical Generic Case: a= 52 5.3.3 Critical Non-generic: a (3/2;5/2) 5.3.4 Examples Part III Infinite Boltzmann Maps 6 Infinite Boltzmann Maps of the Half-Plane 6.1 The Half-Planar Boltzmann Map 6.1.1 Characterizing P(∞) 6.1.2 Peeling Process Under P(∞) 6.1.3 Constructing P(∞) 6.1.4 P(∞) as the Weak Limit of P() as →∞ 6.2 Basic Properties 6.2.1 Translation Invariance and Ergodicity 6.2.2 Cut-Edges and Cut-Points 7 Infinite Boltzmann Maps of the Plane 7.1 Infinite Boltzmann Maps of the Plane 7.1.1 Characterizing P()∞ 7.1.2 Peeling Process Under P()∞ 7.1.3 Constructing P()∞ 7.1.4 P()∞ as the Limit of Maps Conditioned to be Large 7.2 Basic Properties 7.2.1 Stationarity and Reversibility 7.2.2 Ergodicity 8 Hyperbolic Random Maps 8.1 Constructions 8.2 Basic Properties 8.2.1 Stationarity, Reversibility and Ergodicity 8.2.2 Anchored Expansion 9 Simple Boundary, Yet a Bit More Complicated 9.1 Enumeration of Maps with a Simple Boundary 9.1.1 The Core Decomposition 9.1.2 Free Boltzmann Map and Exploration of the Core 9.2 Infinite ∂-Simple Boltzmann Maps of the Half-Plane 9.2.1 Defining M̃(∞) and (∞) 9.2.2 Simple Peeling Exploration of (∞) 9.2.3 (∞) as the Weak Limit of () 9.3 Basic Properties 10 Scaling Limit for the Peeling Process 10.1 Invariance Principles for the Perimeter Process 10.1.1 The Case of the ν-Walk S 10.1.2 The Cases of S↑ and S↓ 10.2 Scaling Limit for the Volume Process 10.2.1 Stable Limit for the Volume of Boltzmann Maps 10.2.2 Functional Scaling Limit for the Volume and Perimeter Processes 10.2.3 Law of ``Iterated'' Logarithm 10.3 Scaling Limits in the Hyperbolic Regime 10.4 Markovian Explorations Are Always Roundish Part IV Percolation(s) 11 Percolation Thresholds in the Half-Plane 11.1 Prerequisites 11.1.1 Randomized Peeling Process 11.1.2 Mean Gulp and Exposure 11.2 Face Percolation 11.2.1 Annealed Threshold and Exploration of Face Percolation 11.2.2 Proof of Theorem 11.3 11.2.3 Dual Exploration 11.2.4 Degree Percolation 11.3 Bond Percolation 11.3.1 A Heuristic Before the Proof: Adding Faces of Degree 2 11.3.2 The True Proof: Adding Crosses! 11.4 Site Percolation and the Simple Peeling 11.4.1 Back to Bond and Face Percolations 11.4.2 Site Percolation 12 More on Bond Percolation 12.1 Critical Exponents in the Half-Plane 12.1.1 Length of Exploration 12.1.2 More Open Questions 12.2 A Boltzmann Approach to Bond Percolation 12.2.1 Duality of Stable Maps Via Percolation 12.2.2 Critical Exponents and Open Questions 12.3 Percolations on M∞ 12.3.1 Do Plane and Half-Plane Bond Percolation Thresholds Coincide? 12.3.2 Open Questions 12.4 Percolation on Hyperbolic Random Maps 12.4.1 Critical and Uniqueness Thresholds 12.4.2 Open Questions Part V Geometry 13 Metric Growths 13.1 Eden Model: Exponential FPP Distances on the Dual 13.1.1 Definition of the Eden Distance 13.1.2 Uniform Peeling 13.1.3 Fpp Growth on M∞ 13.1.4 Fpp Growth on H∞ 13.2 Dual Graph Distances 13.2.1 Exploration of Dual Metric 13.2.2 Growth of the Dual Metric in M∞ 13.2.3 Growth of the Dual Metric on H∞ 13.2.4 Cut-Points in the Dense Phase 13.3 Primal Graph Distances 13.3.1 Triangulations 13.3.2 Quadrangulations 13.3.3 General Case 13.4 ... and for the Half-Plane ? 14 A Taste of Scaling Limit 14.1 Gromov–Hausdorff Topology 14.1.1 Space of Metric Spaces 14.1.2 Gromov–Hausdorff Topology 14.1.3 Properties 14.2 Scaling Limits for Large Boltzmann Maps 14.2.1 The Brownian Sphere 14.2.2 The Stable Maps 14.3 Scaling Limit for Dual Maps and Growth-Fragmentation Trees 14.3.1 Genealogy on Holes 14.3.2 Slicing at Heights Part VI Simple Random Walk 15 Recurrence, Transience, Liouville and Speed 15.1 M∞ Is Recurrent 15.1.1 Discrete Uniformization of Infinite Planar Graphs 15.1.2 Benjamini–Schramm Limits 15.2 Simple Random Walk on M∞ 15.2.1 Transience of M∞ in the Dense Case 15.2.2 Intersection and Recurrence 15.3 Hyperbolic Maps and Positive Speed 15.3.1 Anchored Expansion, Speed and Stationarity 16 Subdiffusivity and Pioneer Points 16.1 Pioneer Points and Subdiffusivity 16.1.1 Pioneer Points 16.1.2 Primal Distances 16.1.3 About Tentacles 16.2 Subdiffusivity via Stationarity 16.2.1 Subdiffusivity from Diffusivity on a Sparse Subgraph 16.2.2 Heuristic for G_R A Elements of Fluctuation Theory A.1 Oscillations, Duality A.2 Cyclic Lemma and Applications A.2.1 Feller's Cyclic Lemma A.2.2 Applications Skip-Free Walks Plane Trees A.3 Random Walks Conditioned to Stay Positive A.3.1 h-Transform of Markov Chains A.3.2 Renewal Function A.3.3 Oscillating Case and Limit of Large Conditionings A.3.4 Tanaka's Construction A.3.5 Drift to -∞ and Cramér's Condition A.4 Ratio and Local Limit Theorem A.4.1 Strong Ratio Limit Theorem A.4.2 Local Limit Theorem B Coding of Bipartite Maps with Labeled Trees B.1 Bouttier–Di Francesco–Guitter Coding of Bipartite Maps B.1.1 From Maps to Trees B.1.2 From Trees to Maps B.2 Distribution of the Forest of Mobiles B.2.1 Janson and Stefansson's Trick B.2.2 Law of the Unlabeled Forest B.3 Back to the Enumeration Results B.3.1 Back to the Admissibility Criterion B.3.2 Interpretation of the Law J and Back to Criticality Bibliography