UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Hyperbolic random maps Ray, Gourab 2014

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata


24-ubc_2014_september_ray_gourab.pdf [ 1.03MB ]
JSON: 24-1.0167338.json
JSON-LD: 24-1.0167338-ld.json
RDF/XML (Pretty): 24-1.0167338-rdf.xml
RDF/JSON: 24-1.0167338-rdf.json
Turtle: 24-1.0167338-turtle.txt
N-Triples: 24-1.0167338-rdf-ntriples.txt
Original Record: 24-1.0167338-source.json
Full Text

Full Text

Hyperbolic random mapsbyGourab RayB.Stat., Indian Statistical Institute, 2008M.Stat., Indian Statistical Institute, 2010A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFDOCTOR OF PHILOSOPHYinThe Faculty of Graduate and Postdoctoral Studies(Mathematics)THE UNIVERSITY OF BRITISH COLUMBIA(Vancouver)July 2014c© Gourab Ray 2014AbstractRandom planar maps have been an object of utmost interest over the lastdecade and half since the pioneering works of Benjamini and Schramm, An-gel and Schramm and Chassaing and Schaeffer. These maps serve as modelsof random surfaces, the study of which is very important with motivationsfrom physics, combinatorics and random geometry.Uniform infinite planar maps, introduced by Angel and Schramm, whichare obtained as local limits of uniform finite maps embedded in the sphere,serve as a very important discrete model of infinite random surfaces. Re-cently, there has been growing interest to create and understand hyperbolicversions of such uniform infinite maps and several conjectures and proposedmodels have been around for some time. In this thesis, we mainly addressthese questions from several viewpoints and gather evidence of their exis-tence and nature.The thesis can be broadly divided into two parts. The first part isconcerned with half planar maps (maps embedded in the upper half plane)which enjoy a certain domain Markov property. This is reminiscent of thatof the SLE curves. Chapters 2 and 3 are mainly concerned with classificationof such maps and their study, with a special focus on triangulations. Thesecond part concerns investigating unicellular maps or maps with one faceembedded in a high genus surface. Unicellular maps are generalizations oftrees in higher genera. The main motivation is that investigating such mapswill shed some light into understanding the local limit of general maps viasome well-known bijective techniques. We obtain certain information aboutthe large scale geometry of such maps in Chapter 4 and about the local limitof such maps in Chapter 5.iiPrefaceThe new results of this thesis are based primarily on four research articles:[9, 12, 81, 82]. Article [12] is joint work with Omer Angel. Paper [9] is jointwork with Omer Angel, Guillaume Chapuy and Nicolas Curien. Articles[81, 82] are independent works of the author of this thesis.The results of [12] are presented in Chapter 2, that of [82] in Chapter 3.The material of [81] is collected in Chapter 4. Finally the results in [9] formthe basis of Chapter 5.iiiTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiList of symbols and acronyms . . . . . . . . . . . . . . . . . . . . xiAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . xviDedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xviii1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 The local topology . . . . . . . . . . . . . . . . . . . . . . . . 41.3 The big picture . . . . . . . . . . . . . . . . . . . . . . . . . 61.3.1 Enumeration . . . . . . . . . . . . . . . . . . . . . . . 61.3.2 Universality . . . . . . . . . . . . . . . . . . . . . . . 91.3.3 Quantum gravity . . . . . . . . . . . . . . . . . . . . 101.4 Percolation on random maps . . . . . . . . . . . . . . . . . . 111.5 Unicellular maps . . . . . . . . . . . . . . . . . . . . . . . . . 121.6 Hyperbolic random maps . . . . . . . . . . . . . . . . . . . . 152 Classification of half planar maps . . . . . . . . . . . . . . . . 192.1 Translation invariant and domain Markov measures . . . . . 192.2 Main results . . . . . . . . . . . . . . . . . . . . . . . . . . . 212.3 Other approaches to the domain Markov property . . . . . . 242.4 Peeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272.5 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 282.5.1 Boltzmann distribution . . . . . . . . . . . . . . . . . 282.6 Half planar triangulations . . . . . . . . . . . . . . . . . . . . 29ivTable of Contents2.7 Existence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342.8 The phase transition . . . . . . . . . . . . . . . . . . . . . . . 362.9 Non-simple triangulations . . . . . . . . . . . . . . . . . . . . 372.10 Simple and general p-angulations . . . . . . . . . . . . . . . 412.11 Non-simple p-angulations . . . . . . . . . . . . . . . . . . . . 472.12 Approximation by finite maps . . . . . . . . . . . . . . . . . 492.13 Quadrangulations and beyond . . . . . . . . . . . . . . . . . 513 Half planar maps: geometry . . . . . . . . . . . . . . . . . . . 543.1 Main results . . . . . . . . . . . . . . . . . . . . . . . . . . . 563.1.1 Geometry . . . . . . . . . . . . . . . . . . . . . . . . . 563.1.2 Percolation . . . . . . . . . . . . . . . . . . . . . . . . 593.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 613.2.1 Free triangulations . . . . . . . . . . . . . . . . . . . 623.2.2 Stable random variables . . . . . . . . . . . . . . . . . 633.2.3 Peeling . . . . . . . . . . . . . . . . . . . . . . . . . . 633.3 Geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 643.3.1 Peeling algorithm . . . . . . . . . . . . . . . . . . . . 643.3.2 Supercritical . . . . . . . . . . . . . . . . . . . . . . . 663.3.3 Subcritical . . . . . . . . . . . . . . . . . . . . . . . . 713.4 Percolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 753.5 Open questions . . . . . . . . . . . . . . . . . . . . . . . . . . 814 Unicellular maps: large scale structure . . . . . . . . . . . . 824.1 Main results . . . . . . . . . . . . . . . . . . . . . . . . . . . 824.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 864.2.1 The bijection . . . . . . . . . . . . . . . . . . . . . . . 864.2.2 Typical λ . . . . . . . . . . . . . . . . . . . . . . . . . 894.2.3 Large deviation estimates on random trees . . . . . . 904.3 Proof outline . . . . . . . . . . . . . . . . . . . . . . . . . . . 914.4 Lower bound and injectivity radius . . . . . . . . . . . . . . 924.5 Upper bound . . . . . . . . . . . . . . . . . . . . . . . . . . . 1044.5.1 Remaining proofs . . . . . . . . . . . . . . . . . . . . 1135 Unicellular maps: the local limit . . . . . . . . . . . . . . . . 1155.1 Main results . . . . . . . . . . . . . . . . . . . . . . . . . . . 1155.2 Enumeration and root degree distribution . . . . . . . . . . . 1165.3 The low genus case . . . . . . . . . . . . . . . . . . . . . . . 1195.4 The local limit . . . . . . . . . . . . . . . . . . . . . . . . . . 1205.4.1 Surgery . . . . . . . . . . . . . . . . . . . . . . . . . . 120vTable of Contents5.5 Identifying the limit . . . . . . . . . . . . . . . . . . . . . . . 1215.6 Questions and remarks . . . . . . . . . . . . . . . . . . . . . 123Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124AppendicesA Proof of lemma 3.2.2 . . . . . . . . . . . . . . . . . . . . . . . . 132B Proof of lemma 4.2.6 . . . . . . . . . . . . . . . . . . . . . . . . 134C Proofs of the lemmas in section 4.2.3 . . . . . . . . . . . . . 137C.1 Critical Galton-Watson trees . . . . . . . . . . . . . . . . . . 137C.2 Supercritical Galton-Watson trees . . . . . . . . . . . . . . . 137C.3 Random plane trees . . . . . . . . . . . . . . . . . . . . . . . 138viList of Figures1.1 Left: A map with a boundary. Right: A map with a simpleboundary. The boundary edges and vertices are marked red. . 21.2 Left: The critical Galton-Watson tree with Geometric(1/2)offspring distribution conditioned to survive. Right: A canopytree which is the local limit of binary trees cut off at the nthlevel. The numbers beside the vertices represent the proba-bility of them being the root. For example the probability ofthe leftmost vertex in the bottom level has probability 1/2 ofbeing the root and so on. . . . . . . . . . . . . . . . . . . . . 51.3 An illustration of the Schaeffer bijection. Left: Figure showsthe way we move along the contour of the tree with 6 verticesstarting from the root vertex. This also introduces a naturalcontour order between the vertices. Middle: Observe thatthe minimal label in the tree is −1. We add a new vertex∂ with label −2. For each vertex encountered while movingaround the contour, draw an arc between the vertex and thenext vertex in the contour order with label one less. Draw anarc between vertices with label −1 and the vertex ∂. Orientthe edge between the root vertex and ∂ in one of the twoways. Right: The rooted quadrangulation, pointed at ∂ with7 vertices obtained by erasing the tree. . . . . . . . . . . . . . 81.4 An illustration of an interface between a black and a whitecluster for percolation in a half planar triangulation. . . . . . 121.5 A unicellular map and its underlying graph. . . . . . . . . . . 131.6 The process of obtaining a scheme of a unicellular map. . . . 131.7 The way of exploring the face in unicellular map. . . . . . . . 141.8 Illustration of the construction of UIPQ in [43]. . . . . . . . . 17viiList of Figures2.1 Left: A finite map Q. Centre: part of a map M containing Qwith 2 edges along the boundary. Right: the resulting mapM˜ . The domain Markov property states that M˜ has the samelaw as M . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202.2 Possibilities when removing a sub-map Q connected to theboundary. The red part is CM which is identified with CQ.Left: Q consists of a single triangle. Right: Q consists of twofaces in a general map. The shaded areas are the holes —finite components of the complement of Q. . . . . . . . . . . . 252.3 Basic building blocks for triangulations. Left: the event Aα.Centre and right: the two events of type Aβ. . . . . . . . . . 292.4 Cases in the inductive step in the proof of Lemma 2.6.2. . . . 312.5 Non-uniqueness for triangulation with self-loops. Startingwith a triangulation with simple faces (left), each edge is re-placed by a geometric number of parallel edges with a self-loopat one of the two vertices between any pair (greater than 1at the bold edges). Independent maps with arbitrary distri-bution are added inside the self-loops (shaded). Note thatmultiple edges may occur on the left (but not self-loops). . . 392.6 Exploring in different orders shows that self-loops are equallylikely to be at each end-point of a 2-gon. Conditioning onface A and removing it leaves a non-simple face along theboundary with the self-loop at the left vertex. Removinginstead face B leaves the self-loop on the right vertex. . . . . 412.7 Building blocks for quadrangulations and general p-angulations.Shown: an event of type A5 for p = 9 and the three buildingblocks for p = 4. . . . . . . . . . . . . . . . . . . . . . . . . . 422.8 The event B4 for p = 6. Depending on the order of explo-ration, its probability is found to be α23 or α4α2. . . . . . . . 432.9 A possible configuration for the root face in a 13-angulation.The hole parameters (ki,mi) from left to right are (4, 5),(2, 2), (5, 7). There are j = 5 vertices exposed to infinity,so the probability of this configuration is α5 · (β2γZ5) · (Z2) ·(β3γ2Z7). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 452.10 Possible faces incident to a boundary edge for quadrangu-lations. The first three may also be reflected to give the 8topologically distinct possibilities. The holes (shaded) canhave boundary of any even length. . . . . . . . . . . . . . . . 46viiiList of Figures2.11 Non-uniqueness for quadrangulations: each edge is replacedwith a geometric number of parallel edges. In each 2-gon aninternal 2–gon is added at a uniformly chosen endpoint, andfilled with an independent finite (possibly empty) quadran-gulation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 483.1 An illustration (artistic) of the geometry of a subcritical halfplanar triangulation to the left and that of supercritical to theright. The blue edges in the subcritical map is the boundaryof the map. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 553.2 Left: An α-step. Centre: A step of the form (R, i). Right: Astep of the form (L, i). The gray area denotes some unspeci-fied triangulation. . . . . . . . . . . . . . . . . . . . . . . . . . 553.3 An very rough intuition of the geometry of supercritical maps. 573.4 An illustration of peeling at the nth step. The gray areadenote the peeled part Pn. The red vertices and edges denotethe internal boundary of Pn. . . . . . . . . . . . . . . . . . . . 653.5 Left: An illustration of a t-bad segment. The segment con-sisting of blue vertices is a t-bad segment. The gray area issome fixed finite triangulation. Right: The red vertices forma (k, i+ j)-separating loop . . . . . . . . . . . . . . . . . . . . 693.6 An illustration of the proof of Lemma 3.4.5. The gray areato the left denotes the revealed part in the exploration. . . . . 804.1 On the left: a unicellular map of genus 2. On the right: itsunderlying graph. . . . . . . . . . . . . . . . . . . . . . . . . . 834.2 An illustration of a C-decorated tree. (a) A C-permutationσ where each cycle is marked with a different color. (b) Aplane tree t with the vertices in the same cycle of σ joined byan arrow of the same color as the cycle. Note that verticesnumbered 8 and 9 are fixed points in the C-permutation. (c)The underlying graph of the C-decorated tree (t, σ). The rootvertex is circled. . . . . . . . . . . . . . . . . . . . . . . . . . 874.3 The web is denoted by the red paths. On the left: a generalweb structure. A priori the web structure might be verycomplicated. Many paths in the web might pass through thesame vertex as is depicted here. On the right: A typical webstructure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 964.4 v∗ denotes the root vertex. (v, v′) is a bad pair if either ofred, green or blue part has at most log2 n many vertices. . . . 97ixList of Figures4.5 Illustration of the death rule in exploration process II. A snap-shot of the revealed vertices when we are exploring the circledvertex v is given. The black vertices and edges correspond toneutral and active vertices, while the crosses correspond todead vertices. We are exploring v and mark(v) is denotedby the red vertices. On the left: a red vertex comes withindistance log3 n of one the revealed vertices, hence death ruleis satisfied. On the right: two of the revealed vertices arewithin distance log3 n. Hence death rule is satisfied. . . . . . 1074.6 An illustration of a worm at a certain step in the explorationprocess. The black vertices denote the vertices of the worm,the crosses are the dead vertices and the head of the worm isas shown. The circle is the v∗-ancestor of the head which isnot dead. This worm has faced death 5 times so far. . . . . . 1095.1 Illustration of the surgical operation . . . . . . . . . . . . . . 120xList of symbols and acronymsA list of symbols and acronyms along with the page number where theyappear for the first time is given below chapter wise.Chapter 1Br(G) The combinatorial ball of radius r around the root of arooted graph G....page 4.Cat(n) The nth catalan number: 1n+1(2nn)....page 14.E(M) The set of edges of a map M ....page 2.F (M) The set of faces of a map M ....page 2.HUIPT Half-plane uniform infinite planar triangulations....page 6.φn,m Number of triangulations without loops of an m-gon with ninternal vertices....page 7.SHIQ Stochastic hyperbolic infinite quadrangulations....15.Tg,n Set of triangulations of genus g with n vertices....page 16UIPT Uniform infinite planar triangulations....page 6.UIPQ Uniform infinite planar quadrangulations....page 6Ug,n The set of unicellular maps of genus g with n edges....page82.V (M) The set of vertices of a map M ....page 2.|X| Cardinality of a set X...page 2.Chapter 2α The probability of the event that the triangle incident to theroot edge is incident to an internal vertex....page 21.AQ,k The event defined in page 20.xiList of symbols and acronymsβp−2 The probability of the event that the face incident to theroot edge consists of a single contiguous segment of lengthp− 2 from the infinite boundary and no internal vertex..seepage 30 (for p = 3) and page 43.γp−2 The probability of the event that the face incident to the rootedge consists of a single edge from the infinite boundary andp− 2 internal vertices...page 43.H Generic class of half plane maps....page 19.H′ Generic class of simple faced half plane maps....page 19.Hp The class of infinite one-ended half plane p-angulations....19H′p The class of simple faced infinite one-ended half plane p-angulations....19Hα Translation invariant and domain Markov measures sup-ported on half-plane loopless triangulations with parameterα....page 21.H(p)α Translation invariant and domain Markov measures sup-ported on half-plane simple faced p-angulations with param-eter α....page 21.Hα,q,ν Translation invariant and domain Markov measuressupported on half-plane triangulations with loops al-lowed....page 38.µm,n Uniform measure on the set of triangulations of an m-gonwith n internal vertices....page 23.pi,k The probability that the triangle incident to a fixed bound-ary edge e of a domain Markov half planar triangulationhas its third vertex on the boundary at a distance i alongthe boundary to the right (or left) of e and that this tri-angle separates k internal vertices of the triangulation frominfinity....page 29.pi The probability that the triangle incident to a fixed bound-ary edge e of a domain Markov half planar triangulation hasits third vertex on the boundary at a distance i along theboundary from e....page 36Zm(x) The generating function of the number of p-angulations ofan m-gon with weight x for every internal vertex....page 28(for p = 3) and page 44.xiiList of symbols and acronymsChapter 3Br(α) The hull of the ball of radius r around the root of a mapwith law Hα....page 56.END(C) The space of ends of a percolation cluster C....page 61.Im(q) Number of internal vertices of a freely distributed triangu-lation of an m-gon with parameter q.....page 62.(L, i) The event that the triangle incident to the root edge is at-tached to a vertex on the boundary which is at a distance ialong the boundary to the left of the root edge....page 54.∂Br(α) Internal boundary of the hull of the ball of radius r aroundthe root of a map with law Hα....page 56.∂ES Set of edges with one vertex in S another in the complementof S....page 57.Pn The sub-map revealed after n steps of peeling....page 63.Pp The overall law of the map along with Bernoulli(p) site per-colation on it....page 60.pc Critical percolation probability...page 60.pu Infimum over p such that there exists a unique infinite per-colation cluster for Bernoulli (p) percolation....page 60.(R, i) The event that the triangle incident to the root edge has itsthird vertex on the boundary which is at a distance i alongthe boundary to the right of the root edge....page 54.|S|E Sum of the degrees of the vertices in S....page 57.Tn The complement of the revealed map after n steps of peel-ing....page 63.Sn = Vn −Xn....page 68.τr Number of peeling steps required to reveal the hull of theball of radius r in the peeling algorithm....page 64.Vn Volume of the map revealed after n steps of peeling....page68.Xn Internal boundary of the revealed map after n steps of peel-ing....page 65.xiiiList of symbols and acronymsChapter 4Ck The event that collision has not occurred up to step k....page112.Cg,n The set of C-decorated trees of genus g with n edges....page86.dG(., .) The graph distance metric in a graph G....page 82.dλ The graph distance metric in the underlying graph ofTλ(n)...page 93.δ The step number when we stop the exploration process I(resp. exploration process II, stage 1)....page 95 (resp. 107).diam(G) The diameter of a graph G....page 83.dTV (X,Y ) The total variation distance between X and Y ....page 98.Er Vertices revealed after round r of exploration....pages 94,106.GW The Galton-Watson tree defined in page 110.Ig,n The local injectivity radius of Ug,n....page 85.λ An element from the set P....page 87.m(v) The mark of v....page 87.mark(v) The set of vertices with the same mark as v....page 94.Mr maxv∈V (U0,n) |Br(v)| where Br(v) is the combinatorial ballof radius r around v in U0,n....page 91.Nr = Er \ Er−1: The set of active vertices in Er....page 94.P The set of ordered N -tuples of odd positive integers whichadd up to n+ 1....page 87.Φσ,e Number of rooted embedded forests consisting of σ trees ande edges....page 100.Pλ The conditional measure induced by Tλ.... page 89.Qk The set of dead vertices revealed after k steps of explo-ration....page 106.Rk The subgraph revealed at the kth step of exploration....pages94, 106.S = (S0, S1, . . . Sδ′): The set of seeds revealed up to stepδ....page 96.S˜ = (S˜0, S˜1, . . . S˜δ′): An i.i.d. sample of uniformly picked ver-tices from U0,n....page 98.xivList of symbols and acronymsTλ(n) The set of marked trees corresponding to the N -tupleλ....page 88.Tλ(n) A uniformly picked element from Tλ(n)....page 88.(t,m) A marked tree with plane tree t and a marking functionm....page 93.TC The auxiliary tree defined in page 108.τr Number of steps needed to complete round r of explo-ration....pages 94, 106.Ug,n The set of unicellular maps of genus g with n edges....page82.Ug,n Uniformly picked element from Ug,n.....page 82.v− The v∗-ancestor which is not dead and nearest to v in thetree t....page 107.Zr The number of vertices at a distance r from the root vertexof TC ...page 108.ZGWj The number of vertices at a distance j from the root vertexof GW ..page 111.Chapter 5βθ The solution of β for (5.1.1)....page 115.Geom(ξ) Geometric distribution with parameter ξ....page 115.T∞ξ Galton-Watson tree with geometric(ξ) −1 offspring distri-bution conditioned to be infinite....page 115.Ug,n The set of unicellular maps of genus g with n edges....page82.Ug,n Uniformly picked element from Ug,n.....page 82.Xβ Random Variable defined in page 116.xvAcknowledgementsFirst of all, I would like to thank my supervisor Prof. Omer Angel forproviding me invaluable support throughout my stay in UBC. He alwaysanswers my questions with utmost patience and care and is very generousabout spending time with me discussing mathematics. Among many otherthings, he was the first to introduce me to the intriguing and beautiful worldof random maps and I have been hooked ever since. Apart from discussingmathematics, he also introduced me to many wonderful mathematicianswhich also played a very important role in shaping my research career sofar. He was also very generous in providing funding for my stay in UBC aswell as for traveling to many interesting meetings and conferences. I wouldlike to specially thank him for providing support for my trip to the summerschool in Saint-Flour in 2011 where I had the privilege to meet Prof. ItaiBenjamini for the first time and for the visit to Paris in 2013 where I hadthe chance to collaborate with Guillaume Chapuy and Nicolas Curien alongwith Omer himself.Being part of the supremely active and dynamic probability group inUBC is an experience on its own. I have been part of a number of researchlevel courses, reading seminars and projects which helped me immensely togrow as a researcher. Many thanks to my friends in the probability group:Roland Bauerschmidt, Yu Ting Chen, Tyler Helmuth , Tim Hulshof, Ba´la´zsRath, Dennis Timmers, Yuri Mejia Miranda, Alex Tomberg, Daniel Valesin,Tom Hutchcroft, Brett Kolesnik, Benjamin Wallace, Zichun Ye, Jing Yuand Qingsan Zhu for making my stay in UBC memorable. I would alsolike to thank professors Martin Barlow, David Brydges, Ed Perkins, GordonSlade, Juan Souto and Asaf Nachmias for running some wonderful coursesand reading seminars and also for patiently answering all my questions. Igained a lot from them. A special thanks should go out to Asaf Nachmiasfor listening to all my blabbering for the past three years. Thanks also toJim Richardson and Asif Zaman for all the wonderful time we spent togetherin my first year here in UBC.Simply put, life is meaningless without friends. I do not make closefriends very easily, but nevertheless I now have two very close friends I firstxviAcknowledgementsmet in UBC: Nishant Chandgotia and Vasu Tewari. Thanks for all thewonderful time we spent together. Special thanks to Vasu for enduring mycooking skills for two years and helping me learn just enough French so thatI could make my way to Saint-Flour. Special thanks to Nishant for forcingme to climb all those mountains. Thanks also to Subhajit Jana for all theinteresting discussions we had time and again over the past year or so.Thanks to all my friends and professors from ISI for providing me supportand writing me recommendation letters which helped me come to UBC.Special thanks to Professors Krishanu Maulik and Amitesh Dasgupta for allthe support during my phd applications. I would not have made anywherenear this far unless I was inspired by three of my closest friends from ISI:Sayan Banerjee, Ritabrata Das and Abhirup Datta. Thanks also to PramitaBagchi, Somak Dutta, Subhajit Mandal, Swarnali Banerjee, Debashree Ray,Adityadeb Mukherjee and Tamoghna Roy for being such wonderful friendsand bearing with me for so many years. I would also like to thank SirDebashish Burman for creating the stepping stone of my mathematics careerduring my high school days.I met Poulami for the first time at the beginning of my phd which shouldcount as one of the significant events of my life. Thanks Poulami for alwaysbeing with me and helping me through the tough times.Finally, the biggest acknowledgement should go out to my parents fromwhom I first learnt about numbers. Without their constant support, sacrificeand love, nothing would have been possible. Dhonnobad Baba aar Maa.xviiDedicationTo my parents and all my friends.xviiiChapter 1Introduction1.1 DefinitionsWe begin with some basic definitions of the objects we shall work with.Definition 1.1.1. A map is a proper embedding of a connected (multi)graphon a compact orientable surface viewed up to orientation preserving home-omorphisms from the surface to itself. Further, the embedding is such thatthe complement of the embedding is a union of disjoint topological discs.Let us clarify few terms in Definition 1.1.1. By a proper embedding, wemean the embedding is such that the edges do not cross each other. Fromthe classification of surfaces theorem (see [73], Theorem 1 or [32]), we knowthat every compact orientable surface can be viewed as a connected sum of afinite number of tori. Thus the reader can imagine the surfaces on which weembed the graphs to be just a connected sum of finite number of tori (whichwe sometimes refer to as handles) and the number of handles is called thegenus of the underlying surface of the map. When the genus is 0, that is theunderlying surface of the map is a sphere, the map is called a planar map.We shall think of a planar map as being embedded in the plane instead ofthe sphere. A major portion of this thesis is concerned with maps embeddedin the half-plane, that is in R× R+ (more in Chapter 2).Definition 1.1.1 is more topological in nature and there exist other equiv-alent ways to define maps. We refer the interested reader to [78] for a morefundamental approach. We also mention here that maps on non-orientablesurfaces have also been studied (see [26, 55, 78]), but such maps are not thefocus of this thesis and hence is not part of Definition 1.1.1.For infinite graphs, there are certain extra assumptions about the em-bedding. A map is one-ended if the complement of any finite subset ofthe map has precisely one infinite connected component. A map is locallyfinite if all the vertex degrees are finite. We shall only consider maps whichare locally finite and one-ended in this thesis. We shall also mark oneoriented edge of the map as the root edge. Sometimes in the literature,11.1. DefinitionsFigure 1.1: Left: A map with a boundary. Right: A map with asimple boundary. The boundary edges and vertices are marked red.maps are defined to be face rooted or corner rooted (see [13, 34]). However,we shall stick to edge rooted maps in this thesis.The connected components of the complement of the embedding arecalled faces. So as per Definition 1.1.1, the faces are homeomorphic to discs.Further, the graphs can have multiple edges or self-loops. The number ofedges incident to a face is called the degree of a face. A face of degree 3 iscalled a triangle, that of degree 4 a quadrangle and so on. A map is calleda triangulation if all its faces are triangles except possibly a face whichis identified to be external to the map. A triangulation with no externalface will be referred to as the triangulation of the surface. The collectionof edges incident to the external face is called the boundary of the map(see Figure 1.1). Notice that the boundary of a map a priori might notbe a simple cycle. If a map has m boundary vertices, n non-boundaryvertices and the boundary forms a simple cycle then we shall refer to it asa triangulation of an m-gon with n internal vertices.For a finite map M , V (M), E(M) and F (M) will denote the set of itsvertices, edges and faces. For any finite set S, let |S| denote its cardinality.For a finite map M with an underlying surface of genus g, recall Euler’sformula for orientable surfaces:|V (M)| − |E(M)|+ |F (M)| = 2− 2gThis formula can impose certain restriction of the genus on which a certainclass of maps can be embedded. For example, if we consider a triangulationwith n faces on a genus g surface, Euler’s formula gives that the maximalgenus surface on which it can be embedded is bn/4c (notice that for a trian-gulation T , we have 3|F (T )| = 2|E(T )|). Similarly for a map with n edgesand one face, the maximal genus possible is bn/2c.One can view suitable classes of maps as metric spaces with a suitablemetric on them. There are two possible ways to do this. The first one is21.1. Definitionsthe local metric introduced by Benjamini and Schramm ([22]) which roughlysays that two maps are close if the combinatorial balls of radius r are iso-morphic for large r. The second is the Gromov-Hausdorff distance whichviews two finite maps as compact metric spaces induced by their appropri-ately rescaled combinatorial graph distances and the distance between themaps is computed by computing the Hausdorff distance between two iso-metric embeddings of the maps in a common metric space and then takinginfimum over all such embeddings. After adding a suitable topology, we canalso define probability measures on such measure spaces and consider weaklimits of such measures as the class of maps we consider becomes large. Verybroadly speaking, proving existence of such limits and studying their geo-metric properties have been a major theme of work in this field. The weaklimit in the local metric is called the local limit and that of the properlyrescaled metric in the Gromov-Hausdorff topology is called the scaling limit.One of the simplest examples of scaling limits is perhaps the classical factthat the simple random walk in Z when properly rescaled converges to onedimensional standard Brownian motion. To be more precise let {Xn}n≥1be the simple random walk in Z. Then 1√n(Xbntc)0≤t≤1 converges weakly to(Bt)0≤t≤1 in the appropriate topology where Bt is the standard Brownianmotion at time t (see [29] for more.) Scaling limits will not be the focus ofthis thesis but still let us mention that proving existence of scaling limits fornatural models of random graphs is an area of extensive ongoing research.The theme of such works is that the graphs are viewed as properly rescaledmetric spaces and the goal is to find a continuum object as a limit of suchmetric spaces in the above mentioned Gromov-Hausdorff topology. For ex-ample, the scaling limits of Erdos-Renyi random graphs are obtained in [1],the random tree in [4], minimal spanning trees in [2], random dissections in[40] etc. For random triangulations and 2p-angulations for p ≥ 1, scaling lim-its are obtained by LeGall ([70]) and the limiting object (which is universalfor all these class of maps and is conjectured to hold for odd p-angulationsas well) is called the Brownian map which forms the continuum analogueof the uniform infinite maps. Independently, Miermont in [76] has obtainedthe scaling limit results for quadrangulations using a different approach. Afine exposition about the scaling limits of random maps can be found in [75].Many basic properties of the Brownian map are still unknown and this isan area of growing interest and extensive research.31.2. The local topology1.2 The local topologyLet G∗ denote the space of all connected, locally finite rooted graphs. ThenG∗ is endowed with the local topology, where two graphs are close if largeballs around their corresponding roots are isomorphic. The local topologyis generated by the following metric: for G,G′ ∈ G∗, we defined(G,G′) = (R+ 1)−1 where R = sup{r : Br(G) ∼= Br(G′)}.Here Br denotes the ball of radius r around the corresponding roots, and ∼=denotes isomorphism of rooted maps. This metric on G∗ is non-Archimedian.Finite graphs are isolated points, and infinite graphs are the accumulationpoints. Sometimes e−R is used instead of (R + 1)−1 in the above definitionof the metric, but the actual metric is of little importance and we mainlycare about the topology induced by it.The local topology on maps induces a weak topology on measures on G∗.One such natural choice of measures is the Benjamini-Schramm limit of asequence of finite planar graphs [22], which is the weak limit of the laws ofthese graphs with a uniformly chosen root edge. The work of Aldous andSteele in the context of trees in [5] also deserves mention here. Let us givea few examples.• The n×n triangular (or square) lattice with the root chosen uniformlyconverges to the infinite triangular (or square) lattice. This followsfrom the observation that the cardinality of the set of boundary edgesis small compared to the total volume. Hence with high probability,the root is not chosen from an edge close to the boundary in the finitegraphs• The binary tree of level n with the root chosen uniformly convergesto what is popularly known as the canopy tree. This is because withhigh probability, the root is near the highest level rather than at thelower levels (see Figure 1.2).• The Erdos-Renyi random graph with n vertices where two vertices areconnected by an edge independently with probability c/n converges tothe Galton-Watson tree with a Poisson(c) offspring distribution exceptthe root vertex which has size biased Poisson(c) offspring distribution.Notice that the degree of the root in the limit is obtained by degreebiasing the limiting degree of a vertex in the Erdos-Renyi graph be-cause we choose the root vertex with probability proportional to itsdegree.41.2. The local topology1/21/41/81/16Geometric(1/2) Galton-WatsontreesFigure 1.2: Left: The critical Galton-Watson tree withGeometric(1/2) offspring distribution conditioned to survive. Right:A canopy tree which is the local limit of binary trees cut off at thenth level. The numbers beside the vertices represent the probabilityof them being the root. For example the probability of the leftmostvertex in the bottom level has probability 1/2 of being the root andso on.• Consider a uniform rooted (embedded) tree with n edges (see [69] forthe precise formalism). The local limit as n→∞ is an object knownas the critical Galton-Watson tree conditioned to survive withGeometric(1/2) offspring distribution (see [63]). The degree of theroot is given by a size biased Geometric (1/2) offspring distribution.It has an infinite spine with critical Galton-Watson trees attached onboth sides (see Figure 1.2)We can endow any class of planar maps with the above local topol-ogy (with the graph isomorphism replaced by map isomorphism). Physicistswere interested in random surfaces and their geometry. More about thisbackground motivation is in Section 1.3.Let Tn be uniformly distributed among all triangulations of the spherewith n faces. Then the weak limit of Tn as n→∞ forms a natural candidatefor a discretized version of random surfaces. Its existence was proved byAngel and Schramm.Theorem 1.2.1 (Angel, Schramm [13]). The weak limit of Tn exists. Thelimiting object is an infinite, one-ended and planar triangulation.Notice that the completion of the space of all triangulations of the spherewith respect to the local topology a priori might not be one-ended: a limitof a sequence of finite triangulations on the sphere may contain more thanone accumulation points. However, Theorem 1.2.1 ensures that the limitingmeasure is supported on one-ended infinite triangulations of the sphere. Thelimit is popularly known as the uniform infinite planar triangulation51.3. The big pictureor the UIPT in short. Similarly, existence of the local limit for quadrangu-lations (called UIPQ) was proved by Krikun (see [65]).Frequently we shall encounter measures of the following type. Let Tm,nbe a uniform distribution on triangulations of an m-gon with n internalvertices. Then it is known thatTm,n −−−→n→∞Tm,∞ −−−−→m→∞T∞,∞.The first limit is an infinite triangulation in an m-gon, and the secondlimit is known as the half-plane uniform infinite planar triangulation(HUIPT). The same limits exist for quadrangulations (yielding the half-plane UIPQ, see e.g. [44]) and many other classes of maps. These half-planemaps have the interesting property that if we remove any simply connectedsub-map Q connected to the boundary, the distribution of the remainingmap after removing Q is the same as the original distribution of the halfplane map we started with. We call this property domain Markov anddefine this precisely in Chapter 2. The name is chosen in analogy with therelated conformal domain Markov property that Schramm-Loewner evolu-tion (SLE) curves have (a property which was central to the discovery ofSLE [85]). This property appears in some forms also in the physics literature[6], and more recently played a central role in several works on planar maps[7, 10, 20].1.3 The big pictureThe motivation for studying random planar maps comes from several direc-tions. This section is devoted to give a rough sketch of the bigger picture inthe background and the history associated with this area of research.1.3.1 EnumerationEnumeration results of planar maps go back to the work of Tutte in the 60’s.The main aim was to prove the four color theorem and the strategy was toshow that the number of planar maps and the number of four colorablemaps are the same. An array of results in this regard (see [31, 87–89])were obtained by solving functional equations involving generating func-tions. Generalization to maps on general surfaces were also obtained (see[54, 55]). We roughly present below the general idea for this technique ofenumeration. Suppose we wish to enumerate the number of triangulations61.3. The big picturewith n faces and an external face of degree m edges rooted on the boundary.We define the following generating function:F (x, y) =∑x#facesy#edges on the boundaryNow the triangle incident to the root edge has the third vertex (the ver-tex which do not belong to the root edge) either on the boundary or thethird vertex is an internal vertex of the triangulation. If the third vertexis a boundary vertex, it breaks up the triangulation into two independenttriangulations with a smaller number of faces and smaller boundary sizes.Similarly, if the third vertex is an internal vertex, then the remaining trian-gulation has one less face and one more boundary edge. This gives us therequired functional equation for F (x, y). Solving such an equation requiresa technique called the quadratic method (see [87–89] for details). The fol-lowing proposition is an example of many results of similar flavor obtainedusing this technique.Proposition 1.3.1. For n,m ≥ 0, the number of rooted triangulations of adisc with m+ 2 boundary vertices and n internal vertices isφn,m+2 =2n+1(2m+ 1)!(2m+ 3n)!m!2n!(2m+ 2n+ 2)! (1.3.1)Note that this formula is for triangulations with multiple edges allowed,but no self-loops (type II in the notations of [13]). The case of φ0,2 requiresspecial attention. A triangulation of a 2-gon must have at least one internalvertex so there are no triangulations with n = 0, yet the above formula givesφ0,2 = 1. This is reconciled by the convention that if a 2-gon has no internalvertices then the two edges are identified, and there are no internal faces.This makes additional sense for the following reason: Frequently a tri-angulation of an m-gon is of interest not on its own, but as part of a largertriangulation. Typically, it may be used to fill an external face of size m ofsome other triangulation by gluing it along the boundary. When the exter-nal face is a 2-gon, there is a further possibility of filling the hole by gluingthe two edges to each other with no additional vertices. Setting φ0,2 = 1takes this possibility into account.Using Stirling’s formula, the asymptotics of φn,m as n → ∞ are easilyfound to beφn,m ∼ Cmn−5/2(272)n. (1.3.2)71.3. The big picture−10 −11 10−10 −11 10∂ ∂−2Figure 1.3: An illustration of the Schaeffer bijection. Left: Figureshows the way we move along the contour of the tree with 6 verticesstarting from the root vertex. This also introduces a natural contourorder between the vertices. Middle: Observe that the minimal labelin the tree is −1. We add a new vertex ∂ with label −2. For eachvertex encountered while moving around the contour, draw an arcbetween the vertex and the next vertex in the contour order withlabel one less. Draw an arc between vertices with label −1 and thevertex ∂. Orient the edge between the root vertex and ∂ in oneof the two ways. Right: The rooted quadrangulation, pointed at ∂with 7 vertices obtained by erasing the tree.where Cm is given byCm+2 =√3(2m+ 1)!4√pim!2(94)m∼ Cm1/29m.The asymptotics in the above equation is obtained by using Stirling’s for-mula. The power terms n−5/2 and m1/2 are common to many classes ofplanar structures. They arise from the common observation that a cyclepartitions the plane into two parts (Jordan’s curve Theorem) and that thetwo parts may generally be triangulated (or for other classes, filled) inde-pendently of each other. Similar enumeration results for other classes ofplanar maps were also obtained.Later, bijective techniques were introduced due to Schaeffer et al (see[37, 84]) to find different interpretations of enumeration formulas like Propo-sition 1.3.1. The main theme of the bijections is to find a correspondencebetween classes of planar maps and tree-like objects maybe with some ad-ditional decorations on the vertices and edges. For example, the simplest ofsuch results is a bijection initially worked out by Cori and Vauquelin ([37])and developed later by Schaeffer ([84]). The bijection popularly used isthat between rooted quadrangulations with n faces and a distinguished ver-tex (sometimes called a rooted pointed quadrangulation) and labelled rooted81.3. The big picturetrees with n edges. A labelled tree is a rooted tree where each vertex isassigned a label such that the absolute value of the difference between thelabels in two adjacent vertices is at most 1 and the root vertex is assignedlabel 0. The prescription to obtain the quadrangulation from the tree isillustrated in Figure 1.3.These beautiful bijections provide us with a method to analyze planarmaps via analyzing the corresponding labelled trees. For example the bijec-tion illustrated in Figure 1.3 immediately gives that the number of rootedquadrangulations of the sphere with n faces is given by2(n+ 2)3n(n+ 1)(2nn)where the factor(2nn)1n+1 counts the number of trees with n edges, 3ncounts the number of labellings, the factor (n+2)−1 comes from the fact thatthe quadrangulation can be pointed in one of its n+2 vertices and the factor2 comes from orienting the root in one of the two directions. Furthermore,the labels on the vertices are the distances between the vertices and thepointed vertex up to an added constant. This enables us to analyze thedistances in the map by looking at the labelling function. See [75] for acomprehensive survey of this approach.1.3.2 UniversalityThe polynomial correction term n−5/2 in the asymptotic formula in (1.3.2)also appears if we replace triangulations by quadrangulations or any rea-sonable class of maps. This is no coincidence and suggests that the largescale properties of random maps are universal and do not depend upon thelocal properties. The results in [70, 76] which depicts the universality of theBrownian Map illustrates this fact. This sort of universality results and con-jectures are similar flavor to convergence of random walk to the Brownianmotion for a wide class of walks.Simple random walk is also conjectured to behave similarly in the locallimit of random maps. Here is a conjecture which has been open for quitesome time. Let X0, X1, . . . be the simple random walk on the UIPT orUIPQ.Conjecture 1.3.2. Show that almost surely, the graph distance between Xnand X0 grows like n1/4 up to poly-logarithmic fluctuations.91.3. The big pictureNote that the exponent of 1/4 is not yet proved and the best known upperbound is 1/3 for the UIPQ obtained in [20]. Recently, the work of Gurel-Gurevich and Nachmias (see [59]) shows that if we consider a sequence offinite planar graphs (might be random) where the root is chosen uniformly,and if the distribution of the root vertex has exponential tail, then the locallimit is recurrent. Previously, the same result was proved for bounded degreegraphs by Benjamini and Schramm in [22].If we enter the world of conformal embeddings of random maps thenthings are much less clear. A finite triangulation can be embedded in thesphere in many ways such that the embedding is conformally invariant.One popular way is to use the circle packing theory. For precise questions,we refer to [18], Section 3.2. Very recently, some information about theconformal structure of the boundary of the half planar maps have beenobtained in [38]. The very recent work in [77] also deserves mention here.1.3.3 Quantum gravityThe motivation to understand random surfaces, keeping aside the aestheticinterests, also comes from the physics literature. Developing the theory oftwo dimensional quantum gravity requires one to extend the Feynman pathintegrals to integrals over surfaces. This motivates the study of randomsurfaces and allows one to wonder: what is the geometry of a large typicalsurface? If we look into the discrete world of lattices, there is a priori noparticular reason to prefer the Z2 lattice over say the triangular lattice orthe hyperbolic plane.One way to make sense of the above question is to consider uniformmeasures on all possible finite surfaces and then take weak limits of suchmeasures. For example, all possible triangulations of a surface can be viewedas a discretized version of a 2-dimensional manifold and the local limit ofsuch objects can be viewed as a discretized model of an infinite randomsurface. Hence, Theorem 1.2.1 suggests that the UIPT or UIPQ are naturalcandidates for such a model.One can consider many models of statistical mechanics (for example theIsing model or the Bernoulli percolation model) on a random surface. Aconnection between dimensions of random fractal objects (for example thecritical Bernoulli percolation cluster or the critical Ising model clusters) inthe fixed surface (for example, Z2) and a random surface has been conjec-tured in [64]. The formula is∆−∆0 =∆(1−∆)k + 2101.4. Percolation on random mapswhere 2 − 2∆ is the dimension of the random fractal object in a randomsurface and 2 − 2∆0 is the dimension of the random fractal object in thedeterministic surface. The parameter k depends upon the model of statisti-cal mechanics in question. Some progress in this area has been made usingthe multiplicative cascades (see [23]) and the Gaussian free field (see [47]).On models of random surfaces such as the UIPQ, such a formula has beenverified for pioneer points of random walk (see [20]) and that of the Bernoullipercolation critical cluster (see [10]). However, much is not known in thisarea as of now.1.4 Percolation on random mapsBernoulli percolation is one of the simplest models of statistical mechanicsthat one can consider. This is the main motivation behind understanding be-havior of percolation clusters on random maps. Recall that the Bernoulli(p)site percolation model on a graph is defined as follows: for every vertex inthe graph is colored black with probability p or white with probability 1−p.We consider the percolation model on random graphs and we are interestedin quenched statements about the percolation model. This means we areinterested in statements about the percolation clusters conditioned on themap. As usual, the critical percolation probability pc is the infimum over psuch that for almost all triangulations there exists an infinite cluster withprobability 1 for Bernoulli(p) site percolation on the triangulation.Recall that the dual graph of a planar map is a graph with a vertexcorresponding to each face and two vertices are joined by an edge if thecorresponding faces in the primal graph have a common adjacent edge (seeFigure 1.4). Site percolation on triangulations are nicer to analyze in thesense that we can consider the interface between two clusters. The interfaceis a path in the dual graph, that uses exactly the dual edges of edges withdifferently colored endpoints. Since faces are triangles, dual vertices havedegree 3, and either two or none of the three dual edges are part of an in-terface. Thus the interfaces can not intersect each other. In a triangulation,the interfaces form cycles, simple paths or infinite lines. The simple pathsmust start at the boundary and end at the boundary.Theorem 1.4.1 (Angel [7, 8]). Almost surely, the critical site percolationprobability on the UIPT is 1/2. Almost surely, the critical site percolationprobability for the half plane UIPT is also 1/2.Thus, the site percolation probability matches with that of the triangulargrid. The structure of the critical percolation cluster around the root vertex111.5. Unicellular mapsFigure 1.4: An illustration of an interface between a black and awhite cluster for percolation in a half planar triangulation.for half plane models as well as bond and face percolation models on thehalf plane UIPT is studied in [10]. The scaling limit of the critical interfacein the full plane UIPT is studied in [41]. Some similar results for uniforminfinite planar maps were obtained in [74].1.5 Unicellular mapsUnicellular maps are maps with a single face. In genus 0, maps with asingle face are nothing but plane embedded trees. So unicellular maps canbe thought of as a generalization of plane trees in higher genera. The set ofall unicellular maps of genus g and n edges will be denoted by Ug,n.In this thesis, random permutations will play a crucial role in Chap-ter 4. So there will be two notions of cycles floating around: one for cycledecomposition of permutations and the other for maps and graphs. To avoidconfusion, we shall refer to a cycle in the context of graphs as a circuit.A circuit in a planar map is a subset of its vertices and edges whose imageunder the embedding is topologically a closed loop. A circuit is called con-tractible if its image under the embedding on the surface can be contractedto a point and not contractible otherwise. Recall that since we wanted thecomplement of the embedding to be disjoint union of discs, in higher genusthe underlying graph of unicellular maps must contain circuits. Also noticethat every circuit in a unicellular map is non-contractible.There are alternate equivalent ways of defining an unicellular map. Oneway is to take a polygon with 2n edges and then glue together pairs ofedges in the boundary of the polygon (to ensure orientability, one must gluetogether edges in the opposite directions in any cyclic orientation of thepolygon.)One can iteratively delete all the leaves of a unicellular map and thenerase the degree 2 vertices as in Figure 1.6 and obtain a unicellular map121.5. Unicellular mapsFigure 1.5: A unicellular map and its underlying graph.Delete leavesiterativelyErase degree 2verticesFigure 1.6: The process of obtaining a scheme of a unicellularmap.with each vertex degree at least 3. Such a map is called the scheme orthe skeleton of the unicellular map. Clearly, the scheme carries all theinformation about the topology of the unicellular map. Thus, a unicellularmap can be decomposed into its scheme and a forest corresponding to everyedge in the scheme (see Figure 1.6).We can explore the contour of a unicellular map in the same way aswe do in a plane tree: we start from any corner, and continue exploringthe corners of the face until we come back to the corner we started with(see Figure 1.7). This gives a cyclic order (called the face order) to thehalf-edges in the unicellular map. However observe that at every vertex,the half edges adjacent to it can be ordered in an anti clockwise mannerwhich we call the vertex order. Notice that for a plane tree, the vertex orderof edges around a vertex always coincides with their face order. However,in a higher genus unicellular map, the face order of edges around a vertexmay not coincide with their vertex order giving rise to intertwinings. Theseintertwinings in some sense carry the information of the underlying topologyof the unicellular maps.131.5. Unicellular mapsFigure 1.7: The way of exploring the face in unicellular map.One can think of starting from a plane tree then iteratively gluing to-gether vertices in the correct fashion so that the number of faces remain 1at any step. Using Euler’s formula it is easy to see that this gluing givesrise to a higher genus unicellular map. Using this heuristic, Chapuy in [33]obtained a recursive formula for the number of unicellular maps of genus gwhich is recursive only in the genus.2g|Ug,n| =g−1∑p=0( n+ 1− 2p2g − 2p+ 1)|Up,n|The idea of iterative gluing can also be used to recover the enumerationformula (see [33])|Ug,n| = Cat(n)122g∑λ∈Ln+1−2g(n+1)(n+ 1)!∏imi!imi, (1.5.1)where Cat(n) = 1n+1(2nn)is the nth Catalan number and the sum is overall the partitions λ of n + 1 of size n + 1 − 2g such that each part has oddnumber of elements and mi is the number of parts with i elements. Theenumeration formula in eq. (1.5.1) is known as the Lehmann-Walsh formula[91].This idea of obtaining a unicellular map of higher genus by gluing to-gether vertices in a lower genus unicellular map was further simplified in [34]and a very simple bijection between unicellular maps and special classes of141.6. Hyperbolic random mapsobjects called C-decorated trees were obtained. This bijection in [34] formsthe main tool for obtaining the results in Chapters 4 and 5.We finish this subsection by mentioning that unicellular maps have ap-peared frequently in the field of combinatorics in the past few decades. Theyare related to representation theory of symmetric group, permutation fac-torization, matrix integrals computation and also the general theory of enu-meration of maps. See the introduction section of [25, 33] for a nice overviewand see [68] for connections to other areas of mathematics and referencestherein.1.6 Hyperbolic random mapsThere has been a growing interest in constructing hyperbolic versions ofthe uniform infinite planar maps. The uniform infinite planar maps areparabolic in the sense that they can be conformally embedded in the fullplane (see [22, 61]). Is there a way to naturally construct a random mapwhich looks more like the hyperbolic plane?One construction of such a possible measure supported on infinite hyper-bolic maps which can be found in [19]. Consider the supercritical Galton-Watson tree and condition it to survive to obtain an infinite tree. Nowfor every edge in the tree, attach independent edge weights uniform on{−1, 0, 1}. Assign label 0 to the root vertex and the label of any vertex vcan be obtained by summing the edge weights along the geodesic joining theroot vertex and v.Notice that there are infinitely many faces in the tree and in every face,the corners can be given a natural order corresponding to exploring thecorners in a clockwise direction similarly as in Figure 1.3. For every cornerc with label l, draw an edge between the vertex corresponding to c andthe first corner in the clockwise order whose associated vertex has labell − 1. Now consider the quadrangulation obtained only by the edges addedbetween vertices in the tree. Such a quadrangulation is named Stochastichyperbolic infinite quadrangulation or SHIQ. The fact that the edgesare non-crossing and the resulting map is a quadrangulation is a consequenceof the results in [36].It is easy to see that the SHIQ is almost surely a locally finite, one endedquadrangulation with exponential volume growth. Many question about theSHIQ remain open, see [19] Section 6.3 for details.A half planar version of hyperbolic triangulations was constructed in[12] which forms the basis of Chapter 2. The geometry of these maps were151.6. Hyperbolic random mapsfurther studied in [82] and it was shown that these maps possess exponentialvolume growth and anchored expansion. Recently in [11], the speed of simplerandom walk and return probabilities are also studied on such maps.Another recent construction of planar hyperbolic triangulation calledstochastic hyperbolic planar triangulation was obtained by Curien in[39]. He obtained a one-parameter family T κ where the parameter κ ∈[0, 2/27) with κ = 2/27 corresponding to the UIPT. These objects are con-structed using some of the ideas in Chapter 2. Results about volume growthand random walk speed are also obtained for these maps in [39]. The naturalquestion that arises from these constructions is to obtain finite approxima-tions for such maps analogous to the uniform infinite planar maps.The idea is to look into random maps in a high genus surface. Gamburdand Makover showed (see [52, 53]) that if we choose a random triangulationwith n faces and no restriction on the genus, typically, the genus is themaximal possible which is bn/4c. The conjecture is that if we restrict to agenus Cn where 0 < C < 1/4, then the local limit obtained is topologicallyplanar and is hyperbolic. The intuition behind such a conjecture is that inhigher genus triangulations, the average degree is higher than 6, which givesrise to negative curvature in the limiting maps, provided the distributionallimit is planar.Conjecture 1.6.1 below appears in this form in [39]. Fix θ ≥ 0 andsuppose we look at Tbθnc,n which is the set of rooted triangulation of genusbθnc and n vertices and let Tbθnc,n be a uniformly picked element from itwith root ρn. Now observe that the degree of the root vertex is continuousin the local topology since we pick the root with probability proportional toits degree. Now if Tbθnc,n converges to T κ thenE((deg(ρn))−1) =16(n+ 2g − 2)|Tbθnc,n|∑t∈Tbθnc,n∑x∈V (t)deg(x) 1deg(x)= n6(n+ 2g − 2) −−−→n→∞16(1 + 2θ) = E(deg(ρκ)−1) (1.6.1)where ρk is the root of T κ.Conjecture 1.6.1. (Benjamini and Curien [39]) For any θ ≥ 0, let κ ∈(0, 2/27] be such that E(deg(ρκ)−1) = (6(1 + 2θ))−1 where ρκ is the root ofT κ. ThenTbθnc,n(d)−−−→n→∞T κOf course, similar conjectures can be coined for quadrangulations orother reasonable classes of planar maps. To prove that the local limit is161.6. Hyperbolic random mapsQn UIPQLTn LT∞Φn Φ∞Figure 1.8: Illustration of the construction of UIPQ in [43].topologically a plane, we have to prove with high probability we do not seenon-contractible cycles near the root.One standard way to attack such a problem is via the bijective techniquesdue to Schaeffer et al. For example, the UIPQ can be constructed using thebijective techniques as illustrated in [43]. Roughly, the idea is as follows:we know that finite quadrangulations Qn with n faces are in bijection Φnwith a uniform labelled tree LTn with n edges. Then one can take theweak limit over n for the trees to easily obtain a uniform infinite labelledtree LT∞. The local limit of a uniformly picked tree with n edges is thecritical Galton-Watson tree conditioned to survive (see Figure 1.2). Thelabel of a vertex v of the uniform infinite labelled tree defined by assigningi.i.d. uniform {−1, 0, 1} edge weights to every edge and then summing theseweights along the (unique) path from the root to v with the root vertexassigned label 0. Now one can obtain a quadrangulation from LT∞ by usinga similar recipe Φ∞ used for the SHIQ: join each corner c with label l to theimmediately next corner in the clockwise contour of the tree with label l−1.Thus we have the commutative diagram in Figure 1.8. Note that the arrowconnecting UIPQ and LT∞ in Figure 1.8 is correct provided the recipe Φ∞is continuous in the local topology which can be seen easily and is provedin [43].One can hope to undertake a similar strategy for the high genus caseas well. There exists a bijection between quadrangulations of genus g andlabelled unicellular maps due to Chapuy, Marcus and Schaeffer (see [35]), butobtaining the local limit of labelled unicellular maps is not so straightforwardas the genus 0 case. As a first step to solve this problem using this approach,we find the local limits of unicellular maps in high genus in Chapter 5. Butit is no longer clear whether the labels are obtained just by adding i.i.d.edge weights as was the situation in the genus 0 case since the presence of171.6. Hyperbolic random mapscycles in unicellular maps makes understanding the distribution of the labelsnon-trivial. Thus these results alone do not suffice and we need new ideasto pursue this apporach.18Chapter 2Classification of half planarmaps1 The primary goal of this work is to classify all probability measures on half-planar maps which are domain Markov, and which additionally satisfy thesimpler condition of translation invariance. As we shall see, these measuresform a natural one (continuous) parameter family of measures.We shall consider many different classes of planar maps in this chapter.We focus on triangulations, where all faces except possibly the external faceare triangles, and on p-angulations where all faces are p-gons (except possiblythe external face). We denote by Hp the class of all infinite, one-ended, half-planar p-angulations. However, it so transpires that Hp is not the best classof maps for studying the domain Markov property, for reasons that will bemade clear later. At the moment, to state our results let us also define H′pto be the subset of Hp of simple maps, where all faces are simple p-gons(meaning that each p-gon consists of p distinct vertices). Note that — asusual in the context of planar maps — multiple edges between vertices areallowed. However, multiple edges between two vertices cannot be part ofany single simple face. We shall use H and H′ to denote generic classes ofhalf-planar maps, and simple half-planar maps, without specifying which.For example, this could also refer to the class of all half-planar maps, ormaps with mixed face valencies.2.1 Translation invariant and domain MarkovmeasuresThe translation operator θ : H → H is the operator translating the rootof a map to the right along the boundary. Formally, θ(M) = M ′ meansthat M and M ′ are the same map, except that the root edge of M ′ is thethe edge immediately to the right of the root edge of M . Note that θ is a1The results in this section are taken from the paper [12] and is joint work with OmerAngel.192.1. Translation invariant and domain Markov measuresQ M M˜Figure 2.1: Left: A finite map Q. Centre: part of a map Mcontaining Q with 2 edges along the boundary. Right: the resultingmap M˜ . The domain Markov property states that M˜ has the samelaw as M .bijection. A measure µ on H is called translation invariant if µ ◦ θ = µ.Abusing language, we will also say that a random map M with law µ istranslation invariant, even though typically moving the root of M yields adifferent (rooted) map.The domain Markov property is more delicate, and may be informallydescribed as follows: if we condition on the event that M contains some finiteconfiguration Q and remove the sub-map Q from M , then the distribution ofthe remaining map is the same as that of the original map (see Figure 2.1).We now make this precise. Let Q be a finite map in an m-gon for somefinite m, and suppose the boundary of Q is simple (i.e. is a simple cyclein the graph of Q), and let 0 < k < m be some integer. Define the eventAQ,k ⊂ H that the map M contains a sub-map which is isomorphic to Q,and which contains the k boundary edges immediately to the right of theroot edge of M , and no other boundary edges or vertices. Moreover, werequire that the root edge of Q corresponds to the edge immediately to theright of the root of M . On this event, we can think of Q as being a subsetof M , and define the map M˜ = M \Q, with the understanding that we keepvertices and edges in Q if they are part of a face not in Q (see Figure 2.1).Note that M˜ is again a half-planar infinite map.Definition 2.1.1. A probability measure µ on H is said to be domainMarkov, if for any finite map Q and k as above, the law of M˜ constructedfrom a sample M of µ conditioned on the event AQ,k is equal to µ.Note that for translation invariant measures, the choice of the k edgesto the right of the root edge is rather arbitrary: any k edges will result inM˜ with the same law. Similarly, we can re-root M˜ at any other determinis-tically chosen edge. Thus it is also possible to consider k edges that includethe root edge, and mark a new edge as the root of M˜ .202.2. Main resultsThis definition is a relatively restrictive form of the domain Markovproperty. There are several other natural definitions, which we shall discussbelow. While some of these definitions are superficially stronger, it turnsout that several of them are equivalent to Definition Main resultsOur main result is a complete classification and description of all probabilitymeasures onH′p which are translation invariant and have the domain Markovproperty.Theorem 2.2.1. Fix p ≥ 3. The set of domain Markov, translation invari-ant probability measures on H′p forms a one parameter family {H(p)α } withα ∈ Ip ⊂ [0, 1). The parameter α is the probability of the event that thep-gon incident to any fixed boundary edge is also incident to p− 2 internalvertices.Moreover, for p = 3, I3 = [0, 1), and for p > 3 we have (α0(p), 1) ⊂ Ipfor some α0(p) < 1.We believe that Ip = [0, 1) for all p although we have been able to provethis fact only for p = 3. We emphasize here that our approach would workfor any p provided we have certain enumeration results. See Section 2.10 formore on this.We shall normally omit the superscript (p), as p is thought of as any fixedinteger. The measures H(p)α are all mixing with respect to the translationθ and in particular are ergodic. This actually follows from a much moregeneral proposition which is well known among experts for the standardhalf planar random maps, but we could not locate a reference. We includeit here for future reference.Proposition 2.2.2. Let µ be domain Markov and translation invariant onH. Then the translation operator is mixing on (H, µ), and in particular isergodic.Proof. Let Q,Q′ and AQ,k, AQ′,k′ be as in Definition 2.1.1. Since events ofthe form AQ,k are simple events in the local topology (recall discussion inSection 1.2), it suffices to prove thatµ(AQ,k ∩ θn(AQ′,k′))→ µ(AQ,k)µ(AQ′,k′)as n → ∞ where θn is the n-fold composition of the operator θ. However,since on AQ,k the remaining map M˜ = M \ Q has the same law as M ,212.2. Main resultsand since θn(AQ′,k′) is just θn′(AQ′,k′) in M˜ , for some n′, we find fromthe domain Markov property that for large enough integer n, the equalityµ(AQ,k ∩ θn(AQ′,k′)) = µ(AQ,k)µ(AQ′,k′) holds.An application of Proposition 2.2.2 shows that the measures in the set{H(p)α : α ∈ I} are all singular with respect to each other. This is becausethe density of the edges on the boundary for which the p-gon containing itis incident to p− 2 internal vertices is precisely α by translation invariance.Note that the domain Markov property is not preserved by convex combi-nations of measures, so the measures Hα are not merely the extremal pointsin the set of domain Markov measures.Note also that the case α = 1 is excluded. It is possible to take a limitα→ 1, and in a suitable topology we even get a deterministic map. However,this map is not locally finite and so this can only hold in a topology strictlyweaker than the local topology on rooted graphs. Indeed, this map is theplane dual of a tree with one vertex of infinite degree (corresponding tothe external face) and all other vertices of degree p. As this case is ratherdegenerate we shall not go into any further details.In the case of triangulations we get a more explicit description of themeasures H(3)α , which we use in a future paper [82] to analyze their geometry.This can be done more easily for triangulations because of readily availableand very explicit enumeration results. We believe deriving similar explicitdescriptions for other p-angulations, at least for even p is possible with amore careful treatment of the associated generating functions, but leave thisfor future work. This deserves some comment, since in most works on planarmaps the case of quadrangulations q = 4 yields the most elegant enumerativeresults. The reason the present work differs is the aforementioned necessityof working with simple maps. In the case of triangulations this precludeshaving any self loops, but any triangle with no self loop is simple, so thereis no other requirement. For any larger p (including 4), the simplicity doesimpose further conditions. For example, a quadrangulation may contain aface consisting of two double edges.We remark also that forbidding multiple edges in maps does not leadto any interesting domain Markov measures. The reason is that in a finitemap Q it is possible that there exists an edge between any two boundaryvertices. Thus on the event AQ,k, it is impossible that M˜ contains any edgebetween boundary edges. This reduces one to the degenerate case of α = 1,which is not a locally finite graph and hence excluded.Our second main result is concerned with limits of uniform measures onfinite maps. Let µm,n be the uniform measure on all simple triangulations222.2. Main resultsof an m-gon containing n internal (non-boundary) vertices (or equivalently,2n+m−2 faces, excluding the external face). Recall we assume that the rootedge is one of the boundary edges. The limits as n→∞ of µm,n w.r.t. thelocal topology on rooted graphs (formally defined in Section 1.2) have beenstudied in [13], and lead to the well-known UIPT. Similar limits exist forother classes of planar maps, see e.g. [65] for the case of quadrangulations. Itis possible to take a second limit as m→∞, and the result is the half-planeUIPT measure (see also [44] for the case of quadrangulations). A secondmotivation for the present work is to identify other possible accumulationpoints of µm,n. These measures would be the limits as m,n → ∞ jointlywith a suitable relation between them.Theorem 2.2.3. Consider sequences of non-negative integers ml and nlsuch that ml, nl → ∞, and ml/nl → a for some a ∈ [0,∞]. Then µml,nlconverges weakly to H(3)α where α = 22a+3 .The main thing to note is that the limiting measure does not depend onthe sequences {ml, nl}, except through the limit of ml/nl. A special caseis the measure H2/3 which correspond to the half-planar UIPT measure.Note that in this case, a = 0, that is the number of internal vertices growsfaster than the boundary. Note that the only requirement to get this limitis ml = o(nl). This extends the definition of the half-planar UIPT, wherewe first took the limit as nl →∞ and only then let ml →∞.The other extreme case α = 0 (or a =∞) is also of special interest. Tolook into this case it is useful to consider the dual map. Recall that thedual map M∗ of a planar map M is the map with a vertex correspondingto each face of M and an edge joining two colours faces (that is faces whichshare at least an edge), or more precisely a dual edge crossing every edgeof M . Note that for a half-planar map M , there will be a vertex of infinitedegree corresponding to the face of infinite degree. All other vertices shallhave a finite degree (p in the case of p-angulations). To fit into the settingof locally finite planar maps, we can simply delete this one vertex, thougha nicer modification is to break it up instead into infinitely many verticesof degree 1, so that the degrees of all other vertices are not changed. Forhalf planar triangulations this gives a locally finite map which is 3-regularexcept for an infinite set of degree 1 vertices, each of which corresponds toa boundary edge. We can similarly define the duals of triangulations of anm−gon, where each vertex is of degree 3 except for m degree 1 vertices.For a triangulation of an m−gon with no internal vertices (n = 0), thedual is a 3 regular tree with m leaves. Let T be the critical Galton-Watsontree where a vertex has 0 or 2 offspring with probability 1/2 each. We add a232.3. Other approaches to the domain Markov propertyleaf to the root vertex, so that all internal vertices of T have degree 3. Thenthe law of M∗ under µm,0 is exactly T conditioned to have m leaves. Hence,this measure has a weak limit known as the critical Galton-Watson treeconditioned to survive (see Section 1.2). This is the law of the dual map M∗under H0. Observe that in H0, α = 0, hence the probability that the triangleincident to any boundary edge has the third vertex also on the boundary is1. As before, note that the only condition on ml, nl in Theorem 2.2.3 to getthis limiting measure is that nl = o(ml). For p > 3 the measure H(p)0 has asimilar description using trees with p− 1 or 0 offspring.Note that Theorem 2.2.3 gives finite approximations of Hα for α ∈[0, 2/3], so it is natural to ask for finite approximations to Hα for α ∈(2/3, 1)? In this regime, the maps behave differently than those in theregime α < 2/3 or α = 2/3. Maps with law H(3)α are hyperbolic in nature,and for example have exponential growth (we elaborate on the difference inSection 2.8 and investigate this further in [82]). Following the discussionin Section 1.6, we make the following conjecture similar in lines to Conjec-ture 1.6.1:Conjecture 2.2.4. Let Tnl,gl,pl be a uniformly picked triangulation of genusgl, nl vertices and pl boundary vertices rooted at the boundary. Also assumegl/nl → θ for some θ ≥ 0 and pl = o(nl). Then Tnl,gl,pl converges weaklyto Hα where α ≥ 2/3 and is only a function of θ. Further if θ = 0 thenα = 2/3.As indicated in Section 2.13, a similar phase transition is expected forp-angulations as well. Thus, we expect a similar conjecture about finiteapproximation to hold for any p, and not only triangulations.Organization We prove the classification theorem for triangulations inSections 2.6 and 2.7 and for p-angulations in Section 2.10 and also discussthe variation of maps with non-simple faces. In Section 2.12 we examinelimits of uniform measures on finite maps, and prove Theorem Other approaches to the domain MarkovpropertyIn this section we discuss alternative possible definitions of the domainMarkov property, and their relation to Definition 2.1.1. The common theme242.3. Other approaches to the domain Markov propertyFigure 2.2: Possibilities when removing a sub-map Q connectedto the boundary. The red part is CM which is identified with CQ.Left: Q consists of a single triangle. Right: Q consists of twofaces in a general map. The shaded areas are the holes — finitecomponents of the complement of Q.is that a map M is conditioned to contain a certain finite sub-map Q, con-nected to the boundary at specified locations. We then remove Q to get anew map M˜ . The difficulty arises because it is possible in general for M˜to contain several connected components. See Figure 2.2 for some ways inwhich this could happen, even when the map Q consists of a single face.To make this precise, we first introduce some topological notions. Asub-map of a planar map M is a subset of the faces of M along with theedges and vertices contained in them. We shall consider a map as a subsetof the sphere on which it is embedded.Definition 2.3.1. A sub-map of a planar map is said to be connected ifit is connected as a subset of the sphere. A connected sub-map E of a halfplanar map M is said to be simply connected if its union with the externalface of M is a simply connected set in the sphere.Let Q denote a finite planar map, and let some (but at least one) of itsfaces be marked as external, and the rest as internal. We assume that theinternal faces of Q are a connected set in the dual graph Q∗. One of theexternal faces of Q is singled out, and a non-empty subset CQ containingat least one edge of the boundary of that external face is marked (in placeof the k edges we had before). Note that CQ need not be a single segmentnow. Fix also along the boundary of M a set CM of the same size as CQ,consisting of segments of the same length as those of CQ and in the sameorder. We consider the eventAQ = {Q ⊂M,∂M ∩ ∂Q = CM},that Q is a sub-map of M , with CQ corresponding to CM . Figure 2.2 showsan example of this where Q has a single face.252.3. Other approaches to the domain Markov propertyOn the event AQ, the complement M \ Q consists of one componentwith infinite boundary in the special external face of Q, and a number ofcomponents with finite boundary, one in each additional external face of Q.Let us refer to the components with finite boundary sizes as holes. Notethat because M is assumed to be one-ended, the component with infiniteboundary size, which is denoted by M˜ is the only infinite component ofM \ Q. All versions of the domain Markov property for a measure µ statethatconditioned on AQ, the infinite component of M \Q has law µ.However, there are several possible assumptions about the distribution ofthe components of M \Q in the holes. We list some of these below.1. No additional information is given about the distribution of the finitecomponents.2. The finite components are independent of the distribution of the infi-nite component.3. The finite components are independent of the distribution of the infi-nite component and of each other.4. The law of the finite components depends only on the sizes of theirrespective boundaries (i.e. two maps Q with holes of the same size giverise to the same joint distribution for the finite components).It may seem at first that these are all stronger than Definition 2.1.1,since our definition of the domain Markov property only applies if Q issimply connected, in which case there are no finite components to M \ Q.This turns out to be misleading. Consider any Q as above, and condition onthe finite components of M \ Q. Together with Q these form some simplyconnected map Q¯ to which we may apply Definition 2.1.1. Thus for any setof finite maps that fill the holes of Q, M˜ has law µ. Since the conditionaldistribution of M˜ does not depend on our choice for the finite components,the finite components are independent of M˜ . Thus options 1 and 2 are bothequivalent to Definition 2.1.1, and the simple-connectivity condition for Qmay be dropped.In the case of p-angulations with simple faces, we have a complete clas-sification of domain Markov measures. Along the proof, it will become clearthat those in fact also satisfy the stronger forms 3 and 4 of the domainMarkov property. This shows that for simple faced maps, every definitionof the domain Markov property gives the same set of measures. If we allownon-simple faces, however, then different choices might yield smaller classes.262.4. PeelingFor example, if a non-simple face surrounds two finite components of themap, then under the domain Markov property as defined above, the partsof the map inside these components need not be independent of each other.2.4 PeelingLet us briefly describe the concept of peeling which has its roots in thephysics literature [6, 92], and was used in the present form in [7]. It is auseful tool for analyzing planar maps, see e.g. applications to percolationand random walks on planar maps in [8, 10, 20]. While there is a versionof this in full planar maps, it takes its most elegant form in the half planecase.Consider a probability measure µ supported on a subset of H and con-sider a sample M from this measure. The peeling process constructs agrowing sequence of finite simply-connected sub-maps (Pi) in M with com-plements Mi = M \Pi as follows. (The complement of a sub-map P containsevery face not in P and every edge and vertex incident to them.) InitiallyP0 = ∅ and M0 = M . Pick an edge ai in the boundary of Mi. Next, removefrom Mi the face incident on ai, as well as all finite components of the com-plement. This leaves a single infinite component Mi+1 = M˜i, and we setPi+1 = M \Mi+1.If µ is domain Markov and the choice of ai depends only on Pi andan independent source of randomness, but not on Mi, then the domainMarkov property implies by induction that Mn has law µ for every n, andmoreover, Mn is independent of Pn. We will see that this leads to yet anotherinteresting viewpoint on the domain Markov property.In general, it need not be the case that ⋃Pi = M (for example, if thedistance from the peeling edge ai to the root grows very quickly). However,there are choices of edges ai for which we do have⋃Pi = M a.s. One wayof achieving this is to pick ai to be the edge of ∂Mi nearest to the root of Min the sub-map Mi, taking e.g. the left-most in case of ties. Note that thischoice of ai only depends on Pi and this strategy will exhaust any locallyfinite map M .Let Qi = Mi−1 \Mi = Pi \ Pi−1 for i ≥ 1. This is the finite, simplyconnected map that is removed from M at step i. We also mark Qi withinformation on its intersection with the boundary of Mi−1 and the peelingedge ai−1. This allows us to reconstruct Pi by gluing Q1, . . . , Qi. In thisway, the peeling procedure encodes an infinite half planar map by an infinitesequence (Qi) of marked finite maps. If the set of possible finite maps is272.5. Preliminariesdenoted by S, then we have a bijection Φ : H → SN. It is straightforwardto see that this bijection is even a homeomorphism, where H is endowedwith the local topology on rooted graphs (see Section 1.2), and SN with theproduct topology (based on the trivial topology on S).Now, if µ is a domain Markov measure on H, then the pull-back mea-sure µ∗ = µ ◦Φ−1 on SN is an i.i.d. product measure, since the maps Mi allhave the same law, and each is independent of all the Qjs for j < i. How-ever, translation invariance of the original measure does not have a simpledescription in this encoding.2.5 Preliminaries2.5.1 Boltzmann distributionWe will also sometimes be interested in triangulations of discs where thenumber of internal vertices is not fixed, but is also random. The followingmeasure is of particular interest:Definition 2.5.1. The Boltzmann distribution on rooted triangulations ofan m-gon with weight q ≤ 227 , is the probability measure on the set of finitetriangulations with a finite simple boundary that assigns weight qn/Zm(q) toeach rooted triangulation of the m-gon having n internal vertices, whereZm(q) =∑nφn,mqn.where φn,m is given by eq. (1.3.1). From the asymptotics of φ as n→∞we see that Zm(q) converges for any q ≤ 227 and for no larger q. The precisevalue of the partition function will be useful, and we record it here:Proposition 2.5.2. If q = θ(1− 2θ)2 with θ ∈ [0, 1/6], thenZm+2(q) =((1− 6θ)(m+ 1) + 1) (2m)!m!(m+ 2)!(1− 2θ)−(2m+2).In particular, at the critical point q = 2/27 we have θ = 1/6 and Z takesthe valuesZm+2 = Zm+2( 227)= (2m)!m!(m+ 2)!(94)m+1.The proof can be found as intermediate steps in the derivation of φn,m in[56]. The above form may be deduced after a suitable reparametrization ofthe form given there.282.6. Half planar triangulationsFigure 2.3: Basic building blocks for triangulations. Left: theevent Aα. Centre and right: the two events of type Aβ.2.6 Half planar triangulationsFor the sake of clarity, we begin by proving the special case p = 3 of The-orem 2.2.1 of half planar triangulations. In the case of triangulations, thenumber of simple maps and corresponding generating functions are knownexplicitly, making certain computations simpler. Somewhat surprisingly, thecase of quadrangulations is more complex here, and the generating functionis not explicitly known. Apart from the lack of explicit formulae, the caseof general p presents a number of additional difficulties, and is treated inSection 2.10.Theorem 2.6.1. All translation invariant, domain Markov probability mea-sures on H′3 form a one parameter family of measures Hα for α ∈ [0, 1).Moreover, in Hα the probability that the triangle containing any given bound-ary edge is incident to an internal vertex is α.In what follows, let µ be a measure supported on H′3, that is translationinvariant and satisfies the domain Markov property. We shall first define acertain family of events and show that their measures can be calculated byrepeatedly using the domain Markov property. Let T ∈ H′3 denote a trian-gulation with law µ. Let α be the µ-measure of the event that the triangleincident to a fixed boundary edge e is also incident to an interior vertex (callthis event Aα, see Figure 2.3). The event depends on the boundary edgechosen, but by translation invariance its probability does not depend on thechoice of e. As stated, our main goal is to show that α fully determines themeasure µ.For i ≥ 1 define p(r)i,k (resp. p(l)i,k) to be the µ-measure of the event that thetriangle incident to a fixed boundary edge e of T is also incident to a vertexon the boundary to the right (resp. left) at a distance i along the boundaryfrom the edge e and that this triangle separates k vertices of T that are noton the boundary from infinity. Note that because of translation invariance,these probabilities only depends on i and k and hence we need not specifye in the notation. It is not immediately clear, but we shall see later thatp(l)i,k = p(r)i,k (see Corollary 2.6.4 below). In light of this, we shall later dropthe superscript.292.6. Half planar triangulationsThe case i = 1, k = 0 is of special importance. Since there is no trian-gulation of a 2-gon with no internal vertex, if the triangle containing e isincident to a boundary vertex adjacent to e, then it must contain also theboundary edge next to e. (See also the discussion in Section 2.5.1.) We callsuch an event Aβ, shown in Figure 2.3. By translation invariance, we nowsee that p(r)1,0 = p(l)1,0. We shall denote β = p(r)1,0 = p(l)1,0.In what follows, fix α and β. Of course, not every choice of α and β isassociated with a domain Markov measure, and so there are some constraintson their values. We compute below these constraints, and derive β as anexplicit function of α for any α ∈ [0, 1).Let Q be a finite simply connected triangulation with a simple boundary,and let B ( ∂Q be a marked, nonempty, connected segment in the boundary∂Q. Fix a segment in ∂T of the same length as B, and let AQ be the eventthat Q is isomorphic to a sub-triangulation of T ∈ H′3 with B being mappedto the fixed segment in ∂T , and no other vertex of Q being mapped to ∂T .Let F (Q) be the set of faces of Q, V (Q) the set of vertices of Q (includingthose in ∂Q), and V (B) the set of vertices in B, including the endpoints.Lemma 2.6.2. Let µ be a translation invariant domain Markov measure onH′3. Then for an event AQ as above we haveµ(AQ) = α|V (Q)|−|V (B)|β|F (Q)|−|V (Q)|+|V (B)| (2.6.1)Furthermore, if a measure µ satisfies (2.6.1) for any such Q, then µ istranslation invariant and domain Markov.Remark 2.6.3. |V (Q)| − |V (B)| is the number of vertices of Q not on theboundary of T . This shows that the probability of the event AQ depends onlyon the number of vertices not on the boundary of T and the number of facesof Q, but nothing else.The proof of Lemma 2.6.2 is based on the idea that the events Aα andAβ form basic “building blocks” for triangulations. More precisely, thereexists some ordering of the faces of Q such that if we reveal triangles of Q inthat order and use the domain Markov property, we only encounter eventsof type Aα, Aβ. Moreover, in any such ordering the number of times weencounter the events Aα and Aβ are the same as for any other ordering.Also observe that, for every event of type Aα encountered, we add a newvertex while for every event of type Aβ encountered, we add a new face.Thus the exponent of Aα counts the number of “new” vertices added whilethe exponent of Aβ counts the number of “remaining” faces.302.6. Half planar triangulationsΓ Γ ΓQ′ Q1 Q2 Q1Q2Figure 2.4: Cases in the inductive step in the proof ofLemma 2.6.2.Proof of Lemma 2.6.2. We prove (2.6.1) by induction on |F (Q)|: the num-ber of faces of Q. If |F (Q)| = 1, then Q is a single triangle, and B containseither one edge or two adjacent edges. If it has one edge, then the triangleincident to it must have the third vertex not on the boundary of T . Bydefinition, in this case µ(AQ) = α and we are done since |V (Q)| = 3 and|V (B)| = 2. Similarly, if B contains two edges, then |V (B)| = 3 and AQ isjust the event Aβ, with probability β, consistent with (2.6.1).Next, call the vertices of Q that are not in B new vertices. Suppose|F (Q)| = n, and that we have proved the lemma for all Q′ with |F (Q)| < n.Pick an edge e0 from B (there exists one by hypothesis), and let Γ be theface of Q incident to this edge. There are three options, depending on wherethe third vertex of Γ lies in Q (see Figure 2.4):• the third vertex of Γ is internal in Q,• the third vertex of Γ is in ∂Q \B,• the third vertex of Γ is in B.We treat each of these cases separately.In the first case, we have that Q′ = Q − Γ is also a simply connectedtriangulation, if we let B′ include the remaining edges from B as well as thetwo new edges from Γ, we can apply the induction hypothesis to Q′. By thedomain Markov property, we have thatµ(AQ) = µ(AΓ)µ(AQ|AΓ) = αµ(AQ′).This implies the claimed identity for Q, since Q′ has one less face and oneless new vertex than Q.In the case where the third vertex of Γ is in ∂Q\B, we have a decompo-sition Q = Γ∪Q1∪Q2, where Q1 and Q2 are the two connected componentsof Q\Γ (see Figure 2.4). We define Bi, to contain the edges of B in Qi, andone edge of Γ that is in Qi. We have that |F (Q)| = |F (Q1)|+ |F (Q2)|+ 1,and that the new vertices in Q1 and Q2 except for the third vertex of F (Q)together are the new vertices of Q. By the domain Markov property, con-ditioned on AΓ, the inclusion of Q1 and of Q2 in T are independent events312.6. Half planar triangulationswith corresponding probabilities µ(AQi). Thusµ(AQ) = αµ(AQ1 |AΓ)µ(AQ2 |AΓ)= αµ(AQ1)µ(AQ2) = α|V (Q)|−|V (B)|β|F (Q)|−|V (Q)|+|V (B)|,as claimed.Finally, consider the case that the third vertex of Γ is in B. As in theprevious case, we have a decomposition Q = Γ ∪ Q1 ∪ Q2, where Q1 is thetriangulation separated from infinity by Γ, and Q2 is the part adjacent tothe rest of T (see Figure 2.4.) We let B1 consist of the edges of B in Q1 andlet B2 be the edges of B in Q2 with the additional edge of Γ. We then haveµ(AQ) = µ(AQ1)µ(AQ1∪Γ|AQ1)µ(AQ|AQ1∪Γ).By the induction hypothesis, the first term isα|V (Q1)|−|V (B1)|β|F (Q1)|−|V (Q1)|+|V (B1)|.By the domain Markov property, the second term is just β. Similarly, thethird term is α|V (Q2)|−|V (B2)|β|F (Q2)|−|V (Q2)|+|V (B2)|. As before we have that|F (Q)| = |F (Q1)|+ |F (Q2)|+1, and this time |V (Q)|−|V (B)| = (|V (Q1)|−|V (B1)|) + (|V (Q2)| − |V (B2)|), since the new vertices of Q are the newvertices of Q1 together with the new vertices of Q2. The claim again follows.Note that in the last case it is possible that Q1 is empty, in which caseΓ contains two edges from ∂Q. All formulae above hold in this case with nochange.For the converse, note first that since the events AQ are a basis for thelocal topology on rooted graphs, they uniquely determine the measure µ.Moreover, the measure of the events of the form AQ do not depend on thelocation of the root and so µ is translation invariant. Now observe fromRemark 2.6.3 that the measure of any event of the form AQ only dependson the number of new vertices and the number of faces in Q. Now supposewe remove any simple connected sub-map Q1 from Q. Then the union ofnew vertices in Q1 and Q \Q1 gives the new vertices of Q. Also clearly, theunion of the faces of Q1 and Q \ Q1 gives the faces of Q. Hence it followsthat µ(AQ|AQ1) = µ(AQ\Q1), and thus µ is domain Markov.Corollary 2.6.4. For any i, k we havepi,k := p(r)i,k = p(l)i,k = φk,i+1αkβi+k (2.6.2)322.6. Half planar triangulationsProof. This is immediate because the event with probability pi,k is a union ofφk,i+1 disjoint events of the form AQ, corresponding to all possible triangu-lations of an i+ 1-gon with k internal vertices. A triangulation contributingto φk,i+1 has k internal vertices by the Euler characteristic formula, 2k+i−1faces. The triangle that separates it from the rest of the map is responsiblefor the extra factor of β.Since the probability of any finite event in H′3 can be computed in termsof the peeling probabilities pi,k’s, we see that for any given α and β wehave at most a unique measure µ supported on H′3 which is translationinvariant and satisfies the domain Markov property. The next step is toreduce the number of parameters to one, thereby proving the first part ofTheorem 2.6.1. This is done in the following lemma.Lemma 2.6.5. Let µ be a domain Markov, translation invariant measureon H′3, and let α,β be as above. Thenβ ={116(2− α)2 α ≤ 2/3,12α(1− α) α ≥ 2/3.Proof. The key is that since the face incident to the root edge is either oftype α, or of the type with probability pi,k for some i, k, (with i = 1, k = 0corresponding to type β) we have the identityα+∑i≥1∑k≥0(p(r)i,k + p(l)i,k)= 1.In light of Corollary 2.6.4 we may write this as1 = α+ 2∑iβi∑kφk,i+1(αβ)k = α+ 2∑iβiZi+1(αβ).From Proposition 2.5.2 we see that the sum above converges if and only ifαβ ≤ 227 . In that case, there is a θ ∈ [0, 1/6] with αβ = θ(1 − 2θ)2. Usingthe generating function for φ (see e.g. [56]) and simplifying gives the explicitidentity(2θ + α− 1)√1− 4θα = 0. (2.6.3)Thus θ ∈ {1−α2 , α4 }. Of these, only one solution satisfies θ ∈ [0, 1/6] forany value of α. If α ≤ 2/3, then we must have θ = α/4 which yieldsβ = 14(1− α2)2= 116(2− α)2332.7. ExistenceIf α ≥ 2/3 one can see from (2.6.3) that the solution satisfying θ ∈ [0, 1/6]is θ = (1− α)/2 which in turn givesβ = α(1− α)2 .2.7 ExistenceAs we have determined β in terms of α, and since Lemma 2.6.2 gives allother probabilities pi,k in terms of α and β, we have at this point proveduniqueness of the translation invariant domain Markov measure with a givenα < 1. However we still need to prove that such a measure exists. Weproceed now to give a construction for these measures, via a version ofthe peeling procedure (see Section 2.4). For α ≤ 2/3, we shall see withTheorem 2.2.3 that the measures Hα can also be constructed as local limitsof uniform measures on finite triangulations.In light of Lemma 2.6.2, all we need is to construct a probability mea-sure µ such that the measure of the events of the form AQ (as defined inLemma 2.6.2) is given by (2.6.1).If we reveal a face incident to any fixed edge in a half planar triangulationalong with all the finite components of its complement, then the revealedfaces form some sub-map Q. The events AQ for such Q are disjoint, andform a set we denote by A. If we choose α and β according to Lemma 2.6.5,then the prescribed measure of the union of the events in A is 1.Let α and let β be given by Lemma 2.6.5. We construct a distributionµr on the hull of the ball of radius r in the triangulation (which consists ofall faces with a corner at distance less than r from the root, and with theholes added to make the hull).Repeatedly pick an edge on the boundary which has at least an endpointat a distance strictly less than r from the root edge in the map revealed sofar. Note that as more faces are added to the map, distances may becomesmaller, but not larger. Reveal the face incident to the chosen edge andall the finite components of its complement. Given α and β we pick whichevent in A occurs by (2.6.1), independently for different steps. We continuethe process as long as any vertex on the exposed boundary is at distanceless than r from the root. Note that this is possible since the revealedtriangulation is always simply connected with at least one vertex on theboundary, the complement must be the upper half plane.Proposition 2.7.1. The above described process almost surely ends afterfinitely many steps. The law of the resulting map does not depend on the342.7. Existenceorder in which we choose the edges.Proof. We first show that the process terminates for some order of explo-ration. The following argument for termination is essentially taken from [7].Assume that at each step we pick a boundary vertex at minimal distance(say, k) from the root (w.r.t. the revealed part of the map), and explorealong an edge containing that vertex. At any step with probability β > 0we add a triangle such that the vertex is no longer on the boundary. Anynew revealed vertex must have distance at least k + 1 from the root. More-over, any vertex that before the exploration step had distance greater thank to the root, still has distance greater than k, since the shortest path to anyvertex must first exit the part of the map revealed before the explorationstep. Thus the number of vertices at distance k to the root cannot increase,and has probability β > 0 of decreasing at each step. Thus almost surelyafter a finite number of steps all vertices at distance k are removed from theboundary. Once we reach distance r, we are done.The probability of getting any possible map T is a monomial in α and β,and is the same regardless of the order in which the exploration takes place(with one α for each non-boundary vertex of the map, and a β term for thedifference between faces and vertices). It remains to show that the processterminates for any other order of exploration. For some order of exploration,let νi(T ) be the probability that the process terminated after at most i stepsand revealed T as the ball of radius r. For i large enough (larger than thenumber of faces in T ) we have that νi(T ) = µr(T ). Summing over T andtaking the limit as i → ∞, Fatou’s lemma implies that limi∑T νi(T ) ≥∑µr(T ). However, the last sum must equal 1, since for some order ofexploration the process terminates a.s.It is clear from Proposition 2.7.1 that µr is a well-defined probabilitymeasure. Since we can first create the hull of radius r and then go on tocreate the hull of radius r+ 1, (µr) forms a consistent sequence of measures.By Kolmogorov’s extension Theorem, (µr)r∈N can be extended to a measureHα on H′3. Also, we have the following characterization of Hα for any simpleevent of the form AQ as defined in Lemma 2.6.2.Lemma 2.7.2. For any AQ and B as defined in Lemma 2.6.2,Hα(AQ) = α|V (Q)|−|V (B)|β|F (Q)|−|V (Q)|+|V (B)| (2.7.1)We alert the reader that such a characterization is not obvious from thefact that the events of the form {Br = T} have the Hα measure exactly as352.8. The phase transitionasserted by Lemma 2.7.2 where Br denotes the hull of the ball of radius raround the root vertex. Any finite event like AQ can be written in terms ofthe measures of Hα(Br = T ) for different T ∈ T by appropriate summation.However it is not clear a priori that the result will be as given by (2.7.1).Proof of Lemma 2.7.2. Since Q is finite, there exists a large enough r suchthat Q is a subset of Br. Now we claim that µr(AQ) is given by the righthand side of (2.7.1). This is because crucially, µr is independent of thechoice of the sequence of edges, and hence we can reveal the faces of Q firstand then the rest of Br. However the measure of such an event is given bythe right hand side of (2.7.1) by the same logic as Proposition 2.7.1. Nowthe lemma is proved because Hα(AQ) = µr(AQ) since Hα is an extension ofµr.We now have all the ingredients for the proof of Theorem 2.6.1.Proof of Theorem 2.6.1. We have the measures Hα constructed above whichare translation invariant and domain Markov (this follows from the secondpart of Lemma 2.6.2). If µ is a translation invariant domain Markov measure,then by Lemmas 2.6.2, 2.6.5 and 2.7.2, µ agrees with Hα on every event ofthe form AQ, and thus µ = Hα for some α.2.8 The phase transitionIn the case of triangulations, we call the measures Hα subcritical, critical andsupercritical when α < 23 , α = 23 , and α > 23 respectively. We summarizehere for future reference the peeling probabilities pi,k and pi = 2∑k≥0 pi,kfor every α ∈ [0, 1). Recall that θ is defined by αβ = θ(1−2θ)2 and θ ∈ [0, 16 ].Critical case: α = 23 This case is the well-known half plane UIPT (see[7]) Here β = 19 and θ = 16 . The two possible values of θ coincide at 16 andhence β = 19 . Using Corollary 2.6.4 and Proposition 2.5.2, we recover theprobabilitiespi,k = φk,i+1(19)i( 227)kpi =24i(2i− 2)!(i− 1)!(i+ 1)!(2.8.1)Note that in H2/3 we have the asymptotics pi ∼ ci−5/2 for some c > 0.362.9. Non-simple triangulationsSub-critical case: α < 23 Here θ = α/4 and hence β =(2−α)216 . UsingCorollary 2.6.4 and Proposition 2.5.2, we getpi,k = φk,i+1(2− α4)2i(α4(1− α2)2)kpi =24i(2i− 2)!(i− 1)!(i+ 1)! ·((1− 3α2)i+ 1) (2.8.2)As before, we get the asymptotics pi ∼ ci−3/2 for some c = c(α) > 0. Notethat pi is closely related to a linearly biased version of pi for the criticalcase.Super-critical case: α > 2/3 Here θ = 1−α2 and hence β =α(1−α)2 .Using Corollary 2.6.4 and Proposition 2.5.2, we getpi,k = φk,i+1αi+2k(1− α2)i+kpi =24i(2i− 2)!(i− 1)!(i+ 1)! ·( 2α − 2)i((3α− 2)i+ 1)(2.8.3)Here, the asymptotics of pi are quite different, and pi has an exponentialtail: pi ∼ cγii−3/2 for some c and γ = 2α − 2. The differing asymptotics ofthe connection probabilities pi indicate very different geometries for thesethree types of half plane maps. These are almost (though not quite) theprobabilities of edges between boundary vertices at distance i.2.9 Non-simple triangulationsSo far in this chapter, we have only considered one type of map: triangula-tions with multiple edges allowed, but no self loops. Forbidding double edgescombined with the domain Markov property, leads to a very constrained setof measures. The reason is that a step of type α followed by a step of typeβ can lead to a double edge. If µ is supported on measures with no multipleedges, this is only possible if αβ = 0. As seen from the discussion above,this gives the unique measure H0 which has no internal vertices at all. Asimilar phenomenon occurs for p-angulations for any p ≥ 3, and we leavethe details to the reader.In contrast, the reason one might wish to forbid self-loops is less clear.We now show that on the one hand, allowing self-loops in a triangulation372.9. Non-simple triangulationsleads to a very large family of translation invariant measures with the domainMarkov property. On the other hand, these measures are all in an essentialway very close to one of the Hα measures already encountered. The reasonthat uniqueness breaks as thoroughly as it does, is that here it is possiblefor removal of a single face to separate the map into two components, oneof which is only connected to the infinite part of the boundary through theremoved face. We remark that for triangulations with self loops, the strongerforms of the domain Markov property discussed in Section 2.3 are no longerequivalent to the weaker ones that we use.Let us construct a large family of domain Markov measures as promised.Our translation invariant measures on triangulations with self-loops aremade up of three ingredients. The first is the parameter α ∈ [0, 1) whichcorresponds to a measure Hα as above. Next, we have a parameter γ ∈ [0, 1)which represents the density of self loops. Taking γ = 0 will result in noself-loops and the measure will be simply Hα. Finally, we have an arbitrarymeasure ν supported on triangulations of the 1-gon (i.e. finite triangulationswhose boundary is a self-loop, possibly with additional self-loops inside).From α, γ and ν we construct a measure denoted Hα,γ,ν . More precisely, wedescribe a construction for a triangulation with law Hα,γ,ν .Given α, take a sample triangulation T from Hα. For each edge e of T ,including the boundary edges, take an independent geometric variable Gewith Hα,q,ν(Ge = k) = (1− q)qk−1. Next, replace the edge e by Ge paralleledges, thereby creating Ge − 1 faces which are all 2-gons. In each of the2-gons formed, add a self-loop at one of the two vertices, chosen with equalprobability and independently of the choices at all other 2-gons. This hasthe effect of splitting the 2-gon into a triangle and a 1-gon. Finally, fill eachself-loop created in this way with an independent triangulation with law ν(see Figure 2.5).Proposition 2.9.1. The measures Hα,q,ν defined above are translation in-variant and satisfy the domain Markov property. For α > 0, these are allthe measures on half planar triangulations with these properties.Recall that we use α to denote the probability of the event of type αthat the triangle incident on any boundary edge also contains an internalvertex. The case of triangulations with α = 0 is special for reasons that willbe clearer after the proof, and is the topic of Proposition 2.9.2. In that casewe shall require another parameter, and another measure ν ′. This will bethe only place where we shall demonstrate domain Markov measures thatare not symmetric w.r.t. left-right reflection.382.9. Non-simple triangulationsFigure 2.5: Non-uniqueness for triangulation with self-loops.Starting with a triangulation with simple faces (left), each edgeis replaced by a geometric number of parallel edges with a self-loop at one of the two vertices between any pair (greater than 1at the bold edges). Independent maps with arbitrary distributionare added inside the self-loops (shaded). Note that multiple edgesmay occur on the left (but not self-loops).Coming back to the case α > 0, note that since ν is arbitrary, the struc-ture of domain Markov triangulations with self-loops is much less restrictedthan without the self-loops. For example, ν could have a very heavy tail forthe size of the maps, or for the degree of the vertex in the self-loop, whichwill affect the degree distribution of vertices in the map. However, the mea-sures Hα,q,ν are closely related to Hα, since the procedure described abovefor generating a sample of Hα,q,ν from a sample of Hα is reversible. Indeed,if we take a sample from Hα,q,ν and remove each loop and the triangulationinside it, we are left with a map whose faces are triangles or 2-gons. If wethen glue the edges of each 2-gon into a single edge, we are left with a simpletriangulation. We refer to this operation as taking the 2-connected core ofthe triangulation, since the dual of the triangulation contains a unique infi-nite maximal 2-connected component, which is a subdivision of the dual ofthe triangulation resulting from this operation. Clearly the push-forward ofthe measures Hα,q,ν via this operation has law Hα. Thus Hα does determinein some ways the large scale structure of Hα,q,ν .Proof of Proposition 2.9.1. Translation invariance is clear as Hα is transla-tion invariant, the variables Ge and triangulations in the self-loops do notdepend upon the location of the root.To see that Hα,q,ν is domain Markov, let T be a half planar triangulationwith law Hα,q,ν . Let core(·) denote the 2-connected core of a map, andobserve that core(T ) is a map with law Hα from which T was constructed.Let Q be a finite simply connected triangulation (which may contain non-simple faces), and let AQ be the event as defined in Lemma 2.6.2. Toestablish the domain Markov property for Hα,q,ν , we need to show that392.9. Non-simple triangulationsconditionally on AQ, T˜ = T\Q (as defined in Section 2.1) has the same law asT . On the event AQ, a corresponding event Acore(Q) that core(Q) ⊂ core(T )also holds. Moreover, on these events, core(T˜ ) = core(T ) \ core(Q) has lawHα, since Hα is domain Markov. We therefore need to show that to get fromcore(T )\core(Q) to T˜ each edge is replaced by a Geom(q) number of parallelnon-simple triangles with ν-distributed triangulations inside the self-loops.Any edge of core(T ) \ core(Q) is split in T˜ into an independent Geom(q)number of parallel edges. Indeed, for edges not in core(Q) this number isthe same as in T , and for edges in the boundary of Q, the number is reducedby those non-simple triangles that are in Q, but is still Geom(q) due to thememory-less property of the geometric variables. The triangulations insidethe self-loops are i.i.d. samples of ν, since they are just a subset of the onesin T which are i.i.d. and ν-distributed.For the second part of the proposition, note first that if µ is domainMarkov, then the push-forward of µ w.r.t. taking the core is also domainMarkov, hence must be Hα for some α ∈ [0, 1) by Theorem 2.6.1.Fix an edge along the boundary, let q be the probability that the facecontaining it is not simple. By the domain Markov property, conditioned onhaving such a non-simple face and removing it leaves the map unchangedin law, and so this is repeated Geom(q) times before a simple face is found.Removing all of these faces also does not change the rest of the map, and sothis number is independent of the multiplicity at any other edge of the map.Similarly, the triangulation inside the self-loop within each such non simpleface is independent of all others, and we may denote its law by ν. Sinceany edge inside the map may be turned into a boundary edge by removinga suitable finite sub-map, the same holds for all edges.To see that µ = Hα,q,ν , it remains to show that the self-loops are equallylikely to appear at each end-point of the 2-gons and are all independent.The independence follows as for the triangulations inside the self-loops. Tosee that the two end-points are equally likely (and only to this end) werequire α > 0. The configuration shown in Figure 2.6 demonstrates this.After removing the face on the right, the self-loop is at the right end-pointof a 2-gon on the boundary. Removing the triangle on the left leaves theself-loop on the left end-point, and so the two are equally likely.As noted above, the case α = 0 is special. In this case, no boundaryedge has its third vertex internal to the triangulation. Note that this is notthe same as saying that the triangulation has no internal vertices - theycould all be inside self-loops, which are attached to the boundary vertices.402.10. Simple and general p-angulationsA BFigure 2.6: Exploring in different orders shows that self-loops areequally likely to be at each end-point of a 2-gon. Conditioning onface A and removing it leaves a non-simple face along the boundarywith the self-loop at the left vertex. Removing instead face B leavesthe self-loop on the right vertex.The contraction operation described above still necessarily yields a sampleT of H0. Similarly, each edge of T must correspond to an independent,geometric number of edges in the full map, and the triangulations inside thecorresponding self-loops must be independent.However, without steps of type α we cannot show that the the two choicesfor the location of the self-loop in 2-gons are equally likely. Indeed, since all2-gons connect a pair of boundary vertices, it is possible to tell them apart.Adding the self-loop always on the left vertex will not be the same as addingit always on the right. This reasoning leads to a complete characterizationalso in the case α = 0. In each 2-gon the self-loop is on the left vertex withsome probability γ ∈ [0, 1], and these must be independent of all other 2-gons. The triangulations inside the self-loops are all independent, but theirlaws may depend on whether the self-loop is on the left or right vertex inthe 2-gon, so we need to specify two measures νL, νR on triangulations ofthe 1-gon. Thus we get the following:Proposition 2.9.2. A domain Markov, translation invariant triangulationwith α = 0 is determined by the intensity of multiple edges q, the probabilityγ ∈ [0, 1] that the self-loop is attached to the left vertex in each 2-gon, andprobability measures νL, νR on triangulations of the 1-gon.2.10 Simple and general p-angulationsHere we prove the general case of Theorem 2.2.1. The proof is similar tothe proof of Theorem 2.6.1, with some additional complications: There aremore than the two types of steps α and β, and the generating function forsimple p-angulations is not explicitly known. There are implicit formulaerelating it to the generating function for general maps with suitably chosen412.10. Simple and general p-angulations(b) (c) (d)(a)Figure 2.7: Building blocks for quadrangulations and general p-angulations. Shown: an event of type A5 for p = 9 and the threebuilding blocks for p = 4.weights for various face sizes, which are fairly well understood in the case ofeven p. For quadrangulations, even more is known. In [83], the problem ofenumerating 2-connected loopless near 4-regular planar maps (see [83] forexact definitions) is considered. This is easily equivalent to our problem ofenumerating simple faced quadrangulations with a simple boundary. Thegenerating function is computed there in a non-closed form. With carefulanalysis, this might lead to explicit expressions analogous to the ones wehave for the triangulation case at least for the case of quadrangulations.We have not been able to obtain such expressions, and thus our descrip-tion of the corresponding Hα’s still depends on an undetermined parameterβ = β(α). Instead, uniqueness is proved by a softer argument based onmonotonicity. The proof of existence used for triangulations goes throughwith no significant changes, but is now conditional on the existence of asolution to a certain equation.Proof of Theorem 2.2.1. As before, let µ be a probability measure supportedon the set H′p of half planar simple p-angulations which is translation in-variant and satisfies the domain Markov property. The building blocks forsimple p-angulations, taking the place of Aα and Aβ, will be the eventswhere the face incident to the root edge consists of a single contiguous seg-ment from the infinite boundary, together with a simple path in the interiorof the map closing the cycle, with the path in any fixed position relative tothe root (see Figure 2.7(a)). The number of internal vertices can be anythingfrom 0 to p− 2. Let the µ-measure of such an event with i internal vertices(call the event Ai) be αi for i = 0, . . . , p − 2. For example, in the case ofp = 3 we have α1 = α and α0 = β. We shall continue to use α for αp−2, i.e.the µ-probability that the face on the root edge contains no other boundaryvertices. Note that there are several such events of type Ai, which differonly in the location of the root. However because of translation invariance,each such event has the same probability αi. For quadrangulations (p = 4),there are three possible building blocks, shown in Figure 2.7(b–d).We have a generalization of Lemma 2.6.2, that shows that the measureµ is determined by α0 . . . , αp−2, leaving us with p − 1 degrees of freedom.422.10. Simple and general p-angulationsFigure 2.8: The event B4 for p = 6. Depending on the order ofexploration, its probability is found to be α23 or α4α2.However, before doing that, let us reduce these to two degrees of freedom.For any i = 1, . . . , p − 2, consider the event Bi defined as follows (see e.g.Figure 2.8):(i) The face incident to the root edge has i − 1 internal vertices andits intersection with the boundary is a contiguous segment of lengthp− i+ 1 with the leftmost of those vertices being the root.(ii) The face incident to the edge to the left of the root edge has iinternal vertices, its intersection with the boundary is a contiguoussegment of length p− i, with the root vertex being the right end-point.(iii) The two faces above share precisely one common edge betweenthem which is also incident to the root vertex.The probability µ(Bi) can be computed by exploring the faces incident tothe root edge, and with the edge to its left in the two possible orders.We find that α2i−1 = αiαi−2, and hence the numbers {α0, . . . , αp−2} forma geometric series, leaving two degrees of freedom. In order to simplifysubsequent formulae we reparametrize these as follows. Denoteβp−2 = α0, γp−2 = αp−2so that the geometric series is given by αi = γiβp−2−i. This is consistentwith the previous definition of β in the case p = 3.Lemma 2.10.1. Let µ be a measure supported on H′p which is translationinvariant and domain Markov. Let Q be a finite simply connected simplep-angulation and 2 ≤ k < |∂Q|. As before, AQ,k is the event that Q isisomorphic to a sub-map of M with k consecutive vertices being mapped tothe boundary of M . Thenµ(AQ,k) = α|V (Q)|−k1 α|F (Q)|−|V (Q)|+k0 = β(p−2)|F (Q)|−|V (Q)|+kγ|V (Q)|−k.(2.10.1)Furthermore, if µ satisfies (2.10.1) for any such Q and k, then µ is transla-tion invariant and domain Markov.432.10. Simple and general p-angulationsThe proof is almost the same as in the case of triangulations, and weomit some of the repeated details, concentrating only on the differences.Proof. We proceed by induction on the number of faces of Q. If Q hasa single face, then we are looking at one of the events Ai. Then the faceconnected to the root sees i new vertices. The measure of such an event is αiwhich is equal to α0(α1/α0)i since {α0, . . . , αp−2} form a geometric series.Hence (2.10.1) holds.In general, the face Γ connected to the root can be connected to theboundary of Q and to the interior of Q in several possible ways. Q \ Γ hasseveral components some of which are connected to the infinite componentof M \Q and some are not. We shall explore the components not connectedto the infinite component of M \Q first, then the face Γ and finally the restof the components. Note that in every step of exploration if we encounteran event of type Ai, we get a factor of αv1αf−v0 for the probability, wherev is the number of new vertices added and f is the number of new facesadded since {α0, α1, . . . , αp} are in geometric progression. Notice that thenumber of new vertices in all the components and Γ add up to that of Qand similarly the number of faces in all the components and Γ also add upto that of Q. Also in each component the number of faces is strictly smallerthan Q. Hence we use induction hypothesis to finish the proof of the claimsimilarly as in Lemma 2.6.2.Returning to the proof of Theorem 2.2.1, let Zm(x) =∑i≥0 ψ(p)m,ixi bethe generating function for p-angulations of an m-gon with weight x for eachinternal vertex. The probability of any particular configuration for the facecontaining the root is found by summing (2.10.1) over all possible ways offilling the holes created by removal of the face. A hole which includes k ≥ 2vertices from the boundary of the half planar p-angulation and has a totalboundary of size m can be filled in ψ(p)m,n ways with n additional vertices. Ap-angulation of an m-gon with n internal vertices has m+2n−2p−2 faces, and soeach of these contributes a factor ofβ(p−2)|F (Q)|−|V (Q)|+kγ|V (Q)|−k = βn+k−2γn+m−k.to the product in (2.10.1). Summing over p-angulations, these weights addup toβk−2γm−kZm(βγ).Now, suppose there are a number of holes with boundary sizes given by asequence (mi) involving (ki) boundary vertices respectively (see Figure 2.9).442.10. Simple and general p-angulationsFigure 2.9: A possible configuration for the root face in a 13-angulation. The hole parameters (ki,mi) from left to right are(4, 5), (2, 2), (5, 7). There are j = 5 vertices exposed to infinity, sothe probability of this configuration is α5 ·(β2γZ5)·(Z2)·(β3γ2Z7).Since any p-angulation can be placed in each of the holes and the weightsare multiplicative, the total combined probability of all ways of filling theholes is ∏iβki−2γmi−kiZmi(βγ).This must still be multiplied by a probability αj of seeing the face containingthe root conditioned on any compatible filling of the holes (see Figure 2.9).Thus we have the final identity R(β, γ) = 1, where we denoteR(β, γ) =∑αj∏iβki−2γmi−kiZmi(βγ), (2.10.2)where the sum is over all possible configurations for the face containing theroot edge, and (mi, ki) and j are as above.For any possible configuration for the face at the root, and each hole itcreates we have ki ≥ 2 (since k = 1 would imply a self-loop) and mi ≥ ki(since k counts a subset of the vertices at the boundary of the hole). Wealso have αj = γjβp−2−j , and so each term in R is a power series in β, γwith all non-negative coefficients. In particular, R is strictly monotone inβ and γ, and consequently for any γ there exists at most a single β so thatR(β, γ) = 1.As an example of (2.10.2), consider the next simplest case after p = 3,namely p = 4. Here, there are 8 topologically different configurations for theface attached to the root, shown in Figure 2.10. Of those, in the leftmostshown and its reflection the hole must have a boundary of size at least 4.In all others, the hole or holes can be of any even size. summing over thepossible even sizes, we get the totalR = γ2 + 4γβ Z − 2γβZ2(βγ) +3β2Z2,452.10. Simple and general p-angulationsFigure 2.10: Possible faces incident to a boundary edge for quad-rangulations. The first three may also be reflected to give the 8topologically distinct possibilities. The holes (shaded) can haveboundary of any even length.where Z =∑k≥2 βkZk(βγ) is the complete generating function for simple-faced quadrangulations with a simple boundary.To get existence of the measures H(p)α , we need to show that for anyγ = α1/(p−2) there exists a β so that R(β, γ) as defined in (2.10.2) equals1. By monotonicity, and since R(0, γ) = γp−2 < 1 (the only term with nopower β corresponds to the event Ap−2 with probability α), it suffices toshow that some β satisfies 1 ≤ R(β, γ) < ∞. Note that just from steps oftype A0 and Ap−2 we get R(β, γ) ≥ βp−2 + γp−2. Thus for β close to 1 wehave R(β, γ) > 1, provided it is finite. We prove this holds at least for αsufficiently close to 1:Proposition 2.10.2. For any p ≥ 4, and any α ∈ (α0(p), 1) there is someβ so that R(β, α1/(p−2)) > 1, and so the measure H(p)α exists for α > α0(p).Proof. To see that Zm(q) <∞ for small enough q we need that the numberof p-angulations grows at most exponentially. For triangulations or even pthis is known from exact enumerative formulae. For any p-angulation wecan partition each face into triangles to get a triangulation of the m-gon.The number of those is at most exponential in the number of vertices. Thenumber of p-angulations corresponding to a triangulation is at most 2 to thenumber of edges, as each edge is either in the p-angulation or not. Thus weget a (crude) exponential bound also for odd p.It is easy to see that there exists a 0 < qc < 1 such that Zm(q) <∞ forq < qc 6= 0. We expect Zm(qc) < ∞ as well, though that is not necessaryfor the rest of the argument. Now we need some general estimate givingexponential growth of Zm. Fix any q < qc. Note that ψm,n ≥ ψm+p−2,n−p+2by just counting maps where the face containing the root is incident to noother boundary vertices. Thus Zm(q) ≥ qp−2Zm+p−2(q), and so Zm(q) ≤462.11. Non-simple p-angulationsCq−m for some constant C > 0, provided it is finite. Of course, this crudebound does not give the correct rate of increase for Z as m→∞.In each term of (2.10.2), the mi − ki are bounded, but while keepingthem fixed, the ki’s could take any value (subject to parity constraints foreven p). Fixing mi − ki and summing over the possibilities for the ki’s wesee that R(β, γ) < ∞ provided that ∑m βmZm(βγ) < ∞. Now Zm(q) isan increasing function of q as long as it is finite since all the coefficients ofZm are non-negative integers. Thus we have for β = qc/(4γ), any choice ofγ > 1/2 and the estimate on Zm found above,∑mβmZm(βγ) =∑mβmZm(qc4)<∑m( qc4γ)mZm(qc2)<∑m(2γ)−m <∞(2.10.3)Thus for a choice of γ close to 1 and β = qc/4γ we have R(β, γ) < ∞ andR(β, γ) ≥ βp−2 + γp−2 > 1.Having found a γ so that R(β, γ) = 1, we know the probability that themap contains any given finite neighborhood of the root. The rest of theconstruction is similar to the triangulation case as described in Section 2.7with no significant changes.Based on the behavior in the case of p = 3, we expect the measuresHα to exist for all α < 1. Moreover, we expect that R(qc/γ, γ) > 1 whenγp−2 = α > αc and that for smaller γ the maximal finite value taken by Ris exactly 1 where αc will be a critical value of α at which a phase transitionoccurs analogous to the triangulation case. We see below that H(4)α existsfor α ≤ 38 , and a similar argument holds for other even p (when there areexplicit enumeration results).2.11 Non-simple p-angulationsFinally, let us address the situation with p-angulations with non-simple faces.In the case of p-angulations for p > 3, uniqueness breaks down thoroughly,and a construction similar to Section 2.9 applies. For even p self-loops areimpossible since a p-angulation is bi-partite. However, inspection of theconstruction of Hα,q,ν shows that it works not because of the self-loop, butbecause it is possible for a single face to completely surround other faces ofthe map.Consider first the case p = 4, and suppose we are given a measure µsupported on H4 satisfying translation invariance and the domain Markovproperty. Take a sample from µ, and replace each edge by an independent472.11. Non-simple p-angulationsFigure 2.11: Non-uniqueness for quadrangulations: each edge isreplaced with a geometric number of parallel edges. In each 2-gonan internal 2–gon is added at a uniformly chosen endpoint, andfilled with an independent finite (possibly empty) quadrangulation.geometric number of parallel edges. In each of the 2-gons created, addanother 2-gon attached to one of the two vertices with equal probability,thereby creating a quadrangle. Fill the smaller 2-gons with i.i.d. samplesfrom an arbitrary distribution supported on quadrangulations of 2-gons (seeFigure 2.11). As with triangulations, this results in a measure which isdomain Markov and translation invariant.Hence we see that faces which completely surround other faces of the mapprevent us from getting only a one-parameter family of domain Markov mea-sures. For triangulations and quadrangulations, the external boundary ofsuch a face can only consist of 2 edges (i.e. there are precisely two edges con-necting the face to the infinite component of the complement). Removingsuch faces and identifying the two edges results in a domain Markov mapwith simple faces, which falls into our classification. Similarly to Propo-sition 2.9.1, it is possible to get a complete characterization of all domainMarkov maps on quadrangulations in terms of α, the density γ of non-simplefaces, and a measure ν on quadrangulations in a 2-gon.For p ≥ 5, things get messier. Similar constructions work for any p > 3,with inserted 2-gons for even p, and any combination of 2-gons and self-loops for p odd. However, here this no longer gives all domain Markovp-angulations. A non-simple face can have external boundary of any sizefrom 2 up to p − 1 (with parity constraint for even p). Thus it is notgenerally possible to get a p-angulation with simple faces from a generalone. Removing the non-simple faces leaves a domain Markov map withsimple faces of unequal sizes. It is possible to classify such maps, and theseare naturally parametrized by a finite number of parameters, since we mustalso allow for the relative frequency of different face sizes. Much of such a482.12. Approximation by finite mapsclassification is similar to the proofs of Theorems 2.2.1 and 2.6.1, and we donot pursue this here.2.12 Approximation by finite mapsWe prove Theorem 2.2.3, identifying the local limits of uniform measures onfinite triangulations in this section. Here, we are concerned only with themeasures Hα on triangulations for critical and sub-critical α ≤ 2/3. Recallfrom the statement of the theorem, that we have sequences (ml)l∈N, (nl)l∈Nof integers such that ml/nl → a for some a ∈ [0,∞] and ml, nl → ∞. Weshow that µml,nl — the uniform measure on triangulations of an m-gon withn internal vertices — converges weakly to Hα where α = 22a+3 . To simplifythe notation, we drop the index l from the sequences ml and nl and assumethat m is implicitly a function of n. Note that since [0,∞] is compact, itfollows that {Hα}α≤2/3 are all the possible local limits of the µm,ns.Here is an outline of the proof: A direct computation shows that theµm,n measure of the event that the hull of the ball of radius r is a particularfinite triangulation T converges to the Hα measure of the same event (forany T ), as given by Lemma 2.7.2. While a priori this only gives convergencein the vague topology, since the limit Hα is a probability measure, it actuallyfollows that µm,n is a tight family of measures and hence converges weakly.Thus we show the convergence of the hulls of balls. Note that the hulls ofballs around the root always have a simple boundary.We start with a simple estimate on relative enumerations on the numberof triangulations of a polygon.Lemma 2.12.1. Suppose m,n→∞ so that m/n→ a for some a ∈ [0,∞].Then for any fixed j, k ∈ Z,limn,m→∞φn−k,m−jφn,m=( (a+ 1)2(2a+ 3)2)j (2(a+ 1)2(2a+ 3)3)kProof. By applying Stirling’s approximation to (1.3.1), we have for m,n492.12. Approximation by finite mapslargeφn,m+2 =2n+1(2m+ 1)!(2m+ 3n)!(m!)2n!(2m+ 2n+ 2)!∼ c12n+1(2m+ 1)!(m!)2((2m+ 3n)2m+3n+1/2(2m+ 2n+ 2)2m+2n+5/2nn+1/2)∼ c22n4m√m(274)n(94)mn−5/2(1 + 2m3n)2m+3n (1 + mn)−2m−2n(2.12.1)Taking the ratio, we haveφn−k,m+2−jφn,m+2∼( 227)k (19)j (1 + mn )2j+2k(1 + 2m3n )2j+3k×(1 + 2m−2j3n−3k1 + 2m3n)2m+3n(1 + m−jn−k1 + mn)−2m−2n. (2.12.2)An easy calculation shows that the product of the last two terms in the righthand side of (2.12.2) converges to 1. Indeed, if a is finite then the first tendsto e−2j+2ak and the second to e2j−2ak. If a =∞ then after shifting a factorof(nn−k)2mfrom the first to the second, the limits are e−2j and e2j .The result follows by taking the limit and using the fact that m/n con-verges to a.Let AQ, V (Q), F (Q), V (B) be as in Lemma 2.6.2, and note that AQmakes sense also when looking for Q as a sub-map of a finite map.Lemma 2.12.2. Suppose m,n → ∞ with m/n → a for some a ∈ [0,∞].Thenlimm,nµm,n(AQ) =( 22a+ 3)|V (Q)|−|V (B)|( a+ 12a+ 3)2(|F (Q)|−|V (Q)|+|V (B)|).Remark 2.12.3. If we make the change of variable α = 2(2a+ 3)−1, thenLemma 2.12.2 gives uslimm,nµm,n(AQ) = α|V (Q)|−|V (B)|((2− α)216)(|F (Q)|−|V (Q)|+|V (B)|).From Lemma 2.12.2 we can immediately conclude that the µm,n-measureof AQ converges to the Hα measure of the corresponding event.502.13. Quadrangulations and beyondCorollary 2.12.4. Suppose m,n→∞ with m/n→ a for some a ∈ [0,∞].Then we havelimm,nµm,n(AQ) = Hα(AQ)where α = 22a+3 .Proof of Lemma 2.12.2. It is clear that the number of simple triangulationsof an m + 2-gon with n internal vertices where AQ occurs is φn−k,m+2−jwhere j = 2|V (B)| − |∂Q| − 2 where |∂Q| is the number of vertices in theboundary of Q, and k = |V (Q)| − |V (B)|. Then from Lemma 2.12.1, wehavelimm,nµm,n(AQ) = limn,mφn−k,m+2−jφn,m+2=( (1 + a)2(2a+ 3)2)j (2(a+ 1)2(2a+ 3)3)kFrom Euler’s formula, it is easy to see that |F (Q)| = 2|V (B)| − |∂Q| − 2.This shows j + k = |F (Q)| − |V (Q)| + |V (B)|. Using all this, we have theLemma.Proof of Theorem 2.2.3. Corollary 2.12.4 gives convergence for cylinder events.Since Hα is a probability measure, the result follows by Fatou’s lemma.2.13 Quadrangulations and beyondCan we get similar finite approximations for H(p)α for p > 3? We think it ispossible to prove such results based on enumeration of general p-angulationswith a boundary, which is available for p even. We believe that similar resultsshould hold for any p, though do not see a way to prove them. Let us presenthere a recipe for quadrangulations. For higher even p there are additionalcomplications as the core is no longer a p-angulation and results on mapswith mixed face sizes are needed.Let us first consider quadrangulations with a simple boundary. Denoteby Q2m,n the space of quadrangulations with simple boundary size 2m andnumber of internal vertices n (note that since the quadrangulation is bipar-tite, the boundary size is always even). Let q2m,n = |Q2m,n| be its cardinal-ity. Enumerative results are available in this situation (see [30]). We alertthe reader that our notation is slightly different from [30]: they use q˜2m,nfor quadrangulations with a simple boundary and n denotes the number offaces, not the number of internal vertices. Using Euler’s formula one caneasily change from one variable to the other. Doing that, we get:q2m,n = 3n−1(3m)!m!(2m− 1)!(2n+ 3m− 3)!n!(n+ 3m− 1)! (2.13.1)512.13. Quadrangulations and beyondNow suppose m/n→ a for some a ∈ [0,∞] where m and n are sequencessuch that m → ∞ and n → ∞. Let ν2m,n be the uniform measure on allquadrangulations of boundary size 2m and n internal vertices. A straight-forward computation similar to Lemmas 2.12.1 and 2.12.2 gives us for anyfinite Q,limm,nν2m,n(AQ) =( 4(1 + 3a)327(2 + 3a)3)|F (Q)|·( 9(2 + 3a)4(1 + 3a)2)|V (Q)|−|V (B)|(2.13.2)where V (Q) is the set of vertices in Q, V (B) is the set of vertices of Q on theboundary of M , and F (Q) is the set of faces in Q (by Euler’s characteristic,the “change” in the boundary length when removingQ is 2(|V (Q)|−|V (B)|−|F (Q)|)).The limit (2.13.2) in itself is not enough to give us distributional conver-gence of ν2m,n, as we are missing tightness. It is possible to get tightness forν2m,n using the same ideas presented for example in [13, 65] or the generalapproach found in [21]. The key is that it suffices to show the tightnessof the root degree. The interested reader can work out the details and weshall not go into them here. Instead, throughout the remaining part of thissection, we shall assume that the distributional limits of ν2m,n exist. Weremark here that when a = 0 the limiting measures of the events describedby (2.13.2) matches exactly with that of the half planar UIPQ measure (see[44]) and that for a = ∞ we get the dual of a critical Galton-Watson treeconditioned to survive. Thus in these two extreme cases, the distributionallimit has already been established.To handle all a, we define the operator core : H4 → H′4, which is thereverse of the process used to define the measures Hα,q,ν in Section 2.9, andacts on the dual by taking the 2-connected core. Formally, any face whichis not simple must have an external double edge connecting it to the rest ofthe map (and a 2-gon inside it). The core operator removes every such face,and identifies the two edges connecting it to the outside. This operation isdefined in the same way on quadrangulations of an m-gon. As discussed inSection 2.9, if µ is domain Markov on H4 then µ ◦ core−1 is domain Markovon H′4.Let µ = lim ν2m,n as m,n → ∞ with m/n → a ∈ [0,∞]. We firstobserve that µ is domain Markov and translation invariant. This followsfrom (2.13.2) and the converse part of Lemma 2.10.1.Next, observe that the events Ai for i = 0, 1, 2 are not affected by core.This is because in each of them, the face containing the root is a simple face,and so is not contained in any non-simple face. At this point from (2.13.2),522.13. Quadrangulations and beyondwe obtain β2 = (4(1+3a)3)/(27(2+3a)3) and γ/β = (9(2+3a))(4(1+3a)2).Thus,µ(A2) =34(1 + 3a)(2 + 3a) µ(A0) =427(1 + 3a2 + 3a)3.From the first we see that as a goes from 0 to ∞ we get α ∈ [0, 38 ].Solving for a in terms of α = µ(A2) and plugging in we find β =√µ(A0) =227(√3 + α − √α)3, which decreases from√4/27 to√1/54 as α increasesfrom 0 to 3/8.This gives the measures H(4)α as the the core of the limit of uniformmeasures on non-simple quadrangulations. Since the core operation is con-tinuous in the local topology, this is also the limit of the core of uniformquadrangulations. This does not give H(4)α as a limit of uniform measureson non-simple quadrangulations, since the number of internal vertices inthe core of a uniform map from Q2m,n is not fixed. Thus the above onlyproves the limit when n is taken to be random with a certain distribution(though concentrated and tending to infinity in proportion to m.) It shouldbe possible to deduce (though we have not proved it) that uniform simplequadrangulations converge to H(4)α by using a local limit theorem for thedistribution of the size of the core (see [15, 16]).The above indicates that a phase transition for the family H(4)α occursat α = 3/8, similar to the case p = 3. We can similarly compute theasymptotics of pk as in Section 2.8 and see that pk ∼ ck−5/2 for α = 3/8and pk ∼ ck−3/2 for α < 3/8. This indicates different geometry of the maps.All these hints encourage us to conjecture that a similar picture of phasetransition do exist for the measures H(p)α for all p > 3.53Chapter 3Half planar maps: geometry2 As a continuation of Chapter 2, we shall study the geometry of domainMarkov half planar random maps and also analyze percolation on them. Weshall focus mainly on half planar triangulation and the main tool will be thepeeling process. Recall that Theorem 2.2.1 for p = 3 gives the classificationresult for domain Markov half planar triangulations. Also recall the param-eter α which denotes the probability that the triangle incident to the rootedge has the other vertex not on the boundary. Recall the phase transitionas described in Section 2.8. In this chapter, we focus on the subcritical andsupercritical phases of domain Markov half planar triangulations, and an-alyze this phase-transition in more detail. In particular, we obtain resultsfor volume growth, isoperimetry and geometry of percolation clusters in thesupercritical and subcritical phases of these maps. Finally, we extract someinformation about the behavior of random walk on these maps from thesegeometric informations.We introduce some new notations which will be used throughout thischapter. A step of the form (L, i) (resp. (R, i)) is the event that the triangleincident to the root edge is attached to a vertex on the boundary which isat a distance i to the left (resp. right) of the root edge along the bound-ary (see Figure 3.2). We shall also talk about such events with the rootedge replaced by any fixed edge on the boundary of the map. Because oftranslation invariance, the measures of such events do not depend on theedge we want to consider and it was also shown in Chapter 2 that for anyfixed i ≥ 1, the measures of (L, i) and (R, i) are the same. Let pi,k denotethe measure of the event that a step of the form (L, i) or (R, i) occurs andthe triangle incident to the root edge separates k internal vertices of themap from infinity. Let pi =∑k pi,k. We will use some of the asymptoticsof pi described in Section 2.8. In particular recall that pi ∼ ci−3/2 in thesubcritical phase and on the other hand, pi ∼ exp(−c′i) in the supercriticalphase for some positive constants c, c′.2The results of this chapter are from the paper [82]54Chapter 3. Half planar maps: geometryFigure 3.1: An illustration (artistic) of the geometry of a subcrit-ical half planar triangulation to the left and that of supercritical tothe right. The blue edges in the subcritical map is the boundary ofthe map.α-step i vertices i vertices.Figure 3.2: Left: An α-step. Centre: A step of the form (R, i).Right: A step of the form (L, i). The gray area denotes someunspecified triangulation.553.1. Main results3.1 Main results3.1.1 GeometryWe present below the results obtained in this chapter first for supercriticaland then for subcritical maps. Roughly, the behavior of supercritical mapsare hyperbolic: they have exponential volume growth and anchored expan-sion which will imply transience of simple random walk. The subcriticalmaps behave, in view of their geometry, roughly like the critical Galton-Watson tree conditioned to survive (see [63]). They have quadratic volumegrowth, and infinitely many cut-sets of finite size. All the terms stated inthis paragraph will be defined rigorously below.We remark here that the geometric properties are certainly very differentfrom the critical uniform infinite half planar triangulation (UIHPT). Forresults of similar nature regarding the UIHPT, see [7, 8, 10]. Predictably,the asymptotics of pi stated in Section 2.8 play a crucial role in proving theresults stated below for different regimes of the parameter α.SupercriticalRoughly, the geometry of maps in the supercritical regime can be viewedas a collection of supercritical trees one attached to each of the boundaryvertices with some horizontal segments being added (see Figure 3.3). Hence,we can expect exponential volume growth, large cut-sets and positive speedof random walk on these maps. In this chapter, we confirm some of theseheuristics.Throughout this subsection, we assume α ∈ (2/3, 1). For a set X, |X|denotes its cardinality, and by an abuse of notation, for any finite graph ormap G, |G| will denote its number of vertices. The ball of radius r in a mapdenotes the sub-map formed by all the faces which have at least one vertexincident to it which is at a distance strictly less than r from the root vertexalong with all the edges and vertices incident to them. Recall that the hullof radius r is the ball of radius r along with all the finite components of itscomplement. Note that since the half planar maps are one-ended, there willbe at most one infinite component in the complement of the ball and thehull is always a simply connected sub-map. The internal boundary of asimply connected sub-map is the set of vertices and edges in the sub-mapwhich is incident to at least one finite face which is not in the sub-map.Clearly, the internal boundary of a hull is a connected simple path in themap. We denote the hull of radius r around the root of a map with law Hαby Br(α) and its internal boundary by ∂Br(α).563.1. Main resultsFigure 3.3: An very rough intuition of the geometry of supercriticalmaps.We first show exponential volume growth of the hull and the boundaryof the hull.Theorem 3.1.1. There exists some positive constants 1 < c < C dependingonly on α such that almost surely,lim sup |∂Br(α)|Cr = 0 and lim inf|∂Br(α)|cr =∞ (3.1.1)and also,lim sup |Br(α)|Cr = 0 and lim inf|Br(α)|cr =∞ (3.1.2)Having established the exponential volume growth, we ask if there aresmall cut-sets in the map. The usual parameter to look for in this situa-tion is the Cheeger constant but since our maps are random and any finiteconfiguration does occur almost surely somewhere in the map, the correctparameter to consider is the anchored expansion (see [72] Chapter 6).For a graph G, let V (G) denote its set of vertices. For any graph G, anda subset of vertices S ⊂ V (G), let |∂ES| denote the number of edges in Gwith one vertex in S and another in V (G) \S. Also let |S|E denote the sumof the degrees of the vertices in S. The anchored expansion constanti∗E(G) of a graph G is defined as follows:lim infn→∞{ |∂ES||S|E;S ⊂ V (G) is connected, v ∈ S, |S|E ≥ n}= i∗E(G)Although we specify a vertex v in the above definition, the definition is inde-pendent of the choice of v. If i∗E(G) > 0, we say G has anchored expansion.Theorem 3.1.2. A half planar triangulation with law Hα for α ∈ (2/3, 1)has anchored expansion almost surely.573.1. Main resultsWe remark here that the exponential lower bound for the volume growthcan be concluded from anchored expansion, but we prove it using a differentprocedure involving an exploration process because we use the same explo-ration process to study the subcritical maps and also we get an upper boundon the volume growth using this method.It is shown in [90] that for bounded degree graphs having anchored ex-pansion, the random walk has positive speed, that is, the graph distancebetween the position of the walker after the nth step and the starting posi-tion grows linearly. Unfortunately our maps are not bounded degree maps,so we cannot directly translate the result. However we can conclude usingTheorem 3.5 of [86] and Theorem 3.1.2 thatCorollary 3.1.3. Simple random walk on a map with law Hα is transientalmost surely if α ∈ (2/3, 1).We believe that the random walk does have positive speed almost surelyfor supercritical maps and in fact the walker should move away from theboundary at linear speed. What we need to do to prove this is to controlthe slowing down of the walk due to the presence of high degree “traps” inthe map.SubcriticalThroughout this subsection, α ∈ [0, 2/3). The journey of understandingsubcritical triangulations begins with a result about their cut-sets. A cut-set of an infinite rooted graph G is a connected subgraph of G which whenremoved breaks up G into two or more connected components, the rootbeing in the finite component.Proposition 3.1.4. In a half planar triangulation with law Hα where α ∈[0, 2/3), there exists infinitely many cutsets each of which consists of a singleedge almost surely.Because of the domain Markov property, the above proposition meansthat a triangulation distributed as a subcritical Hα has i.i.d. copies of finitetriangulation each of which share only a single edge with each other (seeFigure 3.1). Proposition 3.1.4 and the Nash-Williams criterion for recurrence(see [71] Proposition 9.15) immediately impliesCorollary 3.1.5. Simple random walk on a half planar triangulation withlaw Hα is recurrent almost surely for α ∈ (0, 2/3).583.1. Main resultsIt is interesting to study the dual maps of these maps. As described inChapter 2, we make such a dual map locally finite by breaking the infinitedegree vertex corresponding to the infinite face into infinitely many leaves.Hence the dual almost surely consists of i.i.d. sequence of 3-regular graphs(with leaves) connected to each other by a single edge. For α = 0, it canactually be seen that the dual is a critical Galton-Watson tree conditionedto survive (see Chapter 2) and hence, the maps for different values of α canbe seen as an “interpolation” between the UIHPT and critical trees. In fact,we believe that the scaling limit of such maps in the sense of local Gromov-Hausdorff topology exists and is the infinite non-compact continuum randomtree (CRT). This can be viewed as the tangent cone at the root of thecompact Aldous CRT (see [42]). In fact from this heuristic, we expect thatthe random walk behaves more or less similarly as a random walk in thecritical tree conditioned to survive. The spectral dimension of the subcriticalmaps should be almost surely 4/3 and should follows from much more generalresults for strongly recurrent graphs studied in [17, 66].As can be expected from Proposition 3.1.4, the boundary size of the hullof radius r is a tight sequence. We prove a stronger result: the boundarysizes of the hull has exponential tail.Theorem 3.1.6. Let α ∈ [0, 2/3). Then there exists some positive constantc > 0 (depending only on α) such thatHα(|∂Br(α)|) > n) < e−cnfor all n ≥ 1.The following central limit theorem shows that the volume growth isquadratic: another tree-like behavior.Theorem 3.1.7. Suppose α ∈ [0, 2/3). Then|Br|r2 → S1/2(α)in distribution where S1/2(α) is a stable random variable with parameter 1/2and its other parameters depend only upon α and nothing else.3.1.2 PercolationWe are mainly interested in quenched statements about Bernoulli site per-colation on random triangulations: take a half planar triangulation T withlaw Hα and color each vertex independently black with probability p or593.1. Main resultswhite with probability 1 − p. A black (resp. white) cluster is a connectedcomponent induced by the black (resp. white) vertices on the map. Given ahalf planar map, denote the percolation measure on it by Pp and the expec-tation by Ep. Let Pp denote the overall measure induced by the percolationconfiguration on such random maps and let Ep denote the expectation withrespect to the measure Pp. It is understood that in these notations thereis a hidden parameter α which we shall drop to lighten notation. As usual,define pc to be the infimum over p such that there exists an infinite blackcluster Pp-almost surely. Further, we will also be interested inpu = inf{p ∈ (0, 1] : there exists an unique infinite cluster Pp-almost surely}Further history of the study of percolation of random maps is discussed inSection 1.4.Notice that it is immediate to see via Proposition 3.1.4 that percolationis uninteresting in the subcritical maps (in this case pc = 1 almost surely.) Itwas conjectured (see [24]) by Benjamini and Schramm that on non-amenablequasitransitive graphs, pc < pu. For supercritical maps, because of anchoredexpansion as depicted by Theorem 3.1.2, we would expect a similar behavior.Theorem 3.1.8. Fix α ∈ (2/3, 1). Then Hα-almost surely,(i) pc = 12(1−√3− 2α)(ii) pu = 12(1 +√3− 2α)Also, Hα-almost surely, there is no infinite black cluster Ppc-almost surelyand there is an unique infinite black cluster Ppu-almost surely.Note that pc < pu almost surely in the regime α ∈ (2/3, 1). It is interest-ing to note that as α→ 2/3, both pc → 1/2 and pu → 1/2. But in the regime(pc, pu) we have more than one infinite cluster. One can easily conclude viaergodicity of these maps with respect to translation of the root along theboundary (see Chapter 2) that the number of infinite black or white clustersis actually infinite almost surely. The next Theorem shows that the numberof black or white clusters in fact have positive density along the boundary.Let W∞k , B∞k be the number of infinite white and black clusters respectivelywhich share at least vertex with a vertex which is within distance k fromthe root along the boundary.603.2. PreliminariesTheorem 3.1.9. Fix α ∈ (2/3, 1) and suppose p ∈ (pc, pu) where pc,pu areas in Theorem 3.1.8. There exists a positive constant ρ > 0 such that almostsurely,W∞kk → ρ,B∞kk → ρ (3.1.3)The constant ρ is in fact half of the probability of the event of having aninfinite interface starting from a boundary edge (see Section 3.1.2 for moredetails.)A ray in an infinite percolation cluster is a semi-infinite simple path inthe cluster starting from a vertex closest to the root with ties are brokenarbitrarily. Two rays r1 and r2 are equivalent if there is another ray r3which intersect both these rays infinitely many times. An end of a clusteris an equivalence class of rays. Let END(C) denote the space of ends of apercolation cluster C. We shall define a metric on END(C) as follows: forany two rays ξ and η on C, define the distance between them asd(ξ, η) = inf{1/n, n = 1 or ∀X ∈ ξ,∀Z ∈ η,∃ a component K ofC \Bn, |X \K|+ |Z \K| <∞}It is easy to deduce that END(C) does not depend on the choice of thevertex around which we consider the graph-distance balls and that END(C)equipped with this metric is compact.Theorem 3.1.10. Fix α ∈ (2/3, 1). Assume pc, pu are as in Theorem 3.1.8and fix p ∈ (pc, pu). Then Hα-almost surely, the subgraph formed by eachinfinite cluster has no isolated end and has continuum many ends Pp-almostsurely.Organization: The chapter is organized as follows. In Section 3.2 somepreliminary background material is provided. In Section 3.3 results aboutgeometry are proved. For the supercritical case: Theorem 3.1.1 is proved inSection 3.3.2, Theorem 3.1.2 is proved in Section 3.3.2. For the subcriticalcase, Theorems 3.1.6 and 3.1.7 are proved in Section 3.3.2. For percolation,Theorems 3.1.8–3.1.10 are proved in Section 3.4. Some open problems arediscussed in Section PreliminariesIn this Section we gather some results which we are going to need. Thereader might skip this Section in the first reading and come back to it whenit is referred to in the subsequent Sections.613.2. Preliminaries3.2.1 Free triangulationsRecall the Boltzmann distribution defined in Definition 2.5.1. Also recall afreely distributed triangulation with parameter q of an m-gon will be referredto as a free triangulation with parameter q of an m-gon. We will needfew estimates on free triangulations in this chapter.Let Im(q) denote the number of internal vertices of a freely distributedtriangulation of an m-gon with parameter q.Proposition 3.2.1. Fix θ ∈ [0, 1/6) and let q = θ(1− 2θ)2. Fix an integerm ≥ 2.(i) E(Im(q)) = (m−1)(2m−3)2θ(1−6θ)m+6θ =4θ(1−6θ)m+O(1)(ii) V ar(Im(q)) = (m−1)(2m−3)m(1−2θ)((1−6θ)m+6θ)2(1−6θ) =2(1−2θ)(1−6θ)3m+O(1)Proof. Note the following identityE(Im(q)) =q(Z ′m(q))Zm(q)= q(logZm)′(q)Putting q = θ(1− 2θ)2 and using Proposition 2.5.2, we obtain after an easycomputationE(Im(q)) =(m− 1)(2m− 3)2θ(1− 6θ)m+ 6θThe proof of (ii) is a similar computation and is left to the reader to verify.We would need the following estimates whose proof is postponed to ap-pendix A.Lemma 3.2.2. Fix θ ∈ [0, 1/6) and suppose q = θ(1 − 2θ)2. Suppose Yis a variable supported on N \ {0} such that P(Y = k) ∼ ck−3/2 for someconstant c > 0. Then there exists positive constants cθ, c′θ depending upon θsuch that(i) P(Y + IY+1 > x) ∼ cθ√x(ii) E(Y + IY+1)1{Y+IY+1<x} ∼ c′θ√xas x→∞.623.2. Preliminaries3.2.2 Stable random variablesThe theory of stable random variables play a vital role in our subsequentanalysis. Fix α ∈ (0, 2]. An independent sequence X1, X2, . . . is said tofollow a stable distribution of type α if Sn = X1 + . . .+Xn satisfiesSn(d)= n1/αXn + γnfor some sequence γn and the distribution of X1 is not concentrated around0. See for example [49] Chapter VI or [48] for more details.We shall be needing the following classical result. This can be found in[48].Theorem 3.2.3. Suppose X1, X2, . . . are i.i.d. with a distribution that sat-isfies1. limx→∞ P(X1 > x)/P(|X1| > x) = θ ∈ [0, 1]2. P(|X1| > x) = x−αL(x)where α < 2 and L is slowly varying. Let Sn = X1 + . . . Xn. an = inf{x :P(|X1| > x) ≤ n−1} and bn = nE(X11|X1|≤an). As n→∞ (Sn−bn)/an → Yin distribution where Y is a stable random variable of type α.We are specially interested in the case α = 1/2. It turns out that we canadd a constant to a variable following a stable distribution of type α whereα 6= 1 such that γn = 0 for all n in its definition (see [49]). After such acentering, its density can be explicitly written as(2pix3)−1/2 exp(−1/2x)1{x>0} (3.2.1)This is known as the Le´vy distribution.3.2.3 PeelingLet us recall the concept of peeling introduced in Section 2.4. We only focuson triangulations in this section and to that end let us investigate whathappens when we perform peeling on triangulations.Suppose we have a sample T from Hα for some α ∈ (0, 1]. We willconstruct a growing sequence of simply connected sub-maps Pn containingthe root with the complement Tn defined as the set of faces in T not in Pnalong with the edges and vertices incident to them (note that Tn is also ahalf planar triangulation because Pn is simply connected.) Next we choose633.3. Geometryan edge en on the boundary of Tn and reveal the triangle incident to it alongwith all the finite components of the complement.Start with P0 to be empty and T0 = T . At the nth peeling step, we pickan edge en on the boundary of Tn and add the triangle in Tn incident to enalong with the finite components of the complement (if there is any) to Pn+1.Define Tn+1 to be the complement of Pn+1. For all n, Tn is distributed as Hαvia the domain Markov property. By abuse of notation, sometimes we shallre-root Tn on some other edge on the boundary of Tn and the distribution ofTn does not change by translation invariance. Further note that the trianglerevealed in the peeling step is either of the form described by an α-step oris of the form (L, i) or (R, i) for i ≥ 1 (see Figure 3.2.) Recall that if thepeeling step is of the form (L, i) or (R, i), the finite triangulation of the (i+1)gon separated from infinity by the triangle incident to en is distributed as afree triangulation of the i+ 1-gon with parameter given αβ where β is givenby eqs. (2.8.2) and (2.8.3).Recall also that the choice of en depends only on Pn and we are free tochoose any edge on the boundary of Pn for the next peeling step. We shallexploit this freedom of choice of en to prove the different results stated inSection Geometry3.3.1 Peeling algorithmRecall from the discussion in Section 3.2.3 that we are free to choose the edgeen on which we apply the nth peeling step. We now describe an algorithmicprocedure to choose the edges in such a way that at a certain (random)step, we reveal the hull of the ball of radius r around the root vertex. Thealgorithm follows the idea developed in [7] for analyzing the volume growthof the full plane UIPT, but we modify it appropriately for the half planeversions. We take up the notations of Section 3.2.3. Further recall that thehull of the ball of radius r around the root is denoted by Br.Recall that the internal boundary of a simply connected sub-map is theset of vertices and edges in the sub-map which is incident to at least onefinite face which is not in the sub-map. Let τ0 = 0 and let P0 be the rootvertex. Suppose we have defined a (random) time τr so that Pτr = Br forsome r ≥ 1. In particular, the internal boundary of Pτr is ∂Br. The idea isto iteratively peel the edges in ∂Br till none of the vertices in ∂Br remainin the boundary of Tn.643.3. GeometryPnTnPnFree triangulation ofa 3-gon TnPnFree triangulation of a 5-gonFigure 3.4: An illustration of peeling at the nth step. The grayarea denote the peeled part Pn. The red vertices and edges denotethe internal boundary of Pn.Algorithm: Suppose we have described the process up to step n suchthat τr ≤ n < τr+1. Now look for the left most vertex v of ∂Br whichremains in the internal boundary of Pn at step n and perform a peelingstep on the edge to the right of v in the boundary of Tn. If there is novertex v of ∂Br left in the boundary of Tn+1, define n+ 1 = τr+1 andPτr+1 = Br+1.The algorithm proceeds in such a way that for every vertex of ∂Br, wekeep on peeling at an edge incident to that vertex until it goes inside therevealed map. Hence at step τr, we reveal nothing but the hull of the ballof radius r for every r ≥ 1. Recall that internal boundary of Pn is the set ofedges and vertices which are incident to at least one face not in Pn. Let Xndenote the number of vertices in the internal boundary of Pn at the nth step.It is easy to see that Xn itself is not a Markov chain because the transitionprobabilities very much depend on the position of the edge on which we arepeeling. However, a bit of thought reveals that Xτr is in fact an irreducibleaperiodic Markov chain. We record the above observations in the followingProposition.Proposition 3.3.1. For r ≥ 1, Pτr described in the algorithm above is thesame as Br and Xτr = |∂Br|. Also, the sequence {Xτr}r≥1 is an irreducibleaperiodic Markov chain.Following the idea of [7], we estimate the size of the boundary by ana-lyzing Xn separately for α in subcritical and supercritical regimes. Observethat ∆Xn = Xn+1 − Xn ≤ 1 for any n. Note also that ∆Xn has differentbehavior of tails in the subcritical and supercritical regimes:Hα(∆Xn < −i) ≈{i−1/2 α < 2/3exp(−ci) α > 2/3(3.3.1)653.3. Geometryfor some constant c > 0 and a large non negative integer i < Xn. Thus,conditioned on Xn, ∆Xn has negative expectation if Xn is not too small inthe subcritical regime. This tells us that Xn has a drift towards 0 as soonas it gets large which implies it should be a tight sequence. However in thesupercritical regime Lemma 3.3.2 below shows that ∆Xn has positive con-ditional expectation, which implies that Xn grows linearly. This constitutesthe key point of difference between the two regimes which is made rigorousin the following Sections 3.3.2 and SupercriticalIn this subsection, we prove Theorem 3.1.1 and hence we assume α > 2/3throughout this subsection. Further, we shall also borrow the notations fromSections 3.2.3 and 3.3.1.As mentioned before, we will perform the peeling algorithm performed inSection 3.3.1 and analyze the quantity ∆Xn. To that end, we shall approx-imate ∆Xn by a sequence of auxiliary variables X˜n such that the variables∆X˜n = ˜Xn+1 − X˜n for n ≥ 1 form an i.i.d. sequence with ∆X˜n = −i ifa step of the form (L, i) or (R, i) occurs in the (n + 1)th peeling step and∆X˜n = 1 if an α step occurs in the (n + 1)th peeling step. Clearly, fromdefinition, Xn > X˜n since if in a peeling step the triangle revealed has thethird vertex not on the internal boundary of Pn, ∆Xn > ∆X˜n.Because of the exponential tail, the variables ∆X˜n in the supercriticalregime has finite variance. Further its expectation turns out to be positive.Lemma 3.3.2.E(∆(X˜n)) =√3α− 2√α (3.3.2)In particular, E(∆(X˜n)) > 0 for α ∈ (2/3, 1).Proof of Lemma 3.3.2 is an easy computation which is provided in ap-pendix A.Lemma 3.3.3. There exists a constant c > 0 such that almost surelyc < lim inf Xnn ≤ lim supXnn ≤ 1 (3.3.3)Proof. lim supXn/n ≤ 1 follows trivially because ∆Xn ≤ 1. Since the stepsin ∆(X˜i) are i.i.d. with finite mean, strong law of large numbers imply thatX˜n/n →√3α− 2√α > 0 almost surely as n → ∞. The required lowerbound now follows from the fact that Xn > X˜n by definition.663.3. GeometryRecall that step τr in the peeling algorithm marks the step when the hullof the ball of radius r is revealed. We now state some estimates on τr. Thefirst part of the following Lemma 3.3.4 is essentially rephrasing Lemma 4.2of [7]. Further, we remark that Lemma 3.3.4 is valid for any α ∈ [0, 1) andwe shall use it again when dealing with the subcritical case in Section 3.3.3.Lemma 3.3.4. For any r ≥ 0,(i) There exists some constants A > 1 and A′ > 0 such that for anyinteger n ≥ 1,P(∆τr > An||Xτr | = n) < exp(−A′n) (3.3.4)(ii) For any integer k ≥ 1 and integers 1 ≤ l ≤ l′P(∆τr > k||Xτr | = l) ≤ P(∆τr > k||Xτr | = l′).Proof. The number of steps required for a vertex on ∂Br to go inside therevealed map is a geometric random variable (we wait till a step of the form(L, i) occurs for some i ≥ 1.) Thus ∆τr is a sum of at most n i.i.d. geometricvariables. Thus part (i) follows from a suitable large deviations estimate.An easy coupling argument can be used to prove part (ii). To see this, letus consider two marked contiguous segments S with l vertices and S′ withl′ vertices on the boundary with the left most vertex being the root vertex.We can now perform the peeling algorithm described in Section 3.3.1 untilall the vertices in S is inside the revealed map. Clearly, if at some step,some vertices of S are still not swallowed by the revealed map, then somevertices of S′ are also not swallowed.Lemma 3.3.4 along with Lemma 3.3.3 shows that almost surely for somepositive constants a, a′ and for all but finitely many ra′τr+1 < Xτr+1 < ∆(τr) < aXτr < aτr. (3.3.5)For the first and last inequality in the above display, we used Lemma 3.3.3,for the third inequality, we used Lemma 3.3.4 and for the second inequalitywe observe that the vertices of ∂Br+1 are added only one at a time. This inturn shows thatLemma 3.3.5. There exists constants 1 < c < C such that almost surelylim inf c−rτr = ∞lim supC−rτr < ∞673.3. GeometryLet Vn denote the number of vertices in the revealed map Pn in the nthstep of the peeling algorithm. Our main goal is to estimate Vτr in orderto prove Theorem 3.1.1. Now suppose Sn = Vn − Xn. Then it is easyto see just from the description of the algorithm that Sn is a sum of ni.i.d. random variables each of which is distributed as Y + IY+1 where Y =−∆X˜n1∆X˜n 6=1 and IY+1 is distributed as a the number of internal verticesof a free triangulation of a (Y + 1)-gon with parameter αβ. Notice thatthis definition makes sense for all values of α, not for just the supercriticalregime. However in the supercritical regime, the exponential tail of Y entailsthat Y has finite expectation. Further conditioned on Y , the expectation ofIY+1 is 4θY/(1 − 6θ) + O(1) via Proposition 3.2.1 where θ is given by therelation θ(1− 2θ)2 = αβ. Thus Y + IY+1 has finite expectation.Proof of Theorem 3.1.1. Recall that |Br| = Vτr . Now since Sn is a sum ofi.i.d. random variables with finite mean, Sn/n converges almost surely. Thisfact along with (3.3.5) and Lemma 3.3.5 completes the proof.Anchored expansionNow we turn to the proof of Theorem 3.1.2.Recall that internal boundary of a simply connected sub-map with asimple boundary is the set of vertices and edges in the sub-map which isincident to at least one face which do not belong to the sub-map. Also recallthat distance between two vertices on the boundary along the boundary isthe number of edges on the boundary between the vertices. Clearly, distancealong the boundary is at most the graph distance in the whole map. Weshow in the following lemma that the graph distance between vertices onthe boundary in the whole map is at least linear in the distance betweenthem along the boundary.Lemma 3.3.6. Let v be a vertex at distance n ≥ 1 along the boundaryfrom the root vertex on a map with law Hα where α ∈ (2/3, 1). Thereexists a constant t(α) > 0 depending only on α such that the probabilityof the distance between v and the root being smaller than t(α)n is at mostexp(−cn) for some c > 0.Proof. Let us assume without loss of generality that v is to the right of theroot vertex. We use the peeling algorithm described in Section 3.3.1 andreveal the hulls of radius r for r ≥ 1 around the root vertex. Recall thenotations Pn which denotes the revealed map after n peeling steps and τrwhich denotes the step in which we finish exploring the hull of radius r. Now683.3. Geometryk vertices< tk verticesi verticesj verticesk verticesFigure 3.5: Left: An illustration of a t-bad segment. The segmentconsisting of blue vertices is a t-bad segment. The gray area issome fixed finite triangulation. Right: The red vertices form a(k, i+ j)-separating loopthe vertices of the boundary to the right of the root vertex which goes insidethe peeled map is entirely determined by the last step and is easily seen tohave exponential tail and a finite expectation depending only on α. Hencethe probability that v is in the hull of radius at most tn around the rootvertex is at most the probability of the event that the sum of tk independentvariables with finite expectation and exponential tail is larger than k. Thelatter event has probability exp(−ck) for some c > 0 if t is small enough(depending only on α) by a suitable large deviations estimate.A connected segment X on the boundary of the map containing the rootedge is said to be a t-bad segment for some t > 0 if there exists a simplyconnected sub-map Q with a simple boundary whose intersection with theboundary of the map is X and the internal boundary has at most t|X|vertices (see Figure 3.5).Lemma 3.3.7. For small enough t (depending on α), there exists finitelymany t-bad segments almost surely.Proof. Let us fix a connected segment X of length k containing the rootedge. The event that X is t-bad is contained in the event that the distance(in the whole map) between the leftmost and the rightmost vertices in Xis at most tk. If t > 0 is small enough this event has probability at mostexp(−ck) for some c > 0 using Lemma 3.3.6 and translation invariance.Since there are at most k connected segments of length k containing theroot, the rest of the proof follows from Borel-Cantelli.We restate a Lemma which was proved in Chapter 2.693.3. GeometryLemma 3.3.8. Fix α ∈ [0, 1) and β is given by eqs. (2.8.2) and (2.8.3). LetQ be a simply connected triangulation with k + i+ j vertices and boundarysize i+ j. Let T be a sample from Hα. The event that Q is a sub-map of Twith a marked connected segment with i vertices on the boundary of Q beingmapped to a marked connected segment on the boundary of T with i verticesand no other vertex of Q being mapped to the boundary of T has probabilityαk+jβi+k−2We call a simple cycle in a half planar map a (k, l) separating loop if ithas l vertices, its intersection with the boundary forms a connected segmentcontaining the root edge and it separates k internal vertices of the map frominfinity.Lemma 3.3.9. Fix α ∈ (2/3, 1). There exists a constant c(α) dependingupon α such that Hα-almost surely there are finitely many (k, l)-separatingloops with l < c(α)k.Proof. Recall that φn,m denotes the number of triangulations of an m-gonwith n internal vertices. From Lemma 3.3.8 and union bound, the probabil-ity that there exists a (k, l)-separating loop with i vertices on the boundaryof the map is at mostiφk,lαk+j(α(1− α)2)k+i−2(3.3.6)where the factor i comes from the fact that the root can be any one ofthe edges of the intersection of the separating loop with the boundary. Letj = l − i. Now it is easy to see from eq. (2.12.1) thatφk,l < (27/2)k9l(1 + 2l3k)2l+3kk−5/2√l (3.3.7)Combining (3.3.6) and (3.3.7) and summing over i < l where l < tk, we getthat the probability of existence of a (k, l)-separating loop is at mostl5/2k−5/2 ·(27α2(1− α)4)k·(9α(1− α)2)l·(1 + 2t3)(2t+3)k·( 21− α)tk< exp(−ck) (3.3.8)for some constant c > 0 if t is small enough. To see this, observe thatα2(1−α) < 4/27 and α(1−α) < 2/9 if α ∈ (2/3, 1). The sum of the boundin (3.3.8) over k > l/t and then over l is finite. The rest of the proof followsfrom Borel-Cantelli.703.3. GeometryFor S ⊂ V (G), recall that the notation |S|E denotes the sum of thedegrees of the vertices in S and ∂ES denotes the number of edges which areincident to one vertex in S and another in G \ S.Proof of Theorem 3.1.2. Consider a connected set of vertices S containingthe root vertex such that |S|E > n and suppose ∂ES < t2|S|E for somet > 0. By an abuse of notation, denote by S the finite map induced by Sand without loss of generality assume it contains the root edge. Add to Sall the faces which share at least one vertex with S along with the edgesand vertices incident to it. Then add all the connected finite components ofthe complement and call the resulting finite triangulation S. Note that S issimply connected with a simple boundary with |S| > n and the vertices andedges in the boundary of S form a separating loop. Suppose the internalboundary of S has j vertices. From the definition of ∂ES: j < ∂ES < t2|S|E .Let i be the number of vertices of S on the boundary of the map and supposek = |S| − i− j. Now the assumption ∂ES < t2|S|E and Euler’s formula forS yieldsk > 1− 5t26 |S|E −2i3 (3.3.9)If i < t|S|E then i+j < tCk for some universal constant C > 0 using (3.3.9)which can occur for finitely many n almost surely via Lemma 3.3.9 if t issmall enough. If i > t|S|E then j < ti and this can occur for finitely manyn almost surely via Lemma 3.3.7.Proofs of Lemmas 3.3.7 and 3.3.9 and Theorem 3.1.2 in fact says thatthe probability of the existence of a set with small boundary containing theroot vertex is exponentially small. We record it here for future reference.Proposition 3.3.10. There exists a t > 0 depending upon α such that theprobability that there exists a connected set of vertices S containing the rootvertex such that |S|E > n and ∂ES < t|S|E is at most exp(−cn) for somec > SubcriticalIn this section we prove Theorem 3.1.6. We shall use the notations of Sec-tions 3.3.1 and 3.3.2 and α ∈ [0, 2/3) throughout this section. Recall that inthis regime, probability that a peeling step of the form (L, i) or (R, i) occursfor i ≥ k is roughly k−1/2.713.3. GeometryBoundary size estimatesTo understand the boundary sizes, we need to understand the variables Xτrfor r ≥ 1. As a warm up we prove Proposition 3.1.4 first.Proof of Proposition 3.1.4. From the definition, Xn ≤ n+2 for all n ∈ N. Ifat step numbers 2k and 2k+1, events: ∪j>2k+2{(R, j)} and ∪j>2k+2{(L, j)}happen respectively then X2k+2 = 2. But this event has probability at leastc/k for some c > 0 and for different k’s these events are independent by thedomain Markov property. The proof follows by Borel-Cantelli.We know via Proposition 3.3.1 thatXτr is an irreducible aperiodic Markovchain with state space a N \ {0, 1}. We now show that {Xτr}r≥1 is a tightsequence with exponential tail. Suppose Nk for k ≥ 0 denote the number ofvertices in the internal boundary of Pτr+k which do not belong to ∂Br.Lemma 3.3.11. For any r ≥ 0, k ≥ 1,n ≥ 1P(Nk > n|Xτr) < exp(−Bn)for some positive constant B. In particular, this bound is independent of theconditioning.Proof. First fix an n0 large enough such thatα− 12bn0/2c∑i=1ipi < −εfor some ε > 0 where pi is given by eq. (2.8.2) (observe that such a choice ofn0 exists due to the heavy tail of pi.) The above choice of n0 depends onlyon α. Now choose an integer n > n0. Let ∆Nk := Nk+1 − Nk for k ≥ 1.Observe that Nk increases by at most 1 in any step because of the evolutionof Xk and N0 = 0. This has several implications. Firstly, this implies thatit is enough to consider k > n or otherwise the requested probability is 0.Secondly, if Nk > n, then for some integer 1 ≤ j ≤ k, Nj is equal to n0. LetM = max{1 ≤ j ≤ k : Nj = n0}. Finally, we must have M ≤ k − n + n0.Now note thatP(Nk > n,M = j) < P(Ni ≥ n0 for all j ≤ i ≤ k) (3.3.10)Now for any i > j, conditioned on Ni ≥ n0, there are at least n0/2 verticesof the internal boundary of Pτr+k which do not belong to ∂Br either to theleft or right of the edge we perform the (i+ 1)th peeling step because of the723.3. Geometryway the exploration process evolves. Hence it is clear that conditioned onNi ≥ n0, ∆(Ni) is dominated by a variable D with E(D) < −ε because ofthe choice of n0. Thus,P(Ni ≥ n0 for all j ≤ i ≤ k) < P(k−j∑i=1Di > 0)< γk−j (3.3.11)for some 0 < γ < 1 depending only on n0 where {Di}i≥1 are i.i.d. copies ofD and the last inequality of (3.3.11) follows from suitable large deviationsestimate. Now using (3.3.10) and (3.3.11),P(Nk > n|Xτr) =k−n+n0∑j=1P(Nk > n,M = j) <k−n+n0∑j=1γk−j < exp(−Bn)(3.3.12)for some B > 0 for large enough n. Decrease B suitably so that the requestedbound is true even for smaller values of n.We remarked before that Lemma 3.3.4 is true for any value of α. Weshall now use this fact and induction to prove Theorem 3.1.6.Proof of Theorem 3.1.6. First, get hold of the constants A > 1, A′ > 0, B >0 such that Lemma 3.3.4, part (i) and Lemma 3.3.11 are true for n ≥ 1.Now fix a C such that 0 < C < B. Then choose a large N to ensure thatfor all n > N ,max{exp(−A′n2), An2 exp(−Bn), exp(−Cn2)} < 13 exp(−Cn).We shall prove that for all n > N , the Theorem is true for the above choice ofC > 0 by induction on r. Note that for r = 0, the Theorem is true triviallysince Xτ0 = X0 = 1. Now assume, the Theorem is true for r′ = r − 1for any n > N for above choice of C,N . Now recall the notation Nj fromLemma 3.3.11 and observe that Nj = Xj for j ≥ ∆τr. Clearly, for n > N ,using Lemma 3.3.11P(Xτr > n,∆τr−1 = j|Xτr−1) < P(Nj > n|Xτr−1) < exp(−Bn) (3.3.13)Now for any choice of n > N , using (3.3.13),P(Xτr > n) < P(Xτr−1 > n2) + P(∆τr−1 > An2|Xτr−1 ≤ n2) +An2∑j=1exp(−Bn)< exp(−Cn2) + exp(−A′n2) +An2 exp(−Bn) (3.3.14)< exp(−Cn) (3.3.15)733.3. Geometrywhere (3.3.14) follows from induction step, Lemmas 3.3.4 and 3.3.11. Also,(3.3.15) follows from the choice of N . The proof is completed by induction.Hull VolumesFirst, we wish to estimate the growth rate of τr. Note that conditioned onXτr the distribution of ∆(τr) depends only on Xτr and not r. It is easy to seethat Zr := (Xτr ,∆τr) is an irreducible aperiodic Markov chain. Using Theo-rem 3.1.6 and Lemma 3.3.4 it is not difficult to see that the sequence {Zr}r≥1forms a tight sequence. Hence, Zr has a stationary probability distribution.Let us denote the marginal of the second coordinate of this stationary dis-tribution by pi. It is also easy to see using Theorem 3.1.6 and Lemma 3.3.4that pi has exponential tail and hence finite expectation. If we start theMarkov chain {Zr}r≥1 from stationarity, ergodic theorem gives us that τr/rconverges almost surely to∑i≥0 ipi(i). However if we start the Markov chain{Zr}r≥1 from any fixed number, it is still absolutely continuous with respectto the corresponding chain starting from stationarity. This argument provesLemma 3.3.12. Almost surely,τrr →∑i≥0ipi(i)Recall the notation Y,Z, {Sn}n≥1 from Section 3.3.2. Recall that thevolume of the triangulation revealed at the n-th step of peeling is given byVn = Sn +Xn. We wish to estimate Vτr = |Br|. Recall that Sn is a sum ofn i.i.d. copies of W where W = Y + IY+1. From Lemma 3.2.2 part (i), weconclude P(W > x) ∼ cαx−1/2 as x → ∞ for some constant cα dependingon α.Lemma 3.3.13. For some sequence of real numbers an and bnVn − bnan⇒ S (3.3.16)where S follows a stable distribution of type 1/2. Also an ∼ cn2 and bn ∼c′n2 for some positive constants c, c′.Proof. Note that since Xn ≤ n and since Vn = Sn+Xn, it is enough to provethe result with Vn replaced by Sn. Since Sn is a sum of i.i.d. sequence ofvariables, each of which is distributed as W , we apply Theorem 3.2.3. Recallfrom Theorem 3.2.3, the centering sequence an = inf{t : P(W > t) ≤ 1/n}.743.4. PercolationRecall that we also obtained the tail estimate of W , P(W > x) ∼ cαx−1/2. Itis easy to see from this tail estimate of W that an ∼ c2αn2. The asymptoticsof bn is provided in Lemma 3.2.2 part (ii).We need one final lemma before we prove the theorem. Recall the dis-tribution pi from Lemma 3.3.12.Lemma 3.3.14. Vτr/Vbγrc converges in probability to 1 where γ =∑i≥0 ipi(i).Proof. Observe that it is enough to prove Sτr/Sbγrc converges to 1 in prob-ability. Notice that since Sr is nondecreasing in r, for any η > 0 and ε > 0,we haveP(|Sτr/Sbγrc − 1| > η, (1− ε)γr < τr < (1 + ε)γr)< P(Sb(1+ε)γrc − Sb(1−ε)γrcSbγrc> η, (1− ε)γr < τr < (1 + ε)γr)(3.3.17)Recall that a stable law is absolutely continuous (see [49], Chapter VI.1,Lemma 1) and hence via Lemma 3.3.13 we can conclude both {Sr/r2}r≥1and {r2/Sr}r≥1 form a tight sequence in r. Further notice that τr/γr → 1almost surely via Lemma 3.3.12. Combining all these pieces, it is easy tosee that for any η > 0, there exists an ε > 0 such that the right hand side ofeq. (3.3.17) can be made smaller than any prescribed δ > 0 for large enoughr. The details are left to the reader.Proof of Theorem 3.1.7. Notice Vτr = |Br|. Also observeVτr − bbγrcabγrc=Vbγrc − bbγrcabγrc+Vbγrcabγrc( VτrVbγrc− 1)(3.3.18)The first term of eq. (3.3.18) converges to a stable random variable of type1/2 via Lemma 3.3.13. The second term in eq. (3.3.18) converges to 0in probability via Lemma 3.3.14. The proof follows combining these twofacts.3.4 PercolationIn this Section, we prove Theorems 3.1.8–3.1.10. We will use the peelingprocedure and use the notations Pn, Tn introduced in Section 3.2.3. Alongwith revealing the face on the edge we peel, we might also reveal the colorof the new vertex (if any) revealed. It will be useful to consider several753.4. Percolationboundary conditions, which specifies the colors of the boundary vertices. Ifwe consider a percolation configuration on the whole graph including theboundary vertices, we say it is a random i.i.d. boundary condition.Algorithm: We start with the root vertex black and every other vertexon the boundary white. At the n+1th step, we perform a peeling stepat the edge on the boundary of Tn with a black vertex to the right anda white vertex to the left. We stop at the nth step if there is no blackvertex left on the boundary of Tn.A simple topological argument shows that the event that the above al-gorithm stops is the same as the event that the black cluster containing theroot vertex is finite. Now consider the following variable B. If the peelingstep is an α-step and a black vertex is revealed set B = 1. If the peelingstep is of the form (R, i), set B = −i. Otherwise set B = 0. The followingLemma is a simple computation which essentially follows from Lemma 3.3.2.Lemma 3.4.1.Ep(B) = αp−12(α−√α√3α− 2) (3.4.1)In particular, Ep(B) > 0 if and only if p > 1/2(1−√3− 2/α).The following proof is essentially follows the idea of [10]. We add it forcompleteness. Recall the notation Tn from Section 3.2.3.Proof of Theorem 3.1.8( for pc). Assume the boundary condition: the rootvertex is black and the rest of the vertices on the boundary are white. Startwith B0 = 1 and suppose Bk is the number of black vertices left in theboundary of Tk. Clearly Bk+1 −Bk are i.i.d. with the same distribution asB. Lemma 3.4.1 shows that Bk eventually goes to 0 almost surely if and onlyif p ≤ 12(α−√α√3α− 2). Modifying the proof to a random i.i.d. boundaryis an easy exercise of imitating Proposition 9 of [10] and is left to the reader.The almost sure existence of a black cluster if p > 12(α−√α√3α− 2) followsfrom ergodicity of the map with respect to translation of the root as provedin Proposition 2.2.2.Corollary 3.4.2. With random i.i.d. boundary condition, Hα-almost surely,pu ≤ 1/2(1 +√3− 2/α) (3.4.2)763.4. PercolationProof. Assume p ≥ 1/2(1 +√3− 2/α). Consider the event E that there aretwo infinite black clusters. Then one of the components of the complementof one of them must be infinite. Then the vertices in this component whichconnect to the infinite black cluster must be white. This means that thereis also an infinite white cluster since the map is locally finite and one endedalmost surely. Since white clusters are finite almost surely in the givenregime of p (using Theorem 3.1.8 (i) and symmetry), E has probability0.One can define an interface between the black and white clusters of apercolation configuration. More precisely, there is a well defined path inthe dual configuration which separates the white and black clusters (seeFigure 1.4). We are interested in the interfaces which are connected tothe boundary. These are the interfaces which start on those edges on theboundary which have a black and a white vertex incident to it. Interfacesmark the boundary between a white and a black cluster on both its side. Aninterface might be finite or infinite. Finite interface separate finite clustersfrom infinity while infinite interfaces correspond to an infinite black clusteron one side and an infinite white cluster on the other. So in particular, ifp ∈ [0, pc] ∪ [pu, 1], every interface is finite almost surely.In the following exploration procedure The vertices whose colors havenot been revealed yet will be called free vertices.Algorithm 2: We start with the root vertex colored white, the vertexincident to the right of the root edge colored black and every othervertex on the boundary free. Now we start performing peeling on theroot edge.Suppose after n steps of peeling, the boundary of Tn consists of freevertices except for a finite contiguous white segment followed by afinite contiguous black segment to the right of the white segment. Wenow peel on the unique boundary edge of Tn connecting the black andwhite segments. If after a peeling step the third vertex of the facerevealed is free, we reveal its color. If the triangle revealed swallowsall the black vertices to the right (resp. white vertices to the left) andthe revealed third free vertex is white (resp. black), then we revealthe colors of the vertices along the boundary to the right (resp. left)of revealed third vertex until we find a black (resp. white) vertex.Notice that after such a step, we are again left with a boundary whichconsists of free vertices except for a finite contiguous white segmentfollowed by a finite contiguous black segment to its right. We can now773.4. Percolationcontinue this procedure.Suppose we have a random i.i.d. boundary condition. Let I be the eventthat there is an infinite interface starting from the root edge.Lemma 3.4.3. If p ∈ (1/2(1−√3− 2/α), 1/2(1 +√3− 2/α)), thenPp(I) > 0.Proof. Suppose we are on the event that the root vertex is colored white, thevertex incident to the right of the root edge colored black. Now we performalgorithm 2. Let Bk be the size of the black connected segment and Wk bethat of the white connected segment at the kth step of the algorithm. Recallthe definition of the variable B defined in Lemma 3.4.1. Conditioned on Bk,Bk+1 stochastically dominates a variable which has the same distribution as(Bk + B)+ + 1{Bk+B≤0} and Bk+1 − Bk are independent for every k. Thedomination comes from the fact that if a white segment is swallowed, weadd a geometric p number of black vertices to Bk which we ignore in theprescribed expression. Now for p in the given range, E(B) > 0, hence Bkforms a random walk with a positive drift. This implies Bk → ∞ almostsurely. Similarly by symmetry, Wk → ∞ almost surely for p in the givenrange. All this implies the event {Bk > 1,Wk > 1 for all k ≥ 0} has positiveprobability. But Bk > 1 and Wk > 1 for all k ≥ 0 implies that the interfacewe started with is infinite. This completes the proof.Recall the notations W∞k , B∞k the number of black and white infiniteclusters respectively which has least one vertex on the boundary withindistance k along the boundary from the root vertex.Proof of Theorem 3.1.8 (for pu) and Theorem 3.1.9. Fix a number p in thefollowing range: p ∈ (1/2(1−√3− 2/α), 1/2(1+√3− 2/α)). Let Ek be thenumber of edges within distance k from the root edge along the boundarysuch that there is an infinite interface starting from that edge. Now notethat the measure Pp is ergodic with respect to translation of the root. HenceBirkhoff’s ergodic theorem implies that almost surely,Ekk → Pp(I). (3.4.3)Note that W∞k +B∞k = Ek + 1 and also |W∞k −B∞k | ≤ 1. Hence,W∞k /k → ρ and B∞k /k → ρwhere ρ = Pp(I)/2 > 0 from Lemma 3.4.3. This proves Theorem 3.1.9 aswell as shows that pu ≥ 1/2(1 +√3− 2/α).783.4. PercolationNow we turn to the proof of Theorem 3.1.10. We will need the followingtechnical Lemma which can be easily shown using optional stopping The-orem. For details, we refer the reader to [51] Corollary 9.4.1 and Exercise9.13.Lemma 3.4.4. Let X1, X2, . . . be an i.i.d. sequence of random variablessuch that E(X1) > 0 and E(exp(λX1)) exists for values of λ in a neighbor-hood around 0. Let Sn =∑ni=1Xi. Then for any k > 0 there exists someconstant c > 0 such thatP(∪n≥1{Sn ≤ −k}) < exp(−ck)Lemma 3.4.5. Fix p ∈ (pc, pu). The Pp probability that the root vertexis contained in an infinite black cluster with one end or an infinite whitecluster with one end is 0.Proof. Suppose without loss of generality the color of the root vertex isblack and we shall prove that the probability that this vertex is containedin an infinite black cluster with one end is 0. Reveal vertices to the leftand right of this vertex along the boundary until we find a white vertex onboth sides. In the exploration we describe now, there will be a contiguousfinite white segment followed by a contiguous finite black segment followedby a contiguous finite white segment on the boundary and the rest of thevertices on the boundary are free. We shall peel alternately at the two edgesconnecting the black and the white segments to the left and to the right.If at any step we swallow all the black vertices we stop. If we swallow allthe white vertices to the left (resp. to the right), we reveal black verticesto the left (resp. to the right) along the boundary until we find a whitevertex. Consider the sequence of maps Tn. Define the root edge of this mapto be the same root edge as in the previous step if it has not been swallowedin that step. If it is swallowed, define the edge in the middle of the blacksegment in the boundary of Tn oriented from left to right to be the new rootedge.Lemma 3.4.6. The root edge is swallowed finitely many times almost surelyin the above described exploration.Proof. Notice that on the event we stop the exploration, the Lemma is trueby definition. Let Ln (resp. Rn) be the distance between the root vertexand edge to the left (resp. right) on which we perform the nth peeling stepin the above described exploration and let Bn = Ln + Rn be the length ofthe black segment. Clearly, the sequence {∆Bn}n≥1 is an i.i.d. sequence of793.4. PercolationTnT∞n→∞Figure 3.6: An illustration of the proof of Lemma 3.4.5. The grayarea to the left denotes the revealed part in the exploration.variables with each of which is distributed as B. Recall that B has positiveexpectation in the given regime of p (using Lemma 3.4.1). Hence usingstandard large deviation estimates, on the event that we do not stop theexploration, the probability of Bn ≤ tn for small enough t has probabilityat most exp(−cn) for some constant c > 0.Now consider the event En that the root edge is swallowed in the nthstep and is swallowed again in some step after the nth step. On the eventBn > tn if the root edge is swallowed in the nth step, then by descriptionof the exploration both Ln and Rn are at least tn/2 − 1. If the root edgeis swallowed again, then either {Lk}k≥n or {Rk}k≥n has to reach 0 startingfrom at least tn/2−1. This event has probability at most exp(−c′n) for somec′ > 0 via Lemma 3.4.4 since Ln as well as Rn has i.i.d. increments withpositive expectation in every alternate step until the root edge is swallowed.Combining the pieces, we see that En has probability at most exp(−c′′n) forsome c′′ > 0 which means En occurs for finitely many n by Borel-Cantellilemma. This completes the proof.Let T be a map with law Pp and we perform the above exploration. LetBn be the number of black vertices on the boundary of Tn. On the eventthat Bn → ∞, Tn converges almost surely to a sub map T∞ of T sincethe root edge is swallowed finitely often almost surely via Lemma 3.4.6(see Figure 3.6). However, on the event Bn →∞, from the domain Markovproperty, the distribution of the map Tn converges to a map with law Pp withall boundary vertices black and the rest of the vertices are not revealed. Thismap almost surely contains an infinite white cluster with the given range ofp via Theorem 3.1.8. However this means that the cluster containing theroot has at least two ends almost surely on the event that the cluster is803.5. Open questionsinfinite.Corollary 3.4.7. Every infinite cluster does not contain an isolated endalmost surely.Proof. We prove the corollary for an infinite cluster containing the rootvertex. The proof for any infinite cluster is an easy exercise using the domainMarkov property, and is left to the reader. Suppose with positive probabilitythere is an infinite cluster in T containing the root vertex which has anisolated end. This implies that with positive probability there exists an rsuch that T \Br(α) has an infinite cluster incident to the boundary with oneend. This is a contradiction because of Lemma 3.4.5 and domain Markovproperty.Proof of Theorem 3.1.10. Corollary 3.4.7 shows that each infinite cluster donot contain an isolated end. Since END is compact, the non-isolated pointsform a perfect subset via the Cantor Bendixson Theorem. Hence this impliesthat the set of ends has cardinality of the continuum. (see [67]).3.5 Open questionsWe conclude with several open problems for possible future research. InTheorem 3.1.1, it is shown that the volume growth is exponential. A naturalquestion is: what is the exact rate of growth of the volume? We expectsimilar behavior as exhibited by a supercritical Galton-Watson tree.Question 3.5.1. Suppose α ∈ (2/3, 1). Show that almost surely,log |Br(α)|r → cfor some constant c depending only on α. Show further that |Br(α)|/crconverges to some non-degenerate random variable.In Theorem 3.1.10 it is shown that the supercritical percolation clus-ters in the regime p ∈ (pc, pu) have uncountably many ends. It would beinteresting to know how a supercritical percolation cluster behaves.Question 3.5.2. Fix α ∈ (2/3, 1) and p ∈ (pc, pu). Does the supercriticalpercolation cluster have exponential volume growth? Anchored expansion?Is the simple random walk on it transient?The key to understand the supercritical cluster in this regime is to under-stand if the supercritical clusters have long thin cutsets which kills anchoredexpansion.81Chapter 4Unicellular maps: large scalestructure3 This chapter is concerned with looking into the large scale structure ofunicellular maps with genus proportional to the number of edges as thenumber of edges becomes large. In particular, we prove in Theorem 4.1.1and Corollary 4.1.2 that the typical distances and diameter are roughlylogarithmic in the number of edges. We also show that the map is locallyplanar and prove Theorem 4.1.4 quantifying this fact. The motivation forstudying these maps is discussed in Section 1.6.Let us first perform a small calculation. Suppose v is the number ofvertices in a unicellular map of genus g with n edges. Then Euler’s formulayieldsv − n = 1− 2g (4.0.1)Observe from eq. (4.0.1) that the genus of a unicellular map with n edgescan be at most n/2. We are concerned in this chapter with unicellular mapswhose genus grows like θn for some constant 0 < θ < 1/2. Specifically, weare interested in the geometry of a typical element among such maps as nbecomes large.4.1 Main resultsRecall Ug,n denotes the set of unicellular maps of genus g with n edges andlet Ug,n denote a uniformly picked element from Ug,n for integers g ≥ 0and n ≥ 1. For a graph G, let dG(., .) denote its graph distance metric.Our first main result shows that the distance between two uniformly andindependently picked vertices from Ug,n is of logarithmic order if g growslike θn for some constant 0 < θ < 1/2.3The results of this chapter are from [81].824.1. Main resultsFigure 4.1: On the left: a unicellular map of genus 2. On theright: its underlying graph.Theorem 4.1.1. Let {gl, nl}l be a sequence in N2 such that {gl, nl} →{∞,∞} and gl/nl → θ for some constant 0 < θ < 1/2. Suppose V1 and V2are two uniformly and independently picked vertices from Ugl,nl. Then thereexists constants 0 < ε < C (depending only on θ) such that(i) P(dUgl,nl (V1, V2) > ε log nl)→ 1 as l→∞.(ii) P(dUgl,nl (V1, V2) > C log nl) < c(nl)−3 for some c > 0.We remark here that in the course of the proof of part (i) of Theo-rem 4.1.1, a polynomial lower bound on the rate of convergence will beobtained. But since it is far from being sharp and is not much more en-lightening, we exclude it from the statement of the Theorem. For part (ii)however, we do provide an upper bound on the rate. Notice that part (ii)enables us to immediately conclude that the diameter of Ugl,nl is also oforder log n with high probability. For any finite map G, let diam(G) denotethe diameter of its underlying graph.Corollary 4.1.2. Let {gl, nl}l be a sequence in N2 such that {gl, nl} →{∞,∞} and gl/nl → θ for some constant 0 < θ < 1/2. Then there existsconstants ε > 0, C > 0 such thatP(ε log n < diam(Ugl,nl) < C log n)→ 1as n→∞.Proof. The existence of ε > 0 such that P(diam(Ugl,nl) > ε log n) → 1follows directly from Theorem 4.1.1 part (i). For the other direction, pickthe same constant C as in Theorem 4.1.1. Let N be the number of pairsof vertices (v, w) in Ugl,nl where the distance between them is least C log n.From part (ii) of Theorem 4.1.1, E(N) < cn−1l for some c > 0. Hence ENconverges to 0 as l→∞. Consequently, P(N > 0) also converges to 0 whichcompletes the proof.834.1. Main resultsIf the genus is fixed to be 0, that is in the case of plane trees, the ge-ometry is well understood (see [69] for a nice exposition on this topic.) Inparticular, it can be shown that the typical distance between two uniformlyand independently picked vertices of a uniform random plane tree with nedges is of order √n. The diameter of such plane trees is also of order √n.These variables when properly rescaled, converge in distribution to appro-priate functionals of the Brownian excursion. This characterization stemsfrom the fact that a plane tree can be viewed as a metric space and the met-ric if rescaled by √n (up to constants) converges in the Gromov-Hausdorfftopology (see [58] for precise definitions) to the Brownian continuum ran-dom tree (see [4] for more on this.) The Benjamini-Schramm limit in thelocal topology (see [13, 22] for definitions), of the plane tree as the numberof edges grow to infinity is also well understood: the limit is a tree with aninfinite spine with critical Galton-Watson trees of geometric(1/2) offspringdistribution attached on both sides (see Figure 1.2 and see [63] for details.)Thus Theorem 4.1.1 depicts that the picture is starkly different if thegenus of unicellular maps grow linearly in the number of vertices. The mainidea behind the proof of Theorem 4.1.1 is that locally, Ug,n behaves like asupercritical Galton-Watson tree, hence the logarithmic order. We believethat the quantity dUgl,nl (V1, V2) of Theorem 4.1.1 when rescaled by log nshould converge to a deterministic constant. Further, we also believe thatthe diameter of Ugl,nl when rescaled by log n should also converge to anotherdeterministic constant. This constant obtained from the rescaled limit of thediameter should be different from the constant obtained as a rescaled limitof typical distances. The heuristic behind this extra length of the diameter isthe existence of large “bushes” of order log n on the scheme of the unicellularmap (recall the definition of scheme in Chapter 1 and Figure 1.6), a behaviorreminiscent of Erdos-Renyi random graphs.Tools developed for proving Theorem 4.1.1 also helps us conclude thatlocally Ug,n is in fact planar with high probability which is our next mainresult. In fact, we are also able to quantify up to what distance from theroot does Ug,n remain planar. This will be made precise in the next theorem.A natural question at this point is what is the planar distributional limit ofUg,n in the local topology. This is investigated in Chapter 5.We now introduce the notion of local injectivity radius of a map. Re-call that a circuit in a planar map is a subset of its vertices and edges whoseimage under the embedding is topologically a loop. A circuit is called con-tractible if its image under the embedding on the surface can be contractedto a point. A circuit is called non-contractible if it is not contractible.844.1. Main resultsDefinition 4.1.3. The local injectivity radius of a planar map with rootvertex v∗ is the largest r such that the sub-map formed by all the verticeswithin graph distance r from v∗ does not contain any non-contractible circuit.In the world of Riemannian geometry, injectivity radius around a pointp on a Riemannian manifold refers to the largest r such that the ball ofradius r around p is diffeomorphic to an Euclidean ball via the exponentialmap. This notion is similar in spirit to what we are seeking in our situation.Notice however that a circuit in a unicellular map is always non-contractiblebecause it has a single face. Hence looking for circuits and looking for non-contractible circuits are equivalent in our situation.Theorem 4.1.4. Let {gl, nl} → {∞,∞} and gl/nl → θ for some constant0 < θ < 1/2 as l→∞. Let Igl,nl denote the local injectivity radius of Ugl,nl.Then there exists a constant ε > 0 such thatP (Igl,nl > ε log nl)→ 1as l→∞.The girth of a map is defined as the minimum of the circuit sizes in it.The girth of Ug,n also deserves some comment. It is possible to conclude viasecond moment method that the girth of Ugl,nl form a tight sequence. Thisshows that there are small circuits somewhere in the unicellular map, butthey are far away from the root with high probability.The main tool for the proofs is a bijection due to Chapuy, Feray andFusy ([34]) which gives us a connection between unicellular maps and cer-tain objects called C-decorated trees which preserve the underlying graphproperties (details in Section 4.2.1.) This bijection provides us a clear road-way for analyzing the underlying graph of such maps.From now on throughout this chapter, for simplicity, we shall drop thesuffix l in {gl, nl}, and assume g as a function of n such that g → ∞ asn→∞ and g/n→ θ where 0 < θ < 1/2.Overview of the chapter: In Section 4.2 we gather some useful pre-liminary results we need. Proofs and references of some of the results inSection 4.2 are provided in appendices B and C. An overview of the strat-egy of the proofs of Theorems 4.1.1 and 4.1.4 is given in Section 4.3. Part(ii) of Theorem 4.1.1 along with Theorem 4.1.4 is proved in Section 4.4. Part(i) of Theorem 4.1.1 is proved in Section 4.5.854.2. Preliminaries4.2 PreliminariesIn this section, we gather some useful results which we shall need.4.2.1 The bijectionChapuy, Fe´ray and Fusy in ([34]) describes a bijection between unicellularmaps and certain objects called C-decorated trees. The bijection describes away to obtain the underlying graph of Ug,n by simply gluing together verticesof a plane tree in an appropriate way. This description gives us a simplemodel to analyze because plane trees are well understood. In this sectionwe describe the bijection in [34] and define an even simpler model calledmarked trees. The model of marked trees will contain all the informationabout the underlying graph of Ug,n.For a graphG, let V (G) denote the collection of vertices and E(G) denotethe collection of edges of G. The subgraph induced by a subset V ′ ⊆ V (G)of vertices is a graph (V ′, E′) where E′ ⊆ E(G) and for every edge e ∈ E′,both the vertices incident to e is in V ′.A permutation of order n is a bijective map σ from the set {1, 2, . . . , n}to itself. As is classically known, σ can be written as a composition ofdisjoint cycles. The length of a cycle is the number of elements in thecycle. The cycle type of a permutation is an unordered list of the lengths ofthe cycles in the cycle decomposition of the permutation. A cycle-signedpermutation of order n is a permutation of order n where each cycle in itscycle decomposition carries a sign, either + or −.Definition 4.2.1 ([34]). A C-permutation of order n is a cycle-signedpermutation σ of order n such that each cycle of σ in its cycle decompositionhas odd length. The genus of σ is defined to be (n − N)/2 where N is thenumber of cycles in the cycle decomposition of σ.Definition 4.2.2 ([34]). A C-decorated tree on n edges is the pair (t, σ)where t is a rooted plane tree with n edges and σ is a C-permutation of ordern+ 1. The genus of (t, σ) is the genus of σ.The set of all C-decorated trees of genus g is denoted by Cg,n. One cancanonically order and number the vertices of t from 1 to n+1. Hence in a C-decorated tree (t, σ), the permutation σ can be seen as a permutation on thevertices of the tree t. To obtain the underlying graph of a C-decoratedtree (t, σ), any pair of vertices x, y whose numbers are in the same cycle ofσ are glued together (note that this might create loops and multiple edges.)864.2. Preliminaries1234 56 789101112131 3572 121110 468 913(a) (b) (c)(+)(−)(+)(+)(−)Figure 4.2: An illustration of a C-decorated tree. (a) A C-permutation σ where each cycle is marked with a different color.(b) A plane tree t with the vertices in the same cycle of σ joinedby an arrow of the same color as the cycle. Note that verticesnumbered 8 and 9 are fixed points in the C-permutation. (c) Theunderlying graph of the C-decorated tree (t, σ). The root vertex iscircled.The underlying graph of (t, σ) is the vertex rooted graph obtained from(t, σ) after this gluing procedure. So there are N vertices of the underlyinggraph of (t, σ), each correspond to a cycle of σ (see Figure 4.2). By Euler’sformula, if the underlying graph of (t, σ) is embedded in a surface such thatthere is only one face, then the underlying surface must have genus g givenby N = n+ 1− 2g.For a set A, let kA denote k distinct copies of A. Recall that underlyinggraph of a unicellular map is the vertex rooted graph whose embedding isthe map.Theorem 4.2.3. (Chapuy, Fe´ray, Fusy [34]) There exists a bijection2n+1Ug,n ←→ Cg,n.Moreover, the bijection preserves the underlying graph.As promised, we shall now introduce a further simplified model whichwe call marked tree to analyze the underlying graph of C-decorated trees.Let P denote the set of ordered N -tuple of odd positive integers which addup to n+ 1.Definition 4.2.4. A marked tree with n edges corresponding to an N -tupleλ = (λ1, . . . , λN ) ∈ P is a pair (t,m) such that t ∈ U0,n and m : V (t) → N874.2. Preliminariesis a function which takes the value i for exactly λi vertices of t for all i =1, . . . , N . The underlying graph of (t,m) is the rooted graph obtained whenwe merge together all the vertices of t with the same mark.Given a λ ∈ P, let Tλ(n) be the set of marked trees corresponding to λand let Tλ(n) be a uniformly picked element from it. Now pick λ from Paccording to the following distributionP (λ = (λ1, λ2, . . . , λN )) =∏Ni=1 λ−1iZ (4.2.1)where Z =∑λ∈P(∏Ni=1 λ−1i ).Proposition 4.2.5. Choose λ according to the distribution given by (4.2.1).Then the underlying graph of Ug,n and Tλ(n) has the same distribution.Proof. First observe that it is enough to show the following sequence ofbijections2N⋃λ=(λ1,...,λN )∈PN∏i=1(λi − 1)!Tλ(n) Ψ←→ N !Cg,n Φ←→ 2n+1N !Ug,nwhere Φ and Ψ are bijections which preserve the underlying graph. Thisis because for each λ ∈ P, it is easy to see that the number of elements in∏i(λi−1)!Tλ(n) is (n+ 1)!∏Ni=1 λ−1i and given a λ, the underlying graph ofan uniform element of∏i(λi−1)!Tλ(n) and Tλ(n) has the same distribution.Now the existence of bijection Φ which also preserves the underlyinggraph is guaranteed from Theorem 4.2.3. For Ψ, observe that the factor∏Ni=1(λi − 1)! comes from the ordering of the elements within the cycle ofC-permutations and the factor 2N comes from the signs associated witheach cycle of the C-permutations. The factor N ! comes from all possibleordering each cycle type of a C-permutation which is taken into account inthe marked trees but not C-permutations. The proof is now complete byputting the pieces together.Because of Lemma 4.2.5 it is enough to look at the underlying graphof Tλ(n) to prove the Theorems stated in Section 2.2 where λ is chosenaccording to the distribution given by (4.2.1). Our strategy is to show thata typical λ satisfies some “nice” conditions (which we will call condition (A)later), condition on such a λ satisfying those conditions and then work withTλ(n).884.2. PreliminariesRecall N = n + 1 − 2g. Since g/n → θ where 0 < θ < 1/2, n/N →(1 − 2θ)−1. Denote α = (1 − 2θ)−1. Clearly α > 1. The reader shouldbear in mind that α will remain in the background throughout the rest ofthe chapter. We also warn the readers not to confuse this α with the α inChapter Typical λRecall the definition of P from Section 4.2.1. Suppose C0, C1, C2, d1, d2 aresome positive constants which we will fix later. We say that an element inλ = (λ1, λ2, . . . λN ) ∈ P satisfies condition (A) if it satisfies(i) λmax < C0 log n where λmax is the maximum in the set {λ1, λ2, . . . λN}.(ii) C1n <∑Ni=1 λ2i <∑Ni=1 λ3i < C2n.(iii) d1n < |i : λi = 1| < d2nThe following Lemma ensures that λ satisfies condition (A) with high prob-ability for appropriate choice of the constants. The proof is provided inappendix BLemma 4.2.6. Suppose λ is chosen according to the distribution given by(4.2.1). Then there exists constants C0, C1, C2, d1, d2 depending only uponα such that condition (A) holds with probability at least 1 − cn−3 for someconstant c > 0.Now we state a Lemma which will be useful later. Given a λ, we shalldenote by Pλ the conditional measure induced by Tλ(n).Lemma 4.2.7. Fix a tree t ∈ U0,n and a λ ∈ P satisfying condition (A).Fix I ⊂ {1, 2, . . . , N} such that |I| < n3/4. Condition on the event E thatthe plane tree of Tλ(n) is t and S is the set of all the vertices in t whosemark belong to I where S is some fixed subset of V (t) (S is chosen so that Ehas non-zero probability.) Let {v, w, z} ⊂ V (t)\S be any set of three distinctvertices in t and i /∈ I. ThenPλ(m(v) = i|E) ∼ λi/n (4.2.2)Pλ(m(v) = m(w)|E)  n−1 (4.2.3)Pλ(m(v) = m(w) = m(z)|E)  n−2 (4.2.4)Proof. Notice that |S| < C0n3/4 log n because of part (i) of condition (A).The proof of (4.2.2) follows from the fact thatPλ(m(v) = i|E) =(n− |S| − 1)!λi!(n− |S|)!(λi − 1)!= λin− |S| ∼ λi/n894.2. Preliminariessince |S| < C0n3/4 log n.Now we move on to prove (4.2.3). Conditioned on S, t the probabilitythat v and w have the same mark j /∈ I with λj ≥ 3 is(n− |S| − 2)!λj !(n− |S|)!(λj − 2)!∼ λj(λj − 1)n2All we need to prove is∑j /∈I λj(λj − 1)  n which is clear from part (ii) ofcondition (A) and the fact that |I| < n3/4.Proof of eq. (4.2.4) is very similar to that of eq. (4.2.3) and is left to thereader.4.2.3 Large deviation estimates on random treesGalton-Watson treesA Galton-Watson tree, roughly speaking, is the family tree of a Galton-Watson process which is also sometimes referred to as a branching processin the literature. These are well studied in the past and goes far back tothe work of Harris ([60]). A fine comprehensive coverage about branchingprocesses can be found in [14]. Given a Galton-Watson tree, we denote byξ the offspring distribution. Let P(ξ = k) = pk for k ≥ 1. Let Zr be thenumber of vertices at generation r of the tree. We shall also assume• p0 + p1 < 1• E(eλξ) <∞ for small enough λ > 0.We need the following lower deviation estimate. The proof essentiallyfollows from a result in [14] and is provided in appendix C.Lemma 4.2.8. Suppose Eξ = µ > 1 and the distribution of ξ satisfies theassumptions as above. For any constant γ such that 1 < γ < µ, for all r ≥ 1P(Zr ≤ γr) < c exp(−c′r) + P(Zr = 0)for some positive constants c, c′.Random plane treesA random plane tree with n edges is a uniformly picked ordered tree withn edges (see [69] for a formal treatment.) In other words a random planetree with n edges is nothing but U0,n as per our notation. We shall need the904.3. Proof outlinefollowing large deviation result for the lower bounds and upper bounds onthe diameter of U0,n. This follows from Theorem 1.2 of [3] and the discussionin Section 1.1 of [3].Lemma 4.2.9. For any x > 0,(i) P (Diam(U0,n) ≤ x) < c exp(−c1(n− 2)/x2)(ii) P (Diam(U0,n) > x) < c exp(−c1x2/n)where c > 0 and c1 > 0 are constants.We shall also need some estimate of local volume growth in random planetrees. For this purpose, let us define for an integer r ≥ 1,Mr = maxv∈V (U0,n)|Br(v)|where Br(v) denotes the ball of radius r around v in the graph distancemetric of U0,n. In other words, Mr is the maximum over v of the volume ofthe ball of radius r around a vertex v in U0,n. It is well known that typically,the ball of radius r in U0,n grows like r2. The following Lemma states thatMr is not much larger than r2 with high probability. Proof is provided inappendix C.Lemma 4.2.10. Fix j ≥ 1 and r = r(n) is a sequence of integers such that1 ≤ r(n) ≤ n. Then there exists a constant c > 0 such thatP(Mr > r2 log2 n) < exp(−c log2 n)4.3 Proof outlineIn this section we describe the heuristics of the proofs of Theorems 4.1.1and 4.1.4.Let us describe an exploration process on a given marked tree startingfrom any vertex v in the plane tree. This process will describe an increasingsequence of subsets of vertices which we will call the set of revealed vertices.In the first step, we reveal all the vertices with the same mark as v. Thenwe explore the set of revealed vertices one by one. At each step when weexplore a vertex, we reveal all its neighbors and also reveal all the verticeswhich share a mark with one of the neighbors. If a neighbor has alreadybeen revealed, we ignore it. We then explore the unexplored vertices andcontinue.914.4. Lower bound and injectivity radiusWe can associate a branching process with this exploration process wherethe number of vertices revealed while exploring a vertex can be thought of asthe offsprings of the vertex. It is well known that the degree of any uniformlypicked vertex in U0,n is roughly distributed as a geometric(1/2) variable andwe can expect such behavior of the degree as long as the number of verticesrevealed by the exploration is small compared to the size of the tree. Nowthe expected number of vertices with the same mark as a vertex is roughlya constant strictly larger than 1 because of part (ii) of condition (A). Hencethe associated branching process will have expected number of offsprings aconstant which is strictly larger than 1. Thus we can stochastically dominatethis branching process both from above and below by supercritical Galton-Watson processes which will account for the logarithmic order of typicaldistances.Once we have such a domination, observe that the vertices at distance atmost r from the root in the underlying graph of the marked tree is approxi-mately the vertices in the ball of radius r around the root in a supercriticalGalton-Watson tree. Hence by virtue of the fact that supercritical Galton-Watson trees have roughly exponential growth, we can conclude that thenumber of vertices at a distance at most ε log n from the root in the under-lying graph of the marked tree is  √n if ε > 0 is small enough. Hencenote that to have a circuit within distance ε log n in the underlying graph ofthe marked tree, two of the vertices which are revealed within  √n manysteps must be close in the plane tree. But observe that the distribution ofthe revealed vertices is roughly a uniform sample from the set of vertices inthe tree up to the step when at most roughly √n many vertices are revealed.It is not hard to see from this that the probability of revealing two verticeswhich are close in the plane tree up to roughly √n many steps is small. Thisargument shows that the local injectivity radius is at least ε log n for somesmall enough ε > 0.The rest of the chapter is devoted to make these heuristics precise.4.4 Lower bound and injectivity radiusRecall condition (A) as described in the behavior of Section 4.2.2. Pick aλ satisfying condition (A). Recall that Tλ(n) denotes a uniformly pickedelement from Tλ(n). Throughout this section we shall fix a λ satisfyingcondition (A) and work with Tλ(n). Also recall that Tλ(n) = (U0,n,M)where U0,n is a uniformly picked plane tree with n edges andM is a uniformlypicked marking function corresponding to λ which is independent of U0,n.924.4. Lower bound and injectivity radiusLet dλ(., .) denote the graph distance metric in the underlying graph ofTλ(n). In this section we prove the following Theorem.Theorem 4.4.1. Fix a λ satisfying condition (A). Suppose x and y aretwo uniformly and independently picked numbers from {1, 2, . . . , N} and Vxand Vy are the vertices in the underlying graph of Tλ(n) corresponding tothe marks x and y respectively. Then there exists a constant ε > 0 such thatPλ(dλ(Vx, Vy) < ε log n)→ 0as n→∞.Proof of Theorem 4.1.1 part (i). Follows from Theorem 4.4.1 along with Propo-sition 4.2.5 and Lemma 4.2.6.As a by-product of the proof of Theorem 4.4.1, we also obtain the proofof Theorem 4.1.4 in this section.Note that for any finite graph, if the volume growth around a typicalvertex is small, then the distance between two typical vertices is large. Thusto prove Theorem 4.4.1, we aim to prove an upper bound on volume growtharound a typical vertex. Note that with high probability the maximumdegree in U0,n is logarithmic and λmax is also logarithmic (via condition (A)part (i) and Lemma 4.2.9.) Hence it is easy to see using the idea describedin Section 4.3 that the typical distance is at least ε log n/ log log n with highprobability if ε > 0 is small enough. This is enough, as is heuristicallyexplained in Section 4.3, to ensure that the injectivity radius of Ug(n) isat least ε log n/ log log n with high probability for small enough constantε > 0. The rest of this section is devoted to the task of getting rid ofthe log log n factor. This is done by ensuring that while performing theexploration process for reasonably small number of steps, we do not revealvertices of high degree with high probability.Given a marked tree (t,m), we shall define a nested sequence R0 ⊆ R1 ⊆R2 ⊆ . . . of subgraphs of (t,m) where Rk will be the called the subgraphrevealed and the vertices in Rk will be called the vertices revealed atthe kth step of the exploration process. We will also think of the number ofsteps as the amount of time the exploration process has evolved. There willbe two states of the vertices of Rk: active and neutral. Along with {Rk},we will define another nested sequence E0 ⊆ E1 ⊆ E2 ⊆ . . .. In the firststep, R0 = E0 will be a set of vertices with the same mark and hence E0 willcorrespond to a single vertex in the underlying graph of (t,m). The subgraphof the underlying graph of (t,m) formed by gluing together vertices with the934.4. Lower bound and injectivity radiussame mark in Er will be the ball of radius r around the vertex correspondingto E0 in the underlying graph of (t,m). The process will have rounds andduring round i, we shall reveal the vertices which correspond to vertices atdistance exactly i from the vertex corresponding to E0 in the underlyinggraph of (t,m). Define τ0 = 0 and we now define τr which will denotethe time of completion of the rth round for r ≥ 1. Let Nr = Er \ Er−1.Inductively, having defined Nr, we continue to explore every vertex in Nr insome predetermined order and τr+1 is the step when we finish exploring Nr.For a vertex v, mark(v) denotes the set of marked vertices with the samemark as that of v. For a vertex set S, mark(S) = ∪v∈Smark(v). We nowgive a rigorous algorithm for the exploration process.Exploration process I(i) Starting rule: Pick a number x uniformly at random from theset of marks {1, 2, . . . , N} and let E0 = R0 = mark(x). Declareall the vertices in mark(x) to be active. Also set τ0 = 0.(ii) Growth rule:1. For some r ≥ 1, suppose we have defined the nested subsetof vertices of E0 ⊆ . . . ⊆ Er such that Nr := Er \ Er−1 isthe set of active vertices in Er. Suppose we have defined theincreasing sequence of times τ0 ≤ . . . ≤ τr and the nestedsequence of subgraphs R0 ⊆ R1 ⊆ . . . ⊆ Rτr such that Rτr =Er. The number r denotes the number of rounds completedin the exploration process at time τr.2. Order the vertices of Nr in some arbitrary order. Now weexplore the first vertex v in the ordering of Nr. Let Sv de-note all the neighbors of v in t which do not belong to Rτr .Suppose Sv has l vertices {v1, v2, . . . , vl} which are ordered inan arbitrary way. For 1 ≤ j ≤ l, at step τr + j, define Rτr+jto be the subgraph induced by V (Rτr+j−1) ∪mark(vj). Atstep τr + l we finish exploring v. Define all the vertices inRτr+l \ Rτr to be active and declare v to be neutral. Thenwe move on to the next vertex in Nr and continue.3. Suppose we have finished exploring a vertex of Nr in step kand obtained Rk. If there are no more vertices left in Nr,define k = τr+1 and Er+1 = Rτr+1 . Declare round r + 1 iscompleted and go to step 1.4. Otherwise, we move on to the next vertex v′ in Nr accordingto the pre-described order. Let Sv′ = {v1, v2, . . . , vl′} be the944.4. Lower bound and injectivity radiusneighbors of v′ which do not belong to Rk. For 1 ≤ j ≤ l′,at step k + j, define Rk+j to be the subgraph induced byV (Rk+j−1) ∪mark(vj). Define all the vertices in Rk+l′ \ Rkto be active and declare v′ to be neutral. Now go back tostep 3.(iii) Threshold rule: We stop if the number of steps exceeds n1/10or the number of rounds exceeds log n. Let δ be the step numberwhen we stop the exploration process.Recall that Vx denotes the vertex in the underlying graph of Tλ(n) cor-responding to the mark x. The following proposition is clear from the de-scription of the exploration process and is left to the reader to verify.Proposition 4.4.2. For every j ≥ 1, all the vertices with the same markin Ej \ Ej−1 when glued together form all the vertices at a distance exactlyj from Vx in the underlying graph of (t,m).In step 0, define mark(x) to be the seeds revealed in step 0. At anystep, if we reveal mark(z) for some vertex z, then mark(z) \ z is called theseeds revealed at that step. The nomenclature seed comes from the fact thata seed gives rise to a new connected component in the revealed subgraphunless it is a neighbor of one of the revealed subgraph components. Howeverwe shall see that the probability of the latter event is small and typicallyevery connected component has one unique seed from which it “starts togrow”.Now suppose we perform the exploration process on Tλ(n) = (U0,n,M)where recall that M is a uniformly random marking function which is com-patible with λ on the set of vertices of U0,n and is independent of the treeU0,n. Let Fk be the sigma field generated by R0, R1, R2, . . . , Rk.The aim is to control the growth of Rk and to that end, we need tocontrol the size of mark(Sv) while exploring the vertex v conditioned up towhat we have revealed up to the previous step. It turns out that it will bemore convenient to condition on a subtree which is closely related to theconnected tree spanned by the vertices revealed.Definition 4.4.3. The web corresponding to Rk is defined to be the unionof the unique paths joining the root vertex v∗ and the vertices closest to v∗in each of the connected components of Rk including the vertices at whichthe paths intersect Rk. The web corresponding to Rk is denoted by PRk .As mentioned before, the idea is to condition on the web. Observe thatafter removing the web from U0,n at any step, we are left with a uniformly954.4. Lower bound and injectivity radiusv∗ v∗Figure 4.3: The web is denoted by the red paths. On the left:a general web structure. A priori the web structure might be verycomplicated. Many paths in the web might pass through the samevertex as is depicted here. On the right: A typical web structuredistributed forest with appropriate number of edges and trees. What standsin our way is that in general the web corresponding to a subtree might bevery complicated (see Figure 4.3). The paths joining the root and severalcomponents might “go through” the same component. Hence conditioned onthe web, a vertex might a priori have arbitrarily many of its neighbors be-longing to the web. To show that this does not happen with high probabilitywe need the following definitions.For any vertex u in t, the ancestors of u are the vertices in t along theunique path joining u and the root vertex v∗. For any two vertices u, v in tlet u ∧ v denote the common ancestor of u and v which is farthest from theroot vertex v∗ in t. LetC(u, v) = dt(u ∧ v, {u, v, v∗})A pair of vertices (u, v) is called a bad pair if C(u, v) < log2 n (see Fig-ure 4.4.)Recall that we reveal some set of seeds (possibly empty) at each step ofthe exploration process. Suppose we uniformly order the seeds revealed ateach step and then concatenate them in the order in which they are revealed.More formally, Let (si0 , si1 , . . . , siki ) be the set of seeds revealed in step i or-dered in uniform random order. Let S = (s10 , s11 , . . . , s1k1 , . . . , sδ1 , . . . , sδkδ ).To simplify notation, let us denote S = (S0, S1, . . . , Sδ′) where δ′+ 1 countsthe number of seeds revealed up to step δ. The reason for such ordering istechnical and will be clearer later in the proof of Lemma 4.4.8.Lemma 4.4.4. If S does not contain a bad pair then each connected compo-nent of Rδ contains an unique seed and the web PRδ intersects each connectedcomponent of Rδ at most at one vertex.964.4. Lower bound and injectivity radiusv∗vv′Figure 4.4: v∗ denotes the root vertex. (v, v′) is a bad pair ifeither of red, green or blue part has at most log2 n many vertices.Remark 4.4.5. In Lemma 4.4.10, we shall prove that the probability of Scontaining a bad pair goes to 0 as n → ∞. This and Lemma 4.4.4 showsthat for large n, the typical structure of the web is like the right hand figureof Figure 4.3.Proof. Clearly, every connected component of Rδ must contain at least oneseed. Also note that every connected component of Rδ has diameter at most2 log n because of the threshold rule. Since the distance between any pair ofseeds in Rδ is at least log2 n if S do not contain a bad pair, each componentmust contain a unique seed.Suppose at any arbitrary step there is a connected component C whichintersects the web in more than two vertices. Then there must exist a com-ponent C ′ such that the path of the web joining the root and C ′ intersects Cin more than one vertex. This implies that the (unique) seeds of C and C ′form a bad pair since the diameter of both C and C ′ are at most 2 log n.Now we want to prove that with high probability, S do not contain abad pair. Observe that the distribution of the set of seeds revealed is veryclose to a uniformly sampled set of vertices without replacement from theset of vertices of the tree as long as Rδ √n, because of the same effectas the birthday paradox. We quantify this statement and further show thatan i.i.d. sample of size δ′ from the set of vertices do not contain a bad pairwith high probability.We first show that the cardinality of the set Rδ cannot be too large withhigh probability.Lemma 4.4.6. Rδ = O(n1/10 log n)974.4. Lower bound and injectivity radiusProof. At each step at most λmax many vertices are revealed and λmax =O(log n) via condition (A).Given S, let S˜ = {S˜0, S˜1, . . . , S˜δ′} be an i.i.d. sample of uniformly pickedvertices from U0,n. First we need the following technical lemma.Lemma 4.4.7. Suppose a = a(n) and b = b(n) are sequences of positiveintegers such that (a+ b)2 = o(n). Then for large enough n,nb∣∣∣∣∣1b!(n− ab)−1− 1nb∣∣∣∣∣< 4((a+ b)bn)Proof. Observe that1b!(n− ab)−1= 1(n− a− b+ 1) . . . (n− a)= 1nbb∏j=1(1 + a+ b− jn− (a+ b− j))(4.4.1)< 1nbb∏j=1(1 + 2(a+ b)/n))< 1nb exp(2(a+ b)bn)= 1nb(1 + 2(a+ b)bn + o((a+ b)bn))< 1nb(1 + 4((a+ b)bn))where the third inequality follows because n−(a+b) > n/2 for large enough nand a+b−j < a+b. The second last equality follows since b(a+b) = o(n) viathe hypothesis. The other direction follows from the fact that the expressionin the right hand side of eq. (4.4.1) is larger than 1/nb.For random vectors X,Y let dTV (X,Y ) denote the total variation dis-tance between the measures induced by X and Y .Lemma 4.4.8.dTV (S, S˜) < 4n−2/3984.4. Lower bound and injectivity radiusProof. First note that |S| < |Rδ| < n1/9 from Lemma 4.4.6. Let us denoteby (S1, S2, . . . Sd) the ordered set of seeds revealed in the first step afteruniform ordering. ThendTV ((S1, . . . , Sd), (S˜1, . . . , S˜d)) < nd∣∣∣∣∣1d!(nd)−1− 1nd∣∣∣∣∣< 4n−7/9 (4.4.2)where the factor nd in the first inequality of (4.4.2) comes from the definitionof total variation distance and the fact that there are nd many d-tuple ofvertices and the second inequality of (4.4.2) follows from Lemma 4.4.7 andthe fact that d < |S| < n1/9. We will now proceed by induction on thenumber of steps. Suppose up to step t, (S1, . . . , Sm) is the ordered set ofseeds revealed. AssumedTV ((S1, . . . , Sm), (S˜1, . . . , S˜m)) < 4mn−7/9 (4.4.3)Recall Ft = σ(R0, . . . , Rt). Now suppose we reveal Sm+1, . . . , Sm+L in thet+1th step where L is random depending upon the number of seeds revealedin the t+1th step. Observe that to finish the proof of the lemma, it is enoughto prove that the total variation distance between the measure induced by(Sm+1, . . . , Sm+L) conditioned on Ft and (S˜m+1, . . . , S˜m+L) (call this dis-tance ∆) is at most 4n−7/9. This is because using induction hypothesis and∆ < 4n−7/9, we have the following inequalitydTV ((S1, . . . , Sm+L), (S˜1, . . . , S˜m+L))< dTV ((S1, . . . , Sm), (S˜1, . . . , S˜m)) + 4n−7/9 < 4(m+ 1)n−7/9. (4.4.4)Thus (4.4.4) along with induction implies dTV (S, S˜) < 4n1/9n−7/9 < 4n−2/3since δ′ < n1/9.Let F ′t be the sigma field induced by Ft and the mark revealed in stept + 1. To prove ∆ < 4n−7/9, note that it is enough to prove that thetotal variation distance between the measure induced by Sm+1, . . . , Sm+Lconditioned on F ′t and (S˜m+1, . . . , S˜m+L) (call it ∆′) is at most 4n−7/9. Butif l many seeds are revealed in step t+ 1 (note l only depends on the markrevealed) then a calculation similar to (4.4.2) shows that∆′ < nl∣∣∣∣∣1l!(n− |Rt| − 1l)−1− 1nl∣∣∣∣∣< 4n−7/9where the last inequality above again follows from Lemma 4.4.7. The proofis now complete.994.4. Lower bound and injectivity radiusWe next show that the probability of obtaining a bad pair of vertices inthe collection of vertices S˜ is small.Lemma 4.4.9.Pλ(S˜ contains a bad pair ) = O(n−1/10)Proof. Let (V,W ) denote a pair of vertices uniformly and independentlypicked from the set of vertices of U0,n. Let P be the path joining the rootvertex and V . Let A be the event that the unique path joining W and Pintersects P at a vertex which is within distance log2 n from the root vertexor V . Since V and W have the same distribution and since there are at mostn2/9 pairs of vertices in S˜, it is enough to prove Pλ(A) = O(n−1/3 log2 n)Recall the notation Mr of Lemma 4.2.10: Mr is the maximum over allvertices v in U0,n of the volume of the ball of radius r around v. Let |P |denote the number of vertices in P . Consider the event E = {Mbn1/3c <n2/3 log2 n}. On E, the probability of {|P | < n1/3} is O(n−1/3 log2 n). Sincethe probability of the complement of E is O(exp(−c log2 n)) for some con-stant c > 0 because of Lemma 4.2.10, it is enough to prove the bound forthe probability of A on |P | > n1/3.Condition on P to have k edges where k > n1/3. Observe that thedistribution of U0,n \ P is given by an uniformly picked of rooted forestswith σ = 2k + 1 trees and n− k edges. Hence if we pick another uniformlydistributed vertex W independent of everything else, the unique path joiningW and P intersects P at each vertex with equal probability. Hence theprobability that the unique path joining W and P intersects P at a vertexwhich is at a distance within log2 n from the root or V is O(n−1/3 log2 n) byunion bound. This completes the proof.Lemma 4.4.10.Pλ(S contains a bad pair) = O(n−1/10)Proof. Using Lemmas 4.4.8 and 4.4.9, the proof follows.We will now exploit the special structure of the web on the event thatS do not contain a bad pair to dominate the degree of the explored vertexby a suitable random variable of finite expectation for all large n. To thisend, we need some enumeration results for forests. Note that the forests weconsider here are rooted and ordered. Let Φσ,e denote the number of forests1004.4. Lower bound and injectivity radiuswith σ trees and e edges. It is well known (see for example, Lemma 3 in[27]) thatΦσ,e =σ2e+ σ(2e+ σe)(4.4.5)We shall need the following estimate. The proof is postponed for later.Lemma 4.4.11. Suppose e is a positive integer such that e < n. Supposed0, d1 denote the degree of the roots of two trees of a uniformly picked forestwith n− e edges and σ trees. Let j ≤ n− e. Thenmax{P(d0 + d1 = j),P(d0 = j)} <4j(j + 1)2jWe shall now show the degree of an explored vertex at any step of theexploration process can be dominated by a suitable variable of finite expec-tation which do not depend upon n or the step number. Recall that whileexploring v we spend several steps of the exploration process which dependson the number of neighbors of v which have not been revealed before.In the following Lemmas 4.4.12 and 4.4.14, we assume vk+1 is the vertexwe start exploring in the (k + 1)th step of the exploration process.Lemma 4.4.12. The distribution of the degree of vk+1 conditioned on Rksuch that Rk do not contain a bad pair is stochastically dominated by avariable X where EX <∞ and the distribution of X do not depend on n ork.Proof. Consider the conditional distribution of the degree of vk+1 condi-tioned on Rk as well as PRk . Without loss of generality assume PRk donot contain n edges for then the Lemma is trivial. Note that PRk cannotintersect a connected component of Rk at more than one vertex becauseof Lemma 4.4.4. Suppose e < n is the number of edges in the subgraphPRk ∪ Rk. It is easy to see that the distribution of U0,n \ (PRk ∪Rk) is auniformly picked element from the set of forests with σ trees and n−e edgesfor some number σ. If vk+1 is not an isolated vertex in Rk (that is there isan edge in Rk incident to vk+1), the degree of v is at most 2 plus the sumof the degrees of the root vertices of two trees in a uniformly distributedforest of σ trees and n− e edges. If vk+1 is an isolated vertex, the degree ofvk+1 is 1 plus the degree of the root of a tree in a uniform forest of σ treesand n− e edges. Now we can use the bound obtained in Lemma 4.4.11 andobserve that the bound do not depend on the conditioning of the web PRk .It is easy now to choose a suitable variable X. The remaining details areleft to the reader.1014.4. Lower bound and injectivity radiusNow we stochastically dominate the number of seeds revealed at a stepconditioned on the subgraph revealed up to the previous step by a variableY with finite expectation which is independent of the step number or n.Lemma 4.4.13. Number of vertices added to Rj−1 the jth step of the explo-ration process conditioned on Rj−1 is stochastically dominated by a variableY with EY < C where C is a constant which do not depend upon j or n.Proof. Recall ri denotes the cardinality of the set {j : λj = i}. Nownote that because of the condition (A), we can choose ϑ > 1 such that∑i≥3 ϑiri < d3n for some number 0 < d3 < 1. Since |Rk| < n1/9, the prob-ability that the number of vertices added to Rj−1 in the jth step is i fori ≥ 3 is at most iri/(n−n1/9) < ϑiri/n for large enough n using eq. (4.2.2).Now define Y as follows:P(Y = i) ={ϑ irin if i ≥ 31−∑i≥3 ϑ irin := p2 if i = 2Note further thatE(Y ) = 2p2 + ϑ∑i≥3i2ri/n < 2p2 +N∑i=1λ2i /n < 2 + C2from condition (A). Thus clearly Y satisfies the conditions of the Lemma.Again, recall the definition of vk+1 from Lemma 4.4.12. The followinglemma is clear now.Lemma 4.4.14. Let X,Y be distributed as in Lemmas 4.4.12 and 4.4.13and suppose they are mutually independent. Conditioned on Rk such thatRk do not have any bad pair, the number of vertices added to Rk when wefinish exploring vk+1 is stochastically dominated by a variable Z where Z isthe sum of X independent copies of the variable Y . Consequently EZ < Cwhere C is a constant which do not depend upon k or n.Proof of Theorem 4.4.1. We perform exploration process I. Let rδ be themaximum integer r such that τr < δ. Let Bλr (Vx) denote the ball of radius raround the vertex Vx in the underlying graph of Tλ(n). Recall that becauseof Proposition 4.4.2, Bλr (Vx) is obtained by gluing together vertices withthe same mark in Rτr = Er. Note that if |Bλbε lognc(Vx)| ≤ n1/9 then theprobability that Vy lies in Bλbε lognc(Vx) is O(n−8/9 log n) because of condition1024.4. Lower bound and injectivity radius(A) part (i). Hence it is enough to prove Pλ(rδ < ε log n) → 0. Further,because of Lemma 4.4.10, it is enough to prove Pλ(rδ < ε log n ∩ B) → 0where B is the event that S do not contain a bad pair.Consider a Galton-Watson tree with offspring distribution Z as specifiedin Lemma 4.4.14 and suppose Zr is the number of offsprings in generationr for r ≥ 1. Then from Lemma 4.4.14, we getPλ(rδ < ε log n ∩ B) < Pλbε lognc∑k=1Zk > n1/9→ 0 (4.4.6)if ε > 0 is small enough which follows from the fact that E(Zr) < Cr whereC is the constant in Lemma 4.4.14 and Markov’s inequality.Now we finish the proof of Theorem 4.1.4.Proof of Theorem 4.1.4. We shall use the notations used in the proof ofTheorem 4.4.1. Observe that if the ball of radius rδ in the underlying graphof Tλ(n) contains a circuit, then two connected components must coalesce toform a single component at some step k < δ. However this means that thereexists a bad pair. Thus on the event B, the underlying graph of Rδ do notcontain a circuit. Hence on the event B, the ball of radius ε log n containsa circuit in the underlying graph of Tλ(n) implies rδ < ε log n. Howeverfrom eq. (4.4.6), we see that the probability of {rδ < ε log n ∩ B} → 0 forsmall enough ε > 0. The rest of the proof follows easily from Lemmas 4.2.6and 4.4.10 and Proposition 4.2.5.Now we finish off by providing the proof of Lemma 4.4.11.Proof of Lemma 4.4.11. It is easy to see thatP(d0 = j) =Φσ+j−1,n−e−jΦσ,n−ewhere Φσ,n is given by eq. (4.4.5). A simple computation shows thatΦσ+j−1,n−e−jΦσ,n−e= σ + j − 1σ12j×((n− e+ σ)∏j−1i=1 (1− i/(n− e))(2(n− e) + σ − 1)∏j+1i=2 (1 + (σ − i)/2(n− e)))(4.4.7)1034.5. Upper boundNow we can assume (n − e + σ)/(2(n − e) + σ − 1) ≤ 1 (since e 6= n byassumption). Also notice1− in− e < 1 +σ − i2(n− e)for i ≥ 1. Hence eq. (4.4.7) yieldsΦσ+j−1,n−e−jΦσ,n−e≤ σ + j − 1σ12j((1− 1/(n− e))∏j+1i=j (1 + (σ − i)/2(n− e)))≤ σ + j − 1σ42j ≤4j2j (4.4.8)which follows because∏j+1i=j (1+(σ−i)/2(n−e)) ≥ 1/4 since n−e ≥ j and forthe second inequality of (4.4.8), we use the trivial bound (σ+ j − 1)/σ ≤ j.Further note that P(d0 = k, d1 = j − k) for any 0 ≤ k ≤ j is given byΦσ+j−2,n−e−j/Φσ,n−e. Hence summing over k,P(d0 + d1 = j) = (j + 1)Φσ+j−2,n−e−jΦσ,n−e.Now keeping n fixed, Φσ,n is an increasing function of σ, hence using thebound obtained in (4.4.8), the proof is complete.4.5 Upper boundThroughout this section, we again fix a λ satisfying condition (A) as de-scribed in Section 4.2.2. Recall dλ(., .) denotes the graph distance metricin the underlying graph of Tλ(n). In this section we prove the followingTheorem.Theorem 4.5.1. Fix a λ satisfying condition (A). Suppose V1 and V2 bevertices corresponding to the marks 1 and 2 in Tλ(n). Then there exists aconstant C > 0 such thatPλ(dλ(V1, V2) > C log n) = O(n−3)Note that the distribution of Tλ(n) is invariant under permutation of themarks. Hence the choice of marks 1 and 2 in Theorem 4.5.1 plays the samerole as an arbitrary pair of marks.Proof of Theorem 4.1.1 part (ii). Proof follows from Theorem 4.5.1, Propo-sition 4.2.5, and Lemma Upper boundTo prove Theorem 4.5.1, we plan to use an exploration process similarto that in Section 4.4 albeit with certain modification to overcome technicalhurdles. We start the exploration process from a vertex v1 with mark 1 andcontinue to explore for roughly n3/4 steps. Then we start from the vertexv2 with mark 2 and explore for another n3/4 steps. Since the sets of verticesrevealed are approximately uniformly and randomly selected from the setof vertices of the tree, the distance between these sets of vertices should besmall with high probability, because of the same reasoning as the birthdayparadox problem. Then we show that the distance in the underlying graphof Tλ(n) from the set of vertices revealed and 1 or 2 is roughly log n tocomplete the proof. To this end, we shall find a supercritical Galton-Watsontree whose offspring distribution will be dominated by the vertices revealedin every step of the process.However, if we proceed as the exploration process described in Sec-tion 4.4, since an unexplored vertex has a reasonable chance of being a leaf,the corresponding Galton-Watson tree will also have a reasonable chance ofdying out. However, we need the dominated tree to survive for a long timewith high probability. To overcome this difficulty, we shall invoke the follow-ing trick. Condition on the tree U0,n to have diameter  log2 n. Considerthe vertex v∗ which is farthest from {v1, v2}. For each vertex we explore, wereveal its unique neighbor which lie on the path joining the vertex and v∗instead of revealing all the neighbors which do not lie in the set of revealedvertices. Note that the revealed vertices by the exploration process now willmostly be disjoint paths increasing towards v∗ and we shall always have atleast one child if the paths do not intersect. However the chance of pathsintersecting is small. Since expected size of mark(v) for any non-revealedvertex v is larger than 1 throughout the process, we have exponential growthaccounting for the logarithmic distance. The rest of the Section is devotedto rigorously prove the above described heuristic.We shall now give a brief description of the exploration process we shalluse in this section which is a modified version of exploration process de-scribed in Section 4.4. Hence, we shall not write down details of the processagain to avoid repetition, and concentrate on the differences with explorationprocess I as described in Section 4.4.Conditioning on the tree: For the proof of Theorem 4.5.1, we only needrandomness of the marking function M and not that of the tree U0,n. Hence,throughout this section, we shall condition on a plane tree U0,n = t wheret ∈ U0,n such that1054.5. Upper bound(i) diam(t) > √n/ log n.(ii) Mblog3 nc ≤ log8 n.where recall that Mr is as defined in Lemma 4.2.10: maximum over allvertices v in U0,n of the volume of the ball of radius r around v. Let us callthis condition, condition (B). Although apparently it should only help ifthe diameter of t is small, the present proof fails to work if the diameter istoo small and requires a different argument which we do not need. Note thatby Lemmas 4.2.9 and 4.2.10, the probability that U0,n satisfies condition (B)is at least 1− exp(−c log2 n) for some constant c > 0. Hence it is enough toprove Theorem 4.5.1 for the conditional measure which we shall also call Pλby an abuse of notation.We start with a marked tree (t,m) where t satisfies condition (B). Asplanned, the exploration process will proceed in two stages, in the first stage,we start exploring from a vertex with mark 1 and in the second stage froma vertex with mark 2.Exploration process II, stage 1: There will be three states of verticesactive, neutral or dead. We shall again define a nested sequence ofsubgraphs R0 ⊆ R1 ⊆ R2 ⊆ . . . which will denote the subgraph re-vealed. Alongside {Rk}k=0,1,..., we will define another nested sequenceQ0 ⊆ Q1 ⊆ Q2 ⊆ . . . which will denote dead vertices revealed.We shall similarly define the sequences {Nr}, {Er} and {τr} as inexploration process I. We call v to be a v∗-ancestor of another vertexv′ if v lies on the unique path joining v′ and v∗. The v∗-ancestor whichis also the neighbor of v is called the v∗-parent of v.Starting Rule: We start from a vertex v1 with mark 1 and v2 with mark2 (if there are more than one, select arbitrarily.) Let v∗ be a vertexfarthest from {v1, v2} in t (break ties arbitrarily.) Note that becauseof the lower bound on the diameter via condition (B), dt(v1, v∗) anddt(v2, v∗) are at least√n(3 log n)−1. Declare v1 to be active and letR0 = {v1}. Declare all the vertices in mark(v1) \ v1 to be dead andlet Q0 = mark(v1) \ v1. Set τ0 = 0 and E0 = R0.Growth rule: Suppose we have defined E0 ⊆ . . . ⊆ Er, τ0 ≤ . . . ≤ τr andalso R0 ⊆ . . . ⊆ Rτr such that Rτr = Er and Nr := Er \ Er−1 is theset of active vertices in Er. Now we explore vertices in Nr in somepredetermined order and suppose we have determined Rk for somek ≥ τr. We now move on to the next vertex in Nr. If there is no suchvertex, declare k = τr+1 and Er+1 = Rτr+1 .1064.5. Upper bound< log3 n< log3 nv vv∗ v∗Figure 4.5: Illustration of the death rule in exploration processII. A snapshot of the revealed vertices when we are exploring thecircled vertex v is given. The black vertices and edges correspondto neutral and active vertices, while the crosses correspond to deadvertices. We are exploring v and mark(v) is denoted by the redvertices. On the left: a red vertex comes within distance log3 nof one the revealed vertices, hence death rule is satisfied. On theright: two of the revealed vertices are within distance log3 n. Hencedeath rule is satisfied.Otherwise suppose v is the vertex to be explored in the k + 1th step.Let v− denote the v∗-ancestor which is not dead and is nearest to v inthe tree t. If v− is already in Rk then we terminate the process.Death rule: Otherwise, declare v− to be active, v to be neutral and letΛ = mark(v−) \ v−. If any vertex u ∈ Λ is within distance log3 nfrom Rk ∪ Qk ∪ v∗ or another u′ ∈ Λ, we say death rule is satisfied(see Figure 4.5.) If death rule is satisfied declare all the vertices inΛ to be dead and set Qk+1 = Qk ∪ Λ, Rk+1 = Rk ∪ v−. Otherwisedeclare all the vertices in Λ to be active, set Rk+1 = Rk ∪mark(v−)and Qk+1 = Qk.Threshold rule: We stop if the number of steps exceed n3/4 or r exceedslog2 n. Let δ denote the step when we stop stage 1 of the explorationprocedure.Exploration process II, stage 2: Similarly as in stage 1, we start withR′0 = v2 being active and Q′0 = mark(v2) \ v2 being dead. We proceed1074.5. Upper boundexactly as in stage 1, except for the following change: if v2 is a neighborof Rδ ∪Qδ, or while exploring v, if any of the vertices in mark(v−) isa neighbor of Rδ ∪Qδ, we say a collision has occurred and terminatethe procedure.We shall see later (see Lemma 4.5.9 and Corollary 4.5.10) that with highprobability, we perform the exploration for n3/4 steps and the number ofrounds is approximately log n in stage 1. Also in stage 2, collision occurswith high probability and the number of rounds is at most log n with highprobability.In what follows, we shall denote by X ′ in stage 2 the set or variablecorresponding to that denoted by X in stage 1 (for example, R′k, Q′k willdenote the set of revealed subgraphs and dead vertices respectively up tostage k in stage 2 etc.)Now we shall define a new tree TC which is defined on a subset of ver-tices of t. The tree TC will capture the growth process associated with theexploration process. We start with the tree t and remove all its edges so weare left with only its vertices. The root vertex of TC is v1. For every stepof exploring v, we add an edge neighboring v and every vertex of mark(v−)(where v− is defined as in growth rule) in TC if death rule is not satisfied.Otherwise we add an edge between v and v− in TC . The vertices we connectby an edge to v while exploring v is called the offsprings of v in TC similarin spirit to a Galton-Watson tree. It is clear that TC is a tree (since weterminate the procedure if v− ∈ Rk). Let Zr denotes the number of verticesat distance r from v1 in TC . Clearly, if we glue together vertices with thesame mark which are at a distance at most r in TC , we obtain a subgraphof the ball of radius r in the underlying graph of Tλ(n). We similarly defineanother tree corresponding to stage 2 of the process which we call T ′C whichstarts from the root vertex v2.Lemma 4.5.2. The volume of Rδ ∪ Qδ is at most C0n3/4 log n. Also thevolume of Rδ′ ∪ Qδ′ is at most C0n3/4 log n where C0 is as in part (i) ofcondition (A).Proof. In every step, at most C0 log n vertices are revealed by condition(A).Define v1 and v2 to be the seeds revealed in the first step. While explor-ing vertex v, we call the vertices in mark(v−) \ v− to be the seeds revealedat that step if the death rule is not satisfied. Note that because of theprescription of the death rule, seeds are necessarily isolated vertices (not aneighbor of any other revealed neutral or dead vertex up to that step.)1084.5. Upper boundheadFigure 4.6: An illustration of a worm at a certain step in theexploration process. The black vertices denote the vertices of theworm, the crosses are the dead vertices and the head of the wormis as shown. The circle is the v∗-ancestor of the head which is notdead. This worm has faced death 5 times so far.Definition 4.5.3. A worm corresponding to a seed s denotes a sequenceof vertices {w0, w1, w2, . . . , wd} such that w0 is s and wi+1 is the vertex wi−for i ≥ 0.Note that in the above definition, wi− depends on the vertices revealedup to the time we explore wi in exploration process II. Note that in a worm,wi+1 is a neighbor of wi if the v∗-parent of wi is not a dead vertex. If it isa dead vertex we move on to the next nearest ancestor of wi which is notdead. Note that the ancestors of wi which lie on the path joining wi+1 andwi are necessarily dead. If there are p dead vertices on the path between w0and the nearest v∗-ancestor of wd which is not dead, we say that the wormhas faced death p times so far (see Figure 4.6.) Call wd the head of theworm. The length of the worm is the distance in U0,n between wd and w0.We want the worms to remain disjoint so that conditioned up to theprevious step, the number of children of a vertex in the tree TC or T ′Cremain independent of the conditioning. Now for any worm, if wi ∈ Nr(resp. wi ∈ N ′r), then it is easy to see that wi+1 ∈ Nr+1 (resp. wi+1 ∈ N ′r+1)because of the way the exploration process evolves. Hence if none of theworms revealed during the exploration process face a dead vertex, then thelength of each worm is at most log2 n from threshold rule. Since every seedis at a distance at least log3 n from any other seed via the death rule, theworms will remain disjoint from each other if death does not occur.Unfortunately, many worms will face a dead vertex with reasonablechance. But fortunately, none of them will face many dead vertices withhigh probability. We say that a disaster has occurred at step k if after per-forming step k, there is a worm which has faced death at least 16 times. Thefollowing proposition is immediate from the threshold rule for exploration1094.5. Upper boundprocess II and the discussion above.Proposition 4.5.4. If disaster does not occur, then the length of each wormis at most log2 n + 16 and hence no two worms intersect during the explo-ration process for large enough n.We will now provide a series of Lemmas using which we will prove The-orem 4.5.1. The proofs of Lemmas 4.5.5 and 4.5.7 are postponed to Sec-tion 4.5.1 for clarity.We start with a Lemma that shows that disaster does not happen withhigh probability and consequently the length of each worm is at most log2 n+16 with high probability.Lemma 4.5.5. With Pλ-probability at least 1−cn−3 disaster does not occurwhere c > 0 is some constant.Lemma 4.5.6. Suppose disaster does not occur and r ≥ 0. Then in the treeTC , for v ∈ Zr, dTC (v, v1) < 16r. Also in T ′C , for v ∈ Z ′r, dT′C (v, v2) < 16r.Proof. We prove only for stage 1 as for stage 2 the proof is similar. TheLemma is trivially true for r = 0. Suppose now the Lemma is true for r′ = r.Now for any vertex in Zr and its offspring, the vertices corresponding to theirmarks in the underlying graph of Tλ(n) must lie at a distance at most 16because otherwise disaster would occur. Hence the distance of every vertexin Zr+1 from v1 is at most 16r + 16 = 16(r + 1). We use induction tocomplete the proof.Let us denote by E (resp. E ′) the event that disaster has not oc-curred up to step δ (resp. δ′). Let Fk denote the sigma field generatedby R0, . . . , Rk, Q0, . . . , Qk. Let F ′k = σ(R′0, . . . , R′k, Q′0, . . . , Q′k) ∨ Fδ. Letvk+1 (resp. v′k+1) be the vertex we explore in the k + 1th stage in theexploration process stage 1 (resp. stage 2).Lemma 4.5.7. Conditioned on Fk (resp. F ′k) such that k < δ (resp. δ′)and disaster has not occurred up to step k, the Pλ-probability that vk+1 inTC (resp. T ′C) has(i) no offsprings is 0.(ii) at least 3 offsprings is at least k0 for some constant k0 > 0.We now aim to construct a supercritical Galton-Watson tree which willbe stochastically dominated by both TC and T ′C . Consider a Galton-Watsontree GW with offspring distribution ξ where1104.5. Upper bound• P(ξ = 1) = (1− k0/2)• P(ξ = 2) = k0/2and k0 is the constant obtained in part (ii) of Lemma 4.5.7. Let ZGWr be thenumber of offsprings in the r-th generation of GW . Lemma 4.5.7 and thedefinition of GW clearly shows that Zr stochastically dominates ZGWr forall r ≥ 1 if disaster does not occur up to step τr. Let rδ = max{r : τr < δ}and similarly define rδ′ = max{r : τr < δ′}. Thus, we haveLemma 4.5.8. For any integer j ≤ rδ (resp. j ≤ rδ′), Zj stochasticallydominates ZGWj on the event E (resp. E ′).It is clear that the mean offspring distribution of GW is strictly greaterthan 1 and hence GW is a supercritical Galton-Watson tree. Also GW isinfinite with probability 1.Now we are ready to show that the depth of TC (resp. T ′C) when werun the exploration up to time δ (resp. δ′) is of logarithmic order with highprobability.Lemma 4.5.9. There exists a C > 0 such that(i) Pλ((rδ > C log n) ∩ E) = O(n−3)(ii) Pλ((rδ′ > C log n) ∩ E ′) = O(n−3)Proof. We shall prove only (i) as proof of (ii) is similar. Because of Lem-mas 4.5.2 and 4.5.8 we have for a large enough choice of C > 0,Pλ((rδ > C log n) ∩ E) < PλbC lognc∑i=1ZGWi ≤ C0n3/4 log n< Pλ(ZGWbC lognc ≤ C0n3/4 log n)< n−3 (4.5.1)where (4.5.1) follows by applying Lemma 4.2.8, choosing C > 0 large enoughand observing the fact that Pλ(Zr = 0) = 0 for any r from definition ofGW .Recall that in stage 2, we stop the process if we have revealed a vertexwhich is a neighbor of Rδ ∪ Qδ, and we say a collision has occurred. Letus denote the event that collision does not occur up to step k by Ck. Sinceδ ≤ bn3/4c implies either disaster has occurred in stage 1 or rδ > log2 n andδ′ ≤ bn3/4c implies either disaster has occurred in stage 2 or r′δ > log2 n ora collision has occurred we have the immediate corollary1114.5. Upper boundCorollary 4.5.10. On the event E, the Pλ-probability that δ ≤ bn3/4c isO(n−3). On the event E ′∩Cδ′, the Pλ-probability that δ′ ≤ bn3/4c is O(n−3).Now we are ready to prove our estimate on the typical distances. Weshow next, that a collision will occur with high probability.Lemma 4.5.11. Probability that a collision occurs before step δ′ is at least1− cn−3 for some constant c > 0.Proof. Let Q be the event that disaster does not occur up to step δ, δ =bn3/4c+ 1. Let A(Rδ) be the set of v∗- parents of the heads of the worms inRδ. Since at each step at least one vertex is revealed, δ = bn3/4c+ 1 impliesthe number of vertices revealed is at least n3/4. If disaster does not occur,then from Lemma 4.5.5 and Proposition 4.5.4, the worms are disjoint andeach worm has length at most log2 n+ 16. Hence the number of vertices inA(Rδ) is at least n3/4/(log2 n + 16). Also, the number of vertices in A(Rδ)is at most C0n3/4 log n from Lemma 4.5.2. For any k < δ′, conditioned onthe event Ck that no collision has occurred up to step k, the probability thatcollision occurs in step k + 1 when we are exploring a vertex v is at least(using Bonferroni’s inequality),∑w∈A(Rδ)Pλ(m(v) = m(w)|Ck,Q)−∑w,z∈A(Rδ)Pλ(m(v) = m(w) = m(z)|Ck,Q)> cn1/4 log2 n− c log2 n√n (4.5.2)> cn1/4 log2 n(4.5.3)for some constant c > 0. The first term of (4.5.2) follows from the lowerbound of (4.2.3). The second term of (4.5.2) follows from (4.2.4) and notingthat the number of terms in the sum is O(n3/2 log2 n). Since the bound onthe probability displayed in (4.5.3) is independent of the conditioning,Pλ(Cδ′ ∩ δ′ = bn3/4c+ 1|Q) + Pλ(Cδ′ ∩ δ′ ≤ bn3/4c|Q)<(1− cn1/4 log2 n)n3/4+ Pλ(Cδ′ ∩ E ′ ∩ δ′ ≤ bn3/4c|Q) + Pλ((E ′)c|Q)< exp(−c√n/ log2 n) +O(n−3) (4.5.4)=O(n−3)1124.5. Upper boundwhere the bound on the second term in eq. (4.5.4) follows from Corol-lary 4.5.10 and Lemma 4.5.5. The Lemma now follows because the prob-ability of the complement of Q is O(n−3) again from Corollary 4.5.10 andLemma 4.5.5.Proof of Theorem 4.5.1. Suppose we have performed exploration process Istage 1 and 2. Let G be the event that rδ ≤ C log n, rδ′ ≤ C log n, disasterdoes not occur before step δ or δ′ and a collision occurs. On the event Gthe distance between V1 and V2 in the underlying graph of Tλ(n) is at most32C log n+ 1 by Lemma 4.5.6. But by Lemmas 4.5.5, 4.5.9 and 4.5.11, thecomplement of the event G has probability O(n−3).4.5.1 Remaining proofsThe proofs of both the Lemmas in this subsection are for stage 1 of theexploration process as the proof for stage 2 is the same.Proof of Lemma 4.5.5. Let s be a seed revealed in the kth step of explo-ration process II . Suppose P denotes the set of vertices at a distance atmost log2 n + 16 from s along the unique path joining s and v∗. Note thatnone of the vertices in P are revealed yet because of the death rule. If theworm corresponding to s faces more than 16 dead vertices, then more than16 dead vertices must be revealed in P during the exploration from stepk to δ. Conditioned up to the previous step, the probability that one ofthe revealed vertices lie in P in a step is O(n−1(log2 n + 16)) from (4.2.3)and union bound. Since this bound is independent of the conditioning, theprobability that this event happens at least 16 times during the process isO(n−16 log32 n · n12) = O(n−4 log32 n) where the factor n12 has the justifi-cation that(bn3/4c16)= O(n12) is the number of combination of steps bywhich this event can happen 16 times. Observe that more than one vertexmay be revealed in P in a step, but the probability of that event is evensmaller. Thus taking union over all seeds, we see that the probability of dis-aster occurring is O(n−13/4 log33 n) = O(n−3) using Lemma 4.5.2 and unionbound.Proof of Lemma 4.5.7. It is clear that on the event of no disaster, everyexplored vertex has at least the offspring corresponding to its closest non-dead v∗-ancestor in the tree TC . This is because on the event of no disaster,no two worms intersect. For stage 2, the closest non-dead v∗-ancestor cannot1134.5. Upper boundbelong to Rδ∪Qδ because otherwise, the process would have stopped. Hence(i) is trivial.Now for (ii), first recall that condition (A) ensures that the number ofindices i such that λi ≥ 3 is at least (1 − d2)n. Now since the number ofvertices revealed up to any step k < δ is O(n3/4 log n), the number of verticesleft with mark i such that λi ≥ 3 is at least (1 − d2)n − O(n3/4 log n) >(1 − d2)n/2 for large enough n. Note that the number of offsprings of v inTC is at least 3 if the number of vertices with the same mark as v− is atleast 3 and death does not occur. Hence if we can show that the probabilityof death rule being satisfied in a step is o(1), we are done.To satisfy the death rule in step k + 1, a vertex in mark(v−) \ v− mustbe within distance log3 n in the tree U0,n to another vertex in mark(v−)\v−or Rk ∪Qk ∪ v∗. Now using of part (ii) of condition (B) and Lemma 4.5.2,the number of vertices within log3 n of Rδ ∪Qδ ∪ v∗ is O(n3/4 log9 n). Hencethe probability that the death rule is satisfied is O(n−1/4 log9 n) = o(1) byunion bound. This completes the proof.114Chapter 5Unicellular maps: the locallimit4 Our goal in this section is to identify explicitly the local limit of Ugn,nwhere gn ∼ θn for θ ∈ (0, 1/2) as a super-critical geometric Galton-Watsontree conditioned to survive.5.1 Main resultsWe write Geom(ξ) to denote a random variable which follows the geometricdistribution with parameter ξ ∈ (0, 1). In other words,P(Geom(ξ) = k) = (1− ξ)k−1ξ for k ≥ 1.For any ξ ∈ (0, 1) we shall use Tξ to denote the Galton-Watson tree with off-spring distribution Geom(ξ)− 1. We denote by T∞ξ the tree Tξ conditionedto be infinite. For ξ < 1/2 this tree is super-critical and hence the condi-tioning is in the classical sense. We define T∞1/2 to be the limit as n → ∞of the critical tree T1/2 conditioned to have n edges. This limit is known toexist in a much more general setting, see [63], Section 1.2 and Figure 1.2.Theorem 5.1.1. Assume gn is such that gn/n→ θ with θ ∈ [0, 1/2). Thenwe have the following convergence in distribution for the local topology:Ugn,n(d)−−−→n→∞T∞ξθ ,where ξθ = 1−βθ2 , and βθ is the unique solution in β ∈ [0, 1) of12( 1β − β)log 1 + β1− β = (1− 2θ). (5.1.1)4The results of this section are taken from the paper [9] and is joint work with OmerAngel, Guillaume Chapuy and Nicolas Curien1155.2. Enumeration and root degree distributionFor θ = 0, the genus is much smaller than the size of the map, so itis not surprising that the local limit is the same as that of a critical treeconditioned to survive.Note that the mean of the geometric offspring distribution in Theo-rem 5.1.1 is given by (1 + βθ)/(1 − βθ) > 1 and in particular the Galton-Watson tree is supercritical.In order to prove Theorem 5.1.1 we first determine the root degree dis-tribution of unicellular maps using the bijection of [34]. This is done inSection 5.2, where we also obtain an asymptotic formula for |Ug,n|. This en-ables us to compute in Section 5.4.1 the probability that the ball of radius raround the root in Ugn,n is equal to any given tree. In Chapter 4 it is shownthat the local limit of unicellular maps is supported on trees. However, wedo not rely on this result. In Section 5.5 we show that the probabilitiescomputed below are sufficient to characterize the local limit of Ug,n.5.2 Enumeration and root degree distributionRecall the definition of C-decorated tree from Section 4.2.1 and also re-call that the unicellular maps of genus g and n edges are in 2n+1 to onecorrespondence between C-decorated trees of genus g and n edges (Theo-rem 4.2.3)Using this correspondence we will obtain the two main theorems of thissection, Theorems 5.2.1 and 5.2.2. Before stating these theorems we in-troduce a probability distribution on the odd integers that will play animportant role in the sequel. For β ∈ (0, 1), we let Xβ be a random variabletaking its values in the odd integers, whose law is given by:P(Xβ = 2k + 1) :=1Zββ2k+12k + 1 ,whereZβ =∑k≥0β2k+12k + 1 =12 log1 + β1− β = arctanhβ.It is easy to check that eq. (5.1.1) is equivalent toE[Xβ] =1Zββ1− β2 =11− 2θ . (5.2.1)Theorem 5.2.1. Assume gn ∼ θn where θ ∈ (0, 1/2). Let βn be such thatE[Xβn ] = nsn + o(n−1/2)and sn = n + 1 − 2gn. As n tends to infinity we1165.2. Enumeration and root degree distributionhave|Ugn,n| ∼ Aθ(2n)!n!sn!√sn(Zβn)sn4gnβn+1n,where Aθ = 2√2piVar(Xβθ ).Note that βn → βθ. If gn = θn + o(√n) we may take βn to be just βθand not depend on n.Proof. For s, n ≥ 1, let Ls(n+ 1) be the set of partitions of n+ 1 having sparts, all of odd size. Recall that if λ is a partition of n+ 1, the number ofpermutations having cycle-type λ is given by(n+ 1)!∏imi!imi,where for i ≥ 1, mi = mi(λ) is the number of parts of λ with size equal toi. Therefore by Theorem 4.2.3, the number of unicellular maps of genus gnwith n edges is given by|Ugn,n| = Cat(n)2sn2n+1∑λ∈Lsn (n+1)(n+ 1)!∏imi!imi, (5.2.2)where Cat(n) = (2n)!n!(n+1)! is the nth Catalan number, i.e. the number of rootedplane trees with n edges, the sum counts permutations, and the powers of 2are from the signs on cycles of the permutation and since the correspondenceis 2n+1 to 1. Recall that this is the well-known Lehman-Walsh formula ([91])as was described in eq. (1.5.1).Now, let β ∈ (0, 1) and let X1, X2, . . . , Xs be i.i.d. copies of Xβ. Bythe local central limit theorem [80, Chap.7], if n + 1 = sE[Xβ] + o(√s)has the same parity as s, then P(∑i≤sXi = n + 1) ∼ As−1/2 whereA = 2/√2piVar(Xβ). The additional factor 2 comes from the fact thatthe support of Xi are odd numbers. On the other hand, we haveP∑i≤sXi = n+ 1 =∑k1+···+ks=n+1ki odd∏iβkiZβ · ki= βn+1(Zβ)s∑λ∈Ls(n+1)s!∏imi!imi, (5.2.3)1175.2. Enumeration and root degree distributionsince s!∏imi!is the number of distinct ways to order of the parts of thepartition λ.Therefore if, as in the statement of the theorem, we pick βn so thatE[Xβn ] = (n + 1)/sn + o(1/√n), noticing that βn → βθ and Var(Xβn) →Var(Xβθ), it follows from eq. (5.2.2) and the last considerations that|Ugn,n| ∼122gn Cat(n)(n+ 1)!sn!(Zβn)snβn+1nAθs−1/2n .The following theorem gives an asymptotic enumeration of unicellularmaps of high genus with a prescribed root degree.Theorem 5.2.2 (Root degree distribution). Assume gn ∼ θn with θ ∈(0, 1/2), and let βθ be the solution of eq. (5.1.1). Then for every d ∈ N wehaveP (Ugn,n has root degree d) −−−→n→∞(1− β2θ4) (1 + βθ)d − (1− βθ)d2dβθ.Equivalently, the degree of the root of Ugn,n converges in distribution to anindependent sum Geom(1+βθ2 ) + Geom(1−βθ2 )− 1.Proof. As in the proof of Theorem 5.2.1, we see that the length of a uniformlychosen cycle in a uniform random C-decorated tree with n edges and n +1− 2gn cycles is distributed as the random variable X1 conditioned on thefact that X1 + · · · + Xs = n + 1, where the Xi’s are i.i.d. copies of Xβ forany choice of β ∈ (0, 1), and s = n+ 1− 2gn. This follows by writing downthe required probability distributions and using eqs. (5.2.2) and (5.2.3) andTheorem 4.2.3. Using the local central limit theorem, we see that with βnchosen according to Theorem 5.2.1, when n tends to infinity, this randomvariable converges in distribution to Xβθ .Since the permutation is independent of the tree, the probability thata cycle contains the root vertex is proportional to its size. Therefore thesize of the cycle containing the root vertex converges in distribution to asize-biased version of Xβθ , which is a random variable K with distributionP(K = 2k + 1) = (1− β2θ )β2kθ , i.e. K = 2 Geom(1− β2θ )− 1.Now by Theorem 4.2.3, conditionally on the fact that the cycle containingthe root vertex has length 2k + 1, the root degree in Ugn,n is distributed as∑2ki=0Di, where D0 if the degree of the root of a random plane tree of sizen, and (Di)i>0 are the degrees of 2k uniformly chosen distinct vertices ofthe tree. It is classical, and easy to see, that when n tends to infinitythe variables (Di)i>0 converge in distribution to independent Geom(1/2)1185.3. The low genus caserandom variables, while D0 converges to Y +Y ′− 1, where Y, Y ′ are furtherindependent Geom(1/2) variables. All geometric variables here are alsoindependent of K.From this it is easy to deduce that when n tends to infinity, the rootdegree in Ugn,n converges in law to∑Ki=0 Yi−1 where K is as above and theYi’s are independent Geom(1/2) variables. Since the probability that thesum of ` i.i.d. Geom(1/2) random variables equals m is 2−m(m−1`−1), we thusobtain that for all d ≥ 1, the probability that the root vertex has degree dtends to:1− β2θβθ∑k≥0β2k+1θ 2−d−1( d2k + 1)= 1− β2θ4βθ(1 + βθ)d − (1− βθ)d2d .Remark 5.2.3. It may be possible to prove Theorem 5.2.2 using the enumer-ation results for unicellular maps by vertex degrees found in [57], althoughthis would require some computations. Here we prefer to prove it using thebijection of [34], since the proof is quite direct and gives a good understand-ing of the probability distribution that arises. This is also the reason weprove Theorem 5.2.1 from the bijection, rather than starting directly fromthe Lehman-Walsh formula (5.2.2).We now comment on a “paradox” that the reader may have noticed. Forany rooted graph G and any r ≥ 0 we denote by Br(G) the set of verticeswhich are at distance less than r from the origin of the graph. In Ug,n themean degree can be computed aslimr→∞1|Br(Ug,n)|∑u∈Br(Ug,n)deg(u) = 2nv −−−→n→∞ 2(1− 2θ)−1.However, if one interchanges limn→∞ and limr→∞ a different larger resultappears. Indeed, easy arguments about Galton-Watson processes show thatin T∞ξθ we havelimr→∞1|Br(T∞ξθ )|∑u∈Br(T∞ξθ)deg(u) = 21− βθ.5.3 The low genus caseProof of Theorem 5.1.1 for θ = 0. As noted, the case g = 0 is well known.We argue here that the local limit for g = o(n) is the same as for g = 0.1195.4. The local limitIndeed, the permutation on the tree contains n+ 1− 2g cycles, and so hasat most 3g non-fixed points. (If cycles of length 2 were allowed this wouldbe 4g.) Since the permutation is independent of the tree, and since theball of radius r in the tree distance is tight, the probability that any vertexin the ball is in a non-trivial cycle is o(1) (with constant depending on r).In particular, the local limit of the unicellular map and of the tree are thesame.5.4 The local limit5.4.1 SurgeryThroughout this subsection, we fix integers n, g ≥ 0. Let t be a rooted planetree of height r ≥ 1 with k edges and exactly d vertices at height r.Lemma 5.4.1. For any n, g, k, d, r ≥ 0 we have|{m ∈ Ug,n : Br(m) = t}| = |{m ∈ Ug,n−k+d with root degree d}|.Proof. The lemma follows from a surgical argument illustrated in Fig. 5.1:if m ∈ Ug,n is such that Br(m) = t we can replace the r-neighborhood of theroot by a star made of d edges which diminishes the number of edges of themap by k − d and turns it into a map of Ug,n−k+d having root degree d. Tobe precise, consider the leaf of t first reached in the contour around t. Theedge to this leaf is taken to be the root of the new map.Figure 5.1: Illustration of the surgical operation1205.5. Identifying the limitIt is clear that this operation is invertible. To see that it is a bijectionbetween the two sets in question we need to establish that it does not changethe genus or number of faces in a map. One way to see this is based on analternative description of the surgery, namely that it contracts every edgeof t except those incident to the leaves, and it is easy to see that edgecontraction does not change the number of faces or genus of a map.5.5 Identifying the limitRecall that for ξ ∈ (0, 1) we denote by Tξ the law of a Galton-Watson treewith Geom(ξ) − 1 offspring distribution. Note that when ξ ∈ (0, 1/2) themean offspring is strictly greater than 1 and so the process is supercritical,and recall that T∞ξ is Tξ conditioned to survive. Plane trees can be viewedas maps, rooted at the edge from the root to its first child. For every r ≥ 0,if t is a (possibly infinite) plane tree we denote by Br(t) the rooted subtreeof t made of all the vertices at height less than or equal to r.Proposition 5.5.1. Fix ξ ∈ (0, 1/2). For any tree t of height exactly rhaving k edges and exactly d vertices at maximal height, we haveP(Br(T∞ξ ) = t)=(ξ(1− ξ))k+1−d((1− ξ)d − ξd)1− 2ξ .Note that the probability of observing t does not depend on r, but onlyon the number of edges and vertices where t is connected to the rest of Tξ.Proof. Since ξ ∈ (0, 1/2) the Galton-Watson process is supercritical and bystandard result the extinction probability pdie is strictly less than 1 and isthe root of x =∑k≥0 xk(1− ξ)kξ in (0, 1). Hencepdie =ξ1− ξ .Next, fix a tree t of height exactly r with k edges and d vertices at heightr. By the definition of Tξ if ku denotes the number of children of the vertexu in t we haveP(Br(Tξ) = t) =∏u(1− ξ)kuξ = (1− ξ)kξk+1−dwhere the product is taken over all the vertices of t which are at height lessthan r. Conditioned on the event {Br(Tξ) = t}, by the branching property,1215.5. Identifying the limitthe probability that the tree survives forever is (1 − pddie). Combining thepieces, we get the statement of the proposition.Proof of Theorem 5.1.1 for θ ∈ (0, 1/2). Under the assumptions of Theorem 5.1.1,fix r and let t be a rooted oriented tree of height exactly r having k edgesand exactly d vertices at height r. By Lemma 5.4.1 we haveP(Br(Ugn,n) = t) =|{m ∈ Ugn,n−k+d with root degree d}||Ugn,n|= |Ugn,n−k+d||Ugn,n|· P(root degree of Ugn,n−k+d = d).Applying Theorem 5.2.2 we haveP(root degree of Ugn,n−k+d = d) −−−→n→∞(1− β2θ4βθ) (1 + βθ)d − (1− βθ)d2d .(5.5.1)On the other hand, since n/s = (n − k + d)/(s − k + d) + o(1/√n) we canapply Theorem 5.2.1 for the asymptotic of |Ugn,n−k+d| and |Ugn,n| with thesame sequence (βn) and get that|Ugn,n−k+d||Ugn,n|∼(2n+ 2d− 2k)!n!s!Zd−kβn(2n)!(n+ d− k)!(s+ d− k)!βd−kn.Since d, k are fixed, and using the facts that βn → βθ, Zβn → Zβθ ands/n→ (1− 2θ), the last display is also equivalent to|Ugn,n−k+d||Ugn,n|∼(βθ(1− 2θ)4Zβθ)k−d=(1− β2θ4)k−d, (5.5.2)by the definition of βθ in eq. (5.2.1). Plugging (5.5.1) and (5.5.2) togetherand using Proposition 5.5.1 we find thatP(Br(Ugn,n) = t) −−−→n→∞ P(Br(T∞ξθ ) = t),with ξθ = (1− βθ)/2.Finally, note that the law of Br(T∞ξθ ) is a probability measure on theset of finite plane trees. It follows that Br(Ugn,n) is tight, and converges indistribution to Br(T∞ξθ ). Since r is arbitrary, this completes the proof of theTheorem.1225.6. Questions and remarks5.6 Questions and remarksPlanarity. A consequence of Theorem 5.1.1 is that Ugn,n is locally a tree(hence planar) near its root. More precisely, the length of a minimal non-trivial cycle containing the root edge diverges in probability as n → ∞.Note that a much stronger statement has been proved in Chapter 4 wherequantitative estimates on cycle lengths are obtained. As noted above, theproof presented in this section does not rely on this result and our approachis softer. Note that our method of proof only requires to prove convergencesof the quantities P(Br(Ugn,n) = t) when t is a tree since we were able toidentify these limits as coming from a probability measure on infinite trees.Open questions. We gather here a couple of possible extensions of ourwork.Question 5.6.1. Find more precise asymptotic formulae for |Ug,n| as thesequence {g, n} → {∞,∞}. Theorem 5.2.1 gives a first order approximation.Question 5.6.2. Quantify the convergence of Ugn,n to Tξθ . In particular,let rn = o(log n). Is it possible to couple Ugn,n with Tξθ so that Brn(Ugn,n) =Brn(Tξθ) with high probability?123Bibliography[1] L. Addario-Berry, N. Broutin, and C. Goldschmidt. The continuumlimit of critical random graphs. Probab. Theory Related Fields, 152(3-4):367–406, 2012.[2] L. Addario-Berry, N. Broutin, C. Goldschmidt, and G. Miermont. Thescaling limit of the minimum spanning tree of the complete graph. 2013.arXiv:1301.1664.[3] L. Addario-Berry, L. Devroye, and S. Janson. Sub-Gaussian tail boundsfor the width and height of conditioned Galton-Watson trees. Ann.Probab., 41(2):1072–1087, 2013.[4] D. Aldous. The continuum random tree. I. Ann. Probab., 19(1):1–28,1991.[5] D. Aldous and J. M. Steele. The objective method: probabilistic com-binatorial optimization and local weak convergence. In Probability ondiscrete structures, volume 110 of Encyclopaedia Math. Sci., pages 1–72.Springer, Berlin, 2004.[6] J. Ambjørn. Quantization of geometry. In Ge´ome´tries fluctuantes enme´canique statistique et en the´orie des champs (Les Houches, 1994),pages 77–193. North-Holland, Amsterdam, 1996.[7] O. Angel. Growth and percolation on the uniform infinite planar tri-angulation. Geom. Funct. Anal., 13(5):935–974, 2003.[8] O. Angel. Scaling of percolation on infinite planar maps, I.arXiv:math/0501006, 2005.[9] O. Angel, G. Chapuy, N. Curien, and G. Ray. The local limit of uni-cellular maps in high genus. Elec. Comm. Prob, 18:1–8, 2013.[10] O. Angel and N. Curien. Percolations on random maps I: half-planemodels. Ann. Inst. H. Poincare´, 2013. To appear.124Bibliography[11] O. Angel, A. Nachmias, and G. Ray. Random walks in stochastic hy-perbolic planar triangulations. In preparation, 2014.[12] O. Angel and G. Ray. Classification of half planar maps. Ann. Probab.,2013. arXiv:1303.6582.[13] O. Angel and O. Schramm. Uniform infinite planar triangulations.Comm. Math. Phys., 241(2-3):191–213, 2003.[14] K. Athreya and P. Ney. The local limit theorem and some relatedaspects of supercritical branching processes. Trans. Amer. Math. Soc.,152(2):233251, 1970.[15] C. Banderier, P. Flajolet, G. Schaeffer, and M. Soria. Planar maps andAiry phenomena. In Automata, languages and programming (Geneva,2000), volume 1853 of Lecture Notes in Comput. Sci., pages 388–402.Springer, Berlin, 2000.[16] C. Banderier, P. Flajolet, G. Schaeffer, and M. Soria. Random maps,coalescing saddles, singularity analysis, and Airy phenomena. RandomStructures Algorithms, 19(3-4):194–246, 2001. Analysis of algorithms(Krynica Morska, 2000).[17] M. T. Barlow, A. A. Ja´rai, T. Kumagai, and G. Slade. Random walk onthe incipient infinite cluster for oriented percolation in high dimensions.Comm. Math. Phys., 278(2):385–431, 2008.[18] I. Benjamini. Random planar metrics. In Proceedings of the Interna-tional Congress of Mathematicians. Volume IV, pages 2177–2187, NewDelhi, 2010. Hindustan Book Agency.[19] I. Benjamini. Coarse geometry and randomness.cole dt de Probabilits de Saint-Flour XLI, 2011.http://www.wisdom.weizmann.ac.il/ itai/stflouraug24.pdf.[20] I. Benjamini and N. Curien. Simple random walk on the uniform infi-nite planar quadrangulation: subdiffusivity via pioneer points. Geom.Funct. Anal., 23(2):501–531, 2013.[21] I. Benjamini, R. Lyons, and O. Schramm. Unimodular random trees.arXiv:1207.1752, 2012.[22] I. Benjamini and O. Schramm. Recurrence of distributional limits offinite planar graphs. Electron. J. Probab., 6:no. 23, 1–13, 2001.125Bibliography[23] I. Benjamini and O. Schramm. KPZ in one dimensional random geom-etry of multiplicative cascades. Comm. Math. Phys., 289(2):653–662,2009.[24] I. Benjamini and O. Schramm. Percolation beyond Zd, many questionsand a few answers [mr1423907]. In Selected works of Oded Schramm.Volume 1, 2, Sel. Works Probab. Stat., pages 679–690. Springer, NewYork, 2011.[25] O. Bernardi. An analogue of the Harer-Zagier formula for unicellularmaps on general surfaces. Adv. in Appl. Math., 48(1):164–180, 2012.[26] O. Bernardi and G. Chapuy. Counting unicellular maps on non-orientable surfaces. Adv. in Appl. Math., 47(2):259–275, 2011.[27] J. Bettinelli. Scaling limits for random quadrangulations of positivegenus. Electron. J. Probab., 15:no. 52, 1594–1644, 2010.[28] J. D. Biggins and N. H. Bingham. Large deviations in the supercriticalbranching process. Adv. in Appl. Probab., 25(4):757–772, 1993.[29] P. Billingsley. Convergence of probability measures. Wiley Series inProbability and Statistics: Probability and Statistics. John Wiley &Sons, Inc., New York, second edition, 1999. A Wiley-Interscience Pub-lication.[30] J. Bouttier and E. Guitter. Distance statistics in quadrangulations witha boundary, or with a self-avoiding loop. J. Phys. A, 42(46):465208, 44,2009.[31] W. G. Brown. Enumeration of triangulations of the disk. Proc. LondonMath. Soc. (3), 14:746–768, 1964.[32] C. E. Burgess. Classification of surfaces. Amer. Math. Monthly,92(5):349–354, 1985.[33] G. Chapuy. A new combinatorial identity for unicellular maps, via adirect bijective approach. Adv. in Appl. Math., 47(4):874–893, 2011.[34] G. Chapuy, V. Fe´ray, and E´. Fusy. A simple model of trees for unicel-lular maps. Journal of Combinatorial Theory, Series A, 120(8):2064–2092, 2013.[35] G. Chapuy, M. Marcus, and G. Schaeffer. A bijection for rooted mapson orientable surfaces. SIAM J. Discrete Math., 23(3):1587–1611, 2009.126Bibliography[36] P. Chassaing and G. Schaeffer. Random planar lattices and integratedsuperBrownian excursion. Probab. Theory Related Fields, 128(2):161–212, 2004.[37] R. Cori and B. Vauquelin. Planar maps are well labeled trees. Canad.J. Math., 33(5):1023–1042, 1981.[38] N. Curien. A glimpse of the conformal structure of random planarmaps. arXiv:1308.1807, 2013.[39] N. Curien. Planar stochastic hyperbolic infinite triangulations.arXiv:1401.3297, 2014.[40] N. Curien, B. Haas, and I. Kortchemski. The CRT is the scaling limitof random dissections. 2013. arXiv:1305.3534.[41] N. Curien and I. Kortchemski. Percolation on random triangulationsand stable looptrees. 2013. arXiv:1307.6818.[42] N. Curien and J.-F. Le Gall. The Brownian plane. J. Theoret. Probab.,pages 1–43, 2012.[43] N. Curien, L. Me´nard, and G. Miermont. A view from infinity of theuniform infinite planar quadrangulation. ALEA Lat. Am. J. Probab.Math. Stat., 10(1):45–88, 2013.[44] N. Curien and G. Miermont. Uniform infinite planar quadrangulationswith a boundary. Random Structures Algorithms, 2012. to appear.[45] B. Davis and D. McDonald. An elementary proof of the local centrallimit theorem. J. Theoret. Probab., 8(3):693–701, 1995.[46] L. Devroye and S. Janson. Distances between pairs of vertices andvertical profile in conditioned Galton-Watson trees. Random StructuresAlgorithms, 38(4):381–395, 2011.[47] B. Duplantier and S. Sheffield. Liouville quantum gravity and KPZ.Invent. Math., 185(2):333–393, 2011.[48] R. Durrett. Probability: theory and examples. Cambridge Series inStatistical and Probabilistic Mathematics. Cambridge University Press,Cambridge, fourth edition, 2010.[49] W. Feller. An introduction to probability theory and its applications.Vol. II. Second edition. John Wiley & Sons Inc., New York, 1971.127Bibliography[50] K. Fleischmann and V. Wachtel. Lower deviation probabilities for su-percritical Galton-Watson processes. Ann. Inst. H. Poincare´ Probab.Statist., 43(2):233–255, 2007.[51] R. G. Gallager. Discrete stochastic processes, volume 101. KluwerAcademic Publishers Boston, 1996.[52] A. Gamburd. Poisson-Dirichlet distribution for random Belyi surfaces.Ann. Probab., 34(5):1827–1848, 2006.[53] A. Gamburd and E. Makover. On the genus of a random Riemannsurface. In Complex manifolds and hyperbolic geometry (Guanajuato,2001), volume 311 of Contemp. Math., pages 133–140. Amer. Math.Soc., Providence, RI, 2002.[54] Z. Gao. The number of rooted triangular maps on a surface. J. Combin.Theory Ser. B, 52(2):236–249, 1991.[55] Z. Gao. A pattern for the asymptotic number of rooted maps on sur-faces. J. Combin. Theory Ser. A, 64(2):246–264, 1993.[56] I. P. Goulden and D. M. Jackson. Combinatorial enumeration. AWiley-Interscience Publication. John Wiley & Sons Inc., New York,1983. With a foreword by Gian-Carlo Rota, Wiley-Interscience Seriesin Discrete Mathematics.[57] A. Goupil and G. Schaeffer. Factoring n-cycles and counting maps ofgiven genus. European J. Combin., 19(7):819–834, 1998.[58] M. Gromov. Metric structures for Riemannian and non-Riemannianspaces. Modern Birkha¨user Classics. Birkha¨user Boston Inc., Boston,MA, english edition, 2007. Based on the 1981 French original, Withappendices by M. Katz, P. Pansu and S. Semmes, Translated from theFrench by Sean Michael Bates.[59] O. Gurel-Gurevich and A. Nachmias. Recurrence of planar graph limits.Ann. of Math. (2), 177(2):761–781, 2013.[60] T. E. Harris. The theory of branching processes. Dover Phoenix Edi-tions. Dover Publications Inc., Mineola, NY, 2002. Corrected reprintof the 1963 original [Springer, Berlin; MR0163361 (29 #664)].[61] Z.-X. He and O. Schramm. Hyperbolic and parabolic packings. DiscreteComput. Geom., 14(2):123–149, 1995.128Bibliography[62] N. I. Kazimirov. The occurrence of a gigantic component in a randompermutation with a known number of cycles. Diskret. Mat., 15(3):145–159, 2003.[63] H. Kesten. Subdiffusive behavior of random walk on a random cluster.Ann. Inst. H. Poincare´ Probab. Statist., 22(4):425–487, 1986.[64] V. G. Knizhnik, A. M. Polyakov, and A. B. Zamolodchikov. Fractalstructure of 2D-quantum gravity. Modern Phys. Lett. A, 3(8):819–826,1988.[65] M. Krikun. Local structure of random quadrangulations.arXiv:math/0512304, 2005.[66] T. Kumagai and J. Misumi. Heat kernel estimates for strongly recurrentrandom walk on random media. J. Theoret. Probab., 21(4):910–935,2008.[67] K. Kuratowski. Topology. Vol. I. New edition, revised and augmented.Translated from the French by J. Jaworowski. Academic Press, NewYork, 1966.[68] S. K. Lando and A. K. Zvonkin. Graphs on surfaces and their applica-tions, volume 141 of Encyclopaedia of Mathematical Sciences. Springer-Verlag, Berlin, 2004. With an appendix by Don B. Zagier, Low-Dimensional Topology, II.[69] J.-F. Le Gall. Random trees and applications. Probab. Surv., 2:245–311,2005.[70] J.-F. Le Gall. Uniqueness and universality of the Brownian map. Ann.Probab., 41(4):2880–2960, 2013.[71] D. A. Levin, Y. Peres, and E. L. Wilmer. Markov chains and mixingtimes. American Mathematical Society, Providence, RI, 2009. With achapter by James G. Propp and David B. Wilson.[72] R. Lyons and Y. Peres. Probability on Trees and Networks. CambridgeUniversity Press. In preparation. Current version available athttp://mypage.iu.edu/~rdlyons/.[73] W. S. Massey. Algebraic topology: an introduction. Springer-Verlag,New York, 1977. Reprint of the 1967 edition, Graduate Texts in Math-ematics, Vol. 56.129Bibliography[74] L. Me´nard and P. Nolin. Percolation on uniform infinite planar maps.2013. arXiv:1302.2851.[75] G. Miermont. Random maps and their scaling limits. In Fractal geom-etry and stochastics IV, volume 61 of Progr. Probab., pages 197–224.Birkha¨user Verlag, Basel, 2009.[76] G. Miermont. The Brownian map is the scaling limit of uniformrandom plane quadrangulations. Acta Mathematica, to appear, 2011.arXiv:1104.1606.[77] J. Miller and S. Sheffield. Quantum Loewner Evolution.arXiv:1312.5745, 2013.[78] B. Mohar and C. Thomassen. Graphs on surfaces. Johns HopkinsStudies in the Mathematical Sciences. Johns Hopkins University Press,Baltimore, MD, 2001.[79] S. V. Nagaev and N. V. Vahrusev. Estimation of probabilities of largedeviations for a critical Galton-Watson process. Theory Probab. Appl.,20(1):179180, 1975.[80] V. V. Petrov. Sums of independent random variables. Springer-Verlag,New York, 1975. Translated from the Russian by A. A. Brown, Ergeb-nisse der Mathematik und ihrer Grenzgebiete, Band 82.[81] G. Ray. Large unicellular maps in high genus. Ann. Inst. H. Poincare´,2013. To appear. arXiv:1307.1224.[82] G. Ray. Geometry and percolation on half planar triangulations. Elec-tron. J. Probab., 19(47):1–28, 2014.[83] H. Ren, Y. Liu, and Z. Li. Enumeration of 2-connected loopless 4-regular maps on the plane. European J. Combin., 23(1):93–111, 2002.[84] G. Schaeffer. Conjugaison d’arbres et cartes combinatoires ale´atoires.PhD thesis, 1998.[85] O. Schramm. Scaling limits of loop-erased random walks and uniformspanning trees. Israel J. Math., 118:221–288, 2000.[86] C. Thomassen. Isoperimetric inequalities and transient random walkson graphs. Ann. Probab., 20(3):1592–1600, 1992.130[87] W. T. Tutte. A census of planar triangulations. Canad. J. Math.,14:21–38, 1962.[88] W. T. Tutte. A census of slicings. Canad. J. Math., 14:708–722, 1962.[89] W. T. Tutte. A census of planar maps. Canad. J. Math., 15:249–271,1963.[90] B. Vira´g. Anchored expansion and random walk. Geom. Funct. Anal.,10(6):1588–1605, 2000.[91] T. R. S. Walsh and A. B. Lehman. Counting rooted maps by genus. J.Combin. Theory Ser. B., 13:192–218, 1972.[92] Y. Watabiki. Construction of non-critical string field theory by transfermatrix formalism in dynamical triangulation. Nuclear Phys. B, 441(1-2):119–163, 1995.131Appendix AProof of lemma 3.2.2Recall that Im(q) denotes the number of internal vertices of a free trian-gulation of an m-gon and recall the variable θ used in Section 2.5.1 whereq = θ(1− 2θ)2.Proof of Lemma 3.2.2 part (i). Without loss of generality assume x is aninteger. Let dθ = 4θ(1−6θ) . For simplicity of notation let Im(q) = Im. Noticethat conditioned on Y = k, expectation of IY+1 is dθk + O(1) as k → ∞.We want,P(Y + IY+1 > x) =∑k≥1P(IY+1 > x− k|Y = k)P(Y = k) (A.0.1)The trick is to break the sum in (A.0.1) into sums over three subsets ofindices:(i) A1 = {1 ≤ k ≤ bx/(1 + dθ)− x3/4c}(ii) A3 = {k > bx/(1 + dθ) + x3/4c}(iii) A2 = N \ (A1 ∪A3)The sum over A2 is O(x−3/4) by bounding P(IY+1 > x− k|Y = k) by 1 andusing P(Y = k) ∼ ck−3/2. Now note∑A1P(IY+1 > x− k|Y = k)P(Y = k) (A.0.2)<∑A1P(IY+1 − E(IY+1|Y = k) > x3/4 +O(1)|Y = k)P(Y = k) (A.0.3)<∑A1V ar(IY+1|Y = k)x3/2 P(Y = k) = O(x−1). (A.0.4)where we used Proposition 3.2.1 part (i) for (A.0.3) and Chebyshev’s in-132Appendix A. Proof of lemma 3.2.2equality followed by Proposition 3.2.1 part (ii) for (A.0.4). Finally,∑k∈A3P(IY+1 > x− k|Y = k)P(Y = k) (A.0.5)=∑k∈A3P(Y = k)−∑k∈A3P(IY+1 ≤ x− k|Y = k)P(Y = k) (A.0.6)=∑k∈A3P(Y = k)−O(x−1) (A.0.7)where the bound in the second term in the right hand side of (A.0.7) fol-lows in the same way as (A.0.4) using Chebyshev’s inequality and Propo-sition 3.2.1 part (ii) plus the fact that the summands are 0 when k > x.Finally it is easy to verify that∑k∈A3 P(Y = k) ∼ cθx−1/2 for some con-stant cθ > 0.Proof of Lemma 3.2.2 part (ii). Note thatE((Y + IY+1)1{Y+IY+1<x}) =x−1∑k=1(P(Y + IY+1 ≥ k)− P(Y + IY+1 ≥ x))(A.0.8)Now the asymptotics follows by using the asymptotics of part (i).Proof of Lemma 3.3.2. Observe that the expected change is given byα−∑i≥1ipi = 1−∑i≥1(i+ 1)piwhere pi is given by eq. (2.8.3) and the equality follows from the fact that∑i≥1 pi = 1− α. Now from eq. (2.8.3),∑i≥1(i+ 1)pi =∑i≥12Cat(i− 1)(2/α− 24)i((3α− 2)i+ 1) (A.0.9)where Cat(n) = 1n+1(2nn)is the nth catalan number. The sum in the righthand side of eq. (A.0.9) can be easily computed using generating functionsof catalan numbers. We leave this last step to the reader.133Appendix BProof of lemma 4.2.6We shall prove Lemma 4.2.6 in this section. We do the computation followingthe method of random allocation similar in lines of [62]. For this, we need tointroduce i.i.d. random variables {ξ1, ξ2, . . .} such that for some parameterβ ∈ (0, 1)P (ξ1 = i){= βiB(β)(i) if i is odd positive integer= 0 otherwise(B.0.1)where B(β) = 1/2 log((1 + β)/(1 − β)). Recall that P is the set of all N -tuples of odd positive integers which sum up to n+ 1. Observe that for anyz = (z1, . . . , zN ) ∈ P,P (λ = z) = P (ξ1 = z1, . . . , ξN = zN |ξ1 + ξ2 + . . . ξN = n+ 1)throughout this Section, we shall assume the following:• {n,N} → {∞,∞} and n/N → α for some constant α > 1.• For every n, the parameter β = β(n) is chosen such that E(ξ1) = m =(n+ 1)/NIt is easy to check using (B.0.1) that there is a unique choice of such βand β converges to some finite number βα such that 0 < βα < 1 as (n+1)/Nconverges to α. Let ζN,j = ξj1 + . . . ξjN where j ≥ 1 is an integer. It is alsoeasy to see that for any integer j ≥ 1, Eξj1 = mj(n) for some function mjwhich also converge to some number mjα as n→∞. Let σ2j = V ar(ξj1). Tosimplify notation, we shall denote ζN,1 by ζN and σ1 by σ.We will first prove a central limit theorem for ζN .Lemma B.0.3. We have,ζN −Nmσ√N→ N(0, 1) (B.0.2)in distribution as n→∞.134Appendix B. Proof of lemma 4.2.6Proof. Easily follows by checking the Lyapunov condition for triangular ar-rays of random variables (see [48]).We now prove a local version of the CLT asserted by Lemma B.0.3.Lemma B.0.4. We haveP (ζN = n+ 1) ∼2√2piNσProof. Let ξi = (ξi−1)/2. Apply Theorem 1.2 of [45] for the modified arrays{ξ1, . . . ξN}n≥1 and use Lemma B.0.3. The details are left for the readers tocheck.Lemma B.0.5. Fix j ≥ 1. There exists constants C1 > 1 and C2 > 1 (bothdepending only on α and j) such thatP(C1n <N∑i=1λji < C2n)> 1− cn7/2 (B.0.3)for some c > 0 which again depends only on α and j for large enough n.Proof. It is easy to see that mj → mjα as n→∞. Notice thatP(N∑i=1λji > C2n,N∑i=1λji < C1n)= P (ζN,j > C2n, ζN,j < C1n|ζN = n)< P (ζN,j > C2n, ζN,j < C1n)P (ζN = n)(B.0.4)Choose C2 > mjα and C1 < mjα. Then for some c > 0, for large enough n,P (ζN,j > C2n, ζN,j < C1n) < P (|ζN,j −mjN | > cn)< E (ζN,j −mjN)8 (cn)−8 (B.0.5)It is easy to see that E (ζN,j −mjN)8 = O(n4) since the terms involvingE(ξji − mj) vanishes and all the finite moments of ξ1 are bounded. Nowplugging in this estimate into eq. (B.0.5), we getP (ζN,j > C2n, ζN,j < C1n) = O(n−4) (B.0.6)Now plugging in the estimate of eq. (B.0.6) into eq. (B.0.4) and observingthat P (ζN = n)  N−1/2 via Lemma B.0.4, the result follows.135Appendix B. Proof of lemma 4.2.6Lemma B.0.6. There exists a constant C0 > 0 such thatP (λmax > C0 log n) = O(n−3)Proof. Let ξmax be the maximum among ξ1, . . . , ξN . Note thatP(ξmax > C0 log n) < NP(ξ1 > C0 log n) = O(NβC0 logn) = O(n−7/2)(B.0.7)if C0 > 0 is chosen large enough. Now the Lemma follows from the estimateof Lemma B.0.4. The details are left to the reader.Lemma B.0.7. There exists constants 0 < d1 < 1 and 0 < d2 < 1 whichdepends only on α such that P(d1n < |i : λi = 1| < d2n) < e−cn for someconstant c > 0 for large enough n.Proof. The probability that |i : λi = 1| < d2n for large enough n for some0 < d2 < 1 follows directly from the fact that |i : λi = 1| ≤ N . For theupper bound,P(|i : λi = 1| > d1n) = P(N∑i=11λi=1 > d1n)<P(∑Ni=1 1ξi=1 > d1n)P(ζN = n)(B.0.8)Now P(ξi = 1)→ βα/B(βα) as n→∞. The Lemma now follows by choosingd1 small enough, applying Lemma B.0.4 to the denominator in eq. (B.0.8)and a suitable large deviation bound on Bernoulli variables. Details arestandard and is left to the reader.Proof of Lemma 4.2.6. Follows from Lemmas B.0.5–B.0.7.136Appendix CProofs of the lemmas insection 4.2.3In this section, we shall prove Lemmas 4.2.8 and 4.2.10.Let pi denote P(ξ = i) for i ∈ N and denote the generating function byϕ(s) =∑i pisi. Let µ = Eξ. Let Zn denote the number of offsprings in then-th generation of the Galton-Watson processC.1 Critical Galton-Watson treesWe assume ξ has geometric distribution with parameter 1/2. Here µ = 1and we want to show that Zr cannot be much more than r. The followinglarge deviation result is a special case of the main theorem of [79].Proposition C.1.1. For all r ≥ 1 and k ≥ 1,P(Zr ≥ k) <32(1 + 1ϕ′′(3/2)r/2 + 2)−kC.2 Supercritical Galton-Watson treesHere µ > 1. Recall the assumptions• 0 < p0 + p1 < 1• There exists a small enough λ > 0 such that E(eλξ) <∞.It is well known (see [60]) that Zn/µn is a martingale which converges almostsurely to some non-degenerate random variable W . Let ρ := P (limn Zn = 0)be the extinction probability which is strictly less than 1 in the supercriticalregime.The following results may be realized as special cases of the results in[14], [50] and further necessary references can be found in these papers.137C.3. Random plane treesW if restricted to (0,∞) has a strictly positive continuous density whichis denoted by w. In other words, we have the following limit theorem:limnP(Zn ≥ xµn) =∫ ∞xw(t)dt, x > 0Also define γ := ϕ′(ρ) where 0 < γ < 1 in our case. Define β by the relationγ = µ−β. It is clear that in our case β ∈ (0,∞). β is used to determine thebehavior of w as x ↓ 0. The following is proved in [14].Proposition C.2.1. Let η := µβ/(3+β) > 1. Then for all ε ∈ (0, η), thereexists a positive constant Cε > 0 such that for all k ≥ 1,|P(Zr = k)µr − w(k/µr)| ≤ Cεη−rkµ−r + (η − ε)−r (C.2.1)for all r ≥ 1.It can be shown (see [28]) that there exists positive constants A1 >0, A2 > 0 such that A1xβ−1 < w(x) < A2xβ−1 as x ↓ 0. Using this andeq. (C.2.1), we getP(Zr = k) ≤ Ckβ−1µrβ +η−rk + ((η − ε)µ)−r (C.2.2)Proof of Lemma 4.2.8. The proof is straightforward by summing k from 1to γr the expression given by the right hand side of (C.2.2).C.3 Random plane treesProof of Lemma 4.2.10. Note that it is enough to prove the bound for r ≤ nbecause otherwise the probability is 0. It is well known that if we pickan oriented edge uniformly from U0,n and re-root the tree there then thedistribution of this new re-rooted tree is the same as that of U0,n (see [46]).Let V denote the root vertex of the new re-rooted tree and let Zj(V ) denotethe number of vertices at distance exactly j from V . It is well known thatthe probability of a critical geometric Galton-Watson tree to have n edgesis  n−3/2. Using this fact and Proposition C.1.1 we get for any k ≥ 1 and1 ≤ j ≤ rP(Zj(V ) > k) < n3/2c exp(−c′k/j) < n3/2c exp(−c′k/r) (C.3.1)138C.3. Random plane treesand some suitable positive constants c, c′. Note that if Mr > r2 log2 n thenZj(v) > r log2 n for some 1 ≤ j ≤ r and some vertex v ∈ U0,n. Using thisand union bound to the estimate obtained in (C.3.1), we getP(Mr > r2 log2 n) < cn5/2r exp(−c′ log2 n) = O(exp(−c′ log2 n))for some positive constants c and c′. This completes the proof.139


Citation Scheme:


Citations by CSL (citeproc-js)

Usage Statistics



Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            async >
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:


Related Items