François Bienvenu

Jean-Jil Duchamps

Félix Foutel-Rodier

The Moran forest

Starting from any graph on {1, . . . , n}, consider the Markov chain where at each time-step a uniformly chosen vertex is disconnected from all of its neighbors and reconnected to another uniformly chosen vertex. This Markov chain has a stationary distribution whose support is the set of non-empty forests on {1, . . . , n}. The random forest corresponding to this stationary distribution has interesting connections with the uniform rooted labeled tree and the uniform attachment tree. We fully characterize its degree distribution, the distribution of its number of trees, and the limit distribution of the size of a tree sampled uniformly. We also show that the size of the largest tree is asymptotically α log n, where α = (1 -log(e -1)) -1 ≈ 2.18, and that the degree of the most connected vertex is asymptotically log n/ log log n.

This Markov chain has a stationary distribution whose support is the set of nonempty rooted forests on {1, . . . , n}. By rooted forest we mean a disjoint union of rooted trees -or, equivalently, a directed graph where each vertex has at most one incoming edge; any vertex ρ with no incoming edge can then be seen as the root of a tree consisting of all vertices accessible from ρ. To see why the stationary graph is a rooted forest, note that:

• The graph cannot be empty because there is always an edge between the two vertices involved in the last transition.

• Starting from any graph, the chain will eventually reach a forest (for instance, the sequence of transitions [START_REF]The On-Line Encyclopedia of Integer Sequences[END_REF][START_REF] Aigner | Proofs from the book[END_REF], [START_REF]The On-Line Encyclopedia of Integer Sequences[END_REF][START_REF] Aldous | The random walk construction of uniform spanning trees and uniform labelled trees[END_REF], . . . , (1, n) will at some point turn the graph into the star graph rooted on vertex 1).

• The chain cannot leave the set of forests because its transitions cannot make a vertex have two incoming edges.

• Any non-empty rooted forest is accessible from any other graph (if not clear, this will become apparent in Section 2).

• The chain is aperiodic because it can stay in the same state.

The stationary distribution of this chain is the random forest model that we study in this paper. We call it the Moran forest, and use the notation F n to denote a random forest having this distribution. Our interest in this object lies in its connection with the Moran model of population genetics [START_REF] Moran | Random processes in genetics[END_REF]. The Moran model describes the dynamics of a population of constant size n where, at each time step, two distinct individuals are sampled uniformly at random, and the second one is replaced by a copy of the first one. The Markov chain that we consider thus corresponds to the family structure of extant individuals in a Moran model. The Moran model is a central object in mathematical population genetics [START_REF] Durrett | Probability Models for DNA Sequence Evolution[END_REF][START_REF] Etheridge | Some Mathematical Models From Population Genetics[END_REF], whose extensions have been used in a variety of other contexts, including diversification [START_REF] Hey | Using phylogenetic trees to study speciation and extinction[END_REF][START_REF] Morlon | Inferring the dynamics of diversification: A coalescent approach[END_REF] and evolutionary game theory [START_REF] Nowak | Evolutionary Dynamics: Exploring the Equations of Life[END_REF].

Main results

Our first result, which we detail in Section 2, is that there is a simple way to sample F n . This construction enables us to study several of its statistics, such as its number of trees (Section 3.1), its degree distribution (Section 4.1), and the typical size of its trees (Section 5.2). Some of these results are presented in Table 1. T U Asymptotic size of Geometric(e -X ), a uniform tree where X ∼ 2xdx on [0, 1]

Notation Variable Distribution

Table 1: Some statistics of the Moran forest, for fixed n in the case of the number of trees, and as n → ∞ for the degree and the size of a uniform tree. Note that the degree also has a simple, explicit distribution for fixed n (see Proposition 4.1); also, the Bernoulli and the Poisson r.v. appearing in the sum correspond respectively to the in-and out-degrees.

The Bernoulli variables I used to describe the distribution of N n are independent and, conditional on U , so are the Bernoulli and Poisson variables used for the distribution of D.

In Section 3.2, we show that the Moran forest is closely linked to the uniform rooted labeled tree. Specifically, we prove the following theorem.

Theorem 1.1. Let T be a uniform rooted tree on {1, . . . , n -1}. From this tree, build a forest F on {1, . . . , n} according to the following procedure:

1. Remove all decreasing edges from T (that is, edges uv pointing away from the root such that u > v).

Add a vertex labeled n and connect it to a uniformly chosen vertex of T

3. Relabel vertices according to a uniform permutation of {1, . . . , n}.

Then, the resulting forest F has the law of the Moran forest F n .

Finally, we study the asymptotic concentration of the largest degree and of the size of the largest tree of F n . The following theorems are proved in Sections 4.2 and 5. to be the vertex to which it was then reconnected. We refer to the time τ t (w) as the birth time of w, and to the vertex m t (w) as its mother. Note that the variables (τ t (w), 1 w n) are independent of (m t (w), 1 v n).

Now, for each s t, let the vertices be in one of two states, active or inactive, as follows: vertex w is active at times s such that τ t (w) s t, and inactive at times s < τ t (w). Finally, let F n (t) be the forest obtained by connecting each vertex w to its mother if the mother is active at the time of birth of w, that is, there is an edge from m t (w) to w ⇐⇒ τ t (m t (w)) < τ t (w).

This procedure is illustrated in Figure 2. Let us show that the chain (F n (t), t ∈ Z) has the same transitions as the chain described in the introduction. First, note that for w = W t we have τ t (w) = τ t-1 (w), and thus m t (w) = m t-1 (w). As a result, edges that do not involve W t are the same in F n (t) and in F n (t-1). Now, τ t (W t ) = t, so that W t is always inactive as a mother in the construction of F n (t), and m t (W t ) = V t with τ t (V t ) < t, so that W t is linked to V t in F n (t). In other words, F n (t) is obtained from F n (t -1) by disconnecting W t from its neighbors, and then connecting it to V t . This corresponds to the transitions of the chain described in the introduction.

Finally, (F n (t), t ∈ Z) is stationary by construction, and thus F n (t) is distributed as the Moran forest for all time t ∈ Z.

Uniform attachment construction

We now give a forward-in-time variant of the construction described in the previous section. This forward-in-time procedure, which we call the uniform attachment construction (UA construction for short), is our main tool to study F n and will be used throughout the rest of the paper.

In the following, we fix n 2, since the forest F n is not defined for n = 1. Let (U n ( ), 1 n) be a vector of independent variables such that U n ( ) is uniformly distributed on {1, . . . , n} \ { }. Consider the forest F * n on {1, . . . , n} obtained by setting there is an edge from k to , with k < ⇐⇒ U n ( ) = k.

We will show that, after relabeling the vertices of F * n according to a uniform permutation of {1, . . . , n}, we obtain the Moran forest. Before this let us make a few remarks.

First, it will be helpful to think of the construction of F * n as a sequential process where, starting from a single vertex labeled 1, for = 2, . . . , n we add a new vertex labeled and connect it to U n ( ) if U n ( ) < . See Figure 3. This will make the link with some well-known stochastic processes more intuitive. This also explains that we speak of the -th vertex in the UA construction to refer to vertex in F * n . Second, the edges of F * n are by construction increasing, in the sense that every edge uv in the graph is such that u < v.

Rooted trees that have only increasing edges are known as recursive trees [START_REF] Drmota | Random Trees: An Interplay Between Combinatorics and Probability[END_REF], and forests of recursive trees have been called recursive forests [START_REF] Balińska | Random recursive forests[END_REF]. Recursive trees have been studied extensively. In particular, the uniform attachment tree, which corresponds to the uniform distribution over the set of recursive trees, has received much attention [START_REF] Bergeron | Varieties of increasing trees[END_REF][START_REF] Mahmoud | On the distribution of leaves in rooted subtrees of recursive trees[END_REF][START_REF] Meir | Cutting down recursive trees[END_REF]. However, the random forest F * n does not seem to correspond to any previously studied model of random recursive forest (in particular, it is not uniformly distributed over the set of recursive forests).

Figure 3: Illustration of the uniform attachment construction for n = 7 and the vector (U n (1), . . . , U n (n)) = (5, 4, 2, 1, 2, 7, 2). The -th vertical line from the left corresponds to vertex σ( ) (i.e, in the sequential vision, to the -th vertex that is added). U n ( ) is represented by the arrow pointing from the U n ( )-th line to the -th one at time . Compare this with Figure 2: the vertical lines corresponding to the vertices have been reordered in increasing order of their birth time, and the grey arrows that left no trace on the graph at the focal time have been removed. Proof. Consider the forest F n (0) built from the variables ((V t , W t ), t ∈ Z) in the previous section. To ease notation, we will omit the subscript in τ 0 and m 0 . The proof hinges on the fact that there is a natural coupling of F n (0) with a forest F * n having the aforementioned distribution, in a way such that conditional on F * n = F, F n (0) is a uniform relabeling of F.

Let us relabel the vertices in increasing order of their birth time: since the variables (τ (v), 1 v n) are all distinct, there exists a unique permutation σ of {1, . . . , n} such that

τ (σ(1)) < • • • < τ (σ(n)).
In words, σ( ) is the -th vertex that was born in the construction of F n (0). Using the new labeling, let us denote its birth time by τ * ( ) = τ (σ( )) and its mother by m * ( ) = σ -1 (m(σ( ))).

Now, for every vertex

v = σ( ), there is an edge from m(v) to v in F n (0) ⇐⇒ τ (m(v)) < τ (v) ⇐⇒ τ * (m * ( )) < τ * ( ) ⇐⇒ m * ( ) < .
Thus, if we set U n ( ) = m * ( ) in the construction of F * n then is connected to m * ( ) if and only if v = σ( ) is connected to m(v) = σ(m * ( )) in F n (0). Therefore, to finish the proof we have to show that:

(i) The variables (m * ( ), 1 n) are independent and such that m * ( ) is uniformly distributed on {1, . . . , n} \ { }.

(ii) The permutation σ is uniform and independent of (m * ( ), 1 n).

First, note that by construction the variables (m(v), 1 v n) are independent and that for each v, m(v) is uniformly distributed on {1, . . . , n} \ {v}. Since the permutation σ depends only on the variables (τ (v), 1 v n), which are independent of (m(v), 1 v n), we see that σ is independent of (m(v), 1 v n). Moreover, the variables (τ (v), 1 v n) are exchangeable so the permutation σ is uniform. Now, for any fixed permutation π of {1, . . . n} and any fixed map f : {1, . . . , n} → {1, . . . , n} such that f ( ) = for all , we have

P(σ = π, m * = f ) = P σ = π, m = π • f • π -1 = 1 n! 1 (n -1) n , concluding the proof.
One might hope to obtain a complete description of the distribution of the Moran forest from the UA construction. Indeed, let us denote by (S 1 , . . . , S Nn ) the sizes of the trees in the Moran forest, labeled in decreasing order of their sizes, and where N n is the number of trees. Then it is clear from the UA construction, that conditional on the vector (S 1 , . . . , S Nn ), the trees of the Moran forest are independent uniform attachment trees. Therefore, the study of the Moran forest reduces to that of the distribution of (S 1 , . . . , S Nn ). In the terminology of exchangeable partitions, we need to study the exchangeable partition probability function (EPPF) of the Moran forest [START_REF] Pitman | Combinatorial stochastic processes[END_REF]. However, we could not find any closed expression for this EPPF. Note that the Moran forest is not sampling consistent, i.e., the restriction of F n+1 to {1, . . . , n} is not distributed as F n . Therefore the EPPF of the Moran forest cannot be obtained through a Chinese restaurant process.

Number of trees 3.1 Law of the number of trees

In the UA construction, let I = 1 {Un( )< } be the indicator variable of the event "the -th vertex was linked to a previously added vertex". The variables (I 1 , . . . , I n ) are thus independent Bernoulli variables such that

I ∼ Bernoulli -1 n-1 .
With this notation, the number of edges |E n | and the number of trees N n are

|E n | = n =1 I and N n = n =1 (1 -I ) .
Moreover, since

I d = 1 -I n-+1
, we see that

P(N n = k) = P(N n = n -k) = P(|E n | = k) ,
that is, the number of trees and the number of edges have the same, symmetric distribution. In consequence, from now on we only use the notation N n and refer to it as the number of trees of F n when stating our results -even though we sometimes work with the number of edges in the proofs.

From the representation of N n as a sum of independent Bernoulli variables, we immediately get the following result.

Proposition 3.1. Let N n denote the number of trees of F n .

(i) E(N n ) = n 2 . (ii) Var(N n ) = n(n -2) 6(n -1) . (iii) G Nn (z) := E z Nn = n-1 k=1 1 + k n-1 (z -1) .
The representation of N n as a sum of independent Bernoulli variables also makes it straightforward to get the following central limit theorem.

Proposition 3.2. Let N n denote the number of trees of F n . Then,

N n -n/2 n/6 d ----→ n→∞ N (0, 1) .
Proof. This is an immediate consequence of the Lyapunov CLT for triangular arrays of independent random variables. Indeed, E |I -E(I )| 3 1. Therefore,

1 n 3/2 n =1 E |I -E(I )| 3 1 √ n ----→ n→∞ 0 ,
and the result follows, e.g., from Corollary 11.1.4 in [START_REF] Athreya | Measure Theory and Probability Theory[END_REF].

Link with uniform labeled trees

As announced in the introduction, there is a strong connection between the Moran forest and uniform labeled trees. Our starting point is the following observation about the probability generating function of N n . First, we can rewrite point (iii) of Proposition 3.1 as

G Nn (z) = z (n -1) n-2 n-2 k=1 n -1 -k + kz = n-2 k=0 a(n -1, k) (n -1) n-2 z k+1 , where n-2 k=0 a(n -1, k) z k = n-2 k=1 n -1 -k + kz .
Second, the coefficients of this polynomial have a simple combinatorial interpretation: a(n -1, k) is the number of rooted trees on {1, . . . , n -1} with k increasing edges, where an edge uv pointing away from the root is said to be increasing if u < v. This fact is known in the literature as a consequence of the more general Theorem 1.1 of [START_REF] Eğecioğlu | Bijections for Cayley trees, spanning trees, and their q-analogues[END_REF] (see also Example 1.7.2 in [START_REF] Drake | An Inversion Theorem for Labeled Trees and Some Limits of Areas Under Lattice Paths[END_REF] and Theorem 9.1 in [START_REF] Gessel | A refinement of Cayley's formula for trees[END_REF]). This simple observation already gives us the following proposition.

Proposition 3.3. The probability mass function of the number of trees of

F n is P(N n = k) = a(n -1, k -1) (n -1) n-2 ,
where a(n, k) is the number of rooted trees on {1, . . . n} with k increasing edges (sequence A067948 of the On-Line Encyclopedia of Integer Sequences [START_REF]The On-Line Encyclopedia of Integer Sequences[END_REF]).

Looking for a bijective proof of Proposition 3.3 naturally leads to the more general Theorem 1.1, which states that the Moran forest F n can be obtained from a uniform rooted tree on {1, . . . , n -1}, denoted by T , using the following procedure:

1. Remove all decreasing edges from T (that is, edges uv pointing away from the root such that u > v).

2. Add a vertex labeled n and connect it to a uniformly chosen vertex of T .

3. Relabel vertices according to a uniform permutation of {1, . . . , n}.

Proof of Theorem 1.1. In the UA construction, let F n-1 denote the forest obtained after the addition of n -1 vertices, before their relabeling. After this, the n-th vertex will be linked to a uniformly chosen vertex of F n-1 . As a result, to prove the theorem it suffices to show that F n-1 has the same law as the forest obtained from T by removing its decreasing edges.

To do so, we couple F n-1 and T in such a way that the edges of F n-1 are exactly the increasing edges of T . Formally, F n-1 is a deterministic function of the random vector U = (U n (2), . . . , U n (n -1)). Moreover, U is uniform on the set

S n-1 = u ∈ {1, . . . , n} {2,...,n-1} : u = .
Thus, to end the proof it is sufficient to find a bijection Φ from S n-1 to the set of rooted trees on {1, . . . , n -1} and such that

k ∈ F n-1 (u) ⇐⇒ k is an increasing edge of Φ(u) . First, let S n-1 = {1, . . . , n -1} {2,...,n-1}
and consider the bijection Θ :

S n-1 → S n-1 defined by Θu : → u -1 {u > } .
Importantly, note that Θ does not modify the entries of u that correspond to edges of

F n-1 (u), that is, for all k < , k ∈ F n-1 (u) ⇐⇒ u = k ⇐⇒ (Θu)( ) = k .
As a result, it remains to find a bijection Ψ from S n-1 to the set of rooted trees on {1, . . . , n -1} such that u < ⇐⇒ u and are linked by an increasing edge in Ψ(u) .

This bijection will essentially be that used in [START_REF] Eğecioğlu | Bijections for Cayley trees, spanning trees, and their q-analogues[END_REF], which can itself be seen as a variant of Joyal's bijection [START_REF] Aigner | Proofs from the book[END_REF][START_REF]Une théorie combinatoire des séries formelles[END_REF].

Let G u be the directed graph on {1, . . . , n -1} obtained by putting a directed edge going from u to for all 2.

If G u has no cycle or self-loop, then it is a tree. Moreover, the orientation of its edges uniquely identify vertex 1 as its root. Thus we set Ψ(u) = G u .

If G u is not a tree, set C 0 = {1} and let C 1 , . . . , C k denote the cycles of G u , taken in increasing order of their largest element and treating self-loops as cycles of length 1. Note that because each vertex has exactly one incoming edge, except for vertex 1 which has none, these cycles are vertex-disjoint and directed.

To turn G u into a tree, set s 0 = 1 and for i 1 let m i denote the largest element of C i and m i s i its out-going edge in C i . With this notation, for i = 1, . . . , k remove the edge m i s i from G u and replace it by

m i s i-1 . Note that • This turns C 0 • • • C k into a directed path P going from s k to 1. • Because m i = max C i and that 1 < m 1 < • • • < m k ,
every edge m i s i was non-increasing and has been replaced by the decreasing edge m i s i-1 .

Therefore, this procedure turns G u into a tree Ψ(u) rooted in s k , without modifying its increasing edges. Consequently, the increasing edges of Ψ(u) are exactly the pairs k for which k = u < .

To see that Ψ is a bijection, it suffices to note that the cycles C 0 , . . . , C k can be recovered unambiguously from the path P going from the root to vertex 1. Indeed, writing this path as the word 1m

Degrees

Degree of a fixed vertex

Using the UA construction and the notation from Section 2.2, let us denote by

• I = 1 {Un( )< } the indicator variable of the event "the -th vertex has an incoming edge linking it to a previously added vertex".

• X (v) = 1 {Un( )=σ -1 (v)} the indicator variable of the event "the -th vertex is linked to vertex v".

• B v = σ -1 (v) the step of the construction at which vertex v is added.
With this notation, the degree of vertex v is

D (v) n = I Bv + n =Bv+1 X (v) ,
where I Bv is the in-degree, and n =Bv+1 X (v) is the out-degree of vertex v. Moreover, conditional on

{B v = b}, (X (v) b+1 , . . . , X (v) n ) are i.i.d. Bernoulli variables with parameter 1/(n -1) and I b is a Bernoulli variable with parameter b-1 n-1 that is in- dependent of (X (v) b+1 , . . . , X (v) n ). As a result, conditional on B v and writing L v for n -B v , D (v) n d = Ber 1 -Lv n-1 + Bin L v , 1 n-1
, where the Bernoulli and the binomial variables are independent conditional on L v (here, as in similar expressions in the rest of this document, the Ber and Bin notation refers to random variables with the corresponding distribution, not the distributions themselves). Using that L v is uniformly distributed on {0, . . . , n -1}, the mean, variance and probability generating function of D (v) n are obtained by routine calculations. Proposition 4.1. Let D n be the degree of a fixed vertex of F n . Then,

(i) E(D n ) = 1. (ii) Var(D n ) = 2(n -2) 3(n -1) . (iii) G Dn (z) := E(z Dn ) = 1 n n-1 =0 1 + (1 -n-1 )(z -1) 1 + 1 n-1 (z -1) . (iii') G Dn (z) = 2 1 - 1 n 1 + z-1 n-1 n -1 z -1 -1.
Remark 4.2. Note that, conditional on L v , the probability that v has a (unique) incoming edge is 1 -Lv n-1 , and its mean out-degree is Lv n-1 . Therefore, summing the two we have E(D (v) n | L v ) = 1, that is, the average degree of a vertex is independent of the step at which it was added in the UA construction.

(i) D ∼ Ber(1 -U ) + Poisson(U )
, where U is uniform on [0, 1] and the Bernoulli and Poisson variables are independent conditional on U .

(ii) G D (z) := E z D = 1 0 1 + (1 -x)(z -1) e x(z-1) dx = 2 e z-1 -1 z -1 -1. (iii) For all p 1, E D(D -1) • • • (D -p + 1) = 2 p + 1 .
(iv) P(D = 0) = 1 -2/e and, for k 1,

P(D = k) = 2 e j>k 1 j! . Proof. First, for all z ∈ C \ {1}, G Dn (z) = 2 1 - 1 n 1 + z-1 n-1 n -1 z -1 -1 ----→ n→∞ 2 e z-1 -1 z -1 -1.
This pointwise convergence of the probability generating function of D n proves the convergence in distribution of D n to a random variable D satisfying (ii). Point (i) then follows immediately from the integral expression of G D .

To compute the factorial moments of D, note that

G D (z) = 2 k 0 (z -1) k (k + 1)! -1.
As a result, for p 1 the p-th derivative of G D is

G (p) D (z) = 2 k 0 (z -1) k (k + 1 + p)k! ,
and, in particular, E(D(D -1)

• • • (D -p + 1)) = G (p) D (1) = 2 p+1
, proving (iii). Finally, to prove (iv), using (i) we see that

P(D = 0) = 1 0 xe -x dx = 1 - 2 e
and that, for k 1,

P(D = k) = 1 k! 1 0 kx k-1 -kx k + x k+1 e -x dx.
Noting that kx k-1 -kx k + x k+1 e -x = 2x k e -x + d dx (x k -x k+1 )e -x , we get

P(D = k) = 2 k! 1 0
x k e -x dx, and an easy integration by parts yields

P(D = k + 1) = P(D = k) - 2 e(k + 1)! ,
from which (iv) follows by induction.

Before closing this section, let us give an asymptotic equivalent of the tail of D n . We will need it in the proof of Theorem 1.2 on the largest degree. (ii) For all

K n = o( √ n), there exists ε n = o(1) such that, for all k K n , |P(D n k) -P(D k)| ε n P(D k) . (iii) For all k n → +∞ and K n k n such that K n = o( √ n), P(D n k) ∼ 2/e (k + 1)! , uniformly in k such that k n k K n . Proof. First, observe that 1 ( + 1)! 1 • ! - 1 ( + 1) • ( + 1)! , so that >i 1 ! 1 i • i! = 1 + 1 i 1 (i + 1)! .
Recalling from Proposition 4.3 that

P(D k) = 2 e i k >i 1 ! , point (i) follows readily.
The proof of (ii) is somewhat technical so we only outline it here and refer the reader to Section A.1 of the Appendix for the detailed calculations.

Consider the function

∆ n (z) = i 0 P(D i) -P(D n i) z i .
With this function, (ii) can be re-expressed as

∆ (k) n (0) = ε n k + 1 for all k K n = o( √ n),
where ∆ (k) n denotes the k-th derivative of ∆ n . But ∆ n can be expressed in terms of the generating functions of D and D n , namely as

∆ n (z) = 1 + 1 z -1 G D (z) -G Dn (z) .
The expressions of G D and G Dn obtained in Propositions 4.1 and 4.3 thus make it straightforward to obtain a power series expansion of ∆ n at z = 1, and this expansion can be used to bound ∆ (k) n (0) and conclude the proof. Finally, (iii) is a direct consequence of (i) and (ii).

Largest degree

The aim of this section is to prove Theorem 1.2 concerning the largest degree of F n , i.e. to show that

D max n = log n log log n + 1 + o p (1) log n log log log n (log log n) 2 ,
where o p (1) denotes a sequence of random variables that goes to 0 in probability and

D max n = max v D (v) n .
Our proof is a standard application of the first and second moment method and it implies that, asymptotically, D max n behaves like the maximum of n independent random variables distributed as D. As is typically the case with this method, the main difficulty -and therefore the bulk of the proof -consists in bounding the asymptotic dependency between two fixed vertices of F n .

Because the first and second moment method part of our reasoning will also be used in the proof of Theorem 1.3 concerning the size of the largest tree, we isolate it as a lemma, whose proof we recall for the sake of completeness. Lemma 4.5. For all integers n, let (X (1) n , . . . , X (n) n ) be a vector of exchangeable random variables and

X max n = max X (i) n : i = 1, . . . , n .
Write p n (k) for P(X (i) n k), and suppose that there exists a sequence (m n ) and a constant β such that, for all ε > 0, as n → ∞,

(i) np n ((β + ε)m n ) → 0. (ii) np n ((β -ε)m n ) → +∞. (iii) P X (1) n (β -ε)m n , X (2) n (β -ε)m n ∼ p n ((β -ε)m n ) 2 .
Then for all ε > 0,

P X max n (β + ε) m n → 0 and P X max n (β -ε)m n → 1,
which can also be written

X max n = β + o p (1) m n ,
where o p (1) denotes a sequence of random variables that goes to 0 in probability.

Proof. First,

P X max n (β + ε)m n = P n i=1 X (i) n (β + ε)m n np n (β + ε)m n ,
which goes to zero by (i). Now, denote by

Z n = n i=1 1 {X (i) n (β-ε)mn}
the number of variables X (i) n that are greater than or equal to (β -ε)m n . Using the Cauchy-Schwartz inequality, we have

E(Z n ) 2 = E Z n 1 {Zn>0} 2 E(Z 2 n )P(Z n > 0) so P X max n (β -ε)m n = P(Z n > 0) E(Z n ) 2 E(Z 2 n ) .
Moreover,

E Z 2 n = np n (β -ε)m n + n(n -1)P X (1) n (β -ε)m n , X (2) n (β -ε)m n ,
and so, by (ii) and (iii),

E(Z n ) 2 /E(Z 2 n ) → 1 as n → ∞.
Remark 4.6. Note that under assumption (ii) of this lemma, for any ε > 0, letting

n → ∞ in E(Z n ) 2 /E(Z 2 n ) 1 shows that p n ((β -ε)m n ) 2 P X (1) n (β -ε)m n , X (2) n (β -ε)m n (1 + o(1)).
Therefore, to prove (iii) it suffices to show (iii') P X (1) n

(β -ε)m n , X (2) n (β -ε)m n p n ((β -ε)m n ) 2 (1 + o(1)).
We now turn to the proof of Theorem 1.2.

Proof of Theorem 1.2. Instead of proving the theorem directly for the degree random variables (D (1) n , . . . , D (n) n ), we prove it for the out-degrees, which we denote by ( D [START_REF]The On-Line Encyclopedia of Integer Sequences[END_REF] n , . . . , D(n) n ) and whose maximum has the same asymptotic behavior as D max n . The point in doing this is that the tails of the out-degrees are less correlated than those of the variables D (v) n , making it easier to study their maximum by the first and second moment method.

Remember from Section 4.1 that, in the UA construction,

D (v) n = I Bv + n =Bv+1 X (v) ,
where B v is the step at which vertex v was added, X (v) is the indicator of "the -th vertex is linked to vertex v", and I is the indicator of "the -th vertex is linked to a previously added vertex". With this notation, let

D(v) n = n =Bv+1 X (v) ,
denote the out-degree of vertex v, and set Dmax Using Proposition 4.4 and Stirling's formula, we see that for any

k n = o( √ n), log P(D n k n ) = -k n log k n + k n + O(log k n ) .
Writing Dn to refer to the common distribution of the variables D(v) n , since

P D n k n + 1 P Dn k n P D n k n ,
we also have

log P Dn k n = -k n log k n + k n + O(log k n ) .
In particular, for k n = (log n)/(log log n) + γ m n with

m n = log n log log log n (log log n) 2 , this gives log P Dn k n = -log n -γ -1 log n log log log n log log n + O log n log log n (1)
As a result, for all ε > 0,

(i) n P Dn - log n log log n (1 + ε)m n → 0. (ii) n P Dn - log n log log n (1 -ε)m n → +∞.
Thus, to apply Lemma 4.5 and finish the proof it suffices to show that

P D(1) n k n , D(2) n k n ∼ P Dn k n 2 whenever k n = (log n)/(log log n) + (1 -ε)m n .
More precisely, using Remark 4.6 it is sufficient to show that 2) , b 2 + 1 n) are independent Bernoulli variables with parameter 1/(n -1). By further conditioning on the variables X (1) , the independence of (X 2) , b 2 + 1 n) still holds but their distribution is changed. Indeed, choose (x , = b 1 ) ∈ {0, 1} n-1 and consider the event

P D(1) n k n , D(2) n k n P Dn k n 2 + o P Dn k n 2 . First let us fix b 1 = b 2 ∈ {1, . . . , n}. Conditional on {B 1 = b 1 , B 2 = b 2 }, recall that the variables (X (
A := B 1 = b 1 , B 2 = b 2 , ∀ = b 1 , X (1) = x .
Then by construction, for all / ∈ {b 1 , b 2 }, we have

P X (2) = 1 A =    0 if x = 1 1 n-2 if x = 0.
Consequently X (2) is always stochastically dominated by a Bernoulli( 1 n-2 ) random variable, and so we bound the distribution of D( 2)

n = >b 2 X (2) conditional on A by D(2) n A d Binomial n -b 2 , 1 n -2 .
To get a bound on the distribution of D(2) n conditional on D(1) n = i for some i, first note that summing over all configurations b 1 , b 2 , (x , = b 1 ) such that >b

1 x = i gives D(2) n B 1 = b 1 , B 2 = b 2 , D(1) n = i d Binomial n -b 2 , 1 n -2 .
Let us now write for conciseness

L 1 = n -B 1 and L 2 = n -B 2 . Note that L 2 is not independent of { D(1) n = i} because they are linked by L 1 . Indeed, L 1 is positively correlated to D(1)
n and we always have

L 2 = L 1 . Nevertheless, since conditional on L 1 , L 2 is independent of D(1)
n and uniform on {0, . . . , n -1} \ L 1 , we have the following stochastic ordering:

L 2 B 1 = b 1 , D(1) n = i d L 2 ,
where L 2 is uniformly distributed on {1, . . . , n -1}. Summing over b 1 and b 2 , we thus get D( 2)

n D(1) n = i d Binomial L 2 , 1 n -2 .
Let us define a random variable

M n ∼ Bin L 2 , 1 n-2 .
As the previous bound is uniform in i, we have

P D(2) n k n D(1) n k n P(M n k n ).
To conclude, it is sufficient to show that P(M n k n ) ∼ P Dn k n since this implies

P D(1) n k n , D(2) n k n P Dn k n P(M n k n ) ∼ P Dn k n 2 .
For this, define on the same probability space as the variables L 2 and M n the variable

L 2 := L 2 1 {L2 n-2} .
L 2 is then uniformly distributed on {0, . . . , n -2}, and we have the equality in distribution

M n 1 {L2 n-2} d = Dn-1 ∼ Binomial L 2 , 1 n -2 .
As the two variables M n and M n 1 {L2 n-2} differ on an event of probability no greater than 1/(n -1), we have

P(M n k n ) = P Dn-1 k n + O 1 n ,
and finally (1) with γ = (1 -ε) allows us to conclude that this expression is indeed equivalent to P Dn k n .

Tree sizes

In this section, we study the size of the trees composing the Moran forest. Section 5.2 is concerned with the typical size of these trees, while Section 5.3 focuses on the asymptotics of the size of the largest tree. But before going any further we need to introduce a process that will play a central role throughout the rest of this paper.

A discrete-time Yule process

Let Υ n = (Υ n ( ), 0) be the pure birth Markov chain defined by Υ n (0) = 1 and the following transition probabilities:

P Υ n ( + 1) = j Υ n ( ) = i =    i n-1 if j = i + 1 1 -i n-1 if j = i,
and stopped when reaching n.

The reason why this process will play an important role when studying the trees of F n is the following: let T (v) n denote the tree containing v, and T(v) n the subtree descending from v in the UA construction -that is, letting m(v) denote the mother of v and T (v) n \ {vm(v)} the forest obtained by removing the edge between v and m(v) from T (v) n (if that edge existed), T(v) n is the tree of

T (v) n \{vm(v)} containing v.
Recalling that L v denotes the number of steps after vertex v was added in the UA construction and letting T

(v) n = | T(v) n | be the size of T(v) n , we have T (v) n d = Υ n (L v ) ,
where Υ n is independent of L v . In particular, the size of a tree created at step n -h of the UA construction is distributed as Υ n (h).

In the rest of this section, we list a few basic properties of Υ n that will be used in subsequent proofs.

Lemma 5.1. For all 0 n -1,

E(Υ n ( )) = 1 + 1 n -1 .
Proof. For 0 < n -1, we have Υ n ( ) < n almost surely, therefore we can write

E Υ n ( + 1) Υ n ( ) = Υ n ( ) n -1 Υ n ( ) + 1 + 1 - Υ n ( ) n -1 Υ n ( ) = Υ n ( ) 1 + 1 n -1 ,
and the result follows by induction.

We now compare the discrete-time process Υ n to the Yule process. By Yule process, we refer to the continuous-time Markov chain (Y (t), t 0) that jumps from i to i + 1 at rate i (see e.g. [START_REF] Ross | Stochastic Processes[END_REF], Section 5.3).

Lemma 5.2. As n → ∞,

Υ n ( tn ), t 0 =⇒ Y (t), t 0 ,

where " =⇒ " denotes convergence in distribution in the Skorokhod space [START_REF] Billingsley | Convergence of Probability Measures[END_REF], and (Y (t), t 0) is a Yule process.

Proof. Since both processes only have increments of +1, it suffices to prove that the sequence of jump times of (Υ n ( tn ), t 0) converges in distribution to that of the Yule process. For 1 i n, let

t n (i) = inf 0 : Υ n ( ) = i
be the jump times of the chain Υ n . By the strong Markov property, the variables (t n (i + 1) -t n (i), 1 i n -1) are independent, and t n (i + 1) -t n (i) ∼ Geometric( i n-1 ). Therefore,

1 n t n (i + 1) -t n (i) , 1 i n -1 d ----→ n→∞ (E(i), i 1),
where the variables (E(i), i 1) are independent and E(i) ∼ Exponential(i). This concludes the proof.

Lemma 5.3. For all integers 0 k n -1,

P Y -k+1 n-1 > k P(Υ n ( ) > k) P Y λ n (k) n-1 > k ,
where

λ n (k) = - n -1 k log 1 - k n -1 .
Proof. Let us start with the upper bound, and write λ := λ n (k) for simplicity. Note that, for all t 0 and i 1,

P Y t + λ n-1 = i Y (t) = i = e -iλ n-1 ,
and that we have chosen λ such that if i k then

e -iλ n-1 1 - i n -1 = P Υ n ( + 1) = i Υ n ( ) = i .
Thus, until it reaches k +1 individuals, the process Υ n is dominated by the Markov chain (Y ( λ n-1 ), 0 n -1). This shows that

P(Υ n ( ) > k) P Y λ n-1 > k ,
proving the second inequality of the lemma.

To prove the first inequality, we couple Υ n with a "censored" Yule process Y c . Intuitively, this censoring consists in ignoring births that occur less than 1/(n -1) unit of time after another birth.

Formally, we define Y c by specifying the sequence t 0 = 0 < t 1 < t 2 < . . . of times corresponding to births in the population. Let (E i , i 1) be an independent sequence of exponential random variables where E i ∼ Exponential(i). Set t 0 = 0 and, for each i 1,

t i := E 1 + i j=2 1 n -1 + E j = i -1 n -1 + i j=1 E j . (2)
We now define, for all t 0,

Y c (t) := 1 + i 1 1 {t i t} = i 1 i 1 {t i-1 t<t i } .
The censoring of the Yule process after birth events implies that for any time t 0, the random variable

Y c (t + 1 n-1 ) -Y c (t) takes values in {0, 1}. Furthermore, for any i ∈ N, P Y c (t + 1 n-1 ) = i + 1 Y c (t) = i 1 -e -i n-1 i n -1 .
Therefore, we can couple (Υ n ( ), 0 n -1) and (Y c (t), t 0) in such a way that, for all 0 n -1,

Y c n-1 Υ n ( ).
Now, by construction, the sequence (t i -i-1 n-1 , i 1) has the distribution of the sequence of jump times of a Yule process. Therefore,

P(Υ n ( ) > k) P Y c n-1 > k = P t k n-1 = P t k -k-1 n-1 -k+1 n-1 = P Y -k+1 n-1 > k ,
which yields the lower bound of the lemma.

We now use the previous lemma to obtain the following result, which will be used to derive asymptotics for the tail probability of the size of a tree in the Moran forest.

Proposition 5.4. Let L be a uniform random variable on {0, . . . , n -1}, independent of the process Υ n . Then for any sequence of integers k n → ∞ with

k n = o( √ n), P(Υ n (L) > k n ) ∼ e k n (1 -e -1 ) kn+1 .
Proof. Using the upper bound in Lemma 5.3, we have

P(Υ n (L) > k n ) 1 n n-1 =0 P Y λ n (k) n-1 > k n = n -1 n 1 0 P Y λ n (k n ) x(n-1) n-1 > k n dx + 1 n P(Y (λ n (k n )) > k n ) 1 0 P(Y (λ n (k n )x) > k n ) dx + 1 n (1 -e -λn(kn) ) kn = 1 0
1 -e -λn(kn)x kn dx + 1 n (1 -e -λn(kn) ) kn .

Now recall that λ n (k n ) = -n-1 kn log 1-kn n-1 = 1+O( kn n ), so uniformly in x ∈ [0, 1], e -λn(kn)x = e -x + O k n n . Since k n = o( √ n), we have k n /n = o(1/k n ) and thus Lemma A.1 from the Ap- pendix gives 1 0 1 -e -λn(kn)x kn dx ∼ e k n (1 -e -1 ) kn+1 .
Elementary calculations show that when

k n = o( √ n), we also have 1 n (1 -e -λn(kn) ) kn ∼ 1 n (1 -e -1 ) kn = o (1 -e -1 ) kn k n .
It remains to examine the lower bound in Lemma 5.3. As above, we get an integral

P(Υ n (L) > k n ) 1 n n-1 =0 P Y -kn+1 n-1 > k n n -1 n 1 0 P Y x(n-1) -kn n-1 > k n dx n -1 n 1 0 P Y x -kn n-1 > k n dx. Since P Y x -kn n-1 > k n = 1 -exp(-x + kn n-1 ) kn = 1 -e -x + O(k n /n) kn ,
using Lemma A.1 again, we get

P(Υ n (L) > k n ) n -1 n 1 0 P Y x -kn n-1 > k n dx ∼ e k n (1 -e -1 ) kn+1 ,
which completes the proof.

Size of some random trees

In this section, we study the size of some typical trees of F n . In particular, we study the asymptotics of the size T (1) n of the tree containing vertex 1 and of the size T U n of a tree sampled uniformly at random among the trees composing F n . Our main result is the following theorem. (i) Let T U n be the size of a uniform tree of F n . Then,

P T U n = k ----→ n→∞ 2 1 0 xe -x (1 -e -x ) k-1 dx, that is, T U n d -→ T U where T U ∼ Geometric(e -X )
, and X ∼ 2xdx on [0

(ii) Let T (1) n be the size of the tree containing vertex 1 in F n . Then,

P T (1) n = k ----→ n→∞ k 1 0 xe -x (1 -e -x ) k-1 dx,
that is, T (1) n converges in distribution to the size-biasing of T U .

Remark 5.6. Note that even though the limit distribution of T (1) n is the size-biased limit distribution of T U n , for finite n the distribution of T (1) n is not the size-biased distribution of T U n . Indeed, note that

P T (1) n = k = E T ∈Fn 1 {|T |=k} 1 {1∈T } = k n E T ∈Fn 1 {|T |=k} , while P T U n = k = E 1 N n T ∈Fn 1 {|T |=k} ,
where, as in Section 3, N n denotes the number of trees in F n . However, these computations are enough to show that, in the limit, the size-biasing holds: indeed, note that n/N n → 2 in probability by Proposition 3.1. Furthermore, using for instance Hoeffding's inequality [START_REF] Hoeffding | Probability inequalities for sums of bounded random variables[END_REF] to control the deviation of N n from its mean, it is easy to show that n/N n → 2 in L 1 as well, so that

P T (1) n = k -k 2 P T U n = k k 2 E n N n -2 → 0.
This shows that points (i) and (ii) of Theorem 5.5 are equivalent.

We start by giving the distribution of T (1) n in terms of the process Υ n defined in Section 5.1. For this, we first need to introduce some notation. Let T (v) n be the tree containing vertex v in F n . We denote by H (v) n the number of steps after the root of T (v) n was added in the UA construction. Recalling the notation from Section 2.2, where σ -1 (v) ∈ {1, . . . , n} denotes the step of the UA construction at which vertex v was added, we thus have

H (v) n = n -min σ -1 (u) : u ∈ T (v) n .
Proposition 5.7. Let T (1) n be the size of the tree containing vertex 1 in F n , and denote by H (1) n the number of steps after the root of that tree was added in the UA construction. Then, (i) For 0 h n -1, P(H (1)

n = h) = h n(n -1) 1 + 1 n -1 h .
(ii) Conditional on {H (1) n = h}, T (1) n is distributed as the size-biasing of Υ n (h).

Remark 5.8. The size-biasing of Υ n (h) can be easily represented as follows. Consider the Markov chain Υ * n = (Υ * n ( ), 0 n -1) defined by Υ * n (0) = 1 and the following transition probabilities:

P Υ * n ( + 1) = j Υ * n ( ) = i =    i+1 n if j = i + 1 1 -i+1 n if j = i.
A straightforward induction on shows that Υ * n ( ) is distributed as the size-biasing of Υ n ( ).

Proof. First, note that H (1) n = h if and only if a new tree is created at step n -h, and vertex 1 belongs to this tree. Now, the probability that a new tree is created at step n -h is h n-1 , and the size of this tree is then distributed as Υ n (h). Moreover, at the end of the UA construction the labels are assigned to the vertices uniformly. As a result, conditional on a tree having size i, the probability that it contains vertex 1 is i/n. We thus have P H (1) n = h, T (1)

n = i = h n -1 • i n P(Υ n (h) = i).
Summing over i and using Lemma 5.1 yields

P H (1) n = h = h n(n -1) 1 + 1 n -1 h .
Finally, P T (1) n = i H (1)

n = h = i P Υ n (h) = i 1 + 1 n -1 -h
, which concludes the proof.

We can now turn to the proof of our main result.

Proof of Theorem 5.5. By Remark 5.8, it is sufficient to prove (ii). Now from Proposition 5.7, we can write P T (1) n

= k = 1 n n-1 h=0 h n -1 E Υ n (h)1 {Υn(h)=k} = k n n-1 h=0 h n -1 P(Υ n (h) = k).
Therefore using Lemma 5.2, we get

k n n-1 h=0 h n -1 P(Υ n (h) = k) ----→ n→∞ k 1 0 xP(Y (x) = k)dx,
and recalling the well-known fact that Y (x) has a Geometric(e -x ) distribution (see for instance Section 5.3 in [START_REF] Ross | Stochastic Processes[END_REF]) concludes the proof.

Remark 5.9. If H U n denotes the number of steps in the UA construction after the root of a uniformly chosen tree was added, one could give an alternative proof of Theorem 5.5 by showing that H U n /n → X, and then using Lemma 5.2.

Size of the largest tree

The goal of this section is to derive asymptotics for T max n := max v T (v) n , the size of the largest tree in the Moran forest on n vertices, when n → ∞. Namely, we show that

T max n = α log n -(1 + o p (1)) log log n ,
where α = (1 -log(e -1)) -1 . Similarly to Theorem 1.2 concerning the largest degree, this corresponds to the maximum of n/2 independent T U n -distributed trees. Again the key element to the proof is to control the asymptotic independence of two distinct trees of F n .

As in Section 5.1, for any vertex v let us define T(v) n ⊂ T (v) n as the subtree descending from v in the UA construction. For our purpose, it will be sufficient to study the size T (v)

n := | T(v)
n | of those subtrees instead of that of the trees T (v) n . Indeed, observe that

T max n = max v T (v)
n , so that applying Lemma 4.5 with m n = α log log n and β = -1 to the exchangeable variables ( T [START_REF]The On-Line Encyclopedia of Integer Sequences[END_REF] n -α log n, . . . , T (n) n -α log n) will prove the theorem. Again, we omit the superscript and denote by Tn a random variable with distribution equal to that of T [START_REF]The On-Line Encyclopedia of Integer Sequences[END_REF] n . For the rest of the section, we thus study the tail probabilities of the variable Tn . Recall from the UA construction that the number L of steps after a fixed vertex was added is uniformly distributed on {0, . . . , n -1}, and from Section 5.1 that, conditional on {L = },

Tn d = Υ n ( ) .
As a consequence, applying directly Proposition 5.4 yields that for any sequence of integers

k n → ∞ with k n = o( √ n), P Tn > k n ∼ e k n (1 -e -1 ) kn+1 . ( 3
)
tree T (2) n in the UA construction behaves as a modified Υ n process, which we essentially bound from above by Υ n-i . Therefore, T (2) n can be compared with an independent variable with distribution Tn-i . Finally, we show that

i kn P T (1) n = i P Tn-i k n R 2 n + o(R 2 n ),
thereby proving (5) and concluding the proof of Theorem 1.3.

6 Concluding comments

Aldous's construction

The UA construction described in Section 2.2 is reminiscent of Aldous's construction [3, Algorithm 2] of a uniform rooted labeled tree as a function of n uniform random variables on {1, . . . , n} -an algorithm arguably simpler than the variant of Joyal's bijection used in the proof of Theorem 1.1. However, we could not find a simple way to couple both procedures so that the forest obtained from the UA construction coincides with the one obtained by removing decreasing edges in Aldous's uniform tree.

A local limit

The construction of F n from a uniform random tree in Section 3.2 gives us a way to build an infinite forest as a limiting object for the Moran forest, in a weak sense. Let us start by describing the local weak limit of the uniform (rooted) random tree. Recall that the local weak limit of a sequence of random graph G n is a (possibly infinite) random pointed graph (G, u G ) such that for each finite radius r 1, the r-neighborhood of a uniformly chosen vertex u n ∈ G n converges in distribution to the ball of radius r around u G in G. Consider the following infinite random tree:

• Start from an infinite spine of vertices u 0 , u 1 , u 2 , . . . , with edges (u i ← u i+1 ) between subsequent vertices, directed toward the focal vertex u 0 .

• Let independent Galton-Watson trees with Poisson(1) offspring distribution start from each u i , for i 0, with edges directed from mothers to daughters.

The graph T ∞ described above is the local weak limit of the random rooted uniform tree on n labeled vertices [START_REF] Grimmett | Random labelled trees and their branching networks[END_REF]. The root is informally placed at the end of the infinite spine.

In order to translate this result to the Moran forest, we need to remove the decreasing edges of T ∞ . To do so, we equip each vertex v with an independent uniform variable V v on [0, 1], that corresponds to the limiting renormalized label of v. The graph obtained by removing from T ∞ each edge uv such that V u > V v can be understood as the local weak limit of the Moran forest.

This construction can be used to derive some limiting results about the local structure of the Moran forest. We can for instance recover the limiting degree of a uniformly chosen vertex: it is clear that the focal vertex u 0 in the construction above has degree

D d = Ber(V u 0 ) + Poisson(1 -V u 0 ),
as described in Proposition 4.3. However, global results such as the size of the largest tree or the largest degree cannot be easily derived from this local weak limit.

Remark 6.1.

(i) By definition, the local weak limit should be a.s. connected. Only the random tree that contains u 0 corresponds to the actual local weak limit of the Moran forest. It seems difficult to give meaning to the other trees that are obtained in this procedure. They are connected to the tree containing the focal vertex through the labels (V v ). This indicates that the tree that is adjacent to the focal tree is not simply an independent "local limit tree" for another uniformly chosen vertex.

(ii) Note that the local weak limit can be obtained in a simpler, more direct way. Indeed, Theorem 5.5 gives us the limiting size of the tree containing a uniformly chosen vertex, and we know from the UA construction that, conditional on the number of trees and their sizes, trees in the Moran forest are uniform attachment trees.

Possible extension

An important property of the Moran model is that it is an exchangeable population model: its distribution is invariant under re-labeling of the vertices. General exchangeable population models are known as Cannings models, and just as for the Moran model it is possible to associate a forest-valued process to any Cannings model.

A Cannings model is defined from an exchangeable vector (ξ(1), . . . , ξ(n)) of nonnegative integers verifying ξ(1) + • • • + ξ(n) = n. This vector encodes the offspring distribution of a population labeled by {1, . . . , n}. If ξ(v) = 0, we say that individual v is dead. Otherwise, it has ξ(v) -1 children. It is clear that the number of dead individuals is equal to the total number of children in the population. We can thus assign a mother to each dead individual, in such a way that the number of children of each live individual is ξ(v) -1.

Starting from any directed graph, we can now define a transition as follows:

1. Draw a vector distributed as (ξ(1), . . . , ξ(n)).

2. Disconnect each dead vertex from all its neighbors.

3. Assign a mother to each dead vertex, uniformly among all possibilities. For each dead vertex v, draw an edge from its mother to v.

This defines a Markov chain on the set of rooted forests. It is not hard to see that, if (ξ(1), . . . , ξ(n)) is the uniform permutation of the vector (2, 0, 1, . . . , 1), we recover the Markov chain leading to the Moran forest described in Section 1.1.

Studying these general exchangeable forest processes is not the aim of the current work. In particular, the techniques we used here rely heavily on the construction of the Moran forest described in Section 2.2, which cannot be easily adapted to more general exchangeable forest processes. Since P(D k)

A Appendix

2/e (k+1)! , we have to show that for any given sequence

K n = o( √ n), ∆ (k) n (0) = ε n k + 1
for some ε n → 0 and all k K n . Now, since for any non-negative integer-valued random variable X,

i 0 P(X i) z i = z E z X -1 z -1 ,
we can express ∆ n in terms of the generating functions of D and D n , that is,

∆ n (z) = 1 + 1 z -1 G D (z) -G Dn (z) .
Moreover, we know from Proposition 4.3 that

G D (z) = 2 e z-1 -1 z -1 -1 = 2 i 0 (z -1) i (i + 1)! -1
and from Proposition 4.1 that

G Dn (z) = 2 1 - 1 n 1 + z-1 n-1 n -1 z -1 -1 = 2 1 - 1 n n-1 i=0 n i + 1 1 n -1 i+1 (z -1) i -1 = 2 n-1 i=0 i =1 n - n -1 (z -1) i (i + 1)! -1 ,
where the empty product is 1. Therefore, where we used the change of variable y = k n (e 1-x -1)(e -1) -1 , and defined the map g n as g n (y) = e e -1

f n 1 -log 1 + y k n (e -1) .

Since (1 -y kn + g n (y)) kn exp(-y + e e-1 k n sup x f n (x)), it follows from dominated convergence that

Figure 1 :

 1 Figure 1: Example of four successive transitions of the Markov chain. Starting from the left-most graph, transitions are represented by dashed arrows decorated with the pair (u, v) that is chosen uniformly at each step.

I 1 n- 1 D

 11 , where I ∼ Ber -Asymptotic degree Ber(1 -U ) + Poisson(U ), distribution where U ∼ Unif([0, 1])

Figure 2 :

 2 Figure2: Illustration of the backward construction. Each vertex corresponds to a vertical line. A pair (V t , W t ) is represented by an arrow V t → W t . The line representing a vertex is solid black when that vertex is active, and dashed grey when it is inactive. Arrows pointing to inactive vertices are represented in dashed grey because they have no impact on the state of the graph at the focal time: their effect has been erased by subsequent arrows.

Proposition 2 . 1 .

 21 The random forest obtained by relabeling the vertices of F * n according to a uniform permutation of {1, . . . , n} is distributed as the Moran forest.

Proposition 4 . 3 .

 43 The degree D n of a fixed vertex of F n converges in distribution to the variable D satisfying:

Proposition 4 . 4 .

 44 Let D n be the degree of a fixed vertex of F n and let D have the asymptotic distribution of D n . (i) For all k 1,

n

  = max{ D(v)n : v = 1, . . . , n}. Since Dmax n and D max n differ by at most 1, for any m n → +∞, D max n -Dmax n = o p (m n ) , i.e. (D max n -Dmax n )/m n goes to 0 in probability. Thus, to prove the theorem we apply Lemma 4.5 to the variables D(1) n -log n log log n , . . . , D(n) n -log n log log n , with m n = (log n)(log log log n)/(log log n) 2 and β = 1.

. 1 4

 14 Proof of point (ii) of Proposition 4.We want to prove that, for allK n = o( √ n), there exists ε n = o(1) such that, for all k K n , |P(D n k) -P(D k)| ε n P(D k) .Doing this directly from the expressions of D n and D involves unappealing calculations. To somewhat circumvent this, we make use of the simple expressions of the probability generating functions G Dn and G D . For this, let∆ n (z) := i 0 P(D i) -P(D n i) z i , so that the k-th derivative of ∆ n evaluated at z = 0 is ∆ (k) n (0) = k! P(D k) -P(D n k) .

GProof. Let us compute 1 0( 1

 11 D (z) -G Dn (z) = i 0 A(n, i) (z -1) i (i + 1)! , -e -x + f n (x)) kn (1 -e -1 ) kn k n dx =

1 0( 1 0 eP 1 = 1 n

 11011 -e -x + f n (x)) kn (1 -e -1 ) kn k n dx ----→ n→∞ ∞ -y (e -1) dy = e -1,concluding the proof.Lemma A.2. Let T (v)n denote the size of the subtree descending from v in the UA construction of F n . Then, for α = -1/ log(1 -e -1 ) and any ε > 0, lettingk n = α(log n -(1 + ε) log log n) and R n = P Tn k n , Let us denote by A n := { T(2) n ⊂ T(1) n } { T(1) n ⊂ T(2)n } the event that one of the vertices 1 and 2 is an ancestor of the other. We start by showing thatP A n , T (1) n k n , T (2) n k n = o(R 2 n n = i P Tn = i .Let us call the height of a vertex the number of steps after it was added in the UA construction. Conditional on { T (1) n = i} and on the heights of the vertices of T(1)n being 1 > . . . > i , the height L 2 of vertex 2 is uniformly distributed on {0, . . . n -1} \ { 1 }. Moreover, in order to have { T(2) n ⊂ T(1) n , T (2) n k n } ,the height of vertex 2 must belong to { 2 , . . . , i-(kn-1) }, which happens with probability i-kn n-1 . Therefore, P A n , T (1) Tn = i i -k n n --1 i>kn P Tn i .

  3, respectively.

	Theorem 1.2. Let D max n	denote the largest degree of F n . Then,
	D max n	=	log n log log n	+ 1 + o p (1)	log n log log log n (log log n)

2

, where o p (1) denotes a sequence of random variables that goes to 0 in probability. Theorem 1.3. Let T max n denote the size of the largest tree of F n . Then, T max n = α log n -(1 + o p (1)) log log n , where α = (1 -log(e -1)) -1 ≈ 2.18019.

2 Sampling of the stationary distribution 2.1 Backward construction

Consider an i.i.d. sequence ((V t , W t ), t ∈ Z), where (V t , W t ) is uniformly distributed on the set of ordered pairs of distinct elements of {1, . . . , n}. These variables are meant to encode the transitions of the chain: W t represents the vertex that is disconnected at step t, and V t the vertex to which W t is then connected. We now explain how to construct a chain (F n (t), t ∈ Z) of forests by looking at the sequence ((V t , W t ), t ∈ Z) backwards in time.

Fix a focal time t ∈ Z. For each vertex w, let us denote by τ t (w) := max{s t : W s = w} the last time before t that w was chosen to be disconnected, and define m t (w) := V τt(w)

Acknowledgments

We thank Amaury Lambert for initiating the discussion that led us to consider this model and for comments on the first version of this manuscript, and Justin Salez for interesting discussions on the link between the uniform random rooted tree, its local limit and the Moran forest. We are also grateful to the editor for pointing out the similarity between the UA construction and Aldous's algorithm, and to two anonymous referees for helpful comments, including the possibility of adapting the definition of the Moran forest to Cannings models. This work was for the most part done while JJD worked in CIRB and LPSM.

Note that if k n is not integer-valued, then P Tn > k n = P Tn > k n ∼ e k n (1 -e -1 ) kn +1 , which is not necessarily equivalent to e kn (1 -e -1 ) kn+1 since k n -k n may oscillate between 0 and 1. However, we do have P( Tn > k n ) = Θ((1 -e -1 ) kn /k n ), where the Bachmann-Landau notation u n = Θ(v n ) indicates that there exist two positive constants c and C such that c v n u n Cv n for n large enough. This approximation is sufficient for our purpose.

We may now prove Theorem 1.3 using the first and second moment method that we already used for the largest degree.

Proof of Theorem 1.3. We apply Lemma 4.5 to the exchangeable variables (X (1) n , . . . ,

with m n = α log log n and β = -1. The first two points of the lemma are readily checked, since (3) tells us that for

and any γ > 0, we have for

Thus, for all ε > 0,

All that remains to check is the third point of the lemma. From now on, we fix k n = α(log n -(1 + ε) log log n) for some ε > 0, and for the sake of readability, we set R n := P( Tn k n ). With this notation, given Remark 4.6 we need to show

Since this is rather technical, we defer the complete proof to Lemma A.2 in Appendix A.2, and only outline the main ideas of the proof here. As in the study of the largest degree, we prove this by showing that the law of T (2)

n k n } is close to its unconditional law. We first prove that

where

n } is the event that one of the two vertices 1 and 2 is an ancestor of the other in the UA construction. We then show

where A c n denotes the complement of A n . This is done by showing that, conditional on { T (1) n = i}, on the event A c n the process counting the number of vertices of the where

Using that A(n, 0) = A(n, 1) = 0 and rearranging a bit, we obtain the following expansion of ∆ n at z = 1:

.

For i J n , we have

Combining these two upper bounds, we get

.

. This concludes the proof.

Note that although we have been quite crude in that we have used the triangle inequality on an alternating series, a more careful analysis would show that the o( √ n) requirement on K n is in fact optimal.

A.2 Technical lemmas used in the proof of Theorem 1.3

Lemma A.1. For any sequence k n → ∞ and any sequence of measurable maps

To show that this is small enough, we let K n := k n + α(log n) δ with 0 < δ < min(1, ε) and K n := 2α log n, and crudely bound i>kn

Now let us show that these three terms are negligible compared to nR 2 n . Recalling from (4) that R n = Θ (log n) ε n , we have nR 2 n = Θ((log n) 2ε /n) and therefore

As a result, ( 6) is proven and it remains to show that

where A c n denotes the complement of A n . We now fix n 1, i k n , and a finite sequence n -1 1 > . . . > i 0. Let us write B for the event that T(1) n contains exactly the vertices with heights 1 > . . . > i . Conditional on B, let us examine the distribution of T( 2) n . Recall that the height L 2 of vertex 2 is uniformly distributed on {0, . . . n -1} \ { 1 }. In the UA construction, define T as the tree obtained by starting from a root arrived at height L 2 and allowing the attachment of a vertex with height to T only if / ∈ { 1 , . . . i }. Then, on the event A c n , this tree must coincide with T (2) n , and so

From the UA construction, for any / ∈ { 1 , . . . , i }, conditional on B ∩ {L 2 = }, we can describe |T| using the process ( Υ (m), 0 m ) defined by

• For all 0 < m , Υ (m) -Υ (m -1) ∈ {0, 1} and, conditional on

where

n with height greater than -m in the UA construction.

With this definition, for any / ∈ { 1 , . . . , i }, conditional on B ∩ {L 2 = }, we have by construction |T| d = Υ ( ). Now, note that the probability of increasing is always bounded by j/(n -1 -i). Therefore, Υ can be coupled with Υ n-i in such a way that, for all 0 m < n -i,

For n -i, we use the crude bound P( Υ ( ) k n ) E( Υ ( ))/k n . Using the same reasoning as in Lemma 5.1, we get

) n-i-1 e .

We thus have

Since this bound depends on the set { 1 , . . . , i } only via its cardinality i, one can integrate with respect to the distribution of T (1) n to get

Υ n-i ( ), the expression (7) -and therefore (8) -is nondecreasing in i, and we have

for any sequence K n k n . Letting K n := α(log n) 1+ε/2 , we then show that ( 9) is asymptotically no greater than R 2 n , and that (10) is negligible compared to R 2 n . Indeed, ( 9) is bounded from above by

Now note that e Kn kn(n-1) = O( (log n) ε/2 n ) = o(R n ), and that since n -K n ∼ n, we have

. Therefore, using (3) we get P Tn-Kn k n ∼ R n . Finally, up to a multiplicative constant, (10) is bounded from above by

Putting everything together, we have proved that

), which concludes the proof.


M Žitnik

A Mihelič

K Bučar

M Hrast

Ž Barba

Š Krušič

P Rebernik Ribič

J Urbančič

B Ressel

M Stupar

L Poletto

M Coreno

D Gauthier

G De Ninno

Observation of short-lived laser-dressed quantum states in the frequency plane

We present a method for measuring a complete frequency map of laser-dressed states with femtosecond lifetimes. It is based on collecting decay products as a function of the frequency of the excitation pulse and its delay with respect to the linearly chirped laser pulse, centered at the resonant transition frequency. The method has been tested on the case of laser-coupled 2s2p 1 P o and 2p 2 1 S e autoionizing resonances in He and is applicable to other quantum systems with short-lived states. When the laser coupling effects are known, the excitation pulse properties can be extracted from the map.

I. INTRODUCTION

A transient quantum state can be modified in a controlled way by coupling it to one or several of the neighboring states with a laser. Under the influence of a strong electromagnetic field, the states of, e.g., an atom, a molecule, or a crystal, are "dressed" by the field. The properties of these states depend on the field intensity, frequency, and polarization [1]. The physics of a pair of states coupled by a laser is well known [START_REF] Cohen-Tannoudji | The Autler-Townes Effect Revisited[END_REF], and leads to the Autler-Townes doublet [START_REF] Autler | [END_REF], with the characteristic energy splitting given by √ 2 + δ 2 , where denotes the driving (Rabi) frequency and δ the detuning from the resonant frequency. On resonance (δ = 0), each of the dressed states takes half of the original excitation strength and the Autler-Townes splitting (ATS) equals the Rabi frequency. A direct result of the ATS is reduced target absorption in the spectral gap of the doublet where the transmission is also modulated by the quantum interference effect known as electromagnetically induced transparency [4]. These phenomena have a rich variety of applications including dissipation-free light transmission and fast low-power optical switching [5]. They enable a control of decay branching ratios, measurements of transition dipole moments, electromagnetic field characterization [6], and offer a framework for single-qubit operations relying solely on optical fields [7].

The simplest manifestation of the laser coupling is therefore a change in the transmission or reflection of the excitation pulse upon tuning the laser wavelength or intensity [5,8]. The coupling can be explored in greater detail by measuring the temporal dependence of the fluorescence signal from the laser-split states at different laser wavelengths [9]. The Fourier transform of the acquired frequency-time data set results in the frequency map, displaying a typical image of the avoided level crossings, familiar from the Stark and Zeeman spectroscopy [START_REF] Cowan | The Theory of Atomic Structure and Spectra[END_REF]. For optical transitions, the frequency map may also be measured directly, by changing the detuning of both the excitation laser and the coupling laser and detecting the total fluorescence yield at each setting [9], or by inspecting the population of the coupled state [START_REF] Chen | [END_REF]. However, these approaches to the ATS characterization become very demanding or even unfeasible when dealing with short-lived states exhibiting lifetimes of the order of ps or shorter: the indirect approach requires temporal resolution of the emission events well below the lifetime of the excited states, and the direct approach relies on the tunability of short pulses over wide frequency intervals for both radiation sources while maintaining their spatiotemporal overlap at constant intensities.

In order to observe a significant splitting, the Rabi frequency must be comparable to or larger than the decay rate of the excited state, meaning that the laser intensity must stay above the critical value of (8πα|μ| 2 τ 2 ) -1 , at least until most of the exited atomic states have decayed. For atomic states with one or more inner-shell vacancies with lifetimes τ in the 1-10 fs range, the critical intensity is in the 10 13 -10 11 W cm -2 range, as seen by inserting above finestructure constant α and a typical value of the coupling dipole matrix element μ ≈ 1 (in atomic units). Therefore, to keep the required laser power reasonably low, excitation pulses with duration significantly longer than τ should be avoided. A convenient source for studying short-lived states in the extreme-ultraviolet (EUV) spectral range is based on the high harmonic generation (HHG) [12].

In this work, we present an approach to constructing a twodimensional frequency map and demonstrate its applicability on the case of selectively coupled atomic resonances with femtosecond lifetimes and tens of eV excitation energies. We show that the complete information about the optical coupling and pulse properties may be extracted from the map measured by scanning the frequency and delay of the excitation pulse, while keeping the settings of the laser coupling pulse fixed. An essential ingredient of the proposed method is a nonzero laser chirp: when combined with the delay, different frequencies of the laser pulse overlap with the excitation pulse frequencies at different times to imitate the laser frequency scan.

II. EXPERIMENT

The experiment was performed at the CITIUS light source at the University of Nova Gorica, Slovenia [13]. The spectrally purified HHG radiation pulse overlapped with the linearly chirped laser pulse, tuned to the 2s2p 1 P o -2p 2 1 S e transition in helium. The total number of ions formed by autoionization was measured [Fig. 1(a)].

The setup consists of a HHG source, powered by an intense 800 nm Ti:sapphire laser producing 50 fs pulses with a 5 kHz repetition rate [Fig. 1(b)]. Prior to entering the gas cell, a 1.5 mJ laser pulse with a 30 nm bandwidth passed an adjustable delay line. The HHG radiation emitted by the Ne gas was filtered by a grating; at 1200 mm -1 groove density and 20 μm exit slit opening, the monochromator transmitted 60 eV photons with the 100 meV bandwidth. About one-half of the generating laser power was fed to the optical parametric amplifier (OPA) to produce VIS laser pulses tuned to 1.93 eV. The monochromatized HHG pulse, i.e., the EUV pulse and the linearly chirped VIS pulse crossed on the helium gas jet.

He + ions were collected by a 40-mm-diameter MCP detector placed 5 cm below the tip of the gas needle.

A. EUV pulse

The HHG driving laser frequency was tuned until obtaining a good ion yield contrast due to the 2s2p 1 P o excitation at 60.150 eV. In practice, the ratio of ions collected at the 39th harmonic (H39) and the 37th harmonic (H37) was maximized, with the former tuned to the resonance and the latter to the smooth ionization continuum at 3 eV lower photon energy (Fig. 2). The passage of the HHG radiation through the monochromator tilts the pulse front causing prolongation of the pulse [14]. With the known angular divergence of the HHG source, the monochromator ray tracing estimates about 115 fs time broadening resulting in an overall τ 1 = 125 fs pulse duration on the target.

The monochromator resolution was estimated from the ratio of the measured ion yield and the scaled theoretical photoabsorption cross section of helium, convoluted by the monochromator bandwidth (Fig. 2). Taking 100 meV FWHM for the latter, the ratio results in a reasonable ion yield signal when assuming that the resonant structure in this energy range is entirely absent. In other words, if the monochromator broadening was smaller (larger), the expected signal at H39 would be too large (too small) with respect to the mean of the signal detected at H37 and H41. Indeed, the separate measurement of ion yield, using the same HHG source but N 2 gaseous target, resulted in H39 intensity roughly equal to the mean intensity of H37 and H41. This is expected because N 2 does not exhibit any resonant structure and displays a slowly varying photoionization cross section in the H37-H41 frequency region [15]. The EUV pulse broadening on the target was therefore substantially smaller than the width of the harmonic H39, roughly given by the width of the H37 ion yield peak in Fig. 2.

The number of photons in the pulse with the monochromator set to the H37 maximum was 1.2 × 10 5 , as obtained from the measured ion count rate by assuming 1 mm target length and 10 -4 mbar local target pressure, and taking 1.48 Mb for the helium photoionization cross section at 57 eV photon energy [16]. The lateral width of the EUV pulse at the target was not more than 0.15 mm, consistent with the observed ion yield trends when the gas needle was moved across the beam along both the perpendicular directions. The maximum H39 intensity in the target was then around

I 1 = 3 × 10 4 W cm -2 .

B. Linearly chirped VIS pulse

The VIS pulse maximum intensity was estimated by comparing the pulse energy, transmitted through the 0.3 mm pinhole, to the pulse energy measured without the pinhole. Assuming a radially symmetric Gaussian intensity profile, the result is consistent with the 0.3 mm beam waist in the target region and the maximum intensity I 2 = (1 ± 0.2) × 10 11 W cm -2 of the VIS pulse with 145 fs duration. This estimate accounts for the pulse-to-pulse instabilities and for the power losses due to the light scattering on the pinhole walls. Since the EUV beam waist was substantially narrower, the instantaneous VIS intensity was approximately

ω 1 (eV) ω 2 (0) FIG. 2.
Measured ion yield (empty black circles) as a function of the monochromator pass energy covering the H 37-41 wavelength region with the coupling laser off. Thick (red) curve is the theoretical helium photoabsorption cross section [16], convoluted by a 100 meV FWHM Lorentzian (thick green curve) and scaled to 1 on the top of H37. Thin (red) curve denotes the shape of the unconvoluted cross section. The ratio of the measured ion signal (with background subtracted) and the convoluted cross section (full gray circles) estimates the ion yield signal for a fictitious case with no 2s2p 1 P o resonance. The top bar gives energy positions of the lowest-lying 1 S e resonances with dashed line showing the position of the 2p 2 1 S e state. The ion yield signal observed in the limited range of the ATS measurement with a strongly delayed EUV pulse [Fig. 4(a)] is denoted by (blue) crosses. the same at different lateral positions of the target ionization volume.

Time delay, at which the maximum temporal overlap of the VIS laser pulse and the EUV pulse occurs, was estimated by combining the VIS and the generating NIR laser pulses (ω g = 1.55 eV) on the BBO crystal placed at the same distance from the source as the gas target and illuminated by means of the switching mirror. Upon proper delay setting, the harmonic beam component with ω g + ω 2 frequency was observed at the back side of the crystal.

With the OPA set to λ = 648 nm, the generated VIS laser pulses were 57 fs long and showed a nearly Gaussian intensity profile with the spectral width λ = 25 nm. Since this is significantly shorter than the duration of EUV pulses, the VIS pulses were prolonged to τ 2 = 145 fs by passing through the Glan-Taylor polarizer with a thickness of L = 25 mm. According to the optical properties of the calcite [17], the passage generates 1305 fs 2 group delay dispersion (GDD) of the transmitted (extraordinary) ray. Formally, g = L(d 2 k/dω 2 ) is the weight of the lowest-(second-) order pulse-shape-changing term (ω -ω 2 ) 2 /2 in Taylor expansion of the spectral phase [START_REF]Nonlinear Fiber Optics[END_REF]. The effect of such a linear chirp is to prolong a Gaussian pulse for a factor 1 + (4g ln 2/ τ 2 ) 2 with respect to the Fourier limited pulse duration τ = 2λ 2 ln 2/(π c λ) ≈ 25 fs. The expected pulse duration after the biprism is then 146 fs, which is very close to the measured value. However, this estimate neglects a possible intrinsic chirp of the OPA pulse, indicated by pulse duration exceeding τ for about a factor of two. The upper g limit may be obtained by adding 462 fs 2 to the calcite-only GDD value. This would reproduce duration of the OPA pulse, but would overestimate final pulse duration for 30% and still fail to explain slight deviations from the Gaussian profile at the OPA exit (nonlinear chirp). In the following, the VIS laser pulse chirp is approximated by g = 1500 ± 200 fs 2 and the higher-order contributions, such as TOD and FOD, are neglected [START_REF]Nonlinear Fiber Optics[END_REF].

According to [START_REF] Saleh | Fundamentals of Photonics[END_REF][START_REF] Mihelič | [END_REF], the linear chirp in the time domain is defined by introducing linear dependence of the instantaneous angular frequency

ω 2 (t ) = ω 2 (0) + 4χ ln 2 t/τ 2 2 (1)
by a dimensionless parameter χ . For a Gaussian pulse profile it can be shown that, given the temporal pulse width τ 2 , the ratio of the spectral width of the chirped pulse intensity (g = 0) versus the corresponding Fourier spectral width (g = 0) is given by 1 + χ 2 . This leads to the following relation between the two chirp parameters: χ = 4g ln 2/ τ 2 . The linear chirp parameter of the coupling laser pulse is thus estimated to χ = 7 ± 1, considering a relatively small but not precisely known GDD contribution from the OPA pulse. The laser frequency thus increases by a factor of 8χ ln 2/[τ 2 (E 3 -E 2 )] ≈ 8% by the time the VIS pulse returns to one-half of its maximum intensity when the central laser frequency ω 2 (0) corresponds to E 3 -E 2 , the energy difference of the upper states.

III. THEORETICAL DESCRIPTION

Previous calculations dealt with the transmission of the EUV pump pulse as a function of the delay for different durations and intensities of the 800 nm laser coupling pulse [21,22] and, very recently, with simulations of two-color 2s2p 1 P o (auto)ionization under the (near) resonant coupling conditions [23]. To simulate the present experimental situation, the process was modeled by a three-level ladder scheme where the 2s2p 1 P o autoionizing state at energy E 2 = -0.693052 a.u. is weakly coupled to the ground state of the helium atom at energy E 1 = -2.903366 a.u. by an EUV excitation pulse with frequency ω 1 , and strongly coupled to the 2p 2 1 S e autoionizing state at energy E 3 = -0.621704 a.u. by a linearly chirped VIS pulse with frequency ω 2 (t ) [Fig. 1(a)]. Introducing EUV delay t and VIS chirp χ to Eqs. ( 11)-( 13) and ( 21) in Ref. [23], the problem is described by a set of equations for slowly varying amplitudes u i for each of the three states:

i u1 = -iγ 1 u 1 + 12 2 1 - i q 12 u 2 , ( 2
)
i u2 = -δ 1 -i 2 2 u 2 + * 12 2 1 - i q 12 u 1 + 23 2 1 - i q 23 u 3 , ( 3
)
i u3 = -δ 1 -δ 2 -4χ ln2 t τ 2 2 -i 3 2 u 3 + * 23 2 1 - i q 23 u 2 . ( 4
)
The set is solved together with rate equation

ẏi = γ 1 |u 1 | 2 + 2 |u 2 | 2 + 3 |u 3 | 2 + 2 Re * 12 u 1 u * 2 q 12 + * 23 u 2 u * 3 q 23 ( 5
)
to calculate y i (t → ∞), the asymptotic value of the ion yield. Above, δ 1 = ω 1 -E 2 + E 1 and δ 2 = ω 2 (0) -E 3 + E 2 denote the detuning of the EUV pulse and of the central frequency of the VIS pulse, respectively. The autoionization rates of states 2 and 3 are given by 2 = 1.37 × 10 -3 a.u. and 3 = 2.13 × 10 -4 a.u., respectively. The direct ground-state photoionization rate γ 1 (t ) = (σ c /ω 1 )I 1 g τ 1 (tt ) due to the Gaussian excitation pulse, g τ (t ) ≡ exp[-4 ln 2(t 2 /τ 2 )], is determined by the photoionization cross section σ c (ω 1 ) = 1.4 Mb, and results in a smooth background. The Fano parameters are q 12 = -2.76 and q 23 = -2415 [23]; the complex Rabi frequencies are defined as

12 (t ) = μ 12 8παI 1 g τ 1 (t -t )e -iω 1 t , 23 (t ) = μ 23 8παI 2 g τ 2 (t )e 2iχ ln 2(t 2 /τ 2 2 )
, and the dipole matrix elements are μ 12 = 3.60 × 10 -2 a.u. and μ 23 = 2.16 a.u., respectively [23].

A general view on the chirp parameter dependence of results is presented in Fig. 3, where a series of calculated ion yield maps in the frequency-delay space is presented for seven different values of χ in the 0-50 range, together with the corresponding two-color ion yield map, calculated for the unchirped laser pulse (χ = 0), fully overlapping in time with the EUV pulse. To sharpen the picture, the maps are plotted without considering the HHG monochromator broadening.

In the map sequence one can clearly follow evolution of the ion yield signal from the symmetric, ring-shaped form at χ = 0 with (vertical) gap orientation along the delay axis, to the slowly closing, quasihorizontal gap at χ = 50 where the resonant spectral components in the chirped pulse exhibit a strongly reduced duration. In the simple view, the effect of the increasing linear chirp parameter on the ion yield map can be described by the gap rotation from the vertical (delay) to the horizontal (frequency) direction, as indicated by following a sequence of white lines on the frequency-delay maps in Fig. 3.

IV. RESULTS AND DISCUSSION

The ATS experiment was performed by measuring the helium ion yield at different delays of the EUV pulse with respect to the VIS pulse, covering ±400 fs range in steps of 25 fs around a predetermined zero-delay time. At each delay setting, the 2 s/point monochromator scan was taken in the narrow 2s2p 1 P o resonance region. An average of 30 ion yield maps in Fig. 4(a) clearly shows a gap at small delays that intersects the ion signal ridge originating from the 2s2p 1 P o ionization. Note that the previous two-color experiments dealt with the EUV transmission changes in the vicinity of the 2s2p 1 P o autoionizing state in He at a relatively high intensity of the coupling laser pulses, considerably detuned from the resonant frequency [24].

To interpret the observations, two sets of calculations were performed: the first by varying frequency ω 1 and delay t of the EUV pulse with respect to the resonantly tuned and linearly chirped VIS pulse [Fig. 4(b)] and the second one by fixing the delay to zero and varying both, frequency ω 1 of the EUV pulse and frequency ω 2 of the unchirped VIS pulse, across the resonance region [Fig. 4(c)]. While the first set simulates experimental conditions, the second set corresponds to the ion yield in the frequency plane. Apart from the small frequency shifts, the latter reflects the basic ATS result: the two-level anticrossing following a pair of hyperbolas with the asymptotic behavior δ 1 = 0, -δ 2 and 2 eff + δ 2 2 splitting along the δ 1 axis [START_REF] Cohen-Tannoudji | The Autler-Townes Effect Revisited[END_REF]. The minimum splitting, extracted from Fig. 4(c), is eff ≈ 90 meV. The ion signal is seen to jump from one level to the other in the vicinity of δ 2 ≈ 0, following the weight of the 2s2p 1 P o resonance in the laser-coupled states: although the 2p 2 1 S e resonance decays by autoionization too, it acts here as a dark state since its photoexcitation from the atomic ground state is dipole forbidden. Note that the gap in Fig. 4(c) does not cross the doubly resonant position δ 1 = δ 2 = 0 because of the strongly asymmetric absorption profile of the 2s2p 1 P o state.

While the δ 1 axis covers the same frequency range F 1 in all the three maps, the frequency range F 2 = 4χ T ln 2/τ 2 2 ≈ ±0.24 eV on the δ 2 axis in Fig. 2(c) was chosen according to the linear chirp relation (1) to match the experimental delay range T = ±400 fs [Fig. 2(a)]. This scaling determines an angle the asymptotic δ 1 = -δ 2 makes with the δ 2 axis in Fig. 4(c). A good alignment of the asymptotic line with the observed signal gap in Fig. 4(a) indicates that the applied time-to-frequency scaling is reasonable. Conversely, at selected F 1 and T ranges, the gap inclination is given by angle φ = arctan(kχ ), k = (4 ln 2/τ 2 2 )(T /F 1 ), which can be taken as an indication of the linear chirp of the VIS pulse: when χ = 0, the gap (slit) is vertical because the ion yield must be Δt (fs) χ=0 χ=2.5

Δt (fs) the same when the unchirped Gaussian pulse is delayed or advanced by the same amount. Simulations with Eqs. ( 2)-( 5) support this simple chirp dependence of the gap rotation angle (Fig. 3). The sense of rotation towards the horizontal axis depends on the sign of the linear chirp parameter. In our experiment, t < 0 means that the EUV pulse arrives after the laser pulse and the observed rotation is counterclockwise for χ>0 [Fig. 4(b)]. For further analysis it is convenient to introduce the pulseaveraged Rabi frequency av = A 23 (0), where

χ=5 χ=7 Δt (fs) χ=10 χ=20 Δt (fs) 1 (eV) χ=50 ω 2 (eV) 1 (eV)
δ 2 (eV) δ 1 (eV) Ω eff δ 2 =-δ 1 δ 1 (eV) Δt (fs)
A = ∞ -∞ g τ 1 (t )dt ∞ t g τ 2 (t )e -(t -t ) dt ∞ -∞ g τ 1 (t )dt (6)
is the proportionality factor to the maximum Rabi frequency μ 23 √ 8παI 2 ≈ 100 meV, reached at t = 0. The averaging takes into account that decaying population of excited states, created at different times in proportion to I 1 g τ 1 (t ), is submitted to time-dependent intensity I 2 g τ 2 (t ) of the coupling laser field. The minimum doublet splitting thus changes in time and is proportional to the "momentary" Rabi frequency which itself is proportional to the square root of laser intensity. Estimating decay time -1 by the lifetime of the 2s2p 1 P o resonance, av = 84 meV comes close to the value of eff , extracted from the two-color map in Fig. 4(c).

The fit of a simple two-state model to the observed ion yield in Fig. 4(a) gives expt ≈ 80 meV for the minimum splitting. This tends to be smaller than eff because, even with two pulses fully overlapping in time, only a portion of the chirped temporal profile contains frequencies ω 2 (t ) close enough to the resonant frequency ω 2 (0) to cause an observable ion yield from both members of the split doublet. The effect can be roughly described by limiting the integration range in the denominator of (6) to the finite time interval ±u/2 around the pulse maximum. Using the chirp relation (1), the integration range is approximately given by u = E τ 2 2 /(4χ ln 2), where E is the energy interval spanned by the ion yield gap along the δ 2 axis of the two-color map. Inserting E ≈ 100 meV, about 10% drop of the averaged Rabi frequency is obtained, similar to the observation.

From Fig. 4(c) it is evident that at laser detuning larger than 0.2 eV, the ac Stark effect practically vanishes at the selected VIS intensity. This is confirmed by a separate calculation with the additional neighboring 1 S e and 1 D e resonances giving essentially unmodified results shown in Figs. 2(b) and 2(c). At large laser detuning, the coupling effects may be recovered by increasing the VIS pulse intensity but then the mixing with the other close-lying resonances cannot be neglected.

Figure 5(a) shows two horizontal cuts through the measured ion yield map, the first with VIS and EUV pulses overlapping in time (C 1 ) and the second with no overlap (C 2 ). A good match with the corresponding cuts from the calculated map [Fig. 2(b)] not only validates the model, but it also shows quite a weak sensitivity of the ATS on the chirp parameter. The remaining differences may be attributed to the absence of nonlinear chirp effects in the VIS pulse simulation, as well as to the approximations made regarding a spectrotemporal profile of the EUV pulse. The vertical cut through the experimental map matches very well the calculated cut, as well as the scaled EUV-VIS cross-correlation Gaussian profile exhibiting the width of τ 2 1 + τ 2 2 ≈ 190 fs [Fig. 5(b)]. Knowing the VIS pulse duration, the EUV pulse duration can thus be estimated from the experimental data, except for very high chirp parameters where the gap tends to disappear (Fig. 3).

V. SUMMARY AND CONCLUSIONS

In conclusion, we have solved a critical problem of how to measure the frequency map when the coupled states decay on the femtoseconds time scale. Instead of scanning the laser coupling frequency that may easily induce the uncontrolled changes of the pulse focusing, timing, duration, intensity, and chirp, the delay between the excitation and the coupling laser pulse is varied, so that all the laser settings remain fixed. We showed, experimentally and by numerical solutions of Schrödinger equation with predetermined pulse parameters and calculated atomic data, that the frequency-delay map closely resembles the frequency map of the ion yield, provided the coupling laser pulse is linearly chirped. The method was demonstrated on the paradigmatic case of the short-lived resonances in helium, but can be applied to an arbitrary decay channel of other laser-coupled states featuring femtosecond lifetimes. The proposed approach may be helpful to access properties of short-lived states with new properties optimized to certain applications, e.g., generation of femtosecond switches and transfer of decay into a desired dissociation channel, achievable only via population of highly excited states. Another important issue, resolved by such experiments, is the characterization of short EUV radiation pulses: when the two states with known properties are coupled by a well-characterized laser pulse, the excitation pulse parameters such as intensity, duration, and chirp can be extracted from the map. As an alternative to HHG, the laser-sliced synchrotron radiation sources provide short and tunable excitation pulses that may be well adapted to ATS experiments on laser coupled states at high excitation energies [25]. Finally, replacement of a simple ion counting device with an ion-selective detector makes the present approach appealing for molecular studies: a selective laser coupling of states populating different dissociation channels is a promising technique to disentangle and control molecular decay dynamics.

FIG. 1 .

 1 FIG. 1. (a) Three-level excitation and decay scheme with a delayed and detuned EUV pulse and a chirped VIS pulse. (b) Scheme of the experimental setup: a delayed NIR laser pulse (ω g ) is focused into the HHG gas cell filled with Ne. The monochromator selects the radiation ω 1 . EUV pulse is focused on He gas target in the experimental chamber together with the VIS laser pulse ω 2 , generated by the OPA and chirped by passing through the Glan-Taylor prism (G/T). Ions are collected by the MCP detector. T 1,2,3 : toroidal mirrors; G 1 : grating; L 1,2 : lenses; BS: beam splitter. The removable Al filter, deflection mirror (M), and BBO crystal are used to align EUV and VIS pulses in time.

FIG. 3 .

 3 FIG.3. Calculated frequency-delay ion yield maps for laser-coupled 2s2p 1 P o and 2p2 1 S o resonances. The linear chirp parameters are χ = 0, 2.5, 5, 7, 10, 20, 50. The EUV pulse has a maximum intensity I 1 = 3.0 × 10 4 W cm -2 and 125 fs duration and the VIS laser pulse has a maximum intensity I 2 = 10 11 W cm -2 and 145 fs duration. The white line on each of the frequency-delay maps indicates the gap alignment. Presented is also the calculated two-color ion yield map for the unchirped laser pulse at zero delay.

FIG. 4 .

 4 FIG. 4. (a) Ion yield map of the 2s2p 1 P o resonance, measured as a function of the EUV pulse frequency detuning δ 1 from the 60.152 eV excitation energy and delay t with respect to the chirped VIS laser pulse, tuned to the 2s2p 1 P o -2p 2 1 S e transition at 1.938 eV. The pairs of dashed white lines indicate signal integration area for the horizontal (C 1 , C 2 ) and the vertical (V) cut, presented in Figs. 3(a) and 3(b), respectively. (b) Calculated frequency-delay map for the 125 fs EUV pulse with the maximum intensity I 1 = 3 × 10 4 W cm -2 , broadened by a 100 meV Lorentzian and the 145 fs VIS laser pulse with the maximum intensity I 2 = 10 11 W cm -2 and linear chirp parameter χ = 7. (c) Calculated two-color map for the same EUV pulse as in (b) and the unchirped VIS pulse of the same duration and intensity as in (b). The white dotted lines mark the asymptotes of the two-level avoided crossing, characterized by eff minimum splitting and denoted by a pair of white curves.

FIG. 5 .

 5 FIG. 5. (a)Horizontal cuts C 1 (connected black circles) and C 2 (empty connected circles) through the experimental map in Fig.2(a) compared to the same cuts through the calculated ion yield map (black and gray thick curves). Dashed and dotted curves denote the calculated C 1 cut without the 100 meV broadening for χ = 7 and χ = 0, respectively. (b) Vertical cut V (black circles) through the experimental map compared to the calculated cut for χ = 7 (black thick curve). Black dotted and gray full curves denote scaled results for the calculated χ = 0 cut and the EUV-VIS cross correlation, respectively.

ACKNOWLEDGMENTS

This work is supported by the research Programme No. P1-0112 and by the research Project No. J1-8134 of the Slovenian Research Agency.