LATTICE QUOTIENTS, AND Brick Polytopes

Hopf Algebras

Vincent Pilaud

Keywords: Brick polytopes, lattice quotients, and Hopf algebras Brick polytopes -Multitriangulations -Pipe dreams -Combinatorial Hopf algebras -Lattice quotients

published or not. The documents may come

Introduction

The motivation of this paper comes from relevant combinatorial, geometric, and algebraic structures on permutations, binary trees and binary sequences. Classical surjections from permutations to binary trees (BST insertion) and from binary trees to binary sequences (canopy) yield:

• lattice morphisms from the weak order, via the Tamari lattice, to the boolean lattice;

• normal fan coarsenings from the permutahedron, via J.-L. Loday's associahedron [START_REF] Loday | Realization of the Stasheff polytope[END_REF], to the parallelepiped generated by the simple roots e i+1 -e i ; • Hopf algebra refinements from C. Malvenuto and C. Reutenauer's algebra [START_REF] Malvenuto | Duality between quasi-symmetric functions and the Solomon descent algebra[END_REF], via J.-L. Loday and M. Ronco's algebra [START_REF] Loday | Hopf algebra of the planar binary trees[END_REF], to L. Solomon's descent algebra [START_REF] Solomon | A Mackey formula in the group ring of a Coxeter group[END_REF]. These fascinating connections were widely extended by N. Reading in his work on "Lattice congruences, fans and Hopf algebras" [START_REF] Reading | Lattice congruences, fans and Hopf algebras[END_REF]. In particular, he proves that any lattice congruence ≡ of the weak order on the permutations of S n (see Section 1.6 for proper definitions) defines a complete simplicial fan F ≡ refined by the Coxeter fan, and he characterizes in terms of simple rewriting rules the families (≡ n ) n∈N of lattice congruences of the weak orders on (S n ) n∈N which yield Hopf subalgebras of C. Malvenuto and C. Reutenauer's algebra on permutations. His work opens two natural questions. On the geometric side, it is not clear which of the fans F ≡ are actually normal fans of polytopes, as in the previous example of the associahedron. On the algebraic side, this construction produces a combinatorial Hopf algebra whose basis is indexed by the congruence classes of (≡ n ) n∈N . However, the product and coproduct in this Hopf algebra are performed extrinsically: the algebra is embedded in C. Malvenuto and C. Reutenauer's algebra on permutations and the computations are performed at that level. The remaining challenge is to realize the resulting Hopf algebra intrinsically by attaching a combinatorial object to each congruence class of (≡ n ) n∈N and working out the rules for product and coproduct directly on these combinatorial objects. The present paper answers these two questions for a relevant family of lattice congruences of the weak order, generalizing the classical sylvester congruence [START_REF] Hivert | The algebra of binary search trees[END_REF].

Our starting point is the world of acyclic multitriangulations. A k-triangulation of a convex (n+2k)-gon is a maximal set of diagonals such that no k+1 of them are pairwise crossing. Multitriangulations were introduced by V. Capoyleas and J. Pach [START_REF] Capoyleas | A Turán-type theorem on chords of a convex polygon[END_REF] in the context of extremal theory for geometric graphs and studied for their rich combinatorial properties [START_REF] Nakamigawa | A generalization of diagonal flips in a convex polygon[END_REF][START_REF] Dress | On line arrangements in the hyperbolic plane[END_REF][START_REF] Jonsson | Generalized triangulations and diagonal-free subsets of stack polyominoes[END_REF][START_REF] Pilaud | Multitriangulations as complexes of star polygons[END_REF]. Using classical point-line duality, V. Pilaud and M. Pocchiola interpreted k-triangulations of the (n + 2k)-gon as pseudoline arrangements on n-level sorting networks [START_REF] Pilaud | Multitriangulations, pseudotriangulations and primitive sorting networks[END_REF], which can also be seen more combinatorially as beam arrangements in a trapezoidal shape [START_REF] Pilaud | Multitriangulations, pseudotriangulations and some problems of realization of polytopes[END_REF]Section 4.1.4]. In this paper, we call these specific arrangements (k, n)-twists. As observed in [START_REF] Stump | A new perspective on k-triangulations[END_REF][START_REF] Serrano | Maximal fillings of moon polyominoes, simplicial complexes, and Schubert polynomials[END_REF], this connects multitriangulations to (specific) pipe dreams studied in [START_REF] Bergeron | RC-graphs and Schubert polynomials[END_REF][START_REF] Knutson | Gröbner geometry of Schubert polynomials[END_REF]. Motivated by possible polytopal realizations of the simplicial complex of (k + 1)-crossing-free sets of diagonals of a convex (n + 2k)-gon, V. Pilaud and F. Santos defined in [START_REF] Pilaud | The brick polytope of a sorting network[END_REF] the brick polytope of a sorting network, whose vertices correspond to certain acyclic pseudoline arrangements on the network. When k = 1, the pseudoline arrangements on the trapezoidal network correspond to the triangulations of the (n + 2)-gon. They are all acyclic and the brick polytope coincides with J.-L. Loday's associahedron [START_REF] Loday | Realization of the Stasheff polytope[END_REF]. The goal of this paper is to explore further properties of the acyclic (k, n)-twists for arbitrary k and n.

Section 1 is devoted to the combinatorics of acyclic (k, n)-twists. We present a purely combinatorial description of the natural map ins k from the permutations of S n to the acyclic (k, n)-twists in terms of successive insertions in a k-twist. Extending the sylvester congruence of [START_REF] Hivert | The algebra of binary search trees[END_REF], we show that the fibers of this map are the classes of a congruence ≡ k defined as the transitive closure of the rewriting rule U acV

1 b 1 V 2 b 2 • • • V k b k W ≡ k U caV 1 b 1 V 2 b 2 • • • V k b k W where a, b 1 , . . . , b k , c ∈ [n]
are such that a < b i < c for all i ∈ [k] and U, V 1 , . . . , V k , W are words on [n]. This congruence is a lattice congruence of the weak order, so that the increasing flip order on the acyclic (k, n)-twists defines a lattice, generalizing the Tamari lattice. We also define a canopy map can k from the acyclic (k, n)-twists to the acyclic orientations of the graph G k (n) = ([n], {{i, j} | |i -j| ≤ k}). For τ ∈ S n , the composition rec k (τ ) = can k ins k (τ ) records the relative positions in τ of any entries i and j such that |i -j| ≤ k, thus generalizing the recoils of the permutation τ . Note that this generalization of recoils was already considered by J.-C. Novelli, C. Reutenauer and J.-Y. Thibon in [START_REF] Novelli | Generalized descent patterns in permutations and associated Hopf algebras[END_REF] with a slightly different presentation. To sum up, at the combinatorial level, we obtain a commutative triangle of lattice homomorphisms from the weak order, via the increasing flip order on the acyclic (k, n)-twists, to the boolean lattice on acyclic orientations of G k (n).

In Section 2, we survey and partially revisit the geometric aspects of these combinatorial maps. We recall the definitions of the classical permutahedron Perm k (n), of the brick polytope Brick k (n) of the n-level trapezoidal network [START_REF] Pilaud | The brick polytope of a sorting network[END_REF], and of the zonotope Zono k (n) of the graph G k (n). Their vertices correspond to the permutations of S n , to the acyclic (k, n)-twists, and to the acyclic orientations of G k (n), respectively. When oriented in the direction (n -1, n -3, . . . , 1 -n), their 1-skeleta are the Hasse diagrams of the weak order on permutations of S n , of the increasing flip lattice on acyclic (k, n)-twists, and of the boolean lattice on acyclic orientations of G k (n). The maps ins k , rec k and can k can be read as inclusions of normal cones of vertices of Perm k (n), Brick k (n) and Zono k (n). The reader can already glance at Figure 8 on page 13 for an illustration of the geometric situation. Although most results in this section are not new, they provide the geometric side of the picture.

Section 3 finally presents the new algebraic construction which motivated this paper. We consider C. Malvenuto and C. Reutenauer's Hopf algebra on permutations [START_REF] Malvenuto | Duality between quasi-symmetric functions and the Solomon descent algebra[END_REF], that we denote by FQSym. We consider the subspace Twist k generated by the sums of the elements of FQSym over the fibers of ins k . Since these fibers are classes of a congruence ≡ k which satisfy standard compatibility conditions with the shuffle and the standardization [Rea05, Hiv04, HN07, Pri13], this subspace automatically defines a Hopf subalgebra of FQSym. Our approach with k-twists provides a combinatorial interpretation for this subalgebra, and it is interesting to describe the product and the coproduct directly on acyclic k-twists. Note that our Hopf algebra Twist k on acyclic k-twists is sandwiched in between C. Malvenuto and C. Reutenauer's Hopf algebra FQSym on permutations [START_REF] Malvenuto | Duality between quasi-symmetric functions and the Solomon descent algebra[END_REF] and J.-C. Novelli, C. Reutenauer and J.-Y. Thibon's k-recoil Hopf algebra Rec k on acyclic orientations of G k (n) [START_REF] Novelli | Generalized descent patterns in permutations and associated Hopf algebras[END_REF]. We finally briefly study further algebraic properties of Twist k : we define multiplicative bases and study their indecomposable elements, we connect it to integer point transforms of the normal cones of the brick polytope, and we define a natural extension of dendriform structures in the context of k-twists.

The results of this paper can be extended in three independent directions: on Cambrian acyclic twists (parametrized by a sequence of signs [Rea06, HL07, PS12], similar to [CP17, Part 1]), on tuples of Cambrian twists (similar to [START_REF] Law | The Hopf algebra of diagonal rectangulations[END_REF][START_REF] Giraudo | Algebraic and combinatorial structures on pairs of twin binary trees[END_REF] and [CP17, Part 2]), and on Schröder twists (corresponding to the faces of the brick polytope, similar to [START_REF] Chapoton | Algèbres de Hopf des permutahèdres, associahèdres et hypercubes[END_REF] and [CP17, Part 3]). These extensions are skipped here to keep this paper short, but details can be found in [START_REF] Pilaud | Brick polytopes, lattice quotients, and Hopf algebras[END_REF].

Combinatorics of twists

1.1. Pipe dreams and twists. A pipe dream is a filling of a triangular shape with crosses and elbows so that all pipes entering on the left side exit on the top side. These objects were studied in the literature, under different names including "pipe dreams" [START_REF] Knutson | Gröbner geometry of Schubert polynomials[END_REF], "RC-graphs" [START_REF] Bergeron | RC-graphs and Schubert polynomials[END_REF], "beam arrangements" [START_REF] Pilaud | Multitriangulations, pseudotriangulations and some problems of realization of polytopes[END_REF][START_REF] Pilaud | The brick polytope of a sorting network[END_REF]. This paper is mainly concerned with the following specific family of pipe dreams which already appeared under different names in [START_REF] Pilaud | Multitriangulations, pseudotriangulations and some problems of realization of polytopes[END_REF][START_REF] Pilaud | Multitriangulations, pseudotriangulations and primitive sorting networks[END_REF][START_REF] Stump | A new perspective on k-triangulations[END_REF].

Definition 1 ([Pil10, [START_REF] Pilaud | Multitriangulations, pseudotriangulations and primitive sorting networks[END_REF][START_REF] Stump | A new perspective on k-triangulations[END_REF]). For k, n ∈ N, a (k, n)-twist (we also use just k-twist, or even just twist) is a pipe dream with n + 2k pipes such that

• no two pipes cross twice (the pipe dream is reduced),

• the pipe which enters in row i exits in column i if k ≤ i ≤ n+k, and in column n + 2k + 1 -i otherwise. Here and throughout the paper, rows are indexed from bottom to top and columns are indexed from left to right. Besides the first k and last k trivial pipes, a (k, n)-twist has n relevant pipes, labeled by [n] from bottom to top, or equivalently from left to right. In other words, the pth pipe enters in row p + k and exits at column p + k of the (n + 2k) × (n + 2k)-triangular shape. We denote by T k (n) the set of (k, n)-twists.

Definition 2 ([PS12]

). The contact graph of a (k, n)-twist T is the directed multigraph T # with vertex set [n] and with an arc from the se-pipe to the wn-pipe of each elbow in T involving two relevant pipes. We say that a twist T is acyclic if its contact graph T # is (no oriented cycle), and we then let T be the transitive closure of T # . We denote by AT k (n) the set of acyclic (k, n)-twists.

Figure 1 illustrates examples of (k, 5)-twists and their contact graphs for k = 0, 1, 2, 3. The first two are acyclic, the last two are not. Except in Figure 2, we only represent the n relevant pipes of the (k, n)-twists and hide the other 2k trivial pipes (the first k and last k pipes). 1.2. Elementary properties of pipes and twists. We now give some elementary properties of pipes and twists needed in the next sections. For a given pipe in a twist, we call:

• we-crosses its horizontal crosses , and sn-crosses its vertical crosses ,

• se-elbows its elbows (aka. "peaks") and wn-elbows its elbows (aka. "valleys"),

• internal steps the segments between two consecutive elbows and external steps the first and last steps of the pipe. The following statements gather some elementary properties of pipes in k-twists already observed in earlier works, see e.g. [Pil10, Section 4.1.4]. Detailed proofs can be found in [START_REF] Pilaud | Brick polytopes, lattice quotients, and Hopf algebras[END_REF].

Lemma 4. The following properties hold for any k, n ∈ N:

(i) A (k, n)-twist has n 2 crosses and kn elbows . (ii) The pth pipe of a (k, n)-twist has

• n -1 crosses: p -1 we-crosses and n -p sn-crosses , • 2k + 1 elbows: k se-elbows and k + 1 wn-elbows , • 2k + 2 steps: k + 1 vertical steps and k + 1 horizontal steps. (iii) The interior of the rectangle defined by two consecutive steps of a pipe contains no elbow.

Lemma 5. For two pipes p, p , write p < p when p starts below and ends to the left of p .

(i) If p < p are two pipes of a twist T such that the crossing between p and p is on an internal step of p , then there is a path from p to p in the contact graph T # of T. (ii) If p < p are two pipes of a twist T and are incomparable in the contact graph T # of T, then the last vertical step of p crosses the first horizontal step of p . (iii) If a twist T is acyclic, then no two pipes of T cross at internal steps of both.

When T is acyclic, we denote by T the transitive closure of its contact graph T # . Note the difference between our notations p < p (meaning that p starts below and ends to the left of p ) and p T p (meaning that p is smaller than p in the contact graph T # ).

1.3. Pipe insertion and deletion. We now define the pipe insertion and deletion, two reverse operations on k-twists: an insertion transforms a (k, n)-twist into a (k, n + 1)-twist by inserting a single pipe while a deletion transforms a (k, n + 1)-twist into a (k, n)-twist by deleting a single pipe. Insertions are always possible (see Definition 6), while only certain pipes are allowed to be deleted (see Definition 9). We start with pipe insertions. Definition 6. Consider a (k, n)-twist T with an increasing relabeling λ : [n] → N of its relevant pipes and an integer q ∈ N. Let p ∈ {0, . . . , n} be such that λ(p) ≤ q < λ(p + 1), where we set the convention λ(0) = -∞ and λ(n + 1) = +∞. The pipe insertion of q in the relabeled (k, n)-twist T produces the relabeled (k, n + 1)-twist T q obtained by:

• inserting a row and a column in the triangular shape between p + k -1 and p + k,

• filling in with elbows the new boxes (p + k, p), (p + k + 1, p + 1), . . . , (p + 2k, p + k), • filling in with crosses all other new boxes (p+k, j) for j < p and (i, p+k) for i > p+2k, • relabeling the rth relevant pipe of the resulting twist by λ(r) if r < p, by q if r = p, and by λ(r -1) if r > p. Lemma 7. The contact graph (T q) # is obtained from T # by connecting to some existing nodes the new node corresponding to the inserted pipe q. In particular, the node corresponding to the inserted pipe is a source of the contact graph (T q) # .

Example 8 (Insertion in 1-twists, triangulations and binary search trees). The following operations are equivalent under the bijections between 1-twists, triangulations, and binary search trees (see Example 3 and Figure 2):

• the pipe insertion of q in the (relabeled) 1-twist T,

• the triangle insertion of q in the (relabeled) triangulation T ,

• the node insertion q in the (relabeled) binary search tree T # . We now define the deletion, which just erases a pipe from a (k, n + 1)-twist.

Definition 9. Consider a (k, n + 1)-twist T with an increasing relabeling λ : [n + 1] → N of its relevant pipes. Assume that the pth pipe of T, labeled by λ(p) = q, is a source of the contact graph T # . Then the pipe deletion of q in the relabeled (k, n + 1)-twist T produces the relabeled (k, n)-twist T q obtained by: • deleting the (p + k)th row and column of T,

• relabeling the rth relevant pipe of the resulting twist by λ(r) if r < p and by λ(r+1) if r ≥ p.

The following statements are immediate consequences of the definitions.

Lemma 10. The contact graph (T q) # is obtained from T # by deleting the node corresponding to the delete pipe q.

Lemma 11. For any (k, n)-twist T relabeled by λ : [n] → N and any integer q ∈ N, we have • (T q) q = T, and • (T q) q = T as soon as q ∈ λ([n]) labels a source of T.

1.4. k-twist correspondence. We now present a natural surjection from permutations to acyclic k-twists. It relies on an insertion operation on pipe dreams similar to the insertion in binary search trees (see Example 13 for details). It is motivated by the geometry of the normal fan of the corresponding brick polytope (see Section 2 and [START_REF] Pilaud | The brick polytope of a sorting network[END_REF]). We now describe this algorithm. From a permutation τ := [τ 1 , . . . , τ n ] (written in one-line notation), we construct a (k, n)-twist ins k (τ ) obtain from the (k, 0)-twist by successive pipe insertions of the entries τ n , . . . , τ 1 of τ read from right to left. Equivalently, starting from the empty triangular shape, we insert the pipes τ n , . . . , τ 1 of the twist such that each new pipe is as northwest as possible in the space left by the pipes already inserted. This procedure is illustrated in Figure 4 for the permutation 31542 and different values of k.

Proposition 12. For any (k, n)-twist T, the permutations τ ∈ S n such that ins k (τ ) = T are precisely the linear extensions of the contact graph of T. In particular, ins k is a surjection from the permutations of S n to the acyclic (k, n)-twists.

Proof. We prove the result by induction on n. Consider a permutation τ = [τ 1 , . . . , τ n ] ∈ S n , and let τ = [τ 2 , . . . , τ n ]. By definition, we have ins k (τ ) = ins k (τ ) τ 1 . By induction hypothesis, τ is a linear extension of the contact graph ins k (τ ) # and Lemma 7 ensures that τ 1 is a source of ins k (τ ) # = (ins k (τ ) τ 1 ) # . It follows that τ is a linear extension of the contact graph ins k (τ ) # . Conversely, assume that τ is a linear extension of the contact graph of a (k, n)-twist T. Since τ 1 is a source of T # , the twist T τ 1 is well-defined, and τ is a linear extension of (T τ 1 ) # . By induction, we have ins k (τ ) = T τ 1 and thus ins k (τ ) = ins k (τ ) τ 1 = (T τ 1 ) τ 1 = T by Lemma 11.

Example 13 (1-twist correspondence). The contact graph of the 1-twist ins 1 (τ ) is the binary search tree obtained by the successive insertions of the entries of τ read from right to left. 1.5. k-twist congruence. We now characterize the fibers of ins k as classes of a congruence ≡ k defined by a simple rewriting rule, similar to the sylvester congruence [START_REF] Hivert | The algebra of binary search trees[END_REF].

Definition 14. Write the permutations of S n as words in one-line notation. The k-twist congruence is the equivalence relation ≡ k on S n defined as the transitive closure of the rewriting rule

U acV 1 b 1 V 2 b 2 • • • V k b k W ≡ k U caV 1 b 1 V 2 b 2 • • • V k b k W if a < b i < c for all i ∈ [k],
where

a, b 1 , . . . , b k , c are elements of [n] while U, V 1 , . . . , V k , W are (possibly empty) words on [n].
We say that b 1 , . . . , b k are k-twist congruence witnesses for the exchange of a and c. See Figure 5.

Proposition 15. For any τ, τ ∈ S n , we have τ ≡ k τ ⇐⇒ ins k (τ ) = ins k (τ ). In other words, the fibers of ins k are precisely the k-twist congruence classes.

Proof. From Proposition 12, each fiber of ins k gathers the linear extensions of a k-twist. Since the set of linear extensions of a poset is connected by simple transpositions, we just need to show that τ ≡ k τ ⇐⇒ ins k (τ ) = ins k (τ ) for any two permutations τ = U acV and τ = U caV of S n which differ by the inversion of two consecutive values. Let T = ins k (V ) denote the k-twist obtained after the insertion of V . The positions where a and c will be inserted in T are separated by the letters b in V such that a < b < c. Therefore, if there exists at least k such letters, the pipes a and c are not comparable in (T c) a = (T a) c and we have ins k (τ ) = ins k (τ ). Conversely, if there are strictly less than k such letters, then a is below c in (T c) a while a is above c in (T a) c, and thus we get ins k (τ ) = ins k (τ ).

Example 16 (1-twist congruence and sylvester congruence). The 1-twist congruence coincides with the sylvester congruence defined in [START_REF] Hivert | The algebra of binary search trees[END_REF] as the transitive closure of the rewriting rule U acV bW ≡ U caV bW for a < b < c elements of [n] while U, V, W are (possibly empty) words on [n].

1.6. Lattice congruences of the weak order. In this section, we remind results of N. Reading [START_REF] Reading | Lattice congruences of the weak order[END_REF][START_REF] Reading | Cambrian lattices[END_REF][START_REF] Reading | Lattice congruences, fans and Hopf algebras[END_REF] concerning lattice congruences of the weak order.

Remember first that the (right) weak order on S n is defined as the inclusion order of (right) inversions, where a (right) inversion of τ ∈ S n is a pair of values i, j ∈ N such that i < j while τ -1 (i) > τ -1 (j). See e.g. Figure 5 for the Hasse diagram of the weak order on S 4 .

A lattice congruence is an equivalence relation ≡ on a lattice L compatible with meets and joins: for any x ≡ x and y ≡ y , we have x ∧ y ≡ x ∧ y and x ∨ y ≡ x ∨ y . This implies in particular that each equivalence class under ≡ is an interval of L. Consider now the poset quotient L/≡ on the equivalence classes of ≡ defined by X ≤ Y in L/≡ iff there exists representatives x ∈ X and y ∈ Y such that x ≤ y in L. It inherits a lattice structure where the meet X ∧ Y (resp. the join X ∨ Y ) of two congruence classes X and Y is the congruence class of x ∧ y (resp. of x ∨ y) for arbitrary representatives x ∈ X and y ∈ Y .

It turns out that the k-twist congruence already appeared in the work of N. Reading [START_REF] Reading | Lattice congruences, fans and Hopf algebras[END_REF].

Proposition 17 ([Rea05]

). The k-twist congruence ≡ k is a lattice congruence of the weak order.

Corollary 18. The following combinatorial objects are in explicit bijection:

• acyclic (k, n)-twists, • k-twist congruence classes of S n , • permutations of S n avoiding 1(k +2) -(σ 1 +1) -. . . -(σ k +1) for all σ ∈ S k (maximums), • permutations of S n avoiding (k +2)1 -(σ 1 +1) -. . . -(σ k +1) for all σ ∈ S k (minimums).
Remark 19 (13 -2 versus 1 -3 -2 avoiding permutations). It is easy to see that a permutation avoids 13 -2 if and only if it avoids 1 -3 -2. This property fails for larger values of k. For example, the permutation 13524 avoids 14 -2 -3 but not 1 -4 -2 -3. Here, we deal with permutations avoiding the pattern 1

(k + 2) -(σ 1 + 1) -. . . -(σ k + 1)
, where 1 and (k + 2) are consecutive.

1.7. Increasing flip lattice. We now recall the notion of flips in pipe dreams and study the graph of increasing flips in acyclic k-twists.

Definition 20. An elbow flip (or just flip) in a k-twist is the exchange of an elbow between two relevant pipes p, p with the unique crossing between p and p . The flip is increasing if the initial elbow is located (largely) south-west of the final elbow.

We are interested in the graph of increasing flips, restricted to the acyclic (k, n)-twists. See Figure 6 for an illustration when k = 2 and n = 4. Note that although the graph of flips is regular, its restriction to acyclic twists is not anymore regular in general: the first example appears for k = 2 and n = 5. It is known (see e.g. via subword complexes in [START_REF] Pilaud | EL-labelings and canonical spanning trees for subword complexes[END_REF] or via multitriangulations in [START_REF] Pilaud | Multitriangulations as complexes of star polygons[END_REF]) that this graph is acyclic and it has a unique source (resp. sink) given by the (k, n)-twist where all relevant elbows are in the first k columns (resp. last k rows) while all crosses are on the last n columns (resp. first n rows).

We call increasing flip order the transitive closure of the increasing flip graph on acyclic k-twists. Be aware that it is strictly contained in the restriction to acyclic k-twists of the transitive closure of the increasing flip graph on all k-twists: namely, there are pairs of acyclic k-twists so that any path of increasing flips between them passes through a cyclic k-twist.

Example 21 (Tamari lattice). When k = 1, the increasing flip lattice is the classical Tamari lattice [START_REF]Associahedra, Tamari Lattices and Related Structures[END_REF].

Proposition 22. The following posets are all isomorphic:

• the increasing flip order on acyclic k-twists,

• the quotient lattice of the weak order by the k-twist congruence ≡ k ,

• the subposet of the weak order induced by the permutations of S n avoiding the pattern

1(k + 2) -(σ 1 + 1) -• • • -(σ k + 1) for all σ ∈ S k ,
• the subposet of the weak order induced by the permutations of S n avoiding the pattern

(k + 2)1 -(σ 1 + 1) -• • • -(σ k + 1) for all σ ∈ S k .
Proof. Consider two distinct k-twists T, T and their k-twist congruence classes C, C . If there exist representatives τ = U ijV ∈ C and τ = U jiV ∈ C adjacent in weak order, then T = ins k (τ ) and T = ins k (τ ) differ by the flip of the first/last elbow between the ith and jth pipes, by definition of the map ins k . Conversely, if T and T differ by the flip of the first/last elbow between the ith and jth pipes, then i and j are connected in the contact graph T # , so that there exists a linear extension τ = U ijV of T # where i and j are consecutive. Let τ = U jiV be the permutation obtained by the switch of i and j in τ . By definition of the map ins k , the twist ins k (τ ) is obtained by flipping the first elbow between the ith and jth pipes in ins k (τ ). The representatives τ ∈ C and τ ∈ C are thus adjacent in weak order. This proves that ins k induces an isomorphism from the quotient lattice of the weak order by the k-twist congruence to the increasing flip order on acyclic k-twists. In turn, since the k-twist congruence is a lattice congruence, this quotient lattice is isomorphic to the subposet of the weak order induced by the minimal (resp. maximal) elements of the classes. See [START_REF] Reading | Lattice congruences of the weak order[END_REF][START_REF] Reading | Cambrian lattices[END_REF] for further details on quotient lattices.

4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1
Figure 6. The increasing flip lattice on (k, 4)-twists for k = 1 (left) and k = 2 (right). 1.8. k-recoil schemes. To prepare the definition of the k-canopy of an acyclic k-twist, we now briefly recall the notion of k-recoil schemes of permutations, which was already defined by J.-C. Novelli, C. Reutenauer and J.-Y. Thibon in [START_REF] Novelli | Generalized descent patterns in permutations and associated Hopf algebras[END_REF]. We use a description in terms of acyclic orientations of a certain graph as it is closer to the description of the vertices of the zonotope that we will use later in Section 2. We skip the proofs as they appear in

[NRT11, Pil15] A recoil in a permutation τ ∈ S n is a position i ∈ [n -1] such that τ -1 (i) > τ -1 (i + 1) (in
other words, it is a descent of the inverse of τ ). The recoil scheme of τ ∈ S n is the sign vector rec(τ ) ∈ {-, +} n-1 defined by rec(τ

) i = -if i is a recoil of τ and rec(τ ) i = + otherwise.
To extend this definition to general k, we consider the graph G k (n) with vertex set [n] and edge set {i, j} ∈ [n] 2 i < j ≤ i + k . For example, when k = 1, the graph G 1 (n) is just the n-path. We denote by AO k (n) the set of acyclic orientations of G k (n) (i.e. with no oriented cycle).

Proposition 23 ([NRT11, Prop. 2.1]). The number of acyclic orientations of G k (n) is |AO k (n)| = n! if n ≤ k, k! (k + 1) n-k if n ≥ k.
We use these acyclic orientations to define the k-recoil scheme of a permutation and the corresponding k-recoil congruence.

Definition 24. The k-recoil scheme of a permutation τ ∈ S n is the orientation

rec k (τ ) ∈ AO k (n) with an edge i → j for all i, j ∈ [n] such that |i -j| ≤ k and τ -1 (i) < τ -1 (j). We call k-recoil map the map rec k : S n → AO k (n). Proposition 25. For O ∈ AO k (n),
U ijV ≈ k U jiV if i + k < j,
where i, j are elements of [n] while U, V are (possibly empty) words on [n]. See Figure 7.

Proposition 27 ([NRT11, Prop. 2.2]). For any τ, τ ∈ S n , we have τ

≈ k τ ⇐⇒ rec k (τ ) = rec k (τ ).
In other words, the fibers of rec k are precisely the k-recoil congruence classes.

Definition 28. A direction flip (or just flip) in an acyclic orientation is the switch of the direction of an edge of G k (n). The flip is increasing if the initial direction was increasing. Define the increasing flip order on AO k (n) to be the transitive closure of the increasing flip graph on AO k (n).

Proposition 29. The k-recoil congruence ≈ k is a lattice congruence of the weak order. The krecoil map rec k defines an isomorphism from the quotient lattice of the weak order by the k-recoil congruence ≈ k to the increasing flip lattice on the acyclic orientations of G k (n).

1.9. k-canopy schemes. We recall that the canopy of a binary tree T with n nodes is the sign vector can(T) ∈ {-, +} n-1 defined by can(T) i = -if the node i of T is above the node i + 1 of T and can(T) i = + otherwise. This map was already used e.g. in [LR98, [START_REF] Loday | Realization of the Stasheff polytope[END_REF][START_REF] Viennot | Catalan tableaux and the asymmetric exclusion process[END_REF]. The binary search tree insertion map and the canopy map factorize the recoil map: can • ins = rec. This combinatorial fact can also be understood on the geometry of the normal fans of the permutahedron, the associahedron and the cube, see Section 2.2. We now define an equivalent of the canopy map for general k. To ensure that Definition 31 is valid, we need the following simple observation on comparisons of closed pipes in a k-twist.

Lemma 30. If |i -j| ≤ k, the ith and jth pipes in an acyclic k-twist T are comparable for T .

Proof. By Lemma 5 (ii), if i < j and the ith and jth pipes are incomparable, then the last vertical step of i crosses the first horizontal step of j. Since each pipe has k horizontal steps by Lemma 4 (ii), it ensures that j > i + k.

Definition 31. The k-canopy scheme of a (k, n)-twist T is the orientation can k (T) ∈ AO k (n) with an edge i → j for all i, j ∈ [n] such that |i -j| ≤ k and i T j. It indeed defines an acyclic orientation of G k (n) by Lemma 30. We call k-canopy the map

can k : AT k (n) → AO k (n).
Proposition 32. The maps ins k , can k , and rec k define the following commutative diagram of lattice homomorphisms:

S n AO k (n) AT k (n) rec k ins k can k
Proof. Consider a permutation τ and let i, j ∈ [n] with |i -j| < k such that τ -1 (i) < τ -1 (j). By definition, there is an arc i → j in rec k (τ ). Moreover, the ith pipe is inserted after the jth pipe in ins k (τ ), so that i ins k (τ ) j and there is also an arc i → j in can k • ins k (τ ).

See also Section 2.2 for a geometric interpretation of Proposition 32.

Remark 33 (Combinatorial inclusions). When k > , the k-twist congruence ≡ k refines the -twist congruence ≡ (meaning that τ ≡ k τ implies τ ≡ τ ) and the k-recoil congruence ≈ k refines the -recoil congruence ≈ . We can thus define surjective restriction maps res k→ : AT k (n) → AT (n) and res k→ : AO k (n) → AO (n) by:

• for an acyclic k-twist T, the -twist res k→ (T) is obtained by insertion of any linear extension of T # (it is independent of the choice of this linear extension), • for an acyclic orientation θ ∈ AO k (n), the sign vector res k→ (θ) ∈ AO (n) is obtained by restriction of θ to the edges of G (n). We therefore obtain the following commutative diagram of lattice homomorphisms:

AT k (n) AT (n) S n AO k (n) AO (n) ins k ins rec k rec can k can res k→ res k→

Geometry of acyclic twists

This section is devoted to the polyhedral geometry of permutations of S n , acyclic twists of AT k (n), and acyclic orientations of AO k (n). It is mainly based on properties of brick polytopes of sorting networks, defined and studied by V. Pilaud and F. Santos in [START_REF] Pilaud | The brick polytope of a sorting network[END_REF]. To keep this section short, we skip all proofs of its statements as they follow directly from [START_REF] Pilaud | The brick polytope of a sorting network[END_REF]. This section should be seen as a brief geometric motivation for the combinatorial and algebraic construction of this paper. The reader familiar with the geometry of the brick polytope is invited to proceed directly with Section 3.

2.1. Permutahedra, brick polytopes, and zonotopes. We first recall the definition of three families of polytopes, which are illustrated in Figure 8. We refer to [Zie98, Lectures 0 to 2] for background on polytopes. We denote by (e i ) i∈[n] the canonical basis of R n and let 1 1

:= i∈[n] e i .
Permutahedra The permutahedron is a classical polytope [Zie98, Lecture 0] whose geometric and combinatorial properties reflect that of the symmetric group S n .

Definition 34. The permutahedron Perm(n) is the (n -1)-dimensional polytope

Perm(n) := conv {x(τ ) | τ ∈ S n } = H = ([n]) ∩ ∅ =I [n] H ≥ (I) = 1 1 + 1≤i<j≤n [e i , e j ],
defined equivalently as

• the convex hull of the points x(τ

) := [τ -1 (i)] i∈[n] ∈ R n for all permutations τ ∈ S n , • the intersection of the hyperplane H = ([n]) := x ∈ R n | i∈[n] x i = n+1 2 with the half- spaces H ≥ (I) := x ∈ R n | i∈I x i ≥ |I|+1
2 for all proper non-empty subset

∅ = I [n],
• the Minkowski sum of the point 1 1 with the segments [e i , e j ] for 1 ≤ i < j ≤ n.

We consider a dilated and translated copy of the permutahedron Perm(n), which will fit better the other two families of polytopes defined later (see Remark 41 for a precise statement). Namely, we set

Perm k (n) := k Perm(n) - k(n + 1) 2 1 1.
Observe that Perm k (n) now lies in the hyperplane

H := x ∈ R n | i∈[n] x i = 0 .
Brick polytopes To define the brick polytope, we essentially follow [Pil10, PS12] except that we apply again a translation in direction 1 1 to obtain a polytope in the hyperplane H.

Definition 35. We call bricks the squares [i, i + 1] × [j, j + 1] of the triangular shape. The brick area of a pipe p is the number of bricks located below p but inside the axis-parallel rectangle defined by the two endpoints of p. The brick vector of a k-twist T is the vector x(T) ∈ R n whose ith coordinate is the brick area of the ith pipe of T, minus k(n+k)

2

. The brick polytope Brick k (n) is the polytope defined as the convex hull of the brick vectors of all (k, n)-twists.

As for the permutahedron described above, we know three descriptions of the brick polytopes: its vertex description, its hyperplane description, and a Minkowski sum description. These properties are proved in [START_REF] Pilaud | The brick polytope of a sorting network[END_REF] (modulo our translation in the direction 1 1).

Proposition 36 ([PS12]

). The brick polytope Brick k (n) has the following properties for any n, k ∈ N.

(i) It lies in the hyperplane

H := x ∈ R n | i∈[n] x i =
+ + + 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 + -+ 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 -- --- -- -+ - -+ -+ - + + + + + + + + + - + - + + - + + -+ - + + -+ + + - -+ - -+ -+ + -+ --+ -- --+ -- + -- + - + -- -+ + -+ -- + -+ + + + -+ + - + -+
4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 - -- --- - -- -+ - - -+ -+ - - + + -+ - + + + -+ - - + - -+ - - + - + + - + + - + + - - + - + -- - -- --+ - -- + -- - -+ -+ + - -+ --+ + -+ --+ + -+ -+ + + + + -+ + + + + + + + + + + + + - - -- + -+ + -- + -+ + + - + -+ + + + + -+ 3412
(n) is therefore the coefficient of t n in t 2 (2 -t k ) (1 -2t + t k+1 )(1 -t) .
(iv) For a brick b, let x b (T) denote the characteristic vector of the pipes of a (k, n)-twist T whose brick area contain b, and define Brick k b (n) to be the convex hull of the vectors x b (T) for all (k, n)-twists T. Then, up to the translation of vector k(n+k) 2 1 1, the brick polytope Brick k (n) is also the Minkowski sum of the polytopes Brick k b (n) over all bricks b.

Example 37 (J.-L. Loday's associahedron). When k = 1, the brick polytope Brick 1 (n) coincides (up to translation) with J.-L. Loday's associahedron [START_REF] Loday | Realization of the Stasheff polytope[END_REF]. See Figure 8 (top center).

Zonotopes Zonotopes are particularly important polytopes which are constructed equivalently as projections of cubes, or as Minkowski sums of segments. The combinatorics of a zonotope is completely determined by the matroid of the vector configuration defined by these summands. We refer to [Zie98, Lecture 7] for a presentation of these polytopes and their relations to oriented matroids. Notable examples are graphical zonotopes, defined as follows.

Definition 38. The graphical zonotope Zono(G) of a graph G is the Minkowski sum of the segments [e i , e j ] for all edges {i, j} of G.

The following classical statement gives the vertex and facet descriptions of graphical zonotopes.

Proposition 39. The graphical zonotope Zono(G) has the following properties for any graph G. For example, the permutahedron Perm(n) is the graphical zonotope of the complete graph, its vertices correspond to permutations of [n] (acyclic tournaments), and its facets correspond to proper subsets of [n] (minimal cuts). Here, we focus on the zonotope of G k (n) whose vertices correspond to the acyclic orientations in AO k (n) and whose facets correspond to minimal cuts of G k (n). As for the previous polytopes, we perturb this zonotope to fit the other two polytopes better (see Remark 41 for a precise statement), and thus define

Zono k (n) := 1≤i<j≤n λ(i, j, k, n) • [e i , e j ] - (n -1)(n + 3k -2) 6 1 1, where λ(i, j, k, n) :=      n + k -2|i -j| if |i -j| < k, min(i, n + 1 -j) n + k -1 -min(i, n + 1 -j) if |i -j| = k, 0 if |i -j| > k.
Note that this perturbation is only cosmetic and preserves the combinatorics. Indeed, observe that for all 1 ≤ i < j ≤ n, we have λ i,j,k,n = 0 if and only if |i -j| ≤ k. Therefore, the zonotopes Zono k (n) and Zono(G k (n)) have the same normal fan (see Section 2.2) and thus the same face lattice. The translation ensures that Zono k (n) lies in the hyperplane

H := x ∈ R n | i∈[n] x i = 0 .
Example 40 (Cube). When k = 1, the zonotope Zono 1 (n) coincides (up to translation and scaling) with the parallelotope generated by the simple roots e i+1 -e i . It has the same combinatorics as the n-dimensional cube. See Figure 8 (top right). Remark 41 (Geometric inclusions). We have chosen our normalizations (dilations and translations) so that the polytopes Perm k (n), Brick k (n) and Zono k (n) all leave in the hyperplane

H := x ∈ R n | i∈[n]
x i = 0 and fulfill the following inclusions:

1 k Brick k (n) 1 Brick (n) Perm(n) 1 k Zono k (n) 1 Zono (n) ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆ ⊆
These inclusions are illustrated in Figures 8, 9 and 10. Compare to Remark 33. Observe moreover that

Zono k (n) = Zono n-1 (n) + (k + 1 -n) Perm 1 (n)
for all k ≥ n -1. We therefore obtain that the rescaled polytopes 10). 2.2. The geometry of the surjections ins k , can k , and rec k . Besides Remark 41, the main geometric connection between the three polytopes Perm k (n), Brick k (n) and Zono k (n) is given by their normal fans. Remember that a polyhedral fan is a collection of polyhedral cones of R n closed under faces and which intersect pairwise along faces, see e.g. [Zie98, Lecture 7]. The (outer) normal cone of a face F of a polytope P is the cone generated by the outer normal vectors of the facets of P containing F . Finally, the (outer) normal fan of P is the collection of the (outer) normal cones of all its faces.

1 k Brick k (n) and 1 k Zono k (n) both converge to 1 k Perm k (n) = Perm 1 (n) when k tend to ∞ (see Figure
The incidence cone C( ) and the braid cone C ♦ ( ) of an poset are the polyhedral cones defined by C( ) := cone {e i -e j | for all i j} and C ♦ ( ) := {x ∈ H | x i ≤ x j for all i j} .

These two cones lie in the space H and are polar to each other. For a permutation τ ∈ S n (resp. a twist T ∈ AT k (n), resp. an orientation O ∈ AO k (n)), we slightly abuse notation to write C(τ ) (resp. C(T), resp. C(O)) for the incidence cone of the chain τ 1 • • • τ n (resp. of the transitive closure of the contact graph T # , resp. of the transitive closure of O). We define similarly the braid cone C ♦ (τ ) (resp. C ♦ (T), resp. C ♦ (O)). These cones (together with all their faces) form the normal fans of the polytopes of Section 2.1.

C ♦ (τ ) | τ ∈ S n , C ♦ (T) | T ∈ AT k (n) and C ♦ (O) | O ∈ AO k (n) ,
together with all their faces, are the normal fans of the permutahedron Perm k (n), the brick polytope Brick k (n) and the zonotope Zono k (n) respectively.

Observe moreover that the normal fan of Perm k (n) is also the collection of chambers of the Coxeter arrangement given by all hyperplanes {x ∈ H | x i = x j } for all i, j ∈ [n]. Similarly, the normal fan of Zono k (n) is also the collection of chambers of the graphical arrangement given by the hyperplanes {x ∈ H | x i = x j } for all edges {i, j} in G k (n).

Using these normal fans, one can interpret geometrically the maps ins k , can k , and rec k as follows.

Proposition 43. The insertion map ins k : S n → AT k (n), the k-canopy can k : AT k (n) → AO k (n) and the k-recoil map rec k : S n → AO k (n) are characterized by

T = ins k (τ ) ⇐⇒ C(T) ⊆ C(τ ) ⇐⇒ C ♦ (T) ⊇ C ♦ (τ ), O = can k (T) ⇐⇒ C(O) ⊆ C(T) ⇐⇒ C ♦ (O) ⊇ C ♦ (T), O = rec k (τ ) ⇐⇒ C(O) ⊆ C(τ ) ⇐⇒ C ♦ (O) ⊇ C ♦ (τ ).
Finally, the lattices studied in Section 1 also appear naturally in the geometry of the polytopes Perm k (n), Brick k (n) and Zono k (n). Denote by U the vector

U := (n, n -1, . . . , 2, 1) -(1, 2, . . . , n -1, n) = i∈[n] (n + 1 -2i) e i .
Proposition 44. When oriented in the direction U , the 1-skeleton of the permutahedron Perm k (n) (resp. of the brick polytope Brick k (n), resp. of the zonotope Zono k (n)) is the Hasse diagram of the weak order on permutations (resp. of the increasing flip lattice on acyclic (k, n)-twists, resp. of the increasing flip lattice on acyclic orientations of G k (n)).

Algebra of acyclic twists

Motivated by the Hopf algebra on binary trees constructed by J.-L. Loday and M. Ronco [START_REF] Loday | Hopf algebra of the planar binary trees[END_REF] as a subalgebra of the Hopf algebra on permutations of C. Malvenuto and C. Reutenauer (see also [START_REF] Hivert | The algebra of binary search trees[END_REF][START_REF] Aguiar | Structure of the Loday-Ronco Hopf algebra of trees[END_REF]), we define a Hopf algebra with bases indexed by acyclic k-twists. We then give combinatorial interpretations of the product and coproduct of this algebra and its dual in terms of k-twists. We finally conclude with further algebraic properties of this algebra.

3.1. Hopf algebras FQSym and FQSym * . We briefly recall here the definition and some elementary properties of C. Malvenuto and C. Reutenauer's Hopf algebra on permutations [START_REF] Malvenuto | Duality between quasi-symmetric functions and the Solomon descent algebra[END_REF]. We denote this algebra by FQSym to stress out its connection to free quasi-symmetric functions. We will however not use this connection in this paper. We denote by S := n∈N S n the set of all permutations, of arbitrary size.

For n, n ∈ N, let

S (n,n ) := {τ ∈ S n+n | τ 1 < • • • < τ n and τ n+1 < • • • < τ n+n }
denote the set of permutations of S n+n with at most one descent, at position n. The shifted concatenation τ τ , the shifted shuffle τ ¡ τ , and the convolution τ τ of two permutations τ ∈ S n and τ ∈ S n are classically defined by

τ τ := [τ 1 , . . . , τ n , τ 1 + n, . . . , τ n + n] ∈ S n+n , τ ¡ τ := (τ τ ) • π -1 | π ∈ S (n,n ) and τ τ := π • (τ τ ) | π ∈ S (n,n ) .
For Definition 45. We denote by FQSym the Hopf algebra with basis (F τ ) τ ∈S and whose product and coproduct are defined by

F τ • F τ = σ∈τ ¡ τ F σ and F σ = σ∈τ τ F τ ⊗ F τ .
This algebra is graded by the size of the permutations.

Proposition 46. A product of weak order intervals in FQSym is a weak order interval: for any two weak order intervals [µ, ω] and [µ , ω ], we have

µ≤τ ≤ω F τ • µ ≤τ ≤ω F τ = µμ ≤σ≤ω ω F σ .
Corollary 47. For τ ∈ S n , define

E τ = τ ≤τ F τ and H τ = τ ≤τ F τ
where ≤ is the weak order on S n . Then (E τ ) τ ∈S and (H τ ) τ ∈S are multiplicative bases of FQSym:

E τ • E τ = E τ \τ and H τ • H τ = H τ /τ , where τ \τ = τ τ and τ /τ = τ τ . A permutation τ ∈ S n is E-decomposable (resp. H-decomposable) if and only if there exists k ∈ [n -1] such that τ ([k]) = [k] (resp. such that τ ([k]) = [n] [k]).
Moreover, FQSym is freely generated by the elements E τ (resp. H τ ) for the E-indecomposable (resp. H-indecomposable) permutations.

We will also consider the dual Hopf algebra of FQSym, defined as follows.

Definition 48. We denote by FQSym * the Hopf algebra with basis (G τ ) τ ∈S and whose product and coproduct are defined by

G τ • G τ = σ∈τ τ G σ and G σ = σ∈τ ¡ τ G τ ⊗ G τ .
This algebra is graded by the size of the permutations.

3.2. Subalgebra of FQSym. We denote by Twist k the vector subspace of FQSym generated by the elements

P T := τ ∈S ins k (τ )=T F τ = τ ∈L(T # ) F τ ,
for all acyclic k-twists T. For example, for the (k, 5)-twists of Figure 4, we have

P 4 5 3 2 1 = τ ∈S5 F τ P 4 5 3 2 1 = F 13542 + F 15342 + F 31542 + F 51342 + F 35142 + F 53142 + F 35412 + F 53412 P 4 5 3 2 1 = F 31542 + F 35142 P 4 5 3 2 1 = F 31542 . Theorem 49. Twist k is a Hopf subalgebra of FQSym.
Proof. This statement is a particular case of the results of [START_REF] Reading | Lattice congruences, fans and Hopf algebras[END_REF]. Alternatively, we could also invoke the formalism of [Hiv04, HN07, Pri13] and just observe that the k-twist congruence ≡ k is compatible with the standardization and the restriction to intervals. A detailed proof can also be found in [START_REF] Pilaud | Brick polytopes, lattice quotients, and Hopf algebras[END_REF].

Example 50 (J.-L. Loday and M. Ronco's algebra). The bijection given in Example 3 (see also Figure 2) defines an isomorphism from the 1-twist algebra Twist 1 to M. Ronco and J.-L. Loday's Hopf algebra PBT on planar binary trees [START_REF] Loday | Hopf algebra of the planar binary trees[END_REF][START_REF] Hivert | The algebra of binary search trees[END_REF].

We now aim at understanding the product and the coproduct in Twist k directly on k-twists. Although they are not always as satisfactory, our descriptions naturally extend classical results on the binary tree Hopf algebra PBT described in [LR98, [START_REF] Aguiar | Structure of the Loday-Ronco Hopf algebra of trees[END_REF][START_REF] Hivert | The algebra of binary search trees[END_REF].

Product To describe the product in Twist k , we need the following notation, which is illustrated in Figure 11. For a (k, n)-twist T and a (k, n )-twist T , we denote by T\T the (k, n + n )-twist obtained by inserting T in the first rows and columns of T and by T/T the (k, n + n )-twist obtained by inserting T in the last rows and columns of T. Proposition 51. For any acyclic k-twists T ∈ AT k (n) and T ∈ AT k (n ), the product P T • P T is given by

P T • P T = S P S ,
where S runs over the interval between T\T and T/T in the (k, n+n )-twist lattice. See Figure 12.

Proof. Consider two acyclic k-twists T, T . By Proposition 17, their fibers under ins k are intervals of the weak order, which we denote by [µ, ω] and [µ , ω ] respectively. By Proposition 46, the product P T • P T is therefore the weak order interval [µμ , ω ω]. Theorem 49 ensures that this interval is partitioned into various fibers of ins k . In particular, the fiber of T\T contains µμ while the fiber of T/T contains ω ω. Proposition 17 finally ensures that [µμ , ω ω] is precisely the union of the fibers of the increasing flip interval [T\T , T/T ]. Coproduct Our description of the coproduct in Twist k is unfortunately not as simple as the coproduct in PBT. It is very closed to the description of the direct computation using the coproduct of FQSym. We need the following definition. A cut in a k-twist S is a set γ of edges of the contact graph S # such that any path in S # from a leaf to the root contains precisely one edge of γ. We then denote by A # (S, γ) (resp. B # (S, γ)) the restriction of the contact graph S # to the nodes above (resp. below) γ. Moreover, A # (S, γ) is the contact graph of the k-twist A(S, γ) obtained from S by deleting all pipes below γ in S # . Nevertheless, note that B # (S, γ) is not a priori the contact graph of a k-twist.

P 4 3 2 1 • P 2 1 = (F 1423 + F 4123 ) • F 21 = F 142365 + F 412365 +       F 142635 + F 146235 + F 412635 + F 416235 + F 461235       +   F 164235 + F 614235 + F 641235   +       F 142653 + F 146253 + F 412653 + F 416253 + F 461253       +   F 164253 + F 614253 + F 641253   +     F 146523 + F 416523 + F 461523 + F 465123     +     F 164523 + F 614523 + F 641523 + F 645123     +     F 165423 + F 615423 + F 651423 + F 654123     = P
Proposition 52. For any acyclic k-twist S ∈ AT k (m), the coproduct P S is given by

P S = γ τ P ins k (τ ) ⊗ P A(S,γ) ,
where γ runs over all cuts of S and τ runs over a set of representatives of the k-twist congruence classes of the linear extensions of B # (S, γ). See Figure 13.

Proof. By Theorem 49, any element of S is of the form ins k (τ ) ⊗ ins k (τ ) for some permutations τ ∈ S n and τ ∈ S n such that τ τ contains a linear extension σ of S # . Let γ denote the cut of S that separates σ({1, . . . , n}) from σ({n + 1, . . . n + n }). Then τ and τ are linear extensions of B # (S, γ) and A # (S, γ) respectively, so that ins k (τ ) ⊗ ins k (τ ) indeed appear in the sum on the right hand side. Conversely, for any cut γ of S and linear extensions τ of B # (S, γ) and τ of A # (S, γ), there is a linear extension σ of S # in τ τ , so that ins k (τ )⊗A(S, γ) = ins k (τ )⊗ins k (τ ) appears in S. Finally, we have to prove that the coproduct is boolean, meaning that only 0/1 coefficients may appear: this follows from the fact that we can reconstruct the cut γ from A(S, γ) and the k-twist congruence class of τ from ins k (τ ).

P 4 5 3 2 1 = (F 31542 + F 35142 ) = 1 ⊗ (F 31542 + F 35142 ) + F 1 ⊗ (F 1432 + F 4132 ) + F 21 ⊗ F 321 + F 12 ⊗ F 132 + F 213 ⊗ F 21 + F 231 ⊗ F 21 + F 2143 ⊗ F 1 + F 2413 ⊗ F 1 + (F 31542 + F 35142 ) ⊗ 1 = 1 ⊗ P 4 5 3 2 1 + P 1 ⊗ P 4 3 2 1 + P 2 1 ⊗ P 3 2 1 + P 2 1 ⊗ P 3 2 1 + P 3 2 1 ⊗ P 2 1 + P 3 2 1 ⊗ P 2 1 + P 4 3 2 1 ⊗ P 1 + P 4 3 2 1 ⊗ P 1 + P 4 5 3 2 1 ⊗ 1 Figure 13
. An example of coproduct in the 2-twist algebra Twist 2 .

Matriochka algebras

We now connect the twist algebra to the k-recoil algebra Rec k defined as the Hopf subalgebra of FQSym generated by the elements Remark 53 (Algebraic inclusions). Following Remarks 33 and 41, note that we have in fact the following inclusions of subalgebras for k > :

X O := τ ∈S rec k (τ )=O
Twist k Twist FQSym Rec k Rec ⊇ ⊇ ⊇ ⊇ ⊇ ⊇ ⊇ ⊇
We informally call this picture the diagram of Matriochka algebras.

3.3. Quotient algebra of FQSym * . The following statement is automatic from Theorem 49.

Theorem 54. The graded dual Twist k * of the k-twist algebra is the quotient of FQSym * under the k-twist congruence ≡ k . The dual basis Q T of P T is expressed as

Q T = π(G τ )
, where π is the quotient map and τ is any permutation such that ins k (τ ) = T.

Similarly as in the previous section, we try to describe combinatorially the product and coproduct of Q-basis elements of Twist k * in terms of operations on Cambrian trees.

Product Once more, our description of the product in the dual twist algebra is not as simple as the coproduct in PBT, and is very closed to the description of the direct computation using the coproduct of FQSym. We use the following notation. For

X = {x 1 < • • • < x n } ∈ [n+n ]
n , τ ∈ S n , and T ∈ AT k (n ), we denote by T (τ • X) the result of iteratively inserting x τn , . . . , x τ1 in the k-twist T relabeled increasingly by [n + n ] X.

Proposition 55. For any acyclic k-twists

T ∈ AT k (n) and T ∈ AT k (n ), the product Q T • Q T is given by Q T • Q T = X Q T (τ •X)
where X runs over [n+n ] n and τ is an arbitrary permutation such that ins k (τ ) = T. See Figure 14.

Proof. Consider τ ∈ S n and τ ∈ S n such that ins k (τ ) = T and ins k (τ ) = T , and a permutation σ in the convolution τ τ . Let X denote the first n values in σ. Since the relative order of the last n entries in σ is that of the entries of τ , the insertion of the last n values creates a copy of T . The remaining entries are then inserted in this copy of T at the positions given by X according to the order given by of τ . The result immediately follows.

proved that this property implies that the k-twist algebra admits a bidendriform structure (see also Section 3.6) and is therefore self-dual, free and cofree (see also Section 3.4). This intriguing selfduality property deserves further study. In particular, the map defined by Φ(P T ) = τ ∈L(T # ) Q σ -1 would be a natural candidate for an explicit self-duality [START_REF] Hivert | The algebra of binary search trees[END_REF].

3.4. Multiplicative bases and irreducible elements. In this section, we define multiplicative bases of Twist k and study the indecomposable elements of Twist k for these bases. For an acyclic (k, n)-twist T, we define

E T := T≤T P T and H T := T ≤T P T ,
where ≤ denotes the increasing flip lattice on acyclic (k, n)-twists. As the elements E T and H T have symmetric properties, we focus our analysis on E T . The reader is invited to translate the statements and proofs below to H T . We first observe that these elements can also be seen as elements of the multiplicative bases (E τ ) τ ∈S and (H τ ) τ ∈S of FQSym.

Lemma 57. For any acyclic k-twist T, we have E T = E µ and H T = H ω , where µ and ω respectively denote the weak order minimal and maximal permutations in the fiber of T under ins k .

Proof. We directly obtain from the definition that

E T = T≤T P T = T≤T τ ∈Sn ins k (τ )=T F τ = τ ∈Sn T≤ins k (τ ) F τ = τ ∈Sn µ≤τ F τ = E µ .
To describe the product of two elements of the E-or H-basis, remember that the twist T\T (resp. T/T ) is obtained by inserting T in the first rows and columns of T (resp. T in the last rows and columns of T). Examples are given in Figure 11.

E T • E T = E T\T and H T • H T = H T/T .
Proof. Let µ and µ respectively denote the minimal elements of the fibers of T and T under ins k . Using Lemma 57 and the fact that ins k µ\µ = T\T and µ\µ is minimal in its k-twist congruence class, we write

E T • E T = E µ • E µ = E µ\µ = E T\T .
We now consider multiplicative decomposability. We call cut of an acyclic oriented graph any partition (X Y ) of its vertices such that all edges between X and Y are oriented from X to Y .

Proposition 59. The following properties are equivalent for an acyclic k-twist S:

(i) E S can be decomposed into a product E S = E T • E T for non-empty acyclic k-twists T, T ; (ii) ([k] [n] [k]) is a cut of S # for some k ∈ [n -1]; (iii) at least one linear extension τ of S # is E-decomposable, i.e. τ ([k]) = [k] for some k ∈ [n];
(iv) the weak order minimal linear extension of S # is E-decomposable. The k-twist S is then called E-decomposable. Otherwise, it is called E-indecomposable, and we denote by IAT k (n) the set of E-indecomposable acyclic (k, n)-twists.

Proof. The equivalence (i) ⇐⇒ (ii) is an immediate consequence of the description of the product E T • E T = E T\T in Proposition 58. The implication (ii) =⇒ (iii) follows from the fact that for any cut (X Y ) of a directed acyclic graph G, there exists a linear extension of G which starts with X and finishes with Y . The implication (iii) =⇒ (iv) follows from the fact that the E-indecomposable permutations form an up ideal of the weak order. Finally, if τ is a decomposable linear extension of S, then the insertion algorithm on τ first creates a twist labeled by 3.5. Integer point transform. In this section, we observe that the product in the k-twist Hopf algebra Twist k can be interpreted in terms of the integer point transforms of the normal cones of the brick polytope Brick k (n). To make this statement precise, we introduce some notations.

Definition 63. The integer point transform Z S of a subset S of R n is the multivariate generating function of the integer points inside S:

Z S (t 1 , . . . , t n ) = (i1,...,in)∈Z n ∩S t i1 1 • • • t in n .
For a poset , we denote by Z the integer point transform of the cone C ( ) := x ∈ R n +

x i ≤ x j for all i j with i < j x i < x j for all i j with i > j .

Note that this cone differs in two ways from the cone C ♦ ( ) defined in Section 2.2: first it leaves in R n + and not in H, second it excludes the facets of C ♦ ( ) corresponding to the decreasing relations of (i.e. the relations i j with i > j).

Following the notations of Section 2.2, we denote by Z τ the integer point transform of the chain τ 1 • • • τ n for a permutation τ ∈ S n . The following statements are classical.

Proposition 64. (i) For any permutation τ ∈ S n , the integer point transform Z τ is given by

Z τ (t 1 , . . . , t n ) = i∈[n-1] τi>τi+1 t τi • • • t τn i∈[n] 1 -t τi • • • t τn .
(ii) The integer point transform of an arbitrary poset is given by

Z = τ ∈L( ) Z τ ,
where the sum runs over the set L( ) of linear extensions of . (iii) The product of the integer point transforms Z τ and Z τ of two permutations τ ∈ S n and τ ∈ S n is given by the shifted shuffle

Z τ (t 1 , . . . , t n ) • Z τ (t n+1 , . . . , t n+n ) = σ∈τ ¡ τ Z σ (t 1 , . . . , t n+n ).
In other words, the linear map from FQSym to the rational functions defined by Ψ : F τ → Z τ is an algebra morphism.

Proof. For Point (i), we just observe that the cone x ∈ R n + x τi ≤ x τi+1 for all i ∈ [n -1] is generated by the vectors e τi + • • • + e τn , for i ∈ [n], which form a (unimodular) basis of the lattice Z n . A straightforward inductive argument shows that the integer point transform of the cone

x ∈ R n + x τi ≤ x τi+1 for all i ∈ [n -1] is thus given by i∈[n] 1-t τi • • • t τn -1
. The numerator of Z τ is then given by the facets which are excluded from the cone C (τ ). Point (ii) follows from the fact that the cone C ( ) is partitioned by the cones C (τ ) for the linear extensions τ of .

Finally, the product Z τ (t 1 , . . . , t n ) • Z τ (t n+1 , . . . , t n+n ) is the integer point transform of the poset formed by the two disjoint chains τ and τ , whose linear extensions are precisely the permutations which appear in the shifted shuffle of τ and τ . This shows Point (iii).

For an acyclic k-twist T, we denote by Z T the integer point transform of the transitive closure of the contact graph T # . It follows from Proposition 64 that the product of the integer point transforms of two acyclic k-twists behaves as the product in the k-twist algebra Twist k .

Corollary 65. For any two acyclic k-twists T, T , we have

Z T (t 1 , . . . , t n ) • Z T (t n+1 , . . . , t n+n ) = T\T ≤ S ≤ T/T Z S (t 1 , . . . , t n+n ).
Proof. Hiding the variables (t 1 , . . . , t n+n ) for concision, we have

Z T • Z T = Ψ(P T ) • Ψ(P T ) = Ψ(P T • P T ) = Ψ S P S = S Ψ(P S ) = S Z S ,
where the sums run over the k-twists S of the increasing flip lattice interval [T\T , T/T ].

3.6. k-twistiform algebras. In this section, we extend the notion of dendriform algebras to ktwistiform algebras. Dendriform algebras were introduced by J.-L. Loday in [Lod01, Chap. 5]. In a dendriform algebra, the product • is decomposed into two partial products ≺ and satisfying:

x ≺ y • z = x ≺ y ≺ z, x y ≺ z = x y ≺ z, x y z = x • y z.
In our context, we will still decompose the product of FQSym (and of Twist k ) into partial products, but we will use 2 k partial products satisfying 3 k relations. In this paper, we just give the definition and observe that the algebras FQSym and Twist k are naturally endowed with a k-twistiform structure, as they motivated the definition. A detailed study of combinatorial and algebraic properties of k-twistiform algebras and operads is in progress in a joint work with F. Hivert [START_REF] Hivert | Multitwistiform algebras and operads[END_REF]. We need to fix some natural notations on words. We denote by |W | the length of a word W . For a subset P of positions in W and a subset L of letters of W , we denote by W P the subword of W consisting only of the letters at positions in P and by W L the subword of W consisting only of the letters which belong to L. Definition 66. A k-twistiform algebra is a vector space Alg endowed with a collection B := {≺, ≺ , } k of 3 k bilinear operations which satisfy the following k3 k-1 + 3 k relations: Example 67 (1-and 2-twistiform algebras). 1-twistiform algebras are precisely dendriform algebras, i.e. vector spaces endowed with three operations ≺, ≺ , which fulfill the 4 relations:

x ≺ y = x ≺ y + x y, x ≺ y ≺ z = x ≺ y ≺ z, x y ≺ z = x y ≺ z, x y z = x ≺ y z.

2-twistiform algebras are vector spaces endowed with 9 operations ≺≺, ≺≺ , ≺ , ≺ ≺, ≺ ≺ , ≺ , ≺, ≺ , which satisfy the following 15 relations: Remark 68. Adding up all associativity relations, one obtains that

x ≺ k y ≺ k z = x ≺ k y ≺ k z for all x, y, z ∈ Alg, so that the k-twistiform algebra (Alg, {≺, ≺ , } k ) defines in particular a structure of associative algebra (Alg, ≺ k ). Reciprocally, we say that an associative algebra (Alg, •) admits a k-twistiform structure if it is possible to split the product • into 3 k operations B := {≺, ≺ , } k defining a ktwistiform algebra on Alg.

We now show that C. Malvenuto and C. Reutenauer's Hopf algebra on permutations FQSym can be endowed with a structure of k-twistiform algebra. For an operation b ∈ B and two words X := xX and Y := yY , we define

X b Y =          X ¡ Y if b = ∅, x(X b Y ) if b = ≺b, x(X b Y ) ∪ y(X b Y ) if b = ≺ b, y(X b Y ) if b = b
with the initial conditions X b ∅ = ∅ ≺b Y = 0.

In other words, we consider the shuffle of X and Y , except that the ith letter of X b Y is forced to belong to X (resp. to Y ) if the ith letter of b is ≺ (resp. is ). For example, when k = 1, the three operators are given by Proposition 69. The Hopf algebra FQSym, endowed with the operations B described above, defines a k-twistiform algebra. The product of FQSym is then given by • = ≺ k .

X ≺ Y = x(X ¡ Y ), X ≺ Y = X ¡ Y, X Y = y(X ¡ Y ),
Proof. We have to show that the operations defined above on FQSym indeed satisfy the k3 k-1 + 3 k relations of Definition 66. Proof. Let T be an acyclic k-twist. We claim that the last k entries are the same in all linear extensions of T # . Indeed, pick a linear extension τ of T # and let T := ∅ τ n • • • τ n-k+1 denote the k-twist obtain after the insertion of the last k values of τ . All pipes of T are then comparable by Lemma 30 and will be comparable to all other pipes in T = T τ n-k • • • τ 1 . Thus the last k values of τ form a chain at the end of the contact graph T # .

It then follows that the operation b • stabilizes Twist k for any b ∈ B. Indeed, for any two acyclic twists T ∈ AT k (n) and T ∈ AT k (n ), we have

P T b • P T = S P S
where the sum runs over all acyclic twists S ∈ AT k (n + n ) such that T\T ≤ S ≤ T/T and σ n+n +1-i ≤ n if b i = ≺ and σ n+n +1-i > n if b i = for any linear extension σ of S # .

Remark 71. One can also define similarly k-cotwistiform coalgebras, and such a structure on both FQSym and Twist k . Details will be given in [START_REF] Hivert | Multitwistiform algebras and operads[END_REF].

Figure 1 .Figure 2 .

 12 Figure 1. (k, 5)-twists (top) and their contact graphs (bottom) for k = 0, 1, 2, 3.

Figure 3

 3 Figure 3 illustrates the insertion of 4 in the (k, 5)-twists of Figure 1 relabeled by [2, 3, 6, 8, 9]. The following statement is an immediate consequence of the definition of pipe insertion.

Figure 3 .

 3 Figure 3. Inserting 4 in the (k, 5)-twists of Figure 1. The inserted pipe is in bold red.

Figure 5 .

 5 Figure 5. The k-twist congruence classes on S 4 for k = 1 (left) and k = 2 (right).

Figure 7 .

 7 Figure 7. The k-recoil congruence classes on S 4 for k = 1 (left) and k = 2 (right).

  the fiber of O by the k-recoil map is the set of linear extensions of the transitive closure of O. Definition 26. The k-recoil congruence ≈ k on S n is the transitive closure of the rewriting rule

  0 and has dimension n -1. (ii) The vertices of Brick k (n) are precisely the brick vectors of the acyclic (k, n)-twists. (iii) The normal vectors of the facets of Brick k (n) are given by the proper k-connected {0, 1}sequences of size n, i.e. the sequences of {0, 1} n distinct from 0 n and 1 n and which do not

Figure 8 .

 8 Figure 8. The permutahedron Perm k (4) (left), the brick polytope Brick k (4) (middle) and the zonotope Zono k (4) (right) for k = 1 (top), k = 2 (middle) and k = 3 (bottom). For readability, we represent orientations of G k (n) by pyramids of signs.

( i )

 i The dimension of Zono(G) is the number of edges of a maximal cycle-free subgraph of G. (ii) The vertices of Zono(G) correspond to the acyclic orientations of G. The ith coordinate of the vertex x(O) of Zono(G) corresponding to an acyclic orientation O of G is the indegree of vertex i in O. (iii) The facets of Zono(G) correspond to minimal cuts of G.

Figure 9 .

 9 Figure 9. The inclusions Perm k(n) ⊆ Brick k (n) ⊆ Zono k (n) for k = 1 (left), k = 2 (middle) and k = 3 (right). The permutahedron Perm k (n) is in blue, the brick polytope Brick k (n) in red and the zonotope Zono k (n) in green.

Figure 10 .

 10 Figure 10. The inclusions of the brick polytopes 1 k Brick k (4) (left) and of the zonotopes 1k Zono k (4) (right) for k = 1 (red), k = 2 (orange) and k = 3 (green). Both tend to the classical permutahedron Perm 1 (4) (blue) when k tends to ∞.

Figure 11 .

 11 Figure 11. Two twists T, T (left) and the two twists T\T and T/T (right).

Figure 12 .

 12 Figure 12. An example of product in the 2-twist algebra Twist 2 .

F

  τ , for all acyclic orientations O of the graph G k (n) for all n ∈ N. This algebra was first defined by J.-C. Novelli, C. Reutenauer and J.-Y. Thibon in [NRT11] (the dual of Rec k is denoted DSym k in their paper). The commutative diagram of Proposition 32 ensures that X O = T∈AT k can k (T)=O P T , and thus that Rec k is a Hopf subalgebra of Twist k .

  Proposition 58. (E T ) T∈AT k and (H T ) T∈AT k are multiplicative bases of Twist k :

  [n] [k] and then inserts the pipes labeled by [k]. Any arc between [k] and [n] [k] in S = ins k (τ ) will thus be directed from [k] to [n] [k].

≺≺

  Split relations: For any b, b ∈ {≺, ≺ , } * with |b| + |b | = k -1, the operation b≺ b ∈ B decomposes into the operations b≺b ∈ B and b b ∈ B: x b≺ b y = x b≺b y + x b b y for all x, y ∈ Alg. Associativity relations: For any W ∈ {x, y, z} k , the operations b W , b W , b W , b W ∈ B defined by (b W ) p := ≺ if W p = x if W p ∈ {y, z} (b W ) p := if |W {y,z} | ≥ p and (W {y,z} ) p = y if |W {y,z} | ≥ p and (W {y,z} ) p = z ≺ otherwise (b W ) p := if |W {x,y} | ≥ p and (W {x,y} ) p = x if |W {x,y} | ≥ p and (W {y,z} ) p = y ≺ otherwise (b W ) p := ≺ if W p ∈ {x, y} if W p = z satisfy the associativity relation x b W y b W z = x b W y b W z for all x, y, z ∈ Alg.

x

  ≺ ≺ y = x ≺≺ y + x ≺ y, x ≺ ≺ y = x ≺≺ y + x ≺ y, x ≺ y = x ≺ y + x y, x ≺≺ y = x ≺≺ y + x ≺ y, x ≺ ≺ y = x ≺ ≺ y + x ≺ y, x ≺ y = x ≺ y + x y, x ≺≺ y ≺ ≺ z = x ≺≺ y ≺≺ z, x ≺ y ≺≺ z = x ≺ y ≺≺ z, x ≺ y ≺ z = x ≺≺ y ≺ z, x ≺ y ≺≺ z = x ≺ y ≺≺ z, x y ≺≺ z = x y ≺≺ z, x y ≺ z = x ≺ y ≺ z, x ≺ y ≺ z = x ≺≺ y ≺ z, x y ≺ z = x ≺ y ≺ z, x y z = x ≺ ≺ y z.

  with the initial conditions X ∅ = ∅ ≺ Y = 0. Now for an operation b ∈ B and two permutations τ ∈ S n and τ ∈ S n , we define τ b τ = τ b τ , where τ is the permutation τ shifted by the length n of τ . Equivalently, τ b τ is the set of permutations σ ∈ τ ¡ τ such that for all i ∈ [k], we haveσ i ≤ n if b i = ≺ while σ i > n if b i = .Finally, we define the operations B on the Hopf algebra FQSym itself byF τ b F τ = σ∈τ b τ F σ .

  Split relations: Let b, b ∈ {≺, ≺ , } * with |b| + |b | = k -1. It is immediate from the definitions that X b≺ b Y = (X b≺b Y ) ∪ (X b b Y ) for any two words X, Y . Associativity relations: Let W ∈ B. It follows from the definition of the operations b W , b W , b W and b W that for any words X, Y, Z Xb W (Y b W Z) = (X b W Y ) b W Z is the set of all words in X ¡ Y ¡ Z whose pth letter is in the word X if W p = x, in the word Y if W p =y and in the word Z if W p = z. These equalities of sets then translate to the desired linear relations on the corresponding operations in FQSym.We say that the operations B define the forward k-twistiform structure on FQSym. There is also a backward k-twistiform structure on FQSym which considers the last k letters rather than the first k ones. Namely, for each operation b ∈ B, define an operation b• by V b • W = (V • b W • ) • where W • = w n • • • w 1 denotes the mirror of a word W = w 1 • • • w n .Clearly, the operations b • for b ∈ B still fulfill the relations of Definition 66. We have chosen to define the forward ktwistiform structure as it leads to a simpler presentation, but we need this backward k-twistiform structure in the next statement to be coherent with the insertion in k-twists (whose direction was chosen consistently with J.-L. Loday and M. Ronco's conventions).Proposition 70. The subalgebra Twist k of FQSym is stable by the operations b • for b ∈ B and therefore inherits a k-twistiform structure.

CNRS & LIX, École Polytechnique, Palaiseau E-mail address: vincent.pilaud@lix.polytechnique.fr URL: http://www.lix.polytechnique.fr/~pilaud/

Acknoledgements

I am grateful to N. Bergeron and C. Ceballos for sharing their preliminary results on Hopf algebras on pipe dreams, to N. Reading for pointing out relevant references and sharing his expertise on lattice congruences, and to F. Hivert for very interesting discussions on monoids, Hopf algebras, and dendriform structures. I also thank three anonymous referees for relevant suggestions on this paper.

Partially supported by the Spanish MICINN grant MTM2011-22792 and by the French ANR grants EGOS (12 JS02 002 01) and SC3A (15 CE40 0004 01).

Coproduct Our description of the coproduct is more satisfactory. It is a special case of a coproduct on arbitrary pipe dreams studied by N. Bergeron and C. Ceballos [BC14]. We need the following notations, illustrated in Figure 15. For an acyclic (k, m)-twist S and a position p ∈ {0, . . . , m}, we define two k-twists L(S, p) ∈ AT k (p) and R(S, p) ∈ AT k (m -p) as follows. The twist L(S, p) is obtained by erasing the last m -p pipes in S and glide the elbows of the remaining pipes as northwest as possible. More precisely, each elbow e of one of the first p pipes is translated one step north (resp. west) for each of the last m -p pipes passing north (resp. west) of e. The definition is similar for R(S, p), except that we erase the first p pipes instead of the last m -p pipes. Proposition 56. For any acyclic k-twist S ∈ AT k (m), the coproduct Q S is given by

See Figure 16.

Proof. Consider σ ∈ S m such that ins k (σ) = S, let p ∈ {0, . . . , m}, and let τ ∈ S p , τ ∈ S m-p be the two permutations such that σ ∈ τ ¡ τ . By definition, τ (resp. τ ) is given by the relative order of the first p (resp. last m -p) values of σ. It is immediate to see that the insertion process then gives ins k (τ ) = L(S, p) and ins k (τ ) = R(S, p). The result follows.

. An example of coproduct in the dual 2-twist algebra Twist 2 * .

Self-duality Note that the contact graph of any k-twist has a unique sink. It follows that the last entry of the permutations in a ≡ k -congruence class is constant. S. Giraudo [Gir11, Prop. 5.2.11]

Example 60 (Right-tilting k-twists). Say that a k-twist is right-tilting when it has no elbow in its first column. When k = 1, the E-indecomposable 1-twists are precisely the right-tilting 1-twists. Therefore, the number of E-indecomposable (1, n)-twists is the Catalan number C n-1 , and the E-indecomposable (1, n)-twists form a principal ideal of the increasing flip lattice. When k ≥ 2, right-tilting k-twists are E-indecomposable, but are not the only ones. The E-indecomposable (k, n)-twists form an upper ideal of the increasing flip lattice, but this ideal is not principal. Figure 17 illustrates the E-indecomposable acyclic (k, 4)-twists for k = 1, 2.

Proposition 61. The k-twist algebra is freely generated by the elements E T such that T is E-indecomposable.

Proof. Let T be an acyclic k-twist and let µ be the weak order minimal permutation such that ins k (µ) = T. Decompose µ = µ 1 \. . .\µ p into E-indecomposable permutations µ 1 , . . . , µ p . For i ∈ [p], define T i := ins k (µ i ). Since µ i avoids the patterns (k + 2)1 -(σ 1 + 1) -• • • -(σ k + 1) for all σ ∈ S k (because µ avoids these patterns), it is the weak order minimal permutation in the fiber of T i . Since µ i is E-indecomposable, we get by Proposition 59 (iv) that T i is E-indecomposable. Using Lemma 57, we thus obtained a decomposition

Now, there is no relation between the elements E τ of FQSym corresponding to the E-indecomposable permutations. Hence, by Lemma 57 and Proposition 58, there is no relation between the elements E T of Twist k corresponding to the E-indecomposable k-twists.

Corollary 62. The generating functions of the numbers of E-indecomposable acyclic (k, n)-twists and of the numbers of all acyclic (k, n)-twists are related by

Again, the E-indecomposable 1-twists are precisely the right-tilting 1-twists, and are therefore counted by the Catalan number C n-1 . Analogous results for k ≥ 2 remain to be found.