Florent Benaych-Georges

CYCLES OF FREE WORDS IN SEVERAL INDEPENDENT RANDOM PERMUTATIONS WITH RESTRICTED CYCLE LENGTHS

Keywords: Mathematics Subject Classification. 20B30, 60B15, 20P05, 60C05 Random permutation, A-permutations, free group. 1

Cycles of free words in several independent random permutations with restricted cycle lengths

Florent Benaych-Georges

1. Introduction 1.1. General introduction. It is well known [START_REF] Arratia | Simon Logarithmic combinatorial structures: a probabilistic approach EMS Monographs in Mathematics[END_REF] that if σ n is a uniformly distributed random permutation of {1, . . . , n} and for all l ≥ 1, one denotes the number of cycles of σ n with length l by N l (σ n ), then for all k ≥ 1, the joint distribution of (N 1 (σ n ), . . . , N k (σ n )) converges in distribution, as n goes to infinity, to Poisson(1/1) ⊗ • • • ⊗ Poisson(1/k). The law of "large cycles" can be recovered using the Poisson-Dirichlet distribution, but in this paper, we are only going to deal with "small cycles", i.e. cycles with a size which does not vary with n.

In [START_REF] Nica | On the number of cycles of a given length of a free word in several random permutations[END_REF], Nica was the first to consider the case where σ n is a free word in several independent random permutations. For a fixed k ≥ 1 and a fixed free word w in the letters g 1 , g -1 1 , . . . , g k , g -1 k , he introduced, for all n, a random permutation σ n of {1, . . . , n} defined in the following way: σ n is the random permutation obtained by replacing each letter g i in w by s i (n), where s 1 (n), . . . , s k (n) are independent random permutations uniformly distributed on the n-th symmetric group. He proved that under the hypothesis that w is not a power of another word, for all positive integer l, N l (σ n ) converges in distribution, as n goes to infinity, to a Poisson distribution with mean 1/l. His result was reproved recently by Linial and Puder in [START_REF] Linial | Word maps and spectra of random graph lifts[END_REF], where it appeared that free words in random permutations are relevant to analyze spectrums of n-lifts of graphs. None of these papers considered the joint distribution of the N l (σ n )'s. Independently, in [Y07] and in [START_REF] Benaych-Georges | Florent Cycles of random permutations with restricted cycle lengths[END_REF], the authors considered random permutations whose distribution is not uniform on the whole symmetric group, but on the set of permutations of {1, . . . , n} which have all their cycle lengths in a fixed set A of positive integers. This kind of random permutation has been the subject of study by a number of authors for more than thirty years (for a review of the literature in this area, see [Y05]). It was proved [START_REF] Benaych-Georges | Florent Cycles of random permutations with restricted cycle lengths[END_REF] that if A is finite with greatest element d, then as n goes to infinity, such a random permutation tends to get not far away from having d: the cardinality of the subset of {1, . . . , n} covered by the supports of cycles with length d in such a random permutation is asymptotic to n. It was also proved [START_REF] Yakymiv | Random A-Permutations: Convergence to a Poisson Process[END_REF][START_REF] Benaych-Georges | Florent Cycles of random permutations with restricted cycle lengths[END_REF] that if A is infinite, then the order of such a random permutation in the symmetric group goes to infinity as n does.

In the present paper, we shall somehow mix both of the previously presented problems: we shall fix k ≥ 1, a free word w in the letters g 1 , g -1 1 , . . . , g k , g -1 k , and a list A 1 , . . . , A k of sets of positive integers satisfying a technical assumption:

(1) ∀i, A i is finite or satisfies

j≥1,j / ∈A i 1 j < ∞.
Then for all n such that it is possible, we shall introduce a k-tuple s 1 (n), . . . , s k (n) of independent random permutations such that for all i, s i (n) is uniformly distributed on the set of permutations of {1, . . . , n} having all of their cycle lengths in A i and define σ n to be the random permutation obtained by replacing each letter g i in w by s i (n).

The starting point of this study was the relation between random permutations and asymptotic first and second order freeness. The asymptotic freeness of random matrices is a notion due to Voiculescu based upon the non-commutative distribution of the matrices (which is, roughly, defined by the (random) algebra generated by the matrices, up to a global conjugation by a unitary matrix). One mights find several introductions to this theory in [VDN91, HP00, NS06, AGZ09]. A complementary theory, the theory of second order freeness, has been developped these last five years about Gaussian fluctuations of the non-commutative distribution of asymptotically free random matrices around its limit (see [START_REF] Mingo | Annular noncrossing permutations and partitions, and second-order asymptotics for random matrices[END_REF][START_REF] Mingo | Second order freeness and fluctuations of random matrices. I. Gaussian and Wishart matrices and cyclic Fock spaces[END_REF][START_REF] Mingo | Second order freeness and fluctuations of random matrices. II. Unitary random matrices[END_REF][START_REF] Collins | Second order freeness and fluctuations of random matrices. III. Higher order freeness and free cumulants[END_REF]). In [START_REF] Nica | Asymptotically free families of random unitaries in symmetric groups[END_REF][START_REF] Neagu | Asymptotic freeness of random permutation matrices with restricted cycles lengths[END_REF] the authors proved that random matrices associated with uniform random permutations (with, possibly, restricted cycle length) are asymptotically free, i.e. that, as far as their joint noncommutative distribution is concerned, they behave like large Haar-distributed unitary matrices. Concretely, it means that the number of fixed points any non-empty word in such random permutations is o(n) (the fact that this is true for any non-empty word is of importance here). The following step, in the study of this issue, was to consider the asymptotic distribution of the number of fixed points of free words in random permutations (with, possibly, restricted cycle length). In this paper, we extend the investigation to the number of cycles of any fixed length, and prove that for several models (depending on the way we restrict the cycle length), the asymptotic distribution is Poisson.

A more detailed review of our results is given below. 1.2. Link with a quotient of the free group generated by g 1 , . . . , g k . Since, as explained above, for i such that A i is finite, s i (n) is not far away from having order d i := sup A i , it is natural to expect that for large values of n, the distribution of σ n will depend firstly on the word obtained from w by removing all sequences of the type g ±d i i for i such that A i is finite. This is what has led us to introduce the group

F k /[g d 1 1 , . . . , g d k k
] generated by free elements g 1 , . . . , g k and quotiented by the relations g

d i i = 1 for i ∈ [k]
, with d i = sup A i (when d i = +∞, the relation

g d i i = 1 is not included).
Our more general results, respectively Theorems 3.6 and 3.4, are the followings:

-If the element of F k /[g d 1 1 , . . . , g d k k ] represented by w has finite order d ≥ 1, then, as n tends to infinity, N d (σ n )/n converges to 1/d and for all l = d, N l (σ n )/n converges to 0. This means that σ n is not far away from having order d: the cardinality of the subset of {1, . . . , n} covered by the supports of the cycles with length d in such a random permutation is asymptotic to n.

-If the element of

F k /[g d 1 1 , . . . , g d k k
] represented by w has infinite order, then two cases can occur:

(i) There is i ∈ [k] such that A i is infinite and α a nonzero integer such that w represents, up to conjugation, the same element, in

F k /[g d 1 1 , . . . , g d k k ], as the word g α i : then for all l ≥ 1 such that l|α| ∈ A i , lim inf n→∞ (E(N l (σ n ))) ≥ 1/l. (ii) The element of F k /[g d 1 1 , . . . , g d k k
] represented by w is not conjugate to an element represented by a word of the type g α i , with i ∈ [k], α an integer: then for all l ≥ 1, lim inf

n→∞ (E(N l (σ n ))) ≥ 1/l.
The result (ii) means that the cycles of the letters of w are going to mix sufficiently well to give rise to cycles of most lengths, at least as much as in a uniform random permutation, even when the letters of w have very restricted cycle lengths. 1.3. Weak limit of the distributions of the N l (σ n )'s. Then, we are going to prove more precise results: under certain hypotheses on w, for all l ≥ 1, the joint distribution of the random vector (N 1 (σ n ), . . . , N l (σ n ))

converges weakly, as n goes to infinity, to

Poisson(1/1) ⊗ Poisson(1/2) ⊗ • • • ⊗ Poisson(1/l),
just as if the distribution of σ n would have been uniform on S n . When all A i 's are infinite (Theorem 3.7), our hypotheses are that w is neither a single letter nor a power of another word. If some of the A i 's are finite, we prove this result for w = g 1 • • • g k (Theorem 3.8), with the exception of the case k = 2 and A 1 ∪ A 2 ⊂ {1, 2} (i.e. of the product of two random involutions), where we prove that the N l (σ n )'s are still asymptotically independent, but that their asymptotic distributions are slightly different (Theorem 3.12).

These results extend on the one hand a result of Nica (reproved by Linial and Puder in [START_REF] Linial | Word maps and spectra of random graph lifts[END_REF]), who proved in [START_REF] Nica | On the number of cycles of a given length of a free word in several random permutations[END_REF] that in the case where all A i 's are equal to the set of all positive integer and where w is not a power of another word, for all l ≥ 1, the distribution of N l (σ n ) converges weakly to Poisson(1/l) (without considering the joint distribution), and on the other hand a result of Neagu, who proved in [START_REF] Neagu | Asymptotic freeness of random permutation matrices with restricted cycles lengths[END_REF] that the number of fixed points of σ n is o(n).

Here, we shall mention that much of the methods we use in this paper are inspired by the ones introduced in [START_REF] Nica | On the number of cycles of a given length of a free word in several random permutations[END_REF][START_REF] Neagu | Asymptotic freeness of random permutation matrices with restricted cycles lengths[END_REF], and that we use many of their results.

1.4. Comments on these results and open questions. a) In this paper, only small cycles (i.e. cycles which size does not depend on n) are considered by our investigations. It would be interesting to know if it is possible to prove a limit theorem for the whole random partition of {1, . . . , n} defined by the cycles of σ n . It is natural to expect a Poisson-Dirichlet distribution [START_REF] Pitman | Combinatorial stochastic processes[END_REF][START_REF] Arratia | Simon Logarithmic combinatorial structures: a probabilistic approach EMS Monographs in Mathematics[END_REF]. b) Another interesting question arising from the similarity between σ n and a uniform random permutation on S n is the following: do we have a characterization of the words w such that for n large enough, σ n is uniformly distributed ? 1.5. Notation. In this text, for n an integer, we shall denote by [n] the set {1, . . . , n} and by S n the group of permutations of [n]. For A a set of positive integers, S n (A) denotes the set of permutations of [n] whose cycles have length in A. For σ ∈ S n and l ≥ 1, we shall denote by N l (σ) the number of cycles of length l in the decomposition of σ as a product of cycles with disjoint supports. For λ > 0, Poisson(λ) will denote the Poisson distribution with parameter λ.

Combinatorial preliminaries to the study of words in random permutations

2.1. Words and groups generated by relations.

2.1.1. Words. Let, for k ≥ 1, M k be the set of words in the letters g 1 , g -1 1 , . . . , g k , g -1 k , i.e. the set of sequences

g α 1 i 1 • • • g αn in , with n ≥ 0, i 1 , . . . , i n ∈ [k], α 1 , . . . , α n = ±1.
A word w ∈ M k is said to be reduced if in its writing, no letter is followed by its inverse. It is said to be cyclically reduced if moreover, the first and the last letters are not the inverses of each other.

A cyclically reduced word is said to be primitive if it is not the concatenation of d ≥ 2 times the same word.

For w = g α 1 i 1 • • • g α |w| i |w| ∈ M k and s = (s 1 , . . . , s k ) a k-tuple of elements of a group, w(s) denotes s α 1 i 1 • • • s α |w| i |w| .
2.1.2. The quotient of the free group with k generators by the relations g d 1 1 = 1, . . . , g d k k = 1. Let F k be the free group generated by g 1 , . . . , g k . This is the set of reduced words of M k endowed with the operation of concatenation-reduction via the relations

g i g -1 i = 1, g -1 i g i = 1, i ∈ [k].
For w, w 0 ∈ M k with w 0 reduced, w is said to represent or to be a writing of the element w 0 of F k if one can reduce w to w 0 via the previous relations. For example, g 1 g 3 g -1

3 g 1 is a writing of g 2 1 . Consider d 1 , . . . , d k ∈ {2, 3, 4, . . .} ∪ {∞}. Let F k /[g d 1 1 , . . . , g d k k
] be the group F k quotiented by its normal subgroup generated by the set {g

d i i ; i ∈ [k], d i < ∞}. A word w ∈ M k is said to represent or to be a writing of an element C of F k /[g d 1 1 , . . . , g d k k ] if it is a writing of an element of C (seen as a subset of F k ).
Theorem 1.4 of Section 1.4 of [START_REF] Magnus | Combinatorial group theory[END_REF] states the following facts.

Theorem 2.1. (a) Any element of F k /[g d 1 1 , . . . , g d k k ] has a writing of the type g α 1 i 1 • • • g αn in with n ≥ 1, i 1 = i 2 = • • • = i n ∈ [k], α 1 , . . . , α n integers such that 0 < |α 1 | < d i 1 ,. . . , 0 < |α n | < d in ,
and this writing is unique up to replacements of the type

g α j i j →    g d i j +α j i j if α j < 0 and d i j < ∞, g -d i j +α j i j if α j > 0 and d i j < ∞, with j ∈ [n].

(b) In any conjugacy class of the group

F k /[g d 1 1 , . . . , g d k k ],
there is an element represented by a word of the previous type such that moreover, i n = i 1 , and such a word is unique up to replacements of the previous type and to transformations of the type g α

1 i 1 • • • g αn in → g αn in g α 1 i 1 • • • g α n-1 i n-1 .
Let us define the (d 1 . . . , d k )-cyclically reduced words to be the words of the type

g α 1 i 1 • • • g αn in with n ≥ 0, i 1 = i 2 = • • • = i n = i 1 ∈ [k], α 1 , . . . , α n integers such that 0 < |α 1 | < d i 1 ,. . . , 0 < |α n | < d in .
Consider a cyclically reduced word w ∈ M k . We shall call a partial (d 1 , . . . , d k )-cyclic reduction of w a word which can be obtained from w in a finite number of steps of the following types:

(a) uv → vu, with u, v ∈ M k , (b) ug αd i i u -1 v → v, with i ∈ [k]
, α a nonzero integer, u a nonempty word and v ∈ M k a cyclically reduced word, (c)

g αd i i v → v, with i ∈ [k]
, α a nonzero integer, and v a word which can be written v = g β i v ′ , with β an integer, |β| < d i and v ′ a word whose first and last letters do not belong to

{g i , g -1 i }. A partial (d 1 , . . . , d k )-cyclic reduction of w which is (d 1 . . . , d k )-cyclically reduced is called a (d 1 . . . , d k )-cyclic reduction of w.
In general, there is more than one (d 1 . . . , d k )-cyclic reduction of w, but if there is only one, we call it the (d 1 . . . , d k )-cyclic reduction of w.

For example, for d 1 = 4, d 2 = 5, the following words are partial (d

1 , . . . , d k )-cyclic reductions of w = g 2 2 g 1 g 6 2 g 3 g -4 1 g -1 3 g -1 1 g 3 2 : g 5 2 g 1 g 6 2 g 3 g -4 1 g -1 3 g -1 1 , g 6 2 g 3 g -4 1 g -1 3 , g 2 g 3 g -4 1 g -1 3 , g 3 g -4 1 g -1 3 g 2 , g 2 . The last one is a (d 1 . . . , d k )-cyclic reduction of w.
2.2. Admissible graphs and partitions. Colored graphs associated to words and permutations.

Basic graph theoretic definitions.

In this text, we shall consider oriented edge-colored graphs with color set [k]. These are families G = (V ; E 1 , . . . , E k ), where V is a finite set (its elements are called the vertices of G) and for all r ∈ [k], E r is a subset of V 2 (the set of edges with color r of G). For e = (u, v) edge of G, u (resp. v) is called the beginning vertex of e (resp. the ending vertex of e) and is denoted by Beg(e) (resp. End(e)). e is often denoted by u → v. Note that the E r 's are not supposed to be pairwise disjoint. Throughout this paper, the color set of the edges will always be [k], so it will often be implicit.

For r ∈ [k], G = (V ; E 1 , . . . , E k ) is said to be monochromatic with color r if for all i = r, E i = ∅. If moreover, V = {v 1 , . . . , v l } and E r = {v 1 → v 2 → • • • → v l } (resp. E r = {v 1 → v 2 → • • • → v l → v 1 }),
with l ≥ 1 and v 1 , . . . , v l pairwise distinct, G is said to be a monochromatic directed path (resp. monochromatic directed cycle) with length l -1 (resp. l).

A subgraph of a graph (V ; E 1 , . . . , E k ) is a graph of the type (W ;

F 1 , . . . , F k ), with W ⊂ V, F 1 ⊂ E 1 , . . . , F k ⊂ E k .
A monochromatic directed cycle (resp. a monochromatic directed path) of an oriented edgecolored graph is a subgraph which is a monochromatic directed cycle (resp. a monochromatic directed path).

A graph (V ; E 1 , . . . , E k ) is said to be the disjoint union of the graphs (V

′ ; E ′ 1 , . . . , E ′ k ) and (V ′′ ; E ′′ 1 , . . . , E ′′ k ) if V = V ′ ∪ V ′′ , E 1 = E ′ 1 ∪ E ′′ 1 , . . . , E k = E ′ k ∪ E ′′
k and all of these unions are disjoint.

An isomorphism between two oriented edge-colored graphs (

V ; E 1 , . . . , E k ), (V ′ ; E ′ 1 , . . . , E ′ k ) is a bijection ϕ : V → V ′ such that for all u, v ∈ V , for all r ∈ [k], one has u → v ∈ E r ⇐⇒ ϕ(u) → ϕ(v) ∈ E ′ r .
2.2.2. Admissible graphs and partitions. Recall that a partition ∆ of a set X is a set of pairwise disjoint, nonempty subsets of X (called the classes of ∆) whose union is X. In this case, for x, y ∈ X, "x = y mod ∆" and "∆ links x and y" both mean that x, y are in the same class of ∆. Since ∆ is a set, |∆| denotes its cardinality.

For any function γ defined on a set X, we shall denote by Part(γ) the partition of X by the level sets of γ.

Let G be an oriented edge-colored graph with color set [k] and with vertices set V .

G is said to be admissible if two different edges with the same color cannot have the same beginning or the same ending vertex.

We are going to use the notion of quotient graph, that we define now. Let us define, for ∆ a partition of V , G/∆ to be the oriented edge-colored graph whose vertices are the classes of ∆ and such that for all C, C ′ classes of ∆, for all r ∈ [k], there is an edge with color r from C to C ′ in G/∆ when there is an edge with color r in G from a vertex of C to a vertex of

C ′ . Remark 2.2. Note that clearly, if ∆ 1 is a partition of V and ∆ 2 is a partition of ∆ 1 , then the oriented edge-colored graph (G/∆ 1 )/∆ 2 is isomorphic to G/Γ,
where Γ is the partition of V such that for all x, y ∈ V , x = y mod Γ if and only if the classes of x and y in ∆ 1 are in the same class of ∆ 2 .

A partition ∆ of V is said to be an admissible partition of G when the graph G/∆ is admissible, i.e. when for all pair (e, f ) of edges of G with the same color, Beg(e) = Beg(f ) mod ∆ ⇐⇒ End(e) = End(f ) mod ∆.

In the following proposition, whose proof is obvious, we define the operator Adm on the set of oriented edge-colored graphs.

Proposition 2.3. Let G be an oriented edge-colored graph. Let ∆ be the partition of the vertex set of G which links two vertices r, s if and only if there are n ≥ 0,

t 0 = r, t 1 , . . . , t n = s some vertices of G, i 1 , . . . , i n ∈ [k], and ε 1 , . . . , ε n ∈ {±1} such that: -the reduction of the word g ε 1 i 1 • • • g εn in is the empty word, -for all l ∈ [n], the i l -colored edge t l-1 → t l (resp. t l-1 ← t l ) belongs to G if ε l = 1 (resp. if ε l = -1).
Then ∆ is the minimal partition P (with respect to the refinement order) such that G/P is admissible.

With the notations of the previous proposition, the partition ∆ will be called the minimal admissible partition of G and G/∆ will be denoted by Adm(G).

Remark 2.4. Let H be an oriented edge-colored graph with vertex set W and let G be a subgraph of H with vertex set V . Then Adm(H) can be obtained (up to an isomorphism) from Adm(G), by adding to Adm(G) the vertices and edges of H which are not in G, and then quotienting the obtained graph by its minimal admissible partition. More specifically, if, for each vertex v of G, one denotes by v the class of v in the minimal admissible partition of G, then Adm(H) can be identified, via an isomorphism, with Adm(H ′ ), where H ′ is the oriented edge-colored graph whose vertex set is the union of the vertex set of Adm(G) with the set W \V and whose set of edges of color i,

for each i ∈ [k], is the union of the set of edges of color i of Adm(G) with the set {w → w ′ ; w, w ′ ∈ W \V, w → w ′ i-colored edge of H} ∪{v → w ; v ∈ V, w ∈ W \V, v → w i-colored edge of H} ∪{w → v ; v ∈ V, w ∈ W \V, w → v i-colored edge of H}. Lemma 2.5. Consider an oriented edge-colored graph G = (V ; E 1 , . . . , E k ), r, s, t ∈ V , i ∈ [k] such that s → t ∈ E i . Then for H the oriented edge-colored graph obtained from G by adding, if it is not already in G, the i-colored edge r → t (resp. s → r), Adm(H) is isomorphic to Adm(G/{r = s}) (resp. Adm(G/{r = t}))
, where for u, v ∈ V , {u = v} denotes the partition of V whose classes are all singletons, except one: {u, v}.

Proof. The proof is immediate with Remark 2.2 and the following observation: for Γ an admissible partition of G, if, for any v ∈ V , one denotes by v the class of v in Γ, then

r = s (resp. r = t) ⇐⇒ r → t (resp. s → r) is an i-colored edge of G/Γ. 2.2.3. The graph G(σ, w). Fix k, p ≥ 1, σ ∈ S p and w = g α 1 i 1 • • • g α |w| i |w| ∈ M k a
α l = 1 ⇒ (m, l) → (m, l + 1) if l = |w|, (σ -1 (m), 1) if l = |w|, is an i l -colored edge of G(σ, w), α l = -1 ⇒ (m, l) ← (m, l + 1) if l = |w|, (σ -1 (m), 1) if l = |w|, is an i l -colored edge of G(σ, w).
In the case where p = 1 and σ = Id, we shall denote G(σ, w) by G(w) and identify its vertex set with [|w|] by (1, l) ≃ l for all l ∈ [|w|]. We will also use the convention that if w is the empty word, then G(w) is the graph having 1 for only vertex and no edge.

For example, for w = g 1 g 2 g 3 g 4 g -1 2 g 1 g -1 2 g 5 , G(w) is the graph 2 2 G G 3 3 b b b 0 0 b b b 1 1 Ð Ð Ð d d Ð Ð Ð 4 4 8 2 b b b 0 0 b b b 5 y y 5 7 6 1 o o 2 Ð Ð Ð d d Ð Ð Ð
where the colors of the edges appear on them. We shall give examples of graphs of the type G(σ, w) after the following lemma, which expresses G(σ, w) as a disjoint union of graphs isomorphic to G(w α ), with α ≥ 1.

Lemma 2.6. G(σ, w) is the disjoint union of N 1 (σ) graphs isomorphic to G(w 1 ), N 2 (σ) graphs isomorphic to G(w 2 ), . . . , N p (σ) graphs isomorphic to G(w p ).

i ∈ [k], E i (c) = E i ∩ (V (c) 2 ).
Hence it suffices to prove that for any d

∈ [p], for any cycle c = (m 1 m 2 • • • m d ) of σ of length d, there is an isomorphism between (V (c); E 1 (c), . . . , E k (c)) and G(w d ). The function which maps (m i , l) ∈ {m 1 , m 2 , . . . , m d }×[|w|] to (d -i)|w| + l ∈ [d|w|] is such an isomorphism. For example, when w = g 1 g 2 g -1 1 g -1 2 , p = 3 and σ is the cycle (123), G(σ, w) is the graph (1, 1) 1 G G 2 (1, 2) 2 G G (1, 3) (1, 4) 1 o o (3, 1) 2 o o 1 G G (3, 2) 2 (2, 4) 1 G G (2, 3) (2, 2) 2 o o
(2, 1)

1 o o 2 G G (3, 4) 1 G G (3, 3)
where the colors of the edges appear on them.

When w is still g 1 g 2 g -1 1 g -1 2 , but p = 5 and σ is the product of disjoint cycles (123)(45), G(σ, w) is the disjoint union of the previous graph and of If an oriented edge-colored graph G is admissible, it is easy to see that for all i ∈ [k], the graph obtained from G by erasing all edges whose color is not i is a disjoint union of directed paths and directed cycles. If for each i ∈ [k], all these directed cycles have length in A i (resp. length equal to d i ) and all these directed paths have length < d i , G will be said to be (A 1 , . . . , A k )-admissible (resp. (d 1 , . . . , d k )-strongly admissible). A partition ∆ of the vertex set of an oriented edge-colored graph G will be said to be an

(4, 1) 1 G G 2 (4, 2) 2 G G (4, 3) (4, 4) 1 o o (5, 4) 1 G G (5, 3) (5, 2) 2 o o (5,
(A 1 , . . . , A k )-admissible parti- tion (resp. a (d 1 , . . . , d k )-strongly admissible partition) if G/∆ is (A 1 , . . . , A k )-admissible (resp. (d 1 , . . . , d k )-strongly admissible).
We define the Neagu characteristic of an admissible oriented edge-colored graph G to be

χ(G) = |{vertices of G}| - k r=1 |{edges of G with color r}| + k r=1 L directed cycle of G with color r length of L d r ,
with the convention l/∞ = 0.

Let G = (V ; E 1 , . . . , E k ) be an admissible oriented edge-colored graph. A direct extension of G is a graph G ′ of one of the following types:

-G ′ = (V ∪ {r}; E 1 , . . . , E i-1 , E i ∪ {s → r}, E i+1 , . . . , E k ), with r / ∈ V , i ∈ [k]
, and s ∈ V such that no edge of G with color i has s for beginning vertex, -

G ′ = (V ∪ {r}; E 1 , . . . , E i-1 , E i ∪ {r → s}, E i+1 , . . . , E k ), with r / ∈ V , i ∈ [k]
, and s ∈ V such that no edge of G with color i has s for ending vertex, -

G ′ = (V ; E 1 , . . . , E i-1 , E i ∪ {r → s}, E i+1 , . . . , E k ), with i ∈ [k] such that d i < ∞,
r, s ∈ V such that no edge of G with color i has r for beginning vertex, no edge of G with color i has s for ending vertex, and there exists t 1 , . . . , t

d i ∈ V pairwise distinct vertices such that t 1 = s, t d i = r and t 1 → t 2 , t 2 → t 3 , . . . , t d i -1 → t d i ∈ E i .
In other words, a direct extension of G is an admissible oriented edge-colored graph which can be obtained from G either by adding a vertex and connecting this vertex to a vertex of G by an edge of any sense and color, or by adding an edge which closes a monochromatic directed cycle with color i ∈ [k] of length d i . In the first case, the direct extension G ⊂ G ′ is said to be vertex-adding, whereas in the second one, it is said to be cycle-closing.

For example, for d 3 = 4, the graphs G, G ′ , G ′′ , G ′′′ below (where the colors of the edges appear on them) are such that G ⊂ G ′ ⊂ G ′′ ⊂ G ′′′ are direct extensions, the first ones being vertex-adding, whereas the last one is cycle-closing.

G= 1 1 G G 2 2 2 G G 3 3 6 5 1 o o 2 G G 4 , G'= 1 1 G G 2 2 2 G G 3 3 7 3 o o 6 5 1 o o 2 G G 4 G"= 1 1 G G 2 2 2 G G 3 3 7 3 o o 6 5 1 o o 2 G G 4 8 3 y y , G"= 1 1 G G 2 2 2 G G 3 3 7 3 o o 6 5 1 o o 2 G G 4 3 G G 8 3 y y
An extension of G is an oriented edge-colored graph G ′ such that there is n ≥ 0, G 0 = G, . . . , G n = G ′ such that for all i = 1, . . . , n, G i is a direct extension of G i-1 . Such an integer n is unique (it is the number of edges of G ′ minus the number of edges of G) and will be called the degree of the extension.

In other words, an extension of G is an admissible oriented edge-colored graph which can be obtained from G by successively adding vertices and/or edges without adding either any connected component or any monochromatic directed cycle whose length is not d i when its color is i.

Remark 2.7. It can easily be proved, using admissibility, that a vertex or an edge of an extension of G which is not a vertex of G cannot belong to a monochromatic directed cycle with color i ∈ [k]

whose length is not equal to d i .

Lemma 2.8. The Neagu characteristic is preserved by extension.

Proof. It suffices to prove that the Neagu characteristic is preserved by direct extension. In the case of a vertex-adding direct extension, it is obvious. In the case where the direct extension is monochromatic directed cycle-closing, it suffices to notice that the admissibility implies that exactly one monochromatic directed cycle is closed.

The following lemma is the key result of this section. Recall that for u, v in a set V , {u = v} denotes the partition of V whose classes are all singletons, except one: {u, v}.

Lemma 2.9. Consider an oriented edge-colored graph G which is an extension of the graph G(w), with w ∈ M k a cyclically reduced word such that the order, in

F k /[g d 1 1 , . . . , g d k k ],
of the element represented by w is either infinite or equal to one. Suppose that for a certain i ∈

[k] such that d i < ∞, G contains an i-colored directed path t 0 → t 1 → • • • → t d i with length d i .
Then there is a partial (d 1 , . . . , d k )-reduction w of w such that Adm(G/{t 0 = t d i }) is isomorphic to an extension of G( w).

Remark 2.10. Note that by definition of the operator Adm and by Remark 2.2, with the notations of the previous lemma, there is a partition ∆ of the vertex set of G such that Adm(G/{t 0 = t d i }) can be identified with G/∆. Clearly, by definition of {t 0 = t d i } and of Adm, if two vertices of r, s of G are in the same class of ∆, then there are n ≥ 0, x 0 = r, x 1 , . . . , x n = s some vertices of G, i 1 , . . . , i n ∈ [k], and ε 1 , . . . , ε n ∈ {±1} such that: -the (d 1 , . . . , d k )-reduction of the word

g ε 1 i 1 • • • g εn in is the empty word, -for all l ∈ [n], the i l -colored edge x l-1 → x l (resp. x l-1 ← x l ) belongs to G if ε l = 1 (resp. if ε l = -1).
Proof of the lemma. The lemma is a consequence of the following proposition, that we shall prove by induction on (|w|, n) (for the lexical order ): for all w ∈ M k a cyclically reduced word such that the order, in

F k /[g d 1 1 , . . . , g d k k ],
of the element represented by w is either infinite or equal to one, for all extensions G of degree n of G(w), if for a certain i ∈

[k] such that d i < ∞, G contains an i-colored directed path t 0 → t 1 → • • • → t d i with length d i , then Adm(G/{t 0 = t d i })
is either isomorphic to an extension of G(w) with degree ≤ n or isomorphic to an extension of G( w) for a certain strict partial (d 1 , . . . , d k )-reduction w of w.

For |w| = 0 and n = 0, then G = G(w) is a single point, thus there is nothing to prove. Now, let us consider a cyclically reduced word w such that the order, in F k /[g d 1 1 , . . . , g d k k ], of the element represented by w is either infinite or equal to one, and an extension G of G(w) with degree n such that (0, 0) ≺ (|w|, n), and let us suppose the result to be proved for any word w ′ and any extension G(w

′ ) ⊂ G ′ with degree n ′ such that (|w ′ |, n ′ ) ≺ (|w|, n). Suppose that G contains an i-colored directed path t 0 → t 1 → • • • → t d i with length d i .
• If n = 0, then G = G(w), and up to a cyclic permutation of the letters of w (which, up to an isomorphism, does not change G(w)), one can suppose that one of the following cases occurs:

Case 1: w = ug αd i i u -1 w, with α a nonzero integer, u nonempty word and w ∈ M k a cyclically reduced word, and there is an integer j,

1 + |u| ≤ j ≤ 1 + |u| + (|α| -1)d i , such that t 0 = j, t 1 = j + 1, . . . , t d i = j + d i if α > 0, t 0 = j + d i , t 1 = j + d i -1, . . . , t d i = j if α < 0.
Case 2: w = g αd i i w, with α a nonzero integer and w a word which can be written w = g β i v, with β an integer, |β| < d i and v a nonempty (except possibly if β = 0) word whose first and last letters do not belong to {g i , g -1 i }, and there is an integer j,

1 ≤ j ≤ 1 + (|α| -1)d i + |β|, such that t 0 = j, t 1 = j + 1, . . . , t d i = j + d i if α > 0, t 0 = j + d i , t 1 = j + d i -1, . . . , t d i = j if α < 0.
Note that in both cases, w is a strict partial (d 1 , . . . , d k )-reduction of w. We are going to prove that Adm(G(w)/{t 0 = t d i }) is isomorphic to an extension of G( w).

In Case 1, let us write

u = g ε 1 i 1 • • • g ε |u| i |u| , with i 1 , . . . , i |u| ∈ [k], ε 1 , . . . , ε |u| ∈ {±1}. Let us define the sequence of direct extensions G( w) = G 0 ⊂ G 1 ⊂ • • • ⊂ G |u|+d i in
the following way (we consider a copy 1 ′ , 2 ′ , . . . of the set of positive integers):

1) First add the vertex 1 ′ and the i 1 -colored edge 1 → 1 ′ or 1 ← 1 ′ according to whether ε 1 = 1 or -1. This is a direct extension, because since w is cyclically reduced, we know that if the last (resp. first) letter of w is g ε i 1 with ε ∈ {±1}, then ε = ε 1 (resp. -ε 1 ). 2) Then add the vertex 2 ′ and the i 2 -colored edge 1 ′ → 2 ′ or 1 ′ ← 2 ′ according to whether ε 2 = 1 or -1. This is also a direct extension, because since w is cyclically reduced, we know that if

i 1 = i 2 , then ε 1 = ε 2 . . . .
+ d i -2) ′ → (|u| + d i -1) ′ . |u| + d i ) Then add the i-colored edge (|u| + d i -1) ′ → |u| ′
. This is a direct extension because as explained at the (|u| + 1)th step, i |u| = i.

Claim: the last graph of this sequence, G |u|+d i , is isomorphic to Adm(G(w)/{t 0 = t d i }). To prove this, let us first notice that by Remark 2.2, Adm(G/{t 0 = t d i }) is isomorphic to G(w)/P , where P is the partition of the vertex set of G whose classes are singletons, except that: -In the "g αd i i part" of G(w), vertices are linked every d i edges: for all x, y ∈ {|u| + 1, . . . , |u| + |α|d i + 1}, x = y mod P if and only if x = y mod d i . -In the "ug αd i i u -1 part" of G(w), symmetric vertices of "the u and u -1 parts" are linked by P : we have, modulo

P , 1 = 2|u| + |α|d i + 1, 2 = 2|u| + |α|d i , . . . , |u| = |u| + |α|d i + 2.
As an illustration, on Figure 1, we draw the graphs G(w), G(w)/P and G |u|+d i for w = g 4 g 2 g 4 3 g -1 2 g -1 4 g 3 g 1 g 5 g 6 , w = g 3 g 1 g 5 g 6 and d 3 = 4, linking by edges of the type • • the vertices of G(w) which are in the same class of P (but these edges do not belong to G(w)). Now, to be precise, let us give a bijective map ϕ from the vertex set of G |u|+d i to the one of G(w)/P which is an isomorphism of edge-colored oriented graphs. First, recall that the vertex set of The graph G(w)

G |u|+d i is [| w|] ∪ {1 ′ , . . . , (|u| + d i -1) ′ } and that the vertex set of G(w)/P is {{1, 2|u| + |α|d i + 1}, {2, 2|u| + |α|d i }, {3, 2|u| + |α|d i -1}, . . . , {|u|, |u| + |α|d i + 2}}∪ {{|u| + 1 + ld i ; 0 ≤ l ≤ |α|}} ∪ {{|u| + j + ld i ; 0 ≤ l < |α|} ; j = 2, . . . , d i }∪ {{2|u| + |α|d i + 2}, . . . , {2|u| + |α|d i + | w|}}.
The graph G(w)/P The graph G |u|+d i

The bijection ϕ is defined by

∀x ∈ [| w|], ϕ(x) = {1, 2|u| + |α|d i + 1} if x = 1, {2|u| + |α|d i + x} if x > 1, ∀x ∈ [|u| + d i -1], ϕ(x ′ ) =          {x + 1, 2|u| + |α|d i + 1 -x} if x < |u|, {|u| + 1 + ld i ; 0 ≤ l ≤ |α|} if x = |u|, {x + 1 + ld i ; 0 ≤ l < |α|} if x > |u| and α > 0, {2|u| + d i + 1 -x + ld i ; 0 ≤ l < |α|} if x > |u| and α < 0.
In Case 2, let us define the sequence of direct extensions

G(v) = G 0 ⊂ G 1 ⊂ • • • ⊂ G d i -|β|
in the following way (again, we consider a copy 1 ′ , 2 ′ , . . . of the set of positive integers):

1) First add the vertex (|β| + 2) ′ and the i-colored edge |β| + 1 → (|β| + 2) ′ or |β| + 1 ← (|β| + 2) ′ according to whether β ≥ 0 or < 0. This is a direct extension, because v is a nonempty (except possibly if β = 0) word whose first and last letters do not belong to {g i , g -1 i }. 2) Then add the vertex (|β| + 3) ′ and the i-colored edge (|β| + 2) ′ → (|β| + 3) ′ or (|β| + 2) ′ ← (|β| + 3) ′ according to whether β ≥ 0 or < 0. . . .

d i -|β| -1) Then add the vertex d ′ i and the i-colored edge (d i -1) ′ → d ′ i or (d i -1) ′ ← d ′ i according to whether β ≥ 0 or < 0. d i -|β|) Then add the i-colored edge d ′ i → 1 or d ′ i ← 1 according to whether β ≥ 0 or < 0.
As in Case 1, one proves that the last graph of this sequence of direct extensions, namely G d i -|β| , is isomorphic to Adm(G(w)/{t 0 = t d i }) (which, by Remark 2.2, is isomorphic to G(w)/P , where P is the partition of the vertex set of G whose classes are singletons, except that in the "g αd i +β i part" of G, vertices are linked every d i edges). As an illustration, on Figure 2, we draw the graphs G(w), G(w)/P and G d i -|β| , with w = g 5 1 g 2 g 3 g 4 g -1

1 g 4 g -2 2 , w = g 1 g 2 g 3 g 4 g -1 1 g 4 g -2 3 1 G G 4 1 b b b 0 0 b b b 2 1 | 1 1 1 y y linked by P 2 6 2 12 2 7 3 11 8 4 Ð Ð Ð Ð Ð Ð Ð Ð 10 4f f f f f f f f 1 G G 9 4 1 3 1 o o {1, 5} 2 y y y y | | y y y y 1 G G {2, 6} 1 y y 2 h h h 3 3 h h h h 12 2 7 3 11 8
4 y y y y | | y y y y 10 4q q q q q q q q 1 G G 9

4 ′ 1 3 ′ 1 o o 1 2 1 G G 2 1 y y 2 c c c c 1 1 c c c c 8 2 3 3 7 4 4 6 4c c c c c c c c 1 G G 5 The graph G(w)
The graph G(w)/P The graph

G d i -|β|
Figure 2 and d 1 = 4, linking by edges of the type • • the vertices of G(w) which are in the same class of P (but these edges do not belong to G(w)).

• If the degree n of the extension G of G(w) is ≥ 1, let us introduce a sequence G 0 = G(w) ⊂ G 1 ⊂ • • • ⊂ G n = G of direct extensions.
Again, two cases will be to consider.

•• If t 0 , . . . , t d i are not all vertices of G n-1 : Since G n is a direct extension of G n-1 , at most one vertex of G n is not a vertex of G n-1 .
Hence exactly one vertex of G n is not a vertex of G n-1 , the direct extension G n-1 ⊂ G n is vertex-adding and the vertex added is at the extremity of exactly one edge. Thus this vertex is either t 0 or t d i . We suppose that it is t d i : the case where it is t 0 can be treated analogously.

-If no i-colored edge of G n-1 has t 0 for ending vertex, then Adm(G n /{t 0 = t d i }) can simply be identified with the graph obtained from G n-1 by adding the i-colored edge t d i -1 → t 0 : this graph is a cycle-closing direct extension of G n-1 , hence an extension of degree n of G(w), so the result holds. -If t 0 is the ending vertex of a certain i-colored edge t -1 → t 0 of G n-1 , then notice first that by Lemma 2.5, Adm(

G n /{t 0 = t d i }) is isomorphic to Adm(G n-1 /{t -1 = t d i -1 }).
Hence by the induction hypothesis, it suffices to prove that t -1 , . . . , t d i -1 are pairwise distinct: if it wasn't the case, since t 0 , . . . , t d i -1 are pairwise distinct, then we would have t -1 = t l for some l ∈ {0, . . . , d i -1}, but it would imply that t l is the beginning vertex of two distinct i-colored edges of G n (the edges t -1 → t 0 and t l → t l+1 ), which is impossible since G n , as an extension of G(w), is admissible.

•• If t 0 , . . . , t d i are all vertices of G n-1 :

There will be no ambiguity for us to also denote by {t 0 = t d i } the restriction of the partition {t 0 = t d i } to the vertex set of G n-1 . By definition of the operator Adm and by Remark 2.2, there is a partition Γ of the vertex set of G n-1 such that Adm(G n-1 /{t 0 = t d i }) is isomorphic to G n-1 /Γ. Let, for x vertex of G n-1 , x denote the class of x in Γ. We know, by the induction Lemma 2.11. Consider a cyclically reduced word w ∈ M k such that if w admits a (d 1 , . . . , d k )cyclic reduction of the type g α i , with i ∈ [k] and α a nonzero integer, then d i = ∞ and |α| ∈ A i . Consider an oriented edge-colored graph G which is an extension of the graph G(w). Then G admits an (A 1 , . . . , A k )-admissible partition ∆ such that G/∆ is isomorphic to an extension of G(w red ), for a certain (d 1 , . . . , d k )-reduction w red of w and such that if two vertices of r, s of G are in the same class of ∆, then there are n ≥ 0, t 0 = r, t 2 , . . . , t n = s some vertices of G, i 1 , . . . , i n ∈ [k], and ε 1 , . . . , ε n ∈ {±1} such that:

-the (d 1 , . . . , d k )-reduction of the word g ε 1 i 1 • • • g εn in is the empty word, -for all l ∈ [n], the i l -colored edge t l-1 → t l (resp. t l-1 ← t l ) belongs to G if ε l = 1 (resp. if ε l = -1).
The previous lemma allows us to prove the following Theorem, which is the main result this section.

Theorem 2.12. Consider a cyclically reduced word w = g

α 1 i 1 • • • g α |w| i |w| ∈ M k such that if w admits a (d 1 , . . . , d k )-cyclic reduction of the type g α i , with i ∈ [k]
and α a nonzero integer, then d i = ∞ and |α| ∈ A i . Then G(w) admits an (A 1 , . . . , A k )-admissible partition ∆ such that:

(i) χ(G(w)/∆) =
1 if w admits the empty word for (d 1 , . . . , d k )-cyclic reduction, 0 in the other case, (ii) for all r < s ∈ [|w|], r = s mod ∆ implies that one of the words

g αr ir • • • g α s-1 i s-1 , g αs is • • • g α |w| i |w| g α 1 i 1 • • • g α r-1 i r-1
admits the empty word as a (d 1 , . . . , d k )-cyclic reduction.

Proof. Note that by hypothesis, for any (d 1 , . . . , d k )-cyclic reduction w red of w, G(w red ) is an (A 1 , . . . , A k )-admissible graph with Neagu characteristic equal to 1 if the only (d 1 , . . . , d k )-cyclic reduction of w is the empty word, and to 0 in the other case. Hence by Lemma 2.8, for any partition ∆ of the vertex set of G(w), to have (i), it suffices to prove that G(w)/∆ is an extension of G(w red ). Hence this Theorem is an immediate consequence of the previous lemma, applied for G = G(w).

We shall use the following Corollary later. For all l ≥ 1, (1 • • • l) denotes the cyclic permutation of [l] which maps 1 to 2, 2 to 3,. . . , l -1 to l and l to 1. Corollary 2.13. Consider a positive integer l and a cyclically reduced word v ∈ M k . a) Suppose that the order, in

F k /[g d 1 1 , . . . , g d k k ],
of the element represented by v is infinite and that in the case where v admits a (d 1 , . . . , d k )-cyclic reduction of the type g α i , with i ∈ [k] and α an integer, we have l|α|

∈ A i . Then G((1 • • • l), v) admits an (A 1 , . . . , A k )-admissible partition ∆ such that: (i) χ(G((1 • • • l), v)/∆) = 0, (ii) for all m = m ′ ∈ [l], (m, 1) = (m ′ , 1) mod ∆. b) Suppose that the order, in F k /[g d 1 1 , . . . , g d k k ], of the element represented by w is equal to l. Then G((1 • • • l), v) admits an (A 1 , . . . , A k )-admissible partition ∆ such that: (i) χ(G((1 • • • l), v)/∆) = 1, (ii) for all m = m ′ ∈ [l], (m, 1) = (m ′ , 1) mod ∆.
-this partition is admissible and does not link (m, 1) and (m ′ , 1) for m = m ′ , -there is no monochromatic directed cycle in G(σ, w): indeed, by Lemma 2.6, G(σ, w) is a disjoint union of graphs of the type G(w d ) (d ≥ 1), where there is no monochromatic directed cycle since w is primitive and |w| > 1.

The previous theorem, with the fact that for any permutation σ and l, p ≥ 1, we have N l (σ p ) = N lp/h (σ)p/h, where the sum runs over the positive integers h such that h|p and gcd(h, l) = 1, allows us to compute easily the limit distribution of (N 1 (σ n ), . . . , N l (σ n )) whenever w is not a power of a g i .

3.4.

Case where w = g 1 • • • g k . Now, we are not going to make the hypothesis that all A i 's are infinite anymore, but we are going to suppose that w is a particular word:

w = g 1 • • • g k , with k ≥ 2 (the case k = 1 has already been treated in [BG07]). 3.4.1. Case where k > 2 or A 1 ∪ A 2 {1, 2}.
Theorem 3.8. Under this hypothesis, as n goes to infinity, for all l ≥ 1, the law of

(N 1 (σ n ), . . . , N l (σ n )) converges weakly to Poisson(1/1) ⊗ • • • ⊗ Poisson(1/l).
In order to prove the Theorem, we shall need the following lemmas.

Lemma 3.9. Let X be a finite set, let B be a set of subsets of X which have all cardinality 2. Let ∆ be a partition of X such that for all {x, y} ∈ B, x = y mod ∆.

Then |∆| ≤ |X | -|B|.
Proof. Let us define the set Γ of subsets of X by Γ = B ∪ {{z} ; z ∈ X , z / ∈ ∪ {x,y}∈B {x, y}}. By hypothesis, any class of ∆ is a union of elements of Γ, so |∆| ≤ |Γ| = |X | -|B|.

Lemma 3.10. Consider w = g 1 • • • g k , with k ≥ 2, and σ ∈ S p , with p ≥ 1. Let ∆ be an admissible partition of G(σ, w) such that for all i = j ∈ [p], (i, 1) = (j, 1) mod ∆. Then (i) two different edges of G(σ, w) with the same color cannot have their beginning vertices in the same class of ∆, and the same holds for ending vertices, (ii) the following inequalities hold:

(a) if k > 2, then |∆| ≤ pk - k r=1 L directed cycle of G(σ,w)/∆ with color r length of L, (b) if k = 2, then for all r = 1, 2, |∆| ≤ pk - L directed cycle of G(σ,w)/∆ with color r length of L.
Remark 3.11. Note that (i) implies that there is a canonical identification between the set of edges of the graph G(σ, w) and the set of edges of the graph G/∆: if, for all vertex x of G(σ, w), one denotes by x the class of x in ∆, then for all r ∈ [k], the function from the set of r-colored edges of G(σ, w) to the set of r-colored edges of G(σ, w)/∆ which maps any edge x → y to x → y is bijective.

Proof. Note first that since for all i = j ∈ [p], (i, 1) = (j, 1) mod ∆, and by definition of an admissible partition, one has (by an obvious induction on l):

(7) ∀i = j ∈ [p], ∀l ∈ [k], (i, l) = (j, l) mod ∆.
Since two edges of G(σ, w) with the same color have beginning vertices (and ending vertices) with the same second coordinate, it implies (i).

Now, note that, as observed in Remark 3.11, the edges of G(σ, w)/∆ can be identified with the ones of G(σ, w). Let, for r ∈ [k], L[r] be the set of edges of G(σ, w) which, via this identification, belong to an r-colored directed cycle of G(σ, w)/∆ and define L := ∪ k r=1 L[r]. Claim: no edge of G(σ, w)/∆ can belong to more than one monochromatic directed cycle of G(σ, w)/∆. Indeed, if it where the case, there would be r ∈ [k], e, e ′ , e ′′ ∈ L[r] such that e ′ and e ′′ both follow e in r-colored directed cycles of G(σ, w)/∆ and e ′ = e ′′ . Since e ′ and e ′′ follow e in directed cycles of G(σ, w)/∆, we have Beg(e ′ ) = End(e) = Beg(e ′′ ) mod ∆, which implies e ′ = e ′′ by (i). Contradiction.

The first consequences of this claim are that

(8) |L| = k r=1 L directed cycle of G(σ,w)/∆ with color r length of L,
and that for all r = 1, . . . , k, Note that since k ≥ 2, for all edge e of G(σ, w), the color of e is not the same as has the one of the edge whose beginning is the end of e. This allows us to claim that for all e ∈ L, |S(e)| = 2.

For all e ∈ L, since ϕ(e) follows e in G(σ, w)/∆, we have End(e) = Beg(ϕ(e)) mod ∆. So, in order to apply the previous lemma, we have to minor the cardinality of If k > 2: let us prove that S(e) = S(f ) with e = f is impossible. We have End(e) = Beg(ϕ(f )), so the color following the one of e in the cyclic order 1, 2, . . . , k, 1, . . . is the one of ϕ(f ), i.e. of f . In the same way, the relation End(f ) = Beg(ϕ(e)) implies that the color following the one of f in the same cyclic order is the one of e. To sum up, in this cyclic order, one has the following direct sequence: . . . , color of e, color of f , color of e, . . .

which is impossible, since k > 2.
So the cardinality of A is the one of L, and by (8), the result (a) of the lemma is an immediate application of the previous lemma, for X = Proof of Theorem 3.8.

Again, we are going to apply Corollary 3.2. Let us fix p ≥ 1 and σ ∈ S p . Note that the singletons partition, denoted by ∆ s , is in C(σ, w, A 1 , . . . , A k ) (the proof is the same one as in the proof of Theorem 3.7). Moreover, using Lemma 2.6, one easily sees that the Neagu characteristic of G(σ, w) is 0. Hence it suffices to prove that for all ∆ ∈ C(σ, w, A 1 , . . . , A k ) such that ∆ = ∆ s , the Neagu characteristic of G(σ, w)/∆ is negative. Let us fix such a partition ∆. By Remark 3.11, we have to prove that By hypothesis, one has either d 1 > 2 or d 2 > 2. By symetry, we will suppose that d 1 > 2:

-If there is at least one directed cycle of color 1 in G(σ, w)/∆. Then (10) holds, because since d 1 > 2, the right hand term of (11) is strictly less than pk -

2 r=1 L directed cycle of G(σ,w)/∆ with color r length of L d r .
-If there is no directed cycle of color 1 in G(σ, w)/∆. Then there is at least one directed cycle of color 2, and, since d 2 > 1, the right hand term in (ii) (b) of Lemma 3.10 is strictly less than pk -

L directed cycle of G(σ,w)/∆ with color 2 length of L d 2 = pk - 2 r=1 L directed cycle of G(σ,w)/∆ with color r length of L d r ,
i.e. than the right hand term of (10). So (10) holds.

3.4.2.

Case where k = 2 and A 1 ∪ A 2 ⊂ {1, 2}. Here, for n positive integer, we consider σ n = s 1 (n)s 2 (n) with s 1 (n), s 2 (n) independent random involutions. There are three cases:

(i) s 1 (n), s 2 (n) have both uniform distribution on the set of involutions of [n]: A 1 = A 2 = {1, 2}, (ii) s 1 (n), s 2 (n) have both uniform distribution on the set of involutions of [n] without any fixed point: A 1 = A 2 = {2}, (iii) one of the random involutions has uniform distribution on the set of involutions of [n] and the other one has uniform distribution on the set of involutions of [n] without any fixed point: since for s, s ′ involutions, ss ′ and s ′ s are conjugate, one can suppose that

A 1 = {2}, A 2 = {1, 2}.
Theorem 3.12.

(i) If A 1 = A 2 = {1, 2}
, then as n goes to infinity, for all q ≥ 1, the law of (N 1 (σ n ), . . . , N q (σ n )) converges weakly to µ 1 ⊗ • • • ⊗ µ q , where for all l ≥ 1, µ l is the law of P 1 +2 P 1 2l , with P 1 , P 1 2l independent random variables with distributions

Poisson(1), Poisson( 1 2l ). (ii) If A 1 = A 2 = {2}
, then as n goes to infinity, for all q ≥ 1, the law of

1 2 (N 1 (σ n ), . . . , N q (σ n )) converges weakly to Poisson(1/2) ⊗ Poisson(1/4) ⊗ • • • ⊗ Poisson(1/2q). (iii) If A 1 = {2}, A 2 = {1, 2}
, then as n goes to infinity, for all q ≥ 1, the law of (N 1 (σ n ), . . . , N q (σ n ))

converges weakly to µ 1 ⊗ • • • ⊗ µ q , where for all l odd, µ l is the law of 2 P 1 2l and for all l even, µ l is the law of P To prove the Theorem, we shall need the following lemmas. Lemma 3.14. Consider A 1 , A 2 as in (i), (ii) or (iii) of Theorem 3.12. Fix p ≥ 1 and σ ∈ S p . Then the following holds:

• for all ∆ ∈ C(σ, g 1 g 2 , A 1 , A 2 ), χ(G(σ, g 1 g 2 )/∆) = 0, • the cardinality of C(σ, g 1 g 2 , A 1 , A 2 ) is            p l=1 E(( √ lX + l + 1) N l (σ) ) if A 1 = A 2 = {1, 2}, p l=1 E((1 + √ lX) N l (σ) ) if A 1 = A 2 = {2}, 1≤l≤p l odd E[( √ lX + 1) N l (σ) ] 1≤l≤p l even E[( √ lX + l/2 + 1) N l (σ) ] if A 1 = {2}, A 2 = {1, 2},
where X is a standard Gaussian random variable.

(l, i, 2) 2 G G (l, i, 3) 1 G G (l, i, 4) 2 G G (l, i, 5) 1 G G • • • ' '
(l, i, 1) 1 q q q q q V V q q q q q (l, i, 2l)

2 y y Ó Ó (l, i, 2l -1) 1 w w w w w f f w w w w w (l, i, 2l -2) 2 o o • • • 1 o o o o Figure 3.
The graph H(l, i).

Proof. Let, for l positive integer, c 2l be the cycle (1 2

• • • 2l).
First, we are going to use Lemma 2.6: up to a renaming of its vertices and edges, G(σ, g 1 g 2 ) is the disjoint union, for (l, i) such that l ∈ [p], i ∈ [N l (σ)], of the graphs H(l, i), where each H(l, i) is the oriented edge-colored graph with color set {1, 2}, with vertex set {(l, i, j) ; j ∈ [2l]}, with 1-colored edge set {(l, i, j) → (l, i, c 2l (j)) ; j ∈ [2l] odd} and with 2-colored edge set {(l, i, j) → (l, i, c 2l (j)) ; j ∈ [2l] even}. An illustration is given in Figure 3. With this renaming, for ∆ a partition of the vertex set of G(σ, g 1 g 2 ), the condition

∀m = m ′ ∈ [p], (m, 1) = (m ′ , 1) mod ∆ gets ∀l, l ′ ∈ [p], ∀(i, i ′ ) ∈ [N l (σ)]×[N l ′ (σ)], ∀(j, j ′ ) ∈ [2l]×[2l ′ ], (12)
[(l, i, j) = (l ′ , i ′ , j ′ ) and j = j ′ mod 2] ⇒ [(l, i, j) = (l ′ , i ′ , j ′ ) mod ∆]. Now, let us fix ∆ ∈ C(σ, g 1 g 2 , A 1 , A 2 ). a) By Remark 3.11, G(σ, w)/∆ has 2p edges. b) By (12), the classes of ∆ cannot have more than two elements. c) ∆ is an (A 1 , A 2 )-admissible partition, so no directed path of color either 1 or 2 of G(σ, g 1 g 2 )/∆ can have length at least two. This implies that if two distinct edges of G(σ, g 1 g 2 )/∆ have the same color and an extremity in common, then these edges are the ones of a directed cycle of length two, i.e. that the beginning of each of them is the end of the other one and vice versa. d) Let us consider two distinct vertices (l, i, j) = (l ′ , i ′ , j ′ ) of G(σ, g 1 g 2 ) which form together a class of ∆.

(α) By (12), j and j ′ do not have the same parity, hence the edge which begins at (l, i, j) has the color of the edge which ends at (l ′ , i ′ , j ′ ), and vice versa. So by an immediate induction on |m| (using c)), one has:

(13) ∀m positive or negative integer, (l, i, c m 2l (j)) = (l ′ , i ′ , c -m 2l ′ (j ′ )) mod ∆.

(β) Suppose that l = l ′ . One can suppose that l < l ′ . Then by (13) for m = 2l, (l, i, j) = (l, i, c 2l 2l (j)) is in the same time linked, by ∆, with (l ′ , i ′ , c -2l 2l ′ (j ′ )) and (l ′ , i ′ , j ′ ) which are not the same. By b), it is impossible. Hence

l = l ′ . 3 ′ 1 Ð Ð Ð Ð Ð Ð Ð Ð Ð Ð Ð Ð Ð Ð Ð Ð ∆ 2 ′ ∆ 2 o o 2 2 G G 3 1 b b b b 1 1 b b b b 4 ′ ∆ 2 1 1 Ð Ð Ð Ð c c Ð Ð Ð Ð b b 8 2 y y 5 ∆ 1 Ð Ð Ð Ð Ð Ð Ð Ð 8 ′ 2 y y 7 ∆ 1b b b b b b b b 6 ∆ 2 o o 6 ′ 2 G G 7 ′ 1 Ð Ð Ð Ð Ð Ð Ð Ð c c Ð Ð Ð Ð Ð Ð Ð Ð {2, 3 ′ } 2 P P 1 Ñ Ñ {3, 2 ′ } 2 r r 1 9 9 {1, 4 ′ } 1 e e 2 {4, 1 ′ } 1 g g 2 {8, 5 ′ } 1 9 9 2 {5, 8 ′ } 1 Ñ Ñ 2 {7, 6 ′ } 2 P P 1 g g {6, 7 ′ } 2 r r 1 e e
restriction of the graph G(σ, g 1 g 2 ) to {(l,i,1),(l,i,2),...,(l,i,8)}∪{(l,i ′ ,1),(l,i ′ ,2),...,(l,i ′ ,8)} restriction of the graph G(σ, g 1 g 2 )/∆ to the set of classes of (l,i,1),(l,i,2),...,(l,i,8),(l,i ′ ,1),(l,i ′ ,2),...,(l,i ′ ,8)

(γ 1 )Suppose that i = i ′ . Then by ( 13) for m = -j + 1, -j + 2, . . . , -j + 2l, there is a unique q ∈ [l] such that the classes, in ∆, of (l, i, 1), (l, i, 2), . . . , (l, i, 2l), (l, i ′ , 1), (l, i ′ , 2), . . . , (l, i ′ , 2l) are (14) {(l, i, 1), (l, i ′ , 2q)}, {(l, i, 2), (l, i ′ , c -1 2l (2q))}, . . . , {(l, i, 2l), (l, i ′ , c

-(2l-1) 2l (2q))}.
Note that q depends on i and i ′ in a symmetric way, since the set of (14) can also be written {(l, i ′ , 1), (l, i, 2q)}, {(l, i ′ , 2), (l, i, c -1 2l (2q))}, . . . , {(l, i ′ , 2l) , (l, i, c

-(2l-1) 2l
(2q))}.

On Figure 4, we give an illustration of the case (γ 1 ) with l = 4, q = 2. In the inner (resp. outer) octagon, the vertices where not denoted by (l, i, j) (resp. (l, i ′ , j)) but by j (resp. j ′ ), for j ∈ [8], in order to lighten the figure. In G(σ, g 1 g 2 ), vertices linked by ∆ are linked by edges of the type • ∆ • (but these edges do not belong to G(σ, g 1 g 2 )). On this figure, it appears clearly that if two vertices of the left graph linked by an edge of the type • ∆ • are in the same class of ∆, then, since no directed path of color either 1 or 2 of G(σ, g 1 g 2 )/∆ can have length at least two, all the other pairs of vertices linked by an edge of the type • ∆ • must form classes of ∆.

(γ 2 ) Let us prove that if i = i ′ , then there is j 0 ∈ [2l] such that the classes, in ∆, of the elements (l, i, 1), (l, i, 2), . . . , (l, i, 2l) are

{(l, i, j 0 ), (l, i, c 2l (j 0 ))}, {(l, i, c -1 2l (j 0 )), (l, i, c 2 2l (j 0 ))}, {(l, i, c -2 2l (j 0 )), (l, i, c 3 2l (j 0 ))}, (15)
. . . , {(l, i, c -(l-1) 2l (j 0 )), (l, i, c l 2l (j 0 ))}, and that this j 0 is unique up to a replacement by c l 2l (j 0 ). Note first that if such a j 0 exists, then its uniqueness up to a replacement by c l 2l (j 0 ) is obvious. Indeed, if one denotes c l 2l (j 0 ) by j ′ 0 , then since c 2l is a cycle of length 2l, the partition of (15) is

I. {(l, i, j), (l, i ′ , j ′ )} with l ∈ [p], i = i ′ ∈ [N l (σ)], j, j ′ ∈ [2l]
, and if there is such a class {(l, i, j), (l, i ′ , j ′ )} in ∆, then there is a unique q ∈ [l] (depending symmetrically on i and i ′ ) such that the classes, in ∆, of (l, i, 1), (l, i, 2), . . . , (l, i, 2l)(l, i ′ , 1), (l, i ′ , 2), . . . , (l, i ′ , 2l) are given by ( 14). We shall denote this integer q by q ∆ (l, {i, i ′ }).

II. {(l, i, j), (l, i, j ′ )} with l ∈ [p], i ∈ [N l (σ)], j, j ′ ∈ [2l], and that if there is such a class {(l, i, j), (l, i, j ′ )} in ∆, then there is j 0 ∈ [2l], unique up to a replacement by c l 2l (j 0 ), such that the classes, in ∆, of (l, i, 1), (l, i, 2), . . . , (l, i, 2l) are given by (15). We denote by T l (∆) the set of such i's in [N l (σ)]. If A 1 = A 2 = {2}, then this case cannot occur, hence T l (∆) = ∅. If A 1 = A 2 = {1, 2}, then there is no restriction on l and j 0 , and we shall denote the unique element of {j 0 , c l 2l (j 0 )} ∩ [l] by q ∆ (l, {i}). If A 1 = {2}, A 2 = {1, 2}, then the only restriction on l, j 0 is that they have to be even, and we shall denote the unique element of { 1 2 j 0 , 1 2 c l 2l (j 0 )} ∩ [ l 2 ] by q ∆ (l, {i}).

If i ∈ [N l (σ)] is such that for all j ∈ [2l], the singleton {(l, i, j)} is a class of ∆, then we define q ∆ (l, {i}) to be 0. f) Let us define, for l ∈ [p], P l (∆) to be the partition of [N l (σ)] which links to elements i, i ′ if and only if there is j, j ′ ∈ [2l] such that (l, i, j) and (l, i ′ , j ′ ) are linked by ∆ (we use the convention that the empty set has a unique partition, that this partition has cardinality zero and that if N l (σ) = 0, P l (∆) is this partition). l i E(X 2i )(l + 1) N l (σ)-2i .

Let us define, for N ≥ 1, Part 2,1 (N ) to be the set of partitions of [N ] in which all classes have cardinality 1 or 2. It is easy to see that the function ϕ : C(σ, g 1 g 2 , {1, 2}, {1, 2}) → {(P l , (q(l, A)) A∈P l ) l∈C(σ) ; ∀l ∈ C(σ), P l ∈ Part 2,1 (N l (σ)), ∀A ∈ P l such that |A| = 2, q(l, A) ∈ [l] and ∀A ∈ P l such that |A| = 1, q(l, A) ∈ {0} ∪ [l]} ∆ → (P l (∆), (q ∆ (l, A)) A∈P l (∆) ) l∈C(σ) is a bijection. Hence it suffices to prove that for all l ≥ 1, N ≥ 1, the cardinality of the set of pairs (P, (q(A)) A∈P ) such that P ∈ Part 2,1 (N ) and for all A ∈ P , q(A) ∈ [l] if |A| = 2 and q(A) ∈ {0} ∪ [l] in the other case, is equal to

⌊N/2⌋ i=0 N 2i l i E(X 2i )(l + 1) N -2i .
It follows easily from the well known fact (called Wick's formula) that for all i ≥ 1, the number of partitions of a set with cardinality 2i in which all classes have two elements is equal to E(X 2i ).

To prove that cardinalities of C(σ, g 1 g 2 , {2}, {2}) and of C(σ, g 1 g 2 , {2}, {1, 2}) are the ones given in the statement of the Lemma, we use the same technique, replacing the bijection ϕ by φ : C(σ, g 1 g 2 , {2}, {2}) → {(P l , (q(l, A)) A∈P l ) l∈C(σ) ; ∀l ∈ C(σ), P l ∈ Part 2,1 (N l (σ)) and ∀A ∈ P l such that |A| = 2, q(l, A) ∈ [l], ∀A ∈ P l such that |A| = 1, q(l, A) = 1} ∆ → (P l (∆), (q ∆ (l, A)) A∈P l (∆) ) l∈C(σ)

ψ : C(σ, g 1 g 2 , {2}, {1, 2}) → {(P l , (q(l, A)) A∈P l ) l∈C(σ) ; ∀l ∈ C(σ), P l ∈ Part 2,1 (N l (σ)), ∀l ∈ C(σ), ∀A ∈ P l such that |A| = 2, q(l, A) ∈ [l], ∀l even, ∀A ∈ P l such that |A| = 1, q(l, A) ∈ {0} ∪ [l/2]}) and ∀l odd, ∀A ∈ P l such that |A| = 1, q(l, A) = 1} ∆ → (P l (∆), (q ∆ (l, A)) A∈P l (∆) ) l∈C(σ)

Proof of Theorem 3.12. Let us prove (i). (ii) and (iii) can be treated analogously. We are going to apply Theorem 1.1 of [START_REF] Benaych-Georges | Florent Cycles of random permutations with restricted cycle lengths[END_REF]. For q ≥ 1, k 1 , . . . , k q ≥ 1, for p = 1 1 + • • • + k q q and σ ∈ S p such that N 1 (σ) = k 1 , . . . , N q (σ = k q ) , by Proposition 3.1 and Lemma 3.14,

n p 1 k 1 • • • q kq k 1 ! • • • k q !
P ({∀i = 1, . . . , p, σ n (i) = σ(i)} converges, as n goes to infinity, to q l=1 1 k l ! E[(( √ lX +l+1)/l) k l ], where X is a standard Gaussian variable. Hence we have to prove that for all r 1 , . . . , r q ≥ 0, the series

k 1 ≥r 1 • • • kq≥rq (-1) k 1 -r 1 +•••+kq-rq k 1 r 1 • • • k q r q q l=1 1 k l ! E[(( √ lX + l + 1)/l) k l ]
converges to q l=1 µ l (r l ), which is equal, by Lemma 3.13, to q l=1 e -1-

1 2l E[(X+ √ l) r l ]
r l ! l r l /2 . Since this series factorize and by Remark 1.2 of [START_REF] Benaych-Georges | Florent Cycles of random permutations with restricted cycle lengths[END_REF], it suffices to prove that for l ≥ 1, r ≥ 1, the series . This follows from an application of the Dominated Convergence Theorem.

  nonempty word. In[START_REF] Nica | On the number of cycles of a given length of a free word in several random permutations[END_REF], Nica defined G(σ, w) (denoted by H σ -1 ⋆w in his paper) to be the directed, edge-colored graph with vertex set V := [p]×[|w|] and whose edges are the followings: for all (m, l) ∈ [p]×[|w|],

Proof.

  Let us denote G(σ, w) = (V ; E 1 , . . . , E k ). If I, J are disjoint subsets of [p] stabilized by σ, then in G(σ, w), there is no edge between elements of I×[|w|] and J×[|w|]. Hence G(σ, w) is the disjoint union of the graphs (V (c); E 1 (c), . . . , E k (c)), where c varies over the set of cycles of σ, and where for any such cycle c, with support C ⊂ [p], V (c) = C×[|w|] and for any

|u|)

  Then add the vertex |u| ′ and the i |u| -colored edge (|u| -1) ′ → |u| ′ or (|u| -1) ′ ← |u| ′ according to whether ε |u| = 1 or -1. |u| + 1) Then add the vertex (|u| + 1) ′ and the i-colored edge |u| ′ → (|u| + 1) ′ . This is a direct extension, because we know that i |u| = i: indeed, w is cyclically reduced, and on the one hand, the letter g ε |u| i |u| appears in before g αd i i in w, whereas on the other hand, the letter g -ε |u| i |u| appears in after g αd i i in w. |u| + 2) Then add the vertex (|u| + 2) ′ and the i-colored edge (|u| + 1) ′ → (|u| + 2) ′ . . . . |u| + d i -1) Then add the vertex (|u| + d i -1) ′ and the i-colored edge (|u|

  |L[r]| = L directed cycle of G(σ,w)/∆ with color r length of L. Another consequence of the claim is that one can define a permutation ϕ of L which maps any edge e ∈ L to the edge which follows e in the monochromatic directed cycle e belongs to. Let us define, for e ∈ L, S(e) := {End(e), Beg(ϕ(e))} ⊂ [p]×[|w|].

A

  := {S(e) ; e ∈ L} (to prove (a)) or, for r ∈ [k], of A[r] := {S(e) ; e ∈ L, e has color r} (to prove (b)). Suppose that there are e = f ∈ L such that S(e) = S(f ). One has either (End(e), Beg(ϕ(e))) = (End(f ), Beg(ϕ(f ))) or (End(e), Beg(ϕ(e))) = (Beg(ϕ(f )), End(f )). But (End(e), Beg(ϕ(e))) = (End(f ), Beg(ϕ(f ))) is impossible because two different edges of G(σ, w) cannot have the same end, since no letter of w has the exponent -1. So one has (End(e), Beg(ϕ(e))) = (Beg(ϕ(f )), End(f )).

  [p]×[|w|] and B = A. If k = 2: End(f ) = Beg(ϕ(e)) implies that the color of f is different from the color of ϕ(e), i.e. of e. So for all r = 1, 2, the cardinality of A[r] is the one of L[r], and by (9), the result (b) is an immediate application of the previous lemma, for X = [p]×[|w|] and B = A[r].

•

  (10) |∆| < pk -k r=1 L directed cycle of G(σ,w)/∆ with color r length of L d r . If there is no monochromatic directed cycle in G(σ, w)/∆, then, since ∆ = ∆ s , |∆| < |[p]×[|w|]| = pk, and hence (10) holds. • If there is a monochromatic directed cycle in G(σ, w)/∆ and k > 2, then since for all r, d r ≥ 2 > 1, by (ii) (a) of Lemma 3.10, (10) holds. • If there is a monochromatic directed cycle in G(σ, w)/∆ and k = 2. First note that adding (ii) (b) of Lemma 3.10 for r = 1 and r = 2, and then dividing by 2, one gets (11) |∆| ≤ pk -1 2 2 r=1 L directed cycle of G(σ,w)/∆ with color r length of L.

Lemma 3. 13 .

 13 Consider a, b positive real numbers and define the measure ν a,b := e -1+2ab 2b 2 +∞ r=0 E[(X + a) r ] r!b r δ r , with X standard Gaussian random variable. Then ν a,b is the distribution of P a b random variables with respective distributions Poisson(a/b), Poisson(1/(2b 2 )).

  g) It is easily seen that the number of vertices of G(σ, w)/∆ is p l=1 2l|P l (∆)| -l|T l (∆)|, that the sum of the number of 1-colored directed cycles of length two and of the number of 2-colored directed cycles of length two in G(σ, w)/∆ is p l=1 2l|{C ∈ P l (∆) ; |C| = 2}| + (l -1)|T l (∆)| and that the sum of the number of 1-colored directed cycles of length one and of the number of 2-colored directed cycles of length one in G(σ, w)/∆ is p l=1 2|T l (∆)|. Hence by a), the Neagu characteristic of G(σ, w)/∆ is p l=1 2l|P l (∆)| -l|T l (∆)| -2p + p l=1 2l|{C ∈ P l (∆) ; |C| = 2}| + (l -1 + 1)|T l (∆)| = -2p + 2 p l=1 l(|P l (∆)| + |{C ∈ P l (∆) ; |C| = 2}|). But since for all l, P l (∆) is a partition of [N l (σ)] where all classes have cardinality one or two, |P l (∆)| + |{C ∈ P l (∆) ; |C| = 2}| = |[N l (σ)]| = N l (σ). Hence since p l=1 lN l (σ) = p, the Neagu characteristic of G(σ, w)/∆ is null. i) In the case where A 1 = A 2 = {1, 2}, let us prove that cardinality of C(σ, g 1 g 2 , {1, 2}, {1, 2}) is p l=1 E[( √ lX + l + 1) N l (σ) ], for X standard Gaussian variable. Note first that if C(σ) denotes {l ∈ [p] ; N l (σ) = 0}, then this reduces to l∈C(σ) ⌊N l (σ)/2⌋ i=0 N l (σ) 2i

  lX + l + 1)/l) k ] converges to e -1-1 2l E[(X+ √ l) r ] r! l r/2

hypothesis, that G n-1 /Γ is either isomorphic to an extension of G(w) with degree ≤ n -1 or isomorphic to an extension of G( w) for a certain strict partial (d 1 , . . . , d k )-reduction w of w. Hence it suffices to prove one of the following properties: (P1) Adm(G n /{t 0 = t d i }) is isomorphic to G n-1 /Γ, (P2) Adm(G n /{t 0 = t d i }) is isomorphic to a direct extension of G n-1 /Γ, (P3) there is j ∈ [k] such that d j < ∞ and G n-1 /Γ contains a j-colored directed path with length d j and extremity vertices x, y and such that Adm(G n /{t 0 = t d i }) is isomorphic to Adm((G n-1 /Γ)/{x = y}).

(The conclusion, in the (P3) case, requires to use the induction hypothesis again.)

Note that for all w partial (d 1 , . . . , d k )-cyclic reductions of w, since the order of the element of F k /[g d 1 1 , . . . , g d k k ] represented by w (hence by w) cannot be finite and nonzero, we have the following property: (Q) for all j ∈ [k] such that d j < ∞, G( w) does not contain any j-colored directed cycle. Now, again, we have two sub-cases to consider:

-If the extension G n-1 ⊂ G n is vertex-adding: there is j ∈ [k], a vertex r of G n , a vertex s of G n-1 such that G n can be obtained from G n-1 by the addition of the vertex r and of the j-colored edge s → r (or r → s). Now, if no edge with color j has s for beginning vertex (or respectively ending vertex) in

is isomorphic to the vertex-adding direct extension of G n-1 /Γ obtained by adding the vertex r and the edge s → r (or respectively r → s). On the other hand, if an edge with color j has s for beginning vertex (or respectively ending vertex) in

obtained from G n-1 by adding an edge with color j between two vertices of G n-1 which are the extremities of a j-colored directed path with length d j -1. Let us denote by v 1 , . . . , v d j the successive vertices of this directed path: the edge added in the direct extension

We can suppose that a j-colored edge of G n-1 /Γ has v 1 for ending vertex: the other case can be treated analogously. Hence there is a vertex

The following lemma is a consequence of the previous one, by induction on the sum, over j ∈ [k], on the number of j-colored paths of G with length ≥ d j .

Proof. Note that by Lemma 2.6, for all l ≥ 1, the function (m, i)

Then it suffices to apply Theorem 2.12.

Words in random permutations

We fix, until the end of the article, k ≥ 1 and A 1 ,. . . , A k nonempty sets of positive integers, none of them being {1}, satisfying (1). We shall only consider some positive integer n such that S n (A 1 ), . . . , S n (A k ) are all nonempty (which is equivalent, for n large enough, to the fact that for all i ∈ [k], n is divisible by the greatest common divisor of A i [Ne07, Lem. 2.3]). For such an integer n, we consider an independent k-tuple s 1 (n), . . . , s k (n) of random permutations chosen uniformly in respectively S n (A 1 ), . . . , S n (A k ).

We also fix a cyclically reduced word w ∈ M k and define σ n = w(s 1 (n), . . . , s k (n)): the permutation obtained by replacing any g i (or g -1 i )in w by s i (n) (or s i (n) -1 ).

3.1.

A key preliminary result.

Proposition 3.1. Consider p ≥ 1 and σ ∈ S p . The probability of the event

is equivalent, as n goes to infinity, to

where C(σ, w, A 1 , . . . , A k ) is the set of (A 1 , . . . , A r )-admissible partitions ∆ of G(σ, w) such that for all m = m ′ ∈ [p], (m, 1) = (m ′ , 1) mod ∆.

and α 1 , . . . , α |w| ∈ {-1, 1}. We denote by V the vertex set [p] × [|w|] of G(σ, w), fix n ≥ 1, and define, for any s = (s 1 , . . . , s k ) ∈ (S n ) k , the function

. Note that since all s i 's are one-to-one, Part(γ s ) is an admissible partition of G(σ, w). Note also that if γ is a fixed function from V to [n] such that for all m = 1, . . . , p, γ(m, 1) = σ(m), then for all s = (s 1 , . . . , s k ) ∈ (S n ) k , γ s = γ if and only if (4) for all r ∈ [k], for all edge e of G(σ, w) with color r, s r (γ(End(e))) = γ(Beg(e)).

Note at last that since the joint distributions of the s i (n)'s is invariant under conjugation, for such a function γ, the probability of the event {γ (s 1 (n),...,s k (n)) = γ} only depends on Part(γ).

Hence probability of the event of (2) is the sum, over all admissible partitions ∆ of G(σ, w), of the number of functions γ : V → [n] whose level set partition is ∆ and which satisfy γ(m, 1) = σ(m) for all m ∈ [p], times the probability that γ (s 1 (n),...,s k (n)) is a certain (fixed, but the choice is irrelevant) of these functions. Now, note that for ∆ admissible partition of G(σ, w), the number of such functions is

in the other case.

Suppose this number to be nonzero. Then by (4), the probability that γ s 1 (n),...,s k (n) is a certain (fixed) of these functions is

where for all r ∈ [k], (G(σ, w)/∆)[r] is the graph obtained from G(σ, w)/∆ by removing all edges which do not have color r and all vertices which are not the extremity of an r-colored edge, and where for all set A of positive integers and F monochromatic oriented graph, p

n (F ) is the number defined in 3.8(a) of [START_REF] Neagu | Asymptotic freeness of random permutation matrices with restricted cycles lengths[END_REF].

So by definition of C(σ, w, A 1 , . . . , A k ), the probability of the event of (2) is equal to

and Proposition 3.8 of [START_REF] Neagu | Asymptotic freeness of random permutation matrices with restricted cycles lengths[END_REF] allows one to conclude the proof.

The following result is a direct application of Corollary 1.3 of [START_REF] Benaych-Georges | Florent Cycles of random permutations with restricted cycle lengths[END_REF].

Corollary 3.2. If w cyclically reduced is such that for all p ≥ 1, for all σ ∈ S p , for all ∆ ∈ C(σ, w, A 1 , . . . , A k ), one has χ(G(σ, w)/∆) ≤ 0, with equality for exactly one ∆ ∈ C(σ, w, A 1 , . . . , A k ), then for all l ≥ 1, the law of (N 1 (σ n ), . . . , N l (σ n )) converges weakly, as n goes to infinity, to

Remark 3.3. The hypotheses of this corollary do not always hold: for w = g 3 1 g 2 , p = 1, with A 1 = {3, 4}, A 2 = {1, 2}, the quotient of the graph G(w) by the partition {1 = 4} has Neagu characteristic 3 -4 + 3/4 + 1/2 > 0.

3.2. Rate of growth of the N l (σ n )'s.

Case of a word with infinite order in

: existence of cycles of most lengths. Here, we shall see that even though the lengths of the cycles of s 1 (n),. . . , s k (n) are supposed to belong to the specific sets A 1 , . . . , A k of positive integers, these cycles are going to mix sufficiently well to give birth to cycles of most lengths in σ n , at least as much as in a uniform random permutation.

Theorem 3.4. Suppose that the order, in

of the element represented by w is infinite. Then two cases can occur:

, α an integer: then for all l ≥ 1, as n goes to infinity,

(ii) There is i ∈ [k] such that A i is infinite and the (d 1 , . . . , d k )-cyclic reduction of w is g α i , with α nonzero integer: then for all l ≥ 1 such that l|α| ∈ A i , as n goes to infinity,

Remark 3.5. In fact, we prove the more general result: if c l denotes the cycle (1

Proof. We have

1 i belongs to a cycle of length l of σn = 1 l n i=1 P ({i belongs to a cycle of length l}).

But in the last sum, since the law of σ n is invariant under conjugation, all terms are equal. Moreover, by this invariance principle again, each term is equal to the number of cycles of length l containing 1 times the probability that σ n contains the cycle c l := (1

Thus, by Proposition 3.1, (5) follows, and then Corollary 2.13 allows us to conclude.

Case of a word with finite order in

The following theorem states that in the case where the element of

] represented by w has finite order d ≥ 1, σ n is not far away from having order d: the cardinality of the subset of {1, . . . , n} covered by the supports of the cycles with length d in such a random permutation is asymptotic to n. Theorem 3.6. Suppose that the element of

Proof. Notice first that for all n, (6)

which implies that for all positive integer l, the sequence N l (σ n )/n is bounded by 0 and 1/l. Now, recall that for a sequence (X n ) of random variables, if there exists M < ∞ such that for all n, 0 ≤ X n ≤ M , the convergence of X n to a limit X in all L p spaces is implied by this result for p = 1 (indeed, under this hypothesis, if for a certain p ≥ 1, X n does not converge to X in L p , then a subsequence of (X n ) converges to X almost surely but not in L p , which is impossible by the Dominated Convergence Theorem).

Hence by (6), it suffices to prove that lim inf(E(N d (σ n )/n)) ≥ 1/d. This follows from (5) (which has been established in the proof of Theorem 3.4 without using the specific hypothesis of this theorem) and of Corollary 2.13.

3.3.

Case when all A i 's are infinite. Theorem 3.7. Suppose that all A i 's are infinite, that |w| > 1 and that w is not a power of another word. Then as n goes to infinity, for all l ≥ 1, the law of (N 1 (σ n ), . . . , N l (σ n )) converges weakly to

Proof. This result is a direct consequence of Corollary 3.2. Note first that since all A i 's are infinite, for all i, d i = ∞. Hence for all p ≥ 1, for all σ ∈ S p , for all ∆ an admissible partition of G(σ, w), χ(G(σ, w)/∆) is the number of classes of ∆ minus the number of edges of G(σ, w)/∆, hence is not positive by Proposition 2.4.3 of [START_REF] Nica | On the number of cycles of a given length of a free word in several random permutations[END_REF]. The last sentence of Corollary 2.6.6 of the same article also says that there is only one admissible partition ∆ of G(σ, w) such that χ(G(σ, w)/∆) is null and such that for all m = m ′ ∈ [p], (m, 1) and (m ′ , 1) are not in the same class: it is the singletons partition. It remains only to prove that the singletons partition is in C(σ, w, A 1 , . . . , A k ):

{(l,i,1),(l,i,2),...,(l,i,8)} restriction of the graph G(σ, g 1 g 2 )/∆ to the set of classes of (l,i,1),(l,i,2),...,(l,i,8)

Figure 5 equal to

(j 0 )), (l, i, c l 2l (j 0 ))} (= {(l, i, j ′ 0 ), (l, i, c 2l (j ′ 0 ))}) are the only classes of the type {(l, i, x), (l, i, c 2l (x))} in the partition of (15).

To prove the existence of such a j 0 , it suffices to notice that by (13) and b), j 0 = (j ′ + j -1)/2 is convenient.

On Figure 5, give an illustration of the case (γ 2 ) with l = 4, j 0 = 2. The comments on this figure are the same as the ones on Figure 4.

(γ 3 ) Now, notice that the case (γ 2 ) implies the existence of two monochromatic directed cycles with length 1 in G(σ, g 1 g 2 )/∆: indeed, the edges (l, i, j 0 ) → (l, i, c 2l (j 0 )), (l, i, c l 2l (j 0 )) → (l, i, c l+1 2l (j 0 )) of G(σ, g 1 g 2 ) give rise to the edges {(l, i, j 0 ), (l, i, c 2l (j 0 ))} in G(σ, g 1 g 2 )/∆. The respective colors of these edges are

1, 1 if j 0 is odd and l is even, 1, 2 if j 0 is odd and l is odd, 2, 2 if j 0 is even and l is even, 2, 1 if j 0 is even and l is odd.

Hence this case is excluded if A 1 = A 2 = {2}, and if A 1 = {2}, A 2 = {1, 2}, then j 0 and l have to be even.

e) So we have proved that the only non singleton classes of ∆ are of two types


Thomas V O Hansen

Lars Jønson

Anders Albrechtsen

Ane Y Steffensen

Eva Bergsten

Torben Myrhøj

Bent Ejlertsen

Finn C Nielsen

Keywords: BRCA1, Greenland, Inuit, novel mutation

  Identification of a novel nucleotide 4803delCC/c.4684delCC mutation and a nucleotide 249T>A/c.130T>A (p.Cys44Ser) mutation in two Greenlandic Inuit families: implications for genetic screening of Greenlandic Inuit families with high risk for breast and/or ovarian cancer

Introduction

BRCA1 (MIM 113705) and BRCA2 (MIM 600185) germ-line mutations predispose to hereditary breast and ovarian cancer, conferring a lifetime risk of approximately 80% for breast cancer and 20-50% for ovarian cancer in female carriers [START_REF] Thompson | The genetic epidemiology of breast cancer genes[END_REF]. BRCA1 and BRCA2 are involved in a variety of cellular processes, including maintenance of genome stability [START_REF] Moynahan | BRCA2 is required for homology-directed repair of chromosomal breaks[END_REF][START_REF] Davies | Role of BRCA2 in control of the RAD51 recombination and DNA repair protein[END_REF], DNA repair via homologous recombination [START_REF] Moynahan | BRCA2 is required for homology-directed repair of chromosomal breaks[END_REF][START_REF] Davies | Role of BRCA2 in control of the RAD51 recombination and DNA repair protein[END_REF], transcriptional regulation [START_REF] Shin | BRCA2 cooperates with histone acetyltransferases in androgen receptor-mediated transcription[END_REF], cell cycle control [START_REF] Marmorstein | A human BRCA2 complex containing a structural DNA binding component influences cell cycle progression[END_REF], chromatin remodelling [START_REF] Marmorstein | A human BRCA2 complex containing a structural DNA binding component influences cell cycle progression[END_REF] and ubiquitinylation [START_REF] Morris | Genetic analysis of BRCA1 ubiquitin ligase activity and its relationship to breast cancer susceptibility[END_REF]. Mutations are scattered throughout both genes and includes disease-causing mutations as well as unclassified variants (listed in Breast Cancer Information Core (BIC)). Moreover, several founder mutations have been reported in BRCA1 and BRCA2, including the Icelandic BRCA2 nucleotide 999del5, and the Ashkenazi Jews BRCA1 nucleotide 185delAG mutations, which are found with frequencies between 0.6% to 1.0% in the population [START_REF] Roa | Ashkenazi Jewish population frequencies for common mutations in BRCA1 and BRCA2[END_REF][START_REF] Struewing | The carrier frequency of the BRCA1 185delAG mutation is approximately 1 percent in Ashkenazi Jewish individuals[END_REF][START_REF] Thorlacius | A single BRCA2 mutation in male and female breast cancer families from Iceland with varied cancer phenotypes[END_REF][START_REF] Thorlacius | Study of a single BRCA2 mutation with high carrier frequency in a small population[END_REF]. In Denmark multiple disease-causing BRCA1/BRCA2 mutations have been identified [START_REF] Hansen | Large BRCA1 and BRCA2 genomic rearrangements in Danish high risk breastovarian cancer families[END_REF][START_REF] Hansen | Novel de novo BRCA2 mutation in a patient with a family history of breast cancer[END_REF][START_REF] Hansen | The silent mutation nucleotide 744 G --> A, Lys172Lys, in exon 6 of BRCA2 results in exon skipping[END_REF][START_REF] Soegaard | BRCA1 and BRCA2 mutation prevalence and clinical characteristics of a population-based series of ovarian cancer cases from Denmark[END_REF][START_REF] Thomassen | BRCA1 and BRCA2 mutations in Danish families with hereditary breast and/or ovarian cancer[END_REF]. However, only one disease-causing mutation (p.Cys39Gly) has been identified in Greenlandic Inuits [START_REF] Hansen | A common Greenlandic Inuit BRCA1 RING domain founder mutation[END_REF]. This mutation was identified in 13 Greenlandic Inuit families with breast and/or ovarian cancer, and had not previously been identified in other populations. Mutation positive individuals shared a 4.5 Mb haplotype in the BRCA1 region, indicating that the mutation in the BRCA1 region happened once and segregated in the population as a founder mutation [START_REF] Hansen | A common Greenlandic Inuit BRCA1 RING domain founder mutation[END_REF].

We now report the identification of another novel BRCA1 nucleotide 4803delCC/c.4684delCC mutation in a Greenlandic Inuit with ovarian cancer, which results in a frameshift and a premature stop at codon 1572. Moreover, we have identified a nucleotide 249T>A/c.130T>A (p.Cys44Ser) mutation in a Greenlandic Inuit with ovarian cancer. However, SNP array analysis indicates that this mutation originates from a Danish ancestor. These findings have implications for the genetic testing of Greenlandic Inuits with high risk for breast or ovarian cancer, and we suggest that genetic screening of this group of patients should comprise sequencing of the entire BRCA1 gene.

Patients and methods

Patients

Two Greenlandic Inuit families with ovarian and early breast cancer were identified (Fig. 1A andB). In one (family 97016), the proband was a 41 year-old woman recently diagnosed with ovarian cancer. The family had two cases of breast cancer (Fig. 1A). In the other family (family 84814), a 47-year old woman was diagnosed with ovarian cancer. This family had one case of breast cancer in a cousin (Fig. 1B). Following verbal and written consent, blood samples were collected and both probands underwent genetic testing. The family history was verified using the registry of the DBCG (Danish Breast Cancer Cooperative Group), hospital medical records and pathology reports, and genetic counselling was provided for the families.

BRCA1 and BRCA2 screening

Genomic DNA was purified from 2 ml whole blood using the Maxwell 16 system (Promega) according to the manufacturer's instructions. As a first step, BRCA1 exon 3 was amplified using intronic primer to examine for the Greenlandic BRCA1 nucleotide 234 T>G/c.115 T>G (p.Cys39Gly) founder mutation. When negative for this screening, all other BRCA1 and BRCA2 exons were amplified using intronic primer pairs. PCR products were pre-screened by high-resolution melting curve analysis using the LightScanner (Idaho Technology) and variants were sequenced using an ABI3730 DNA analyzer (Applied Biosystems). Sequence variations were verified in a new blood sample. Moreover, genomic DNA was examined by MLPA analysis as recommended by the manufacturer (MRC-Holland). The BRCA1 mutation is numbered according to Genbank accession number U14680 in which the A in the AUG start codon has number 120. Furthermore, the guidelines from the Human Genetic Variation Society (www.hgvs.org/mutnomen) were used.

In silico analysis

In silico prediction of the functional consequence of the BRCA1 Cys44Ser missense variant was performed using SIFT (Sorting Intolerant From Tolerant): http://blocks.fhcrc.org/sift/SIFT.html [START_REF] Kumar | Predicting the effects of coding non-synonymous variants on protein function using the SIFT algorithm[END_REF] Polyphen: http://coot.embl.de/PolyPhen/ [START_REF] Sunyaev | Prediction of deleterious human alleles[END_REF] and PMut: http://mmb2.pcb.ub.es:8080/PMut/ [START_REF] Ferrer-Costa | PMUT: a web-based tool for the annotation of pathological mutations on proteins[END_REF]. The mutation was introduced according to the guidelines of each programme and default settings were used in all predictions.

SNP chip analysis

Genomic DNA was applied to 250K StyI (~238.000 SNPs) SNP-microarray chips and processed according to the manufacturer's instructions (Affymetrix, UK). Briefly, 250 ng of genomic DNA was digested with StyI and ligated to adapters. Adapter ligated DNA was amplified, purified, fragmented and labeled with biotin and hybridized to the arrays for 18 hr.

The Affymetrix 450 fluidics station and the Affymetrix 3000 G7 gene scanner were used to wash, stain and scan the arrays. The CEL files were analysed using the BRLMM algorithm from Affymetrix Genotyping analysis software (GTYPE).

In order to assess whether the mutation happens once or several times, we investigate the local relatedness across the genome using Relate [START_REF] Albrechtsen | Relatedness mapping and tracts of relatedness for genome-wide data in the presence of linkage disequilibrium[END_REF]. The method estimates the local identical by descent (IBD) sharing in the presence of linkage disequilibrium using a hidden Markov model by conditioning on the 25 previous SNPs. Haplotype frequencies and allele frequencies were estimate using the five affected individuals plus an additional 60 unrelated

HapMap CEPH (Centre d'Etude du Polymorphisme Humain) individuals. SNPs with more than 5% missing data or a minor allele frequency of less than 1% were excluded from the analysis. Genetic distances were used instead of physical distances inferred from the Kong genetic map [START_REF] Kong | A high-resolution recombination map of the human genome[END_REF].

Results

The proband from family 97016, which was diagnosed with ovarian cancer at the age of 41, was referred to genetic counselling, since her deceased mother was diagnosed with breast cancer before the age of 40, and her deceased aunt was diagnosed with breast cancer at 55 years of age (Fig. 1A). The proband from family 84814, which was diagnosed with ovarian cancer at the age of 47, was referred to genetic counselling, since her cousin had breast cancer. Her mother died at the age of 34 of unknown reason, while the father is unknown (Fig. 1B). Both probands underwent genetic testing. The probands were first examined for the Greenlandic BRCA1 nucleotide 234T>G/c.115T>G (p.Cys39Gly) founder mutation. However, both were negative for this mutation. Due to the family history, the proband from family 97016 underwent whole screening of both BRCA1 and BRCA2. The analysis demonstrated a BRCA1 exon 16 nucleotide 4803delCC/c.4684delCC mutation (Fig. 2A) not previously described in the BIC database or the literature. The mutation introduces a frameshift and a premature stop at codon 1572. In family 84814, the analysis of BRCA1 exon 3 identified a nucleotide 249T>A/c.130T>A (p.Cys44Ser) mutation (Fig. 2B). This mutation is reported once in the BIC database as a variant of unknown significance. To indicate whether the mutations could be disease-causing, three different protein prediction programmes [START_REF] Kumar | Predicting the effects of coding non-synonymous variants on protein function using the SIFT algorithm[END_REF][START_REF] Sunyaev | Prediction of deleterious human alleles[END_REF][START_REF] Ferrer-Costa | PMUT: a web-based tool for the annotation of pathological mutations on proteins[END_REF] were used to predict the functional consequence of the BRCA1 p.Cys44Ser mutation. All three protein prediction programmes estimated the BRCA1 p.Cys44Ser mutation to be pathogenic. We have previously identified the p.Cys44Ser mutation in 4 Danish families.

Since the paternal side of patient with the nucleotide 249T>A/ c.130T>A (p.Cys44Ser) mutation is unknown, a SNP array analysis was performed to determine if the mutation represented a Danish founder mutation. If the BRCA1 mutation is a founder mutation, we would expect the carriers to share as least one allele identical by descent (IBD) around the BRCA1 gene.

Discussion

Individuals from Greenland with hereditary breast and/or ovarian cancer are screened for BRCA1/BRCA2 mutations at Rigshospitalet, Copenhagen, Denmark. We previously reported the BRCA1 nucleotide 234T>G/c.115T>G (p.Cys39Gly) mutation, which -at that point -was the only disease-causing mutation identified in this population [START_REF] Hansen | A common Greenlandic Inuit BRCA1 RING domain founder mutation[END_REF]. The first individual with this mutation was identified in 2001 and was a woman with breast cancer at the age of 43. But it was first until later, when the mutation was identified in other patients, we realized that this mutation was exclusively identified in Greenlandic Inuit's and that the mutation represented a Greenlandic founder mutation [START_REF] Hansen | A common Greenlandic Inuit BRCA1 RING domain founder mutation[END_REF]. The finding suggested that screening of the mutation in the whole population could be warranted [START_REF] Hansen | A common Greenlandic Inuit BRCA1 RING domain founder mutation[END_REF], but due to difficulties in collection of blood samples this is not feasible. We have -until now -screened 51 Greenlandic breast and/or ovarian cancer families and have identified the nucleotide 234T>G/c.115T>G (p.Cys39Gly) mutation in 18 of these families, which primarily includes high-risk breast and/or ovarian cancer families.

Here, we report a novel BRCA1 nucleotide 4803delCC/c.4684delCC mutation in a

Greenlandic high risk family. The mutation introduces a frameshift and a premature stop at codon 1572, resulting in the deletion of 292 amino acid residues of BRCA1, including the Cterminal BRCT domain, which is involved in protein-protein interaction [START_REF] Glover | Insights into the molecular basis of human hereditary breast cancer from studies of the BRCA1 BRCT domain[END_REF]. It is currently not known whether this mutation introduces nonsense-mediated decay (NMD). Moreover, we identified a BRCA1 nucleotide 249T>A/c.130T>A (p.Cys44Ser) mutation in another Greenlandic family. This mutation changes the amino acid residue cysteine, which is polar, to a serine, which is hydrophobic. Cys-44 is highly conserved [START_REF] Hansen | A common Greenlandic Inuit BRCA1 RING domain founder mutation[END_REF] and resides in the RING domain of BRCA1, which is involved in protein-protein interaction [START_REF] Wu | Identification of a RING protein that can interact in vivo with the BRCA1 gene product[END_REF][START_REF] Jensen | BAP1: a novel ubiquitin hydrolase which binds to the BRCA1 RING finger and enhances BRCA1-mediated cell growth suppression[END_REF]. The RING domain is characterized by a pattern of seven highly conserved cysteines and one highly conserved histidine residue forming two distinct Zn 2+ binding sites, termed site I and II [START_REF] Brzovic | BRCA1 RING domain cancerpredisposing mutations. Structural consequences and effects on protein-protein interactions[END_REF][START_REF] Brzovic | Structure of a BRCA1-BARD1 heterodimeric RING-RING complex[END_REF].

Mutations in the conserved residues in the RING domain disrupt the ubiquitin ligase activity of BRCA1 by interfering either with the heterodimerization between BRCA1 and BARD1 or by changing the ubiquitin ligase activity by disturbing the binding of E2 proteins like UbcH5c to the BRCA1/BARD1 complex [START_REF] Morris | Genetic analysis of BRCA1 ubiquitin ligase activity and its relationship to breast cancer susceptibility[END_REF][START_REF] Brzovic | Binding and recognition in the assembly of an active BRCA1/BARD1 ubiquitin-ligase complex[END_REF][START_REF] Xia | Enhancement of BRCA1 E3 ubiquitin ligase activity through direct interaction with the BARD1 protein[END_REF]. Indeed, in silico analysis using the SIFT, Polyphen or PMut software all regarded the BRCA1 p.Cys44Ser mutation as diseasecausing. We have moreover only observed the mutation in breast and/or ovarian cancer families, and not in 200 healthy adult Danish controls (blood donors). Other mutations have been reported on this position, including p.Cys44Phe, p.Cys44Tyr and p.Cys44Ala and functional and in silico studies supports that they are disease-causing [START_REF] Morris | Genetic analysis of BRCA1 ubiquitin ligase activity and its relationship to breast cancer susceptibility[END_REF][START_REF] Brzovic | Binding and recognition in the assembly of an active BRCA1/BARD1 ubiquitin-ligase complex[END_REF][START_REF] Abkevich | Analysis of missense variation in human BRCA1 in the context of interspecific sequence variation[END_REF].

The identification of the novel BRCA1 nucleotide 4803delCC/c.4684delCC mutation has led us to consider the optimal screening strategy in the Greenlandic population. Screening of individuals from Greenland for BRCA1/BRCA2 mutations have until now -as a first step -included examination of the BRCA1 nucleotide 234T>G/c.115T>G (p.Cys39Gly) mutation.

However, due to the finding in this report we now suggest that whole sequencing of the BRCA1 gene should be performed in high risk families. We have retrospectively screened the remaining thirty-one BRCA1 nucleotide 234T>G/c.115T>G (p.Cys39Gly) negative individuals, but have not found other disease-causing mutations in either BRCA1 or BRCA2 than the ones described in this paper.

In summary, we have identified two additional BRCA1 mutations in Greenlandic Inuits.

While the novel nucleotide 4803delCC/c.4684delCC mutation is found in an Inuit family, the nucleotide 249T>A/c.130T>A (p.Cys44Ser) mutation could be a Danish derived mutation.

We conclude that screening of Greenlandic Inuits with high risk for breast-and/or ovarian cancer should include sequencing of all BRCA1 exons.

  Identification of a novel BRCA1 nucleotide 4803delCC/c.4684delCC mutation and a nucleotide 249T>A/c.130T>A (p.Cys44Ser) mutation in two Greenlandic Inuit families: Implications for genetic screening of Greenlandic Inuit families with high risk for breast and/or ovarian cancer Thomas v. O. Hansen 1 , Lars Jønson 1 , Anders Albrechtsen 2 , Ane Y. Steffensen 1 , Eva Bergsten 3 , Torben Myrhøj 4 , Bent Ejlertsen 3 , and Finn C. Nielsen 1 .

Fig. 3

 3 shows the average IBD sharing between the 5 mutation carriers on chromosome 17. The probability of IBD sharing for the BRCA1 gene is shown in Fig. 4. Four out of the five carriers, including the Greenlandic individual, all have high probability of being IBD in the gene. Accordingly, we infer that the BRCA1 nucleotide 249T>A/c.130T>A (p.Cys44Ser) mutation represent a Danish founder mutation. The last individual only shows high probability with one of the other individual and this region is only 1-2 Mb long and too short to infer relatedness between the other three individuals.

Fig. 1

 1 Fig. 1 Family pedigrees. (A) shows the pedigree from family 97016, while (B) show the pedigree from family 84814. Breast and ovarian cancer are indicated as well as the age at diagnosis. Diagonal slash indicates deceased, while the proband is indicated with an arrow. Mutation positive individuals are indicated with +.

Fig. 2 .

 2 Fig. 2. Identification of the BRCA1 nucleotide 4803delCC/c.4684delCC and the nucleotide 249T>A/c.130T>A (p.Cys44Ser) mutations. DNA was purified from the patients and the BRCA1 and/or BRCA2 genes were amplified using intronic primer pairs flanking each exon. For total BRCA1/BRCA2 screening, the PCR products were pre-screened by high-resolution melting curve analysis followed by sequenced. The BRCA1 nucleotide 4803/c.4684delCC identified in family 97016 (A) and the nucleotide 249T>A/c.130T>A identified in family 84814 (B) are shown.

Fig. 3 .

 3 Fig. 3. Average identical by descent (IBD) sharing across chromosome 17 between all five p.Cys44Ser mutation carriers. Each orange dot represents the average IBD sharing for a single SNP. The BRCA1 gene is indicated as the green dot with the highest IBD sharing peak directly above it.

Fig. 4 .

 4 Fig. 4. Pairwise identical by descent (IBD) sharing probabilities at the BRCA1 gene between each possible pair of the five p.Cys44Ser mutation carriers. The four Danish and one Greenlandic individuals are indicated.

Acknowledgements Berit Bak Jensen, Christina Berantzino, Jesper Andreasen, Jesper Johansson, Karina Nørgaard, Lis Krüger, and Nina Ilsøe are thanked for BRCA1/BRCA2 screening of breast and/or ovarian cancer patients. The study was supported by the Neye Foundation.