Vincent Pilaud

HOPF ALGEBRAS ON DECORATED NONCROSSING ARC DIAGRAMS

Noncrossing arc diagrams are combinatorial models for the equivalence classes of the lattice congruences of the weak order on permutations. In this paper, we provide a general method to endow these objects with Hopf algebra structures. Specific instances of this method produce relevant Hopf algebras that appeared earlier in the literature.

Introduction

Combinatorial Hopf algebras are combinatorial vector spaces endowed with a product (that combines combinatorial objects) and a coproduct (that decomposes combinatorial objects), subject to a strong compatibility relation. This paper is motivated by two particularly relevant combinatorial Hopf algebras: C. Malvenuto and C. Reutenauer's Hopf algebra MR on permutations [START_REF] Malvenuto | Duality between quasi-symmetric functions and the Solomon descent algebra[END_REF] and J.-L. Loday and M. Ronco's Hopf algebra LR on binary trees [START_REF] Loday | Hopf algebra of the planar binary trees[END_REF]. Remarkably [START_REF] Hivert | The algebra of binary search trees[END_REF], LR embeds as a Hopf subalgebra of MR by sending each binary tree T to the sum of the permutations in a certain class L(T). More precisely, the permutations in L(T) are the linear extensions of T (seen as the Hasse diagram of a poset oriented towards its root), or equivalently the permutations whose insertion in a binary search tree gives T. The resulting classes are equivalence classes of the sylvester congruence [START_REF] Hivert | The algebra of binary search trees[END_REF] on permutations, defined as the transitive closure of the rewriting rule U acV bW ≡ sylv U caV bW where a < b < c are letters while U, V, W are words on N.

The objective of the present work is to discuss similar Hopf algebra structures on congruence classes of all lattice quotients of the weak order on S n . Several examples of relevant combinatorial structures arise from lattice quotients of the weak order. The fundamental example is the Tamari lattice introduced by D. Tamari in [START_REF] Tamari | Monoides préordonnés et chaînes de Malcev[END_REF] and largely studied since then (see the survey book [START_REF]Associahedra, Tamari Lattices and Related Structures[END_REF]). It can be defined as the transitive closure of right rotations on binary trees. It is also (isomorphic to) the quotient of the weak order on S n by the above-mentioned sylvester congruence. See Figure 1. Many other relevant lattice quotients of the weak order have been studied, see in particular [Rea06, CP17, PP18, LR12, Gir12, Law14, Pil18]. N. Reading provided in [START_REF] Reading | Noncrossing arc diagrams and canonical join representations[END_REF] a powerful combinatorial description of the lattice congruences of the weak order and of their congruence classes in terms of collections of certain arcs and noncrossing arc diagrams.

The search for Hopf algebra structures on congruence classes of lattice quotients of the weak order was pioneered by N. Reading. In [START_REF] Reading | Lattice congruences, fans and Hopf algebras[END_REF], he studied Hopf subalgebras of MR generated by sums of permutations over the classes of a fixed lattice congruence ≡ n on each S n for n ≥ 0. He called translational (resp. insertional) certain families (≡ n ) n∈N of congruences that yield a subalegbra (resp. subcoalgebra). This approach produces relevant Hopf algebras indexed by interesting combinatorial objects such as permutations [START_REF] Malvenuto | Duality between quasi-symmetric functions and the Solomon descent algebra[END_REF], binary trees [START_REF] Loday | Hopf algebra of the planar binary trees[END_REF], diagonal rectangulations [START_REF] Law | The Hopf algebra of diagonal rectangulations[END_REF] (or equivalently twin binary trees [START_REF] Giraudo | Algebraic and combinatorial structures on pairs of twin binary trees[END_REF]), sashes [START_REF] Law | Combinatorial realization of the Hopf algebra of sashes[END_REF], certain pipe dreams called twists [START_REF] Pilaud | Brick polytopes, lattice quotients, and Hopf algebras[END_REF], etc. However, the conditions on these families of congruences are rather constrained.

A more recent approach, initiated by G. Chatel and V. Pilaud for the Cambrian algebra [CP17] and extended by V. Pilaud and V. Pons for the permutree algebra [START_REF] Pilaud | Permutrees[END_REF], consists of constructing subalgebras of decorated versions of the algebra MR. For example, [START_REF] Chatel | Cambrian Hopf Algebras[END_REF] considers simultaneously all Cambrian congruences defined in [START_REF] Reading | Cambrian lattices[END_REF]. These congruences are given by certain rewriting rules [START_REF] Reading | Cambrian lattices[END_REF] generalizing the sylvester congruence, and their classes are given by linear extensions of certain Cambrian trees [START_REF] Lange | Associahedra via spines[END_REF][START_REF] Chatel | Cambrian Hopf Algebras[END_REF] generalizing binary trees. Since these congruences depend on a sequence of signs, the Cambrian algebra of [START_REF] Chatel | Cambrian Hopf Algebras[END_REF] is constructed as a subalgebra of a Hopf algebra on signed permutations generalizing MR and studied by J.-C. Novelli and J.-Y. Thibon in [START_REF] Novelli | Free quasi-symmetric functions and descent algebras for wreath products, and noncommutative multi-symmetric functions[END_REF]. The same idea was used in [START_REF] Pilaud | Permutrees[END_REF] to construct an algebra on permutrees. Note that the Hopf algebra of [START_REF] Novelli | Free quasi-symmetric functions and descent algebras for wreath products, and noncommutative multi-symmetric functions[END_REF] on signed permutations is also useful for type B generalizations, see for instance [START_REF] Fromentin | A divisibility result in combinatorics of generalized braids[END_REF][START_REF] Josuat-Vergès | The algebraic combinatorics of snakes[END_REF].

In this paper, we explore this approach further to construct Hopf algebras on other families of congruences of the weak order. Starting with a graded set of decorations X endowed with an operation of concatenation and an operation of selection that fulfill natural compatibility relations (see Definition 9), we construct a Hopf algebra on permutations decorated with elements of X. Provided a well-chosen map Ψ from the decoration set X to the lattice congruences of the weak order (see Definition 15), we then construct a Hopf algebra on the classes of the lattice congruences in the image of Ψ. This algebra is obtained as a Hopf subalgebra of the Hopf algebra of X-decorated permutations. The choice of X and Ψ leaves quite some flexibility and allows to construct different relevant Hopf algebras on lattice congruence classes. In this paper, we apply this general recipe in two particular settings:

(i) In the first setting, the image of Ψ is a family of lattice congruences of the weak order that simultaneously generalize the permutree congruences of [START_REF] Pilaud | Permutrees[END_REF] and the twist congruences of [START_REF] Pilaud | Brick polytopes, lattice quotients, and Hopf algebras[END_REF]. The resulting Hopf algebra contains (as Hopf subalgebras) those of [START_REF] Pilaud | Permutrees[END_REF][START_REF] Pilaud | Brick polytopes, lattice quotients, and Hopf algebras[END_REF].

(ii) In the second setting, the map Ψ is surjective so that we obtain a Hopf algebra involving the classes of all lattice congruences of the weak order. It contains (as Hopf subalgebras) the algebras of [MR95, LR98, CP17, PP18] but not those of [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][START_REF] Pilaud | Brick polytopes, lattice quotients, and Hopf algebras[END_REF].

Let us mention that, although our method covers simultaneously all lattice congruences and allows quite some flexibility on the resulting Hopf algebra structure, it is restricted to lattice congruences of the weak order. Many monoid congruences are not lattice congruences of the weak order, but give rise to relevant subalgebras of MR. For instance, the plactic monoid related to the Robinson-Schensted-Knuth insertion gives rise to the Hopf algebra of S. Poirier and C. Reutenauer on Young tableaux [START_REF] Poirier | Algèbres de Hopf de tableaux[END_REF].

The paper is organized as follows. In Section 2, we first recall N. Reading's combinatorial model for lattice quotients of the weak order on S n in terms of arc diagrams, and provide a combinatorial description of the surjection map from permutations to noncrossing arc diagrams of any fixed lattice congruence of S n . In Section 3, we present our general recipe to construct Hopf algebras on permutations and arc diagrams decorated with a given decoration set. Finally, Section 4 is devoted to some relevant applications of this general recipe.

Lattice congruences of the weak order and arc diagrams

We first review a powerful combinatorial interpretation of the lattice quotients of the weak order on permutations in terms of arc diagrams. All results presented in this section are either borrowed or directly follow from N. Reading's work on noncrossing arc diagrams [START_REF] Reading | Noncrossing arc diagrams and canonical join representations[END_REF].

2.1. Canonical representations of permutations and noncrossing arc diagrams. Consider a finite lattice (L, ≤, ∧, ∨). A join representation of x ∈ L is a subset J ⊆ L such that x = J. Such a representation is irredundant if x = J for a strict subset J J. The irredundant join representations of an element x ∈ L are ordered by containment of the lower ideals of their elements, i.e. J ≤ J if and only if for any y ∈ J there exists y ∈ J such that y ≤ y in L. When this order has a minimal element, it is called the canonical join representation of x. All elements of the canonical join representation x = J are then join-irreducible, i.e. cover a single element. A lattice is join-semidistributive when every element has a canonical join representation. Equivalently [FN95, Thm. 2.24], x ∨ z = y ∨ z =⇒ x ∨ z = (x ∧ y) ∨ z for any x, y, z ∈ L. Canonical meet representations, meet-irreducible elements and meet-semidistributive lattices are defined dually. A lattice is semi-distributive if it is both join-and meet-semidistributive.

Let . An inversion of σ = σ 1 . . . σ n ∈ S n is a pair (σ i , σ j ) such that i < j and σ i > σ j . Denote by inv(σ) the inversion set of σ. The weak order on S n is defined by inclusion of inversion sets, that is σ ≤ τ if and only if inv(σ) ⊆ inv(τ ). Its minimal (resp. maximal) element is the permutation 1 . . . n (resp. n . . . 1) and its cover relations correspond to swapping two consecutive entries in a permutation. See Figure 1. The weak order on S n is known to be a semidistributive lattice. The canonical join and meet representations of a permutation σ were explicitly described by N. Reading in [START_REF] Reading | Noncrossing arc diagrams and canonical join representations[END_REF] as follows.

A descent (resp. ascent)

in σ = σ 1 . . . σ n ∈ S n is a position i ∈ [n -1] such that σ i > σ i+1 (resp. σ i < σ i+1 ).
For a descent i of σ, define λ(σ, i) to be the permutation whose entries are given by 1 . . . (σ i+1 -1) followed by {σ j | j < i, σ j ∈ ]σ i+1 , σ i [} in increasing order, then σ i σ i+1 , then {σ j | j > i + 1, σ j ∈ ]σ i+1 , σ i [} in increasing order, and finally (σ i + 1) . . . n. This permutation λ(σ, i) is join-irreducible since it has a unique descent σ i > σ i+1 . We define dually a meetirreducible permutation λ(σ, i) := ω • λ(ω • σ, i) for each ascent i of σ, where ω • := [n, n -1, . . . , 2, 1] is the longest permutation of S n .

Theorem 1 ([Rea15, Thm. 2.4]). The canonical join and meet representations of a permutation σ = σ 1 . . . σ n are given by {λ(σ, i) | σ i > σ i+1 } and λ(σ, i) σ i < σ i+1 .

As N. Reading observed in [START_REF] Reading | Noncrossing arc diagrams and canonical join representations[END_REF], the permutation λ(σ, i) is uniquely determined by the values σ i and σ i+1 and by the set {σ j | j < i, σ j ∈ ]σ i+1 , σ i [}. This combinatorial data can be recorded in the following combinatorial gadgets.

An arc is a quadruple (a, b, n, S) where a, b, n ∈ N are such that 1 ≤ a < b ≤ n, and S ⊆ ]a, b[. We define A n := {(a, b, n, S) | 1 ≤ a < b ≤ n and S ⊆ ]a, b[}, and A := n∈N A n . For a permutation σ ∈ S n , we denote by α(i, i + 1, σ) := (σ i+1 , σ i , n, {σ j | j < i and σ j ∈ ]σ i+1 , σ i [ }) the arc associated to a descent i of σ and by δ(σ) := {α(i, i + 1, σ) | σ i > σ i+1 } the set of arcs corresponding to all descents of σ. We define α and δ dually for ascents.

An arc (a, b, n, S) can be visually represented as an x-monotone continuous curve wiggling around the horizontal axis, with endpoints a and b, and passing above the points of S and below the points of ]a, b[ S. Using this representation, N. Reading provided a convenient visual interpretation of δ and δ. For this, represent the permutation σ by its permutation table (σ i , i). (This unusual choice of orientation is necessary to fit later with the existing constructions [LR98, HNT05, CP17, PP18].) Draw arcs between any two consecutive dots (σ i , i) and (σ i+1 , i + 1), colored green if σ i < σ i+1 is an ascent and red if σ i > σ i+1 is a descent. Then move all dots down to the horizontal axis, allowing the segments to curve, but not to cross each other nor to pass through any dot. The set of red (resp. green) arcs is then the set δ(σ) (resp. δ(σ)) corresponding to the canonical join (resp. meet) representation of σ. See Figure 2 for illustrations of these maps. This representation provides a natural characterization of the sets of join-irreducible (resp. meetirreducible) permutations that form canonical join (resp. meet) representations. We say that two arcs cross if the interior of the two curves representing these arcs intersect. In other words, the arcs (a, b, n, R) and (c, d, n, S) cross if there exist r, s

∈ [a, b] ∩ [c, d] {a, b} ∩ {c, d} such that r ∈ R ∪ {a, b} S while s ∈ S ∩ {c, d} R.
A noncrossing arc diagram is a collection D of arcs of A n such that for any two arcs α, β ∈ D do not cross and have distinct left endpoints and distinct right endpoints (but the right endpoint of α can be the left endpoint of β or vice versa). See Figure 2 2.2. Lattice quotients of the weak order. Consider a finite lattice (L, ≤, ∧, ∨). A lattice congruence of L is an equivalence relation on L that respects the meet and the join operations, i.e. such that x ≡ x and y ≡ y implies x ∧ y ≡ x ∧ y and x ∨ y ≡ x ∨ y . Equivalently, the equivalence classes of ≡ are intervals of L, and the up and down maps π ↑ ≡ and π ≡ ↓ , respectively sending an element of L to the top and bottom elements of its equivalence class for ≡, are orderpreserving. A lattice congruence ≡ defines a lattice quotient L/≡ on the congruence classes of ≡ where the order relation is given by X ≤ Y if and only if there exists x ∈ X and y ∈ Y such that x ≤ y. 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 . Intuitively, the quotient L/≡ is obtained by contracting the equivalence classes of ≡ in the lattice L. More precisely, we say that an element x is contracted by ≡ if it is not minimal in its equivalence class of ≡, i.e. if x = π ≡ ↓ (x). As each class of ≡ is an interval of L, it contains a unique uncontracted element, and the quotient L/≡ is isomorphic to the subposet of L induced by its uncontracted elements. Moreover, the canonical join representations in the quotient π ≡ ↓ (L) are precisely the Example 5. The sets of all arcs A n , the set of upper arcs

A + n := {(a, b, n, ]a, b[) | 1 ≤ a < b ≤ n}, the set of lower arcs A - n := {(a, b, n, ∅) | 1 ≤ a < b ≤ n}, or the union A + n ∪ A -
n are all arc ideals. More generally, fix four functions n, s, e, w : [n] → N and choose k ∈ N. For each a ∈ [n], draw n(a) upper vertical walls above a, s(a) lower vertical walls below a, and min(e(a), w(a + 1)) horizontal walls from a and a + 1. Then the set A <k n,s,e,w of arcs that cross at most k -1 of all these walls is an arc ideal. For certain choices of n, s, e, w and k, the resulting arc ideals can correspond to:

• the weak order (n = s = e = w = 0 and k = 1),

• the Tamari lattice [START_REF] Tamari | Monoides préordonnés et chaînes de Malcev[END_REF] (n = e = w = 0 and s = k = 1),

• the boolean lattice (n = s = k = 1 and e = w = 0),

• the lattice of diagonal rectangulations [LR12] (n = s = 0 and e = w = k = 1),

• the permutree lattices [START_REF] Pilaud | Permutrees[END_REF] (n ≤ 1, s ≤ 1, e = w = 0 and k = 1),

• the lattice of sashes [START_REF] Law | Combinatorial realization of the Hopf algebra of sashes[END_REF] (n = 1, s = 2, e = w = 0 and k = 2),

• the lattice of acyclic k-twists [START_REF] Pilaud | Brick polytopes, lattice quotients, and Hopf algebras[END_REF] (n = e = w = 0, s = 1 and k ≥ 1),

• the lattice of k-descent schemes [NRT11, Pil18] (n = s = 1, e = w = 0 and k ≥ 1). See Figure 3 (right).

2.4. Explicit surjection. Consider a lattice congruence ≡ of the weak order and let I = I ≡ . According to Theorem 3, the congruence classes of ≡ are in bijection with noncrossing arc diagrams of I. Moreover, the map η I defined by η I (σ) := δ π ≡ ↓ (σ) sends a permutation σ ∈ S n to the noncrossing arc diagram of I corresponding to the congruence class of σ. For completeness, we now provide a direct explicit description of this surjection η I .

We still represent the permutation σ by its permutation table

{(σ i , i) | i ∈ [n]}. We define (σ) := {(i, j) | 1 ≤ i < j ≤ n, σ i > σ j and σ(]i, j[) ∩ ]σ j , σ i [ = ∅} .
Intuitively, (σ) are the pairs of positions such that the rectangle with bottom right corner (σ i , i) and top left corner (σ j , j) contains no other point (σ k , k) of the permutation table of σ. Order (σ) by (i, j) ≺ (k, ) if i ≤ k < ≤ j and σ k ≥ σ i > σ j ≥ σ . For (i, j) ∈ (σ), we define an arc α(i, j, σ) by α(i, j, σ

) := (σ j , σ i , n, {σ k | j < k and σ k ∈ ]σ j , σ i [ }).
Note that it extends our previous definition of α(i, i + 1, σ) in Section 2.1. Finally, define I (σ) to be the subset of ≺-maximal elements in {(i, j) ∈ (σ) | α(i, j, σ) ∈ I}.

Proposition 6. For any σ ∈ S n , the set η

I (σ) = δ π ≡ ↓ (σ) = α(i, j, σ) | (i, j) ∈ I (σ) is the noncrossing arc diagram of I corresponding to the ≡-congruence class of σ.
Proof. We first observe that if σ ∈ S n is minimal in its congruence class, then η I (σ) = δ(σ) is the arc diagram of the congruence class of σ. Indeed, observe first that the characterization of Theorem 3 (i) ensures that I (σ) contains (i, i + 1) for each descent i of σ. Conversely, consider (i, j) ∈ I (σ). Since (i, j) ∈ (σ), there exists i ≤ k < j such that σ k+1 ≤ σ j < σ i ≤ σ k . Therefore, (k, k + 1) ∈ I (σ) so that (i, j) = (k, k + 1) by ≺-maximality in the definition of I (σ). Assume now that σ ∈ S n is not minimal in its congruence class. By Theorem 3 (i), σ has a descent i such that α(i, i + 1, σ) / ∈ I. Let σ := σ • (i i + 1). Note that (σ) {(i, i + 1)} ⊆ (σ ). Conversely, consider (k, ) ∈ (σ ) (σ). Then either k = i and > j, or k < i and = j. In both cases, α(i, j, σ ) cannot belong to I since it forces α(i, i + 1, σ) which does not belong to I. We conclude that I (σ ) = I (σ) so that η I (σ ) = η I (σ). In other words, η I (σ) is preserved by the rewriting rule of Theorem 3 (iii). This concludes the proof since this rewriting rule terminates on a permutation which is minimal in its congruence class.

As in Section 2.1, η I (σ) is obtained by connecting the points (σ i , i) and (σ j , j) in the table of the permutation σ for all (i, j) ∈ I (σ), and by moving all numbers of this table to the horizontal axis, allowing the segment connecting i and j to curve but not to pass through any number. Note that to obtain all pairs (i, j) ∈ I (σ), one can either draw all pairs (i, j) ∈ (σ) for which α(i, j, σ) ∈ I and conserve the ≺-maximal ones, or one can perform a direct insertion algorithm similar to that of [START_REF] Chatel | Cambrian Hopf Algebras[END_REF][START_REF] Pilaud | Permutrees[END_REF]. Details are left to the reader. We define dually the sets (σ) and I (σ) and the maps α and η I . See Figure 4 for an illustration of the maps η I and η I .

Hopf algebra structures on noncrossing arc diagrams

In this section, we present general methods to construct Hopf algebra structures on decorated permutations and decorated arc diagrams. Recall that a combinatorial Hopf algebra is a combinatorial vector space A endowed with an associative product • : A ⊗ A → A and a coassociative coproduct : A → A ⊗ A so that the diagram

A ⊗ A A A ⊗ A A ⊗ A ⊗ A ⊗ A A ⊗ A ⊗ A ⊗ A • ⊗ I ⊗ swap ⊗ I • ⊗ •
commutes, where swap : A ⊗ A → A ⊗ A is defined by swap(x ⊗ y) = y ⊗ x and I is the identity.

3.1. Hopf algebra on permutations. Before constructing our decorated versions, we briefly recall 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 by S := n∈N S n the set of all permutations, of arbitrary size. The standardization of a word w ∈ N q with distinct entries is the permutation std(w) of [q] whose entries are in the same relative order as the entries of w. For a permutation ρ ∈ S p and a subset R = {r 1 < • • • < r q } ⊆ [p], we define stdp(ρ, R) (resp. stdv(ρ, R)) as the standardization of the word obtained by deleting form ρ the entries whose positions (resp. values) are not in R. For two permutations σ ∈ S m and τ ∈ S n , define the shifted shuffle σ ¡ τ and the convolution σ τ by

σ ¡ τ := {ρ ∈ S m+n | stdv(ρ, [m]) = σ and stdv(ρ, [m + n] [m]) = τ } and σ τ := {ρ ∈ S m+n | stdp(ρ, [m]) = σ and stdp(ρ, [m + n] [m]) = τ } .

Theorem 7 ([MR95]

). The vector space kS with basis (F σ ) σ∈S endowed with the product and coproduct defined by

F σ • F τ = ρ∈σ ¡ τ F ρ and F ρ = ρ∈σ τ F σ ⊗ F τ is a graded Hopf algebra.
Recall that the product in kS behaves nicely with the weak order on S n . For two permutations σ ∈ S m and τ ∈ S n , consider the permutations σ\τ and τ /σ of S m+n defined by

σ\τ (i) = µ(i) if i ∈ [m] m + τ (i -m) otherwise and τ /σ(i) = m + τ (i) if i ∈ [n] σ(i -n) otherwise.
The shifted shuffle σ ¡ τ is then precisely given the weak order interval between σ\τ and σ/τ in the weak order on S m+n . This extends to product of weak order intervals as follows.

Proposition 8. A product of weak order intervals in kS is a weak order interval: for any two weak order intervals [µ, ν] ⊆ S m and [λ, ω] ⊆ S n , we have µ≤σ≤ν

F σ • λ≤τ ≤ω F τ = µ\λ≤ρ≤ω/ν F ρ .
3.2. Decorated permutations. For our purposes, we need extensions of C. Malvenuto and C. Reutenauer's Hopf algebra on permutations. For example, we needed the signed or decorated permutations of [START_REF] Novelli | Free quasi-symmetric functions and descent algebras for wreath products, and noncommutative multi-symmetric functions[END_REF] to construct the Cambrian and permutree Hopf algebras [START_REF] Chatel | Cambrian Hopf Algebras[END_REF][START_REF] Pilaud | Permutrees[END_REF].

We now define Hopf algebras on permutations decorated with potentially more complicated structures.

Definition 9. A decoration set is a graded set X := n≥0 X n endowed with

• a concatenation concat : X m × X n -→ X m+n for all m, n ∈ N, • a selection select : X m × [m] k -→ X k for all m, k ∈ N, such that (i) concat(X , concat(Y, Z)) = concat(concat(X , Y), Z) for any elements X , Y, Z ∈ X, (ii) select(select(X , R), S) = select(X , {r s | s ∈ S})
for any element X ∈ X p , and any subsets R = {r 1 , . . . , r q } ⊆ [p] and S ⊆ [q], (iii) concat(select(X , R), select(Y, S)) = select(concat(X , Y), R ∪ S →m ) for any elements X ∈ X m and Y ∈ X n , and any subsets R ⊆ [m] and S ⊆ [n], where S →m := {s + m | s ∈ S}.

Example 10. A typical decoration set is the set of words A * on a finite alphabet A, graded by their length, with the classical concatenation of words, and the selection defined by subwords: concat(u 1 . . . u m , v 1 . . . v n ) = u 1 . . . u m v 1 . . . v n and select(w 1 . . . w p , {r 1 , . . . , r q }) = w r1 . . . w rq . Among many other examples, let us also mention the set of labeled graphs, graded by their number of vertices, with the concatenation defined as the shifted union, and the selection defined by standardized induced subgraphs. Further examples will appear in Section 4.

For n ≥ 0, we denote by P n the set of X-decorated permutations of size n, i.e. of pairs (σ, X ) with σ ∈ S n and X ∈ X n . We consider the graded set P := n≥0 P n and the graded vector space kP := n≥0 kP n , where kP n is a vector space with basis (F (σ,X ) ) (σ,X )∈Pn indexed by X-decorated permutations of size n. For two decorated permutations (σ, X ) and (τ, Y), we define the product F (σ,X ) • F (τ,Y) by

F (σ,X ) • F (τ,Y) := ρ∈σ ¡ τ F (ρ,concat(X ,Y)) .
Proposition 11. The product • defines an associative graded algebra structure on kP.

Proof. If (σ, X ) ∈ P m and (τ, Y) ∈ P n , we have (ρ, concat(X , Y)) ∈ P m+n for any ρ ∈ σ ¡ τ , so that • is a graded product. It is associative since both the concatenation (by Definition 9 (i)) and the shifted shuffle product (by Theorem 7) are associative.

Note that an analogue of Proposition 8 clearly holds for decorated permutations.

We define the standardization of a decorated permutation (ρ, Z) ∈ P p at a subset R ⊆ [p] as std((ρ, Z), R) := stdp(ρ, R), select(Z, ρ -1 (R)) , where stdp(ρ, R) is the position standardization on permutations and select(Z, ρ -1 (R)) is the selection on X. For a decorated permutation (ρ, Z) ∈ P p , we define the coproduct F (ρ,Z) by

F (ρ,Z) := p k=0 F std((ρ,Z),[k]) ⊗ F std((ρ,Z),[p] [k]) .
Proposition 12. The coproduct defines a coassociative graded coalgebra structure on kP.

Proof. If (σ, Z) ∈ P p and R ⊆ [p], we have std((ρ, Z), R) ∈ P |R| so that is a graded coproduct. Moreover, using Definition 9 (ii), we obtain that for a decorated permutation (ρ, Z) ∈ P p , both (Id ⊗ )( F (ρ,Z) ) and ( ⊗ Id)( F (ρ,Z) ) equal to

0≤k≤ ≤p F std((ρ,Z),[k]) ⊗ F std((ρ,Z),[ ] [k]) ⊗ F std((ρ,Z),[p] [ ]) .
Theorem 13. The product • and coproduct endow the family of decorated permutations with a graded Hopf algebra structure.

Proof. This follows from the same property for the product and coproduct on permutations and by Definition 9 (iii). Indeed

F (σ,X ) • F (τ,Y) = m+n k=0 ρ∈σ ¡ τ F std((ρ,concat(X ,Y)),[k]) ⊗ F std((ρ,concat(X ,Y)),[m+n] [k]) = m p=0 n q=0 µ F (µ,concat(std(X ,σ -1 ([p])),std(Y,τ -1 ([q])))) ⊗ ν F (ν,concat(std(X ,σ -1 ([m] [p])),std(Y,τ -1 ([n] [q])))) = m p=0 F std((σ,X ),[p]) ⊗ F std((σ,X ),[m] [p]) • n q=0 F std((τ,X ),[q]) ⊗ F std((τ,X ),[n] [q]) = F (σ,X ) • F (τ,Y)
where µ ranges over stdp(σ, [p]) ¡ stdp(τ, [q]) while ν ranges over stdp(σ, [m] [p]) ¡ stdp(τ, [n] [q]) in the second line, and the swap is understood in the last two lines.

Example 14. When X is the set of words A * on a finite alphabet A (with the classical concatenation of words and the selection defined by subwords, as in Example 10), the Hopf algebra of decorated permutations was studied in detail by J.-C. Novelli and J.-Y. Thibon in [START_REF] Novelli | Free quasi-symmetric functions and descent algebras for wreath products, and noncommutative multi-symmetric functions[END_REF]. Further relevant examples will appear in Section 4.

3.3. Decorated noncrossing arc diagrams. We now use our Hopf algebra on decorated permutations to construct Hopf algebras on decorated noncrossing arc diagrams. As in the previous section, we consider a decoration set (X, concat, select) and the corresponding Hopf algebra (kP, • , ) on X-decorated permutations. Recall from Section 2.3 that I n denotes the set of arc ideals of A n .

For an arc α = (a, b, m, S) and n ∈ N, we define the augmented arc α +n := (a, b, m + n, S) and the shifted arc α →n := (a+n, b+n, m+n, {s + n | s ∈ S}). Graphically, α +n is obtained from α by adding n points to its right, and α →n is obtained from α by adding n points to its left. For I ⊆ A m and n ∈ N, define I +n := {α +n | α ∈ I} and

I →n := {α →n | α ∈ I}. Definition 15. A graded function Ψ : X = n≥0 X n -→ I = n≥0 I n is conservative if (i) Ψ(X ) +n and Ψ(Y) →m are both subsets of Ψ(concat(X , Y)) for any X ∈ X m and Y ∈ X n , (ii) (r a , r b , p, S) ∈ Ψ(Z) implies (a, b, q, {c ∈ [q] | r c ∈ S}) ∈ Ψ(select(Z, R)) for any Z ∈ X p , any R = {r 1 < • • • < r q } ⊆ [p], any 1 ≤ a < b ≤ q and any S ⊆ ]r a , r b [. Example 16. If X = {•} *
is the decoration set of words on a one element alphabet, then the maps

• n → A n = {(a, b, n, S) | 1 ≤ a < b ≤ n and S ⊆ ]a, b[} and • n → {(a, b, n, ∅) | 1 ≤ a < b ≤ n} are both conservative.
Further relevant examples will appear in Section 4.

From now on, we assume that we are given a conservative function Ψ : X -→ I. For n ≥ 0, we denote by D n the set of X-decorated noncrossing arc diagrams of size n, i.e. of pairs (D, X ) where X ∈ X n and D is a noncrossing arc diagram contained in Ψ(X ).

We now define a Hopf algebra on X-decorated noncrossing arc diagrams using the map η defined in Section 2.4. We denote by kD := n≥0 kD n the graded vector subspace of kP generated by the elements

P (D,X ) := σ∈S η Ψ(X ) (σ)=D F (σ,X ) ,
for all X-decorated noncrossing arc diagrams (D, X ). Our central result is the following statement.

Theorem 17. The subspace kD is a Hopf subalgebra of kP.

Proof. We first prove that kD is a subalgebra of kP, i.e. that it is stable by product. Consider two X-decorated noncrossing arc diagrams (D, X ) ∈ D m and (E, Y) ∈ D n . By definition, all permutations that appear in the product P (D,X ) • P (E,Y) are decorated by the product Z := concat(X , Y). Observe first that the product P (D,X ) • P (E,Y) is multiplicity-free in the basis (F (ρ,Z) ) (ρ,Z)∈P of kP, since any F (ρ,Z) in P (D,X ) • P (E,Y) must come from the product

F (stdv(ρ,[m]),X ) • F (stdv(ρ,[m+n] [m]),Y) .
Consider now two decorated permutations (ρ, Z) and (ρ , Z) such that η Ψ(Z) (ρ) = η Ψ(Z) (ρ ). We want to show that F (ρ,Z) appears in P (D,X )

• P (E,Y) if and only if F (ρ ,Z) appears in P (D,X ) • P (E,Y) . Assume first that ρ = ρ • (k k + 1) for a descent k of ρ such that α(k, k + 1, ρ) / ∈ Ψ(Z) and that F (ρ,Z) appears in the product P (D,X ) • P (E,Y) . Let σ ∈ η -1 Ψ(X ) (D) and τ ∈ η -1 Ψ(Y) (E)
be such that ρ ∈ σ ¡ τ . We then distinguish three cases:

• If ρ k+1 ≤ m < ρ k , then ρ also belongs to σ ¡ τ so that F (ρ ,Z) also appears in

P (D,X ) • P (E,Y) . • If ρ k ≤ m, then Definition 15 (i) ensures that α(i, i + 1, σ) / ∈ X , where i is the descent of σ such that σ i = ρ k . The permutation σ := σ•(i i+1) thus satisfies η Ψ(X ) (σ ) = η Ψ(X ) (σ) = D. Since ρ ∈ σ ¡ τ , it follows that F (ρ ,Z) also appears in P (D,X ) • P (E,Y) .
• Finally, if m < ρ k+1 , the argument is similar using τ := τ • (j j + 1) where τ j = ρ k . By transitivity in Theorem 3 (iii), we obtain that F (ρ,Z) appears in P (D,X ) • P (E,Y) if and only if F (ρ ,Z) appears in P (D,X ) • P (E,Y) . Therefore kD is a subalgebra of kP.

We now prove that kD is a subcoalgebra of kP, i.e. that it is stable by coproduct. Consider a decorated noncrossing arc diagram (D, Z) ∈ D p . Observe first that the coproduct P (D,Z) is multiplicity-free in the basis (F (ρ,Z) ) (ρ,Z)∈P of kP, since any F (σ,X ) ⊗ F (τ,Y) in P (D,Z) must come from the coproduct F (ρ,Z) where ρ

(i) = σ(i) if i ∈ [m] and ρ(i) = m + σ(i -m) if i ∈ [m + n] [m]. Consider now four decorated permutations (σ, X ), (σ , X ), (τ, Y) and (τ , Y) such that η Ψ(X ) (σ) = η Ψ(X ) (σ ) and η Ψ(Y) (τ ) = η Ψ(Y) (τ ).
We want to show that F (σ,X ) ⊗ F (τ,Y) appears in the coproduct P (D,Z) if and only if F (σ ,X ) ⊗ F (τ ,Y) appears in the coproduct P (D,Z) . Assume first that σ = σ • (i i + 1) for a descent i of σ with α(i, i + 1, σ) / ∈ X , that τ = τ and that F (σ,X ) ⊗ F (τ,Y) appears in the coproduct P (D,Z) . By definition of the coproduct, there exist ρ ∈ η -1

Ψ(Z) (D) and k ∈ [p] such that (σ, X ) = std((ρ, Z), [k]) and (τ, Y) = std((ρ, Z), [p] [k]). Since X = select(Z, ρ -1 ([k])) and α(i, i+1, σ) / ∈ X , Definition 15 (ii) ensures that α(i, i+1, ρ) / ∈ Z. We conclude that ρ = ρ • (i i + 1) is in η -1 Ψ(Z) (D). Since moreover (σ , X ) = std((ρ , Z), [k]) and (τ, Y) = std((ρ , Z), [p] [k]), we get that F (σ ,X ) ⊗ F (τ,Y) appears in the coproduct P (D,Z) .
By symmetry and by transitivity in Theorem 3 (ii), we conclude that F (σ,X ) ⊗ F (τ,Y) appears in the coproduct P (D,Z) if and only if

F (σ ,X ) ⊗ F (τ ,Y) appears in the coproduct P (D,Z) for any (σ, X ), (σ , X ), (τ, Y) and (τ , Y) such that η Ψ(X ) (σ) = η Ψ(X ) (σ ) and η Ψ(Y) (τ ) = η Ψ(Y) (τ ).
Therefore kD is a subcoalgebra of kP.

We now provide an analogue of Proposition 8 for decorated noncrossing arc diagrams.

Proposition 18. Consider two X-decorated noncrossing arc diagrams (D, X ) and (E, Y), and their corresponding weak order intervals [µ, ν]

:= η -1 Ψ(X ) (D) and [λ, ω] := η -1 Ψ(Y) (E). Then P (D,X ) • P (E,Y) = F P (F ,concat(X ,Y)) ,
where F ranges in the interval between D\E := η Ψ(concat(X ,Y)) (µ\λ) and E/D := η Ψ(concat(X ,Y)) (ω/ν) in the lattice of noncrossing arc diagrams in Ψ(concat(X , Y)).

Proof. This follows from Proposition 8 and the fact that the η Ψ(concat(X ,Y)) fibers of the noncrossing arc diagrams in the Ψ(concat(X , Y))-interval between D\E and E/D form a partition of the weak order interval between µ\λ and ω/ν:

P (D,X ) • P (E,Y) = µ≤σ≤ν F (σ,X ) • λ≤τ ≤ω F (τ,Y) = µ\λ≤ρ≤ω/ν F (ρ,concat(X ,Y)) = F P (F ,concat(X ,Y))
3.4. Decoration products and decoration subsets. To close our generic Hopf algebra constructions, we observe two natural operations on decoration sets that behave properly with our construction. The straightforward proofs are left to the reader. First, we observe that we can obtain Hopf algebra structures on arc diagrams decorated by Cartesian products of decorations.

Proposition 19. The Cartesian product X × X of two decoration sets X and X , endowed with the concatenation and selection defined by

concat((X , X ), (Y, Y )) := (concat(X , Y), concat(X , Y )) and select((Z, Z ), R) := (select(Z, R), select(Z , R)),
is a decoration set. Moreover, for two conservative functions Ψ : X → I and Ψ :

X → I, the function Ψ ∩ Ψ : X × X → I defined by (Ψ ∩ Ψ )(X , X ) := Ψ(X ) ∩ Ψ (X ) is conservative.
On the other hand, we observe that decoration subsets define Hopf subalgebras.

Proposition 20. If X ⊆ X are two decoration sets, and Ψ : X → I is a conservative function, then the restriction Ψ of Ψ to X is conservative. Therefore, the Hopf algebra kD constructed from Ψ is a Hopf subalgebra of the Hopf algebra kD constructed from Ψ .

Applications

In this section, we provide examples of applications of Theorems 13 and 17.

I m+n for all m, n ∈ N, • (r a , r b , p, S) ∈ I p implies (a, b, q, {c ∈ [q] | r c ∈ S}) ∈ I q for any R = {r 1 < • • • < r q } ⊆ [p],
any 1 ≤ a < b ≤ q and any S ⊆ ]r a , r b [, then the subvector space of kS generated by the sums σ F σ over the classes of the congruences ≡ n is a Hopf subalgebra of C. Malvenuto and C. Reutenauer's Hopf algebra kS. Choose k ∈ N and define the function Ψ : X n → A n by Ψ(n, s, e, w) = A <k n,s,e,w . Recall from Example 5 that for each a ∈ [n], we place n(a) upper vertical walls above a, s(a) lower vertical walls below a and min(e(a), w(a + 1)) horizontal walls between a and a + 1, and that an arc belongs to A <k n,s,e,w if it crosses at most k -1 of these walls. The function Ψ is conservative since • for any u ∈ X m , v ∈ X n , α ∈ Ψ(u) and β ∈ Ψ(v), the walls of uv crossed by α +n are precisely the walls of u crossed by α, while the walls of uv crossed by β →m are precisely the m-translates of the walls of v crossed by β, • for any w ∈ X p , R = {r 1 , . . . , r q } ⊆ [p], 1 ≤ a < b ≤ q and S ⊆ ]r a , r b [, the walls crossed by the arc (a, b, q, {c | r c ∈ S}) are walls crossed by the arc (r a , r b , p, S) (but the latter might cross more walls than the former). We therefore obtain a Hopf algebra kD <k on the classes of all lattice congruences A <k n,s,e,w simultaneously. Moreover, as observed in Proposition 20 any subset of X stable by concatenation and selection provides a Hopf subalgebra kD <k . In particular, kD <1 contains simultaneously Hopf subalgebras on permutations [START_REF] Malvenuto | Duality between quasi-symmetric functions and the Solomon descent algebra[END_REF], 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], binary sequences [GKL + 95], Cambrian trees [START_REF] Chatel | Cambrian Hopf Algebras[END_REF], permutrees [START_REF] Pilaud | Permutrees[END_REF], and diagonal rectangulations [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], while kD <k contains subalgebras on k-twists [START_REF] Pilaud | Brick polytopes, lattice quotients, and Hopf algebras[END_REF] and on k-descent schemes [START_REF] Novelli | Generalized descent patterns in permutations and associated Hopf algebras[END_REF][START_REF] Pilaud | Brick polytopes, lattice quotients, and Hopf algebras[END_REF]. Finally, one could also mix conditions on the crossing numbers with walls of different colors using Proposition 19. 4.3. All arc diagrams. To conclude, we define a Hopf algebra kD simultaneously involving the classes of all lattice congruences of the weak order, and containing the permutree algebra. 4.3.1. Extended arcs. We call extended arc any quadruple (a, b, n, S) where a, b, n ∈ N are such that 0 ≤ a < b ≤ n + 1, and S ⊆ ]a, b[. In other words, extended arcs are precisely like arcs but they are allowed to be attached before 1 and after n. We represent extended arcs exactly in the same way as arcs (but the points 0 and n + 1 are colored white). We denote by A n := {(a, b, n, S) | 0 ≤ a < b ≤ n + 1 and S ⊆ ]a, b[} the set of all extended arcs. An extended arc (a, b, n, S) is initial if a = 0, terminal if b = n + 1, and strict otherwise. The notions of crossing and forcing, as well as the operations α +n and α →n , are defined as for classical arcs. We denote by I n the set of extended arc ideals (i.e. upper ideals of the forcing order ≺ on A n ).

We call juxtaposition αβ of two extended arcs α := (a, b, n, R) and β := (c, d, n, S) the arc

αβ := {(a, d, n, R ∪ S)} if b = c + 1, ∅ otherwise.
In other words, αβ is obtained by joining α to β when the final endpoint of α appears just after the initial endpoint of β, and is empty otherwise. Note that the juxtaposition is associative: for α We define the concatenation of two extended arc ideals I ⊆ A m and J ⊆ A n by concat(I, J ) := I +n J →m .

Graphically, concat(I, J ) is obtained by juxtaposing I and J such that the n -(n + 1) edge of I coincides with the 0 -1 edge of J , and joining all final arcs of I with all initial arcs of J . See Figure 5 for an illustration. Proof. The set concat(I, J ) is contained in A m+n by definition and closed by forcing since both I +n and J →m are.

Lemma 24. For any arc ideals I, J , K, we have concat(concat(I, J ), K) = concat(I, concat(J , K)).

Proof. Assume that I ⊆ A m , J ⊆ A n and K ⊆ A p . Using the associativity of the juxtaposition,

concat(concat(I, J ), K) = (I +n J →m ) +p K →(m+n) = I +(n+p) (J →m ) +p K →(m+n) = I +(n+p) (J +p K →n ) →m = concat(I, concat(J , K)).
Consider now an extended arc ideal K ⊆ A p and a subset

X := {x 1 < • • • < x q } of [p]
. Define by convention x 0 := 0 and x q+1 := p + 1. We define the selection of K at X by select(K, X) := (a, b, q, S) ∃ y 0 < • • • < y r ∈ [p] with x a = y 0 and x b = y r while y 1 , . . . , y r-1 / ∈ X ∃ (y 0 , y 1 , p, S 1 ), . . . , (y r-1 , y r , p, S r ) ∈ K with S = { ∈ [q] | x ∈ S k } .

Graphically, select(K, X) is obtained by considering all arcs obtained by merging x-monotone paths in K with endpoints in {0} ∪ X ∪ {p + 1} but all interior points in [p] X, deleting all points of [p] X, and packing the remaining points of {0} ∪ X ∪ {p + 1} (together with the merged arcs) to the left towards their standard position 0, 1, . . . , q, q + 1. See Figure 6 for an illustration. Lemma 25. The selection select(K, X) of an extended arc ideal K ⊆ A p on a q-element subset X of [p] is an extended arc ideal of A q .

Proof. Let I := select(K, X). We have I ⊆ A q by definition. To show that I is closed by forcing, assume that an arc (a, d, q, S) ∈ I is forced by an arc (b, c, q, T ), so that a ≤ b < c ≤ d and T = S ∩ ]b, c[. Consider a path of arcs α 1 := (y 0 , y 1 , p, S 1 ), . . . , α r := (y r-1 , y r , p, S r ) of K corresponding to I. Let u := min {s ∈

[r] | x b < y s } and v := max {s ∈ [r] | y s-1 < x c }. If u = v, then (x b , x c , p, S u ∩ ]x b ,
x c [) belongs to K (since it is closed by forcing), thus (b, c, q, T ) belongs to I. If u < v, then both α u := (x b , y u , p, S u ∩ ]x b , y u [) and α v := (y v-1 , x c , S v ∩ ]y v-1 , x c [) belong to K (since it is closed by forcing). The path of arcs α u , α u+1 , . . . , α v-1 , α v thus ensures that (b, c, q, T ) belongs to I as well.

Lemma 26. For any extended arc ideal K ⊆ A p , any subset X := {x 1 , . . . , x q } of [p] and any subset Y of [q], we have select(select(K, X), Y ) = select(K, {x y | y ∈ Y }). We have therefore proved the following statement.

Corollary 28. The set I := n∈N I n of all extended arcs ideals, endowed with the concatenation concat and selection select, is a decoration set. 4.3.2. Noncrossing extended arc diagrams. We now consider the map Ψ : I → I which sends an extended arc ideal to the arc ideal of its strict arcs. This function is clearly conservative so that we obtain a Hopf algebra kD on pairs (D, I), where I is any extended arc ideal and D is a noncrossing arc diagram containing only strict arcs of I. Note that kD is graded but not connected as there are two extended arc ideals in A 0 : the pair ∅, {(0, 1, 0, ∅)} is the identity of kD , while the pair (∅, ∅) is a primitive idempotent of kD . We could have forced connectivity by imposing all short arcs (i, i + 1, n, ∅) for 0 ≤ i ≤ n in all extended arc ideals of J n . The Hopf algebra kD involves the classes of all lattice congruences of the weak order. Moreover, the concatenation and selection on extended arc diagrams was chosen to fulfill the following statement.

Proposition 29. The permutree Hopf algebra is a Hopf subalgebra of kD .

Proof. Any function n, s : [n] → {0, 1} naturally correspond to the extended arc ideal of extended arcs (a, b, n, S) such that n(c) = 0 for c ∈ S and s(c) = 0 for c ∈ ]a, b[ S. On these particular extended arc ideals, the concatenation and selection corresponds to that defined in Section 4.2. The result immediately follows by Proposition 20.

In contrast, the reader can check that none of the Hopf algebras of [LR12, Gir12, Pil18] is a Hopf subalgebra of kD .

Figure 1 .

 1 Figure 1. The weak order (left) and the Tamari lattice (right).

  [n] := {1, . . . , n} and let [a, b] := {a, . . . , b} and ]a, b[ := {a + 1, . . . , b -1} for a < b. Consider the set S n of permutations of [n]

Figure 2 .

 2 Figure 2. The noncrossing arc diagrams δ(σ) (bottom) and δ(σ) (top) for the permutations σ = 2537146, 2531746, 2513746, and 2513476.

  for examples of noncrossing arc diagrams. Theorem 2 ([Rea15, Thm. 3.1]). The maps δ and δ are bijections from permutations of S n to noncrossing arc diagrams of A n . The reverse bijections δ -1 and δ -1 are explicitly described in [Rea15, Prop. 3.2]. Briefly speaking, consider the poset of connected components of D ordered by (the transitive closure of) the priority X ≺ Y if there is an arc α = (a, b, n, S) ∈ D with S ∩ X = ∅ and a, b ∈ Y or with a, b ∈ X and (]a, b[ S) ∩ Y = ∅. To obtain δ -1 (D) (resp. δ -1 (D)), choose the linear extension of this priority poset where ties are resolved by choosing first the leftmost (resp. rightmost) connected component, and order decreasingly (resp. increasingly) the values in each connected component. See Figure 2.

Figure 3 .

 3 Figure 3. The forcing order on arcs of A 4 (left) and some examples of arc ideals A <k n,s,e,w (right) whose associated lattice congruence classes correspond to permutations, binary trees, binary sequences, diagonal rectangulations, permutrees, sashes, acyclic 2-twists, and 3-descent schemes. Walls are in red and k = 1 if not stated otherwise.

Figure 4 .

 4 Figure 4. The noncrossing arc diagrams η I (σ) (bottom) and η I (σ) (top) for the permutation σ = 2537146 and different arc ideals (represented in light gray).

  = {12453, 14253, 14523, 14532, 41253, 41523, 41532, 45123, 45132, 45312}, and 12 231 = {12453, 13452, 14352, 15342, 23451, 24351, 25341, 34251, 35241, 45231}.

4. 1 .

 1 Insertional, translational, and Hopf families of congruences. For all n ∈ N, fix a lattice congruence ≡ n of the weak order on S n , with arc ideal I n . As a first application of Theorem 17, we obtain sufficient conditions for the family (≡ n ) n∈N to define a Hopf subalgebra of kS. Corollary 21 ([Rea05, Thm. 1.2 & 1.3]). For all n ∈ N, consider a lattice congruence ≡ n of the weak order on S n , with arc ideal I n . If • both I +n m and I →m n are contained in

Proof.

  Consider the decoration set {•} * of words over a one element alphabet and the function Ψ : {•} * → I given by Ψ(• n ) = I ≡n . Note that the Hopf algebra kP of permutations decorated with {•} * is just isomorphic to C. Malvenuto and C. Reutenauer's Hopf algebra kS on permutations. Moreover, the conditions of the statement assert that Ψ is conservative. The result thus immediately follows from Theorem 17. The conditions of Corollary 21 are essentially the translational and insertional conditions given by N. Reading in [Rea05, Thm. 1.2 & 1.3]. Note however that our condition is slightly weaker as we only require that the restriction of ≡ m+n to {σ\τ | σ ∈ S m and τ ∈ S n } refines the congruence relation induced by ≡ m × ≡ n on {σ\τ | σ ∈ S m and τ ∈ S n } while N. Reading's definition of translational families requires that these congruences coincide. Example 22. Corollary 21 covers various families of lattice congruences, producing Hopf algebra structures on permutations [MR95], on binary trees [LR98, HNT05], on binary sequences [GKL + 95], on diagonal quadragulations [LR12] or equivalently on twin binary trees [Gir12], on k-twists [Pil18], on k-descent schemes [NRT11, Pil18], etc. 4.2. Bounded crossings. We now consider the family of arc ideals A <k n,s,e,w defined in Example 5. Consider the decoration set X = n∈N X n , where X n is the set of quadruples of functions [n] → N, and where the concatenation is defined by concat((n, s, e, w), (n , s , e , w ))(a) = (n(a), s(a), e(a), w(a)) if a ≤ m (n (a), s (a), e (a), w (a)) if a > m (in other words, the usual concatenation of words in (N 4 ) * ), and the selection is defined by select((n, s, e, w), R)(a) = (n(r a ), s(r a ), min {e(s) | s ∈ ]r a-1 , r a ]} , min {w(s) | s ∈ [r a , r a+1 [}).

  := (a, b, n, R), β := (c, d, n, S), and γ := (e, f, n, T ) we have (αβ)γ = α(βγ) = {(a, f, n, R∪S ∪T )} if c = b + 1 and e = d + 1, and (αβ)γ = α(βγ) = ∅ otherwise. For I, J ⊆ A n , we define the juxtaposition IJ by IJ := I ∪ J ∪ α∈I β∈J αβ Observe that if I and J are both extended arc ideals, then IJ is also an extended arc ideal. Note again that the juxtaposition is associative: (IJ )K = I(J K) = I ∪ J ∪ α∈I β∈J γ∈K αβ ∪ βγ ∪ αβγ .

Figure 5 .

 5 Figure 5. The concatenation of two extended arc ideals.

Figure 6 .

 6 Figure6. The selection in an arc ideal. Selected points are in red. The blue extended arc (0, 4, 3, {1, 3}) in select(K, {1, 3, 6}) arises from the concatenation of the three blue extended arcs (0, 2, 6, {1}), (2, 5, 6, {4}) and (5, 7, 6, {6}) in K.

Proof.γ →m 0 , γ →m 1 ,

 01 By definition, both select(select(K, X), Y ) and select(K, {x y | y ∈ Y }) are obtained by merging all paths in K whose endpoints are in {0} ∪ {x y | y ∈ Y } ∪ {p + 1} but whose interior vertices are all in [p] {x y | y ∈ Y }, and packing the remaining points of {0} ∪ {x y | y ∈ Y } ∪ {p + 1} to their standard position 0, 1, . . . , |Y |, |Y | + 1. Proposition 27. For any arc ideals I ⊆ A m and J ⊆ A n and any subsets X ⊆ [m] and Y ⊆ [n],concat(select(I, X), select(J , Y )) = select(concat(I, J ), X ∪ Y →m )whereY →m := {y + m | y ∈ Y }.Proof. Consider an arc α := (a, b, m + n, S) ∈ A m+n . We distinguish three cases:• If b ≤ m, then α ∈ concat(select(I, X), select(J , Y )) and α ∈ select(concat(I, J ), X ∪ Y →m ) are both equivalent to (a, b, m, S) ∈ select(I, X). • If m < a, then α ∈ concat(select(I, X), select(J , Y )) and α ∈ select(concat(I, J ), X ∪ Y →m ) are both equivalent to (a -m, b -m, n, {s -m | s ∈ S}) ∈ select(J , Y ). • Finally, assume that a ≤ m < b. If α ∈ concat(select(I, X), select(J , Y )), then there exists a final arc β ∈ select(I, X) and an initial arc γ ∈ select(J , Y ) such that {α} = β +n γ →m . The arc β ∈ select(I, X) corresponds to a path of arcs β 0 , . . . , β r in I whose interior points all belong to [m] X, and similarly the arc γ ∈ select(J , Y ) corresponds to a path of arcs γ 0 , . . . , γ s in J whose interior points all belong to [n] Y . The path β +n 0 , . . . , β +n r-1 , β +n r . . . , γ →m s thus shows that α ∈ select(concat(I, J ), X ∪ Y →m ). Conversely, if α ∈ select(concat(I, J ), X∪Y →m ), it corresponds to a path of arcs α 1 , . . . , α r in concat(I, J ) whose interior points all belong to X ∪ Y →m . Since a ≤ m < b, there is s ∈ [r] such that α s = (c, d, m + n, T ) with c ≤ m < d. Let β 1 , . . . , β s in I and γ s , . . . , γ r in J be such that α s = β +n s γ →m s andα i = β +n i if i < s while α i = γ →m i if i > s.Then the paths β 1 , . . . , β s in I and γ s , . . . , γ r in J ensure the existence of β ∈ select(I, X) and γ ∈ select(J , Y ) such that α = β +n γ →m ∈ concat(select(I, X), select(J , Y )).

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

Acknowledgements

I thank two anonymous referees for helpful comments that improved the presentation, fixed imprecise statements, and suggested relevant bibliographic connections.

Partially supported by the French ANR grants SC3A (15 CE40 0004 01) and CAPPS (17 CE40 0018