domain: chim sde

text:
est destinée au dépôt

  Sample preparation on future space missions for in situ gas chromatograph-mass spectrometer analyses of molecules with astrobiology interests David Boulesteix, A. Buch, Cyril Szopa, Caroline Freissinet, Melissa G. Trainer, Jennifer C. Stern, David Coscia, Yuanyuan He, Amy Williams To cite this version: David Boulesteix, A. Buch, Cyril Szopa, Caroline Freissinet, Melissa G. Trainer, et al.. Sample preparation on future space missions for in situ gas chromatograph-mass spectrometer analyses of molecules with astrobiology interests. Titan through time, Jun 2022, Paris (en ligne), France. hal-

Acknowledgements

Thanks to LGPM, LATMOS, GSFC/NASA laboratories for the technical and human supports, shared samples, and all advice.


François Bienvenu
email: francois.bienvenu@normalesup.org

Florence Débarre

Amaury Lambert

The split-and-drift random graph, a null model for speciation

Keywords: dynamical network, duplication-divergence, vertex duplication, genetic drift, species problem, coalescent

We introduce a new random graph model motivated by biological questions relating to speciation. This random graph is defined as the stationary distribution of a Markov chain on the space of graphs on {1, . . . , n}. The dynamics of this Markov chain is governed by two types of events: vertex duplication, where at constant rate a pair of vertices is sampled uniformly and one of these vertices loses its incident edges and is rewired to the other vertex and its neighbors; and edge removal, where each edge disappears at constant rate. Besides the number of vertices n, the model has a single parameter r n .

Using a coalescent approach, we obtain explicit formulas for the first moments of several graph invariants such as the number of edges or the number of complete subgraphs of order k. These are then used to identify five non-trivial regimes depending on the asymptotics of the parameter r n . We derive an explicit expression for the degree distribution, and show that under appropriate rescaling it converges to classical distributions when the number of vertices goes to infinity. Finally, we give asymptotic bounds for the number of connected components, and show that in the sparse regime the number of edges is Poissonian.

Introduction

In this paper, we introduce a random graph derived from a minimalistic model of speciation. This random graph bears superficial resemblance to classic models of protein interaction networks [START_REF] Chung | Duplication models for biological networks[END_REF][START_REF] Ispolatov | Duplication-divergence model of protein interaction network[END_REF][START_REF] Solé | A model of largescale proteome evolution[END_REF][START_REF] Vázquez | Modeling of protein interaction networks[END_REF] in that the events shaping the graph are the duplication of vertices and the loss of edges. However, our model is obtained as the steady state of a Markov process (rather than by repeatedly adding vertices), and has the crucial feature that the duplication of vertices is independent from the loss of edges. These differences result in a very different behavior of the model.

Before describing the model formally in Section 1.2, let us briefly explain the motivation behind its introduction.

Biological context

Although it is often presented as central to biology, there is no consensus about how the concept of species should be defined. A widely held view is that it should be based on the capacity of individuals to interbreed. This is the so-called "biological species concept", wherein a species is defined as a group of potentially interbreeding populations that cannot interbreed with populations outside the group.

This view, whose origins can be traced back to the beginning of the 20th century [START_REF] Poulton | What is a species?[END_REF], was most famously promoted by Ernst Mayr [START_REF] Mayr | Systematics and the Origin of Species from the Viewpoint of a Zoologist[END_REF] and has been most influential in biology [START_REF] Coyne | Speciation[END_REF]. However, it remains quite imprecise: indeed, groups of populations such that (1) all pairs of populations can interbreed and (2) no population can interbreed with a population outside the group are probably not common in nature -and, at any rate, do not correspond to what is considered a species in practice. Therefore, some leniency is required when applying conditions (1) and [START_REF] Ispolatov | Duplication-divergence model of protein interaction network[END_REF]. But once we allow for this, there are several ways to formalize the biological species concept, as illustrated in Figure 1. Thus, it seems arbitrary to favor one over the others in the absence of a mechanism to explain why some kind of groups should be more relevant (e.g., arise more frequently) than others. The vertices of the graph represent populations and its edges denote interbreeding potential (that is, individuals from two linked populations could interbreed, if given the chance). Even with such perfect information, it is not obvious how to delineate "groups of potentially interbreeding populations that cannot interbreed with populations outside the group": should these correspond to connected components (on the left, in green), maximal complete subgraphs (on the right, in red), or be based on some other clustering method (middle, in blue)?

Our aim is to build a minimal model of speciation that would make predictions about the structure and dynamics of the interbreeding network and allow one to recover species as an emergent property. To do so, we model speciation at the level of populations. Thus, we consider a set of n populations and we track the interbreeding ability for every pair of populations. All this information is encoded in a graph whose vertices correspond to populations and whose edges indicate potential interbreeding, i.e., two vertices are linked if and only if the corresponding populations can interbreed.

Speciation will result from the interplay between two mechanisms. First, populations can sometimes "split" into two initially identical populations which then behave as independent entities; this could happen as a result of the fragmentation of the habitat or of the colonization of a new patch. Second, because they behave as independent units, two initially identical populations will diverge (e.g., as a result of genetic drift) until they can no longer interbreed.

Formal description of the model

Start from any graph with vertex set V = {1, . . . , n}, and let it evolve according to the following rules 1. Vertex duplication: each vertex "duplicates" at rate 1; when a vertex duplicates, it chooses another vertex uniformly at random among the other vertices and replaces it with a copy of itself. The replacement of j by a copy of i means that j loses its incident edges and is then linked to i and to all of its neighbors, as depicted in Figure 2. Here, i duplicates and replaces j. After the duplication, j is linked to i and to each of its neighbors.

2. Edge removal: each edge disappears at constant rate ρ.

This procedure defines a continuous-time Markov chain (G n (t)) t 0 on the finite state space of all graphs whose vertices are the integers 1, . . . , n. It is easy to see that this Markov chain is irreducible. Indeed, to go from any graph G (1) to any graph G (2) , one can consider the following sequence of events: first, a vertex is duplicated repeatedly in order to obtain the complete graph of order n (e.g., ∀k ∈ {2, . . . , n}, vertex k is replaced by a copy of vertex 1); then, all the edges that are not in G (2) are removed.

Because the Markov chain (G n (t)) t 0 is irreducible, it has a unique stationary probability distribution µ n,ρ . This probability distribution on the set of graphs of order n defines a random graph that is the object of study of this paper.

Notation

To study the asymptotic behavior of our model as n → +∞, we can let ρ, the ratio of the edge removal rate to the vertex duplication rate, be a function of n. As will become evident, it is more convenient to parametrize the model by r n := n-1 2 ρ n . Thus, we write G n,rn to refer to a random graph whose law is µ n, 2rn n-1 . Although some of our results hold for any (n, r), in many cases we will be interested in asymptotic properties that are going to depend on the asymptotics of r n . To quantify these, we will use the Bachmann-Landau notation, which for positive sequences r n and f (n) can be summarized as:

• r n ∼ f (n) when r n /f (n) → 1. • r n = o(f (n)) when r n /f (n) → 0.
• r n = Θ(f (n)) when there exists positive constants α and β such that, asymptotically, αf (n) r n βf (n).

•

r n = ω(f (n)) when r n /f (n) → +∞.
These notations also have stochastic counterparts, whose meaning will be recalled when we use them.

Finally, we occasionally use the expression asymptotically almost surely (abbreviated as a.a.s.) to that a property holds with probability that goes to 1 as n tends to infinity:

Q n a.a.s. ⇐⇒ P(Q n ) -----→ n→+∞ 1 .

Statement of results

Table 1 lists the first moments of several graph invariants obtained in Section 3.1. These are then used to identify different regimes, depending on the asymptotic behavior of the parameter r n , as stated in Theorem 3.10. Theorem 3.10. Let D n be the degree of a fixed vertex of G n,rn . In the limit as n → +∞, depending on the asymptotics of r n we have the following behaviors for G n,rn (i) Complete graph: when r n = o(1/n), P(G n,rn is complete) goes to 1, while when r n = ω(1/n) it goes to 0; when r n = Θ(1/n), this probability is bounded away from 0 and from 1.

(ii) Dense regime: when r n = o(1), P(D n = n -1) → 1.

(iii) Sparse regime: when r n = ω(n), P(D n = 0) → 1.

(iv) Empty graph: when r n = o(n 2 ), P(G n,rn is empty) goes to 0 while when r n = ω(n 2 ) it goes to 1; when r n = Θ(n 2 ), this probability is bounded away from 0 and from 1.

Variable Expectation Variance Covariance

1 {i↔j} 1 1+r r (1+r) 2 r (1+r) 2 (3+2r) if vertex in common, 2 r (1+r) 2 (3+r)(3+2r) otherwise. D (i) n n-1 1+r r(n-1)(1+2r+n) (1+r) 2 (3+2r) r (1+r) 2 1 + 3(n-2) 3+2r + 2(n-2)(n-3) (3+r)(3+2r) |E n | n(n-1) 2(1+r) rn(n-1)(n 2 +2r 2 +2nr+n+5r+3) 2 (1+r) 2 (3+r) (3+2r) - X n,k n k 1 1+r k-1 unknown - Table 1:
First and second moments of several graph invariants of G n,r : 1 {i↔j} is the variable indicating that {ij} is an edge, D (i) n the degree of vertex i, |E n | the number of edges and X n,k the number of complete subgraphs of order k. The covariance of the indicator variables of two edges depends on whether these edges share a common end, hence the two expressions. All expressions hold for every value of n and r.

In Section 4, we derive an explicit expression for the degree distribution, which holds for every value of n and r n . We then show that, under appropriate rescaling, this degree converges to classical distributions. Theorem 4.1. Let D n be the degree of a fixed vertex of G n,rn . Then, for each k ∈ {0, . . . , n -1},

P(D n = k) = 2 r n (2 r n + 1) (n + 2 r n )(n -1 + 2 r n ) (k + 1) k i=1 n -i n -i + 2 r n -1 ,
where the empty product is 1.

Theorem 4.2.

(i) If r n → r > 0, then Dn n converges in distribution to a Beta(2, 2 r) random variable.

(ii) If r n is both ω(1) and o(n), then Dn n/rn converges in distribution to a size-biased exponential variable with parameter 2.

(iii) If 2 r n /n → ρ > 0, then D n + 1 converges in distribution to a size-biased geometric variable with parameter ρ/(1 + ρ).

Asymptotic bounds for the number of connected components are obtained in Section 5, where the following theorem is proved. Theorem 5.1. Let #CC n be the number of connected components of G n,rn . If r n is both ω(1) and o(n), then

r n 2 + o p (r n ) #CC n 2 r n log n + o p (r n log n)
where, for a positive sequence (u n ), o p (u n ) denotes a given sequence of random variables (X n ) such that X n /u n → 0 in probability.

Because the method used to obtain the upper bound in Theorem 5.1 is rather crude, we formulate the following conjecture, which is well supported by simulations.

Conjecture 5.4.

∃α, β > 0 s.t. P(αr n #CC n βr n ) ----→ n→∞ 1.
Finally, in Section 6 we use the Stein-Chen method to show that the number of edges is Poissonian in the sparse regime, as shown by Theorem 6.1.

Theorem 6.1. Let |E n | be the number of edges of G n,rn . If r n = ω(n) then d TV |E n |, Poisson(λ n ) -----→ n→+∞ 0 ,
where d TV stands for the total variation distance and

λ n = E(|E n |) ∼ n 2
2rn . If in addition r n = o(n 2 ), then λ n → +∞ and as a result

|E n | -λ n √ λ n D -----→ n→+∞ N (0, 1) ,
where N (0, 1) denotes the standard normal distribution.

These results are summarized in Figure 3. All equalities and inequalities are to be understood "asymptotically almost surely" (i.e. hold with probability that goes to 1 as n tends to infinity).

Coalescent constructions of G n,r n

In this section, we detail coalescent constructions of G n,rn that will be used throughout the rest of the paper. Let us start by recalling some results about the Moran model.

The standard Moran process

The Moran model [START_REF] Moran | Random processes in genetics[END_REF] is a classic model of population genetics. It consists in a set of n particles governed by the following dynamics: after an exponential waiting time with parameter n 2 , a pair of particles is sampled uniformly at random. One of these particles is then removed (death) and replaced by a copy of the other (birth), and we iterate the procedure.

In this document, we will use the Poissonian representation of the Moran process detailed in the next definition.

Definition 2.1. The driving measure of a standard Moran process on

V is a collection M = (M (ij) ) (ij)∈V 2 of i.i.d. Poisson point processes with rate 1/2 on R.
We think of the elements of V as sites, each occupied by a single particle. In forward time, each atom t ∈ M (ij) indicates the replacement, at time t, of the particle in i by a copy of the particle in j.

For any given time α ∈ R, M defines a genealogy of V on ]-∞, α]. Taking α = 0 and working in backward time, i.e. writing t 0 to refer to the absolute time -t, this genealogy is described by a collection of ancestor functions a t , t ∈ [0, +∞[, a t : V → V , defined as follows: (a t ) t 0 is the piecewise constant process such that (i) a 0 is the identity on V .

(ii) If t ∈ M (ij) then • For all k such that a t-(k) = i, a t (k) = j. • For all k such that a t-(k) = i, a t (k) = a t-(k). (iii) If for all (ij) ∈ V 2 , M (ij) ∩ [s, t] = O , then a t = a s .
We refer to a t (i) as the ancestor of i at time t before the present -or, more simply, as the ancestor of i at time t.

The standard Moran process is closely related to the Kingman coalescent [START_REF] Kingman | The coalescent, Stoch[END_REF]. Indeed, let R t denote the equivalence relation on V defined by i R t j ⇐⇒ a t (i) = a t (j) , and let K t = V /R t be the partition of V induced by R t . Then, (K t ) t 0 is a Kingman coalescent on V . In particular, we will frequently use the next lemma.

Lemma 2.2. Let (a t ) t 0 be the ancestor functions of a standard Moran process on V . For any i = j, let T {ij} = inf{t 0 : a t (i) = a t (j)} be the coalescence time of i and j and, for any S ⊂ V , let

T S = inf{T {ij} : i, j ∈ S, i = j} .
Then, for all t 0, conditional on {T S > t}, (T S -t) is an exponential variable with parameter |S| 2 . For a more general introduction to Kingman's coalescent and Moran's model, one can refer to e.g. [START_REF] Durrett | Probability models for DNA sequence evolution, 2nd Edition[END_REF] or [START_REF] Etheridge | Some mathematical models from population genetics. École d'été de probabilités de Saint-Flour XXXIX-2009[END_REF].

Backward construction

We now turn to the description of the coalescent framework on which our study relies. The crucial observation is that, for t large enough, every edge of G n (t) can ultimately be traced back to an initial edge that was inserted between a duplicating vertex and its copy. To find out whether two vertices i and j are linked in G n (t) , we can trace back the ancestry of the potential link between them and see whether the corresponding initial edge and its subsequent copies survived up to time t. The first part of this procedure depends only on the vertex duplication process and, conditional on the sequence of ancestors of {ij}, the second one depends only on the edge removal process, making the whole procedure tractable. The next proposition formalizes these ideas. Proposition 2.3. Let V = {1, . . . , n} and let V (2) be the set of unordered pairs of elements of V . Let M be the driving measure of a standard Moran process on V , and (a t ) t 0 the associated ancestor functions (that is, for each i in V , a t (i) is the ancestor of i at time t). Let P = (P {ij} ) {ij}∈V (2) be a collection of i.i.d. Poisson point processes with rate r n on [0, +∞[ such that M and P are independent. For every pair {ij} ∈ V (2) , define

P {ij} = t 0 : t ∈ P {at(i)at(j)} ,
with the convention that, ∀k ∈ V , P {k} = O . Finally, let G = (V, E) be the graph defined by E = {ij} ∈ V (2) :

P {ij} = O . Then, G ∼ G n,rn .
Throughout the rest of this document, we will write G n,rn for the graph obtained by the procedure of Proposition 2.3.

Proof of Proposition 2.3. First, consider the two-sided extension of (G n (t)) t 0 , i.e. the corresponding stationary process on R (see, e.g., Section 7.1 of [START_REF] Durrett | Probability: theory and examples[END_REF]), which by a slight abuse of notation we note (G n (t)) t∈R . Next, let ( Ḡn (t)) t∈R be the time-rescaled process defined by

Ḡn (t) = G n (t(n -1)/2) .
This time-rescaled process has the same stationary distribution as (G n (t)) t∈R and so, in particular, Ḡn (0) ∼ G n,rn .

In the time-rescaled process, each vertex duplicates at rate (n -1)/2 and each edge disappears at rate r n = (n -1)ρ n /2. All these events being independent, we see that the vertex duplications correspond to the atoms of a standard Moran process on V = {1, . . . , n}, and the edge removals to the atoms of n 2 i.i.d. Poisson point processes with rate r n on R, that are also independent of the Moran process. Thus, there exists ( M , P ) with the same law as (M , P ) from the proposition and such that, for t 0,

• If t ∈ M(ij) , then j duplicates and replaces i in Ḡn (-t).

• If t ∈ P{ij} , then if there is an edge between i and j in Ḡn (-t), it is removed.

Since ( M , P ) has the same law as (M , P ), if we show that {ij} ∈ Ḡn (0) ⇐⇒ P {ij} = O , where P {ij} = t 0 : t ∈ P{āt(i)āt(j)} is the same deterministic function of ( M , P ) as P {ij} of (M , P ), then we will have proved that Ḡn (0) has the same law as the graph G from the proposition. Now to see why the edges of Ḡn (0) are exactly the pairs {ij} such that P{ij} is empty, note that, in the absence of edge-removal events, Ḡn (0) is the complete graph and the ancestor the edge {ij} at time t is {a t (i) a t (j)}. Conversely, deleting the edge {k } from Ḡn (-t) will remove all of its subsequent copies from Ḡn (0), i.e. all edges {ij} such that {a t (i) a t (j)} = {k }. Thus, the edges of Ḡn (0) are exactly the edges that have no edge-removal events on their ancestral lineage -i.e, such that P {ij} = O . Proposition 2.3 shows that G n,rn can be obtained as a deterministic function of the genealogy (a t ) t 0 of a Moran process and of independent Poisson point processes. Our next result shows that, in this construction, (a t ) t 0 can be replaced by a more coarse-grained process -namely, a Kingman coalescent (note that the Kingman coalescent contains less information because it only keeps track of blocks, not of which ancestor corresponds to which block at a given time t). This will be useful to give a forward construction of G n,rn in Section 2.3. The proof of this result is straightforward and can be found in Section A of the Appendix. Proposition 2.4. Let (K t ) t 0 be a Kingman coalescent on V = {1, . . . , n}, and let π t (i) denote the block containing i in the corresponding partition at time t. Let the associated genealogy of pairs be the set

G = t, {π t (i) π t (j)} : {ij} ∈ V (2) , t ∈ 0, T {ij} ,
where T {ij} = inf{t 0 : π t (i) = π t (j)}. Denote by

L {ij} = t, {π t (i) π t (j)} : t ∈ 0, T {ij}
the lineage of {ij} in this genealogy. Finally, let P • be a Poisson point process with constant intensity r n on G and let G = (V, E), where

E = {ij} ∈ V (2) : P • ∩ L {ij} = O . Then, G ∼ G n,rn .
We finish this section with a technical lemma that will be useful in the calculations of Section 3.1. Again, the proof of this result has no interest in itself and can be found in Section A of the Appendix. Lemma 2.5. Let S be a subset of V (2) . Conditional on the measure M , for any interval I ⊂ [0, +∞[ such that (i) For all {ij} ∈ S, ∀t ∈ I, a t (i) = a t (j).

(ii) For all {k } = {ij} in S, ∀t ∈ I, {a t (i) a t (j)} = {a t (k) a t ( )}, P {ij} ∩I, {ij} ∈ S, are independent Poisson point processes with rate r n on I.

Moreover, for any disjoint intervals I and J, (P {ij} ∩ I) {ij}∈S is independent of (P {ij} ∩ J) {ij}∈S .

Before closing this section, let us sum up our results in words: if we think of {a t (i) a t (j)} as being the ancestor of {ij} at time t, then the genealogy of vertices induces a genealogy of pairs of vertices, as illustrated by Figure 4. Edge-removal events occur at constant rate r n along the branches of this genealogy and the events affecting disjoint sections of branches are independent, so that we can think of P {ij} , {ij} ∈ V (2) , as a single Poisson point process P on the lineages of pairs of vertices. A pair of vertices is an edge of G n,rn if and only if there is no atom of P on its lineage.

Figure 4: On the left, a genealogy on {i, j, k, } and on the right the corresponding genealogy of the pairs. Edge removal events occur at constant rate along the lineages of pairs of vertices, and a pair of vertices is an edge of G n,rn if and only if there is no atom on its lineage.

Forward construction

We now give a forward version of the coalescent construction presented in the previous section. Here, unlike in the previous section, the graph G n,r is built by adding vertices one at a time. This construction will be useful in proofs and provides a computationally efficient way to sample G n,r .

Consider the Markov process (G † r (t)) t 0 defined by (i) G † r (0) = ({1, 2}, {{1, 2}}) is the complete graph of order 2.

(ii) Conditional on V t = {1, . . . , n}, where V t is the set of vertices of G † r (t): at rate n 2 , a vertex is sampled uniformly in V t and duplicated without replacement -that is, we copy the vertex and all incident edges, and label the new vertex n + 1, resulting in a graph with vertex set {1, . . . , n + 1}.

(iii) During the whole process, each edge disappears at constant rate r.

Next, for every integer

n 2, let G r (n) = G † r (t n -),
where

t n = sup t 0 : G † r (t) has n vertices .
Finally, let Φ n (G r (n)) denote the graph obtained by shuffling the labels of the vertices of G r (n) uniformly at random, i.e. let Φ n be picked uniformly at random among all the permutations of {1, . . . , n} and, by a slight abuse of notation, let

Φ n (G r (n)) = {1, . . . , n}, {Φ n (i) Φ n (j)} : {ij} ∈ G r (n)
Proposition 2.6. For any r > 0, for any integer n 2,

Φ n (G r (n)) ∼ G n,r .
Going from a backward construction such as Proposition 2.4 to a forward construction such as Proposition 2.6 is common in coalescent theory. The proofs, though straightforward, are somewhat tedious. They can be found in Section A of the Appendix, and we save the rest of this section to comment on the forward construction.

Proposition 2.6 shows that, for any given sequence (r n ), for any n 2, Φ n (G rn (n)) ∼ G n,rn . Note however that this is not a compatible construction of a sequence (G n,rn ) n 2 . In particular, all elements of a sequence (Φ n (G r (n))) n 2 are associated to the same value of r, while each term of a sequence (G n,rn ) n 2 corresponds to a different value of r n .

Finally, it is necessary to relabel the vertices of G r (n) in Proposition 2.6, as failing to do so would condition on {k, k -1} being the (n -k + 1)-th pair of vertices to coalesce in the genealogy of G n,r (in particular, the edges of G r (n) are not exchangeable: "old" edges such as {1, 2} are least likely to be present than more recent ones such as {n -1, n}). However, since G r (n) and Φ n (G r (n)) are isomorphic, when studying properties that are invariant under graph isomorphism (such as the number of connected components in Section 5 or the positive association of the edges in Section 6), we can work directly on G r (n).

First and second moment methods

In this section, we apply Proposition 2.3 and Lemma 2.5 to obtain the expressions presented in Table 1. These are then used to identify different regimes for G n,rn , depending on the asymptotic behavior of the parameter r n .

In order to be able to use Lemma 2.5, we will always reason conditionally on the genealogy of the vertices (i.e. on the vertex duplication process M ) and then integrate against its law.

First moments of graph invariants 3.1.1. Degree and number of edges

Proposition 3.1. For any fixed vertices i and j, i = j, the probability that i and j are linked in G n,rn is

P(i ↔ j) = 1 1 + r n .
Corollary 3.2. Let D n be the degree of a fixed vertex of G n,rn , and |E n | be the number of edges of G n,rn . Then,

E(D n ) = n -1 1 + r n and E(|E n |) = n 2 1 1 + r n . Proof. By Proposition 2.3, {i ↔ j} ⇐⇒ P {ij} ∩ [0, T {ij} [ = O .
Reasoning conditionally on T {ij} and applying Lemma 2.5 to S = {{ij}} and I = [0, T {ij} [, we see that P {ij} is a Poisson point process with rate r n on I.

Since T {ij} ∼ Exp(1),

P(i ↔ j) = P e 1 > T {ij} ,
where e 1 = inf P {ij} is an exponential variable with rate r n that is independent of T {ij} . The corollary follows directly from the fact that the degree of a vertex v can be written as

D (v) n = i =v 1 {i↔v}
and that the number of edges of G n,rn is

|E n | = {ij}∈V (2)
1 {i↔j} .

Proposition 3.3. Let i, j and k be three distinct vertices of G n,rn . We have

Cov 1 {i↔j} , 1 {i↔k} = r n (3 + 2r n )(1 + r n ) 2
Corollary 3.4. Let D n be the degree of a fixed vertex of G n,rn . We have

Var(D n ) = r n (n -1)(1 + 2 r n + n) (1 + r n ) 2 (3 + 2 r n )
Proof. For all t 0, let S t = {a t (i), a t (j), a t (k)}. Let τ 1 = inf{t 0 :

|S t | =
P {ij} ∩ [0, τ 1 [ ∪ P {ik} ∩ [0, τ 1 [ ∪ P {uv} ∩ [τ 1 , τ 2 [ = O Conditionally on τ 1 and τ 2 , by Lemma 2.5, (P {ij} ∩ [0, τ 1 [) ∪ (P {ik} ∩ [0, τ 1 [) is independent of P {uv} ∩ [τ 1 ,
P(i ↔ j, i ↔ k) = P(e 1 > τ 1 ) P(e 2 > τ 2 -τ 1 )
,

where e 1 = inf(P {ij} ∪ P {ik} ) ∼ Exp(2 r n ) is independent of τ 1 and e 2 = inf(P {uv} ∩ [τ 1 , +∞[) ∼ Exp(r n ) is independent of τ 2 -τ 1 . As a result, P(i ↔ j, i ↔ k) = 3 3 + 2 r n × 1 1 + r n . A short calculation shows that Cov 1 {i↔j} , 1 {i↔k} = r n (3 + 2r n )(1 + r n ) 2 ,
proving the proposition.

As before, the corollary follows from writing the degree of v as

D (v) n = i =v 1 {i↔v} , which gives Var D (v) n = (n -1) Var 1 {i↔v} + (n -1)(n -2) Cov 1 {i↔v} , 1 {j↔v} . Substituting Var 1 {i↔v} = r n /(1 + r n ) 2 and
1 {k↔ } = 2 r n (1 + r n ) 2 (3 + r n )(3 + 2 r n ) Corollary 3.6. Let D (i)
n and D (j) n be the respective degrees of two fixed vertices i and j, and let |E n | be the number of edges of G n,rn . We have

Cov D (i) n , D (j) n = r n (1 + r n ) 2 1 + 3(n -2) 3 + 2 r n + 2(n -2)(n -3) (3 + r n )(3 + 2 r n )
and

Var(|E n |) = r n n (n -1)(n 2 + 2 r 2 n + 2 n r n + n + 5 r n + 3) 2 (1 + r n ) 2 (3 + r n ) (3 + 2 r n )
The proof of Proposition 3.5 and its corollary are conceptually identical to the proofs of Propositions 3.1 and 3.3 and their corollaries, but the calculations are more tedious and so they have been relegated to Section B of the Appendix.

Complete subgraphs

From a biological perspective, complete subgraphs are interesting because they are related to how fine the partition of the set of populations into species can be. Indeed, the vertices of a complete subgraph -and especially of a large one -should be considered as part of the same species. A complementary point of view will be brought by connected components in Section 5.

In this section we establish the following results.

Proposition 3.7. Let X n,k be the number of complete subgraphs of order k in G n,rn . Then,

E(X n,k ) = n k 1 1 + r n k-1 .

Corollary 3.8. Let κ n be the clique number of G n,rn , i.e. the maximal number of vertices in a complete subgraph of G

n,rn . If (k n ) is such that n k n 1 1 + r n kn-1 ----→ n→∞ 0 ,
then k n is asymptotically almost surely an upper bound on κ n , i.e. P(κ n k n ) → 1 as n → +∞. In particular, when r n → +∞,

(i) If r n = o(n), then κ n log(r n )n/r n a.a.s. (ii) If r n = O(n/ log(n)), κ n = O p (n/r n ), i.e. ∀ε > 0, ∃M > 0, ∃N s.t. ∀n N, P(κ n > M n/r n ) < ε . Proof of Proposition 3.7. The number of complete subgraphs of order k of G n,rn is X n,k = S∈V (k) 1 {Gn,r n [S] is complete}
where the elements of V (k) are the k-subsets of V = {1, . . . , n}, and G n,rn [S] is the subgraph of G n,rn induced by S. By exchangeability,

E(X n,k ) = n k P G n,rn [S] is complete ,
where S is any fixed set of k vertices. Using the notation of Proposition 2.3,

G n,rn [S] is complete ⇐⇒ ∀{ij} ∈ S, P {ij} = O .
For all t 0, let A t = {a t (i) : i ∈ S} be the set of ancestors of S at t. Let τ 0 = 0 and for each = 1, . . . , k -1 let τ be the time of the -th coalescence between two lineages of S, i.e.

τ = inf t > τ -1 : |A t | = |A τ -1 | -1 Finally, let A = A τ and I = [τ , τ +1 [. With this notation, ∀{ij} ∈ S, P {ij} = O = k-2 =0 B , where B = {ij}∈ A (2)
{P {ij} ∩ I = O } and A (2) denotes the (unordered) pairs of A . Since for = m, I ∩ I m = O , Lemma 2.5 shows that conditionally on I 0 , . . . , I k-1 , the events B 0 , . . . , B k-2 are independent. By construction, for all {ij} = {uv} in A (2) ,

∀t ∈ I , {a t (i), a t (j)} = {a t (u), a t (v)} = O
and so it follows from Lemma 2.5 that, conditional on I , (P {ij} ∩I ), {ij} ∈ A (2) , are i.i.d. Poisson point processes with rate r n on I . Therefore,

P(B ) = P min e ( ) {ij} : {ij} ∈ A (2) > |I | ,
where e ( ) {ij} , {ij} ∈ A (2) , are k- Proof of Corollary 3.8. The first part of the corollary is a direct consequence of Proposition 3.7. First, note that X n,kn = 0 ⇐⇒ κ n < k n that a complete subgraph of order k contains complete subgraphs of order for all < k. As a result, any k n such that P(X n,kn = 0) → 1 is asymptotically almost surely an upper bound on the clique number κ n . Now, observe that since X n,kn is a non-negative integer, X n,kn 1 {Xn,k n =0} and therefore E(X n,kn ) P(X n,kn = 0) . Finally, X n,k being integer-valued, P(X n,kn = 0) → 0 implies P(X n,kn = 0) → 1.

To prove the second part of the corollary, using Stirling's formula we find that whenever r n and k n are o(n) and go to +∞ as n → +∞,

n k n 1 1 + r n kn-1 ∼ C √ k n n n k kn n (n -k n ) n-kn 1 1 + r n kn-1
, where C = √ 2π. The right-hand side goes to zero if and only if its logarithm goes to -∞, i.e. if and only if

A n := k n log n -k n k n (1 + r n ) -n log 1 - k n n + log 1 + r n √ k n goes to -∞. Now let k n = ng n /r n , where g n → +∞ and is o(r n ), so that k n = o(n). Then, k n log n -k n k n (1 + r n ) ∼ -k n log(g n ) and -n log 1 - k n n ∼ k n .
Moreover, as long as it does not go to zero,

log 1 + r n √ k n ∼ 3 2 log(r n ) - 1 2 log(ng n ) .
Putting the pieces together, we find that A n is asymptotically equivalent to

- ng n r n log(g n ) + 3 2 log(r n ) - 1 2 log(ng n ) .
Taking g n = log(r n ), this expression goes to -∞ as n → +∞, yielding (i). If r n = O(n/ log(n)), then it goes to -∞ for any g n → +∞, which proves (ii). Indeed, if there exists ε > 0 such that

∀M > 0, ∀N, ∃n N s.t. P(κ n > M n/r n ) ε ,
then considering successively M = 1, 2, . . ., we can find

n 1 < n 2 < • • • such that ∀k ∈ N, P(κ n k > kn k /r n k ) ε . Defining (g n ) by ∀n ∈ {n k , . . . , n k+1 -1}, g n = k ,
we obtain a sequence (g n ) that goes to infinity and yet is such that for all N there exists n := min{n k :

n k N } such that P(κ n > g n n/r n ) ε.
A natural pendant to Proposition 3.7 and Corollary 3.8 would be to use the variance of X n,k to find a lower bound on the clique number. Indeed, it follows from Chebychev's inequality that

P(X n,k = 0) Var(X n,k ) E(X n,k ) 2 .
However, computing Var(X n,k ) requires being able to compute the probability that two subsets of k vertices S and S both induce a complete subgraph, which we have not managed to do. Using the probability that G n,rn [S] is complete as an upper bound for this quantity, we have the very crude inequality

Var(X n,k ) n k 2 p (1 -p) ,
where p = 1/(1 + r n ) k-1 . This shows that when r n → 0 and

k n = o(1/r n ), P(X n,kn = 0) tends to zero, proving that κ n is at least Θ(1/r n ).
Finally, because we expect our model to form dense connected components, whose number we conjecture to be on the order of r n in the intermediate regime (see Theorem 5.1 and Conjecture 5.4), and since the degree of a typical vertex is approximately n/r n in that regime, it seems reasonable to conjecture Conjecture 3.9. In the intermediate regime, i.e. when r n → +∞ and

r n = o(n), ∃α, β > 0 s.t. P(αn/r n κ n βn/r n ) -----→ n→+∞ 1.

Identification of different regimes

We now use the results of the previous section to identify different regimes for the behavior of G n,rn . The proof of our next theorem relies in part on results proved later in the paper (namely, Theorems 4.1 and 6.1), but no subsequent result depends on it, avoiding cyclic dependencies. While this section could have been placed at the end of the paper, it makes more sense to present it here because it relies mostly on Section 3.1 and because it helps structure the rest of the paper. Theorem 3.10. Let D n be the degree of a fixed vertex of G n,rn . In the limit as n → +∞, depending on the asymptotics of r n we have the following behaviors for G n,rn (i) Transition for the complete graph: when

r n = o(1/n), P(G n,rn is complete)
goes to 1, while when r n = ω(1/n) it goes to 0; when r n = Θ(1/n), this probability is bounded away from 0 and from 1.

(ii) Dense regime: when r n = o(1), P(D n = n -1) → 1.

(iii) Sparse regime: when r n = ω(n), P(D n = 0) → 1.

(iv) Transition for the empty graph: when r n = o(n 2 ), P(G n,rn is empty) goes to 0 while when r n = ω(n 2 ) it goes to 1; when r n = Θ(n 2 ), this probability is bounded away from 0 and from 1.

Proof. (i) is a direct consequence of Proposition 3.7 which, applied to k = n, yields

P(G n,rn is complete) = 1 1 + r n n-1 . (ii) is intuitive since E(D n ) = (n -1)/(1 + r n ); but because it takes r n = o(1/n 2 )
for Var(D n ) to go to zero, a second moment method is not sufficient to prove it. However, using Theorem 4.1, we see that P(D n = n -1) can be written as

P(D n = n -1) = Γ(2 + 2 r n )Γ(n + 1) Γ(n + 1 + 2 r n ) ,
where Γ is the gamma function. The results follows by letting r n go to zero and using the continuity of Γ.

(iii) follows from the same argument as in the proof of Corollary 3.8, by which, D n being a non-negative integer,

P(D n = 0) E(D n ) = n-1
1+rn . In (iv), the fact that G n,rn is empty when r n = ω(n 2 ) is yet another application of this argument, but this time using the expected number of edges,

E(|E n |) = n(n-1)
2(1+rn) , in conjunction with the fact that G n,rn is empty if and only if |E n | = 0; to see why the graph cannot be empty when r n = o(n 2 ), consider the edge that was created between the duplicated vertex and its copy in the most recent duplication. Clearly, if this edge has not disappeared yet then G n,rn cannot be empty. But the probability that this edge has disappeared is just r n n 2 + r n , which goes to zero when r n = o(n 2 ). Finally, the fact that P(G n,rn is empty) is bounded away from 0 and from 1 when r n = Θ(n 2 ) is a consequence of Theorem 6.1, which shows that the number of edges is Poissonian when

r n = ω(n).

The degree distribution

The degree distribution is one of the most widely studied graph invariants in network science. Our model makes it possible to obtain an exact expression for its probability distribution: Theorem 4.1 (degree distribution). Let D n be the degree of a fixed vertex of G n,rn . Then, for each k ∈ {0, . . . , n -1},

P(D n = k) = 2 r n (2 r n + 1) (n + 2 r n )(n -1 + 2 r n ) (k + 1) k i=1 n -i n -i + 2 r n -1 ,
where the empty product is 1.

The expression above holds for any positive sequence (r n ) and any n; but as n → +∞ it becomes much simpler and, under appropriate rescaling, the degree converges to classical distributions: Theorem 4.2 (convergence of the rescaled degree).

(i) If r n → r > 0, then Dn n converges in distribution to a Beta(2, 2 r) random variable.

(ii) If r n is both ω(1) and o(n), then Dn n/rn converges in distribution to a size-biased exponential variable with parameter 2.

(iii) If 2 r n /n → ρ > 0, then D n + 1 converges in distribution to a size-biased geometric variable with parameter ρ/(1 + ρ).

In this section we prove Theorem 4.1 by coupling the degree to the number of individuals descended from a founder in a branching process with immigration. Theorem 4.2 is then easily deduced by a standard study that has been relegated to Section C of the Appendix.

Ideas of the proof of Theorem 4.1

Before jumping to the formal proof of Theorem 4.1, we give a verbal account of the main ideas of the proof.

In order to find the degree of a fixed vertex v, we have to consider all pairs {iv} and look at their ancestry to assess the absence/presence of atoms in the corresponding Poisson point processes. To do so, we can restrict our attention to the genealogy of the vertices, and consider that edge-removal events occur along the lineages of this genealogy: a point that falls on the lineage of vertex i at time t means that t ∈ P {iv} . In this setting, edgeremoval events occur at constant rate r n on every lineage different from that of v.

Next, the closed neighborhood of v (i.e. the set of vertices that are linked to v, plus v itself) can be obtained through the following procedure: we trace the genealogy of vertices, backwards in time; if we encounter an edge-removal event on lineage i at time t, then we mark all vertices that descend from this lineage, i.e. all vertices whose ancestor at time t is i; only the lineages of unmarked vertices are considered after t. We stop when there is only one lineage left in the genealogy. The unmarked vertices are then exactly the neighbors of v (plus v itself). The procedure is illustrated in Figure 5.

Figure 5: Illustration of the procedure used to find the neighborhood of v. On the left, the genealogy of the vertices. The dashed blue line represents the lineage of the focal vertex v, and a dot on lineage k corresponds to a point in P {kat(v)} . In the middle, we uncover the genealogy and edge-removal events in backward time, as described in the main text. On the right, the forest that we get when the procedure is complete. The non-colored (black) branches are exactly the neighbors of v.

This vertex marking process is not convenient to describe in backward time because we typically mark several vertices simultaneously. By contrast, the forest that results from the completed process seems much easier to describe in forward time. Indeed, the arrival of a new lineage corresponds either to the addition of a new unmarked vertex or to the addition of a marked one, depending on whether the new lineage belongs to the same tree as v or not.

Moreover, in forward time, the process is reminiscent of a branching process with immigration: new lineages are either grafted to existing ones (branching) or sprout spontaneously (immigration). Let us try to find what the branching and immigration rates should be. In backward time, when there are k + 1 lineages then a coalescence occurs at rate k+1 2 , while an edge-removal event occurs at rate k r n . Reversing time, these events occur at the same rates. As a result, when going from k to k + 1 lineages, the probability that the next event is a branching is (k + 1)/(k + 1 + 2 r n ).

Next, we have to find the probability that each lineage has to branch, given that the next event is a branching. Here, a spinal decomposition [START_REF] Chauvin | Growing conditioned trees[END_REF][START_REF] Lyons | Conceptual proofs of L log L criteria for mean behavior of branching processes[END_REF] suggests that every lineage branches at rate 1, except for the lineage of v, which branches at rate 2. To see why, observe that this is coherent with the fact that, in backward time, when going from k + 1 to k lineages there are k pairs out of k+1 2 that involve the lineage of v, so that the probability that the lineage of v is involved in the next coalescence is 2/(k + 1).

If this heuristic is correct, then in forward time it is easy to track the number of branches of the tree of v versus the number of branches of other trees: when there are p branches in the tree of v and q branches in the other trees, the probability that the next branch is added to the tree of v is just (p + 1)/(p + 1 + q + 2 r n ). Moreover, when the total number of branches reaches n, the number of branches in the tree of v is also the number of unmarked vertices at the end of the vertex marking procedure, which is itself D (v) n + 1, the degree of v plus one.

Formal proof of Theorem 4.1

The ideas and outline of the proof parallels the account given in the previous section: first, given a realization of the vertex-duplication process M and of the edge-removal process P , we describe a deterministic procedure that gives the closed neighborhood of any vertex v,

N G [v] = i ∈ V : {iv} ∈ E ∪ v ,
where G = (V, E) is the graph associated to M and P ; then, we identify the law of the process (F t ) t 0 corresponding to this procedure, and recognize it as the law of a branching process with immigration.

Definition 4.3. A rooted forest with marked vertices is a triple

F = (V • , V • , E) such that (i) V • ∩ V • = O . (ii) Letting V = V • ∪V • , (V, E) is an acyclic digraph with the property that ∀i ∈ V , deg + (i) ∈ {0, 1}, where deg + (i) is the out-degree of vertex i.
The marked vertices are the elements of V • ; the roots of F are the vertices with out-degree 0 (that is, edges are oriented towards the root), whose set we denote by R(F ); finally, the trees of F are its connected components (in the weak sense, i.e. considering the underlying undirected graph), and we write T F (i) for the tree containing i in F .

The vertex-marking process

We now define the backward-time process (F t ) t 0 that corresponds to the procedure described informally in Section 4.1. Recall the notation of Proposition 2.3. For a given realization of M and P , and for any fixed vertex v, let (F t ) t 0 be the piecewise constant process defined deterministically by

• F 0 = (V, O , O ). • If t ∈ M (ij) , then ∀k, ∈ R(F t-)∩V • t-such that (a t-(k), a t-( )) = (i, j), E t = E t-∪ (k, ) .
• If t ∈ P {iat(v)} , then letting d t (i) = {j ∈ V : a t (j) = i} be the set of descendants of i born after time t,

V • t = V • t-\ d t (i) V • t = V • t-∪ d t (i) .
What makes (F t ) t 0 interesting is that

N G [v] = V • ∞ .
Indeed, by construction,

i ∈ V • t ⇐⇒ s∈[0,t]   j:i∈ds(j) P {jas(v)}   = O ,
and since for every s the unique j such that i ∈ d s (j) is a s (i), we have

V • t = i ∈ V : P {iv} ∩ [0, t] = O .
The Poissonian construction given above shows that (F t , a t ) t 0 is a Markov process. Now, observe that conditional on a t

(i) M (ij) ∩ ]t, +∞[ ∼ M (at(i)at(j)) ∩ ]t, +∞[ and is independent of (F s , a s ) s t (ii) P {iat(v)} ∩]t, +∞[ ∼ P {at(i)at(v)} ∩]t, +∞[ and is independent of (F s , a s ) s t (iii) j ∈ d t (i) ⇐⇒ i ∈ R(F t ) and j ∈ T Ft (i)
As a consequence, (F t ) t 0 is also a Markov process, whose law is characterized by

• F 0 = (V, O , O ). • F t goes from (V • t , V • t , E t ) to -V • t , V • t , E t ∪ {(i, j)} at rate 1/2, for all i, j in R(F t ) -V • t \ T Ft (i), V • t ∪ T Ft (i), E t at rate r n , for all i in R(F t ).
Let ( F k ) k∈{1,...,n} be the chain embedded in (F t ) t 0 , i.e. defined by

F k = F t k , where t k = inf t 0 : |R(F t )| = n -k + 1 .
The rooted forests with marked vertices that correspond to realizations of F n are exactly the f n = (V • , V • , E) that have n vertices and are such that V • = T fn (v). Moreover, for each of these there exists a unique trajectory (f 1 , . . . , f n ) of ( F 1 , . . . , F n ) such that F n = f n and it follows from the transition rates of (F t ) t 0 that

P F n = f n = (1/2) n-|R(fn)| r |R(fn)|-1 n n k=2 (k(k -1)/2 + (k -1)r n ) = 1 (n -1)! × (2 r n ) |R(fn)|-1 n k=2 (k + 2 r n ) (1)
Finally, note that

V • n = V • ∞ is the closed neighborhood of v in our graph.

The branching process

The process with which we will couple the vertex-marking process described in the previous section is a simple random function of the trajectories of a branching process with immigration (Z t ) t 0 . In this branching process, immigration occurs at rate 2 r n and each particle gives birth to a new particle at rate 1 -except for one particle, which carries a special item that enables it to give birth at rate 2; when this lineage reproduces, it keeps the item with probability 1/2, and passes it to its offspring with probability 1/2.

Formally, we consider the Markov process on the set of rooted forests with marked vertices (augmented with an indication of the carrier of the item), defined by Z 0 = ({1}, O , O , 1) and by the following transition rates:

(Z t ) t 0 goes from (W • , W • , E, c) to • W • ∪ {N }, W • , E ∪ {(N, i)}, c at rate 1, for all i ∈ W • • W • , W • ∪ {N }, E ∪ {(N, i)}, c at rate 1, for all i ∈ W • • W • ∪ {N }, W • , E ∪ {(N, c)}, N at rate 1 • W • , W • ∪ {N }, E, c at rate 2 r n where N = |W • ∪ W • | + 1
is the label of the new particle. The fourth coordinate of (Z t ) t 0 tracks the carrier of the item. As previously, the Markov chain ( Z k ) k∈N * embedded in (Z t ) t 0 is defined by

Z k = Z t k , where t k = inf t 0 : |W • t ∪ W • t | = k .
The realizations of Z n are exactly the (W

• n , W • n , E n , c n ) such that f n = (W • n , W • n , E n
) is a rooted forest with marked vertices on {1, . . . , n} and W • n = T fn (1) = T fn (c n ). For these, it follows from the transition rates of (Z t ) t 0 that

P Z n = (W • n , W • n , E n , c n ) = (2 r n ) |R(fn)|-1 n-1 k=1 (k + 1 + 2 r n ) . ( 2
)
Finally, note that (X k

) k∈N * = | W • k |, | W • k | k∈N *
, which counts the number of descendants of the first particle and the number of descendants of immigrants, is a Markov chain whose law is characterized by X 1 = (1, 0) and X k goes from (p, q) to • (p + 1, q) with probability p+1 p+1+q+2rn

• (p, q + 1) with probability q+2r p+1+q+2rn .

Relabeling and end of proof

The last step before finishing the proof of Theorem 4.1 is to shuffle the vertices of the forest associated to Z n appropriately. For any fixed n, v and c in {1, . . . , n}, let Φ (c,v) be uniformly and independently of anything else picked among the permutations of {1, . . . , n} that map

c to v; define Φ v ( Z n ) by Φ v W • n , W • n , E n , c n = Φ (cn,v) ( W • n ), Φ (cn,v) ( W • n ), Φ (cn,v) ( E n ) where Φ (cn,v) ( E n ) is to be understood as Φ (cn,v) (i), Φ (cn,v) (j) : (i, j) ∈ E n .
With all these elements, the proof of Theorem 4.1 goes as follows. First, from equations (1) and ( 2) and the definition of Φ v , we see that for all rooted forest with marked vertices f n ,

P F n = f n = P Φ v ( Z n ) = f n .
In particular, V • n , the set of unmarked vertices in the vertex-marking process, and Φ (cn,v) ( W • n ), the relabeled set of descendants of the first particle in the branching process, have the same law. Now, on the one hand we have

V • n = N G [v] = D (v)
n + 1 , and on the other hand we have

Φ (cn,v) ( W • n ) = W • n .
Since W • n is the first coordinate of the Markov chain (X k ) k∈N * introduced in the previous section, it follows directly from the transition probabilities of (X k ) k∈N * that

P X n = (k + 1, n -k -1) = n -1 k k p=1 (p + 1) n-k-2 q=0 (q + 2 r n ) n-1 (p+q)=1 (p+q) + 1 + 2 r n ,
from which the expression of Theorem 4.1 can be deduced through elementary calculations.

Connected components in the intermediate regime

From a biological perspective, connected components are good candidates to define species, and have frequently been used to that end. Moreover, among the possible definitions of species, they play a special role because they indicate how coarse the partition of the set of populations into species can be; indeed, it would not make sense biologically for distinct connected components to be part of the same species. As a result, connected components are in a sense the "loosest" possible definition of species. This complements the perspective brought by complete subgraphs, which inform us on how fine the species partition can be (see Section 3.1.2). For a discussion of the definition of species in a context where traits and ancestral relationships between individuals are known, see [START_REF] Manceau | The species problem from the modeler's point of view[END_REF].

The aim of this section is to prove the following theorem.

Theorem 5.1. Let #CC n be the number of connected components of G n,rn . If r n is both ω(1) and o(n), then

r n 2 + o p (r n ) #CC n 2 r n log n + o p (r n log n)
where, for a positive sequence (u n ), o p (u n ) denotes a given sequence of random variables (X n ) such that X n /u n → 0 in probability.

Lower bound on the number of connected components

The proof of the lower bound on the number of connected components uses the forward construction introduced in Section 2.2 and the associated notation. It relies on the simple observation that, letting #CC(G) denote the number of connected components of a graph G, #CC(G rn (k)) is a nondecreasing function of k. Indeed, in the sequence of events defining (G rn (k)) k 2 , vertex duplications do not change the number of connected components -because a new vertex is always linked to an existing vertex (its 'mother') and her neighbors -and edge removals can only increase it. Thus, if m n n and n are such that P #CC(G rn (m n ) n → 1 as n → ∞, then n is asymptotically almost surely a lower bound on the number of connected components of G rn (n) -and therefore of G n,rn .

To find such a pair (m n , n ), note that, for every graph G of order m,

#CC(G) m -#edges(G) .
Moreover, since for any fixed n, G rn (m n ) has the same law as G mn,rn , the exact expressions for the expectation and the variance of |E mn |, the number of edges of G rn (m n ), are given in Table 1. We see that, if r n and m n are both ω(1) and o(n),

E |E mn | ∼ m 2 n 2 r n and Var |E mn | ∼ m 2 n 4 r 3 n m 2 n + 2 r 2 n .
By Chebychev's inequality,

P |E mn | -E |E mn | m 1-ε n Var |E mn | m 2-2ε n .
When m n = Θ(r n ), since r n = ω(1) the right-hand side of this inequality goes to 0 as n → +∞, for all ε < 1/2. It follows that

|E mn | = E |E mn | + o p (r n ) .
Taking m n := α r n , we find that

#CC(G rn (m n )) m n -|E mn | = α 1 - α 2 r n + o p (r n ) .
The right-hand side is maximal for α = 1 and is then r n /2 + o p (r n ).

Upper bound on the number of connected components

Our strategy to get an upper bound on the number of connected components is to find a spanning subgraph whose number of connected components we can estimate. A natural idea is to look for a spanning forest, because forests have the property that their number of connected components is their number of vertices minus their number of edges. Definition 5.2. A pair of vertices {ij} is said to be a founder if it has no ancestor other than itself, i.e., letting T {ij} = sup{t 0 : a t (i) = a t (j)} be the coalescence time of i and j, {ij} is a founder if and only if ∀t < T {ij} , {a t (i) a t (j)} = {ij}.

Let F be the set of founders of G n,rn = (V, E), and let T n = (V, F ). Note that #F = n -1 and that T n is a tree. Therefore, letting F n = (V, F ∩ E) be the spanning forest of G n,rn induced by T n , we have

#CC n n -#edges(F n ) .
Let us estimate the number of edges of F n . Recall Proposition 2.3. By construction, ∀{ij} ∈ F ,

P {ij} = P {ij} ∩ [0, T {ij} ]. It follows that #edges(F n ) = {ij}∈F 1 {P{ij}∩[0,T{ij}]=O }
and, as a consequence,

#CC n 1 + {ij}∈F 1 {P{ij}∩[0,T{ij}] =O } . Now, 1 {P{ij}∩[0,T{ij}] =O } #(P {ij} ∩ [0, T {ij} ]
), and since (P {ij} ) {ij}∈F are i.i.d. Poisson point processes with intensity r n that are also independent of (T {ij} ) {ij}∈F , {ij}∈F

#(P {ij} ∩ [0, T {ij} ]) #(P ∩ [0, L n ]) ,
where P is a Poisson point process on ]0, +∞] with intensity r n and L n = T MRCA + {ij}∈F T {ij} is the total branch length of the genealogy of the vertices. Putting the pieces together,

#CC n 1 + #(P ∩ [0, L n ]) .
Conditional on L n , #(P ∩[0, L n ]) is a Poisson random variable with parameter r n L n . Moreover, it is known [START_REF] Tavaré | Line-of-descent and genealogical processes, and their applications in population genetics models[END_REF] that

E(L n ) = 2 n-1 i=1 1 i and Var(L n ) = 4 n-1 i=1 1 i 2
As a result,

E(#(P ∩ [0, L n ])) = r n E(L n ) ∼ 2 r n log n and Var(#(P ∩ [0, L n ])) = r n E(L n ) + Var(r n L n ) ∼ 2 r n log n + α r 2 n ,
with α = 2π 2 /3. Using Chebychev's inequality, we find that for all ε > 0,

P |#(P ∩ [0, L n ]) -2 r n log n| ε r n log n = O 2 ε 2 r n log(n) + α ε 2 log(n) 2 .
The right-hand side goes to 0 as n → +∞, which shows that #(P ∩ [0, L n ]) -2 r n log n = o p (r n log n) and finishes the proof. Remark 5.3. Using #(P ∩[0, L n ]) as an upper bound for {ij}∈F 1 {P{ij}∩[0,T{ij}] =O } turns out not to be a great source of imprecision, because most of the total branch length of a Kingman coalescent comes from very short branches. As a result, when r n = o(n), only a negligible proportion of the P {ij} ∩[0, T {ij} ]'s, {ij} ∈ F , have more than one point.

By contrast, using n -#edges(F n ) as an upper bound on #CC n is very crude. This leads us to formulate the following conjecture:

Number of edges in the sparse regime

From the expressions obtained in section 3.1.1 and recapitulated in Table 1, we see that when r n = ω(n),

E(|E n |) ∼ Var(|E n |) ∼ n 2 2 r n .
This suggests that the number of edges is Poissonian in the sparse regime, and this is what the next theorem states.

|E n | -λ n √ λ n D -----→ n→+∞ N (0, 1) ,
where N (0, 1) denotes the standard normal distribution.

The proof of Theorem 6.1 is a standard application of the Stein-Chen method [START_REF] Stein | A bound for the error in the normal approximation to the distribution of a sum of dependent random variables[END_REF][START_REF] Chen | Poisson approximation for dependent trials[END_REF]. A reference on the topic is [START_REF] Barbour | Oxford Studies in Probability[END_REF], and another excellent survey is given in [START_REF] Ross | Fundamentals of Stein's method[END_REF]. Let us state briefly the results that we will need.

Definition A. The Bernoulli variables X 1 , . . . , X N are said to be positively related if for each i = 1, . . . , N there exists (X (i) 1 , . . . , X (i) N ), built on the same space as (X 1 , . . . , X N ), such that (i)

X (i) 1 , . . . , X (i) N ∼ (X 1 , . . . , X N ) | X i = 1.
(ii) For all j = 1, . . . N , X (i) j X j .

Note that there are other equivalent definitions of positive relation (see e.g. Lemma 4.27 in [START_REF] Ross | Fundamentals of Stein's method[END_REF]). Finally, we will need the following classic theorem, which appears, e.g., as Theorem 4.20 in [START_REF] Ross | Fundamentals of Stein's method[END_REF].

Theorem A. Let X 1 , . . . , X N be positively related Bernoulli variables with P(X i = 1) = p i . Let W = N i=1 X i and λ = E(W ). Then,

d TV (W, Poisson(λ)) min{1, λ -1 } Var(W ) -λ + 2 N i=1 p 2 i .

Proof of the positive relation between the edges

It is intuitive that the variables indicating the presence of edges in our graph are positively related, because the only way through which these variables depend on each other is through the fact that the edges share ancestors. Our proof is nevertheless technical.

Preliminary lemmas

In this section we isolate the proof of two useful results that are not tied to the particular setting of our model. Lemma 6.2. Let X = (X 1 , . . . , X N ) be a vector of Bernoulli variables. The distribution of X is uniquely characterized by the quantities

p I = E i∈I X i and q I = E   i∈I X i j∈I c (1 -X j )  
where the empty product is understood to be 1.

Clearly, the distribution of X is fully specified by (q I ). Now observe that, by the inclusion-exclusion principle,

q I = J⊃I (-1) |J|-|I| p J ,
which terminates the proof. Lemma 6.3. Let X 1 , . . . , X N be independent random nondecreasing functions from [0, +∞[ to {0, 1} such that ∀i ∈ {1, . . . , N }, inf{t 0 : X i (t) = 1} < +∞ almost surely.

Let T be a non-negative random variable that is independent of (X 1 , . . . , X N ). Then, X 1 (T ), . . . , X N (T ) are positively related.

Proof. Pick i ∈ {1, . . . , N }. Now, let τ i = inf{t 0 : X i (t) = 1}. Assume without loss of generality that X i is left-continuous, so that {X i (T ) = 1} = {T > τ i }. Next, note that, ∀x, t 0, P(T > x, T > t) P(T > x)P(T > t) .

Integrating in t against the law of τ i , we find that

∀x 0, P(T > x | T > τ i ) P(T > x) .
This shows that T is stochastically dominated by T (i) , where T (i) has the law of T conditioned on {T > τ i }. As a result, there exists S, built on the same space as X 1 , . . . , X N and independent of (X j ) j =i , such that S ∼ T (i) and S T . For all j = i, let X (i) j = X j (S). Since X j is nondecreasing, X (i) j X j (T ), and since (X j ) j =i ⊥ ⊥ (T, τ i ), (X

(i) j ) j =i ∼ ((X j (T )) j =i | X i (T ) = 1)
. This shows that X 1 (T ), . . . , X N (T ) are positively related. Remark 6.4. Lemma 6.3 and its proof are easily adapted to the case where X 1 , . . . , X N are nonincreasing and such that inf{t 0 : X i (t) = 0} < +∞ almost surely. Lemma 6.3 (see also Remark 6.4), it follows that A 1 , . . . , A N +n are positively related.

We now pick any i n+1 2

= N + n and build a vector Y (i) that has the same law as (X | X i = 1) and satisfies Y (i) X .

Assume that M i = O . In that case, 1. By the induction hypothesis, there exists Y (M i ) that satisfies (3).

2. Since by A 1 , . . . , A N +n are positively related, ∃B (i) ∼ (A | A i = 1) such that B (i) A.

Note that A, B (i) , X and Y (M i ) are all built on the same space. Therefore, omitting the (M i ) and (i) superscripts to keep the notation light, we can set

Y i = 1 and, for k = i, Y k =    B k if M k = O Y M k B k otherwise. With this definition, ∀J ⊂ {1, . . . , N + n}, E   j∈J Y j   = E    j∈ J Y j    E   j∈J B j   , where J = {M j : j ∈ J, M j = O }. By hypothesis, E    j∈ J Y j    = E    j∈ J X j X M i = 1    = E X M i j∈ J X j E X M i Similarly, E   j∈J B j   = E   A i j∈J A j   E A i .
As a result,

E   j∈J Y j   = E X M i j∈ J X j E A i j∈J A j E(X M i )E(A i ) = E X M i A i j∈J X j E(X M i A i ) = E   j∈J X j X i = 1   By Lemma 6.2, this shows that Y ∼ (X | X i = 1).
If M i = O , we can no longer choose Y (M i ) . However, in that case, X i depends only on A i . Therefore, we set Y i = 1 and, for k = i,

Y k = X M k B k Remembering that X i = A i , we then check that E   j∈J Y j   = E j∈ J X j E A i j∈J A j E(A i ) = E   j∈J X j X i = 1   .
Finally, it is clear that, with both constructions of

Y (i) , Y (i) k X k .

Proof of Theorem 6.1

Applying Theorem A to |E n | = {ij} 1 {i↔j} and using the expressions in Table 1, we get

d TV |E n |, Poisson(λ n ) min 1, λ -1 n C n , with λ n = n(n-1) 2(rn+1) and C n = n(n -1)(n 2 r n + 2nr 2 n + nr n -2r 2 n + 3r n + 9) 2 (2 r n + 3)(r n + 3)(r n + 1) 2 . When r n = ω(n), C n = Θ n 4 r 3 n + n 3 r 2 n . Now, if r n > n(n-1) 2 -1, so that min{1, λ -1 n } = 1, we see that C n = Θ(n 3 /r 2 n ). If by contrast r n n(n-1) 2 -1 then λ -1 n C n = Θ(n/r n ).
In both cases, min{1, λ -1 n } C n goes to zero as n → +∞, proving the first part of Theorem 6.1.

The convergence of |En|-λn √ λn to the standard normal distribution is a classic consequence of the conjunction of d TV (|E n |, Poisson(λ n )) → 0 with λ n → +∞. See, e.g., [START_REF] Barbour | Oxford Studies in Probability[END_REF], page 17, where this is recovered as a consequence of inequality (1.39).

A. Proofs of Propositions 2.4 and 2.6 and of Lemma 2.5

A.1. Proof of Propositions 2.4 and 2.6 Proposition 2.4. Let (K t ) t 0 be a Kingman coalescent on V = {1, . . . , n}, and let π t (i) denote the block containing i in the corresponding partition at time t. Let the associated genealogy of pairs be the set G = t, {π t (i) π t (j)} : {ij} ∈ V (2) , t ∈ 0, T {ij} , where T {ij} = inf{t 0 : π t (i) = π t (j)}. Denote by L {ij} = t, {π t (i) π t (j)} : t ∈ 0, T {ij} the lineage of {ij} in this genealogy. Finally, let P • be a Poisson point process with constant intensity r n on G and let G = (V, E), where

E = {ij} ∈ V (2) : P • ∩ L {ij} = O . Then, G ∼ G n,rn .
Proof. Let (a t ) t 0 and P be as in Proposition 2.3, and let

G = t, {a t (i) a t (j)} : {ij} ∈ V (2) , t ∈ 0, T {ij} ,
where T {ij} = inf{t 0 : a t (i) = a t (j)}. Being essentially a finite union of intervals, G can be endowed with the Lebesgue measure.

As already suggested, conditional on (a t ) t 0 , P can be seen as a Poisson point process P with constant intensity r n on G . More specifically, P = t, {a t (i) a t (j)} : {ij} ∈ V (2) , t ∈ P {ij} .

With this formalism, writing L {ij} = t, {a t (i) a t (j)} : t ∈ 0, T {ij} for the lineage of {ij} in this genealogy, we see that P {ij} is isomorphic to P ∩ L {ij} . In particular,

P {ij} = O ⇐⇒ P ∩ L {ij} = O Now let (π t ) t 0 be defined by ∀i ∈ V, πt (i) = {j ∈ V : a t (j) = a t (i)} .
Then, ψ : (t, {a t (i) a t (j)}) → (t, {π t (i) πt (j)}) is a measure-preserving bijection from G to ψ(G ). Therefore, ψ(P ) is a Poisson point process with constant intensity r n on ψ(G ). Since (π t ) t 0 has the same law as (π t ) t 0 from the proposition, we conclude that ψ(G ), ψ(P ) ∼ (G, P • ) which terminates the proof.

prove that the tree encoded by (π t ) t 0 has the same topology as the Kingman coalescent tree. This follows directly from the standard fact that the shape of a Yule tree with n tips labeled uniformly at random with the integers from 1 to n is the same as that of the shape of a Kingman n-coalescent treenamely, the uniform law on the set of ranked tree shapes with n tips labeled by {1, . . . , n} (see e.g. [START_REF] Lambert | Probabilistic models for the (sub)tree(s) of life[END_REF]).

Alternatively, we can finish the proof as follows: working in backward time, for i = 1, . . . , n -1, consider the i-th coalescence and let U i denote the mother in the corresponding duplication in the construction of G r (n). Note that U i ∼ Uniform({1, . . . , n -i}), and that the coalescing blocks are then the block that contains Φ n (U i ) and the block that contains Φ n (n -i + 1). Let us record the information about the i first coalescences in the variable Λ i defined by Λ 0 = O and, for i 1,

Λ i = Φ n (n -k + 1), Φ n (U k ) k=1,...,i
. Thus, we have to show that, conditional on Λ i-1 , the block containing Φ n (ni + 1) and the block containing Φ n (U i ) are uniformly chosen. We proceed by induction. For i = 1, this is trivial. Now, for i > 1, observe that, conditional on Λ i-1 , the restriction of Φ n to

I i = {1, . . . , n} \ {Φ n (n), . . . , Φ n (n -i)}
is a uniform permutation on I i . As a result, {Φ n (n -i + 1), Φ n (U i )} is a uniformly chosen pair of elements of I i (note that the fact that U i is uniformly distributed on {1, . . . , n -i} is not necessary for this, but is needed to ensure that the restriction of Φ n to I i+1 remains uniform when conditioning on Λ i in the next step of the induction). Since each block contains exactly one element of I i , this terminates the proof.

A.2. Proof of Lemma 2.5 Lemma 2.5. Let S be a subset of V (2) . Conditional on the measure M , for any interval I ⊂ [0, +∞[ such that (i) For all {ij} ∈ S, ∀t ∈ I, a t (i) = a t (j).

(ii) For all {k } = {ij} in S, ∀t ∈ I, {a t (i), a t (j)} = {a t (k), a t ( )}, P {ij} ∩I, {ij} ∈ S, are independent Poisson point processes with rate r n on I.

Moreover, for any disjoint intervals I and J, (P {ij} ∩ I) {ij}∈S is independent of (P {ij} ∩ J) {ij}∈S .

Proof. For all t 0, define S t by S t = {{a t (i), a t (j)} : {ij} ∈ S} .

Set t 0 = inf I and let t 1 , . . . , t m-1 be the jump times of (S t ) t 0 on I, i.e. t p = inf t > t p-1 : S t = S t p-1 , p = 1, . . . , m -1.

Finally, set t m = sup I and, for p = 0, . . . , m -1, let I p = [t p , t p+1 [ and ãp = a tp , so that (ã p ) p∈{0,...,m} is the embedded chain of (a t ) t∈I . With this notation, for all {ij} ∈ S, P {ij} ∩ I = m-1 p=0 P {ãp(i), ãp(j)} ∩ I p , where for p = q, I p ∩ I q = O , and P {uv} , {uv} ∈ V (2) , are i.i.d. Poisson point processes on [0, +∞[ with rate r n . By assumption, for all p = 0, . . . , m -1, for all {ij} = {k } in S, ãp (i) = ãp (j), ãp (k) = ãp ( ) and {ã p (i), ãp (j)} = {ã p (k), ãp ( )}. This shows that (P {ãp(i),ãp(j)} ∩ I p ), {ij} ∈ S and p = 0, . . . , m -1, are i.i.d. Poisson point processes with rate r n on the corresponding intervals, proving the first part of the lemma.

The second assertion is proved similarly. Adapting the previous notation to work with two disjoint intervals I and J, i.e. letting (ã I p ) p∈{0,...,m I } be the embedded chain of (a t ) t∈I and (ã J p ) p∈{0,...,m J } that of (a t ) t∈J , for all {ij} ∈ S we write and the rank after which these inequalities hold is uniform in y, because the convergence of ( N n y + 1)/N n to y is.

P {ij} ∩ I =

C.3. Step 2

To identify the limit of f n , we reexpress it in terms of the gamma function. Using that Γ(z) = zΓ(z), by induction, Therefore, f n (x) can also be written We now turn to the specificities of the proofs of (i) and (ii).

C.3.1. Proof of (i)

In this subsection, r n → r > 0 and N n = n.

Limit of f n . Recall that

∀α ∈ R, Γ(n + α) Γ(n) ∼ n α .
Using this in (C.2), we see that, for all x ∈ [0, 1[,

P n (x) → (1 -x) 2r-1 .
Therefore, for all x ∈ [0, 1[,

f n (x) → 2r(2r + 1) x (1 -x) 2r-1 .
Noting that 2r(2r + 1) = 1/B(2, 2r), where B denotes the beta function, we can write f = lim n f n as

f : x → x(1 -x) 2r-1 B(2, 2r) 1 [0,1[ (x)
and we recognize the probability density function of the Beta(2, 2r) distribution.

Domination of (f n ). First note that, for all x ∈ [0, 1[,

1 n -1 + 2 r n nx i=1 n -i n -i + 2 r n -1 = 1 n -nx + 2 r n -1 nx i=1 n -i n -i + 2 r n ,
where the empty product is understood to be 1. Since 2 r n > 0, this enables us to write that, for all x ∈ [0, 1[,

f n (x) = n 2r (2r + 1) n + 2r (2r+1) 2 × nx + 1 n -1 + 2r × 1 n -nx + 2r -1 1 2r × nx i=1 n -i n -i + 2r 1 .
where, to avoid cluttering the expression, the n index of r n has been dropped. Since

C.3.2. Proof of (ii)

In this subsection, r n is both ω(1) and o(n), and N n = n/r n . For brevity, we will write k n for nx/r n . It should be noted that • k n is both ω(1) and o(n).

• k n r n /n → x uniformly in x on [0, +∞[. Limit of f n . In this paragraph, we will need Stirling's formula for the asymptotics of Γ: where

Γ(t +
∼ (n -1)(n -2 -k n + 2 r n ) (n -1 -k n )(n -2 + 2 r n ) ∼1 × e n-
Q n = (n -1) n-1 (n -2 -k n + 2 r n ) n-2-kn+2rn (n -1 -k n ) n-1-kn (n -2 + 2 r n ) n-2+2rn .
Let us show that Q n → e

Figure 1 :

 1 Figure1: The vertices of the graph represent populations and its edges denote interbreeding potential (that is, individuals from two linked populations could interbreed, if given the chance). Even with such perfect information, it is not obvious how to delineate "groups of potentially interbreeding populations that cannot interbreed with populations outside the group": should these correspond to connected components (on the left, in green), maximal complete subgraphs (on the right, in red), or be based on some other clustering method (middle, in blue)?

Figure 2 :

 2 Figure 2: An illustration of vertex duplication.Here, i duplicates and replaces j. After the duplication, j is linked to i and to each of its neighbors.

Figure 3 :

 3 Figure 3: A graphical summary of the main results established in the paper; D n is the degree of a fixed vertex, |E n | the number of edges, #CC n the number of connected components, and κ n the clique number.All equalities and inequalities are to be understood "asymptotically almost surely" (i.e. hold with probability that goes to 1 as n tends to infinity).

2 i 2 ,

 22 .i.d. exponential variables with parameter r n that are also independent of |I |. Since |I | ∼ Exp k-

  As a result, P(|E n | = 0) ∼ e -E(|En|) . Remark 3.11. Note that when r n = o(1), Var(D n ) ∼ r n n 2 /3 can go to infinity even though D n = n -1 with probability that goes to 1. Similarly, when r n = o(1/n), Var(|E n |) ∼ r n n 4 /18 and |E n | = n 2 a.a.s. Notably, D n = (n -1) -D n converges to 0 in probability while Var D n goes to infinity.

Conjecture 5. 4 .

 4 ∃α, β > 0 s.t. P(αr n #CC n βr n ) ----→ n→∞ 1.

Theorem 6 . 1 .

 61 Let |E n | be the number of edges of G n,rn . If r n = ω(n) then d TV |E n |, Poisson(λ n ) -----→ n→+∞ 0 ,where d TV stands for the total variation distance andλ n = E(|E n |) ∼ n 22rn . If in addition r n = o(n 2 ), then λ n → +∞ and as a result

  E i∈I X i , I ⊂ {1, . . . , N }, I = O Proof. For all I ⊂ {1, . . . , N }, I = O , let

m I - 1 p=0PFinally, since y Nny +1 Nn y + 1

 11 {ã I p (i), ãI p (j)} ∩ I p , andP {ij} ∩ J = m J -1 p=0 P {ã J p (i), ãJ p (j)} ∩ J p .We conclude the proof by noting that the families P {ã I p (i), ãI p (j)} ∩ I p {ij}∈S, p∈{0,...,m I } and P {ã J p (i), ãJ p (j)} ∩ J p {ij}∈S, p∈{0,...,m J } are independent, because the elements of these families are either deterministic (if, e.g, a I p (i) = a I p (j), in which case P {ã I p (i), ãI p (j)} = O ) or Poisson point processes on intervals that are disjoint from each of the intervals involved in the definition of the other family.C.2. Step 1For all x > 0, letf n (x) = N n P(D n = N n x ), so that ∀k ∈ N, P(D n = k) =(k+1)/Nn k/Nn f n (x) dx . If follows that F n (y) = ( Nny +1)/Nn 0 f n (x) dx . Nn and f n is non-negative, for any ε > 0, for n large enough, ∀y 0, y 0 f n (x) dx F n (y) y+ε 0 f n (x) dx ,

  i + 2 r n -1) = Γ(n + 2 r n -1) Γ(n -k + 2 r n -1).

  f n (x) = N n 2 r n (2 r n + 1) (n + 2 r n )(n -1 + 2 r n ) N n x + 1 × P n (x) , (C.1)whereP n (x) = Γ(n) Γ(n -N n x + 2 r n -1) Γ(n -N n x ) Γ(n + 2 r n -1) . (C.2)

  exists c such that, for all x ∈ [0, 1[ and n large enough,f n (x) c x Since f n is zero outside of [0, 1[, this shows that (f n ) is dominated by g : x → c x 1 [0,1[ (x).

2knrn n 2 =

 2 -2x : log Q n = (n -1) log(n -1) + (n -a + b) log(n -a + b) -(n -a) log(n -a) -(n -1 + b) log(n -1 + b)where, to avoid cluttering the text, we have written a for k n + 1 and b for 2 r n -1. Factorizing, we getlog Q n = n log (n -1)(n -a + b) (n -a)(n -1 + b) -a log n -a + b n -a +b log n -a + b n -1 + b -log n -1 n -1 + b . Now, (n -1)(n -a + b) (n -a)(n -1 + b) = 1 + (a -1)b n 2 -n + nb -na + a -ab ∼ o(1) so that n log (n -1)(n -a + b) (n -a)(n -1 + b) ∼ 2k n r n n → 2x

  τ 2 [, P {ij} and P {ik} are independent Poisson point processes with rate r n on [0, τ 1 [, and P {uv} is a Poisson point process with rate r n on [τ 1 , τ 2 [. Therefore,

  Cov 1 {i↔v} , 1 {j↔v} yields the desired expression. Let i, j, k and be four distinct vertices of G n,rn . We have Cov 1 {i↔j} ,

	Proposition 3.5.

  -N n x + 2 r n -1) Γ(n -N n x ) Γ(n + 2 r n -1)

		1) ∼	√	2πt	t t e t .
	Using this in Equation (C.2),
	P n (x) =	Γ(n) Γ(n

  1-kn e n-2+2rn e n-1 e n-2-kn+2rn

=1

× Q n

Acknowledgements

François Bienvenu thanks Jean-Jil Duchamps for helpful discussions. All authors thank the Center for Interdisciplinary Research in Biology (CIRB) for funding. Florence Débarre thanks the Agence Nationale de la Recherche for funding (grant ANR-14-ACHN-0003-01).

Stein-Chen coupling

Proposition 6.5. For any n 2 and r > 0, the random variables 1 {i↔j} for {ij} ∈ V (2) , which indicate the presence of edges in G n,r , are positively related.

Proof. We use the forward construction described in Section 2.3 and proceed by induction. To keep the notation light, throughout the rest of the proof we index the pairs of vertices of G r (n) = ({1, . . . , n}, E n ) by the integers from 1 to N = n 2 and, for i ∈ {1, . . . , N }, we let X i = 1 {i∈E n } . We also make consistent use of bold letters to denote vectors, i.e., given any family of random variables Z 1 , . . . , Z p , we write Z for (Z 1 , . . . , Z p ).

For n = 2, the family X i for i ∈ {1, . . . , n} consists of a single variable X 1 , so it is trivially positively related. Now assume that X 1 , . . . , X N are positively related in G r (n), i.e.

∀i N,

(ii) ∀k N, Y

Remember that G r (n+1) is obtained by (1) adding a vertex to G r (n) (which, without loss of generality, we label n+1) and linking it to a uniformly chosen vertex u n of G r (n) as well as to the neighbors of u n ; and (2) waiting for an exponential time T with parameter n 2 while removing each edge at constant rate r.

Formally, ∀k N + n, define the "mother" of k, M k ∈ {1, . . . , N } ∪ {O }, by

is the label of {u n , v}.

Letting X k = 1 {k∈E n+1 } , we then have

, where we recall that T ∼ Exp(N ) and, e 1 , . . . , e N +n are i.i.d. exponential variables with parameter r that are also independent of everything else.

Note that the random functions A k : t → 1 {e k >t} , k ∈ {1, . . . N + n} are nonincreasing and such that inf{t 0 : A k (t) = 0} < +∞ almost surely. By Proposition 2.6. For any r > 0, for any integer n 2,

Proof. First, let us give a Poissonian construction of (G † r (t)) t 0 . The edgeremoval events can be recovered from a collection P † = P † {ij} {ij}∈V (2) of i.i.d. Poisson point processes with rate r on R such that, if t ∈ P {ij} and there is an edge between i and j in G † r (t-), it is removed at time t. The duplication events induce a genealogy on the vertices of G r (n) that is independent of P † . Using a backward-time notation, let a † t (i) denote the ancestor of i at time (t n -t), i.e. t time-units before we reach G r (n). Observe that, by construction of G r (n),

Taking the relabeling of vertices into account, the genealogy on the vertices of G r (n) translates into a genealogy on the vertices of Φ n (G r (n)), where the ancestor āt function is given by āt

To keep only the relevant information about this genealogy, define

where T {ij} = inf{t 0 : πt (i) = πt (j)}. As before, let us denote by L{ij} = t, {π t (i) πt (j)} : t ∈ 0, T {ij} the lineage of {ij} in this genealogy. Finally, define

Then, conditional on Ḡ, P is a Poisson point process with constant intensity r n on Ḡ. Moreover,

Therefore, by Proposition 2.4, to conclude the proof it is sufficient to show that (π t ) t 0 has the same law as the corresponding process for a Kingman coalescent. By construction, the time to go from k to k -1 blocks in (π t ) t 0 is an exponential variable with parameter k 2 and thus it only remains to

n and D (j) n be the respective degrees of two fixed vertices i and j, and let |E n | be the number of edges of G n,rn . We have

and

The proof of Proposition 3.5 parallels that of Proposition 3.3, but this time the topology of the genealogy of the pairs of vertices has to be taken into account. Indeed, define

and let τ 1 < τ 2 < τ 3 be the times of coalescence in the genealogy of {i, j, k, }, i.e.

τ p = inf{t 0 : |S t | = 4 -p}, p = 1, 2, 3 .

Write

be the event that the m-th coalescence in the genealogy of {i, j, k, } involved the lineages of u and v (note that the third coalescence is uniquely determined by the first and the second, so we do not need

so that, conditionally on I 1 and I 2 , by Lemma 2.5,

By contrast, on A

(1)

and thus

Given a realization of the topology of the genealogy of the form A

(1)

{u 2 v 2 } , we can always express {i ↔ j, k ↔ } as a union of intersections of P {ij} and P {k } with I 1 , I 2 and I 3 . In total, there are 4 2 × 3 2 = 18 possible events A

(1)

{u 2 v 2 } , each having probability 1/18. This enables us to compute P(i ↔ j, k ↔ ), but in fact the calculations can be simplified by exploiting symmetries, such as the fact that {ij} and {k } are interchangeable. In the end, it suffices to consider four cases, as depicted in Figure B.6.

Figure B.6:

The four cases that we consider to compute P(i ↔ j, k ↔ ). Top, the "aggregated" genealogies of vertices and their probability. Each of these correspond to several genealogies on {i, j, k, }, which are obtained by labeling symbols in such a way that a pair of matching symbols has to correspond to either {ij} or {k }. For instance, C = (A

{ij} ) and therefore P(C) = 2/18. Similarly,

{jk} ) and P(A) = 4/18, etc. Bottom, the associated genealogy of the pairs and the corresponding conditional

Putting the pieces together, we find that

and Proposition 3.5 follows, since

B.2. Proof of Corollary 3.6

Corollary 3.6 is proved by standard calculations. First,

Remembering from Proposition 3.1 that Var(1 {i↔j} ) = r n /(1 + r n ) 2 and from Proposition 3.3 that Cov(1 {i↔k} , 1 {j↔k} ) = rn (1+rn) 2 (3+2 rn , and using Proposition 3.5, we find that

Finally, to compute Var(|E n |), we could do a similar calculation. However, it is easier to note that

As a result,

C. Proof of Theorem 4.2

In this section, we prove Theorem 4.2.

Theorem 4.2 (convergence of the rescaled degree).

(i) If r n → r > 0, then Dn n converges in distribution to a Beta(2, 2 r) random variable.

(ii) If r n is both ω [START_REF] Chung | Duplication models for biological networks[END_REF] and o(n), then Dn n/rn converges in distribution to a size-biased exponential variable with parameter 2.

(iii) If 2 r n /n → ρ > 0, then D n + 1 converges in distribution to a size-biased geometric variable with parameter ρ/(1 + ρ).

The proof of (iii) is immediate: indeed, by Theorem 4.1,

If 2 r n /n → ρ, then for any fixed k this goes to

as n → +∞.

C.1. Outline of the proof

To prove (i) and (ii), we show the pointwise convergence of the cumulative distribution function F n of the rescaled degree. To do so, in both cases, 1. We show that, for any ε > 0, for n large enough, ∀y 0,

for some function f n to be introduced later. 2. We identify the limit of f n as a classical probability density f , and use dominated convergence to conclude that ∀y 0,

In order to factorize as much of the reasoning as possible, we introduce the rescaling factor N n :

• When r n → r, i.e. when we want to prove (i), N n = n.

• When r n is both ω(1) and o(n), i.e. when we want to prove (ii), N n = n/r n .

Thus, in both cases the rescaled degree is D n /N n and its cumulative distribution function is

Similarly,

and, finally, -log n-1 n-1+b → 0. Putting the pieces together, log Q n → -2x .

Having done that, we note that

Plugging these results in Equation (C.1), we see that

and we recognize the probability density function of a size-biased exponential distribution with parameter 2.

Domination of (f n ). Recall that, since N n = n/r n , for all x ∈ [0, 1[,

Next, note that, for all i,

Because r n = ω(1), for all ε > 0, 2 r n -1 (1 -ε)2 r n for n large enough. Similarly, since r n = o(n),