Guy Louchard
email: louchard@ulb.ac.be

Helmut Prodinger
email: hproding@sun.ac.za

Philippe Flajolet

The Asymmetric Leader Election Algorithm with swedish stopping: A probabilistic analysis

Keywords: asymmetric leader election, probabilistic analysis, urn models, limiting distributions

. The goal is to select one among n > 0 players, by proceeding through a number of rounds. If there is only one player remaining, the protocol stops and the player is declared the leader. Otherwise, all remaining players flip a biased coin; with probability q the player survives to the next round, with probability p = 1 -q the player loses (is killed) and plays no further . . . unless all players lose in a given round (null round), so all of them play again. In the classical leader election protocol, any number of null rounds may take place, and with probability 1 some player will ultimately be elected. In the Swedish leader election protocol there is a maximum number τ of consecutive null rounds, and if the threshold is attained the protocol fails without declaring a leader.

In this paper, several parameters are asymptotically analyzed, among them: Success Probability, Number of rounds Rn, Number of null rounds Tn.

,2009). Identifying some underlying distributions as Gumbel (type) distributions, one can start with approximations at a very early stage and compute (at least in principle) all moments asymptotically. This is in contrast to the companion work, where only expected values were considered. In an appendix, it is shown that, whereever results are given in both papers, they coincide, although they are presented in different ways.

Introduction

We present a probabilistic analysis, based on an urn model, of a leader election protocol that we call the Swedish leader election protocol. This name comes from a protocol presented by L. Bondesson, T.

Nilsson, and G. Wikstrand in [START_REF] Bondesson | Probability calculus for silent elimination : A method for medium access control[END_REF]. The goal is to select one among n > 0 players, by proceeding through a number of rounds. If there is only one player remaining, the protocol stops and the player is declared the leader. Otherwise, all remaining players flip a biased coin; with probability q the player survives to the next round, with probability p = 1 -q the player loses (is killed) and plays no further . . . unless all players lose in a given round (null round), so all of them play again. We say that a round is null if every active player tosses tails (all killed). In the classical leader election protocol, any number of null rounds may take place, and with probability 1 some player will ultimately be elected. In the Swedish leader election protocol there is a maximum number τ of consecutive null rounds, and if the threshold is attained the protocol fails without declaring a leader.

In this paper, several parameters are asymptotically analyzed, starting with n players, n large: (i) success probability S n , number of rounds R n , number of null rounds T n , number L n , in case of failure, of players that were active at the last non-null round, the so-called left-overs, and the total number C n of coins flipped. As suggested by one referee, other RVs of interest could be considered, for instance the number of useless coin flips (i.e. coin flips that lead to null rounds or rounds where every player goes forward to the next round). These RVs can indeed be analyzed with the same techniques, but due to length constraints, we refrain to do this here. Such considerations would make an excellent project for research students. This work is a companion paper to [START_REF] Louchard | The swedish leader election protocol: Analysis and variations[END_REF] where De-Poissonization was used, together with the Mellin transform. Here, we approximate the relevant quantities at an early stage; the loss in accuracy results in a gain when it comes to the complexity of the necessary computations. Indeed, we can deal here with all moments, whereas in [START_REF] Louchard | The swedish leader election protocol: Analysis and variations[END_REF] only expected values could be computed.

Urn model

In this section we show how to proceed from the leader election algorithm to an urn model. Then, within this model, we explain how to derive the asymptotic distributions of our random variables (RVs). Finally we obtain (via Laplace transforms) all asymptotic distributions and moments we need.

By the definition of the protocol each player does have a life duration, being independent of all other players, given by a geometrically distributed random variable X, with probability mass function P(X = j) = pq j-1 , where p denotes the killing probability, and q the probability of survival. Proceeding as in [START_REF] Louchard | The asymmetric leader election algorithm[END_REF] the leader election protocol can be considered as an urn model in the following way: we have urns numbered 1, 2, . . . , and n balls are thrown into the urns. The probability of each out of the n balls falling into an urn numbered j is being given by pq j-1 . The balls contained in the urn numbered j represent the candidates who are killed at level j of the leader election protocol. The advantage of the viewpoint is that the parameters of interest can be interpreted in terms of statistics on the urn model. In order to do so, we will introduce several additional parameters. Let I denote the number of balls contained in the maximal (highest numbered) non-empty urn. If it contains only a single ball, then the leader election protocol has succeeded, and a single player has survived. If it contains more than one ball, say i ≥ 2, this implies that a null round has taken place, and the process has to be restarted with i balls (all remaining i players have been killed and play again in the next round). A restarted process does not necessarily lead to a successful election, additional null rounds may happen. Note that no null rounds have occurred if the maximal nonempty urn contains only a single ball. We will use another random variable J denoting either the position of the maximal non-empty urn, if it contains i > 1 balls, or the position of the last non-empty urn before (i) We use the same notations as in [START_REF] Louchard | The swedish leader election protocol: Analysis and variations[END_REF], to ease further comparisons, with the exception of In, replaced here by Tn the maximal non-empty urn if the latter contains i = 1 balls. Moreover, in the case i = 1 we denote with K the number of balls in the urn j.

Instead of directly analyzing the parameters of interest (compare with [START_REF] Louchard | The swedish leader election protocol: Analysis and variations[END_REF]), we can analyze suitable statistics on the urn model, avoiding more cumbersome calculations. For example, for the analysis of the success probability S n we will study the joint distribution P(J = j, I = i) of I and J, distinguishing between the cases i = 1 and i ≥ 2.

Asymptotic analysis

We state, for later use, the following properties, for large n, which are crucial for our approach -early stage approximation of the relevant quantities defined on the urn model.

= O(1)] ∼ P[urn j 1 contains i 1 balls ] × P[urn j 2 contains i 2 balls ] × • • • × P[urn j k contains i k balls ].
This is proved, by Poissonization-De-Poissonization, in [START_REF] Louchard | On gaps and unoccupied urns in sequences of geometrically distributed random variables[END_REF], [START_REF] Louchard | The number of distinct values of some multiplicity in sequences of geometrically distributed random variables[END_REF] and [START_REF] Hitczenko | Distinctness of compositions of an integer: a probabilistic analysis[END_REF] (in this paper for p = 1/2, but the proof is easily adapted). The error term is O(n -C ) where C is a positive constant.

• ASYMPTOTIC DISTRIBUTIONS. We obtain asymptotic distributions of the interesting RVs as follows. The number of balls in each urn is asymptotically Poisson-distributed with parameter npq j-1 in urn j containing O(1) balls (this is the classical asymptotic for the Binomial distribution). This means that the asymptotic number of balls in urn j is given by exp -npq j-1 npq j-1 ! , and with Q := 1/q, L := ln Q, η = j -log np/q, this is equivalent to P e -Lη , , where P(λ, u) := e -λ λ u /u!. The asymptotic distributions are related to Gumbel distribution functions (given by exp (-e -x )) or convergent series of such. The error term is O(n -1 ).

• EXTENDED SUMMATIONS. Some summations now go to ∞. This is justified, for example, in [START_REF] Louchard | On gaps and unoccupied urns in sequences of geometrically distributed random variables[END_REF].

• UNIFORM INTEGRABILITY. We have uniform integrability for the moments of our RVs. To show that the limiting moments are equivalent to the moments of the limiting distributions, we need a suitable rate of convergence. This is related to a uniform integrability condition (see Loève [START_REF] Loève | Theory[END_REF]Section 11.4]). For the kind of limiting distributions we consider here, the rate of convergence is analyzed in detail in [START_REF] Louchard | Asymptotics of the moments of extreme-value related distribution functions[END_REF] and [START_REF] Louchard | The number of distinct values of some multiplicity in sequences of geometrically distributed random variables[END_REF]. The error term is O(n -C ).

• MELLIN TRANSFORM. Asymptotic expressions for the moments are obtained by Mellin transforms. The error term is O(n -C ). We proceed as follows (see [START_REF] Louchard | Asymptotics of the moments of extreme-value related distribution functions[END_REF] for detailed proofs): from the asymptotic properties of the urns, we have obtained the asymptotic distributions of our RV of interest. Next we compute the Laplace transform φ(α) of these distributions, from which we can derive the dominant part of probabilities and moments as well as the (tiny) periodic part in the form of a Fourier series. This connection will be detailed in the next sections. Note that we will also need the first values of probabilities and moments, obtained via some recurrences.

• SLOW INCREASE PROPERTY. Γ(s) decreases exponentially in the direction i∞:

|Γ(σ + it)| ∼ √ 2π|t| σ-1/2 e -π|t|/2 .
Also, we this property is true for all other functions we encounter. So inverting the Mellin transforms is easily justified.

If we compare the approach in this paper with other ones that appeared previously, then we can notice the following. Traditionally, one would stay with exact enumerations as long as possible, and only at a late stage move to asymptotics. Doing this, one would, in terms of asymptotics, carry many unimportant contributions around, which makes the computations quite heavy, especially when it comes to higher moments. Here, however, approximations are carried out as early as possible, and this allows for streamlined (and often automatic) computations of asymptotic distributions and higher moments.

The present paper falls into the paradigm of combinatorics of geometrically distributed words; many papers have been written on that since the mid-nineties. We cite only the first one in this series: [START_REF] Prodinger | Combinatorics of geometrically distributed random variables: Left-to-right maxima[END_REF] 3 Notation and Plan of the paper

Notation

We will use several abbreviations for probabilities and moments in order to derive more compact expressions. Throughout this work we denote with n the number of initial players; we assume that n is large, we derive asymptotic expansions with respect to n → ∞. Moreover, let n * = n • p q . Since the Poisson distribution is crucial for our approach -early stage asymptotic analysis -we use the shorthand notation P(λ, u) := e -λ λ u /u!. For the asymptotic analysis we use η := j -log n * or η := κ -log n * . The fractional part of x is denoted by {x}.

In the context of combinatorics of geometrically distributed words the following notation is frequently used: Q := 1/q, log := log Q , and L := ln Q. Moreover, M := log p, and χ l := 2lπi L , where i denotes the imaginary unit. The expected values of the parameters of interest number of rounds R n , number of null rounds T n , number L n , in case of failure, of players that were active at the last non-null round, the so-called left-overs, and the total number C n of coins flipped, will be denoted with

R n = E(R n ), T n = E(T n ), L n = E(L n ), C n := E(C n ).
Moreover, the second moments will be denoted with

R (2) n = E(R 2 n ), T (2) n = E(T 2 n ), L (2) n = E(L 2 n ), C (2) n := E(C 2 n ).
Note that the " " notation will always be used, in the sequel, in relation with the failure case, and the tilde will denote that the players were obtained in a null round; for example T i denotes the average number of null rounds, starting with i players, with failure at the end, given that the i players were obtained in a null round, not preceded by another null round.

In our analysis we will encounter certain sums:

Σ 1 (i, τ ) := τ -1 v=0 (p i ) v , Σ 2 (i, τ ) := τ -1 v=0 (p i ) v (v + 1), Σ 3 (i, τ ) := τ -1 v=0 (p i ) v (v + 1) 2 , Σ 4 (i, τ ) := τ -1 v=0 (p i ) v v and Σ 5 (i, τ ) := τ -1 v=0 (p i ) v v 2 .
Closed form expressions can readily be obtained and are given in the Appendix. We will first analyze Model 1: we fail if we have τ consecutive null records. The Model 2: we fail if we have τ null records, consecutive or not, will be briefly considered in Appendix G.

Plan of the paper

The paper is organized as follows: Section 4 is devoted to the success probability, Section 5 to 8 give the asymptotic distribution and first two moments of the RVs of interest (all moments can be derived by the same technique): we compute the dominant and periodic part, both in the success and failure case. Appendices A summarizes some definitions and identities. In [START_REF] Louchard | The swedish leader election protocol: Analysis and variations[END_REF], was presented an analytic treatment of the Swedish leader election protocol. In particular, the success probability and the dominant part of the mean of the following RV was computed: total number of rounds, total number of null rounds, number of left-overs. We prove, in Appendices B to E, the equivalence with the results given in this paper. Some matrix expressions are presented in Appendix F and Appendix G briefly presents the second model where we fail if we have τ null records, consecutive or not. Appendix H gives the proof of Theorem 8.2.

Success probability

In order to analyze the success probability S n we proceed in three steps. First, we deduce basic recurrence relations for the success probability based on the leader election algorithm. Second, we reformulate the problem in terms of the urn model. Third, we carry out the asymptotic analysis: we compute the Laplace transform of the asymptotic distributions, and finally derive the asymptotic expressions for them. It is beneficial to distinguish between starting with i players (used in the recurrences and the asymptotics) and n which denotes the initial number of players. Moreover, for stating the recurrence relations we use the notation P (i) = S i , and P (i) for the probability that, starting with i players, we succeed given that the i players were obtained in a null round, not preceded by another null round. We will first show how to compute the basic probabilities, which will be used in the sequel. Next, as explained in Section 2, we proceed to some asymptotic distributions.

Since we can have up to τ -1 or τ -2 null rounds (all killed), followed by survivors, we readily obtain P (1) = 1, P (1) = 1,

P (i) = τ -1 s=0 (p i ) s i =1 i q p i-P ( ) = Σ 1 (i, τ ) i =1 i q p i-P ( ), i ≥ 2, P (i) = τ -2 s=0 (p i ) s i =1 i q p i-P ( ) = Σ 1 (i, τ -1) i =1 i q p i-P ( ) = Σ 1 (i, τ -1) Σ 1 (i, τ ) P (i), i ≥ 2.
Note that = i in the right-hand side leads to P (i).

Urn model correspondance

Instead of working with the basic recurrence relations, compare with [START_REF] Louchard | The swedish leader election protocol: Analysis and variations[END_REF], we use the fact that the leader election algorithm succeeds if in the corresponding urn model the maximal nonempty urn I = 1 has a single entry, or if it succeeds after a restart (null round) (I > 1). We consider the joint distribution of I and J. Recall that we have asymptotic independence of urns, for all events related to urn j containing O(1) balls. Also the number of balls in each such urn is now Poisson-distributed with parameter npq j-1 in urn j. The asymptotic number of balls in urn j is given by exp -npq j-1 npq j-1 ! = P e -Lη , , with η = j -log n * . The asymptotic probability that urns j + 1, j + 2, . . . are empty is given by ∞ =j+1 e -npq -1 = P q p e -Lη , 0 .

Similar simple calculations lead to P(J = j, I = i) ∼ P q p e -Lη , 0 P e -Lη , i , i ≥ 2, P(J = j, I = 1) ∼ P q p e -Lη , 1 1 -P e -Lη , 0 .

Note that the case i ≥ 2 does not necessarily lead to a success: urn J corresponds to the first null round, hence the multiplication by the success probability P (i). On the other hand, the case i = 1 does lead to a success: urn J corresponds to a round with one single player alive, which is immediately declared as the leader (there are no null rounds before). We have from [START_REF] Louchard | The asymmetric leader election algorithm[END_REF], (here and in the sequel ∼ always denotes ∼ n→∞ ), with η := j -log n * ,

P(J = j, I = i) ∼ exp - 1 p e -Lη e -Lηi i! , i ≥ 2, (1)
P(J = j, I ≥ 2, S) ∼ f 1 (η), f 1 (η) := ∞ i=2 exp - 1 p e -Lη e -Lηi i! P (i), P(J = j, I = 1) ∼ f 2 (η), f 2 (η) := exp - q p e -Lη q p e -Lη 1 -exp -e -Lη . (2)

Asymptotic analysis

We now compute the Laplace transform. This gives

φ 1 (α) = ∞ -∞ e αη f 1 (η)dη = ∞ i=2 (1/p) -i+ α Li! Γ(i -α) P (i).
From [START_REF] Louchard | Asymptotics of the moments of extreme-value related distribution functions[END_REF] the corresponding dominant part of S n is given by

φ 1 (0) = ∞ i=2 p i Li Σ 1 (i, τ -1) Σ 1 (i, τ ) P (i).
The corresponding periodic part is given by

ω 1,1 = l =0 ϕ 1,1 (χ l )e -2lπi{log n * } , with ϕ 1,1 (χ l ) = φ 1 (α) α=-Lχ l .
We obtain

ϕ 1,1 (χ l ) = ∞ i=2 p i+χ l Γ(i + χ l ) Li! Σ 1 (i, τ -1) Σ 1 (i, τ ) P (i).
Also,

φ 2 (α) = ∞ -∞ e αη f 2 (η)dη = 1 L q p α -q 1 p α Γ(1 -α).
Hence

φ 2 (0) = p L = Probability that the maximal non-empty urn contains one ball, (3)
ω 2,1 = l =0 ϕ 2,1 (χ l )e -2lπi{log n * } , ϕ 2,1 (χ l ) = 1 L q p -χ l -q 1 p -χ l Γ(1 + χ l ) = p 1+χ l L Γ(1 + χ l ).
And finally, with notations provided in the Appendix A, we have the following result.

Theorem 4.1 The success probability S n of the asymmetric leader election algorithm with swedish stopping satisfies the asymptotic expansion

S n ∼ ∞ i=2 p i Li Σ 1 (i, τ -1) Σ 1 (i, τ ) P (i) + p L + l =0 ϕ 1,1 (χ l )e -2lπi{log n * } + l =0 ϕ 2,1 (χ l )e -2lπi{log n * } =: V 1 + p L + l =0 ϕ 1,1 (χ l )e -2lπi{log n * } + l =0 ϕ 2,1 (χ l )e -2lπi{log n * } .
It might look paradoxical at first sight, that the asymptotic formula involves the quantities P (i) on the right site. However, that happens often, and convergence is quite good, so that with only a few terms (obtained directly from the recursion) a good approximation of the numerical values can be obtained. This phenomenon will appear in all our subsequent analyses. Of course, the failure probability F n = 1 -S n . Note also that as τ → ∞, the dominant part gives

∞ i=2 p i Li + p L = 1
as expected. For further use, we denote

Π 1 := p L (one ball in the maximal non-empty urn), Π 2 (i) := p i Li , P d(S) = V 1 + p L (dominant part of S n ).
5 Asymptotic distribution and moments of R n -log n * 5.1 Asymptotic distribution and moments of R n -log n * success case

We denote with P R (i, k) the probability that, starting with i players, we succeed after k rounds, and with PR (i, k) the probability that, starting with i players, we succeed after k rounds, given that the i players were obtained in a null round. Furthermore, let R i denote the average number of rounds, starting with i players, with success at the end, and Ri the average number of rounds, starting with i players, with success at the end, given that the i players were obtained in a null round, not preceded by another null round. We will first compute some asymptotic distributions, then the recurrences for the moments and finally the asymptotics for distributions and moments. In case of success, the moments of R n -log n * are computed as in [START_REF] Louchard | The asymmetric leader election algorithm[END_REF], and expressed with some Ri , R

i , instead of x i,S , x (2)
i,S used in [START_REF] Louchard | The asymmetric leader election algorithm[END_REF]. They are computed as described in the sequel. Here and in the sequel, we give the first two moments. All moments could be computed, only with more (algebraic and Maple) efforts.

We use f 1 (η) as given by ( 4) of [START_REF] Louchard | The asymmetric leader election algorithm[END_REF], with PR (i, k) instead of P (i, k) and η := κ -log n * , i.e.,

f 1 (η) = ∞ k=1 ∞ i=2 exp - 1 p e Lk e -Lη e -Lηi e Lki i! PR (i, k).
Above we deal here with the case I ≥ 2. The probability that R = κ is given by the probability that, at some time κ -k, all i players are dead multiplied by the probability that, starting with i players, we succeed after k rounds. The quantity f 2 (η) is given by ( 2). Indeed, in the case

I = 1, R is identical to J.
The first few exact values of the probabilities will be needed in the asymptotic formulae. We can have up to τ -1 or τ -2 null rounds (all killed), followed by survivors. This takes s + 1 rounds already. This leads to the following recurrences.

P R (1, 0) = 1, PR (1, 0) = 1, P R (1, ≥ 1) = 0, PR (1, ≥ 1) = 0, P R (i, k) = τ -1 s=0 (p i ) s i =1 i q p i-P R ( , k -1 -s), i ≥ 2, PR (i, k) = τ -2 s=0 (p i ) s i =1 i q p i-P R ( , k -1 -s), i ≥ 2.
Concerning the first two moments we obtain the following results.

R i = k P R (i, k)k = k τ -1 s=0 (p i ) s i =1 i q p i-P R ( , k -1 -s)[k -1 -s + s + 1], = τ -1 s=0 (p i ) s i =1 i q p i-R + k τ -1 s=0 (p i ) s (s + 1) i =1 i q p i-P R ( , k -1 -s) = Σ 1 (i, τ ) i =1 i q p i-R + Σ 2 (i, τ )P (i)/Σ 1 (i, τ ), R 1 = 0, Ri = k PR (i, k)k = k τ -2 s=0 (p i ) s i =1 i q p i-P R ( , k -1 -s)[k -1 -s + s + 1], = τ -2 s=0 (p i ) s i =1 i q p i-R + k τ -2 s=0 (p i ) s (s + 1) i =1 i q p i-P R ( , k -1 -s) = Σ 1 (i, τ -1) i =1 i q p i-R + Σ 2 (i, τ -1)P (i)/Σ 1 (i, τ ), R1 = 0, R (2) i = k P R (i, k)k 2 = k τ -1 s=0 (p i ) s i =1 i q p i-P R ( , k -1 -s)[k -1 -s + s + 1] 2 , = τ -1 s=0 (p i ) s i =1 i q p i-R (2) + k τ -1 s=0 (p i ) s (s + 1) 2 i =1 i q p i-P R ( , k -1 -s) + 2 τ -1 s=0 (p i ) s (s + 1) i =1 i q p i-R = Σ 1 (i, τ ) i =1 i q p i-R (2) + Σ 3 (i, τ )P (i)/Σ 1 (i, τ ) + 2Σ 2 (i, τ ) i =1 i q p i-R , R (2)
1 = 0, R (2)
i = k PR (i, k)k 2 = k τ -2 s=0 (p i ) s i =1 i q p i-P R ( , k -1 -s)[k -1 -s + s + 1] 2 , = τ -2 s=0 (p i ) s i =1 i q p i-R (2) + k τ -2 s=0 (p i ) s (s + 1) 2 i =1 i q p i-P R ( , k -1 -s) + 2 τ -2 s=0 (p i ) s (s + 1) i =1 i q p i-R = Σ 1 (i, τ -1) i =1 i q p i-R (2) + Σ 3 (i, τ -1)P (i)/Σ 1 (i, τ ) + 2Σ 2 (i, τ -1) i =1 i q p i-R , R(2) 1 = 0.
Note that, in previous expressions, we could replace

i =1 i q p i-R by [R i -Σ 2 (i, τ )P (i)/Σ 1 (i, τ )]/Σ 1 (i, τ ).
As the details of the Laplace transforms are given in [START_REF] Louchard | The asymmetric leader election algorithm[END_REF], we will not repeat them here. Let us however summarize the general connection between φ(α) and the moments of the corresponding RV. From [START_REF] Louchard | Asymptotics of the moments of extreme-value related distribution functions[END_REF], we have

E(R n -log n * ) k ∼ mk + w k , mk = φ (k) (0), w k = l =0 Υ * k (χ l )e -2lπi{log n * } , Υ * k (s) = φ (k) (α) α=-Ls ,
To obtain the moments of R n -log n * , we plug, mutatis mutandis, Ri , R

i into the moments given in [START_REF] Louchard | The asymmetric leader election algorithm[END_REF]. Note that to each value I = i ≥ 2 corresponds P (i) as explained in Section 4. Also A 0 (χ l ) is no more null here and P (1) = 1 by convention. This leads, with the quantities defined in the Appendix A, to the next result.

Theorem 5.1 The asymptotic distribution and moments of the number of rounds R n -log n * in the asymmetric leader election algorithm with swedish stopping, the success case, satisfies

P(R n = κ) ∼ f 1 (η) + f 2 (η), R n -log n * = E(R n -log n * ) ∼ U 1 -M V 1 - V 2 L + pγ L 2 - 1 + pM L + l =0 B 1 (χ l ) -M A 0 (χ l ) - A 1 (χ l ) L - Γ(1 + χ l ) L e -2lπi{log n} , E(R n -log n * ) 2 ∼ U 2 -2M U 1 -2 U 4 L + M 2 V 1 + 2M V 2 L + V 3 + V 4 L 2 + p(π 2 /6 + γ 2 ) L 3 - 2γ(pM + 1) L 2 + pM 2 + 2M + 1 L + l =0 B 2 (χ l ) -2M B 1 (χ l ) -2 B 3 (χ l ) L + M 2 A 0 (χ l ) + 2M A 1 (χ l ) L + A 2 (χ l ) + A 3 (χ l ) L 2 +Γ(1 + χ l ) 2 ψ(1 + χ l ) L 2 + 1 L + 2 M L e -2lπi{log n} .
Note that the periodic component contains {log n} in the exponent (and not {log n * }). Note also that, again, the asymptotics depend on R i on the right-side.

To obtain the moments of R n -log n * , given success, we simply divide the moments given in the theorem by S n .

5.2 Asymptotic distribution and moments of R n -log n * , failure case

The analysis of this RV (as well as the next ones, with the exception of the number of flipped coins) follows the same pattern as the previous ones. We will only present the necessary expressions. In the following we denote with P R (i, k) the probability that, starting with i players, we fail after k rounds, and with P R (i, k) the probability that, starting with i players, we fail after k rounds, given that the i players were obtained in a null round. Moreover, let P (i) denote the probability that, starting with i players, we fail, such that P (i) = 1 -P (i), and let P (i) denote the probability that, starting with i players, we fail, given that the i players were obtained in a null round, such that P (i) = 1 -P (i). Finally, the mean number of rounds, starting with i players, with failure at the end is denoted by R i and the mean number of rounds, starting with i players, with failure at the end, given that the i players were obtained in a null round, is denoted by R i . Note that the " " notation will always be used, in the sequel, in relation with the failure case. In case of failure, the moments of R n -log n * are computed as in [START_REF] Louchard | The asymmetric leader election algorithm[END_REF], with some R i , R(2) i , computed as follows. First we have

P (i) = 1 -P (i) = (p i ) τ + τ -1 s=0 (p i ) s i =1 i q p i-P ( ) = (p i ) τ + Σ 1 (i, τ ) i =1 i q p i-P ( ), i ≥ 2, P (1) = 0.
Next the recurrences: we can have τ or τ -1 null rounds (all killed) at start, leading to failure. We readily obtain.

P R (1, 0) = 0, P R (1, 0) = 0, P R (1, ≥ 1) = 0, P R (1, ≥ 1) = 0, P R (i, k) = (p i ) τ [[k = τ ]] + τ -1 s=0 (p i ) s i =1 i q p i-P R ( , k -1 -s), i ≥ 2, P R (i, k) = (p i ) τ -1 [[k = τ -1]] + τ -2 s=0 (p i ) s i =1 i q p i-P R ( , k -1 -s), i ≥ 2. R i = (p i ) τ τ + Σ 1 (i, τ ) i =1 i q p i-R + Σ 2 (i, τ )[P (i) -(p i ) τ ]/Σ 1 (i, τ ), R 1 = 0, R i = (p i ) τ -1 (τ -1) + Σ 1 (i, τ -1) i =1 i q p i-R + Σ 2 (i, τ -1)[P (i) -(p i ) τ ]/Σ 1 (i, τ ), R 1 = 0,
and similar equations for R

i , R (2)
i . To obtain the moments of

R n -log n * , we plug R i , R (2)
i into the moments given in [START_REF] Louchard | The asymmetric leader election algorithm[END_REF], based only on f 1 (η) as given by (4) of [START_REF] Louchard | The asymmetric leader election algorithm[END_REF], with P R (i, k) instead of P (i, k), and again η := κ -log n * , i.e.,

f 1 (η) = ∞ k=1 ∞ i=2 exp - 1 p e Lk e -Lη e -Lηi e Lki i! P R (i, k).
Indeed, a maximal non-empty urn with only 1 ball leads to a success. Note that to each value I = i ≥ 2 corresponds P (i). Also A 0 (χ l ) is no more null here and P (1) = 0 by convention. This gives Theorem 5.2 The asymptotic distribution and moments of the shifted number of rounds R n -log n * in the asymmetric leader election algorithm with swedish stopping, failure case, satisfies

P (R n = κ) ∼ f 1 (η), R n -log n * = E(R n -log n * ) ∼ U 1 -M V 1 - V 2 L + l =0 B 1 (χ l ) -M A 0 (χ l ) - A 1 (χ l ) L e -2lπi{log n} , E(R n -log n * ) 2 ∼ U 2 -2M U 1 -2 U 4 L + M 2 V 1 + 2M V 2 L + V 3 + V 4 L 2 + l =0 B 2 (χ l ) -2M B 1 (χ l ) -2 B 3 (χ l ) L + M 2 A 0 (χ l ) + 2M A 1 (χ l ) L + A 2 (χ l ) + A 3 (χ l ) L 2 e -2lπi{log n} .
To obtain the moments of R n -log n * , given failure, we simply divide the moments given in the theorem by F n .

6 Asymptotic distribution and moments of T n (null rounds)

6.1 Asymptotic distribution and moments of T n (null rounds), with success

Let P T (i, t) denote the probability that, starting with i players, we succeed with t null rounds, and PT (i, t) the probability that, starting with i players, we succeed with t null rounds, given that the i players were obtained in a null round. Furthermore, we denote with P T (t) the probability that, starting with n players, we succeed with t null rounds, with T i the average number of null rounds, starting with i players, with success at the end, and with Ti the average number of null rounds, starting with i players, with success at the end, given that the i players were obtained in a null round. The analysis is similar to that of R n . Concerning the basic recurrence relations we use the following considerations: we can have up to τ -1 or τ -2 null rounds (all killed), followed by survivors. This leads to s or s + 1 null rounds already. Hence, we obtain:

P T (1, 0) = 1, PT (1, 0) = 1, P T (1, ≥ 1) = 0, PT (1, ≥ 1) = 0, P T (i, t) = τ -1 s=0 (p i ) s i =1 i q p i-P T ( , t -s), i ≥ 2, PT (i, t) = τ -2 s=0 (p i ) s i =1 i q p i-P T ( , t -1 -s), i ≥ 2.
Moreover, the first two moments satisfy

T i = t P T (i, t)t = t τ -1 s=0 (p i ) s i =1 i q p i-P T ( , t -s)[t -s + s], = τ -1 s=0 (p i ) s i =1 i q p i-T + t τ -1 s=0 (p i ) s s i =1 i q p i-P T ( , t -s) = Σ 1 (i, τ ) i =1 i q p i-T + Σ 4 (i, τ )P (i)/Σ 1 (i, τ ), T 1 = 0, Ti = t PT (i, t)t = t τ -2 s=0 (p i ) s i =1 i q p i-P T ( , t -1 -s)[t -1 -s + s + 1], = τ -2 s=0 (p i ) s i =1 i q p i-T + t τ -2 s=0 (p i ) s (s + 1) i =1 i q p i-P T ( , t -1 -s) = Σ 1 (i, τ -1) i =1 i q p i-T + Σ 2 (i, τ -1)P (i)/Σ 1 (i, τ ), T1 = 1, T (2) i = t P T (i, t)t 2 = t τ -1 s=0 (p i ) s i =1 i q p i-P T ( , t -s)[t -s + s] 2 , = τ -1 s=0 (p i ) s i =1 i q p i-T (2) + t τ -1 s=0 (p i ) s s 2 i =1 i q p i-P T ( , t -1 -s) + 2 τ -1 s=0 (p i ) s s i =1 i q p i-T = Σ 1 (i, τ ) i =1 i q p i-T (2) + Σ 5 (i, τ )P (i)/Σ 1 (i, τ ) + 2Σ 4 (i, τ ) i =1 i q p i-T , T (2) 1 = 1,
T

i = t PT (i, t)t 2 = t τ -2 s=0 (p i ) s i =1 i q p i-P T ( , t -1 -s)[t -1 -s + s + 1] 2 , = τ -2 s=0 (p i ) s i =1 i q p i-T (2) + t τ -2 s=0 (p i ) s (s + 1) 2 i =1 i q p i-P T ( , t -1 -s) + 2 τ -2 s=0 (p i ) s (s + 1) i =1 i q p i-T = Σ 1 (i, τ -1) i =1 i q p i-T (2) + Σ 3 (i, τ -1)P (i)/Σ 1 (i, τ ) + 2Σ 2 (i, τ -1) i =1 i q p i-T , T (2)
= 0.

Again, as in previous expressions, we could replace

i =1 i q p i-T by [T i -Σ 4 (i, τ )P (i)/Σ 1 (i, τ )]/Σ 1 (i, τ ).
Next, with (1) and η := j -log n * ,

P(J = j, T n = t) ∼ f 3 (η, t), f 3 (η, t) = ∞ i=2 exp - 1 p e -Lη e -Lηi i! PT (i, t).
Hence

φ 3 (α, t) = ∞ -∞ e αη f 3 (η, t)dη = ∞ i=2 (1/p) -i+ α Li! Γ(i -α) PT (i, t).
Note that there are no null rounds if the maximal non-empty urn contains only 1 ball.

The dominant component of P T (t) is given by

φ 3 (0, t) = ∞ i=2 (1/p) -i Li! Γ(i) PT (i, t) = ∞ i=2 p i Li PT (i, t),
and the periodic component by

ω 1,3 (t) = l =0 ϕ 3 (χ l , t)e -2lπi{log n * } , with ϕ 3 (χ l , t) = φ 3 (α, t) α=-Lχ l .
We obtain

ϕ 3 (χ l , t) = ∞ i=2 p i+χ l Γ(i + χ l ) Li! PT (i, t).
Hence, we have the following theorem.

Theorem 6.1 The asymptotic distribution of the number T n of null rounds, with success, in the asymmetric leader election algorithm with swedish stopping is given by

P T (t) = P(T n = t) ∼ ∞ i=2 p i Li PT (i, t) + l =0 ϕ 3 (χ l , t)e -2lπi{log n * } .
The moments are given by

T n ∼ ∞ i=2 p i Li Ti + l =0 ∞ i=2 p i+χ l Γ(i + χ l ) Li! Ti e -2lπi{log n * } , T (2) n ∼ ∞ i=2 p i Li T (2) i + l =0 ∞ i=2 p i+χ l Γ(i + χ l ) Li! T (2) i e -2lπi{log n * } .
Note that T n = O(1).

Asymptotic distribution and moments of T n (null rounds), with failure

Let P T (i, t) denote the probability that, starting with i players, we fail with t null rounds, and P T (i, t) the probability that, starting with i players, we fail with t null rounds, given that the i players were obtained in a null round. We denote with P T (t) the probability that, starting with n players, we fail with t null rounds, with T i the average number of null rounds, starting with i players, with failure at the end, and with T i the average number of null rounds, starting with i players, with failure at the end, given that the i players were obtained in a null round.

Since we can have τ or τ -1 null rounds (all killed) at start, leading to failure, we obtain the recurrences:

P T (1, 0) = 0, P T (1, 0) = 0, P T (1, ≥ 1) = 0, P T (1, ≥ 1) = 0, P T (i, t) = (p i ) τ [[t = τ ]] + τ -1 s=0 (p i ) s i =1 i q p i-P T ( , t -s), P T (i, t) = (p i ) τ -1 [[t = τ ]] + τ -2 s=0 (p i ) s i =1 i q p i-P T ( , t -1 -s).
Furthermore, the average numbers satisfy

T i = t P T (i, t)t = (p i ) τ τ + t τ -1 s=0 (p i ) s i =1 i q p i-P T ( , t -s)[t -s + s] = (p i ) τ τ + τ -1 s=0 (p i ) s i =1 i q p i-T + t τ -1 s=0 (p i ) s s i =1 i q p i-P T ( , t -s) = (p i ) τ τ + Σ 1 (i, τ ) i =1 i q p i-T + Σ 4 (i, τ )[P (i) -(p i ) τ ]/Σ 1 (i, τ ), T 1 = 0, T i = t P T (i, t)t = (p i ) τ -1 τ + t τ -2 s=0 (p i ) s i =1 i q p i-P T ( , t -1 -s)[t -1 -s + s + 1] = (p i ) τ -1 τ + τ -2 s=0 (p i ) s i =1 i q p i-T + t τ -2 s=0 (p i ) s (s + 1) i =1 i q p i-P T ( , t -1 -s) = (p i ) τ -1 τ + Σ 1 (i, τ -1) i =1 i q p i-T + Σ 2 (i, τ -1)[P (i) -(p i ) τ ]/Σ 1 (i, τ ), T 1 = 0.
Next, with (1), again with η := j -log n * ,

P (J = j, T n = t) ∼ f 4 (η, t), f 4 (η, t) = ∞ i=2 exp - 1 p e -Lη e -Lηi i! P T (i, t).
Hence

φ 4 (α, t) = ∞ -∞ e αη f 4 (η, t)dη = ∞ i=2 (1/p) -i+ α Li! Γ(i -α) P T (i, t).
Note that there are no null rounds if the maximal non-empty urn contains only 1 ball.

The dominant component of P T (t) is given by

φ 4 (0, t) = ∞ i=2 p i Li! Γ(i) P T (i, t),
and the periodic component by

ω 1,4 (t) = l =0 ϕ 4 (χ l , t)e -2lπi{log n * } , with ϕ 4 (χ l , t) = φ 4 (α, t) α=-Lχ l .
We obtain

ϕ 4 (χ l , t) = ∞ i=2 p i+χ l Γ(i + χ l ) Li! P T (i, t).
Hence Theorem 6.2 The asymptotic distribution of the number T n of null rounds, with failure, is given by

P T (t) = P (T n = t) ∼ ∞ i=2 p i Li P T (i, t) + l =0 ϕ 4 (χ l , t)e -2lπi{log n * } .
The moments are given by

T n ∼ ∞ i=2 p i Li T i + l =0 ∞ i=2 p i+χ l Γ(i + χ l ) Li! T i e -2lπi{log n * } , T (2)
n ∼ ∞ i=2 p i Li T (2) i + l =0 ∞ i=2 p i+χ l Γ(i + χ l ) Li! T (2) i e -2lπi{log n * } .
Note that T n = O(1).

7 Asymptotic distribution and moments of L n (leftovers), with failure

Let P L (i, r) denote the probability that, starting with i players, we fail, with r players remaining at the end (leftovers), and P L (i, r) the probability that, starting with i players, we fail, with r players remaining at the end (leftovers), given that the i players were obtained in a null round. Moreover, let P L (r) denote the probability that, starting with n players, we fail, with r players remaining at the end (leftovers). Concern the average numbers we use the notation, L i for the average number of leftovers, starting with i players, with failure at the end, and L i for the average number of leftovers, starting with i players, with failure at the end, given that the i players were obtained in a null round. Since we have r players alive at start or r players alive before the starting null round, we obtain the following recurrences: P L (r, r) = (p r ) τ + Σ 1 (r, τ )q r P L (r, r), hence

P L (r, r) = p rτ (1 -p r ) 1 -p r -q r + q r p rτ , P L (r, r) = (p r ) τ -1 + Σ 1 (r, τ -1)q r P L (r, r).
We can have up to τ -1 or τ -2 null rounds (all killed), followed by survivors.

P L (i, r) = τ -1 s=0 (p i ) s i =r i q p i-P L ( , r) = Σ 1 (i, τ ) i =r i q p i-P L ( , r), i > r, i ≥ 2, P L (i, r) = τ -2 s=0 (p i ) s i =r i q p i-P L ( , r) = Σ 1 (i, τ -1) i =r i q p i-P L ( , r), i > r, i ≥ 2, = Σ 1 (i, τ -1)/Σ 1 (i, τ )P L (i, r), i > r, i ≥ 2.

Moreover, we get

L i = p iτ (1 -p i ) 1 -p i -q i + q i p iτ i + i-1 r=0 P L (i, r)r = p iτ (1 -p i ) 1 -p i -q i + q i p iτ i + Σ 1 (i, τ ) i-1 r=0 i =r i q p i-P L ( , r)r, = p iτ (1 -p i ) 1 -p i -q i + q i p iτ i + Σ 1 (i, τ ) i-1 =0 i q p i- r=0 P L ( , r)r + i-1 r=0 q i P L (i, r)r = p iτ (1 -p i ) 1 -p i -q i + q i p iτ i + Σ 1 (i, τ ) i-1 =0 i q p i-L + q i L i - p iτ (1 -p i ) 1 -p i -q i + q i p iτ i , L i = Σ 1 (i, τ -1) Σ 1 (i, τ ) i-1 r=0 P L (i, r)r + (p i ) τ -1 + Σ 1 (i, τ -1)q i P L (i, i) i,
and similar equations for

L (2) i , L (2)
i . Next, with (1) and η := j -log n * ,

P (J = j, L n = r) ∼ f 5 (η, r), f 5 (η, r) = ∞ i=2 exp - 1 p e -Lη e -Lηi i! P L (i, r).
Hence

φ 5 (α, r) = ∞ -∞ e αη f 5 (η, r)dη = ∞ i=2 (1/p) -i+ α Li! Γ(i -α) P L (i, r).
Note that there are no leftovers if the maximal non-empty urn contains only 1 ball. The dominant component of P L (r) is given by

φ 5 (0, r) = ∞ i=2 (1/p) -i Li! Γ(i) P L (i, r) = ∞ i=2 p i Li Γ(i) P L (i, r),
and the periodic component by

ω 1,5 (r) = l =0 ϕ 5 (χ l , r)e -2lπi{log n * } , with ϕ 5 (χ l , r) = φ 5 (α) α=-Lχ l .
We obtain

ϕ 5 (χ l , r) = ∞ i=2 p i+χ l Γ(i + χ l ) Li! P L (i, r).
Hence Theorem 7.1 The asymptotic distribution of the number L n of leftovers, with failure, is given by

P L (r) = P (L n = r) ∼ ∞ i=2 p i Li Σ 1 (i, τ -1) Σ 1 (i, τ ) P L (i, r) + l =0 ϕ 5 (χ l , r)e -2lπi{log n * } .
The moments are given by

L n ∼ ∞ i=2 p i Li L i + l =0 ∞ i=2 p i+χ l Γ(i + χ l ) Li! L i e -2lπi{log n * } , L (2) n ∼ ∞ i=2 p i Li L(2) i + l =0 ∞ i=2 p i+χ l Γ(i + χ l ) Li! L(2) i e -2lπi{log n * } .
Note that L n = O(1).

8 Asymptotic distribution and moments of C n (coins flipped)

Asymptotic distribution and moments of C n (coins flipped), with success

This RV is more delicate to analyze. In previous cases, all interesting RV were related to urns (at high level) containing O(1) balls. Here all urns contribute to C n , so we must include the contribution of urns before J, which actually lead to the dominant part of C n . Also some correlations must be taken into account. We obtain the dominant and corrected terms of the moments as well as a central limit theorem. Let C i denote the Average number of coins flipped, starting with i players, with success at the end, and Ci the average number of coins flipped, starting with i players, with success at the end, given that the i players were obtained in a null round.

Case I = 1

Note that, as explained in Section 4, this case entails a success. We will only deal here with the nonperiodic part of our expressions. The maximal non-empty urn contains 1 ball and the position of the last non-empty urn before this maximal non-empty urn is denoted by J. Let us also denote by K the number of balls in urn J.

P(J = j, K = k) ∼ f 6 (η, k), k ≥ 1, f 6 (η, k) := exp - q p e -Lη q p e -Lη exp -e -Lη e -Lηk k! , = exp - 1 p e -Lη q p e -Lη(k+1) k! , because P(J = j, K = k) ∼ P
q p e -Lη , 1 P e -Lη , k .

We have

φ 6 (α, k) = ∞ -∞ e αη f 6 (η, k)dη = q Lk! 1 p α-k Γ(1 -α + k), Π 4 (k) := φ 6 (0, k) = q L p k .
Note that

Z 1 := ∞ k=1 Π 4 (k) = p L
≡ Π 1 (one ball in the maximal non-empty urn) which conforms to (3). Let us denote by ∆ the difference between the maximal non-empty urn (containing 1 ball) and J. We have

P(J = j, I = 1, ∆ = δ) ∼ f 7 (η, δ), f 7 (η, δ) := exp - q p e -Lη e -L(η+δ) 1 -exp -e -Lη , = exp(-Lδ) exp - q p e -Lη e -Lη 1 -exp -e -Lη ,
which shows that ∆ is asymptotically independent of J. This can readily be seen as follows:

P(J = j, I = 1, ∆ = δ) ∼ P e -L(η+1) , 0 P e -L(η+2) , 0 . . . . . . P e -L(η+δ) , 1 P e -L(η+δ+1) , 0 . . . 1 -P e -Lη , 0 .

We have

φ 7 (α, δ) = ∞ -∞ e αη f 7 (η, δ)dη = exp(-Lδ) p Lq q p α -q 1 p α Γ(1 -α), Π 5 (δ) := φ 7 (0, δ) = e -Lδ p 2 Lq = q δ p 2 Lq .
Note that

∞ δ=1 Π 5 (δ) = p L ≡ Π 1
which again conforms to (3). We have

E(∆) = 1 L and E(∆ 2 ) = 1 + q Lp .
However, note carefully that the player corresponding to I = 1 is actually related to a flipped coin in urn J. So we must use a new RV G, denoting the number of flipped coins at step J:

G = K + 1, G ≥ 2, with distribution Π 6 (g) = q L p g-1 , g ≥ 2 and f 8 (η, g) = exp - 1 p e -Lη q p e -Lηg (g -1)
! .

We will also need

Z 5 = E(G) := ∞ g=2 Π 6 (g)g = p(1 + q) Lq .
Later on, we will use the following variants:

e -Lη f 8 (η, g), e -2Lη f 8 (η, g), ηf 8 (η, g), e -Lη ηf 8 (η, g), e -2Lη ηf 8 (η, g).

These variants lead respectively to φ . (0, g):

p g qg L , qp g+1 g(g + 1) L , - p g-1 q[(g -1) ln(p) + (g -1)ψ(g -1) + 1] L 2 (g -1) , -qp g [2(g -1) + (g -1) 2 ln(p) + (g -1) 2 ψ(g -1) + (g -1) ln(p) +(g -1)ψ((g -1)) + 1]] /[L 2 (g -1)],
Ω 15 (g) is too long to be displayed here.

This leads to Z 7 , Z 8 , Z 11 , Z 12 , Z 10 , Z 13 , Z 15 as given in Appendix A: we simply sum on g ≥ 2. Indeed, the case I = 1 immediately leads to a success. Now we will separate the contribution of urn J (containing G balls) from that of urns < J.

Let us denote by S Γ (j, i) the sum of (n -i) iid RV Γ(j), and Γ(j) is a truncated geometric RV < j. As Σ 0 := j-1 l=1 pq l-1 = 1 -q j-1 , we have (we give only the terms needed in the sequel) 1) .

E(j) := E(Γ(j)) = j-1 l=1 pq l-1 l/Σ 0 ∼ 1 p + q j-1 -jq j-1 -jq 2(j-1) + O q 2(j-1) , E (2) (j) := E(Γ(j) 2 ) = j-1 l=1 pq l-1 l 2 /Σ 0 ∼ 1 + q p 2 + q j-1 1 + q p -j 2q p q j-1 -j 2 q j-1 + O j 2 q 2(j-
Note that, with j = η + log n * , q j = e -Lη 1 n * . This leads, by carefully taking into account the correlation between J and G (we expand the mean up to the log n * /n * term and the square mean up to the log n * term) to (there are n -G dead players before attaining step J)

C n,1 ∼ S Γ (J, G) + JG, (4)
E(C n,1 ) ∼ E(S Γ (J, G) + JG), ∼ E (n -G) 1 p + n q e -Lη n * - n -G q e -Lη n * (log n * + η) - n q 2 e -2Lη n * 2 log n * + (log n * + η)G ∼ n p Z 1 - 1 p Z 5 + n q Z 7 n * - n q Z 7 n * log n * + 1 q Z 8 n * log n * - n q Z 10 n * - n q 2 Z 11 n * 2 log n * + Z 5 log n * + Z 13 , (5)
E(C 2 n,1 ) ∼ E((S Γ (J, G) + JG) 2 ) ∼ E[nE (2) (J) + (n -G)(n -G -1)(E(J)) 2 + 2E[(n -G)E(J)JG] + E[(log n * + η) 2 G 2 ]. (6)

Case I > 1

First of all, we must compute the moments of C i and Ci . This gives

C i = τ -1 s=0 (p i ) s i =1 i q p i-[si + i + C ], C 1 = 0, C (2) i
= τ -1 s=0 (p i ) s i =1 i q p i-E[((s + 1)i + C ) 2 ] = τ -1 s=0 (p i ) s i =1 i q p i-[((s + 1)i) 2 + 2(s + 1)iC + C (2) ],
and similar expressions for Ci , C

i . Next, with (1),

P(J = j, I = i) ∼ f 9 (η, i), f 9 (η, i) := exp - 1 p e -Lη e -Lηi i! , P(J = j) ∼ f 10 (η), f 10 (η) = ∞ i=2 exp - 1 p e -Lη e -Lηi i! = exp - 1 p e -Lη exp -e -Lη -1 -e -Lη , φ 9 (α, i) = ∞ -∞ e αη f 9 (η, i)dη = (1/p) -i+ α Li! Γ(i -α), Π 2 (i) := φ 9 (0, i) = p i Li , P 0 := ∞ i=2 Π 2 (i) = 1 -p/L.
Later on, we will use the following variants:

e -Lη f 9 (η, i), e -2Lη f 9 (η, i), ηf 9 (η, i), e -Lη ηf 9 (η, i), e -2Lη ηf 9 (η, i).

These variants lead respectively to φ . (0, i):

p i p L , p i p 2 (i + 1) L , - p i [ln(p) + ψ(i)] L 2 i , - p i p[i ln(p) + iψ(i) + 1] L 2 i , - p i p 2 [i 2 ln(p) + i 2 ψ(i) + 2i + i ln(p) + iψ(i) + 1] L 2 i .
Multiplying by P (i) and summing on i ≥ 2, this leads to V 7 , V 5 , V 8 , V 11 , V 12 , V 10 , V 13 , V 15 . Indeed, the case I > 1 does not immediately lead to a success. Again we expand the mean up to the log n * /n * term and the square mean up to the log n * term. We have (there are n -I dead players before attaining step J)

C n,2 ∼ S Γ (J, I) + JI + CI , (7)
E(C n,2 ) ∼ E(S Γ (J, I) + JI + CI ) ∼ E(S Γ (J, I) + JI) + U 1 ∼ E (n -I) 1 p + n q e -Lη n * - n -I q e -Lη n * (log n * + η) - n q 2 e -2Lη n * 2 log n * + (log n * + η)I + U 1 ∼ n p V 1 - 1 p V 5 + n q V 7 n * - n q V 7 n * log n * + 1 q V 8 n * log n * - n q V 10 n * - n q 2 V 11 n * 2 log n * + V 5 log n * + V 13 + U 1 , (8)
E(C 2 n,2 ) ∼ E((S Γ (J, I) + JI) 2 ) + 2E[(S Γ (J, I) + JI) CI ] ∼ E((S Γ (J, I) + JI) 2 ) + 2E n p - n q e -Lη n * log n * + I log n * CI ∼ E((S Γ (J, I) + JI) 2 ) + 2 n p U 1 - n q U 3 n * log n * + U 5 log n * ∼ E[nE (2) (J) + (n -I)(n -I -1)(E(J)) 2 + 2E[(n -I)E(J)JI] + E[(log n * + η) 2 I 2 ] + 2 n p U 1 - n q U 3 n * log n * + U 5 log n * .

General case.

The total mean is given by (we provide here only two terms)

C n = E(C n ) ∼ E(C n,1 ) + E(C n,2 ) ∼ n p L + V 1 1 p + - Z 7 p + Z 5 - V 7 p + V 5 log n * .
Recall that p L + V 1 is equal to P d (S) as defined before. But the first term amounts to the mean of a sum of n GEOM pq l-1 RVs. (Indeed, the GEOM pq l-1 RV has mean 1 p , second moment 1+q p 2 and variance q p 2 ). This is easy to explain: from ( 4) and ( 7), the correction CI,S is asymptotically O(1) and the correction -∆ is also asymptotically O [START_REF] Bondesson | Probability calculus for silent elimination : A method for medium access control[END_REF]. Similarly

E(C 2 n ) ∼ E(C 2 n,1 ) + E(C 2 n,2 ) ∼ n 2 p L + V 1 1 p 2 + n - 2(Z 7 -pZ 5 ) p 2 - 2(V 7 -pV 5 ) p 2 log n *
and the variance is finally given by (we must adequately condition on the dominant success probability P d(S)

:= p L + V 1 ) V(C n ) ∼ P d(S) E(C 2 n ) P d(S) - E(C n ) P d(S) 2 ∼ P d(S)n q p 2 . A2(χ l ) := ∞ i=1 p i Li! Γ(i + χ l )ψ(1, i + χ l ) P (i), A3(χ l ) := ∞ i=1 p i Li! Γ(i + χ l )ψ 2 (i + χ l ) P (i), B1(χ l ) := ∞ i=2 p i Li! ξiΓ(i + χ l ), B2(χ l ) := ∞ i=2 p i Li! ξ(2) i Γ(i + χ l ), B3(χ l ) ∞ i=2 p i Li! ξiψ(i + χ l )Γ(i + χ l ), U1 := ∞ i=2 p i ξi Li , U2 := ∞ i=2 p i ξ(2) i Li , U3 := ∞ i=2 pp i ξi L , U4 := ∞ i=2 p i ξiψ(i) i , U5 := ∞ i=2 p i i ξi Li , Z7 := p 2 [2 -3p + p 2 ] q 2 L , Z8 := ∞ g=2 p g qg 2 L = p 2 [4 -3p + p 2 ] q 2 L , Z11 := 2p 3 (p 2 -3p + 3) Lq 2 , Z12 := ∞ g=2 - p g-1 q[(g -1) ln(p) + (g -1)ψ(g -1) + 1] L 2 (g -1) , Z10 := ∞ g=2 - qp g [2(g -1) + (g -1) 2 ln(p) + (g -1) 2 ψ((g -1)) + (g -1) ln(p) + (g -1)ψ((g -1)) + 1] L 2 (g -1) , Z13 := ∞ g=2 - p g-1 q[(g -1) ln(p) + (g -1)ψ((g -1)) + 1]g L 2 (g -1) , Z15 := ∞ g=2 Ω15(g).
The quantities Σ1(i, τ ) can be expressed in the following way:

Σ1(i, τ ) := τ -1 v=0 (p i ) v = 1 -p iτ 1 -p i , Σ2(i, τ ) := τ -1 v=0 (p i ) v (v + 1) = p iτ (-1 + τ p i -τ ) + 1 (1 -p i ) 2 , Σ3(i, τ ) := τ -1 v=0 (p i ) v (v + 1) 2 = p iτ (p i + 1 -2τ p i + 2τ + τ 2 p 2i -2τ 2 p i + τ 2 ) -p i + 1 (1 -p i ) 3 , Σ4(i, τ ) := τ -1 v=0 (p i ) v v = p iτ (τ p i -τ -p i ) + p i (1 -p i ) 2 , Σ5(i, τ ) := τ -1 v=0 (p i ) v v 2 = p iτ (p i + 2τ p i + τ 2 p 2i -2τ 2 p i + τ 2 + p 2i -2τ p 2i ) -p 2i + p i (1 -p i ) 3 .

B Success Probability

We show here that, where the results are given both, here, and in [START_REF] Louchard | The swedish leader election protocol: Analysis and variations[END_REF], they coincide. First, we look at Theorem 4.1.

The constant is given by

1 L k≥2 S k p k k 1 -p (τ -1)k 1 -p τ k + p L ,
and it should coincide with

1 L qp τ + k≥1 S k k p k - q k p τ k (1 -q τ +1 ) k .
We use the notation Sn from [START_REF] Louchard | The swedish leader election protocol: Analysis and variations[END_REF] as in this paper. We have the recursion

1 -p k 1 -p τ k S k = k j=1 k j p k-j q j Sj. Therefore k≥2 S k p k k 1 -p (τ -1)k 1 -p τ k = k≥2 S k p k k 1 -p τ k + p τ k -p (τ -1)k 1 -p τ k = k≥2 S k p k k - k≥2 S k p τ k 1 -p k 1 -p τ k = k≥2 S k p k k - k≥2 p τ k k k j=1 k j p k-j q j Sj = k≥1 S k p k k -p + p τ q - j≥1 q j Sj j k≥j p τ k k -1 j -1 p k-j = k≥1 S k p k k -p + p τ q - j≥1 q j Sj j p τ j (1 -p τ +1 ) j ,
which is the desired formula after trivial modifications.

For the Fourier coefficients, we have to prove that

pΓ(χ l + 1) + k≥2 S k p k k! 1 -p (τ -1)k 1 -p τ k Γ(χ l + k) = qp τ Γ(χ l + 1) + k≥1 S k k! Γ(χ l + k) p k - q k p τ k (1 -q τ +1 ) χ l +k ,
which is done in a similar way:

k≥2 S k p k k! 1 -p (τ -1)k 1 -p τ k Γ(χ l + k) = k≥2 S k p k k! 1 -p τ k + p τ k -p (τ -1)k 1 -p τ k Γ(χ l + k) = k≥1 S k p k k! Γ(χ l + k) -pΓ(χ l + 1) - k≥2 p τ k k! Γ(χ l + k) k j=1 k j p k-j q j Sj = k≥1 S k p k k! Γ(χ l + k) -pΓ(χ l + 1) - j≥1 q j Sj j! k≥j p τ k Γ(χ l + k) 1 (k -j)! p k-j + qp τ Γ(χ l + 1) = k≥1 S k p k k! Γ(χ l + k) -pΓ(χ l + 1) + qp τ Γ(χ l + 1) - j≥1 q j Sj j! Γ(χ l + j)p τ j (1 -p τ +1 ) χ j +k ,
which is the formula.

C Total number of rounds

Notations: PR(i, k) := Probability that, starting with i players, we end after k rounds, PR(i, k) := Probability that, starting with i players, we end after k rounds, given that the i players were obtained in a null round, not preceded by another null round.

Next we turn to the nonfluctuating part of Rn. We must use the total number of rounds: Ri = Ri + R i . Now from Theorems 5.1 and 5.2, we have

Rn -log n * = E(Rn -log n * ) ∼ Ū1 -M V1 - V2 L + pγ L 2 - 1 + pM L + l =0 B1(χl) -M Ā0(χl) - Ā1(χl) L - Γ(1 + χ l ) L e -2lπi{log n}
where, now,

B1(χl) := ∞ i=2 p i Li! RiΓ(i + χ l ), Ū1 := ∞ i=2 p i Ri Li , Ā0(χl) := 0, Ā1(χl) := Γ(χ l ), V1 := L -p L , V2 := L 2 - γ(L -p) L .
We have the following recurrences, with PR now combining S and F ,

PR(1, 0) = 1, PR(1, 0) = 1, PR(i, k) = (p i ) τ [[k = τ ]] + τ -1 s=0 (p i ) s i =1 i q p i-PR( , k -1 -s), i ≥ 2, PR(i, k) = (p i ) τ -1 [[k = τ -1]] + τ -2 s=0 (p i ) s i =1 i q p i-PR( , k -1 -s), i ≥ 2. Ri = k PR(i, k)k = (p i ) τ τ + k τ -1 s=0 (p i ) s i =1 i q p i-PR( , k -1 -s)[k -1 -s + s + 1], = (p i ) τ τ + τ -1 s=0 (p i ) s i =1 i q p i-R + k τ -1 s=0 (p i ) s (s + 1) i =1 i q p i-PR( , k -1 -s) = (p i ) τ τ + Σ1(i, τ ) i =1 i q p i-R + Σ2(i, τ ) 1 -(p i ) τ /Σ1(i, τ ), = 1 -p iτ 1 -p i i =1 i q p i-R + 1 -p iτ 1 -p i , R1 = 0, Ri = k PR(i, k)k = (p i ) τ -1 (τ -1) + Σ1(i, τ -1) i =1 i q p i-R , + Σ2(i, τ -1) 1 -(p i ) τ /Σ1(i, τ ) = (p i ) τ -1 (τ -1) + Σ1(i, τ -1) Ri -Σ2(i, τ ) 1 -(p i ) τ /Σ1(i, τ ) -(p i ) τ /Σ1(i, τ ) + Σ2(i, τ -1) 1 -(p i ) τ /Σ1(i, τ ) = Ri 1 -p i -p i(τ -1) + p iτ (1 -p iτ )(1 -p i ) = Ri 1 -p i(τ -1) 1 -p iτ , R1 = 0.
In [START_REF] Louchard | The swedish leader election protocol: Analysis and variations[END_REF], the following recursion is derived:

Rn(τ ) = n j=1 n j p n-j q j Rj(τ ) + p n Rn(τ -1) + 1, τ > 0, n ≥ 2,
and the interest is in Rn = Rn(τ ). We write

Rn(τ ) = Dn(τ ) + p n Rn(τ -1) = Dn(τ ) + p n (Rn(τ ) + Rn(τ -2)) = • • • = 1 -p τ n 1 -p n Dn(τ ).
We find the recursion

Rn = 1 -p τ n 1 -p n n j=1 n j p n-j q j Rj + 1 -p τ n 1 -p n .
This coincides with the recursion given here. Now

Ū1 -M V1 - V2 L + pγ L 2 - 1 + pM L = ∞ i=2 p i Ri Li - ln p L L -p L - 1 L L 2 - γ(L -p) L + pγ L 2 - 1 L - p ln p L 2 = 1 L ∞ i=2 p i (1 -p i(τ -1) ) i Ri 1 -p iτ - ln p L - 1 2 + γ L - 1 L = 1 L ∞ i=2 p i (1 -p iτ + p iτ -p i(τ -1) ) i Ri 1 -p iτ - ln p L - 1 2 + γ L - 1 L = 1 L ∞ i=2 p i Ri i - 1 L ∞ i=2 p iτ i Ri(1 -p i ) 1 -p iτ - ln p L - 1 2 + γ L - 1 L = 1 L ∞ i=2 p i Ri i - 1 L ∞ i=1 p iτ i i j=1 i j p i-j q j Rj - 1 L ∞ i=1 p iτ i + p τ L - ln p L - 1 2 + γ L - 1 L = 1 L ∞ i=2 p i Ri i - 1 L j≥1 q j Rj j i≥j p iτ i -1 j -1 p i-j + 1 L ln(1 -p τ ) + p τ L - ln p L - 1 2 + γ L - 1 L = 1 L ∞ i=2 p i Ri i - 1 L j≥1 q j Rj j p jτ (1 -p τ +1 ) j + 1 L ln(1 -p τ ) + p τ L - ln p L - 1 2 + γ L - 1 L .
Thus the constant term in the asymptotic expansion of Rn -log n is

ln p L + 1 + 1 L ∞ i=2 p i Ri i - 1 L j≥1 q j Rj j p jτ (1 -p τ +1 ) j + 1 L ln(1 -p τ ) + p τ L - ln p L - 1 2 + γ L - 1 L = 1 L i≥2 p i Ri i - 1 L j≥2 q j Rj j p jτ (1 -p τ +1 ) j + 1 L ln(1 -p τ ) + p τ L + 1 2 + γ L - 1 L .
This is the expansion that was also obtained in [START_REF] Louchard | The swedish leader election protocol: Analysis and variations[END_REF].

D Total number of null rounds

Notations:

PT (i, t) := Probability that, starting with i players, we end with t null rounds, PT (i, t) := Probability that, starting with i players, we end with t null rounds, given that the i players were obtained in a null round.

We have the recurrences:

PT (1, 0) = 1, PT (1, 1) = 1, PT (i, t) = (p i ) τ [[t = τ ]] + τ -1 s=0 (p i ) s i =1 i q p i-PT ( , t -s), PT (i, t) = (p i ) τ -1 [[t = τ ]] + τ -2 s=0 (p i ) s i =1 i q p i-PT ( , t -1 -s). Ti = t PT (i, = (p i ) τ τ + t τ -1 s=0 (p i ) s i =1 i q p i-PT ( , t -s)[t -s + s] = (p i ) τ τ + τ -1 s=0 (p i ) s i =1 i q p i-T + t τ -1 s=0 (p i ) s s i =1 i q p i-PT ( , t -s), = (p i ) τ τ + Σ1(i, τ ) i =1 i q p i-T + Σ4(i, τ )[1 -(p i ) τ ]/Σ1(i, τ ) = 1 -p iτ 1 -p i i =1 i q p i-T + p i 1 -p iτ 1 -p i , T1 = 0. Ti = t PT (i, t)t = (p i ) τ -1 τ + t τ -2 s=0 (p i ) s i =1 i q p i-PT ( , t -1 -s)[t -1 -s + s + 1] = (p i ) τ -1 τ + τ -2 s=0 (p i ) s i =1 i q p i-T + t τ -2 s=0 (p i ) s (s + 1) i =1 i q p i-PT ( , t -1 -s) = (p i ) τ -1 τ + Σ1(i, τ -1) Ti -(p i ) τ τ -Σ4(i, τ )[1 -(p i ) τ ]/Σ1(i, τ ) /Σ1(i, τ ) + Σ2(i, τ -1)[1 -(p i ) τ ]/Σ1(i, τ ) = 1 -p i + p i(τ +1) -p iτ (1 -p iτ )(1 -p i ) + 1 -p i -p i(τ -1) + p iτ (1 -p iτ )(1 -p i ) Ti = 1 + 1 -p i(τ -1) 1 -p iτ Ti, T1 = 1.
The mean is given by

Tn ∼ ∞ i=2 p i Li Ti + l =0 ∞ i=2 p i+χ l Γ(i + χ l ) Li! Tie -2lπi{log n * } .
Indeed, In from the paper [START_REF] Louchard | The swedish leader election protocol: Analysis and variations[END_REF] satisfies the same recursion as here, after unwinding it as shown in the previous example. And now we look at the nonfluctuating part in the asymptotic expansion of the mean:

∞ i=2 p i Li Ti = 1 L n≥2 p n n 1 + 1 -p n(τ -1) 1 -p nτ Tn = 1 L (-ln(1 -p) -p) + 1 L n≥2 p n n 1 -p nτ + p nτ -p n(τ -1) 1 -p nτ Tn = 1 - p L + 1 L n≥2 p n n Tn - 1 L n≥2 p nτ n 1 -p n 1 -p nτ Tn = 1 - p L + 1 L n≥1 p n n Tn - 1 L n≥2 p nτ n 1≤j≤n n j q j p n-j Tj + p n = 1 - p L + 1 L n≥1 p n n Tn - 1 L n≥1 p n(τ +1) n + p τ +1 L - 1 L n≥1 p nτ n 1≤j≤n n j q j p n-j Tj = 1 - p L + 1 L ln(1 -p τ +1 ) + p τ +1 L + 1 L n≥1 p n n Tn - 1 L j≥1 q j Tj j n≥j n -1 j -1 p nτ p n-j = 1 - p L + 1 L ln(1 -p τ +1 ) + p τ +1 L + 1 L n≥1 p n n Tn - 1 L j≥1 q j Tj j p jτ (1 -τ τ +1 ) j .
This is the expression given in [START_REF] Louchard | The swedish leader election protocol: Analysis and variations[END_REF].

E Total number of leftovers

We have here only the failure case. This gives

L i =
p iτ (1 -p i ) 1 -p i -q i + q i p iτ i + Σ1(i, τ ) i-1 =0 i q p i-L + q i L i -p iτ (1 -p i ) 1 -p i -q i + q i p iτ i L i = p i(τ -1) + 1 -p i(τ -1) 1 -p i q i p iτ (1 -p i ) 1 -p i -q i + q i p iτ i + 1 -p i(τ -1) 1 -p iτ L i -p iτ (1 -p i ) 1 -p i -q i + q i p iτ i = 1 -p i(τ -1) 1 -p iτ L i + p i(τ -1) (1 -p i ) 1 -p iτ i.

1 -p iτ + p iτ -p i(τ -1) 1 -

p iτ L i + 1 L i≥2 p iτ (1 -p i ) 1 -p iτ = 1 L i≥2 p i i L i - 1 L i≥2 p iτ i i j=1 i j p i-j q j L j + 1 -p i 1 -p iτ ip iτ + 1 L i≥2 p iτ (1 -p i ) 1 -p iτ = 1 L i≥2 p i i L i - 1 L i≥2 p iτ i i j=1 i j p i-j q j L j - 1 L i≥2 1 -p i 1 -p iτ p 2iτ + 1 L i≥2 p iτ (1 -p i ) 1 -p iτ = 1 L i≥2 p i i L i - 1 L j≥1 q j L j j i≥j p iτ i -1 j -1 p i-j + 1 L i≥2 p iτ (1 -p i ) = 1 L i≥2 p i i L i - 1 L j≥1 q j L j j q jτ (1 -p τ +1 ) j + 1 L 1 1 -p τ - 1 L 1 1 -p τ +1 -qp τ ,
which is the same expression as in [START_REF] Louchard | The swedish leader election protocol: Analysis and variations[END_REF].

F Matrix expressions.

We will give a few explicit matrix expressions for several quantities computed before. We will not use these expressions, but we only wanted to show that some compact relations can be written down in some cases, showing an unified view of our different RV.

P (i, τ ) = τ -2 s=0 (p i ) s i =1
i q p i-P ( , τ -s -1) = P (i, τ -1), PR(i, k, τ ) = τ -1 s=0 (p i ) s i =1 i q p i-PR( , k -1 -s, τ -s), i ≥ 2, PR(i, k, τ ) = τ -2 s=0 (p i ) s i =1 i q p i-PR( , k -1 -s, τ -s -1) = PR(i, k, τ -1),

Ri(τ ) = τ -1 s=0 (p i ) s i =1 i q p i-R (τ -s) + τ -1 s=0 (p i ) s (s + 1) i =1
i q p i-P ( , τ -s), Ri(τ ) = Ri(τ -1),

Ci(τ ) = τ -1 s=0 (p i ) s i =1 i q p i-[si + i + C (τ -s)],
Ci(τ ) = Ci(τ -1),

PT (i, t, τ ) = τ -1 s=0 (p i ) s i =1 i q p i-PT ( , t -s, τ -s), i ≥ 2, PT (i, t) = τ -2 s=0 (p i ) s i =1 i q p i-PT ( , t -1 -s, τ -s -1), i ≥ 2, Ti(τ ) = τ -1 s=0 (p i ) s i =1 i q p i-T (τ -s) + τ -1 s=0 (p i ) s s i =1 i q p i-P ( , τ -s) Ti = τ -2 s=0 (p i ) s i =1
i q p i-T (τ -s -1) + τ -2 s=0 (p i ) s (s + 1) i =1 i q p i-P ( , τ -s -1), P L (r, r, τ ) = (p r ) τ + Σ1(r, τ )q r P L (r, r, τ ), P L (r, r, τ ) = P L (r, r, τ -1), P L (i, r, τ ) = τ -1 s=0 (p i ) s i =r i q p i-P L ( , r, τ -s), i > r, i ≥ 2, P L (i, r, τ ) = τ -2 s=0 (p i ) s i =r i q p i-P L ( , r, τ -s -1) = P L (i, r, τ -1), L i (τ ) = τ -1 s=0 i =r i q p i- i-1 r=0 P L ( , r, τ -s)r + [(p i ) τ + q i P L (i, i, τ )]i, L i = L i (τ -1). and the PGF of SΓ(j, 0) is given by [F (z)] n . We will now use the Saddle point method (for a good introduction to this method, see Flajolet and Sedgewick [3, chapter VIII]). By Cauchy's theorem,

One can now proceed as in Model

P(SΓ(j, 0) = k) = 1 2πi Ω [F (z)] n z k+1 dz = 1 2πi Ω e H(z) dz,
where Ω is inside the domain of analyticity of the integrand and encircles the origin and

H(z) = n ln pz 1 -qz - e -Lη z j n(1 -qz)
-ln(Σ0) -(k + 1) ln(z).

Set H (i) := d i H dz i . First we must find the solution of H (1) (z) = 0 (H.1) with smallest modulus. Set z := z * -ε, where z * = limn→∞ z. Here, it is easy to check that z * = 1. Set k = nE(j) + √ nσ(j)x, x fixed. We will soon see that ε = O 1 √ n , so we can expand z j in F (z) as This shows that, asymptotically, ε is given by a series of powers of n -1/2 , where each coefficient is given by a series of powers of log n * . To obtain more precision, we set again k = nE(j) + √ nσ(j)x, expand in powers of n -1/2 , and equate each coefficient to 0. We have, with z := z * -ε = 1 -ε,

P(SΓ(j, 0) = k) = 1 2πi Ω exp H(z) + H (2) (z)(z -z) 2 /2! + ∞ l=3
H (l) (z)(z -z) l /l! dz.

Note that the linear term vanishes. Set z = z + iτ . This gives

P(SΓ(j, 0) = k) ∼ 1 2π exp[H(z)] ∞ -∞ exp H (2) (z)(iτ ) 2 /2! + ∞ l=3 H (l) (z)(iτ ) l /l! dτ. (H.2)
Let us first analyze H(z). We obtain

H(z) = -x 2 /2 + O 1 √ n .

1 .HF

 1 Proof of Theorem 8.2 We start from Cn,S = [[I = 1]][SΓ,1(J, G) + JG] + [[I > 1]][SΓ,2(J, I) + JI + CI,S]. Now the probability generating function (PGF) of Γ(j) is given by

z j = 1

 1 -jε + j(j -1) 2 ε 2 + • • • Also j = log n * + η.This leads, to first order (keeping only the ε term in (H.1)), to

  • ASYMPTOTIC INDEPENDENCE. We have asymptotic independence of urns, for all events related to urn j containing O(1) balls. This means, for instance that

P[urn j 1 contains i 1 balls ; urn j 2 contains i 2 balls ; . . . ; urn j k contains i k balls, where i 1 , i 2 , . . . , i k

Acknowledgments

The insightful comments of two referees are gratefully acknowledged. Moreover, we would like to thank M. Kuba for many useful suggestions and editorial assistance that greatly improved the quality of this paper.

So we obtain

Theorem 8.1 The moments of C n in case of success, are given by (with Maple, more terms could be provided, in particular the log 2 n * and log n * terms of the variance)

Note again that the dominant term of the variance corresponds to a sum of n iid GEOM pq l-1 RVs. Intuitively, the asymptotic distribution should be Gaussian: again from ( 4) and [START_REF] Louchard | The swedish leader election protocol: Analysis and variations[END_REF], the correction CI,S is asymptotically O(1), but not independent of the dominant term and the correction -∆ is also asymptotically O(1), but independent of the dominant term. Actually we have the following theorem.

Theorem 8.2 Conditioned on a success,

where φ(x) denotes the Gaussian distribution function.

The proof is given in Appendix H. See also Kalpathy et al. [START_REF] Kalpathy | Asymptotic properties of a leader election algorithm[END_REF], for a leader election scheme which stops if I > 1. In this model, C n is shown to be asymptotically Gaussian.

Distribution of C n (number coins flipped), with failure

Only the case I > 1 matters here. Proceeding as before (we omit the details), we finally derive Theorem 8.3 The moments of C n in case of failure, are given by

Again, the distribution should be asymptotically Gaussian, but we did not check the details.

Appendix

A Some definitions and identities

Here, ξ ∈ {R, T, L, C}. ξi must be replaced by ξi or ξ i depending on the case we consider. Also P (i) must be replaced by P (i) or P (i), respectively. Note that, compared with [START_REF] Louchard | The asymmetric leader election algorithm[END_REF], we use here Π2(i) = p i Li instead of p i i , for V1, . . . , V5. Also we have P (1) = 1, P (1) = 0.

The mean is given by

The recursion derived in [START_REF] Louchard | The swedish leader election protocol: Analysis and variations[END_REF] is

Here, we have

and hence we do have the same recursion. Now we turn to the nonfluctuating part of the mean:

Then we have the expression

Note that, to get some precision in Sn, only finite matrices are necessary.

F.2 Number of rounds

Let ϕ2(i) := Σ2(i, τ )P (i)/Σ1(i, τ ), i ≥ 2.

Then we have the expression R. = ΠR. + ϕ2 = [I -Π] -1 ϕ2.

F.3 Number of null rounds

Let ϕ3(i) := Σ4(i, τ )P (i)/Σ1(i, τ ), i ≥ 2.

Then we have the expression T. = [I -Π] -1 ϕ3.

F.4 Number of leftovers

Fix r. Let Π1[i, u] := Σ1(i, τ ) i u q u p i-u , i, u > r, and ϕ3(i) := Σ1(i, τ ) i r q r p i-r P L (r, r).

Then we have the expression

G Model 2

We will only briefly mention the modifications related to the main expressions. A supplementary last index will indicate how many null rounds are allowed before failure. Only the mean in the success case will be given, all other cases can be similarly computed; we leave the details for any research student who is interested.

Here, SΓ,1, η1 are related to the case I = 1 and SΓ,2, η2 are related to the case I > 1. In the sequel, with some abuse of notation, OV (1) will denote a RV, asymptotically independent of n, with finite moments. Rewriting,

We have, conditioned on a success, (we use the dominant success probability P d(S))

Cn,S P d(S)

Again we will separate the contribution of urn J from that of urns < J. So, conditioning on J = j and Γ k (j) denoting a sequence of iid truncated geometric RV < j, SΓ,1(j, G) + jG = SΓ,1(j, 0) - Now we must show that SΓ(j, 0) is asymptotically Gaussian. We could simply use Feller [2, example IX,1,a on triangular arrays], but we want an error estimation. We will provide the first terms of our expansions, but Maple "knows" more. The standard deviation of Γ(j) will be denoted by σ(j). We have

Also,

We can now compute (H.2), for instance by using the classical trick of setting

Computing τ as a truncated series in u, this gives, by inversion,

Setting dτ = dτ du du, and integrating on -∞ < u < ∞, this gives [SΓ,1(j, 0) -nE1(j)] √ nσ1(j)

[SΓ,2(j, 0) -nE2(j)] √ nσ2(j) ≤ x as σ(j) q/p 2 -→


Faisal N Abu-Khzam
email: faisal.abukhzam@lau.edu.

Michael A Langston
email: langston@eecs.utk.edu

Immersion Containment and Connectivity in Color-Critical Graphs † ‡

Keywords: Immersion order, graph coloring, color-critical graphs

The relationship between graph coloring and the immersion order is considered. Vertex connectivity, edge connectivity and related issues are explored. It is shown that a t-chromatic graph G contains either an immersed Kt or an immersed t-chromatic subgraph that is both 4-vertex-connected and t-edge-connected. This gives supporting evidence of our conjecture that if G requires at least t colors, then Kt is immersed in G.

Overview

The applications of graph coloring are legion. The usual goal, and the one we consider here, is to assign colors to vertices so that no two adjacent vertices are given the same color. Graph coloring has a long and storied history. The study of four-coloring planar graphs alone has generated interest for over 150 years [START_REF] Saaty | The Four-Color Problem[END_REF]. Despite all this effort, graph coloring in general remains a notoriously difficult combinatorial problem.

Comparatively less is known about the immersion order and its applications. A pair of adjacent edges uv and vw, with u = v and v = w, is lifted by deleting the edges uv and vw, and adding the edge uw. A graph H is said to be immersed in a graph G if and only if a graph isomorphic to H can be obtained from G by lifting pairs of edges and taking a subgraph. This notion is illustrated in Figure 1, which shows that K 4 is immersed in K 1 + P 5 .

In the next section, we briefly survey some of the history behind the intriguing relationship between graph coloring and various forms of containment. Section 3 contains a few requisite mathematical preliminaries, foundational conjectures and initial observations. Here and elsewhere the central parameter is t, the number of colors in use. The main body of our work is contained in the subsequent two sections.

In particular, we prove that, for arbitrary t ≥ 5, every t-chromatic graph contains either an immersed K t or an immersed t-chromatic subgraph that is both 4-vertex connected and t-edge connected. This work, which is of special interest on its own, gives supporting evidence of our conjecture that every t-chromatic graph contains an immersed K t .

Historical Context

The chromatic number of G, denoted by χ(G), is the minimum number of colors required by G in any proper coloring of its vertices. It is tempting to try to associate χ(G) with some sort of clique contained within G. After all, if G contains K t as a subgraph (i) , then it is easy to show that G can be colored with no fewer than t colors. To see that the presence of a K t subgraph is not necessary, however, one needs only to observe that C 5 , the cycle of order five, requires three colors yet does not contain K 3 as a subgraph. Nevertheless, perhaps some weaker form of K t is present. One possibility is topological containment, in which taking subgraphs is augmented with removing subdivisions. An edge is subdivided when it is replaced by a path formed from two edges and an internal vertex of degree two; subdivision removal reverses this operation. For example, C 5 contains K 3 topologically. In the 1940s Hajós conjectured that if χ(G) ≥ t, then G contains a topological K t [START_REF] Hajós | Über eine Konstruktion nicht n-färbbarer Graphen[END_REF]. The conjecture is trivially true for t ≤ 3. In 1952 Dirac proved it true for t = 4 [START_REF] Dirac | A property of 4-chromatic graphs and some remarks on critical graphs[END_REF]. It was not until Catlin's work in 1979 that Hajós' conjecture was finally settled, and negatively, with a family of counterexamples for t ≥ 7 [START_REF] Catlin | Hajós graph-coloring conjecture: variation and counterexamples[END_REF]. Ironically, one such counterexample is the 15-vertex graph defined by the crossproduct of C 5 and K 3 . It requires eight colors but contains no topological K 8 . Subsequently, Erdős and Fajtlowicz were able to prove the rather surprising result that almost all graphs are counterexamples [START_REF] Erdős | On the conjecture of Hajös[END_REF]. Thus Hajós' conjecture remains open only for t ∈ {5, 6}.

Another possibility is the minor order, for which the allowable operations are taking subgraphs and contracting edges. The minor order is a generalization of the topological order, because subdivision removal is just a special case of edge contraction. Hadwiger conjectured in 1943 that, if χ(G) ≥ t, then G contains a K t minor [START_REF] Hadwiger | Über eine Klassifikation der Streckenkomplexe[END_REF]. This conjecture equates to Hajós' conjecture for t ≤ 4. Wagner proved in (i) Of course what we really mean is that G contains a subgraph isomorphic to Kt. We shall henceforth adopt this slight abuse of terminology, dropping the cumbersome reference to isomorphism as long as it creates no confusion or ambiguity.

1964 that, for t = 5, it is equivalent to the four color theorem [START_REF] Wagner | Beweis einer Abschwächung der Hadwiger-Vermutung[END_REF]. In 1993 Robertson, Seymour and Thomas proved it true for t = 6 [START_REF] Robertson | Hadwiger's conjecture for K6-free graphs[END_REF]. Whether Hadwiger's conjecture holds true in general, however, has thus far not been decided. This is in spite of decades of research, hordes of supporting evidence and a multitude of results on many of its variants and restrictions [START_REF] Bollobás | Extremal Graph Theory[END_REF][START_REF] Toft | On separating sets of edges in contraction-critical graphs[END_REF][START_REF] Toft | Colouring, stable sets and perfect graphs[END_REF][START_REF] West | Introduction to Graph Theory[END_REF]. Even the celebrated Graph Minor Theorem [START_REF] Robertson | Graph minors XX: Wagner's conjecture[END_REF] appears to shed no particular light on this question, despite its extraordinary range of algorithmic applications [START_REF] Bienstock | Algorithmic implications of the graph minor theorem[END_REF]. As of this writing, a resolution of Hadwiger's conjecture seems distant.

In this paper we focus instead on the immersion order. Immersion containment is quite distinct from topological and minor containment. Recalling Figure 1, for example, we observe that K 4 is contained in K 1 + P 5 in neither the topological nor the minor order. Like the minor order, however, the immersion order is a generalization of the topological order. This is because subdivision removal is just a special case of lifting pairs of edges. Previous investigations into the immersion order have generally been conducted from a purely algorithmic standpoint. We refer the reader to [BGLR99, FL88, FL92, FL94, LP98] for examples and applications. In contrast, here we mainly consider structural issues. We establish compelling connections between graph coloring and the immersion order, which provides supporting evidence of our conjecture that K t is immersed in any t-chromatic graph (ii) .

Preliminaries

We mainly restrict our attention to finite, simple undirected graphs (multiple edges and loops that may arise from lifting are irrelevant to coloring). G is said to be t-vertex-connected if at least t vertex-disjoint paths connect every pair of its vertices. Moreover, the cardinality of a smallest vertex cutset in G is equal to the largest t for which G is t-vertex-connected (unless G is a complete graph, which can have no vertex cutset). G is said to be t-edge-connected if at least t edge-disjoint paths connect every pair of its vertices, and the cardinality of a smallest edge cutset in G is equal to the largest t for which G is t-edge-connected.

We use δ(G) to denote the minimum degree of a vertex of G. We use

N (u) to denote the neighborhood of u. If χ(G) ≤ t, then G is said to be t-colorable. If χ(G) = t, then G is said to be t-chromatic. If χ(G) = t and χ(H) < t for every proper subgraph H of G, then G is said to be t-color-critical. If G is t-color-critical, then it is easy to see that δ(G) ≥ t -1.
It is sometimes advantageous to select, restrict or manipulate colorings. For example, if G is tchromatic but G -u is only (t -1)-chromatic, then it is possible to consider only colorings in which u is assigned a unique color. In fact, if G is t-color-critical, then for any vertex u there exists a coloring c in which c(u) = 1 and c(v) = 1 for every vertex v ∈ G -u.

A t-coloring of G is realized by a map c from the vertices of G to the set {1, 2, • • • , t} so that, if G contains the edge uv, then c(u) = c(v). Given such a map, c ij is used to denote the subgraph induced by the vertex set {u : c(u) ∈ {i, j}}. A path contained within c ij is termed a Kempe chain [WT72], so-named in honor of the foundational work done on them by Kempe [START_REF] Kempe | How to color a map with four colours without coloring adjacent districts the same color[END_REF]. Of course c ij need not be connected, and so for any u ∈ c ij we employ c ij (u) to denote the set {v : v resides in the same connected component of c ij as does u}. Observe that, if {i, j} = {k, l}, then c ij and c kl are edge-disjoint.

Although the immersion order is traditionally defined in terms of taking subgraphs and lifting pairs of edges, the fact that different Kempe chains are edge-disjoint make it helpful for us to utilize the following alternate characterization: H is immersed in G if and only if there exists an injection from the vertices of (ii) The conjecture was first published in the preliminary conference version of this paper at COCOON 2003.

H to the vertices of G for which the images of adjacent elements of H are connected in G by edge-disjoint paths. Under such an injection, an image vertex is called a corner of H in G; all image vertices and their associated paths are collectively called a model of H in G.

Given the various connections between graph coloring, degrees and connectivity, and in turn the connections between connectivity and the immersion order, we seek to determine just how χ(G) is related to immersion containment. Our efforts prompted us to set the stage for this with the following conjecture, which we formulated more than a decade ago.

Conjecture If χ(G) ≥ t, then K t is immersed in G.
This conjecture motivates our work in the sequel. There we shall present what we believe is compelling evidence in its support. Our conjecture, like Hadwiger's, is trivially true for t ≤ 4. This is because the immersion order generalizes the topological order, for which Hajós' conjecture is long known to hold when t ≤ 4. Recently, Devos et al verified our conjecture for t ≤ 7 [DKMO10, DDF + ]. The general case quite naturally appears to be much more difficult. Accordingly, our efforts in this paper focus mainly on global connectivity issues.

Before proceeding, we introduce a notion of immersion-criticality and show how it relates to the possible existence of counterexamples.

Definition G is t-immersion-critical if χ(G) = t and χ(H) < t whenever H is properly immersed in G.
Because χ(K t ) = t, any counterexample must either be t-immersion-critical or have properly immersed within it another t-immersion-critical counterexample. Similarly, any t-immersion-critical graph distinct from K t must be a counterexample. Thus our immersion-conjecture is equivalent to the statement that K t is the only t-immersion-critical graph for every t. Although we have thus far fallen short of establishing this one way or the other, we note that there are at most a finite number of them for each t. This follows easily from properties of well-quasi-orders and immersion order obstruction sets. We refer the reader unfamiliar with these concepts to [START_REF] Fellows | Nonconstructive tools for proving polynomial-time decidability[END_REF][START_REF] Fellows | On well-partial-order theory and its application to combinatorial problems of VLSI design[END_REF][START_REF] Kinnersley | Immersion order obstruction sets[END_REF]. Graph connectivity has long been a central feature of attempts to settle Hadwiger's conjecture. G is said to be t-minor-critical (iii) if χ(G) = t and χ(H) < t whenever H is a proper minor of G. K t is of course both (t -1)-vertex-connected and (t -1)-edge-connected. Thus, if any t-minor-critical graph is not as strongly connected, then Hadwiger's conjecture is false for all t ≥ t. So suppose G denotes a t-minor-critical graph other than K t (in which case the conjecture fails). Some 35 years ago, Mader [START_REF] Mader | Homomorphiesätze für Graphen[END_REF] showed that G must be at least 7-vertex-connected whenever t ≥ 7. This provides evidence in support of our conjecture for t ∈ {7, 8}. A few years later [START_REF] Toft | On separating sets of edges in contraction-critical graphs[END_REF], Toft proved that G must also be t-edge-connected. This provides additional supporting evidence for all t. Very recently, Kawarabayashi has shown that G must be at least t 3 -vertex-connected as well [START_REF] Kawarabayashi | On the connectivity of minimum and minimal counterexamples to Hadwiger's conjecture[END_REF]. Following this approach, we study both the vertex and edge connectivity of t-immersion-critical graphs. We assume t ≥ 8 unless stated otherwise. Kempe chains play a pivotal role in our investigation.

(iii) In the literature, this notion has sometimes been termed t-contraction-critical.

Vertex Connectivity of t-Immersion-Critical Graphs

Because they are t-color-critical, it is easy to see that t-immersion-critical graphs are 2-vertex-connected [START_REF] Bollobás | Extremal Graph Theory[END_REF]. We now establish that they must in fact be at least 4-vertex-connected. Our work linking coloring to the immersion order begins in earnest with Lemma 4. First, however, we present something of an introduction with three easy but useful lemmas about cutsets, paths and coloring. Lemmas 1 and 2 are probably well known, although they may not be formulated anywhere else in precisely the same way we state them in this treatment. Lemma 2, which we dub The Patching Lemma, is especially helpful. Lemma 3 is certainly well known, and mentioned in a variety of sources (see, for example, [START_REF] Harary | Graph Theory[END_REF][START_REF] Toft | Colouring, stable sets and perfect graphs[END_REF][START_REF] West | Introduction to Graph Theory[END_REF]). We include the proofs of these lemmas here both for completeness and, more importantly, to illustrate and clarify their utility in subsequent results.

Lemma 1 Let S denote a minimum-cardinality vertex cutset in a 2-vertex-connected graph G, and let C denote a connected component of G\S. Then any two elements of S must be connected by a path whose interior vertices lie completely within C.

Proof: Because G is 2-vertex-connected, |S| ≥ 2. Let a and b denote any two distinct elements of S. It must be that a is adjacent to some vertex u in C, since otherwise S is not minimal (S\{a} defines a vertex cutset of cardinality |S| -1). Similarly, it must be that b is adjacent to some vertex v in C. If u = v, then we are done. If u = v, then the connectedness of C ensures that there is a subpath P from u to v lying completely within C. Thus au ∪ P ∪ vb is the desired path.

2

Two colorings are said to be equivalent if the partitions induced by their respective color classes are identical.

Lemma 2 (The Patching Lemma) Let S denote a vertex cutset of G, and let G 1 and G 2 denote a pair of induced subgraphs for which G 1 ∪ G 2 = G and G 1 ∩ G 2 = S. If G 1 and G 2 admit t-colorings whose restrictions to S are equivalent, then G is t-colorable.

Proof: Let S, G, G 1 and G 2 be as defined in the statement of the lemma. Let c and d denote the specified t-colorings of G 1 and G 2 , respectively. Modify one coloring, say d, by renaming its color classes so that each element of S is assigned the same integer under both colorings. Patched together, c and d now provide a t-coloring of G.

2

The Patching Lemma can be used to establish the following well-known fact.

Lemma 3 No vertex cutset of a t-color-critical graph can be a clique.

The preceding lemmas tell us a good deal about the make-up of vertex cutsets, and how they relate to coloring. Armed with this information, we are now able to argue more directly about vertex connectivity and the immersion order. To simplify matters, we shall adopt the following conventions for the remainder of this subsection:

t is at least eight, -G denotes a t-immersion-critical graph, -S denotes a minimum-cardinality vertex cutset in G, -C denotes a connected component of G\S, -G 1 denotes the subgraph induced by C ∪ S, and -G 2 denotes G\C.

Lemma 4 Every t-immersion-critical graph is 3-vertex-connected.

Proof: Suppose otherwise, as witnessed by some G with S = {a, b}. We know from Lemma 3 that the edge ab is not present in G. Let i ∈ {1, 2}. By Lemma 1, there must be a path, P i , with endpoints a and b, whose vertices lie completely within G i . Lifting the edges of P 3-i to form the single edge ab, and then taking the subgraph induced by the vertices of G i , produces a graph H i properly immersed in G. It follows that H i is (t -1)-colorable. Because ab is present in H i , any such coloring of H i assigns different colors to a and b. But G i is a subgraph of H i . Thus, there are (t -1)-colorings of G 1 and G 2 that each assign different colors to a and b. By the Patching Lemma, this ensures a (t -1)-coloring of G, a contradiction. 2

Lemma 5 If |S| = 3, then both G 1 and G 2 admit (t -1)-colorings that assign more than one color to the elements of S.

Proof: Let S = {u, v, w}, and consider the case for G 1 . By Lemma 1, there is a path between u and v in G 2 . Lifting this path and taking the subgraph induced by the vertices of G 1 produces a graph H properly immersed in G. Because G is t-immersion-critical, and because H contains the edge uv, H admits a (t -1)-coloring that assigns different colors to u and v. As a subgraph of H, G 1 can likewise be colored.

A symmetrical argument handles the case for G 2 . 2

What we have really just shown is that if G is only 3-vertex-connected, then G 1 admits a (t -1)coloring that assigns different colors to any fixed pair of elements of S. This raises the possibility that a single coloring of G 1 may suffice, simultaneously assigning different colors to all three elements of S. We now show that this cannot happen. It follows that the same must then be true for G Lemma 6 If |S| = 3, then neither G 1 nor G 2 admits a (t -1)-coloring that assigns three different colors to the elements of S.

Proof: Suppose otherwise, as witnessed by a (t -1)-coloring c of G 1 . Let S = {u, v, w} and assume, without loss of generality, that c(u) = 1, c(v) = 2 and c(w) = 3. Let d denote some (t -1)-coloring of G 2 . By Lemma 5 and the Patching Lemma, we may further assume, again without loss of generality, that d assigns exactly two colors to the elements of S, with d(u) = d(v). If u and v are not c-chained, then we can exchange colors 1 and 2 in c 12 (v) to produce a (t -1)-coloring c of G 1 that assigns color 1 to both u and v and leaves the color of w set to 3. This means that the restrictions of c and d to S are equivalent. But now, by the Patching Lemma, G is (t -1)-colorable, which is impossible.

Thus it must be that u and v are c-chained by some P 12 in G 1 . Lifting this chain and taking the subgraph induced by the vertices of G 2 produces a graph H properly immersed in G. H contains uv, and so must admit a (t -1)-coloring d that assigns different colors to u and v. G 2 is likewise colored by d . By the Patching Lemma, d cannot assign a third color to w. So assume, again without loss of generality, that d (w) = d (u). If u and w are not c-chained, then (as in the previous argument) we can construct a (t -1)-coloring c of G 1 so that the restrictions of c and d to S are equivalent, which is impossible.

Thus it must be that u and w are c-chained by some P 13 in G 1 . Because they are edge disjoint, P 12 and P 13 can be lifted simultaneously. Lifting these two chains and taking the subgraph induced by the vertices of G 2 produces a graph H properly immersed in G. H contains both uv and uw, and so must admit a (t -1)-coloring d that assigns different colors to u and v and different colors to u and w. G 2 is likewise colored by d . By the Patching Lemma, d cannot assign three colors to the elements of S. So it must be that d (v) = d (w). If v and w are not c-chained, then (as in the previous arguments) we can construct a (t -1)-coloring c of G 1 so that the restrictions of c and d to S are equivalent, which is impossible.

Thus it must be that v and w are c-chained by some P 23 in G 1 . Because they are edge disjoint, P 12 , P 13 and P 23 can be lifted simultaneously. Lifting these three chains and taking the subgraph induced by the vertices of G 2 produces a graph H properly immersed in G. H contains uv, uw and vw, and so must admit a (t -1)-coloring d that assigns three different colors to S. G 2 is likewise colored by d . This means that the restrictions of c and d to S are equivalent, which is impossible, contradicting the supposition that c exists. 2

Bolstered by the preceding Lemmas, we are now ready to prove that minimum-cardinality vertex cutsets of t-immersion-critical graphs have at least four elements. The use of Kempe chains in Lemma 6 has been especially effective, so much so that we need only paths not chains in what follows.

Theorem 1 Every t-immersion-critical graph is 4-vertex-connected.

Proof: Suppose otherwise, as witnessed by some G with S = {u, v, w}. Let c and d denote (t -1)colorings of G 1 and G 2 , respectively. By Lemmas 5 and 6, we restrict our attention to the case in which both c and d assign exactly two colors to elements of S. Without loss of generality, assume c(u) = c(v) and d(u) = d(w). By Lemma 1, there is a path P 1 in G 1 whose endpoints are u and w. Similarly, there is a path P 2 in G 2 whose endpoints are u and v. Lifting P i and taking the graph induced by the vertices of G 3-i produces a graph H 3-i properly immersed in G. H 1 contains uv, and so must admit a (t -1)coloring c that assigns different colors to u and v. G 1 is likewise colored by c . By Lemma 6, c cannot assign a third color to w. Lest the restrictions of c and d to S be equivalent, it must be that c (w) = c (v). H 2 contains uw, and so must admit a (t -1)-coloring d that assigns different colors to u and w. G 2 is likewise colored by d . By Lemma 6, d cannot assign a third color to v. But if d (v) = d (u), then the restrictions of c and d to S are equivalent. And if d (v) = d (w), then the restrictions of c and d to S are equivalent. Thus, under some pair of colorings of G 1 and G 2 , the Patching Lemma ensures that G is (t -1)-colorable, a contradiction. 2

Edge Connectivity

Because the immersion order includes the taking of subgraphs, we know that t-immersion-critical graphs are also t-color-critical. From the work of [START_REF] Toft | On critical subgraphs of colour critical graphs[END_REF] it follows that they are (t -1)-edge-connected. We now show that any t-immersion-critical graph other than K t is in fact t-edge-connected. We begin a pair of well-known observations (see, for example, [START_REF] West | Introduction to Graph Theory[END_REF]).

Observation 1 A minimum-cardinality edge cutset separates a graph into exactly two connected components.

Fig. 1 :

 1 Fig. 1: K4 is immersed in K1 + P5.

  2 . Let a and b denote vertices of G, and let c denote a coloring of G in which c(a) = i = j = c(b). If a and b belong to the same connected component of c ij , then they are connected by some Kempe chain P ij contained within c ij . In this event, we say that a and b are c-chained.

† This research has been supported in part by the National Science Foundation under grants EIA-9972889 and CCR-0075792, by the Office of Naval Research under grant N00014-01-1-0608, by the Department of Energy under contract DE-AC05-00OR22725, and by the Tennessee Center for Information Technology Research under award E01-0178-081. ‡ A preliminary version of a portion of this paper was presented at the Ninth International Conference on Computing and Combinatorics, held in Big Sky, Montana, in July 2003.

Observation 2 If H is obtained by deleting the edge uv from a t-color-critical graph, then H is (t -1)colorable and, under any (t -1)-coloring, u and v are assigned the same color.

The significance of Observation 2 rests with the next lemma, which plays an essential role in our edgeconnectivity arguments. This lemma is probably also well known, although it may not be formulated elsewhere in exactly the same way we state it here.

Lemma 7 Let H be obtained by deleting the edge uv from a t-color-critical graph. Let c denote a (t-1)-

Proof: Let H and c be defined as stated. Suppose the lemma is false, as witnessed by some i with v / ∈ c 1i (u). Exchanging colors 1 and i in c 1i (u) produces c , another (t -1)-coloring of H. But then u and v are assigned different colors under c , which is impossible.

2

Aided by this information about color-criticality, we are now able to argue more directly about edge connectivity and the immersion order. We shall adopt the following conventions for the remainder of this subsection:

t is at least eight, -G denotes a t-immersion-critical graph, -S denotes a minimum-cardinality edge cutset in G, -C 1 and C 2 denote the two connected components of G\S, -S 1 and S 2 denote the endpoints of S contained in C 1 and C 2 , respectively, -uv denotes an element of S, with u ∈ S 1 and v ∈ S 2 , and -H denotes G\{uv}.

Lemma 8 If G is not t-edge-connected, then every (t -1)-coloring of H assigns either one color to S 1 and all t -1 colors to S 2 or vice versa.

Proof: Suppose G is not t-edge-connected. We know from [START_REF] Toft | On critical subgraphs of colour critical graphs[END_REF] that

Therefore u and v are the endpoints of t-2 Kempe chains, where each chain is contained within c 1i (u) for some i. The chains are edge disjoint, and so each contains at least one distinct element of S = S\{uv}. Thus there is a one-to-one correspondence between chains and elements of S . This means that every element of S has an endpoint assigned color 1 by c. If c assigns only color 1 to S 1 , then it must assign all t -1 colors to S 2 . Similarly, if c assigns all t -1 colors to S 1 , then it must assign only color 1 to S 2 .

The only remaining case to consider occurs if c assigns more than one but fewer than t -1 colors to S 1 . To show that this cannot happen, we now proceed by contradiction, and suppose S 1 contains vertex w assigned color i, but no vertex assigned color j, where {i, j} ⊆ {2, 3, • • • , t -1}. It must be that c ij (w) is completely contained within C 1 . We exchange colors i and j in c ij (w) to produce c , another (t -1)-coloring of H with c (u) = c (v) = 1. By this construction, c assigns color j to endpoints of two different elements of S , and accordingly assigns color i to the endpoint of no element of S . We conclude that v / ∈ c 1i (u), contradicting Lemma 7. 2

Theorem 2 Any t-immersion-critical graph other than K t is t-edge-connected.

Proof: Suppose otherwise, as witnessed by some G, not isomorphic to K t , that is only (t -1)-edgeconnected. We apply Lemma 8 and, without loss of generality, let c denote a (t -1)-coloring of H that assigns color 1 to S 1 ∪ {v}. Thus all t -1 colors are assigned to S 2 , and we index the elements of S 2 by

Let i and j denote distinct elements of {1, 2, • • • , t -1}. It must be that v i belongs to c ij (v j ), since otherwise we can exchange colors i and j in c ij (v j ) to produce a (t -1)-coloring of H in which the elements of S 2 are assigned t -2 colors, thereby contradicting Lemma 8. It follows that v i and v j are the endpoints of a Kempe chain contained within c ij (v j ). Moreover, even if i or j is 1, the elements of S 1 are excluded from this chain. Therefore the chain is completely contained within C 2 . Because such a chain exists for each pair of vertices in S 2 , and because the chains are edge disjoint, K t-1 is immersed in C 2 using a model whose corners are the elements of S 2 . Now let i denote an element of {2, • • • , t -1}. From the proof of Lemma 8, we know that u and v are the endpoints of a Kempe chain containing v i . This means that u and v i are the endpoints of a subchain completely contained within C 1 ∪ S. Because such a chain exists for each vertex in S 2 \{v}, because the chains are edge disjoint, and because uv ∈ G, K t is immersed in G using a model whose corners are {u} ∪ S 2 . This is the desired contradiction.

2

Corollary 1 If G is t-immersion-critical and not K t , then δ(G) ≥ t.

Proof: Immediate from Theorem 2 and the fact that δ(G) is an upper bound on G's edge connectivity. 2

Corollary 2 If G is t-color-critical with a vertex u of degree t -1, then K t is immersed in G via a model whose corners are {u} ∪ N (u).

Proof: Follows from the proof of Theorem 2 by letting S be the set of edges incident on u. 2