# Dual filtered graphs

Rebecca Patrias, Pavlo Pylyavskyy

► To cite this version:

Rebecca Patrias, Pavlo Pylyavskyy. Dual filtered graphs. 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015), Jul 2015, Daejeon, South Korea. pp.1-12, 10.46298/dmtcs.2515. hal-01337847

HAL Id: hal-01337847

https://hal.science/hal-01337847

Submitted on 27 Jun 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Dual filtered graphs

Rebecca Patrias† and Pavlo Pylyavskyy‡

School of Mathematics, University of Minnesota, Minneapolis, MN 55455, USA

**Abstract.** We define a *K*-theoretic analogue of Fomin's dual graded graphs, which we call dual filtered graphs. The key formula in the definition is $DU - UD = D + I$. Our major examples are *K*-theoretic analogues of Young's lattice, the binary tree, and the graph determined by the Poirier-Reutenauer Hopf algebra. Most of our examples arise via two constructions, which we call the Pieri construction and the Möbius construction. The Pieri construction is closely related to the construction of dual graded graphs from a graded Hopf algebra, as described in Bergeron-Lam-Li, Nzeutchap, and Lam-Shimozono. The Möbius construction is more mysterious but also potentially more important, as it corresponds to natural insertion algorithms.

**Résumé.** Nous définissons un analogue *K*-théorique aux graphes gradués en dualité de Fomin que nous appelons les graphes filtrés en dualité. La formule importante pour la définition est $DU - UD = D + I$. Nos principaux exemples sont un analogue *K*-théorique aux graphe de Young, l'arbre binaire, et un graphe déterminé par l'algèbre de Hopf de Poirier-Reutenauer. La plupart de nos exemples surviennent de deux constructions que nous appelons la construction de Pieri et la construction de Möbius. La construction de Pieri est étroitement liée à la construction des graphes gradués en dualité d'une algèbre graduée de Hopf à la Bergeron-Lam-Li, Nzeutchap, et Lam-Shimozono. La construction de Möbius est plus mystérieuse, mais aussi peut-être plus importante car cette construction correspond aux algorithmes d'insertion naturelles.

**Keywords:** dual graded graphs, *K*-theory, bialgebras

## 1 Introduction

Fomin's dual graded graphs (Fomin (1994)), as well as their predecessors - Stanley's differential posets (Stanley (1988)), were invented as a tool to better understand the Robinson-Schensted insertion algorithm. Dual graded graphs are significant in the areas where the Robinson-Schensted correspondence appears, for example in Schubert calculus or in the study of representations of towers of algebras (Begeron et al. (2012); Björner and Stanley). A recent work of Lam and Shimozono (2007) associates a dual graded graph to any Kac-Moody algebra, bringing their study to a new level of generality.

<footnote>†Email: patrio80@umn.edu. R.P. was supported by NSF grant DMS-1148634.</footnote>

<footnote>‡Email: ppylyavs@umn.edu. P.P. was supported by NSF grants DMS-1068169, DMS-1148634, DMS-1351590, and Sloan Fellowship.</footnote>
## 1.1 Weyl algebra and its deformations

One way to view the theory is as a study of certain combinatorial representations of the first Weyl algebra. Let us briefly recall the definitions. The Weyl algebra, or the first Weyl algebra, is an algebra over some field $K$ (usually $K = \mathbb{R}$) generated by two generators $U$ and $D$ with a single relation $DU - UD = 1$. It was originally introduced by Hermann Weyl in his study of quantum mechanics. We refer the reader to Bjork (1979), for example, for more background on the Weyl algebra.

A graded graph is a triple $G = (P, \rho, E)$, where $P$ is a discrete set of vertices, $\rho: P \to \mathbb{Z}$ is a rank function, and $E$ is a multiset of edges/arcs $(x, y)$, where $\rho(y) = \rho(x) + 1$. In other words, each vertex is assigned a rank, and edges can only join vertices in successive ranks. For the set of vertices $P$, let $P_n$ denote the subset of vertices of rank $n$. For any field $K$ of characteristic zero, the formal linear combinations of vertices of $G$ form the vector space $KP$.

Let $G_1 = (P, \rho, E_1)$ and $G_2 = (P, \rho, E_2)$ be a pair of graded graphs with a common vertex set and rank function. From this pair, define an oriented graded graph $G = (P, \rho, E_1, E_2)$ by orienting the edges of $G_1$ in the direction of increasing rank and the edges of $G_2$ in the direction of decreasing rank. Let $a_i(x, y)$ denote the number of edges of $E_i$ joining $x$ and $y$ or the multiplicity of edge $(x, y)$ in $E_i$. We define the *up* and *down* operators $U, D \in \text{End}(KP)$ associated with graph $G$ by

$$ Ux = \sum_{y} a_{1}(x, y)y $$

and

$$ Dy = \sum_{x} a_{2}(x, y)x. $$

Graded graphs $G_1$ and $G_2$ with a common vertex set and rank function are said to be *dual* if

$$ DU - UD = I, $$

where $I$ is an identity operator acting on $KP$. Thus, we see that $KP$ is a representation of the Weyl algebra. Furthermore, it is a representation of a very special kind, where $U$ and $D$ act in a particularly nice combinatorial way on a fixed basis.

One would then expect that variations of the Weyl algebra would correspond to some variations of the theory of dual graded graphs. One such variation is the *q-Weyl algebra* defined by the relation

$$ DU - qUD = 1. $$

The corresponding theory of *quantum dual graded graphs* was pursued in Lam (2010).

In this paper, we shall study the theory arising from an analogue $W$ of the Weyl algebra with defining relation

$$ DU - UD = D + 1. $$

We shall refer to it as the *Ore algebra* Ore (1933), and we shall see that it is a very natural object. In particular, the corresponding theory of *dual filtered graphs* fits naturally with the existing body of work on the $K$-theory of Grassmannians.

Note that it is easy to see that by rescaling $U$ and $D$, we can pass from arbitrary $DU - UD = \alpha D + \beta$ to $DU - UD = D + I$. We thus suffer no loss in generality by writing down the relation in the latter form.
## 1.2 Pieri and Möbius constructions

We make use of two conceptual ways to build examples of dual filtered graphs. The first construction starts with an algebra $A$, a derivation $D$ on $A$, and an element $f \in A$ such that $D(f) = f + 1$. We often build the desired derivation $D$ using a bialgebra structure on $A$. This construction is very close to an existing one in the literature (Begeron et al. (2012); Nzeutchap (2006); Lam and Shimozono), where dual graded graphs are constructed from graded Hopf algebras. In fact, if we were to require $D(f) = 1$, we would get dual graded graphs instead of dual filtered graphs in our construction. We refer to this method as the *Pieri construction* or sometimes as the *Pieri deformation*.

Instead, we can also start with an existing dual graded graph $G = (P, \rho, E_1, E_2)$ (see definition below), composed of graphs $G_1 = (P, \rho, E_1)$ and $G_2 = (P, \rho, e_2)$, and adjust $E_1$ and $E_2$ in the following manner. To obtain $G'_1$, we add $\#\{x|y$ covers $x$ in $G_1\}$ loops at each vertex $y \in P$ to $E_1$. As for $G'_2$, we create a new edge set $E'_2$ by forming

$$a'_2(x, y) = |\mu(x, y)|$$

edges between vertices $x$ and $y$, where $\mu$ denotes the Möbius function in $G_2 = (P, \rho, E_2)$. We refer to this construction as the *Möbius construction* or *Möbius deformation*. Note that this does not always produce a pair of dual filtered graphs, and it is mysterious to determine when it does. In some major examples, however, it is the result of this construction that relates to Robinson-Schensted-like algorithms, for example to *Hecke insertion* of Buch et al. (2008).

The following observation seems remarkable, and we call it the *Möbius via Pieri phenomenon*. Let $A$ be a graded Hopf algebra, and let bialgebra $\tilde{A}$ be its $K$-theoretic deformation in some appropriate sense which we do not know how to formalize. Let $G$ be a natural dual graded graph associated with $A$. What we observe is that applying the Möbius construction to $G$ yields the same result as a natural Pieri construction applied to $\tilde{A}$. In other words, the following diagram commutes.

<figure><img src="image_2.png" /></figure>

This happens for Young's lattice, see Section 4.4, and for the binary tree dual graded graph, see Section 5.1.

The crucial condition necessary for this phenomenon to be observed is for $A$ to be the associated graded algebra of $\tilde{A}$, but this is not always the case. For example, this is not the case for the $K$-theoretic analogue of the Poirier-Reutenauer Hopf algebra, see Section 5.3. To put it simply, the numbers of basis elements for the filtered components of $A$ and $\tilde{A}$ are distinct in those cases, thus there is no hope to obtain corresponding graphs one from the other via Möbius construction. Interestingly, those are exactly the examples we found where the Möbius construction fails to produce a dual filtered graph.

# 2 Dual graded graphs

This section follows Fomin (1994), and we refer the reader to this source for further reading.

A graded graph is a triple $G = (P, \rho, E)$, where $P$ is a discrete set of vertices, $\rho: P \to \mathbb{Z}$ is a rank function, and $E$ is a multiset of edges/arcs $(x, y)$, where $\rho(y) = \rho(x) + 1$. In other words, each vertex
is assigned a rank, and edges can only join vertices in successive ranks. For any field $K$ of characteristic zero, the formal linear combinations of vertices of $G$ form the vector space $KP$.

**Example 2.1** Young's lattice is an example of a graded graph where for any partition $\lambda$, $\rho(\lambda) = |\lambda|$, and there is an edge from $\lambda$ to $\mu$ if $\mu$ can be obtained from $\lambda$ by adding one box. Ranks zero through four are shown below. We see that $(3, 31) \in E$ and $\rho(3) + 1 = 3 + 1 = \rho(31) = 4$.

<figure><img src="image_3.png" /></figure>

Let $G_1 = (P, \rho, E_1)$ and $G_2 = (P, \rho, E_2)$ be a pair of graded graphs with a common vertex set and rank function. From this pair, define an *oriented graded graph* $G = (P, \rho, E_1, E_2)$ by orienting the edges of $G_1$ in the direction of increasing rank and the edges of $G_2$ in the direction of decreasing rank. Let $a_i(x, y)$ denote the number of edges of $E_i$ joining $x$ and $y$ or the multiplicity of edge $(x, y)$ in $E_i$. We define the *up* and *down* operators $U, D \in \text{End}(KP)$ associated with graph $G$ by

$$Ux = \sum_{y} a_{1}(x, y)y$$

and

$$Dy = \sum_{x} a_{2}(x, y)x.$$

For example, in Young's lattice shown above, $U(21) = 31 + 22 + 211$ and $D(21) = 2 + 11$.

Graded graphs $G_1$ and $G_2$ with a common vertex set and rank function are said to be *dual* if

$$DU - UD = I.$$

**Example 2.2** Young's lattice is an example of a self-dual graded graph.

## 3 Dual filtered graphs

A weak filtered graph is a triple $G = (P, \rho, E)$, where $P$ is a discrete set of vertices, $\rho: P \to \mathbb{Z}$ is a rank function, and $E$ is a multiset of edges/arcs $(x, y)$, where $\rho(y) \ge \rho(x)$. A strict filtered graph is a triple $G = (P, \rho, E)$, where $P$ is a discrete set of vertices, $\rho: P \to \mathbb{Z}$ is a rank function, and $E$ is a multiset of edges/arcs $(x, y)$, where $\rho(y) > \rho(x)$. Let $P_n$ as before denote the subset of vertices of rank $n$.

Let $G_1 = (P, \rho, E_1)$ and $G_2 = (P, \rho, E_2)$ be a pair of filtered graphs with a common vertex set, $G_1$ weak while $G_2$ strict. From this pair, define an *oriented filtered graph* $G = (P, E_1, E_2)$ by orienting the edges of $G_1$ in the positive filtration direction and the edges of $G_2$ in the negative filtration direction. Recall that $a_i(x, y)$ denotes the number of edges of $E_i$ joining $x$ and $y$ or the multiplicity of edge $(x, y)$
in $E_i$. Using the *up* and *down* operators associated with graph $G$ as previously defined, we say that $G_1$ and $G_2$ are dual filtered graphs if

$$DU - UD = D + I.$$

In the next sections, we describe three constructions of dual filtered graphs. For proofs of the following results, see Patrias and Pylyavskyy (2014b).

## 3.1 Trivial construction

Every dual graded graph has an easy deformation that makes it a dual filtered graph. To construct it, simply add $\rho(x)$ “upward” loops to each element $x$ of the dual graded graph, where $\rho$ is the rank function. We will call this the *trivial construction*.

**Theorem 3.1** For any dual graded graph $G$, the trivial construction gives a dual filtered graph $G'$.

**Example 3.2** The trivial construction for the first four ranks of Young's lattice is shown below. The edges in the graph on the left are oriented upward, and the edges in the graph on the right are oriented downward.

<figure><img src="image_4.png" /></figure>

<figure><img src="image_5.png" /></figure>

## 3.2 Pieri construction

The following construction is close to the one for dual graded graphs described in the works of Begeron et al. (2012), Nzeutchap (2006), and Lam and Shimozono.

Let

$$A = \bigoplus_{i \ge 0} A_i$$

be a filtered, commutative algebra over a field $\mathbb{F}$ with $A_0 = \mathbb{F}$ and a linear basis $a_\lambda \in A_{|\lambda|}$. Here, the $\lambda$'s belong to some infinite indexing set $P$, where each graded component, $P_i = \{\lambda \mid |\lambda| = i\}$, is finite. The property of being filtered means that $a_\lambda a_\mu = \sum c_\nu a_\nu$, where $|\lambda| + |\mu| \le |\nu|$.

Let $f = f_1 + f_2 + \dots \in \hat{A}$ be an element of the completion $\hat{A}$ of $A$ such that $f_i \in A_i$. Assume $D \in \text{End}(A)$ is a derivation on $A$ satisfying $D(f) = f + 1$.

To form a graph, we define $E_1$ by defining $a_1(\lambda, \mu)$ to be the coefficient of $a_\lambda$ in $D(a_\mu)$. We also define $E_2$ by defining $a_2(\lambda, \mu)$ to be the coefficient of $a_\mu$ in $a_\lambda f$.

**Theorem 3.3** The resulting graph is a dual filtered graph.

The result follows from $D(fa_\lambda) = D(f)a_\lambda + fD(a_\lambda)$, or $D(fa_\lambda) - fD(a_\lambda) = a_\lambda + D(a_\lambda)$.

Now, assume $A_1$ is one-dimensional, and let $g$ be its generator. We shall often find a derivation $D$ from a bialgebra structure on $A$. Indeed, assume $\Delta$ is a coproduct on $A$ such that $\Delta(a) = 1 \otimes a + a \otimes 1 + \dots$, where the rest of the terms lie in $(A_1 \oplus A_2 \oplus \dots) \otimes (A_1 \oplus A_2 \oplus \dots)$. Assume also $\xi$ is a map $A \otimes A \to A$ such that $\xi(p \otimes g) = p$ and for any element $q \in A_i$, $i \ne 1$, we have $\xi(p \otimes q) = 0$.

**Lemma 3.4** The map $D(a) = \xi(\Delta(a))$ is a derivation.
## 3.3 Möbius construction

Let $G = (P, \rho, E_1, E_2)$ be a dual graded graph. From $G$, form a pair of filtered graphs as follows. Let $G'_1 = (P, \rho, E'_1)$ have the set of edges $E'_1$ consisting of the same edges as $E_1$ plus $\#\{x|y$ covers $x$ in $G_1\}$ loops at each vertex $y \in P$. Let $G'_2 = (P, \rho, E'_2)$ have the set of edges $E'_2$ consisting of $a'_2(x, y) = |\mu(x, y)|$ edges between vertices $x$ and $y$, where $\mu$ denotes the Möbius function in $(P, \rho, E_2)$. Compose $G'_1$ and $G'_2$ into an oriented filtered graph $\tilde{G}$.

In many cases, including that of Young's lattice, the Möbius construction results in a dual filtered graph. However, it does not always do so. Unlike with the Pieri construction, we do not have the algebraic machinery explaining why this is so. Instead, we provide the proofs on a case-by-case basis. Nevertheless, the Möbius construction is the most important one, as it is this construction that relates to insertion algorithms and thus to K-theory of Grassmannians and Lagrangian Grassmannians.

# 4 Young's lattice

## 4.1 A Pieri deformation of Young's lattice

Let $A = \Lambda$ be the ring of symmetric functions. Let $s_\lambda$, $p_\lambda$, and $h_\lambda$ be its bases of Schur functions, power sum symmetric functions, and complete homogeneous symmetric functions. Let

$$f = h_1 + h_2 + \dots$$

Define up and down edges of a filtered graph $G = (P, \rho, E_1, E_2)$ by letting $a_1(\mu, \nu)$ be the coefficient of $s_\nu$ in $p_1 s_\mu$, and $a_2(\mu, \nu)$ be the coefficient of $s_\nu$ in $f s_\mu$.

Recall that given two partitions, $\mu$ and $\nu$, $\mu/\nu$ forms a horizontal strip if no two boxes of $\mu/\nu$ lie in the same column. For example, $(4, 2, 1)/(2, 1)$ forms a horizontal strip while $(4, 3, 1)/(2, 1)$ does not.

**Lemma 4.1** *The up edges $E_1$ coincide with those of Young's lattice, while the down edges $E_2$ connect shapes that differ by a horizontal strip.*

In the figure below, the first six ranks are shown. The edges in the graph on the left are upward-oriented, and the edges on the graph on the right are downward-oriented.

<figure><img src="image_6.png" /></figure>

<figure><img src="image_7.png" /></figure>

**Theorem 4.2** *The Pieri deformation of Young's lattice is a dual filtered graph.*

We prove this theorem using the fact the $\Lambda$ is a free polynomial ring in $p_1, p_2, \dots$, which can be endowed with a standard bilinear inner product determined by $\langle s_\lambda, s_\mu \rangle = \delta_{\lambda,\mu}$. We then show that for any $h, g \in \Lambda$ we have $\langle g, p_1 h \rangle = \langle \frac{d}{dp_1} g, h \rangle$ and $\frac{d}{dp_1} f = f + 1$. Now, we see that $A = \Lambda$, $a_\lambda = s_\lambda$, $D = \frac{d}{dp_1}$, and $f = h_1 + h_2 + \dots$ satisfy the conditions of Theorem 3.3. The claim follows.
## 4.2 Möbius deformation of Young's lattice

Given two partitions, $\lambda$ and $\nu$, $\lambda/\nu$ forms a rook strip if no two boxes of $\lambda/\nu$ lie in the same row and no two boxes of $\lambda/\nu$ lie in the same column. In other words, $\lambda/\nu$ is a rook strip if it is a disconnected union of boxes. It is well known that in Young's lattice, $|\mu(\lambda, \nu)| = 1$ if $\nu/\lambda$ is a rook strip and is 0 otherwise, see Example 3.9.6 in Stanley (1999). Using this fact, we can use the Möbius construction to form the pair of filtered graphs from Young's lattice shown below.

<figure><img src="image_8.png" /></figure>

<figure><img src="image_9.png" /></figure>

Using a simple combinatorial proof involving counting inner and outer corners, one can quickly show that $[\lambda](DU - UD)\mu = [\lambda]D\mu$ when $\mu$ covers $\lambda$, which suffices to prove the following result.

**Theorem 4.3** *The Möbius deformation of Young's lattice forms a dual filtered graph.*

## 4.3 Hecke insertion

In Buch et al. (2008), Buch, Kresch, Shimozono, Tamvakis, and Yong introduce a K-theoretic analogue of the RSK algorithm called *Hecke insertion* and *reverse Hecke insertion* that corresponds to the Möbius deformation of Young's lattice in the same way that RSK corresponds to Young's lattice. In other words, if we insert a word $w$ of length $n$ using Hecke insertion, the construction of the insertion tableau will be represented as a path of length $n$ downward that ends at $\emptyset$ in the Möbius deformation of Young's lattice, and the construction of the recording tableau is represented as a path of length $n$ upward starting at $\emptyset$.

In this setting, the proper K-theoretic analogues of standard Young tableaux are *increasing tableaux* (Thomas and Yong (2009)) and *set-valued tableaux* (Buch (2002)), acting as insertion and recording tableaux, respectively. See Patrias and Pylyavskyy (2014a) for details about this correspondence.

## 4.4 Möbius via Pieri

The following shows that we have an instance of the Möbius via Pieri phenomenon in the case of Young's lattice. Namely, the Möbius deformation of Young's lattice is obtained by the Pieri construction from an appropriate K-theoretic deformation of the underlying Hopf algebra.

Take $A$ to be the subring of the completion $\hat{\Lambda}$ of the ring of symmetric functions with basis $\{G_\lambda\}$, the stable Grothendieck polynomials. For details, see Buch (2002) and Lam and Pylyavskyy (2007). Let $S_\mu$ be the superstandard tableau of shape $\mu$, that is, the first row of $S$ is filled with $1, 2, \dots, \mu_1$, the second row with $\mu_1 + 1, m_1 + 2, \dots, \mu_1 + \mu_2$, etc. This space has a bialgebra structure reminiscent of that of the $\Lambda$ with Hecke insertion taking the role of RSK insertion. We refer the reader to Buch and Samuel (2013), Patrias and Pylyavskyy (2014a), and Thomas and Yong (2011) for details.

We consider the following Pieri construction in $A$. Let $g = G_1$, and define an operator $D$ by $D(G_\nu) = \xi(\Delta(G_\nu))$. We define a graph $G$, where elements are partitions, $a_1(\mu, \lambda)$ is the absolute value of the coefficient of $G_\mu$ in $D(G_\lambda)$, and $a_2(\mu, \lambda)$ is the absolute value of the coefficient of $G_\lambda$ in $G_\mu G_1$. It is
not hard to show the result is the same as the Möbius deformation of Young's lattice using the bialgebra structure.

**Proposition 4.4** *The resulting graph coincides with the one obtained via Möbius construction in Section 4.2.*

# 5 Binary tree deformations

## 5.1 A Pieri deformation of BinWord

The lifted binary tree is shown on the left, where vertices can be naturally labeled by bit strings: 0, 1, 10, 11, 100, 101, .... The graph *BinWord* with the same set of vertices and rank function is shown on the right. In *BinWord*, an element *x* covers *y* if *y* can be obtained from *x* by deleting a single digit from *x*, and in addition, 1 covers 0. The lifted binary tree and *BinWord* form a dual graded graph, see (Fomin, 1994, Example 2.4.1).

<figure><img src="image_10.png" /></figure>

We form a Pieri deformation by interpreting the graph in the context of the ring of quasisymmetric functions, QSym (see Stanley (1999)). If we interpret “1” as $L_1$, “10” as $L_2$, “100” as $L_3$, 11001 as $L_{131}$, and so on, we see that *x* covers *y* in the graph on the right exactly when *x* appears in the product $L_y \cdot L_1$, where $L_\alpha$ is the fundamental quasisymmetric function with the usual product. Let *D* be the operator that subtracts 1 from the rightmost number in the subscript or deletes the rightmost number if it is 1. For example, $D(L_{14}) = L_{13}$ and $D(L_{1421}) = L_{142}$. Then *x* covers *y* in the graph on the left exactly when *y* = *D*(*x*). To form the Pieri deformation, we can let $f = L_1 + L_{11} + L_{111} + ...$. In other words, the multiplicity of the edge from *x* down to *y* is the coefficient of *x* in $y \cdot (L_1 + L_{11} + ...)$.

<figure><img src="image_11.png" /></figure>

Using $A = \text{QSym}$ and $D$ as defined above, it is easy to see that $D(f) = L_0 + f = id + f$. Using the Hopf algebra structure of $\text{QSym}$, it is clear that $D$ is a derivation by Lemma 3.4. Thus the resulting graph is a dual filtered graph by Theorem 3.3.

## 5.2 Möbius via Pieri

Consider the Hopf algebra of multi-quasisymmetric functions, $m\text{QSym}$, defined in Lam and Pylyavksyy (2007). This Hopf algebra is a natural $K$-analogue of the Hopf algebra of quasisymmetric functions and
has a basis of multi-fundamental quasisymmetric functions indexed by compositions, {$\tilde{L}_{\alpha}$}. Notice that a graph with vertices indexed by {$\tilde{L}_{\alpha}$} has the same vertices as in Section 5.1.

The product of $\tilde{L}_{\alpha}$ and $\tilde{L}_{\beta}$ mQSym is obtained by first identifying permutations, $w_{\alpha}$ and $w_{\beta}$, where the composition of the descent set is $\alpha$ and $\beta$, respectively, taking the sum of all multishuffles of multiwords of $w_{\alpha}$ and $w_{\beta}$, and finally translating each term back into a term $\tilde{L}_{\gamma}$ by identifying the composition of the descent set. See Lam and Pylyavksyy (2007) for details. Note that there are infinitely many terms in the product of any two basis elements. For example, $\tilde{L}_{(2,1)}\tilde{L}_{(1)} = \tilde{L}_{(2,2)} + \tilde{L}_{(2,1,1)} + \tilde{L}_{(3,1)} + \tilde{L}_{(12121)} + \dots$, where the terms shown correspond to multishuffles 2314, 2431, 2341, 4243141 of $w_{\alpha} = 231$ and $w_{\beta} = 4$.

Define the coproduct using the *cuut coproduct* of a word $w$: $\Delta(w_1w_2\cdots w_k) = \emptyset \otimes w_1 \cdots w_k + w_1 \otimes w_1 \cdots w_k + w_1 \otimes w_2 \cdots w_k + w_2 \cdots w_k + \dots + w_1 \cdots w_k \otimes w_k + w_1 \cdots w_k \otimes \emptyset$. Then let

$$ \Delta(\tilde{L}_{\alpha}) = \sum_{u \otimes u' \text{ in cuut}(w_{\alpha})} \tilde{L}_{C(u)} \otimes \tilde{L}_{C(u')}. $$

For example,

$$ \Delta(\tilde{L}_{(2,1)}) = \emptyset \otimes \tilde{L}_{(2,1)} + \tilde{L}_{(1)} \otimes \tilde{L}_{(2,1)} + \tilde{L}_{(1)} \otimes \tilde{L}_{(1,1)} + \tilde{L}_{(2)} \otimes \tilde{L}_{(1,1)} + \tilde{L}_{(2)} \otimes \tilde{L}_{(1)} + \tilde{L}_{(2,1)} \otimes \tilde{L}_{(1)} + \tilde{L}_{(2,1)} \otimes \emptyset $$

since

$$ \Delta(\tilde{L}_{(2,1)}) = \emptyset \otimes 231 + 2 \otimes 231 + 2 \otimes 31 + 23 \otimes 31 + 23 \otimes 1 + 231 \otimes 1 + 231 \otimes \emptyset. $$

Taking $A$ to be mQSym with the basis {$\tilde{L}_{\alpha}$} indexed by compositions, we create a dual filtered graph by taking $f = \tilde{L}_{(1)}$ and $D = \xi \circ \Delta$ with $g = \tilde{L}_{(1)}$. The first five ranks are shown below.

<figure><img src="image_12.png" /></figure>

<figure><img src="image_13.png" /></figure>

This is a dual filtered graph by Theorem 3.3.

The following proposition shows that we have another instance of Möbius via Pieri phenomenon, just like in the case of Young's lattice.

**Proposition 5.1** *The Pieri construction above is a Möbius deformation of the dual graded graph composed of the lifted binary tree and BinWord in Section 5.1.*

## 5.3 K-Poirer-Reutenauer Peiri deformation

Take $A$ to be the $K$-theoretic Poierier-Reutenauer bialgebra (KPR) defined in Patrias and Pylyavskyy (2014a) with a basis of $K$-Knuth classes of initial words (i.e. words containing only $1, 2, \dots, n$ for some
n) on $\mathbb{N}$. The K-Knuth relations are as follows:

$$ \begin{array}{lclcl} pp & \equiv & p & \text{for all } p \\ pqp & \equiv & qpq & \text{for all } q, p \\ pqs & \equiv & qps & \text{and } spq & \equiv sqp & \text{for } p < s < q \end{array} $$

See Buch and Samuel (2013) for details on this relation.

Multiplication of two classes $[w_1]$ and $[w_2]$ is done by shuffling each pair of elements, one from $[w_1]$ and one from $[w_2[n]]$, where $w_1$ is a word on $n$ and $w_2[n]$ is obtained by adding $n$ to each letter in $w_2$, and writing the result as a sum of classes. For example,

$$ [[12]] \cdot [[312]] = [[53124]] + [[51234]] + [[35124]] + [[351234]] + [[53412]] + [[5351234]]. $$

The coproduct is similarly defined by taking the sum of the coproduct, $\Delta(w_1 \cdots w_k) = \emptyset \otimes w_1 \cdots w_k + \text{std}(w_1) \otimes \text{std}(w_2 \cdots w_k) + \dots + \text{std}(w_1 \cdots w_{k-1}w_k) + \text{std}(w_1 \cdots w_k) \otimes \emptyset$, of each element in the class and writing the result as a sum of classes. Here, $\text{std}(w)$ sends $w$ to the unique word with the same relative order using all letters $\{1, 2, \dots, n\}$ for some $n$. For example, $\text{std}(13375) = 12243$. Using this, we compute,

$$ \Delta([[[12]]]) = [[\emptyset]] \otimes [[12]] + [[1]] \otimes [[1]] + [[1]] \otimes [[12]] + [[12]] \otimes [[1]] + [[12]] \otimes [[\emptyset]]. $$

Letting $g = [[1]]$ and $f = [[1]]$, we create a Pieri construction using Theorem 3.3. The partial dual filtered graph is shown below. The first five ranks are shown completely, and there are a few additional elements shown in the graph on the right to illustrate all elements that cover [212]. To see that there is an upward edge from [[3412]] to [[3124]], we first notice that $34124 \in [[3124]]$ and that $3412 \otimes 1$ appears in the coproduct of 34124.

In the figure below, K-Knuth equivalence classes of words are represented by an increasing tableau. Note that there may be more than one increasing tableau in any given class.

<figure><img src="image_14.png" /></figure>
<figure><img src="image_15.png" /></figure>

# 6 Enumerative theorems via up-down calculus

Let $\emptyset$ be the minimal element of a dual filtered graph satisfying $DU - UD = 1 + D$. Let $T(n, k)$ be the number of ways $n$ labeled objects can be distributed into $k$ nonempty parcels. We have

$$T(n, k) = k! \cdot S(n, k),$$

where $S(n, k)$ is the Stirling number of the second kind.

**Theorem 6.1** For any dual filtered graph, the coefficient of $\emptyset$ in $D^k U^n(\emptyset)$ is $T(n, k)$.

Let $f^\lambda$ be the number of increasing tableaux of shape $\lambda$. Let $g_n^\lambda$ be the number of set-valued tableaux of shape $\lambda$ and content $1, \dots, n$. Let $F(n)$ denote the *Fubini number*, or *ordered Bell number* - the number of ordered set partitions of $[n]$.

**Corollary 6.2** We have

$$\sum_{|\lambda| \le n} f^\lambda g_n^\lambda = F(n).$$

This is the analogue of the famous Frobenius-Young identity. Of course, this also follows from bijec- tivity of Hecke insertion. The advantage of our proof is that a similar result exists for any dual filtered graph.

The following result is analogous to counting oscillating tableaux.

**Theorem 6.3** For any dual graded graph the coefficient of $\emptyset$ in $(D+U)^n(\emptyset)$ is equal to the number of set partitions of $[n]$ with parts of size at least 2.

# Acknowledgements

We thank Vic Reiner, Alexander Garver, and Thomas Lam for helpful discussions.
References

N. Begeron, T. Lam, and H. Li. Combinatorial hopf algebras and towers of algebras: dimension, quantization and functoriality. *Algebr. Represent. Theory*, 15(4):675–696, 2012.

J. Bjork. *Rings of differential operators*. North-Hollan Pub. Co., 1979.

A. Björner and R. Stanley. An analogue of Young's lattice for compositions. *Unpublished*.

A. S. Buch. A Littlewood Richardson rule for K-theory of Grassmannians. *Acta Mathematica*, 189:37–78, 2002.

A. S. Buch and M. Samuel. *k*-theory of miniscule varieties. preprint arXiv:1306.5419v1, 2013.

A. S. Buch, A. Kresch, M. Shimozono, H. Tamvakis, and A. Yong. Stable Grothendieck polynomials and K-theoretic factor sequences. *Math. Annalen*, 340(2):359–382, 2008.

S. Fomin. Duality of graded graphs. *Journal of Algebraic Combinatorics*, 3:357 – 404, 1994.

T. Lam. Quantized dual graded graphs. *Elec. J. Combin.*, 17(1), 2010.

T. Lam and P. Pylyavksyy. Combinatorial Hopf algebras and K-homology of grassmannians. *Int. Math. Res. Not.*, 2007, 2007.

T. Lam and M. Shimozono. *Unpublished*.

T. Lam and M. Shimozono. Dual graded graphs for Kac-Moody algebras. *Algebra and Number Theory*, 1:451–488, 2007.

J. Nzeutchap. Dual graded graphs and Fomin's *r*-correspondences associated to the Hopf algebras of planar binary trees, quasi-symmetric functions and noncommutative symmetric functions. *FPSAC*, 2006.

Ø. Ore. Theory of non-commutative polynomials. *Ann. of Math.*, 34:480 – 508, 1933.

R. Patrias and P. Pylyavskyy. *K*-theoretic Poirier-Reutenauer bialgebra. preprint arXiv:1404.4340v1, 2014a.

R. Patrias and P. Pylyavskyy. Dual filtered graphs. preprint arXiv:1410.7683, 2014b.

S. Poirier and C. Reutenauer. Hopf algebras of tableaux. *Ann. Sci. Math. Quebec*, 19:79 – 90, 1995.

R. Stanley. Differential posets. *Amer. Math. Soc*, 1:919 – 961, 1988.

R. Stanley. *Enumerative Combinatorics*, Vol 2. Cambridge University Press, Cambridge, 1999.

H. Thomas and A. Yong. A jeu de taquin theory for increasing tableaux, with applications to *K*-theoretic Schubert calculus. *Algebra and Number Theory J.*, 3:121 – 148, 2009.

H. Thomas and A. Yong. The direct sum map on grassmannians and jeu de taquin for increasing tableaux. *Int. Math. Res. Not.*, 12:2766 – 2793, 2011.