Séminaire Lotharingien de Combinatoire 82 (2020), Article B82a

SURJECTIONS AS DOUBLE POSETS

LOÏC FOISSY AND FRÉDÉRIC PATRAS

Abstract. The theory of double posets and pictures between them, introduced by Malvenuto and Reutenauer, is a far reaching development of Zelevinsky’s theory of pictures in that, among others, it embeds the latter into a self-dual Hopf algebraic framework. It has brought forward many ideas and results and has led recently to several developments, in various directions. Namely, besides algebraic combinatorics and noncommutative representation theory: algebraic topology and the geometry of polytopes.

One of these developments, by the first author of this article, was the combinatorial and Hopf algebraic study of symmetric groups from the point of view of double posets. The present article extends these results to surjections. We introduce first a family of double posets, packed double posets. Using an appropriate statistics on surjections that generalizes inversions, it is shown that they are in bijection with surjections or, equivalently, with packed words. The following sections investigate their self-dual Hopf algebraic properties. Using an appropriate notion of linear extensions of packed double posets, the Hopf algebra of packed double posets is proved to be isomorphic with (two different versions of) the Hopf algebra of word quasi-symmetric functions.

1. Introduction

The theory of double posets and pictures between them was introduced by Malvenuto and Reutenauer in 2011 [14]. It is a far reaching development of Zelevinsky’s theory of pictures [17] in that it embeds for example the latter into a self-dual Hopf algebraic framework. It has brought forward many ideas and results and has recently led to several developments, in various directions. In algebraic combinatorics and noncommutative representation theory, double posets have been used to study the combinatorics of symmetric groups [4, 5, 6] and, in relation to quasisymmetric functions, to generalize objects such as dual immaculate functions or quasisymmetric P, ω -partition enumerators [11]. The theory of double posets was also generalized to double quasiposets, a natural framework to study objects such as semi-standard tableaux on which several quasi-orders coexist naturally [8]. In algebraic topology, they appear as an example of monoidal (directed) restriction species [10]. In the geometry of polytopes, the notion of double poset polytopes [3, 1] has been introduced as a generalization of Stanley’s work relating the geometry of polytopes with the combinatorics of associated posets [16].

The present article extends the results of [4, 5] on permutations to surjections. It is organized as follows. We introduce first (Section 2) a family of double posets, packed double posets, that generalize the planar posets of [5]. They can be shown to be in bijection with surjections or, equivalently, with packed words (Theorem 4, Section 3). Section 4 investigates their self-dual Hopf algebraic properties, which are inherited from the Hopf algebra structure of double posets [14]. Section 5 recalls briefly the idea of non-linear Schur–Weyl duality and how two Hopf algebra structures can be constructed on the linear span of surjections using their interpretation as operations on tensor powers of a commutative algebra. One of these two Hopf algebras is the classical Chapoton–Hivert Hopf algebra WQSym of word quasi-symmetric functions [12, 2]. Section 6 introduces the notion of linear and weak linear extensions of packed double posets. It gives rise to Hopf algebra isomorphisms from the Hopf algebra of packed double posets to the two Hopf algebra structures introduced in Section 5.

2. Packed double posets

Recall that a double poset is a set equipped with two orders. A quasi-order is a binary relation which is reflexive and transitive but not necessarily antisymmetric (so that one may have x y and y x with x y). A quasi-order is total when all elements are comparable (i.e., when x y or y x for arbitrary x and y). If x y and y x, we write x y and say that x and y are equivalent (the relation is an equivalence relation). A quasi-poset is a set equipped with a quasiorder. All the posets, double posets, quasi-posets, … we consider here are assumed to be finite (we omit therefore “finite” in our definitions and statements).

Definition 1. A packed double poset is a double poset P, _{1}, _{2} that satisfies the following two properties:

(1) For all x, y P, we have x _{1} y and x _{2} y x y .

(2) The relation defined on P by x _{1} y or x _{2} y is a total quasi-order.

In particular, the relation defined by (x y and y x) is an equivalence relation (we denote it as above by ).

Example. A plane poset is a double poset P, _{1}, _{2} with the following properties:

For all x, y P, if x and y are comparable for both _{1} and _{2},

then x y. For all x, y P, x and y are comparable for _{1} or for _{2}.

By Proposition 11 of [5], if P, _{1}, _{2} is a plane poset, then is a total order, and obviously (1) is also satisfied. So plane posets are packed double posets. Moreover, if P is a packed double poset, then is an order if, and only if, P is plane: by (2), two distinct elements x, y are always comparable, and the fact that is an order implies that they cannot be comparable for both _{1} and _{2}.

Lemma 2. Let P, _{1}, _{2} be a packed double poset. Then:

(3) The relation defined on P by y _{1} x or x _{2} y is a total order.

Proof. Let x, y, z P, such that x y and y z. The following three cases are possible:

(y _{1} x and z _{1} y) or (x _{2} y and y _{2} z). Then (z _{1} x or

x _{2} z), so x z. x _{2} y and z _{1} y. As is a total quasi-order, the following

two subcases are possible:

– x z, then x _{1} z or x _{2} z. If x _{2} z, then x z. If

x _{1} z, then x _{1} y and x _{2} y. By (1), x y, so x z.

– z x, then z _{1} x or z _{2} x. If z _{1} x, then x z. If

z _{2} x, then z _{2} y and z _{1} y. By (1), y z, so x z.

y _{1} x and y _{2} z. Similar proof. Therefore, is transitive.

Let x, y P, such that x y and y x. The following two cases are possible:

(1) (y _{1} x and x _{1} y) or (x _{2} y and y _{2} x): then x y.

(2) y _{1} x and y _{2} x, or x _{1} y and x _{2} y: by (1), x y. So is an order.

For all x, y P, x y or y x, so y _{1} x or x _{2} y or x _{1} y or y _{2} x, so x y or y x: in other words, is total. □

Remark. (3) implies (1), but not (2).

Remark. The lemma allows one to canonically identify P with n and the pair P, with a packed word. This is the reason for the terminology adopted for “packed double posets”. See the next section for details.

3. Surjections and packed words

When a surjection f from n to k is represented by the sequence of its values, w_{f} : f 1 … f n , the word w_{f} is packed: its set of letters can be identified with an initial subset of the integers (in that case, k ). Conversely, an arbitrary packed word of length n can always be obtained in that way: packed words (of length n) are in bijection with surjections (with domain n and codomain an initial subset of the integers). We write pack for the packing operation: given a word w with (possibly repeated) letters x_{1} x_{k} in n , pack w is the word obtained from w by replacing the letter x_{i} by i. For example, pack 714274 413243 .

Recall also that total quasi-orders on n are in bijection with packed words. An example illustrates the general rule: assume that n 6 and that the quasi-order is defined by

2 5 1 3 6 4.

Then the corresponding packed word is 212312: the first equivalence class 2, 5 gives the position of letter 1, the second, 1, 3, 6 , the positions of letter 2, and so on.

Proposition 3. Let w be a packed word of length n. The double poset P_{w} (also written Dp w ) is defined by P_{w} n , _{1}, _{2} , with:

for all i, j n ,  i _{1} j  i j and w i w j ,
i _{2} j  i j and w i w j .

It is a packed double poset. The total quasi-order is the one associated bijectively with w; the total order is the natural order on n .

Proof. The fact that P_{w} is a double poset is obvious. For all i, j n , if i _{1} j and i _{2} j, then i j and i j, so i j: (1) is verified. Moreover:

i j w i w j ,

so is indeed a total quasi-order. □

Theorem 4. The set of packed words of length n and the set of isomorphism classes of packed double posets are in bijection through Dp. The inverse map, pack, is given as follows. Let P be a packed double poset. By Lemma 2, we can assume that P n with the natural order. Then Dp^{1} P : pack P is the packed word associated with the total quasi-order .

Proof. We first show that, for any packed words w, w^{}, the double posets P_{w} and P_{w^{}}are isomorphic if, and only if, w w^{}. Let f :

P_{w} P_{w^{}}be an isomorphism. Then f is increasing from n , to n^{}, ^{}. As and ^{}are the usual total orders of n and n^{}, n n^{} and f Id_{n}. Consequently, for all i, j n with i j, we have

w i w j i _{2} j i _{2}^{}j w^{}i w^{}j .

As w and w^{}are packed words, we infer w w^{}.

Let now P be a packed double poset. We claim that Dp pack P P. We may assume that P, n , . The packed word w pack P is such that, for all i, j n , i j w i w j . We denote the orders of P_{w} by _{1}^{}and _{2}^{}. Then, for all i, j n , we have

i _{1}^{}j  j i and w i w j
j i and i j
i _{1} j or j _{2} i and i _{1} j or i _{2} j
i _{1} j or j _{2} i and i _{2} j
i _{1} j or i j
i _{1} j.

So _{1}^{}_{1}. Similarly, _{2}^{}_{2}. □

4. The self-dual Hopf algebra structure

We denote by H_{DP} the vector space generated by isomorphism classes of double posets, and by H_{P DP} its subspace generated by isomorphism classes of packed double posets. Below we show how definitions and results in [14, 8] apply in this context (definitions and results relative to double posets are taken from [14]).

Let P, Q be two double posets. We define two orders on P Q by:

for all i, j P Q,  i _{1} j if i, j P and i _{1} j
or i, j Q and i _{1} j ;
i _{2} j if i, j P and i _{2} j
or i, j Q and i _{2} j
or i P and j Q .

This defines a double poset, which we denote by P Q. Extension of this product by bilinearity makes H_{DP} an associative algebra, whose unit is the empty double poset denoted 1. If P and Q are packed double posets, then so is P Q. Hence, H_{P DP} is a subalgebra of H_{DP}.

Definition 5. Let P be a double poset (respectively packed double poset) and let X P.

X is also a double poset (respectively packed) by restriction of 1 and _{2}: we denote this double poset (respectively packed) by P_{X}.

We say that X is an open set of P if

for all i, j P,  i _{1} j and i X j X.

The set of open sets of P is denoted by Top P . A coproduct is defined on H_{DP} (respectively H_{P DP}) by

Δ P _{O Top P}P_{P O} P_{O}.

Theorem 6. The product and the coproduct equip H_{DP} and therefore its subspace H_{P DP} with the structure of a graded, connected Hopf algebra.

See [14] for a proof of the compatibility properties between the product and the coproduct characterizing a Hopf algebra.

Recall that, for P P, _{1}, _{2} , ι P : P, _{2}, _{1} . If P is a packed double poset, then so is ι P . Recall also that, given two double posets P, Q, there exists a pairing on H_{DP} defined by

P, Q : P ic P, Q ,

where P ic P, Q stands for the number of pictures between P and Q (a picture between P and Q is a bijection f such that

i _{1} j f i _{2} f j ,  f i _{1} f j i _{2} j.

The Hopf algebra of double posets H_{DP} is self-dual for this pairing. By Proposition 24 of [8], we get the following result.

Proposition 7. The Hopf algebra H_{P DP} is a self-dual Hopf subalgebra of the Hopf algebra of double posets H_{DP}.

5. Hopf algebras of surjections

We write WQSym_{n} for the linear span of surjections from n to an arbitrary p , p n (and set WQSym_{0} : ℚ, WQSym :

_{n 0} WQSym_{n}).

The symbol WQSym stands for “word quasi-symmetric functions”. We refer to [2, 12] for definitions and to [13, 15] for studies of their combinatorial properties. On the terminology and notation, see also Remark 9 below.

Recall that natural transformations from the functor (from commutative algebras to vector spaces) T_{n} A : A^{n} to T_{p} A : A^{p} , 0 p n, are in bijection with the linear span of surjections from n to p by non-linear Schur–Weyl duality [9]. For example, the map f : 5 3 , f 1 2, f 2 1, f 3 3, f 4 2, f 5 1 gives rise to the map

A^{5} A^{3} ,
a_{1}  a_{5}  a_{2}a_{5} a_{1}a_{4} a_{3}.

This observation leads to two Hopf algebra structures on WQSym. Recall indeed that, given a commutative algebra A, the tensor algebra over A, T A , carries two Hopf algebra structures when equipped with the deconcatenation coproduct

δ : a_{1}  a_{n}  _{i n} a_{1}  a_{i} a_{i 1}  a_{n} .

The first structure uses the shuffle product inductively defined by

a_{1}  a_{n} � b_{1}  b_{m} : a_{1} a_{2}  a_{n} � b_{1}  b_{m}
b_{1} a_{1}  a_{n} � b_{2}  b_{m} ,

the second uses the quasi-shuffle product inductively defined by

a_{1}  a_{n} b_{1}  b_{m} : a_{1} a_{2}  a_{n} b_{1}  b_{m}
b_{1} a_{1}  a_{n} b_{2}  b_{m}
a_{1}b_{1} a_{2}  a_{n} b_{2}  b_{m} .

Due to the embedding WQSym End T A , where a surjection f : n p acts trivially on T_{r} A for r n and by the action obtained by Schur–Weyl duality otherwise, we get two graded convolution products: for f as above, g : k l and w T A , we define

f � g w : f w^{1} � g w^{2} ,
f g w : f w^{1} g w^{2} ,

using the Sweedler shortcut notation δ w w^{1} w^{2}. That is, equivalently, f � g _{h} h, where h runs over the surjections h : n k p l with pack h 1 … h n f 1 … f n and pack h n 1 … h n k g 1 … g k . Notice that these conditions imply

h 1 , …, h n  h n 1 , …, h n k  .

For the product we have instead f g _{h} h, where h runs over the surjections h : n k q with sup p, l q p l with pack h 1 … h n f 1 … f n and pack h n 1 … h n k g 1 … g k .

For example,

211 � 1  2113 3112 3221 ,
211 1 2113 3112 3221 2111 2112 .

A coproduct Δ is defined on WQSym by

Δ f : _{i p} f_{1,...,i} pack f_{i 1,...,p} ,

where a surjection is written as a packed word and, given S p , f_{S} stands for the subword of f containing the letters in S. For example, if f 5312354 and S 2, 4, 5 , f_{S} 5254 and pack f_{S} 3132 .

The following proposition is proved in [12, 2], respectively in [7].

Proposition 8. The triples WQSym, , Δ and WQSym, �, Δ are graded connected (noncommutative, noncocommutative) Hopf algebras.

Remark 9. Our notation is slightly conflicting with the usual practice. Indeed, the symbol WQSym stands very often in the literature for the Hopf algebra WQSym, , Δ , not just (as in the present article) for the underlying graded vector space. Moreover, this Hopf algebra is classically presented as a subalgebra of a ring of formal series 𝕂 X , where X is a countably infinite totally ordered alphabet, linearly generated by formal series M_{u} indexed by surjections. For example,

M_{1} _{x X} x,  M_{12} _{x y X} xy,
M_{11} _{x X} xx,  M_{21} _{x y X} yx.

The coproduct Δ is then obtained by doubling the alphabet, see [15].

Our notational choice was motivated by the fact that we are working directly with surjections (and not linear combinations of words indexed by them) and need to define two products on their linear span, one of which (�) is not induced by the product of monomials in 𝕂 X .

6. Linear extensions and WQSym.

Definition 10. Let P P, _{1}, _{2} be a packed double poset. A linear extension of P is a surjective map f : P k such that:

(1) For all i, j P, i _{1} j f i f j .

(2) For all i, j P, f i f j i j. The set of linear extensions of P is denoted by Lin P , the set of linear extensions from P to k is denoted by Lin^{k} P .

If f is a linear extension of a packed double poset P with P, n , , a property that we can always assume up to a canonical isomorphism, we see it as a packed word f 1 … f n . We denote the set of packed words of length n by P W n .

Recall that an open set X of a packed double poset P is a packed double subposet of P such that

for all i, j P,  i _{1} j and i X j X.

The following lemmas follow immediately from the definitions, and hence their proof is omitted.

Lemma 11. Let P be a packed double poset and X an open set of P. Let f_{X} : X p and f_{P X} : P X q be two linear extensions. Then the map f : P p q defined by

f i : f_{P X} i for i P X,
f j : f_{X} j q for j X,

is a linear extension of P.

Lemma 12. Conversely, let f be a linear extension of P, f : P k . For any i k, X : f^{1} i 1, …, k is an open subset of P. Moreover, f_{P X} : P X i and f_{X} : X k i , f_{X} x : f x i are linear extensions of P X, respectively of X.

The two lemmas show that there is a bijection between triples X, f_{X}, f_{P X} and pairs f, i . We get the following consequence.

Corollary 13. The following map is a coalgebra morphism:

ϕ :  ;  ; H_{P DP} , Δ  WQSym, Δ P  _{f Lin P}f.

Lemma 14. Let P, _{1}^{P} , _{2}^{P} and Q, _{1}^{Q}, _{2}^{Q} be two packed double posets. There is a canonical isomorphism

Lin^{n} P Q _{p q n} Lin^{p} P , Lin^{q} Q , Sh p, q ,

where Sh p, q stands for the set of p, q -shuffles, which, by definition, are permutations of p q such that

σ^{1} 1  σ^{1} p , σ^{1} p 1  σ^{1} p q .

Proof. Let us assume that P l and Q k , so that P Q l k . By definition of linear extensions, if f is a linear extension of P Q, f i f j for any i l and j l, and there are no other relations between the restriction of f to l and to l 1, …, l k . In particular, the restrictions of f to l and to l 1, …, l k have disjoint images and, composing them with the packing operator defines linear extensions of P and Q l 1, …, l k . The lemma follows. □

The preceding proof implies the following result.

Proposition 15. The map ϕ defined by

ϕ :  ;  ; H_{P DP} , , Δ  WQSym, �, Δ P  _{f Lin P}f

is a Hopf algebra morphism.

Notice that, since the product of two double posets is a double poset, the image of packed double posets by ϕ is a multiplicative family (actually a multiplicative basis, see Corollary 17 below) in WQSym for the product �. This is similar to what happens with the usual product , see the construction of multiplicative bases for WQSym, in [15]. The forthcoming results below on WQSym, and its relations to H_{P DP} and WQSym, � can actually be understood as a refinement of the results in that article.

Proposition 16. For all f, g P W n , we say that f g if: (1) For all i, j n , i j and f i f j g i g j .

(2) For all i, j n , g i g j f i f j . Then is an order on P W n . Moreover, for all f P W n , we have

ϕ P_{f} _{f g} g.

Proof. The relation is clearly transitive and reflexive. Let us assume that f g and g f. By (2), for all i, j n , f i f j if, and only if, g i g j . Hence, putting k max f max g , there exists a unique permutation σ 𝔖_{k} such that, for all i k , f^{1} i g^{1} σ i . By (1), if i j, we have g i g j f i f j . Hence,

max f^{1} 1 max i n for all j i, f i f j
max i n for all j i, g i g j
max g^{1} 1
max g^{1} σ 1 ,

so σ 1 1. Iterating this, one shows that σ Id_{k}, so f g: the relation is an order. Let f, g P W n . Then we have

g Lin f  ;  ;  ;  ; for all i, j n , i j and f i f j g i g j , for all i, j n , g i g j f i f j ,

f g.
So Lin P_{f}  g P W n , f g .  □

Corollary 17. The map ϕ is a Hopf algebra isomorphism.

Here are the Hasse graphs of P W 2 , and P W 3 , .

[figure: 21; 12; 11]

[figure: 321; 221; 312; 231; 211; 212; 213; 111; 132; 121; 112; 123; 122]

Remark. If f and g are two permutations, then

f g for all i, j n , i j and f i f j g i g j
Inv f Inv g ,

where Inv f stands for the set of inversions of f. So the restriction of to 𝔖_{n} is the Bruhat order.

Definition 18. Let P P, _{1}, _{2} be a packed double poset. We assume that P, n , . A weak linear extension of P is a surjective map f : n k such that:

(1) For all i, j n , i _{1} j f i f j .

(2) For all i, j n , if i _{1} j and f i f j i j. The set of weak linear extensions of P is denoted by WLin P .

In [7], an order is defined on P W n : for all f, g P W n , f g if (1) For all i, j n , g i g j f i f j .

(2) For all i, j n , i j and g i g j f i f j . It is proved that the following map is a Hopf algebra isomorphism:

ψ :  ;  ; WQSym, �, Δ  WQSym, , Δ f  _{g f} g.

Lemma 19. Let P be a packed double poset. Then

WLin P _{f Lin P} g P W n , g f .

Proof. . Let g WLin P . For any p max g , we put P_{p} P_{g^{1} p}. Then P_{p} is a packed double poset, so there exists a unique packed word f_{p} such that P_{p} is isomorphic to P_{f_{p}}. Let us define g^{}by g^{}i f_{p} i max f_{1} max f_{p 1} for any i P_{p}; g^{}is a packed word.

We first show that g^{}Lin p . Assume that i _{1} j. Then g i g j . We claim that we also have g^{}i g^{}j :

If we do not have i j, then, as g is a weak linear extension of

P, g i g j , which implies g^{}i g^{}j . If g i g j p, then i j in P_{p}, so f_{p} i f_{p} j and finally

g^{}i g^{}j . Now, if g^{}i g^{}j , then g i g j p and f_{p} i f_{p} j , so i j in P_{p} and finally i j. Thus, we have indeed g^{}Lin P .

We finally show that g g^{}. If g^{}i g^{}j , then necessarily g i g j . Let us assume i j and g^{}i g^{}j . Then g i g j . If g i g j p, then f_{p} i f_{p} j , so j _{i} 1 and we do not have i j: this contradicts the fact that g is a weak linear extension. So g i g j , and finally g g^{}.

. Let f Lin P and g f. If i _{1} j, then f i f j , so g i g j . If moreover g i g j , as i j (because i _{1} j), we can not have f i f j as g f, so f i f j and i j. So g WLin P .

Disjoint union. Let f, f^{}Lin P , such that there exists g P W n , g f, f^{}. Let us consider i j. If f i f j , then g i g j . If f^{}i f^{}j , we would have g i g j , which is a contradiction. Hence, by symmetry,

for all i, j n such that i j, f i f j f^{}i f^{}j ,
f i f j f^{}i f^{}j .

Let us assume that i j and f i f j . Then i j, and f^{}i f^{}j . As P is isomorphic to P_{h} for a certain packed word h, i j and h i h j , so j _{1} i in P; consequently, f^{}j f^{}i and finally f^{}i f^{}j . As a conclusion, we have

for all i, j n such that i j, f i f j f^{}i f^{}j ,
f i f j f^{}i f^{}j ,
f i f j f^{}i f^{}j .

So P_{f} P_{f^{}}, which implies f f^{}. □

Proposition 20. The following map is a Hopf algebra isomorphism:

ϕ^{}ψ ϕ :  ;  ; H_{P DP}  WQSym, , Δ P_{f}  _{f WLin P}f.

Proof. Indeed, for any packed word f, by the preceding lemma we have

ψ ϕ P_{f} _{f Lin P} _{g f} g _{f WLin P}f.

By composition, ϕ^{}is an isomorphism. □

Examples. We order the packed words of degree 2 in the following way: (11,12,21).

(1) The matrices of ϕ and ϕ^{}from the basis P_{f} _{f P W 2} to the basis P W 2 are given by

{ \atop }1 0 0 0 1 0 1 1 1{ \atop },  { \atop }1 1 0 0 1 0 1 1 1{ \atop },

respectively.

(2) The matrix of the pairing of H_{P DP} in the basis P_{f} _{f P W 2} is given by

{ \atop }1 1 0 1 2 1 0 1 0{ \atop }.

(3) Via ϕ and ϕ^{}, WQSym, �, Δ and WQSym, , Δ inherit nondegenerate Hopf pairings. The matrices of these pairings in the basis P W 2 are given by

{ \atop }1 0 0 0 0 1 0 1 0{ \atop },  { \atop }\begin{matrix}1 & 1 & 0 \\ 1 & 1 & 1 \\ 0 & 1 & 0 \end{matrix}{ \atop },

respectively.

References

[1] A. Benjes, Incompatible double posets and double order polytopes, The Electronic Journal of Combinatorics 27(1) (2020), Art. P1.9, 13 pp.

[2] F. Chapoton, Algèbres de Hopf des permutoèdres, associaèdres et hypercubes, Advances in Mathematics 150 (2000), 264–275.

[3] T. Chappell, T. Friedl and R. Sanyal, Two double poset polytopes, SIAM Journal of Discrete Mathematics 31 (2017), 2378–2413.

[4] L. Foissy, Algebraic structures on double and plane posets, Journal of Algebraic Combinatorics, 37(1) (2013), 39–66.

[5] L. Foissy, Plane posets, special posets, and permutations, Advances in Mathematics, 240 (2013), 24–60.

[6] L. Foissy, Deformation of the Hopf algebra of plane posets, European Journal of Combinatorics, 38 (2014), 36–60.

[7] L. Foissy and C. Malvenuto, The Hopf algebra of finite topologies and T - partitions, Journal of Algebra, 438 (2015), 130–169.

[8] L. Foissy, C. Malvenuto and F. Patras, A theory of pictures for quasiposets, Journal of Algebra, 477 (2017), 496–515.

[9] L. Foissy, F. Patras and J.-Y. Thibon, Deformations of shuffles and quasishuffles, Annales de l’Institut Fourier, 66(1) (2016), 209–237.

[10] I. Gálvez, J. Kock and A. Tonks, Decomposition spaces and restriction species, International Mathematics Research Notices, (2018).

[11] D. Grinberg, Double posets and the antipode of QSym, Séminaire Lotharingien de Combinatoire, 78B (2017), 12p.

[12] F. Hivert, Combinatoire des fonctions quasi-symétriques, Ph.D. Thesis, 1999.

[13] D. Krob, M. Latapy, J.-C. Novelli, H. D. Phan and S. Schwer, Pseudo-permutations I: First combinatorial and lattice properties, Proceedings of the 13th Conference on Formal Power Series and Algebraic Combinatorics, Tempe, Arizona, 2001, H. Barcelo, ed., (2001).

[14] C. Malvenuto and Ch. Reutenauer, A self paired Hopf algebra on double posets and a Littlewood–Richardson rule, Journal of Combinatorial Theory. Series A, 118(4) (2011), 1322–1333.

[15] J.-C. Novelli and J.-Y. Thibon, Polynomial realizations of some trialgebras, Proceedings of the 18th Conference on Formal Power Series and Algebraic Combinatorics, San Diego, California, 2006.

[16] R. P. Stanley, Two poset polytopes, Discrete Computational Geometry, 1(1), (1986), 9–23.

[17] A. V. Zelevinsky, A generalization of the Littlewood–Richardson rule and the Robinson–Schensted–Knuth correspondence, Journal of Algebra, 69(1) (1981), 82–94.

LMPA Joseph Liouville, Université du Littoral Côte d’opale, Centre Universitaire de la Mi-Voix, 50, rue Ferdinand Buisson, CS 80699, 62228 Calais Cedex, France, email foissy@lmpa.univ-littoral.fr

Université Côte d’Azur, UMR 7351 CNRS, Parc Valrose, 06108 Nice Cedex 02 France, email patras@unice.fr