# Combinatorial Hopf Algebras and Towers of Algebras

Nantel Bergeron<fnref n="1" />† and Thomas Lam<fnref n="2" />‡ and Huilan Li<fnref n="3" />§

**Abstract.** Bergeron and Li have introduced a set of axioms which guarantee that the Grothendieck groups of a tower of algebras $\bigoplus_{n \ge 0} A_n$ can be endowed with the structure of graded dual Hopf algebras. Hivert and Nzeutzhap, and independently Lam and Shimozono constructed dual graded graphs from primitive elements in Hopf algebras. In this paper we apply the composition of these constructions to towers of algebras. We show that if a tower $\bigoplus_{n \ge 0} A_n$ gives rise to graded dual Hopf algebras then we must have $\dim(A_n) = r^n n!$ where $r = \dim(A_1)$.

**Résumé.** Bergeron et Li ont donné un ensemble d'axiomes qui garanti que les groupes de Grothendieck d'une tour d'algèbres $\bigoplus_{n \ge 0} A_n$ peuvent être dotés d'une structure d'algèbres de Hopf graduées duales. Hivert et Nzeutzhap, et indépendamment Lam et Shimozono, ont construit des graphes gradués duals à partir d'éléments primitifs dans des algèbres de Hopf. Dans cet article, nous appliquons la composition de ces constructions aux tours des algèbres. Nous prouvons que si une tour $\bigoplus_{n \ge 0} A_n$ donne des algèbres de Hopf graduées duales, alors nous devons avoir $\dim(A_n) = r^n n!$ où $r = \dim(A_1)$.

**Keywords:** graded algebra, Hopf algebra, Grothendieck group, dual graded graph

2000 Mathematics Subject Classification. Hopf algebras 16W30; Grothendieck groups 18F30.

## 1 Introduction

This paper is concerned with the interplay between towers of associative algebras, pairs of dual combinatorial Hopf algebras, and dual graded graphs. Our point of departure is the study of the composition of two constructions: (i) the construction of dual Hopf algebras from towers of algebras satisfying some axioms, due to Bergeron and Li (BL); and (ii) the construction of dual graded graphs from primitive elements in dual Hopf algebras, discovered independently by Hivert and Nzeutzhap (HN), and Lam and Shimozono:

$$ \text{tower of algebras} \rightarrow \text{combinatorial Hopf algebra} \rightarrow \text{dual graded graph} \quad (1) $$

<footnote n="1">¹Department of Mathematics and Statistics, York University, Toronto, Ontario, M3J 1P3, CANADA</footnote>

<footnote n="2">²Department of Mathematics, Harvard University, Cambridge, MA 02138, USA.</footnote>

<footnote n="3">³LaCIM, Université du Québec à Montréal, C. P. 8888, Succ. Centre-ville, Montréal, Québec, H3C 3P8, CANADA</footnote>

<footnote>†He is supported in part by CRC and NSERC.</footnote>

<footnote>‡He is partially supported by NSF grants DMS-0600677 and DMS-0652641.</footnote>

<footnote>§She is supported in part by CRC and NSERC.</footnote>
The notion of a pair $(\Gamma, \Gamma')$ dual graded graphs is likely to be the least familiar. They were introduced by Fomin (F) (see also (St)) to encode the enumerative properties of the Robinson-Schensted correspondence and its generalizations. The first arrow in (1) is obtained by using induction and restriction on the Grothendieck groups. The second arrow is obtained by using (some of the) structure constants of a combinatorial Hopf algebra as edge multiplicities for a graph. We review these constructions in Sections 2 and 3. The notion of combinatorial Hopf algebra used here is related, but slightly different from the one in (ABS).

The key example of all three classes of objects arises from the theory of symmetric functions. In (Ge), L. Geissinger showed that the ring *Sym* of symmetric functions is a graded self-dual Hopf algebra. Using the work of Frobenius and Schur, Zelevinsky (Z) interpreted the Hopf structure in terms of the Grothendieck groups of the tower of symmetric group algebras $\bigoplus_{n \ge 0} C_S_n$. Finally it follows from the classical work of Young that the branching rule for the symmetric group, or equivalently the Pieri rule for symmetric functions, gives rise to the *Young graph* on the set of partitions. The Young graph is the motivating example of dual graded graphs.

In recent years it has been shown that other graded dual Hopf algebras can be obtained from towers of algebras. In (MR) Malvenuto and Reutenauer establish the duality between the Hopf algebra *NSym* of noncommutative symmetric functions and the Hopf algebra *QSym* of quasi-symmetric functions. Krob and Thibon (KT) then showed that this duality can be interpreted as the duality of the Grothendieck groups associated with $\bigoplus_{n \ge 0} H_n(0)$ the tower of Hecke algebras at $q = 0$. For more examples, see (BHT; HNT; Se).

It is very tempting, as suggested by J. Y. Thibon, to classify all combinatorial Hopf algebras which arise as Grothendieck groups associated with a tower of algebras $\bigoplus_{n \ge 0} A_n$. The list of axioms given by the first and last author in (BL) guarantees that the Grothendieck groups of a tower of algebras form a pair of graded dual Hopf algebras. This list of axioms is not totally satisfactory as some of the axioms are difficult to verify and the description is far from a classification. In this paper we present a very surprising fact which shows that towers of algebras giving rise to combinatorial Hopf algebras are much more rigid than they appear.

**Theorem 1.1** If $A = \bigoplus_{n \ge 0} A_n$ is a tower of algebras such that its associated Grothendieck groups form a pair of graded dual Hopf algebras, then $\dim(A_n) = r^n n!$ where $r = \dim(A_1)$.

The notion of “forming a pair of graded dual Hopf algebras” is made precise in Section 2. The numbers $r^n n!$ will be familiar to experts in the theory of dual graded graphs – they count certain paths in a pair of dual graded graphs.

The rigidity proved in Theorem 1.1 suggests that there may be a structure theorem for towers of algebras which give rise to combinatorial Hopf algebras. In particular, to perform the inverse constructions of the arrows in (1), it suggests that one should study algebras related to symmetric groups (or wreath products of symmetric groups). There are many combinatorial Hopf algebras for which one may attempt to perform the inverse construction, but there are even more dual graded graphs. The general construction of (LS) produces dual graded graphs from Bruhat orders of Weyl groups of Kac-Moody algebras and it is unclear whether there are Hopf algebras, or towers of algebras giving rise to these graphs.

**Acknowledgements.** The second author would like to thank Mark Shimozono for the collaboration which led to the line of thinking in this paper.
## 2 From towers of algebras to combinatorial Hopf algebras

We recall here the work of Bergeron and Li (BL) on towers of algebras. For $B$ an arbitrary algebra we denote by $B\text{mod}$, the category of all finitely generated left $B$-modules, and by $\mathcal{P}(B)$, the category of all finitely generated projective left $B$-modules. For some category $\mathcal{C}$ of left $B$-modules ($B\text{mod}$ or $\mathcal{P}(B)$) let $\mathbf{F}$ be the free abelian group generated by the symbols $(M)$, one for each isomorphism class of modules $M$ in $\mathcal{C}$. Let $\mathbf{F}_0$ be the subgroup of $\mathbf{F}$ generated by all expressions $(M) - (L) - (N)$ one for each exact sequence

$$0 \to L \to M \to N \to 0$$

in $\mathcal{C}$. The Grothendieck group $\mathcal{K}_0(\mathcal{C})$ of the category $\mathcal{C}$ is defined by the quotient $\mathbf{F}/\mathbf{F}_0$, an abelian additive group. For $M \in \mathcal{C}$, we denote by $[M]$ its image in $\mathcal{K}_0(\mathcal{C})$. We then set

$$G_0(B) = \mathcal{K}_0(B\text{mod}) \quad \text{and} \quad K_0(B) = \mathcal{K}_0(\mathcal{P}(B)).$$

For $B$ a finite-dimensional algebra over a field $K$, let $\{V_1, \dots, V_s\}$ be a complete list of nonisomorphic simple $B$-modules. The projective covers $\{P_1, \dots, P_s\}$ of the simple modules $V_i$'s is a complete list of nonisomorphic indecomposable projective $B$-modules. We have that $G_0(B) = \bigoplus_{i=1}^s \mathbb{Z}[V_i]$ and $K_0(B) = \bigoplus_{i=1}^s \mathbb{Z}[P_i]$.

Let $\varphi: B \to A$ be an injection of algebras preserving unities, and let $M$ be a (left) $A$-module and $N$ a (left) $B$-module. The induction of $N$ from $B$ to $A$ is $\text{Ind}_B^A N = A \otimes_{\varphi} N$, the (left) $A$-module $A \otimes N$ modulo the relations $a \otimes bn \equiv a\varphi(b) \otimes n$, and the restriction of $M$ from $A$ to $B$ is $\text{Res}_B^A M = \text{Hom}_A(A, M)$, the (left) $B$-module with the $B$-action defined by $bf(a) = f(a\varphi(b))$.

Let $A = \bigoplus_{n \ge 0} A_n$ be a graded algebra over $\mathbb{C}$ with multiplication $\rho: A \otimes A \to A$. Bergeron and Li studied five axioms for $A$ (we refer to (BL) for full details):

(1) For each $n \ge 0$, $A_n$ is a finite-dimensional algebra by itself with (internal) multiplication $\mu_n: A_n \otimes A_n \to A_n$ and unit $1_n$. $A_0 \cong \mathbb{C}$.

(2) The (external) multiplication $\rho_{m,n}: A_m \otimes A_n \to A_{m+n}$ is an injective homomorphism of algebras, for all $m$ and $n$ (sending $1_m \otimes 1_n$ to $1_{m+n}$).

(3) $A_{m+n}$ is a two-sided projective $A_m \otimes A_n$-module with the action defined by $a \cdot (b \otimes c) = a\rho_{m,n}(b \otimes c)$ and $(b \otimes c) \cdot a = \rho_{m,n}(b \otimes c)a$, for all $m, n \ge 0$, $a \in A_{m+n}$, $b \in A_m$, $c \in A_n$ and $m, n \ge 0$.

(4) A relation between the decomposition of $A_{n+m}$ as a left $A_m \otimes A_n$-module and as a right $A_m \otimes A_n$-module holds.

(5) An analogue of Mackey's formula relating induction and restriction of modules holds.

We say here that $A = \bigoplus_{n \ge 0} A_n$ is a *tower of algebras* if it satisfies Conditions (1), (2) and (3). Condition (1) guarantees that the Grothendieck groups

$$G(A) = \bigoplus_{n \ge 0} G_0(A_n) \quad \text{and} \quad K(A) = \bigoplus_{n \ge 0} K_0(A_n)$$

are graded connected. Conditions (2) and (3) ensure that induction and restriction are well defined on $G(A)$ and $K(A)$, defining a multiplication and comultiplication, as follows. For $[M] \in G_0(A_m)$ (or $K_0(A_m)$) and $[N] \in G_0(A_n)$ (or $K_0(A_n)$) we let

$$[M][N] = [\text{Ind}_{A_m \otimes A_n}^{A_{m+n}} M \otimes N] \quad \text{and} \quad \Delta([N]) = \sum_{k+l=n} [\text{Res}_{A_k \otimes A_l}^{A_{k+l}} N].$$
The pairing between $K(A)$ and $G(A)$ is given by $\langle , \rangle : K(A) \times G(A) \to \mathbb{Z}$ where

$$ \langle [P], [M] \rangle = \begin{cases} \dim_K(\operatorname{Hom}_{A_n}(P, M)) & \text{if } [P] \in K_0(A_n) \text{ and } [M] \in G_0(A_n), \\ 0 & \text{otherwise.} \end{cases} $$

Thus with (only) Conditions (1), (2), and (3), $G(A)$ and $K(A)$ are dual free $\mathbb{Z}$-modules both endowed with a multiplication and comultiplication. Bergeron and Li (BL) prove

**Theorem 2.1** If a graded algebra $A = \bigoplus_{n \ge 0} A_n$ over $\mathbb{C}$ satisfies Conditions (1)-(5) then $G(A)$ and $K(A)$ are graded dual Hopf algebras.

In particular Theorem 1.1 applies to graded algebras which satisfy Conditions (1)-(5). Note that the dual Hopf algebras $G(A)$ and $K(A)$ come with distinguished bases consisting of the isomorphism classes of simple and indecomposable projective modules.

## 3 From combinatorial Hopf algebras to dual graded graphs

This section recounts work of Fomin (F), Hivert and Nzeutchap (HN), and Lam and Shimozono. A graded graph $\Gamma = (V, E, h, m)$ consists of a set of vertices $V$, a set of (directed) edges $E \subset V \times V$, a height function $h: V \to \{0, 1, \dots\}$ and an edge multiplicity function $m: V \times V \to \{0, 1, \dots\}$. If $(v, u) \in E$ is an edge then we must have $h(u) = h(v)+1$. The multiplicity function determines the edge set: $(v, u) \in E$ if and only if $m(v, u) \neq 0$. We assume always that there is a single vertex $v_0$ of height 0.

Let $\mathbb{Z}V = \bigoplus_{v \in V} \mathbb{Z}v$ be the free $\mathbb{Z}$-module generated by the vertex set. Given a graded graph $\Gamma = (V, E, h, m)$ we define up and down operators $U, D: \mathbb{Z}V \to \mathbb{Z}V$ by

$$ U_{\Gamma}(v) = \sum_{u \in V} m(v, u) u \qquad D_{\Gamma}(v) = \sum_{u \in V} m(u, v) u $$

and extending by linearity over $\mathbb{Z}$. We will assume that $\Gamma$ is locally-finite, so that these operators are well defined. A pair $(\Gamma, \Gamma')$ of graded graphs with the same vertex set $V$ and height function $h$ is called dual with differential coefficient $r$ if we have

$$ D_{\Gamma'}U_{\Gamma} - U_{\Gamma}D_{\Gamma'} = r \operatorname{Id}. $$

We shall need the following result of Fomin. For a graded graph $\Gamma$, let $f_{\Gamma}^v$ denote the number of paths from $v_0$ to $v$, where for two vertices $w, u \in V$, we think that there are $m(w, u)$ edges connecting $w$ to $u$.

**Theorem 3.1 (Fomin (F))** Let $(\Gamma, \Gamma')$ be a pair of dual graded graphs with differential coefficient $r$. Then

$$ r^n n! = \sum_{v:h(v)=n} f_{\Gamma}^v f_{\Gamma'}^v. $$

Let $H_{\bullet} = \bigoplus_{n \ge 0} H_n$ and $H^{\bullet} = \bigoplus_{n \ge 0} H^n$ be graded dual Hopf algebras over $\mathbb{Z}$ with respect to the pairing $\langle \cdot, \cdot \rangle : H_{\bullet} \times H^{\bullet} \to \mathbb{Z}$. We assume that we are given dual sets of homogeneous free $\mathbb{Z}$-module generators $\{p_{\lambda} \in H_{\bullet}\}_{\lambda \in \Lambda}$ and $\{s_{\lambda} \in H^{\bullet}\}_{\lambda \in \Lambda}$, such that all structure constants are non-negative integers. We also assume that $\dim(H_i) = \dim(H^i) < \infty$ for each $i \ge 0$ and $\dim(H_0) = \dim(H^0) = 1$, so that $H_0$ and $H^0$ are spanned by distinguished elements the unit 1. Let us suppose we are given non-zero
homogeneous elements $\alpha \in H_1$ and $\beta \in H^1$ of degree 1 such that $\alpha p_\mu$ (resp. $\beta s_\mu$) is a linear combination of $\{p_\lambda\}$ (resp. $\{s_\lambda\}$) with nonnegative integer coefficients for any $\mu \in \Lambda$.

We now define a graded graph $\Gamma(\beta) = (V, E, h, m)$ where $V = \{s_\lambda\}_{\lambda \in \Lambda}$ and $h: V \to \mathbb{Z}$ is defined by $h(s_\lambda) = \deg(s_\lambda)$. The map $m: V \times V \to \mathbb{Z}$ is defined by

$$m(s_{\lambda}, s_{\mu}) = \langle p_{\mu}, \beta s_{\lambda} \rangle = \langle \Delta(p_{\mu}), \beta \otimes s_{\lambda} \rangle$$

and $E$ is determined by $m$. The graph $\Gamma(\beta)$ is graded because of the assumption that $\beta$ has degree 1. Similarly, we define a graded graph $\Gamma'(\alpha) = (V', E', h', m')$ where $V' = V$, $h' = h$, and

$$m'(s_{\lambda}, s_{\mu}) = \langle \alpha p_{\lambda}, s_{\mu} \rangle = \langle \alpha \otimes p_{\lambda}, \Delta(s_{\mu}) \rangle.$$

The following theorem is due independently to Hivert and Nzeutchap (HN) and Lam and Shimozono (unpublished).

**Theorem 3.2** The graded graphs $\Gamma = \Gamma(\beta)$ and $\Gamma' = \Gamma'(\alpha)$ form a pair of dual graded graphs with differential coefficient $\langle \alpha, \beta \rangle$.

**Proof:** We identify $\mathbb{Z}V$ with $H^\bullet$ and note that $U_\Gamma(x) = \beta x$ where $x \in H^\bullet$ and we use the multiplication in $H^\bullet$. Also,

$$D_{\Gamma'}(x) = \sum_{\mu \in \Lambda} \langle \alpha \otimes p_{\mu}, \Delta x \rangle s_{\mu} = \sum \langle \alpha, x^{(1)} \rangle x^{(2)},$$

where $\Delta x = \sum x^{(1)} \otimes x^{(2)}$. Now observe that by our hypotheses on the degree of $\alpha$ and $\beta$ they are primitive elements: $\Delta \alpha = 1 \otimes \alpha + \alpha \otimes 1$ and $\Delta \beta = 1 \otimes \beta + \beta \otimes 1$. We first calculate

$$\langle \alpha, \beta x \rangle = \langle \Delta \alpha, \beta \otimes x \rangle = \langle 1, \beta \rangle \langle \alpha, x \rangle + \langle \alpha, \beta \rangle \langle 1, x \rangle = \langle \alpha, \beta \rangle \langle 1, x \rangle$$

and then compute

$$\begin{aligned} D_{\Gamma'} U_{\Gamma}(x) &= D_{\Gamma'}(\beta x) \\ &= \sum (\langle \alpha, \beta x^{(1)} \rangle x^{(2)} + \langle \alpha, x^{(1)} \rangle \beta x^{(2)}) \\ &= \langle \alpha, \beta \rangle x + U_{\Gamma} D_{\Gamma'}(x) \end{aligned}$$

where to obtain $\langle \alpha, \beta \rangle x$ in the last line we use $\Delta x = 1 \otimes x + \text{terms of other degrees.}$ $\square$

# 4 Proof of Theorem 1.1

We are given a graded algebra $A = \bigoplus_{n \ge 0} A_n$ over $\mathbb{C}$ with multiplication $\rho$ satisfying Conditions (1), (2) and (3). Moreover we assume that the two Grothendieck groups $G(A)$ and $K(A)$ form a pair of graded dual Hopf algebras as in Section 2. Under these assumptions we show that

$$\dim(A_n) = r^n n!$$

where $r = \dim(A_1)$.

Let $H^\bullet = G(A)$ and $H_\bullet = K(A)$. Let $\{s_1^{(1)} = [S_1^{(1)}], \dots, s_t^{(1)} = [S_t^{(1)}]\}$ and $\{p_1^{(1)} = [P_1^{(1)}], \dots, p_t^{(1)} = [P_t^{(1)}]\}$ denote the isomorphism classes of simple and indecomposable projective $A_1$-modules, so that
$H^1 = \bigoplus_{i=1}^t \mathbb{Z}s_i^{(1)}$ and $H_1 = \bigoplus_{i=1}^t \mathbb{Z}p_i^{(1)}$. Define $a_i = \dim(S_i^{(1)})$ and $b_i = \dim(P_i^{(1)})$ for $1 \le i \le t$. We set for the remainder of this paper

$$ \alpha = \sum_{i=1}^{t} a_i p_i^{(1)} \in H_1 \quad \text{and} \quad \beta = \sum_{i=1}^{t} b_i s_i^{(1)} \in H^1. $$

Since $A_0 \cong \mathbb{C}$, we let $s_1^{(0)}$ (respectively, $p_1^{(0)}$) be the unique simple (respectively, indecomposable projective) module representative in $H^0$ (respectively, $H_0$). Similarly, let $\{s_i^{(n)} = [S_i^{(n)}]\}$ be all isomorphic classes of simple $A_n$-modules and $\{p_i^{(n)} = [P_i^{(n)}]\}$ be all isomorphism classes of indecomposable projective $A_n$-modules. The sets $\cup_{n \ge 0} \{s_i^{(n)}\}$ and $\cup_{n \ge 0} \{p_i^{(n)}\}$ form dual free $\mathbb{Z}$-module bases of $H^\bullet$ and $H_\bullet$.

Now define $\Gamma = \Gamma(\beta)$ and $\Gamma' = \Gamma'(\alpha)$ as in Section 3.

**Lemma 4.1** We have

$$ f_{\Gamma}^{s_j^{(n)}} = \dim P_j^{(n)} \quad \text{and} \quad f_{\Gamma'}^{s_j^{(n)}} = \dim S_j^{(n)}. $$

**Proof:** We have

$$ m(s_i^{(n-1)}, s_j^{(n)}) = \sum_{l=1}^{t} b_l c_l, $$

where $c_l$ is the number of copies of the indecomposable projective module $P_l^{(1)} \otimes P_i^{(n-1)}$ as a summand in $\mathrm{Res}_{A_1 \otimes A_{n-1}}^{A_n} P_j^{(n)}$. Note that $s_1^{(0)}$ is the unit of $H^\bullet$ and $m(s_1^{(0)}, s_i^{(1)}) = b_i = \dim P_i^{(1)}$ for all $1 \le i \le t$. The dimension of an indecomposable projective module $P_j^{(n)}$ is given by

$$ \dim P_j^{(n)} = \sum_{i,l} c_l \dim (P_l^{(1)} \otimes P_i^{(n-1)}) = \sum_i m(s_i^{(n-1)}, s_j^{(n)}) \dim P_i^{(n-1)}. $$

By induction on $n$, we deduce that $\dim P_j^{(n)}$ is the number of paths from $s_1^{(0)}$ to $s_j^{(n)}$ in $\Gamma$. The claim for $\Gamma'$ is similar. $\square$

For any finite dimensional algebra $B$ let $\{S_\lambda\}_\lambda$ be a complete set of simple $B$-modules. For each $\lambda$ let $P_\lambda$ be the projective cover of $S_\lambda$. It is well known (see (CR)) that we can find minimal idempotents $\{e_i\}$ such that $B = \bigoplus Be_i$ where each $Be_i$ is isomorhic to a $P_\lambda$. Moreover, the quotient of $B$ by its radical shows that the multiplicity of $P_\lambda$ in $B$ is equal to $\dim S_\lambda$. This implies the following lemma.

**Lemma 4.2** Let $B$ be a finite dimensional algebra and $\{S_\lambda\}_\lambda$ be a complete set of simple $B$-modules.

$$ \dim B = \sum_{\lambda} (\dim P_{\lambda})(\dim S_{\lambda}), $$

where $P_\lambda$ is the projective cover of $S_\lambda$.

By Lemma 4.2, we have $r = \sum_{i=1}^t a_i b_i = \langle \alpha, \beta \rangle$. By Theorem 3.2 we may apply Theorem 3.1 to $(\Gamma, \Gamma')$. Using Lemma 4.2 and Lemma 4.1, Theorem 3.1 says

$$ \dim(A_n) = \sum_i (\dim P_i^{(n)})(\dim S_i^{(n)}) = \sum_i f_{\Gamma}^{s_i^{(n)}} f_{\Gamma'}^{s_i^{(n)}} = r^n n!. $$
**Remark 4.3** If the tower consists of semisimple algebras $A_i$ then $\Gamma = \Gamma'$ so we obtain a self-dual graph. In this case the graph would be a weighted version of a differential poset in the sense of Stanley (St). If furthermore the branching of irreducible modules from $A_n$ to $A_1 \otimes A_{n-1}$ is multiplicity free then we get a true differential poset.

**Remark 4.4** The Hopf algebras $H^\bullet$ and $H_\bullet$ are not in general commutative and co-commutative. Thus in the definitions of Section 3 we could have obtained a different pair of dual graded graphs by setting $m(s_\lambda, s_\mu) = \langle p_\mu, s_\lambda \beta \rangle$ or $m'(s_\lambda, s_\mu) = \langle p_\lambda \alpha, s_\mu \rangle$.

## References

[ABS] M. Aguiar, N. Bergeron, and F. Sottile, *Combinatorial Hopf algebras and generalized Dehn-Sommerville relations*, Compos. Math. **142** (2006), no. 1, 1–30.

[BHT] N. Bergeron, F. Hivert and J. Y. Thibon, *The peak algebra and the Hecke-Clifford algebras at $q=0$*. J. Combin. Theory Ser. A **107-1** (2004) 1–19.

[BL] N. Bergeron and H. Li, *Algebraic Structures on Grothendieck Groups of a Tower of Algebras*, To appear. [arXiv:math/0612170].

[CR] C. Curtis and I. Reiner, *Methods of representation theory. Vol. I. With applications to finite groups and orders*, John Wiley & Sons, Inc., New York, 1990.

[F] S. Fomin, *Duality of graded graphs*, J. Algebraic Combin. **3** (1994), no. 4, 357–404.

[Ge] L. Geissinger, *Hopf algebras of symmetric functions and class functions*, Combinatoire et Combinatoire et représentation du groupe symétrique (Actes Table Ronde C.N.R.S., Univ. Louis-Pasteur Strasbourg, Strasbourg, 1976), pp. 168–181. Lecture Notes in Math., Vol. 579, Springer, Berlin, 1977.

[HNT] F. Hivert, J.-C. Novelli and J.-Y. Thibon, *Representation theory of the 0-Ariki-Koike-Shoji algebras*, to appear. [math.CO/0407218].

[HN] F. Hivert and J. Nzeutchap, *Dual Graded Graphs in Combinatorial Hopf Algebras*, in preparation.

[KT] D. Krob and J. Y. Thibon, *Noncommutative symmetric functions. IV. Quantum linear groups and Hecke algebras at $q=0$*, J. Algebraic Combin. **6-4** (1997) 339–376.

[LS] T. Lam and M. Shimozono, *Dual graded graphs for Kac-Moody algebras*, Algebra and Number Theory, to appear. [math.CO/0702090].

[MR] C. Malvenuto and C. Reutenauer, *Duality between quasi-symmetric functions and the solomon descent algebra*, J. Algebra **177-3** (1995) 967–982.

[Se] A. N. Sergeev, *Tensor algebra of the identity representation as a module over the Lie superalgebras $GL(n;m)$ and $Q(n)$*, Math. USSR Sbornik **51** (1985) 419–427.

[St] R. Stanley, *Differential posets*, J. Amer. Math. Soc. **1** (1988), 919–961.

[Z] A. V. Zelevinsky, *Representations of finite classical groups. A Hopf algebra approach*, Lecture Notes in Mathematics 869. Springer-Verlag, Berlin-New York, 1981.