Olivier Bernardi
email: bernardi@math.mit.edu

Rosena R X Du
email: rxdu@math.ecnu.edu.cn

Alejandro H Morales
email: ahmorales@math.mit.edu

Richard P Stanley

Separation probabilities for products of permutations

We study the mixing properties of permutations obtained as a product of two uniformly random permutations of fixed cycle types. For instance, we give an exact formula for the probability that elements 1, 2, . . . , k are in distinct cycles of the random permutation of {1, 2, . . . , n} obtained as product of two uniformly random n-cycles.

Introduction

We study certain separation probabilities for products of permutations. The archetypal question can be stated as follows: in the symmetric group S n , what is the probability that the elements 1, 2, . . . , k are in distinct cycles of the product of two n-cycles chosen uniformly randomly? The answer is surprisingly elegant: the probability is 1 k! if n -k is odd and

1 k! + 2 (k-2)!(n-k+1)(n+k)
if n -k is even. This result was originally conjectured by Bóna [START_REF] Bóna | The average number of block interchanges needed to sort a permutation and a recent result of stanley[END_REF] for k = 2 and n odd. Subsequently, Du and Stanley proved it for all k and proposed additional conjectures [START_REF] Stanley | Products of cycles[END_REF]. The goal of this paper is to prove these conjectures, and establish generalizations of the above result. Our approach is different from the one used in [START_REF] Stanley | Products of cycles[END_REF].

Let us define a larger class of problems. Given a tuple A = (A 1 , . . . , A k ) of k disjoint non-empty subsets of {1, . . . , n}, we say that a permutation π is A-separated if no cycle of π contains elements of more than one of the subsets A i . Now, given two integer partitions λ, µ of n, one can wonder about the probability P λ,µ (A) that the product of two uniformly random permutations of cycle type λ and µ is A-separated. The example presented above corresponds to A = ({1}, . . . , {k}) and λ = µ = (n). Clearly, the separation probabilities P λ,µ (A) only depend on A through the size of the subsets #A 1 , . . . , #A k , and we shall denote σ α λ,µ := P λ,µ (A), where α = (#A 1 , . . . , #A k ) is a composition (of size m ≤ n). Note also that σ α λ,µ = σ α ′ λ,µ whenever the composition α ′ is a permutation of the composition α. Below, we focus on the case µ = (n) and we further denote σ α λ := σ α λ,(n) .

In this paper, we first express the separation probabilities σ α λ as some coefficients in an explicit generating function. Using this expression we then prove the following symmetry property: if α = (α 1 , . . . , α k ) and β = (β 1 , . . . , β k ) are compositions of the same size m ≤ n and of the same length k, then

σ α λ k i=1 α i ! = σ β λ k i=1 β i ! . (1)
Moreover, for certain partitions λ (including the cases λ = (n) and λ = 2 N ) we obtain explicit expressions for the probabilities σ α λ for certain partitions λ. For instance, the separation probability σ α (n) for the product of two n-cycles is found to be

σ α (n) = (n -m)! k i=1 α i ! (n + k)(n -1)! (-1) n-m n-1 k-2 n+m m-k + m-k r=0 (-1) r m-k r n+r+1 m n+k+r r . (2)
This includes the case α = 1 k proved by Du and Stanley [START_REF] Stanley | Products of cycles[END_REF].

Our general expression for the separation probabilities σ α λ is derived using a formula obtained in [START_REF] Morales | Bijective enumeration of bicolored maps of given vertex degree distribution[END_REF] about colored factorizations of the n-cycle into two permutations. This formula displays a symmetry which turns out to be of crucial importance for our method. Our approach can in fact be made mostly bijective as explained in Section 5. Indeed, the formula obtained in [START_REF] Morales | Bijective enumeration of bicolored maps of given vertex degree distribution[END_REF] builds on a bijection established in [START_REF] Schaeffer | A bijective proof of Jackson's formula for the number of factorizations of a cycle[END_REF]. An alternative bijective proof was given in [START_REF] Bernardi | Bijections and symmetries for the factorizations of the long cycle[END_REF] and in Section 5 we explain how to concatenate this bijective proof with the constructions of the present paper.

Outline. In Section 2 we present our strategy for computing the separation probabilities. This involves counting certain colored factorizations of the n-cycle. We then gather our main results in Section 3. In particular we prove the symmetry property [START_REF] Bernardi | An analogue of the Harer-Zagier formula for unicellular maps on general surfaces[END_REF] and obtain formulas for the separation probabilities σ α λ for certain partitions λ including λ = (n) or when λ = 2 N . In Section 4, we give formulas relating the separation probabilities σ α λ and σ α λ ′ when λ ′ is a partition obtained from another partition λ by adding some parts of size 1. In Section 5, we indicate how our proofs could be made bijective. We gather a few additional remarks in Section 6.

Notation. We denote [n] := {1, 2, . . . , n}. We denote by #S the cardinality of a set S.

A composition of an integer n is a tuple α = (α 1 , α 2 , . . . , α k ) of positive integer summing to n. We then say that α has size n and length ℓ(α) = k. An integer partition is a composition such that the parts α i are in weakly decreasing order. We use the notation λ |= n (resp. λ ⊢ n) to indicate that λ is a composition (resp. integer partition) of n. We sometime write integer partitions in multiset notation: writing λ = 1 n 1 , 2 n 2 , . . . , j n j means that λ has n i parts equal to i.

We denote by S n the symmetric group on [n]. Given a partition λ of n, we denote by C λ the set of permutations in S n with cycle type λ. It is well known that #C λ = n!/z λ where z λ = i i n i (λ) n i (λ)! and n i (λ) is the number of parts equal to i in λ.

We shall consider symmetric functions in an infinite number of variables x = {x 1 , x 2 , . . .}. For any sequence of nonnegative integers, α = (α 1 , α 2 , . . . , α k ) we denote x α := x α 1 1 x α 2 2 . . . x α k k . We denote by [x α ]f (x) the coefficient of this monomial in a series f (x). For an integer partition λ = (λ 1 , . . . , λ k ) we denote by p λ (x) and m λ (x) respectively the power symmetric function and monomial symmetric function indexed by λ (see e.g. [START_REF] Stanley | Enumerative combinatorics[END_REF]). That is,

p λ (x) = ℓ(λ) i=1 p λ i (x) where p k (x) = i≥1 x k
i , and m λ (x) = α x α where the sum is over all the distinct sequences α whose positive parts are {λ 1 , λ 2 , . . . , λ k } (in any order). Recall that the power symmetric functions form a basis of the ring of symmetric functions. For a symmetric function f (x) we denote by [p λ (x)]f (x) the coefficient of p λ (x) of the decomposition of f (x) in this basis.

Strategy

In this section, we first translate the problem of determining the separation probabilities σ α λ into the problem of enumerating certain sets S α λ . Then, we introduce a symmetric function G α n (x, t) whose coefficients in one basis are the cardinalities #S α λ , while the coefficients in another basis count certain "colored" separated factorizations of the permutation (1, . . . , n). Lastly, we give exact counting formulas for these colored separated factorizations. Our main results will follow as corollaries in Section 3.

For a composition α = (α 1 , . . . , α k ) of size m ≤ n, we denote by A α n the set of tuples

A = (A 1 , . . . , A k ) of pairwise disjoint subsets of [n] with #A i = α i for all i in [k]. Observe that #A α n = n α 1 ,α 2 ,...,α k ,n-m .
Now, recall from the introduction that σ α λ is the probability for the product of a uniformly random permutation of cycle type λ with a uniformly random n-cycle to be A-separated for a fixed tuple A in A α n . Alternatively, it can be defined as the probability for the product of a uniformly random permutation of cycle type λ with a fixed n-cycle to be A-separated for a uniformly random tuple A in A α n (since the only property that matters is that the elements in A are randomly distributed in the n-cycle).

Definition 1. For an integer partition λ of n, and a composition α of m ≤ n, we denote by S α λ the set of pairs (π, A), where π is a permutation in C λ and A is a tuple in A α n such that the product π

• (1, 2, ..., n) is A-separated.
From the above discussion we obtain for any composition α = (α 1 , . . . , α k ) of size m,

σ α λ = #S α λ n α 1 ,α 2 ,...,α k ,n-m #C λ . (3)
Enumerating the sets S α λ directly seems rather challenging. However, we will show below how to enumerate a related class of "colored" separated permutations denoted by T α γ (r). We define a cycle coloring of a permutation π ∈ S n in [q] to be a mapping c from [n] to [q] such that if i, j ∈ [n] belong to the same cycle of π then c(i) = c(j). We think of [q] as the set of colors, and c -1 (i) as set of elements colored i. Definition 2. Let γ = (γ 1 , . . . , γ ℓ ) be a composition of size n and length ℓ, and let α = (α 1 , . . . , α k ) be a composition of size m ≤ n and length k. For a nonnegative integer r we define T α γ (r) as the set of quadruples (π, A, c 1 , c 2 ), where π is a permutation of

[n], A = (A 1 , . . . , A k ) is in A α n , and (i) c 1 is a cycle coloring of π in [ℓ] such that there are γ i element colored i for all i in [ℓ], (ii) c 2 is a cycle coloring of the product π • (1, 2, . . . , n) in [k + r] such that every color in [k + r]
is used and for all i in [k] the elements in the subset A i are colored i.

Note that condition (ii) in Definition 2 and the definition of cycle coloring implies that the product π

• (1, 2, . . . , n) is A-separated.
In order to relate the cardinalities of the sets S α λ and T α γ (r), it is convenient to use symmetric functions (in the variables x = {x 1 , x 2 , x 3 , . . .}). Namely, given a composition α of m ≤ n, we define

G α n (x, t) := λ⊢n p λ (x) (π,A)∈S α λ t excess(π,A) ,
where the outer sum runs over all the integer partitions of n, and excess(π, A) is the number of cycles of the product π • (1, 2, . . . , n) containing none of the elements in A. Recall that the power symmetric functions p λ (x) form a basis of the ring of symmetric functions, so that the contribution of a partition λ to G α n (x, t) can be recovered by extracting the coefficient of p λ (x) in this basis:

#S α λ = [p λ (x)] G α n (x, 1). (4)
As we prove now, the sets T α γ (r) are related to the coefficients of G α n (x, t) in the basis of monomial symmetric functions.

Proposition 3. If α is a composition of length k, then G α n (x, t + k) = γ⊢n m γ (x) r≥0 t r #T α γ (r), (5)
where the outer sum is over all integer partitions of n, and t r

:= t(t -1) • • • (t -r + 1) r! .
Proof. Since both sides of (5) are polynomial in t and symmetric function in x it suffices to show that for any nonnegative integer t and any partition γ the coefficient of x γ is the same on both sides of [START_REF] Jackson | Some combinatorial problems associated with products of conjugacy classes of the symmetric group[END_REF]. We first determine the coefficient [x γ ]G α n (x, t + k) when t is a nonnegative integer. Let λ be a partition, and π be a permutation of cycle type λ. Then the symmetric function p λ (x) can be interpreted as the generating function of the cycle colorings of π, that is, for any sequence γ = (γ 1 , . . . , γ ℓ ) of nonnegative integers, the coefficient [x γ ]p λ (x) is the number of cycle colorings of π such that γ i elements are colored i, for all i > 0. Moreover, if π is A-separated for a certain tuple A = (A 1 , . . . , A k ) in A α n , then (t + k) excess(S,π) represents the number of cycle colorings of the permutation π • (1, 2, . . . , n) in [k + t] (not necessarily using every color) such that for all i ∈ [k] the elements in the subset A i are colored i. Therefore, for a partition γ and a nonnegative integer t, the coefficient [x γ ]G α n (x, t + k) counts the number of quadruples (π, A, c 1 , c 2 ), where π, A, c 1 , c 2 are as in the definition of T α γ (t) except that c 2 might actually use only a subset of the colors [k + t]. Note however that all the colors in [k] will necessarily be used by c 2 , and that we can partition the quadruples according to the subset of colors used by c 2 . This gives

[x γ ]G α n (x, t + k) = r≥0 t r #T α γ (r).
Now extracting the coefficient of x γ in the right-hand side of (5) gives the same result. This completes the proof.

In order to obtain an explicit expression for the series G α n (x, t) it remains to enumerate the sets T α γ (r) which is done below.

Proposition 4. Let r be a nonnegative integer, let α be a composition of size m and length k, and let γ be a partition of size n ≥ m and length ℓ. Then the set T α γ (r) specified by Definition 2 has cardinality

#T α γ (r) = n(n -ℓ)!(n -k -r)! (n -k -ℓ -r + 1)! n + k -1 n -m -r , (6)
if n -k -ℓ -r + 1 ≥ 0, and 0 otherwise.

The rest of this section is devoted to the proof of Proposition [START_REF] Harer | The Euler characteristic of the moduli space of curves[END_REF]. In order to count the quadruples (π, A, c 1 , c 2 ) satisfying Definition 2, we shall start by choosing π, c 1 , c 2 before choosing the tuple A. For compositions γ = (γ 1 , . . . , γ ℓ ), δ = (δ 1 , . . . , δ ℓ ′ ) of n we denote by B γ,δ the set of triples (π, c 1 , c 2 ), where π is a permutation of [n], c 1 is a cycle coloring of π such that γ i elements are colored i for all i ∈ [ℓ], and c 2 is a cycle coloring of the permutation π • (1, 2, . . . , n) such that δ i elements are colored i for all i ∈ [ℓ ′ ]. The problem of counting such sets was first considered by Jackson [START_REF] Jackson | Some combinatorial problems associated with products of conjugacy classes of the symmetric group[END_REF] who actually enumerated the union B n i,j := γ,δ|=n, ℓ(γ)=i, ℓ(δ)=j B γ,δ using representation theory. It was later proved in [START_REF] Morales | Bijective enumeration of bicolored maps of given vertex degree distribution[END_REF] that

#B γ,δ = n(n -ℓ)!(n -ℓ ′ )! (n -ℓ -ℓ ′ + 1)! , (7)
if n -ℓ -ℓ ′ + 1 ≥ 0, and 0 otherwise. The proof of ( 7) in [START_REF] Morales | Bijective enumeration of bicolored maps of given vertex degree distribution[END_REF] uses a refinement of a bijection designed in [START_REF] Schaeffer | A bijective proof of Jackson's formula for the number of factorizations of a cycle[END_REF] in order to prove Jackson's formula for #B n i,j . Another bijective proof of ( 7) is given in [START_REF] Bernardi | Bijections and symmetries for the factorizations of the long cycle[END_REF], and we shall discuss it further in Section 5 (a proof of (7) using representation theory can be found in [START_REF] Vassilieva | Explicit monomial expansions of the generating series for connection coefficients[END_REF]).

One of the striking features of the counting formula [START_REF] Mohar | Graphs on surfaces[END_REF] is that it depends on the compositions γ, δ only through their lengths ℓ, ℓ ′ . This "symmetry" will prove particularly handy for enumerating T α γ (r). Let r, α, γ be as in Proposition 4, and let δ = (δ 1 , . . . , δ k+r ) be a composition of n of length k + r. We denote by T α γ,δ the set of quadruples (π,

A, c 1 , c 2 ) in T α γ (r) such that the cycle coloring c 2 has δ i elements colored i for all i in [k + r] (equivalently, (π, c 1 , c 2 ) ∈ B γ,δ ). We also denote d α δ := k i=1 δ i α i . It is easily seen that for any triple (π, c 1 , c 2 ) ∈ B γ,δ , the number d α δ counts the tuples A ∈ A α n such that (π, A, c 1 , c 2 ) ∈ T α γ,δ . Therefore, #T α γ (r) = δ|=n, ℓ(δ)=k+r #T α γ,δ = δ|=n, ℓ(δ)=k+r d α δ #B γ,δ ,
where the sum is over all the compositions of n of length k + r. Using (7) then gives

#T α γ (r) = n(n -ℓ)!(n -k -r)! (n -k -ℓ -r + 1)! δ|=n, ℓ(δ)=k+r d α δ if n -k -ℓ -r + 1 ≥ 0,
d α δ = n + k -1 n -m -r .
Proof. We give a bijective proof illustrated in Figure 1. One can represent a composition δ = (δ 1 , . . . , δ k+r ) as a sequence of rows of boxes (the ith row has δ i boxes). With this representation,

d α δ := k i=1 δ i
α i is the number of ways of choosing α i boxes in the ith row of δ for i = 1, . . . , k. Hence δ|=n, ℓ(δ)=k+r d α δ counts α-marked compositions of size n and length k+r, that is, sequences of k+r non-empty rows of boxes with some marked boxes in the first k rows, with a total of n boxes, and α i marks in the ith row for i = 1, . . . , k; see Figure 1. Now α-marked compositions of size n and length k + r are clearly in bijection (by adding a marked box to each of the rows 1, . . . , k, and marking the last box of each of the rows k + 1, . . . , k + r) with α ′ -marked compositions of size n + k and length k + r such that the last box of each row is marked, where α ′ = (α 1 + 1, α 2 + 1, . . . , α k + 1, 1, 1, . . . , 1) is a composition of length k + r. Lastly, these objects are clearly in bijection (by concatenating all the rows) with sequences of n + k boxes with m + k + r marks, one of which is on the last box. There are n+k-1 n-m-r such sequences, which concludes the proof of Lemma 5 and Proposition 4.

Main results

In this section, we exploit Propositions 3 and 4 in order to derive our main results. All the results in this section will be consequences of the following theorem.

Theorem 6. For any composition α of m ≤ n of length k, the generating function G α n (x, t + k) in the variables t and x = {x 1 , x 2 , . . .} has the following explicit expression in the bases m λ (x) and t r :

G α n (x, t + k) = n-m r=0 t r n + k -1 n -m -r λ⊢n, ℓ(λ)≤n-k-r+1 n(n -ℓ(λ))!(n -k -r)! (n -k -r -ℓ(λ) + 1)! m λ (x). (8)
Moreover, for any partition

λ of n, one has #S α λ = [p λ (x)]G α n (x, 1) and σ α λ = #S α λ n α 1 ,α 2 ,...,α k ,n-m #C λ .
Theorem 6 is the direct consequence of Propositions 3 and 4. One of the striking features of ( 8) is that the expression of G α n (x, t + k) depends on α only through its size and length. This "symmetry property" then obviously also holds for #S α λ = [p λ (x)]G α n (x, 1), and translates into the formula (1) for separation probabilities as stated below.

Corollary 7. Let λ be a partition of n, and let α = (α 1 , . . . , α k ) and β = (β 1 , . . . , β k ) be compositions of the same size m and length k. Then,

#S α λ = #S β λ , (9)
or equivalently, in terms of separation probabilities,

σ α λ k i=1 α i ! = σ β λ k i=1 β i ! .
We now derive explicit formulas for the separation probabilities for the product of a uniformly random permutation π, with particular constraints on its cycle type, with a uniformly random n-cycle. We focus on two constraints: the case where π is required to have p cycles, and the case where π is a fixed-point-free involution (for n even).

Case when π has exactly p cycles

Let C(n, p) denote the set of permutations of [n] having p cycles. Recall that the numbers c(n, p) = #C(n, p) = [x p ]x(x + 1)(x + 2) • • • (x + n -1) are called the signless Stirling numbers of the first kind. We denote by σ α (n, p) the probability that the product of a uniformly random permutation in C(n, p) with a uniformly random n-cycle is A-separated for a given set A in A α n . By a reasoning similar to the one used in the proof of (3), one gets

σ α (n, p) = 1 n α 1 ,α 2 ,...,α k ,n-m c(n, p) λ⊢n,ℓ(λ)=p #S α λ . (10)
We now compute the probabilities σ α (n, p) explicitly.

Theorem 8. Let α be a composition of m with k parts. Then,

σ α (n, p) = (n -m)! k i=1 α i ! c(n, p) n-m r=0 1 -k r n + k -1 n -m -r c(n -k -r + 1, p) (n -k -r + 1)! , (11)
where c(n, p) are signless Stirling numbers of the first kind.

For instance, Theorem 8 in the case m = n gives the probability that the cycles of the product of a uniformly random permutation in C(n, p) with a uniformly random n-cycle refine a given set partition of [n] having blocks of sizes α 1 , α 2 , . . . , α k . This probability is found to be

σ α (n, p) = k i=1 α i ! c(n, p) c(n -k + 1, p) (n -k + 1)! .
We now prove Theorem 8. Via [START_REF] Stanley | Enumerative combinatorics[END_REF], this amounts to enumerating S α (n, p) := λ⊢n,ℓ(λ)=p S α λ , and using Theorem 6 one gets

#S α (n, p) = λ⊢n,ℓ(λ)=p [p λ (x)] G α n (x, 1) = n-m r=0 1 -k r n + k -1 n -m -r n-k-r+1 ℓ=1 n(n -ℓ)!(n -k -r)! (n -k -r -ℓ + 1)! A(n, p, ℓ), (12)
where

A(n, p, ℓ) := µ⊢n, ℓ(µ)=p [p µ (x)] λ⊢n, ℓ(λ)=ℓ m λ (x).
The next lemma gives a formula for A(n, p, ℓ).

Lemma 9. For any positive integers p, ℓ ≤ n µ⊢n, ℓ(µ)=p

[p µ (x)] λ⊢n, ℓ(λ)=ℓ m λ (x) = n -1 ℓ -1 (-1) ℓ-p c(ℓ, p) ℓ! , (13)
where c(a, b) are the signless Stirling numbers of the first kind.

Proof. For this proof we use the principal specialization of symmetric functions, that is, their evaluation at x = 1 a := {1, 1, . . . , 1, 0, 0 . . .} (a ones). Since p γ (1 a ) = a ℓ(γ) for any positive integer a, one gets

λ⊢n, ℓ(λ)=ℓ m λ (1 a ) = n p=1 a p µ⊢n, ℓ(µ)=p [p µ (x)] λ⊢n, ℓ(λ)=ℓ m λ (x).
The right-hand side of the previous equation is a polynomial in a, and by extracting the coefficient of a p one gets

µ⊢n, ℓ(µ)=p [p µ (x)] λ⊢n, ℓ(λ)=ℓ m λ (x) = [a p ] λ⊢n, ℓ(λ)=ℓ m λ (1 a ).
Now, for any partition λ, m λ (1 a ) counts the a-tuples of nonnegative integers such that the positive ones are the same as the parts of λ (in some order). Hence λ⊢n, ℓ(λ)=ℓ m λ (1 a ) counts the a-tuples of nonnegative integers with ℓ positive ones summing to n. This gives,

λ⊢n, ℓ(λ)=ℓ m λ (1 a ) = n -1 ℓ -1 a ℓ .
Extracting the coefficient of a p gives (13) since [a p ] a ℓ = (-1) ℓ-p c(ℓ, p) ℓ! .

Using Lemma 9 in [START_REF] Vassilieva | Explicit monomial expansions of the generating series for connection coefficients[END_REF] gives

#S α (n, p) = n! n-m r≥0 1 -k r n + k -1 n -m -r n-k-r+1 ℓ=1 n -k -r ℓ -1 (-1) ℓ-p c(ℓ, p) ℓ! , (14)
which we simplify using the following lemma.

Lemma 10. For any nonnegative integer a, a q=0 a q (-1) q+1-p c(q + 1, p)

(q + 1)! = c(a + 1, p) (a + 1)! .
Proof. The left-hand side equals [x p ] a q=0 a q x q+1 . Using the Chu-Vandermonde identity this equals [x p ] x+a a+1 which is precisely the right-hand side. Using Lemma 10 in (14) gives

#S α (n, p) = n! n-m r=0 1 -k r n + k -1 n -m -r c(n -k -r + 1, p) (n -k -r + 1)! , (15)
which is equivalent to (11) via (3). This completes the proof of Theorem 8.

In the case p = 1, the expression [START_REF] Stanley | Products of cycles[END_REF] for the probability σ α (1) = σ α (n) can be written as a sum of m -k terms instead. We state this below.

Corollary 11. Let α be a composition of m with k parts. Then the separation probabilities σ α (n) (separation for the product of two uniformly random n-cycles) are

σ α (n) = (n -m)! k i=1 α i ! (n + k)(n -1)! (-1) n-m n-1 k-2 n+m m-k + m-k r=0 (-1) r m-k r n+r+1 m n+k+r r
.

The equation in Corollary 11, already stated in the introduction, is particularly simple when m -k is small. For α = 1 k (i.e. m = k) one gets the result stated at the beginning of this paper:

σ 1 k (n) = 1 k! if n -k odd, 1 k! + 2 (k-2)!(n-k+1)(n+k) if n -k even. ( 16
)
In order to prove Corollary 11 we start with the expression obtained by setting p = 1 in (11):

σ α (n) = (n -m)! k i=1 α i ! (n -1)! n-m r=0 1 -k r 1 n -k -r + 1 n + k -1 n -m -r = (n -m)! k i=1 α i ! (n -1)! [x n-m ](1 + x) 1-k n+k-1 r=0 x r r + m -k + 1 n + k -1 r . ( 17
)
We now use the following polynomial identity.

Lemma 12. For nonnegative integers a, b, one has the following identity between polynomials in x:

a i=0 x i i + b + 1 a i = 1 (a + 1) 1 a+b+1 b (-x) b+1 - b i=0 b i (x + 1) a+i+1 a+i+1 i (-x) i+1 . ( 18
)
Proof. It is easy to see that the left-hand side of (18) is equal to 1

x b+1

x 0 (1 + t) a t b dt. Now this integral can be computed via integration by parts. By a simple induction on b, this gives the right-hand side of (18). Now using (18) in (17), with a = n + k -1 and b = m -k, gives

σ α (n) = (n -m)! k i=1 α i ! (n + k)(n -1)! [x n-m ] (1 + x) 1-k n+m m-k (-x) m-k+1 - m-k r=0 m-k r (1 + x) n+r+1 n+k+r r (-x) r+1 = (n -m)! k i=1 α i ! (n + k)(n -1)! (-1) n-m n-1 k-2 n+m m-k + m-k r=0 (-1) r m-k r n+r+1 m n+k+r r
.

This completes the proof of Corollary 11.

Case when π is a fixed-point-free involution

Given a composition α of m ≤ 2N with k parts, we define

H α N (t) := (π,A)∈S α 2 N t excess(π,A) ,
where excess(π, A) is the number of cycles of the product π • (1, 2, . . . , 2N ) containing none of the elements of A and where π is a fixed-point-free involution of

[2N ]. Note that H α N (t) = [p 2 N (x)] G α 2N (x, t)
. We now give an explicit expression for this series.

Theorem 13. For any composition α of m ≤ 2N of length k, the generating series H α N (t + k) is given by

H α N (t + k) = N min(2N -m,N -k+1) r=0 t r 2N + k -1 2N -m -r 2 k+r-N (2N -k -r)! (N -k -r + 1)! . ( 19
)
Consequently the separation probabilities for the product of a fixed-point-free involution with a 2N -cycle are given by

σ α 2 N = k i=1 α i ! (2N -1)!(2N -1)!! min(2N -m,N -k+1) r=0 1 -k r 2N + k -1 2N -m -r 2 k+r-N -1 (2N -k -r)! (N -k -r + 1)! . ( 20
)
Remark 14. It is possible to prove Theorem 13 directly using ideas similar to the ones used to prove Theorem 6 in Section 2. This will be explained in more detail in Section 5. In the proof given below, we instead obtain Theorem 13 as a consequence of Theorem 6.

The rest of this section is devoted to the proof of Theorem 13. Since

H α N (t) = [p 2 N (x)] G α 2N (x, t), Theorem 6 gives H α N (t + k) = (21) 2N -m r=0 t r 2N + k -1 2N -m -r N -k-r+1 s=0 2N (N -s)!(2N -k -r)! (N -k -r -s + 1)! [p 2 N (x)] λ⊢2N, ℓ(λ)=N +s m λ (x).
We then use the following result.

Lemma 15. For any nonnegative integer s ≤ N ,

[p 2 N (x)] λ⊢2N, ℓ(λ)=N +s m λ (x) = (-1) s 2 s s!(N -s)! .
Proof. For partitions λ, µ of n, we denote S λ,µ = [p λ (x)]m µ (x) and R λ,µ = [m λ (x)]p µ (x). The matrices S = (S λ,µ ) λ,µ⊢n and R = (R λ,µ ) λ,µ⊢n are the transition matrices between the bases {p λ } λ,⊢n and {m λ } λ⊢n of symmetric functions of degree n, hence S = R -1 . Moreover the matrix R is easily seen to be lower triangular in the dominance order of partitions, that is, R λ,µ = 0 unless

λ 1 + λ 2 + • • • + λ i ≤ µ 1 + µ 2 + • • • + µ i for all i ≥ 1 ([ 10
, Prop. 7.5.3]). Thus the matrix S = R -1 is also lower triangular in the dominance order. Since the only partition of 2N of length N + s that is not larger than the partition 2 N in the dominance order is 1 2s 2 N -s , one gets

[p 2 N (x)] λ⊢2N, ℓ(λ)=N +s m λ (x) = [p 2 N (x)] m 1 2s 2 N-s (x). ( 22
)
To compute this coefficient we use the standard scalar product •, • on symmetric functions (see e.g. [10, Sec. 7]) defined by p λ , p µ = z λ if λ = µ and 0 otherwise, where z λ was defined at the end of Section 1. From this definition one immediately gets

[p 2 N ] m 1 2s 2 N-s = 1 z 2 N p 2 N , m 1 2s 2 N-s = 1 N !2 N p 2 N , m 1 2s 2 N-s . (23)
Let {h λ } denote the basis of the complete symmetric functions. It is well known that h λ , m µ = 1 if λ = µ and 0 otherwise, therefore

p 2 N , m 1 2s 2 N-s = [h 1 2s 2 N-s ]p 2 N . Lastly, since p 2 N = (p 2 ) N and p 2 = 2h 2 -h 2 1 one gets p 2 N , m 1 2s 2 N-s = [h 1 2s 2 N-s ]p 2 N = [h 2s 1 h N -s 2 ] (2h 2 -h 2 1 ) N = 2 N -s (-1) s N s . (24)
Putting together ( 22), ( 23) and (24) completes the proof.

By Lemma 15, Equation (21) becomes

H α N (t + k) = 2N -m r=0 t r 2N + k -1 2N -m -r N -k-r+1 s=0 2N (N -s)!(2N -k -r)! (N -k -r -s + 1)! (-1) s 2 s s!(N -s)! = 2N 2N -m r=0 t r 2N + k -1 2N -m -r (2N -k -r)! (N -k -r + 1)! N -k-r+1 s=0 N -k -r + 1 s (-1) s 2 s = 2N min(2N -m,N -k+1) r=0 t r 2N + k -1 2N -m -r (2N -k -r)! (N -k -r + 1)! 1 2 N -k-r+1 ,
where the last equality uses the binomial theorem. This completes the proof of Equation (19). Equation (20) then immediately follows from the case t = 1 -k of (19) via (3). This completes the proof of Theorem 13.

Adding fixed points to the permutation π

In this section we obtain a relation between the separation probabilities σ α λ and σ α λ ′ , when the partition λ ′ is obtained from λ by adding some parts of size 1. Our main result is given below.

Theorem 16. Let λ be a partition of n with parts of size at least 2 and let λ ′ be the partition obtained from λ by adding r parts of size 1. Then for any composition α = (α 1 , . . . , α k ) of m ≤ n+r of length k,

#S α λ ′ = m-k p=0 n + p n n + m + r -p n + m + m -p n n + m + r -p -1 n + m m -k p #S (m-k-p+1,1 k-1 ) λ .
(25) Equivalently, in terms of separation probabilities,

σ α λ ′ = n! n+r α 1 ,...,α k ,n+r-m n+r r m-k p=0 n+p n n+m+r-p n+m + m-p n n+m+r-p-1 n+m m-k p (n -m + p)!(m -k -p + 1)! σ (m-k-p+1,1 k-1 ) λ . ( 26
)
For instance, when α = 1 k Theorem 16 gives

σ 1 k λ ′ = n+r-k r n+r r 2 n + r + k n + k + k n n + r + k -1 n + k σ 1 k λ .
The rest of the section is devoted to proving Theorem 16. Observe first that (26) is a simple restatement of (25) via (3) (using the fact that #C λ ′ = n+r n #C λ ). Thus it only remains to prove (25), which amounts to enumerating S α λ ′ . For this purpose, we will first define a mapping Ψ from S α λ ′ to Ŝα λ , where Ŝα λ is a set closely related to S α λ . We shall then count the number of preimages of each element in Ŝα λ under the mapping Ψ. Roughly speaking, if (π ′ , A) is in S α λ ′ and the tuple A = (A 1 , . . . , A k ) is thought as "marking" some elements in the cycles of the permutation ω = π ′ • (1, 2, . . . , n + r), then the mapping Ψ simply consists in removing all the fixed points of π ′ from the cycle structure of ω and transferring their "marks" to the element preceding them in the cycle structure of ω.

We introduce some notation. A multisubset of [n] is a function M which associates to each integer i ∈ [n] its multiplicity M (i) which is a nonnegative integer. The integer i is said to be in the multisubset M if M (i) > 0. The size of M is the sum of multiplicities n i=1 M (i). For a composition α = (α 1 , . . . , α k ), we denote by Âα n the set of tuples (M 1 , . . . , M k ) of disjoint multisubsets of [n] (i.e., no element i ∈ [n] is in more than one multisubset) such that the multisubset M j has size α j for all j ∈ [k]. For M = (M 1 , . . . , M k ) in Âα n we say that a permutation π of [n] is M -separated if no cycle of π contains elements of more than one of the multisubsets M j . Lastly, for a partition λ of n we denote by Ŝα λ the set of pairs (π, M ) where π is a permutation in C λ , and M is a tuple in Âα n such that the product π

• (1, 2, . . . , n) is M -separated.
We now set λ, λ ′ , α, k, m, n, r to be as in Theorem 16, and define a mapping Ψ from S α λ ′ to Ŝα λ . Let π ′ be a permutation of [n + r] of cycle type λ ′ , and let e 1 < e 2 < • • • < e n ∈ [n + r] be the elements not fixed by π ′ . We denote ϕ(π ′ ) the permutation π defined by setting π(i) = π(j) if π ′ (e i ) = e j . Observe that π has cycle type λ. Now given a pair (π ′ , A) in S α λ ′ , where A = (A 1 , . . . , A k ), we consider the pair Ψ(π ′ , A) = (π, M ), where π = ϕ(π ′ ) and M = (M 1 , . . . , M k ) is a tuple of multisubsets of [n] defined as follows: for all j ∈ [k] and all i ∈ [n] the multiplicity M j (i) is the number of elements in the sequence F i belonging to the subset A j (where the sequence F i is defined as in Remark 17). It is easy to see that Ψ is a mapping from S α λ ′ to Ŝα λ . We are now going to evaluate #S α λ ′ by counting the number of preimages of each element in Ŝα λ under the mapping Ψ. As we will see now, the number of preimages of a pair (π, M ) in Ŝα λ only depends on M .

Lemma 18. Let (π, M ) ∈ Ŝα λ , where M = (M 1 , . . . , M k ). Let s be the number of distinct elements appearing in the multisets M 1 , . . . , M k , and let x = k j=1 M j (n) be the multiplicity of the integer n. Then the number of preimages of the pair (π, M ) under the mapping Ψ is

#Ψ -1 (π, M ) =        n + r + s n + m if x = 0, x n + r + s n + m + n + r + s -1 n + m otherwise. ( 27
)
Proof. We adopt the notation of Remark 17, and for all i ∈ [n] we denote M * (i) = k j=1 M j (i) the multiplicity of the integer i. In order to construct a preimage (π ′ , A) of (π, M ), where

A = (A 1 , . . . , A k ), one has to (i) choose for all i ∈ [n] the length f i > 0 of the sequence F i (with n i=1 f i = n + r), (ii) choose the position b ∈ [f n ] corresponding to the integer n + r in the sequence F n , (iii) if M j (i) > 0 for some i ∈ [n] and j ∈ [k],
then choose which M j (i) elements in the sequence F i are in the subset A j . Indeed, the choices (i), (ii) determine the permutation π ′ ∈ C λ ′ (since they determine the fixedpoints of π ′ , which is enough to recover π ′ from π), while by Remark 17 the choice (iii) determines the tuple of subsets A = (A 1 , . . . , A k ).

We will now count the number ways of making the choices (i), (ii), (iii) by encoding such choices as rows of (marked and unmarked) boxes as illustrated in Figure 2. We treat separately the cases x = 0 and x = 0. Suppose first x = 0. To each i ∈ [n] we associate a row of boxes R i encoding the choices (i), (ii), (iii) as follows:

(1) if i = n and M * (i) = 0, then the row R i is made of f i boxes, the first of which is marked, (2) if i = n and M * (i) > 0, then the row R i is made of f i + 1 boxes, with the first box being marked and M * (i) other boxes being marked (the marks represent the choice (iii)), (3) the row R n is made of f n + 1 boxes, with the first box being marked and an additional box being marked and called special marked box (this box represents the choice (ii)). There is no loss of information in concatenating the rows R 1 , R 2 , . . . , R n given that M is known (indeed the row R i starts at the (i + N i )th marked box, where N i = h<i M * (h) ). This concatenation results in a row of n + r + s + 1 boxes with n + m + 1 marks such that the first box is marked and the last mark is "special"; see Figure 2. Moreover there are n+r+s n+m such rows of boxes and any of them can be obtained for some choices of (i), (ii), (iii). This proves the case x = 0 of Lemma 18.

We now suppose x > 0. We reason similarly as above but there are now two possibilities for the row R n , depending on whether or not the integer n + r belongs to one of the subsets A 1 , . . . , A k . In order to encode a preimage such that n + r belong to one of the subsets A 1 , . . . , A k the condition (3) above must be changed to 2),(3) encoded by a sequence of boxes, some of which being marked (indicated in gray), with one mark being special (indicated with a cross). Here n = 6, k = 2, r = 11, x = 0 and the multisubsets M 1 , M 2 are defined by M 1 (1) = 1, M 2 (3) = 1, M 1 (4) = 3, and M j (i) = 0 for the other values of i, j.

R1 (f1 = 4) R2 (f2 = 2) R3 (f3 = 2) R4 (f4 = 5) R5 (f5 = 1) R6 (f6 = 3, x = 0)
(3') the row R n is made of f n + 1 boxes, with the first box being marked and x other boxes being marked, one of which being called special marked box. In this case, concatenating the rows R 1 , R 2 , . . . , R n gives a row of n + r + s boxes with n + m marks, with the first box being marked and one of the x last marked boxes being special. There are x n+r+s-1 n+m-1 such rows and each of them comes from a unique choice of (i), (ii) and (iii). Lastly, in order to encode a preimage such that n + r does not belong to one of the subsets A 1 , . . . , A k the condition (3) above must be changed to (3") the row R n is made of f n + 1 boxes, with the first box being marked and x + 1 other boxes being marked, one of which being called special marked box. In this case, concatenating the rows R 1 , R 2 , . . . , R n gives a row of n + r + s boxes with n + m + 1 marks, with the first box being marked and one of the x + 1 last marked boxes being special. There are (x + 1) n+r+s-1 n+m such rows and each of them comes from a unique choice of (i), (ii) and (iii). Thus, in the case x > 0 one has

#Ψ -1 (π, M ) = x n + r + s -1 n + m -1 + (x + 1) n + r + s -1 n + m = x n + r + s n + m + n + r + s -1 n + m .
This completes the proof of Lemma 18.

We now complete the proof of Theorem 16. For any composition γ = (γ 1 , . . . , γ k ), we denote by Ŝα,γ λ the set of pairs (π, M ) in Ŝα λ , where the tuple M = (M 1 , . . . , M k ) is such that for all j ∈ [k] the multisubset M j (which is of size α j ) contains exactly γ j distinct elements. Summing (27) gives

(π,M )∈ Ŝα,γ λ #Ψ -1 (π, M ) = (E(X) + P(X = 0)) n + r + |γ| n + m + P(X > 0) n + r + |γ| -1 n + m # Ŝα,γ λ , (28)
where X is the random variable defined as X = k j=1 M j (n) for a pair (π, M ) chosen uniformly randomly in Ŝα,γ

λ , E(X) is the expectation of this random variable, and P(X > 0) = 1 -P(X = 0) is the probability that X is positive.

Lemma 19. With the above notation, E(X) = m n , and
P(X > 0) = |γ| n .
Proof. The proof is simply based on a cyclic symmetry. For i ∈ [n] we consider the random variable X i = k j=1 M j (i) for a pair (π, M ) chosen uniformly randomly in Ŝα,γ λ . It is easy to see that all the variables X 1 , . . . , X n = X are identically distributed since the set Ŝα,γ λ is unchanged by cyclically shifting the value of the integers 1, 2, . . . , n in pairs (π, M ) ∈ Ŝα,γ λ . Therefore,

n E(X) = n i=1 E(X i ) = E n i=1 X i = E(m) = m,
and

n P(X > 0) = n i=1 P(X i > 0) = E n i=1 1 X i >0 = E (|γ|) = |γ|.
We now enumerate the set Ŝα,γ λ . Observe that any pair (π, M ) in Ŝα,γ λ can be obtained (in a unique way) from a pair (π, A) in S γ λ by transforming A = (A 1 , . . . , A k ) into M = (M 1 , . . . , M k ) as follows: for each j ∈ [k] one has to assign a positive multiplicity M j (i) for all i ∈ A j so as to get a multisubset M j of size α j . There are α j -1 γ j -1 ways of performing the latter task, hence

# Ŝα,γ λ = k i=1 α i -1 γ i -1 #S γ λ .
Using this result and Lemma 19 in (28) gives

(π,M )∈ Ŝα,γ λ #Ψ -1 (π, M ) = m + n -|γ| n n + r + |γ| n + m + |γ| n n + r + |γ| -1 n + m k i=1 α i -1 γ i -1 #S γ λ .
Observe that the above expression is 0 unless γ is less or equal to α componentwise. Finally, one gets

#S α λ ′ = γ≤α, ℓ(γ)=k m + n -|γ| n n + r + |γ| n + m + |γ| n n + r + |γ| -1 n + m k i=1 α i -1 γ i -1 #S γ λ , (29)
where the sum is over compositions γ with k parts, which are less or equal to α componentwise. Lastly, by Corollary 7, the cardinality #S γ λ ′ only depends on the composition α through the length and size of α. Therefore, one can use (29) with α = (m-k+1, 1 k-1 ), in which case the compositions γ appearing in the sum are of the form γ = (m -k -p + 1, 1 k-1 ) for some p ≤ m -k. This gives (25) and completes the proof of Theorem 16.

Bijective proofs and interpretation in terms of maps

In this section we explain how certain results of this paper can be interpreted in terms of maps, and can be proved bijectively. In particular, we shall interpret the sets T α γ,δ of "separated colored factorizations" (defined in Section 2) in terms of maps. We can then extend a bijection from [START_REF] Bernardi | An analogue of the Harer-Zagier formula for unicellular maps on general surfaces[END_REF] in order to prove bijectively the symmetry property stated in Corollary 7.

Interpretations of (separated) colored factorizations in terms of maps

We first recall some definitions about maps. Our graphs are undirected, and they can have multiple edges and loops. Our surfaces are two-dimensional, compact, boundaryless, orientable, and considered up to homeomorphism; such a surface is characterized by its genus. A connected graph is cellularly embedded in a surface if its edges are not crossing and its faces (connected components of the complement of the graph) are simply connected. A map is a cellular embedding of a connected graph in an orientable surface considered up to homeomorphism. A map is represented in Figure 3. By cutting an edge in its midpoint one gets two half-edges. A map is rooted if one of its half-edges is distinguished as the root. In what follows we shall consider rooted bipartite maps, and consider the unique proper coloring of the vertices in black and white such that the root half-edge is incident to a black vertex.

By a classical encoding (see e.g. [START_REF] Lando | Graphs on surfaces and their applications[END_REF]), for any partitions λ, µ of n, the solutions (π 1 , π 2 ) ∈ C λ × C µ of the equation π 1 • π 2 = (1, 2, . . . , n) are in bijection with the rooted one-face bipartite maps such that black and white vertices have degrees given by the permutations λ and µ respectively. That is, the number of black (resp. white) vertices of degree i is equal to the number of parts of the partition λ (resp. µ) equal to i. Let γ = (γ 1 , . . . , γ ℓ ), δ = (δ 1 , . . . , δ ℓ ′ ) be compositions of n and let α = (α 1 , . . . , α k ) be a composition of m ≤ n. A rooted bipartite map is (γ, δ)-colored if its black vertices are colored in [ℓ] (that is, every vertex is assigned a "color" in [ℓ]) in such a way that γ i edges are incident to black vertices of color i, and its white vertices are colored in [ℓ ′ ] in such a way that δ i edges are incident to white vertices of color i. Through the above mentioned encoding, the set B γ,δ of colored factorizations of the n-cycles defined in Section 2 corresponds to the set of (γ, δ)-colored rooted bipartite one-face maps. Similarly, the sets T α γ,δ of "separated colored factorizations" corresponds to the set of (γ, δ)-colored rooted bipartite one-face maps with some marked edges, such that for all i ∈ [k] exactly α i marked edges are incident to white vertices colored i.

The results in this paper can then be interpreted in terms of maps. For instance, one can interpret [START_REF] Morales | Bijective enumeration of bicolored maps of given vertex degree distribution[END_REF] in the case m = k = 0 (no marked edges) as follows:

λ⊢n M ∈B λ p λ (x) t #white vertices = G ∅ n (x, t) = n r=1 λ⊢n, ℓ(λ)≤n-r+1 m λ (x) t r n(n -ℓ(λ))!(n -r)! (n -r -ℓ(λ) + 1)! n -1 n -r ,
where B λ is the set of rooted bipartite one-face maps such that black vertices have degrees given by the partition λ. The results in Subsection 3.2 can also be interpreted in terms of general (i.e., non-necessarily bipartite) maps. Indeed, the set M N = B 2 N can be interpreted as the set of general rooted one-face maps with N edges (because a bipartite map in which every black vertex has degree two can be interpreted as a general map upon contracting the black vertices). Therefore one can interpret (19) in the case m = k = 0 (no marked edges) as follows:

M ∈M N t #vertices = H ∅ N (t) = N N +1 r=1 t r 2 r-N (2N -r)! (N -r + 1)! 2N -1 2N -r . ( 30
)
This equation is exactly the celebrated Harer-Zagier formula [START_REF] Harer | The Euler characteristic of the moduli space of curves[END_REF].

Bijection for separated colored factorizations, and symmetry

In this section, we explain how some of our proofs could be made bijective. In particular we will use bijective results obtained in [START_REF] Bernardi | An analogue of the Harer-Zagier formula for unicellular maps on general surfaces[END_REF] in order to prove the symmetry result stated in Corollary 7.

We first recall the bijection obtained in [START_REF] Bernardi | An analogue of the Harer-Zagier formula for unicellular maps on general surfaces[END_REF] about the sets B γ,δ . We define a tree-rooted map to be a rooted map with a marked spanning tree; see Figure 3(b). We say that a bipartite tree-rooted map is (ℓ, ℓ ′ )-labelled if it has ℓ black vertices labelled with distinct labels in [ℓ], and ℓ ′ white vertices labelled with distinct labels in [ℓ ′ ]. It was shown in [START_REF] Bernardi | An analogue of the Harer-Zagier formula for unicellular maps on general surfaces[END_REF] that for any compositions γ = (γ 1 , . . . , γ ℓ ), δ = (δ 1 , . . . , δ ℓ ′ ) of n, the set B γ,δ is in bijection with the set of (ℓ, ℓ ′ )-labelled bipartite tree-rooted maps such that the black (resp. white) vertex labelled i has degree γ i (resp. δ i ).

From this bijection, it is not too hard to derive the enumerative formula [START_REF] Mohar | Graphs on surfaces[END_REF] (see Remark 21). We now adapt the bijection established in [START_REF] Bernardi | An analogue of the Harer-Zagier formula for unicellular maps on general surfaces[END_REF] to the sets T α γ,δ of "separated colored factorizations". For a composition α = (α 1 , . . . , α k ), a (ℓ, ℓ ′ )-labelled bipartite maps is said to be α-marked if α i edges incident to the white vertex labelled i are marked for all i in [k].

Theorem 20. The bijection in [START_REF] Bernardi | An analogue of the Harer-Zagier formula for unicellular maps on general surfaces[END_REF] extends into a bijection between the set T α γ,δ and the set of α-marked (ℓ, ℓ ′ )-labelled bipartite tree-rooted maps with n edges such that the black (resp. white) vertex labelled i has degree γ i (resp. δ i ).

We will now show that the bijection given by Theorem 20 easily implies

#T α γ (r) = #T β γ (r), (31)
whenever the compositions α and β have the same length and size. Observe that, in turn, (31) readily implies Corollary 7. By Theorem 20, the set T α γ (r) specified by Definition 2 is in bijection with the set T α γ (r) of α-marked (ℓ, k + r)-labelled bipartite tree-rooted maps with n edges such that the black vertex labelled i has degree γ i . We will now describe a bijection between the sets T α γ (r) and T β γ (r) when α and β have the same length and size. For this purpose it is convenient to interpret maps as graphs endowed with a rotation system. A rotation system of a graph G is an assignment for each vertex v of G of a cyclic ordering of the half-edges incident to v. Any map M defines a rotation system ρ(M ) of the underlying graph: the cyclic orderings are given by the clockwise order of the halfedges around the vertices. This correspondence is in fact bijective (see e.g. [START_REF] Mohar | Graphs on surfaces[END_REF]): for any connected graph G the mapping ρ gives a bijection between maps having underlying graph G and the rotation systems of G. Using the "rotation system" interpretation, any map can be represented in the plane (with edges allowed to cross each other) by choosing the clockwise order of the half-edges around each vertex to represent the rotation system; this is the convention used in Figures 4 and5 )-labelled bipartite tree-rooted map obtained by applying the mapping ϕ 1,3 . In this figure, maps are represented using the "rotation system interpretation", so that the edge-crossings are irrelevant. The spanning trees are drawn in thick lines, the marked edges are indicated by stars, and the root half-edge is indicated by an arrow.

We now prove (31) it is sufficient to establish a bijection between the sets T α γ (r) and T β γ (r) in the case α = (α 1 , . . . , α k ), β = (β 1 , . . . , β k ) with β i = α i -1, β j = α j + 1 and α s = β s for s = i, j. Let M be an α-marked (ℓ, ℓ ′ )-labelled bipartite tree-rooted map. We consider the path joining the white vertices i and j in the spanning tree of M . Let e i and e j be the edges of this path incident to the white vertices i and j respectively; see Figure 4. We consider the first marked edge e ′ i following e i in clockwise order around the vertex i (note that e i = e ′ i since α i = β i + 1 > 1). We then define ϕ i,j (M ) as the map obtained by ungluing from the vertex i the half-edge of e ′ i as well as all the half-edges appearing strictly between e i and e ′ i , and gluing them (in the same clockwise order) in the corner following e j clockwise around the vertex j. Figure 4 illustrates the mapping ϕ 1,3 . It is easy to see that ϕ i,j (M ) is a tree-rooted map, and that ϕ i,j and ϕ j,i are reverse mappings. Therefore ϕ i,j (M ) is a bijection between T α γ (r) and T β γ (r). This proves (31).

Remark 21. By an argument similar to the one used above to prove (31), one can prove that if γ, γ ′ , δ, δ ′ are compositions of n such that ℓ(γ) = ℓ(γ ′ ) and ℓ(δ) = ℓ(δ ′ ) then B γ,δ = B γ ′ ,δ ′ (this is actually done in a more general setting in [START_REF] Bernardi | Bijections and symmetries for the factorizations of the long cycle[END_REF]). From this property one can compute the cardinality of B γ,δ by choosing the most convenient compositions γ, δ of length ℓ and ℓ ′ . We take γ = (n -ℓ + 1, 1, 1, . . . , 1) and δ = (n -ℓ ′ + 1, 1, 1, . . . , 1), so that #B γ,δ is the number of (ℓ, ℓ ′ )labelled bipartite tree-rooted maps with the black and white vertices labelled 1 of degrees n -ℓ + 1 and n-ℓ ′ +1 respectively, and all the other vertices of degree 1. In order to construct such an object (see Figure 5), one must choose the unrooted plane tree (1 choice), the labelling of the vertices ((ℓ -1)!(ℓ ′ -1)! choices), the n -ℓ -ℓ ′ + 1 edges not in the tree ( n-ℓ n-ℓ-ℓ ′ +1 n-ℓ ′ n-ℓ-ℓ ′ +1 (n -ℓ ′ -ℓ ′ + 1)! choices), and lastly the root (n choices). This gives (7). , where γ = (8, 1, 1, 1, 1), δ = (9, 1, 1, 1). Here the map is represented using the "rotation system interpretation", so that the edge-crossings are irrelevant.

A direct proof of Theorem 13

In Section 3 we obtained Theorem 13 as a consequence of Theorem 6. Here we explain how to obtain it directly.

First of all, by a reasoning identical to the one used to derive (5) one gets

H α N (t + k) = 2N -m r=0 t r #U α (r), (32)
where U α (r) is the set of triples (π, A, c 2 ) where π is a fixed-point free involution of [2N ], A is in A α n and c 2 is a a cycle coloring of the product π • (1, 2, . . . , 2N ) in [k + r] such that every color in [k + r] is used and for all i in [k] the elements in the subset A i are colored i.

In order to enumerate U α (r) one considers for each composition γ = (γ 1 , . . . , γ ℓ ) the set M γ of pairs (π, c 2 ), where π is a fixed-point-free involution of [2N ] and c 2 is a cycle coloring of the

Lemma 5 .

 5 and 0 otherwise. In order to complete the proof of Proposition 4, it only remains to prove the following lemma. If α has size m and length k, then δ|=n, ℓ(δ)=k+r

Figure 1 :

 1 Figure 1: A (2, 1, 2)-marked composition of size n = 12 and length 5 and its bijective transformation into a sequence n + k = 15 boxes with m + k + r = 5 + 3 + 2 = 10 marks, one of which is on the last box.

Remark 17 .

 17 If e 1 < e 2 < • • • < e n ∈ [n + r] are the elements not fixed by π ′ and π = ϕ(π ′ ), then the cycle structure of the permutation π ′ • (1, 2, . . . , n + r) is obtained from the cycle structure of π • (1, 2, . . . , n) by replacing each element i ∈ [n -1] by the sequence of elements F i = e i , e i + 1, e i + 2, . . . , e i+1 -1, and replacing the element n by the sequence of elements F n = e n , e n + 1, e n + 2, . . . , n + r, 1, 2, . . . , e 1 -1. In particular, the permutations π • (1, 2, . . . , n) and π ′ • (1, 2, . . . , n + r) have the same number of cycles.

Figure 2 :

 2 Figure 2: Example of choices (1),(2),(3) encoded by a sequence of boxes, some of which being marked (indicated in gray), with one mark being special (indicated with a cross). Here n = 6, k = 2, r = 11, x = 0 and the multisubsets M 1 , M 2 are defined by M 1 (1) = 1, M 2 (3) = 1, M 1 (4) = 3, and M j (i) = 0 for the other values of i, j.

Figure 3 :

 3 Figure 3: (a) A rooted bipartite one-face map. (b) A rooted bipartite tree-rooted map (the spanning tree is indicated by thick lines). The root half-edge is indicated by an arrow.

  .

1 Figure 4 :

 14 Figure4: Left: a (3, 1, 1)-marked (4, 5)-labelled bipartite tree-rooted map. Right: the (2, 1, 2)marked (4, 5)-labelled bipartite tree-rooted map obtained by applying the mapping ϕ 1,3 . In this figure, maps are represented using the "rotation system interpretation", so that the edge-crossings are irrelevant. The spanning trees are drawn in thick lines, the marked edges are indicated by stars, and the root half-edge is indicated by an arrow.

Figure 5 :

 5 Figure5: A tree-rooted map in B γ,δ , where γ = (8, 1, 1, 1, 1), δ = (9, 1, 1, 1). Here the map is represented using the "rotation system interpretation", so that the edge-crossings are irrelevant.

Acknowledgment: We thank Taedong Yun for several stimulating discussions.

* O.B. aknowledges support from NSF grant DMS-1068626, ANR A3, and ERC Explore-Maps.

permutation π • (1, 2, . . . , 2N ) such that γ i elements are colored i for all i ∈ [ℓ]. One then uses the following analogue of [START_REF] Mohar | Graphs on surfaces[END_REF]:

Using this result in conjunction with Lemma 5, one then obtains the following analogue of (6):

Plugging this result in (32) completes the proof of Theorem 13.

Similarly as [START_REF] Mohar | Graphs on surfaces[END_REF], Equation (33) can be obtained bijectively. Indeed by a classical encoding, the set M γ is in bijection with the set of rooted one-face maps with vertices colored in [ℓ] in such a way that for all i ∈ [ℓ], there are exactly γ i half-edges incident to vertices of color i. Using this interpretation, it was proved in [START_REF] Bernardi | An analogue of the Harer-Zagier formula for unicellular maps on general surfaces[END_REF] that the set M γ is in bijection with the set of tree-rooted maps with ℓ vertices labelled with distinct labels in [ℓ] such that the vertex labelled i has degree γ i . The latter set is easy to enumerate (using symmetry as in Remark 21) and one gets (33).

Concluding remarks: strong separation and connection coefficients

Given a partition λ of n and a composition α of m ≤ n, we denote by π α λ the probability that the product ω • ρ is strongly A-separated, where ω (resp. ρ) is a uniformly random permutation of cycle type λ (resp. (n)) and A is a fixed tuple in A α n . In particular, for a composition α of size m = n, one gets

where K α λ,(n) is the connection coefficient of the symmetric group counting the number of solutions (ω, ρ) ∈ C λ × C (n) , of the equation ω • ρ = φ where φ is a fixed permutation of cycle type α.

We now argue that the separation probabilities {σ α λ } α|=m computed in this paper are enough to determine the probabilities {π α λ } α|=m . Indeed, it is easy to prove that

where the sum is over the compositions β = (β 1 , . . . , β ℓ ) of size m = |α| such that there exists 0 = j 0 < j 1 < j 2 < • • • < j k = ℓ such that (β j i-1 +1 , β j i-1 +1 , . . . , β j i ) is a composition of α i for all i ∈ [k], and R α,β = k i=1 R i where R i is the number of ways of partitioning a set of size α i into blocks of respective sizes β j i-1 +1 , β j i-1 +1 , . . . , β j i . Moreover, the matrix (R α,β ) α,β|=m is invertible (since the matrix is upper triangular for the lexicographic ordering of compositions). Thus, from the separation probabilities {σ α λ } α|=m one can deduce the strong separation probabilities {π α λ } α|=m and in particular, for m = n, the connection coefficients K α λ,(n) of the symmetric group.


S Buzzaccaro
email: stefano.buzzaccaro@mail.polimi.it

E Secchi

G Brambilla

R Piazza

L Cipelletti
email: luca.cipelletti@univ-montp2.fr

Equilibrium concentration profiles and sedimentation kinetics of colloidal gels under gravitational stress

Keywords: numbers: 47.57.ef, 64.70.pv, 82.70.Dd

We study the sedimentation of colloidal gels by using a combination of light scattering, polarimetry and video imaging. The asymptotic concentration profiles ϕ(z, t → ∞) exhibit remarkable scaling properties: profiles for gels prepared at different initial volume fractions and particle interactions can be superimposed onto a single master curve by using suitable reduced variables. We show theoretically that this behavior stems from a power law dependence of the compressive elastic modulus vs ϕ, which we directly test experimentally. The sedimentation kinetics comprises an initial latency stage, followed by a rapid collapse where the gel height h decreases at constant velocity, and a final compaction stage characterized by a stretched exponential relaxation of h towards a plateau. Analogies and differences with previous works are briefly discussed.

Introduction

Colloidal gels are the focus of an intensive research effort for both fundamental and practical reasons. On the one hand, they are model systems to understand the interplay between percolation, phase separation and dynamical arrest in systems with attractive interactions [1,2,3]. On the other hand, colloidal gels are ubiquitous, e.g., in the food, drug, personal care and cosmetic industries, where they are often used as a means to stabilize a complex formulation against macroscopic phase separation. Mechanically, colloidal gels are viscoelastic systems with a predominantly solid-like behavior. However, they typically yield under a modest stress, often including the gravitational stress exerted by their own weight. It is therefore not surprising that many studies have been devoted to the sedimentation behavior of colloidal gels, revealing a wealth of fascinating but yet not fully understood phenomena, such as delayed sedimentation [4,5,6,7,8], creep [4,9,[START_REF] Condre | J Stat Mech -Theory and Experiments[END_REF][START_REF] Manley | [END_REF]12], and fracture associated with complex flow patterns [4,9,13]. With a few notable exceptions [4,6,8], most previous work has focussed on the macroscopic behavior of the gels, typically by measuring the time evolution of the gel height, h(t). This has prevented a thorough test of the various models proposed to rationalize the gel behavior, and in particular of the poroelastic model [14,15].

To overcome these limitations, we have recently reported in Ref. [16] a full characterization of the temporal evolution of the concentration profile, ϕ(z, t), sedimentation velocity profile, v(z, t) and microscopic rearrangement dynamics of a colloidal gel. In particular, we have shown that the poroelastic model captures remarkably well the evolution of h(t), ϕ(z, t) and v(z, t). Additionally, a single quantity, the compressive strain rate ε(t), was shown to control both the macroscopic behavior and the microscopic dynamics. Here, we test the generality of the findings of Ref. [16] by studying gels with different particle concentration and interparticle attraction strength. We focus on the sedimentation kinetics and on the asymptotic concentration profiles as the gels attain mechanical equilibrium, showing that the concentration profiles have a universal shape. Using the poroelastic model [14,15], we show that this remarkable scaling behavior stems from a particularly simple relation between elastic stress and local volume fraction. The rest of the paper is organized as follows: in Sec. 2 we describe the system and the optical methods used to investigate it. The main features of the poroelastic model are recalled in Sec. 3, while Secs. 4.1 and 4.2 report our findings on the asymptotic concentration profiles and the sedimentation kinetics, respectively, before the concluding remarks of Sec. 5.

Materials and methods

Sample preparation

The colloidal particles are spheres of a polytetrafluoroethylene copolymer (MFA). They have a crystalline core, leading to peculiar optical properties that allow one to measure accurately the local volume fraction, as discussed below. The data presented here are obtained using two different batches, B1 and B2, for which the particle radii are slightly different: R 1 = 82 ± 3 nm and R 2 = 92 ± 3 nm, for batches B1 and B2 respectively. The high density ρ = 2.14 g/cm 3 of MFA, combined with its lack of swelling, allows for a precise determination of the initial particle volume fraction ϕ 0 by density measurements. The particles are suspended in an aqueous solution of 0.1M NaCl, to screen electrostatic repulsive interactions, and different amounts of urea were added to suppress coherent polarized scattering by matching the solvent and particle refractive indices. A nonionic surfactant, Triton X100, is added to induce attractive depletion interactions [17], whose range r ≈ 3 nm is of the order of the size of the micelles formed by the surfactant. In the following we denote by φ TX the concentration of surfactant, defined by φ TX = V TX /(V s -V p ), where V TX , V p and V s are the volume of the surfactant, that of the particles, and the total volume of the suspension, respectively. A detailed description of the phase behavior of this system can be found in [2]. In brief, the system displays a metastable liquid-liquid coexistence gap; when the amount of added depletant is sufficiently large to drive the colloidal suspension within the coexistence region, as in our case, arrested spinodal decomposition leads to the formation of a disordered gel. All samples described here are deeply in the coexistence region, far from the spinodal line.

Because the range of the attractive potential is much smaller than the particle size, our system is well described by Baxter's adhesive hard sphere model [18]. It is convenient to quantify the strength of the attractive interactions via Baxter's stickiness parameter τ B . Using methods detailed in [2], we estimate τ ≈ 0.01 for the gels of batch B1 and τ B ≈ 0.02 for the gels of batch B2 at Φ TX = 0.11. The samples are prepared by mixing a particle suspension and a surfactant solution with appropriate concentrations; the resulting suspension is loaded in cells with square cross section (either 3×3 mm 2 or 5×5 mm 2 ) and filled to an initial height h 0 = 22.7 mm (h 0 = 32 mm) for batch B1 (B2). The samples are shaken at time t w = 0 and then left undisturbed for measurements during the sedimentation process.

Light scattering measurements

The apparatus used for light scattering measurements on systems prepared from the first batch is shown in Fig. 1 (a). The sample S is immersed in a transparent water bath B to minimize temperature gradients and temperature fluctuations. It is illuminated by a laser sheet LS, of thickness ≈ 200 µm, height sufficient to cover the whole gel column, and in-vacuo wavelength λ = 648 nm. The two lenses L1 and L2 form a demagnified image of the sample onto a charge-coupled detector (CCD) camera. Their focal length is 200 mm and 58 mm, respectively. Two crossed polarizers, P1 and P2, are used to illuminate the sample with light polarized in the vertical direction while detecting only depolarized scattered light, i.e. light linearly polarized in the horizontal direction. Note that this apparatus combines features of both imaging and scattering [19], since an image of the sample is formed, but using only light scattered around a well-defined scattering wave vector q = 4πnλ -1 sin(θ/2) = 18.5 µm -1 , with n = 1.356 the refractive index of the solvent and θ = 90 deg the scattering angle. A typical image recorded by the CCD is shown in Fig. 1 (b). The gel appears as a speckled, bright column, while the supernatant is black since scattering by the solvent is negligible. Each speckle results from the interference of the light scattered by a small volume in the sample, of depth equal to the laser sheet thickness and lateral size ≈ 50 µm. The speckle size is controlled to about 2 CCD pixels by adjusting the range of θ accepted by the detection optics, using the diaphragm D placed in the common focal plane of L1 and L2.

By analyzing a time series of CCD images, we measure four different quantities. The gel total height h(t) is simply obtained from the height of the bright column. The concentration profiles ϕ(z, t) are obtained by averaging the intensity I over regions of interest (ROIs) of height ≈ 100 µm and width equal to the cell width. We emphasize that in general the (polarized) scattered intensity is proportional to both ϕ and the particle structure factor S(q), thus making impossible a determination of the volume fraction based on I without a detailed knowledge of the sample structure. By contrast, our particles posses a crystalline core and thus partially depolarize the scattered light. As discussed, e.g., in Ref. [20], the depolarized scattered light can be shown to be simply proportional to ϕ, regardless of the structure. We use an image taken immediately after homogenizing the sample to determine the proportionality constant between I and ϕ and to correct for any non-uniformity in the incident beam intensity profile. As the gel sediments, the speckle pattern is shifted downwards: using cross-correlation methods similar to those used in particle imaging velocimetry [21], we are able to measure the full sedimentation velocity profiles, v(z, t), with a vertical resolution of about 0.5 mm. Finally, we measure the microscopic dynamics as detailed in Ref. [16], probing in particular particle motion in the horizontal plane, on a length scale of the order of q -1 ≈ R/1.5. As a final remark, we emphasize that our measurements of ϕ, of the microscopic dynamics and, to some extent, of v all rely on the assumption that the CCD images are formed only by singly scattered photons. Fortunately, the relative low average refractive index of the MFA particles (n p ≈ 1.356) allow one to carefully match n p using water-based solvents, thereby effectively suppressing multiple scattering.

For systems prepared from the second batch, we use a simplified version of the apparatus shown in Fig. 1, optimized for measuring only h(t) and ϕ(z, t) [2]. It consists of a custom-made light scattering setup, operating at a fixed scattering angle θ = 90 • . Selection of the incident and detected polarization of the scattered intensity is made by means of two Glan-Thomson polarizers with an extinction ratio better than 1 × 10 -6 . The cell is mounted on a DC-motorized micrometric translator allowing cell positioning with a resolution of 0.1 µm and an absolute accuracy of about 3 µm. A He-Ne laser beam is mildly focused in the cell to a spot size w = 46 µm, corresponding to a depth of focus (Rayleigh range) of about 10 mm, fixing the maximum useful optical path in the cell. The whole setup is enclosed into a removable hood allowing to control temperature to better than 0.5 • C.

Visualization of stresses

Valuable information on the distribution of the gravity-induced stress in the sample can be obtained by polarimetry. The sample is illuminated by a collimated beam of white light, issued from a LED source. A demagnified image of the gel is formed onto a CMOS camera, working in transmission. Two crossed polarizers are placed before and after the sample. Under these conditions, for a stress-free sample essentially no light is detected by the camera, because the birefringence induced by the particles is extremely weak. Because stress induces birefringence in the particles [22], regions of the gel where gravity-induced stress accumulates depolarize the incident light and appear as bright in the image (see Fig. 3 below for an example). More precisely [START_REF] Coker | Treatise on Photoelasticity[END_REF], when the transmission axes of the polarizers are oriented at ±45 deg with respect to the vertical direction, stresses along the horizontal and vertical direction are visualized. Conversely, by turning the polarizers so that their axes are vertical and horizontal, stresses oriented at ±45 deg with respect to the vertical direction can be imaged.

The poroelastic model

We shortly recall here the main features of the poroelastic model, a popular model introduced by Biot [14] and widely used in the literature (see e.g. [15]) to describe the deformation of a gel under its own weight. The system is treated as a continuum medium that responds elastically to a compressive deformation. The effect of the solvent back flow through the gel is accounted for by introducing a viscous friction term. For the sake of completeness, we introduce also a solid friction term, due to the adhesion of the gel to the container walls, which is usually not discussed in the literature.

Typically, the gel sedimentation occurs at a very low Reynolds number and the rate of change of v is small; thus, inertia terms can be neglected. Using the reference frame shown in Fig. 1 with z = 0 the cell bottom, Newton's law for a gel slice of thickness dz

yields ∂p ∂z = -∆ρϕg - ∂σ ∂z + σ L . (1)
Here, p is pressure, ∆ρ the buoyant density, g the acceleration of gravity, σ the elastic stress, and L a characteristic length. The term on the l.h.s. originates from the viscous drag, while the terms on the r.h.s. account for the buoyant weight, the elastic stress and the wall friction, respectively. In particular, L represents Jansen's screening length [START_REF] Boutreux | [END_REF]25], such that the gravitational stress in a given horizontal plane Σ exerted by a gel slice located ∆z above Σ is divided by a factor exp(∆zL -1 ). This screening is due to the redirection of part of the gel weight towards the walls. For L to be finite, the gel must "push" against the walls as it is compressed; in other words, the gel must have a positive Poisson's ratio ν, such that L = l(1 -ν)(µν) -1 is finite [START_REF] Boutreux | [END_REF]25], where l is side of the square cell section and µ is Coulomb's solid friction coefficient. We will show in Sec. 4.1 that for our gels ν ≈ 0 and hence L → ∞. Thus, in the following we shall neglect the wall friction term in Eq. ( 1). The conservation of colloidal particles is expressed by the continuity equation:

∂ϕ ∂t + ∂ ∂z (vϕ) = 0 . (2)
The particle velocity v is related to the viscous stress gradient by Darcy's law [START_REF] Darcy | Les Fontaines Publiques de la Ville de Dijon[END_REF] via

q = - κ(ϕ) η ∂p ∂z , ( 3
)
where κ is the volume fraction dependent permeability, η the solvent's viscosity, q = (1 -ϕ)(v s -v) the fluid flux in a reference frame co-moving with the gel, and v s the solvent velocity in the laboratory frame. Since the volume of the suspension (solvent plus particles) is conserved, (1 -ϕ)v s = -ϕv, which inserted in Eq. ( 3) yields

v = κ(ϕ) η ∂p ∂z . (4)
By inserting Eq. ( 4) in the continuity equation, Eq. ( 2), and replacing ∂p/∂z by the r.h.s. of Eq. ( 1) with no solid friction term, one finds

∂ϕ ∂t = ∂ ∂z ϕκ(ϕ) η ∆ρϕg + ∂σ ∂z . (5)
The final equation describing the temporal evolution of the concentration profiles in the poroelastic model is then

∂ϕ ∂t = ∂ ∂z ϕκ(ϕ) η ∆ρϕg + K(ϕ) ϕ ∂ϕ ∂z , (6)
where we have used the definition of the uniaxial compressional modulus K

K(ϕ) = ϕ ∂σ ∂ϕ . (7)
In order to solve Eq. ( 6), the two material functions κ(ϕ) and K(ϕ) must be specified. Insight on K(ϕ) may be gained by examining the gel behavior for t → ∞, when the gels approaches mechanical equilibrium. In this limit, v vanishes and so does the viscous friction. If wall friction is negligible, at any height z the buoyant weight per unit area of the gel column above z is balanced by the elastic response of the gel portion below z:

h∞ z ∆ρgϕdz = σ(z) , (8)
implying that ϕ must satisfy

∆ρgϕ = - ∂σ ∂z = - ∂σ ∂ϕ ∂ϕ ∂z . (9)
Experimentally, Eq. ( 8) can be used to obtain σ(z), provided that ϕ(z) can be measured. Once both σ(z) and ϕ(z) are known, the volume fraction dependence of the elastic stress is simply obtained by plotting directly σ vs ϕ. As we will show in Sec. 4.1, for our gels σ(ϕ) is well modeled by a power law:

σ(ϕ) = Aϕ α . (10)
Assuming this functional form, Eq. ( 9) can be easily solved:

ϕ(z) = ∆ρg A α -1 α (z max -z) 1 α-1 , (11)
where the integration constant z max is determined by imposing particle conservation, finding

z α α-1 max -(z max -h ∞ ) α α-1 = h 0 ϕ 0 α α -1 α α-1 A ∆ρg 1 α-1 . ( 12
)
The determination of the permeability κ(ϕ) is less straightforward. In practice, we test several functional forms proposed for κ(ϕ) and check whether they are able to reproduce the temporal evolution of h(t), the total gel height, as we shall discuss it in Sec. 4.2.

(13)

Results and discussion

Equilibrium concentration profiles

In this section, we focus on the particle volume fraction and interaction strength dependence of the concentration profiles in the long time limit, when no sedimentation is experimentally detectable and the gel is very close to mechanical equilibrium.

For gels of batch B1 and B2, concentration profiles where measured at least 240 and 500 hours after initializing the sample, respectively. We first focus on gels of batch B2. Figure 2a) shows ϕ ∞ (z) = ϕ(z, t → ∞) for three gels, prepared at various particle concentrations ϕ 0 but keeping the same particle interactions (φ TX = 0.12). The main plot shows that the shape of the concentration profiles does not depend on ϕ 0 : the profiles can be collapsed onto a master curve simply by shifting them along the z axis so as to make the top part coincide. Thus, the final height of a gel with a given ϕ 0 may be simply predicted using the master curve of Fig. 2 a) and imposing mass conservation. Note that this surprising scaling implies that gels prepared at different ϕ 0 compress in the same way and thus must have the same strength, a counterintuitive result. In fact, we anticipate that these gels are formed by the debris of a percolating network, which is too weak to sustain itself and collapses almost immediately. These debris must have similar structure regardless of ϕ 0 , so that the network resulting from their accumulation at the bottom of the cell has essentially the same mechanical properties.

Interestingly, we observe that the concentration profiles are not very smooth. Measurements of ϕ ∞ (z) for the same gels but using the "beam deflection" method described in Ref. [START_REF] Piazza | [END_REF] exhibit a smoother behavior, probably because in the beam deflection method the concentration profile is smoothed over a length comparable to the cell optical path (5 mm). The noise in ϕ as measured here may be due also to an extra-contribution to the intensity of the depolarized scattered light stemming from stress-induced birefringence, which we will show below to be spatially non-uniform. In spite of these differences, we emphasize that there is an overall good agreement between ϕ measured by the beam deflection and the depolarized scattered intensity methods [START_REF] Piazza | [END_REF].

The concentration profiles of gels prepared at a fixed particle concentration ϕ 0 = 8% and variable interaction strength are shown in Fig. 2 b). As φ TX increases, interparticle attractive forces grow and the gel becomes stronger, leading to a smaller compaction under the action of gravity. The change in gel strength is reflected by the fact that the shape of the asymptotic profiles is modified. Indeed, in this case the simple scaling shown in Fig. 2 a) is no more possible.

As discussed in Sec. 3, the asymptotic concentration profile is dictated by the ϕ dependence of the elastic stress σ, which may be obtained directly from the experimental ϕ ∞ (z), provided that wall friction is negligible. To investigate whether this assumption holds for our gels, we image the distribution of stresses in the gel by polarimetry. The inset of Fig. 3 shows the gel column observed under crossed polarizers, where highly stressed regions are brighter. In the left image, stresses along the vertical and horizontal direction are a priori imaged, although one of course expects vertical stress to dominate. The brightness increases towards the bottom of the cell, a first indication that most of the gravitational stress is transmitted downward, rather than being redirected to the walls. In the right image, the crossed polarizers have been rotated, in order to visualize stress oriented at ±45 deg with respect to the vertical direction, which would be nonnegligible if wall friction was significant. Although some bright patches do appear, we emphasize that the right image was taken with an exposure time 1000 times larger than for the left one. The intensity profiles along an horizontal line, corrected for the exposure time, clearly show that the vertical component of the stress dominates over that at ±45 deg, implying that wall friction can be neglected for our gels. Interestingly, this is at variance with observations for other kinds of colloidal gels [START_REF] Condre | J Stat Mech -Theory and Experiments[END_REF] and may be due to the fact that here the percolating network initially formed is then broken, in contrast to the gels of Ref. [START_REF] Condre | J Stat Mech -Theory and Experiments[END_REF].

From the asymptotic concentration profiles shown in Fig. 2 b), we calculate σ(ϕ) as described in Sec. 3 (see Eq. ( 8)) and plot the result in the inset of Fig. 4 a). The main graph shows that data for all Φ TX can be collapsed onto a single line in a log-log plot, thus indicating that the stress grows with ϕ as a power law: σ = Aϕ α . The exponent is essentially the same for all curves, as shown by the good collapse in Fig. 4. By contrast, the prefactor A depends on Φ TX : stronger bonds (larger Φ TX ) yield a stiffer gel. One expects A to scale with the interparticle bond spring constant, A ∼ U c /r 2 , where U c is the interparticle potential at contact. If the Triton micelles were non-interacting, U c Thus, this behavior hints at deviations with respect to the ideal depletion interaction induced by a diluted gas of micelles. In principle, both A and α may be obtained by fitting σ(ϕ) to a power law. However, we find that a more robust procedure consist in fitting the concentration profiles ϕ(z, t → ∞) to Eq. ( 11), the expression derived in Sec. 3 for a power law dependence of σ vs ϕ. The resulting fits are shown as lines in Fig. 2 b). We find that all the concentration profiles for the gels of Fig. 2 b) can be very well fit using the same value α = 4.08. We furthermore check that the fitting parameter z max of Eq. ( 11) satisfies Eq. ( 12) to within 2%. It is worth noting that, although σ must eventually diverge as ϕ approaches the volume fraction of random close packing, no hint of such divergence is observed here, nor in Ref. [16], up to ϕ values as high as 0.45 (batch B2) or even 0.55 (batch B1).

We check that the law σ = Aϕ α holds for all gels of both batches, with similar exponents: α = 3.6 (resp., 4.1) for batch B1 (resp., B2). Given the power law dependence of σ vs ϕ, Eq. [START_REF] Manley | [END_REF] suggests that all concentration profiles should collapse on the same straight line when plotting ϕ α-1 vs (z -z max )/ℓ, where ℓ = A/(∆ρg) is a characteristic length scale that compares the gel elasticity to the gravity pull. . Inset: asymptotic concentration profiles for all gels of both batches. Main plot: the same data collapse onto a straight line when using reduced variables, as explained in the text. Data for gels of batch B1 at ϕ 0 = 0.08 (resp., Φ TX = 0.12) are labeled by Φ TX (resp., ϕ 0 ). For the gel of batch B1, ϕ 0 = 0.12, φ TX = 0.12. The line is the poroelastic model.

shows that this is indeed the case for all the gels we have studied.

Sedimentation kinetics

The temporal evolution of the total height of the gel, h, exhibits a qualitatively similar behavior for all the gels of batches B1 and B2. Denoting by t w the time after filling the sample cell, an initial regime where no sedimentation occurs is observed for t w < t d . The latency time t d grows with the strength of interparticle bonds and ϕ 0 , as observed in previous works [4,5,6,7,8]. During this phase, the speckle dynamics is essentially frozen, indicating that a system-spanning arrested network has been formed. For t d ≤ t w < t c , h decreases steeply and the speckles fluctuate rapidly, indicating that the network has failed under gravitational stress. Finally, for t w ≥ t c the falling debris of the initial network have deposited at the bottom of the cell, forming a denser gel, as indicated by the dramatic slowing down of the speckle dynamics. This denser gel slowly compacts under its own weight: we define t = t w -t c and describe the gel evolution in this third regime using the poroelastic model of Sec. 3. An example of h(t w ) for a gel of batch B1 is shown in Fig. 6 a). Here, network failure occurs almost immediately, t d ≈ 0. Note that h(t w ) is almost identical for gels prepared in cells with square sections equal to 3 × 3 mm 2 and 5 × 5 mm 2 , thus confirming that wall effects are negligible. Interestingly, during the initial collapse h(t w ) decreases linearly in time, as observed also for gels of the second batch prepared at various ϕ 0 , see Fig. 6 b). This behavior is in striking contrast with that reported very recently by Bartlett et al. [8], who find a "compressed exponential" decrease, h(t w -t d ) ∼ exp{-[(t w -t d )/τ c ] 1.5 }. This difference might be due to the different range of the attractive potential, which is small in our case (r/R ≈ 0.037) and much larger in Ref. [8] (r/R ≈ 0.62). More experiments will be needed to elucidate this point. Figure 6 c) shows the time-varying part of h during the compaction stage, for various ϕ 0 . The decay of h is not a simple exponential, as shown by the curvature of the data in a semilogarithmic plot. Indeed, we find that the data can be reasonably well fit by a stretched exponential function,

h(t) -h ∞ ∼ exp[-(Γt) β ],
with β = 0.68 -0.87, depending on sample composition (fit not shown). Although the stretched exponential fit works well, it has no obvious theoretical interpretation, besides the generic remark that the system exhibits a distribution of relaxation times. A better justified fit is provided by the prediction of the poroelastic model, Eq. ( 6), which we solve numerically for the gel of batch B1 [16] and show as a continuous line in Figure 6 c). As discussed in Sec. 3, the permeability κ(ϕ) must be provided in order to solve Eq. (6). By testing various functional forms, including those proposed in the past for gels with a fractal structure [12], we find that only a critical-like law similar to that used for suspensions of hard spheres is able to reproduce our results: the solution to Eq. ( 6) reproduces very well the full time evolution of the concentration and velocity profiles, as reported in Ref. [16]. One of the most surprising findings of Ref. [16] is the linear variation of the sedimentation velocity v with height z in the gel column. Figure 7 a) shows that indeed |v| ∼ z, at least for the lower part of the gel column. Close to the top, deviations from this linear behavior appear, in that v appears to grow more slowly with z. These deviations are more pronounced for longer times. We define a compressive strain rate, εfit , as the slope of a linear fit to v(z) in the regime where a linear behavior is observed, e.g. up to z = 7 mm for data at t w = 30h in Fig. 7 a). We also define the strain rate measured at height z as ε(z) = v/z and plot its height dependence in Fig. 7 b). This quantity is almost independent of z, with the exception of the very bottom and top parts of the gel column, thus confirming that the temporal evolution of the full velocity profiles is essentially captured by the evolution of a single parameter, ε. Additionally, we have shown in Ref. [16] that ε governs also the microscopic dynamics, since structural rearrangements occur on a time scale τ α such that τ α ε = ε y , where ε y ≈ 0.02 is the typical yield strain beyond which irreversible rearrangements occur. In view of the key role played by ε, it is interesting to test whether a macroscopic measurement of the global strain rate, | ḣ|/h, reflects accurately the microscopic strain rate. In Fig. 7 c) we compare for a gel of batch B1 | ḣ|/h (dotted line) to εfit (crosses) and ε, the average of ε(z) over the gel height (open circles). In order to reduce the impact of the measurement noise on the numerical derivative of h(t), we differentiate the stretched exponential fit of h(t) discussed in reference to Figure 6 c), rather than the data themselves. Figure 7 c) shows that a reasonably good agreement is found between these three ways of quantifying the compressive strain rate, thus demonstrating that deviations from the linear behavior of v(z) are limited. To check the generality of our findings we simulate the time evolution of gels with different value of K(ϕ) and κ(ϕ). In all cases we have studied, |v| ∼ z in the lower part of the gel column while, close to the top, v grows slower with z. Besides εfit , ε(z) and | ḣ|/h are strongly correlated. In particular, we found that | ḣ|/h < ε(z) = v/z < εfit ≈ A| ḣ|/h with 1 < A < 1.35 depending on the functional form of K(ϕ) and κ(ϕ), so that ε may be directly estimated from | ḣ|/h. This observation can be particularly useful when dealing with turbid samples, where the velocity profiles can not be measured directly.

κ(ϕ) = κ 0 ϕ -1 (1 -ϕ)
Figure 7 c) shows also the macroscopic strain rate for the same three gels of batch B2 as in Figs. 2 a) and 6. In spite of the variation of ϕ 0 , the strain rate at the beginning of the compaction stage is of the same order of magnitude for all samples. This is probably due to the fact that the structure of the gel is similar, as discussed in relation to the scaling of the concentration profiles shown in Fig. 2 a). By contrast, the temporal evolution of the strain rate is significantly different, | ḣ|/h decaying faster for the gels at lower initial ϕ. This is at odd with the scaling behavior of the concentration profiles reported in Fig. 2a, where it was shown that the top part of the gels at fixed Φ TX have the same concentration profile. This can be qualitatively understood be recalling that, although the top of the profiles for samples prepared at different ϕ 0 are similar (see Fig. 4.1), gels prepared at higher initial concentration reach a higher volume fraction at the cell bottom. Therefore, they display in this region a lower permeability and a higher stiffness, which slows down the compaction process.

Conclusions

We have studied the sedimentation kinetics and the concentration profiles of depletioninduced colloidal gels, varying both the particle volume fraction and the strength of the interparticle interactions. By using optical methods that combine light scattering and imaging, we have been able to gain detailed information on the evolution of the concentration profiles and the dynamics of the gels. Coupled to stress visualization experiments that rule out any significant role of solid friction on the cell walls, this has allowed us to measure quantitatively the volume fraction dependence of the elastic response of the gels and to test thoroughly the poroelastic model. In discussing the ϕ 0 and Φ TX dependence of the parameters issued from the poroelastic model, it is essential to keep in mind that the model can only be applied to the last regime of the sedimentation process, i.e. the compaction of a denser gel formed by the falling debris of the initial network that fails under gravity. This allows one to rationalize some apparently paradoxical results, such as the scaling of the asymptotic concentration profiles obtained at fixed Φ TX and variable ϕ 0 .

Our work and that of other groups using confocal microscopy [6,8] show that detailed microscopic information on the structure and the dynamics of the gels can be very valuable in order to better understand the behavior of colloidal gels under gravitational stress. More work along these lines will be required to fully understand the microscopic origin of the diversity of behaviors observed for different systems.

Figure 1 .

 1 Figure 1. (a): schematic top view of the light scattering apparatus. See the text for more details. (b): Typical image of the sample. The gel is the bright, speckled column, the black part is the supernatant.

Figure 2 .

 2 Figure2. Inset of a): asymptotic concentration profiles for gels with fixed φ TX = 0.12 and various particle concentrations, as indicated in the labels. Main plot of a): same data rescaled onto a master curve as described in the text. b): asymptotic concentration profiles for gels with fixed ϕ 0 = 0.08 and various surfactant concentrations, as indicated by the labels. Lines: fits of Eq.[START_REF] Manley | [END_REF] to the data.

Figure 3 .

 3 Figure3. Inset: visualization of gravity-induced stress in a gel of batch B2 observed between crossed polarizers (ϕ = 0.08, Φ TX = 0.12). The height of the image corresponds to the gel height, the width of the cell is 5 mm. In the image on the left (resp., on the right) the polarizers are oriented so as to visualize stress along the vertical and horizontal directions (resp., along directions at ±45 deg with respect to vertical). The right image was obtained using an exposure time 1000 times larger than that for the left image. Main plot: intensity level along the horizontal line shown in the images. The intensity levels have been corrected for the difference in exposure time.

Figure 4 .

 4 Figure 4. Inset of a): elastic stress as a function of ϕ, for gels with ϕ 0 = 0.08 and Φ TX as indicated by the labels. Main plot: scaling of σ(ϕ)/A onto a single power law. The dotted line has slope 4.08. b) Dependence of the scaling factor A on the amount of depletant.

Figure 5 -Figure 5

 55 Figure 5. Inset: asymptotic concentration profiles for all gels of both batches. Main plot: the same data collapse onto a straight line when using reduced variables, as explained in the text. Data for gels of batch B1 at ϕ 0 = 0.08 (resp., Φ TX = 0.12) are labeled by Φ TX (resp., ϕ 0 ). For the gel of batch B1, ϕ 0 = 0.12, φ TX = 0.12. The line is the poroelastic model.

Figure 6 .

 6 Figure6. a): time evolution of the total height for a gel of batch B1 with ϕ = 0.12, φ TX = 0.12. The cell section is 3 × 3 mm 2 (5 × 5 mm 2 ) for the solid circles (open triangles), h 0 = 22.7 mm. b): initial decay of h during the collapse of gels of both batches (same symbols as in c)): in all cases, a linear behavior is observed. c) semilogarithmic plot of the time varying part of h normalized by h 0 , during the compaction regime. The line is a fit of the poroelastic model to the data for the gel of batch B1.

1 )Figure 7 .

 17 Figure7. a) sedimentation velocity vs height at various times, ranging from t w = 30h to t w = 167h from top to bottom, for a B1 gel with ϕ = 0.12, Φ TX = 0.12. The line is a linear fit to v(z, t w = 30h) up to z = 7 mm. b): strain measured over a height z, ε = |v|/z, for the same data as in a). c): global strain | ḣ|/h (dotted line), z-averaged strain ε (open circles) and εfit as defined in the text, for the same gel as in a) and b). The solid lines are | ḣ|/h for the three gels of batch B2 shown in Fig.6, for which Φ TX increases from left to right.

  m , with m = 7. The remarkable success of the poroelastic model is demonstrated by the fact that, having determined K(ϕ) and κ(ϕ) from fits of ϕ(z, t → ∞) and h(t), respectively,

											10	-5
			0.12
											10	-6
	|v| (mm/h)	0.04 0.08	0	2	4	6	8	b)	10	-7
			0.00
				0		2		4			6	8	10
									z (mm)
			10	-5							2%, B2
											4%, B2
											8%, B2
	-1 . .	) , |h|/h (s	10 10	-7 -6							. 12%, B1 . , 12%, B1 fit , 12%, B1
											c)
			10	-8
				0			48		96		144	192
									t (h)

Acknowledgments

We thank L. Berthier for many useful discussions and Solvay-Solexis for having provided us the Hyflon T M MFA particle batch. Financial support from Région Languedoc Roussillon, CNES, ANR "Dynhet", the Italian Ministry of Education and Research (MIUR) (PRIN 2008) and ASI is gratefully acknowledged.