Marc Autord
email: marc.autord@math.unicaen.fr

Patrick Dehornoy
email: dehornoy@math.unicaen.fr

ON THE DISTANCE BETWEEN THE EXPRESSIONS OF A PERMUTATION

Keywords: 1991 Mathematics Subject Classification. 20B30, 05E15, 20F55, 20F36 permutation, transposition, reduced expression, combinatorial distance, van Kampen diagram, subword reversing, braid relation

We prove that the combinatorial distance between any two reduced expressions of a given permutation of {1, ..., n} in terms of transpositions lies in O(n 4 ), a sharp bound. Using a connection with the intersection numbers of certain curves in van Kampen diagrams, we prove that this bound is sharp, and give a practical criterion for proving that the derivations provided by the reversing algorithm of [Dehornoy, JPAA 116 (1997) 115-197] are optimal. We also show the existence of length ℓ expressions whose reversing requires Cℓ 4 elementary steps.

This paper is about the various ways of expressing a permutation as a product of transpositions and the complexity of transforming one such expression into another. We consider both the absolute complexity ("combinatorial distance"), which deals with the minimal possible number of steps, and the more specific complexity ("reversing complexity"), which arises when one uses subword reversing, a certain prescribed strategy for transforming expressions.

Throughout the paper, we denote by [[1, n]] the set {1, 2, ..., n}, and by s i the transposition that exchanges i and i + 1. A well known result-see for instance [8]-states that, if π is any permutation of [[1, n]] and u, v are any two reduced (i.e., minimal length) expressions of π in terms of s 1 , ..., s n-1 , then one can transform u into v only using the braid relations s i s j s i = s j s i s j with |i -j| = 1, (I)

In this context, we define the combinatorial distance dist(u, v) of u and v to be the minimal number of braid relations needed to transform u into v. The standard proof for the finiteness of dist(u, v) relies on the so-called Exchange Lemma of Coxeter groups, and it leads to an exponential upper bound for dist(u, v) in terms of n. The first aim of this paper is to establish a polynomial upper bound, namely a sharp degree 4 one. Using "n-expression" as a shorthand for "expression representing a permutation of [[1, n]]", i.e., involving letters about s 1 , ..., s n-1 only, we prove

called separatrices, which are associated with the names of the strands involved in the successive crossings.

The latter notion, which seems of independent interest, provides general criteria for proving that a van Kampen diagram (i.e., in algebraic terms, a derivation by braid relations) is possibly optimal, i.e., it involves the minimal number of braid relations. In particular, Proposition 1.11 below states that a sufficient condition for a van Kampen diagram to be optimal is that any two separatrices cross at most once in it.

In the second part, we address similar complexity issues in the particular case of subword reversing. This is a specific strategy that, given two equivalent expressions u, v, returns a derivation of v from u by means of braid relations, i.e., equivalently, constructs a van Kampen diagram for the pair (u, v). We observe on a simple counter-example that the reversing method need not be optimal, but we deduce from the above approach based on separatrices a simple optimality criterion, namely Proposition 2.5 that states that a sufficient condition for the reversing method to be optimal for some pair (u, v) is that the so-called reversing diagram for (u, v) contains no digon, i.e., in algebraic terms, the reversing sequence from uv contains no ǫ-step-all technical terms are defined below.

Finally, we address the general question of the complexity of the reversing method. Frustratingly, the only upper bound we can establish at the moment is exponential-this does not contradict the polynomial upper bound of Proposition 1, since reversing need not be optimal. On the other hand, the optimal lower bound of Proposition 1 induces a similar lower bound in the case of reversing. What is more interesting is to consider the case of non-necessarily equivalent expressions. In that case, the reversing method still applies, and its complexity remains widely unknown. The relevant question is to determine the number compl (u, v) of elementary steps when one starts with expressions u, v of length ℓ (independently from the index n). When the lower bound of Proposition 1 is translated in this language, it leads to a quadratic lower bound compl (u, v) C ℓ 2 . This value is far from optimal. Proposition 2. There exists a positive constant C 3 such that, for each ℓ,

• there exist length ℓ expressions u, v satisfying compl (u, v) C 3 ℓ 4 .

(For ℓ large enough, we can take C 3 = 4/3.) At the moment, we do not know whether the above result is optimal.

It is likely that most results of this paper extend to finite Coxeter groups of other type. However, the arguments developed here heavily rely on specific properties of permutations, so how extending to Coxeter types other than A and B is not clear.

Remark. Most constructions developed in this paper in the case of permutations and their expressions in terms of transpositions can be extended to the case of positive braid and their decompositions in terms of Artin's generators σ i . Technically, the case of permutations corresponds to the particular case of the so-called simple braids, which are the divisors of Garside's fundamental braid ∆ n in the braid monoid B + n , see [START_REF] Garside | The braid group and other groups[END_REF] or [START_REF] Epstein | Word Processing in Groups[END_REF]Chap. 9]. Our reason for choosing the language of permutations here is that it is more widely accessible and it avoids introducing the general framework of braids whereas most results would involve simple braids exclusively. Indeed, it turns out that the worst cases known so far, in particular in terms of subword reversing, always involve simple braids. We have no explanation for this phenomenon.

We finally mention that the results of Section 1 are mainly due to the second author, whereas those of Section 2 are mainly due to the first author.

The combinatorial distance

Hereafter, a word u on the alphabet {s 1 , ..., s n-1 } is generically called an nexpression. Two n-expressions are called equivalent if they represent the same permutation of [ [1, n]]. Throughout the paper (in particular in view of the braid diagrams considered below), it is convenient that the product, both for words and for permutations, refers to reverse composition: uv means "u first, then v". An nexpression u is called reduced if the permutation represented by u has no expression that is shorter than u.

If u and v are equivalent reduced n-expressions, then, as recalled above, one can transform u into v using the braid relations of types I and II, and we denote by dist(u, v) the minimal number of braid relations needed to do it. In this section, we establish bounds for dist(u, v) when n grows to infinity.

1.1. An upper bound result. We begin with an upper bound result. To this end, we introduce one distinguished reduced expression, called normal, for each permutation, and we define a strategy that transforms any reduced expression into the (unique) normal expression that represents the same braid.

For each n-expression u, we define D u to be the n-strand braid diagram obtained by associating with the letter s i the pattern Definition. Define s j,i to be s j-1 s j-2 ...s i+1 s i for j > i, and to be the empty word ǫ for j = i. An n-expression is called normal if it has the form

(1.2) s 1,f (1) s 2,f (2) ... s n,f (n) , for some function f : [[1, n]] → [[1, n]] satisfying f (i) i for each i.
(The first factor s 1,f (1) is mentioned for symmetry, but is necessarily empty.)

Lemma 1.1. (i) Every normal expression is reduced. (ii) Each permutation of [[1, n]
] admits a unique normal n-expression.

Proof. (i) Assume that u has the form (1.2). Then, for each i, the ith strand crosses over no jth strand with j > i in the diagram D u . Therefore, any two strands cross at most once in D u , so u is a reduced expression.

(ii) For f satisfying f (i) i for each i, let n f be the largest m satisfying f (m) < m, if any, and 0 otherwise, and let π f be the permutation represented by the expression (1.2) associated with f . We prove that π f determines f using induction on n f . For n f = 0, the only possibility is that f (i) = i holds for each i, so the permutation π f is the identity. Assume now n f 1. By construction, we have π f (i) = i for i n f , and

π f (n f ) = f (n f ). Hence π f determines n f and f (n f ). Next, let f ′ be defined by f ′ (i) = f (i) for i < n f , and f ′ (i) = i for i n f . Then we have π f ′ = π f s n f ,f (n f ) , hence π f determines π f ′ . By construction, we have n f ′ n f -1.
By induction hypothesis, π f ′ determines f ′ , hence so does π f . Finally, f is determined by f ′ , n f , and f (n f ), hence by π f . For each (reduced) expression u, we denote by NF(u) the unique normal expression that is equivalent to u. We shall now define a strategy for transforming u into NF(u).

First, we concentrate on the last factor of the normal form. We have associated with every n-expression u a braid diagram D u . We shall assume that the pattern (1.1) is drawn in a rectangle that has width n -1 and height 1. So, if u is an n-expression of length ℓ, the diagram D u is drawn in an (n -1) × ℓ grid. It includes (n -1)ℓ squares of size 1, and it makes sense to count how many such squares lie on the left or on the right of a given strand. Lemma 1.2. For each n-expression u, define a(u) to be the number of plain squares lying on the right of the nth strand in the diagram D u . Then, for each reduced nexpression u, there exists an equivalent reduced expression vs n,k , with v an (n -1)expression, satisfying

(1.3) dist(u, vs n,k ) a(u).
For an induction it is enough to establish

Claim. If u is not of the form vs n,k with v an (n -1)-expression, there exists an n-expression u ′ satisfying dist(u, u ′ ) = 1 and a(u ′ ) < a(u).

Proof. Let p be the final position of the nth strand in D u . The hypothesis implies p < n holds as, otherwise, u itself would be an (n -1)expression and it could be expressed as us n,n . Then there exists a unique decomposition u = v s n,i s j w with v an (n -1)-expression, i < n, and j = i -1: we consider the first block of crossings s n,i in which the nth strand is the front strand, and the hypothesis on u means that, after that block, there still remains at least one crossing s j in which the nth strand is not the front strand, which means j = i -1. We consider the various possible values of j with respect to i. First, j = i -1 is excluded by hypothesis, whereas j = i would contradicts the hypothesis that u is reduced since the nth strand would cross the same strand twice. There remain two cases only. Case 1: |j -i| 2. Put u ′ = vs n,i+1 s j s i w. Then we have dist(u, u ′ ) = 1, and a(u ′ ) = a(u) -1, as shown in the following diagrams, which compare the contributions of the factors s i s j and s j s i to the right hand side area of the nth strand (the nth strand is in bold, and the squares contributing to a are in grey) case j i -2: case j i + 2:

j i j i
Case 2: j = i + 1. By construction this may happen only for i n -2. Let u ′ = vs n,i+2 s i s j s i w. Then we have again dist(u, u ′ ) = 1, and a(u ′ ) = a(u) -2, as shown in the diagram case j = i + 1: j i So the proof of the claim is complete, and the lemma follows.

Repeated uses of Lemma 1.2 lead to Lemma 1.3. For every reduced n-expression u of length ℓ, we have

(1.4) dist(u, NF(u)) n(n -1)ℓ/2.
Proof. We use induction on n. The result is obvious for n 3. Assume n 4. Assume that the last factor in NF(u) is s n,k . By Lemma 1.2, there exists a reduced (n -1)-expression v of length at most ℓ-actually of length exactly ℓ -(nk)satisfying dist(u, vs n,k ) a(u). By construction, we have a(u) (n -1)ℓ. On the other hand, the uniqueness of the normal form implies NF(u) = NF(v)s n,k . Hence, using the induction hypothesis, we find

dist(u, NF(u)) (n -1)ℓ + (n -1)(n -2)ℓ/2 = n(n -1)ℓ/2.
We immediately deduce Proposition 1.4. For all equivalent n-expressions u, v of length ℓ, we have

(1.5) dist(u, v) (n -1)(n -2)ℓ.
As every reduced n-expression has length at most n(n -1)/2, the upper bound O(n 4 ) of Proposition 1 follows.

Remark 1.5. Considering the rightmost strand in the argument of Lemma 1.2 is essential. Indeed, for each reduced expression u and each i such that s i u is not reduced, i.e., such that the ith and the i + 1st strands cross in D u , we can consider the area a i of the domain bounded by the top line and the ith and i + 1st strands before they cross. It is natural to wonder whether u can be transformed into an equivalent expression s i v in such a way that the parameter a i decreases at each step-thus obtaining a new proof of the Exchange Lemma. The answer is negative. Indeed, assume u = s 1 s 3 s 2 s 1 s 3 s 2 . Then the second and third strands cross in D u and s 2 u is not reduced: u is equivalent to s 2 s 3 s 2 s 1 s 2 s 3 . However, there is no way to apply a braid relation to u so as to decrease the area a 2 of the domain bounded by the second and third strands. Indeed, the two expressions at distance 1 from u are u ′ = s 3 s 1 s 2 s 1 s 3 s 2 and u ′′ = s 1 s 3 s 2 s 3 s 1 s 2 , which satisfy By construction, every crossing in a braid diagram D u involves two strands, each of which has an initial position that corresponds to an integer in [ [1, n]]. By considering the initial positions of the strands that cross there, we associate with each instance of a letter s i in an n-expression a well defined pair {p, q} in [ [1, n]] (2) , hereafter called its name.

a 2 (u) = a 2 (u ′ ) = a 2 (u ′′ ) = 9,
Definition. For each reduced n-expression u, we define S(u) to be the sequence composed of the names of the successive letters in u.

So, formally, S(u) is the sequence in [[1, n]] (2) recursively defined by S(ǫ) = ∅ (the empty sequence) and, using ⌢ for concatenation, S(u) = S(v) ⌢ ({p, q}), assuming that u = vs i and the strands that finish at positions i and i + 1 in D v are the pth and the qth ones, i.e., start at positions p and q, respectively.

Example 1.6. Let u n = s 1,1 s 2,1 ...s n,1 . Then u n is a reduced expression of the Coxeter element of S n , i.e., of the flip permutation φ that exchanges i and ni for each i. An easy induction gives (1.6) S(u n ) = ({1, 2}, {1, 3}, {2, 3}, ..., {n -2, n -1}{1, n}, {2, n}, ..., {n -1, n}).

Symmetrically, let v n be the expression obtained from u n by reversing the order of the factors and flipping their entries, i.e., v n = s n,1 s n,2 ...s n,n-1 . Then v n is another reduced expression of φ, and we find

(1.7) S(v n ) = ({n -1, n}, ..., {2, n}, {1, n}, {n-2, n -1}, ..., {2, 3}, {1, 3}, {1, 2}) : so S(v n ) is the sequence obtained by reversing the entries of S(u n ).
By construction, if u is a reduced n-expression, the pair {p, q} occurs in S(u) if and only if the strands starting at positions p and q cross in the diagram D u , hence if and only if {p, q} is an inversion of the permutation represented by u. Hence, if u, v are equivalent reduced n-expressions, the pairs occurring in S(u) and in S(v) coincide, and S(v) is a permuted image of S(u).

We shall see now that comparing the sequences S(u) and S(v) leads to a lower bound on the combinatorial distance between u and v. 2) ) such that the order of the pairs {p, q}, {p, r}, {q, r} (resp. the order of {p, q} and {p ′ , q ′ }) is not the same in S and S ′ . Proposition 1.7. For all equivalent n-expressions u, v, we have

Definition. If S, S ′ are enumerations of [[1, n]] (2) , we denote by I 3 (S, S ′ ) (resp. I 2,2 (S, S ′ )) the number of triples {p, q, r} in [[1, n]] (3) (resp. the number of pairs of pairs {{p, q}, {p ′ , q ′ }} in [[1, n]] (2,
(1.8) dist(u, v) I 3 (S(u), S(v)) + I 2,2 (S(u), S(v)).
More precisely, every derivation from u to v contains at least I 3 (S(u), S(v)) relations of type I and I 2,2 (S(u), S(v)) relations of type II.

Proof. We first consider the case dist(u, v) = 1, i.e., the case when v is obtained from u by applying one braid relation. Assume first that v is obtained by applying a type I relation s i s i+1 s i = s i+1 s i s i+1 . Then there exists a unique triple {p, q, r}, namely the names of the three strands involved in the transformation, such that the sequence S(v) is obtained from S(u) by replacing the subsequence {p, q}, {p, r}, {q, r} with {q, r}, {p, r}, {p, q}-see Figure 1 below for an illustration. So the order of the three pairs arising from {p, q, r} has changed between S(u) and S(v). On the other hand, any other triple in [[1, n]] (3) has at most two elements in common with {p, q, r}, and the order of the three pairs arising from that triple is the same in S(u) and S(v). Hence, we have I 3 (S(u), S(v)) = 1 in this case. On the other hand, any pair of pairs in [[1, n]] (2,2) contains at most one of the three pairs {p, q}, {p, r}, {q, r} and, therefore, the order of this pair is not changed from S(u) and S(v). Hence, we have I 2,2 (S(u), S(v)) = 0 in this case. Assume now that v is obtained by applying a type II relation

s i s j = s j s i with |j -i| 2.
Then there exists a unique pair of pairs {p, q}, {p 2) , namely the names of the four strands involved in the transformation, such that the sequence S(v) is obtained from S(u) by replacing the subsequence {p, q}, {p ′ , q ′ } with {p ′ , q ′ }, {p, q}. So the order of the two considered pairs has changed between S(u) and S(v). On the other hand, any other pair of pairs in [[1, n]] (2,2) contains at most one of the two pairs {p, q}, {p ′ , q ′ }, and its order is the same in S(u) and S(v). Hence, we have

′ , q ′ } in [[1, n]] (2,
I 2,2 (S(u), S(v)) = 1. Moreover, any triple in [[1, n]] (3)
gives rise to a triple of pairs that contains at most one of {p, q}, {p ′ , q ′ }. Hence the order of the three pairs in this triple has not changed from S(u) and S(v), and we have I 3 (S(u), S(v)) = 0.

We conclude that, in every case, the quantity I 3 (S(u), S(v)) + I 2,2 (S(u), S(v)) changes by not more than one (and even by exactly one) when one braid relation is applied. This clearly implies (1.8).

We can now complete the proof of Proposition 1.

Corollary 1.8. For each n, there exist reduced n-expressions u, v satisfying

(1.9) dist(u, v) 1 8 n 4 + O(n 3 ).
Proof. Consider the expressions u n , v n of Example 1.6. As observed above, the sequences S(u n ) and S(v n ) are mirror images of one another. It follows that each triple {p, q, r} in [[1, n]] (3) contributes 1 to the parameter I 3 , leading to

I 3 (S(u n ), S(v n )) = #([[1, n]] (3) ) = n 3 .
Similarly, each pair of pairs {{p, q}, {p 2) contributes 1 to the parameter I 2,2 , giving

′ , q ′ }} in [[1, n]] (2,
I 2,2 (S(u n ), S(v n )) = #([[1, n]] (2,2) ) = 1 2 n 2 n -2 2 = 3 n 4 .
Owing to the last sentence in Proposition 1.7, we also deduce from the above computation the result that the number of type I braid relations occurring in every derivation of v from u is at least n 3 /6 + O(n 2 ).

In the context of Proposition 1.7, it is natural to wonder whether (1.8) is always an equality, as it turns out to be in simple cases. Question 1.9. Does the equality

(1.10) dist(u, v) = I 3 (S(u), S(v)) + I 2,2 (S(u), S(v))
hold for all equivalent n-expressions u, v?

So far we have not been able to obtain any answer. In particular, computer tries failed to find expressions disproving the equality (1.10).

Remark 1.10. A result similar to Proposition 1.7 can be obtained by simply counting the inversion number I(S(u), S(v)) of the sequences S(u) and S(v), i.e., the total number of pairs of pairs whose order is changed. One easily checks that I(S(u), S(v)) is changed by three when a type I relation is applied, and by one in the case of a type II relation, thus leading to dist(u, v) I(S(u), S(v))/3. Also, it can be mentionned that using areas in braid diagrams as in Section 1.1 can also lead to lower bounds on the combinatorial distance. Indeed, it is easy to check that applying one braid relation can change such areas by a bounded factor K only, leading to inequalities of the generic form

dist(u, v) |area(D u ) -area(D v )|/K.
1.3. Van Kampen diagrams. Proposition 1.7 and the approach of Section 1.2 leads to a nice geometric criterion for proving that a derivation between two reduced expressions u, v of a permutation π is possibly optimal, i.e., that it realizes the combinatorial distance dist(u, v) between u and v.

Assume that u, v are equivalent expressions. A van Kampen diagram for (u, v) is a planar connected diagram K consisting of finitely many adjacent tiles of the two types type I:

s j s i s i s j s j s i with |i -j|=1, type II: s j s i s j s i with |i -j| 2,
and such that the boundary of K consists of two paths labeled u and v. Because of the orientation of the edges of the tiles, such a diagram has exactly one initial vertex (source) and one terminal vertex (sink), and two boundary paths labeled u and v from the source to the sink. It is standard-see for instance [START_REF] Lyndon | Combinatorial Group Theory[END_REF] or [START_REF] Epstein | Word Processing in Groups[END_REF]-that, if u, v are reduced expressions, then v can be derived from u using braid relations if and only if there exists a van Kampen diagram for (u, v). See Figure 2 for an example. More precisely, if v can be derived from u using N braid relations, then there exists a van Kampen diagram for (u, v) that contains N tiles, and conversely. So, we have the natural notion of an optimal (or minimal) van Kampen diagram: Definition. Assume that K is a van Kampen diagram for (u, v). We say that K is optimal if the number of tiles in K equals the combinatorial distance dist(u, v).

In other words, a van Kampen diagram is declared optimal if there exists no smaller (i.e., containing less tiles) diagram with the same boundary. Our aim in the sequel will be to describe criteria for recognizing that a van Kampen diagram is possibly optimal. The first idea is to use names. Assume that K is a van Kampen diagram for a pair (u, v). Then we can unambiguously attribute a name with every tile of K. First, we attribute a name to each edge of K. Let e be such an edge. It follows from the definition of a van Kampen diagram that there exists at least one path that connects the source of K to any vertex V , and at least one path that connects V to the sink of K. Hence there is a path γ that connects the source of K to its sink and contains e. Then the successive labels of the edges of γ make an expression w, which is certainly equivalent to u (and v) since, by construction, there is a van Kampen diagram for (u, w), namely the subdiagram of K bounded by γ and the path labeled u. Then, as in Section 1.2, we attribute a name to each letter of w, and copy these names on the corresponding edges of γ. In this way, we have given a name to e which is a certain pair in [[1, n]] (2) . We claim that this name only depends on e, and not on the choice of the path γ. As any two paths γ, γ ′ correspond to equivalent expressions w, w ′ , it is enough to consider the case when w and w ′ are deduced from one another using one braid relation, and the result is then obvious. Then, we observe that the names occurring on the edges of an elementary tile can be of two types only, namely those displayed in Figure 1. type II:

{p,q} {p ′ ,q ′ } {p,q} {p ′ ,q ′ } Figure 1.
Giving names to the tiles in a van Kampen diagram: the left tile is called {p, q, r}, the right one is called {{p, q}, {p ′ , q ′ }}.

Definition. (See Figures 1 and2.) Assume that K is a van Kampen diagram for (u, v). We define the name of a tile in K as follows:

• for a type I tile, it is the (unique) triple {p, q, r} of [[1, n]] (3) such that the names of the border edges are {p, q}, {p, r}, and {q, r};

• for a type II tile, it is the (unique) pair {{p, q}, {p ′ , q ′ }} of [[1, n]] (2,2) such that the names of the border edges are {p, q} and {p ′ , q ′ }.

Then the optimality criterion is Proposition 1.11. A van Kampen diagram in which any two tiles have different names is optimal.

Proof. The proof of Proposition 1.7 shows that, if K contains exactly one tile named {p, q, r}, then the order of {p, q}, {p, r}, {q, r} has changed between S(u) and S(v). Hence, under the hypothesis, if K contains N hexagons with pairwise distinct names, then we have I 3 (S(u), S(v))

N . Similarly, if K contains exactly one tile named {{p, q}, {p ′ , q ′ }}, then the order of {p, q} and {p ′ , q ′ } has changed between S(u) and S(v). So, if K contains N ′ squares with pairwise distinct names, then we have

I 2,2 (S(u), S(v)) N ′ . Applying Proposition 1.7, we deduce dist(u, v) N + N ′ , hence dist(u, v) = N + N ′ . {{1,3},{2,4}} {{1,2},{3,4}} Σ 1,2 Σ 1,3 Σ 2,3 Σ 1,4 Σ 2,4 Σ 3,4 {1,2,3} {2,3,4} {1,3,4} {1,2,4} s 3 s 1 s 2 s 2 s 3 s 1 s 2 s 3 s 1 s 2 s 2 s 1 s 3 s 2 s 1 s 3 s 1 s 3 s 2 s 2 s 3 s 1 {{1,4},{2,3}} {{1,4},{2,3}} {{1,2},{3,4}} {{1,3},{2,4}} s 3 s 1 s 2 s 2 s 3 s 1 s 3 s 1 s 1 s 3 s 2 s 3 s 2 s 1 s 1 s 3 s 2 s 2 s 1 s 3 s 3 s 1 s 2 s 2 s 3 s 1 Σ 1,3 Σ 2,4 Σ 3,4 {2,3,4} {1,2,4} {1,3,4} {1,2,3} Figure 2.
Two van Kampen diagrams for the pair (s 1 s 2 s 1 s 3 s 2 s 1 , s 3 s 2 s 3 s 1 s 2 s 3 ): a tiling by squares and hexagons witnessing the equivalence of the two expressions. Indexed by pairs, the separatrices are drawn in grey, inducing a name for every tile. In the top diagram, no two tiles share the same name, hence the diagram is optimal, and the combinatorial distance is 6; by contrast, two tiles in the bottom diagrams share the name {{1, 4}, {2, 3}}, hence the diagram cannot be optimal.

1.4. Separatrices. Having given names to the edges of a van Kampen diagram, we can now draw curves that connect the edges with the same name.

Definition. Assume that K is a van Kampen diagram for (u, v), and {p, q} is an inversion of the permutation π represented by u and v, i.e., we have (qp)(π(q)π(p)) < 0. The {p, q}-separatrix in K is the curve Σ p,q obtained by connecting the middle points of the (diametrally opposed) edges named {p, q} inside each tile, oriented so that the edges of u are crossed first, and those of v last.

If {p, q} is not an inversion of the involved permutation, we may consider that Σ p,q still exists, but it lies outside the diagram and cuts no edge. So, by definition, separatrices are obtained by connecting patterns of the form Σ p,q Σ p,r Σ q,r for type I, and

Σ p,q Σ p ′ ,q ′
for type II.

To make Σ p,q unique, we might require in addition that the curve we choose inside each tile is the image of the median lines under the affine transformation that maps a regular polygon to the considered tile (provided the latter is convex).

Then we have the following optimality criterion involving separatrices.

Proposition 1.12. A van Kampen diagram in which any two separatrices cross at most once is optimal.

Proof. By construction, for each triple {p, q, r} in [[1, n]] (3) , the only place where Σ p,q and Σ p,r may intersect is a type I tile named {p, q, r} and, conversely, the three separatrices appearing in a type I tile pairwise cross one another. Similarly, for each {{p, q}, {p 2) , the only place where Σ p,q and Σ p ′ ,q ′ may intersect is a type II tile named {{p, q}, {p ′ , q ′ }}, and, conversely, the two separatrices do cross in such a type II tile. Summarizing, the number of times two separatrices Σ p,q and Σ p ′ ,q ′ cross is exactly the number of type I tiles named {p, q, p ′ , q ′ } if the set {p, q, p ′ , q ′ } has three elements, and the number of type II tiles named {{p, q}, {p ′ , q ′ }} if it has four elements. Hence all tiles in K have pairwise different names if and only if any two separatrices cross at most once in K, and we apply Proposition 1.11.

′ , q ′ }} in [[1, n]] (2,

Subword reversing

Up to now, we considered the combinatorial distance between two expressions u, v representing some permutation, i.e., the minimal number of braid relations needed to transform u into v. We now address a related, but different question, namely the number of braid relations needed to transform u into v when one uses the specific strategy called subword reversing [START_REF] Dehornoy | Groups with a complemented presentation[END_REF][START_REF] Dehornoy | On completeness of word reversing[END_REF]. The latter is known to solve the word problem, i.e., to provide a step-by-step transformation of u into v by means of braid relations when this is possible, i.e., when u and v are equivalent reduced expressions.

Investigating the optimality of the reversing method, i.e., comparing the number of braid relations used by subword reversing and the combinatorial distance, is a natural question. Little is known at the moment. Here, we shall establish several partial results. We observe in particular that the reversing method need not be optimal but, using the geometric criteria of Sections 1.3 and 1.4, we characterize cases when reversing turns out to be optimal. Also, in a slightly different context of non-equivalent initial expressions, we shall prove that there exist length ℓ expressions u, v whose reversing require using O(ℓ 4 ) braid relations, which is not redundant with Proposition 1.

2.1. Subword reversing and reversing diagrams. We recall that an n-expression is a word on the alphabet {s 1 , ..., s n-1 }. Hereafter, we introduce a second alphabet {s 1 , ..., s n-1 } which is a formal copy of the previous one. A word over the extended alphabet {s 1 , ..., s n-1 , s 1 , ..., s n-1 } will be called an extended n-expression.

For each extended expression u, we denote by u the extended expression obtained from u by reversing the order of the letters and exchanging s i and s i everywhere. So, for instance, we have s 1 s 2 = s 2 s 1 .

We now introduce a binary relation (or rewrite rule) on extended expressions.

Definition. If w, w ′ are extended expressions, we declare that w w ′ holds if w ′ is obtained from w by replacing some subword s i s j either by s j s i s j s i (if |i -j| = 1 holds), or by s j s i (if |i -j| 2 holds), or by the empty word ǫ (if j = i holds). A finite sequence (w 0 , ..., w N ) is called a reversing sequence if w k w k+1 holds for each k. Finally, we say that w reverses to w ′ if there exists a reversing sequence (w 0 , ..., w N ) satisfying w 0 = w and w N = w ′ .

The principle of reversing is to push the letters s i to the right, and the letters s j to the left, until no subword s i s j remains. For instance, s 1 s 2 s 1 s 2 s 1 s 2 reverses to the empty word, as we have

( * ) s 1 s 2 s 1 s 2 s 1 s 2 s 1 s 2 s 1 s 2 s 1 s 2 s 2 s 2 s 2 s 2 s 2 s 1 s 2 s 1 s 1 s 2 s 1 s 1 s 1 s 1 s 1 s 1 s 2 s 1 s 1 s 2 s 2 s 1 s 1 s 1 s 1 s 1 s 1 s 2 s 2 s 2 s 2 s 2 s 2 s 2 ǫ,
where, at each step, the subword that will be reversed has been written in bold.

As will become clear below, a reversing sequence from uv to the empty word provides a distinguished way of transforming u into v by means of braid relations and, therefore, there exists an associated van Kampen diagram. Now, it follows from the particular definition of subword reversing that the associated van Kampen diagrams have specific properties, namely they can essentially be drawn on a rectangular grid, a specific point that will be important in the sequel.

These diagrams that are essentially van Kampen diagrams will be called reversing diagrams. As a van Kampen diagram, a reversing diagram consists of edges labeled by letters s i . The specific point is that, in a reversing diagram, all edges are either horizontal right-oriented edges and vertical down-oriented edges, and that, in addition to the latter, there may exist ǫ-labeled arcs. Assume that (w 0 , ..., w N ) is a reversing sequence, hence a sequence of extended expressions containing both types of letters s i and s j . First, we draw a connected path indexed by the successive letters of w 0 by attaching a horizontal arrow si → with each letter s i , and a vertical arrow ↓ si with each letter s i . Then, we inductively complete the diagram as follows. Assume that one goes from w k-1 to w k by reversing some subword s i s j . By induction hypothesis, the latter subword s i s j corresponds to an open pattern si sj in the diagram. Then we complete that pattern with new arrows, according to the rule In this way, we associate with every reversing sequence a reversing diagram. Conversely, it is easy to see that, starting with a diagram as above, we can recover a (not necessarily unique) reversing sequence by reading the labels of the various paths going from the bottom-left corner to the top-right corner, and using the convention that a vertical s i -labeled edge contributes s i .

s i sj → s i s j s j s i s i s j for |i-j|=1, ( type
By construction, subword reversing may be applied to any initial word consisting of letters s i and s i , and not only to words of the form uv where u and v are equivalent reduced expressions. So there is no ambiguity in the following notion.

Definition. If u, v a are expressions, the reversing diagram for (u, v) is the reversing diagram starting with the word uv.

By construction, the reversing diagram for the pair (u, v) starts with a vertical down-oriented path labeled u and a horizontal right-oriented path labeled v starting from a common source. For instance, the diagram of Figure 3 is the reversing diagram for the pair (s

1 s 2 s 1 , s 2 s 1 s 2 ).
By construction, a reversing diagram becomes a van Kampen diagram when all ǫ-arcs are collapsed-but we do not do it, and keep the diagrams as they are now, insisting that they are drawn in a rectangular grid. A reversing diagram contains three types of tiles:

-type I tiles, which are hexagons, and correspond to type I braid relations, -type II tiles, which are squares, and correspond to type II braid relations, -type III tiles, which are digons, and correspond to free group relations s i s i = 1. The latter will be called trivial.

The connection between subword reversing and the problem of recognizing equivalent reduced expressions of a permutation is given by the following result. Proposition 2.2. [3] (i) For all reduced expressions u, v, there exists a unique pair of reduced expressions u ′ , v ′ such that uv reverses to v ′ u ′ .

(ii) Two reduced expressions u, v represent the same permutation if and only if uv reverses to the empty word.

In the case of (ii), one implication is clear: by construction, a reversing sequence from uv to the empty word gives a reversing diagram for (u, v) that concludes with ǫ-arcs everywhere on the bottom and the right, hence, after collapsing the ǫ-edges, it gives a van Kampen diagram for (u, v), thus proving that u and v are equivalent. The converse implication is not obvious, as not every van Kampen diagram comes from a reversing diagram. The specific point is that, in a reversing diagram, two edges at most start from any vertex, a property that fails in the top diagram of Figure 2: so that diagram is certainly not associated with a reversing. The proof of Proposition 2.2-which actually extends to arbitrary braids-relies on the so-called Garside theory of braids [START_REF] Garside | The braid group and other groups[END_REF][START_REF] Epstein | Word Processing in Groups[END_REF].

In terms of reversing diagrams, the situation is as follows. In the particular case when u and v are equivalent reduced expressions, the reversing diagram for (u, v) finishes for ǫ-labeled arcs everywhere, and collapsing all these ǫ-labeled arcs yields a van Kampen diagram for (u, v). In general, if u, v are arbitrary expressions, then the reserving diagram for (u, v) is still finite, and it finishes with arrows forming a word of the form v ′ u ′ where u ′ , v ′ are two expressions that need not be empty. Then collapsing all the ǫ-labeled arcs yields a van Kampen diagram for the pair (uv ′ , vu ′ ). It can be shown that, if u and v are reduced, then uv ′ and vu ′ are reduced and equivalent-the latter point is obvious as, by construction, the reversing diagram for (u, v) provides a van Kampen diagram for (uv ′ , vu ′ )-and the permutation represented by uv ′ and vu ′ is the least upper bound of the permutations represented by u and v with respect to the weak order of S n [START_REF] Björner | Combinatorics of Coxeter groups[END_REF].

In every case, the number of nontrivial tiles in the reversing diagram or, equivalently, the number of nontrivial steps in an associated reversing sequence, is well defined.

Definition. Assume that u, v are reduced expressions. The reversing complexity of (u, v), denoted compl (u, v), is the number of nontrivial tiles in the reversing diagram for (u, v).

Equivalently, the reversing complexity compl (u, v) is the number of nontrivial steps in a reversing sequence from uv to a word of the form v ′ u ′ . By the above remarks, a reversing diagram for (u, v) with N nontrivial tiles provides a van Kampen diagram for (uv ′ , vu ′ ) with N tiles, where v ′ u ′ is the final word of the reversing process. So we always have (2.1) dist(uv ′ , vu ′ ) compl (u, v).

In particular, when we start with equivalent reduced expressions u, v, we have

(2.2) dist(u, v) compl (u, v),
since, in this case, the final expressions u ′ and v ′ are empty by Proposition 2.2(ii). We shall now discuss the converse inequality, i.e., the question of whether subword reversing, viewed as a particular strategy for finding derivations between equivalent expressions of a permutation, is efficient, or even possibly optimal. Proposition 2.3. Subword reversing is not always optimal: There exist equivalent reduced expressions u, v satisfying dist(u, v) < compl (u, v).

Proof. Consider the 4-expressions u = s 1 s 2 s 1 s 3 s 2 s 1 and v = s 3 s 2 s 3 s 1 s 2 s 3 , two expressions of the flip permutation φ 4 of S 4 . Together with Proposition 1.11, the top diagram in Figure 2 gives dist(u, v) = 6. On the other hand, the reversing diagram of Figure 4 gives compl (u, v) = 8.

2.

2. An optimality criterion. Despite the negative result of Proposition 2.3, experiments show that subword reversing is often an efficient strategy. What we do now is to establish sufficient criteria for recognizing that reversing is possibly optimal. Of course, we shall say that a reversing diagram D is optimal if the van Kampen diagram obtained by collapsing the ǫ-labeled arcs in D is optimal, i.e., if it realizes the combinatorial distance between the boundary expressions. Proof. Assume that D is the reversing diagram for (u, v). By definition, the separatrices of D start from the edges corresponding to u, i.e., here, from the left. Then an induction on the number of tiles shows that only the following orientations may appear in the tiles of D.

s 1 s 2 s 3 s 1 s 1 s 1 s 2 s 2 s 1 s 1 s 2 s 3 s 3 s 3 s 2 s 1 s 3 s 2 s 2 s 3 s 1 s 3 s 2 s 1 s 2 s 3 s 1 s 2 s 1 s 1 s 1 s 2 s 3 s 2 s 2 s 1 Σ 2,3 Σ 1,4
Σ Σ Σ Σ ′′ Σ ′ Σ ′
Hence every vertical edge of D is crossed by a separatrix from left to right, and every horizontal edge is crossed from bottom to top. Moreover, we see that digons are the only tiles that can change the orientation of a separatrix from horizontal to vertical-whereas only hexagons can change the orientation from vertical to horizontal. Also we see that, if two separatrices cross in a tile, then, when entering that tile, at least one of them is vertical. Now assume that two separatrices Σ, Σ ′ cross at least twice in D, Two cases may occur, according to whether the names of these separatrices involve three or four integers. Assume first that there exist p, q, r satisfying Σ = Σ p,q and Σ ′ = Σ p,r . Then Σ and Σ ′ can cross only in hexagons named {p, q, r}, in which case, putting Σ ′′ = Σ q,r , the separatrices Σ and Σ ′′ , as well as Σ ′ and Σ ′′ , cross too. Let H 1 (resp. H 2 ) be the first (resp. second) hexagon where Σ, Σ ′ and Σ ′′ cross. Without loss of generality, we may assume that Σ is horizontal when entering H 1 (hence also when exiting it) and that Σ ′ is vertical when exiting H 1 (hence also when entering it). Then Σ ′ remains above Σ (measured from the bottom of the diagram)-with Σ ′′ lying in between-until they enter the hexagon H 2 . Therefore, the only possibility is that Σ ′ is horizontal when entering H 2 (from the left), whereas Σ is vertical when entering H 2 (from the bottom). This is possible only if a digon changes the orientation of Σ from horizontal to vertical between H 1 and H 2 .

Assume now that there exist p, q, p ′ , q ′ satisfying Σ = Σ p,q and Σ ′ = Σ p ′ ,q ′ . Then Σ and Σ ′ can cross only in squares named {{p, q}, {p ′ , q ′ }}. Let S 1 (resp. S 2 ) be the first (resp. second) square where Σ and Σ ′ cross. Without loss of generality, we can assume that Σ is horizontal after (and before) S 1 , and Σ ′ is vertical. Then, as in the case of hexagons, Σ ′ remains above Σ until they enter the square S 2 . Therefore, Σ ′ is horizontal when entering S 2 (from the left), whereas Σ is vertical when entering S 2 (from the bottom). Hence a digon changes the orientation of Σ from horizontal to vertical between S 1 and S 2 .

So, in any case, two separatrices may cross twice only if there is a digon in D. Then we apply Proposition 1.12.

The previous result can be improved by showing that some digons are harmless and can be ignored. Indeed, consider a pattern of the form s i s i+1 s i .

s i s j s i s j s j s i .
Unsing such tiles amounts to replacing two adjacent tiles with one unique tile of the new type, but they do not change anything in the rest of the diagram. In this way, we obtain a new type of reversing diagrams that we call compacted. Note that the compacted diagram associated with an initial expression uv need not be unique, as there may be several ways of grouping the tiles, see Figure 5. However, as the situation after a tile of type I' or I" is exactly the same as the situation after the corresponding type I tile followed by a type III tile, the number of nontrivial tiles is the same in any diagram associated with a given initial pair (u, v).

The expected improvement of Proposition 2.4 is Proposition 2.5. A compacted reversing diagram containing no digon, i.e., containing only tiles of types I, I', I", and II, is optimal.

Proof. The new tiles of type I' and I" do not change the orientation of separatrices. Indeed, the corresponding possibilities are None of these tiles changes the horizontal-vertical orientation of the separatrices, and, therefore, their appearing in a reversing diagram does not affect the argument used in the proof of Proposition 2.4.

s 1 s 2 s 3 s 1 s 2 s 1 s 3 s 2 s 3 s 1 s 2 s 3 Σ 2,3 Σ 1,4 s 1 s 2 s 3 s 1 s 2 s 1 s 3 s 2 s 3 s 1 s 2 s 3 Σ 2,3 Σ 1,4
An application of the above criterion will be mentioned in Remark 2.11 below.

Upper bounds.

Very little is known about the reversing complexity in general. In particular, the following conjecture, which is the natural counterpart of Proposition 1. [START_REF] Dehornoy | On completeness of word reversing[END_REF], remains open at the moment-see [START_REF] Autord | Aspects algorithmiques du retournement de mot[END_REF] for partial results.

Conjecture 2.6. For all n-expressions u, v of length ℓ, the reversing complexity compl (u, v) lies in O(n 2 ℓ).

Even the weaker result of the reversing complexity being polynomial is not known. By adapting the method used for [5, Prop. 3], one comes up with the weak result that, if u, v are length ℓ expressions, then dist(u, v) C • 81 ℓ holds for some constant C. Using a careful analysis of separatrices, one can obtain the following improvement. As the argument is complicated and, at the same time, the result seems far from optimal, we skip the proof and refer to [START_REF] Autord | Aspects algorithmiques du retournement de mot[END_REF] for details.

Remark. The index n does not appear in Proposition 2.7. This reflects the fact that, although the maximal reversing complexity between two n-expressions of length ℓ increases with n and ℓ, it does not increase indefinitely: if we denote by N (n, ℓ) the maximal reversing complexity between two n-expressions of length ℓ, then, for each ℓ, the value of N (n, ℓ) is constant for n 2ℓ. This is due to the fact that, when n is too large with respect to ℓ, the indices of the transpositions s i occurring in an n-expression cannot cover the whole of [ [1, n]] and commutation relations of type II occur. Here again, we refer to [START_REF] Autord | Aspects algorithmiques du retournement de mot[END_REF] for more details.

2.4.

A lower bound for the reversing complexity. The n-expressions used in the proof of Proposition 1.7 to establish the inequality (1.9) have length ℓ = n(n -1)/2 so that, in this way, we obtain for infinitely many values of ℓ equivalent reduced expressions of length ℓ that satisfy dist(u, v) ℓ(ℓ -1)/2, hence, a fortiori,

(2.3) compl (u, v) ℓ(ℓ -1) 2 .
Question 2.8. Can one construct a sequence (u ℓ , v ℓ ) of pairwise equivalent reduced expressions of length ℓ such that compl (u ℓ , v ℓ ) is more than quadratic in ℓ?

We leave Question 2.8 open, but we now address another related question and establish a result that illustrates how complicated the reversing process may be. for ℓ large enough.

We begin with an auxiliary lemma. Hereafter we write w k w ′ if there is a length k reversing sequence from w to w ′ , not counting trivial steps of type III.

Lemma 2.10. For i, p 1, put a i,p = s i+p-1 s i+p-2 ...s i , b i,p = s i s i+1 ...s i+p-1 , c i,p = a i,p a i+1,p , and d i,p = b i+1,p b i,p . Then, for all i, p, we have b i,p a i+1,p Np a i,p+1 b i,p+1 , (2.4)

d i,p c i+2,p N ′ p c i,p+2 d i,p+2 , (2.5) with N p = p 2 + p -1 and N ′ p = 4p 2 + 8p -3.
i,1 b i+1,1 1 a i,2 b i,2 , a restatement of s i s i+1 1 s i+1 s i s i+1 s i . Assume p 2.
Applying the induction hypothesis once, plus one reversing step of type I and one step of type III-or one type I' step instead-and 2p -1 steps of type II, we obtain

b i,p a i+1,p = s i+p-1 b i,p-1 s i+p b i,p-1 s i+p b i,p-1 s i+p a i+1,p-1 p-1 s i+p-1 s i+p b i,p-1 a i+1,p-1 b i,p-1 a i+1,p-1 b i,p-1 a i+1,p-1 Np-1 s i+p-1 s i+p s i+p-1 s i+p s i+p-1 s i+p a i,p b i,p 1 s i+p s i+p+1 s i+p s i+p+1 a i+1,p s i+p+1 a i+1,p s i+p+1 a i+1,p b i,p 0 s i+p s i+p+1 s i+p a i+1,p-1 s i+p a i+1,p-1 s i+p a i+1,p-1 b i,p p s i+p s i+p+1 a i+1,p-1 s i+p b i,p = a i,p+1 b i,p+1 ,
where, in each case, the factors that are about to be reversed are marked in bold. We deduce

N p = N p-1 + 2p = p 2 + p -1.
The computation for (2.5) is illustrated in Figure 6. Using (2.4) four times, plus 4p + 1 type II steps, we obtain: From there, we apply (2.5) repeatedly: after ℓ -1 applications, we obtain A careful bookkeeping shows that the total number of reversing steps involved in the process is (8ℓ 4 -23ℓ 2 + 9ℓ + 12)/6, hence Θ(ℓ 4 ) as announced. With Proposition 2.9, we prove that compl (u, v) can be quartic in the length of u and v. We conjecture this lower bound is also an upper bound, but have no proof of this result so far. The problem is that we have no control on the number of hexagons and digons that may occur in a reversing diagram. There is a quadratic upper bound on the lengths of the final expressions u ′ , v ′ that may arise from some initial pair (u, v) of length ℓ expressions, but this does not directly lead to a bound on the number of type I reversing steps used (the only ones that increase the length) because some subsequent type III steps might erase the letters so created. Remark 2.12. As mentioned in the introduction, most results of this paper extend to positive braids. For instance, the optimality criterion of Proposition 1.12 extends to positive braids at the expense of adding a notion of rank in the definition of separatrices: in the braid diagram associated with a permutation, i.e., with a simple braid, any two strands cross at most once, and we introduce one separatrix Σ p,q only. For the case of arbitrary positive braids, we should introduce several separatrices for pairs of strands that cross more than one time, Σ (k) p,q being associated with the kth intersection of the strands p and q. As for subword reversing, it works in the general braid case exactly as in the case of simple braids, i.e., of permutations. Experiments show that the worst cases in terms of complexity arise with simple braids. So we have no better result in the general braid case than in the particular permutation case.

s

  from top to bottom the elementary patterns corresponding to the successive letters of u. When we speak of the pth strand in D u , we refer to the strand that starts at the pth position from the left on the top line. It is well known that u is a reduced expression if and only if any two strands in D u cross at most once[START_REF] Epstein | Word Processing in Groups[END_REF] Chap. 9].

Figure 4 .

 4 Figure 4. Reversing diagram for s 1 s 2 s 3 s 1 s 2 s 1 s 3 s 2 s 3 s 1 s 2 s 1 . There are eight nontrivial tiles (four type I hexagons and four type II squares), giving compl (s 1 s 2 s 1 s 3 s 2 s 1 , s 3 s 2 s 3 s 1 s 2 s 1 ) = 8. Collapsing the ǫedges in the above diagram yields the bottom van Kampen diagram of Figure 2. The failure of optimality is witnessed by the two intersections of the separatrices Σ 1,4 and Σ 2,3 .

Figure 5 .

 5 Figure 5. Two slightly different ways of compacting the reversing diagram of Figure 4.

Proposition 2 . 7 .

 27 If u, v are expressions of length ℓ, then we have dist(u, v) C •9 ℓ for some constant C.

Proposition 2 . 9 .

 29 For each ℓ there exist expressions u, v of length ℓ satisfying compl (u, v)

6 a 3 , 3 a 3 , 3 a 2 , 4 Figure 6 .

 63333246 Figure 6. Proof of Relation 2.5, here with i = 1 and p = 3; the grey rectangles correspond to Relation 2.4.

  d i,p c i+2,p = b i,p b i+1,p a i+2,p b i+1,p a i+2,p b i+1,p a i+2,p a i+3,p Np b i,p a i+1,p+1 b i+1,p+1 a i+3,p = b i,p s i+p+1 b i,p s i+p+1 b i,p s i+p+1 a i+1,p b i+1,p+1 a i+3,p p s i+p+1 b i,p a i+1,p b i,p a i+1,p b i,p a i+1,p b i+1,p+1 a i+3,p Np s i+p+1 a i,p+1 b i,p+1 b i+1,p+1 a i+3,p = a i,p+2 b i,p+1 b i+2,p s i+1 a i+3,p s i+1 a i+3,p s i+1 a i+3,p p a i,p+2 b i,p+1 b i+2,p a i+3,p b i+2,p a i+3,p b i+2,p a i+3,p s i+1 Np a i,p+2 b i,p+1 a i+3,p+1 b i+3,p+1 s i+1 = a i,p+2 b i+1,p s i s i+p+2 a i+2,p s i s i+p+2 a i+2,p s i s i+p+2 a i+2,p b i+2,p+2 p+1 a i,p+2 b i+1,p s i+p+2 b i+1,p s i+p+2 b i+1,p s i+p+2 a i+2,p s i b i+1,p+1 p a i,p+2 s i+p+2 b i+1,p a i+2,p b i+1,p a i+2,p b i+1,p a i+2,p s i b i+1,p+1 Np a i,p+2 s i+p+2 a i+1,p+1 b i+1,p+1 s i b i+1,p+1 = c i,p+2 d i,p+2 ,leading to N ′ p = 4p 2 + 8p -3. We can now establish Proposition 2.9.Proof of Proposition 2.9. (See Figure7.) We putu ℓ = s 2ℓ s 2ℓ-2 ...s 2 and v ℓ = s 1 s 3 ...s 2ℓ-1 ,and analyze the reversing of u ℓ v ℓ . The latter consists of three sequences of elementary steps. First, ℓ(ℓ -2)/2 steps of type II lead tos 2 s 1 s 4 s 3 ... s 2ℓ s 2ℓ-1 .Then, ℓ type I steps lead to s 1 s 2 s 1 s 2 s 3 s 4 s 3 s 4 ... s 2ℓ-1 s 2ℓ s 2ℓ-1 s 2ℓ , which is c 1,1 d 2,1 c 3,1 d 4,1 ... c 2ℓ-1,1 d 2ℓ,1 .

c 1 , 1 •

 11 c 1,3 d 2,3 c 3,3 d 4,3 ... c 2ℓ-3,3 d 2ℓ-2,3 • d 2ℓ,1 ; after ℓ -2 more applications, we obtain c 1,1 c 1,3 • c 1,5 d 2,5 c 3,5 d 4,3 ... c 2ℓ-5,5 d 2ℓ-4,5 • d 2ℓ-2,3 d 2ℓ,1 , and so on. After using (2.5) ℓ(ℓ -1)/2 times, we finally obtain c 1,1 c 1,3 ...c 1,2ℓ+1 d 2,2ℓ-1 d 4,2ℓ-3 ... d 2ℓ-2,3 d 2ℓ,1 .

Remark 2 .

 2 11. At the expense of using one type I' tile for the proof of Relation 2.4, no type III tile is used thoughout the above constructions. Using Proposition 2.5, we conclude that the reversing diagram we obtained gives an optimal van Kampen diagram, i.e., it realizes the combinatorial distance between the boundary words, here u ℓ c 1,1 c 1,3 ... c 1,2ℓ+1 and v ℓ d 2ℓ,1 d 2ℓ-2,3 ..., d 4,2ℓ-3 d 2,2ℓ-1 .

  Figure 3. Reversing diagram associated with the sequence ( * ), i.e., the reversing diagram of the pair (s 1 s 2 s 1 , s 2 s 1 s 2 ). Metric aspects are ignored, so the reversing diagram is always considered up to a piecewise affine deformation.

	s 1	s 2 s 2 s 1	s 1 s 2 s 1 s 2 ǫ	ǫ
	s 1 s 2	ǫ	ǫ
				s j			s j
		I)	s i	s j	s i	for |i-j| 2, (type II)	s i	ǫ	for i=j, (type III)
	with the convention that ǫ-labeled dotted arcs, dotted arcs in the diagrams, are
	subsequently ignored. For instance, the reversing diagram associated with the above
	reversing sequence ( * ) is displayed in Figure 3.
	Remark 2.1. Because of the ǫ-labelled arcs, the above patterns are not the most
	general ones appearing in a reversing diagram. The general patterns are actually ǫ s i s j → ǫ s i s j s j s i s i s j for |i-j|=1, (type I) ǫ s i s j for |i-j| 2, s j ǫ for i=j. s i s j (type II) s i ǫ (type III)

  Then we have s i s i+1 s i s i+1 s i s i+1 s i s i s i+1 s i s i+1 , corresponding to an hexagon with an appended digon s i

	s i+1	s i
	s i s i+1	ǫ in the diagram. Let us introduce two new types
	s i+1 s i
	of hexagonal tiles, namely, for |i -j| = 1,
			s j	s i
	type I': s i		s j , type I":
			s j	s i

  Figure 7. Proof of Proposition 2.9, here for ℓ = 4; each grey rectangle corresponds to applying Relation (2.5), hence contains a number of elementary tiles that lies in O(ℓ 2 ).

		1		s 3		s 5		s 7
	s 8	s 1	s 8	s 3	s 8	s 5	s 8	c 7,1	d 8,1
	s 6	s 1	s 6	s 3	s 6	c 5,1	c 7,3 d 6,1	d 6,3
	s 4	s 1	s 4	c 3,1	c 5,3 d 4,1	c 7,5 d 4,3	d 4,5
	s 2		d 2,1	d 2,3	d 2,5	d 2,7
		c 1,1		c 3,3		c 5,5		c 7,7


Alexandra Delion

Sophie Girerd

Kevin Duarte

Nicolas Girerd

Johan Schikowski

Michèle Kessler

Luc Frimat

Alice Aarnink

Which is the best

Keywords: HLA, kidney transplantation, epitope mismatches, physiochemical properties, donor specific antibody

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

Introduction

While numerous factors influence long-term kidney graft survival, Human Leukocyte Antigen (HLA) matching is nevertheless of particular importance [START_REF] Opelz | Effect of human leukocyte antigen compatibility on kidney graft survival: comparative analysis of two decades[END_REF] . Recipients of a mismatched graft have an increased risk of developing donor-specific antibodies (DSA), which is an independent risk factor for acute and chronic antibody-mediated rejection (ABMR) and graft loss [START_REF] Cooper | Inferior kidney allograft outcomes in patients with de novo donor-specific antibodies are due to acute rejection episodes[END_REF] . Furthermore, the development of DSA limits access to repeated transplantation due to long waiting list times in the case of highly sensitized patients. Due to the high polymorphism of HLA antigens, the chance of finding an unrelated fully matched kidney donor is very low. In France, more than ninety percent of transplant recipients in 2016 received grafts with one or more HLA mismatches based on HLA-A, -B, -DR and -DQ antigens [START_REF]Le rapport médical et scientifique du prélèvement et de la greffe en France[END_REF] .

However, the probability of developing DSA or anti-HLA antibodies is not strictly proportional to the number of mismatched HLA antigens. Indeed, anti-HLA antibodies do not recognize whole HLA antigens but interact with a small set of amino acid residues in the structural epitope through six complementarity determining region (CDR) loops of the antibody [START_REF] Duquesnoy | Human leukocyte antigen epitope antigenicity and immunogenicity[END_REF] . Immunization by a single HLA antigen mismatch can result in the appearance of antibodies directed against numerous other HLA antigens due to the sharing of epitopes among different alleles. Conversely, the mismatched antigens may not necessarily present a "foreign" epitope and thus do not have the ability to induce the development of a DSA.

Several approaches have been described to determine the structural compatibility between donors and recipients. The available quaternary HLA molecule structures enabled Duquesnoy et al. to describe the eplet as a functional epitope bound by the CDR-H3 loop, which has a dominant role in determining antibody specificity [START_REF] Duquesnoy | Structural aspects of human leukocyte antigen class I epitopes detected by human monoclonal antibodies[END_REF][START_REF] Duquesnoy | HLAMatchmaker: a molecularly based algorithm for histocompatibility determination. V. Eplet matching for HLA-DR, HLA-DQ, and HLA-DP[END_REF] . The eplet is a cluster of polymorphic amino acids, either linear or discontinuous, within a 3-3.5 Å radius of an accessible sequence position with the ability of inducing an antibody response. For each mismatched donor HLA antigen, the latest version of HLA Matchmaker determines which eplet is non-self, compared with the repertoire of self-eplets of the recipients, resulting in a quantification of eplet mismatches. An important component of this algorithm is that antibodies cannot be induced against an eplet present on a self-HLA antigen.

More recently, Kosmoliaptsis et al. proposed that the relative antigenicity of an epitope could be predicted from the sequence of its amino acid residues and its physicochemical properties. They defined three physiochemical properties: the amino acid mismatch score (AAMS), the electrostatic mismatch score (EMS), and the hydrophobic mismatch score (HMS) [START_REF] Kosmoliaptsis | HLA class I amino acid sequence-based matching after interlocus subtraction and long-term outcome after deceased donor kidney transplantation[END_REF][START_REF] Kosmoliaptsis | Predicting HLA class II alloantigen immunogenicity from the number and physiochemical properties of amino acid polymorphisms[END_REF] . Accordingly, the electrostatic difference between a non-self eplet and a self eplet may provide the trigger for B-cell activation.

Several studies have demonstrated significant correlations between eplet load (via HLA Matchmaker) of HLA mismatches and the development of DSA class I and class II as well as allograft outcomes [START_REF] Duquesnoy | Are We Ready for Epitope-Based HLA Matching in Clinical Organ Transplantation?[END_REF] . However, to the best of our knowledge, only two recent studies, conducted by Kosmoliaptsis et al. [START_REF] Kosmoliaptsis | Alloantibody Responses After Renal Transplant Failure Can Be Better Predicted by Donor-Recipient HLA Amino Acid Sequence and Physicochemical Disparities Than Conventional HLA Matching[END_REF]

Materials and Methods

Patient population and clinical data

This single-center study included all patients aged >18 years, non-immunized, who received a first kidney transplantation from January 1, 2010 to December 31, 2014 in the Nancy University Hospital, Nancy, France. Patients were followed until January 1, 2017. All kidney transplantations (with living or deceased donor) were included. Recipients who had anti-HLA antibodies before transplantation, a kidney-pancreas transplant, an ABO-incompatible kidney transplant, other previous organ transplants or hematopoietic stem cell graft before kidney transplant were excluded (Figure 1). The transplantation allocation system followed the rules of the French national agency for organ assignment (Agence de la Biomédecine) [START_REF] Agence De La Biomédecine | 'ATTRIBUTION DES GREFFONS PRELEVES SUR PERSONNE DECEDEE[END_REF] . Anonymized data were prospectively entered in a computerized database on day 0, at 3 months and 12 months after kidney transplantation, and annually thereafter.

Expanded criteria donors (ECD) were defined as: deceased donors aged 60 and older, and those aged over 50-59 years with at least two of the following three conditions: cerebrovascular cause of death, serum creatinine higher than 1.5 mg/dL (132.6 μmol/L), or a history of hypertension. In our center, despite the absence of immunization, patients receive thymoglobulin as an induction treatment, in case of graft from an ECD, or in case of high-risk of delayed graft function (for example in the event of cardiac arrest with successful resuscitation). Otherwise, they receive either basiliximab, or no induction. Patients also received intravenous methylprednisolone intraoperatively, followed by tapering doses over the following days. Standard immunosuppression consisted of a calcineurin inhibitor (CNI), mycophenolate mofetil and prednisone.

Renal biopsy

In case of graft dysfunction, kidney allograft biopsies were performed and assessed by light microscopy and immunofluorescence. The graft biopsies were scored and graded by trained pathologists according to the international Banff criteria for kidney allograft transplantation [START_REF] Hara | Banff 2013 update: Pearls and pitfalls in transplant renal pathology[END_REF] .

HLA typing methods

Recipient and living donor HLA typing was performed in the Histocompatibility Laboratory of Nancy on genomic DNA by a Luminex-based PCR-SSO typing method (LABTypeTM HD kit, One Lambda Inc., Canoga Park) according to the manufacturer's instructions. HLA typing of deceased donors was performed in each transplant center according to local practice. In Nancy, PCR-SSP typing methods were used (Micro SSP Generic HLA kit, One Lambda Inc., Canoga Park or Alow, Blow, DRBlow, DQlow kits, Olerup, Stockholm, Sweden). Antigenic typing (serological nomenclature or the first set of digits of molecular HLA nomenclature) were converted into allelic typing (two first sets of digits of molecular HLA nomenclature) for the antigen with only one frequent allele in the European NMDP population (Supplementary Table 1a and1b) while high definition typing was performed for the other HLA antigens (N= 31 HLA-A, 31 HLA-B, 81 HLA-DRB1 and 51 HLA-DQB1 high definition typing). Since HLA-C, -DRB3, -DRB4, -DRB5, -DQA1, -DPA1 and -DPB1 typing was not commonly performed during the study period and was not available for many included patients, focus was placed on HLA-A, HLA-B, HLA-DRB1, HLA-DQB1. For each locus, the number of Ag MM and Al MM mismatches was calculated using the serological nomenclature and the two first sets of digits of molecular HLA nomenclature, respectively.

Eplet mismatch identification

Eplet mismatch score (EpMM) was determined with the HLA Matchmaker program (HLAMatchmaker, V02 for class I and V02.1 for class II) using the four-digit allele of each donorrecipient pair. This program analyzes donor and recipient HLA genotypes to generate a list of reactive eplets. The specific eplets found on the HLA molecules of the donor and the recipient are compared, within loci and across loci of the same class, leading to the calculation of the number of unique eplets found in the donor, but not in the recipient.

Identification of amino-acid sequence and physicochemical disparities

HLA immunogenicity of mismatches was analyzed by three properties, namely: amino acid mismatch score (AAMS), electrostatic mismatch score (EMS), and hydrophobic mismatch score (HMS), as described by Kosmoliaptsis et al. [START_REF] Kosmoliaptsis | HLA class I amino acid sequence-based matching after interlocus subtraction and long-term outcome after deceased donor kidney transplantation[END_REF][START_REF] Kosmoliaptsis | Predicting HLA class II alloantigen immunogenicity from the number and physiochemical properties of amino acid polymorphisms[END_REF]

Antibody monitoring

Serum samples were collected at 0, 3, 6, 12 months and yearly thereafter, or at the time of biopsy when clinically indicated (presence of graft dysfunction or suspicion of rejection). Sera were screened for HLA-specific antibodies using solid-phase Luminex antibody-detection beads (LABScreen™ Mixed, One Lambda Inc., Canoga Park). Selected HLA-specific antibody-positive samples were analyzed using Luminex single-antigen class I and class II antibody-detection beads (LABScreen Single Antigen HLA Class I and Class II, One Lambda Inc Canoga Park). Specificities with mean fluorescence intensity (MFI) > 1000 were considered positive.

Exposure to CNI

Measurement of CNI (calcineurin inhibitor) exposure was identical to that described in Girerd et al. [START_REF] Girerd | Impact of reduced exposure to calcineurin inhibitors on the development of de novo DSA: a cohort of non-immunized first kidney graft recipients between 2007 and 2014[END_REF] . Briefly, blood concentrations of CNI were measured by the antibody-conjugated magnetic immunoassay (ACMIA) method using a Dimension® system (Siemens). Trough levels were measured at month 3, month 6, month 12, and annually thereafter. The mean absolute deviation percent (MAD%) formula was used as previously described by Shuker et al [START_REF] Shuker | Intra-patient variability in tacrolimus exposure: causes, consequences for clinical management[END_REF] . The CNI Mean Absolute Deviation (%)

was compared in the group of patients having developed dnDSA and those who did not during followup.

Statistical analysis

All analyses were performed using R software (the R foundation for Statistical Computing).

The two-tailed significance level was set at p<0.05. Continuous variables are described as means ± standard deviation and median (interquartile range), and categorical variables as frequencies (percentages). Comparison of baseline characteristics and follow-up data according to development of dnDSA was carried out using the non-parametric Mann-Whitney test for continuous variables and Fisher's exact test for categorical variables. The number of epitope mismatches was compared among groups defined according the number of antigenic or allelic mismatches using the Kruskal-Wallis test.

Survival analysis with dnDSA outcome was performed by the Kaplan-Meier method using the log-rank test for significance. Univariable and adjusted Cox proportional hazard models were used to assess the association between dnDSA development with antigenic, allelic and epitope mismatches and physiochemical scores. The adjustment variables included age, induction treatment and type of donor (living or deceased). Hazard ratios are presented with their 95% confidence intervals as HR (CI 95%).

Harrell's C-index was used to determine the optimal threshold for each mismatch or score variables.

The diagnostic performance of each mismatch variable dichotomized according to optimal threshold was assessed using Harrell's C-index with their respective confidence interval at 95%.

Results

Baseline Characteristics of the Kidney Transplant Recipients and Donors (Table 1)

A total of 398 transplantations were performed in our center between January 2010 and December 2014: 248 recipients were excluded (previous kidney (n=57), other organ (n=4) and HSC (n=1) transplant; ABO-incompatible kidney transplants (n=2), kidney-pancreas transplant (n=2), previously sensitized patients (n=182)). Hence, 150 non-sensitized first kidney transplantation recipients were eligible for the study (Figure 1).

Baseline characteristics of the included recipients and their donors are presented in Table 1A.

The median recipient age was 52 years. Induction therapy with thymoglobulin (n=82) or basiliximab (n=58) was used in 93.4% patients. Standard immunosuppression therapy included a calcineurin inhibitor (tacrolimus or cyclosporine) and mycophenolate mofetil or azathioprine (n=3). Most patients also received low-dose prednisolone as long-term maintenance therapy.

dnDSA development and graft and patient outcomes during follow-up (Table 1)

During a mean follow-up time of 4.1±1.5 years, 18 patients (12%) developed dnDSA (1 HLA class I dnDSA, 12 HLA class II dnDSA and 5 HLA class I and II dnDSA, data not shown). The proportion of living donors was similar in the two groups (33.3% in the groups with dnDSA vs. 37.9%

in the group without dnDSA, p=0.22). Of note, the proportion of diabetic patients was higher in the group who developed dnDSA, and mean BMI was significantly higher in this group. The proportion of patients who received thymoglobulin, basiliximab or no induction was similar between the two groups.

Nevertheless, the majority of patients in the group who developed dnDSA were receiving cyclosporine (66.7%), whereas the majority of patients without dnDSA were receiving tacrolimus (63.6%). The CNI Mean Absolute Deviation (%) did not differ in the two groups (17.5 ± 8.8 vs. 17.9 ± 8.5, p=0.71).

Nine patients returned to dialysis during follow-up and 7 patients died with a functioning graft.

Patients with dnDSA more frequently experienced graft rejection (55.6% vs. 24.2%, p=0.01), and return to dialysis (22.2% vs. 3.8, p=0.013). Of note, DSA was detected before the return to dialysis. No difference was observed with regard to patient survival.

Distribution of allelic, epitope and physiochemical mismatches within antigenic mismatch groups

The use of the two first sets of digits of molecular HLA nomenclature to define allelic compatibility increased the number of antigenic mismatches of 11 donor-recipient pairs for class I and 53 for class II, mostly on the HLA-DR locus (data not shown).

As expected, the number of EpMM rose gradually with increasing number of AgMM and AlMM (Figure 2). In our cohort, the number of epitope mismatches varied between 0-31 for class I (vs. 0-4 with AgMM or AlMM) and 0-51 for class II (vs. 0-4 with AgMM or AlMM).

For the three physiochemical scores, AAMS, EMS and HMS, the range of values were respectively 0-61, 0-87 and 0-79 in class I, and 0-67, 0-85 and 0-63 in class II.

Association between HLA mismatches and de novo DSA development

The total number of MM (class I + class II) was significantly higher in the group of patients who developed dnDSA, irrespective of the method used (Table 2). When considering the total number of MM as a continuous variable, the latter was significantly associated with an increased risk of dnDSA development, even after adjustment for the recipient's age, induction treatment, and type of donor (living or deceased), irrespective of the method used (for AgMM-adjusted HR=1.66, p=0.004; for AlMM-adjusted HR=1.62, p=0.005; for EpMM-adjusted HR=1.04, p=0.01; for AAMS-adjusted HR= 1.04, p=0.002; for EMS-adjusted HR= 1.02, p=0.004; for HSM-adjusted HR= 1.03, p=0.006) (Table 3). All approaches to evaluate compatibility (with or without adjustment) were significantly associated with the development of DSA during follow-up (which were mostly class II dnDSA) (Supplementary Table 2).

For each method, an optimal threshold of the sum of class I and class II mismatches was determined for the prediction of dnDSA development (5 for AgMM (p=0.006), 6 for AlMM(p=0.009), 22 for EpMM (p=0.005), 42 for AAMS (p=0.0007), 45 for EMS (p=0.009) and 44 for HSM (p=0.026)).

The impact of a number of MM above the threshold value after adjustment for age, induction treatment and type of donor is presented in Table 3, with adjusted hazard ratios ranging from 3.22 to 6.85. Figure 3 presents the probability of developing dnDSA when the number of MM was greater or lower than the optimal threshold value of the sum of class I and class II MM for each method.

Which is the best predictor of de novo DSA development?

The diagnostic performance of each mismatch variable (dichotomized according to the optimal threshold) was assessed using Harrell's C-index with their 95% confidence interval (Table 4). C-indices ranged from 64.1 to 70.4 (C-index of the sum of class I and II AAMS). Nevertheless, the standard antigenic approach yielded a C-index for dnDSA development prediction (C-index 68.0, p=0.0005) in a range similar to the allelic, epitope or physicochemical methods.

Discussion

It is well established that the risk of allosensitization following kidney transplantation increases incrementally with the number of antigenic mismatches at individual HLA-A, -B, -C, -DR, and -DQ loci [START_REF] Kosmoliaptsis | Impact of donor mismatches at individual HLA-A, -B, -C, -DR, and -DQ loci on the development of HLA-specific antibodies in patients listed for repeat renal transplantation[END_REF] . With the knowledge of HLA structure, new approaches such as epitope and physiochemical disparities have been described in order to take into account the differences in donor HLA immunogenicity according to the recipient's HLA type. The present study aimed to determine if one approach was superior to another in predicting dnDSA development in kidney transplantation.

In the present study conducted among homogenous cohort of non-sensitized first kidney transplant patients, the six different approaches (antigenic, allelic and epitope mismatches, as well as amino-acid sequence and physiochemical disparities (AAMS, EMS, HMS)) were compared for the assessment of HLA class I and class II immunogenicity. As detailed, our cohort was moderately well antigenically-matched with 61.3% and 32% of recipients presenting 3 or 4 antigenic mismatches for HLA Class I and II molecules, respectively. This observation is in accordance with the French allocation policy for deceased donor kidneys which promotes antigenic HLA-DR compatibility. At the allelic level, mismatching was greater than at the antigenic level with 65.3% of recipients presenting Although the AAMS (defined by Cambridge algorithm) and the number of epitope mismatches both reflect differences in amino sequence between donor and recipient, these two parameters do not yield the exact same information. The epitope mismatches only consider the number of polymorphic accessible amino acid residues at discontinuous positions of donor HLA that cluster together to form a potential epitope. In contrast, AAMS considers all amino acid differences between both donor and recipient HLA class I and class II molecules. Notwithstanding, these two parameters do not allow studying the physiochemical properties of the amino acid polymorphisms involved, while the specificity and affinity of antibody binding to target antigen is strongly influenced by electrostatic interactions; such interactions are determined by the number and polarity charges of amino acid chains. EMS and HMS, on the other hand, integrate information on the number of mismatched amino acids and the differences in electrostatic (EMS) and hydrophobic (HMS) charges between donor and recipient HLA class I and class II molecules [START_REF] Kosmoliaptsis | HLA class I amino acid sequence-based matching after interlocus subtraction and long-term outcome after deceased donor kidney transplantation[END_REF][START_REF] Kosmoliaptsis | Predicting HLA class II alloantigen immunogenicity from the number and physiochemical properties of amino acid polymorphisms[END_REF] .

In our cohort, few patients developed de novo DSA (12%). This observation is in accordance with previous reports whereby Wiebe et al. [START_REF] Wiebe | Evolution and clinical pathologic correlations of de novo donor-specific HLA antibody post kidney transplant[END_REF] and Willecombe et al. [START_REF] Willicombe | De novo DQ donor-specific antibodies are associated with a significant risk of antibody-mediated rejection and transplant glomerulopathy[END_REF] respectively observed 15% and 18% of dnDSA development. However, the low number of dnDSA of our cohort did not allow assessing the impact of HLA class I and HLA class II immunogenicity separately. For each of the six approaches, the significant total mismatch/score threshold on dnDSA onset was established, allowing a comparison between the different methods and illustrating the clinical applicability and relevance of these approaches.

As a result of the above analyses, a cut-off of 22 epitope mismatches was defined as a clinically [START_REF] Wiebe | A Comparison of HLA Molecular Mismatch Methods to Determine HLA Immunogenicity[END_REF] . Among the 6 approaches tested in the current study, the highest C-index was observed with the AAMS, albeit only marginally higher than that observed with the other techniques. Of note, the prediction capacity of the epitope approach was not strikingly higher. Importantly, in this low immunological risk cohort, the routine antigenic approach (with a threshold of 5 mismatches) was also very effective in predicting the development of dnDSA.

However, our analyses were limited to the HLA-A, HLA-B, HLA-DRB1 and HLA-DQB1 loci, which are considered as the most crucial loci influencing transplant outcomes. The addition of HLA-C 22 , -DQA1 [START_REF] Tambur | Epitope analysis of HLA-DQ antigens: what does the antibody see?[END_REF] , -DPB1 [START_REF] Laux | Critical evaluation of the amino acid triplet-epitope matching concept in cadaver kidney transplantation[END_REF] , -DRB3/4/5 [START_REF] Sapir-Pichhadze | HLA-DR and -DQ eplet mismatches and transplant glomerulopathy: a nested case-control study[END_REF] in future studies could help improve risk stratification.

The study of 11 loci is now easier with the marketing of fast typing kits that provide, within a few hours, a typing of all the loci (with notably HLA-C, HLA-DRB3, -DRB4, -DRB5, -DQA1, -DPA1 and -DPB1). However, to our knowledge, no fast HLA typing technique specifically aimed at HLA typing of deceased donors is able to provide high-resolution typing (first two fields). For antigens that have a single allele with a very high frequency, regardless of the ethnic origin of the donor, it is possible to extrapolate the information obtained by these techniques as a result of 4 digits (first two fields).

Conversely, it is not possible to extrapolate for antigens with numerous alleles with high and/or equivalent frequencies which may vary depending on the ethnic origin of the donor. However, the HLA typing resolution of deceased donors has increased with the latest versions of the fast typing kits. In living donor transplants, it is possible to determine the most compatible donor at the allelic, epitope and physiochemical level with high resolution typing techniques, such as NGS or PCR-SSO typing with high resolution kits, suitable for routine HLA typing in organ transplantation.

Certain limitations of this study should be acknowledged, the first of which being its observational single-center design. Secondly, protocol biopsies were not performed, nor was a biopsy systematically performed in instances of de novo DSA detection. Consequently, the number of antibody-mediated rejections observed in this study could have been underestimated. As a result, statistical analyses were only performed on the outcome of development of dnDSA. However, numerous study results have shown an association between DSA and hard evidence of injury [START_REF] Loupy | The impact of donor-specific anti-HLA antibodies on late kidney allograft failure[END_REF][START_REF] Loupy | Antibody-Mediated Rejection of Solid-Organ Allografts[END_REF][START_REF] Gosset | Circulating donor-specific anti-HLA antibodies are a major factor in premature and accelerated allograft fibrosis[END_REF] .

Thirdly, certain factors that may contribute to de novo DSA development were not taken into account in this study, namely post-transplant pregnancies and transfusions. Maintenance immunosuppressive therapy (type and level of exposure) was also not taken into account in the multivariable analyses given that the CNI Mean Absolute Deviation (%) did not differ between the two groups (patient with or without dnDSA). However, the type of donor and the induction regimen were taken into account.

Clinical implications

In all cases, when there is a choice to be made among several donors (in instances of living donor kidney transplant) or recipients (in instances of deceased donor transplant), we believe that it would be of interest to have all immunogenicity information. For instance, when two recipient-donor pairs have the same number of antigen mismatches, determining the number of epitope mismatches as well as the AMMS, EMS or HMS could help choose the best living donor or recipient in terms of immunological compatibility.

The main objective of all of these investigations is to minimize and anticipate the appearance of anti-HLA antibodies which could reduce the graft survival of the first graft [START_REF] Loupy | The impact of donor-specific anti-HLA antibodies on late kidney allograft failure[END_REF][START_REF] Loupy | Antibody-Mediated Rejection of Solid-Organ Allografts[END_REF][START_REF] Gosset | Circulating donor-specific anti-HLA antibodies are a major factor in premature and accelerated allograft fibrosis[END_REF] , but also decrease access to a second transplant. For immunized patients, the challenge is twofold. First, the graft should be as compatible as possible, similarly as in non-sensitized patients. Second, it should not contain epitopes against which the patient is already immunized. The epitope approach allows forbidding some epitopes, but also authorizes certain acceptable epitopes (which could have been forbidden by a traditional antigenic or allelic approach).

Ideally, as recently described by Wiebe et al. [START_REF] Wiebe | BMI: body mass CMV: cytomegalovirus; D: donor's serology; DSA: donor specific antibody; dnDSA: donor specific antibody; eGFR: estimated Glomerular Filtration Rate[END_REF] , our capacity to predict the appearance of anti-HLA antibodies could allow adapting immunosuppressive treatments to each immunological risk and to minimize the risks of infections and neoplasia related to unnecessary over-immunosuppression. In this cohort of non-sensitized first graft recipients, we did not observe any single approach (antigenic, allelic, epitope, amino-acid or physicochemical disparities) to be more predictive than another.

However, our results should be confirmed in a larger prospective cohort.

Conclusion

HLA matching is one of the highlights of long-term research in the field of organ transplantation. To date, it remains unclear whether pre-transplantation epitope analysis or physiochemical mismatch analysis should be consistently incorporated into HLA-matching algorithms.

In the present study including patients, a more physiochemically comprehensive approach including amino-acid and physiochemical disparities, as well as epitope and allelic analyses yielded similar prediction of the risk of DSA development as that observed with routine/classical approaches. Larger studies should confirm these results. Although no particular advantages of using each of these methods alone is demonstrated among non-sensitized patients with a low immunological risk, a prospective study should be conducted to assess whether implementing these various HLA mismatch algorithms as complementary tools would have an impact on the long-term prognosis of kidney transplant patients. The band inside the box represents the median with the lower and upper portions representing the first and third quartiles, while the ends of the whiskers represent the minimum and maximum.

Groups were compared using the Kruskal-Wallis test.

MM: mismatch(es). Harrell's C-index was used to determine the optimal threshold for each mismatch and score variable.

AAMM: amino-acid mismatch; dnDSA: de novo donor specific antibody; EMS: electrostatic mismatch score; HMS: hydrophobic mismatch score;

  and Wiebe et al. 11 , compared the two approaches provided by Duquesnoy et al. and Kosmoliaptsis et al. In light of the above, the present study aimed to determine the best predictor of dnDSA development in non-sensitized first kidney transplant patients by estimating the associations between the number of antigenic mismatches (Ag MM), allelic mismatches (Al MM), Eplet mismatch score (Ep MM) as well as physiochemical properties of amino-acid sequences (via AAMS, EMS, and HMS) and the development of DSA class I and class II in a cohort of transplant recipients with low immunological risk.

3 or 4 allelic

 4 mismatches for HLA class I and 46.7% for HLA class II, particularly for HLA-DR. The results were expected and are explained by the presence, in the Caucasian population, of certain antigens (for example HLA-DRB1*04, *11, *13 or HLA-DQB1*06) with several high frequency alleles. Of note, numerous supplementary high definition HLA typing tests (N= 194) were performed herein in order to precisely define the allele rather than extrapolating the latter, which undoubtedly conferred an additional measure of robustness to our observations.

  relevant threshold for the risk of dnDSA development. Recent reports from Wiebe et al. focused on the development of DSA against HLA class II and the risk of graft loss according to the number of HLA mismatch eplets[START_REF] Wiebe | Class II HLA epitope matching-A strategy to minimize de novo donor-specific antibody development and improve outcomes[END_REF][START_REF] Wiebe | The Synergistic Effect of Class II HLA Epitope-Mismatch and Nonadherence on Acute Rejection and Graft Survival[END_REF] . The optimal threshold for epitope mismatches on development of HLA Class II dnDSA was 10 for HLA-DR (including DRB1/3/4/5) and 17 for HLA-DQ (DQA1/B1). Such threshold was higher than in the present study and might be explained by the higher number of loci considered herein (HLA-DRB3/4/5, and HLA-DQA1 alleles in Wiebe et al. study). In effect, 17 eplets were defined on α chain DQ (http://epitopes.net). Regarding class I immunogenicity, Silva et al. suggested a threshold of 6 HLA-B epitope mismatches for the risk of developing anti-HLA class I antibodies 21 . Overall, our epitope threshold is thus in keeping with previous reports. Recently, Kosmoliaptsis et al. recorded the risk of allosensitization following a first renal transplant using three different approaches: eplet mismatches, AAMS and EMS 10 . The three approaches were independently associated with the risk of developing post-transplant HLA class I and class II specific antibodies. The authors furthermore did not demonstrate any advantage in using the eplet approach over enumerating the number of different amino-acids (AAMS) to assess the risk of DSA development. Wiebe et al. confirmed these results in a large cohort (N=596) evaluating the prediction capacity for the development of HLA-DR/DQ dnDSA

Figure 1 :Figure 2 :

 12 Figure 1: Flow Chart

Figure 3 :

 3 Figure 3: Kaplan-Meier survival curves for de novo DSA development according to each mismatch and score variable.

Table 1 : Baseline characteristics and follow-up data of patients according to the development or not of de novo DSA during follow-up

 1

			No DSA (n=132)		De novo DSA (n=18)	p-value
		N	Mean ± SD / n (%)	Median (Q1 -Q3)	N	Mean ± SD / n (%)	Median (Q1 -Q3)
	Demographics
	Age (years)	132 50.8 ± 14.7	53.0 (39.5 -62.5)	18 45.1 ± 13.1	39.0 (35.0 -59.0)	0.083
	Gender	132			18			0.76
	Male		103 (78.0 %)			15 (83.3 %)
	Female		29 (22.0 %)			3 (16.7 %)
	BMI (kg/m²)	132	25.5 ± 5.1	25.0 (21.5 -29.0)	18	28.9 ± 4.6	30.0 (26.0 -33.0)	0.006
	Comorbidities
	Stroke	132	7 (5.3 %)		18	0 (0.0 %)		1.00
	Diabetes	132 23 (17.4 %)		18	6 (33.3 %)		0.12
	Diabetes	132			18			0.036
	No history of diabetes		109 (82.6 %)			12 (66.7 %)
	Type I diabetes		4 (3.0 %)			3 (16.7 %)
	Type II diabetes		19 (14.4 %)			3 (16.7 %)
	History of coronary disease	132 15 (11.4 %)		18	0 (0.0 %)		0.22
	Heart failure	132 22 (16.7 %)		18	2 (11.1 %)		0.74
	Peripheral artery disease	132 14 (10.6 %)		18	2 (11.1 %)		1.00
	Neoplasia	132 10 (7.6 %)		18	2 (11.1 %)		0.64
	Causal nephropathy	132			18			0.29
	Other		14 (10.6 %)			1 (5.6 %)
	Glomerulonephritis		38 (28.8 %)			7 (38.9 %)
	Toxic		1 (0.8 %)			0 (0.0 %)
	Diabetic nephropathy		14 (10.6 %)			6 (33.3 %)
	Vascular nephropathy		18 (13.6 %)			1 (5.6 %)
	Unknown		11 (8.3 %)			2 (11.1 %)
	Polycystic disease		19 (14.4 %)			0 (0.0 %)
	Nephrectomy		1 (0.8 %)			0 (0.0 %)
	Malformative uropathy		9 (6.8 %)			1 (5.6 %)
	Vasculitis		6 (4.5 %)			0 (0.0 %)
	Tubulo-interstitial		1 (0.8 %)			0 (0.0 %)
	Dialysis prior to transplantation	132			18			0.83
	Non-dialyzed		15 (11.4 %)			2 (11.1 %)
	Peritoneal dialysis		16 (12.1 %)			3 (16.7 %)
	Hemodialysis		101 (76.5 %)			13 (72.2 %)
	Pre-transplant dialysis time (years)	117	2.6 ± 2.1	2.0 (1.1 -3.3)	16	2.6 ± 2.7	1.9 (1.6 -2.6)	0.80

Table 2 : Number of mismatches, amino-acid and physicochemical disparities according to the development or not of de novo DSA during follow-up

 2

			No DSA (n=132)		De novo DSA (n=18)
		N	Mean ± SD / n (%)	Median (Q1 -Q3)	N	Mean ± SD / n (%)	Median (Q1 -Q3)	p-value
	Antigenic MM 132	4.6 ± 2.0	5 (3 -6)	18	5.9 ± 1.1	6 (5 -7)	0.004
	Allelic MM	132	5.0 ± 2.1	5 (4 -7)	18	6.4 ± 1.1	7 (6 -7)	0.005
	Epitope MM	132	29.5 ± 15.5	29 (18 -41.5)	18	39.9 ± 12.4	37.5 (30 -46)	0.008
	AAMS	114	36.7 ± 20.2	36.5 (22 -51)	16	54.1 ± 19.8	47 (44.5 -76)	0.006
	EMS	114	45.6 ± 28.3	43.5 (25 -63)	16	67.6 ± 30.9	64.5 (48 -80.5)	0.009
	HMS	114	35.9 ± 22.8	33.5 (20 -50)	16	52.0 ± 23.9	49 (32 -70)	0.016
	AAMS: amino-acid mismatch score; dnDSA: de novo donor specific antibody; EMS: electrostatic electrostatic mismatch
	score; HMS: hydrophobic mismatch score; MM: mismatch. Q1: first quartile; Q3: third quartile; SD: standard deviation.

Table 3 : Association between de novo DSA development and antigenic, allelic, epitope, amino- acid and physicochemical mismatch variables (continuous variables and dichotomized according an optimal cutoff): univariable and adjusted Cox models

 3

			Univariable Cox model	Adjusted Cox model*
		NdnDSA/N	HR (CI 95 %)	p-value	HR (CI 95 %)	p-value
	Antigenic MM
	Continuous	18 / 150 (12.0 %)	1.51 (1.10-2.07)	0.011	1.66 (1.17-2.35)	0.004
	0-5 MM	5 / 88 (5.7 %)	1.00	-	1.00	-
	> 5 MM	13 / 62 (21.0 %)	3.85 (1.37-10.82)	0.010	4.63 (1.53-14.02)	0.007
	Allelic MM
	Continuous	18 / 150 (12.0 %)	1.52 (1.10-2.09)	0.011	1.62 (1.16-2.26)	0.005
	0-6 MM	7 / 100 (7.0 %)	1.00	-	1.00	-
	> 6 MM	11 / 50 (22.0 %)	3.31 (1.28-8.56)	0.013	3.76 (1.40-10.14)	0.009
	Epitope MM
	Continuous	18 / 150 (12.0 %)	1.04 (1.01-1.07)	0.016	1.04 (1.01-1.08)	0.010
	0-22 MM	0 / 46 (0.0 %)	-	-	-	-
	> 22 MM	18 / 104 (17.3 %)	-	-	-	-
	AAMS
	Continuous	16 / 130 (12.3 %)	1.04 (1.01-1.06)	0.003	1.04 (1.01-1.06)	0.002
	0-42 MM	3 / 75 (4.0 %)	1.00	-	1.00	-
	> 42 MM	13 / 55 (23.6 %)	6.60 (1.88-23.17)	0.003	6.85 (1.91-24.62)	0.003
	EMS
	Continuous	16 / 130 (12.3 %)	1.02 (1.01-1.04)	0.006	1.02 (1.01-1.04)	0.004
	0-45 MM	3 / 64 (4.7 %)	1.00	-	1.00	-
	> 45 MM	13 / 66 (19.7 %)	4.63 (1.32-16.25)	0.017	5.13 (1.37-19.13)	0.015
	HMS
	Continuous	16 / 130 (12.3 %)	1.03 (1.01-1.05)	0.009	1.03 (1.01-1.05)	0.006
	0-44 MM	6 / 80 (7.5 %)	1.00	-	1.00	-
	> 44 MM	10 / 50 (20.0 %)	2.99 (1.09-8.25)	0.034	3.22 (1.15-8.96)	0.026

AAMS: amino-acid mismatch score; dnDSA: de novo donor specific antibody; EMS: electrostatic mismatch score; HMS: hydrophobic mismatch score; HR: hazard ratio; MM: mismatch(es). NdnDSA: number of patients with dnDSA; N: number of non-missing patients. † adjusted for age, induction, living donor

Table 4 : C-index of antigenic, allelic, epitope, and physicochemical variables (continuous, dichotomized according an optimal cutoff) for the risk of de novo DSA development

 4

		C-index (CI 95 %)	p-value
	Antigenic MM
	Continuous	69.3 (59.7 -79.0)	<0.0001
	> 5 MM	68.0 (57.8 -78.1)	0.0005
	Allelic MM
	Continuous	70.6 (60.7 -80.6)	<0.0001
	> 6 MM	67.7 (56.7 -78.8)	0.002
	Epitope MM
	Continuous	66.5 (55.8 -77.2)	0.003
	> 22 MM	65.7 (61.9 -69.4)	<0.0001
	AAMS
	Continuous	67.8 (56.6 -79.1)	0.002
	> 42 MM	70.4 (60.1 -80.7)	0.0001
	EMS
	Continuous	66.7 (54.9 -78.4)	0.005
	> 45 MM	65.9 (55.5 -76.3)	0.003
	HMS
	Continuous	66.9 (54.4 -79.3)	0.008
	> 44 MM	64.1 (51.9 -76.3)	0.024

AAMS: amino-acid mismatch score; EMS: electrostatic mismatch score; HMS: hydrophobic mismatch score.

MM: mismatch(es).

Acknowledgments

The authors thank Dr Anne Kennel of the Histocompatibility Laboratory for her kind advice.