title: On the profile of trees with a given degree sequence
authors: Osvaldo Angtuncio Gerónimo Uribe Bravo
text: 
  
  Focused linearly-polarized light scattering from a silver nanowire: Experimental characterization of optical spin-Hall effect
      G V Pavan Kumar
      
  =============================================================================================================================
  
  
  		A degree sequence is a sequence s=(N_i,i≥ 0) of non-negative integers 
  		satisfying 1+∑_i iN_i=∑_i N_i<∞. 
  		We are interested in the uniform distribution  _ s  on rooted plane trees 
  		whose degree sequence equals s, 
  		giving conditions for the convergence of the profile 
  		(sequence of generation sizes) 
  		as the size of the tree 
  		goes to infinity. 
  		This provides a more general  formulation 
  		and a probabilistic proof 
  		of a conjecture due to Aldous <cit.>. 
  		Our formulation contains and extends results in this direction 
  		obtained previously by Drmota and Gittenberger <cit.> and Kersting <cit.>. 
  		A technical result is needed to ensure that trees with law _ s 
  		have enough individuals in the first generations, 
  		and this is handled 
  		through novel path transformations and fluctuation theory of exchangeable increment processes. 
  		As a consequence, 
  		we obtain
  		a boundedness criterion for  the inhomogeneous continuum random tree 
  		introduced by Aldous, Miermont and Pitman  <cit.>. 
  
  
  
  Keywords:  
  		Configuration model; 
  		exchangeable increment processes; 
  		Vervaat transform; Lamperti transform.
  
  
  
  AMS subject classifications:   
  		05C05; 
  		34A36; 
  		60F17;  
  		60G09; 
  		60G17; 
  		60J80
  
  
  
  § INTRODUCTION AND STATEMENT OF THE RESULTS
  
  Trees are an important concept in both pure and applied mathematics, 
  appearing (for example) 
  in biology to represent genealogies, 
  in computer science as a fundamental data structure, 
  as well as an important example of a combinatorial class or species 
  (cf. <cit.>, <cit.>, <cit.>,  <cit.>, <cit.>). 
  Random trees, on the other hand, 
  have been shown to be useful in analyzing the asymptotic behavior of certain families of deterministic trees. 
  One of the most widely studied classes of random trees is 
  that of Galton-Watson (GW) trees conditioned to have size n (denoted CGW(n)), 
  some of which have been shown to be uniform in classes of trees of size n, 
  like plane trees, binary plane trees or Cayley trees (cf. <cit.>). 
  Hence, asymptotic counting problems associated to such trees 
  can be solved using the limiting continuum random tree introduced by Aldous 
  (cf. <cit.>).
  
  We will analyze the class of trees with a given degree sequence because of two reasons. 
  First,  for several real-world networks that have been analyzed, 
  their degree sequence might have a certain feature such as having power law decay 
  (see for example <cit.>). 
  Then, the simplest way to build an associated model of random trees 
  is through the uniform distribution on trees whose degree sequence has the observed feature 
  (in the random graph setting, this corresponds to the configuration model). 
  Second, trees with a given degree sequence are more general than the widely studied CGW(n) trees, 
  since the latter laws can be obtained as mixtures of the former. 
  Part of the success in the study of Galton-Watson trees comes from their link to random walks; 
  we wish to to argue that similar success can be had for trees with a given degree sequence thanks to their link with exchangeable increment processes. 
  
  One way to understand the shape of rooted trees is through their profile, 
  which counts the quantity of elements in the successive generations. 
  (The introductions in <cit.> 
  summarize certain applications and references on the profile of random trees. )
  A conjecture due to Aldous <cit.> 
  (for CGW(n) having a finite variance offspring distribution)  
  states that the rescaled profile converges in distribution to a multiple of the total local time process of the normalized Brownian excursion (NBE). 
  Aldous's conjecture was proved in <cit.> as a complex application of analytic combinatorics.
  
  The latter work was generalized  in <cit.> 
  to the case where the offspring distribution is in the domain of attraction of a stable law. 
  In this paper, we state and prove a much more general version of Aldous's conjecture 
  in the setting of trees with a given degree sequence. 
  
  
  Let us turn to the  
  statements of our results. 
  We define rooted plane trees following <cit.> and <cit.>. 
  Let ℤ_+={1,2,…} be the set of positive integers, 
  and define U=⋃_n=0^∞ℤ_+^n 
  as the set of all labels, 
  using the convention ℤ^0_+={∅}. 
  An element of U is a sequence u=u_1⋯ u_n of positive integers, 
  where |u|=n represents the generation or height of u. 
  If u=u_1⋯ u_i and v=v_1⋯ v_j belong to U, 
  write uv=u_1⋯ u_iv_1⋯ v_j for the concatenation of u and v. 
  By convention u∅=∅ u=u. 
  For any n∈, let [n]={1,…, n} with [0]=∅.
  
  	A rooted plane tree τ is a finite subset of U such that:
  	
  		
    * ∅∈τ,
  		
    * if v∈τ and v=uj for some j∈ℤ_+, then u∈τ,
  		
    * for every u∈τ, there exists a number χ(u)∈, such that uj∈τ iff j∈ [χ(u)].
  	
  
  In the previous definition, the value χ(u) represents the number of children of u in τ.
  The size of a tree τ (the number of individuals) will be denoted by |τ|.
  In the following, by a tree we mean a rooted plane tree. 
  See Figure <ref> for a graphical representation.
  
  
  
  
  
  
  Let us introduce the class of trees analyzed in this paper. 
  
  A degree sequence s is an integer sequence (N_i,i≥ 0)  satisfying ∑ N_i=1+∑ iN_i<∞. 
  A random tree with a given degree sequence s  
  is one whose law is uniform on the set of trees having degree sequence s; 
  we denote its law by _ s. 
  The size of the tree (or of the associated degree sequence) is the constant s=∑_i N_i. 
  
  The integer N_i represents the number of vertices with i children of some rooted plane tree. 
  
  [Trees with restricted degrees]
  
  Let S⊂1,2,… be a finite set of possible degrees. 
  For every s∈ S, choose n_s≥ 0 (but not all zero!). 
  Then, set N_i=n_i for i∈ S and choose N_0=1+∑_i(i-1)N_i, 
  so that (N_i,i≥ 0) is a degree sequence. 
  
  In particular, we can choose S=k to obtain k-ary trees 
  and if n_k=n 
  then the degree sequence is N_k=n, N_0=1+(k-1)n 
  (and N_i=0 for all i≠ 0,k) and its size  equals 1+nk. 
  
  
  [Galton-Watson trees]
  
  Let μ be a distribution on the integers with mean in (0,1]; 
  we think of μ_k as the probability that individuals in the population have k offspring. 
  A Galton-Watson tree with offspring distribution μ 
  is a random rooted plane tree Θ such that, 
  for any (finite) rooted plane tree τ of degree sequence s=(N_i), 
  
      Θ=τ
      	
      	=∏_i μ_i^N_i.
  Hence, conditionally on their degree sequence being s 
  (which already conditions on their size being s), 
  Galton-Watson trees have law _ s. 
  In other words, a Galton-Watson tree (even if conditioned by its size) 
  can be obtained by mixing the laws _s 
  with respect to the law of the degree distribution of Θ. 
   
   A CGW(n) tree has the law of τ conditioned on |τ|=n. 
   In particular, if μ_0,μ_k>0 and μ_0+μ_k=1, 
   then the GW(1+nk) is uniform on k-ary trees with n inner vertices. 
   When μ has finite variance 
   or μ(x)∼ x^-αLx for some α∈ (1,2) 
   (where L is a so-called slowly varying function which could be a constant), 
   <cit.> has proved that CGW(n) have scaling limits 
   which have been termed the Continuum Random Tree (CRT) of Aldous in the first case, 
   and  stable trees in the second case. 
  
  
  Note that Example <ref> is more combinatorial in nature 
  than Example <ref>, 
  even though they share the class of k-ary degree sequences. 
  We will show more elaborate examples of degree sequences 
  (having for example finite size versions of power law decay or showing applicability of our main results) in Section <ref>. 
  We would like to mention an example which is not inside our framework but that inspired it: p-trees. 
  This family of growing random trees is introduced in <cit.>. 
  Fix n and a probability measure p=(p_i)_1≤ i≤ n. 
  A p-tree is a random tree labelled by 1,…, n, denoted Θ,  
  such that, for any labelled tree τ with n vertices: 
  
      Θ=τ=∏_i=1^n p_i^χ_i(τ),
  where χ_i(τ) is the number of children of the vertex with label i in τ 
  (cf. formula (5) in <cit.>). 
  If now (p^n)_n=((p^n_i)_i≤ n)_n≥ 1 is a sequence of probability measures 
  such that p^n_k+1<p^n_k, 
  <cit.> and <cit.> are interested in the following asymptotic regime:
  
      p^n_1→ 0  and  p^n_i/s_n→β_i  where  
      	s_n=√(∑_i(p^n_i)^2).
  In a sense, p^n_i represents the size of the i-th individual with most children in the n-th tree 
  (individuals with a big quantity of children are also referred to as hubs in the tree); 
  then s_n can be interpreted as the characteristic hub size in the n-th tree. 
  In this case, the tree Θ_n with law _p^n 
  can be scaled to converge 
  (in the sense of sampling, also called the Gromov-weak sense in <cit.>) 
  to the so-called inhomogeneous continuum random tree (or ICRT(θ)). 
  When β_i=0 for all i, the ICRT corresponds to Aldous' CRT. 
  A natural conjecture is that the scaling limit of trees with a given degree sequence is also the ICRT(β); 
  this has been proved under some conditions (which imply β_i=0 for all i≥ 1) in <cit.>. 
  One open question in <cit.> is whether the height of the ICRT is finite; 
  by analogy to the case of Lévy trees (cf. <cit.>) 
  this might be equivalent to the ICRT being compact. 
  We will be able to give a partial answer to boundedness as an application of our techniques. 
  We expect this to be relevant to proving convergence of trees with a given degree sequence to the ICRT. 
  
  The main characteristic we will study in a plane tree are the profiles. 
  
  Let τ be a plane tree. 
  Define c_τ so that 
  c_τ(j) is the total number of vertices of τ up to generation j. 
  Then, c_τ is called the cumulative profile or cumulative population process of the tree τ. 
  
  Let z_τ be such that 
  z_τ(j) is the number of vertices in τ in generation j. 
  Then z_τ is called the  profile of the tree τ. 
  We write z and c when there is no risk of confusion. 
  
  
  
  
  Our study the profile exploits its connection to breadth-first walks as follows. 
  We can order the vertices of the tree according to the lexicographical order 
  (e.g., ∅<1<21<22), 
  and assign label i to the ith vertex, for i∈ [|T|]. 
  The depth-first walk (DFW) of the tree 
  will be the walk with ith increment c(i)-1, started at one.
  See Figure <ref> for an example. 
  This ordering is also called depth-first order and, 
  together with the associated depth-first walk,  
  is fundamental in understanding distances in the tree 
  (cf. <cit.>). 
  Another useful labeling of the tree is the breadth-first order. 
  To define this, assign label 1 to the root. 
  Suppose the first generation (offspring of the root) has size z_1. 
  Order the first generation in lexicographical order, 
  and assign label i to the ith vertex, for i∈{2,…, 1+z_1 }, 
  continuing this way for each consecutive generation. 
  The breadth-first walk (BFW) of the tree will be 
  the walk with ith increment c(i)-1, started at one; 
  denote it by x. 
  See Figure <ref> for an example. 
  As we now discuss, the breadth-first walk x is the key to understanding the profile of a tree. 
  Indeed, a simple counting argument of a proof by induction 
  show us that z_n can be recursively obtained by setting  
  
      z_0=1,  
      	c_k=z_0+⋯ + z_k
      	  and  
      	z_k+1=x∘ c_k
  (cf. Chapter 9 of <cit.> and the introduction in <cit.>). 
  Also, breadth-first and depth-first walks have the same law; 
  this can be seen as a manifestation 
  of their link with exchangeable increment processes (cf. proof of <cit.>). 
  
  
  For every n∈, let s_n=(N_i^n ,i≥ 0) be a degree sequence. 
  Consider a tree Θ_n with law _ s_n. 
  The BFW of Θ_n will be denoted by X^n, its cumulative profile by C^n and its profile by Z^n and recall that Z^n(k+1)=X^n(C^n(k)). 
  By analogy with the continuous-time case (cf. <cit.>), 
  Z^n is called the discrete Lamperti transform of W^n. 
  Figure <ref> shows an example of a BFW and its Lamperti transform. 
  For certain classes of trees 
  (such as finite variance CGW(n) trees), 
  the breadth-first walks X^n have a scaling limit 
  (in the sense that X^n(n·)/√(n) converges weakly to a stochastic process X, 
  which is the so-called normalized Brownian excursion for finite variance CGW(n) trees.)
  To study the scaling limit of the profile, 
  the general idea is 
  to prove, for some sequence b_n→∞,  
  that the scaling (Z^n(s_n ·/b_n)/b_n) of the profile has a limit 
  which is a particular solution to
  
      Z(t)=X∘ C(t)   with   C(t)=∫_0^tZ(s) ds,
  in analogy to (<ref>), 
  where X is the limit of the rescaled BFWs. 
  Before our main result, 
  we will consider scaling limits of BFWs and then a characterization of solutions to (<ref>). 
  BFWs have a simple probabilistic structure: 
  they correspond to the Vervaat transform of exchangeable increment processes 
  as shown in <cit.> and recalled in Section <ref>. 
  
  In our case, the scaling limit X of the breadth-first walks of the trees Θ_n is related 
  to a continuous time process X^b with exchangeable increments 
  (abridged EI process) 
  of the form
  
      X^b(t)=σ b(t)+∑_j=1^∞β_j 1U_j≤ t-t      t∈[0,1],
  where b is a Brownian bridge on [0,1], 
  (U_j,j≥ 1) are independent of b and i.i.d. with uniform law on [0,1], 
  and with constants σ∈^+, β_1 ≥β_2≥⋯≥ 0 with ∑β_j^2<∞. 
  (From Kallenberg's representation <cit.>, 
  the process X^b has canonical parameters (0,σ, β).) 
  Recall that X^b can be considered as a random element of Skorohod space, that is, of the space of functions on [0,1] which are right-continuous and have left limits (abridged ). 
  The “excursion-type" process X serving as a scaling limit of the breadth first walks X_n, 
  is obtained from X^b using the  Vervaat  transformation, 
  which exchanges the pre and post minimum parts of X^b. 
  It is formally defined as follows and visualized in Figure <ref>.
  
  
  Let X=(X_t,t∈ [0,1]) be a stochastic process with  paths 
  which reaches its infimum value uniquely and continuously at ρ. 
  Assume that X_0=X_1=0. 
  The Vervaat transform of X is the  stochastic process V=(V_t,t∈ [0,1]) 
  defined by V_t=X_{t+ρ}-X_t, where {t} is the fractional part of t. 
  
  
  
  
  For a given degree sequence s_n, 
  let (d(j),j∈ [s_n]) be the associated child sequence, 
  obtained by writing N^n_0 zeros, N^n_1 ones, etc.
  , and ordering the resulting sequence decreasingly. 
  The ordering shifts focus into the hubs (individuals with the most offspring) as in the case of p-trees. 
  Note that N^n_j=|{i:d(i)=j }|. 
  Recall that for  functions f_n,f[0,1]∞, f_n→ f 
  if there exists a sequence of increasing homemorphisms λ_n[0,1][0,1] 
  such that f_n∘λ_n→ f and λ_n→𝕀 uniformly. 
  This notion of convergence comes from several metrics 
  and defines the Skorohod topology (cf. <cit.> and <cit.>). 
  Recall that convergence to f in the Skorohod topology 
  coincides with uniform convergence on compact sets 
  whenever f is continuous. 
  We will use the product topology whenever the convergence of more than one  function is required. 
  Also, if X^n,X are  processes, the weak convergence
  
      X^nd→X means that FX^n→FX
  for any F which is bounded and continuous on  functions. 
  
  
  
  Let s_n  be a degree sequence for every n∈ of size s_n, where s_n=(N^n_i,i≥ 0). 
  Denote by d^n its ordered child sequence. 
  Let X̃^n be the breadth-first walk of a uniform tree with degree sequence 𝐬_𝐧, extended by constancy on each interval [i,i+1) for i∈. 
  Assume that
  
    Size s_n→∞, 
  
    Hubs there exists b_n→∞ such that, for every i≥ 1,  (d^n_i/b_n) is convergent to a limit β_i≥ 0, 
  
    Degree variance there exists σ∈ [0,∞) such that 1/b_n^2∑_i (i-1)^2 N_i→σ^2+∑_iβ_i^2, and 
  
    Unbounded variation either σ^2>0 or ∑_i β_i=∞. 
  
  Define the scaled breadth-first walk X^n as X̃^n(s_n·)/b_n. 
  Then, the EI process X^b given by (<ref>) achieves its minimum uniquely and continuously and 
  the sequence (X^n) converges weakly to the Vervaat transform V(X^b). The process V(X^b) is strictly positive on (0,1). 
  
  In the above proposition, the hypotheses size, hubs and degree variance are exactly those that are needed to apply the characterization and convergence results for EI processes of <cit.> and <cit.> and obtain convergence of the bridge-like processes. To obtain the convergence of the breadth-first walks, we need results concerning the continuity properties of the Vervaat transformation, like the identification of conditions to ensure that EI processes reach their minimum uniquely and continuously, obtained recently in <cit.>. 
  This is where hypothesis unbounded variation is relevant. 
  
  Regarding solutions to (<ref>), we now characterize them in terms of a very special one, the Lamperti transform of X. Randomness is not needed for the result. 
  
  For a given function f[0,1]_+, 
  which is right-continuous and admits left limits 
  (abridged ), 
  let 
  
      i(t)=∫_0^t 1/fs  ds
  and define the right-continuous inverse of i, denoted c^0, by
  
      c^0(t)=infs≥ 0: i(s)>t,
  where, by convention inf∅=1. 
  The Lamperti transform of f is h^0=f∘ c^0. 
  We call the pair (h^0,c^0) the Lamperti pair associated to f.
  
  
  In the next result, D_+h denotes the right-hand derivative of the function h. 
  
  
  Let f_+_+ be a  function with non-negative jumps Δ f(t)=f(t)-f(t-)≥ 0. 
  Assume that f=0 on 0∪[1,∞) 
   and f>0 on (0,1). 
  Let (h^0,c^0) be the Lamperti pair associated to f. 
  Then, solutions to the equation
  
      c_0=0,  
      D_+ c=f∘ c
  can be characterized as follows:
  
  
    * If ∫_0+1/fs  ds=∞ then h,c=0 and 0 is the unique solution to (<ref>). 
  
    * If ∫_0+1/fs  ds<∞, then c^0 is not identically zero and D_+c^0=h^0, 
  so that c^0 solves (<ref>). 
  Furthermore, solutions to (<ref>) conform a one-parameter family (c^λ)_λ∈ [0,∞], 
  
      c^λ(t)=c^0( ⟨λ-t|^+  )
      	 for λ>0 and  
      	c^∞=0.
  Finally, assume that ∫_0+1/fs  ds<∞.  
  
    * If ∫^1-1/fs  ds=∞ then c^0 is strictly increasing on _+, with c^0(∞)=1.
  
    * If ∫^1-1/fs  ds<∞ then c^0 is strictly increasing until it reaches the value 1 at the finite time ∫_0^1 1/fs  ds. 
  
  
  
  Note that the Lamperti transformation is strictly increasing, plateauing if it reaches 1. 
  Hence, under the conditions of Proposition <ref>, 
  solutions c to (<ref>) 
  cannot have constancy intervals except when they take the values zero or one. 
  This is a key fact which will allow us to prove our main theorem. 
  
  In <cit.>, it is proved that boundedness of the ICRT is equivalent to ∫_0^1 1/X_s  ds<∞. 
  Having seen that this is related to (non-triviality and finite time absorption of) 
  the Lamperti transformation of the scaling limits of breadth-first walks, 
  we offer the following sufficient conditions which are simple to check. 
  For a sequence β_i↓ 0, 
  define β(x)=#{i: β_i>x}. 
  
  
  Let X be the Vervaat transform of the EI process X^b given in (<ref>). 
  If σ^2>0 then ∫_0^1 1/X_s  ds<∞. 
  Otherwise, if σ^2=0  and 
  
  
    * 
  lim_x→ 0x^αβ(x)→∞ for some α∈ (1,2) then ∫^1- 1/X_s  ds<∞. 
  
    * If furthermore  there exists α̃<1/(2-α) such that ∑_i β_i^α̃<∞ then ∫_0^1 1/X_s  ds<∞. 
  
  
  In the above proposition, recall that  ∑_i β_i^2<∞. 
  Hence,  ∫_0^1 1/X_s ds<∞ if condition <ref> above holds for some α>3/2. 
  We also obtain the integrability of 1/X when β has power law type decay, or more broadly, when 
  
      1<supα: lim_x→ 0x^αβ(x) =∞	  
      	=infα: lim_x→ 0 x^αβ(x)=0.
  Based on the case of scaling limits of Galton-Watson trees, 
  <cit.> conjectured a necessary and sufficient condition in terms of σ and β for finitude of the integral of 1/X, 
  which is required for compactness of the ICRT. 
  Our condition is only sufficient, 
  but it is acknowledged in <cit.> that “checking compactness...turns out to be quite intractable". 
  In that article, one obtains 
  annealed results where β is random and satisfies almost surely the last display. 
  See also <cit.> for more up to date accounts on annealed criteria for the compactness of the ICRT coming from the study of a different random graph model, which gives further evidence for the boundedness conjecture in <cit.>. 
  
  Our main theorem is the following. 
  
  
  
  
  Let ( s_n) be a sequence of degree sequences of sizes (s_n) 
  and let X̃^n be the breadth-first walk of a uniform tree with degree sequence s_n. 
  Assume the existence of constants b_n→∞ 
  such that X^n=X̃^n(s_n ·)/b_n converges weakly to 
  the Vervaat transform X of an unbounded variation exchangeable increment process. 
  Let (Z,C) be the Lamperti pair associated to X. 
  Define C̃^n as the cumulative population 
  and Z̃^n the population profile of a uniform tree with degree sequence s_n, as well as
  
      C^n=1/s_nC̃^ns_n/b_n·  and  
      	 Z^n= 1/b_nZ̃^ns_n/b_n·.
  Then, under the hypotheses s_n/b_n→∞ and 
  
      ∫^1-1/X_sds<∞   a.s.,
  we have the joint convergence	
  X^n,Z^n, C^nd→X,Z,C 
  under the product Skorohod topology. 
  
  
  
  
  
  As a simple application, 
  consider the case  where s_n=(N^n_i,i≥ 0) is the k-ary degree sequence 
  with n inner (non-leaf) vertices.
  Then,  the sequence ( s_n) satisfies the conditions of Proposition <ref>. 
  Indeed, obviously the sizes 1+nk grow to infinity, 
  
      ∑ (i-1)^2N^n_i= 1+k(k-1)n
  so that we can take b_n=√(n) 
  to see that hypothesis degree variance holds and that hubs holds with β=0. 
  The limiting EI process then has parameters (0,√(k(k-1)),0). 
  Hence, the limiting EI process X^b is a (non-zero) multiple of the Brownian bridge 
  (which satisfies Hypothesis unbounded variation); 
  its Vervaat transform X is called the normalized Brownian excursion (cf. <cit.>). 
  Proposition <ref> tells us that 1/X is integrable; 
  since s_n/b_n∼ k√(n)→∞, the hypotheses of Theorem <ref> therefore hold 
  and we conclude a limit theorem for the profiles of k-ary trees with n inner vertices as n→∞. 
  The scaling limit of the profile is the Lamperti transform of the normalized Brownian excursion; 
  this has the same law as the total local time process of the normalized Brownian excursion thanks to a celebrated theorem of Jeulin (cf. <cit.> and <cit.>). 
  We could similarly treat the case of restricted degree trees, with the same scaling sequences and scaling limit. 
  
  More generally, one can easily build degree sequences satisfying the hypotheses of Theorem <ref>; see Section <ref>. 
  Also, the theorem can also be applied to mixtures of trees with a given degree sequence. 
  This is exemplified in the following more complex application to the the convergence of the rescaled profile of CGW(n) trees of Example <ref>. 
  
  
  Recall that a distribution μ=(μ_n,n≥ 0) is called critical if ∑ nμ_n=1, and aperiodic if the greatest common divisor of all n with μ_n>0 is one. 
  
  
  	
  	Consider a CGW(n) tree with offspring distribution μ, which is critical
  	 and aperiodic. 
  	Assume also that either μ has finite variance σ^2 
  	or that its tails satisfy μk=k^-αLk for some slowly varying function L. 
  	Denote by X^n, C^n and Z^n its rescaled breadth-first walk, cumulative profile and profile 
  	as in Theorem <ref>, 
  	where s_n=n and b_n equals  √(n) in the finite variance case 
  	and n^1/αL̃(n) 
  	for some  slowly varying function L̃ 
  	otherwise. 
  	Then, we have the joint convergence
  	
      X^n,Z^n,C^nd→X,Z,C,
  where X is the normalized Brownian excursion (multiplied by σ^2) in the first case and otherwise is the normalized stable excursion and (Z,C) is the Lamperti pair associated to X. 
  
  The normalized stable excursion equals the Vervaat transform of the bridge of a stable process. 
  More information about it can be found in <cit.>. 
  This gives another proof of Aldous's conjecture <cit.> in the finite variance case, 
  first proved in <cit.>. 
  Kersting analyzed the second case in <cit.>. 
  We would be able to give a further extension to the case where μ is allowed to vary with n. 
  What is lacking are local limit theorems for triangular arrays, 
  which are relevant to obtain the scaling limit of Lévy bridges, 
  as can be seen from the proof. 
  
  We conclude this section with an overview of the proof of Theorem <ref>. 
  First, we perform a deterministic analysis of the Lamperti transformation and its probabilistic counterpart. 
  In particular, we obtain subsequential compactness and, through Proposition <ref>, 
  that all subsequential limits in the context of Theorem <ref> are of the form (X,Z^Λ, C^Λ) for some random Λ. 
  (Recall that C^Λ is a shift of C and that Z^Λ is its right-hand derivative). 
  In order to prove convergence, we must prove that all subsequential limits agree: this is done by showing that
  Λ=0 almost surely, 
  which can be interpreted as an asymptotic thickness near the root (or at the base) of our random tree. 
  A novel path transformation for discrete EI process, called the 213 transformation, is introduced to show that, under the conditions of Theorem <ref>, our random tree sequence is asymptotically thick. 
  
  Let τ be a plane tree labeled in depth-first order. 
  	Let v∈{2,…,|τ| } be a vertex in τ and let u be any strict ancestor of v.
  	Cut τ at u and v, obtaining three subtrees keeping their original labels: 
  	τ(1,u) has the original root, 
  	τ(u,v) with root u, 
  	and τ(v) with root v.
  	 (If v is a leaf, then τ(v) is empty) 
  	Construct a new tree Ψ_u,v(τ) by grafting (or pasting) the root of τ(v) at u, 
  	and then further grafting this structure at the leaf v of τ(u,v). 
  	If w is the depth-first walk of τ, denote by Ψ_u,v(w) the depth-first walk of Ψ_u,v(τ). 
  
  An example is shown in Figure <ref>. 
  We obtain in this way a new tree with the same degree sequence; 
  more importantly, when choosing u and v adequately, this transformation preserves the law _ s. 
  
  
  	Let W be the DFW of a tree Θ with law _ s. 
  	Consider an independent uniform r.v. V on {2,…, | s| }, and a positive integer h. 
  	When the vertex V in depth-first order has height greater than h, 
  	let U be the only ancestor of V at distance h from V, 
  	and define W̃:=Ψ_V,U(W). 
  	If the height of U is ≤ h, set W̃=W. 
  	Then (W̃, V) and (W,V) have the same law. 
  
  
  To apply this in the context of Theorem <ref>, 
  consider an arbitrary λ∈ and a sequence of trees τ_n with law _ s_n; 
  we keep the same notation for a subsequence where the triplet (X_n,C_n,Z_n) converges.  
  Then, if Λ>λ>0, then there exists a giant subtree at the top of τ_n 
  (one having a positive proportion of vertices) and of height smaller than λ_1<λ/2 
  (all of this with non-vanishing probability). 
  Consider then the effect of applying the 213 transformation. 
  When the uniform random variable V falls in this giant subtree, with U being its ancestor at distance λ_1, the transformed subtree will become thick before height 2λ_1, 
  thin between heights {2λ_1,…, λ} and thick after height λ 
  (as in Figure <ref>). 
  In other words, the transformed cumulative population (which has the same law) will have a scaling limit which is increasing before 2λ_1 and after λ but that will have a constancy interval in between. 
  From the characterization of solutions to (<ref>), this represents a contradiction, showing that Λ=0=1. 
  
  
  Regarding the organization of the paper, 
  Section <ref> 
  contains the deterministic analysis around the Lamperti transformation, 
  including the characterization of solutions of Proposition <ref>, 
  a result on subsequential (scaling) limits of the discrete Lamperti transformation 
  and results on convergence of hitting times of the cumulative population process 
  which are useful for the analysis of giant subtrees. 
  Then, Section <ref> contains results on exchangeable increment processes  
  which give  the convergence of breadth-first walks of Proposition <ref>, 
  weak subsequential compactness of profiles, 
  the compactness criteria for the ICRT of Proposition <ref> 
  and invariance under the 312 transformation of Proposition <ref>. 
  Our main result (Theorem <ref>) is proved in Section <ref>. 
  Finally, Section <ref> contains the application of the main theorem to Galton-Watson trees (Corollary <ref>) and the construction of degree sequences which show the general applicability of Theorem <ref>. 
  
  
  
  § DETERMINISTIC RESULTS ON THE LAMPERTI TRANSFORMATION
  
  
  In this subsection we will collect results on the (deterministic) analysis of solutions to the initial value problem (<ref>) and its discrete counterpart (<ref>). 
  First of all, the latter can be seen as a discretization of the former: 
  as argued in <cit.>, 
  it corresponds to applying a Euler method of span 1 
  to the initial value problem. 
  Indeed, a discretized initial value problem of the form (<ref>) can be written as
  
      c^σ(0)=0,  
      	h^σ(t):=D_+ c^σ(t)= f∘ c^σ(σt/σ).
  Note that as for the discrete Lamperti transformation, the (unique) solution can be obtained recursively (see <cit.>). 
  Also, note that if f is the breadth-first walk of some plane tree τ 
  (extended by constancy on each [n,n+1) and on [|τ|, ∞)), then h^1 is the Lamperti transform of f. 
  Finally, the effect of scaling can also be incorporated: 
  if f_n is the breadth-first walk of a plane tree τ_n 
  and there exist scaling constants s_n,b_n such that f_n(s_n·)/b_n converges on Skorohod space 
  to some  function f, our method will be based on showing that
  
      h^1(w_n)(b_n· /s_n) 
      	=h^b_n/s_n(f_n)
      	→  h^0(f)
  (the Lamperti transform of f) whenever the discretization parameter converges to zero. This highlights the role of b_n/s_n as a discretization parameter and explains the hypothesis s_n/b_n→∞ in Theorem <ref>. 
  This method was introduced in <cit.>, 
  although in the setting there (<ref>) has a unique solution. 
  
  We first establish Proposition <ref>.
  Then we will examine the convergence of hitting times of cummulative population processes, 
  which are needed to ensure that our random trees have enough individuals near the top of the tree. 
  
  
  Let us proceed to the proof of Propositon <ref>. 
  
  
   §.§ Characterization of solutions to the ODE
  
  
  
  Consider then an excursion type function f as in the statement and let (c^0,h^0) be the Lamperti pair of f. 
  If ∫_0+1/f(s)  ds=∞, then, by definition, i=∞ on (0,∞) and then c^0=h^0=0. 
  Let f_-(t)=f(t-) be the left-continuous version of f (where f(0)=0). 
  We will actually prove the characterization result for any solution to the differential inequality
  
      ∫_s^t f_-∘ c(r)  dr ≤ct-ct≤∫_s^t f∘ c(r)  dr
  which is more useful when discussing scaling limits. 
  Any solution to the above equation (or to (<ref>)) is non-decreasing, 
  since f and f_- are non-negative. 
  Note that, because Δ f(t)≥ 0, 
  any solution to (<ref>) actually solves (<ref>). 
  Assume there exists a non-zero solution c̃ to (<ref>) and define
  
      λ=inf{t>0:c̃(t)>0 }<∞.
  Then, for t>0
  
      ∫^λ+t_λ f_-∘ c(r) dr≤ c(λ+t)-c(λ)≤∫^λ+t_λ f∘ c(r) dr.
  The function c_λ(·)=c̃(λ+·) satisfies (<ref>) and is positive on (0,∞). 
  Recall that c^λ is the shift of the Lamperti transform c^0 by λ. 
  We now show that c_λ= c^0, 
  which proves that c=c^λ and that c^λ is a solution to (<ref>) and therefore to <ref>. 
  
  
  	To ease notation, we write c̃ instead of c_λ. 
  	Let a=inft>0:c̃(t)=1. 
  	Then c̃ is constant on (a,∞) because f is absorbed at zero at time 1. 
  	By construction, c̃ is positive on the interval (0,∞) and, since f>0 on (0,1), 
  	c̃ is strictly increasing on (0,a) 
  	Hence, f_-∘c̃=f∘c̃ except at a countable number of points on (0,a), 
  	so that we have equalities in (<ref>).
  	Hence, c̃ is also a solution to (<ref>) which is strictly increasing on (0,a). 
  	
  	Let ι̃ be the inverse of c̃ on [0,1). 
  	On [0,1), ι̃ is increasing, continuous, and with values on [0,∞). 
  	Let 0<r<1. 
  	From the definition of the IVP, 
  	D_+ c̃(ι̃(r))=f∘c̃(ι̃(r))=f(r)>0. 
  	Hence, by the formula for the derivative of an inverse function and the fundamental theorem of calculus 
  
      ∞>ι̃(t)-ι̃(s)=∫_s^tD_+ι̃(r) dr=∫_s^tdr/f(r)   for 0<s<t<1.
  Because c̃ is continuous at 0, then ι̃(s)→ 0 as s↓ 0. 
  	Therefore, we obtain
  	
      ∫_0^tdr/f(r)=ι̃(t)<∞   for all  t∈ [0,1).
  We conclude that the Lamperti transform c^0 is not zero 
  	and that its inverse, i, equals ι̃ on [0,1). 
  	It remains to prove that a=i(1). 
  	But this is clear from (<ref>), because lim_t↑ 1ι̃=lim_t↑ 1 i.
  	This implies that c̃= c^0 and that, therefore, c^0 is a solution to <ref>. 
  	We also deduce that the existence of a non-zero solution to <ref> implies finitude of i, 
  	which also says that 0 is the only solution if i(0+)=∞. 
  	
  	Finally, applying the above paragraph to c, we have shown that c is strictly increasing on (0,i(1-)) 
  	with inverse i. 
  	Hence, c reaches 1 in finite time if and only if i(1-)<∞. 
  	Otherwise, c is strictly increasing, never reaching the value 1. 
  	
  	Recall from the proof that λ=inft≥ 0: c̃(t)>0 
  	when ∫_0+1/f(s)  ds<∞ and c̃ is a non-trivial solution to (<ref>). 
  	However, 
  	we can define λ even when c̃ is a trivial solution or ∫_0+1/f(s)  ds=∞. 
  	With the usual convention inf∅=∞, we see that λ=∞ in this case, 
  	but that the equality c̃=c^λ holds in both cases. 
  	
  	The preceding argument is based on the analysis of continuity properties of the Lamperti transformation of <cit.>, where it is noted that the zero sets of f are responsible for the non-uniqueness of the ODE c'=f∘ c. We will also use the fact from the latter paper that if f>0 on [0,1) and f=0 on [1,∞), then the ODE has a unique solution c which is strictly increasing until it reaches the value 1. 
  	
  
  
   §.§ The composition operation and convergence of profiles
  
  
  
  In this subsection, we note that, whenever we have the joint convergence of the (scaled) breadth-first walk and the cumulative profile (on the product Skorohod space), we can already deduce convergence together with the profile. 
  The result follows from continuity considerations regarding the composition operation on Skorohod space studied in <cit.>, <cit.> and <cit.>. 
  
  
  	Let f_n,f  be non-negative  functions on _+ and such that f_n,f0≥ 0, and f_n,f=0 on [1,∞). 
  	Also, let c_n,c be non-decreasing continuous functions such that
  	
  	
    * there exist λ_n∈ [0,∞) and λ∈[0,∞] such that c_n and c equal 0  on [0,λ_n] and [0,λ], 
  	
    * there exist μ_n∈ (λ_n,∞) and μ∈ (λ,∞) such that c_n and c equal 1  on [μ_n,∞) 
  	and  [μ,∞), and
  	
    * c_n and c are strictly increasing on [λ_n,μ_n] and [λ, μ]. 
  If c_n→ c uniformly on compact sets then, f^n∘ c^n→ f∘ c on Skorohod space. 
  
  
  	Lemma <ref> could be proved as in Theorem 3 of <cit.>, using Theorem 1.2 of <cit.>. Indeed the conditions of the latter hold since f is continuous at 0 and 1, which are the only possible discontinuities of 
  	the right-continuous inverse of c. 
  	For completeness, we include the following proof, adapted from the proof of Lemma 3 of <cit.>.
  
  
  	First suppose that λ<∞ and let i be the right-continuous inverse of c. 
  	Let 0<u<v<r be continuity points of f∘ c. 
  	Using Lemma 2.2 of <cit.>, convergence of f^n∘ c^n on [0,r] follows from its convergence on each of the subintervals [0,u], [u,v] and [v,r]. 
  	
  	The simplest is the middle interval whenever 0<i(ϵ)=u<v= i(1-ϵ) for some ϵ∈ (0,1/2) where ϵ and 1-ϵ are continuity points of f. 
  	Indeed, the hypotheses imply that for n large enough, c^n and c are strictly increasing on [u,v]. 
  	If f is any  function on [0,v] and u<v, let f_u=sup_s≤ ufs and f_[u,v]=sup_u≤ s≤ vfs
  	If f^n∘α^n-f_[ϵ,1-ϵ]→ 0 where (α^n,n∈) are increasing homeomorphisms on [ϵ,1-ϵ] converging uniformly to the identity, we can define β^n=i∘α^n∘ c^n to obtain
  	
      i∘α^n∘ c^n-𝕀_[u,v]→ 0
  because i∘α^n∘ c^n→ i∘ c=𝕀 on [u,v].  
  	Also, 
  	
      f^n∘ c^n-f∘ c∘β^n_[u,v]=f^n∘ c^n-f∘α^n∘ c^n_[u,v]=f^n -f∘α^n_[c^n(u),c^n(v)]
  The right-hand side goes to zero because c^n(u)→ϵ, c^n(v)→ 1-ϵ, and both limits are continuity points of f.
  	
  	
  	Now, we choose v and r such that ||f^n∘ c^n-f∘ c||_[v,r] is as small as we want. 
  	Let τ^↓(ϵ)=inf{t:||f||_[t,1]<ϵ}.
  	For ϵ∈ (0,1/2), set ṽ=τ^↓(ϵ), v=i(τ^↓(ϵ)) and choose any r>v. 
  	Since f_[ṽ,1]≤ϵ then f^n_[ṽ,1]≤ 2ϵ for n large enough. 
  	Then 
  	
      f∘ c_[v,r]=f_[c(v),c(r)]≤f_[ṽ,1]≤ϵ        f^n∘ c^n_[v,r]≤f^n_[c^n(v),1].
  Also, since the interval [c^n(v),1] converges to [ṽ,1] and f is continuous at ṽ (by the lack of negative jumps), then f^n_[c^n(v),1]≤ 3ϵ for large enough n. 
  	Hence ||f^n∘ c^n- f∘ c||_[v,r]≤ 4ϵ for large enough n. 
  	
  	A similar argument proves that ||f^n∘ c^n-f∘ c||_u can be made smaller than ϵ for large enough n by choosing u  adequately. 
  	The latter works also when λ= ∞ (in which case f∘ c^∞≡ 0), but for any u>0.
  
  
  
  
  
  
   §.§ Hitting times of the cumulative population process
  
  
  
  From Proposition <ref>, 
  recall that cumulative populations are continuous and strictly increasing except when taking the values zero or one. 
  We will now see that the hitting times of points x∈ (0,1) are continuous at them. 
  
  
  
  Let c[0,∞)[0,1] be continuous, non-decreasing 
  and strictly increasing at t if 0<ct<1. 
  Assume that c(0)=0 and c(∞)=1. 
  Fix x∈ (0,1) and define h_x(c)=inft≥ 0: ct=x. 
  If c^n→ c on Skorohod space, then h_x(c^n)→ h_x(c). 
  
  
  
  Note that h_c(x) is finite for any x∈ (0,1) as c is continuous, c(0)=0<x<1=c(∞). 
  Since c is non-decreasing, we see that h_c(x)=inft≥ 0: c(t)≥ x and c(h_c(x))=x. 
  Since, by hypothesis, c is strictly increasing at h_c(x), we see that h_c(x)=inft≥ 0: c(t)>x. 
  Hence, we can apply Lemma 8 in <cit.>, to see that h_x is continuous at c on Skorohod space. 
  
  
  
  
  § FIRST RESULTS ON EXCHANGEABLE INCREMENT PROCESSES
  
  
  The aim of this section is to establish the fundamental relationship 
  between trees with a given degree sequence 
  and exchangeable increment processes. 
  With this, we will establish Proposition <ref> 
  and to prove the following preliminary results on exchangeable increment processes: 
  subsequential limits of the cumulative profile of the trees in Theorem <ref> 
  and the path transformation of Proposition <ref>). 
  A subsection is devoted to each of these topics. 
  
  We will mainly deal with discrete time exchangeable increment processes. 
  
  	Fix s∈. 
  	A discrete time process (W^b(j),0≤ j≤ s) 
  	with increments Δ W^b(i)=W^b(i)-W^b(i-1) 
  	has exchangeable increments (EI) if for every permutation σ on [s]
  	
      Δ W^b(1),…, Δ W^b(s)d=Δ W^b(σ_1),…,Δ W^b(σ_s).
  
  
  
  Among discrete time EI processes, extremal ones play a fundamental role. 
  Extremal EI processes are constructed in terms of a deterministic sequence d_1,…, d_s and a uniform permutation π of [s] by setting
  
      Δ W^b_i=d_π_i
  In general, if σ is a deterministic permutation of [s] and x^σ_i=d_σ_1+⋯+d_σ_i, we see that W^b=x^π. This expression separates the deterministic and random components x^σ and π. 
  
  Write θ_i(W^b)=W^b,(i) for the cyclic shift of W^b at i, that is, the sequence of length s whose jth increment is Δ W^b(i+j) with i+j interpreted mod s. 
  A path transformation, introduced by Vervaat in <cit.>, is used to code discrete random trees from EI processes. The discrete Vervaat transform of W^b, denoted by V(W^b), is the ρ-th cyclic shift of W^b, where ρ=min{i∈ [ s]:W^b(i)=min_j∈ [ s]W(j) } is the index of the first minimum of W^b.
  
  The next proposition is an easy consequence of the definitions (cf. the proof of Lemma 7 in <cit.>). 
  It provides a construction of trees with a given degree sequence in terms of a random permutation. 
  
  
  Let s be a degree sequence with child sequence c and size s. 
  Let W^b be an independent increment process constructed by uniformly permuting c-1 and let ρ be the index of its first minimum. 
  If W is the breadth-first walk (or the depth-first walk) of a uniform tree with degree sequence s and U is a uniform random variable on [s] independent of W then (W,U)d= (V(W^b),ρ).
  
  Note, in particular, that the index ρ of the first minimum of W^b is uniform and independent of V(W^b).
  Also, both the DFW and the BFW have the same increments, but in a different order. They have, however, the same distribution. 
  
  
  
   §.§ Convergence of breadth-first walks
  
  
  
  This subsection is devoted to the proof of Proposition <ref>. 
  Consider a sequence of degree sequences ( s_n)_n≥ 1=(N^n_i,i≥ 0)_n≥ 1
  and define s_n=| s_n|. 
  Assume that the sequence ( s_n)_n≥ 1 satisfies the assumptions of Proposition <ref>. 
  Using a uniform permutation π_n on [s_n] and a child sequence (d^n(j),j∈ [s_n]), construct the process
  
      W^b_n(t)=1/b_n+1/b_n∑_j≤s_n t(d^n(π_n(j))-1),   t∈ [0,1],
  where b stands for bridge. 
  It has exchangeable increments on k/s_n: 0≤ k≤ s_n. 
  
  First, we analyze the convergence of W^b_n to the EI process X^b given in (<ref>).
  Define ξ_ j=(d^n(π_n(j))-1)/b_s_n. 
  	By Theorem 2.2 of <cit.>, we know that
  	
      W^b_n
      		d→ X^b  if and only if ∑ξ_j,∑ξ^2_j,ξ_1,ξ_2,…d→α,σ^2+∑β^2_j,β_1,β_2,….
  
  	
  	
  	Since ∑_i ξ_i=-1/b_n, 
  	by definition of a degree sequence, 
  	we see that the limit α exists and equals 0. 
  	For the sum of the squares, using the definition of a child sequence as well as hypothesis degree variance, we get
  	
      ∑ξ^2_j
      		=1/b_n^2 ∑
      		(j-1)^2N^n_j→σ^2+∑β_j^2.
  Finally, hypothesis hubs gives us the convergence of ξ̃_j→β_j. 
  
  
  
  	We can substitute the hypotheses of Proposition <ref> to 
  	s_n→∞, b_n=√(s_n), maxi: N^n_i>0=o (b_n) and ∑(j-1)^2N^n_j/b_n^2→σ^2∈ (0,∞).
  	In this case, we obtain in the limit the Brownian bridge on [0,1], as in <cit.>.
  
  
  We now prove convergence of the scaled breadth-first walks X_n. 
  Note that X_n has the same law as the Vervaat transform of W_n^b. 
  By the proof of Lemma 6 of <cit.>, 
  the process X^b achieves its infimum in a unique time and continuously. 
  The latter reference deals only with EI processes with no-negative jumps; 
  the same conclusion is found in Theorem 2 of <cit.> for more general EI processes. 
  We can therefore define the Vervaat transform of X^b and note that this process is strictly positive on (0,1). 
  Hence, by Lemma 3 of <cit.> (or Lemma 14 of <cit.>)
  
  	the Vervaat transform X^n of the rescaled bridges W_n^b converges to X, the Vervaat transform of X^b. This finishes the proof of Proposition <ref>. 
  
  
  
   §.§ Subsequential compactness of profiles
  
  
  
  In this subsection, we give a simple argument to show that the rescaled cumulative populations (C^n) (extended to [0,∞) by linear interpolation) admit subsequential (weak) limits. 
  Since each C^n is a continuous function, we will use the weak sequential compactness (also called tightness) criteria of <cit.>. 
  This is a step in the proof of Theorem <ref>, whose proof then amounts to showing uniqueness of subsequential weak limits. 
  
  
  
  	Under the assumptions of Theorem <ref>, 
  	let (X^n, n≥ 1 ) be the rescaled breadth-first walks of trees (τ_n,n≥ 1) with law _ s_n. 
  	Let X be the limit of (X^n,n∈). 
  	Consider the rescaled cumulative profile C^n of τ_n. 
  	Then, (C^n,n≥ 1) is tight, 
  	and every weakly subsequential limit of ((X^n,C^n),n≥ 1) is of the form X,C 
  	where C satisfies C_t=∫_0^t X∘ C_s  ds. 
  
  
  	We prove tightness of (C^n,n∈), which together with the tightness of (X^n,n∈), 
  	implies tightness of ((X^n,C^n),n∈). 
  	Recall that 0≤ C^n≤ 1, so the sequence (C^n,n∈) is uniformly bounded.	
  	Note that, for a_n=s_n/b_n, we have
  	
      0≤  D_+C^n(s)= X^n∘ C^n(a_n s/a_n)≤X^n:=sup_s∈ [0,1]X^n_s
  and so the modulus of continuity
      ω_nδ=sup|C^n(t)-C^n(s)|: |t-s|≤δ
  of C^n satisfies ω_nδ≤X^nδ. 
  	Therefore
  	
      ω_nδ>ϵ≤X^n> ϵ/δ.
  Using Theorem 13.2 in <cit.>,
  	
      lim_δ→ 0sup_nX^n> ϵ/δ.
  Hence ((X^n,C^n),n∈) is tight by Theorem II.7.2 of <cit.>. 
  	
  	Suppose that (X,D) is the limit of ((X^n_l, C^n_l),l∈). 
  	By Skorohod's theorem (see for example <cit.>), we assume the convergence takes place almost surely. 
  	Suppose we have proved that for any T>0
  	
      X_-∘ D≤lim inf_l X^n_l∘ C^n_l≤lim sup_l X^n_l∘ C^n_l≤ X∘ D       [0,T].
  Then, using Fatou's lemma, for 0≤ s<t≤ T
  	
      ∫_s^t X_-∘ D(r) dr≤ D(t)-D(s)≤∫_s^t X∘ D(r) dr,
  and therefore, by the proof of Proposition <ref>, we see that D=C^Λ for some Λ∈ [0,∞]. 
  	
  	It remains to prove (<ref>). 
  	We start with the equality
  	
      X^n_l∘ C^n_l=X^n_l∘ C^n_l-X∘α^n_l∘ C^n_l+X∘α^n_l∘ C^n_l.
  The difference in parenthesis is bounded above by ||X^n_l-X∘α^n_l||, which goes to zero.
  	The convergence of α^n_l∘ C^n_l→ D follows by adding the terms ± C^n_l:
  	
      sup_u≤ v|α^n_l∘ C^n_l(a_n u/a_n)-D(u)|≤ ||α^n_l-𝕀||+sup_u≤ v|C^n_l(a_n u/a_n)-D(u)|→ 0.
  Then, because X is  and has only positive jumps
  	
      X_-∘ D≤lim inf_l X∘α^n_l∘ C^n_l≤lim sup_l X∘α^n_l∘ C^n_l≤ X∘ D.
  
  
  
  As in Subsection <ref>, 
  we note that since the process X^a=X_a+· is positive until absorbed at zero at time 1-a, 
  there exists a unique solution C^a to the ODE D_+ C=X^a∘ C. 
  Because of uniqueness, the above tightness result actually proves weak convergence. 
  Note that for 0<x<1, if Λ_x=inft≥ 0: C^a_t=x then
  
      Λ_b-a(C^a)=∫_a^b1/X_s  ds;
  hence, even if Λ_a(X^l)→∞ along a subsequence, 
  Proposition <ref> tells us that Λ_b(X^l)-Λ_a(X^l) converges to the finite quantity Λ_b-a(C^a). 
  This will be relevant to the proof of Theorem <ref>. 
  
  
  
   §.§ The 213 transformation
  
  
  
  This subsection is devoted to the proof of invariance under the 213 transformation stated as Proposition <ref>. 
  The aforementioned transformation of a tree is easy to formalize using the associated depth-first walk. 
  
  Let s∈ and x_i∈∪{-1} for i∈[s] such that ∑_1^sx_i=-1.
  Consider the discrete time excursion w 
  constructed by applying the Vervaat transformation to the partial sums of x, 
  starting at zero and non-negative up to time s, where w_s=-1. 
  Let τ be the tree whose depth-first walk is w. 
  We now define the 213 transformation of τ, 
  denoted Ψ_u,v(τ). 
  Let Δ w_j:=w_j-w_j-1 be the jth increment of w (number of children of j). 
  Choose a vertex v∈{2,…, s} in the tree which is neither the root nor a leaf, and let
  
      d_v=inf{j∈{1,…, s-v+1}:w_v-1+j-w_v-1=-1 }
  be the length of the excursion starting at v (this is equal to  |T(v)|+1). 
  Notice that a vertex v is a leaf iff d_v=1. 
  Consider any vertex v∈{v+1,…, v-1+d_v }, implying that v is its ancestor. 
  
  The tree Ψ_u,v(τ) is the plane tree whose depth-first walk is Ψ_u,v(w) defined as follows:
  
  ΔΨ_u,v(w)_j={
  [                     Δw_v-1+j                 if  1≤j ≤u-v;                   Δw_j-(u-v)             if  u-v+1≤j ≤u-1;                     Δw_u+j-u              if  u≤j≤u-1+d_u;           Δw_v+d_v+j-(u+d_u)   if  u+d_u≤j ≤s+u+d_u-v-d_v; Δw_u+d_u+j-(s+u+d_u-v-d_v+1)    if  s+u+d_u-v-d_v+1≤j ≤s. ] .
  Figure <ref> shows the 213 transformation of a depth-first walk. 
  
  
  
  
  	
  
  
  
  Using a uniform law on the vertex u and choosing v in an adequate way, 
  we prove the invariance of the law _ s under a 213-type transformation.
  
  Define the space of all excursions coding a tree with given degree sequence s by
  
      ℰ_ s={w:w s}.
  
  
  Given an excursion w∈ℰ_ s, the natural numbers u∈[s]∖{1} and h≥ 1, we construct w̃ as follows. 
  In the tree generated by w, if |u| denotes the height of the vertex u and 
  
      |u|>h,
  let v be the ancestor of u at distance h from u, 
  and define w̃=Ψ_u,v(w). If condition (<ref>) is not satisfied, define w̃=w. 
  
  
  
  
  
  
  
  
  	For fixed h≥ 1 and u∈{2,…, s }, the transformation Φ_h,u:ℰ_ s→ℰ_ s  sending w to w̃ 
  	is bijective. 
  
  
  	It is easy to prove that u satisfies (<ref>) for w iff u satisfies (<ref>) for w̃. 
  	Being a transformation of a finite set to itself, 
  	it suffices to prove it is onto.
  	Consider w̃∈ℰ_ s.
  	If u does not satisfy (<ref>) for w̃, define w:=w̃.
  	If u satisfies (<ref>) for w̃, choose the ancestor v_h=u-n+1 of u at height h from u. 
  	Define in this case w=Ψ_u,u-v+1(w̃). 
  	In other words, 
  	
      w̃=Ψ_u,v(Ψ_u,u-v+1(w̃)).
  
  
  
  
  
  We now prove the aforementioned equality in distribution.
  
  
  
  	Consider any excursion w∈ℰ_ s and u∈{2,…,s }.
  	Using the bijection Φ_h,u of Lemma <ref> and the independence between the tree Θ∼_ s and U
  	
      W̃=w,U=u = W=Φ_h,u^-1(w),U=u
      		= W=w,U=u,
  using that W is the (uniform) excursion of the tree Θ. 
  
  
  The 213 transformation was naturally defined on trees and has a simple definition as a path-transformation of its depth-first walks. This is possible since the subtree rooted above a vertex is encoded by a contiguous excursion of its depth-first walk. The transformation can also be seen in terms of the breadth-first walk although it does not have such a simple visualization. 
  
  
  
  
  
  
  
  
  
  
  
  
  § ASYMPTOTIC THICKNESS AND UNIQUENESS OF SUBSEQUENTIAL LIMITS
  
  
  
  In this section, we prove the main technical result 
  responsible for the validity of Theorem <ref> and therefore finish its proof. 
  Namely, that our random trees have an asymptotically thick base. 
  We assume the hypotheses of Theorem <ref>. 
  
  Since, by Proposition <ref> 
  and Lemma <ref>, 
  the sequence of (scaled) breadth-first walk, profile and cumulative profile satisfy is tight and 
  all its subsequential limits (X,Z,C) 
  satisfy D_+C=Z=X∘ C, 
  Proposition <ref> gives us the existence 
  of an initial inverval of constancy of size Λ=inft≥ 0: C_t>0, 
  such that (Z,C)=(Z^Λ,C^Λ). 
  When ∫_0+1/X_s  ds=∞, there is a unique trivial solution to the ODE, 
  which implies that all subsequential limits agree and that therefore there is convergence in this case. 
  Hence, we now focus on the case ∫_0+1/X_s  ds<∞. 
  Having an asymptotically thick base 
  is the assertion that Λ=0, in which case (Z,C) is the Lamperti pair of X. 
  Hence, subsequential limits are unique and this establishes the weak convergence asserted in Theorem <ref>. More specifically, the objective of this section is to prove the following result. 
  
  
  
  	Assume the hypotheses of Theorem <ref> are satisfied and that ∫_0+1/X_s  ds<∞. 
  	
  	Let C^Λ be any subsequential limit of (C^n,n∈), and I^Λ(·)=Λ+∫_0^· ds/X(s) its right-continuous inverse.
  	
  	Then 
  	
  	
  	
  	
      Λ∈ (0,∞]
      	=0.
  
  	
  	
  	
  	
  	
  
  
  The reader can imagine the event on the left-hand side as ocurring with a subsequential limit of trees having a thin base (looking like a cord) with (scaled) height approximately Λ; after that, a giant subtree (with size proportional to the size of the tree) starts to grow. 
  Attached to such cord, there can be other cords with (possibly) giant subtrees growing after height Λ 
  (as in Figure <ref>).
  
  
  
  
  
  
  To prove Theorem <ref>, we use the path transformation of Proposition <ref>. 
  We will use this transformation for individuals near the top of the tree. 
  To give a formal definition of what near the top means, 
  we need a lemma regarding the convergence of the heights of the first and last individuals. 
  
  Using Skorohod's theorem, we work on the space where the almost sure convergence (X^n_l,C^n_l, Z^n_l)→ (X,C^Λ,Z^Λ) happens, for some deterministic subsequence (n_l,l≥ 1). 
  
  Write only (X^l,C^l,Z^l)→ (X,C^Λ,Z^Λ) to avoid cumbersome notation.
  Also, note that, on this same probability space, we can let Θ_l be the only tree whose breadth-first walk is (the unscaled version of) X^l. 
  We introduce the hitting times of (ϵ,∞) by C^l. 
  
  
  	For ϵ∈ (0,1) and l∈, define the first height that the rescaled cumulative profile has more than ϵ individuals as
  
      Λ_l,ϵ:=inf{t>0:C^l(t)>ϵ}.
  
  Since C^Λ is a shift by Λ of C^0, 
  the definition of the Lamperti transformation tells us that
  
      inf{t>0: C^Λ(t)>ϵ}=I^Λ(ϵ)=Λ+I(ϵ)
  for any ϵ∈ (0,1). 
  
  However, since C^Λ is strictly increasing except when at 0 or 1, 
  we can apply Proposition <ref> to obtain the first part of the following lemma. 
  
  	For every ϵ∈ (0,1), the convergence Λ_l,ϵ→Λ+I(ϵ) holds almost surely as l→∞. Furthermore, for every 0<a<b<1, Λ_l,b-Λ_l,a→ I(b)-I(a). 
  	Consider any sequence ϵ_k↓ 0. 
  	Then, there exists a deterministic subsequence l_k 
  	such that
  	
  	
  	
  
      (Λ_l_k,_k,Λ_l_k,1-_k-Λ_l_k,1/2)	
      	→_l→∞  (Λ,I_1-I_1/2)
  almost surely. 
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  Indeed, from the proof of this lemma, we see that the previous convergence takes place together with X^k and C^k. 
  Also, we remark that the choice of 1/2 is arbitrary, and the lemma works for any a∈ (0,1).
  
  
  	
  	
  	
  	For the second part of the statement, recall our remark at the end of Subsection <ref> 
  	and that 
   I(b)-I(a):=∫_a^bds/X(s)<∞ for 0<a<b<1. 
  Thus, even if Λ_l,a→∞, the sequence
  Λ_l,b-Λ_l,a has a finite limit. 
  
  	Note that Λ+I(ϵ)→Λ as ϵ↓ 0, 
  	since either both sides are finite or infinite. 
  	Also, I_1-_k-I_1/2→ I_1-I_1/2 as k→∞. 
  	Let δ_k be a summable sequence decreasing to zero and consider a distance d which generates the topology of  the one-point compactification of [0,∞). 
  	From the (almost sure) convergences 
  	Λ_l,_k→Λ_ and Λ_l,1-_k-Λ_l,1/2→ I_1-_k-I_1/2 
  	as l→∞, 
  	there exists l_k such that for l≥ l_k
  	
      dΛ_l,_k, Λ__k or dΛ_l,1-_k-Λ_l,1/2, I_1-_k-I_1/2>δ_k<δ_k.
  Without loss of generality, we assume that l_k increases, 
  	and deduce from the Borel-Canteli Lemma that Λ_l_k,_k→Λ and Λ_l_k,1-_k-Λ_l_k,1/2→ I_1-I_1/2 almost surely. 
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  	In the following, we will use the temporal rescaling a_k=s_k/b_k, which comes from the Lamperti transform in Subsection <ref>. 
  	For ease of notation, we sometimes put the superscript (k) to refer of such rescaling, for example, for λ>0, we write λ^(k):=λ a_s_k, and also Λ_k,ϵ_k^(k)=Λ_k,ϵ_ka_s_k.
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  To prove Theorem <ref>, we fix any λ>0 and show that
  
  
      Λ∈ (λ,∞]=0
  in the following manner.
  Recall the 213 transformation 
  from Proposition <ref>. 
  
  Let  δ_n↓ 0 and λ_1∈ (0,λ/2). 
  In Subsection <ref> we prove that for n big enough and under the event of Equation (<ref>), near the top of the tree, that is, at height Λ^(k)_k,1-ϵ_k-λ_1^(k), there is one vertex v_k having at least δ_n s_k descendants, for every k big enough. 
  The subtree rooted at v_k will be referred to as a giant subtree. 
  It is a subtree with a positive proportion of individuals, almost all of them between its first λ_1^(k) generations.
  
  Using such a giant subtree, 
  we apply the 213 transformation to obtain a tree which is thick near the root, thin in the middle and thick after that. 
  This contradicts the fact that solutions to D_+C=X∘ C are strictly increasing unless taking the values 0 or 1. 
  The steps in the argument are:
  
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
    * Show that one can intersect with the set Λ_k,1-ϵ_k-λ_1>Λ_k,1/2. 
  	
    * Consider two heights H_k,1/2<H_k,1/4 where the giant subtree is thick: 
  	up to H_k,1/2 there is at least half of the size of the giant subtree, between  H_k,1/2 and H_k,1/4 there is at least quarter of the size of the giant subtree. 
  	
    * The probability that U_k (the uniform variable used for the 213 transformation) be in the giant subtree, between heights H_k,1/2 and H_k,1/4, is at least δ_n/4. Intersect with this set. 
  	
    * Apply the 213 transformation cutting at U_k and N_k, the latter being the ancestor of U_k at distance λ_1^(k) from U_k. 
  	Note that N_k is an ancestor of v_k. 
  	
    *  On such events, the transformed tree Θ̃_k has 
  	
  		
    * at least δ_n s_k/2 individuals up to height (2λ_1)^(k), 
  		
    * less than 2ϵ_ks_k individuals between heights {(2λ_1)^(k),…, λ^(k)},
  		
    * at least s_k/2-ϵ_ks_k individuals after λ^(k).
  	 
  	
    * The transformed tree has the same distribution as the original, 
  	but its cumulative Lamperti transform is constant between two intervals where it increases. 
  	This has probability zero.
  	
  
  
  We now carry out this program. 
  Since I(1)-I(1/2)∈ (0,∞) almost surely,  note that it is enough to establish
  
      AΛ∈ (λ, ∞), I(1)-I(1/2)∈ (λ_2,λ_2')=0,
  where 0<λ<∞ and 0<λ_2<λ_2'<∞ are continuity points for the distributions of Λ and  I(1)-I(1/2), respectively. 
  We decompose <ref> using the set where there is a giant subtree at the top of the tree. 
  For a plane tree τ_k with s_k vertices, let u∈ [s_k] be any vertex on τ_k.
  We denote by τ_k(u) the subtree rooted at u in the tree τ_k 
  (a tree with root u  and all its descendants). 
  For v∈ [0,1] with vs_k∈ [s_k], we also refer to v as a vertex in the tree (and write τ_k(v) instead of τ_k(v s_k)).
  Let δ_m↓ 0. 
  For any m,k∈ and λ_1>0 consider
  
      A(m,k)={ |Θ_k(V_k)|> δ_m s_k },
  where we defined
  λ^(k):=λ a_k in Remark <ref>. 
  Recall that Lemma <ref> implies Λ_k,ϵ_k→Λ, and Λ_k,1-ϵ_k-Λ_k,1/2→ I(1)-I(1/2) almost surely.
  Then, we bound <ref> as
  
      B   Λ∈ (λ,∞],I(1)-I(1/2)∈ (λ_2,λ_2')
         ≤lim_k {Λ_k,ϵ_k>λ, Λ_k,1-ϵ_k-Λ_k,1/2∈ (λ_2,λ_2')}
         ≤_m _k ({Λ_k,ϵ_k>λ ,Λ_k,1-ϵ_k-Λ_k,1/2∈ (λ_2,λ_2')}∩ A(m,k) )
          + _m _k({I(1)-I(1/2)∈ (λ_2,λ_2')}∩ A(m,k)^c ).
  (The last equality follows since
  
      Λ_k,1-_k-Λ_k,1/2∈ (λ_2,λ'_2)ΔI(1)-I(1/2)∈ (λ_2,λ_2')→_k→∞ 0. )
  
  The summands on the right-side will be denoted by <ref>1 and <ref>2, respectively.
  First we prove that under <ref>1, 
  a giant subtree is moved to the base of the tree by applying the 213 transformation, 
  causing a zero probability event. 
  After that, we prove <ref>2 is zero, 
  which is interpreted as the existence of a (vanishingly small) giant component.
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
   §.§ <ref>1 equals zero: moving a giant subtree to the base of the tree
  
  Now we formalize the steps given in page enumerateStepsToMoveGiantSubtree and Figure <ref>, proving that <ref>1 can be bounded for n big enough and 2λ_1<λ by 
  
      C^Λ(2λ_1)≥δ_n/2,C^Λ(λ)-C^Λ(2λ_1)=0,1-C^Λ(λ)≥ 1/2,
  which is zero since C^Λ cannot be constant inside an interval where it is strictly increasing.  
  
  First we need some definitions. 
  
  
  
  	Let τ be a tree and v a non-leaf vertex in τ. 
  	For any h_1,h_2∈∪{∞} with |v|≤ h_1≤ h_2, let
  	
  	
  	
  	
  	
  	
  	
      |τ(v)|(h_1,h_2)={}.
  Let |τ(v)|(h_1):=|τ(v)|(h(v),h_1), the number of individuals in τ(v) up to height h_1 in the tree τ.
  
  
  
  Define the first height where the subtree τ(v) has at least half of its size:
  
      h_τ(v),1/2=min{h≥ h(v):|τ(v)|(h)≥ |τ(v)|/2 },
  and the first height h after h_τ(v),1/2, where the subtree τ(v) accumulates a quarter of its size between {h_τ(v),1/2+1,…, h }:
  
      h_τ(v),1/4=min{h≥ h_τ(v),1/2+1:|τ(v)|(h_τ(v),1/2+1,h)≥ |τ(v)|/4 }.
  
  
  We now prove the our random tree cannot have a thin base if there is a giant subtree. 
  
  
  	Let 2λ_1<λ_2∧λ and λ_2<λ_2'. 
  	Then for every m big enough
  
  
      _k (Λ_k,ϵ_k>λ ,Λ_k,1-ϵ_k-Λ_k,1/2∈ (λ_2,λ_2'),.
         .|Θ_k(V_k)|> δ_m s_k )=0.
  
  
  
  Denote the event inside the probability as B(m,k) and refer to Figure <ref> for visual assistance. 
  Consider a uniform random variable U_k on {2,…, s_k }, independent of Θ_k (recall that the subsequence (n(l(k)),k∈) obtained in Lemma <ref> was deterministic). 
  We apply the 213 transformation, cutting the tree Θ_k at vertices U_k and N_k (at distance λ_1^(k)), obtaining the subtrees 1, 2 and 3, and rearranging them as subtrees 2, 1 and 3. 
  
  
  For the tree Θ_k and the root of the giant component V_k, define the quantities H_k,1/2:=h_Θ_k(V_k),1/2 and H_k,1/4:=h_Θ_k(V_k),1/4. 
  Let us assume that H_k,1/4<Λ_k,1-ϵ_k^(k) with probability going to one as k→∞, and postpone the proof to the end. 
  
  
  
  
  
  	
  	
  	The probability for U_k to fall in Θ_k(V_k), between heights {H_k,1/2+1,…,H_k,1/4}, is at least δ_m/4, by definition of H_k,1/4. 
  	It follows that
  	
  	
      δ_m/4_k B(m,k)
         ≤_k B(m,k)∩{U_k∈Θ_k(V_k), h(U_k)∈{H_k,1/2+1,…,H_k,1/4} ,H_k,1/4<Λ_k,1-ϵ_k^(k)}.
  Denote the event on the right-hand side by B_1(m,k). 
  	Note that the ancestor N_k at distance λ_1^(k) of U_k, is also an ancestor of V_k. 
  	Indeed, we have
  	
      h(N_k)=h(U_k)-λ_1^(k)≤ H_k,1/4-λ_1^(k)≤Λ_k,1-ϵ_k^(k)-λ_1^(k)=h(V_k).
  
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	On the set B_1(m,k) the transformed tree Θ̃_k satisfies
  	
  		
    * There are at least δ_m s_k/2 individuals up to height λ_1^(k). 
  		This holds true since,  
  		before height λ_1^(k), 
  		Θ̃_k 
  		
  		contains the band of the subtree Θ_k(V_k) between heights  {h(V_k),…, H_k,1/2}  and thus, contains at least δ_m s_k/2 individuals. 
  		Indeed
  		
      H_k,1/2-h(N_k) ≤  h(U_k)-h(N_k)=λ_1^(k)        
      			|Θ_k(N_k)|(H_k,1/2)≥ |Θ_k(V_k)|(H_k,1/2)≥δ_m s_k/2.
  
  		
    * Between heights {(2λ_1)^(k),…, λ^(k)} there are at most 2ϵ_ks_k individuals. 
  		To prove this, note that the transformation lifts the height of the subtree 1. 
  		Hence, the maximum number of individuals that Θ̃_k can have in the band between heights {(2λ_1)^(k),…, λ^(k)}, 
  		is the sum of the cardinality of such a band of subtree 2 and the band between {1,…, λ^(k)} of subtree 1. 
  		The latter has at most ϵ_ks_k individuals since Λ_k,1-ϵ_k>λ, and the former has at most ϵ_k s_k individuals since it takes at most (2λ_1^(k)) generations to reach height Λ_k,1-ϵ_k^(k). 
  		Indeed
  	
      Λ_k,1-ϵ_k^(k)-h(N_k)≤ h(U_k)+λ_1^(k)-h(N_k)=(2λ_1)^(k)
  and
      |Θ_k(N_k)|(Λ_k,1-ϵ_k^(k),∞)≤ |Θ_k|(Λ_k,1-ϵ_k^(k),∞)≤ϵ_ks_k.
  
  
  
  
  
  		
    * After height λ^(k) there are at least s_k/2-ϵ_ks_k individuals.
  		This holds since Θ̃_k after height λ^(k), contains the individuals of subtree 1 between heights {λ^(k),…, h(N_k) }. 
  		Hence
  		
      h(N_k)/a_s_k≥Λ_k,1-ϵ_k-2λ_1 ≥Λ_k,1/2+λ_2-2λ_1≥Λ_k,1/2,
  and λ_1^(k)≤Λ_k,ϵ_k^(k) implies
  		
      C^k(h(N_k)/a_s_k)-C^k(λ)≥ 1/2-ϵ_k.
  
  	Using the equality in distribution Θ_kd=Θ̃_k of Proposition <ref>, we bound
  	
  	
  	
      δ_m/4_k B_1(m,k)   ≤_k C̃^k(2λ_1)≥δ_m/2,C̃^k(λ)-C̃^k(2λ_1)≤ 2ϵ_k,1-C̃^k(λ)≥ 1/2-ϵ_k 
         =_k C^k(2λ_1)≥δ_m/2,C^k(λ)-C^k(2λ_1)≤ 2ϵ_k,1-C^k(λ)≥ 1/2-ϵ_k 
         ≤C^Λ(2λ_1)≥δ_m/2,C^Λ(λ)-C^Λ(2λ_1)=0,1-C^Λ(λ)≥ 1/2,
  which is zero, since C^Λ cannot be constant inside an interval where it is strictly increasing.
  	
  	
  	
  	
  	
  	
  	
  	This implies _k B(m,k)=0. 
  	
  	To conclude, we prove
  	
      lim_k→∞B(m,k)∩H_k,1/4<Λ_k,1-ϵ_k^(k)=1.
  
  
  
  
  
  
  
  
  	Since Θ_k has less than ϵ_k s_k individuals after height Λ_k,1-ϵ_k^(k), the same holds for Θ_k(V_k) on the event {H_k,1/4≥Λ_k,1-ϵ_k^(k)}, and thus
  	
      s_kϵ_k≥ |Θ_k(V_k)|(H_k,1/4,∞)≥ |Θ_k(V_k)|/4-z_k(V_k,1/2)≥ s_kδ_m/4-Z̃^k(H_k,1/2).
  Therefore, on the mentioned event, from the rescaling of Z^k, we obtain
  	
      δ_m/4-ϵ_k<(b_k/s_k)||Z^k||≤ (b_k/s_k)||X^k||,
  where the last inequality follows by the time-change relating Z^k and X^k. 
  	Hence, we bound
  	
      _kB(m,k)∩{H_k,1/4≥Λ_k,1-ϵ_k^(k)}≤_k{δ_m /4-ϵ_k≤ (b_k/s_k)2||X^k|| }
      	=0
  where the computation of the limit follows since ||X^k||→ ||X|| and b_k/s_k→ 0, 
  	by hypothesis. 
  	
  
  
  
  
  
  
  
   §.§ <ref>2 equals zero: existence of a vanishingly small giant subtree
  
  
  
  For arbitrary ϵ∈ (0,1/2), we split <ref>2 as
  
      C   _m _k({I(1)-I(1/2)∈ (λ_2,λ_2')}∩ A(m,k)^c )
         ≤_m _k({C^k(Λ_k,1-ϵ_k-λ_1)<1-ϵ}∩ A(m,k)^c )
          + _k({ I(1)-I(1/2)∈ [λ_2,λ_2']}∩{ C^k(Λ_k,1-ϵ_k-λ_1)≥ 1-ϵ}),
  
  
  
  
  
  
  
  
  and denote by <ref> the first term on the right.
  Similarly as in <ref>, we shall prove that <ref> is zero for fixed ϵ.
  Thus
  
      D   _m _k({I(1)-I(1/2)∈ [λ_2,λ_2']}∩ A(m,k)^c )
         ≤({I(1)-I(1/2)∈ [λ_2,λ_2']}∩_ϵ↓ 0_k { C^k(Λ_k,1-ϵ_k-λ_1)≥ 1-ϵ}).
  
  
  
  
  
  
  
  Denote the right-hand side by <ref>.
  
  
  
  
  
  
  
  
  
  
  
  
  
  <ref> equals zero: 
  the last λ_1 generations have many individuals.
  
  
  Let a∈ (0,1/2) and consider 0<λ_1<λ_2. 
  We will prove, 
  using Lemma <ref>, 
  that, even when Λ=∞, 
  
  
  the limit of the (shifted) cumulative profile C^k(Λ_k,1-ϵ_k)-C^k(Λ_k,1-ϵ_k-λ_1) will be positive. 
  If the limit is called L, 
  by adding  the terms ± C^k(Λ_k,1-ϵ_k-λ_1)  to C^k(Λ_k,1-ϵ_k-1/a_s_k)
  we get
  
  
      _ϵ↓ 0_k { 1-ϵ_k≥ 1-ϵ+C^k(Λ_k,1-ϵ_k-1/a_s_k)-C^k(Λ_k,1-ϵ_k-λ_1)}⊂{1≥ 1+L }.
  We now prove that L exists and that L>0=1, so that D equals zero. 
  
  Consider any fixed a∈ (0,1/2) (thus, a continuity point of X). 
  Let Λ^k=Λ_k,a· a_k/a_k and 
  
  
      X^k_a=(X^k(C^k(Λ^k)+v),v∈ [0,1-C^k(Λ^k)])          X_a=(X(a+v),v∈ [0,1-a]).
  We remarked at the end of Subsection <ref>, 
  D_+C_a=X_a∘ C_a has a unique solution C_a, 
  with inverse I_a given by
  
      I_a(b)=∫_0^b1/X_a(s)  ds.
  Consider also the solution C^k_a to the equation
  
      C^k_a(t)=∫_0^tX^k_a∘ C^k_a(ua_k/a_k)du,
  which is uniquely obtained by recursion. 
  The reader can check that C^k_a=C^k(Λ^k+·)-C^k(Λ^k). 
  From the proof of Lemma <ref> we deduce C^k_a→ C_a uniformly on the interval [0,I(1)-I(1/2)]. 
  
  From the definition of C^k, we get
  
  
  
  
      C^k(Λ_k,1-ϵ_k)-C^k(Λ_k,1-ϵ_k-λ_1)     =C^k_a(Λ_k,1-ϵ_k-Λ^k)-C^k_a(Λ_k,1-ϵ_k-Λ^k-λ_1)
         → C_a(I(1)-I(a))-C_a(I(1)-I(a)-λ_1).
  
  
  Note that the above expression is well-defined for k big enough since a∈ (0,1/2) and
  
  
      Λ_k,1-ϵ_k-Λ^k→ I(1)-I(a) ≥ I(1)-I(1/2)≥λ_2>λ_1,
  
  using Lemma <ref> and the definition of <ref>. 
  Since C_a is the (strictly increasing) solution IVP(X_a) (on [0,I(1)-I(a)]), then L>0.  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  <ref> equals zero: a vertex at height λ_1 from the top of the tree has many descendants. 
  
  On the event <ref>, 
  we have the bounds |Θ_k(v)|<δ_m s_k for the subtree rooted at every vertex v at height Λ_k,1-ϵ_k^(k)-λ_1^(k) and ϵ <C^k(∞)-C^k(Λ_k,1-ϵ_k-λ_1). 
  We might think of the collection of such subtrees as a forest. 
  
  On <ref>, 
  each of the last ϵ s_k individuals (of our tree, in breadth-first order) have less than δ_m s_k descendants. 
  If we consider the breadth-first walk of these deterministic quantity of individuals, 
  it is given by X̃^k_ϵ s_k+· and corresponds to the BFW of a forest with a given degree sequence (albeit a non-extremal one). 
  
  
  Let us now consider the depth-first walk of this forest X̃^D,ϵ, k, which has the same law; let X^D,ϵ,k denote its scaled version. 
  
  
  
  
  
  
  
  The size of the subtree rooted at v equals the length of the (sub)excursion of X̃^D,ϵ,k above its running minimum:
  
  
      L^D_k(v):=min{u>v: X^D,ϵ,k_u<X^D,ϵ,k_v }
      	=|τ^ϵ_k(v)|/s_k≤δ_m
  for every v∈ [0,ϵ], 
  
  
  
  and hence
  
  
      _m_k { C^k(Λ_k,1-ϵ_k)-C^k(Λ_k,1-ϵ_k-λ_1)>ϵ}∩ A(m,k)^c 
         ≤_m_k {}
          =  _m_k {},
  where L_k(v) denotes the lengths of excursions of X^ϵ,k above its running minimum. 
  
  Since X is continuous at 1-ϵ almost surely, we know that X^ϵ,k→ X^ϵ in the Skorohod topology, where X^ϵ_t=X_1-ϵ+t (cf. by <cit.>). 
  Define the length of a subexcursion of v in X^ϵ by L(v). 
  
  If there exists v∈ [0,ϵ] such that L(v)>2δ_m, then for some δ>0 small and k big enough we can take a subinterval (g',d')⊂ (v,v+L(v)) such that d'-g'>δ_m and X^D,ϵ,k_s≥ X^D,ϵ_v+δ for every s∈ (g',d'). 
  This implies 
  
  the existence of v' with L_k(v')≥ d'-g'>δ_m.  
  Hence, 
  
  
      _m_k { C^k(Λ_k,1-ϵ_k)-C^k(Λ_k,1-ϵ_k-λ_1)>ϵ}∩ A(m,k)^c 
         ≤_m  L(v)≤δ_m  for all v∈ [0,ϵ]
         = L(v)=0  for all v∈ [0,ϵ].
  However, a process with no excursions above its running minimum necessarily coincides with it, 
  so that it is of bounded variation. 
  Since X has sample paths of unbounded variation, 
  we see that L(v)=0  for all v∈ [0,ϵ] which concludes the proof that <ref>=0. 
  
  
  
  
  
  
  
  
  § EI PROCESSES AND THE LAMPERTI TRANSFORMATION
  
  
  In this section, we analyze non-triviality and finite-time extinction 
  of the Lamperti transformation of the Vervaat transform of EI processes 
  stated as Proposition <ref>. 
  
  Let X^b be the EI process given in (<ref>) and let X be its Vervaat transform. 
  Note that under any one of the conditions in Proposition <ref>, 
  X^b is of unbounded variation so that X^b reaches its minimum uniquely and continuously, 
  say at a time ρ. (See for example <cit.>)
  Also, note that the trajectories of X close to zero or one coincide 
  with the corresponding the corresponding trajectories of X^b 
  after or before it reaches its minimum at ρ. 
  The proof of Proposition <ref> follows from an analysis of the pre and post-minimum processes of X^b, in particular, in the obtention of lower envelopes as in the following proposition. 
  Let us write X instead of X^b to lighten notation. 
  
  
  
  Let X be an extremal EI process of infinite variation and parameters (0,σ^2,β), 
  where β_i↓ 0. 
  Let ρ be the unique instant at which X reaches its minimum. 
  Then, there exists γ,γ'>1 such that
  
      lim_t→ 0+X_ρ-t-X_ρ/t^1/γ=∞,
  and 
  
      lim_t→ 0+X_ρ+t-X_ρ/t^1/γ'=∞.
  Otherwise, assume there exists α∈ (1,2) such that lim_x→ 0x^αβ(x)=∞. 
  Then, there exists γ>1 such that (<ref>) holds. 
  If furthermore, there exists α̃<  1/(2- α) such that ∑_i β_i^α̃<∞, there exists γ'>1 such that (<ref>) holds. 
  
  Of course, Proposition <ref> follows from the above result if σ^2=0. 
  To prove the latter, however, we will need a path transformation that extends Lemme 4 in <cit.> for Lévy processes to the EI setting. 
  We will consider the future minimum process X, 
  given by X_s=infX_t:t≥ s, 
  as well as the right-endpoint of the excursion straddling t given by d_t=inf{s≥ t: X_s=X_s}.  
  Also, note that there are no restrictions on the sign of the parameters β_i. 
  
  
  
  Let X be an extremal EI process of parameters (0,σ,β) of unbounded variation. 
  Let ρ be the place the unique minimum of X is achieved. 
  Then X_ρ+·-X_ρd=X∘ d. 
  
  Via the above proposition and the simple inequality X∘ d ≥X, 
  we recover some comparison results for the sample function growth of <cit.>, 
  since for any increasing f_+_+: 
  
      lim inf_t→ 0+X_ρ+t-X_ρ/ft≥lim inf_t→ 0+X_ρ+t-X_ρ/ft≥lim inf_t→ 0+X_t/ft.
  
  On the other hand, since viewing the process at the left of the infimum is the same as viewing the process -X^R_t=X_(1-t)- at the right of its infimum, then
  
      lim inf_t→ 0+X_ρ-t-X_ρ/ft≥lim inf_t→ 0+sup_s≤ t -X^R_s/ftd=lim inf_t→ 0+-X_t/ft.
  
  
  The importance in translating the problem from the post-minimum process into one near zero is that we can use couplings between EI processes and the more well-known Lévy processes, as well as the following result for Lévy processes. 
  
  
  Let X be a spectrally positive Lévy process of infinite variation 
  with Lévy measure ν supported on a compact subset of _+. 
  If σ>0, then there exists γ,γ'>1 such that
  
      lim_t→ 0+X_t/t^1/γ
      =-∞
  
  and
  
      lim_t→ 0+X_t/t^1/γ' 
      =∞.
  Otherwise, if there exists α>1 such that lim_x→ 0x^ανx=∞ for ν(x)=ν(x,∞),
  then (<ref>) holds true. 
  If furthermore, there exists α̃<1/(2-α) such that
  	
      ∫_0^1 x^α̃ νdx<∞,
  
  then (<ref>) holds true.
  
  Let us apply Propositions <ref> and <ref> to prove  Proposition <ref>  and then finish by proving the former. 
  
   
  Assume first that  all β_i have the same sign and that x^αβ(x)→∞ for some α>1. 
  
  
  
  Using that d_t≥ t, from Proposition <ref> we have
  
      _t→ 0+X_ρ+t-X_ρ/f(t)≥_t→ 0+X_t/f(t).
  From Theorem 3.27 in <cit.>, 
  we can write X=Y+Z, where Y is a Lévy process with characteristics (0,0,∑_i δ_β_i)
  and Z is an exchangeable increment process 
  
  whose jumps β̃ satisfy ∑_i  |β̃_i|^γ<∞ for every γ>1. 
  Thanks to Theorem 2.32 item (i) in the same reference, Z_t/t^1/γ→ 0 almost surely for every γ>1. 
  Also, our hypothesis on α implies that the Lévy measure of Y satisfies the hypothesis of Proposition <ref> and that therefore, there exists γ>1 such that lim_t→ 0Y_t/t^1/γ=∞ for some γ>1. 
  We conclude that
  
      lim inf_t→ 0X_t/t^1/γ
      	=lim inf_t→ 0Y_t/t^1/γ
      	=∞.
  
  
  
  
  
  We continue the proof of Proposition <ref> by
  dealing with lower envelopes for the pre and post minimum processes 
  of a Lévy process with no negative jumps. 
  The tools require fluctuation theory of Lévy processes 
  as presented in <cit.>, <cit.> and <cit.>. 
  It also requires the indices of Blumenthal and Getoor for subordinators. 
  Given any subordinator τ with Laplace exponent Φ, 
  we define the upper and lower indices according to Blumenthal and Getoor 
  (See Theorem 6.1 in <cit.>, there called β and σ)  
  as follows
  
      α(τ)
      	
      	=infα>0: lim_λ→∞λ^-αΦλ=0α(τ)=supα>0: lim_λ→∞λ^-αΦλ=∞.
  and recall that they satisfy 
  0≤α(τ)≤α(τ)≤ 1 and that, whenever its dfirt is zero, 
  
      lim_t→ 0 t^-1/ατ_t=∞ if α<α(τ)
      	 and lim_t→ 0 t^-1/ατ_t=0
      	 if α>α(τ).
  
  (cf. <cit.>). 
  
  
  
  Let X be a spectrally positive Lévy process with parameters (0,0,ν). 
  Note that the conclusions we want to establish do not depend on large jumps. 
  Hence, we assume that  the Lévy measure ν is supported on [0,1]. 
  
  Our hypothesis with α implies that X is of infinite variation (∫_0^1 x νdx=∞); 
  thanks to a celebrated theorem of Rogozin, 
  we know that lim sup_t→ 0+ X_t/t=lim sup_t→ 0+ -X_t/t=∞ 
  and therefore 0 is regular for both half-lines (0,∞) and (-∞,0) 
  (cf. <cit.> or <cit.>). 
  
  
  The Laplace exponent Ψ of X 
  (which satisfies e^-λ X_t=e^tΨλ)  
   is given by
  
      Ψλ=∫_0^1 (e^-λ x-1+λ x) νdx.
  In the case σ>0, for γ∈ (1,2) we have λ^-γΨλ≥σ^2λ^2-γ/2→∞. When σ=0, we now prove the same convergence for γ∈ (1,α). 
  We will denote by Φ the right-continuous inverse of Ψ given by Φλ=infu≥ 0: Ψu>λ.  Φ appears naturally when considering the running maximum of -X. 
  Indeed, if τ̂_t=infs: -X_s>t, then τ̂_t is a subordinator with Lapace exponent Φ. 
  From our assumption x^αν(x)→∞ as x→ 0. 
  Given γ∈ (1,α) and k>0, 
  choose >0 such that νy≥ k y^-γ if y∈ (0,).
  
  For x>0 define
      νx=∫_x^1 νx  dx.
  Then, for any x∈ (0,), 
  
      νx
      	=∫_x^1 νx  dx
      	≥∫_x^νx  dx
      	≥k/γ-1⟨x^-(γ-1)-^-(γ-1)|.
  Use Fubini's theorem to write the Laplace exponent Ψ of X as follows
  
      Ψλ
      	=∫_0^1 ⟨e^-λ x-1+λ x| νdx
      
      	=λνT/λ,
  where T is a standard exponential random variable independent of X. 
  
  Then, 
  
      λ^-γΨλ≥λ^-(γ-1)νT/λT/λ≤≥λ^-(γ-1)k/γ-1⟨λ/T^γ-1-^-(γ-1)|T/λ≤
  Considering the inferior limit as λ→∞, the second summand disappears, and we get: 
  
      lim inf_λ→∞λ^-γΨλ≥k/γ-1Γ2-γ.
  Since the above is valid for any k>0, joining the two cases we deduce that
  
      lim_λ→∞λ^-γΨλ=∞ for any γ∈ (1,α∧ 2) .
  It therefore follows that 
  
      lim_λ→∞λ^-1/γΦλ=0.
  for any γ∈ (1,α)⊂ (1,2). 
  In terms of indices, we see that ατ̂≤ 1/α<1. 
  Now, under our assumptions, the drift of τ̂ is zero. 
  Indeed, if Φ̃ is the Laplace exponent of any subordinator, the corresponding drift is given by lim_λ→∞Φ̃λ/λ. 
  Note that the hypotheses α(X)>1 or σ>0 implies that 
  
      1/λΨλ
      =σ^2/2λ+∫_0^1 ⟨1-e^-λ x|νx  dx
      →∞    λ→∞.
  
  Hence, the drift of τ̂ equals
  
      lim_λ→∞Φλ/λ
      =lim_λ→∞λ/Ψλ
      =0.
  
  
  
  From Theorem 3.1 in <cit.>, we deduce that
  
      lim_t→ 0τ̂_t/t^γ=0.
  for γ∈ (1,α)⊂ (1,2). -X and τ̂ satisfy the following: if -X_t=y then τ̂_y≥ t. Hence
  
      lim inf_t→ 0-X_t/t^1/γ≥lim inf_y→ 0+y/τ̂_y^1/γ=∞,
  which settles the first part of the proposition. 
  
  
  Let us pass to the second part. 
  Let X be the running maximum process  of X given by X_t=sup_s≤ t X_s. 
  
  It is well known that the reflected process X-X is a Feller process (cf. <cit.>); regularity of 0 for both half-lines implies that 0 is a regular and instantaneous state for the reflected process  
  so that we can define local times at zero, denoted L. 
  Then, the upward process,  denoted (τ,H), is defined by 
  
      (τ,H)=(L^-1, X∘ L^-1);
  it allows one to sample the Lévy process X only at the times at which it achieves a new maximum. 
  It is a two-dimensional subordinator. 
  Since X is spectrally positive,  
  
  the Laplace exponent of (τ,H) can be obtained as follows: 
  
      -1/tloge^-λτ_t -μ H_t
      	
      	=-cΨμ-λ/Φλ-μ
  where c is a constant depending on the normalization of the local time L. (See for example formulae 9.2.8 and 9.2.9 in <cit.>.) 
  
  In particular, since X is spectrally positive, 
  
  the Laplace exponents of L^-1 and H are given by
  
  
      -1/tloge^-λτ   = cλ/Φλ   and      -1/tloge^-μ H_t   = cΨμ/μ.
  
  To obtain the drifts of τ and H, 
  first note that Ψλ→∞ as λ→∞, and thus  Φλ→∞ as λ→∞. 
  Hence, 
  
      lim_λ→∞cλ/Φλλ=0
  so that the drift of τ is zero. 
  On the other hand, recall that lim_μ→∞μ^-2Ψμ exists and equals the Gaussian coefficient of X (see <cit.>). 
  We deduce that the drift of H equals σ^2/2.
  
  
  Let us now obtain bounds on  the upper Blumenthal-Getoor indices for τ. 
  The upper index for X has a similar definition to that of subordinators, but in terms of its Laplace exponent Ψ; 
  it will be denoted by α(X) in terms of our hypotheses, α(X)≤α̃<1/(2-α). 
  Note that if δ<1 and 1/(1-δ)>α(X) then
  
      lim_λ→∞λ/λ^δΦλ
      	
      	=lim_λ→∞⟨Ψλ/λ^1/(1-δ)|^1-δ
      	=0.
  We conclude that α(τ)≤ 1-1/α(X). 
  Finally, for H, note that if δ∈ (0,α-1) then we have proved in (<ref>) that 
  
      lim_λ→∞Ψλ/λ^δλ=∞.
  We conclude that α-1≤α(H). 
  
  
  
  Let us now show that under our hypotheses, α(τ)<α(H). 
  Indeed, we have shown that α(τ)≤ 1-1/α(X) and α-1≤α(H). 
  However, our hypothesis
  
      α(X)<1/2-α
  implies 1-1/α(X)< α-1. 
  
  Let L=τ^-1. 
  Recall that, from Lemme 4 in <cit.> that the future minimum of the post-minimum process of X has the same law as H∘ L 
  and that 
  X=H^-∘ L. 
  We can therefore find γ>1 and δ∈ (0,1) such that γα(τ)<δ<α(H). 
  Therefore
  
      lim_t→ 0H_t/t^1/δ=lim_t→ 0H^-_t/t^1/δ=∞, 
      	  lim_t→ 0τ_t/t^γ/δ=0
  and then (reasoning as with -X and τ̂ above)
  
      lim_t→ 0X_t/t^1/γ
      	=lim_t→ 0H^-∘ L_t/t^1/γ≥lim_t→ 0H^-_t/τ_t^1/γ
      	=lim_t→ 0H^-_t/t^1/δ⟨t^γ/δ/τ_t|^1/γ
      	=∞.
  
  
  Finally, in the case σ>0 we have X_t≥σ^2 L_t/2. 
  Note that above we obtained the bound α(τ)≤ 1-1/α(X) using only the definitions of α(τ) and α(X). 
  Since α(X) ≤ 2, we have α(τ)≤ 1/2. 
  Thus, for any γ>1 such that α(τ)<1/γ, similarly as before 
  
      lim_t→ 0X_t/t^1/γ≥σ^2/2lim_t→ 0⟨t^γ/τ_t|^1/γ
      =∞.
  
  
  
  
  
   §.§ EI processes after their minimum
   
  
  The objective of this subsection is to prove Proposition <ref> and therefore finish the proof of Propositions <ref> and <ref>. 
  
  We do this by first showing the result in discrete time and then passing to the limit. 
  In discrete time, we first prove that the excursions below the running maximum are reversible, 
  which allows us to prove a path transformation that explains Proposition <ref> in the discrete time-case. 
  Finally, we tackle some technical results which allow us to pass to the limit. 
  
  Let W be a discrete time EI process on [n] 
  
  
  
  
  
  as introduced in Section <ref>. 
  As in that section, we will mainly work with extremal EI processes W; 
  recall that these are built from a sequence of increments,  say x=(x_i)_i=1^n. 
  Also, the possible trajectories of W are
  
      P=x^σ: σ is a permutation of  [s].
  In general, the law of W on P is uniform, 
  except when different permutations give rise to the same trajectory. 
  Hence, the law of W is uniform on P when x has the different subset sum property 
  (∑_i∈ I_1 x_i≠∑_i∈ I_2 x_i if I_1 and I_2 are different subsets of [s]) 
  and in particular when x is a sample from a non-atomic distribution. 
  We will use uniformity in establishing the invariance of W under path-transformations by using bijections between the set P. 
  Also, general EI processes can be thought of as extremal ones with the jumps x taken at random. 
  In particular, random walks correspond to when x is a sample from a given distribution. 
  
  We will be interested in the (complete) excursions of W under its running maximum W 
  given by W_j=max_i≤ j W_i. 
  To define them formally, consider the (random) set Z=i∈ [n]_0: X_i=X_i, 
  where [n]_0={0,1,…, n }. 
  If Z=0=I_0<I_1<⋯<I_K≤ n, 
  we define the excursion intervals of W under W as [I_j-1,I_j) for 1≤ j≤ K. 
  (K=0 if X_n<X_n=0, in which case there are no excursion intervals.) 
  	
  Let B_k be the set of paths w:[n]_0↦ in P  having k excursions below its maximum, 
  for k∈ [n]_0. 
  We now  prove that the excursions of X below its maximum are exchangeable.
  
  	
  	
  
  For any k∈ [n], let σ be a permutation on [k]. 
  For any w∈B_k, let ϕ_σ(w):=w̃ be the transformation that permutes the k excursions of w below its maximum by means of σ. 
  Then, the transformation w↦w̃ is a bijection. 
  
  
  
  
  Note that ϕ_σ^-1∘ϕ_σ=ϕ_σ∘ϕ_σ^-1=𝕀. 
  	
  	
  Now we define a transformation that permutes the excursions below the maximum of W, and prove that the distribution remains unchanged.
  	
  
  
  
  Let X be an extremal EI process based on a deterministic difference sequence x=(x_i)_i=1^n satisfying the different subset sum property. 
  Fix deterministic permutations (σ_k,k∈ [n]_0) where σ_k∈ S_k, 
  and define ϕ(W) as ϕ_σ_k(W)  if W∈B_k. 
  
  
  
  Then, we have the equality in distribution
  
      Wd=ϕ(W).
  
  
  
  Note that ϕ is a random bijection of P, but equals the deterministic bijection ϕ_σ_k if W∈B_k. 
  Since ϕ does not change the number of excursions below the maximum, we have that ϕ(W)∈B_k if and only if W∈B_k. 
  Fix k∈ [n]_0 and w∈B_k. 
  Then
  
  
      ϕ(W)=w
      =ϕ_σ_k(W)=w
      =W=ϕ_σ_k^-1(w)
      =1/n!.
  The last equality follows because, thanks to the different subset sum property, W is uniform on P. 
  Therefore ϕ(W) is also uniform on P and hence equal in law to W. 
  
  	
  	
  We can now obtain Proposition <ref>, by applying the above result with the particular permutations σ_k that just reverse the order of the excursions below the minimum. 
  Let us see how this is true for discrete time EI processes and then how to pass to the limit. 
  
  
  
  Let X be a discrete time extremal EI process on [0,1], having jumps at times j/n, for j∈ [n]_0 constructed from the deterministic jump sequence x=(x_i)_i=1^n which satisfies the different subset sum property. 
  
  Then  X reaches its minimum at a unique time ρ∈ [0,1),  its supremum at a unique time η∈ (0,1] and
  	
      X_ρ+j/n-X_ρ_0≤ j≤ n-nρd=X∘ d(j/n)_0≤ j≤ nη.
  
  
  
  Uniqueness of the minimum and the maximum are obvious since otherwise there would be two different subsets of x with the same sum. 
  
  The proof equality in law is based on a simple path transformation of X, which is the composition of the time-reversal operation X↦ (-X_1-t)_t∈ [0,1], together with the transformation ϕ obtained in Lemma <ref> when σ_k is the reversal permutation sending i to n-i+1. 
  Call the result X̃. 
  Since both transformation leading to X̃ preserve the law, we see that X̃d= X. 
  To conclude, just note that (with obvious notation) X̃∘d̃=  X_ρ+·- X_ρ. 
  (See Figure <ref> for an illustration.)
  
  
  
  
  
  Consider now an EI process X as in Proposition <ref> 
  and let X^n be such that
  
      X^n_t=X_(k+1)/n if t∈ [k/n,(k+1)/n).
  Then, X^n is an EI process on k/n: 0≤ k≤ n and, by right continuity of X, 
  X^n→ X almost surely (as random elements of Skorohod space). 
  Recall the definition of d and define d^n analogously to d but for the process X^n. 
  The following lemma will allow us to prove Proposition <ref> by passing to the limit in Proposition <ref>. 
  
  
  For any fixed t∈ [0,1] we have d^n(t)→ d(t) almost surely, 
  and X^n∘ d^n→ X∘ d in the sense of finite-dimensional distributions. 
  
  
  For the proof, we need an additional lemma. 
  
  The following lemma will be used to prove that 0 is instantaneous for X-X (meaning that, for every >0 there exists t_∈ (0,) such that X_t_-X_t_>0 ), 
  which is needed to prove that d^n_t→ d_t. 
  It is similar to the strong Markov property and can be proven quite simply by a path transformation due to Kallenberg. 
  
  
  
  	
  	Let X be an extremal EI process on [0,1] and let T be a stopping time on [0,1]
  	
  	. 
  	Then the process X̃ given by
  	
      X̃_t=
      	
      	X_t+T-X_T	    0≤ t≤ 1-T
      
      	X_1-X_(1-t)-    1-T<t≤ 1
  has the same law as X. 
  
  
  	The assertion will follow from the predictable mapping theorem for EI processes (cf. <cit.>), once we show that random bijection V of [0,1] given by 
  	
      V_t=
      	1-t	    0≤ t≤ T
      
      	t-T	    T<t≤ 1
  preserves Lebesgue measure and is predictable (in the sense that for any t≥ 0, the process V_·≤ t is predictable). Indeed, the predictable mapping theorem tells us that the process I:t↦∫_0^1 V_s≤ t  dX_s has the same law as X and we will now see that X̃=I. 
  	
  	That V preserves Lebesgue measure can be seen simply as follows: the effect of V is to interchange the intervals [0,T] and [T,1], reflecting the former. 
  	
  	On the other hand, since V is càg, predictability follows if V is adapted. 
  	However, note that
  	
      V_s≤ t
      	
      	=T≤ 1-t, T≤ s-t∪T>1-t, 1-t≤ s.
  The first set on the union belongs to _s-t⊂_s, while the second one belongs to _1-t⊂_s  if 1-t≤ s and equals ∅ otherwise. In any case, we see that V_s≤ t∈_s. 
  	
  	Also, note that s≥ 0: V_s≤ t is one of two stochastic intervals: 
  	either [T,T+t] if t≤ 1-T or [1-t,1] if t>1-T. 
  	Hence, ∫_0^1 V_s≤ t   dX_s=X̃_t. 
  	We deduce from the predictable mapping theorem that X̃d=X. 
  
  
  Define 𝒵:={t∈ [0,1]:X_t=X_t }. 
  
  
  
  We will use Lemma 8 in <cit.>, 
  which gives conditions for the continuity (on Skorohod's space) of the hitting times and hitting positions of an open set. 
  Fixing t∈ (0,1), we will consider the (random) open set O=(X_t,∞). 
  The aforementioned lemma 8 tells us that if X cannot approach O without reaching O and if there are no jumps from ∂ O into O then d^n_t→ d_t and X^n_d^n_t→ X_d_t. 
  To prove this, let us note that X does not jump when it approaches a level of its previous maximum. 
  In other words, that if R=infs≥ t: X_s->X_t, then Δ X_R=0. 
  This follows since otherwise the reflected process X̂ features a jump time U such that X̂_U+·-X̂_U is negative on a right neighborhood of 0. However, by Lemma <ref> tells us that the latter has the same behavior as X̂ on a neighborhood of zero Theorem 1 in <cit.> tells us that infinite variation EI processes such as X̂ achieve positive values immediately. 
  But then, if A is the approach time of O given by infs≥ t: X_s- or X_s≥X_t, we see that X_A≥X_t. Also, Lemma <ref> tells us that right after X_A, X reaches higher levels. Hence, we see that A coincides with the hitting time of O. 
  We have proved the two conditions implying that, for every fixed t∈ (0,1), almost surely, d^n_t→ d_t and X^n_d^n_t→ X_d_t. The finite-dimensional convergence now follows. 
  
  
   
  By Proposition <ref>, 
  we have that
  
      X^n_ρ_n+·-X^n_ρ_nd=X^n∘ d^n
  
  Regarding the left hand side, recall that the minimum is a continuous operation on Skorohod space (cf. <cit.>) and that ρ_n→ρ (by uniqueness of the minimum). 
  Hence, we see that
  
      X^n_ρ_n+·-X^n_ρ_n→X_ρ+·-X_ρ.
  
  But then, Proposition <ref> and Lemma <ref> tell us that the  processes 
  
      X_ρ+·-X_ρ  and    
      	X∘ d
  have the same finite-dimensional distributions, so forcibly the same law. 
  
  
  We have just finished providing the proofs of the main results of the paper, 
  contained in the statements of the Propositions and the Theorem in  Section <ref>. 
  All that remains is to give further remarks on the examples, by proving Corollary <ref> and showing how one can construct degree sequences satisfying the hypotheses of Theorem <ref>. 
  
  
  
  
  § SOME REMARKS ON THE EXAMPLES
  
  
  
  This section has two objectives. 
  First, to prove Corollary <ref>. 
  Secondly, to construct degree sequences showing the general applicability of Theorem <ref>.
  
  
  
   §.§ Application to Conditioned Galton-Watson trees
  
  Let us turn to the proof of Corollary <ref>. 
  Part of the interest of this proposition lies in showing how one can apply Theorem <ref> to non-extremal EI processes. 
  
  Let μ be a critical and aperiodic offspring distribution 
  which either has finite variance or regularly varying tails 
  as stated in Corollary <ref>. 
  Consider a random walk W with jump distribution μ̃ given by μ̃_k=μ_k+1. 
  W oscillates as it has mean zero and therefore its hitting time T of -1 is finite almost surely. 
  From Section 1.2 in <cit.> (see also the introduction to <cit.>), 
  we know that the BFW of the μ-Galton-Watson tree has the same law 
  as the random length sequence 1+W_0,1+W_1,…, 1+W_T. 
  Therefore the size of of the tree has the same law as T 
  and aperiodicity implies that 
  T=n>0 for large enough n, so that the CGW(n) tree is well defined. 
  Also, one sees that the BFW X^n of the CGW(n) tree 
  has the same law as (1+W_i,i≤ n) conditionally on T=n. 
  This process can also be obtained by means of the Vervaat transformation 
  of the random walk bridge W^b of length n from 1 to 0 
   by interchanging the pre first minimum and post first minimum parts of the trajectory. 
  The random walk bridge has the law of (1+W_i,i≤ n) conditionally on W_n=-1. 
  Since, by Kemperman's formula 
  (related to the preceeding assertion on the Vervaat transformation in <cit.>, <cit.>), 
  T=n=W_n=-1/n, 
  then the bridge is also well defined for large n. 
  As is well known, the random walk W has a scaling limit. 
  If μ has finite variance σ^2>0, 
  (W_nt/√(n),t≥ 0) converges weakly in Skorohod space 
  to Z=σ B where B is a Brownian motion. 
  If, on the other hand, μ_n∼ n^-αLn 
  for some regularly varying function L and some α∈ (1,2)  
  then (W_nt/b_n,t≥ 0) converges weakly 
  to an α-stable Lévy process Z with no negative jumps, where b_n is a regularly varying sequence of index 1/α<1. Note that in both cases the size of the tree is n and n/b_n→∞. 
  There are also convergence results for the corresponding bridge and for the BFWs. 
  Indeed, the latter follows from the former by continuity of the Vervaat transformation on functions that achieve their minimum uniquely and continuously. 
  To get convergence of the bridges, one can use <cit.>; 
  and for the convergence of 
  BFWs of a CGW(n), recall that 
  the classical result from <cit.> implies that the BFW of the CGW(n) W̃ is such that (W̃_nt, 0≤ t≤ 1) converges weakly to X=σ e where e is the so-called normalized Brownian excursion. 
  When μ has regularly varying tails, Proposition 13 in <cit.> or 
  Lemma 4.5 from <cit.> give us the same result for W̃ under the spatial normalization b_n∼ n^1/αL̃(n) for some slowly varying function L̃, where now X is the normalized stable excursion. These stable excursions can be obtained from the bridge by applying the Vervaat transformation as in <cit.> and <cit.>. 
  
  
  
  Let X be the normalized excursion of an α-stable process with no negative jumps and index α∈ (1,2]. 
  Then ∫_0^1 1/X_s  ds<∞. 
  
  
  The lemma follows simply from results in the literature (for α=2 several ways to prove the integrability of 1/e on [0,1] are given in <cit.>). 
  However, it also follows from the analysis in Section <ref>, 
  which is why we briefly sketch both approaches. 
  
  In the finite variance case when α=2, X and (X_1-t,0≤ t≤ 1) have the same law and (X_t,t≤ 1/2) is absolutely continuous with respect to the three-dimensional Bessel process R. 
  On the other hand, the Brownian escape process F_t=inf_s≥ t R_s is the inverse of a stable subordinator τ of index 1/2 as shown in <cit.>. 
  By <cit.>, we see that lim sup_t→ 0τ_t/t^2=0. 
  Hence, lim inf_t→ 0R_s/√(s)≥lim inf_t→ 0F_s/√(s)=∞. 
  Therefore, for some random >0, ∫_[0,]∪[1-,1] 1/X_s  ds<∞. 
  Since X_t=0 only for t=0,1, we deduce the result in this case. 
  
  When α<2, the statement is proved using continuous state branching processes with immigration in Lemma 9 and the final comment of <cit.>. 
  It is also proved in <cit.> by applying the stretched exponential bounds on the tails of the distribution of the height of CGW(n) trees of <cit.>. 
  However, we can give a proof as in the preceeding paragraph. 
  First let us note that the statement follows if we find power law bounds for the pre and post minimum processes of X^b, by the Vervaat transformation. 
  Let ρ_t be the unique place that X^b reaches its minimum on [0,t]; 
  it is known that the minimum is achieved uniquely and continuously under our hypothesis. 
  Therefore ρ_t=ρ as long as t is close enough to 1 so that for positive β we have
  
      lim inf_s→ 0X^b_ρ+s-X^b_ρ/s^β=∞
      =
      lim_t→ 1lim inf_s→ 0X^b_ρ_t+s-X^b_ρ_t/s^β=∞.
  However, recall that X^b is locally absolutely continuous with respect to X (cf. <cit.>): 
  if t<1 then
  
      lim inf_s→ 0X^b_ρ_t+s-X^b_ρ_t/s^β=∞
      =lim inf_s→ 0X_ρ_t+s/s^β=∞f̂_1-t(X_s)/f̂_1(t)=0,
  where f̂_t is the density of -X_t and the last equality follows from Proposition <ref> whenever β∈ (1/α, 1) for some β<1. 
  An analogous result holds for the pre minimum of the bridge. 
  Since the minimum is achieved uniquely, we see that, almost surely
  
      ∫_0^1 1/X^b_s-X^b_ρ  ds<∞.
  
  
  
  
  We have already argued that, under the conditions of Corollary <ref>, 
  the breadth-first walks have scaling limits equal to the Vervaat transform of an exchangeable increment process of unbounded variation: either the Brownian bridge or the stable bridge of index α∈ (1,2). 
  Thanks to Skorohod's representation result, 
  we can place ourselves in a probability space where the convergence W^b_n·/b_n holds almost surely. 
  
  Let β^n_1≥β^n_2≥⋯>0 be the ranked jumps of W^b/b_n and β^1≥β_2⋯ be the corresponding ones for X. If we add one to the former, we get the ordered child sequence  associated to the random degree sequence  of the conditioned Galton-Watson trees. 
  
  Since W^b and X^b are exchangeable increment processes, 
  the convergence of W^b_n·/a_n→ X^b is equivalent (thanks to Theorem 2.2 in <cit.> as recalled in Subsection <ref>) to that of
  
      β^n_i→β_i
      	  and  ∑_i (β^n_i)^2→∑_i β_i^2.
  (in the regularly varying case) and to
  
      β^n_i→ 0
      	  and  ∑_i (β^n_i)^2→σ^2.
  in the finite variance case. 
  
  Also, our discussion in Section <ref> on the fact that conditioned Galton-Watson trees, conditioned on their degree sequence being s have law _s, implies that
      W^b=w=_β^nW^n=w
  where _β^n is the law of an exchangeable increment process constructed from the sequence of jumps β^n as in Section <ref>. The similar statement
  
      X^b∈ A=_βX^b∈ A
  is true, where _β is the law of the continuous EI process obtained through Kallenberg's representation in Equation (<ref>) out of the jumps β. 
  Since the sequences β^n and β almost surely satisfy the conditions of Theorem <ref>, we obtain
  
      _β^nHX^n,C^n,Z^n→_βHX,C,Z
  for continuous and bounded functionals H. 
  The bounded convergence theorem let's us conclude that, 
  
      HX^n,C^n,Z^n_β^nHX^n,C^n,Z^n→_βHX,C,Z
      	=HX,C,Z,
  which concludes the proof of Corollary <ref>. 
  
  
  
  
   §.§ Examples of degree sequences satisfying the assumptions of Theorem <ref>
  
  [Infinite variation EI process with σ=0]
  Let (β_j,j∈)⊂_+ be a deterministic sequence such that ∑β_j^2<∞ and ∑β_j=∞. 
  For simplicity assume β_j> β_j+1 for every j. 
  
  
  Consider a sequence (b_n,n∈)⊂ such that b_n→∞, and assume that for M_n:=sup{j:β_ja_n≥ 1 }, we have ∑_1^M_nβ_j/b_n→ 0 as n→∞.
  For the child sequence d^n_j=β_jb_n, define for n big enough the degree sequence 
  
      N^n_0=1+∑_1^M_n d^n_j-M_n         N^n_d^n_j =1   j∈ [M_n].
  
  
  To obtain the scaling of the BFW given in hypothesis Hubs, we compute
  
      ∑_0^d^n_1(j-1)^2/b_n^2N^n_j
      =∑_1^M_nβ_j b_n^2/b_n^2-s_n/b_n^2+2/b_n^2
      =∑_1^M_nβ_j b_n^2/b_n^2-∑_1^M_nβ_jb_n/b_n^2+1/b_n^2.
  The first term is bounded by ∑β_j^2 and the negative of the second by ∑_1^M_nβ_j/b_n. 
  Hence, by the hypothesis on M_n and b_n, the above display converges to ∑β_j^2.  
  Finally, for every m∈ we obtain s_n/b_n≥∑_1^m β_j, implying the hypothesis of Theorem <ref>. 
  
  An explicit sequence satisfying the previous assumptions is β_j=j^-α and b_n=1/β_n for j,n∈ and α∈ (1/2,1).
  To see this, note that for n big enough we have for some positive c that ∑_1^nβ_j^γ≈ c n^1-αγ-1 which is finite or infinite, for 1/α<γ or 1/α>γ respectively.
  Therefore, the hypothesis on α implies sup{γ:∑β_j^γ=∞}=inf{γ:∑β_j^γ<∞}=1/α∈ (1,2). 
  
  Now, let {x } denote the fractional part of x∈.  
  Since n^-αn^α=1-n^-α{n^α}≤ 1, then M_n≤ n. 
  
  It follows that for some positive constant c
  
  
  
  
      1/b_n∑_1^M_nβ_j≤1/n^α∑_1^nβ_j≤ c1/n^αn^1-α-1∼n^1-2α-n^-α→ 0.
  
  
  
  [EI process with σ>0 and jumps]
  	Let X be an extremal EI process with parameters (0,σ,β), where σ>0, having jumps (β_j,j∈ [M]), with M∈∪{∞} and ∑_1^M β_j^2<∞.
  	For simplicity assume β_j>β_j+1>0 for every j∈ [M-1]. 
  	Following <cit.>, consider a degree sequence s_n=(N^n_j) of size s_n=∑ N^n_j such that Δ_n=max{j:N^n_j>0 }=o(√(s_n)) and 
  	
      σ^2=lim_n∑_1^Δ_nj^2/s_nN^n_j-1.
  We know from <cit.> that in this case b_n=√(s_n), and the rescaled BFW's converge to the Brownian excursion. 
  	We add jumps to the degree sequence. 
  	
  	Consider M_n↑ M satisfying ∑_1^M_nβ_j/√(s_n)→ 0 as n→∞, and define d^n_j=β_j√(s_n) for j≤ M_n. 
  	Construct the degree sequence s̃_n=(Ñ^n_j) as
  	
      Ñ^n_i=  
      	N^n_0+∑_1^M_n[d^n_j-1]     i=0 
      
      	N^n_i     1≤ i≤Δ_n
      
      	1     d^n_M_n≤ i≤ d^n_1,
  noting that Δ_n<d^n_M_n for n big enough. 
  	If s̃_n is the size of s̃_n, then 
  	
      s̃_n/s_n-1=∑_1^M_nd^n_j/s_n≤1/√(s_n)∑_1^M_nβ_j → 0
  by hypothesis.
  	Finally, since for the child sequence (d̃^n_j) of s̃_n we have
  	
      ∑[j-1]^2/s̃_nÑ^n_j
      	=∑_1^Δ_nj^2/s̃_nN^n_j-1+∑_1^M_nβ_j √(s_n)^2/s̃_n+2/s̃_n≤s_n/s̃_n∑_1^Δ_nj^2/s_nN^n_j-1+s_n/s̃_n∑_1^∞β_j^2+1,
  using dominated convergence the left-hand side converges to σ^2+∑_1^M β_j^2, and thus, the scaling is b̃_n=√(s̃_n).
  
  
  
  
  
  
  
  § ACKNOWLEDGEMENTS
  
  Research supported by CoNaCyT grant FC 2016 1946 and UNAM-DGAPA-PAPIIT grants IN115217 and IN114720.
  
  amsalpha
  