Bruno Schapira
email: bruno.schapira@univ-amu.fr

Daniel Valesin

Exponential rate for the contact process extinction time

We consider the extinction time of the contact process on increasing sequences of finite graphs obtained from a variety of random graph models. Under the assumption that the infection rate is above the critical value for the process on the integer line, in each case we prove that the logarithm of the extinction time divided by the size of the graph converges in probability to a (model-dependent) positive constant. The graphs we treat include various percolation models on increasing boxes of Z d or R d in their supercritical or percolative regimes (Bernoulli bond and site percolation, the occupied and vacant sets of random interlacements, excursion sets of the Gaussian free field, random geometric graphs) as well as supercritical Galton-Watson trees grown up to finite generations.

Introduction

In this paper, continuing our earlier work [START_REF] Schapira | Extinction time for the contact process on general graphs[END_REF], we present a robust method allowing to prove the existence of an exponential rate of convergence of the contact process extinction time on various models of random graphs, when the infection parameter is large enough.

In the contact process, each vertex of a graph is at any point in time either healthy (state 0) or infected (state 1). The continuous-time dynamics is defined by the specification that infected vertices become healthy with rate one, and transmit the infection to each neighboring vertex with rate λ > 0. We refer to [START_REF] Liggett | Stochastic interacting systems: contact, voter and exclusion processes[END_REF] for a standard reference on the contact process.

The configuration in which all vertices are healthy is absorbing for the dynamics, and in finite graphs it is reached with probability one. In certain situations, the dynamics stays active for a very long time before reaching this absorbing state, and this behavior can be understood as an instance of metastability. To be more precise, let τ G be the hitting time of the absorbing, "all-healthy" (or "empty") state when the process is started from the configuration in which all vertices are infected. The distribution of τ G depends on the graph G and the infection rate λ. One typically considers a sequence of graphs (G n ) (which could be deterministic and nested, or an increasing sequence of random graphs from the same random graph model), fixes λ > 0 and studies the asymptotic behavior of τ Gn . For a variety of sequences (G n ), it is known that, if λ is large enough, then there exists c > 0 such that

P (τ Gn > exp{c|G n |}) n→∞ ---→ 1, (1.1)
where for any graph G we let |G| denote its number of vertices (see for instance Theorem 3.9 in Section I.3 of [START_REF] Liggett | Stochastic interacting systems: contact, voter and exclusion processes[END_REF], Theorem 1.3 in [START_REF] Mountford | Exponential extinction time of the contact process on finite graphs[END_REF] and Theorem 1.5 in [START_REF] Cranston | The contact process on finite trees revisited[END_REF]). Evidently, the meaning of "λ large enough" depends on the chosen sequence of graphs. For instance, for certain random graphs with power law degree distributions, λ > 0 suffices, whereas for boxes of Z d , one must take λ larger than λ c (Z d ), the critical value for the d-dimensional contact process, defined as the supremum of values of λ for which the process on Z d started from a single infection almost surely reaches the empty configuration. Recently, in [START_REF] Mountford | Exponential extinction time of the contact process on finite graphs[END_REF] and [START_REF] Schapira | Extinction time for the contact process on general graphs[END_REF], it has been established that for values of the infection rate above λ c (Z) -the critical value of the one-dimensional contact process -, statement (1.1) (or at least a slightly weaker result in which exp{c|G n |} is replaced by exp{c|G n |/(log |G n |) 1+ε }) holds for arbitrary sequences of connected graphs (G n ) with |G n | → ∞.

A natural refinement of (1.1) is the statement that 1 |Gn| • log τ Gn converges (in some sense) to something positive as n → ∞. The first result of this kind was given in [START_REF] Durrett | The contact process on a finite set[END_REF]: there it is proved that for λ > λ c (Z) and (G n ) given by line segments of length n, there exists a constant γ ∈ (0, ∞) such that

1 |G n | • log(τ Gn ) n→∞ ---→ γ in probability. (1.2)
This was generalized in [START_REF] Mountford | Existence of a constant for finite system extinction[END_REF] to boxes of Z d (with λ > λ c (Z d )), and the same result was proved in [START_REF] Cranston | The contact process on finite trees revisited[END_REF] for d-regular trees truncated at height n (with λ larger than the upper critical value of the contact process on the infinite d-regular tree; see [START_REF] Liggett | Stochastic interacting systems: contact, voter and exclusion processes[END_REF] for the definition). Our goal in this paper is to establish results of the type (1.2) for sequences (G n ) obtained from random graph models. As we rely on techniques developed in our previous work [START_REF] Schapira | Extinction time for the contact process on general graphs[END_REF],

where the assumption λ > λ c (Z) was crucial, we also need this assumption here, though we do not believe it to be sharp in any of the settings we consider. This being said, our method is quite robust, and depends essentially on the graphs G n possessing some kind of self-similar structure which allows for a recursive decomposition.

Let us list the choices of sequences of random graphs (G n ) covered by our main theorem.

For now we only refer to these random graph models by their names and the assumptions we place on their defining parameters; in Sections 3 and 4, we will present each model in detail. We abuse notation and denote by B n both the set {-n, . . . , n -

1} d ⊆ Z d and the set [-n, n] d ⊆ R d .
1. For d ≥ 2, perform supercritical Bernoulli bond percolation on B n and let G n be the resulting maximal component (that is, the connected component with largest cardinality).

2. For d ≥ 3, perform supercritical Bernoulli site percolation on B n and let G n be the resulting maximal component. Theorem 1.1. For any λ > λ c (Z) and any of the choices of (G n ) listed above, there exists a (deterministic) constant γ ∈ (0, ∞) such that the extinction time of the contact process on G n with rate λ and started from full occupancy satisfies:

1 |G n | • log τ Gn n→∞ ---→ γ in probability.
Our main tool to prove Theorem 1.1 is Proposition 2.3 below, which was proved in our previous paper [START_REF] Schapira | Extinction time for the contact process on general graphs[END_REF]; it states that on any (deterministic) graph, and for any λ larger than λ c (Z), the expected extinction time is larger than the product of the expected extinction times on any collection of disjoint connected subgraphs, up to some correction term. This result allows us to use a block decomposition in the same vein as in the proof of Mountford [START_REF] Mountford | Existence of a constant for finite system extinction[END_REF] in the case of boxes of Z d . The main graph property which is required is as already mentioned some kind of self-similarity, namely that at each scale n, the graph G n can be decomposed as a union of subgraphs, which are copies (in law) of the original graph at a smaller scale. Few results are available for the contact process on random graphs obtained from percolationtype models; see for instance [START_REF] Bertacchi | Contact and voter processes on the infinite percolation cluster as models of host-symbiont interactions[END_REF][START_REF] Chen | The complete convergence theorem holds for contact processes on open clusters of Z d × Z +[END_REF][START_REF] Xue | Critical value for contact processes on clusters of oriented bond percolation[END_REF] and references therein. The contact process on the supercritical random geometric graph has also been previously considered by Ménard and Singh [START_REF] Ménard | Percolation by cumulative merging and phase transition for the contact process on random graphs[END_REF], who proved that the critical infection rate is positive, and by Can [START_REF] Can | Super-exponential extinction time of the contact process on random geometric graphs[END_REF] who obtained sharp bounds on the expected value of the extinction time on G n when the radius of connectedness goes to infinity. The contact process on Galton-Watson trees has been studied by in Pemantle [START_REF] Pemantle | The contact process on trees[END_REF].

Finally, let us mention that for several important random graph models, it would be interesting to obtain results of the form (1.2), but our present techniques are not applicable (at least not directly). These include the configuration model, the Erdós-Renyi random graph, random planar maps, and Delaunay triangulations of the plane (provided that in each case, the parameters defining the graph and the value of λ yield a regime of exponentially large extinction time). The paper is organized as follows. In the next section we gather known important results for the contact process. In Section 3, we consider all the percolation-type models we treat (models 1 to 6 in the list above), starting with those which are subgraphs of Z d . In this case, very similarly to [START_REF] Drewitz | On chemical distances and shape theorems in percolation models with long-range correlations[END_REF] and [START_REF] Sapozhnikov | Random walks on infinite percolation clusters in models with long-range correlations[END_REF], we list a number of general conditions under which the conclusion of Theorem 1.1 hold true, and which are known to be satisfied in all the models mentioned above. The case of Galton-Watson trees is treated separately in the last section, as the proof in this setting presents some substantial differences.

Notation and conventions for graphs

We use the convention that a graph G = (V, E) is a collection of vertices V and edges E between vertices, and we assume that graphs are undirected, with no loops, and no multiple edges. They are also assumed to be locally finite, meaning that any vertex has only finitely many neighbors (or edges emanating from this vertex). We denote by |V | and |E| respectively the number of vertices and edges in the graph, and use the convention that |G| also denotes the number of vertices in the graph.

If G = (V, E) and V ⊆ V , the subgraph of G induced by V is the graph G = (V , E ),
where E is the set of edges of E with both extremities in V . Finally, we use the notation Z d to refer both to the set of d-dimensional vectors with integer coordinates, and to the graph with these vectors are vertices, and edges connecting vectors at 1 -distance one from each other.

Prelimaries on the contact process on finite graphs

For a full account of the contact process on Z d and other locally finite graphs, we refer the reader to the book of Liggett [START_REF] Liggett | Stochastic interacting systems: contact, voter and exclusion processes[END_REF]. Here we merely recall some bounds on the expected extinction time of the process on finite graphs. We start with the following basic fact, which provides a general upper bound, and indicate its short proof for the reader's convenience.

Lemma 2.1. For any λ > 0, and any finite connected graph G = (V, E),

E[τ G ] ≤ exp(|V | + 2λ|E|).
Proof. The probability that extinction occurs before time 1 is larger than the probability that all vertices recover and no transmission occurs before time 1, which is at least exp(-|V |-2λ|E|).

Then, τ G is stochastically dominated by a random variable following the geometric distribution with parameter exp(-|V | -2λ|E|); the expectation of this random variable is exp(|V | + 2λ|E|).

On the other hand, general lower bounds were provided in [START_REF] Mountford | Exponential extinction time of the contact process on finite graphs[END_REF] and [START_REF] Schapira | Extinction time for the contact process on general graphs[END_REF]:

Theorem 2.2. Assume λ > λ c (Z).
[20] For any d > 0, there exists c > 0 such that for any connected graph G with degrees bounded by d, we have

E[τ G ] > exp{c|G|}.
[26] For any ε > 0, there exists ĉ > 0 such that for any connected graph G with at least two vertices, we have

E[τ G ] > exp ĉ|G| (log |G|) 1+ε .
Next, let us recall the general result from [START_REF] Schapira | Extinction time for the contact process on general graphs[END_REF] alluded to in the introduction, which is also our main tool.

Proposition 2.3 ([26], Proposition 2.9)

. There exists a constant c 0 > 0, such that for any finite connected graph G and any λ > λ c (Z), the following holds: for any N ≥ 1, and any finite collection of disjoint connected subgraphs G 1 , . . . , G N ⊆ G, one has

E[τ G ] ≥ c 0 (2|G| 3 ) N +1 • N i=1 E[τ G i ].
We note that this result was stated and proved for trees only in [START_REF] Schapira | Extinction time for the contact process on general graphs[END_REF], but the identical statement, with the same proof, works for general graphs.

Finally, the following is useful in turning bounds on expectations into bounds on probabilities: Lemma 2.4 ([20], Lemma 4.5). For any t > 0,

P (τ G ≤ t) ≤ t E[τ G ] .
3 Percolation-type models

General lattice model

We consider here random graphs obtained from percolation-type models on Z d (models 1-5 in the list before Theorem 1.1). Rather than treating model by model, we will be able to treat them all at once by following an approach similar of that of [START_REF] Drewitz | On chemical distances and shape theorems in percolation models with long-range correlations[END_REF] and [START_REF] Sapozhnikov | Random walks on infinite percolation clusters in models with long-range correlations[END_REF]. That is, we will first present a list of four properties to be satisfied by a probability measure P under which a random subgraph G of Z d is defined. Next, letting G n be the maximal component of G ∩ B n , we will prove the statement of Theorem 1.1 by only making use of the mentioned properties. Finally, at the end of this subsection, we will give formal definitions of the aforementioned five models (Bernoulli bond and site percolation, occupied and vacant set of random interlacements, excursion set of the Gaussian free field), and provide references that show that each model satisfies the four properties (at least for some choices of their defining parameters).

We let Ω = {0, 1} S , where S is either the set of vertices or edges of Z d (as usual, elements of Ω can be identified with subsets of the vertex (or edge) set of Z d ). In the percolation terminology, given ω ∈ Ω, a vertex (or edge) is said to be open if its ω-value is one, and to be closed otherwise. A configuration ω ∈ Ω then defines a subgraph G = G(ω) of Z d in the standard manner. That is, if S is the set of vertices of Z d , then G is the subgraph of Z d induced by {x : ω x = 1}, and if S is a set of edges, then G has all the vertices of Z d and the set of edges {e : ω e = 1}. (The second situation is only needed to include the case of Bernoulli bond percolation). We endow Ω with the σ-algebra generated by the coordinate maps, and note that any probability measure P on Ω then defines a random subgraph G of Z d .

Our two first assumptions on P are the following: P is translation invariant and ergodic with respect to spatial shifts of Z d Our next assumption ensures that with high probability, connected components of G ∩ B n distinct from G n have small diameter. So under (3.2), we consider there exists a constant ∆ > 0, such that for all n large enough,

P   G ∞ ∩ B n = ∅, and any two connected components of G ∩ B n with diameter larger than n 10 are connected in B 2n   ≥ 1 -exp(-(log n) 1+∆ ). (3.3)
Note that when the above assumption holds, one can easily derive the following useful fact: for all n large enough,

P any two connected components of G ∞ ∩ B n are connected in B 4n ≥ 1 -exp(-(log 2n) 1+∆ ). (3.4)
Indeed, any connected component of G ∞ ∩ B 2n intersecting B n necessarily has a diameter larger than n, so that one can apply (3.3) in B 2n . Let us also mention that for our purposes this hypothesis (3.3) could be weakened, for instance a super-polynomial decay as in Section 5 of [START_REF] Sznitman | Disconnection and level-set percolation for the Gaussian free field[END_REF] would be sufficient.

Finally our last assumption gives a bound on the decay of correlations for events depending on the configurations inside two disjoint boxes, as the distance between the two boxes diverges. Note that we have not tried to find an optimal condition for the proof here, and so we assume that the decay of correlations is at least polynomially fast. Indeed this is good enough for the proof, and it is satisfied by all the models of interest to us here. We let • be the Euclidean norm. Then we consider there exists a constant C 0 such that for any x ∈ Z d , and any events A and B depending only on the configurations inside B n and x + B n respectively, one has:

|Cov(1 A , 1 B )| ≤ C 0 ( n 2 x ) d-2 .
(3.5)

We restate now Theorem 1.1 in this general setting.

3). Then with the above notation, for any ε ∈ (0, 1) there exists δ > 0 such that for n large enough the following holds with probability higher than 1 -exp{-(log n) 1+δ }: ) and a union bound, there exists δ > 0 such that, for n large enough, the following conditions are satisfied with probability at least 1 -exp{-(log n) 1+δ }:

G ∞ ∩ B n
• for any x ∈ B n , the graph G ∞ ∩ (x + B 2n ) has a unique component C (x) that crosses x + (B n \B n/4 ); • for any x ∈ B n , any connected component of G ∩ (x + B n ) with diameter larger than n /10 is connected to C(x) in x + B 2 n ;
• for any x, y ∈ B n with x ∼ y, we have that C (x) and C (y) are connected together in

G ∞ ∩ (x + B 4 n ).
In particular, all the graphs C (x) for x ∈ B n- • C has diameter smaller than n (so |C | ≤ n ε );

• C is contained in B n \B n-9 n ⊆ B n \B n-n ε (so |C | ≤ 2d • n d-1 • 9 n ).
This also shows that C is the unique component of G ∩ B n with cardinality above n d-ε , completing the proof.

As a corollary, one obtains the following result, interesting in itself.

Corollary 3.3. Under the hypotheses of Proposition 3.2,

|G n | |B n | n→∞ ---→ (P) θ := P(0 ∈ G ∞ ). (3.9)
Proof. Fix ε ∈ (0, 1). Also fix n ∈ N and assume that (3.7) and (3.8) hold. Then,

G n is a component of G ∞ ∩ B n . If C is any component of G ∩ B n distinct from G n , then we must have either |C | < n ε or C ⊆ B n \B n-n ε . If we also assume C is a component of G ∞ ∩ B n , it must be the case that C intersects the boundary B n \B n-1 (since G ∞ is connected), so we necessarily have C ⊆ B n \B n-n ε . Then, |G ∞ ∩ B n | -|G n | = C component of G∞∩Bn: C =Gn |C | ≤ |B n \B n-n ε | = o(n d ).
The desired result now follows from noting that, by ergodicity,

|G ∞ ∩ B n |/|B n | converges in probability to θ as n → ∞.
We are now in position give the proof of Theorem 3.1.

Proof of Theorem 3.1. Define

X n := 1 n d log E[τ Gn | G n ] (3.10) and γ := lim sup n→∞ E[X n ]. (3.11)
By Lemma 2.1, the (X n ) n≥1 are bounded random variables, and thus γ is finite. We claim that it is also positive. Indeed by Theorem 2.2 (noting that G n is by definition connected and has degrees bounded by 2d), for n large enough,

E[X n ] ≥ 1 n d • E log E[τ n | G n ] • 1 |G n | > θ 2 |B n | ≥ 1 n d • cθ(2n) d 2 • P |G n | > θ 2 |B n | (3.9) ≥ cθ2 d-2 .
(3.12)

Now we prove that (X n ) n≥0 converges in probability to γ. Fix ε > 0, and let n 0 be such that E

[X n 0 ] ≥ γ -ε/2.
In what follows we will also assume that n 0 is large enough (depending on ε). We now write for k ∈ N,

n k = (n 0 ) 3 k , ε k = 2 -k ε, E k = k i=1 ε i .
We proceed by induction. Fix k ≥ 0, and assume that we have already proved that

E[X n k ] ≥ γ -E k+1 . (3.13)
Then we show that for any n ∈ [n k+1 , n k+2 ], we have

P (X n ≤ γ -E k+1 -ε k+3 ) < ε k+3 γ , so E[X n ] > ( γ -E k+1 -ε k+3 ) • 1 - ε k+3 γ ≥ γ -E k+2 . ( 3
E[τ Gn | G n ] ≥ c 0 (2|G n |) 3N • N i=1 E[τ G (i) | G (i) ], so that, with X (i) := (1/n d k ) log E τ G (i) | G (i) , X n • 1 A ≥ n k n d • N i=1 X (i) - CN log(|G n |) n d • 1 A , (3.16)
for some constant C > 0. Now note that, by the definition of N ,

CN log(|G n |) n d ≤ Cdn d log(2n) n d k • n d ≤ ε k+5 ,
at least for n 0 large enough. Moreover, Lemma 2.1 implies that all the X (i) are bounded. Therefore,

1 N - n k n d N i=1 X (i) ≤ C 1 1 -N n k n d ≤ C 2 1 - n -2n k n k • n k n ≤ ε k+5 ,
for some positive constants C 1 and C 2 . Using these estimates in (3.16) we get

X n • 1 A ≥ 1 N • N i=1 X (i) -ε k+4 • 1 A .
Consequently,

P(X n ≤ γ -E k+1 -ε k+3 ) ≤ P(A c ) + P 1 N • N i=1 X (i) ≤ γ -E k+1 -ε k+4 . (3.17)
We now apply Proposition 3.2 in each of the boxes and deduce that for some δ > 0, with probability at least 1 -exp{-(log n) 1+δ }, all the G (i) have cardinality larger than n d-1 k and are subgraphs of G ∞ . Note also that the G (i) are by definition at distance at least n k from the boundary of B n , since they all belong to B n-n k , and by hypothesis one has n k ≥ n 1/9 . Thus by applying again Proposition 3.2 in the box B n , we get that for n 0 large enough, and for some δ > 0,

P(A c ) ≤ exp{-(log n) 1+δ } ≤ ε k+4 γ . (3.18)
We now bound the second term in (3.17) using the hypothesis (3.5). To this end we discretize the random variables (X (i) ) i≤N , which we recall are bounded by a constant C 1 > 0. Set

X (i) := ε k+5 C 1 /ε k+5 =0 1{X (i) ≥ ε k+5 }. Note that X (i) ≤ X (i) ≤ X (i) + ε k+5 ,
and that by (3.1), all the (X (i) ) i≤N have the same distribution as X n k . Therefore (3.13) gives, using also Chebyshev's inequality,

P 1 N • N i=1 X (i) ≤ γ -E k+1 -ε k+4 (3.13) ≤ P 1 N N i=1 X (i) -E[ X (i) ] ≤ -ε k+5 ≤ 1 N 2 ε 2 k+5 • 1≤i,j≤N |Cov( X (i) , X (j) )|. (3.19)
We now bound the covariances using (3.5). Note first that by using the bilinearity of the covariance and (3.5), we get that for all i, j,

|Cov( X (i) , X (j) )| ≤ C 0 C 2 1 n 2(d-2) k d(i, j) d-2 ,
where by d(i, j) we mean the distance between the two boxes containing G (i) and G (j) . We deduce that for any fixed i ≤ N , for some constant C > 0,

1≤j≤N |Cov( X (i) , X (j) )| ≤ Cn d-2 k • ( n n k ) 2 .
Summing next over i, and using that n ≥ n 3 k , we obtain

1 N 2 1≤i,j≤N |Cov( X (i) , X (j) )| ≤ C • n d-2 k N n n k 2 ≤ C • 1 n d-2 k .
Combining this with (3.19) gives, for n 0 large enough,

P 1 N • N i=1 X (i) ≤ γ -E k+1 -ε k+4 ≤ ε k+4 γ .
Together with (3.17) and (3.18) this proves (3.14).

One can then conclude that (X n ) n≥0 converges in probability to γ using a general argument, which we recall for completeness. For n ≥ 1 and ε > 0, let ϕ n (ε) := P(X n < γ -ε) + ε. For n large enough we have

γ + ε ≥ E[X n ] ≥ ( γ + ϕ n (ε)) • P X n > γ + ϕ n (ε) + ( γ -ε) • P γ -ε ≤ X n ≤ γ + ϕ n (ε) ≥ γ(1 -ϕ n (ε)) + ϕ n (ε) • P X n > γ + ϕ n (ε) -ε,
which gives

P X n > γ + ϕ n (ε) ≤ 2ε(ϕ n (ε)) -1/2 + γ(ϕ n (ε)) 1/2 .
Together with (3.14) this gives the convergence in probability of X n towards γ.

The proof of the theorem is almost finished now. Fix ε > 0. On the one hand, the Markov inequality entails

P 1 n d log τ Gn ≥ γ + ε ≤ P X n > γ + ε 2 + e -( γ+ε)n d • E τ Gn 1 E[τ Gn | G] ≤ e ( γ+ε/2)n d ≤ P X n > γ + ε 2 + exp - ε 2 n d .
On the other hand, Lemma 2.4 gives

P 1 n d log τ Gn ≤ γ -ε ≤ P X n ≤ γ - ε 2 + e ( γ-ε)n d • E 1 E[τ Gn | G] 1 E[τ Gn | G] ≥ e ( γ-ε/2)n d ≤ P X n ≤ γ - ε 2 + exp - ε 2 n d .
Together with (3.9) this completes the proof of (3.6) with γ = γ/θ. The proof of the theorem is now complete.

Description of lattice models and verification of assumptions

As mentioned earlier, we now give definitions of five models that fit in the above framework, and indicate references where proofs of all the hypotheses of the theorem are given for each of them.

Supercritical Bernoulli bond percolation, d ≥ 2. This is the basic percolation model defined by the prescription that each edge of Z d is declared open with probability p and closed with probability 1 -p, independently for all edges, where p ∈ [0, 1]. It is thoroughly studied in the standard reference of Grimmett [14]; there it is shown that there exists p c (d) ∈ (0, 1) such that there is no infinite component if p < p c and there is a unique infinite component if p > p c .

Here we assume that p > p c . Proofs of (3.1) and (3.2) can be found in [14]. Condition (3.3) is proved in [START_REF] Pisztora | Surface order large deviations for Ising, Potts and percolation models[END_REF] in dimension d ≥ 3, and in [START_REF] Couronné | Surface order large deviations for 2D FK-percolation and Potts models[END_REF] for d = 2. Condition (3.5) follows readily from independence.

Supercritical Bernoulli site percolation, d ≥ 3. This is defined as above, except that vertices, rather than edges, are declared to be open of closed. Site percolation is also covered in the book [14]. Again, a critical value p c (d) ∈ (0, 1) separates a non-percolative phase from a phase where there is almost surely a unique infinite component. Here we assume that d ≥ 3 and p > p c (d). All the references and observations provided above for supercritical bond percolation are also valid for supercritical site percolation, except that (3.3) has not been established for the case d = 2, which is why we exclude it.

Occupied set of random interlacements, d ≥ 3. The model of random interlacements has been introduced by Sznitman in [START_REF] Sznitman | Vacant set of random interlacements and percolation[END_REF], and detailed expositions are available in [START_REF] Černý | From random walk trajectories to random interlacements[END_REF] and [START_REF] Drewitz | An introduction to random interlacements[END_REF]. It arises as a local limit of the trace of a simple random walk on a d-dimensional torus ran for an amount of time proportional to the volume of the torus. The proportionality constant u > 0 and the dimension d are the two parameters of the model; as the random walk is required embedded in R d is defined as the supremum of the ∞ -distance between vertices of the graph. This is not to be confused with the graph-theoretic diameter. Second, consider the modified version of the random geometric graph on R d such that a vertex is artificially placed at the origin (and other vertices and edges are placed as before); let θ R be the probability that the vertex at the origin is in an infinite component. Then (see Chapter 9 of [START_REF] Penrose | Random geometric graphs[END_REF]), we have θ R > 0 if and only if R > R c .

Proposition 3.4. For any d ≥ 2, R > R c and ε > 0, there exists δ > 0 such that for n large enough the following holds with probability larger than 1 -exp{-(log n) 1+δ }. The maximal component G n of the random geometric graph with parameter R on B n has metric diameter larger than n and

|G n |/(2n) d ∈ ((1 -ε) • θ R , (1 + ε) • θ R ).
Moreover, any other component has metric diameter smaller than (log n) 2 and cardinality smaller than εn d .

Proof. This follows from putting together Proposition 10.13, Theorem 10.19, and Theorem 10.20 in [START_REF] Penrose | Random geometric graphs[END_REF].

Note that Proposition 3.4 immediately gives

|G n | (2n) d n→∞ ---→ (P) θ R .
We define X n and γ as in (3.10) and (3.11). We would now like to show that γ > 0. However, unlike the lattice models considered earlier, here no universal upper bound is available for the degrees in G n . To remedy this, we use the following result.

Lemma 3.5. For any d ≥ 2 there exists K > 0 such that G n has a spanning tree with degrees bounded by K.

The above statement for d = 2 (and K = 5) is Lemma 2.12 in [START_REF] Beveridge | Makerbreaker games on random geometric graphs[END_REF]. The proof easily generalizes to any dimension (with dimension-dependent K). The idea is to take the spanning tree of G n in which the sum of the lengths of the edges is the smallest possible, and to show that this tree has degrees bounded by a dimension-dependent constant. For this, one argues by contradiction: if the tree had a vertex whose degree was too large, then the edges in the ball of radius R around this vertex could be rearranged so as to produce a spanning tree with smaller total edge length.

With this result at hand, we prove that γ is positive with the same computation as in (3.12), replacing G n by its spanning tree with bounded degrees. From this point on, the proof of Theorem 1.1 for (G n ) proceeds in the same way as the one we gave for the lattice models; the only difference is that, in giving a lower bound to the probability of the event A defined in (3.15), we use Proposition 3.4 instead of Proposition 3.2 (also note that the computation involving covariances is unnecessary in this case, since graphs inside disjoint boxes are independent).

Galton-Watson trees

In this section we consider a supercritical Galton-Watson tree with offspring distribution having a finite second moment. This means that if ν is the law of the number of individuals at the first generation of the tree, then m := k∈N kν(k) is larger than one, and σ 2 := k∈N k 2 ν(k) is finite. We let Z 0 = 0 and for n ≥ 1, we let Z n be the number of individuals at generation (height) n, and let G n be the subtree of individuals belonging to the first n generations (including the root, which is in generation zero). In particular Letting v n = 1 + m + • • • m n , it is well known that there exists a nonnegative random variable

|G n | = 1 + Z 1 + • • • + Z n . We
W ∞ satisfying Z n m n → W ∞ , |G n | v n → W ∞ ,
E |G n | v n -W ∞ 2 1/2 ≤ n i=0 m i v n E Z i m i -W ∞ 2 1/2 n→∞ ---→ 0.
We now define

Y n = log E[τ Gn | G n ] m n , X n = log E[τ Gn | G n ] |G n | , and γ := lim sup n→∞ E[Y n ].
We first show the following:

Claim 4.1. E[Y n ] n→∞ ---→ γ > 0.
Proof. On {Z 1 = k} for k > 0, let G (1) , . . . , G (k) denote the subtrees that descend from the vertices in the first generation. We have using Proposition 2.3 that

log E[τ Gn | G n ] ≥ Z 1 i=1 log E[τ G (i) | G n ] -CZ 1 log |G n |,
with the understanding that the right-hand side is zero when Z 1 = 0. Hence,

E[Y n ] ≥ m n-1 m n E Z 1 i=1 log E[τ G (i) | G n ] m n-1 -C • E Z 1 log |G n | v n = E[Y n-1 ] -C • E Z 1 log |G n | m n .
Using Cauchy-Schwarz inequality and the fact that log

2 (k) < √ k for k large enough, E [Z 1 log |G n |] ≤ E[Z 2 1 ] • E[log 2 |G n |] 1/2 ≤ E[Z 2 1 ] 1/2 • log 2 (m n 2 ) + E |G n | • 1{|G n | ≥ m n 2 } 1/2 ≤ E[Z 2 1 ] 1/2 • n 4 log 2 (m) + E[|G n |] • P |G n | ≥ m n 2 1/2 1/2 ≤ E[Z 2 1 ] 1/2 • n 4 log 2 (m) + v 2 n /m n 2 1/2 1/2 ≤ n 3 ,
if n is large enough. We thus have, for n large enough,

E[Y n ] ≥ E[Y n-1 ] - n 4 m n . (4.3)
Next, using (4.1) and (4.2), we can choose ε > 0 such that, for n large enough,

P(εm n < |G n | < m n /ε) > ε.
Then, if n is large, using Theorem 2.2,

E[Y n ] ≥ E log E[τ Gn | G n ] m n • 1{εm n < |G n | < m n /ε} ≥ 1 m n E log exp ĉ|G n | log 2 |G n | • 1{εm n < |G n | < m n /ε} ≥ c n 2 , (4.4)
for some constant c > 0. Now, (4.3) and (4.4) can be combined to first give γ > 0, and then again to give

E[Y n ] n→∞ ---→ γ. Define next γ = m -1 m • γ. Claim 4.2. For all ε > 0, P(X n < γ -ε | Z n = 0) n→∞ ---→ 0 and P(X n < γ -ε | Surv) n→∞ ---→ 0.
Proof. Since P({Z n = 0}\Surv) n→∞ ---→ 0, any of the above convergences follows from the other, so we will prove the first one. For n ∈ N, we write n = n/2 , n = n -n .

On Z n = k > 0, let G (1) , . . . , G (k) denote the subtrees that descend from the vertices in generation n . On {Z n = 0}, we have

X n ≥ 1 |G n | Z n i=1 log E[τ G (i) | G n ] - cZ n log |G n | |G n | = v n |G n | • m n v n • Z n m n • 1 Z n Z n i=1 log E[τ G (i) | G n ] m n - cZ n log |G n | |G n | . (4.5)
Conditionally on {Z n = k} for k > 0, the random variables (

m n ) -1 • log E[τ G (i) | G n ],
for i = 1, . . . , k, are independent and all have the same distribution as Y n . Hence, for any ε > 0,

P 1 k k i=1 log E[τ G (i) | G n ] m n -E[Y n ] > ε Z n = k ≤ E[(Y n ) 2 ] ε 2 k .
Since for any k > 0 we have Proof. We will prove the second convergence. Assume by contradiction that there exists ε > 0 such that, for some increasing sequence (n k ) with n k → ∞,

P(Z n ≤ k | Z n = 0) n →∞ ----→ 0, we obtain P   1 Z n Z n i=1 log E[τ G (i) | G n ] m n -E[Y n ] > ε Z n = 0   n →∞ ----→ 0.
P(X n k > γ + ε | Surv) > ε. (4.7)
Fix a small δ > 0 to be chosen later. Define the events

B k,1 = Surv ∩ {X n k < γ -δ}, B k,2 = Surv ∩ {γ -δ ≤ X n k ≤ γ + ε}, B k,3 = Surv ∩ {X n k > γ + ε}.
Also define

q k,0 = E |G n k | v n k • 1 Ext , q k,j = E |G n k | v n k • 1 B k,j , j ∈ {1, 2, 3}.
Note that q k,0 + q k,1 + q k,2 + q k,3 = 1. (4.8) By (4.1) and (4.2) we have

q k,0 ≤ E |G n k | v n k -W ∞ + E [W ∞ • 1 Ext ] k→∞ ---→ 0. (4.9)
Similarly, we bound

q k,1 ≤ E |G n k | v n k -W ∞ + E W ∞ • 1 B k,1
k→∞ ---→ 0; (4.10) the convergence follows from the fact that P(B k,1 ) k→∞ ---→ 0, by Claim 4.2. Next,

q k,3 ≥ E W ∞ • 1 B k,3 -E |G n k | v n k -W ∞ .
Noting that (4.7) gives P(B k,3 ) > ε for every k, we have lim inf

k→∞ q k,3 ≥ ε := inf B E[W ∞ • 1 B ], (4.11)
where the infimum ranges over all sets B with B ∈ σ ({Z n : n ≥ 0}) , B ⊆ Surv, P(B) > ε.

Since the law of W ∞ conditioned on Surv has no atom at zero, we obtain ε > 0.

We now put these estimates together. We start computing

E[Y n k ] = v n k m n k •   E X n k • |G n k | v n k • 1 Ext + 3 j=1 E X n k • |G n k | v n k • 1 B k,j   ≥ v n k m n k • [(γ -δ) • q k,2 + (γ + ε) • q k,3 ] (4.8) = v n k m n k • [γ + q k,3 • ε + q k,3 • δ -δ + (q k,0 + q k,1 )(δ -γ)] . (4.12)
Using (4.9), (4.10), (4.11) and the convergence v n /m n → m/(m -1), by first choosing δ small enough and then assuming k is large enough, the expression in (4.12) is larger than

≤ P X n < γ - ε 2 + Ē P τ Gn < e (γ-ε)|Gn| | G n • 1 X n ≥ γ - ε 2
≤ P X n < γ - ε 2 + Ē e (γ-ε)|Gn| • E [τ Gn | G n ] -1 • 1 E[τ Gn | G n ] ≥ e (γ-ε 2 )|Gn| n→∞ ---→ 0.

3 . 4 . 5 . 6 .

 3456 For d ≥ 3 and u > 0, let I u be the occupied set of random interlacement with intensity u on Z d ; let G n be the maximal component of the subgraph of Z d induced by I u ∩ B n . For d ≥ 3 and u > 0 sufficiently small, let V u be the vacant set of random interlacement with intensity u on Z d ; let G n be the maximal component of the subgraph of Z d induced by V u ∩ B n . For d ≥ 3, let ϕ = (ϕ x ) x∈Z d be the Gaussian free field on Z d . Let E ≥h ϕ = {x ∈ Z d : ϕ x ≥ h} for h ∈ R small enough, and let G n be the maximal component of the subgraph of Z d induced by E ≥h ϕ ∩ B n . For d ≥ 2, consider the supercritical random geometric graph on B n and let G n be the resulting maximal component. 7. Let ν be a probability measure on N with k kν(k) > 1 and k k 2 ν(k) < ∞. Let G be a Galton-Watson tree with offspring distribution ν and either conditioned on being infinite, or conditioned on reaching generation n. Let G n be the subgraph of G induced by the set of vertices at distance at most n from the root.

  surely G has a unique infinite connected component, denoted by G ∞ . (3.2)Under these hypotheses, for any n ≥ 1, we let G n be the maximal connected component of G intersected with the box B n := {-n, . . . , n -1} d (with the convention that if there are more than one maximal connected component, one chooses G n among them in an arbitrary way).

  has a single component of cardinality larger than n d-ε ; (3.7) all other components of G ∩ B n either have cardinality smaller (3.8) than n ε or are contained in B n \B n-n ε . Proof. Fix ε > 0, and define n = n ε/d /2 . Given a connected graph G ⊆ Z d , we say G crosses an annulus x + (B n \B n/4 ) if the vertex set of G intersects both x + B n/4 and x + (B n ) c . By (3.3), (3.4

  also denote the whole tree by G ∞ . The events of non-extinction (or survival) and extinction are defined respectively by Surv = {|G ∞ | = ∞} , and Ext = Surv c = {|G ∞ | < ∞} .

Further using the factClaim 4 . 3 .

 43 that E[Y n ] n→∞ ---→ γ and P(Z n = 0 | Z n = 0) τ G (i) | G n ] m n -γ > ε Z n = 0 ∞ = 0 | Z n = 0) = 0. For all ε > 0, P(X n > γ + ε | Z n = 0) n→∞ ---→ 0 and P(X n > γ + ε | Surv) n→∞ ---→ 0.

m m- 1 2 ≤

 12 (γ + ε ε/2). This gives lim inf k→∞ E[Y n k ] > γ, contradicting E[Y n ] n→∞ ---→ γ.The proof of Theorem 1.1 in the case of Galton-Watson trees now follows from Claims 4.2 and 4.3 by the same estimates as in the last paragraph of Section 3.1. Letting P(•) denote either P(• | Surv) or P(• | Z n = 0) (and similarly for Ē), we haveP 1 |G n | log τ Gn > γ + ε ≤ P X n > γ + ε 2 + Ē P τ Gn > e (γ+ε)|Gn| | G n • 1 X n ≤ γ + ε P X n > γ + ε 2 + Ē e -(γ+ε)|Gn| • E [τ Gn | G n ] • 1 E[τ Gn | G n ] ≤ e (γ+ ε log τ Gn < γ -ε

  Theorem 3.1. Let P denote a probability measure on {0, 1} Z d , d ≥ 2, satisfying (3.1), (3.2), (3.3) and (3.5), and let (G n ) n≥1 and G ∞ be as defined above. Consider now the contact process on G n , with infection rate λ > λ c (Z), starting from full occupancy, and denote by τ Gn its extinction time. There exists γ ∈ (0, ∞) such that Before proving this result let us start with some preliminary facts concerning the sizes of the connected components inside B n .

	1 |G n |	• log τ Gn	(P) ---→ n→∞	γ.	(3.6)

Proposition 3.2. Let P denote a probability measure on {0, 1} Z d , d ≥ 2, satisfying (3.1), (3.2), and

  8 n are subgraphs of a single component C of G ∞ ∩ B n . Noting that C intersects all boxes x + B n for x ∈ B n-8

n , it follows that C has at least (n -8 n ) d /( n ) d ≥ n d-ε vertices. Now, let C be some component of G ∩ B n distinct from C . Then, C cannot cross any annulus x + (B n \B n/4 ) with x ∈ B n-8 n . It thus follows that at least one of the following two conditions hold:

  .14) To this end, fix n ∈ [n k+1 , n k+2 ]. We split the box B n-n k into N := ( n/n k -1) d disjoint boxes of side length 2n k , and denote by (G (i) ) 1≤i≤N the maximal connected components inside each of these boxes. Define the event A = all the (G (i) ) 1≤i≤N are subgraphs of G n .

	(3.15)
	By Proposition 2.3, on A we have

  The convergence of Z n /m n (almost surely and in L 2 ) and the two equalities in (4.2) are proved in Chapter 1 of[START_REF] Athreya | Branching processes[END_REF]. The almost sure convergence of |G n |/v n is then immediate, and the convergence in L 2 of |G n |/v n can be obtained from Minkowski inequality:

	almost surely and in L 2 ,	(4.1)
	and moreover,
	P (W ∞ = 0 | Ext) = 1, and P (W ∞ > 0 | Surv) = 1.	(4.2)

Acknowledgements

We would like to thank Balázs Ráth for directing us to several references on the models we study, leading to a wider applicability of our results. We would also like to thank Tobias Müller for helpful discussions and references on the random geometric graph.

to be transient, one takes d ≥ 3. An equivalent definition of the occupied set of random interlacements is the following: it is the unique random set of vertices I u ⊆ Z d satisfying

where K is any finite set of vertices of Z d and cap(K) denotes the discrete capacity of K (see Chapter 6 of [START_REF] Lawler | Random walk: a modern introduction[END_REF]). The density of I u is thus an increasing function of u. Here we take any d ≥ 3 and any u > 0. Our four conditions are proved in the following references. Conditions (3.1) and (3.2) are given respectively by Theorem 2.1 and Corollary 2.3 in [START_REF] Sznitman | Vacant set of random interlacements and percolation[END_REF]. Condition (3.3) follows from Proposition 1 in [START_REF] Ráth | On the transience of random interlacements[END_REF], and condition (3.5) is equation (2.15) in [START_REF] Sznitman | Vacant set of random interlacements and percolation[END_REF] (one also needs the fact that the capacity of B n is of order n d-2 ; see Section 6.5 in [START_REF] Lawler | Random walk: a modern introduction[END_REF]).

Vacant set of random interlacements in strongly percolative regime, d ≥ 3. For d ≥ 3 and u > 0, the vacant set V u of random interlacements is defined as the complement of I u . There exists u * ∈ (0, ∞) such that V u has an infinite component if u < u * and no infinite component if u > u * ([31], [START_REF] Sidoravicius | Percolation for the vacant set of random interlacements[END_REF]; see also [START_REF] Ráth | A short proof of the phase transition for the vacant set of random interlacements[END_REF] for a short proof). Conditions (3.1) and (3.5) follow from the same conditions for I u , for which references were given above. For d ≥ 3 and u ∈ (0, u * ), condition (3.2) is proved in [START_REF] Teixeira | On the uniqueness of the infinite cluster of the vacant set of random interlacements[END_REF]. Condition (3.3) is only known for u small enough (in the so-called strongly percolative regime of the vacant set), so we assume this regime is in force here. The proof is given in [START_REF] Teixeira | On the size of a finite vacant cluster of random interlacements with small intensity[END_REF] for d ≥ 5 and in [START_REF] Drewitz | On chemical distances and shape theorems in percolation models with long-range correlations[END_REF] for all d ≥ 3; see Theorem 2.5 in the latter reference.

Excursion set of Gaussian free field in strongly percolative regime, d ≥ 3. The Gaussian free field in Z d , d ≥ 3, is the centered Gaussian field ϕ = (ϕ x ) x∈Z d with covariances E[ϕ x ϕ y ] = g(x, y), where g denotes the Green function of simple random walk in Z d . Its excursion sets are the sets

There is again a critical value h * ∈ R so that E ≥h ϕ almost surely has an infinite component when h < h * and only finite components if h > h * (in fact it is also known that h * > 0). This has been proved in [START_REF] Bricmont | Percolation in strongly correlated systems: the massless Gaussian field[END_REF] for d = 3 and in [START_REF] Rodriguez | Phase transition and level-set percolation for the Gaussian free field[END_REF] for any d ≥ 3. Our condition (3.1) is proved in the paragraph preceding Lemma 1.5 in [START_REF] Rodriguez | Phase transition and level-set percolation for the Gaussian free field[END_REF], and (3.2) is verified in [START_REF] Rodriguez | Phase transition and level-set percolation for the Gaussian free field[END_REF], Remark 1.6. Condition (3.3) is included in Theorem 2.7 in [START_REF] Drewitz | On chemical distances and shape theorems in percolation models with long-range correlations[END_REF]; again this is only known in a strongly percolative regime where h is smaller than a constant h ≤ h * , so we assume this regime is in force here. Finally, (3.5) is given in Proposition 1.1 in [START_REF] Popov | On decoupling inequalities and percolation of excursion sets of the Gaussian free field[END_REF].

Random geometric graph

The random geometric graph in R d , d ≥ 2, is the random graph whose vertex set is a Poisson point process of intensity one, and the edge set is defined with the rule that two vertices are connected by an edge if and only if they are at Euclidean distance smaller than some fixed constant R > 0. It has been shown that there exists a critical value R c > 0 such that the graph almost surely has only finite components if R < R c and a uniue infinite component if R > R c . This result and an in-depth treatment in the model can be found in the book of Penrose [START_REF] Penrose | Random geometric graphs[END_REF]. (We observe that the model is parametrized in a different manner there than the one we take here: the author fixes the radius for connectivity R = 1 and takes the intensity of the Poisson process of vertices as the parameter of the model, which is denoted λ throughout the book. This choice is equivalent to ours after a rescaling of R d ). As mentioned in the Introduction, we assume d ≥ 2, R > R c , and let G n be the connected component with highest cardinality in the graph restricted to B n = [-n, n] d . Here we will prove that the statement of Theorem 1.1 holds for these graphs. The proof is very similar to that of Section 3.1, so we will only describe the points in which the proofs differ. Below we state a proposition that contains all the properties that we will need concerning the graphs G n . Before doing so, let us give two definitions. First, the metric diameter of a graph


Caroline Legoupil

Isabelle Enderle

Flore-Anne Le Baccon

Claude Bendavid

Lucas Peltier

Estelle Bauville

Jean Leveque

Vincent Lavoue

MD Maela Le Lous
email: maela.le.lous@chu-rennes.fr

Performance of a quick pregnancy test on whole blood in early pregnancy units a prospective cohort study

Keywords: early pregnancy, human chorionic gonadotropin, point-of-care test, whole blood

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

R e v i s e d m a n u s c r i t p t

Performance of a quick pregnancy test on whole blood in early pregnancy units: a prospective cohort study Introduction Pelvic pain (PP) and vaginal bleeding (VB) are present in 71-88% of women consulted in early pregnancy units [1,[START_REF] Calvo | Gynecological emergencies: a prospective study about patients purpose of consultation and outcome[END_REF]. The systematic management of these women relies on the identification of a pregnancy and its location [i.e. intrauterine pregnancy (IUP) or ectopic pregnancy (EP)]. Both physical examination and ultrasound usually help with the diagnosis. However, in approximately one-third of cases, pregnancy status cannot be established without a biological pregnancy test [1,[START_REF] Calvo | Gynecological emergencies: a prospective study about patients purpose of consultation and outcome[END_REF]. The gold-standard test for pregnancy is based on an immunologic dose of human chorionic gonadotropin (hCG) through a serum pregnancy test, with a 5 UI/l positivity threshold [START_REF] Greene | Pathology consultation on human chorionic gonadotropin testing for pregnancy assessment[END_REF].

There has been increasing pressure to improve emergency department efficiency and throughput. Turnaround times for laboratory results have been shown to significantly influence throughput, with qualitative quick pregnancy testing often delaying advanced imaging, medication delivery, and disposition decisions. Usually, urinary tests are used, but they have shown a variable sensitivity with a theoretical detection threshold of hCG of 20-25 UI/l. Nevertheless, false-negative point-of-care (POC) urine pregnancy results are infrequent, but the large number of tests ordered in a high-volume emergency department can be expected to yield a significant cohort and thus increase the risk of missed EP [START_REF] Woo | 417 False negative point-of-care urine pregnancy results in the emergency department: quantifying a needle in the haystack in the clinical setting[END_REF].

A new POC qualitative pregnancy test that detects hCG in whole blood was developed recently, called the NG-Test hCG WB (Laboratoire NG Biotech, Z.A Courbouton, Guipry, France). It works thanks to a simple blood drop (in the way diabetic patients perform glycemic control tests on their finger). It is easy to use during a medical consultation at any time and can be performed by a nurse. The positivity threshold is 10 UI/l and the results are obtained within 5 min.

The main aim of this study was to assess the diagnostic performance of the NG-Test hCG WB. The secondary objectives were to assess the usefulness of performing the test, the cost-effectiveness, and the impact on throughput for women consulted in early pregnancy units for PP or VB.

R e v i s e d m a n u s c r i t p t

Materials and methods

Population

A prospective cohort study was carried out. A total of 200 women consulted in early pregnancy units at a tertiary hospital for PP and/or VB between 9 December 2016 and 3 December 2017 were included in the study. The sample size was calculated to detect more than 15 events (i.e. positive pregnancy tests). The inclusion criteria were the absence of a visible pregnancy with transvaginal ultrasound, at first medical contact, and the necessity to perform a pregnancy test. The exclusion criteria were patients younger than 18 years of age and patients who were treated for infertility.

All patients provided their consent after receiving oral and written information about the study. This study was approved by a local ethics committee (IRB, France Avis no. 16.84).

In our current protocol, patients consulted for PP or VB undergo a physical examination and an ultrasound scan (Philips HD7xe; Philips, Amsterdam, the Netherlands). If required, a quantitative hCG serum test is performed. Patients who were included in the study were also tested in a blinded manner using the NG-Test hCG WB at the end of the consultation. Patients included in the study were managed according to our standard policy on the basis of ultrasound findings and a serum pregnancy test. Medical management was not modified by the results of the NG-Test hCG WB.

The NG-Test hCG WB (Laboratoire NG Biotech) is a qualitative hCG whole-blood test based on an immunochromatographic technique. Therefore, hCG is recognized in its intact form by a monoclonal pair of antibodies: anti-α-hCG and anti-β-hCG. It was standardized according to the 5th International Standard for hCG of the National Institute for Biological Standards and Control NIBSC (preparation 07/364) [START_REF]WHO International Standard, 5th WHO IS, chorionic gonadotrophin[END_REF]. The positivity threshold is 10 UI/l. A nurse made a small finger incision with a lancing device and then dropped a small quantity of blood onto the test before adding the reactive. After 5 min, the result was read by the nurse, who was blinded to the laboratory results. The result was considered positive if the test displayed two lines and negative if there was only one line (Fig. 1). If no line was visualized, the test was considered invalid and was repeated.

Laboratory test

All included patients had a laboratory test with a quantitative serum hCG measurement, which is considered the 'gold-standard' technique, using a venous blood sample drawn by a nurse. A dose of hCG was administered on isolated serum after centrifugation of the tubes with an electrochemiluminescence immunoassay using the hCG + β Roche reagent, which detects intact hCG and unity β, on the automate COBAS e411 (Roche Diagnostics GmbH, Mannheim, Germany). This method was standardized according to the 4th International Standard for hCG of the NIBSC (preparation 75/589) [START_REF]WHO International Standard, 4th IS chorionic gonadotropin, human[END_REF]. The inferior limit of detection was 0.1 UI/l and the positivity threshold was 5 UI/l for the gold-standard test. The results were read by technicians and validated by a biologist, who were all blinded to the NG-Test hCG WB results.

Data collection

The following data were recorded: patient age, gravidity, parity, date of last menstruation, contraception, smoking, clinical symptoms, physical examination data, ultrasound data, quick test result, gold-standard quantitative pregnancy test result, final diagnosis, and treatment received at patient discharge. PP was rated using a Numerical Pain Scale from 0 to 10, with 0 corresponding to no pain and 10 representing the worst pain imaginable.

Nurses who were involved in the performance of the NG-Test hCG WB completed a questionnaire on the ease of use and reading of the result. They also had to report their overall satisfaction.

Finally, the time of patient arrival, time of blood sampling, time of result obtainment, and time of patient discharge were recorded.

Outcome measure

The main outcome was a positive laboratory pregnancy test. We also assessed the diagnostic performance of the NG-Test hCG WB at the threshold of 10 UI/l of hCG, which was the positivity threshold established by NG Biotech. Secondary outcomes included the global satisfaction of the nurses, the time between blood sampling and the result, and the costs.

Statistical analysis

Sensitivity (Se), specificity (Sp), positive predictive value (PPV), negative predictive value (NPV), and Youden index (Y = Se + Sp -1) were calculated. Data were compared using a χ 2 -test and Fisher's test for qualitative variables, and a t-test for continuous variables. A P value less than 0.05 was considered significant.

Results

Population

Two hundred patients were included in the study. Twenty-seven (13.5%) patients were excluded because of missing data and three other patients were excluded a posteriori because of mistaken inclusion: one patient had a confirmed EP and two other patients had an IUP diagnosed by ultrasound. A total of 170 patients were included in the analysis (Fig. 2). The characteristics of 170 patients are described in Table 1. Twenty-nine (17%) patients had a pregnancy diagnosis confirmed by the goldstandard serum test. Age, smoking, gravidity, parity, and symptomatology (VB or pain) rates were similar in both groups (i.e. pregnant women vs. nonpregnant women).

R e v i s e d m a n u s c r i t p t

Absence of contraception, delayed menstruation, and severe pain (Numerical Pain Scale > 6) were significantly more frequent in the pregnant group (Table 1).

Menstruation delay was 9 12 days in pregnant patients. In terms of ultrasound findings, the endometrium was significantly thicker (13.1 7.3 vs. 6.2 4.1, P < 0.001) and 2.

NG-Test hCG WB performance

Twenty-six (15.3%) patients had a positive NG-Test hCG WB and 29 (17%) patients were pregnant according to the laboratory test. Sensitivity, specificity, PPV, and NPV of the NG-Test hCG WB were 89.7, 100, 100, and 97.9%, respectively. The Youden index was 0.90.

Of the three patients with a negative NG-Test hCG WB and a positive laboratory test, two had a quantitative hCG level of 7 UI/l and the third level was 35 UI/l. The two patients who had a laboratory serum hCG level of 7 UI/l and a negative NG-Test hCG WB underwent a new laboratory test 48 h later. The results were negative. These two patients presented with pregnancy and stopped the use of contraceptives. One was consulted for VB and the other for PP and VB. Physical examination and ultrasound findings were normal. The diagnosis of pregnancy was not confirmed. The final diagnoses were menstruation and dysmenorrhea. The third patient, who had a false-negative NG-Test hCG WB with a laboratory serum hCG level of 35 UI/l, had a vacuum aspiration for an early pregnancy loss 1 month ago. The 2-day control showed a negative laboratory test. The retained hypothesis was a residual hCG level following the previous pregnancy.

Using a positivity threshold of 10 IU/l for the outcome measure, the sensitivity, specificity, PPV, and NPV of the NG-Test hCG WB were 96.3, 100, 100, and 99.3%, respectively. In this case, the Youden index was 0.96.

Among the 26 patients presenting a positive pregnancy test for both the NG-Test hCG WB and the laboratory test, there were three patients with EP who had hemoperitoneum requiring immediate surgical management; the other 23 patients had a pregnancy at an unknown location at the time of the initial NG-Test hCG WB. The evaluation indicated 11 IUP, eight early pregnancy losses, and four EP requiring medical treatment with methotrexate.

Quick test use

Nurses were satisfied with the NG-Test hCG WB at 89%. The test was easy to perform for 56% of the cases, moderately easy for 26% of the cases, and difficult for 18% of the cases. The main difficulty was the obtainment of a sufficient volume of blood. Nurses who had performed the NG-Test hCG WB at least twice did not have any difficulty subsequently. Reading of the results was easy in 99% of the cases. Reading was considered difficult by the nurse in two cases, for which a second reading was carried out by the doctor, who was unaware of the nurse's answer. Both tests were interpreted positively at both readings. For seven patients, the NG-Test hCG WB had to be performed twice because the first one was not valid. Five control tests were negative and two were positive. This was because of manipulation mistakes during different steps: insufficient waiting time, insufficient reactive quantity, and inversion between the blood reception zone and the reactive zone.

Impact of the quick test on waiting time for patients in the early pregnancy unit

The mean time spent in early pregnancy units was 254 78 min for patients. The mean time between patient arrival and the blood sample taken by the nurse was 121 58 min. The result of the laboratory test was obtained at a mean time of 90 31 min. After the biological results, the mean time required to allow patient

Cost-effectiveness analysis

The implementation of the NG-Test hCG WB implies that the laboratory test would be performed only for a

Discussion

The NG-Test hCG WB showed good performance in the present study. Indeed, our study showed 89.7% sensitivity of the quick test with a 5 UI/l hCG threshold and 96.3% sensitivity with a 10 UI/l hCG threshold.

The patient who had a negative NG-Test hCG WB and a serum hCG level of 35 UI/l had a residual hCG level after early pregnancy loss, which returned a negative result 48 h later. Intact hCG is the bioactive form produced by the syncytiotrophoblast and it accounts for the quasitotality of serum hCG in the first trimester [START_REF] Berger | Pregnancy testing with hCGfuture prospects[END_REF][START_REF] Montagnana | Human chorionic gonadotropin in pregnancy diagnostics[END_REF][START_REF] Stenman | The classification, functions and clinical use of different isoforms of HCG[END_REF]. The β unit is a metabolite arising from its degradation and disappears after intact hCG [START_REF] Stenman | The classification, functions and clinical use of different isoforms of HCG[END_REF], explaining our falsenegative result.

The two patients who had an hCG level of 7 UI/l had a negative NG-Test hCG WB, which was expected, given its theoretical positivity threshold. The control was negative and the clinical findings did not suggest a pregnancy. A very low quantity of hCG can be detected in the serum of nonpregnant women, which increased with patient age. Snyder et al. [START_REF] Snyder | Diagnostic considerations in the measurement of human chorionic gonadotropin in aging women[END_REF] observed hCG levels as high as 7.7 UI/l before 55 years of age in the absence of pregnancy. According to a European study, 1.1% of nonpregnant women had hCG levels between 2 and 7 UI/l, which was in agreement with the present study.

However, it is crucial to choose a sufficiently low threshold to detect all pregnancies. The danger is in missing the EPs. The commonly accepted threshold is 5 UI/l for quantitative tests, keeping in mind that higher levels can be observed in nonpregnant women. For qualitative tests, a 10 UI/l threshold may be acceptable because the risk of severe complications because of undiagnosed EP with hCG levels between 5 and 10 UI/l is low. However, the correlation between serum hCG level and the risk of a ruptured EP has been debated [START_REF] Downey | Indicators of potential for rupture for ectopics seen in the emergency department[END_REF]. In the case of unstable hemodynamics, both tests could be carried out from the outset, the first allowing a fast and adapted therapeutic management and the second allowing the diagnosis to be rectified without delay if the hCG level is between 5 and 10 IU/l. It is also interesting to note that cases of EP with hemoperitoneum and negative serum hCG levels have been reported [START_REF] Grynberg | Rupture of ectopic pregnancy with negative serum beta-hCG leading to hemorrhagic shock[END_REF][START_REF] Lonky | Ectopic pregnancy with shock and undetectable betahuman chorionic gonadotropin. A case report[END_REF].

Use of the NG-Test hCG WB reduces the time spent in early pregnancy units. The time required to obtain the pregnancy status results after sampling was reduced from 90 to 5 min. If the result is negative, the information can be dispensed instantaneously and the patient discharged without delay. It has already been established that the use of POC testing reduces length of stay in an emergency department [START_REF] Singer | Point-of-care testing reduces length of stay in emergency department chest pain patients[END_REF][START_REF] Asha | Impact from point-of-care devices on emergency department patient processing times compared with central laboratory testing of blood samples: a randomised controlled trial and cost-effectiveness analysis[END_REF].

Using the NG-Test hCG WB would increase the cost of pregnancy tests. However, this evaluation did not include the costs of sampling and transport to the laboratory. From our point of view, time savings, optimization of human resources, and optimization of emergency unit throughput could justify the use of the NG-Test hCG WB, although it is currently still investigational.

Some studies evaluated qualitative urinary tests. The level of detection for hCG is ∼ 20-25 UI/l, which is inadequate to detect early pregnancy and leads to falsenegative results [START_REF] Terwijn | Pregnancy detection by quantitative urine hCG analysis: the need for a lower cut-off[END_REF]. A qualitative whole-blood quick test has several advantages compared with qualitative urinary tests. It reduces the turnaround time for results because there is no need to wait for a spontaneous miction depending on bladder repletion level and patient hydration [START_REF] Gottlieb | Comparison of result times between urine and whole blood point-of-care pregnancy testing[END_REF]. The quick test can be performed on anuric patients in the case of hypovolemic shock, a rare but not exceptional situation [START_REF] Habboushe | Novel use of a urine pregnancy test using whole blood[END_REF].

The strengths of our study are its prospective setting and the originality of the qualitative whole-blood pregnancy test. It was evaluated in routine clinical practice, and not using a bank blood, to limit bias because of the degradation of hCG. IUP identified with ultrasound were excluded because they do not warrant an indication for a biological pregnancy test. However, this yielded a low rate of positive tests (16%) in our population. One limitation was that we did not study the reproducibility or the interobserver variability. No hook effect occurred in our study because it only occurs for higher hCG concentrations (around 500 000 UI/l) in molar pregnancies or advanced IUP.

Conclusion

The NG-Test hCG WB using whole blood is effective for diagnosing early pregnancy with a 10 UI/l positivity threshold. Its use allows a quick triage for patients presenting with VB or PP in the case of noncontributive clinical and ultrasound examinations. Its use for patient follow-up after EP, molar pregnancies, or tumors is not recommended. The use of this diagnosis algorithm would spare human requirements and optimize patient throughput.

R e v i s e d m a n u s c r i t p t

Fig. 1

 1 Fig. 1

  Quick pregnancy test. (a) Test kit. (b) Incision with a lancing device. (c) Sampling with a pipette. (d) Deposition of the blood drop. (e) Addition of reagent. (f) Negative result. (g) Positive result.

  R e v i s e d m a n u s c r i t p t adnexal masses were significantly more frequent (13.8 vs. 3.5%, P = 0.047) in pregnant women. The results of the quick test, reference test, and final diagnosis are described in Table

  Fig.2

Table 1 Population

 1

		Total (N = 170)	Pregnant (N = 29)	Not pregnant (N = 141)	P
	Age (mean SD) (years)	30.1 8.1	29.9 6.9	30.2 8.7	0.890
	Smoking [n (%)]
	Smoker	74 (43.5)	10 (34.5)	64 (45.4)	0.280
	Nonsmoker	96 (56.5)	19 (65.5)	77 (54.6)
	Patients using contraception [n (%)]	88 (51.8)	9 (31)	79 (56)	0.014
	Oral progestative	13	1	12
	Oral estroprogestative	21	2	19
	Emergency oral contraception	1	0	1
	Intrauterine device	15	2	13
	Intrauterine levonorgestrel device	16	0	16
	Progestative implant	3	0	3
	Tubal ligation	1	1	0
	Local	18	3	15
	Gravidity (mean SD)	2 2	1.9 2	2 2	0.860
	Parity (mean SD)	1.2 1.4	1.2 1.6	1.2 1.3	0.760
	Vaginal bleeding [n (%)]	91 (53.5)	17 (58.6)	74 (52.5)	0.546
	Light	50	12	38	0.203
	Moderate	19	1	18
	Strong	22	4	18
	Pain [n (%)]	143 (84.1)	23 (79.3)	120 (85.1)	0.437
	Intensity ≤ 6	1 1 9	1 0	1 0 9	< 0.001
	Intensity > 6	2 4	1 3	1 1
	Menstrual cycle [n (%)]
	Presence of amenorrhea	69 (40.6)	21 (72.4)	48 (34)	< 0.001
	Normal	101 (59.4)	8 (27.6)	93 (66)
	Ultrasound data
	Endometrial (mean SD) (mm)	7.3 5.4	13.1 7.3	6.2 4.1	< 0.001
	Outpouring [n (%)]	25 (14.7)	7 (24.1)	18 (12.8)	0.115
	Adnexal mass [n (%)] Other [n (%)] a	9 (5.3) 29 (17)	4 (13.8) 2 (7)	5 (3.5) 27 (19.1)	0.047 0.170

a Fibroids, ovarian cyst, adenomyosis, polycystic ovaries.

Table 2

 2 Final diagnosis in patients with a positive laboratory test Test hCG WB. The cost of an NG-Test hCG WB is ~4 euros. In our laboratory, a quantitative plasma dose of hCG costs ∼ 2 euros, including the reagent and materials needed for the blood sample (compress, needle, tube, etc.). Using the NG-Test hCG WB in our population would have cost 732 euros (170 NG-Test hCG WB + 26 laboratory tests) versus 340 euros for 170 laboratory tests. As a comparison, urine tests cost approximately the same as NG-Test hCG WB.

	Symptoms	Serum hCG with gold standard test	Quick test	Final diagnosis
	Vaginal bleeding and pelvic pain	7	Negative	Dysmenorrhea
	Vaginal bleeding	7	Negative	Menstruation
	Vaginal bleeding	17	Positive	Trophoblastic retention
	Pelvic pain	27	Positive	Intrauterine pregnancy
	Vaginal bleeding	35	Negative	Residual hCG
	Vaginal bleeding	101	Positive	Early miscarriage
	Vaginal bleeding and pelvic pain	203	Positive	Early miscarriage
	Vaginal bleeding and pelvic pain	338	Positive	Early miscarriage
	Pelvic pain	339	Positive	Intrauterine pregnancy
	Pelvic pain	349	Positive	Intrauterine pregnancy
	Pelvic pain	353	Positive	Intrauterine pregnancy
	Pelvic pain	464	Positive	Intrauterine pregnancy
	Vaginal bleeding	534	Positive	Ectopic pregnancy (medical treatment)
	Pelvic pain	565	Positive	IUP
	Vaginal bleeding and pelvic pain	823	Positive	EP (medical treatment)
	Pelvic pain	891	Positive	EP (surgical treatment)
	Vaginal bleeding and pelvic pain	1293	Positive	EP (surgical treatment)
	Pelvic pain	1461	Positive	IUP
	Pelvic pain	1624	Positive	IUP
	Vaginal bleeding and pelvic pain	1817	Positive	IUP
	Pelvic pain	2404	Positive	EP (medical treatment)
	Vaginal bleeding and pelvic pain	2700	Positive	EP (surgical treatment)
	Vaginal bleeding and pelvic pain	2747	Positive	Early miscarriage
	Vaginal bleeding	3170	Positive	Early miscarriage
	Pelvic pain	4552	Positive	IUP
	Pelvic pain	4731	Positive	IUP
	Vaginal bleeding and pelvic pain	5939	Positive	EP (medical treatment)
	Vaginal bleeding and pelvic pain	8711	Positive	Early miscarriage
	Vaginal bleeding and pelvic pain	9950	Positive	Early miscarriage
	EP, ectopic pregnancy; hCG, human chorionic gonadotropin; IUP, intrauterine pregnancy.

Alouini S, Mesnard L, Coly S, Dolique M, Lemaire B. Gynecological emergencies: etiology and degree of gravity. J Gynecol Obstet Biol Reprod (Paris)

2012; 41:48-54.

Acknowledgements

Conflicts of interest

There are no conflicts of interest.


Paul Zuber
email: paul.zuber@tum.de

Armin Windschiegl

Raúl Medina

Beltrán De Otálora

Walter Stechele

Andreas Herkersdorf

Reduction of CMOS Power Consumption and Signal Integrity Issues by Routing Optimization

This paper suggests a methodology to decrease the power of a static CMOS standard cell design at layout level by focusing on switched capacitance. The term switched is the key: if a capacitance is not switched often, it may be high. If it is frequently switched, it should be minimized in order to reduce power consumption. This can be done by an algorithm based on forces that automatically optimizes the position and length of every single wire segment in a routed design. The forces are proportional to the toggle activities derived from a gate level simulation. The novelty is that this allows to iteratively find a new topology for the wire segments. Our algorithm takes as input an already given, grid routed layout.

I. INTRODUCTION

Dynamic power, more precisely the switching net capacitances, still causes the highest part of the power consumed in integrated systems. If most of a system is designed, an optimization late in the development flow can avoid long redesign iteration cycles.

A. Related Work

Some ideas in the proposed methodology are inspired by force driven placement strategies as in [START_REF] Eisenmann | Generic global placement and floorplanning[END_REF]. The minimization of these forces yields a power optimized placement. The wire lengths of highly active nodes are kept low.

Using the switching activity as a steering factor while optimizing C is a well-known general strategy in literature. This has been suggested in [START_REF] Nebel | Low Power Design in Deep Submicron Electronics, chapter Layout Optimization[END_REF] and [START_REF] Chandrakasan | Low Power Digital CMOS Design[END_REF].

An actual application on layout level is given in [START_REF] Macii | Combining wire swapping and spacing for low-power deep-submicron buses[END_REF]. Similar to our method, it is shown that non-uniform space between wires can minimize power. However, only bus interconnects are considered, rather than logic signal nets in general. Also, a change in topology is not in the scope of [START_REF] Macii | Combining wire swapping and spacing for low-power deep-submicron buses[END_REF] [8] describes how the properties of metal layers can be exploited to achieve a low total net switching power. This is done by assigning long and highly active wires to upper routing layers carrying the least coupling capacity per unit length. Our methodology optimizes the topology of wire segments after routing within the layers.

B. CMOS Basics

1) Capacity: Two important trends in the physics of wires justify to focus their topology for power minimization. First, wire capacitances increase over the years when compared to the average gate capacitances [START_REF][END_REF] [START_REF] Ho | The future of wires[END_REF]. Second, the side-to-side capacitances make up an ever growing amount of the total capacitance [START_REF] Windschiegl | Exploiting metal layer characteristics for low-power routing[END_REF].

2) Power: We try to reduce the capacitive power. Its formula is well known in the literature as P C = Cα 01 fV 2 dd . α 01 fV 2 dd is the product of switching frequency and the square of the supply voltage of the node and is invariant after logic synthesis. We can therefore introduce a proportionality constant κ that includes this product and express the power as:

P net = i κ i l i 1 d li + 1 d ri , ( 1
)
if we only consider the sidewall capacitances, l i is length of the i th wire segment, and d li and d ri are the left and right distances to the next metal objects, respectively.

II. OPTIMIZING THE WEIGHTED CAPACITANCE

A power optimized routing can be obtained by surrounding each single wire with more space. Of course, this is undesirable due to limitations in area. However, we can exploit the remaining space after routing, especially grid-based routing, such that highly active wire segments become more isolated than segments with low switching activities. Section I derived the wire length as a second parameter to be optimized regarding the capacity. We propose to shorten high-κ nets accepting an increase in low-κ net's coupling wire segment lengths.

Both optimization goals described above can only be useful if they respect each other. It is not very helpful to isolate a high-κ wire segment if it is very short. On the other hand, shortening a high-κ wire that is not in the proximity of another net might be less effective than shortening a low-κ net that is very close to another one.

Wire segments that are already physically routed can not just be placed somewhere else. There could be other not movable objects in the way like clock or power lines or vias. Moreover, we must consider wire segments in one metal layer that have one or more branch segments in a layer above or below. Then, a change in position of such a segment would cause these branch segments to change their coupling lengths and thus their power.

III. THE PROPOSED METHOD

The idea of how to separate higher-κ wires relies on a force model between wire segments. The force between two wires is proportional to the sum of their κ-factors. The force decreases with 1/d to reflect Formula (1). Iteratively, the segments traverse into a balanced state by following the directions of their force fields.

Since the branch lines must be taken into account (cf. Section II), this step may be taken only if we gain a total minus on our objective function. This can be mapped to a second model: the longer a segment gets, the more a counter force must prevent this. This can be thought of as a repulsive spring. The proximity of the considered branch segment influences the spring constant. It should be high, if a reduction in length would save a lot of switched capacitance. This is the case if the branch segment is close to a high-κ object and/or carries a high-κ value itself. Fig. 1 shows the most simple example, where we optimize a topology as in the left side. The optimized position for the horizontal segment of the net connecting the two end nodes is above the fixed other horizontal wire (cf. right side). Using the field forces only, the horizontal bar would move further to the south. With the repulsive springs introduced, the lower horizontal segment receives a high contraction, because of the presence of a high field. The contraction gets transmitted across the vertical segment to the upper horizontal segment. Because the spring force of the upper segment is smaller, the balance will cause the lower bar to get shorter, and the upper bar longer. After a sufficient amount of time steps, the optimized layout results.

IV. EXPECTED BENEFITS

This section derives a comparison between the net switching powers before and after optimization. The expected optimization potential is high.

The design model produced by a commercial tool consists of N parallel wire segments routed on M > N tracks. Two additional fixed wires with κ = 0 model the border of the scenario. This shall represent the result of a grid-based router as used in the industry under chip size constraints. The assumed wire width to minimum spacing ratio is 1:1. A 1/x distribution of toggle activities reflects the typical situation for industrial ASIC designs.

The task to optimize the N + 1 distances d 0 , d 1 , . . . , d N between N + 2 wires such that the power is minimal can be formulated as:

P segs ∝ N +1 n=0 (κ n + κ n-1 ) d n = min! d n ≥ d min ∀n = 0 . . . N N +1 n=0 d n ≤ (M + 1)d min (2)
This is a geometric program, where the first line is the objective function. We recorded the value of P segs with the generated κ i s and the initial d i s for comparison. The second line reflects the minimum spacing rule. Together with the chip size constraint in the third line, the complete system was passed to a public domain geometric program solver [START_REF]Computational Optimization Laboratory. A geometric programming solver[END_REF]. The solver returns both the optimized value for the objective function P segs and the new constraint values d n .

Tab Tab. 1 displays the resulting average net switching power savings of random designs as a function of N , the parameter M is set to N + 1. Multiple passes with different sets of random seeds were run to obtain average numbers. The savings displayed in the table are promising: For example, for a bus with N = 64 wires running on M = 65 different tracks, optimal wire spacing can reduce the net switching power by about 17%. This is a significant change. It further increases for higher numbers of M , ie. with more space.

There are a couple of factors that will cause loss in optimization potential, cf. Section II. Considering this, we are in the range of the power savings at layout level as expected in [START_REF] Macii | Combining wire swapping and spacing for low-power deep-submicron buses[END_REF] for buses.

V. FUTURE REMARKS

The optimization engine is intended to work together with standard ASIC design flow tools. It reads real layout data and toggle activities from them and performs the optimization methods described. The result is a modified layout which is written back to the tool's database.

The method does not yet support Miller capacitances. However, if the variable toggle rate is replaced by the possible overlapping transition time frame of two adjacent nets, the same algorithm can be used to minimize the risk of failure due to crosstalk disrupted signal integrity. The algorithm can further be optimized to react on the two forces at the two sides of a wire segment with an optimal wire width. This can repair timing violations late in the flow. Ordering the nets in a very specific way can further improve the effectiveness of wire spacing [START_REF] Zuber | Net ordering in combination with wire spacing for reduced cmos power consumption[END_REF]. A mechanism to split the wire segment into pieces is beneficial if only part of it is movable.

Fig. 1 :

 1 Fig. 1: Topology before (left) and after (right) optimization.

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE


Pascal Puech

Hannes Hubel

David J Dunstan

Ayman Bassil

Revathi Bacsa

Alain Peigney

Emmanuel Flahaut

Christophe Laurent

Wolfgang S Bacsa
email: wolfgang.bacsa@lpst.ups-tlse.fr

Light scattering of double wall carbon nanotubes under hydrostatic

Keywords: 61.46.+c, 62.50.+p, 63.22.+m, 78.30.Na

Introduction

Interest in carbon nanotubes (CNT) has been growing since their discovery in 1991 [1], thanks to their exceptional properties leading to a large number of potential applications [START_REF] Reich | Carbon Nanotubes: Basic Concepts & Physical Properties[END_REF]. Double wall carbon nanotubes (DWCNT) are more stable than single wall tubes (SWCNT). As the internal tube is protected by the external tube, interaction of the external tube with its environment will to a lesser extend influence the mechanical properties. This will be important for molecular motor applications. The DWCNT can also be considered as a molecular pressure sensor giving information of the interaction of the external tube with adsorbed molecules. We use inelastic light scattering as a tool to examine the mechanical properties of DWCNTs. DWCNTs give the opportunity to explore the effect of hydrostatic pressure on the internal tubes. Multi wall carbon nanotube samples have a large range of diameters and variable number of walls, which makes it difficult to distinguish contributions from internal and external tubes. Double wall carbon nanotubes with narrow diameter distribution have recently become available and contributions from the internal tubes in the Raman spectrum have been identified. There have been a number of reports on multi wall and single wall CNT's under hydrostatic pressure. Tang et al. [START_REF] Tang | [END_REF] observed with X-ray a structural distortion near 2 GPa attributed to a faceting of the tube. The X-ray diffraction profile of Sharma et al. [4] shows that the diffraction line related to the tubes vanishes beyond ~10 GPa. The circular tube section is proposed to be transformed into flattened elliptical shape. A highly flattened structure corresponding to a peanut structure has been predicted by Wu et al. [5]. SWNTs have been probed by Raman spectroscopy and under high pressure extensively [6]. The pressure behaviour of hollow nanostructures [7] as well as multi wall CNTs [8] have been explained using the elastic continuum model. Ab-initio [9,10], molecular dynamics calculations [11], have been used to understand the transition, at low and high pressure. A recent review focussed on Raman spectroscopy on CNTs at highpressure [6] notes that there is no clear correlation between the observed pressure coefficient in different samples and pressure media. Schlecht et al. [11] have studied isolated single-walled carbon nanotubes under high-pressure and find experimentally an identical frequency dependence of the optical mode in bundled and isolated SWCNTs, which is not predicted by their model simulations using generalized tight-bending molecular dynamics (GTBMD). Venkateswaran et al [12] find using GTBMD, that the van der Waals interaction makes an important contribution to the frequency and pressure coefficient of the radial breathing modes (RBM). The assumption that the pressure-transmitting medium does not penetrate in the tube bundle is inconsistent with the small observed shift of the RBMs of SWCNTs in an alcoholic mixture [13]. It is found that the observed band positions at zero pressure depend on the pressure medium. Wood et al. [14,15] show that the frequency shift of the D* mode ranges from 2610 to 2630 cm -1 . The observed shift correlates with the cohesive energy density of the medium. Teredesai et al [16] have observed with SWCNTs a higher-pressure coefficient with water as pressure medium. We have recently explored double wall carbon nanotubes using a methanol-ethanol mixture as pressure medium [17]. Here we compare the Raman spectra under hydrostatic pressure using two different pressure media. We also report on the low and additional high frequency bands.

Samples and experiment

The DWCNTs were prepared by the catalytic chemical vapour deposition method (CCVD). Selective reduction at 1000 °C in a methane-hydrogen (18% CH4) atmosphere of a solid solution of a transition metal oxide (CoO) and an insulating oxide (MgO) led to the formation of small diameter CNT with one to four walls; for more details see [18,19]. After the reaction, the not reacted Co and MgO were dissolved in dilute (3.7%) hydrochloric acid and CNT were recovered. High-resolution electron microscopy images showed the presence of individual and small bundles of DWCNTs with radius ranging from 0.3 to 1.5 nm. The tubes were single, double or triple walled with about 80% of DWCNTs and a few four walls tubes. A significant fraction of DWCNTs had internal radius smaller than 0.5 nm. The mean radius is 0.7 nm. All Raman spectra were recorded at room temperature using a microprobe instrument from Renishaw Inc. The scattered light was collected in backscattering geometry using a microscope objective (× 20) to focus the laser beam (633 nm) on to the sample inside the pressure cell. The high-pressure Raman measurements were performed in a diamond anvil cell with a 4 :1 mixture by volume of methanol-ethanol or argon as the pressure-transmitting medium. The pressure chamber was defined by the volume of a 200 µm diameter hole in a stainless steel gasket (thickness of 100 µm). The pressure was monitored using the luminescence of a ruby chip inside the cell. For the liquid pressure medium, the DWCNTs were dispersed using a ultrasonic bath before loading. With argon, an agglomerated tube sample was placed in the drilled hole of the gasket before cryogenic loading of argon. We have used for both experiments samples from the same batch of DWNTs.

Experimental results

Figure 1 shows the Raman spectra as a function of applied pressure in the high frequency range obtained using the methanol-ethanol pressure medium. We observe a splitting of the G band, the in-plane optical zone centre phonon mode of graphite. A broader band is located at 1480 cm -1 . The splitting can be attributed to the internal and external tubes as will be shown below. The higher frequency band is attributed to the external walls and the low frequency band to the internal walls. The fitted band positions are shown as a function of applied pressure in Fig. 2. Figure 3 shows spectra recorded on different locations in the pressure cell. We can see a correlation between the relative intensity of one of the bands in the doublet and the appearance of the broader band at 1480 cm -1 . The intensity of the band at 1480 cm -1 is larger when the intensity of the band associated to the external walls is smaller. The band at 1480 cm -1 has been report in the literature [20] and attributed to tubes with a larger number of defects. We note that the intensity of the band associated to the internal tube does not change. In Fig. 2 we see that at low pressure, the frequency of the external walls does not follow the same linear behaviour obtained at higher pressures (>3 GPa).

The transition at 3 GPa observed with the alcohol medium is unusual. More measurements will be needed to clarify the behaviour in this range. The pressure coefficient changes near 3 GPa. Below 3 GPa the pressure coefficient is in range of 10 cm -1 /GPa while at higher pressures the pressure coefficient reduces to 5.6 cm -1 /GPa. The band associated to the internal walls follows linear pressure dependence at low and high pressures. Differences between the internal and external walls are also observed in the behaviour of the line-width with applied pressure. The line-width of the band associated to the internal tube is constant while the line-width of the band of the external walls increases linearly up to 6 GPa and saturates at higher pressures. In the low frequency range we have observed the RBMs located at 220 cm -1 and 260 cm -1 up to 6 GP. A band located at 340 cm -1 persisted to higher pressures. The origin of this band is not yet understood. It was attributed to a second harmonic of RBM [21]. But Venkateswaran et al. [22] shows that this explanation cannot fully explain the frequency shift of this peak with applied pressure. The frequency shift is too small and persists also with argon as pressure medium. At the highest pressure applied the frequency shift of the G band of the external walls approaches ~50 cm -1 . This is the same value observed for single wall CNTs [8].

In Fig. 4 we show the Raman spectra obtained using argon as the pressure-transmitting medium. Cryogenic loading does not permit to obtain values at low pressures. When releasing the pressure some spec-1450 1500 1550 1600 1650 1700 )

PRESSURE (GPa)

Internal External tra at low pressure have been recorded and are shown as dotted lines. Fully hydrostatic conditions are probably not established when releasing pressure, leading to uncertainties on the pressure calibration. We will not use them in the following analysis. We have used non-linear least square fitting to determine the peak positions as a function of applied pressure (Fig. 5). The frequency shift is larger in the 3 -6 GPa pressure range with the alcohol mixture as pressure transmitting medium. We find a pressure coefficient for the internal tube of 6 ± 1 cm -1 /GPa and for the external tube of 10 ± 1 cm -1 /GPa. When the frequency shift associated to the external walls reaches 60 cm -1 , a transition is observed. This high pressure induced frequency shift was not obtained with the alcoholic mixture. After the pressure-induced transition, the frequencies decrease and the splitting of external and internal walls disappears. When increasing the pressure furthermore the pressure coefficient is linear and the frequency shift is close to 45 cm -1 at 10 GPa. When decreasing the pressure, the splitting is recovered, showing a reversible transition.

Discussion

We first discuss the splitting of the G-band with applied pressure for double wall tubes. While the phase transition in SWCNTs has been identified as deformation of the cylinder shape, the presence of the internal wall is expected to reduce the deformations. Tight binding model simulations and local density approximation calculations confirm the consistency of the elastic continuum shell model [23]. In order to explain the lower pressure coefficient of the internal tube in DWCNTs, we have used the elastic continuum shell model [7,8,[START_REF] Boresi | Advanced Mechanics of Materials[END_REF]. For the pressure dependence of a single shell with a finite wall width we obtain the following expressions for the elements of the strain tensor:

2 1 rr B A r σ   = - -     , θθ σ   = - +     2 1 B A r and σ = - zz A , (1)
A and B are constants which depend on the boundary conditions. We consider two separate cylinders by introducing a discontinuity of the tangential stress component and use a continuous radial stress component. We write for the pressure external -p(R 2 ), between the tube -pi(R i ) and zero at the inside. We obtain two parameters for A and B for the internal and external tube. For the external tube we obtain:

- = - 2 2 2 ext 2 2 2 i i i R p R p A R R and - = - ext 2 2 2 i i i p p B p p R R (2)
and for the internal tube:

= - 2 int 2 2 1 i i i R A p R R and = 2 int 1 B R , (3)
p i is obtained by minimizing the elastic strain energy.

( )

( ) ( ) ν ν ν - - =       + - + + +       - - - -       2 2 2 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 1 2 1 5 4 1 1 3 1 2 2 1 i i i i i i i R R R p p R R R R R R R R R R R . ( 4
)
By using the derived expressions for the constants A and B for the external and internal walls for the tangential stress component, we find that the high frequency G-band can be attributed to the external tubes and the low frequency G-band to the internal tubes. When looking at the diameter dependence of the coefficients A and B we find that the tangential stress is nearly independent for the internal tube but varies linearly for the external tube for the diameter range found in our sample (0.5-1.5 nm) [17]. Con-sequently, we associate a inhomogeneous broadened of the band of the external tube with applied pressure with the diameter distribution.

When taking argon as a pressure-transmitting medium we observe a transition at 6 GPa. A similar pressure induced transition has been observed for SWCNTs at 10 GPa using an alcohol pressuretransmitting medium [25]. In both cases, the transition occurs with a frequency shift of the G-band at 60 cm -1 . Single as well as double wall tubes have the same pressure coefficient after the transition. This rules out effects due to tube faceting. It is more likely that the tubes are flattened. The flattening has been predicted by recent ab-initio calculations [10] and also observed for hollow nanostructures [7].

The fact that the pressure coefficient depends on the pressure medium suggests that the interaction of the pressure medium with the tube is not negligible. It has been noted in the literature that CNTs are sensitive to molecular pressure. Wood et al. [14,15] have shown that CNTs can be considered as a molecular sensor of the medium. By immersing SWCNT in a variety of liquids and dispersing them using ultrasound, they observe a frequency shift of the D* Raman peak up to 20 cm -1 in water compared with the values observed in air. Teresdai et al. [16] have observed for SWNTs using two different pressure transmitting media, alcohol mixture and water, that the pressure coefficient is different. The pressure coefficient is higher in water (7 cm -1 /GPa) as compared to alcohol (6 cm -1 /GPa). No helium, neon or argon transmitting pressure media has been reported to our knowledge so far. Model simulations [12] suggest that no fluid is likely to be present between CNT bundles. All the pressure coefficients are similar in the low-pressure range (0-3 GPa). Above this range a change in the pressure coefficient is observed in the case of alcohol. This change is not related to a shape change. The RBMs are not influenced. At the high-pressure transition, all the shifts induced by pressure are reduced. This reduction is somewhat higher for alcohol than when water is added in the alcohol mixture [16]. We can advance two explanations: faceting or polygonalization [START_REF] Tang | [END_REF] of the external tube resulting in a modified pressure coefficient. Small distortion of the circular cross section might preserve the splitting of the G-band. This would imply local non-hydrostatic pressure conditions. The second explanation takes into account of the interaction of the pressure medium with the CNTs. A local organization of the pressure medium can form a concentric shell around the tube, which has the consequence to reduce the pressure on the tube in the same manner as the internal tube experiences a smaller pressure than the external tube.

Conclusion

DWCNTs give the opportunity to distinguish pressure induced spectral changes from internal and external walls in multi wall carbon nanotubes. A first low-pressure transition is observed at 3 GPa in alcoholic mixture, which could correspond to a structural distortion or to an interaction with the medium. Further experiments are needed to elucidate this point. When the G-band frequency of the outer tube shifts by 50 -60 cm -1 , a collapse of the cylindrical structure is observed which reduces the pressure-induced shifts and removes the G-band splitting. The pressure transitions are reversible. The splitting of the G-band reappears when releasing the pressure. The splitting of the G-band can be explained by considering a tangential discontinuity of the stress component as one goes from the external wall to the internal tube. The ratio of the pressure coefficient of internal and external walls remains the same independent of the medium.

Fig. 1

 1 Fig.1Raman spectra of the G band region with methanol-ethanol as pressure-transmitting medium.

Fig. 2

 2 Fig.2Variation of the frequency as a function of pressure. Pressure-transmitting medium is methanolethanol.

Fig. 3

 3 Fig.3Correlation between the peak located near 1480 cm -1 and the peak associated to the external tubes. Pressuretransmitting medium is methanol-ethanol.

Fig. 4

 4 Fig.4 Raman spectra associated to the G-band. Notice a decrease of the frequency at 9.3 GPa. The dotted spectra are recorded while reducing the pressure. Pressure-transmitting medium is argon.

Fig. 5

 5 Fig.5 Variation of the G-band frequency as a function of the pressure. The pressure-transmitting medium is argon.