Samuele Giraudo
email: samuele.giraudo@univ-mlv.fr

ALGEBRAIC AND COMBINATORIAL STRUCTURES ON PAIRS OF TWIN BINARY TREES

Keywords: Hopf algebra, Robinson-Schensted algorithm, Quotient monoid, Lattice, Baxter permutation

We give a new construction of a Hopf algebra defined first by Reading [Rea05] whose bases are indexed by objects belonging to the Baxter combinatorial family (i.e., Baxter permutations, pairs of twin binary trees, etc.). Our construction relies on the definition of the Baxter monoid, analog of the plactic monoid and the sylvester monoid, and on a Robinson-Schensted-like correspondence and insertion algorithm. Indeed, the Baxter monoid leads to the definition of a lattice structure over pairs of twin binary trees and the definition of a Hopf algebra. The algebraic properties of this Hopf algebra are studied and among other, multiplicative bases are provided, and freeness and self-duality proved.

1. Introduction 2. Preliminaries 2.1. Words, definitions and notations 2.2. Permutations, definitions and notations 2.3. Binary trees, definitions and notations 2.4. Baxter permutations and pairs of twin binary trees 3. The Baxter monoid 3.1. Definition and first properties 3.2. Connection with the sylvester monoid 3.3. Connection with the 3-recoil monoid 4. A Robinson-Schensted-like algorithm 4.1. Principle of the algorithm 4.2. Correctness of the insertion algorithm 4.3. Distinguished permutations from a pair of twin binary trees 4.4. Definition and correctness of the iterative insertion algorithm 5. The Baxter lattice 5.1. The Baxter lattice congruence 5.2. A lattice structure over the set of pairs of twin binary trees 5.3. Covering relations of the Baxter lattice 5.4. Twin Tamari diagrams 6. The Hopf algebra of pairs of twin binary trees 6.1. The Hopf algebra FQSym and construction of Hopf subalgebras 6.2. Construction of the Hopf algebra Baxter 6.3. Properties of the Hopf algebra Baxter 6.4. Connections with other Hopf subalgebras of FQSym References

Introduction

In recent years, many combinatorial Hopf algebras, whose bases are indexed by combinatorial objects, have been intensively studied. For example, the Malvenuto-Reutenauer Hopf algebra FQSym of Free quasi-symmetric functions [START_REF] Malvenuto | Duality between quasi-symmetric functions and Solomon descent algebra[END_REF][START_REF] Duchamp | Noncommutative Symmetric Functions VI: Free Quasi-Symmetric Functions and Related Algebras[END_REF] has bases indexed by permutations. This Hopf algebra admits several Hopf subalgebras: The Hopf algebra of Free symmetric functions FSym [START_REF] Poirier | Algèbres de Hopf de tableaux[END_REF][START_REF] Duchamp | Noncommutative Symmetric Functions VI: Free Quasi-Symmetric Functions and Related Algebras[END_REF], whose bases are indexed by standard Young tableaux, the Hopf algebra Bell [START_REF] Rey | Algebraic constructions on set partitions[END_REF] whose bases are indexed by set partitions, the Loday-Ronco Hopf algebra PBT [START_REF] Loday | Hopf Algebra of the Planar Binary Trees[END_REF][START_REF] Hivert | The Algebra of Binary Search Trees[END_REF] whose bases are indexed by planar binary trees, and the Hopf algebra Sym of non-commutative symmetric functions [GKL + 94] whose bases are indexed by integer compositions. A unifying approach to construct all these structures relies on a definition of a congruence on words leading to the definition of monoids on combinatorial objects. Indeed, FSym is directly obtained from the plactic monoid [LS81, [START_REF] Duchamp | Noncommutative Symmetric Functions VI: Free Quasi-Symmetric Functions and Related Algebras[END_REF][START_REF] Lothaire | Algebraic combinatorics on words[END_REF], Bell from the Bell monoid [START_REF] Rey | Algebraic constructions on set partitions[END_REF], PBT from the sylvester monoid [START_REF] Hivert | An analogue of the plactic monoid for binary search trees[END_REF][START_REF] Hivert | The Algebra of Binary Search Trees[END_REF], and Sym from the hypoplactic monoid [START_REF] Krob | Noncommutative symmetric functions IV: Quantum linear groups and Hecke algebras at q = 0[END_REF][START_REF] Novelli | On the hypoplactic monoid[END_REF]. The richness of these constructions relies on the fact that, in addition to constructing Hopf algebras, the definition of such monoids often brings partial orders, combinatorial algorithms and Robinson-Schensted-like algorithms, of independent interest.

The Baxter combinatorial family admits various representations. The most famous of these are Baxter permutations [START_REF] Baxter | On fixed points of the composite of commuting functions[END_REF], which are permutations that avoid certain patterns, and pairs of twin binary trees [START_REF] Dulucq | Mots de piles, tableaux standards et permutations de Baxter[END_REF]. This family also contains more exotic objects like quadrangulations [START_REF] Ackerman | On the Number of Rectangular Partitions[END_REF] and plane bipolar orientations [START_REF] Bonichon | Baxter permutations and plane bipolar orientations[END_REF]. In this paper, we propose to enrich the above collection of Hopf algebras by providing a plactic-like monoid, namely the Baxter monoid, leading to the construction of a Hopf algebra whose bases are indexed by objects belonging to this combinatorial family.

In order to show examples of relations between lattice congruences [START_REF] Chajda | Congruences in Ordered Sets[END_REF] and Hopf algebras, Reading presented in [START_REF] Reading | Lattice congruences, fans and Hopf algebras[END_REF] a lattice congruence of the permutohedron whose equivalence classes are indexed by twisted Baxter permutations. These permutations were defined by a pattern avoidance property. This congruence is very natural: The meet of two lattice congruences of the permutohedron related to the construction of PBT is one starting point to build Sym; A natural question is to understand what happens when the join, instead of the meet, of these two lattice congruences is considered. Reading proved that his lattice congruence is precisely this last one, and that the minimal elements of its equivalence classes are twisted Baxter permutations. Besides, thanks to his theory, he gets for free a Hopf algebra whose bases are indexed by twisted Baxter permutations. Actually, twisted Baxter permutations are equinumerous with Baxter permutations. Indeed, Law and Reading pointed out in [START_REF] Law | The Hopf algebra of diagonal rectangulations[END_REF] that the first proof occurred in unpublished notes of West. Hence, the Hopf algebra of Reading defined in [START_REF] Reading | Lattice congruences, fans and Hopf algebras[END_REF] can already be seen as a Hopf algebra on Baxter permutations, and our construction, considered as a different construction of the same Hopf algebra. Moreover, very recently, Law and Reading [START_REF] Law | The Hopf algebra of diagonal rectangulations[END_REF] detailed their construction of this Hopf algebra and studied some of its algebraic properties.

We started independently the study of Baxter objects in a different way: We looked for a quotient of the free monoid analogous to the plactic and the sylvester monoid. Surprisingly, the equivalence classes of permutations under our monoid congruence are the same as the equivalence classes of the lattice congruence of Law and Reading, and hence have the same by-products, as e.g., the Hopf algebra structure and the fact that each class contains both one twisted and one non-twisted Baxter permutation. However, even if both points of view lead to the same general theory, their paths are different and provide different ways of understanding the construction, one centered on lattice theory, the other centered on combinatorics on words. Moreover, a large part of the results of each paper do not appear in the other as, in our case, the Robinson-Schensted-like correspondence and its insertion algorithm, the polynomial realization, the bidendriform bialgebra structure, the freeness, cofreeness, self-duality, primitive elements, and multiplicative bases of the Hopf algebra, and a few other combinatorial properties.

We begin by recalling in Section 2 the preliminary notions about words, permutations, and pairs of twin binary trees used thereafter. In Section 3, we define the Baxter congruence. This congruence allows to define a quotient of the free monoid, the Baxter monoid, which has a number of properties required for the Hopf algebraic construction which follows. We show that the Baxter monoid is intimately linked to the sylvester monoid and that the equivalence classes of the permutations under the Baxter congruence form intervals of the permutohedron. Next, in Section 4, we develop a Robinson-Schensted-like insertion algorithm that allows to decide if two words are equivalent according to the Baxter congruence. Given a word, this algorithm computes iteratively a pair of twin binary trees inserting one by one the letters of u. We give as well some algorithms to read the minimal, the maximal and the Baxter permutation of a Baxter equivalence class encoded by a pair of twin binary trees. We also show that each equivalence class of permutations under the Baxter congruence contains exactly one Baxter permutation. Section 5 is devoted to the study of some properties of the equivalence classes of permutations under the Baxter congruence. This leads to the definition of a lattice structure on pairs of twin binary trees, very similar to the Tamari lattice [START_REF] Tamari | The algebra of bracketings and their enumeration[END_REF][START_REF] Knuth | The art of computer programming[END_REF] since covering relations can be expressed by binary tree rotations. We introduce in this section twin Tamari diagrams that are objects in bijection with pairs of twin binary trees and offer a simple way to test comparisons in this lattice. Finally, in Section 6, we start by recalling some basic facts about the Hopf algebra of Free quasi-symmetric functions FQSym, and then give our construction of the Hopf algebra Baxter and study it. Using the polynomial realization of FQSym, we deduce a polynomial realization of Baxter. Using the order structure on pairs of twin binary trees defined in the above section, we describe its product as an interval of this order. Moreover, we prove that this Hopf algebra is free as an algebra by constructing two multiplicative bases, and introduce two operators on pairs of twin binary trees, analogous to the operators over and under of Loday-Ronco on binary trees [START_REF] Loday | Order Structure on the Algebra of Permutations and of Planar Binary Trees[END_REF]. Using the results of Foissy on bidendriform bialgebras [START_REF] Foissy | Bidendriform bialgebras, trees, and free quasi-symmetric functions[END_REF], we show that this Hopf algebra is also self-dual and that the Lie algebra of its primitive elements is free. We conclude by explaining some morphism with other known Hopf subalgebras of FQSym.

This paper is an extended version of [START_REF] Giraudo | Algebraic and combinatorial structures on Baxter permutations[END_REF]. It contains all proofs and Sections 4 and 6 have new results.

Acknowledgments. The author would like to thank Florent Hivert and Jean-Christophe Novelli for their advice and help during all stages of the preparation of this paper. The computations of this work have been done with the open-source mathematical software Sage [S + 11].

Preliminaries

2.1. Words, definitions and notations. In the sequel, A := {a 1 < a 2 < • • • } is a totally ordered infinite alphabet and A * is the free monoid generated by A. Let u ∈ A * . We shall denote by |u| the length of u and by ǫ the word of length 0. The largest (resp. smallest) letter of u is denoted by max(u) (resp. min(u)). The evaluation ev(u) of the word u is the nonnegative integer vector such that its i-th entry is the number of occurrences of the letter a i in u. It is convenient to denote by Alph(u) := {u i : 1 i |u|} the smallest alphabet on which u is defined. We say that (i, j) is an inversion of u if i < j and u i > u j . Additionally, i is descent of u if (i, i + 1) is an inversion of u.

Let us now recall some classical operations on words. We shall denote by u ∼ := u |u| . . . u 1 the mirror image of u and by u |S the restriction of u on the alphabet S ⊆ A, that is the longest subword of u such that Alph(u) ⊆ S. Let v ∈ A * . The shuffle product ¡ is recursively defined on the linear span of words Z A by

(2.1) u ¡ v :=      u if v = ǫ, v if u = ǫ, a(u ′ ¡ bv ′ ) + b(au ′ ¡ v ′ ) otherwise, where u = au ′ , v = bv ′ , and a, b ∈ A.
For example,

a 1 a 2 ¡ a 2 a 1 = a 1 a 2 a 2 a 1 + a 1 a 2 a 2 a 1 + a 1 a 2 a 1 a 2 + a 2 a 1 a 2 a 1 + a 2 a 1 a 1 a 2 + a 2 a 1 a 1 a 2 , = a 1 a 2 a 1 a 2 + 2 a 1 a 2 a 2 a 1 + 2 a 2 a 1 a 1 a 2 + a 2 a 1 a 2 a 1 . (2.2) Let A # := {a # 1 > a # 2 > • •
• } be the alphabet A on which the order relation has been reversed. The Schützenberger transformation # is defined on words by

(2.3) u # = u 1 u 2 . . . u |u| # := u # |u| . . . u # 2 u # 1 .
For example, (a

5 a 3 a 1 a 1 a 5 a 2 ) # = a # 2 a # 5 a # 1 a # 1 a # 3 a # 5 .
Note that by setting A # # := A, the transformation # becomes an involution on words.

2.2. Permutations, definitions and notations. Denote by S n the set of permutations of size n and by S the set of all permutations. One can see a permutation of size n as a word without repetition of length n on the first letters of A. We shall call i a recoil of σ ∈ S n if (i, i + 1) is an inversion of σ -1 . By convention, n also is a recoil of σ.

The (right) permutohedron order is the partial order P defined on S n where σ is covered by ν if σ = u ab v and ν = u ba v where a < b ∈ A, and u and v are words. Recall that one has σ P ν if and only if any inversion of σ -1 also is an inversion of ν -1 . Let σ, ν ∈ S. The permutation σ ν is obtained by concatenating σ and the letters of ν incremented by |σ|; In the same way, the permutation σ ν is obtained by concatenating the letters of ν incremented by |σ| and σ. For example, (2.4) 312 2314 = 3125647 and 312 2314 = 5647312. The standardized word std(u) of u ∈ A * is the unique permutation of size |u| having the same inversions as u. For example, std(a 3 a 1 a 4 a 2 a 5 a 7 a 4 a 2 a 3 ) = 416289735.

A permutation σ is connected if σ = ν π implies ν = σ or π = σ. Similarly, σ is anti-connected if σ ∼ is connected.
2.3. Binary trees, definitions and notations. We call binary tree any complete rooted planar binary tree. Recall that a binary tree T is either a leaf (also called empty tree) denoted by ⊥, or a node that is attached through two edges to two binary trees, called respectively the left subtree and the right subtree of T . Let BT n be the set of binary trees with n nodes and BT be the set of all binary trees. We use in the sequel the standard terminology (i.e., child, ancestor, path, etc.) about binary trees [START_REF] Aho | Foundations of Computer Science[END_REF]. In our graphical representations, nodes are represented by circles , leaves by squares , edges by segments or , and arbitrary subtrees by big squares like .

2.3.1. The Tamari order. The Tamari order [START_REF] Tamari | The algebra of bracketings and their enumeration[END_REF][START_REF] Knuth | The art of computer programming[END_REF] is the partial order T defined on BT n where T 0 ∈ BT n is covered by T 1 ∈ BT n if it is possible to obtain T 1 by performing a right rotation into T 0 (see Figure 1). One has T 0 T T 1 if and only if starting from T 0 , it is possible to obtain T 1 by performing some right rotations.

2.3.2.

Operations on binary trees. If L and R are binary trees, denote by L ∧ R the binary tree which has L as left subtree and R as right subtree. Similarly, if L and R are A-labeled binary trees, denote by L ∧ a R the A-labeled binary tree which has L as left subtree, R as right subtree and a root labeled by a ∈ A.

Let T 0 , T 1 ∈ BT . The binary tree T 0 T 1 is obtained by grafting T 0 from its root on the leftmost leaf of T 1 ; In the same way, the binary tree T 0 T 1 is obtained by grafting T 1 from its root on the rightmost leaf of T 0 .

For example, for T 0 := and T 1 := , (2.7) we have

T 0 ∧ T 1 = , (2.8) T 0 T 1 = and T 0 T 1 = .
(2.9) 2.3.3. Binary search trees, increasing, and decreasing binary trees. An A-labeled binary tree T is a right (resp. left) binary search tree if for any node x labeled by b, each label a of a node in the left subtree of x and each label c of a node in the right subtree of x, the inequality a b < c (resp. a < b c) holds.

A binary tree T ∈ BT n is an increasing (resp. decreasing) binary tree if it is bijectively labeled on {1, . . . , n} and, for any node x of T , if y is a child of x, then the label of y is greater (resp. smaller) than the label of x.

The shape sh(T ) of an A-labeled binary tree T is the unlabeled binary tree obtained by forgetting its labels. 2.3.4. Inorder traversal. The inorder traversal of a binary tree T consists in recursively visiting its left subtree, then its root, and finally its right subtree (see Figure 2). We shall say that a node x is the i-th node of T if x is the i-th visited node by the inorder traversal of T . In the same way, a leaf y is the j-th leaf of T if y is the j-th visited leaf by the inorder traversal of T . We also say that i is the index of x and j is the index of y. If T is labeled, its inorder reading is the word u 1 . . . u |u| such that for any 1 i |u|, u i is the label of the i-th node of T . Note that when T is a right (or left) binary search tree, its inorder reading is a nondecreasing word.

2.3.5. The canopy of binary trees. The canopy (see [START_REF] Loday | Hopf Algebra of the Planar Binary Trees[END_REF] and [START_REF] Viennot | Up-down sequences of permutations, paths and canopy of binary trees[END_REF]) cnp(T ) of a binary tree T is the word on the alphabet {0, 1} obtained by browsing the leaves of T from left to right except the first and the last one, writing 0 if the considered leaf is oriented to the right, 1 otherwise (see Figure 3). Note that the orientation of the leaves in a binary tree is determined only by its nodes so that we can omit to draw the leaves in our graphical representations. 2.4. Baxter permutations and pairs of twin binary trees.

Baxter permutations.

A permutation σ is a Baxter permutation if for any subword u := u 1 u 2 u 3 u 4 of σ such that the letters u 2 and u 3 are adjacent in σ, std(u) / ∈ {2413, 3142}. In other words, σ is a Baxter permutation if it avoids the generalized permutation patterns 2-41-3 and 3 -14 -2 (see [START_REF] Babson | Generalized permutation patterns and a classification of the Mahonian statistic[END_REF] for an introduction on generalized permutation patterns). For example, 42173856 is not a Baxter permutation; On the other hand 436975128, is a Baxter permutation. Let us denote by S B n the set of Baxter permutations of size n and by S B the set of all Baxter permutations.

Pairs of twin binary trees.

A pair of twin binary trees (T L , T R ) is made of two binary trees T L , T R ∈ BT n such that the canopies of T L and T R are complementary, that is (2.10) cnp(T L ) i = cnp(T R ) i for all 1 i n -1 (see Figure 4).

Denote by T BT n the set of pairs of twin binary trees where each binary tree has n nodes and by T BT the set of all pairs of twin binary trees.

An A-labeled pair of twin binary trees (T L , T R ) is a pair of twin binary search trees if T L (resp. T R ) is an A-labeled left (resp. right) binary search tree and T L and T R have the same inorder reading. The shape sh(J) of an A-labeled pair of twin binary trees J := (T L , T R ) is the unlabeled pair of twin binary trees (sh(T L ), sh(T R )).

In [START_REF] Dulucq | Mots de piles, tableaux standards et permutations de Baxter[END_REF], Dulucq and Guibert have highlighted a bijection between Baxter permutations and unlabeled pairs of twin binary trees. In the sequel, we shall make use of a very similar bijection.

The Baxter monoid

Definition and first properties. Recall that an equivalence relation

≡ defined on A * is a congruence if for all u, u ′ , v, v ′ ∈ A * , u ≡ u ′ and v ≡ v ′ imply uv ≡ u ′ v ′ .
Note that the quotient A * / ≡ of A * by a congruence ≡ is naturally a monoid. Indeed, by denoting by τ : A * → A * / ≡ the canonical projection, the set A * / ≡ is endowed with a product • defined by u • v := τ (uv) for all u, v ∈ A * / ≡ where u and v are any words such that τ (u) = u and τ (v) = v.

, v ∈ A * , u ≡ v implies u # ≡ v # .
Proposition 3.4. The Baxter monoid is compatible with the Schützenberger involution.

Proof. It is enough to check the property on adjacency relations. Moreover, by Proposition 3.2, it is enough to check the property for permutations. Let σ, ν ∈ S n and assume that σ ⇄ B ν.

We have σ = x b y ad z b ′ t and ν = x b y da z b ′ t for some letters a < b, b ′ < d and words x, y, z, and t. We have Note that this adjacency relation is defined by taking the images by the Schützenberger involution of the sylvester adjacency relation. Indeed, for all u, v ∈ A * , u ≡ S # v if and only if u # ≡ S v # .

(3.8) σ # = t # b ′# z # d # a # y # b # x # and ν # = t # b ′# z # a # d # y # b # x # . Since d # < b ′# , b # < a # , we have σ # ⇄ B ν # .
In [START_REF] Hivert | The Algebra of Binary Search Trees[END_REF], Hivert, Novelli and Thibon have shown that two words are sylvester equivalent if and only if each gives the same right binary search tree by inserting their letters from right to left using the binary search tree insertion algorithm [START_REF] Aho | Foundations of Computer Science[END_REF]. In our setting, we call this process the leaf insertion and it comes in two versions, depending on if the considered binary tree is a right or a left binary search tree: Algorithm: LeafInsertion. Input: An A-labeled right (resp. left) binary search tree T , a letter a ∈ A. Output: T after the leaf insertion of a.

(1) If T =⊥, return the one-node binary search tree labeled by a.

(2) Let b be the label of the root of T .

( End.

For further reference, let us recall the following theorem due to Hivert, Novelli and Thibon [START_REF] Hivert | The Algebra of Binary Search Trees[END_REF], restated in our setting and supplemented with a respective part: Theorem 3.5. Two words are ≡ S -equivalent (resp. ≡ S # -equivalent) if and only if they give the same right (resp. left) binary search tree by inserting their letters from right to left (resp. left to right).

In other words, any A-labeled right (resp. left) binary search tree encodes a sylvester (resp. #-sylvester) equivalence class of words of A * , and conversely.

Let us explain the respective part of Theorem 3.5. It follows from (3.10) that encoding the ≡ S # -equivalence class of a word u is equivalent to encoding the ≡ S -equivalence class of u # . For this, simply insert u from left to right by considering that the reversed order relation holds between its letters. In this way, we obtain a binary tree such that for any node x labeled by a letter b, all labels a of the nodes of the left subtree of x, and all labels c of the nodes of the right subtree of x, the inequality a b > c holds. This binary tree is obviously not a left binary search tree. Nevertheless, a left binary search tree can be obtained from it after swapping, for each node, its left and right subtree recursively. One can prove by induction on |u| that this left binary search tree is the one that LeafInsertion constructs by inserting the letters of u from left to right and hence, this remark explains the difference of treatment between right and left binary search trees for the instruction (3) of LeafInsertion.

Lemma 3.6. Let u := x ac y and v := x ca y be two words such that x and y are two words, a < c are two letters, and u ≡ S v. Then, u ⇌ S v.

Proof. Follows from Theorem 3.5: Since u and v give the same right binary search tree T by inserting these from right to left, the node labeled by a and the node labeled by c in T cannot be ancestor one of the other. That implies that there exists a node labeled by a letter b, common ancestor of both nodes labeled by a and c such that a b < c. Thus, u ⇌ S v.

Lemma 3.6 also proves that the ⇌ S -adjacency relations of any equivalence class C of S n / ≡S are exactly the covering relations of the permutohedron restricted to the elements of C. Note that it is also the case for the ⇌ S # -adjacency relations.

The Baxter monoid, the sylvester monoid and the #-sylvester monoid are related in the following way. (⇐): Since the sylvester and the #-sylvester monoids are compatible with the destandardization process [START_REF] Hivert | The Algebra of Binary Search Trees[END_REF], it is enough to check the property for permutations. Let σ, ν ∈ S n such that σ ≡ S ν and σ ≡ S # ν. Set τ := inf P {σ, ν}. Since the permutohedron is a lattice, τ is well-defined, and since the equivalence classes of permutations under the ≡ S and ≡ S # congruences are intervals of the permutohedron [HNT05], we have σ ≡ S τ ≡ S ν and σ ≡ S # τ ≡ S # ν. Moreover, by Lemma 3.6, and again since that the equivalence classes of permutations under the ≡ S and the ≡ S # congruences are intervals of the permutohedron, for each saturated chains τ P σ ′ P • • • P σ and τ P ν ′ P • • • P ν, there are sequences of ad-

jacency relations τ ⇌ S σ ′ ⇌ S • • • ⇌ S σ, τ ⇌ S # σ ′ ⇌ S # • • • ⇌ S # σ, τ ⇌ S ν ′ ⇌ S • • • ⇌ S ν and τ ⇌ S # ν ′ ⇌ S # • • • ⇌ S # ν. Hence, τ ≡ B σ and τ ≡ B ν, implying σ ≡ B ν.
Proposition 3.7 shows that the ≡ B -equivalence classes are the intersection of ≡ S -equivalence classes and ≡ S # -equivalence classes.

By the characterization of the ≡ B -equivalence classes provided by Proposition 3.7, restricting the Baxter congruence on permutations, we have the following property: Proposition 3.8. For any n 0, each equivalence class of S n / ≡B is an interval of the permutohedron.

Proof. By Proposition 3.7, the ≡ B -equivalence classes are the intersection of the ≡ S and the ≡ S # -equivalence classes. Moreover, the permutations under the ≡ S and the ≡ S # equivalence relations are intervals of the permutohedron [START_REF] Hivert | The Algebra of Binary Search Trees[END_REF]. The proposition comes from the fact that the intersection of two lattice intervals is also an interval and that the permutohedron is a lattice. Lemma 3.9. Let u := x ad y and v := x da y such that x and y are two words, a < d are two letters, and u

≡ B v. Then, u ⇌ B v or u ⇋ B v.
Proof. By Proposition 3.7, since u ≡ B v, we have u ≡ S v and thus by Lemma 3.6 we have u ⇌ S v, implying the existence of a letter b ′ in the factor y satisfying a b ′ < d. In the same way, we also have u ≡ S # v and thus u ⇌ S # v, hence the existence of a letter b in the factor x satisfying a < b d. That proves that u and v are ⇌ B or ⇋ B -adjacent. Lemma 3.9 is the analog, in the case of the Baxter congruence, of Lemma 3.6 and also proves that the ⇌ B and ⇋ B -adjacency relations of any equivalence class C of S n / ≡B are exactly the covering relations of the permutohedron restricted to the elements of C. The k-recoil monoid is the quotient of the free monoid A * by the congruence ≡ R (k) . Note that the congruence ≡ R (2) restricted to permutations is nothing but the hypoplactic congruence [START_REF] Novelli | On the hypoplactic monoid[END_REF].

The Baxter monoid and the 3-recoil monoid are related in the following way.

Proposition 3.10. Each ≡ R (3) -equivalence class of permutations can be expressed as a union of some ≡ B -equivalence classes.

Proof. This amounts to prove that for all permutations σ and ν,

if σ ≡ B ν then σ ≡ R (3) ν. It is enough
′ < d or a < b ′ < b < d, implying that d -a 3. Hence, σ ≡ R (3) ν.
Note that Proposition 3.10 is false for the congruence ≡ R (4) since there are twenty-two equivalence classes of permutations of size 4 under the congruence ≡ B but twenty-four under ≡ R (4) . Conversely, note that ≡ R (4) is not a refinement of ≡ B since for any n 5, the permutation 1.n.n-1 . . . 2 is the only member of its ≡ B -equivalence class but not of its ≡ R (4) -equivalence class.

Moreover, it is clear, by definition of ≡ R (k) , that the ≡ R (k) -equivalence classes of permutations are union of ≡ R (k+1) -equivalence classes. Hence, by Proposition 3.10, the hypoplactic equivalence classes of permutations are union of some ≡ B -equivalence classes.

A Robinson-Schensted-like algorithm

The goal of this section is to define an analog to the Robinson-Schensted algorithm for the Baxter monoid-see [START_REF] Lascoux | Le monoïde plaxique[END_REF][START_REF] Lothaire | Algebraic combinatorics on words[END_REF] for the usual Robinson-Schensted insertion algorithm that associate to any word u its P-symbol, that is a Young tableau.

The interest of the Baxter monoid in our context is that the equivalence classes of the permutations of size n under the Baxter congruence are equinumerous with unlabeled pairs of twin binary trees with n nodes, and thus, by the results of Dulucq and Guibert [START_REF] Dulucq | Mots de piles, tableaux standards et permutations de Baxter[END_REF], also equinumerous with Baxter permutations of size n. We shall provide a proof of this property in this section, using our analog of the Robinson-Schensted algorithm.

4.1. Principle of the algorithm. We describe here an algorithm testing if two words are equivalent according to the Baxter congruence. Given a word u ∈ A * , it computes its Baxter P-symbol, that is an A-labeled pair (T L , T R ) consisting in a left and a right binary search tree such that the nondecreasing rearrangement of u is the inorder reading of both T L and T R . It also computes its Baxter Q-symbol, that is a pair of twin binary trees (S L , S R ) where S L (resp. S R ) is an increasing (resp. decreasing) binary tree, such that the inorder reading of S L and S R are the same. Moreover, T L and S L have same shape, and so have T R and S R . 4.1.1. The Baxter P-symbol.

Definition 4.1. The Baxter P-symbol (or simply P-symbol if the context is clear) of a word u ∈ A * is the pair P(u) = (T L , T R ) where T L (resp. T R ) is the left (resp. right) binary search tree obtained by leaf inserting the letters of u from left to right (resp. right to left).

Figure 6 shows the P-symbol of u := 2415253. Before showing that the P-symbol of Definition 4.1 can be used to decide if two words are equivalent under the Baxter congruence, let us give an intuitive explanation of its validity.

Recall that, according to Proposition 3.7, to represent the Baxter equivalence class of a word u, one has to represent both the equivalence class of u under the ≡ S congruence and the equivalence class of u under the ≡ S # congruence. This is exactly what the Baxter P-symbol does since, for a word u, it computes a pair (T L , T R ) where, by Theorem 3.5, T L represents the ≡ S # -equivalence class of u and T R represents the ≡ S -equivalence class of u.

4.1.2. The Baxter Q-symbol. Let us first recall two algorithms. Let u be a word. Define incr(u), the increasing binary tree of u recursively by

(4.1) incr(u) :=    ⊥ if u = ǫ, incr (v)
∧ a incr(w) where u = vaw, a = min(u), and a < min(v).

In the same way, define the decreasing binary tree of u decr(u), by Figure 6 shows the Q-symbol of u := 2415253, whose standardized word is 2516374, so that std(u) -1 = 3157246. It is plain that given a word u, the Q-symbol of u allows, in addition with its P-symbol, to retrieve the original word. Indeed, if P(u) = (T L , T R ) and Q(u) = (S L , S R ), the pair (T R , S R ) is the output of the Robinson-Schensted-like algorithm in the context of the sylvester monoid, which is a bijection between words and pairs of such binary trees [START_REF] Hivert | The Algebra of Binary Search Trees[END_REF]. Given (T R , S R ), it amounts to reading the labels of T R in the order of the corresponding labels in S R . The same holds of the pair (T L , S L ).

(4.2) decr(u) :=    ⊥ if u = ǫ, decr (

P(u) =

Correctness of the insertion algorithm.

Lemma 4.3. Let T be a non-empty binary tree and y be the i-th leaf of T . If y is left-oriented, it is attached to the i-th node of T . If y is right-oriented, it is attached to the i-1-st node of T .

Proof. We proceed by structural induction on the set of non-empty binary trees. If T is the one-node binary tree, the lemma is clearly satisfied. Otherwise, we have T = A ∧ B. Let y be the i-th leaf of T and x be the node where y is attached. If y is also in A and A =⊥, y is leftoriented and is attached to the root of T (that is the first node of T ) and the lemma is satisfied. If y is in A and A =⊥, y is also the i-th leaf of A and x is a node of A, so that the lemma follows by induction hypothesis on A. Otherwise, y is in B. If B =⊥, y is right-oriented and is attached to the root of T (that is the last node of T ) and the lemma is satisfied. Otherwise, y is the i-(n+1)-st leaf of B where n is the number of nodes of A. Assume that the node x is the j-st node of T , then, x becomes the j -(n+1)-st node of B. Hence, the lemma follows by induction hypothesis on B.

The following proposition is the key of our construction.

Proposition 4.4. Let σ be a permutation and T be the left binary search tree obtained by left leaf insertions of the letters of σ, from left to right. Then, the i+1-st leaf of T is right-oriented if and only if i is a recoil of σ.

Proof. Set a := i and c := i+1. Assume that a is a recoil of σ. We have σ = u c v a w for some words u, v, and w. Since no letter b of u and v satisfies a < b < c, the node of T labeled by c has a node labeled by a in its left subtree, itself having no right child and thus contributes, by Lemma 4.3, to a right-oriented leaf in position i+1.

Conversely, assume that a is not a recoil of σ. We have σ = u a v c w for some words u, v, and w. For the same reason as before, the node of T labeled by a has a node labeled by c in its right subtree, itself having no left child and thus contributes, by Lemma 4.3, to a left-oriented leaf in position i+1. Proof. Note by definition of the LeafInsertion algorithm that T L (resp. T R ) is a left (resp. right) binary search tree and the inorder reading of both T L and T R is the nondecreasing rearrangement of u. It is plain that the leaf insertion of u and std(u) from left to right (resp.

right to left) into left (resp. right) binary search trees give binary trees of same shape. That implies that we can consider that u =: σ is a permutation. Proposition 4.4 implies that the canopies of T L and T R are complementary because i is a recoil of σ if and only if i is not a recoil of σ ∼ . Thus, the shapes of T L and T R consist in a pair of twin binary trees.

Theorem 4.6. Let u, v ∈ A * . Then, u ≡ B v if and only if P(u) = P(v).

Proof. Assume u ≡ B v. Then, by Proposition 3.7, u and v are ≡ S and ≡ S # -equivalent. Hence, by Theorem 3.5, u and v have the same sylvester and #-sylvester P-symbol, so that P(u) = P(v).

Conversely assume that P(u) = P(v) =: (T L , T R ). Since the leaf insertion of both u and v from left to right gives T L , we have, by Theorem 3.5, u ≡ S # v. In addition, the leaf insertion of both u and v from right to left gives T R , so that, by the just cited theorem, u ≡ S v. By Proposition 3.7, we have u ≡ B v.

In the case of permutations, each ≡ B -equivalence class can be encoded by an unlabeled pair of twin binary trees because there is one unique way to bijectively label a binary tree with n nodes on {1, . . . , n} such that it is a binary search tree. Hence, in the sequel, unlabeled pairs of twin binary search trees can be considered as labeled by a permutation, and conversely. 4.2.2. The Q-symbol. Let us recall the following lemma of [START_REF] Hivert | The Algebra of Binary Search Trees[END_REF], restated in our setting and supplemented with a respective part: Lemma 4.7. Let u be a word and σ := std(u) -1 . The right (resp. left) binary search tree obtained by inserting u from right to left (resp. from left to right) and decr(σ) (resp. incr(σ)) have same shape.

Proposition 4.8. For any word u ∈ A * , the shape of the Q-symbol (S L , S R ) of u is a pair of twin binary trees. Moreover, S L is an increasing binary tree, S R is a decreasing binary tree and their inorder reading is std(u) -1 .

Proof. By definition of the Q-symbol, S L and S R are respectively the increasing and the decreasing binary trees of σ := std(u) -1 . By Lemma 4.7, a binary tree with same shape as S L (resp. S R ) can also be obtained by leaf insertions of the letters of σ -1 from left to right (resp. right to left). Thus, by Proposition 4.4, the shape of (S L , S R ) is a pair of twin binary trees. Moreover, by the definition of the algorithms incr and decr, we can prove by induction on the size of σ that the binary trees S L and S R have both σ as inorder reading.

Theorem 4.9. The map u -→ (P(u), Q(u)) is a bijection between the elements of A * and the set formed by the pairs ((T L , T R ), (S L , S R )) where (i) (T L , T R ) is a pair of twin binary search trees-T L (resp. T R ) is a left (resp. right) binary search tree, and T L and T R have both the same inorder reading; (ii) (S L , S R ) is a pair of twin binary trees where S L (resp. S R ) is an increasing (resp. decreasing) binary tree, and S L and S R have both the same inorder reading; (iii) (T L , T R ) and (S L , S R ) have same shape.

Proof. Let us first show that for any u ∈ A * , the pair (P(u), Q(u)) satisfies the assertions of the theorem. Point (i) follows from Proposition 4.5. Point (ii) follows from Proposition 4.8. Moreover, by Lemma 4.7, Point (iii) checks out. Besides, as already mentioned, it is possible to reconstruct from the pair (P(u), Q(u)) the word u and such a word is unique. That shows that the correspondence is well-defined and injective.

Conversely, assume that ((T L , T R ), (S L , S R )) satisfies the three assertions of the theorem. According to [START_REF] Hivert | An analogue of the plactic monoid for binary search trees[END_REF], there is a bijection between the elements of A * and the pairs (T R , S R ) where T R is a right binary search tree and S R a decreasing binary tree of same shape. Let u be the word in correspondence with (T R , S R ). In the same way, there is a bijection between the elements of A * and the pairs (T L , S L ) where T L is a left binary search tree and S L an increasing binary tree of same shape. Let v be the word in correspondence with (T L , S L ). By hypothesis, T L and T R have both the same inorder reading, implying ev(u) = ev(v). In the same way, since S L and S R have both the same inorder reading, one has std(u) -1 = std(v) -1 . Hence, we have std(u) = std(v) and thus u = v. Note also that the pair (T L , S L ) is entirely determined by the pair (T R , S R ) and conversely. Now, again according to [START_REF] Hivert | An analogue of the plactic monoid for binary search trees[END_REF], the pair (T R , S R ) is the sylvester P-symbol of u and the pair (T L , S R ) is the #-sylvester P-symbol of u. Hence, the insertion of u gives the pair ((T L , T R ), (S L , S R )), showing that the correspondence is also surjective. 4.3. Distinguished permutations from a pair of twin binary trees. We present in this section some algorithms to read some distinguished permutations from a pair of twin binary search trees. Let us first start with a useful characterization of ≡ B -equivalence classes. 4.3.1. Baxter equivalence classes as linear extensions of posets. Let T be an A-labeled binary tree. We shall denote by △(T ) (resp. ▽(T )) the poset (N, ) where N := {1, . . . , n}, n is the number of nodes of T , and is defined, for i, j ∈ N , by (4.4) i j if the i-th node is an ancestor (resp. descendant) of the j-th node of T .

If the sequence i 1 . . . i n is a linear extension of △(T ) (resp. ▽(T )), we shall also say that the word u 1 . . . u n is a linear extension of △(T ) (resp. ▽(T )) if for any 1 ℓ n, the label of the i ℓ -th node of T is u ℓ .

The words of a sylvester equivalence class encoded by a labeled right binary search tree T coincide with the linear extensions of ▽(T ) (see Note 4 of [START_REF] Hivert | The Algebra of Binary Search Trees[END_REF]). Additionally, this also says that the words of a #-sylvester equivalence class encoded by a labeled left binary search tree T are exactly the linear extensions of △(T ). One has a similar characterization of Baxter equivalence classes:

Proposition 4.10. The words of a Baxter equivalence class encoded by a pair of twin binary search trees (T L , T R ) coincide with the words that are both linear extensions of the posets △(T L ) and ▽(T R ).

Proof. Let u be a word belonging to the Baxter equivalence class encoded by (T L , T R ). By Theorem 4.6, T L (resp. T R ) can be obtained by leaf inserting u from left to right (resp. right to left). Hence, if i j in △(T L ) (resp. in ▽(T R )) then i is smaller than j as integers. Thus, u is a linear extension of both △(T L ) and ▽(T R ).

Assume now that u is a linear extension of △(T L ) and ▽(T R ) and let v be any word of the Baxter equivalence class encoded by (T L , T R ). By Theorem 4.6, T L (resp. T R ) can be obtained by leaf inserting v from left to right (resp. right to left). Note 4 of [START_REF] Hivert | The Algebra of Binary Search Trees[END_REF] implies that u ≡ S # v and u ≡ S v. Hence, by Proposition 3.7, one has u ≡ B v, showing that u also belongs to the Baxter equivalence class represented by (T L , T R ). Note that it is possible to represent the order relations induced by the posets △(T L ) and ▽(T R ) in only one poset △(T L )∪▽(T R ), adding on △(T L ) the order relations induced by ▽(T R ). For the previous example, we obtain the poset (3) Return u.

△(T L ) ∪ ▽(T R ) = 1

End.

Figure 8 shows an execution of this algorithm.

The results of Dulucq and Guibert [START_REF] Dulucq | Mots de piles, tableaux standards et permutations de Baxter[END_REF] imply that ExtractBaxter terminates. The only thing to prove is that the computed word belongs to the ≡ B -equivalence class encoded by the pair of twin binary search trees as input. For that, let us first prove the following lemma. If A =⊥, assume that the i-th node of T R has a non-empty left subtree. That implies that the i-th leaf of T R is not attached to its i-th node. Thus, by Lemma 4.3, the i-th leaf of T R is attached to its i-1-st node and is right-oriented. In T L , the i-th leaf cannot be attached to its i-th node because A =⊥. Hence, by Lemma 4.3, the i-th leaf of T L is also attached to its i-1-st node and is right-oriented. Since T contains at least i nodes, there is at least i+1 leaves in T , implying that the i-th leaf is not the rightmost leaf of T L and T R , and thus (T L , T R ) is not a pair of twin binary trees, contradicting the hypothesis.

Assume now that the i-th node of T R has a non-empty right subtree. That implies that the i+1-st leaf of T R is not attached to its i-th node and thus, by Lemma 4.3, the i+1-st leaf of T R is left-oriented. Moreover, since the i-th node of T R has a non-empty right subtree and the i-th node of T L is its root, the i-th node of T L also has a non-empty right subtree. That implies that the i+1-st leaf of T L is not attached to its i-th node and thus, by Lemma 4.3, the i+1-st leaf of T R is also left-oriented. That contradicts that (T L , T R ) is a pair of twin binary trees, and implies that the i-th node of T R has no child. The case B =⊥ is analogous.

Proposition 4.12. For any A-labeled pair of twin binary search trees (T L , T R ) as input, the algorithm ExtractBaxter computes a word belonging to the ≡ B -equivalence class encoded by (T L , T R ). Moreover, if (T L , T R ) is labeled by a permutation, the computed word is a Baxter permutation.

Proof. Let us prove by induction on n, that is the number of nodes of T L and T R , that if (T L , T R ) is an A-labeled pair of twin binary search trees, then ExtractBaxter returns a word that is a linear extension of △(T L ) and a linear extension of ▽(T R ), i.e., by Proposition 4.10, a word belonging to the ≡ B -equivalence class encoded by (T L , T R ). This property clearly holds for n 1. Now, assume that T L = A∧ a B where a is the label of the root of T L . By Lemma 4.11, if the root of T L is its i-th node, the i-th node x of T R has no child. Moreover, since T L and T R are binary search trees and labeled by a same word, their respective i-th nodes have the same label a. Moreover, the canopy of T L is of the form v01w where v := cnp(A) and w := cnp(B), and the canopy of T R is of the form v ′ 10w ′ where v ′ (resp. w ′ ) is the complementary of v (resp. w) since that (T L , T R ) is a pair of twin binary trees. We have now two cases whether x is a left of right child in T R .

If x is a left child in T R , the algorithm returns the word au where u is the word obtained by applying the algorithm on (T ′ L , T ′ R ) where T ′ L = A B and T ′ R is obtained from T R by suppressing the node x. First, the canopy of T ′ L is of the form v0w and the canopy of T ′ R is of the form v ′ 1w ′ . Moreover, T ′ L and T ′ R are clearly still binary search trees. That implies that (T ′ L , T ′ R ) is a pair of twin binary search trees. By induction hypothesis and Proposition 4.10, the word u belongs to the ≡ B -equivalence class encoded by (T ′ L , T ′ R ), and thus, au belongs to the ≡ B -equivalence class encoded by (T L , T R ) because au is a linear extension of △(T L ) (resp. ▽(T R )) since u is a linear extension of both △(T ′ L ) and ▽(T ′ R ). The case where x is a right child in T R is analogous.

Finally, when (T L , T R ) is labeled by a permutation, ExtractBaxter coincides with the algorithm of Dulucq and Guibert [START_REF] Dulucq | Mots de piles, tableaux standards et permutations de Baxter[END_REF] and computes a Baxter permutation.

The validity of ExtractBaxter implies the two following results.

Theorem 4.13. For any n 0, there is a bijection between the set of Baxter equivalence classes of words of length n and A-labeled pairs of twin binary search trees with n nodes.

Proof. By Proposition 4.5 and Theorem 4.6, the P-symbol algorithm induces an injection between the set of equivalence classes of S n / ≡B and the set of unlabeled pairs of twin binary trees. Moreover, by Proposition 4.12, the algorithm ExtractBaxter exhibits a surjection between these two sets. Hence, these two sets are in bijection.

Theorem 4.13 implies in particular that the Baxter equivalence classes of permutations of size n are in bijection with pairs of twin binary trees labeled by a permutation (or equivalently with unlabeled pairs of twin binary trees).

Theorem 4.14. For any n 0, each equivalence class of S n / ≡B contains exactly one Baxter permutation.

Proof. Let C be an equivalence class of S n / ≡B . By Theorem 4.13, C can be represented by an unlabeled pair of twin binary trees J. By Proposition 4.12, the algorithm ExtractBaxter computes a permutation belonging to the ≡ B -equivalence class encoded by J, showing that each ≡ B -equivalence class of permutations contains at least one Baxter permutation. The theorem follows from the fact that Baxter permutations are equinumerous with unlabeled pairs of twin binary trees. 4.3.3. Extracting minimal and maximal permutations. Reading defined in [START_REF] Reading | Lattice congruences, fans and Hopf algebras[END_REF] twisted Baxter permutations, that are the permutations avoiding the generalized permutation patterns 2 -41 -3 and 3 -41 -2. These permutations are particular elements of Baxter classes of permutations: Proposition 4.15. Twisted Baxter permutations coincide with minimal elements of Baxter equivalence classes of permutations.

Proof. First, note that by Proposition 3.8, every Baxter equivalence class of permutations has a minimal element. Assume that σ is minimal of its ≡ B -equivalence class of permutations. Then, it is not possible to perform any rewriting of the form

(4.8) b u da v b ′ → b u ad v b ′ ,
where a < b, b ′ < d are letters, and u and v are words. Hence, σ avoids the patterns 2 -41 -3 and 3 -41 -2, and is a twisted Baxter permutation. Conversely, if σ is a twisted Baxter permutation, it avoids 2 -41 -3 and 3 -41 -2 and it is not possible to perform any rewriting →, so that, by Proposition 3.8 and Lemma 3.9, it is minimal of its ≡ B -equivalence class.

In a similar way, by calling anti-twisted Baxter permutation any permutation that avoids the generalized permutation patterns 2 -14 -3 and 3 -14 -2, an analogous proof to the one of Proposition 4.15 shows that anti-twisted Baxter permutations coincide with maximal elements of Baxter equivalence classes of permutations. Proposition 4.15 implies that twisted Baxter permutations, anti-twisted Baxter permutations, and Baxter permutations are equinumerous since by Theorem 4.14 there is exactly one Baxter permutation by ≡ B -equivalence class of permutations and by Proposition 3.8, there is also exactly one twisted (and one anti-twisted) Baxter permutation. This suggests among other that there exists a bijection sending a Baxter permutation to the twisted Baxter permutation of its ≡ B -equivalence class.

As pointed out by Law and Reading, West has shown first a bijection between Baxter permutations and twisted Baxter permutations using generating trees [START_REF] Bousquet-Mélou | Four classes of pattern-avoiding permutations under one roof: generating trees with two labels[END_REF]. In our setting, as in the setting of Law and Reading [START_REF] Law | The Hopf algebra of diagonal rectangulations[END_REF], this bijection is the one preserving the classes. Here follows an algorithm to compute this bijection.

Let us consider the following algorithm which allows, given an A-labeled pair of twin binary search trees (T L , T R ), to compute the minimal permutation for the lexicographic order belonging to the ≡ B -equivalence class encoded by (T L , T R ).

Algorithm: ExtractMin.

Input: An A-labeled pair of twin binary search trees (T L , T R ). Output: The minimal word for the lexicographic order of the class encoded by (T L , T R ).

(1) Let u := ǫ be the empty word.

(2) Let F := T L be a rooted forest.

(3) While F is not empty and T R =⊥: (a) Let i be the smallest index such that the i-th node of F is a root and the i-th node of T R has no child. (b) Let a be the label of the i-th node of T L . (c) Set u := ua. (d) Suppress the i-th node of F and the i-th node of T R . (4) Return u.

End.

Note that, by choosing in the instruction (3a) the greatest index instead of the smallest, the previous algorithm would compute the maximal word for the lexicographic order of the ≡ B -equivalence class encoded by (T L , T R ). Let us call this variant ExtractMax. Figure 9 shows an example of application of ExtractMin. Proposition 4.16. For any A-labeled pair of twin binary search trees (T L , T R ) as input, the algorithm ExtractMin (resp. ExtractMax) computes the minimal (resp. maximal) word for the lexicographic order of the ≡ B -equivalence class encoded by (T L , T R ). Moreover, if (T L , T R ) is labeled by a permutation, the computed word is the minimal (resp. maximal) permutation for the permutohedron order of its ≡ B -equivalence class.

Proof. The output u of the algorithm ExtractMin (resp. ExtractMax) is both a linear extension of △(T L ) and a linear extension of ▽(T R ). That implies by Proposition 4.10 that u belongs to the ≡ B -equivalence class encoded by the input pair of twin binary trees. Moreover, this algorithm terminates since by Theorem 4.14, each A-labeled pair of twin binary search trees (T L , T R ) admits at least one word that is a common linear extension of △(T L ) and ▽(T R ). The minimality (resp. maximality) for the lexicographic order of the computed word comes from the fact that at each step, the node that has the smallest (resp. greatest) label is chosen. Finally, since the lexicographic order is a linear extension of the permutohedron order, and by Proposition 3.8, since Baxter equivalence classes are intervals of the permutohedron, Ex-tractMin (resp. ExtractMax) returns the minimal (resp. maximal) permutation for the permutohedron order of its Baxter equivalence class. By Proposition 4.16 and using our Robinson-Schensted-like algorithm, we can compute the bijection between Baxter permutations and twisted Baxter permutations in the following way: If σ is a Baxter permutation, apply ExtractMin on P(σ) to obtain its corresponding twisted Baxter permutation. Conversely, if σ is a twisted Baxter permutation, apply ExtractBaxter on P(σ) to obtain its corresponding Baxter permutation.

In the same way, we can compute a bijection between Baxter permutations and anti-twisted Baxter permutations using ExtractMax instead of ExtractMin. Moreover, these algorithms give a bijection between twisted Baxter permutations and anti-twisted Baxter permutations: If σ is a twisted (resp. anti-twisted) Baxter permutation, apply ExtractMax (resp. ExtractMin) on P(σ) to obtain its corresponding anti-twisted (resp. twisted) Baxter permutation.

Definition and correctness of the iterative insertion algorithm.

In what follows, we shall revise our P-symbol algorithm that we have presented in Section 4.1 to make it iterative. Indeed, we propose an insertion algorithm such that, for any word u such that P(u) = (T L , T R ) and any letter a, the insertion of a into (T L , T R ) is the pair of twin binary trees P(ua). This, besides being in agreement with the usual Robinson-Schensted-like algorithms, has the merit to allow to compute in the Baxter monoid. Indeed, this gives a simple way to compute the concatenation of two words u and v under the Baxter congruence simply by inserting the letters of the word uv into the pair (⊥, ⊥). Note that one can compute the product of two pairs of twin binary trees (T L , T R ) and (T ′ L , T ′ R ) by computing a word u ′ that belongs to the ≡ B -equivalence class of (T ′ L , T ′ R ) by applying the algorithm ExtractMin (or ExtractBaxter) with (T ′ L , T ′ R ) as input, and then, by inserting the letters of u ′ from left to right into (T L , T R ). 4.4.1. Root insertion in binary search trees. Let T be an A-labeled right binary search tree and b a letter of A. The lower restricted binary tree of T compared to b, namely T b , is the right binary search tree uniquely made of the nodes x of T labeled by letters a satisfying a b and such that for all nodes x and y of T b , if x is ancestor of y in T b , then x is also ancestor of y in T . In the same way, we define the higher restricted binary tree of T compared to b, namely T >b (see Figure 10). Let T be an A-labeled right binary search tree and a a letter of A. The root insertion of a into T consists in modifying T so that the root of T is a new node labeled by a, its left subtree is T a and its right subtree is T >a .

The iterative insertion algorithm.

Definition 4.17. Let (T L , T R ) be an A-labeled pair of twin binary search trees and a be a letter. The insertion of a into (T L , T R ) consists in making a leaf insertion of a into T L and a root insertion of a into T R . The iterative Baxter P-symbol (or simply iterative P-symbol if the context is clear) of a word u ∈ A * is the pair P(u) = (T L , T R ) computed by iteratively inserting the letters of u, from left to right, into (⊥, ⊥). The iterative Baxter Q-symbol (or simply iterative Q-symbol if the context is clear) of u ∈ A * is the pair Q(u) = (S L , S R ) of same shape as P(u) and such that each node is labeled by its date of creation in P(u). The correctness of the iterative version of the Q-symbol algorithm comes from the correctness of the iterative P-algorithm.

⊥⊥ 2 --→ 1 1 4 --→ 1 2 1 2 1 --→ 3 1 2 3 1 2 5 --→ 3 1 2 4 3 1 2 4 2 --→

The Baxter lattice

5.1. The Baxter lattice congruence. Recall that an equivalence relation ≡ on the elements of a lattice (L, ∧, ∨) is a lattice congruence if for all x, x ′ , y, y ′ ∈ L, x ≡ x ′ and y ≡ y ′ imply x ∧ y ≡ x ′ ∧ y ′ and x ∨ y ≡ x ′ ∨ y ′ . The quotient L/ ≡ of L by ≡ is naturally a lattice. Indeed, by denoting by τ : L → L/ ≡ the canonical projection, the set L/ ≡ is endowed with meet and join operations defined by x ∧ y := τ (x ∧ y) and x ∨ y := τ (x ∨ y) for all x, y ∈ L/ ≡ where x and y are any elements of L such that τ (x) = x and τ (y) = y.

Lattices congruences admit the following very useful order-theoretic characterization [START_REF] Chajda | Congruences in Ordered Sets[END_REF][START_REF] Reading | Lattice congruences, fans and Hopf algebras[END_REF]. An equivalence relation ≡ on the elements of a lattice (L, ∧, ∨) seen as a poset (L, ) is a lattice congruence is the following three conditions hold. For any permutation σ, let us denote by σ↓ (resp. σ↑) the maximal (resp. minimal) permutation of the ≡ B -equivalence class of σ for the permutohedron order. Note by Proposition 3.8 that σ↓ and σ↑ are well-defined.

Theorem 5.1. The Baxter equivalence relation is a lattice congruence of the permutohedron.

Proof. By Proposition 3.8, any Baxter equivalence class of permutations is an interval of the permutohedron, so that (L1) checks out. One just has to show that ≡ B satisfies (L2) and (L3).

Let σ and ν two permutations such that σ P ν. Let us show that σ↓ P ν↓. It is enough to check the property when ν = σs i where s i is an elementary transposition and i is not a descent of σ. If σ = σ↓, then σ↓ P ν P ν↓ and the property holds. Otherwise, by Lemma 3.9, there exists an elementary transposition s j and a permutation π such that π and σ are ⇄ Badjacent, π = σs j and σ P π. It then remains to prove that there exists a permutation µ such that ν ≡ B µ and π P µ. Indeed, this leads to show, by applying iteratively this reasoning, that σ↓ is smaller than a permutation belonging to the ≡ B -equivalence class of ν for the permutohedron order and hence, by transitivity, that σ↓ P ν↓. We have four cases: Case 1: If j i -2, σ is of the form σ = u ab v cd w where u, v, and w are some words and a (resp. c) is the j-th (resp. i-th) letter of σ. One has a < b and c < d since i and j are not descents of σ. We have ν = u ab v dc w and νs j = u ba v dc w =: µ. Moreover, since π ⇄ B σ, there are some letters x ∈ Alph(u) and y ∈ Alph(v cd w) such that a < x, y < b. Thus, µ ⇄ B ν. Finally, since π = u ba v cd w, π P µ, so that µ is appropriate. Case 2: If j i + 2, this is analogous to the previous case. Case 3: If j = i + 1, σ is of the form σ = u abc v where u and v are some words and a is the i-th letter of σ. One has a < b < c since i and j are not descents of σ. Since σ ⇄ B π, there are some letters x ∈ Alph(u) and y ∈ Alph(v) such that b < x, y < c. Thus, since ν = u bac v and a < b < x, y < c, we have νs j = u bca v ⇄ B ν. Moreover, νs j s i = u cba v =: µ and νs j ⇄ B νs j s i since b < x, y < c and thus, µ ≡ B ν. Finally, since π = u acb v, we have π P µ, and hence µ is appropriate. Case 4: If j = i -1, this is analogous to the previous case. Hence, the Baxter equivalence relation satisfies (L2). The proof that ≡ B satisfies (L3) is analogous.

5.2.

A lattice structure over the set of pairs of twin binary trees. Recall that by Theorem 4.13, the Baxter equivalence classes of permutations are in correspondence with unlabeled pairs of twin binary trees. Thus, the quotient of the permutohedron of order n by the Baxter congruence is a lattice (T BT n , B ) where the Baxter order relation B satisfies, for any J 0 , J 1 ∈ T BT n , (5.1) J 0 B J 1 if and only if there are σ, ν ∈ S n such that σ P ν, P (σ) = J 0 and P (ν) = J 1 .

Let us call Baxter lattice the lattice (T BT n , B ). Figure 12 shows the ≡ B -equivalence classes in the permutohedron of order 4 that form the Baxter lattice (T BT 4 , B ).

′ L , T ′ R ), (5.3) (T L , T R ) B (T ′ L , T ′ R ) if and only if T ′ L T T L and T R T T ′ R .
Note that a right rotation at root y in a binary tree T changes its canopy if and only if the right subtree B of the left child x of y is empty (see Figure 1). Similarly, a left rotation at root y changes the canopy of T if and only if the left subtree B of y is empty. Moreover, if y is the i-th node of T , by Lemma 4.3, one can see that B is the i-th leaf of T . Hence, the right (resp. left) rotation at root y changes the orientation of the i-th leaf of T formerly on the right to the left (resp. left to the right). 5.4. Twin Tamari diagrams. The purpose of this section is to introduce twin Tamari diagrams. These diagrams are in bijection with pairs of twin binary trees and provide a useful realization of the Baxter lattice since it appears that testing if two twin Tamari diagrams are comparable under the Baxter order relation is immediate. 5.4.1. Tamari diagrams and the Tamari order relation. Pallo introduced in [Pal86] words in bijection with binary trees (see also [START_REF] Knuth | The art of computer programming[END_REF]). We call Tamari diagrams these words and to compute the Tamari diagram td(T ) of a binary tree T , just label each node x of T by the number of nodes in the right subtree of x and then, consider its inorder reading.

Any Tamari diagram δ of length n satisfies the following two inequalities:

(1) 0 δ i n -i, for all 1 i n;

(2) δ i+j δ i -j, for all 1 i n and 1 j δ i .

The main interest of Tamari diagrams is that they offer a very simple way to test if two binary trees are comparable in the Tamari lattice [START_REF] Knuth | The art of computer programming[END_REF]. Indeed, if T and T ′ are two binary trees with n nodes, one has (5.4) T T T ′ if and only if td(T ) i td(T ′ ) i for all 1 i n.

5.4.2. Twin Tamari diagrams and the Baxter order relation.

Definition 5.2. A twin Tamari diagram of size n is a pair δ L , δ R such that δ L and δ R are Tamari diagrams of length n and for all index 1 i n -1, exactly one letter among δ L i and δ R i is zero. Note that we can represent any twin Tamari diagram δ := δ L , δ R in a more compact way by a word ω(δ) were

(5.5) ω(δ) i := -δ L i if δ L i = 0, δ R i otherwise,
for all 1 i n where n is the size of δ. We graphically represent a twin Tamari diagram δ by drawing for each index i a column of |ω(δ) i | boxes facing up if ω(δ) i 0 and facing down otherwise. First twin Tamari diagrams are drawn in Figure 13.

ǫ , , , , , , , , , Figure 13
. First twin Tamari diagrams of size 0, 1, 2, and 3.

Proposition 5.3. For any n 0, the set of twin Tamari diagrams of size n is in bijection with the set of pairs of twin binary trees with n nodes. Moreover, this bijection is expressed as follows: If J := (T L , T R ) is a pair of twin binary trees, the twin Tamari diagram in bijection with J is ttd(J) := (td(T L ), td(T R )).

Proof. Let us show that the application ttd is well-defined, that is ttd(J) =: δ L , δ R is a twin Tamari diagram. Fix an index 1 i n -1. By contradiction, assume first that δ L i = δ R i = 0. By definition of td, this implies that the i-th nodes of T L and T R have no right child. Hence, by Lemma 4.3, the i+1-st leaves of T L and T R are attached to its i-th nodes and are right-oriented. Since i n-1, these leaves are not the rightmost leaves of T L and T R , implying that T L and T R have not complementary canopies, and hence that (T L , T R ) is not a pair of twin binary trees. Assume now that δ L i = 0 and δ R i = 0. By definition of td, this implies that the i-th nodes of T L and T R have a right child. Hence, by Lemma 4.3, the i+1-st leaves of T L and T R are attached to its i+1-st nodes and are left-oriented. This implies again that (T L , T R ) is not a pair of twin binary trees. Thus, ttd computes twin Tamari diagrams. Now, since td is a bijection between the set of binary trees with n nodes and Tamari diagrams of size n [Pal86], for any twin Tamari diagram δ, there is a unique pair of binary trees J such that ttd(J) = δ. Using very similar arguments as above, one can prove that the canopies of the trees of J are complementary, and hence, that J is a pair of twin binary trees. Proposition 5.4. Let J 0 and J 1 two pairs of twin binary trees with n nodes. We have

(5.6) J 0 B J 1 if and only if ω (ttd (J 0 )) i ω (ttd (J 1 )) i for all 1 i n.
Proof. This result is a direct consequence of the characterization of the Baxter order relation (5.3) using the Tamari order relation, the characterization furnished by (5.4) to compare two binary trees in the Tamari lattice with Tamari diagrams, and the bijection between pairs of twin binary trees and Twin Tamari diagrams provided by Proposition 5.3.

Figure 15 shows an interval of the Baxter lattice.

Figure 15. An interval of the Baxter lattice of order 5 where vertices are seen as pairs of twin binary trees and as Twin Tamari diagrams.

The Hopf algebra of pairs of twin binary trees

In the sequel, all the algebraic structures have a field of characteristic zero K as ground field.

6.1. The Hopf algebra FQSym and construction of Hopf subalgebras.

6.1.1. The Hopf algebra FQSym. Recall that the family {F σ } σ∈S forms the fundamental basis of FQSym, the Hopf algebra of Free quasi-symmetric functions [START_REF] Malvenuto | Duality between quasi-symmetric functions and Solomon descent algebra[END_REF][START_REF] Duchamp | Noncommutative Symmetric Functions VI: Free Quasi-Symmetric Functions and Related Algebras[END_REF]. Its product and its coproduct are defined by (6.1)

F σ • F ν := π ∈ σ ¢ ν F π , (6.2) ∆ (F σ ) := σ=uv F std(u) ⊗ F std(v) .
For example,

F 132 • F 12 = F 13245 + F 13425 + F 13452 + F 14325 + F 14352 + F 14532 + F 41325 + F 41352 + F 41532 + F 45132 , (6.3) ∆ (F 35142 ) = 1 ⊗ F 35142 + F 1 ⊗ F 4132 + F 12 ⊗ F 132 + F 231 ⊗ F 21 + F 2413 ⊗ F 1 + F 35142 ⊗ 1. (6.4) Set G σ := F σ -1 . Recall that FQSym is isomorphic to its dual FQSym ⋆ through the map ψ : FQSym → FQSym ⋆ defined by ψ (F σ ) := F ⋆ σ -1 = G ⋆ σ .
Recall also that FQSym admits a polynomial realization [START_REF] Duchamp | Noncommutative Symmetric Functions VI: Free Quasi-Symmetric Functions and Related Algebras[END_REF], that is an injective algebra morphism r A : FQSym ֒→ K A . Furthermore, this map should be compatible with the coalgebra structure in the sense that the coproduct of an element can be computed by taking its image by r A , and then by applying the alphabet doubling trick [START_REF] Duchamp | Noncommutative Symmetric Functions VI: Free Quasi-Symmetric Functions and Related Algebras[END_REF][START_REF] Hivert | An introduction to Combinatorial Hopf Algebras-examples and realizations[END_REF]. This map is defined by

(6.5) r A (G σ ) := u ∈ A * std(u)=σ u.
For example, The following theorem contained in an unpublished note of Hivert and Nzeutchap [START_REF] Hivert | Dual graded graphs in combinatorial Hopf algebras[END_REF] (see also [START_REF] Duchamp | Noncommutative Symmetric Functions VI: Free Quasi-Symmetric Functions and Related Algebras[END_REF][START_REF] Hivert | An introduction to Combinatorial Hopf Algebras-examples and realizations[END_REF]) shows that an equivalence relation on A * satisfying some properties can be used to define Hopf subalgebras of FQSym: Theorem 6.1. Let ≡ be an equivalence relation defined on A * . If ≡ is a congruence, compatible with the restriction of alphabet intervals and compatible with the destandardization process, then the family {P σ } σ∈S/≡ defined by (6.9)

r A (G ǫ ) = 1, (6.6) r A (G 1 ) = i a i = a 1 + a 2 + a 3 + • • • , (6.7) r A (G 231 ) = k<i j a i a j a k = a 2 a 2 a 1 + a 2 a 3 a 1 + a 2 a 4 a 1 + • • • . (6.8) 6.1.2.
P σ := ν ∈ σ F ν ,
spans a Hopf subalgebra of FQSym.

The compatibility with the destandardization process and with the restriction of alphabet intervals imply that for any F π appearing in a product P σ •P ν and any permutation π ′ ≡ π, F π ′ also appears in the product. Moreover, the compatibility with the destandardization process and the fact that ≡ is a congruence imply that for any F σ ⊗F ν appearing in a coproduct ∆ (P π ) and any permutations σ ′ ≡ σ and ν ′ ≡ ν, F σ ′ ⊗ F ν ′ also appears in the coproduct.

In the sequel, we shall call {P σ } σ∈S/≡ the fundamental basis of the corresponding Hopf subalgebra of FQSym.

6.2. Construction of the Hopf algebra Baxter. By Theorem 4.13, the ≡ B -equivalence classes of permutations can be encoded by unlabeled pairs of twin binary trees. Moreover, in the sequel, the P-symbols of permutations are regarded as unlabeled pairs of twin binary trees since there is only one way to label a pair of twin binary trees with a permutation so that it is a pair of twin binary search trees. Hence, in our graphical representations we will only represent their shape.

Since by definition ≡ B is a congruence, since by Propositions 3.2 and 3.3, ≡ B satisfies the conditions of Theorem 6.1, and since by Theorem 4.6, the permutations σ such that P(σ) = J coincide with the Baxter equivalence class represented by the pair of twin binary trees J, we have the following theorem.

Theorem 6.2. The family {P J } J∈T BT defined by (6.10)

P J := σ ∈ S P(σ)=J F σ ,
spans a Hopf subalgebra of FQSym, namely the Hopf algebra Baxter.

For example, P = F 12 , (6.11)

P

= F 2143 + F 2413 , (6.12)

P = F 542163 + F 542613 + F 546213 . (6.13)
The Hilbert series of Baxter is (6.14) B(z) := 1 + z + 2z 2 + 6z 3 + 22z 4 + 92z 5 + 422z 6 + 2074z 7 + 10754z 8 + 58202z 9 + • • • , the generating series of Baxter permutations (sequence A001181 of [Slo]). By Theorem 6.1, the product of Baxter is well-defined. We deduce it from the product of FQSym, and, since by Theorem 4.14 there is exactly one Baxter permutation in any ≡ Bequivalence class of permutations, we obtain (6.15) P J0

6.3.1.

A polynomial realization. We deduce a polynomial realization of Baxter from the one of FQSym. In this section, we shall use the notation J 0 ≃ J 1 to say that the labeled pairs of twin binary trees J 0 and J 1 have same shape.

Theorem 6.3. The map r A : Baxter → K A defined by (6.19) r A (P J ) := u ∈ A * (incr(u), decr(u))≃J u, for any J ∈ T BT provides a polynomial realization of Baxter.

Proof. Let us apply the polynomial realization r A of FQSym defined in (6.5) on elements of the fundamental basis of Baxter:

r A (P J ) = σ ∈ S P(σ)=J r A (F σ ), (6.20) = σ ∈ S P(σ -1 )=J r A (G σ ), (6.21) = σ ∈ S (incr(σ), decr(σ))≃J r A (G σ ), (6.22) = σ ∈ S (incr(σ), decr(σ))≃J u ∈ A * std(u)=σ
u, (6.23)

The equality between (6.21) and (6.22) follows from Lemma 4.7. The equality between (6.23) and the right member of (6.19) follows from the fact that incr(σ) ≃ incr(u) (resp. decr(σ) ≃ decr(u)) whenever std(u) = σ. 6.3.2. The dual Hopf algebra. We denote by {P ⋆ J } J∈T BT the dual basis of the basis {P J } J∈T BT . The Hopf algebra Baxter ⋆ , dual of Baxter, is a quotient Hopf algebra of FQSym ⋆ . More precisely, (6.24)

Baxter ⋆ = FQSym ⋆ /I, where I is the Hopf ideal of FQSym ⋆ spanned by the elements (F ⋆ σ -F ⋆ ν ) whenever σ ≡ B ν. Let φ : FQSym ⋆ ։ Baxter ⋆ be the canonical projection, mapping F ⋆ σ on P ⋆ P(σ) . By definition, the product of Baxter ⋆ is (6.25)

P ⋆ J0 • P ⋆ J1 = φ (F ⋆ σ • F ⋆ ν )
, where σ and ν are any permutations such that P(σ) = J 0 and P(ν) = J 1 . Note that due to the fact that Baxter ⋆ is a quotient of FQSym ⋆ , the number of terms occurring in a product P ⋆ J0 • P ⋆ J1 only depends on the number m (resp. n) of nodes of J 0 (resp. J 1 ) and is m+n m . For example,

P ⋆

• P ⋆ = P ⋆ + P ⋆ + P ⋆ + P ⋆ + P ⋆ + P ⋆ + P ⋆ + P ⋆ + P ⋆ + P ⋆ .

(6.26)

In the same way, the coproduct of Baxter ⋆ is (6.27)

∆(P J ) = (φ ⊗ φ) (∆ (F ⋆ σ ))
, where σ is any permutation such that P(σ) = J. Note that the number of terms occurring in a coproduct ∆ (P J ) only depends on the number n of nodes of each binary trees of J and is n + 1. For example, ∆ P ⋆ = 1 ⊗ P ⋆ + P ⋆ ⊗ P ⋆ + P ⋆ ⊗ P ⋆ + P ⋆ ⊗ P ⋆ + P ⋆ ⊗ 1.

(6.28)

Following Fomin [START_REF] Fomin | Duality of Graded Graphs[END_REF] (see also [START_REF] Bergeron | Combinatorial Hopf Algebras and Towers of Algebras[END_REF]), we can build a pair of graded graphs in duality (G P , G P ⋆ ). The set of vertices of G P and G P ⋆ is the set of pairs of twin binary trees. There is an edge between the vertices J and J ′ in G P (resp. in G P ⋆ ) if P J ′ (resp. P ⋆ J ′ ) appears in the product P J • P (resp. in the product P ⋆ J • P ⋆ ). Figure 16 (resp. Figure 17) shows the graded graph G P (resp. G P ⋆ ) restricted to vertices of order smaller than 5. 6.3.3. A boolean basis. We shall call a basis of an algebra (resp. coalgebra) a boolean algebra basis (resp. boolean coalgebra basis) if each element of the basis (resp. tensor square of the basis) only occurs with coefficient 0 or 1 in any product (resp. coproduct) involving two (resp. one) elements of the basis. Proposition 6.4. If ≡ is an equivalence relation defined on A * satisfying the conditions of Theorem 6.1 and additionally, for all π, µ ∈ S, (6.29) σ, ν ∈ π ¢ µ and σ -1 ≡ ν -1 imply σ = ν, then, the family {P σ } σ∈S/≡ defined in (6.9) is both an algebra and a coalgebra boolean basis of the corresponding Hopf subalgebra of FQSym. Proof. It is immediate from the definition of the product of FQSym that {P σ } σ∈S/≡ is a boolean algebra basis, regardless of (6.29).

By duality, {P σ } σ∈S/≡ is a boolean coalgebra basis if and only if its dual basis {P ⋆ σ } σ∈S/≡ is a boolean algebra basis. One has

P ⋆ π • P ⋆ µ = φ F ⋆ π • F ⋆ µ (6.30) = φ ψ ψ -1 (F ⋆ π ) • ψ -1 F ⋆ µ (6.31) = φ ψ F π -1 • F µ -1 (6.32) = σ ∈ π -1 ¢ ν -1 φ (F ⋆ σ -1 ) , (6.33)
where φ is the canonical projection mapping F ⋆ σ on P ⋆ σ for any permutation σ, ψ is the Hopf isomorphism mapping F σ on F ⋆ σ -1 for any permutation σ, and π ∈ π and µ ∈ µ. One can easily see that if ≡ satisfies the hypothesis of the proposition, then there are no multiplicities in (6.33).

Law and Reading have proved in [START_REF] Law | The Hopf algebra of diagonal rectangulations[END_REF] that the basis of their Baxter Hopf algebra, analog to our basis {P J } J∈T BT , is both a boolean algebra basis and a boolean coalgebra basis. We re-prove this result in our setting: Proposition 6.5. The basis {P J } J∈T BT is both a boolean algebra basis and a boolean coalgebra basis of Baxter.

Proof. Let us prove that the sylvester equivalence relation satisfies the assumptions of Proposition 6.4. Indeed, the result directly follows from the fact that, by Proposition 3.7, the Baxter equivalence relation is finer than the sylvester equivalence relation.

Let us start with a useful result: Let x and y be two words without repetition of same length and u, v ∈ x ¢y (here, the letters of y are shifted by max(x)). Let us prove by induction on |x| + |y| that if decr(u) and decr(v) have same shape, then u = v. It is obvious if |x| + |y| = 0.

Otherwise, one has u = u ′ b u ′′ and v = v ′ b v ′′ where b := max(u) = max(v). Since the shape of the left subtree of decr(u) is equal to the shape of the left subtree of decr(v), the position of b in u and v is the same. Moreover, the word y is of the form y = y ′ a y ′′ where a := max(y), and x is of the form x = x ′ x ′′ , where u ′ , v ′ ∈ x ′ ¢ y ′ and u ′′ , v ′′ ∈ x ′′ ¢ y ′′ . Since the left (resp. right) subtree of decr(u) is equal to the left (resp. right) subtree of decr(v), by induction hypothesis, u ′ = v ′ and u ′′ = v ′′ , showing that u = v. Now, let π, µ ∈ S and σ = ν ∈ π ¢ µ and assume that σ -1 ≡ S ν -1 . Then, by Theorem 3.5, the permutations σ -1 and ν -1 give the same right binary search tree when inserted from right to left. By Lemma 4.7, that implies that decr(σ) and decr(ν) have same shape. That implies σ = ν, contradicting our hypothesis.

By duality, Proposition 6.5 also shows that the basis {P ⋆ J } J∈T BT is a boolean algebra and coalgebra basis. 6.3.4. A lattice interval description of the product. If ≡ is an equivalence relation of S and σ a permutation, denote by σ↑ (resp. σ↓) the minimal (resp. maximal) permutation of the ≡equivalence class of σ for the permutohedron order. Proposition 6.6. If ≡ is an equivalence relation defined on A * satisfying the conditions of Theorem 6.1 and additionally, the ≡-equivalence classes of permutations are intervals of the permutohedron, then the product on the family defined in (6.9) can be expressed as: (6.34) P σ • P ν = σ↑ ν↑ P π P σ↓ ν↓ π=min π P π .

Proof. It is well-known that the shifted shuffle product of two permutohedron intervals is still a permutohedron interval. Restating this fact in FQSym, we have (6.35)

  σ P µ P σ ′ F µ   •   ν P τ P ν ′ F τ   = σ ν P π P σ ′ ν ′ F π .
By (6.35) and since that every ≡-equivalence class is an interval of the permutohedron, we obtain (6.36)

P σ • P ν = σ↑ ν↑ P π P σ↓ ν↓ F π .
By Theorem 6.1, the expression (6.36) can be expressed as a sum of P π elements and the proposition follows.

Let J 0 := (T 0 L , T 0 R ) and J 1 := (T 1 L , T 1 R ) be two pairs of twin binary trees. Let us define the pair of twin binary trees J 0 J 1 by (6.37)

J 0 J 1 := (T 0 L T 1 L , T 0 R T 1 R ).
In the same way, the pair of twin binary trees J 0 J 1 is defined by

(6.38) J 0 J 1 := (T 0 L T 1 L , T 0 R T 1 R
). Proposition 6.6 leads to the following expression for the product of Baxter. Corollary 6.7. For all pairs of twin binary trees J 0 and J 1 , the product of Baxter satisfies (6.39)

P J0 • P J1 = J0 J1 B J B J0 J1 P J .
Proof. Let σ and ν two permutations. It is immediate, from the definition of the P-symbol algorithm, that the P-symbol of the permutation σ ν (resp. σ ν) is the pair of twin binary trees P(σ) P(ν) (resp. P(σ) P(ν)). The expression (6.39) follows from the fact that ≡ Bequivalence classes of permutations are intervals of the permutohedron (Proposition 3.8) and from Proposition 6.6. 6.3.5. Multiplicative bases and free generators. Recall that the elementary family {E σ } σ∈S and the homogeneous family {H σ } σ∈S of FQSym respectively defined by

E σ := σ P σ ′ F σ ′ , (6.40) H σ := σ ′ P σ F σ ′ , (6.41)
form multiplicative bases of FQSym (see [START_REF] Aguiar | Structure of the Malvenuto-Reutenauer Hopf algebra of permutations[END_REF][START_REF] Duchamp | Noncommutative symmetric functions VII: free quasi-symmetric functions revisited[END_REF] for an exposition of some known bases of FQSym). Indeed, for all σ, ν ∈ S, the product satisfies

E σ • E ν = E σ ν , (6.42) H σ • H ν = H σ ν . (6.43)
Mimicking these definitions, let us define the elementary family {E J } J∈T BT and the homogeneous family {H J } J∈T BT of Baxter respectively by

E J := J B J ′ P J ′ , (6.44) H J := J ′ B J P J ′ . (6.45)
These families are bases of Baxter since they are defined by triangularity. Proposition 6.8. Let J be a pair of twin binary trees and σ↑ (resp. σ↓) be the minimal (resp. maximal) permutation such that P(σ↑) = J (resp. P(σ↓) = J). Then, E J = E σ↑ , (6.46)

H J = H σ↓ . (6.47)
Proof. Using the fact that, by Theorem 5.1, the ≡ B -equivalence relation is a lattice congruence of the permutohedron, one successively has (6.48)

E J = J B J ′ P J ′ = J B J ′ ν ∈ S P(ν)=J ′ F ν = ν ∈ S J B P(ν) F ν = ν ∈ S σ↑ P ν F ν = E σ↑ .
The proof for the homogeneous family is analogous. Corollary 6.9. For all pairs of twin binary trees J 0 and J 1 , we have

E J0 • E J1 = E J0 J1 , (6.49) H J0 • H J1 = H J0 J1 . (6.50)
Proof. Let σ and ν be the minimal permutations of the ≡ B -equivalence classes respectively encoded by J 0 and J 1 . By Proposition 6.8, we have (6.51)

E J0 • E J1 = E σ • E ν = E σ ν .
The permutation σ ν is obviously the minimal element of its ≡ B -equivalence class, and, by the definition of the P-symbol algorithm, the P-symbol of σ ν is the pair of twin binary trees P(σ) P(ν) = J 0 J 1 . The proof of the second part of the proposition is analogous.

For example,

E • E = E , (6.52) H • H = H . ( 6
.53) Corollary 6.9 also shows that the {E J } J∈T BT and {H J } J∈T BT bases of Baxter are boolean algebra bases. However, these are not boolean coalgebra bases since one has (6.54)

∆ E = 1 ⊗ E + 2 E ⊗ E + E ⊗ 1, and
(6.55) ∆ H = 1 ⊗ H + 2 H ⊗ H + H ⊗ 1.
Let us say that a pair of twin binary trees J is connected (resp. anti-connected ) if all the permutations σ such that P(σ) = J are connected (resp. anti-connected). Since for any connected (resp. anti-connected) permutation σ and a permutation ν such that σ P ν (resp. ν P σ) the permutation ν is also connected (resp. anti-connected), it is enough to check if the minimal (resp. maximal) permutation of the ≡ B -equivalence class encoded by J is connected (resp. anti-connected) to decide if J is connected (resp. anti-connected). Lemma 6.10. For any pair of twin binary trees J, there exists a sequence of connected (resp. anti-connected) pairs of twin binary trees J 1 , . . . , J k such that (6.56)

J = J 1 • • • J k (resp. J = J 1 • • • J k ).
Proof. Let σ be the minimal permutation of the ≡ B -equivalence class encoded by J (recall that the existence of this element is ensured by Proposition 3.8). One can write σ as (6.57)

σ = σ (1) • • • σ (k) ,
where the permutations σ (i) are connected for all 1 i k. Since σ is the minimal permutation of its ≡ B -equivalence class, all the permutations σ (i) are also minimal of their ≡ B -equivalence classes. Hence, the pairs of twin binary trees P σ (i) are connected and we can write (6.58)

J = P σ (1) • • • P σ (k) .
The proof for the respective part is analogous.

Theorem 6.11. The algebra Baxter is free on the elements E J (resp. H J ) such that J is a connected (resp. anti-connected) pair of twin binary trees.

Proof. By Corollary 6.9 and Lemma 6.10, each element E J can be expressed as (6.59)

E J = E J1 • . . . • E J k ,
where the pairs of twin binary trees J i are connected for all 1 i k. Now, since for all permutations σ and ν one has E σ • E ν = E σ ν in FQSym, and since any permutation σ admits a unique expression (6.60)

σ = σ (1) • • • σ (k) ,
where σ (1) , . . . , σ (k) are connected permutations, there is no relation in FQSym between the elements E σ where σ is a connected permutation. Hence, by Proposition 6.8 and Corollary 6.9, there is also no relation in Baxter between the elements E J where J is a connected pair of twin binary trees. The proof for the respective part is analogous.

Let us denote by B C (z) the generating series of connected (resp. anti-connected) pairs of twin binary trees. It follows, from Theorem 6.11, that the Hilbert series B(z) of Baxter satisfies B(z) = 1/ (1 -B C (z)). Hence, the generating series B C (z) satisfies (6.61)

B C (z) = 1 - 1 B(z)
. Proposition 6.12. If σ is a connected (resp. anti-connected) Baxter permutation, then any permutation ν such that σ ≡ B ν is also connected (resp. anti-connected).

First dimensions of algebraic generators of

Proof. As any permutation, every Baxter permutation σ can be uniquely expressed as (6.67)

σ = σ (1) • • • σ (k) ,
where the permutations σ (i) are connected for all 1 i k. Moreover, since σ avoids the permutation patterns 2 -41 -3 and 3 -14 -2, the permutations σ (i) also does, and hence, the σ (i) are Baxter permutations. This shows that the generating series of connected Baxter permutations is B C (z) and thus, that connected Baxter permutations, connected pairs of twin binary trees, and connected minimal permutations of Baxter equivalence classes are equinumerous. The proposition follows from Theorem 4.14 saying that each ≡ B -equivalence class of permutations contains exactly one Baxter permutation. The proof for the respective part is analogous.

Corollary 6.13. The algebra Baxter is free on the elements E J (resp. H J ) where the Baxter permutation belonging to the ≡ B -equivalence class encoded by J is connected (resp. anticonnected).

6.3.6. Bidendriform bialgebra structure and self-duality. A Hopf algebra (H, •, ∆) can be fit into a bidendriform bialgebra structure [START_REF] Foissy | Bidendriform bialgebras, trees, and free quasi-symmetric functions[END_REF] if (H + , ≺, ≻) is a dendriform algebra [Lod01] and (H + , ∆ ≺ , ∆ ≻ ) a codendriform coalgebra, where H + is the augmentation ideal of H. The operators ≺, ≻, ∆ ≺ and ∆ ≻ have to fulfill some compatibility relations. In particular, for all x, y ∈ H + , the product • of H is retrieved by x • y = x ≺ y + x ≻ y and the coproduct ∆ of H is retrieved by ∆

(x) = 1 ⊗ x + ∆ ≺ (x) + ∆ ≻ (x) + x ⊗ 1. Recall that an element x ∈ H + is totally primitive if ∆ ≺ (x) = 0 = ∆ ≻ (x).
The Hopf algebra FQSym admits a bidendriform bialgebra structure [START_REF] Foissy | Bidendriform bialgebras, trees, and free quasi-symmetric functions[END_REF]. Indeed, for all σ, ν ∈ S n with n 1, set (6.68)

F σ ≺ F ν := π ∈ σ ¢ ν π |π| =σ |σ| F π , (6.69) F σ ≻ F ν := π ∈ σ ¢ ν π |π| =ν |ν| +|σ| F π , (6.70) ∆ ≺ (F σ ) := σ=uv max(u)=max(σ) F std(u) ⊗ F std(v) , (6.71) ∆ ≻ (F σ ) := σ=uv max(v)=max(σ) F std(u) ⊗ F std(v) .
Proposition 6.14. If ≡ is an equivalence relation defined on A * satisfying the conditions of Theorem 6.1 and additionally, for all u, v ∈ A * , the relation u ≡ v implies u |u| = v |v| , then, the family defined in (6.9) spans a bidendriform sub-bialgebra of FQSym that is free as an algebra, cofree as a coalgebra, self-dual, free as a dendriform algebra on its totally primitive elements, and the Lie algebra of its primitive elements is free.

Proof. It is enough to show that the operators ≺, ≻, ∆ ≺ and ∆ ≻ of FQSym are well-defined in the Hopf subalgebra H of FQSym spanned by the elements {P σ } σ∈S/≡ . In this way, H is endowed with a structure of bidendriform bialgebra and the results of Foissy [START_REF] Foissy | Bidendriform bialgebras, trees, and free quasi-symmetric functions[END_REF] imply the rest of the proposition.

Fix σ, ν ∈ S/ ≡ and an element F π appearing in the product P σ ≺ P ν . Hence, there is a permutation σ ∈ σ such that π |π| = σ |σ| . Let π ′ a permutation such that π ≡ π ′ . By Theorem 6.1, the element F π ′ appears in the product P σ • P ν , and hence, it also appears in P σ ≺ P ν or in P σ ≻ P ν . Assume by contradiction that F π ′ appears in P σ ≻ P ν . There are two permutations σ ′ ∈ σ and ν ′ ∈ ν such that π

′ |π ′ | = ν ′ |ν ′ | + |σ ′ |. That implies that π |π| = π ′ |π ′ |
and contradicts the fact that all permutations of a same ≡-equivalence class end with a same letter. Hence, the element F π ′ appears in P σ ≺ P ν , showing that the product ≺ is well-defined in H. Then so is ≻ since ≺ + ≻ is the whole product. Fix σ ∈ S/ ≡ and an element F ν ⊗ F π appearing in the coproduct ∆ ≺ (P σ ). Hence, there is a permutation σ ∈ σ such that σ = uv, ν = std(u), π = std(v) and the maximal letter of uv is in the factor u. Now, let ν ′ and π ′ be two permutations such that ν ≡ ν ′ , π ≡ π ′ . Let us show that the element F ν ′ ⊗ F π ′ also appears in ∆ ≺ (P σ ). For that, let u ′ be a permutation of u such that std(u ′ ) = ν ′ , and v ′ be a permutation of v such that std(v ′ ) = π ′ . Since ev(u ′ ) = ev(u), std(u ′ ) ≡ std(u), and ≡ is compatible with the destandardization process, one has u ≡ u ′ . For the same reason, v ≡ v ′ , and since ≡ is a congruence, one has uv ≡ u ′ v ′ . Finally, since the maximal letter of uv is in u, the maximal letter of u ′ v ′ is in u ′ , showing that the element F ν ′ ⊗ F π ′ appears in ∆ ≺ (P σ ). Thus, the coproduct ∆ ≺ is well-defined in H. The proof for the coproduct ∆ ≻ is analogous.

Corollary 6.15. The Hopf algebra Baxter is free as an algebra, cofree as a coalgebra, selfdual, free as a dendriform algebra on its totally primitive elements, and the Lie algebra of its primitive elements is free.

Proof. Since all words of a same ≡ B -equivalence class end with a same letter, ≡ B satisfies the premises of Proposition 6.14 and hence, Baxter satisfies all stated properties.

Considering the map θ ′ : PBT ֒→ FQSym that is the injection from PBT to FQSym and φ ′ : FQSym ⋆ ։ PBT ⋆ the surjection from FQSym ⋆ to PBT ⋆ , it is well-known (see [START_REF] Hivert | The Algebra of Binary Search Trees[END_REF]) that the map φ ′ • ψ • θ ′ induces an isomorphism between PBT and PBT ⋆ . Hence, since by Corollary 6.15, the Hopf algebras Baxter and Baxter ⋆ are isomorphic, it is natural to test if an analogous map is still an isomorphism between Baxter and Baxter ⋆ . However, denoting by θ : Baxter ֒→ FQSym the injection from Baxter to FQSym, the map φ • ψ • θ : Baxter → Baxter ⋆ is not an isomorphism. Indeed [START_REF] Aval | The product of trees in the Loday-Ronco algebra through Catalan alternative tableaux[END_REF] endowed PBT with a new associative product called the # product. The product of two elements of PBT of degrees n and m is an element of degree n + m -1. Aval, Novelli, and Thibon [START_REF] Aval | The # product in combinatorial Hopf algebras[END_REF] generalized the # product at the level of the associative algebra and showed that it is still well-defined in FQSym.

Let for all k

1 the linear maps d k : FQSym → FQSym defined for any permutation σ of S n by (6.82) d k (F σ ) := F std(σ1...σiσi+2...σn) if there is 1 i n -1 such that σ i = k and σ i+1 = k + 1, 0 otherwise. Now, for any permutations σ and ν, the #-product is defined in FQSym by (6.83)

F σ #F ν := d n (F σ • F ν ) ,
where n is the size of σ. Proof. This proof relies on the fact that, according to Proposition 4.10, the permutations of a Baxter equivalence class coincide with linear extensions of the posets △(T L ) and ▽(T R ).

We have two cases to consider whether the k +1-st (resp. k-th) node is a child of the k-th (resp. k+1-st) node in T L (resp. T R ). Case 1. If so, there is in the Baxter equivalence class represented by J some permutations with a factor k.(k+1). The map d k deletes letters k+1 in these permutations and standardizes them. The obtained permutations coincide with linear extensions of the posets △(T ′ L ) and ▽(T ′ R ). Case 2. If this is not the case, since the k-th and k + 1-st nodes of a binary tree are on a same path starting from the root, no permutation of the Baxter class represented by J has a factor k.(k+1). Hence, d k (P J ) = 0.

One has for example (6.85) d 3 P = P .

Proposition 6.16 shows in particular that the # product in well-defined in Baxter.

6.4. Connections with other Hopf subalgebras of FQSym.

6.4.1. Connection with the Hopf algebra PBT. We already recalled that the sylvester congruence leads to the construction of the Hopf subalgebra PBT [LR98] of FQSym, whose fundamental basis (6.86) {P T : T ∈ BT } is defined in accordance with (6.9) (see [START_REF] Hivert | An analogue of the plactic monoid for binary search trees[END_REF] and [START_REF] Hivert | The Algebra of Binary Search Trees[END_REF]). By Proposition 3.7, every ≡ S -equivalence class is a union of some ≡ B -equivalence classes. Hence, we have the following injective Hopf map:

(6.87) ρ : PBT ֒→ Baxter, satisfying (6.88) ρ (P T ) =

T ′ ∈ BT J:=(T ′ ,T ) ∈ T BT P J , for any binary tree T . For example, ρ P = P + P + P . (6.89) 6.4.2. Connection with the Hopf algebra DSym (3) . The congruence ≡ R (3) leads to the construction of the Hopf subalgebra DSym (3) of FQSym, whose fundamental basis (6.90)

P σ : σ ∈ S/ ≡ R (3)
is defined in accordance with (6.9) (see [START_REF] Novelli | Generalized descent patterns in permutations and associated Hopf algebras[END_REF]). By Proposition 3.10, every ≡ R (3) -equivalence class of permutations is a union of some ≡ B -equivalence classes. Hence, we have the following injective Hopf map:

Figure 1 .

 1 Figure 1. The right rotation of root y.

Figure 2 .

 2 Figure 2. The sequence (a, b,c, d, e, f, g, h) is the sequence of all nodes of this binary tree visited by the inorder traversal.

Figure 3 .

 3 Figure 3. The canopy of this binary tree is 0100101.

Figure 4 .

 4 Figure 4. A pair of twin binary trees.

Definition 3. 1 .

 1 The Baxter monoid is the quotient of the free monoid A * by the congruence ≡ B that is the reflexive and transitive closure of the Baxter adjacency relations ⇌ B and ⇋ B defined for u, v ∈ A * and a, b, c, d ∈ A by c u ad v b ⇌ B c u da v b where a b < c d, (3.1) b u da v c ⇋ B b u ad v c where a < b c < d. (3.2) For example, the ≡ B -equivalence class of 2415253 (see Figure 5) is (3.3) {2142553, 2145253, 2145523, 2412553, 2415253, 2415523, 2451253, 2451523, 2455123}.

Figure 5 .

 5 Figure 5. The Baxter equivalence class of the word u := 2415253 and of the permutation 2516374 = std(u). Edges represent Baxter adjacency relations.

3. 2 .

 2 Connection with the sylvester monoid. The sylvester monoid [HNT02, HNT05] is the quotient of the free monoid A * by the congruence ≡ S that is the reflexive and transitive closure of the sylvester adjacency relation ⇌ S defined for u ∈ A * and a, b, c ∈ A by (3.9) ac u b ⇌ S ca u b where a b < c. In the same way, let us define the #-sylvester monoid, the quotient of A * by the congruence ≡ S # that is the reflexive and transitive closure of the #-sylvester adjacency relation ⇌ S # defined for u ∈ A * and a, b, c ∈ A by (3.10) b u ac ⇌ S # b u ca where a < b c.

)

  If a b (resp. a < b): (a) Then, recursively leaf insert a into the left subtree of T . (b) Otherwise, recursively leaf insert a into the right subtree of T .

  Proposition 3.7. Let u, v ∈ A * . Then, u ≡ B v if and only if u ≡ S v and u ≡ S # v.Proof. (⇒): Once more, it is enough to check the property on adjacency relations. Moreover, by Proposition 3.2, it is enough to check the property for permutations. Let σ, ν ∈ S n and assume that σ ⇄ B ν. We have σ = x b y ad z b ′ t and ν = x b y da z b ′ t for some letters a < b, b ′ < d and words x, y, z, and t. The presence of the letters a, d and b ′ with a < b ′ < d ensures that σ ⇌ S ν. Besides, the presence of the letters b, a and d with a < b < d ensures that σ ⇌ S # ν.

3. 3 .

 3 Connection with the 3-recoil monoid. If a and c are two letters of A, denote by ca the cardinality of the set {b ∈ A : a < b c}. In [NRT11], Novelli, Reutenauer and Thibon defined for any k 0 the congruence ≡ R (k) . This congruence is the reflexive and transitive closure of the k-recoil adjacency relation, defined for a, b ∈ A by (3.11) ab ⇌ R (k) ba where ba k.

  to check this property on adjacency relations. Hence, assume that σ ⇄ B ν. We have σ = x b y ad zb ′ t and ν = x b y da z b ′ t for some letters a < b, b ′ < d and words x, y, z, and t. Since σ and ν are permutations, b = b ′ and thus, we have a < b < b

  v) ∧ b decr(w) where u = vbw, b = max(u), and b > max(w). Definition 4.2. The Baxter Q-symbol (or simply Q-symbol if the context is clear) of a word u ∈ A * is the pair Q(u) = (S L , S T ) where (4.3) S L := incr std(u) -1 and S R := decr std(u) -1 .

Figure 6 .

 6 Figure 6. The P-symbol and the Q-symbol of u := 2415253.

Figure 7 Figure 7 .

 77 Figure 7 shows an example of application of Proposition 4.4.

  To illustrate Proposition 4.10, consider the following labeled pair of twin binary search trees, (T L , T R ) := words that are linear extensions of △(T L ) and ▽(T R ) are (the highlighted permutation is a Baxter permutation) {5214376, 5214736, 5217436, 5241376, 5241736, 5247136, 5271436, 5274136, 5721436, 5724136}, (4.6) which is exactly the Baxter equivalence class encoded by (T L , T R ).

  .2. Extracting Baxter permutations. The following algorithm allows, given an A-labeled pair of twin binary search trees (T L , T R ), to compute a word belonging to the ≡ B -equivalence class encoded by (T L , T R ). When (T L , T R ) is labeled by a permutation, our algorithm coincides with the algorithm designed by Dulucq and Guibert to describe a bijection between pairs of twin binary trees and Baxter permutations[START_REF] Dulucq | Mots de piles, tableaux standards et permutations de Baxter[END_REF]. Besides, since their algorithm always computes a Baxter permutation, our algorithm also returns a Baxter permutation when (T L , T R ) is labeled by a permutation.Algorithm: ExtractBaxter.Input: An A-labeled pair of twin binary search trees (T L , T R ). Output: A word belonging to the Baxter equivalence class encoded by (T L , T R ).(1) Let u := ǫ be the empty word.(2) While T L =⊥ and T R =⊥: (a) Let a be the label of the root of T L . (b) Let i be the index of root of T L . (c) Set u := ua. (d) Let A (resp. B) be the left (resp. right) subtree of T L . (e) If the i-th node of T R is a left child in T R : (i) Then, set T L := A B. (ii) Otherwise, set T L := A B. (f) Suppress the i-th node in T R .

Figure 8 .

 8 Figure 8. An execution of the algorithm ExtractBaxter on (T L , T R ). The computed Baxter permutation is 562134.

(Figure 9 .

 9 Figure 9. An execution of the algorithm ExtractMin on (T L , T R ). The computed permutation is 521364 and it is minimal in its ≡ B -equivalence class.

Figure 10 .

 10 Figure 10. A right binary search tree T , T 2 and T >2 .

Figure 11

 11 Figure11shows, step by step, the computation of the iterative Baxter P and Q-symbols of a word. 4.4.3. Correctness of the iterative insertion algorithm. To show that the iterative version of the Baxter P-symbol computes the same labeled pair of twin binary trees than its non-iterative version, we need the following lemma.Lemma 4.18. Let u ∈ A * . Let T be the right binary search tree obtained by root insertions of the letters of u, from left to right. Let T ′ be the right binary search tree obtained by leaf insertions of the letters of u, from right to left. Then, T = T ′ .Proof. Let us proceed by induction on |u|. If u = ǫ, the lemma is satisfied. Otherwise, assume that u = va where a ∈ A. Let S be the right binary search tree obtained by root insertions of the letters of v from left to right. By induction hypothesis, S also is the right binary tree obtained by leaf insertions of the letters of v from right to left. The right binary search tree T obtained by root insertions of u from left to right satisfies, by definition, T = S a ∧ a S >a . The right binary search tree T ′ obtained by leaf insertions of u from right to left satisfies T ′ = L ′ ∧ a R ′ where the subtree L ′ only depends on the subword v a := v |]-∞,a] and the subtree R ′ only depends on the subword v >a := v |]a,+∞[ , so that, by induction hypothesis, L ′ = S a , R ′ = S >a and thus, T = T ′ . Proposition 4.19. For any u ∈ A * , the Baxter P-symbol of u and the iterative Baxter P-symbol of u are equal.Proof. Let (T L , T R ) be the P-symbol of u and (T ′ L , T ′ R ) be the iterative P-symbol of u. By definition of these two insertion algorithms, we have T L = T ′ L . Moreover, T R is obtained by leaf insertions of the letters of u from right to left and T ′ R is obtained by root insertions of the letters of u from left to right. By Lemma 4.18, we have T R = T ′ R .

Figure 11 .

 11 Figure 11. Steps of the computation of the P-symbol and the Q-symbol of u := 2415253.

(

  L1) Every ≡-equivalence class is an interval of L; (L2) For any x, y ∈ L, if x y then x↓ y↓ where x↓ is the maximal element of the ≡-equivalence class of x; (L3) For any x, y ∈ L, if x y then x↑ y↑ where x↑ is the minimal element of the ≡-equivalence class of x.

5. 3 .Figure 12 .

 312 Figure 12. The permutohedron of order 4 cut into Baxter equivalence classes.

Figure 14 Figure 14 .

 1414 Figure 14 shows an example of a pair of twin binary trees with the corresponding twin Tamari diagram.

  Construction of Hopf subalgebras of FQSym. If ≡ is an equivalence relation on S and σ ∈ S, let us denote by σ the ≡-equivalence class of σ.

Figure 16 .

 16 Figure16. The graded graph G P restricted to vertices of order smaller than 5.

Figure 17 .

 17 Figure17. The graded graph G P ⋆ restricted to vertices of order smaller than 5.

Proposition 6. 16 .

 16 The linear maps d k are well-defined in Baxter. More precisely, one has for any pair of twin binary trees J := (T 0 , T 1 ), (6.84)d k (P J ) =    P J ′ if the k+1-st (resp. k-th) node is a child of the k-th (resp. k+1-st) node in T L (resp. T R ), 0 otherwise,whereJ ′ := (T ′ L , T ′ R )is the pair of twin binary trees obtained by contracting in T L and T R the edges connecting the k-th and the k+1-st nodes.

( 6 FQSymFigure 18 .

 618 Figure 18. Diagram of injective Hopf maps between some Hopf algebras related to Baxter. Arrows are injective Hopf maps.

  The shifted shuffle product ¢ of two permutations is defined by

	(2.5)
	For example,
	(2.6)	12 ¢ 21 = 12 ¡ 43 = 1243 + 1423 + 1432 + 4123 + 4132 + 4312.

σ ¢ ν := σ ¡ ν 1 +|σ| . . . ν |ν| +|σ| .

  Compatibility with the restriction of alphabet intervals. A monoid A * / ≡ is compatible with the restriction of alphabet intervals if for any interval I of A and for all u, v ∈ A * , u ≡ v implies u |I ≡ v |I . ∈ S n such that σ ⇄ B ν. We have σ = x b y ad z b ′ t and ν = x b y da z b ′ t for some letters a < b, b ′ < d and words x, y, z, and t. Let I be an interval of {1, . . . , n} and R := I ∩ {a, b, b ′ , d}. If R = {a, b, b ′ , d}, |I = x |I b y |I ad z |I b ′ t |I and ν |I = x |I b y |I da z |I b ′ t |I so that σ |I ⇄ B ν |I . Otherwise, we have σ |I = ν |I and thus σ |I ≡ B ν |I . 3.1.3. Compatibility with the Schützenberger involution. A monoid A * / ≡ is compatible with the Schützenberger involution if for all u

	3.1.2. Proposition 3.3. The Baxter monoid is compatible with the restriction of alphabet intervals.
	Proof. It is enough to check the property on adjacency relations. Moreover, by Proposition 3.2,
	it is enough to check the property for permutations. Let σ, ν (3.7) σ

  • P J1 = Properties of the Hopf algebra Baxter.

	For example,
	P	• P	= P	+ P	+ P
	(6.16)		+ P	+ P	+ P	.
	In the same way, we deduce the coproduct of Baxter from the coproduct of FQSym and
	by Theorem 4.14, we obtain
	(6.17)	∆ (P J ) =		P P(σ) ⊗ P P(ν) .
				uv ∈ S
				P(uv)=J
			σ:=std(u), ν:=std(v) ∈ S B
	For example,
	(6.18)
	∆ P	= 1 ⊗ P	+ P ⊗ P	+ P ⊗ P	+ P	⊗ P
		+ P	⊗ P	+ P	⊗ P + P	⊗ P + P	⊗ 1.
	6.3.
					P P(π) .
				P(σ)=J0, P(ν)=J1 π ∈ σ ¢ ν ∩ S B

  φ • ψ • θ P = φ • ψ (F 2143 + F 2413 ) = φ (F ⋆ 2143 + F ⋆ 3142 ) = P ⋆ + P ⋆ , (6.72) φ • ψ • θ P = φ • ψ (F 3142 + F 3412 ) = φ (F ⋆ 2413 + F ⋆ 3412 ) = P ⋆ + P ⋆ ,(6.73)showing that φ • ψ • θ is not injective.6.3.7. Primitive and totally primitive elements. Since the family {E J } J∈C (resp. {H J } J∈C ), where C is the set of connected (resp. anti-connected) pairs of twin binary trees are indecomposable elements of Baxter, its dual family {E ⋆ J } J∈C (resp. {H ⋆ J } J∈C ) forms a basis of the Lie algebra of the primitive elements of Baxter ⋆ . By Corollary 6.15, this Lie algebra is free.Following[START_REF] Foissy | Bidendriform bialgebras, trees, and free quasi-symmetric functions[END_REF], the generating series B T (z) of the totally primitive elements of Baxter is (6.74)B T (z) = B(z) -1 B(z) 2 . First dimensionsof totally primitive elements of Baxter are (6.75) 0, 1, 0, 1, 4, 19, 96, 511, 2832, 16215, 95374, 573837.Here follows a basis of the totally primitive elements of Baxter of order 1, 3 and 4: Compatibility with the # product. Aval and Viennot

	(6.76)	t 1,1 = P ,
	(6.77)	t 3,1 = P	-P	,
	(6.78)	t 4,1 = P	+ P	+ P	+ P
		-P	-P	-P	,
	(6.79)	t 4,2 = P	-P	,
	(6.80)	t 4,3 = P	-P	,
	(6.81)	t 4,4 = P	-P	.
	6.3.8.