Markovian explorations of random planar maps are roundish
Nicolas Curien Cyril Marzouk





Discovery of a nitrogen-enhanced mildly metal-poor binary system: Possible evidence for pollution from an extinct AGB Star
    
José G. Fernández-Trincado1,2,3,
Ronald Mennickent3,
Mauricio Cabezas4, 
Olga Zamora5,6,
Sarah L. Martell7,8,
Timothy C. Beers9,
Vinicius M. Placco9,
David M. Nataf10,
Szabolcs Mészáros11,12,
Dante Minniti13, 14, 15,
Dominik R. G. Schleicher3,
Baitian Tang16,
Angeles Pérez-Villegas17,
Annie C. Robin2,
Céline Reylé2,
and
Mario Ortigoza-Urdaneta1

    Received ...; Accepted ...
================================================================================================================================================================================================================================================================================================================================================================





The infinite discrete stable Boltzmann maps are “heavy-tailed”  generalisations of the well-known Uniform Infinite Planar Quadrangulation. Very efficient tools to study these objects are Markovian step-by-step explorations of the lattice called peeling processes. Such a process depends on an algorithm which selects at each step the next edge where the exploration continues. We prove here that, whatever this algorithm, a peeling process always reveals about the same portion of the map, thus growing roughly metric balls. Applied to well-designed algorithms, this easily enables us to compare distances in the map and in its dual, as well as to control the so-called pioneer points of the simple random walk, both on the map and on its dual.







§ INTRODUCTION





  
Peeling process. Since the introduction of the UIPT (Uniform Infinite Planar Triangulation) by Angel & Schramm <cit.>, the study of the large scale properties of infinite planar maps has been an intensive field of research. One of the main tools to study these random graphs, is the so-called peeling process which is a Markovian way to explore these random discrete surfaces step-by-step and connects them with random walks. It has fruitfully been used in the case of the UIPT (or its quadrangular cousin the UIPQ) to study e.g. its geometry <cit.>, the behaviour of the simple random walk <cit.>, its conformal structure <cit.> or fine properties of percolation <cit.>. The idea of Markovian exploration of random triangulations can be traced back to Watabiki in the physics literature and it was formalised first by Angel <cit.>. Later Budd <cit.> introduced a different and more robust version of it which we will use below.

The main advantage of the peeling process is the flexibility on the choice of the exploration, which depends on an algorithm, and the results cited above were obtained using different peeling algorithms. However, certain properties of the peeling process are universal in the sense that they do not depend upon the algorithm: for example the law of the underlying random walk driving the perimeter process, or the fact that any peeling algorithm eventually discovers the complete underlying lattice <cit.>. In this work we will show, in a rather strong sense, that all Markovian explorations of the UIPT/UIPQ are bound to discover roughly the same portion of the map at time n. In fact, our result applies more generally to infinite (bipartite) “discrete stable” Boltzmann maps whose definition we now recall.



  
Infinite Boltzmann map and the filled-in peeling process. As usual, all planar maps in this work are rooted, i.e. equipped with a distinguished oriented edge, and as it is customary, we will only consider bipartite planar maps (all faces have even degree). Given a non-zero sequence 𝐪= (q_k)_ k ≥ 1 of non-negative numbers we define the Boltzmann measure w on the set of all bipartite planar maps by the formula

    w() ∏_f∈Faces() q_deg(f)/2.

We shall assume that  is a critical weight sequence of type a ∈ (3/2, 5/2]. This means that the equation z  =1 + ∑_i ≥ 12i-1i-1 q_i z^i has a unique solution Z_ > 1 and that the probability measure 

    μ(0)=Z_^-1    and    μ(k)=Z_^k-12k-1k-1q_k.

has mean one, and either it has finite variance in the case a = 5/2, or it is in the strict domain of attraction of an (a-1)-stable distribution i.e. μ([k,∞)) ∼ c k^-a+1 for some constant c>0 as k →∞, see <cit.> and <cit.> for details. One can then define (using the assumption of criticality only) a random infinite bipartite map  _∞ of the plane as the local weak limit of random maps sampled according to w(·) and conditioned to be large, see <cit.>. We will consider so-called filled-explorations of _∞ which are sequences of submaps with one hole

    _0⊂⋯⊂_n⊂⋯⊂_∞,

obtained by starting with the root-edge _0 of _∞ and iteratively peeling an edge on the boundary of _n at each step. If the peeling of an edge creates more than one hole, then we immediately fill-in the finite part (recall that _∞ is one-ended), see Section <ref> and <cit.> for details. As recalled above, these explorations depend on an algorithm, hereafter denoted by 𝒜 to choose the next edge to peel 𝒜( _n) on the boundary of the explored part. This algorithm can be deterministic or it may depend on another source of randomness, as long as it is independent of _∞,  and we denote by (^_n)_n ≥ 0 the filled-in  peeling exploration of _∞ to highlight the dependence in 𝒜. 

The ball of radius r in _∞, denoted by ( _∞,r), is obtained by keeping the faces of _∞ which have at least one vertex at graph distance smaller than r from the origin ρ of (the root-edge of) the map; its hull ( _∞,r) is obtained by filling-in all the finite regions of the complement of ( _∞,r) in _∞ (recall that _∞ is one-ended). Our main result is then the following, which explains the title:




Fix a critical weight sequence 𝐪 of type a ∈ (3/2, 5/2]. For any ε>0, there exist  0 < c_ε < C_ε< ∞ such that for any algorithm 𝒜 we have for every n large enough,

    (_∞, c_ε n^1/2(a-1))
    ⊂^_n
    ⊂(_∞, C_ε n^1/2(a-1))

with probability at least 1 - ε.


Our main result thus shows, in a sense, that Markovian explorations of _∞ are bound to discover roughly the same region of _∞ by time n. In particular this implies that any Markovian exploration will eventually discover the full map, a fact already proved in <cit.>. In the other direction, the paper <cit.> studies the decay of the (small) probability that a given edge remains exposed on the boundary of _n for large n's. 

 There is little doubt that our results also hold in the case of non-bipartite maps but we restrict to the case of bipartite maps for technical convenience. In the particular case of the UIPT (type I) our geometric estimates on maps (Proposition <ref>) can be derived from <cit.> and Proposition <ref> and <ref> on maps with a boundary may be obtained using similar techniques, with <cit.>.  

Let us now derive corollaries of our main theorem by specifying it to well-chosen peeling algorithms.




  
Dual graph distance. There is an algorithm ℒ_dual which explores the hull of the balls for the dual metric on _∞ (i.e. the graph distance on the dual graph _∞^†) whose details can be found in Section <ref>. Since faces of a map correspond to vertices of its dual, in order to compare these two lattices, let us view (_∞^†, r) as the subset of vertices of _∞ which are incident to a face at dual graph distance from the root-face (the one to the right of the root-edge) less than r, then let (_∞^†, r) be the set of all these vertices to which we add all the finite regions of the complement.

When a ∈ (2, 5/2], the so-called “dilute phase”, balls in the dual graph grow polynomially in the radius <cit.>; combined with the above result, this yields the following rough comparison between primal and dual distances in _∞: the hull of the ball of radius r in _∞^† is close to the hull of the ball of radius r^1/(2a-4) in _∞. For the so-called “dense phase” a ∈ (3/2, 2), the balls in the dual graph grow exponentially in the radius <cit.>, whilst in the intermediate regime a=2, they have an “intermediate growth”, exponential in the square-root of the radius <cit.>, so now the hull of the dual ball of radius r is close to the hull of a primal ball with radius of order ^r when a < 2 and ^√(r) for a=2.



Fix a critical weight sequence  of type a ∈ (3/2, 5/2]; there exists c_a > 0 such that the following holds: For every ε>0, there exist 0 < c_ε < C_ε< ∞ such that for every r large enough, we have 

    [   (_∞, c_ε r^1/2a-4)                    ⊂            (_∞^†, r)                    ⊂   (_∞, C_ε r^1/2a-4)                             a ∈ (2; 5/2],; (_∞, ^π√(r/2) (1-ε))                    ⊂            (_∞^†, r)                    ⊂ (_∞, ^π√(r/2) (1+ε))                                    a = 2,;   (_∞, ^c_a (1-ε) r)                    ⊂            (_∞^†, r)                    ⊂  (_∞, ^c_a  (1+ε) r)                             a ∈ (3/2; 2), ]

with probability at least 1 - ε.


Observe that 2a-4=1 when a = 5/2; in the case of triangulations, it is known more precisely that the distances on the primal and dual are in fact asymptotically proportional <cit.>. 







  
Pioneer points for simple random walk. 
In another direction we study the behaviour of the simple random walk on _∞ and _∞^† using algorithms 𝒮_primal and 𝒮_dual respectively which both explore the map _∞ along the corresponding walk. These algorithms enable us to keep track of the so-called pioneer points of the walk, which are roughly speaking steps performed by the walk which yield to the discovery of a new vertex which is not disconnected from infinity when removing the past trajectory (see Section <ref> for details). Our theorem shows that the respective walk performs about

    [                         r^2a-2   pioneer steps within ( _∞,r)                      (primal),;                         g_a(r) pioneer steps within (_∞^†, r)                        (dual), ]

with high probability, where g_a(r) = r^a-1/a-2·a > 2 +  √(log r)·a=2 + log r·a < 2. We refer to Corollary <ref> and <ref> for more precise statements.

For the walk on the primal map _∞, in the dilute regime a > 2, this in particular establishes a sub-diffusivity phenomenon in the sense that with high probability, the n-th step of the walk is at distance at most n^1/(2a-2) from its starting point. This idea to use the pioneer points to derive a sub-diffusive behaviour was exploited in <cit.> on the UIPQ and considers in some sense the worst case where each step of the random walk is a pioneer point. It is likely that this is far from what really occurs and controlling this would improve the exponent (see <cit.> for an argument based on reversibility which improves a tiny bit the exponent in the case of the UIPT/Q). Let us mention that in a forthcoming paper <cit.>, we use a completely different method to prove that the walk on the primal map is actually always sub-diffusive with exponent at most 1/3, for all a ∈ (3/2, 5/2].

One could apply our main result to many others peeling algorithms such as the uniform peeling (or metric exploration for the Eden model), peeling along percolation interfaces or peeling associated with internal DLA. We refrain from doing so to keep the paper short.


Throughout this work, for two positive random processes (X_n)_n ≥ 0 and (Y_n)_n ≥ 0, we write X_n ≲ Y_n, resp. X_n ≳ Y_n, when

    lim_C →∞lim sup_n →∞X_n > C Y_n = 0,
        resp.    lim_C →∞lim sup_n →∞X_n < C^-1 Y_n = 0.

We also write X_n ≈ Y_n when both X_n ≲ Y_n and X_n ≳ Y_n hold. This notion of comparison is different from the one used in <cit.>, where these symbols have the following different meaning: there X_n ≲ Y_n means that there exists κ > 0 such that X_n / (Y_n log^κ n) converges almost surely to 0. This notion is neither weaker nor stronger than the present one (it is a trade-off between a strong convergence and logarithmic factors instead of constants). We believe that all our results also hold in this sense but our current estimates do not imply it.

 


  
Acknowledgments We acknowledge support from the Fondation Mathématique Jacques Hadamard, the grants  “CombiTop” and  “GeoBrown”, as well as the grant  “ANR GRAAL”.





§ PEELING PROCESS AND GEOMETRIC ESTIMATES

In this section, we briefly recall the filled-in peeling process of _∞ and refer the reader to <cit.> for details. We also gather  the geometric estimates needed for the proof of our main result, which is then rather short and simple. The proofs of these estimates, which are based on constructions with labelled trees, are postponed to Section <ref>.



 §.§ Filled-in peeling process

Given an instance of _∞, a filled-in peeling process is a sequence of growing submaps _0⊂_1⊂⋯⊂_∞ where _0 is the root-edge of _∞ and _n+1 is obtained by the peeling of one edge on the boundary of _n. More precisely, _n is a planar (bipartite) map with a hole, i.e. a distinguished face whose boundary is simple. We say that _n is a submap of _∞ in the sense that _∞ can be recovered by gluing a proper map with (general) boundary inside the unique hole of _n. To pass on from _n to _n+1 we first select an edge 𝒜( _n) on the boundary of the hole of _n, where 𝒜 is our peeling algorithm which may depend on another source of randomness as long as it is independent of _∞. Once 𝒜( _n ) is picked, we reveal its status inside the map _∞, two cases may appear, as illustrated in Figure <ref>:
 

  * Either the peel edge is incident to a new face in _∞ of degree 2k, then _n+1 is obtained from _n by gluing this face on the peel edge without performing any other identification. This event is called event of type 𝖢_k.

  * Or the peel edge is incident to another face of _n in the map _∞, in which case we perform the identification of the two boundary edges of _n. When doing so, the hole  of _n of perimeter, say 2p, is split into two holes of perimeter 2p_1 and 2 p_2 with p_1+p_2=p-1. Since _∞ is one-ended almost surely, only one of these holes corresponds to an infinite region in _∞. We then fill-in the finite hole with the corresponding map inside _∞ to obtain _n+1. We speak of event of type 𝖦_*,p_1 or 𝖦_p_2, * depending whether the finite hole is on the left or on the right of the peel edge.



 
During a filled-in peeling exploration (_n)_n ≥ 0 of _∞ we denote by |∂_n| the half-perimeter of the boundary of the unique hole of _n and by | _n| the number of inner vertices. The process ( | ∂_n|, | _n|)_n ≥ 0 is a Markov chain whose law is independent of the peeling algorithm with explicit probability transitions <cit.>. In particular we recall that (| ∂_n|)_n ≥ 0 is a Doob h-transform of a random walk with i.id. increments of law ν for the function h^↑(p)= 2p· 2^-2p2 pp for p ≥0 and where ν satisfies 

    ν(-k) ∼𝗉_𝐪· k^-a    and    ν([k, ∞))= 𝗉_𝐪/a-1cos( a π) k^1-a,

where the constant 𝗉_𝐪>0 depends on our weight sequence. Precise scaling limits for the process ( | ∂_n|, | _n|)_n ≥ 0 are known  (<cit.> in the case a 2[The case a=5/2 is not considered there but the arguments extend readily.] and <cit.> in the case a= 2) and in particular it follows that



Let (_n)_n ≥ 0 be a filled-in peeling process of _∞. Then we have

    |∂_n| ≈ n^1/a-1    and    
    |_n| ≈ n^a-1/2/a-1.







 §.§ Geometric estimates


We now recall a few geometric estimates that we will use during the proof of our main result. Although some of these estimates may be obtained using the peeling process, we find it more convenient to prove them using Schaeffer-type construction of  _∞ <cit.>. We postpone the proof of these estimates to Section <ref>. Recall that || denotes the number of vertices of a map  and ρ is the origin vertex of _∞.




We have

    |(_∞, r)| ≈ r^2a-1,
      
    |(_∞, r)| ≈ r^2a-1,
      and  max{(ρ, u); u ∈(_∞, r)}≈ r.



This proposition will be deduced from the results  of Le Gall & Miermont <cit.> who studied scaling limits of our finite Boltzmann maps conditioned to be large. The next estimates deal with maps with a boundary. For p ≥ 1 we denote ^(p) a 𝐪-Boltzmann map with a (general) boundary of perimeter 2p which is a random bipartite planar map whose law is given by 

    ℙ(^(p)= ) ∝∏_f   inner face q_deg(f)/2.

This law is important since in a filled-in exploration, during an event of type 𝖦_p, * or 𝖦_*,p, the finite hole of perimeter 2p is filled-in with a copy of ^(p) independently of the past exploration. It can be shown that in the finite map ^(p) with boundary-length 2p, the volume grows like p^2a-1 whilst the diameter grows like p^1/2. The next result considers the volume growth of the balls in such a map with a boundary.


There exists c > 0 and λ > 0 such that for all r large enough and all p ≥ 2r^2, we have

    |(^(p), r)| > λ r^2a-1 > c.




We can also define ^(p)_∞ the infinite 𝐪-Boltzmann map with boundary of perimeter 2p as a local limit of finite maps conditioned to be large, see e.g. <cit.>.  If  is a map with a boundary we define the aperture of  as  
    ( ) = max{(x,y) : x,y }.





We have

    (^(p)_∞) ≈ p^1/2.







 §.§ Proof of the main result



We may now prove Theorem <ref> relying on the preceding estimates and on properties of the peeling process. Fix any peeling process (_n)_n ≥ 0 of _∞, and for every n ≥ 0, let us denote by D_n^- and D_n^+ the smallest and the largest distance in the whole map to the origin ρ of a vertex on the boundary ∂_n. We stress that D_n^- is measurable with respect to _n, and it equals the smallest distance in the submap _n to the origin ρ of a vertex on ∂_n, whereas D_n^+ is not measurable with respect to _n and is smaller than or equal to the largest distance  in the submap _n to the origin ρ of a vertex on ∂_n.
Clearly, 

    (_∞, D_n^- - 1) ⊂_n ⊂(_∞, D_n^+ + 1).

Theorem <ref> thus follows if we prove that

    D_n^- ≳ n^1/2(a-1)    and    
    D_n^+ ≲ n^1/2(a-1).

We shall prove these two bounds separately. The second bound D_n^+ ≲ n^1/2(a-1) is the easy one, it will follow from the same proof technique as that of <cit.> also recalled in <cit.> and is primarily based on the aperture estimate of Proposition <ref>. The first bound D_n^- ≳ n^1/2(a-1) will follow from more precise volume consideration. The main idea being that if D_n^- is small, then a lot of “large” peeling steps will accumulate too much volume near the origin of _∞.




  
Upper bound D_n^+ ≲ n^1/2(a-1) via aperture. We follow the same lines as <cit.> in our more general context of infinite “discrete stable” maps of type a ∈ (3/2, 5/2]. Since |_n| ≈ n^a - 1/2/a-1 by Proposition <ref> and |(_∞, r)| ≈ r^2a-1 by Proposition <ref>, we deduce from (<ref>) the first bounds

    D_n^- ≲ n^1/2(a-1)    and    
    D_n^+ ≳ n^1/2(a-1).

Notice also the easy bound D_n^+ - D_n^- ≤(_∞∖_n); now recall that the spatial Markov property of the peeling exploration  asserts that conditionally on |∂_n|, the unexplored region _∞∖_n is independent of _n and has the law of _∞^(p) with p = |∂_n|/2. Since |∂_n| ≈ n^1/a-1 by Proposition <ref>,  we conclude using Proposition <ref>  that

    D_n^+ - D_n^- ≲ |∂_n|^1/2≈ n^1/2(a-1).

Combined with the previous bound, we get D_n^+ ≈ n^1/2(a-1) as desired.




  
Lower bound D_n^- ≳ n^1/2(a-1) via accumulation of volume near the origin. As announced, the lower bound will follow from volume consideration. More precisely we shall consider |(_n, 2r)| the number of vertices in the ball of radius r in the submap _n centred at the origin ρ of the map _∞ and study its variation Δ |(_n, 2r)| = |(_n+1, 2r)|-|(_n, 2r)|. Below we write (ℱ_n)_n≥ 0 for the filtration generated by the peeling process and recall that D_n^- as well as |∂_n| are measurable with respect to ℱ_n.




There exists two constants K, λ > 0 such that for all r and n large enough, we have

    Δ |(_n, 2r)| > λ r^2a-1ℱ_n, D_n^- ≤ r≥ K · |∂_n|^-(a-1)1_|∂_n| ≥ 5r^2.







Let us condition on ℱ_n and on the events D_n^- ≤ r and |∂_n| ≥ 4 r^2. Suppose that in the next peeling step, we identify the peel edge with another one on the boundary, separating from infinity a part of the boundary containing (twice) -Δ |∂_n| - 1 ≥ |∂_n| / 2 edges. On such an event, by symmetry, there is a chance at least 1/2 that the boundary swallowed in the finite part contains a vertex x_n^- say, at distance D_n^- ≤ r from the origin. Then we fill-in this hole by inserting an independent finite Boltzmann map with half-perimeter -Δ |∂_n|-1. Since such a map is invariant under re-rooting along the boundary, we may assume that its root-vertex is matched with x_n^-. See Figure <ref>.



In this scenario Δ |(_n, 2r)| is larger than or equal to the volume of the ball of radius r in the map with half-boundary -Δ |∂_n|-1 we just added. According to Proposition <ref>, there exist c > 0 and λ > 0 such that for any p ≥ 2r^2, we have (|(^(p), r)| > λ r^2a-1) > c for all r large enough.
Therefore, for r large, as soon as | ∂_n| ≥ 4r^2, on the event -Δ |∂_n| - 1 ≥ |∂_n| / 2  ≥ 2 r^2, the ball of radius r in the map we add to fill-in the hole has volume at least λ r^2a-1 with probability at least c. By the exact transition probabilities of the Markov chain | ∂_n| and the facts that ν(-k)∼𝗉_𝐪k^-a and h^↑(p) ∼ c' √(p) for some c' > 0,
the probability that such a peeling step occurs is bounded below by

    Δ | ∂_n| ≤ - | ∂_n| / 2ℱ_n≥∑_k = | ∂_n|/2^3| ∂_n|/4h^↑(| ∂_n|-k)/h^↑(| ∂_n|)ν(-k)
    ≥ C · | ∂_n|^1-a.

as | ∂_n| →∞, for some constant C>0. Moreover, given that Δ | ∂_n| - 1 ≤ - | ∂_n| / 2, the probability that a given vertex x_n^- at distance D_n^- ≤ r from the origin sits on the part of the boundary separated from infinity is at least 1/2. Gathering-up the pieces we deduce as desired that

    Δ |(_n, 2r)| > λ r^2a-1ℱ_n, D_n^- ≤ r, |∂_n| ≥ 4 r^2≥1/2× c ×  C · |∂_n|^-(a-1)

for r,n large enough.



Let us come back to the proof of the lower bound D_n^- ≳ n^1/2(a-1) in order to complete the proof of Theorem <ref>. Let us fix ε > 0, we aim at showing that there exists δ > 0 such that for all n large enough, we have (D_n^- ≤δ n^1/2(a-1)) ≤ε.  Fix A large (the value of A will be fixed in a few lines by ε), we will first choose  η small enough so that 

    ∑_i = 1^n K/|∂_i|^a-11_|∂_n| ≥η n^1/(a-1) > A≥ 1-ε/4,

where K is the constant appearing in Lemma <ref>. This is indeed possible since  by <cit.> in the case a 2 and <cit.> in the case a= 2: for each η>0 the sum in the above display converges in distribution towards 

    ∫_0^1dt/(Υ_t^↑)^a-11_Υ_t^↑ > η,

where Υ_t^↑ is an (a-1)-stable Lévy process conditioned to stay positive (the details of this process can be found in the above references) for which we have  ∫_0^1 (Υ_t^↑)^1-ad t = ∞ almost surely by an application of Jeulin's lemma, see <cit.>. We now apply Lemma <ref> with r ≡ r_n = δ n^1/(2a-2) with δ chosen small enough so that η≥ 4δ^2: for all n large enough it holds that

    Δ |(_i, 2 r_n)| > λ r_n^2a-1ℱ_n, D_i^- ≤ r_n≥ K · |∂_i|^-(a-1)1_|∂_i| ≥η n^1/a-1,

for all i ∈{1, …, n}.  Let us denote by X_n,i the indicator of the event in the conditional probability above. Notice that since D_i^- is non-decreasing, if D_n^-≤ r_n then D_i^-≤ r_n for all 1 ≤ i ≤ n. By this remark, conditionally on D_n≤ r_n and on  the event studied in (<ref>), the variable ∑_i=1^n X_n,i is stochastically lower bounded by a sum of independent Bernoulli random variables Z_i with success parameter 0<p_i<  η^a-1/i and so that ∑_i=1^n p_i≥ A for n large enough. An easy Chernoff bound then shows that

    ∑_i=1^n Z_i >  A/8≥ 1- ε/4.

When this scenario occurs, the ball of radius 2 r_n in _∞ contains a volume of at least A/8 times λ r_n^2a-1 whence we deduce that 

    |( _∞, 2r_n)| ≥A/8λ r_n^2a-1≥D_n^-≤δ n^1/(2(a-1)) - ε/4 -  ε/4.

Now, one can further assume that A was chosen large enough so that (|( _∞, 2r)| ≥A/8λ r^2a-1) ≤ε/2 for all r large enough by Proposition <ref>. This finally proves that (D_n^-≤δ n^1/(2(a-1))) ≤ε as desired.






§ APPLICATIONS




Let us apply Theorem <ref> to three peeling procedures especially designed to study the volume growth of the dual map, the  behaviour of a simple random walk on _∞, and the behaviour of a simple random walk on _∞^†.



 §.§ Comparison with the dual map




We apply Theorem <ref> to the peeling _n with the algorithm ℒ_dual defined in <cit.>. Very briefly, in this algorithm, we start with the root-face of _∞ (the one to the right of its root-edge) and we first peel all the edges of this face to reveal the hull of the dual ball of radius 1. Then we iteratively peel all the edges which, at this moment are on the boundary of the explored region to reveal the hull of the dual ball of radius 2, etc. Note that at every step n, the faces incident to the boundary are either at a dual distance H_n say, to the root-face, or at dual distance H_n+1. We deduce from Theorem <ref> that for every ε>0, there exist 0 < c_ε< C_ε < ∞ such that for every n large enough, we have

    (_∞, c_ε n^1/2(a-1))
    ⊂(_∞^†, H_n)
    ⊂(_∞, C_ε n^1/2(a-1)),

with probability at least 1 - ε. 
Now, depending on the value a ∈ (3/2;5/2] we know the asymptotic behaviour of H_n: for a ∈ (2;5/2], by <cit.> we have H_n≈ n^a-2/a-1, for a ∈ (3/2;2), combining <cit.> and <cit.>, the ratio H_n / log n converges in probability to some constant C_a > 0, and finally for a=2, according to <cit.>, the ratio H_n / log^2 n converges in probability to (2 π^2)^-1. For some 0< c'_ε<C'_ε < ∞ we thus have with probability at least 1- ε when n is large enough,

    [    c'_ε n^a-2/a-1                 ≤               H_n                 ≤    C'_ε n^a-2/a-1                       a ∈ (2; 5/2],;  (1- ε) C_a log n                 ≤               H_n                 ≤  (1+ ε) C_a log n                        a ∈ (3/2;2),; 1- ε/2 π^2log^2 n                 ≤               H_n                 ≤ 1+ ε/2 π^2log^2 n                               a =2. ]

Corollary <ref> then follows by combining these bounds with (<ref>) and using monotonicity properties. 




 §.§ Pioneer points and sub-diffusivity




  
Walk on _∞
Let X = (X_n)_n ≥ 0 be the simple random walk on _∞ started from the origin ρ, which should be viewed as a sequence (E⃗_n)_n ≥ 0 of oriented edges such that E⃗_0 is the root-edge, and for every n ≥ 0, conditional on the edge E⃗_n, we choose one of the edges incident to the tip of E⃗_n uniformly at random, then E⃗_n+1 is this new edge, oriented from the tip of E⃗_n. Then X_n is the origin of the edge E⃗_n. We say that τ≥ 0 is a pioneer time if X_τ lies on the boundary of the unique infinite component when we remove all the faces incident to one of the X_i's for i < τ; then X_τ is called a pioneer point (so X_0 = ρ is a pioneer point). For every n ≥ 0, we let 𝒫_n be the n-th pioneer point.




Fix a critical weight sequence  of type a ∈ (3/2, 5/2]. We have

    sup_1 ≤ k ≤ n(ρ, 𝒫_k) ≈  n^1/2(a-1)    and    sup_0 ≤ k ≤ n(ρ, X_k) ≲ n^1/2(a-1).





We use the peeling algorithm 𝒮_primal defined in <cit.> which follows the walk X: if X_n is not a pioneer point, it lies in the interior of the submap we have revealed so far and we may directly move to X_n+1. If otherwise X_n is a pioneer point, then it lies on the boundary of the explored part and we peel the edge on the boundary which lies immediately to the left of X_n. We continue to do so until X_n does not belong to the boundary of the explored part: The 1-neighborhood of X_n has then been completely explored and we may  perform a random walk step.

Let us denote by (_n)_n ≥ 0 the associated filled-in peeling process and write θ_n for the number of pioneer points we have encountered in the first n peeling steps. Since we only peel when the walk is at a pioneer point we have θ_n≤ n+1. On the other hand, if X_n is on the boundary of the explored part of perimeter say 2 p, there is a probability at least ν(-1)h^↑(p-1)/h^↑(p) that X_n is swallowed by a peeling step of type 𝖦_*,0 and is not exposed on the boundary of the explored part anymore. If p=1 the point X_n can be swallowed in two peeling steps. Since inf_ p ≥ 2ν(-1)h^↑(p-1)/h^↑(p) >c >0 we see that the time it takes to discover the neighbourhood of a given pioneer point is stochastically dominated by a geometric random variable. It easily follows that

    θ_n≈ n.

Using this and Theorem <ref> it follows that the first n pioneers points of the walk, and a fortiori the first n steps of the walk, take place within (_∞, C_ε n^1/2(a-1)) with probability at least 1- ε. Using  the third item of Proposition <ref> it follows that 

    sup_1 ≤ k ≤ n(ρ, 𝒫_k) ≲  n^1/2(a-1)    and    sup_0 ≤ k ≤ n(ρ, X_k) ≲ n^1/2(a-1).

For the lower bound sup_1 ≤ k ≤ n(ρ, 𝒫_k) ≳  n^1/2(a-1) notice that the n-th pioneer point is necessarily outside _n-1 and so by Theorem <ref> it must be at distance at least c_ε n^1/2(a-1) from the origin of the map with probability at least 1- ε.





  
Walk on _∞^†
We can use the same strategy as in the last section to study the random walk on _∞^†. More precisely, let us denote by X^† = (X^†_n)_n ≥ 0 the simple random walk on _∞^† started from the root-face . As before, one can design an algorithm 𝒮_dual that explores the map along the walk (see <cit.>). The latter is simpler than 𝒮_primal: the walk starts from the root-face  and wants to traverse one of the edges of this face, we then peel this edge and reveal the face on the other side before moving to X^†_1. Then we continue like this: at each step, either the walk wants to traverse an edge such that the other side has not been revealed yet, in which case we peel this edge, or the other side is known and the walk can directly move. We call pioneer edges the edges traversed by the walk that lead to the triggering of a peeling step; for all k ≥ 0, let us denote by 𝒫^†_k the k-th pioneer edge. Finally, we denote by ^† the graph distance in _∞^†.


Fix a critical weight sequence  of type a ∈ (3/2, 5/2]; there exists c_a > 0 such that the following holds: For every ε>0, there exist 0 < c_ε < C_ε< ∞ such that for every r large enough, we have 

    [            c_ε n^a-2/a-1                        ≤ max_1 ≤ k ≤ n^†(, 𝒫^†_k)                        ≤            C_ε n^a-2/a-1                                     a ∈ (2, 5/2],;         (1- ε) c_a log n                        ≤ max_1 ≤ k ≤ n^†(, 𝒫^†_k)                        ≤         (1+ ε) c_a log n                                      a ∈ (3/2,2),;        1- ε/2 π^2log^2 n                        ≤ max_1 ≤ k ≤ n^†(, 𝒫^†_k)                        ≤        1+ ε/2 π^2log^2 n                                             a =2. ]

with probability at least 1 - ε.




Let (_n)_n ≥ 0 be the filled-in peeling process associated with 𝒮_dual. Using the fact that the submaps (_k)_0 ≤ k ≤ n are nested, a moment's though shows that 

    min_f ∈∂_n^†(, f)
    ≤^†(, 𝒫^†_n)
    ≤max_1 ≤ k ≤ n^†(, 𝒫^†_k)≤max_1 ≤ k ≤ nmax_f ∈∂_k^†(, f)
    = max_f ∈∂_n^†(, f),

where by f ∈∂_n we mean a face incident to the boundary ∂_n. By Theorem <ref>, the smallest and the largest primal graph distance to the root-vertex of the boundary ∂_n are both of order n^1/(2a-2), we then conclude from Corollary <ref> that min_f ∈∂_n^†(, f) and max_f ∈∂_n^†(, f) satisfy respectively the lower and upper bounds of our claim.



We point out that, as opposed to Corollary <ref>, this result does not imply upper bounds for the quantities max_1 ≤ k ≤ n^†(, X^†_k) because we do not have the last claim of Proposition <ref> for the dual map: We do get that the walk X^† up to time n stays within a hull (_∞^†, r_n) for some r_n given by Corollary <ref>, but this hull may have “tentacles” reaching distance much larger than r_n (at least in the dense regime, but it should not be the case in the dilute regime).





§ MAPS AS LABELLED TREES AND GEOMETRIC ESTIMATES



In this section, we recall the other very efficient tool to study planar maps which is a construction from labelled mobiles originally due to Bouttier, Di Francesco, and Guitter; let us first define these objects before recalling the construction (we refer the reader to <cit.> for details).



 §.§ Bouttier–Di Francesco–Guitter coding of bipartite maps





  
Finite maps.
Let us set _≥ -1 = {-1, 0, 1, 2, …} and for every k ≥ 1, consider the following set of bridges:

    ℬ_k^≥ -1 = {(b_0, …, b_k): b_0=b_k=0  and  b_j-b_j-1∈_≥ -1 for  1 ≤ j ≤ k}.

A mobile is a finite rooted plane tree whose vertices at even (resp. odd) generations are white (resp. black). We consider labelled mobiles, in which every white vertex u carries a label ℓ(u) ∈. We say that a finite ordered forest of mobiles (𝔱_1,…,𝔱_p) is well-labelled if


  * The sequence of labels of the roots of 𝔱_1,…,𝔱_p, 𝔱_1 belongs to ℬ_p+1^≥ -1;

  * For every black vertex u, if u_0 denotes its white parent and u_1, …, u_k its white children, ordered from left to right, then the sequence of labels (ℓ(u_0), ℓ(u_1), …, ℓ(u_k), ℓ(u_0)) belongs to ℬ_k+1^≥ -1. 




Imagine that the forest 𝔱_1, …, 𝔱_p is properly drawn on the plane inside a cycle of length p, with the roots grafted in counter-clockwise order on the cycle. Let us define the white contour sequence (c^∘_n)_n ≥ 0 as the sequence of corners formed by the white vertices, starting from c^∘_0 the corner between the root of 𝔱_1 and its first black child (if any, otherwise the corner formed by this root only), and following the contour of the forest from left to right cyclically. Recall that the white vertices are labelled, we associate with each white corner the label of the corresponding vertex; we then say that a corner c^∘_j is the successor of another corner c^∘_i if c^∘_j is the first corner in the cyclic contour after c^∘_i such that ℓ(c^∘_j) = ℓ(c^∘_i) - 1. For this definition to hold also when ℓ(c^∘_i) = ℓ_min is the overall minimum of labels, we add an extra vertex u_⋆ labelled ℓ_min-1. 

We associate a pointed planar map — i.e. a map with a distinguished vertex — with such a well-labelled forest of mobiles by drawing the links between each corner and its successor in a non-crossing fashion and then erasing the embedding of the cycle and the edges of the mobiles; we are then left with a bipartite map on the set of white vertices of the forest and the distinguished vertex u_⋆, with a black vertex inside each inner face, and the degree of this vertex in its mobile is half the degree of the face in the map. The external face of the map is the face that “encloses” the cycle on which the mobiles have been grafted. The root-edge of the map is not prescribed by the forest and is taken uniformly at random on the external face of degree 2p (oriented so that the external face is on its right). 
The labelling of the above forest has a geometric interpretation in terms of the map: the label of a vertex minus ℓ_min plus one is the graph distance in the map to the distinguished vertex u_⋆. 
See Figure <ref> for an illustration.








  
Infinite maps.
Let us next briefly extend the preceding construction to infinite maps with boundary-length 2p. We start as above with a forest of mobiles (𝔱_1,…,𝔱_p), where the 𝔱_i's for i ≥ 2 are as above, but 𝔱_1 is now an infinite mobile with one end, in the sense that it is locally finite and there is a unique self-avoiding infinite path, called thereafter the spine, so the tree can be constructed from such a half-line of alternating white and black vertices s^∘_0, s^∙_0, s^∘_1, s^∙_1, s^∘_2, s^∙_2, … on which are grafted finite trees. This spine splits the forest into two parts: the one on its left made of all the trees grafted to the left of the spine, and the one on the right made of all the trees grafted to the right of the spine and the other 𝔱_i's. Then we may define a white contour sequence as a process indexed by : define (c^∘_n)_n ≥ 0 following the contour of 𝔱_1 starting as above from c^∘_0 the corner between the root of 𝔱_1 and its first black child; on the other hand define (c^∘_-n)_n ≥ 1 following the contour of the forest but now from right to left: c^∘_-1 is the corner between the root of 𝔱_p and its last black child and then we visit all the white corners of the 𝔱_i's for i ≥ 2 before reaching 𝔱_1 and following the part to the right of the spine.

As before we consider labels on the white vertices and we say that the forest is well-labelled when the labels satisfy the same local rule as in the finite case and furthermore the set of labels on the spine is not bounded below. We then construct a map as previously, by first imagining that the trees are properly drawn inside a cycle of length p with a unique accumulation point (corresponding to the infinite tree) and then linking every white corner to its successor in a non-crossing fashion. Our assumption ensures that this is always possible, so there is no need to add any extra vertex here (the distinguished vertex is “sent to infinity”). The root-edge is chosen uniformly at random on the external face as above. We refer to <cit.> and <cit.>  for this construction in the case p=1.



 §.§ The distribution of random labelled mobiles



A way to generate random  bipartite pointed Boltzmann planar maps consists in constructing it as previously, starting from a random forest.  Let  be an alternating two-type Bienaymé–Galton–Watson tree: it has white and black vertices at even and odd generation respectively, which reproduce independently according to the following offspring distributions:

    μ_∘(k) = Z_^-1 (1 - Z_^-1)^k
        and    μ_∙(k) = Z_^k+12k+1k q_k+1/Z_q-1

for all k ≥ 0. Recall the law μ from the introduction, note that for k ≥ 1, the ratio μ(k) / μ_∙(k-1) is constant, so μ_∙ or μ has finite variance or belongs to the strict domain of attraction of an (a-1)-stable distribution if and only if the other satisfies the same property. Furthermore, easy calculations show that μ has mean one if and only if the product of the means of μ_∘ and μ_∙ equals one, so the two-type tree is critical. A simple and useful observation is that the tree induced by the white vertices, given by keeping only these white vertices and linking each one to its white grand-parent, is a Bienaymé–Galton–Watson forest; we shall denote the offspring distribution by μ̃, which slightly differs from μ but has the same “stable behaviour”, see <cit.>.

Let _1, …, _p be i.id. copies of  and, conditionally on this forest, sample  labels uniformly at random amongst all possibilities which make the forest well-labelled; this just means that at every black vertex with, say, k-1 offsprings, the sequence of labels around it in clockwise order forms a uniformly random bridge in ℬ_k^≥ -1 shifted by the value of the label of its parent, independently of the rest, and similarly for the roots. The law of that bridge is the same as that of a random walk bridge of length k, with i.id. increments of law

    ξ=k = 2^-2-k    for  k ≥ -1.

Then <cit.> shows that the pointed map constructed as above from _1, …, _p has the law of a -Boltzmann pointed planar map with a boundary with length 2p which we denote by 
^(p)_∙, i.e. ( ^(p)_∙ = (, ∙)) ∝ w( ). This is not quite the desired law ^(p) but the latter can be obtained by a simple bias: for every non-negative function f that depends on the map only (not of its pointing),

    f( ^(p)) =  1/[1/ | ^(p)_∙|]·f ( ^(p)_∙) ·1/| ^(p)_∙|,

where || is the number of vertices of the map .  
 
 Similarly, if the random labelled forest (_1, …, _p) has the same law as above, except that _1 is infinite  and has the law of _∞, the two-type Bienaymé–Galton–Watson trees as above conditioned to survive then the associated map has the law ^(p)_∞ (this follows from <cit.> and the work <cit.>). The law of _∞  may be constructed in the following way: all the vertices reproduce independently, the ones outside the spine reproduce according to their respective offspring distribution, and the ones on the spine s^∘_i, s^∙_i reproduce according the size-biased versions of these laws; finally, the offspring of a vertex on the spine which belongs to the spine is chosen uniformly at random.





 §.§ Asymptotic estimates on labelled mobiles



Let us consider a sequence (_n)_n ≥ 1 of i.id. well-labelled mobiles with the same distribution as , that we view as an ordered forest; the labels of the roots of the mobiles is zero and the rest of the labels of the mobiles is sampled uniformly at random as above. Let S^∘ = (S^∘_k)_k ≥ 0 and L^∘ = (L^∘_k)_k ≥ 0 be respectively the white Łukasiewicz walk and the label process associated with this forest, constructed as follows: let us read the white vertices of the forest in depth-first search order, starting at 0 from the root of the first tree, then put S^∘_0 = 0 and for every k ≥ 0, let the difference S^∘_k+1 - S^∘_k record the number of grand-children minus one of the k-th white vertex (so S^∘ is nothing but a centred random walk with step distribution μ̃(· + 1)), and let L^∘_k denote the label of this k-th white vertex. According to Le Gall & Miermont <cit.>, for a ∈ (3/2, 5/2), we have the convergence in distribution in the Skorohod space

    (n^-1/a-1/2 S^∘_⌊ nt⌋, n^-1/2a-1 L^∘_⌊ nt⌋)_t ≥ 0
    (c_0 𝒮_t, √(2c_0)𝒵_t)_t ≥ 0,

where c_0 is some constant depending on μ̃, where 𝒮 is an (a-1/2)-stable Lévy process with no negative jump, and the process 𝒵 is the continuous distance process constructed in <cit.>. 

Let us say a few words about this process 𝒵. In the discrete setting, the label of a white vertex is the sum of the label increments along its ancestral line, between each white ancestor, u say, and its grand-parent, v say, and these increments are given by the value B(k,j) of an independent uniformly random bridge with jumps in _≥ -1 of length k at time j, where k is the degree of the black vertex between u and v, and j is the position of u amongst its siblings. The ancestors of the n-th white vertex are given by those times m ≤ n such that S^∘_m ≤min_[m+1,n] S^∘, and the values k and k-j associated with this ancestor are encoded in the Łukasiewicz path: suppose for simplicity that v has only one black child, then k and k-j are given respectively by S^∘_m+1 - S^∘_m+1 and min_[m+1,n] S^∘ - S^∘_m. At the continuum level, the construction of 𝒵 is similar: conditional on 𝒮, for every t > 0, the value of 𝒵_t is given by the sum of independent Brownian bridges of length given by the jumps 𝒮_s - 𝒮_s- and evaluated at times given by inf_[s,t]𝒮 - 𝒮_s-, only for those times s < t such that inf_[s,t]𝒮 > 𝒮_s-. It is shown in <cit.> that such a process is well-defined and admits a continuous version.

In the case a = 5/2, the convergence (<ref>) still holds, where 𝒮 is now a Brownian motion and 𝒵 is the so-called head of the Brownian snake driven by 𝒮, which can be viewed as a Brownian motion indexed by the Brownian forest encoded by 𝒮; the argument may be adapted from <cit.> which considers size-conditioned trees with offspring distribution μ instead.


We next derive a version of (<ref>) for the tree _∞ conditioned to survive. Let us define similarly its Łukasiewicz path S^∞ and its label process L^∞ by restricting to the white vertices on the left part of the tree. It is known that S^∞ has the law of the random walk S^∘ conditioned to always stay non-negative (see e.g. <cit.>), which can be rigorously defined as the Doob h-transform using the harmonic function h(n) = (n+1) n ≥ 0. Similarly, the Lévy process 𝒮 can be conditioned to stay positive via such an h-transform and we denote by 𝒮^↑ this process, see the introduction of <cit.> and references therein. One can finally adapt the construction of the process 𝒵 from 𝒮 in <cit.> to this setting and define a process 𝒵^↑ from 𝒮^↑ when a < 5/2; when a = 5/2 the process 𝒵^↑ is simply the head of the Brownian snake driven by a three-dimensional Bessel process (Brownian motion conditioned to stay positive).




We have the convergence in distribution for the Skorokhod topology 

    (n^-1/a-1/2 S^∞_⌊ nt⌋, n^-1/2a-1 L^∞_⌊ nt⌋)_t ≥ 0
    (c_0 𝒮^↑_t, √(2c_0)𝒵^↑_t)_t ≥ 0,






Since the path S^∞ has the law of the random walk S^∘ conditioned to stay non-negative, the convergence of the former follows from that of the latter in (<ref>), see Caravenna & Chaumont <cit.>. 
Let us next focus on the convergence of the finite-dimensional marginals of the label process. By appealing to Skorokhod's representation theorem, we may assume that the convergence of the Łukasiewicz path holds almost surely. Recall the construction of the process L^∞ from random bridges associated with each black branch-point. When a < 5/2, the proof goes exactly as that of Proposition 7 in <cit.>, it suffices to only consider the large black branch-points since the contribution of all the others is small; these large branch-points, with  length of order n^1/(a-1/2), give at the limit, after a diffusive scaling n^1/(2a-1), independent Brownian bridges, and the sum of these bridges evaluated at the corresponding times, along the ancestral line of a point is the definition of 𝒵^↑_t. When a = 5/2, we may similarly adapt the argument from <cit.>: here the branch-points are too small and the label increments between a white individual in the tree and its white grand-parent behave almost like i.i.d. random variables with finite variance, which gives at the limit a Brownian motion indexed by the infinite Brownian tree, which again is the definition of 𝒵^↑_t.

Finally, tightness of L^∞ follows by absolute continuity considerations with respect to the infinite forest. Indeed, for any N ≥ 1 fixed, the law of the pair (S^∞_k, L^∞_k)_k ≤ N is absolutely continuous with respect to the similar pair associated with a mobile conditioned to have more than 2N white vertices, which has the law of the first mobile in the infinite forest with more than 2N white vertices. This is well-known for the Łukasiewicz path and more generally for conditioned random walk, and it extends to the label process by construction, since the latter is obtained from the Łukasiewicz path and independent random bridges.



For every r ≥ 0, let σ_r denote the first instant i ≥ 0 such that the i-th white vertex of _∞ is on its spine, and it is the first one on the spine with label smaller than -r. The preceding proposition yields the following asymptotic behaviour.


We have

    σ_r ≈ r^2a-1    and    max_k ≤σ_r |L^∞_k| ≈ r.





It is clear from the definition that the times of visit of a white vertex on the spine correspond to those times i ≥ 0 such that S^∞_i = min_j ≥ i S^∞_j. The continuum analogue of σ_r is the first-passage time Σ_α  below -α<0 of the process √(2 c_0)𝒵^↑ restricted to those times t ≥ 0 such that 𝒮^↑_s ≥𝒮^↑_t for all s ≥ t, which is easily seen to be finite for all α >0. We claim that 

    (r^-(2a-1)σ_r, r^-1max_k ≤σ_r |L^∞_k|) [r] (Σ_1, sup_0 ≤ s ≤Σ_1 | √(2 c_0)𝒵^↑_s | ).

Indeed, in the case a = 5/2, the label process along the spine behaves as a Brownian motion which, almost surely, takes values smaller than -1 immediately after reaching -1, so the last display is implied by Proposition <ref>. In particular σ_r ≈ r^2a-1 and max_k ≤σ_r |L^∞_k|  ≈ r when a=5/2. When a < 5/2, the same phenomenon occurs, and in fact the limiting process of labels on the spine is a 2(a-3/2)-stable symmetric Lévy process, which jumps strictly below -1 when entering (-∞,-1]. We conclude similarly.






 §.§ Proof of the geometric estimates on maps



We prove in this final section the volume estimates from Section <ref> we used in the proof of Theorem <ref>, appealing to the results from the preceding section on labelled forests. Let us first start by considering _∞ and proving Proposition <ref> on the balls and their hulls, that is

    |(_∞, r)| ≈ r^2a-1,
      
    |(_∞, r)| ≈ r^2a-1,
      and  max{(ρ, u); u ∈(_∞, r)}≈ r.




We suppose that _∞ is constructed from  _∞ as in the last section (this corresponds to the case p=1) and let us suppose for convenience that we rooted the map is such a way that the origin vertex is the origin of the tree (otherwise it is at distance at most 1 from it). Recall that _∞ has a spine, and denote by 𝕋_r the tree _∞ obtained by chopping off the descendant of the first white vertex on the spine whose label drops below -r-3. Using the well-known “cactus bound”, the proof of <cit.> shows mutatis mutandis (considering only white vertices and corners) that the following inclusion holds in terms of white vertices in _∞:

    (_∞, r) ⊂𝕋_r.

Using the notation of Corollary <ref>, the number of white vertices on the “spine” of 𝕋_r and to its left is given by σ_r+3, and the number of white vertices on the spine and to the right has the same law by symmetry. By Corollary <ref> the number of white vertices of 𝕋_r is  is therefore of order r^2a-1; note that we counted twice the n vertices on the spine, which is negligible. 

Newt we claim that 

    max{(ρ, u); u ∈𝕋_r}≤ 2 + 3 max_u ∈𝕋_r |ℓ(u)|
    ≈ r

where the distance  is in the map _∞ and ρ is its origin vertex. Indeed, the chain of successors starting from any white vertex in 𝕋_r must coalesce with the chain starting from the root corner and this produces a path between those two vertices of length bounded above by 2+3max_u ∈𝕋_r|ℓ(u)|. This variable is of order r by  Corollary <ref>.

We can then prove the three points of the proposition. The third point follows from (<ref>) and (<ref>) after noting that certainly max{(ρ, u); u ∈(_∞, r)} is at least r. Using (<ref>) together with | 𝕋_r| ≈ r^2a-1 then yields 

    (_∞, r) ≲ r^2a-1.

Finally, note that in terms of vertex set in the map we have 𝕋_r⊂(_∞, R) where R = 3+3max_u ∈𝕋_r|ℓ(u)| ≈ r. This yields a lower bound  r^2a-1≲| (_∞, r)| on the volume of balls, hence on their hull, and completes the proof of the proposition.




We finally consider maps with a boundary. 


Suppose that ^(p)_∞ is constructed from a forest 𝒯_1, 𝒯_2, …, 𝒯_p as in the preceding section where the 𝒯_i, i ≥ 2 are independent two-type Galton–Watson trees and 𝒯_1 is the infinite one. Let Δ_p be the largest absolute value of a vertex's label belong to the finite trees 𝒯_2, …, 𝒯_p. Recalling the law (<ref>) of the labels of the root of the trees, it follows from (<ref>) that 

    Δ_p≈ p^1/2.

On the other hand, it is easy to see from the construction of _∞^(p) from the forest that if x,y are any two vertices on the boundary of _∞^(p) then they correspond to two vertices in the forest for which the iterated chain of successors coalesce before 2 Δ_p+2 steps. Hence we deduce that 

    (^(p)_∞) ≲ 4 Δ_p+4 ≈ p^1/2.

The lower bound is obtained by saying that (^(p)_∞) is at least the largest difference between labels of the root of the trees (they must belong to the boundary) and so of order p^1/2.


We finally prove Proposition <ref> which we recall for the reader's convenience: for any r large enough and any p ≥ 2r^2, let us prove that

    |(^(p), r)| > λ r^2a-1 > c,

where c > 0 and λ > 0 are some constants which do not depend on p and r. 


 Fix p ≥ 2 r^2. We will rely on the construction of the pointed map ^(p)_∙ from a forest _1, …, _p of i.id. two-type Galton–Watson trees together with the relation (<ref>) between ^(p) and ^(p)_∙. We first assume for simplicity that the origin of ^(p)_∙ corresponds to the root of _1 in the construction.
We will denote by ℰ_λ the following event:


  * The largest label in absolute value amongst the roots of _1, …, _r^2 is smaller than r/2;


  * The maximum over _1, …, _r^2 of the largest relative label in absolute value inside each tree (so each root is reset to 0) is smaller than r/2 and the total number of vertices in these r^2 trees is larger than λ r^2a-1.

  * The total number of white vertices in _1, …, _p is less than p^a- 1/2.

On the event ℰ_λ (still assuming that the origin of the map ^(p)_∙ is the origin of _1) we have from (iii) that | ^(p)_∙| ≤ p^a- 1/2. Also, combining (i) and (ii) and using the usual bound on distances in the map we deduce that as vertex set of white vertices ⋃_1 ≤ i ≤ r^2_i⊂( ^(p)_∙, 2r+2) and so the later has cardinality more than or equal to λ r^2a-1. Using (<ref>) we can write 

    ( ^(p), 2r+2) > λ r^2a-1≥1/[1/| ^(p)_∙|]·ℰ_λ·1/| ^(p)_∙|≥(ℰ_λ)/[p^a- 1/2/| ^(p)_∙|].

By <cit.> (and its easy extension to the case a=5/2, see <cit.>) we deduce that the denominator in the right-hand side is convergent and is thus bounded as p →∞. All it remains to see is that one can find λ>0 small enough so that ℰ_λ occurs with probability at least c>0 irrespectively of p large: The first point is clearly satisfied with an asymptotically positive probability since the labels of the root of the trees converge after diffusive scaling towards a Brownian bridge see <cit.>. As for points (ii) and (iii), they are independent of point (i) and are clearly  satisfied with an asymptotically positive probability thanks to (<ref>). Et voilà. 

1
10

Angel:Growth_and_percolation_on_the_UIPT
Angel, O.
Growth and percolation on the uniform infinite planar triangulation.
Geom. Funct. Anal. 13, 5 (2003), 935–974.

Angel-Curien:Percolations_on_random_maps_half_plane_models
Angel, O., and Curien, N.
Percolations on random maps I: Half-plane models.
Ann. Inst. Henri Poincaré Probab. Stat. 51, 2 (2015),
  405–431.

Angel-Schramm:UIPT
Angel, O., and Schramm, O.
Uniform infinite planar triangulations.
Comm. Math. Phys. 241, 2-3 (2003), 191–213.

Benjamini-Curien:Simple_random_walk_on_the_uniform_infinite_planar_quadrangulation_subdiffusivity_via_pioneer_points
Benjamini, I., and Curien, N.
Simple random walk on the uniform infinite planar quadrangulation:
  subdiffusivity via pioneer points.
Geom. Funct. Anal. 23, 2 (2013), 501–531.

Bertoin-Doney:On_conditioning_a_random_walk_to_stay_nonnegative
Bertoin, J., and Doney, R. A.
On conditioning a random walk to stay nonnegative.
Ann. Probab. 22, 4 (1994), 2152–2167.

Bettinelli-Miermont:Compact_Brownian_surfaces_I_Brownian_disks
Bettinelli, J., and Miermont, G.
Compact Brownian surfaces I: Brownian disks.
Probab. Theory Related Fields 167, 3-4 (2017), 555–614.

Bjornberg-Stefansson:Recurrence_of_bipartite_planar_maps
Björnberg, J., and Stefánsson, S. Ö.
Recurrence of bipartite planar maps.
Electron. J. Probab. 19 (2014), no. 31, 40.

Borot-Bouttier-Guitter:A_recursive_approach_to_the_O_n_model_on_random_maps_via_nested_loops
Borot, G., Bouttier, J., and Guitter, E.
A recursive approach to the O(n) model on random maps via nested
  loops.
J. Phys. A 45, 4 (2012), 045002, 38.

Budd:The_peeling_process_of_infinite_Boltzmann_planar_maps
Budd, T.
The peeling process of infinite Boltzmann planar maps.
Electron. J. Combin. 23, 1 (2016), Paper 1.28, 37.

Budd-Curien:Geometry_of_infinite_planar_maps_with_high_degrees
Budd, T., and Curien, N.
Geometry of infinite planar maps with high degrees.
Electron. J. Probab. 22 (2017), Paper No. 35, 37.

Budd-Curien-Marzouk:Infinite_random_planar_maps_related_to_Cauchy_processes
Budd, T., Curien, N., and Marzouk, C.
Infinite random planar maps related to Cauchy processes.
J. Éc. polytech. Math. 5 (2018), 749–791.

Budzinski:The_hyperbolic_Brownian_plane
Budzinski, T.
The hyperbolic Brownian plane.
Probab. Theory Related Fields 171, 1 (2018), 503–541.

Caravenna-Chaumont:Invariance_principles_for_random_walks_conditioned_to_stay_positive
Caravenna, F., and Chaumont, L.
Invariance principles for random walks conditioned to stay positive.
Ann. Inst. Henri Poincaré Probab. Stat. 44, 1 (2008),
  170–190.

Curien-A_glimpse_of_the_conformal_structure_of_random_planar_maps
Curien, N.
A glimpse of the conformal structure of random planar maps.
Comm. Math. Phys. 333, 3 (2015), 1417–1463.

Curien:Peccot
Curien, N.
Peeling random planar maps (lecture notes).
Available at
  <https://www.math.u-psud.fr/ curien/cours/peccot.pdf>, 2017.

Curien-Le_Gall:First_passage_percolation_and_local_modifications_of_distances_in_random_triangulations
Curien, N., and Le Gall, J.-F.
First-passage percolation and local modifications of distances in
  random triangulations.
To appear in Ann. Sci. Éc. Norm. Supér. Preprint
  available at http://arxiv.org/abs/1511.04264arXiv:1511.04264
  (2015).

Curien-Le_Gall:Scaling_limits_for_the_peeling_process_on_random_maps
Curien, N., and Le Gall, J.-F.
Scaling limits for the peeling process on random maps.
Ann. Inst. Henri Poincaré Probab. Stat. 53, 1 (2017),
  322–357.

Curien-Marzouk:Sous_diff_Boltzmann
Curien, N., and Marzouk, C.
Infinite stable Boltzmann planar maps are sub-diffusive.
In preparation.

Curien-Marzouk:How_fast_planar_maps_get_swallowed_by_a_peeling_process
Curien, N., and Marzouk, C.
How fast planar maps get swallowed by a peeling process.
Electron. Commun. Probab. 23 (2018), Paper No. 18, 11.

Curien-Richier:Duality_of_random_planar_maps_via_percolation
Curien, N., and Richier, L.
Duality of random planar maps via percolation.
Preprint available at
  http://arxiv.org/abs/1802.01576arXiv:1802.01576 (2018).

Le_Gall-Miermont:Scaling_limits_of_random_planar_maps_with_large_faces
Le Gall, J.-F., and Miermont, G.
Scaling limits of random planar maps with large faces.
Ann. Probab. 39, 1 (2011), 1–69.

Marzouk:On_scaling_limits_of_planar_maps_with_stable_face_degrees
Marzouk, C.
On scaling limits of planar maps with stable face-degrees.
ALEA Lat. Am. J. Probab. Math. Stat. 15 (2018), 1089–1122.

Miermont:Invariance_principles_for_spatial_multitype_Galton_Watson_trees
Miermont, G.
Invariance principles for spatial multitype Galton-Watson trees.
Ann. Inst. Henri Poincaré Probab. Stat. 44, 6 (2008),
  1128–1161.

Stephenson:Local_convergence_of_large_critical_multi_type_Galton_Watson_trees_and_applications_to_random_maps
Stephenson, R.
Local convergence of large critical multi-type Galton-Watson
  trees and applications to random maps.
J. Theoret. Probab. 31, 1 (2018), 159–205.




