Grégory Chatel
email: gregory.chatel@univ-paris-est.fr

G R Égory

Vincent Pilaud
email: vincent.pilaud@lix.polytechnique.fr

CAMBRIAN HOPF ALGEBRAS

Keywords:

The background of this paper is the fascinating interplay between the combinatorial, geometric and algebraic structures of permutations, binary trees and binary sequences (see Table 1):

Combinatorially, the descent map from permutations to binary sequences factors via binary trees through the BST insertion and the canopy map. These maps define lattice homomorphisms from the weak order via the Tamari lattice to the boolean lattice.

Geometrically, the permutahedron is contained in Loday's associahedron [START_REF] Loday | Realization of the Stasheff polytope[END_REF] which is in turn contained in the parallelepiped generated by the simple roots. These polytopes are just obtained by deleting inequalities from the facet description of the permutahedron. See Figure 1.

Algebraically, these maps translate to Hopf algebra inclusions from M. Malvenuto and C. Reutenauer's algebra on permutations [START_REF] Malvenuto | Duality between quasi-symmetric functions and the Solomon descent algebra[END_REF] associahedron [START_REF] Loday | Realization of the Stasheff polytope[END_REF] generated by e i+1 -e i Algebra Malvenuto-Reutenauer Loday-Ronco descent Hopf algebra [START_REF] Malvenuto | Duality between quasi-symmetric functions and the Solomon descent algebra[END_REF] Hopf algebra [START_REF] Loday | Hopf algebra of the planar binary trees[END_REF] Hopf algebra [GKL + 95] Table 1. Related combinatorial, geometric and algebraic structures. These structures and their connections have been partially extended in several directions in particular to the Cambrian lattices of N. Reading [START_REF] Reading | Cambrian lattices[END_REF][START_REF] Reading | Cambrian fans[END_REF] and their polytopal realizations by C. Hohlweg, C. Lange, and H. Thomas [START_REF] Hohlweg | Realizations of the associahedron and cyclohedron[END_REF][START_REF] Hohlweg | Permutahedra and generalized associahedra[END_REF], to the graph associahedra of M. Carr and S. Devadoss [START_REF] Michael | Coxeter complexes and graph-associahedra[END_REF][START_REF] Satyan | A realization of graph associahedra[END_REF], the nested complexes and their realizations as generalized associahedra by A. Postnikov [START_REF] Postnikov | Permutohedra, associahedra, and beyond[END_REF] (see also [START_REF] Postnikov | Faces of generalized permutohedra[END_REF][START_REF] Eva | Matroid polytopes, nested sets and Bergman fans[END_REF][START_REF] Zelevinsky | Nested complexes and their polyhedral realizations[END_REF]), or to the m-Tamari lattices of F. Bergeron and L.-F. Préville-Ratelle [START_REF] Bergeron | Higher trivariate diagonal harmonics via generalized Tamari posets[END_REF] (see also [START_REF] Bousquet-Mélou | The number of intervals in the m-Tamari lattices[END_REF][START_REF] Bousquet-Mélou | The representation of the symmetric group on m-Tamari intervals[END_REF]) and the Hopf algebras on these m-structures recently constructed by J.-C. Novelli and J.-Y. Thibon [START_REF] Novelli | Hopf algebras of m-permutations, (m + 1)-ary trees, and m-parking functions[END_REF][START_REF] Novelli | m-dendriform algebras[END_REF].

This paper explores combinatorial and algebraic aspects of Hopf algebras related to the type A Cambrian lattices. N. Reading provides in [START_REF] Reading | Cambrian lattices[END_REF] a procedure to map a signed permutation of S n into a triangulation of a certain convex (n + 3)-gon. The dual trees of these triangulations naturally extend rooted binary trees and were introduced and studied as "spines" [START_REF] Lange | Associahedra via spines[END_REF] or "mixed cobinary trees" [START_REF] Igusa | Mixed cobinary trees[END_REF]. We prefer here the term "Cambrian trees" in reference to N. Reading's work. The map ct from signed permutations to Cambrian trees is known to encode combinatorial and geometric properties of the Cambrian structures: the Cambrian lattice is the quotient of the weak order under the fibers of ct, each maximal cone of the Cambrian fan is the incidence cone of a Cambrian tree T and is refined by the braid cones of the permutations in the fiber ct -1 (T), etc.

In this paper, we use this map ct for algebraic purposes. In the first part, we introduce the Cambrian Hopf algebra Camb as a subalgebra of the Hopf algebra FQSym ± on signed permutations, and the dual Cambrian algebra Camb * as a quotient algebra of the dual Hopf algebra FQSym * ± . Their bases are indexed by all Cambrian trees. Our approach extends that of F. Hivert, J.-C. Novelli and J.-Y. Thibon [START_REF] Hivert | The algebra of binary search trees[END_REF] to construct J.-L. Loday and M. Ronco's Hopf algebra on binary trees [START_REF] Loday | Hopf algebra of the planar binary trees[END_REF] as a subalgebra of C. Malvenuto and C. Reutenauer's Hopf algebra on permutations [START_REF] Malvenuto | Duality between quasi-symmetric functions and the Solomon descent algebra[END_REF]. We also use this map ct to describe both the product and coproduct in the algebras Camb and Camb * in terms of simple combinatorial operations on Cambrian trees.

In the second part of this paper, we study Baxter-Cambrian structures, extending in the Cambrian setting the constructions of S. Law and N. Reading on rectangulations [START_REF] Law | The Hopf algebra of diagonal rectangulations[END_REF] and that of S. Giraudo on twin binary trees [START_REF] Giraudo | Algebraic and combinatorial structures on pairs of twin binary trees[END_REF]. We define Baxter-Cambrian lattices as quotients of the weak order under the intersections of two opposite Cambrian congruences. Their elements can be labeled by pairs of twin Cambrian trees, i.e. Cambrian trees with opposite signatures whose union forms an acyclic graph. We study in detail the number of such pairs of Cambrian trees for arbitrary signatures. Following [START_REF] Law | The Hopf algebra of diagonal rectangulations[END_REF], we also observe that the Minkowski sums of opposite associahedra of C. Hohlweg and C. Lange [START_REF] Hohlweg | Realizations of the associahedron and cyclohedron[END_REF] provide polytopal realizations of the Baxter-Cambrian lattices. Finally, we introduce the Baxter-Cambrian Hopf algebra BaxCamb as a subalgebra of the Hopf algebra FQSym ± on signed permutations and its dual BaxCamb * as a quotient algebra of the dual Hopf algebra FQSym * ± . Their bases are indexed by pairs of twin Cambrian trees, and it is also possible to describe both the product and coproduct in the algebras BaxCamb and BaxCamb * in terms of simple combinatorial operations on Cambrian trees.

Finally, the ideas of this paper can be extended further to construct Hopf algebras on tuples of Cambrian trees (generalizing the pairs of twin Cambrian trees), and on Schröder-Cambrian trees (corresponding to all faces of all C. Hohlweg and C. Lange's associahedra [START_REF] Hohlweg | Realizations of the associahedron and cyclohedron[END_REF]). We skip these constructions to keep this version short, but the interested reader can find details in [START_REF] Chatel | Cambrian Hopf Algebras[END_REF].

Part 1. The Cambrian Hopf Algebra

Cambrian trees

In this section, we recall the definition and properties of "Cambrian trees", generalizing standard binary search trees. They were introduced independently by K. Igusa and J. Ostroff in [START_REF] Igusa | Mixed cobinary trees[END_REF] as "mixed cobinary trees" in the context of cluster algebras and quiver representation theory and by C. Lange and V. Pilaud in [START_REF] Lange | Associahedra via spines[END_REF] as "spines" (i.e. oriented and labeled dual trees) of triangulations of polygons to revisit the multiple realizations of the associahedron of C. Hohlweg and C. Lange [START_REF] Hohlweg | Realizations of the associahedron and cyclohedron[END_REF]. Here, we use the term "Cambrian trees" to underline their connection with the type A Cambrian lattices of N. Reading [START_REF] Reading | Cambrian lattices[END_REF].

1.1.1. Cambrian trees. Consider a directed tree T and a vertex v of T. We call children (resp. parents) of v the sources of the incoming arcs (resp. the targets of the outgoing arcs) at v and descendant (resp. ancestor) subtrees of v the subtrees attached to them. We focus on the following trees, which generalize standard binary search trees, see Figure 2 Remark 2 (Spines of triangulations). Cambrian trees can be seen as spines (i.e. oriented and labeled dual trees) of triangulations of labeled polygons. More precisely, consider an (n+2)-gon P ε with vertices labeled by 0, . . . , n + 1 from left to right, and where vertex i is located above the diagonal [0, n + 1] if ε i = + and below it if ε i = -. We associate with a triangulation σ of P ε its dual tree having a node labeled by j for each triangle ijk of σ where i < j < k, and an edge between any two adjacent triangles oriented from the triangle below to the triangle above their common diagonal. See Figure 2 and refer to [START_REF] Lange | Associahedra via spines[END_REF] for details. Throughout the paper, we denote by T * the triangulation of P ε dual to the ε-Cambrian tree T, and we use this interpretation to provide the reader with some geometric intuition of definitions and results of this paper. The first consequence of this geometric interpretation concerns the enumeration of Cambrian trees. A signed permutation is a permutation table where each dot receives a + or -sign, see Figure 3 (top left). We could also think of a permutation where the positions or the values receive a sign, but it will be useful later to switch the signature from positions to values. The p-signature (resp. v-signature) of a signed permutation τ is the sequence ε p (τ ) (resp. ε v (τ )) of signs of τ ordered by positions from bottom to top (resp. by values from left to right). For a signature ε ∈ ± n , we denote by S ε (resp. by S ε ) the set of signed permutations τ with p-signature ε p (τ ) = ε (resp. with v-signature ε v (τ ) = ε). Finally, we denote the set of all signed permutations by In concrete examples, we underline negative positions/values while we overline positive positions/values: for example, we write 2751346 for the signed permutation represented on the top left corner of Figure 3, where τ = [2, 7, 5, 1, 3, 4, 6], ε p = -+--+-+ and ε v = --+--++.

S ± := n∈N ε∈± n S ε = n∈N ε∈± n S ε .
Following [START_REF] Lange | Associahedra via spines[END_REF], we now present an algorithm to construct an ε-Cambrian tree ct(τ ) from a signed permutation τ ∈ S ε . Figure 3 illustrates this algorithm on the permutation 2751346. As a preprocessing, we represent the table of τ (with signed dots in positions (τ (i), i) for i ∈ [n]) and draw a vertical wall below the negative vertices and above the positive vertices. We then sweep the table from bottom to top (thus reading the permutation τ from left to right) as follows. The procedure starts with an incoming strand between any two consecutive negative values. A negative dot connects the two strands immediately to its left and immediately to its right to form a unique outgoing strand. A positive dot ⊕ separates the only visible strand (not hidden by a wall) into two outgoing strands. The procedure finishes with an outgoing strand between any two consecutive positive values. See Figure 3. We denote by ct(τ ) the resulting oriented graph.

Proposition 4 ([LP13]

). The map ct is a surjection from the signed permutations S ε to the Cambrian trees Camb(ε). The fiber ct -1 (T) := {τ ∈ S ε | ct(τ ) = T} of a Cambrian tree T ∈ Camb(ε) is its set L(T) of linear extensions.

Remark 5 (Cambrian correspondence on triangulations). The map ct was previously described on the triangulations of the polygon P ε in [START_REF] Reading | Cambrian lattices[END_REF] (see also the references therein). Namely, the triangulation ct(τ ) * is the union of the paths π 0 , . . . , π n where π i is the path between vertices 0 and n + 1 of P ε passing through the vertices in the symmetric difference ε -1 (-) τ ([i]).

1.1.3. Cambrian congruence. Following the sylvester congruence in [START_REF] Hivert | The algebra of binary search trees[END_REF], we now characterize by a congruence relation the signed permutations τ ∈ S ε which have the same image ct(τ ). This Cambrian congruence goes back to the original definition of N. Reading [START_REF] Reading | Cambrian lattices[END_REF].

Definition 6 ([Rea06]

). For a signature ε ∈ ± n , the ε-Cambrian congruence is the equivalence relation on S ε defined as the transitive closure of the rewriting rules

U acV bW ≡ ε U caV bW if a < b < c and ε b = -, U bV acW ≡ ε U bV caW if a < b < c and ε b = +,
where a, b, c are elements of [n] while U, V, W are words on [n]. The Cambrian congruence is the equivalence relation on all signed permutations S ± given by all ε-Cambrian congruences:

for τ ∈ S ε , τ ∈ S ε τ ≡ τ ⇐⇒ ε = ε and τ ≡ ε τ .
We now focus on the equivalence classes of the Cambrian congruence.

Proposition 7. The ε-Cambrian congruence classes are precisely the fibers of the map ct:

for τ, τ ∈ S ε τ ≡ ε τ ⇐⇒ ct(τ ) = ct(τ ).
Proof. It boils down to observe that two consecutive vertices a, c in a linear extension τ of a ε-Cambrian tree T can be switched while preserving a linear extension τ of T precisely when they belong to distinct subtrees of a vertex b of T. It follows that the vertices a, c lie on either sides of b so that we have a < b < c. If ε b = -, then a, c appear before b and τ = U acV bW can be switched to τ = U caV bW , while if ε b = +, then a, c appear after b and τ = U bV acW can be switched to τ = U bV caW .

Remember that the (right) weak order on S ε is defined as the inclusion order of (right) inversions, where a (right) inversion of τ ∈ S ε is a pair of values i < j such that τ -1 (i) > τ -1 (j). In this definition, the signs on τ do not matter (they are seen as decorations, not as actual signs that would change the order on the values). In this paper, we always work with the right weak order, that we simply call weak order for brevity. The following statement is due to N. Reading [START_REF] Reading | Cambrian lattices[END_REF].

Proposition 8 ( [START_REF] Reading | Cambrian lattices[END_REF]). All ε-Cambrian classes are intervals of the weak order on S ε , whose minimal (resp. maximal) elements avoid the patterns b-ca and ca-b (resp. b-ac and ac-b).

1.1.4. Rotations and Cambrian lattices. We now present rotations in Cambrian trees, a local operation which transforms a ε-Cambrian tree into another ε-Cambrian tree where a single oriented cut differs (see Proposition 10).

Definition 9. Let i → j be an edge in a Cambrian tree T, with i < j. Let L denote the left subtree of i and B denote the remaining incoming subtree of i, and similarly, let R denote the right subtree of j and A denote the remaining outgoing subtree of j. Let T be the oriented tree obtained from T just reversing the orientation of i → j and attaching the subtrees L and A to i and the subtrees B and R to j. The transformation from T to T is called rotation of the edge i → j. See Figure 4.

rotation of i → j T -----→ T i j L B R A i j L B R A B L A i j L B A R i j R B j R B i j L A R i L A B i L i j B R L A j R A Figure 4
. Rotations in Cambrian trees: the tree T (top) is transformed into the tree T (bottom) by rotation of the edge i → j. The four cases correspond to the possible signs of i and j.

The following proposition states that rotations are compatible with Cambrian trees and their edge cuts. An edge cut in a Cambrian tree T is the ordered partition (X Y ) of the vertices of T into the set X of vertices in the source set and the set Y of vertices in the target set of an oriented edge of T.

Proposition 10 ([LP13]

). The result T of the rotation of an edge i → j in a ε-Cambrian tree T is a ε-Cambrian tree. Moreover, T is the unique ε-Cambrian tree with the same edge cuts as T, except the cut defined by the edge i → j.

Remark 11 (Rotations and flips). Rotating an edge e in a ε-Cambrian tree T corresponds to flipping the dual diagonal e * of the dual triangulation T * of the polygon P ε . See [START_REF] Lange | Associahedra via spines[END_REF]Lemma 13].

Define the increasing rotation graph on Camb(ε) to be the graph whose vertices are the ε-Cambrian trees and whose arcs are increasing rotations T → T , i.e. where the edge i → j in T is reversed to the edge i ← j in T for i < j. See Figure 5 for an illustration. The following statement, adapted from N. Reading's work [START_REF] Reading | Cambrian lattices[END_REF], asserts that this graph is acyclic, that its transitive closure defines a lattice, and that this lattice is closely related to the weak order.

Proposition 12 [START_REF] Reading | Cambrian lattices[END_REF]). The transitive closure of the increasing rotation graph on Camb(ε) is a lattice, called ε-Cambrian lattice. The map ct : S ε → Camb(ε) defines a lattice homomorphism from the weak order on S ε to the ε-Cambrian lattice on Camb(ε).

Example 13. When ε = (-) n , the Cambrian lattice is the classical Tamari lattice [START_REF]Associahedra, Tamari Lattices and Related Structures[END_REF]. It can be defined equivalently by left-to-right rotations in planar binary trees, by slope increasing flips in triangulations of P (-) n , or as the quotient of the weak order by the sylvester congruence.

1.1.5. Canopy. The canopy of a binary tree was already used by J.-L. Loday in [START_REF] Loday | Hopf algebra of the planar binary trees[END_REF][START_REF] Loday | Realization of the Stasheff polytope[END_REF] but the name was coined by X. Viennot [START_REF] Viennot | Catalan tableaux and the asymmetric exclusion process[END_REF]. It was then extended to Cambrian trees (or spines) in [START_REF] Lange | Associahedra via spines[END_REF] to define a surjection from the associahedron Asso(ε) to the parallelepiped Para(n) generated by the simple roots. The main observation is that the vertices i and i + 1 are always comparable in a Cambrian tree (otherwise, they would be in distinct subtrees of a vertex j which should then lie between i and i + 1). Definition 14. The canopy of a Cambrian tree T is the sequence can(T)

∈ ± n-1 defined by can(T) i = -if i is above i + 1 in T and can(T) i = + if i is below i + 1 in T.
For example, the canopy of the Cambrian tree of Figure 2 (left) is -++-+-. The canopy of T behaves nicely with the linear extensions of T and with the Cambrian lattice. To state this, we define for a permutation τ ∈ S ε the sequence rec(τ ) ∈ ± n-1 , where rec(T) i =if τ -1 (i) > τ -1 (i + 1) and rec(T) i = + otherwise. In other words, rec(τ ) records the recoils of the permutation τ , i.e. the descents of the inverse permutation of τ .

Proposition 15. The maps ct, can, and rec define the following commutative diagram of lattice homomorphisms:

S ε ± n-1 Camb(ε) rec ct can
1.1.6. Geometric realizations. We close this section with geometric interpretations of the Cambrian trees, Cambrian classes, Cambrian correspondence, and Cambrian lattices. We denote by e 1 , . . . , e n the canonical basis of R n and by H the hyperplane of R n orthogonal to e i . Define the incidence cone C(T) and the braid cone C (T) of a directed tree T as C(T) := cone {e i -e j | for all i → j in T} and C (T

) := {x ∈ H | x i ≤ x j for all i → j in T} .
These two cones lie in the space H and are polar to each other. For a permutation τ ∈ S n , we denote by C(τ ) and C (τ ) the incidence and braid cone of the chain τ (1) → • • • → τ (n). Finally, for a sign vector χ ∈ ± n-1 , we denote by C(χ) and C (χ) the incidence and braid cone of the oriented path 1

-• • • -n, where i → i + 1 if χ i = + and i ← i + 1 if χ i = -.
These cones (together with all their faces) form complete simplicial fans in H: (i) the cones C (τ ), for all permutations τ ∈ S n , form the braid fan, which is the normal fan of the permutahedron Perm(n

) := conv i∈[n] τ (i)e i | τ ∈ S n ; (ii) the cones C (T)
, for all ε-Cambrian trees T, form the ε-Cambrian fan, which is the normal fan of the ε-associahedron Asso(ε) of C. Hohlweg and C. Lange [START_REF] Hohlweg | Realizations of the associahedron and cyclohedron[END_REF] (see also [START_REF] Lange | Associahedra via spines[END_REF]); (iii) the cones C (χ), for all sign vectors χ ∈ ± n-1 , form the boolean fan, which is the normal fan of the parallelepiped Para(n

) := x ∈ H | i(2n + 1 -i) ≤ 2 j≤i x j ≤ i(i + 1) for all i ∈ [n] .
In fact, Asso(ε) is obtained by deleting certain inequalities in the facet description of Perm(n), and similarly, Para(n) is obtained by deleting facets of Asso(ε). In particular, we have the geometric inclusions Perm(n) ⊂ Asso(ε) ⊂ Para(n). See Figure 6 for 3-dimensional examples. -----+----+--++-Figure 6. The polytope inclusion Perm(4) ⊂ Asso(ε) ⊂ Para(4) for different signatures ε ∈ ± 4 . The permutahedron Perm(4) is represented in red, the associahedron Asso(ε) in blue, and the parallelepiped Para(4) in green.

The incidence and braid cones also characterize the maps ct, can, and rec as follows

T = ct(τ ) ⇐⇒ C(T) ⊆ C(τ ) ⇐⇒ C (T) ⊇ C (τ ), χ = can(T) ⇐⇒ C(χ) ⊆ C(T) ⇐⇒ C (χ) ⊇ C (T), χ = rec(τ ) ⇐⇒ C(χ) ⊆ C(τ ) ⇐⇒ C (χ) ⊇ C (τ ).
In particular, Cambrian classes are formed by all permutations whose braid cone belong to the same Cambrian cone. Finally, the 1-skeleta of the permutahedron Perm(n), associahedron Asso(ε) and parallelepiped Para(n), oriented in the direction (n, . . . , 1)

-(1, . . . , n) = i∈[n] (n + 1 -2i) e i
are the Hasse diagrams of the weak order, the Cambrian lattice and the boolean lattice respectively. These geometric properties originally motivated the definition of Cambrian trees in [START_REF] Lange | Associahedra via spines[END_REF].

Cambrian Hopf Algebra

In this section, we introduce the Cambrian Hopf algebra Camb as a subalgebra of the Hopf algebra FQSym ± on signed permutations, and the dual Cambrian algebra Camb * as a quotient algebra of the dual Hopf algebra FQSym * ± . We describe both the product and coproduct in these algebras in terms of combinatorial operations on Cambrian trees. These results extend the approach of F. Hivert, J.-C. Novelli and J.-Y. Thibon [START_REF] Hivert | The algebra of binary search trees[END_REF] to construct the algebra of J.-L. Loday and M. Ronco on binary trees [START_REF] Loday | Hopf algebra of the planar binary trees[END_REF] as a subalgebra of the algebra of C. Malvenuto and C. Reutenauer on permutations [START_REF] Malvenuto | Duality between quasi-symmetric functions and the Solomon descent algebra[END_REF].

We immediately mention that a different generalization was studied by N. Reading in [START_REF] Reading | Lattice congruences, fans and Hopf algebras[END_REF]. His idea was to construct a subalgebra of C. Malvenuto and C. Reutenauer's algebra FQSym using equivalent classes of a congruence relation defined as the union n∈N ≡ εn of ε n -Cambrian relation for one fixed signature ε n ∈ ± n for each n ∈ N. In order to obtain a valid Hopf algebra, the choice of (ε n ) n∈N has to satisfy certain compatibility relations: N. Reading characterizes the "translational" (resp. "insertional") families ≡ n of lattice congruences on S n for which the sums over the elements of the congruence classes of (≡ n ) n∈N form the basis of a subalgebra (resp. subcoalgebra) of FQSym. These conditions make the choice of (ε n ) n∈N rather constrained. In contrast, by constructing a subalgebra of FQSym ± rather than FQSym, we consider simultaneously all Cambrian relations for all signatures. 1.2.1. Signed shuffle and convolution products. For n, n ∈ N, let

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

τ τ := [τ (1), . . . , τ (n), τ (1) + n, . . . , τ (n ) + n] ∈ S n+n , τ ¡ τ := (τ τ ) • π -1 | π ∈ S (n,n ) and τ τ := π • (τ τ ) | π ∈ S (n,n ) .
As shown by J.-C. Novelli and J.-Y. Thibon in [START_REF] Novelli | Free quasi-symmetric functions and descent algebras for wreath products, and noncommutative multi-symmetric functions[END_REF], these definitions extend to signed permutations as follows. The signed shifted shuffle product τ ¡ τ is defined as the shifted product of the permutations where signs travel with their values, while the signed convolution product τ τ is defined as the convolution product of the permutations where signs stay at their positions

F τ • F τ = σ∈τ ¡ τ F σ and F σ = σ∈τ τ F τ ⊗ F τ .
It naturally extends to signed permutations the Hopf algebra FQSym on permutations defined by C. Malvenuto and C. Reutenauer [START_REF] Malvenuto | Duality between quasi-symmetric functions and the Solomon descent algebra[END_REF].

We denote by Camb the vector subspace of FQSym ± generated by the elements

P T := τ ∈S± ct(τ )=T F τ = τ ∈L(T) F τ ,
for all Cambrian trees T (recall that {τ ∈ S ± | ct(τ ) = T} = L(T) is the set of linear extensions of T). The following result is a straightforward adaptation of a similar result [START_REF] Hivert | The algebra of binary search trees[END_REF]. We skip the proof, whose details can be found in [START_REF] Chatel | Cambrian Hopf Algebras[END_REF].

Theorem 16. Camb is a Hopf subalgebra of FQSym ± .

In the remaining of this section, we provide direct descriptions of the product and coproduct of P-basis elements of Camb in terms of combinatorial operations on Cambrian trees.

Product The product in the Cambrian algebra can be described in terms of intervals in Cambrian lattices. Given two Cambrian trees T, T , we denote by T T the tree obtained by grafting the rightmost outgoing leaf of T on the leftmost incoming leaf of T and shifting all labels of T . See Figure 7 (left). Note that the resulting tree is εε -Cambrian, where εε is the concatenation of the signatures ε = ε(T) and ε = ε(T ). We define similarly T T .

Proposition 17. For any Cambrian trees T, T , the product P T • P T is given by

P T • P T = S P S ,
where S runs over the interval between T T and T T in the ε(T)ε(T )-Cambrian lattice.

Proof. By Proposition 8, the linear extensions L(T) of any Cambrian tree T form an interval of the weak order. Moreover, the shuffle product of two intervals of the weak order is an interval of the weak order. Therefore, the product P T • P T is a sum of P S where S runs over an interval of the Cambrian lattice. It remains to characterize the minimal and maximal elements of this interval. Let µ T and ω T denote respectively the smallest and the greatest linear extension of T in weak order. The product P T • P T is the sum of where ¯denotes as usual the shifting operator on permutations. The result thus follows from the fact that ct(µ T μT ) = T T and ct(ω T ω T ) = T T .

P S over the interval [µ T , ω T ] ¡ [µ T , ω T ] = [µ T μT , ωT ω T ],
Coproduct The coproduct in the Cambrian algebra can also be described in combinatorial terms. Define a cut of a Cambrian tree S to be a set γ of edges such that any geodesic vertical path in S from a down leaf to an up leaf contains precisely one edge of γ. Such a cut separates the tree S into two forests, one above γ and one below γ, denoted A(S, γ) and B(S, γ), respectively. See Figure 7 (right).

Proposition 18. For any Cambrian tree S, the coproduct P S is given by

P S = γ T∈B(S,γ) P T ⊗ T ∈A(S,γ) P T ,
where γ runs over all cuts of S.

Proof. Let σ be a linear extension of S and τ, τ ∈ S ± such that σ ∈ τ τ . The tables of τ and τ respectively appear in the bottom and top rows of the table of σ. We can therefore associate a cut of S to each element which appears in the coproduct P S . Reciprocally, given a cut γ of S, we are interested in the linear extensions of S where all indices below γ appear before all indices above γ. These linear extensions are precisely the permutations formed by a linear extension of B(S, γ) followed by a linear extension of A(S, γ). But the linear extensions of a forest are obtained by shuffling the linear extensions of its connected components. The result immediately follows since the product P T • P T precisely involves the shuffle of the linear extensions of T with the linear extensions of T .

Matriochka algebras Observe that the commutative diagram of Proposition 15 ensures that the Cambrian algebra is sandwiched between the signed permutation algebra and the recoils algebra, defined as the Hopf subalgebra of FQSym ± generated by the elements

X χ := τ ∈S± rec(τ )=χ F τ = T∈Camb can(T)=χ P T ,
for all sign vectors χ ∈ ± n-1 .

Multiplicative bases For a Cambrian tree T, define E T := T≤T P T and H T := T ≤T P T . The sets (E T ) T∈Camb and (H T ) T∈Camb are then multiplicative bases of Camb:

E T • E T = E T T and H T • H T = H T T . A Cambrian tree S is called E-indecomposable if E S = E T • E T implies T = S or T = S.
As for J.-L. Loday and M. Ronco's algebra, it turns out that

• Camb is freely generated by the elements E S for all E-indecomposable Cambrian trees S,

• for any ε ∈ ± n , there are C n-1 E-indecomposable ε-Cambrian trees,

• the set of E-indecomposable elements is a principal upper ideal of the ε-Cambrian lattice.

We omit here the proofs of these results since they are much more involved than in J.-L. Loday and M. Ronco's algebra. Details can be found in [START_REF] Chatel | Cambrian Hopf Algebras[END_REF].

1.2.3. Quotient algebra of FQSym * ± . We switch to the dual Hopf algebra FQSym * ± with basis (G τ ) τ ∈S± and whose product and coproduct are defined by

G τ • G τ = σ∈τ τ G σ and G σ = σ∈τ ¡ τ G τ ⊗ G τ .
The following statement is automatic from Theorem 16.

Theorem 19. The graded dual Camb * of the Cambrian algebra is isomorphic to the image of FQSym * ± under the canonical projection

π : C A -→ C A / ≡,
where ≡ denotes the Cambrian congruence. The dual basis Q T of P T is expressed as

Q T = π(G τ ),
where τ is any linear extension of T.

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

Product Call gaps the n + 1 positions between two consecutive integers of [n], including the position before 1 and the position after n. A gap γ defines a geodesic vertical path λ(T, γ) in a Cambrian tree T from the bottom leaf which lies in the same interval of consecutive negative labels as γ to the top leaf which lies in the same interval of consecutive positive labels as γ. See Figure 9. A multiset Γ of gaps therefore defines a lamination λ(T, Γ) of T, i.e. a multiset of pairwise non-crossing geodesic vertical paths in T from down leaves to up leaves. When cut along the paths of a lamination, the Cambrian tree T splits into a forest.

Consider two Cambrian trees T and T on [n] and [n ] respectively. For any shuffle s of their signatures ε and ε , consider the multiset Γ of gaps of [n] given by the positions of the negative signs of ε in s and the multiset Γ of gaps of [n ] given by the positions of the positive signs of ε in s. We denote by T s \T the Cambrian tree obtained by connecting the up leaves of the forest defined by the lamination λ(T, Γ) to the down leaves of the forest defined by the lamination λ(T , Γ ).

Example 20. Consider the Cambrian trees T and T of Figure 8. To distinguish signs in T and T , we circle the signs in ε(T ) = ⊕ and square the signs in ε(T ) = . Consider now an arbitrary shuffle s = ⊕ of these two signatures. The resulting laminations of T and T , as well as the Cambrian tree T s \T are represented in Figure 8.

Q T • Q T = s Q T s\T ,
where s runs over all shuffles of the signatures of T and T .

Proof. Let τ and τ be linear extensions of T and T respectively, let σ ∈ τ τ and let S = ct(σ). The convolution τ τ shuffles the columns of the tables of τ and τ while preserving the order of their rows. According to the description of the insertion algorithm ct, the tree S thus consists in T below and T above, except that the vertical walls falling from the negative nodes of T split T and similarly the vertical walls rising from the positive nodes of T split T . This corresponds to the description of T s \T , where s is the shuffle of the signatures of T and T given by σ.

Coproduct To describe the coproduct of Q-basis elements of Camb * , we also use gaps and vertical paths in Cambrian trees. Namely, for a gap γ, we denote by L(S, γ) and R(S, γ) the left and right Cambrian subtrees of S when split along the path λ(S, γ). See Figure 9.

Proposition 22. For any Cambrian tree S, the coproduct Q S is given by

Q S = γ Q L(S,γ) ⊗ Q R(S,γ) ,
where γ runs over all gaps between vertices of S.

Proof. Let σ be a linear extension of S and τ, τ ∈ S ± such that σ ∈ τ ¡ τ . As discussed in Section 1.2.1, τ and τ respectively appear on the left and right columns of σ. Let γ denote the vertical gap separating τ from τ . Applying the insertion algorithm to τ and τ separately then yields the trees L(S, γ) and R(S, γ). The description follows. Part 2. The Baxter-Cambrian Hopf Algebra

Twin Cambrian trees

We now consider twin Cambrian trees and the resulting Baxter-Cambrian algebra. It provides a straightforward generalization to the Cambrian setting of the work of S. Law and N. Reading on rectangulations [START_REF] Law | The Hopf algebra of diagonal rectangulations[END_REF] and S. Giraudo on twin binary trees [START_REF] Giraudo | Algebraic and combinatorial structures on pairs of twin binary trees[END_REF]. The bases of these algebras are counted by the Baxter numbers. In Section 2.1.5 we provide references for the various Baxter families and their bijective correspondences, and we discuss the Cambrian counterpart of these numbers. Definitions and combinatorial properties of twin Cambrian trees are given in this section, while the algebraic aspects are treated in the next section.

2.1.1. Twin Cambrian trees. We consider the following pairs of Cambrian trees (see Figure 10).

Proposition 24 ([Gir12]). Two binary trees are twin if and only if they have opposite canopy.

We conjecture that this statement holds for general signatures. Consider two ε-Cambrian trees T • , T • with opposite canopies. It is easy to show that T • T • cannot have trivial cycles, meaning that T • and T • cannot both have a path from i to j for i = j. To prove that T • T • has no cycles at all, a good method is to design an algorithm to extract a linear extension of T • T • . This approach was used in [START_REF] Giraudo | Algebraic and combinatorial structures on pairs of twin binary trees[END_REF] for the signature (-) n . In this situation, it is clear that the root of T • is minimal in T • (by the canopy assumption), and we therefore pick it as the first value of a linear extension of T • T • . The remaining of the linear extension is constructed inductively. In the general situation, it turns out that not all maximums in T • are minimums in T • (and reciprocally). It is thus not clear how to choose the first value of a linear extension of T • T • .

2.1.2. Baxter-Cambrian correspondence. We send a permutation τ ∈ S ε of S ε to a pair of twin ε-Cambrian trees by inserting τ = τ 1 • • • τ n and its mirror

← τ = τ n • • • τ 1 ∈ S ε with the map ct from Section 1.1.2.
Proposition 25. The map ct defined by ct (τ ) := ct(τ ), ct( ← τ ) is a surjection from signed permutations to pairs of twin Cambrian trees.

Proof. By definition, τ is a linear extension of ct(τ ) and of the reverse of ct( The Baxter-Cambrian congruence is the equivalence relation on all signed permutations S ± given by all ε-Baxter-Cambrian congruences:

← τ ), so that ct(τ ) ct( ← τ ) is indeed acyclic. Moreover, the fiber (ct ) -1 ([T • , T • ]) of a pair of twin ε-Cambrian trees T • , T • is the set L(T • T • ) of
for τ ∈ S ε , τ ∈ S ε τ ≡ τ ⇐⇒ ε = ε and τ ≡ ε τ .
Proposition 27. The ε-Cambrian congruence classes are precisely the fibers of the map ct :

for τ, τ ∈ S ε τ ≡ ε τ ⇐⇒ ct (τ ) = ct (τ ).
Proof. The proof of this proposition consists essentially in seeing that ct (τ ) = ct (τ ) if and only if τ ≡ ε τ and Definition 29. Let [T • , T • ] be a pair of ε-Cambrian trees and i → j be an edge of T • T • . We say that the edge i → j is rotatable if and only if one of the following holds:

• i → j is an edge in T • and j → i is an edge in T • , • i → j is an edge in T • while i and j are incomparable in T • , • i and j are incomparable in T • while j → i is an edge in T • . If i → j is rotatable in [T • , T • ], its rotation transforms [T • , T • ] to the pair of trees [T • , T • ],
where

• T • is obtained by rotation of i → j in T • if possible and T • = T • otherwise, and • T • is obtained by rotation of j → i in T • if possible and T • = T • otherwise. Proposition 30. Rotating a rotatable edge i → j in a pair [T • , T • ] of twin ε-Cambrian trees yields a pair [T • , T • ] of twin ε-Cambrian trees.
Proof. By Proposition 10, the trees T • , T • are ε-Cambrian trees. To see that they are twins, observe that switching i and j in a linear extension of T • T • yields a linear extension of T • T • .

Remark 31 (Number of rotatable edges). Note that a pair [T • , T • ] of ε-Cambrian trees has always at least n -1 rotatable edges. This will be immediate from the considerations of Section 2.1.6.

Consider the increasing rotation graph whose vertices are pairs of twin ε-Cambrian trees and whose arcs are increasing rotations [T

• , T • ] → [T • , T • ],
i.e. for which i < j in Definition 29. This graph is illustrated on Figure 11 for the signatures ε = -+--and ε = +---.

Proposition 32. For any cover relation τ < τ in the weak order on S ε , either ct (τ ) = ct (τ ) or ct (τ ) → ct (τ ) in the increasing rotation graph.

Proof. Let i, j ∈ [n] be such that τ is obtained from τ by switching two consecutive values ij to ji. If i and j are incomparable in ct(τ ), then ct(τ ) = ct(τ ). Otherwise, there is an edge i → j in ct(τ ), and ct(τ ) is obtained by rotating i → j in ct(τ ). The same discussion is valid for the trees ct( ← τ ) and ct( ← τ ) and edge j → i. The result immediately follows.

It follows that the increasing rotation graph on pairs of twin ε-Cambrian trees is acyclic and we call ε-Baxter-Cambrian poset its transitive closure. In other words, the previous statement says that the map ct defines a poset homomorphism from the weak order on S ε to the ε-Baxter-Cambrian poset. The following statement extends the results of N. Reading [START_REF] Reading | Cambrian lattices[END_REF] on Cambrian lattices and S. Law and N. Reading [START_REF] Law | The Hopf algebra of diagonal rectangulations[END_REF] on the lattice of diagonal rectangulations.

Proposition 33. The ε-Baxter-Cambrian poset is a lattice quotient of the weak order on S ε . Proof. By Proposition 28, the ε-Baxter-Cambrian congruence is the intersection of two Cambrian congruences. The statement follows since the Cambrian congruences are lattice congruences of the weak order [START_REF] Reading | Cambrian lattices[END_REF] and an intersection of lattice congruences is a lattice congruence. 2.1.5. Baxter-Cambrian numbers. In contrast to the number of ε-Cambrian trees, the number of pairs of twin ε-Cambrian trees depends on the signature ε. For example, there are 22 pairs of twin (----)-Cambrian trees and only 20 pairs of twin (-+--)-Cambrian trees. See Figures 11 and12.

For a signature ε, we define the ε-Baxter-Cambrian number B ε to be the number of pairs of twin ε-Cambrian trees. We immediately observe that B ε is preserved when we change the first and last sign of ε, inverse simultaneously all signs of ε, or reverse the signature ε:

B ε = B χ0(ε) = B χn(ε) = B -ε = B← ε ,
where χ 0 and χ n change the first and last sign, (-ε) i = -ε i and (

← ε ) i = ε n+1-i .
In the following statements, we provide an inductive formula to compute all ε-Baxter-Cambrian numbers, using a two-parameters refinement. The pairs of twin ε-Cambrian trees are in bijection with the weak order maximal permutations of ε-Baxter-Cambrian classes. These permutations are precisely the permutations avoiding the patterns ( ) in Remark 34. We consider the generating tree T ε for these permutations. This tree has n levels, and the nodes at level m are labeled by permutations of [m] whose values are signed by the restriction of ε to [m] and avoiding the patterns ( ). The parent of a permutation in T ε is obtained by deleting its maximal value. See Figure 12.

We consider the possible positions of m + 1 in the children of a permutation τ at level m in this generating tree T ε . Index by {0, . . . , m} from left to right the gaps before the first letter, between two consecutive letters, and after the last letter of τ . Free gaps are those where placing m + 1 does not create a pattern of ( ). Free gaps are marked with a blue dot in Figure 12. It is important to observe that gap 0 as well as the gaps immediately after m -1 and m are always free, no matter τ or the signature ε.

Define the free-gap-type of τ to be the pair ( , r) where (resp. r) denote the number of free gaps on the left (resp. right) of m in τ . For a signature ε, let B ε ( , r) denote the number of freegap-type ( , r) weak order maximal permutations of ε-Baxter-Cambrian classes. These refined Baxter-Cambrian numbers enables us to write inductive equations.

Proposition 35. Consider two signatures ε ∈ ± n and ε ∈ ± n-1 , where ε is obtained by deleting the last sign of ε. Then

B ε ( , r) =          ≥ B ε ( , r -1) + r ≥r B ε ( -1, r ) if ε n-1 = ε n , (=) δ =1 • δ r≥2 • ≥r-1 r ≥1 B ε ( , r ) + δ ≥2 • δ r=1 • ≥1 r ≥ -1 B ε ( , r ) if ε n-1 = ε n , ( =)
where δ denote the Kronecker δ (defined by δ X = 1 if X is satisfied and 0 otherwise).

Proof. Assume first that ε n-1 = ε n . Consider two permutations τ and τ at level n and n-1 in T ε such that τ is obtained by deleting n in τ . Denote by α and β the gaps immediately after n -1 and n in τ , by α the gap immediately after n -1 in τ , and by β the gap in τ where we insert n to get τ . Then, besides gaps 0, α and β, the free gaps of τ are precisely the free gaps of τ not located between gaps α and β . Indeed,

• inserting d := n + 1 just after a value a located between b := n -1 and c := n in τ would create a pattern b-ad-c or c-ad-b with ε b = ε c ; • conversely, consider a gap γ of τ not located between α and β. If inserting n + 1 at γ in τ creates a forbidden pattern of ( ) with c = n, then inserting n at γ in τ would also create the same forbidden pattern of ( ) with c = n -1. Therefore, all free gaps not located between gaps α and β remain free. Let ( , r) denote the free-gap-type of τ and ( , r ) denote the free-gap-type of τ . We obtain that

• ≥ and r = r -1 if n is inserted on the left of n -1; • = -1 and r ≥ r if n is inserted on the right of n -1. The formula follows immediately when ε n-1 = ε n .

Assume now that ε n-1 = -ε n , and keep the same notations as before. Using similar arguments, we observe that besides gaps 0, α and β, the free gaps of τ are precisely the free gaps of τ located between gaps α and β . Therefore, we obtain that • = 1, r ≥ 2, and ≥ r -1 if n is inserted on the left of n -1;

• ≥ 2, r = 1, and r ≥ -1 if n is inserted on the right of n -1. The formula follows for ε n-1 = -ε n .

Before applying these formulas to obtain bounds on B ε for arbitrary signatures ε, let us consider two special signatures: the constant and the alternating signature.

Alternating signature Since it is the easiest, we start with the alternating signature (+-) n 2 (where we define (+-) n 2 to be (+-) m + when n = 2m + 1 is odd).

Proposition 36. The Baxter-Cambrian numbers for alternating signatures are central binomial coefficients (see [START_REF]The On-Line Encyclopedia of Integer Sequences[END_REF]A000984]):

B (+-) n 2 = 2n -2 n -1 .
Proof. We prove by induction on n that the refined Baxter-Cambrian numbers are

B (+-) n 2 ( , r) = δ =1 • δ r≥2 • 2n -2 -r n -r + δ ≥2 • δ r=1 • 2n -2 - n - .
This is true for n = 2 since B +-(1, 2) = 1 (counting the permutation 21) and B +-(2, 1) = 1 (counting the permutation 12). Assume now that it is true for some n ∈ N. Then Equation ( =) of Proposition 35 shows that

B (+-) n+1 2 ( , r) = δ =1 • δ r≥2 • ≥r-1 2n -2 - n - + δ ≥2 • δ r=1 • r ≥ -1 2n -2 -r n -r = δ =1 • δ r≥2 • 2n -r n + 1 -r + δ ≥2 • δ r=1 • 2n - n + 1 - ,
since a sum of binomial coefficients along a diagonal p i=0 q+i i simplifies to the binomial coefficient q+p+1 p by multiple applications of Pascal's rule. Finally, we conclude observing that

B (+-) n 2 = ,r∈[n] B (+-) n 2 ( , r) = 2 u≥2 2n -2 -u n -u = 2 2n -3 n -2 = 2n -2 n -1 .
Constant signature We now consider the constant signature (+) n . The number B (+) n is the classical Baxter number (see [OEI10, A001181]) defined by Remark 37 (Two proofs of the summation formula). There are essentially two ways to obtain the above summation formula for Baxter numbers: it was first proved analytically in [START_REF] Fan | The number of Baxter permutations[END_REF], and then bijectively in [START_REF] Viennot | A bijective proof for the number of baxter permutations. 3rd Seminaire Lotharingien de Combinatoire[END_REF][START_REF] Dulucq | Baxter permutations[END_REF][START_REF] Felsner | Bijections for Baxter families and related objects[END_REF]. Let us shortly comment on these two techniques and discuss the limits of their extension to the Baxter-Cambrian setting.

B (+) n = B n = n + 1 1 -1 n + 1 2 -1 n k=1 n + 1 k -1 n + 1 k n + 1 k + 1 .
(i) The bijective proofs in [START_REF] Dulucq | Baxter permutations[END_REF][START_REF] Felsner | Bijections for Baxter families and related objects[END_REF] transform pairs of binary trees to triples of noncrossing paths, and then use the Gessel-Viennot determinant lemma [START_REF] Gessel | Binomial determinants, paths, and hook length formulae[END_REF] to get the summation formula. The middle path of these triples is given by the canopy of the twin binary trees, while the other two paths are given by the structure of the trees. We are not yet able to adapt this technique to provide summation formulas for all Baxter-Cambrian numbers.

(ii) The analytic proof in [START_REF] Fan | The number of Baxter permutations[END_REF] is based on Equation (=) of Proposition 35 and can be partially adapted to arbitrary signatures as follows. Define the extension of a signature ε ∈ ± n by a signature δ ∈ ± m to be the signature ε δ ∈ ± n+m such that (ε δ) i = ε i for i ∈ [n] and (ε δ) n+j = δ j • (ε δ) n+j-1 for j ∈ m. For example, ++-+--+ = ++--+--.

Then for any ε ∈ ± n and δ ∈ ± m , we have

B ε δ = ,r≥1 X δ ( , r) B ε ( , r),
where the coefficients X δ ( , r) are obtained inductively from the formulas of Proposition 35. Namely, for any , r ≥ 1, we have X ∅ ( , r) = 1 and

X (+δ) ( , r) = 1≤ ≤ X δ ( , r + 1) + 1≤r ≤r X δ ( + 1, r ), X (-δ) ( , r) = 2≤ ≤r+1 X δ ( , 1) + 2≤r ≤ +1 X δ (1, r ).
These equations translate on the generating function

X δ (u, v) := ,r≥1 X δ ( , r)u -1 v r-1 to the formulas X ∅ (u, v) = 1 (1-u)(1-v) and X (+δ) (u, v) = X δ (u, v) -X δ (u, 0) (1 -u)v + X δ (u, v) -X δ (0, v) u(1 -v) , X (-δ) (u, v) = X δ (v, 0) -X δ (0, 0) (1 -u)(1 -v)v + X δ (0, u) -X δ (0, 0) u(1 -u)(1 -v) .
Note that the u/v-symmetry of X δ (u, v) is reflected in a symmetry on these inductive equations. We can thus write this generating function X δ (u, v) as

X δ (u, v) = i,j≥0 k∈[|δ|+1] Y i,j,k δ (-u) i (-v) j (1 -u) |δ|+2-k (1 -v) k ,
where the non-vanishing coefficients Y i,j,k δ are computed inductively by Y 0,0,1 ∅ = 1 and

Y i,j,k (+δ) = k j + 1 Y i,0,k δ -Y i,j+1,k δ + |δ| + 3 -k i + 1 Y 0,j,k-1 δ -Y i+1,j,k-1 δ , Y i,j,k (-δ) = k -1 j |δ| + 2 -k i + 1 Y 0,0,k δ -Y i+1,0,k δ + |δ| + 2 -k i k -1 j + 1 Y 0,0,k-1 δ -Y 0,j+1,k-1 δ . We used that Y i,j,k δ = Y j,i,|δ|+2-k δ
to simplify the second equation. Note that this decomposition of X δ is not unique and the inductive equations on Y i,j,k δ follow from a particular choice of such a decomposition.

At that stage, F. Chung, R. Graham, V. Hoggatt, and M. Kleiman [START_REF] Fan | The number of Baxter permutations[END_REF], guess and check that the first equation is always satisfied by

Y i,j,k (+) n-1 = n+1 k n+1 k+i+1 n+1 k-j-1 k+i-2 i n+j-k-1 j -k+i-2 i-1 n+j-k-1 j-1 n+1 1 n+1 2
from which they derive immediately that

B (+) n = B + (+) n-1 = ,r≥1 X (+) n-1 ( , r) B + ( , r) = X (+) n-1 (1, 1) = X (+) n-1 (0, 0) = k∈[n] Y 0,0,k (+) n-1 = n + 1 1 -1 n + 1 2 -1 n k=1 n + 1 k -1 n + 1 k n + 1 k + 1 .
Unfortunately, we have not been able to guess closed formulas for the coefficients Y i,j,k δ for arbitrary δ ∈ ± n .

Arbitrary signatures We now come back to an arbitrary signature ε. We were not able to derive summation formulas for arbitrary signatures using the techniques presented in Remark 37 above. However, we use here the inductive formulas of Proposition 35 to bound the Baxter-Cambrian number B ε for an arbitrary signature ε.

For this, we consider the matrix B ε := B ε ( , r) ,r∈ [n] . The inductive formulas of Proposition 35 provide an efficient inductive algorithm to compute this matrix B ε and thus the ε-Baxter-Cambrian number B ε =

,r∈[n] B ε ( , r). Namely, if ε is obtained by adding a sign at the end of ε , then each entry of B ε is the sum of entries of B ε in a region depending on whether ε n = ε n-1 . These regions are sketched in Figure 13.

ε n = ε n-1 ε n = -ε n-1 Figure 13
. Inductive computation of B ε : the black entry of B ε is the sum of the entries of B ε over the shaded region. Entries outside the upper triangular region always vanish. When ε n = -ε n-1 , the only non-vanishing entries of B ε are in the first row or in the first column.

We observe that the transformations of Figure 13 are symmetric with respect to the diagonal of the matrix. Since B ε1ε2 = 0 1 1 0 is symmetric, and B ε is obtained from B ε1ε2 by successive applications of these symmetric transformations, we obtain that B ε is always symmetric. Although this fact may seem natural to the reader, it is not at all immediate as there is an asymmetry on the three forced free gaps: for example gap 0 is always free.

For a matrix M := (m i,j ), we consider the matrix M se := m se i,j where

m se i,j := p≥i, q≥j m p,q
is the sum of all entries located south-east of (i, j) (in matrix notation). Observe that (B ε ) se 1,1 is the sum of all entries of B ε , and thus equals the ε-Baxter-Cambrian number B ε . Using Figure 13, we obtain a similar rule to compute the entries of B se ε as sums of entries of B se ε when ε is obtained by adding a sign at the end of ε . This rule is presented in Figure 14.

ε n = ε n-1 ε n = -ε n-1
, ε ∈ ± n , if switch(ε) ⊂ switch(ε) then B ε > B ε.
Proof. For two matrices M := (m i,j ) and M := ( mi,j ), we write M M when m i,j ≥ mi,j for all indices i, j (entrywise comparison), and we write M M when M M and M = M . Consider four signatures ε, ε ∈ ± n and ε , ε ∈ ± n-1 such that ε (resp. ε ) is obtained by deleting the last sign of ε (resp. ε). From Figure 14, and using the fact that B ε is symmetric, we obtain that:

• if ε n = ε n-1 while εn = -ε n-1 , then B se ε B se ε implies B se ε B se ε . • if either both ε n = ε n-1 and εn = εn-1 , or both ε n = -ε n-1 and εn = -ε n-1 , then B se ε B se ε implies B se ε B se ε .
By repeated applications of these observations, we therefore obtain that switch(ε) ⊂ switch(ε) implies B se ε B se ε , and thus B ε > B ε. Corollary 39. Among all signatures of ± n , the constant signature maximizes the Baxter-Cambrian number, while the alternating signature minimizes it: for all ε ∈ ± n ,

2n -2 n -1 = B (+-) n 2 ≤ B ε ≤ B (+) n = n + 1 1 -1 n + 1 2 -1 n k=1 n + 1 k -1 n + 1 k n + 1 k -1 .
Remark 40. The proof of Proposition 38 may seem unnecessarily intricate. Observe however that the situation is rather subtle:

• If switch(ε) ⊆ switch(ε), we may have B ε < B ε even if |switch(ε)| < |switch(ε)|. The smallest example is given by B +++-++---= 18376 < 18544 = B ++-+++-++ . • We may have B se ε B se ε but B ε B ε.
2.1.6. Geometric realizations. Using similar tools as in Section 1.1.6 and following [START_REF] Law | The Hopf algebra of diagonal rectangulations[END_REF], we present geometric realizations for pairs of twin Cambrian trees, for the Baxter-Cambrian lattice, and for the map ct . For a partial order ≺ on [n], we still define its incidence cone C(≺) and its braid cone C (≺) as C(≺) := cone {e i -e j | for all i ≺ j} and C (≺) := {x ∈ H | x i ≤ x j for all i ≺ j} .

The cones C(T • T • ) for all pairs [T • , T • ] of twin ε-Cambrian trees form (together with all their faces) a complete polyhedral fan that we call the ε-Baxter-Cambrian fan. It is the common refinement of the ε-and (-ε)-Cambrian fans. It is therefore the normal fan of the Minkowski sum of the associahedra Asso(ε) and Asso(-ε). We call this polytope Baxter-Cambrian associahedron and denote it by BaxAsso(ε). Note that BaxAsso(ε) is clearly centrally symmetric (since Asso(ε) = -Asso(-ε)) but not necessarily simple. Examples are illustrated on Figure 15. The graph of BaxAsso(ε), oriented in the direction (n, . . .

Baxter-Cambrian Hopf Algebra

In this section, we define the Baxter-Cambrian Hopf algebra BaxCamb, extending simultaneously the Cambrian Hopf algebra and the Baxter Hopf algebra studied by S. Law and N. Reading [START_REF] Law | The Hopf algebra of diagonal rectangulations[END_REF] and S. Giraudo [START_REF] Giraudo | Algebraic and combinatorial structures on pairs of twin binary trees[END_REF]. We present again the construction of BaxCamb as a subalgebra of FQSym ± and that of its dual BaxCamb * as a quotient of FQSym * ± . 2.2.1. Subalgebra of FQSym ± . We denote by BaxCamb the vector subspace of FQSym ± generated by the elements Asso(-+--) Asso(+-++) Asso(+---) Asso(-+++) Asso(-+--) + Asso(+-++) Asso(+---) + Asso(-+++) The following statement is similar to Theorem 16.

Theorem 41. BaxCamb is a Hopf subalgebra of FQSym ± .

As for the Cambrian algebra, we can describe combinatorially the product and coproduct of P-basis elements of BaxCamb in terms of operations on pairs of twin Cambrian trees.

Product The product in the Baxter-Cambrian algebra BaxCamb can be described in terms of intervals in Baxter-Cambrian lattices. Proof. The result relies on the fact that the ε-Baxter-Cambrian classes are intervals of the weak order on S ε , and that the shuffle product of two intervals of the weak order is again an interval of the weak order. See the similar proof of Proposition 17. Coproduct The coproduct in BaxCamb * can be described combinatorially as in Proposition 22. For a Cambrian tree S and a gap γ between two consecutive vertices of S, we still denote by L(S, γ) and R(S, γ) the left and right Cambrian subtrees of S when split along the path λ(S, γ). Proof. The proof is identical to that of Proposition 22.

Figure 1 .

 1 Figure 1. The 3-dimensional permutahedron (blue, left), Loday's associahedron (red, middle), and parallelepiped (green, right). Shaded facets are preserved to get the next polytope.

  (left). Definition 1. A Cambrian tree is a directed tree T on [n] such that for each v ∈ [n], (i) v has either one parent and two children (its descendant subtrees are called left and right subtrees) or one child and two parents (its ancestor subtrees are called left and right subtrees); (ii) all vertices are smaller (resp. larger) than v in the left (resp. right) subtree of v. The signature of T is the n-tuple ε(T) ∈ ± n defined by ε(T) v = -if v has two children and ε(T) v = + if v has two parents. Denote by Camb(ε) the set of Cambrian trees with signature ε, by Camb(n) = ε∈± n Camb(ε) the set of all Cambrian trees on [n], and by Camb := n∈N Camb(n) the set of all Cambrian trees. Throughout the paper, we represent Cambrian trees as follows (see Figure 2 (left)): (i) each vertex v ∈ [n] appears at abscissa v; (ii) the edges are oriented form bottom to top; (iii) negative vertices (with one parent and two children) are represented by , while positive vertices (with one child and two parents) are represented by ⊕; (iv) we sometimes draw a vertical red wall below the negative vertices and above the positive vertices to mark the separation between the left and right subtrees of each vertex.

Proposition 3 (Figure 2 .

 32 Figure 2. Cambrian trees (left) and triangulations (right) are dual to each other (middle).

Figure 3 .

 3 Figure 3. The insertion algorithm on the signed permutation 2751346.

Figure 5 .

 5 Figure 5. The ε-Cambrian lattices for ε = -+--(left) and ε = +---(right).

Figure 7 .

 7 Figure 7. Grafting Cambrian trees (left) and cutting a Cambrian tree (right).

Figure 8 .

 8 Figure 8. (a) The two Cambrian trees T and T . (b) Given the shuffle s = ⊕ , the positions of the are reported in T and the positions of the ⊕ are reported in T . (c) The corresponding laminations. (d) The trees are split according to the laminations. (e) The resulting Cambrian tree T s \T . Proposition 21. For any Cambrian trees T, T , the product Q T • Q T is given by

Figure 9 .

 9 Figure 9. A gap γ (left) defines a vertical cut (middle) which splits the Cambrian tree (right).

Definition 23 .

 23 Two ε-Cambrian trees T • , T • are twin if the union T • T • of T • withthe reverse of T • (reversing the orientations of all edges) is acyclic.

Figure 10 .

 10 Figure 10. A pair of twin Cambrian trees.

  linear extensions of the graph T • T • . This set is non-empty since T • T • is acyclic by definition of twin Cambrian trees. 2.1.3. Baxter-Cambrian congruence. We now characterize by a congruence relation the signed permutations τ ∈ S ε which have the same image ct (τ ). Definition 26. For a signature ε ∈ ± n , the ε-Baxter-Cambrian congruence is the equivalence relation on S ε defined as the transitive closure of the rewriting rules U bV adW cX ≡ ε U bV daW cX if a < {b, c} < d and ε b = ε c , U bV cW adX ≡ ε U bV cW daX if a < {b, c} < d and ε b = ε c , U adV bW cX ≡ ε U daV bW cX if a < {b, c} < d and ε b = ε c , where a, b, c, d are elements of [n] while U, V, W, X are words on [n].

← τ ≡ ε ←τ

 ε (by definition of ct ). The definition of the ε-Baxter-Cambrian equivalence ≡ ε is exactly the translation of this observation in terms of rewriting rules. Proposition 28. The ε-Baxter-Cambrian class indexed by a pair [T • , T • ] of twin ε-Cambrian trees is the intersection of the ε-Cambrian class indexed by T • with the (-ε)-Cambrian class indexed by the reverse of T • . Proof. The ε-Baxter-Cambrian class indexed by [T • , T • ] is the set of linear extensions of T • T • , i.e. of permutations which are both linear extensions of T • and linear extensions of the reverse of T • . The former form the ε-Cambrian class indexed by T • while the latter form the (-ε)-Cambrian class indexed by the reverse of T • . 2.1.4. Rotations and Baxter-Cambrian lattices. We now present the rotation operation on pairs of twin ε-Cambrian trees.

Remark 34 (

 34 Extremal elements and pattern avoidance). Since the Baxter-Cambrian classes are generated by rewriting rules, we immediately obtain that the minimal elements of the Baxter-Cambrian classes are precisely the signed permutations avoiding the patterns: b-da-c, b-da-c, c-da-b, c-da-b, b-c-da, b-c-da, c-b-da, c-b-da, da-b-c, da-b-c, da-c-b, da-c-b. Similarly, the maximal elements of the Baxter-Cambrian classes are precisely the signed permutations avoiding the patterns: ( ) b-ad-c, b-ad-c, c-ad-b, c-ad-b, b-c-ad, b-c-ad, c-b-ad, c-b-ad, ad-b-c, ad-b-c, ad-c-b, ad-c-b.

  These numbers have been extensively studied, see in particular [CGHK78, Mal79, DG96, DG98, YCCG03, FFNO11, BBMF11, LR12, Gir12]. The Baxter number B n counts several families: • Baxter permutations of [n], i.e. permutations avoiding the patterns b-da-c and c-ad-b, • weak order maximal (resp. minimal) permutations of Baxter congruence classes on S n , i.e. permutations avoiding the patterns b-ad-c and c-ad-b (resp. b-da-c and c-da-b), • pairs of twin binary trees on n nodes, • diagonal rectangulations of an n × n grid, • plane bipolar orientations with n edges, • non-crossing triples of path with k -1 north steps and n -k east steps, for all k ∈ [n], • etc. Bijections between all these Baxter families are discussed in [DG96, DG98, FFNO11, BBMF11].

Figure 14 .

 14 Figure 14. Inductive computation of B se ε : the black entry of B se ε is the sum of the entries of B se ε over the shaded region. Entries outside the triangular shape always vanish. When ε n = -ε n-1 , the only non-vanishing entries of B se ε are in the first row or in the first column.

  , 1) -(1, . . . , n) = i∈[n] (n + 1 -2i) e i ,is the Hasse diagram of the ε-Baxter-Cambrian lattice. Finally, the map ct can be read geometrically as[T • , T • ] = ct (τ ) ⇐⇒ C(T • T • ) ⊆ C(τ ) ⇐⇒ C (T • T • ) ⊇ C (τ ).

P

  [T•,T•] := τ ∈S± ct (τ )=[T•,T•]

F τ = τ=

 = ∈L(T• T•) F τ , for all pairs of twin Cambrian trees [T • , T • ] (recall that τ ∈ S ± ct (τ ) = T • T • = L(T • T • )is the set of linear extensions of T • T • ). For example, for the pair of twin Cambrian trees of Figure10(left), we have F 2175346 + F 2715346 + F 2751346 + F 7215346 + F 7251346 + F 7521346 .

Figure 15 .

 15 Figure 15. The Minkowski sum (blue, right) of the associahedra Asso(ε) (red, left) and Asso(-ε) (green, middle) gives a realization of the ε-Baxter-Cambrian lattice. Illustrated with the signatures ε = -+--(top) and ε = +---(bottom) whose ε-Baxter-Cambrian lattice appear in Figure 11.

Proposition 42 .

 42 For any two pairs[T • , T • ] and [T • , T • ] of twin Cambrian trees, the product P [T•,T•] • P [T • ,T • ] is given by P [T•,T•] • P [T • ,T • ] = [S•,S•] P [S•,S•] ,where[S • , S • ] runs over the interval between T • T • , T • T • and T • T • , T • T • in the ε(T • )ε(T • )-Baxter-Cambrian lattice.

Coproduct

  A cut of a pair of twin Cambrian trees [S • , S • ] is a pair γ = [γ • , γ • ] where γ • is a cut of S • and γ • is a cut of S • such that the labels of S • below γ • coincide with the labels of S • above γ • . Equivalently, it can be seen as a lower set of T • T • . An example is illustrated in Figure 16. We denote by AB([S • , S • ], [γ • , γ • ]) the set of pairs [A • , B • ], where A • appears in the product T∈A(S•) P T while B • appears in the product T∈B(S•) P T , and A • and B • are twin Cambrian trees. We define BA([S • , S • ], [γ • , γ • ]) similarly exchanging the role of A and B. We obtain the following description of the coproduct in the Baxter-Cambrian algebra BaxCamb. Proof. The proof follows the same lines as that of Proposition 21. The only difference is that if τ ∈ L(T • T • ), τ ∈ L(T • T • ), and σ ∈ τ τ , then T • = ct(τ ) appears below T • = ct(τ ) in ct(σ) since σ is inserted from left to right in ct(σ), while T • = ct( ← τ ) appears above T • = ct( ← τ ) in ct( ← σ ) since σ is inserted from right to left in ct( ← σ ).

Proposition 46 .

 46 For any pair of twin Cambrian trees[S • , S • ], the coproduct Q [S•,S•] is given by Q [S•,S•] = γ Q [L(S•,γ),L(S•,γ)] ⊗ Q [R(S•,γ),R(S•,γ)] ,where γ runs over all gaps between consecutive positions in [n].

  Subalgebra of FQSym ± . We denote by FQSym ± the Hopf algebra with basis (F τ ) τ ∈S± and whose product and coproduct are defined by

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

Acknowledgements

We are grateful to the participants of the Groupe de travail de Combinatoire Algébrique de l'Université de Marne-la-Vallée for helpful discussions and comments on preliminary stages of this work, in particular J.-Y. Thibon, J.-C. Novelli and V. Pons. The second author thanks C. Hohlweg for introducing him to this algebraic combinatorics crowd. We are also grateful to M. Bousquet-Melou, C. Hohlweg and N. Reading for pointing out to us various relevant references. Finally, we thank two anonymous referees for valuable comments and suggestions on the paper.

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

where γ runs over all cuts of

Proof. The proof is similar to that of Proposition 18. The difficulty here is to describe the linear extensions of the union of the forest A(S • , γ • ) with the opposite of the forest

2.2.2. Quotient algebra of FQSym * ± . As for the Cambrian algebra, the following result is automatic from Theorem 41.

Theorem 44. The graded dual BaxCamb * of the Baxter-Cambrian algebra is isomorphic to the image of FQSym * ± under the canonical projection

where ≡ denotes the Baxter-Cambrian congruence. The dual basis

, where τ is any linear extension of T • T • .

We now describe the product and coproduct in BaxCamb * by combinatorial operations on pairs of twin Cambrian trees. We use the definitions and notations introduced in Section 1.2.3.

Product

The product in BaxCamb * can be described using gaps and laminations similarly to Proposition 21. An example is illustrated on Figure 17. For two Cambrian trees T and T and a shuffle s of the signatures ε(T) and ε(T ), we still denote by T s \T the tree described in Section 1.2.3.

where s runs over all shuffles of the signatures ε(T • ) = ε(T • ) and ε(T • ) = ε(T • ).