%~Mouliné par MaN_auto v.0.17.2 2018-05-31 09:49:30 \documentclass[ALCO,Unicode,ThmDefs]{cedram} \OneNumberAllTheorems \usepackage{tikz} \usepackage{ytableau} \usepackage[vcentermath]{youngtab} \usepackage{array} %\DeclarePairedDelimiter\abs{\lvert}{\rvert} \DeclareMathOperator{\row}{row} \usetikzlibrary{matrix,arrows,decorations.pathmorphing} \newcommand*\QSym{\mathrm{QSym}} \newcommand*\mQSym{\mathfrak{m} \mathrm{QSym}} \graphicspath{{./figures/}} \newcommand*{\mk}{\mkern -1mu} \newcommand*{\Mk}{\mkern -2mu} \newcommand*{\mK}{\mkern 1mu} \newcommand*{\MK}{\mkern 2mu} \newcommand*{\dd}{\mathrm{d}} \newcommand{\llbracket}{{[\mkern -2.7mu[}} \newcommand{\rrbracket}{{]\mkern -2.7mu]}} \newcommand*{\casetext}{\textsc} \numberwithin{equation}{section} \numberwithin{figure}{section} \title[Dual filtered graphs]{Dual filtered graphs} \author[\initial{R.} Patrias]{\firstname{Rebecca} \lastname{Patrias}} \address{Laboratoire de Combinatoire et d'Informatique Mathématique \\ Université du Québec à Montréal\\ 201 Président-Kennedy \\ Montréal, Québec H2X 3Y7, Canada} \email{patriasr@lacim.ca} \author[\initial{P.} Pylyavksyy]{\firstname{Pavlo} \lastname{Pylyavskyy}} \address{Department of Mathematics\\ University of Minnesota\\ 127 Vincent Hall\\ 206 Church Street\\ Minneapolis, MN 5545, USA} \email{ppylyavs@umn.edu} \thanks{R.P. was supported by NSF grant DMS-1148634. P.P. was supported by NSF grants DMS-1068169, DMS-1148634, DMS-1351590, and Sloan Fellowship.} \keywords{dual graded graphs, insertion algorithms, $K$-theory, symmetric functions} \subjclass{05E99, 05E05} \begin{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, of shifted Young's lattice, and of the Young--Fibonacci lattice. We suggest notions of tableaux, insertion algorithms, and growth rules whenever such objects are not already present in the literature. (See the table below.) We also provide a large number of other examples. Most of our examples arise via two constructions, which we call the Pieri construction and the M\"obius construction. The Pieri construction is closely related to the construction of dual graded graphs from a graded Hopf algebra, as described in~\cite{BLL,HN,LS}. The M\"obius construction is more mysterious but also potentially more important, as it corresponds to natural insertion algorithms. \end{abstract} \begin{document} \maketitle \begin{center} \begin{tabular}{|l|>{\centering} p{2.9cm}|>{\centering} p{2.9cm}| c|} \hline & Tableaux & Insertion & Growth\\[.5ex] \hline Young & Standard Young tableaux \cite{Young} & RSK insertion \cite{Knuth, Robinson, Schensted}&\cite{Fomin} \\[.5ex] \hline Shifted Young & Standard shifted Young tableaux with and without circles \cite{Sagan} & Shifted Robinson--Schensted insertion \cite{Sagan,W} & \cite{FSchen}\\[.5ex] \hline Young--Fibonacci & Young--Fibonacci tableaux \cite{Fomin,F} & Young--Fibonacci insertion \cite{Fomin} & \cite{FSchen} \\[.5ex] \hline M\"obius Young & Increasing and set-valued tableaux \cite{B,ThY}& Hecke insertion \cite{BKSTY} & Section \ref{sec:HeckeGrowth}\\[.5ex] \hline M\"obius shifted Young & Definitions \ref{def:increasingshifted} and~\ref{def:shiftedset} & Section \ref{sec:shiftedinsertion} & Section \ref{sec:shiftedgrowth}\\[.5ex] \hline M\"obius Young--Fibonacci & Definitions \ref{def:KYFtableau} and~\ref{def:KYFsetvalued} & Section \ref{sec:KYFinsertion} & Section \ref{sec:KYFgrowth} \\[.5ex] \hline \end{tabular} \end{center} \section{Introduction} Fomin's \emph{dual graded graphs}~\cite{F}, as well as their predecessors - Stanley's \emph{differential posets}~\cite{St}, 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~\cite{BLL, BS}. A recent work of Lam and Shimozono~\cite{LSh} associates a dual graded graph to any Kac--Moody algebra, bringing their study to a new level of generality. \subsection{Weyl algebra and its deformations} One way to view the theory is as a study of certain \emph{combinatorial representations} of the \emph{first Weyl algebra}. Let us briefly recall the definitions. The \emph{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~\cite{Bjo}, for example, for more background on the Weyl algebra. A \emph{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 \emph{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 \emph{up} and \emph{down operators} $U,D\in 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 \emph{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 \emph{$q$-Weyl algebra} defined by the relation \[ DU-qUD=1. \] The corresponding theory of \emph{quantum dual graded graphs} was pursued by Lam in~\cite{L}. 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~\cite{O}, and we shall see that it is a very natural object. In particular, the corresponding theory of \emph{dual filtered graphs} fits naturally with the existing body of work on the $K$-theory of Grassmannians. \begin{rema}\label{rem:rescale} 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. \end{rema} \subsection{Differential vs difference operators}\label{sec:differential} The following provides some intuitive explanation for the relation between representations of Weyl and Ore algebras. The simplest representation of the Weyl algebra is that acting on a polynomial ring. Indeed, consider polynomial ring $R=\mathbb R[x]$, and for $f \in R$ let \[ U(f)= xf, \;\;\; D(f)=\frac{\partial f}{\partial x}. \] It is an easy exercise to verify that this indeed produces a representation of the Weyl algebra. In fact, this is how it is often defined. Let us now redefine the down operator to be the \emph{difference operator}: \[ U(f)= xf, \;\;\; D(f)= f(x+1) - f(x). \] \begin{lemm} This gives a representation of the Ore algebra $W$. In other words, those operators satisfy \[ DU-UD= D+I, \] where $I$ is the identity map on $R$. \end{lemm} \begin{proof} We have \begin{align*} (DU-UD)(f)&=((x+1)f(x+1)-xf(x)) - x(f(x+1)-f(x)) \\ &= f(x+1)= f(x) + (f(x+1)-f(x))=(I+D)(f).\qedhere \end{align*} \end{proof} It can also be noted that differential and difference operators can be related as follows: \[ D= e^{\frac{\partial}{\partial x}}-1. \] We omit the easy proof for brevity. As we shall see in Example~\ref{ex:polys}, this representation of $W$ corresponds to a very basic dual filtered graph. \subsection{Pieri and M\"obius 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 \emph{bialgebra} structure on $A$. This construction is very close to an existing one in the literature~\cite{BLL,LS,HN}, 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 \emph{Pieri construction} or sometimes as the \emph{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\mid y\text{ covers }x\text{ 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\"obius function in $G_2=(P, \rho, E_2)$. We refer to this construction as the \emph{M\"obius construction} or \emph{M\"obius 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 \emph{Hecke insertion} of~\cite{BKSTY}. The following observation seems remarkable, and we call it the \emph{M\"obius via Pieri phenomenon}. Let $A$ be a graded Hopf algebra, and let bialgebra $\tilde A$ be its \emph{$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\"obius construction to $G$ yields \emph{the same result} as a natural Pieri construction applied to $\tilde A$. In other words, the following diagram commutes. \[ \begin{tikzpicture} \node (A) at (-2,2) {$A$}; \node (tildeA) at (2,2) {$\tilde A$}; \node (G) at (-2,0) {$G$}; \node (tildeG) at (2,0) {$\tilde G$}; \path[->] (G) edge node [above] {\tiny{M\"obius construction}} (tildeG); \path[->] (A) edge node [left] {$\substack{\text{Pieri}\\\text{construction}}$} (G); \path[->] (tildeA) edge node [right] {$\substack{\text{Pieri}\\\text{construction}}$} (tildeG); \path[->] (A) edge node [above] {\tiny{$K$ deformation}} (tildeA); \end{tikzpicture} \] This happens for Young's lattice, see Section~\ref{ex:G}, and for the binary tree dual graded graph, see Section~\ref{sec:bin}. We expect this phenomenon to also occur for the shifted Young's lattice. 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 $K$-theoretic analogues of the Poirier--Reutenauer and Malvenuto--Reutenauer Hopf algebras, as described in Sections~\ref{sec:PR}, \ref{sec:MR}. 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\"obius construction. Interestingly, those are exactly the examples we found where the M\"obius construction fails to produce a dual filtered graph. \subsection{Synopsis of the paper} In Section~\ref{sec:dgg}, we recall the definition of dual graded graphs from~\cite{F} as well as three major examples: Young's lattice, Young--Fibonacci lattice, and shifted Young's lattice. We then remind the reader of the definition of the Robinson--Schensted algorithm and how one can obtain it locally via the machinery of \emph{growth diagrams}, also introduced by Fomin in~\cite{F, FSchen}. In Section~\ref{sec:dfg}, we formulate our definition of dual filtered graphs. We then introduce the trivial, Pieri, and M\"obius constructions. In Section~\ref{sec:Y}, we build the Pieri and M\"obius deformations of Young's lattice. We recall the definition of Hecke insertion and observe it is a map into a pair of paths in the M\"obius deformation of Young's lattice. We provide growth rules that realize Hecke insertion. We also show how the Pieri construction applied to the ring generated by \emph{Grothendieck polynomials} yields the same result as the M\"obius construction applied to Young's lattice. Thus we demonstrate an instance of the M\"obius via Pieri phenomenon. In Section~\ref{sec:sY}, we build Pieri and M\"obius deformations of the shifted Young's lattice. We introduce \emph{shifted Hecke insertion} and remark that its result always coincides with that of $K$-theoretic jeu de taquin rectification as defined in~\cite{ThYshift}. We also provide the corresponding growth rules. In Section~\ref{sec:YF}, we build Pieri and M\"obius deformations of the Young--Fibonacci lattice. We define $K$-Young--Fibonacci tableaux and suggest the corresponding insertion algorithm and growth rules. In Section~\ref{sec:other}, we consider some other examples of dual filtered graphs. Of special interest are the Pieri constructions associated to the quasisymmetric functions, to the Poirier--Reutenauer and Malvenuto--Reutenauer Hopf algebras, as well as to their $K$-theoretic analogues, which we draw from~\cite{LP, PP}. The Hopf algebra of quasisymmetric functions and its $K$-theoretic analogue provide another instance of the M\"obius via Pieri phenomenon. In Section~\ref{sec:enum}, we use the calculus of up and down operators to prove some identities similar to the ones known for dual graded graphs. In particular, we formulate and prove a $K$-theoretic analogue of the Frobenius--Young identity. \section{Dual graded graphs} \label{sec:dgg} \subsection{Dual graded graphs} This section follows~\cite{F}, and we refer the reader to this source for further reading on dual graded graphs. 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$. In future examples, the idea of \emph{inner corners} and \emph{outer corners} of certain configurations of boxes or cells will be necessary. We will call a cell an inner corner if it can be removed from the configuration and the resulting configuration is still valid. A cell is an outer corner of a configuration if it can be added to the configuration, and the resulting configuration is still valid. \begin{exem} 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 five are shown below. We see that $(3,31)\in E$ and $\rho(3)+1=3+1=\rho(31)=4$. \[ \begin{tikzpicture}[scale=1] \node (empty) at (0,0) {$\varnothing$}; \node (1) at (0,1) {\ytableausetup{boxsize=.15cm}\begin{ytableau}$ $ \end{ytableau}}; \node (2) at (1,2) {\begin{ytableau}$ $ & $ $ \end{ytableau}}; \node (11) at (-1,2) {\begin{ytableau}$ $ \\ $ $ \end{ytableau}}; \node (111) at (-2,3) {\begin{ytableau}$ $ \\ $ $ \\ $ $ \end{ytableau}}; \node (21) at (0,3) {\begin{ytableau}$ $ & $ $ \\ $ $ \end{ytableau}}; \node (3) at (2,3) {\begin{ytableau}$ $ & $ $ & $ $ \end{ytableau}}; \node (1111) at (-3,4) {\begin{ytableau}$ $ \\ $ $ \\ $ $ \\ $ $\end{ytableau}}; \node (211) at (-1,4) {\begin{ytableau}$ $ & $ $ \\ $ $ \\ $ $\end{ytableau}}; \node (22) at (0,4) {\begin{ytableau}$ $ & $ $ \\ $ $ & $ $ \end{ytableau}}; \node (31) at (1,4) {\begin{ytableau}$ $ & $ $ & $ $ \\ $ $\end{ytableau}}; \node (4) at (3,4) {\begin{ytableau}$ $ & $ $ & $ $ & $ $\end{ytableau}}; \node (5) at (4,5) {\begin{ytableau}$ $ & $ $ & & & \end{ytableau}}; \node (41) at (2,5) {\begin{ytableau}$ $ & $ $ & & \\ $ $ \end{ytableau}}; \node (32) at (1,5) {\begin{ytableau}$ $ & $ $ & \\ $ $ & $ $ \end{ytableau}}; \node (311) at (0,5) {\begin{ytableau}$ $ & $ $ & \\ $ $ \\ $ $ \end{ytableau}}; \node (221) at (-1,5) {\begin{ytableau}$ $ & $ $ \\ $ $ & $ $ \\ $ $ \end{ytableau}}; \node (2111) at (-2,5) {\begin{ytableau}$ $ & $ $ \\ $ $ \\ $ $ \\ $ $ \end{ytableau}}; \node (11111) at (-4,5) {\begin{ytableau}$ $ \\ $ $ \\ $ $ \\ $ $ \\ $ $ \end{ytableau}}; \draw (empty) -- (1) (1) -- (2)--(3)--(4)--(5) (1)--(11)--(111)--(1111)--(11111) (11)--(21)--(31)--(41) (111)--(211)--(2111) (1111)--(2111) (4)--(41) (22)--(221) (211)--(221) (31)--(311) (3)--(31)--(32) (21)--(22)--(32) (2)--(21)--(211)--(311); \end{tikzpicture} \] \ytableausetup{boxsize=.3cm} If we look at the partition (4,4,2,1), visually represented below, we see that the inner corners are in positions (2,4), (3,2), and (4,1), and the outer corners are in positions (1,5), (3,3), (4,2), and (5,1). \[ \begin{ytableau} $ $ & $ $ & $ $ & $ $ \\ $ $ & $ $ & $ $ & $ $ \\ $ $ & $ $ \\ $ $ \end{ytableau} \] \end{exem} 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 \emph{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 \emph{up} and \emph{down operators} $U,D\in 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$. The restrictions of $U$ and $D$ to ``homogeneous'' subspaces $KP_n$ are denoted by $U_n$ and $D_n$, respectively. Graded graphs $G_1$ and $G_2$ with a common vertex set and rank function are said to be \emph{r-dual} if \[ D_{n+1}U_n=U_{n-1}D_n+rI_n \] for some $r\in\mathbb{R}$ and simply \emph{dual} if \[ D_{n+1}U_n=U_{n-1}D_n+I_n. \] We focus on the latter. \begin{exem} Young's lattice is an example of a self-dual graded graph. \end{exem} \begin{exem} Another well-known example of a self-dual graded graph is the \emph{Young--Fibonacci lattice}, $\mathbb{YF}$. The first six ranks are shown below. The vertices of the graph are all finite words in the alphabet $\{1,2\}$, where the rank of a word is the sum of its entries. The covering relations are as follows: a word $w'$ covers $w$ if and only if either $w'=1w$ or $w'=2v$ for some $v$ covered by $w$. For example, the word $121$ covers the word $21$ since $121$ is obtained by concatenating $1$ and $21$, and $121$ is covered by $221$ because $121$ covers $21$. The words in the alphabet $\{1,2\}$ are sometimes called snakes and can be represented as a collection of boxes whose heights correspond to the entries of the word called snakeshapes. For example, the word $122112$ can be pictured as \[ \ytableausetup{boxsize=.3cm} \begin{ytableau} \none & $ $ & $ $ & \none & \none & $ $ \\ $ $ & $ $ & $ $ & $ $ & $ $ & $ $ \end{ytableau} \] Thought of this way, the rank of a word is the number of boxes in its corresponding snakeshape. \[ \ytableausetup{boxsize=.15cm} \begin{tikzpicture}[scale=1] \node (empty) at (0,0) {$\varnothing$}; \node (1) at (0,1) {\begin{ytableau} $ $ \end{ytableau}}; \node (11) at (1,2) {\begin{ytableau} $ $ & $ $ \end{ytableau}}; \node (2) at (-1,2) {\begin{ytableau} $ $ \\ $ $ \end{ytableau}}; \node (12) at (-2,3) {\begin{ytableau} \none & $ $ \\ $ $ & \end{ytableau}}; \node (21) at (0,3) {\begin{ytableau} $ $ & \none \\ $ $ & $ $ \end{ytableau}}; \node (111) at (2,3) {\begin{ytableau} $ $ & & \end{ytableau}}; \node (112) at (-3,4) {\begin{ytableau} \none & \none & $ $ \\ $ $ & & \end{ytableau}}; \node (22) at (-1,4) {\begin{ytableau} $ $ & \\ $ $ & \end{ytableau}}; \node (121) at (0,4) {\begin{ytableau} \none & $ $ & \none \\ $ $ & & \end{ytableau}}; \node (211) at (1,4) {\begin{ytableau} $ $ & \none & \none \\ $ $ & & \end{ytableau}}; \node (1111) at (3,4) {\begin{ytableau} $ $ & & & \end{ytableau}}; \node (11111) at (4,5) {\begin{ytableau} $ $ & & & & \end{ytableau}}; \node (2111) at (2.92,5) {\begin{ytableau} $ $ & \none & \none & \none \\ $ $ & & & \end{ytableau}}; \node (1211) at (1.78,5) {\begin{ytableau} \none & $ $ & \none & \none \\ $ $ & & & \end{ytableau}}; \node (221) at (.64,5) {\begin{ytableau} $ $ & & \none \\ $ $ & & \end{ytableau}}; \node (1121) at (-.64,5) {\begin{ytableau} \none & \none & $ $ & \none \\ $ $ & & & \end{ytableau}}; \node (212) at (-2.92,5) {\begin{ytableau} $ $ & \none & $ $ \\ $ $ & & \end{ytableau}}; \node(122) at(-1.78,5) {\begin{ytableau} \none & $ $ & \\ $ $ & & \end{ytableau}}; \node (1112) at (-4,5) {\begin{ytableau} \none & \none & \none & $ $ \\ $ $ & & & \end{ytableau}}; \draw (empty) -- (1) --(11)--(111)--(1111)--(11111) (1)--(2)--(12)--(112)--(1112) (11)--(21)--(22)--(212) (2)--(21)--(211)--(2111) (111)--(211)--(221) (21)--(121)--(1121) (12)--(22)--(212) (112)--(212) (22)--(122) (22)--(221) (121)--(221) (211)--(1211) (1111)--(2111); \end{tikzpicture} \] \end{exem} \ytableausetup{boxsize=.3cm} Young's lattice and the Young--Fibonacci lattice discussed above are the most interesting examples of self-dual graded graphs. We close this section by describing the graph of shifted shapes, $\mathbb{SY}$, and its dual, which together form a dual graded graph. \begin{exem}\label{ex:shifted} Given a strict partition $\lambda$ (i.e. $\lambda=(\lambda_1>\lambda_2>\dots>\lambda_k)$), the corresponding shifted shape $\lambda$ is an arrangement of cells in $k$ rows where row $i$ contains $\lambda_i$ cells and is indented $i-1$ spaces. For example, the strict partition $(5,4,3,1)$ corresponds to the shifted shape shown below. \[ \begin{ytableau} $ $ & $ $ & $ $ & $ $ & $ $ \\ \none & $ $ & $ $ & $ $ & $ $ \\ \none & \none & $ $ & $ $ & $ $ \\ \none & \none & \none & $ $ \end{ytableau} \] We say that cells in row $i$ and column $i$ are \emph{diagonal} cells and all other cells are \emph{off-diagonal}. The graph of shifted shapes, $\mathbb{SY}$, has shifted shapes as vertices, the rank function counts the number of cells in a shape, and shifted shape $\lambda$ covers $\mu$ if $\lambda$ is obtained from $\mu$ by adding one cell. The first six ranks of the graph $\mathbb{SY}$ are shown below on the left. The graph shown on the right is its dual. In the dual graph, there is one edge between $\lambda$ and $\mu$ if $\lambda$ is obtained from $\mu$ by adding a diagonal cell, and there are two edges between $\lambda$ and $\mu$ if $\lambda$ is obtained from $\mu$ by adding an off-diagonal cell. To form the dual graded graph, the edges of $\mathbb{SY}$ are oriented upward and those of its dual are oriented downward. \[ \begin{tikzpicture} \node (empty) at (0,0) {$\varnothing$}; \node (1) at (0,1) {\ytableausetup{boxsize=.15cm}\begin{ytableau}$ $ \end{ytableau}}; \node (2) at (0,2) {\begin{ytableau}$ $ & $ $ \end{ytableau}}; \node (3) at (1,3) {\begin{ytableau}$ $ & $ $ & $ $ \end{ytableau}}; \node (21) at (-1,3) {\begin{ytableau}$ $ & $ $ \\ \none & $ $ \end{ytableau}}; \node (31) at (0,4) {\begin{ytableau}$ $ & $ $ & $ $\\ \none & $ $ \end{ytableau}}; \node (4) at (2,4) {\begin{ytableau}$ $ & $ $ & $ $ & $ $ \end{ytableau}}; \node (32) at (-1,5) {\begin{ytableau}$ $ & $ $ & $ $\\ \none & $ $ & $ $\end{ytableau}}; \node (41) at (1,5) {\begin{ytableau}$ $ & $ $ & $ $ & $ $ \\ \none & $ $ \end{ytableau}}; \node (5) at (3,5) {\begin{ytableau}$ $ & $ $ & $ $ & $ $ & $ $ \end{ytableau}}; \draw (empty)--(1)--(2)--(3)--(4)--(5) (2)--(21)--(31)--(32) (3)--(31)--(41) (4)--(41); \end{tikzpicture} \mkern 70mu \begin{tikzpicture} \node (empty) at (0,0) {$\varnothing$}; \node (1) at (0,1) {\ytableausetup{boxsize=.15cm}\begin{ytableau}$ $ \end{ytableau}}; \node (2) at (0,2) {\begin{ytableau}$ $ & $ $ \end{ytableau}}; \node (3) at (1,3) {\begin{ytableau}$ $ & $ $ & $ $ \end{ytableau}}; \node (21) at (-1,3) {\begin{ytableau}$ $ & $ $ \\ \none & $ $ \end{ytableau}}; \node (31) at (0,4) {\begin{ytableau}$ $ & $ $ & $ $\\ \none & $ $ \end{ytableau}}; \node (4) at (2,4) {\begin{ytableau}$ $ & $ $ & $ $ & $ $ \end{ytableau}}; \node (32) at (-1,5) {\begin{ytableau}$ $ & $ $ & $ $\\ \none & $ $ & $ $\end{ytableau}}; \node (41) at (1,5) {\begin{ytableau}$ $ & $ $ & $ $ & $ $ \\ \none & $ $ \end{ytableau}}; \node (5) at (3,5) {\begin{ytableau}$ $ & $ $ & $ $ & $ $ & $ $ \end{ytableau}}; \draw (empty) -- (1) (2) -- (21) (3) -- (31) (4) -- (41); \draw[double, thick] (1)--(2) (2)--(3) (3)--(4) (4)--(5) (21)--(31) (31)--(32) (31)--(41); \end{tikzpicture} \] \ytableausetup{boxsize=.4cm} \end{exem} \subsection{Growth rules as generalized RSK} There is a well-known combinatorial correspondence between words in the alphabet of positive integers and pairs consisting of a semistandard Young tableau and a standard Young tableau of the same shape called the Robinson--Schensted--Knuth (RSK) correspondence. We briefly review the correspondence here and refer the reader to~\cite{EC2} for more information. Given a word $w$, the RSK correspondence maps $w$ to a pair of tableaux via a row insertion algorithm consisting of inserting a positive integer into a tableau. The algorithm for inserting positive integer $k$ into a row of a semistandard tableau is as follows. If $k$ is greater than or equal to all entries in the row, add a box labeled $k$ to the end of the row. Otherwise, find the first $y$ in the row with $y>k$. Replace $y$ with $k$ in this box, and proceed to insert $y$ into the next row. To insert $k$ into semistandard tableau $P$, we start by inserting $k$ into the first row of $P$. To create the \emph{insertion tableau} of a word $w=w_1w_2\dots w_r$, we first insert $w_1$ into the empty tableau, insert $w_2$ into the result of the previous insertion, insert $w_3$ into the result of the previous insertion, and so on until we have inserted all letters of $w$. We denote the resulting insertion tableau by $P(w)$. The insertion tableau will always be a semistandard tableau. To obtain a standard Young tableau from $w$, we define the \emph{recording tableau}, $Q(w)$, of $w$ by labeling the box of $P(w_1\dots w_s)/P(w_1\dots w_{s-1})$ by $s$. For example, $w=14252$ has insertion and recording tableau shown below. \[ P(w)=\begin{ytableau} 1 & 2 & 2 \\ 4 & 5 \end{ytableau} \hspace{1in} Q(w)= \begin{ytableau} 1 & 2 & 4 \\ 3 & 5 \end{ytableau} \] The RSK correspondence described above is a bijection between words consisting of positive integers and pairs $(P,Q)$, where $P$ is a semistandard Young tableau and $Q$ is a standard Young tableau of the same shape. If $w=w_1w_2\dots w_k$ is a permutation, we can also obtain $(P(w),Q(w))$ from $w$ by using growth diagrams. First, we create a $k \times k$ array with an $X$ in the $w_i^{th}$ square from the bottom of column $i$. For example, if $w=14253$, we have \[ \begin{ytableau} $ $ & $ $ & $ $ & X & $ $ \\ $ $ & X & $ $ & $ $ & $ $ \\ $ $ & $ $ & $ $ & $ $ & X \\ $ $ & $ $ & X & $ $ & $ $ \\ X & $ $ & $ $ & $ $ & $ $ \end{ytableau} \] We will label the corners of each square with a partition. We begin by labeling all corners along the bottom row and left side of the diagram with the empty shape, $\varnothing$. To complete the labeling of the corners, suppose the corners $\mu$, $\lambda$, and $\nu$ are labeled, where $\mu$, $\lambda$, and $\nu$ are as in the picture below. We label $\gamma$ according to the following rules. \[ \begin{tikzpicture}[scale=1] \node (A) at (-1,-1) {$\lambda$}; \node (B) at (1,-1) {$\nu$}; \node (C) at (-1,1) {$\mu$}; \node (D) at (1,1) {$\gamma$}; \draw (A) -- (B) (C) -- (D) (B) -- (D) (A) -- (C); \end{tikzpicture} \] \renewcommand*{\theenumi}{L\arabic{enumi}} \begin{enumerate} \item \label{L1} If the square does not contain an $X$ and $\lambda=\mu=\nu$, then $\gamma=\lambda$. \item \label{L2} If the square does not contain an $X$ and $\lambda\subset\mu=\nu$, then $\mu/\lambda$ is one box in some row $i$. In this case, $\gamma$ is obtained from $\mu$ by adding one box in row $i+1$. \item \label{L3} If the square does not contain an $X$ and $\mu\neq\nu$, define $\gamma=\mu\cup\nu$. \item \label{L4} If the square contains an $X$, then $\lambda=\nu=\mu$ and $\gamma$ is obtained from $\mu$ by adding one box in the first row. \end{enumerate} \renewcommand*{\theenumi}{\arabic{enumi}} Following these rules, there is a unique way to label the corners of the diagram. The resulting array is called the \emph{growth diagram} of $w$, and rules~\eqref{L1}--\eqref{L4} are called \emph{growth rules}. For the remainder of this paper, we will use the word ``square'' when referring to a square in the growth diagram and the word ``box'' or ``cell'' when referring to a box in a partition, shifted partition, or snakeshape. The chains of partitions read across the top of the diagram and up the right side of the diagram determine $Q(w)$ and $P(w)$, respectively. To obtain a tableau of shape $\lambda$ from a chain of partitions $\varnothing \subset \lambda^1 \subset \lambda^2 \subset \dots \subset \lambda^k=\lambda$, label the box of $\lambda^i/\lambda^{i-1}$ by $i$. \begin{exem} The growth diagram for the word $14253$ is shown below. \[ \begin{tikzpicture}[scale=1] \node (00) at (0,0) {$\varnothing$}; \node (10) at (1,0) {$\varnothing$}; \node (20) at (2,0) {$\varnothing$}; \node (30) at (3,0) {$\varnothing$}; \node (40) at (4,0) {$\varnothing$}; \node (50) at (5,0) {$\varnothing$}; \node (01) at (0,1) {$\varnothing$}; \node (.5.5) at (.5,.5) {$X$}; \node (11) at (1,1) {$1$}; \node (21) at (2,1) {$1$}; \node (31) at (3,1) {$1$}; \node (41) at (4,1) {$1$}; \node (51) at (5,1) {$1$}; \node (02) at (0,2) {$\varnothing$}; \node (12) at (1,2) {$1$}; \node (22) at (2,2) {$1$}; \node (32) at (3,2) {$2$}; \node (2.51.5) at (2.5,1.5) {$X$}; \node (42) at (4,2) {$2$}; \node (52) at (5,2) {$2$}; \node (03) at (0,3) {$\varnothing$}; \node (13) at (1,3) {$1$}; \node (23) at (2,3) {$1$}; \node (33) at (3,3) {$2$}; \node (43) at (4,3) {$2$}; \node (53) at (5,3) {$3$}; \node (4.52.5) at (4.5,2.5) {$X$}; \node (04) at (0,4) {$\varnothing$}; \node (14) at (1,4) {$1$}; \node (24) at (2,4) {$2$}; \node (34) at (3,4) {$21$}; \node (44) at (4,4) {$21$}; \node (54) at (5,4) {$31$}; \node (1.53.5) at (1.5,3.5) {$X$}; \node (05) at (0,5) {$\varnothing$}; \node (15) at (1,5) {$1$}; \node (25) at (2,5) {$2$}; \node (35) at (3,5) {$21$}; \node (45) at (4,5) {$31$}; \node (55) at (5,5) {$32$}; \node (3.54.5) at (3.5,4.5) {$X$}; \draw (00)--(10)--(20)--(30)--(40)--(50) (01)--(11)--(21)--(31)--(41)--(51) (02)--(12)--(22)--(32)--(42)--(52) (03)--(13)--(23)--(33)--(43)--(53) (04)--(14)--(24)--(34)--(44)--(54) (05)--(15)--(25)--(35)--(45)--(55) (00)--(01)--(02)--(03)--(04)--(05) (10)--(11)--(12)--(13)--(14)--(15) (20)--(21)--(22)--(23)--(24)--(25) (30)--(31)--(32)--(33)--(34)--(35) (40)--(41)--(42)--(43)--(44)--(45) (50)--(51)--(52)--(53)--(54)--(55); \end{tikzpicture} \] From the chains of partitions on the rightmost edge and uppermost edge of the diagram, we can read the insertion tableau and recording tableau, respectively. \[ P(14253)= \begin{ytableau} 1 & 2 & 3 \\ 4 & 5 \end{ytableau}\hspace{1in} Q(14253)= \begin{ytableau} 1 & 2 & 4\\ 3 & 5 \end{ytableau} \] \end{exem} We next draw a connection between the growth rules described and an explicit cancellation in Young's lattice that shows that $DU-UD=I$. We shall start by giving explicit cancellation rules to pair all down-up paths from $\mu$ to $\nu$ with up-down paths from $\mu$ to $\nu$, which will leave one up-down path unpaired with $\mu=\nu$. (Note that if $\rho(\mu)\neq \rho (\nu)$, then there are no up-down or down-up paths from $\mu$ to $\nu$.) \renewcommand*{\theenumi}{C\arabic{enumi}} \begin{enumerate} \item \label{C1} If $\mu\neq \nu$, there is only one down-up path from $\mu$ to $\nu$, which passes through $\mu\cap\nu$. Pair this with the only up-down path from $\mu$ to $\nu$, which passes through $\mu\cup\nu$. \item \label{C2} If $\mu=\nu$, then any down-up path can be represented by the inner corner of $\mu$ that is deleted in the downward step, and any up-down path can be represented by the outer corner of $\mu$ that is added in the upward step. Pair each down-up path with the up-down path that adds the first outer corner of $\mu$ strictly below the inner corner of the down-up path. \end{enumerate} Now, the only up-down path that has not been paired with a down-up path is the path corresponding to adding the outer corner of $\mu$ in the first row. This gives $(DU-UD)\mu=\mu$. It is easy to see that this cancellation yields exactly the growth rules described above. Cancellation rule~\eqref{C1} determines growth rule~\eqref{L3}, cancellation rule~\eqref{C2} determines growth rule~\eqref{L2}, and the up-down path left unmatched determines growth rule~\eqref{L4}. If we started with a different explicit cancellation, we could modify~\eqref{L2}, \eqref{L3}, and~\eqref{L4} accordingly to obtain new growth rules. Note that growth rule~\eqref{L1} is simply a way to transfer information and will remain the same for any explicit cancellation. \begin{exem} Starting with $\mu=(3,1)$, cancellation rule~\eqref{C2} says that the down-up path from $\mu$ to itself passing through $(2,1)$ is paired with the up-down path\pagebreak passing through $(3,2)$. The corresponding growth rule in this situation, \eqref{L4}, is illustrated on the right. \[ \begin{tikzpicture}[scale=1] \node (A) at (0,-1) {21}; \node (B) at (0,0) {31}; \node (D) at (0,1) {32}; \draw (A) -- (B) -- (D); \end{tikzpicture}\hspace{1.5in} \begin{tikzpicture}[scale=1] \node (A) at (-1,-1) {21}; \node (B) at (1,-1) {31}; \node (C) at (-1,1) {31}; \node (D) at (1,1) {32}; \draw (A) -- (B) (C) -- (D) (B) -- (D) (A) -- (C); \end{tikzpicture} \] \end{exem} \section{Dual filtered graphs} \label{sec:dfg} \subsection{The definition} 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)\geq\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 \emph{oriented filtered graph} $G=(P, \rho, 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 \emph{up} and \emph{down operators} associated with graph $G$ as previously defined, we say that $G_1$ and $G_2$ are \emph{dual filtered graphs} if for any $x\in G$, \[ (DU-UD)x=\alpha x+\beta Dx \] for some $\alpha,\beta\in\mathbb{R}$. We focus on examples where $DU-UD=D+I$, see Remark~\ref{rem:rescale}. In the next sections, we describe three constructions of dual filtered graphs. \subsection{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 \emph{trivial construction}. \begin{theo} For any dual graded graph $G$, the trivial construction gives a dual filtered graph $G'$. \end{theo} \begin{proof} It suffices to show that if $q$ covers $p$ in $G_2$, then $[p](DU-UD)(q)=[p]D(q)$, where $[p](DU-UD)(q)$ and $[p]D(q)$ denote the coefficient of $p$ in the linear combination $(DU-UD)(q)$ and $(D)(q)$, respectively. If we restrict to all paths that do not contain a loop, the coefficient of $p$ in $(DU-UD)(q)$ is $0$ since without loops, we have a dual graded graph. Hence we may restrict our attention to up-down paths and down-up paths that contain a loop. The up-down paths beginning at $q$ and ending at $p$ are exactly the paths consisting of a loop at $q$ followed by an edge from $q$ to $p$. There are $\rho(q)e(q\to p)$ such paths, where $e(q\to p)$ denotes the number of directed edges from $q$ to $p$ in $G$. The down-up paths containing a loop are the paths consisting of an edge from $q$ to $p$ followed by a loop at $p$. There are $e(q\to p)\rho(p)$ such paths. Thus \[ [p](DU-UD)(q)=e(q \to p)(\rho(q)-\rho(p))=e(q \to p)=[p]D(q).\qedhere \] \end{proof} \goodbreak \begin{exem} 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. \[ \begin{tikzpicture}[scale=.9] \node (empty) at (0,0) {$\varnothing$}; \node (1) at (0,1) {\ytableausetup{boxsize=.15cm}\begin{ytableau}$ $ \end{ytableau}}; \node (2) at (1,2) {\begin{ytableau}$ $ & $ $ \end{ytableau}}; \node (11) at (-1,2) {\begin{ytableau}$ $ \\ $ $ \end{ytableau}}; \node (111) at (-2,3) {\begin{ytableau}$ $ \\ $ $ \\ $ $ \end{ytableau}}; \node (21) at (0,3) {\begin{ytableau}$ $ & $ $ \\ $ $ \end{ytableau}}; \node (3) at (2,3) {\begin{ytableau}$ $ & $ $ & $ $ \end{ytableau}}; \draw (empty) -- (1) (1) -- (2)--(3) (1)--(11)--(111) (11)--(21) (2)--(21); \draw(1) to [out=60,in=100,distance=.5cm] (1); \draw(2) to [out=60,in=100,distance=.5cm] (2); \draw(2) to [out=60,in=100,distance=.7cm] (2); \draw(11) to [out=60,in=100,distance=.5cm] (11); \draw(11) to [out=60,in=100,distance=.7cm] (11); \draw(111) to [out=60,in=100,distance=.5cm] (111); \draw(111) to [out=60,in=100,distance=.7cm] (111); \draw(111) to [out=60,in=100,distance=.9cm] (111); \draw(21) to [out=60,in=100,distance=.5cm] (21); \draw(21) to [out=60,in=100,distance=.7cm] (21); \draw(21) to [out=60,in=100,distance=.9cm] (21); \draw(3) to [out=60,in=100,distance=.5cm] (3); \draw(3) to [out=60,in=100,distance=.7cm] (3); \draw(3) to [out=60,in=100,distance=.9cm] (3); \end{tikzpicture} \mkern 80mu \begin{tikzpicture}[scale=.9] \node (empty) at (0,0) {$\varnothing$}; \node (1) at (0,1) {\ytableausetup{boxsize=.15cm}\begin{ytableau}$ $ \end{ytableau}}; \node (2) at (1,2) {\begin{ytableau}$ $ & $ $ \end{ytableau}}; \node (11) at (-1,2) {\begin{ytableau}$ $ \\ $ $ \end{ytableau}}; \node (111) at (-2,3) {\begin{ytableau}$ $ \\ $ $ \\ $ $ \end{ytableau}}; \node (21) at (0,3) {\begin{ytableau}$ $ & $ $ \\ $ $ \end{ytableau}}; \node (3) at (2,3) {\begin{ytableau}$ $ & $ $ & $ $ \end{ytableau}}; \draw (empty) -- (1) (1) -- (2)--(3) (1)--(11)--(111) (11)--(21) (2)--(21); \end{tikzpicture} \] \end{exem} \ytableausetup{boxsize=.4cm} \subsection{Pieri construction} The following construction is close to the one for dual graded graphs described in the works of Bergeron--Lam--Li~\cite{BLL}, Nzeutchap~\cite{HN}, and Lam--Shimozono~\cite{LS}. Let \[ A=\bigoplus_{i\geq0} 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$, each graded component of which \[ 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|\leq|\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 End(A)$ is a derivation on $A$ satisfying $d(f)= f+1$ and $d(a_\lambda)\in \bigoplus_{0\leq i\leq|\lambda|}A_i$. To form a graph, we define $E_1$ by defining $a_1(\lambda,\mu)$ to be the coefficient of $a_{\lambda} \text{ in } d (a_{\mu}).$ We also define $E_2$ by defining $a_2(\lambda,\mu)$ to be the coefficient of $a_{\mu} \text{ in } a_{\lambda} f.$ We assume here that $a_i(\lambda,\mu)$ are non-negative integers. \begin{theo}\label{thm:pieri} The resulting graph is a dual filtered graph. \end{theo} \begin{proof} It follows from \[ d(f a_{\lambda})= d(f) a_{\lambda} + f d(a_{\lambda}), \] or \[ d(f a_{\lambda}) - f d(a_{\lambda})= a_{\lambda} + d(a_{\lambda}).\qedhere \] \end{proof} Assume $A_1$ is one-dimensional, and let $g$ be its generator. We shall often find a derivation $d$ from a \emph{bialgebra} structure on $A$. Indeed, assume $\Delta$ is a coproduct on $A$ such that $\Delta(a)=1 \otimes a + a \otimes 1 + \cdots$, where the rest of the terms lie in $(A_1 \oplus A_2 \oplus \cdots) \otimes (A_1 \oplus A_2 \oplus \cdots)$. Assume also $\xi$ is a map $A \otimes A \longrightarrow A$ such that $\xi(p \otimes g)= p$ and for any element $q \in A_i$, $i \not=1$, we have $\xi(p \otimes q)=0$. \begin{lemm}\label{lem:derivation} The map $D(a)=\xi(\Delta(a))$ is a derivation. \end{lemm} \begin{proof} We have $\xi(\Delta(ab))=\xi(\Delta(a) \Delta(b)))$. Pick a linear basis for $A$ that contains $1$ and $g$. Express $\Delta(a)$ and $\Delta(b)$ so that the right side of tensors consists of the basis elements. The only terms that are not killed by $\xi$ are the ones of the form $p \otimes g$. The only way we can get such terms is from $(p_1 \otimes 1) \cdot (p_2 \otimes g)$ or $(p_1 \otimes g) \cdot (p_2 \otimes 1)$. Those are exactly the terms that contribute to \[ \xi(\Delta(a))\cdot b + a \cdot \xi(\Delta(b)).\qedhere \] \end{proof} \subsection{M\"obius 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\mid y\text{ covers }x\text{ 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\"obius function in $(P, \rho, E_2)$. Compose $G_1'$ and $G_2'$ into an oriented filtered graph $\tilde G$. As we shall see, in all three of our major examples, the M\"obius deformation forms a dual filtered graph. Unlike with the Pieri construction, we do not have the algebraic machinery explaining why the construction yields dual filtered graphs. Instead, we provide the proofs on a case-by-case basis. Nevertheless, the M\"obius construction is the most important one, as it is this construction that relates to insertion algorithms and thus to $K$-theory of Grassmannians. It is not the case that every dual graded graph's M\"obius deformation makes it a dual filtered graph. For example, it is easy to see that the M\"obius deformation of the graphs in Example~\ref{ex:mMR} and Example~\ref{ex:SYTtree} are not dual filtered graphs. \begin{enonce}{Problem} Determine for which dual graded graphs $G$ the M\"obius construction $\tilde G$ yields a dual filtered graph. \end{enonce} \section{Major examples: Young's lattice} \label{sec:Y} \subsection{Pieri deformations 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 + \cdots. \] 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} \text{ in } p_1 s_{\mu}, \text{ and } a_2(\mu, \nu)$ be the coefficient of $s_{\nu} \text{ in } f s_{\mu}.$ Recall that given two partitions, $\mu$ and $\nu$, $\mu/\nu$ forms a \emph{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. \[ \begin{ytableau} \none & \none & $ $ & $ $ \\ \none & $ $ \\ $ $ \end{ytableau}\hspace{1in} \begin{ytableau} \none & \none & $ $ & $ $ \\ \none & $ $ & $ $\\ $ $ \end{ytableau} \] \begin{lemm} 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. \end{lemm} \begin{proof} The statement follows from the Pieri rule and the fact that $p_1=h_1$,\linebreak see~\cite{EC2}. \end{proof} 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. \[ \begin{tikzpicture}[scale=.9] \node (empty) at (0,0) {$\varnothing$}; \node (1) at (0,1) {\ytableausetup{boxsize=.15cm}\begin{ytableau}$ $ \end{ytableau}}; \node (2) at (1,2) {\begin{ytableau}$ $ & $ $ \end{ytableau}}; \node (11) at (-1,2) {\begin{ytableau}$ $ \\ $ $ \end{ytableau}}; \node (111) at (-2,3) {\begin{ytableau}$ $ \\ $ $ \\ $ $ \end{ytableau}}; \node (21) at (0,3) {\begin{ytableau}$ $ & $ $ \\ $ $ \end{ytableau}}; \node (3) at (2,3) {\begin{ytableau}$ $ & $ $ & $ $ \end{ytableau}}; \node (1111) at (-3,4) {\begin{ytableau}$ $ \\ $ $ \\ $ $ \\ $ $\end{ytableau}}; \node (211) at (-1,4) {\begin{ytableau}$ $ & $ $ \\ $ $ \\ $ $\end{ytableau}}; \node (22) at (0,4) {\begin{ytableau}$ $ & $ $ \\ $ $ & $ $ \end{ytableau}}; \node (31) at (1,4) {\begin{ytableau}$ $ & $ $ & $ $ \\ $ $\end{ytableau}}; \node (4) at (3,4) {\begin{ytableau}$ $ & $ $ & $ $ & $ $\end{ytableau}}; \draw (empty) -- (1) (1) -- (2)--(3)--(4) (1)--(11)--(111)--(1111) (11)--(21)--(31) (111)--(211) (3)--(31) (21)--(22) (2)--(21)--(211); \end{tikzpicture} \quad \begin{tikzpicture}[scale=.9] \node (empty) at (0,0) {$\varnothing$}; \node (1) at (0,1) {\ytableausetup{boxsize=.15cm}\begin{ytableau}$ $ \end{ytableau}}; \node (2) at (1,2) {\begin{ytableau}$ $ & $ $ \end{ytableau}}; \node (11) at (-1,2) {\begin{ytableau}$ $ \\ $ $ \end{ytableau}}; \node (111) at (-2,3) {\begin{ytableau}$ $ \\ $ $ \\ $ $ \end{ytableau}}; \node (21) at (0,3) {\begin{ytableau}$ $ & $ $ \\ $ $ \end{ytableau}}; \node (3) at (2,3) {\begin{ytableau}$ $ & $ $ & $ $ \end{ytableau}}; \node (1111) at (-3,4) {\begin{ytableau}$ $ \\ $ $ \\ $ $ \\ $ $\end{ytableau}}; \node (211) at (-1,4) {\begin{ytableau}$ $ & $ $ \\ $ $ \\ $ $\end{ytableau}}; \node (22) at (0,4) {\begin{ytableau}$ $ & $ $ \\ $ $ & $ $ \end{ytableau}}; \node (31) at (1,4) {\begin{ytableau}$ $ & $ $ & $ $ \\ $ $\end{ytableau}}; \node (4) at (3,4) {\begin{ytableau}$ $ & $ $ & $ $ & $ $\end{ytableau}}; \draw (empty) -- (1) (1) -- (2)--(3)--(4) (1)--(11)--(111)--(1111) (11)--(21)--(31) (111)--(211) (3)--(31) (21)--(22) (2)--(21)--(211) (3) to [bend left=20] (empty) (4) to [bend left=25] (empty) (2) to [bend left=15] (empty) (3) to [bend left=15] (1) (4) to [bend left=15](2) (4) to [bend left=20] (1) (21)--(1) (211)--(11) (22) to [bend left=10] (2) (31) to [bend left=15] (11) (31) to [bend left=10] (1) (31)--(2); \end{tikzpicture} \] \begin{theo}\label{thm:young} The Pieri deformation of Young's lattice is a dual filtered graph with \[ DU-UD=D+I. \] \end{theo} Recall the following facts regarding the ring of symmetric functions. \begin{theo}[\cite{EC2, Mac}]\ \renewcommand*{\theenumi}{\alph{enumi}} \begin{enumerate} \item $\Lambda$ is a free polynomial ring in $p_1, p_2, \dots$. \item $\Lambda$ can be endowed with a standard bilinear inner product determined by $\langle s_{\lambda}, s_{\mu} \rangle=\delta_{\lambda, \mu}$. \end{enumerate} \end{theo} Because of the first property, we can differentiate elements of $\Lambda$ with respect to $p_1$ by expressing them first as a polynomial in the $p_i$'s. We shall need the following two properties of $f$ and $p_1$. \begin{lemm}\label{lem:young}\ \renewcommand*{\theenumi}{\alph{enumi}} \begin{enumerate} \item For any $h,g \in \Lambda$ we have \[ \langle g, p_1 h \rangle=\left\langle \frac{\dd}{\dd p_1} g, h \right\rangle. \] \item We have \[ \frac{\dd}{\dd p_1} f= f+1. \] \end{enumerate} \end{lemm} \begin{proof} By bilinearity, it suffices to prove the first claim for $g,h$ in some basis of $\Lambda$. Let us choose the power sum basis. Then we want to argue that \[ \langle p_{\lambda}, p_1 p_{\mu} \rangle=\left\langle \frac{\dd}{\dd p_1} p_{\lambda}, p_{\mu} \right\rangle. \] This follows from the fact that $p_{\lambda}$'s form an orthogonal basis and~\cite[Proposition~7.9.3]{EC2}. For the second claim, using~\cite[Proposition~7.7.4]{EC2} we have \[ 1 + f= e^{p_1 + \frac{p_2}{2} + \dots}, \] which of course implies $\frac{\dd}{\dd p_1} (1+f)=1+f$. \end{proof} Now we are ready for the proof of Theorem~\ref{thm:young}. \begin{proof} Applying Lemma~\ref{lem:young} we see that $A=\Lambda$, $a_{\lambda}= s_{\lambda}$, $d=\frac{\dd}{\dd p_1}$ and $f= h_1 + h_2 + \cdots$ satisfy the conditions of Theorem~\ref{thm:pieri}. The claim follows. \end{proof} \begin{rema} We can make a similar argument for the analogous construction where the edges in $E_1$ are again those of Young's lattice and the edges in $E_2$ connect shapes that differ by a vertical strip. In this case we use $f= e_1 + e_2 + \cdots,$ where the $e_i$ are the elementary symmetric functions. \end{rema} \subsection{M\"obius deformation of Young's lattice}\label{sec:MobiusYoung} Given two partitions, $\lambda$ and $\nu$, $\lambda/\nu$ forms a \emph{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. We state the following well-known result about the M\"obius function on Young's lattice. \begin{prop} We have \[ |\mu(\lambda, \nu)|= \begin{cases} 1 & \text{if $\lambda/\nu$ is a rook strip;}\\ 0 & \text{otherwise.} \end{cases} \] \end{prop} \begin{proof} The statement follows from the fact that Young's lattice is a distributive lattice, and the interval $[\lambda,\mu]$ is isomorphic to a Boolean algebra if and only if $\mu/\lambda$ is a rook strip. See~\cite[Example~3.9.6]{EC1}. \end{proof} The M\"obius deformation of Young's lattice is shown below with upward-oriented edges shown on the left and downward-oriented edges shown on the right. Notice that loops at a partition $\lambda$ may be indexed by inner corners of $\lambda$. \[ \begin{tikzpicture}[scale=.9] \node (empty) at (0,0) {$\varnothing$}; \node (1) at (0,1) {\ytableausetup{boxsize=.15cm}\begin{ytableau}$ $ \end{ytableau}}; \node (2) at (1,2) {\begin{ytableau}$ $ & $ $ \end{ytableau}}; \node (11) at (-1,2) {\begin{ytableau}$ $ \\ $ $ \end{ytableau}}; \node (111) at (-2,3) {\begin{ytableau}$ $ \\ $ $ \\ $ $ \end{ytableau}}; \node (21) at (0,3) {\begin{ytableau}$ $ & $ $ \\ $ $ \end{ytableau}}; \node (3) at (2,3) {\begin{ytableau}$ $ & $ $ & $ $ \end{ytableau}}; \node (1111) at (-3,4) {\begin{ytableau}$ $ \\ $ $ \\ $ $ \\ $ $\end{ytableau}}; \node (211) at (-1,4) {\begin{ytableau}$ $ & $ $ \\ $ $ \\ $ $\end{ytableau}}; \node (22) at (0,4) {\begin{ytableau}$ $ & $ $ \\ $ $ & $ $ \end{ytableau}}; \node (31) at (1,4) {\begin{ytableau}$ $ & $ $ & $ $ \\ $ $\end{ytableau}}; \node (4) at (3,4) {\begin{ytableau}$ $ & $ $ & $ $ & $ $\end{ytableau}}; \draw (empty) -- (1) (1) -- (2)--(3)--(4) (1)--(11)--(111)--(1111) (11)--(21)--(31) (111)--(211) (3)--(31) (21)--(22) (2)--(21)--(211) (1) to [out=60,in=100,distance=.5cm] (1) (2) to [out=60,in=100,distance=.5cm] (2) (11) to [out=60,in=100,distance=.5cm] (11) (3) to [out=60,in=100,distance=.5cm] (3) (4) to [out=60,in=100,distance=.5cm] (4) (111) to [out=60,in=100,distance=.5cm] (111) (1111) to [out=60,in=100,distance=.5cm] (1111) (21) to [out=-60,in=-100,distance=.5cm] (21) (21) to [out=-60,in=-100,distance=.7cm] (21) (211) to [out=60,in=100,distance=.5cm] (211) (211) to [out=60,in=100,distance=.7cm] (211) (31) to [out=60,in=100,distance=.5cm] (31) (31) to [out=60,in=100,distance=.7cm] (31) (22) to [out=60,in=100,distance=.5cm] (22) ; \end{tikzpicture}\hspace{.1in} \begin{tikzpicture}[scale=.9] \node (empty) at (0,0) {$\varnothing$}; \node (1) at (0,1) {\ytableausetup{boxsize=.15cm}\begin{ytableau}$ $ \end{ytableau}}; \node (2) at (1,2) {\begin{ytableau}$ $ & $ $ \end{ytableau}}; \node (11) at (-1,2) {\begin{ytableau}$ $ \\ $ $ \end{ytableau}}; \node (111) at (-2,3) {\begin{ytableau}$ $ \\ $ $ \\ $ $ \end{ytableau}}; \node (21) at (0,3) {\begin{ytableau}$ $ & $ $ \\ $ $ \end{ytableau}}; \node (3) at (2,3) {\begin{ytableau}$ $ & $ $ & $ $ \end{ytableau}}; \node (1111) at (-3,4) {\begin{ytableau}$ $ \\ $ $ \\ $ $ \\ $ $\end{ytableau}}; \node (211) at (-1,4) {\begin{ytableau}$ $ & $ $ \\ $ $ \\ $ $\end{ytableau}}; \node (22) at (0,4) {\begin{ytableau}$ $ & $ $ \\ $ $ & $ $ \end{ytableau}}; \node (31) at (1,4) {\begin{ytableau}$ $ & $ $ & $ $ \\ $ $\end{ytableau}}; \node (4) at (3,4) {\begin{ytableau}$ $ & $ $ & $ $ & $ $\end{ytableau}}; \draw (empty) -- (1) (1) -- (2)--(3)--(4) (1)--(11)--(111)--(1111) (11)--(21)--(31) (111)--(211) (3)--(31) (21)--(22) (2)--(21)--(211) (21)--(1) (31)--(2) (211)--(11); \end{tikzpicture} \] \ytableausetup{boxsize=.5cm} \begin{theo} The M\"obius deformation of Young's lattice forms a dual filtered graph with \[ DU-UD=D+I. \] \end{theo} \begin{proof} It suffices to show that $[\lambda](DU-UD)\mu=[\lambda]D\mu$ when $\mu$ covers $\lambda$ in $G_2$ since we started with a dual graded graph. Suppose shape $\lambda$ is covered by shape $\mu$. Each inner corner of $\mu$ contributes one to the coefficient of $\lambda$ in $DU\mu$ via taking the loop corresponding to that inner corner of $\mu$ as an upward move and then going down to $\lambda$. Next, consider shape $\mu$ and mark the outer corners of $\lambda$ contained in $\mu$. The marked boxes will be inner corners of $\mu$. The shapes with an upward arrow from $\mu$ and a downward arrow to $\lambda$ are exactly those obtained by adding one box to an outer corner of $\mu$ which is not adjacent to one of the marked boxes. There are $\#\{\text{outer corners of $\lambda$}\}-|\mu/\lambda|$ possible places to add such a box. Thus the coefficient of $\lambda$ in $DU\mu$ is \[ \#\{\text{inner corners of $\mu$}\}+\#\{\text{outer corners of $\lambda$}\}-|\mu/\lambda|. \] For down-up paths that involve three shapes, consider the inner corners of $\mu$ that are also inner corners of $\lambda$. Every shape obtained by removing one of these inner corners determines one down-up path from $\mu$ to $\lambda$, and there are $\#\{\text{inner corners of $\mu$}\}-|\mu/\lambda|$ such shapes. The remaining down-up paths are given by going from $\mu$ to $\lambda$ and then taking a loop at $\lambda$. Hence the coefficient of $\lambda$ in $UD\mu$ is \[ \#\{\text{inner corners of $\mu$}\}-|\mu/\lambda|+\#\{\text{inner corners of }\lambda\}. \] Since all shapes have one more outer corner than inner corner, the coefficient of $\lambda$ in $(DU-UD)\mu$ is 1. \end{proof} \subsection{Hecke insertion} We next describe an insertion and reverse insertion procedure that correspond to the M\"obius deformation of Young's lattice in the same way that RSK corresponds to Young's lattice, which is called \emph{Hecke insertion}~\cite{BKSTY}. 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 $\varnothing$ in the M\"obius deformation of Young's lattice, and the construction of the recording tableau is represented as a path of length $n$ upward starting at $\varnothing$. We illustrate this in Example~\ref{ex:Heckewalks} after introducing the necessary definitions. An \emph{increasing tableau} is a filling of a Young diagram with positive integers such that the entries in rows are strictly increasing from left to right and the entries in columns are strictly increasing from top to bottom. \begin{exem} The tableau shown on the left is an increasing tableau. The tableau on the right is not an increasing tableau because the entries in the first row are not strictly increasing. \[ \begin{ytableau} 1 & 2 & 4 & 5 \\ 2 & 3 & 5 & 7 \\ 6 & 7 \\ 8 \end{ytableau}\hspace{1in} \begin{ytableau} 1 & 2 & 2 & 4 \\ 3 & 4 \\ 5 \end{ytableau} \] \end{exem} We follow~\cite{BKSTY} to give a description of Hecke (row) insertion of a positive integer $x$ into an increasing tableau $Y$ resulting in an increasing tableau $Z$. The shape of $Z$ is obtained from the shape of $Y$ by adding at most one box. If a box is added in position $(i,j)$, then we set $c=(i,j)$. In the case where no box is added, then $c=(i,j)$, where $(i,j)$ is a special corner indicating where the insertion process terminated. We will use a parameter $\alpha\in\{0,1\}$ to keep track of whether or not a box is added to $Y$ after inserting $x$ by setting $\alpha=0$ if $c\in Y$ and $\alpha=1$ if $c\notin Y$. We use the notation $Z=(Y {\overset{H}{\longleftarrow}} x)$ to denote the resulting tableau, and we denote the outcome of the insertion by $(Z,c,\alpha)$. We now describe how to insert $x$ into increasing tableau $Y$ by describing how to insert $x$ into $R$, a row of $Y$. This insertion may modify the row and may produce an output integer, which we will insert into the next row. To begin the insertion process, insert $x$ into the first row of $Y$. The process stops when there is no output integer. The rules for insertion of $x$ into $R$ are as follows: \renewcommand{\theenumi}{H\arabic{enumi}} \begin{enumerate} \item \label{H1} If $x$ is weakly larger than all integers in $R$ and adjoining $x$ to the end of row $R$ results in an increasing tableau, then $Z$ is the resulting tableau and $c$ is the new corner where $x$ was added. \item \label{H2} If $x$ is weakly larger than all integers in $R$ and adjoining $x$ to the end of row $R$ does not result in an increasing tableau, then $Z=Y$, and $c$ is the box at the bottom of the column of $Z$ containing the rightmost box of the row $R$. \end{enumerate} For the next two rules, assume $R$ contains boxes strictly larger than $x$, and let $y$ be the smallest such box. \begin{enumerate}\setcounter{enumi}{2} \item \label{H3} If replacing $y$ with $x$ results in an increasing tableau, then replace $y$ with $x$. In this case, $y$ is the output integer to be inserted into the next row \item \label{H4} If replacing $y$ with $x$ does not result in an increasing tableau, then do not change row $R$. In this case, $y$ is the output integer to be inserted into the next row. \end{enumerate} \begin{exem} \[ \begin{ytableau} $1$ & $2$ & $3$ & $5$ \\ $2$ & $3$ & $4$ & $6$ \\ $6$ \\ $7$ \end{ytableau}\ {\overset{H}{\longleftarrow}}\, 3\;=\; \begin{ytableau} $1$ & $2$ & $3$ & $5$ \\ $2$ & $3$ & $4$ & $6$ \\ $6$ \\ $7$ \end{ytableau} \] We use rule~\eqref{H4} in the first row to obtain output integer $5$. Notice that the $5$ cannot replace the $6$ in the second row since it would be directly below the $5$ in the first row. Thus we use~\eqref{H4} again and get output integer $6$. Since we cannot add this $6$ to the end of the third row, we use~\eqref{H2} and get $c=(4,1)$. Notice that the shape did not change in this insertion, so $\alpha=0$. \end{exem} \begin{exem}\label{ex:ins2} \[ \begin{ytableau} $2$ & $4$ & $6$ \\ $3$ & $6$ & $8$ \\ $7$ \end{ytableau}\ {\overset{H}{\longleftarrow}}\, 5\;=\; \begin{ytableau} $2$ & $4$ & $5$ \\ $3$ & $6$ & $8$ \\ $7$ & $8$ \end{ytableau} \] The integer $5$ bumps the $6$ from the first row using~\eqref{H3}. The $6$ is inserted into the second row, which already contains a $6$. Using~\eqref{H4}, the second row remains unchanged and we insert $8$ into the third row. Since $8$ is larger than everything in the third row, we use~\eqref{H1} to adjoin it to the end of the row. Thus $\alpha=1$. \end{exem} Using this insertion algorithm, we define the \emph{Hecke insertion tableau} of a word $w=w_1w_2\dots w_n$ to be \[ P_H(w)=(\dots((\varnothing\overset{H}{\longleftarrow} w_1)\overset{H}{\longleftarrow} w_2)\dots) \overset{H}{\longleftarrow} w_n. \] In~\cite{BKSTY}, Buch, Kresch, Shimozono, Tamvakis, and Yong give the following algorithm for reverse Hecke insertion starting with the triple $(Z,c,\alpha)$ as described above and ending with a pair $(Y,x)$ consisting of an increasing tableau and a positive integer. \renewcommand{\theenumi}{rH\arabic{enumi}} \begin{enumerate} \item \label{rH1} If $y$ is the cell in square $c$ of $Z$ and $\alpha=1$, then remove $y$ and reverse insert $y$ into the row above. \item \label{rH2} If $\alpha=0$, do not remove $y$, but still reverse insert it into the row above. \end{enumerate} Let $x$ be the largest integer in the row above square $c$ (if such a row exists) such that $x0$. Similarly, for fixed $i$, we have \[ \varnothing=\gamma(i,0)\subseteq\gamma(i,1)\subseteq\dots\subseteq\gamma(i,n), \] where $|\gamma(i,j)/\gamma(i,j-1)|=0$ or 1. Let $R(i,j)$ be the set-valued tableau of shape $\gamma(i,j)$ obtained by inserting $k$ into $\gamma(i,k)/\gamma(i,k-1)$ when $0\leq k\leq j$ and $|\gamma(k,j)/\gamma(k-1,j)|=1$ and by inserting $k$ into the rightmost cell in row $i$ of $\gamma(i,k)$ when $0\leq k\leq j$ and $|\gamma(k,j)/\gamma(k-1,j)|=0$ with the edge between them having label $i$. For example, in the growth diagram for $h=121331$ shown above, we have the tableaux below. \begin{gather*} T(1,3)= \begin{ytableau} 1 \end{ytableau} \hspace{.4in} T(2,3)=T(3,3)= \begin{ytableau} 1 & 2 \\ 2 \end{ytableau} \\ R(2,1)=\begin{ytableau} 1 \end{ytableau}\hspace{.3in} R(2,2)=\begin{ytableau} 1 & 2 \end{ytableau}\hspace{.3in} R(2,3)=R(2,4)=R(2,5)=\begin{ytableau} 1 & 2 \\ 3 \end{ytableau} \\ R(2,6)=\begin{ytableau} 1 & 2 \\ 36 \end{ytableau} \end{gather*} We will prove that $T(i,j)$ and $R(i,j)$ can also be defined as follows. Suppose the $X$'s to the left of and below $T(i,j)$ are in positions $(i_1,j_1),\dots,(i_k,j_k)$ with $j_1<\dots0$. By the induction hypothesis, $T(t-1,s)$, $T(t,s-1)$, and $T(t-1,s-1)$ satisfy the desired conditions. We next check that $T(t,s)$ satisfies the conditions.We will denote the shape of $T(t-1,s)$ by $\nu$,the shape of $T(t,s-1)$ by $\mu$, the shape of $T(t-1,s-1)$ by $\lambda$, and the shape of $T(t,s)$ by $\gamma$ to match the description of the growth rules. \begin{enumerate} \item \label{rule1} Since our square contains an X, there is no other X in the same column. It follows that $\lambda=\nu$. Also, the X in the square we are considering corresponds to inserting a $t$ into $T(t,s-1)$. Since, by the induction hypothesis, shapes along columns represent the insertion tableaux, $\mu_1=\nu_1=\lambda_1$ means that before adding the $t$, there are no $t$'s in the first row of $T(t,s-1)$. Since $t$ is weakly the largest number inserted to this point, inserting the $t$ will result in a $t$ being added to the first row of $T(t,s-1)$. Thus $\gamma=(\mu_1+1,\mu_2,\mu_3,\dots)$. \item \label{rule2} If $\mu_1\neq\nu_1=\lambda_1$, then there is a $t$ at the end of the first row of $T(t,s-1)$. It follows that inserting another $t$ will result in this $t$ merging with the $t$ at the end of the first row, and the special corner in this case becomes the bottom box of the last column, or in other words, the highest inner corner of $\mu$. \item \label{rule3} If $\mu=\lambda$ and there is no X in our square, then there is no X in row $t$ in columns $1$ to $s$. Thus there is no $t$ to add to $T(t-1,s)$ to obtain $T(t,s)$, and so $\nu=\gamma$. Similarly for the case where $\nu=\lambda$. \item \label{rule4} Suppose that $\nu/\lambda$ is one box in row $i$ and $\mu/\lambda$ is a rook strip containing boxes in rows $j_1,j_2,\dots,j_k$. Then $\nu \nsubseteq \mu$ implies that $i\notin \{j_1,j_2,\dots,j_k\}$. Since $\nu/\lambda$ is one box, the last action in the insertion sequence of $r$ into $T(t-1,s-1)$ is a box being added in row $i$, where $r$ is the row index of the X in column $s$. (We will continue to denote this row index by $r$ for the rest of the proof.) Since there is not a $t$ in row $i$ of $T(t,s-1)$, the bumping sequence when inserting $r$ into $T(t,s-1)$ will not disturb the $t$'s. \item \label{rule5} Suppose $\nu$ is $\lambda$ plus one box in position $(i,j)$. Then since $\nu \subseteq \mu$, $\mu/\lambda$ contains the box at $(i,j)$, and so there is a $t$ in position $(i,j)$ of $T(t,s-1)$. It follows that inserting $r$ into $T(t,s-1)$ will result in bumping the $t$ in position $(i,j)$ since the bumping path of $r$ inserted into $T(t-1,s-1)$ ends by adding a box at $(i,j)$. Since there is no box in row $i+1$ of $\mu/\lambda$, everything in row $i+1$ of $T(t,s-1)$ is strictly less than $t$. It follows that the $t$ bumped from $(i,j)$ can be added to the end of row $i+1$. \item \label{rule6} This is almost identical to the proof of Rule~\eqref{rule4}. Since there is now a box in row $i+1$ of $\mu/\lambda$, there is a $t$ at the end of row $i+1$ of $T(t,s-1)$. Inserting $r$ will bump the $t$ in row $i$ as above, but now the $t$ will merge with the $t$ in row $i+1$. Thus the special corner is now at the inner corner of $\mu$ in row $i+1$. \item \label{rule7} There are two ways that inserting $r$ into $T(t,s-1)$ will involve the $t$'s. Assume the edge between $\nu$ and $\lambda$ is labeled $i$, and the inner corner of $\nu$ in row $i$ is in column $j$. Assume rows $k$ through $i$ all have length $j$ in $\nu$ for some $k\leq i$. \smallskip\noindent \casetext{Case 1.} A box containing some $y\geq r$ was bumped from row $k-1$ of $T(t,s-1)$ or inserted into $T(t,s-1)$ if $k=1$, merged with itself in row $k$, and there was a $t$ to the right of the $y$ in row $k$. Note that $k\neq i$. Then the $y$ duplicates and bumps the $t$ in row $k$ of $T(t,s-1)$, but this $t$ cannot be added to row $k+1$ as it would be directly below the original $t$. Thus, by the rules of Hecke insertion, the special corner is the box at the bottom of column $j$, box $(i,j)$. See the left-hand figure below where the dot indicates the box $(i,j)$. \smallskip\noindent \casetext{Case 2.} Consider the situation in the right-hand figure below where the dot indicates the box $(i,j)$. Assume that during the insertion of $r$ into $T(t,s-1)$, some number merged with itself to the left of $z$ in row $k-1$ and $z$ is duplicated bumped to the next row. Following the rules of Hecke insertion, $z$ bumps the $t$ in row $k$, but as it cannot replace the $t$, the $t$ remains at the end of row $k$. The $t$ that was bumped cannot be added to end of row $k+1$, so no new boxes are created in the insertion and the special corner is the box at the bottom of column $j$, box $(i,j)$. \[ \includegraphics[scale=0.7]{6.pdf} \] \item \label{rule8} There are three ways that inserting $r$ into $T(t,s-1)$ will involve the $t$'s. Assume the edge between $\nu$ and $\lambda$ is labeled $i$, and the inner corner of $\nu$ in row $i$ is in column $j$. Assume rows $k$ through $i$ all have length $j$ in $\nu$. \smallskip\noindent \casetext{Case 1.} If there is a $t$ in square $(i,j+1)$, we are in the situation described by Rule~\eqref{rule9}. \smallskip Cases 2 and 3 are described in the proof of Rule~\eqref{rule7}. The difference is that the bottom of column $j$ after we insert $r$ is now the box $(i+1,j)$, so the special corner in each case will be $(i+1,j)$, as desired. \[ \includegraphics[scale=0.7]{7.pdf} \] \item \label{rule9} Note that an edge label of $i$ between $\lambda$ and $\nu$ with a box of $\mu/\nu$ in row $i$ implies that $\nu_{i-1}>\nu_i>\nu_{i+1}$. There are two ways the special corner of the insertion of $r$ into the $T(t-1,s-1)$ could have been $(i,j)$. \smallskip\noindent \casetext{Case 1.} Some $y$ was bumped from row $i-1$ and merged with itself in box $(i,j)$. Since there is a $t$ to the right of box $(i,j)$ in $T(t,s-1)$, this will result in duplicating and bumping $t$. Since there is nothing in row $i+1$ of $\mu/\nu$, everything in row $i+1$ of $T(t,s-1)$ is strictly less than $t$. Hence the $t$ bumped from row $i$ of $T(t,s-1)$ can be added to the end of row $i+1$. \smallskip\noindent \casetext{Case 2.} As in the figure below, $z$ was duplicated and bumped from box $(i-1,j+1)$. This $z$ cannot replace the $t$ in box $(i,j+1)$ of $T(t,s-1)$ since it would be directly below the original $z$, but it bumps the $t$ to row $i+1$. Since there is nothing in row $i+1$ of $\mu/\nu$, everything in row $i+1$ of $T(t,s-1)$ is strictly less than $t$. Hence the $t$ bumped from row $i$ can be added to the end of row $i+1$ of $T(t,s-1)$ to obtain $T(t,s)$. \[ \includegraphics[scale=0.7]{8.pdf} \] \item \label{rule10} This is similar to the situation described in the proof of Rule 9. The difference is that a box in row $i+1$ of $\mu/\nu$ means there is already a $t$ at the end of row $i+1$ of $T(t,s-1)$, so each insertion will end with the bumped $t$ merging with itself at the end of row $i+1$. \[ \includegraphics[scale=0.7]{9.pdf}\qedhere \] \end{enumerate} \end{proof} \subsection{M\"obius via Pieri} \label{ex:G} The following shows that we have an instance of the M\"obius via Pieri phenomenon in the case of Young's lattice. Namely, the M\"obius deformation of Young's lattice is obtained by the Pieri construction from an appropriate $K$-theoretic deformation of the underlying Hopf algebra. Let $A$ 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~\cite{B, LP}. Define the \emph{signless stable Grothendieck polynomials} $\tilde G_\lambda$ by omitting the sign. Note that these coincide with the $\tilde K_\lambda$ defined in~\cite{LP}. The structure constants will coincide with those of the stable Grothendieck polynomials up to sign. We recall these structure constants here. 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. Given an increasing tableau $R$, let $\row(R)$ denote the \emph{row word} of $R$: the word obtained by reading the entries of $R$ left to right across rows from the bottom row to the top row. This space has a bialgebra product structure given by \[ \tilde G_\lambda \tilde G_\mu=\displaystyle\sum c_{\lambda,\mu}^\nu \tilde G_\nu, \] where $c_{\lambda,\mu}^\nu$ is the number of increasing tableaux $R$ of skew shape $\nu/\lambda$ such that $P_H(\row(R))=S_\mu$. The coproduct structure is given by \[ \Delta(\tilde G_\nu)=\displaystyle\sum_{\lambda,\mu} d_{\lambda,\mu}^\nu \tilde G_\lambda \otimes \tilde G_\mu, \] where $d_{\lambda,\mu}^\nu$ is the number of increasing tableaux $R$ of skew shape $\lambda \oplus \mu$ such that $P_H(\row(R))=S_\nu$, see~\cite{BuchSam, PP,ThY3}. Here $\lambda\oplus\mu$ denotes the skew shape obtained by joining the rightmost top corner of $\lambda$ to the leftmost bottom corner of $\mu$. For example, $(2,1)\oplus (2,2)=(4,4,2,1)/(2,2)$ is shown below. \[ \begin{ytableau} \none & \none & $ $ & $ $ \\ \none & \none & $ $ & $ $ \\ $ $ & $ $ \\ $ $ \end{ytableau} \] We consider the following Pieri construction in $A$. Let $g=\tilde G_1$, and define an operator $d$ by $d(\tilde G_\nu)=\xi(\Delta(\tilde G_\nu))$. We define a graph $G$, where elements are partitions, $a_1(\mu,\lambda)$ is the coefficient of $\tilde G_\mu$ in $d(\tilde G_\lambda)$, and $a_2(\mu,\lambda)$ is the coefficient of $\tilde G_\lambda$ in $\tilde G_\mu \tilde G_1$. Here, our element $f=f_1+f_2+\dots\in\hat{A}$ is $\tilde G_1$. \begin{prop}\label{prop:mobpieriyoung} The resulting graph coincides with the one obtained via M\"obius construction in Section~\ref{sec:MobiusYoung}. \[ \begin{tikzpicture}[scale=.9] \node (empty) at (0,0) {$\varnothing$}; \node (1) at (0,1) {\ytableausetup{boxsize=.15cm}\begin{ytableau}$ $ \end{ytableau}}; \node (2) at (1,2) {\begin{ytableau}$ $ & $ $ \end{ytableau}}; \node (11) at (-1,2) {\begin{ytableau}$ $ \\ $ $ \end{ytableau}}; \node (111) at (-2,3) {\begin{ytableau}$ $ \\ $ $ \\ $ $ \end{ytableau}}; \node (21) at (0,3) {\begin{ytableau}$ $ & $ $ \\ $ $ \end{ytableau}}; \node (3) at (2,3) {\begin{ytableau}$ $ & $ $ & $ $ \end{ytableau}}; \node (1111) at (-3,4) {\begin{ytableau}$ $ \\ $ $ \\ $ $ \\ $ $\end{ytableau}}; \node (211) at (-1,4) {\begin{ytableau}$ $ & $ $ \\ $ $ \\ $ $\end{ytableau}}; \node (22) at (0,4) {\begin{ytableau}$ $ & $ $ \\ $ $ & $ $ \end{ytableau}}; \node (31) at (1,4) {\begin{ytableau}$ $ & $ $ & $ $ \\ $ $\end{ytableau}}; \node (4) at (3,4) {\begin{ytableau}$ $ & $ $ & $ $ & $ $\end{ytableau}}; \draw (empty) -- (1) (1) -- (2)--(3)--(4) (1)--(11)--(111)--(1111) (11)--(21)--(31) (111)--(211) (3)--(31) (21)--(22) (2)--(21)--(211) (1) to [out=60,in=100,distance=.5cm] (1) (2) to [out=60,in=100,distance=.5cm] (2) (11) to [out=60,in=100,distance=.5cm] (11) (3) to [out=60,in=100,distance=.5cm] (3) (4) to [out=60,in=100,distance=.5cm] (4) (111) to [out=60,in=100,distance=.5cm] (111) (1111) to [out=60,in=100,distance=.5cm] (1111) (21) to [out=-60,in=-100,distance=.5cm] (21) (21) to [out=-60,in=-100,distance=.7cm] (21) (211) to [out=60,in=100,distance=.5cm] (211) (211) to [out=60,in=100,distance=.7cm] (211) (31) to [out=60,in=100,distance=.5cm] (31) (31) to [out=60,in=100,distance=.7cm] (31) (22) to [out=60,in=100,distance=.5cm] (22) ; \end{tikzpicture} \hspace{.1in} \raisebox{-.1in}{ \begin{tikzpicture}[scale=.9] \node (empty) at (0,0) {$\varnothing$}; \node (1) at (0,1) {\ytableausetup{boxsize=.15cm}\begin{ytableau}$ $ \end{ytableau}}; \node (2) at (1,2) {\begin{ytableau}$ $ & $ $ \end{ytableau}}; \node (11) at (-1,2) {\begin{ytableau}$ $ \\ $ $ \end{ytableau}}; \node (111) at (-2,3) {\begin{ytableau}$ $ \\ $ $ \\ $ $ \end{ytableau}}; \node (21) at (0,3) {\begin{ytableau}$ $ & $ $ \\ $ $ \end{ytableau}}; \node (3) at (2,3) {\begin{ytableau}$ $ & $ $ & $ $ \end{ytableau}}; \node (1111) at (-3,4) {\begin{ytableau}$ $ \\ $ $ \\ $ $ \\ $ $\end{ytableau}}; \node (211) at (-1,4) {\begin{ytableau}$ $ & $ $ \\ $ $ \\ $ $\end{ytableau}}; \node (22) at (0,4) {\begin{ytableau}$ $ & $ $ \\ $ $ & $ $ \end{ytableau}}; \node (31) at (1,4) {\begin{ytableau}$ $ & $ $ & $ $ \\ $ $\end{ytableau}}; \node (4) at (3,4) {\begin{ytableau}$ $ & $ $ & $ $ & $ $\end{ytableau}}; \draw (empty) -- (1) (1) -- (2)--(3)--(4) (1)--(11)--(111)--(1111) (11)--(21)--(31) (111)--(211) (3)--(31) (21)--(22) (2)--(21)--(211) (21)--(1) (31)--(2) (211)--(11); \end{tikzpicture}} \] \ytableausetup{boxsize=.5cm} \end{prop} \begin{proof} To verify this claim, we first show why the coefficient of $\tilde G_\nu$ in $\tilde G_\lambda \tilde G_1$ is 1 if $\nu/\lambda$ is a rook strip and is 0 otherwise. This follows from that fact that the only words that Hecke insert into $S_1$ are words consisting only of the letter $1$. Thus, $\row(R)=11\dots 1$ for any $R$ contributing to $c_{\lambda,1}^\nu$. Increasing tableaux of shape $\nu/\lambda$ with row word $11\dots 1$ are precisely rook strips. Secondly, it must be true that $d_{\lambda,1}^\lambda$ is the number of inner corners of $\lambda$ and if $\nu\neq\lambda$, $d_{\lambda,1}^\nu$ is 1 if $\nu$ is obtained from $\lambda$ by adding one box and 0 otherwise. Suppose $\nu\neq\lambda$ and consider all skew tableaux $R$ of shape $\lambda \oplus 1$ such that $P_H(\row(R))=S_\nu$. To obtain such $\lambda$, simply reverse insert an entry of $S_\nu$ with $\alpha=1$ and use the output integer to fill the single box in $\lambda\oplus 1$. The resulting shapes are the shapes obtained from $\nu$ by deleting one inner corner of $\nu$. Similarly, if $\nu=\lambda$, we reverse insert each inner corner of $S_\lambda$ using $\alpha=0$ and then let $R$ be $S_\lambda\oplus x$, where $x$ is the result of the reverse insertion. \end{proof} \section{Major examples: shifted Young's lattice} \label{sec:sY} \subsection{Pieri deformation of shifted Young's lattice} Let $A=\Lambda'$ be the subring of the ring of symmetric functions generated by the odd power sums $p_1, p_3, \dots$. Let $Q_{\lambda}$ and $P_{\lambda}$ be the bases of Schur $Q$ and Schur $P$ functions for this ring. Here $\lambda$ varies over the set of partitions with distinct parts. We refer the reader to~\cite{Mac} for background. Let $q_i$ be defined by \[ q_i=\sum_{0\leq j\leq i} e_j h_{i-j}, \] and let $f= q_1 + q_2 + \cdots.$ Define up and down edges of the Pieri deformation of shifted Young's lattice $G=(P, \rho, E_1, E_2)$ by letting $a_2(\mu, \nu)$ be the coefficient of $Q_\mu$ in $fQ_\nu$ and $a_1(\mu,\nu)$ be the coefficient of $P_\mu$ in $p_1P_\nu$. We will fill a shifted partition $\lambda$ with ordered alphabet $1'<1<2'<2<3'<3\dots$ according to the usual rules: \begin{itemize} \item the filling must be weakly increasing in rows and columns; \item there can be at most one instance of $k'$ in any row; \item there can be at most one instance of $k$ in any column; \item there can be no primed entries on the main diagonal. \end{itemize} For example, the shifted partition below is filled according to the rules stated above. \[ \begin{ytableau} 1 & 2' & 2 & 2 & 4' \\ \none & 2 & 3' & 5' & 5 \\ \none & \none & 4 & 5' \\ \none & \none & \none & 6 \end{ytableau} \] Given two shifted shapes, $\mu$ and $\nu$, we say that $\mu/\nu$ forms a \emph{border strip} if it contains no 2-by-2 square. \begin{lemm} The Pieri deformation of the shifted Young's lattice is formed by adding downward-oriented edges from $\mu$ to $\nu$ whenever $\mu/\nu$ forms a border strip. The number of such edges added is the same as the number of ways to fill the boxes of the border strip with $k$ and $k'$ according to the usual rules. \end{lemm} \begin{proof} The proof follows from Formula (8.15) in Chapter~III of~\cite{Mac}, which is an analogue of the Pieri rule for Schur $P$ functions, and the fact that $q_1=2 p_1$. \end{proof} The first six ranks of the Pieri deformation are shown below. \[ \begin{tikzpicture} \node (empty) at (0,0) {$\varnothing$}; \node (1) at (0,1) {\ytableausetup{boxsize=.15cm}\begin{ytableau}$ $ \end{ytableau}}; \node (2) at (0,2) {\begin{ytableau}$ $ & $ $ \end{ytableau}}; \node (3) at (1,3) {\begin{ytableau}$ $ & $ $ & $ $ \end{ytableau}}; \node (21) at (-1,3) {\begin{ytableau}$ $ & $ $ \\ \none & $ $ \end{ytableau}}; \node (31) at (0,4) {\begin{ytableau}$ $ & $ $ & $ $\\ \none & $ $ \end{ytableau}}; \node (4) at (2,4) {\begin{ytableau}$ $ & $ $ & $ $ & $ $ \end{ytableau}}; \node (32) at (-1,5) {\begin{ytableau}$ $ & $ $ & $ $\\ \none & $ $ & $ $\end{ytableau}}; \node (41) at (1,5) {\begin{ytableau}$ $ & $ $ & $ $ & $ $ \\ \none & $ $ \end{ytableau}}; \node (5) at (3,5) {\begin{ytableau}$ $ & $ $ & $ $ & $ $ & $ $ \end{ytableau}}; \draw (empty)--(1)--(2)--(3)--(4)--(5) (2)--(21)--(31)--(32) (3)--(31)--(41) (4)--(41); \end{tikzpicture} \qquad \begin{tikzpicture} \node (empty) at (0,0) {$\varnothing$}; \node (1) at (0,1) {\ytableausetup{boxsize=.15cm}\begin{ytableau}$ $ \end{ytableau}}; \node (2) at (0,2) {\begin{ytableau}$ $ & $ $ \end{ytableau}}; \node (3) at (1,3) {\begin{ytableau}$ $ & $ $ & $ $ \end{ytableau}}; \node (21) at (-1,3) {\begin{ytableau}$ $ & $ $ \\ \none & $ $ \end{ytableau}}; \node (31) at (0,4) {\begin{ytableau}$ $ & $ $ & $ $\\ \none & $ $ \end{ytableau}}; \node (4) at (2,4) {\begin{ytableau}$ $ & $ $ & $ $ & $ $ \end{ytableau}}; \node (32) at (-1,5) {\begin{ytableau}$ $ & $ $ & $ $\\ \none & $ $ & $ $\end{ytableau}}; \node (41) at (1,5) {\begin{ytableau}$ $ & $ $ & $ $ & $ $ \\ \none & $ $ \end{ytableau}}; \node (5) at (3,5) {\begin{ytableau}$ $ & $ $ & $ $ & $ $ & $ $ \end{ytableau}}; \draw (empty) -- (1) to [bend right=5] (2) (2) to [bend left=5] (3) (3) to [bend left=5] (2) (2) -- (21) to [bend left=5] (31) (21) to [bend right=5] (31) (1) to [bend left=5] (2) (3) to [bend left=5] (4) (3) to [bend right=5] (4) (3) -- (31) to [bend left=5] (41) (31) to [bend right=5] (41) (31) to [bend left=5] (32) (31) to [bend right=5] (32) (4) to [bend right=5] (5) (4) to [bend left=5] (5) (2) to [bend left=15] (empty) (3) to [bend left=15] (1) (3) to [bend left=25] (1) (3) to [bend left=15] (empty) (4) to [bend left=15] (2) (4) to [bend left=25] (2) (4) to [bend left=15] (1) (4) to [bend left=25] (1) (4) to [bend left=15] (empty) (5) to [bend left=15] (3) (5) to [bend left=25] (3) (5) to [bend left=15] (2) (5) to [bend left=25] (2) (5) to [bend left=15] (1) (5) to [bend left=25] (1) (5) to [bend left=15] (empty) (31) to [bend left=5] (2) (31) to [bend right=5] (2) (31) to [bend right=15] (1) (21) to [bend right=15] (1) (32) to [bend right=20] (3) (41) to [bend left=5] (3) (41) to [bend right=5] (3) (41) to [bend right=15] (21) (41) to [bend right=20] (21) (41) to [bend left=5] (2) (41) to [bend right=5] (2) (32) -- (2) (4) -- (41); \end{tikzpicture} \ytableausetup{boxsize=.5cm} \] Notice that there are two edges from $41$ to $2$ corresponding to the following fillings of the border strip $(4,1)/(2)$. \[ \begin{ytableau} \none & \none & $k$' & $k$ \\ \none & $k$ \end{ytableau}\hspace{1in} \begin{ytableau} \none & \none & $k$ & $k$ \\ \none & $k$ \end{ytableau} \] \begin{theo}\label{thm:syoung} The Pieri deformation of the dual graded graph of shifted shapes satisfies \[ DU-UD=D+I. \] \end{theo} We shall need the following two properties of $\Lambda'$. \begin{theo}[\cite{Mac}]\ \begin{itemize} \item $\Lambda'$ is a free polynomial ring in odd power sums $p_1, p_3, \dots$. \item $\Lambda'$ inherits the standard bilinear inner product from $\Lambda$, which satisfies $\langle Q_{\lambda}, P_{\mu} \rangle=2^{l(\mu)} \delta_{\lambda, \mu}$. \end{itemize} \end{theo} Because of the first property, we can again differentiate elements of $\Lambda'$ with respect to $p_1$ by expressing them first as a polynomial in the $p_i$'s. We shall need the following property of $f$. \begin{lemm}\label{lem:syoung} We have \[ \frac{\dd}{\dd p_1} f=2f+2. \] \end{lemm} \begin{proof} From~\cite[Ex.~6 (a), III, 8]{Mac} we have \[ 1 + f= e^{2p_1 + \frac{2p_3}{3} + \cdots}, \] which of course implies $\frac{\dd}{\dd p_1} (1+f)=2+2f$. \end{proof} Now we are ready for the proof of Theorem~\ref{thm:syoung}. \begin{proof} Applying Lemma~\ref{lem:young} we see that $A=\Lambda'$, $a_{\lambda}= Q_{\lambda}$, $d=\frac{1}{2} \frac{\dd}{\dd p_1}$ and $f= q_1 + q_2 + \cdots$ satisfy the conditions of Theorem~\ref{thm:pieri}. The claim follows. \end{proof} \begin{rema} If we instead take $a_1(\mu, \nu)$ to be 2 times the coefficient of $Q_{\nu} \text{ in } p_1 Q_{\mu}$, and $a_2(\mu, \nu)$ to be $\frac{1}{2}$ times the coefficient of $P_{\mu} \text{ in } f P_{\nu},$ we get a dual filtered graph with \[ DU-UD=2D+I. \] This choice corresponds to first swapping $E_1$ and $E_2$ in the original dual graded graph of $\mathbb{SY}$ and then adding downward edges to $E_2$ as described above. \[ \begin{tikzpicture} \node (empty) at (0,0) {$\varnothing$}; \node (1) at (0,1) {\ytableausetup{boxsize=.15cm}\begin{ytableau}$ $ \end{ytableau}}; \node (2) at (0,2) {\begin{ytableau}$ $ & $ $ \end{ytableau}}; \node (3) at (1,3) {\begin{ytableau}$ $ & $ $ & $ $ \end{ytableau}}; \node (21) at (-1,3) {\begin{ytableau}$ $ & $ $ \\ \none & $ $ \end{ytableau}}; \node (31) at (0,4) {\begin{ytableau}$ $ & $ $ & $ $\\ \none & $ $ \end{ytableau}}; \node (4) at (2,4) {\begin{ytableau}$ $ & $ $ & $ $ & $ $ \end{ytableau}}; \node (32) at (-1,5) {\begin{ytableau}$ $ & $ $ & $ $\\ \none & $ $ & $ $\end{ytableau}}; \node (41) at (1,5) {\begin{ytableau}$ $ & $ $ & $ $ & $ $ \\ \none & $ $ \end{ytableau}}; \node (5) at (3,5) {\begin{ytableau}$ $ & $ $ & $ $ & $ $ & $ $ \end{ytableau}}; \draw (empty)--(1) to [bend right=5] (2) (2) to [bend left=5] (3) (3) to [bend left=5] (2) (2) -- (21) to [bend left=5] (31) (21) to [bend right=5] (31) (1) to [bend left=5] (2) (3) to [bend left=5] (4) (3) to [bend right=5] (4) (3) -- (31) to [bend left=5] (41) (31) to [bend right=5] (41) (31) to [bend left=5] (32) (31) to [bend right=5] (32) (4) to [bend right=5] (5) (4) -- (41) (4) to [bend left=5] (5); \end{tikzpicture} \qquad \begin{tikzpicture} \node (empty) at (0,0) {$\varnothing$}; \node (1) at (0,1) {\ytableausetup{boxsize=.15cm}\begin{ytableau}$ $ \end{ytableau}}; \node (2) at (0,2) {\begin{ytableau}$ $ & $ $ \end{ytableau}}; \node (3) at (1,3) {\begin{ytableau}$ $ & $ $ & $ $ \end{ytableau}}; \node (21) at (-1,3) {\begin{ytableau}$ $ & $ $ \\ \none & $ $ \end{ytableau}}; \node (31) at (0,4) {\begin{ytableau}$ $ & $ $ & $ $\\ \none & $ $ \end{ytableau}}; \node (4) at (2,4) {\begin{ytableau}$ $ & $ $ & $ $ & $ $ \end{ytableau}}; \node (32) at (-1,5) {\begin{ytableau}$ $ & $ $ & $ $\\ \none & $ $ & $ $\end{ytableau}}; \node (41) at (1,5) {\begin{ytableau}$ $ & $ $ & $ $ & $ $ \\ \none & $ $ \end{ytableau}}; \node (5) at (3,5) {\begin{ytableau}$ $ & $ $ & $ $ & $ $ & $ $ \end{ytableau}}; \draw (empty)--(1)--(2)--(3)--(4)--(5) (2)--(21)--(31)--(32) (3)--(31)--(41) (4)--(41) (2) to [bend left=15] (empty) (3) to [bend left=15] (1) (3) to [bend left=25] (1) (3) to [bend left=15] (empty) (4) to [bend left=15] (2) (4) to [bend left=25] (2) (4) to [bend left=15] (1) (4) to [bend left=25] (1) (4) to [bend left=15] (empty) (5) to [bend left=15] (3) (5) to [bend left=25] (3) (5) to [bend left=15] (2) (5) to [bend left=25] (2) (5) to [bend left=15] (1) (5) to [bend left=25] (1) (5) to [bend left=15] (empty) (31) to [bend left=5] (2) (31) to [bend right=5] (2) (31) to [bend right=15] (1) (21) to [bend right=15] (1) (32) to [bend right=20] (3) (41) to [bend left=5] (3) (41) to [bend right=5] (3) (41) to [bend right=15] (21) (41) to [bend right=20] (21) (41) to [bend left=5] (2) (41) to [bend right=5] (2) (32) -- (2) (4) -- (41); \end{tikzpicture} \] \end{rema} \subsection{M\"obius deformation of shifted Young's lattice} The M\"obius deformation of the shifted Young's lattice is shown below with upward-oriented edges shown on the left and downward-oriented edges on the right. Note that we swapped the $E_1$ and $E_2$ of Example~\ref{ex:shifted}. \[ \begin{tikzpicture} \node (empty) at (0,0) {$\varnothing$}; \node (1) at (0,1) {\ytableausetup{boxsize=.15cm}\begin{ytableau}$ $ \end{ytableau}}; \node (2) at (0,2) {\begin{ytableau}$ $ & $ $ \end{ytableau}}; \node (3) at (1,3) {\begin{ytableau}$ $ & $ $ & $ $ \end{ytableau}}; \node (21) at (-1,3) {\begin{ytableau}$ $ & $ $ \\ \none & $ $ \end{ytableau}}; \node (31) at (0,4) {\begin{ytableau}$ $ & $ $ & $ $\\ \none & $ $ \end{ytableau}}; \node (4) at (2,4) {\begin{ytableau}$ $ & $ $ & $ $ & $ $ \end{ytableau}}; \node (32) at (-1,5) {\begin{ytableau}$ $ & $ $ & $ $\\ \none & $ $ & $ $\end{ytableau}}; \node (41) at (1,5) {\begin{ytableau}$ $ & $ $ & $ $ & $ $ \\ \none & $ $ \end{ytableau}}; \node (5) at (3,5) {\begin{ytableau}$ $ & $ $ & $ $ & $ $ & $ $ \end{ytableau}}; \draw (empty) -- (1) to [bend right=5] (2) (2) to [bend left=5] (3) (3) to [bend left=5] (2) (2) -- (21) to [bend left=5] (31) (21) to [bend right=5] (31) (1) to [bend left=5] (2) (3) to [bend left=5] (4) (3) to [bend right=5] (4) (3) -- (31) to [bend left=5] (41) (31) to [bend right=5] (41) (31) to [bend left=5] (32) (31) to [bend right=5] (32) (4) to [bend right=5] (5) (4) to [bend left=5] (5) (4) -- (41) (1) to [out=160,in=100,distance=.5cm] (1) (2) to [out=60, in=100, distance=.5cm] (2) (2) to [out=60, in=100, distance=.7cm] (2) (21) to [out=60, in=100, distance=.5cm] (21) (3) to [out=60, in=100, distance=.5cm] (3) (3) to [out=60, in=100, distance=.7cm] (3) (4) to [out=60, in=100, distance=.5cm] (4) (4) to [out=60, in=100, distance=.7cm] (4) (5) to [out=60, in=100, distance=.5cm] (5) (5) to [out=60, in=100, distance=.7cm] (5) (31) to [out=60, in=100, distance=.5cm] (31) (31) to [out=60, in=100, distance=.7cm] (31) (31) to [out=60, in=100, distance=.9cm] (31) (41) to [out=60, in=100, distance=.5cm] (41) (41) to [out=60, in=100, distance=.7cm] (41) (41) to [out=60, in=100, distance=.9cm] (41) (32) to [out=60, in=100, distance=.5cm] (32) (32) to [out=60, in=100, distance=.7cm] (32); \end{tikzpicture}\qquad \raisebox{-.2in}{ \begin{tikzpicture} \node (empty) at (0,0) {$\varnothing$}; \node (1) at (0,1) {\ytableausetup{boxsize=.15cm}\begin{ytableau}$ $ \end{ytableau}}; \node (2) at (0,2) {\begin{ytableau}$ $ & $ $ \end{ytableau}}; \node (3) at (1,3) {\begin{ytableau}$ $ & $ $ & $ $ \end{ytableau}}; \node (21) at (-1,3) {\begin{ytableau}$ $ & $ $ \\ \none & $ $ \end{ytableau}}; \node (31) at (0,4) {\begin{ytableau}$ $ & $ $ & $ $\\ \none & $ $ \end{ytableau}}; \node (4) at (2,4) {\begin{ytableau}$ $ & $ $ & $ $ & $ $ \end{ytableau}}; \node (32) at (-1,5) {\begin{ytableau}$ $ & $ $ & $ $\\ \none & $ $ & $ $\end{ytableau}}; \node (41) at (1,5) {\begin{ytableau}$ $ & $ $ & $ $ & $ $ \\ \none & $ $ \end{ytableau}}; \node (5) at (3,5) {\begin{ytableau}$ $ & $ $ & $ $ & $ $ & $ $ \end{ytableau}}; \draw (empty)--(1)--(2)--(3)--(4)--(5) (31)--(2) (41)--(3) (2)--(21)--(31)--(32) (3)--(31)--(41) (4)--(41); \end{tikzpicture}} \ytableausetup{boxsize=.5cm} \] \begin{lemm} For the lattice of shifted shapes, the M\"obius function is given by the following formula: \[ \mu(p,q)= \begin{cases} (-1)^{|p|-|q|} & \text{if }q/p\text{ is a disjoint union of boxes} \\ 0 & \text{otherwise} \end{cases} \] \end{lemm} \begin{proof} It is known that $\mathbb{SY}$ is a distributive lattice~\cite[Example~2.2.8]{F}, and so it follows that $\mu(p,q)$ is nonzero if and only if the interval $[p,q]$ is a Boolean lattice, in which case $\mu(p,q)$ is as described above, \cite[Example~3.9.6]{EC2}. And $[p,q]$ is a Boolean lattice exactly when $q/p$ is a disjoint union of boxes, i.e. no two boxes of $q/p$ share an edge. \end{proof} \begin{theo} The M\"obius deformation of the shifted Young's lattice forms a dual filtered graph with \[ DU-UD=D+I. \] \end{theo} \begin{proof} Given that the non-deformed pair form a pair of dual graded graphs, it suffices to show that \[ [\lambda](DU-UD)(\mu)=[\lambda](D)(\mu) \] when $\mu$ covers $\lambda$ in $G_2$. For a shifted shape $\lambda$, let $I_{diag}(\lambda)$ denote the size of the set of inner corners of $\lambda$ that are on the diagonal, $I_{odiag}(\lambda)$ denote the size of the set of inner corners of $\lambda$ that are not on the diagonal, $O_{diag}(\lambda)$ denote the size of the set of outer corners of $\lambda$ that are on the diagonal, and $O_{odiag}(\lambda)$ denote the size of the set of outer corners of $\lambda$ that are not on the diagonal. \begin{lemm}\label{lem:shiftededges} For any shifted shape $\lambda$, \[ O_{diag}(\lambda) + 2O_{odiag}(\lambda)-I_{diag}(\lambda)-2I_{odiag}(\lambda)=1. \] \end{lemm} \begin{proof} Consider some element $\lambda=(\lambda_1,\lambda_2,\dots,\lambda_k)$. Suppose $\lambda_k=1$. We can add a box at some subset of rows $\{i_1=1,i_2,\dots,i_t\}$ and fill each with either $s$ or $s'$. Thus $O_{diag}(\lambda) + 2O_{odiag}(\lambda)=2t$. We can delete a box in rows $\{i_2-1,i_3-1,\dots,i_t-1,k\}$, where each can be filled with $s$ or $s'$ except the box in row $k$, which is on the diagonal. Thus $I_{diag}(\lambda)+2I_{odiag}(\lambda)=2(t-1)+1$. Now suppose $\lambda_k\geq2$. We can add a box at some subset of rows $\{i_1=1,i_2,\dots,i_t,\linebreak k+1\}$ and fill each with either $s$ or $s'$ except for the box in row $k+1$, which is on the diagonal. This gives $O_{diag}(\lambda) + 2O_{odiag}(\lambda)=2t+1$. We can delete boxes in rows $\{i_2-1,\dots,i_t-1,k\}$, where each can be filled with $s$ or $s'$, giving $I_{diag}(\lambda)+\linebreak 2I_{odiag}(\lambda)=2t$. \end{proof} First, consider all up-down paths from $\mu$ to $\lambda$ that begin with a loop at $\mu$. There~are \[ 2I_{odiag}(\mu)+I_{diag}(\mu) \] such paths since there are the same number of loops at $\mu$. Up-down paths that do not start with a loop can be counted by the number of outer corners of $\lambda$ that are not inner corners of $q$ counted with multiplicity two if they are off the main diagonal since each of these corners may be added to $q$ for the step up and then removed in addition to the boxes of $\mu/\lambda$ for the step down. There are \[ 2(O_{odiag}(\lambda)-I_{odiag}(\mu/\lambda))+(O_{diag}(\lambda)-I_{diag}(\mu/\lambda)) \] such corners. Thus there are \[ 2I_{odiag}(\mu)+I_{diag}(\mu)+2(O_{odiag}(\lambda)-I_{odiag}(\mu/\lambda))+(O_{diag}(\lambda)-I_{diag}(\mu/\lambda)) \] up-down paths from $\mu$ to $\lambda$. Next, consider all down-up paths from $\mu$ to $\lambda$ that end with a loop at $\lambda$. There are exactly \[ 2I_{odiag}(\lambda)+I_{diag}(\lambda) \] such paths. Down-up paths that do not end with a loop can be counted by the inner corners of $q$ that are also inner corners of $\lambda$ counted twice if they are off the main diagonal since removing this type of inner corner in addition to the boxes of $\lambda/\mu$ will result in a shifted shape covered by $\lambda$. There are \[ 2(I_{odiag}(\mu)-I_{odiag}(\mu/\lambda))+(I_{diag}(\mu)-I_{diag}(\mu/\lambda)) \] such corners. Thus there are \[ 2I_{odiag}(\lambda)+I_{diag}(\lambda)+2(I_{odiag}(\mu)-I_{odiag}(\mu/\lambda))+(I_{diag}(\mu)-I_{diag}(\mu/\lambda)) \] down-up paths from $\mu$ to $\lambda$. Hence \begin{align*} [\lambda](DU-UD)(\mu) &= 2I_{odiag}(\mu)+I_{diag}(\mu)+2(O_{odiag}(\lambda)-I_{odiag}(\mu/\lambda))\\ &\qquad+(O_{diag}(\lambda)-I_{diag}(\mu/\lambda)) -(2I_{odiag}(\lambda)+ I_{diag}(\lambda)\\ &\qquad+2(I_{odiag}(\mu)-I_{odiag}(\mu/\lambda))+(I_{diag}(\mu)-I_{diag}(\mu/\lambda)))) \\ &= 2O_{odiag}(\lambda) + O_{diag}(\lambda)-2I_{odiag}(\lambda)-I_{diag}(\lambda) \\ &= 1 \nonumber \end{align*} by Lemma~\ref{lem:shiftededges}. \end{proof} \subsection{Shifted Hecke insertion}\label{sec:shiftedinsertion} \begin{defi}\label{def:increasingshifted} An \emph{increasing shifted tableau} is a filling of a shifted shape with positive integers such that entries are strictly increasing across rows and down columns. \end{defi} The following are examples of increasing shifted tableaux. \[ \begin{ytableau}1 & 2 & 4 \\ \none & 4\end{ytableau}\hspace{1in}\begin{ytableau} 2 & 3 & 5 & 7 & 8 \\ \none & 5 & 8 \\ \none & \none & 9\end{ytableau} \] We now describe an insertion procedure for increasing shifted shapes that is similar to Hecke insertion, which we call \emph{shifted Hecke insertion}. This procedure is a natural analogue of that of Sagan and Worley, \cite{Sagan, W}. As before, any insertion tableau will correspond to a walk downward ending at $\varnothing$ in the dual filtered graph of shifted shapes from the M\"obius deformation and any recording tableau corresponds to a walk upward starting at $\varnothing$. The correspondence is completely analogous to that in Example~\ref{ex:Heckewalks}. In this case, whenever there are two edges connecting $\lambda$ and $\mu$, we assign one of the two edges to be the ``primed edge'' and the other to be the ``unprimed edge''. We start by describing how to insert $x$ into an increasing shifted tableau $Y$ to obtain increasing shifted tableau $Z$. We begin by inserting $x=y_1$ into the first row of $Y$. This insertion may modify the first row of $Y$ and may produce an output integer $y_2$. Following the rules below, we then insert $y_2$ into the second row of $Y$ and continue in this manner until one of two things happens. Either at some stage the insertion will not create an output integer, in which case the insertion of $x$ into $Y$ terminates, or $y_k$ will replace some diagonal element of $Y$. In the latter case, we continue the insertion process along the columns: $y_{k+1}$ is inserted into the column to the right of its original position and so on until some step in this process does not create an output integer. For each insertion, we designate a specific box of the resulting tableau, $Z$, as being the box where the insertion terminated. We will later use this notion to define recording tableaux. The rules for inserting any positive integer $x$ into a row or column are as follows: \renewcommand*{\theenumi}{S\arabic{enumi}} \begin{enumerate} \item \label{S1} If $x$ is weakly larger than all integers in the row (resp. column) and adjoining $x$ to the end of the row (resp. column) results in an increasing tableau, then $Z$ is the resulting tableau. We say that the insertion terminated at this new box. \end{enumerate} \begin{exem} Inserting $4$ into the first row of the tableau below on the left gives the tableau on the right. This insertion terminated in position $(1,3)$. \[ \begin{ytableau} 1 & 2 \\ \none & 4 \end{ytableau}\hspace{1in} \begin{ytableau} 1 & 2 & 4\\ \none & 4 \end{ytableau} \] Inserting $5$ into the third column of the resulting tableau gives the tableau shown below. This insertion terminated in position $(2,3)$. \[ \begin{ytableau} 1 & 2 & 4\\ \none & 4 & 5 \end{ytableau} \] \end{exem} \begin{enumerate}\setcounter{enumi}{1} \item \label{S2} If $x$ is weakly larger than all integers in the row (resp. column) and adjoining $x$ to the end of the row (resp. column) does not result in an increasing tableau, then $Z=Y$. If $x$ was row inserted into a nonempty row, we say that the insertion terminated at the box at the bottom of the column containing the rightmost box of this row. If $x$ was row inserted into an empty row, we say the insertion terminated at the rightmost box of the previous row. If $x$ was column inserted, we say the insertion terminated at the rightmost box of the row containing the bottom box of the column $x$ could not be added to. \end{enumerate} \begin{exem} Inserting $4$ into the first row of the tableau below does not change the row and does not give an output integer, and so the insertion does not change the tableau. The insertion terminated in position $(2,3)$. \[ \begin{ytableau} 1 & 2 & 4 \\ \none & 3 & 5 \end{ytableau} \] Inserting $4$ into the third column of the tableau below does not change the column and does not produce an output integer, and so the insertion does not change the tableau. The insertion terminated in position $(1,4)$. \[ \begin{ytableau} 1 & 2 & 4 & 5 \\ \none & 3 \end{ytableau} \] Inserting 2 into the (empty) second row of the tableau below does not change the row. The insertion terminated in position (1,2) \[ \begin{ytableau} 1 & 2 \end{ytableau} \] \end{exem} For the last two rules, suppose the row (resp. column) contains a box with label strictly larger than $x$, and let $y$ be the smallest such box. \begin{enumerate}\setcounter{enumi}{2} \item \label{S3} If replacing $y$ with $x$ results in an increasing tableau, then replace $y$ with $x$. In this case, $y$ is the output integer. If $x$ was inserted into a column or if $y$ was on the main diagonal, proceed to insert all future output integers into the next column to the right. If $x$ was inserted into a row and $y$ was not on the main diagonal, then insert $y$ into the row below. \end{enumerate} \begin{exem} Inserting $6$ into the second row of the tableau on the left results in the tableau on the right with output integer $7$ to be inserted into the third row. \[ \begin{ytableau} 1 & 2 & 3 & 4 \\ \none & 4 & 7 & 8 \\ \none & \none & 8 \end{ytableau}\hspace{1in} \begin{ytableau} 1 & 2 & 3 & 4 \\ \none & 4 & 6 & 8 \\ \none & \none & 8 \end{ytableau} \] Inserting $6$ into the third column of the tableau on the left also results in the tableau on the right with output integer $7$, but this time, $7$ is to be inserted into the fourth column. Inserting $3$ into the second row of the tableau on the left results in the tableau shown below with output integer $4$ to be inserted into the third column. \[ \begin{ytableau} 1 & 2 & 3 & 4 \\ \none & 3 & 7 & 8 \\ \none & \none & 8 \end{ytableau} \] \end{exem} \begin{enumerate}\setcounter{enumi}{3} \item \label{S4} If replacing $y$ with $x$ does not result in an increasing tableau, then do not change the row (resp. column). In this case, $y$ is the output integer. If $x$ was inserted into a column or if $y$ was on the main diagonal, proceed to insert all future output integers into the next column to the right. If $x$ was inserted into a row, then insert $y$ into the row below. \end{enumerate} \begin{exem} Inserting $2$ into the first row of the tableau below does not change the tableau and produces output integer $5$ to be inserted into the second row. \[ \begin{ytableau} 1 & 2 & 5 & 8\\ \none & 3 & 6 \end{ytableau} \] Inserting $5$ into the third column does not change the tableau and gives output integer $6$ to be inserted into the fourth column. Inserting $2$ into the second row does not change the tableau. In this case, the output integer is 3 and is to be inserted into the third column. \end{exem} Using this insertion algorithm, we define the \emph{shifted Hecke insertion tableau} of a word $w=w_1w_2\dots w_n$ to be \[ P_S(w)=(\dots((\varnothing\leftarrow w_1)\leftarrow w_2)\dots) \leftarrow w_n. \] \begin{exem} We show the sequence of shifted tableaux obtained while computing $P_S(4211232)$. We start by inserting $4$ into the first row. \[ \begin{ytableau} 4 \end{ytableau}\hspace{.1in} \begin{ytableau} 2 & 4 \end{ytableau}\hspace{.1in} \begin{ytableau} 1 & 2 & 4 \end{ytableau}\hspace{.1in} \begin{ytableau} 1 & 2 & 4 \end{ytableau}\hspace{.1in} \begin{ytableau} 1 & 2 & 4 \\ \none & 4 \end{ytableau}\hspace{.1in} \begin{ytableau} 1 & 2 & 3 \\ \none & 4 \end{ytableau}\hspace{.1in} \begin{ytableau} 1 & 2 & 3 \\ \none & 3 & 4 \end{ytableau}\hspace{.1in} \] \end{exem} \begin{rema} The result of such insertion agrees with that of $K$-theoretic jeu de taquin rectification described in~\cite{ThYshift}. See~\cite{REU2015}. \end{rema} In this setting, recording tableaux will be set-valued shifted tableaux. \begin{defi}\label{def:shiftedset} A \emph{set-valued shifted tableau} $T$ of shifted shape $\lambda$ is a filling of the boxes with finite, nonempty subsets of primed and unprimed positive integers so that \renewcommand{\theenumi}{\arabic{enumi}} \begin{enumerate} \item the smallest number in each box is greater than or equal to the largest number in the box directly to the left of it (if that box is present), \item the smallest number in each box is greater than or equal to the largest number in the box directly to the above it (if that box is present), \item any positive integer appears at most once, either primed or unprimed, but not both, and \item there are no primed entries on the main diagonal. \end{enumerate} \end{defi} A set-valued shifted tableau is called \emph{standard} if the set of labels consists of $1,2,\dots,n$, each appearing either primed or unprimed exactly once, for some $n$. A recording tableau for a word $w=w_1w_2\dots w_n$ is a standard shifted set-valued tableau and is obtained as follows. Begin with $Q_S(\varnothing)=\varnothing$. If the insertion of $w_k$ into $P_S(w_1\dots w_{k-1})$ resulted in adding a new box to $P_S(w_1\dots w_{k-1})$, add this same box with label $k$ if the box was added via row insertion and $k'$ if the box was added via column insertion to $Q_S(w_1\dots w_{k-1})$ to obtain $Q_S(w_1\dots w_k)$. If the insertion of $w_k$ into $P_S(w_1\dots w_{k-1})$ did not change the shape of $P_S(w_1\dots w_{k-1})$, obtain $Q_S(w_1\dots w_k)$ from $Q_S(w_1\dots w_{k-1})$ by adding the label $k$ to the box where the insertion terminated if the last move was a row insertion into a nonempty row and $k'$ if the last move was a column insertion. If the last move was row insertion into an empty row, label the box where the insertion terminated $k'$. \begin{exem} The top row of tableaux shows the sequence of tableaux obtained from inserting $w=4211232$ as in the previous example, and the bottom row shows the corresponding steps to form $Q_S(w)$. {%\small \begin{gather*} \ytableausetup{boxsize=.58cm} \begin{ytableau} 4 \end{ytableau}\; \begin{ytableau} 2 & 4 \end{ytableau}\; \begin{ytableau} 1 & 2 & 4 \end{ytableau}\; \begin{ytableau} 1 & 2 & 4 \end{ytableau}\; \begin{ytableau} 1 & 2 & 4 \\ \none & 4 \end{ytableau}\; \begin{ytableau} 1 & 2 & 3 \\ \none & 4 \end{ytableau}\; \begin{ytableau} 1 & 2 & 3 \\ \none & 3 & 4 \end{ytableau}\; =P_S(w) \\ \begin{ytableau} 1 \end{ytableau}\; \begin{ytableau} 1 & 2' \end{ytableau}\; \begin{ytableau} 1 & 2' & 3' \end{ytableau}\; \begin{ytableau} 1 & 2' & 3'4' \end{ytableau}\; \begin{ytableau} 1 & 2' & 3'4' \\ \none & 5 \end{ytableau}\; \begin{ytableau} 1 & 2' & 3'4' \\ \none & 56 \end{ytableau}\; \begin{ytableau} 1 & 2' & 3'4' \\ \none & 56 & 7' \end{ytableau}\, =Q_S(w) \end{gather*}} \end{exem} We next define a reverse insertion procedure so that given a pair $(P_S(w),Q_S(w))$, we can recover $w$. First locate the box containing the largest label of $Q_S(w)$, call the label $n$ and the position of the box $(i_n,j_n)$, and find the corresponding box in $P_S(w)$. Say the integer in position $(i_n,j_n)$ of $P_S(w)$ is $y_n$. We then perform reverse insertion on cell $(i_n,j_n)$ of $P_S(w)$ by following the rules below. \renewcommand{\theenumi}{rS\arabic{enumi}} \begin{enumerate} \item \label{rS1} If $n$ is the only label in cell $(i_n,j_n)$ of $Q(w)$, remove box $(i_n,j_n)$ from $P_S(w)$ and reverse insert $y_n$ into the row above if $n$ is unprimed and into the column to the left if $n$ is primed. \item \label{rS2} If $n$ is not the only label in cell $(i_n,j_n)$ of $Q_S(w)$, do not remove box $(i_n,j_n)$ from $P_S(w)$, but still reverse insert $y_n$ into the row above if $n$ is unprimed and into the column to the left if $n$ is primed. \end{enumerate} If $y_n$ is reverse inserted into row $i_n-1$, let $x$ be the largest label in row $i_n-1$ with $x0$. We will use the same two claims from the Hecke growth diagram proof, which have analogous proofs. \begin{enonce}{Claim} Oriented as in the square above, $|\nu/\lambda|\leq1$. \end{enonce} \begin{enonce}{Claim} Oriented as in the square above, $\mu/\lambda$ is a rook strip, that is, no two boxes in $\mu/\lambda$ are in the same row or column. \end{enonce} \begin{itemize} \item[(1-2)] Note that if the square contains an $X$, then $\lambda=\nu$ because there are no other $X$'s in column $t$. If $\lambda_1=\mu_1$, then there are no $s$'s in the first row of $T(s,t-1)$. Thus the inserted $s$ will be added to the end of the first row, creating $\gamma$. If $\lambda_1=\mu_1$, then there is already an $s$ at the end of the first row of $T(s,t-1)$. The inserted $s$ cannot be added to the first row, so the $\mu=\gamma$. In this case, the insertion terminated at the end of the first row. We know this is an inner corner because $s$ is the largest number inserted so far, so there can not be anything directly below the box labeled $s$ in the first row. \item[(3)] If $\mu=\lambda$, there is no $X$ to the left of square $(s,t)$ in row $s$. Thus nothing changes between $\nu$ and $\gamma$ as we consider occurrences of entry $s$. If $\lambda=\nu$, there is no $X$ below square $(s,t)$ in column $t$ and so no new insertion.Thus nothing changes between $\mu$ and $\gamma$. \item[(4)] Suppose $\nu/\lambda$ is one box in row $n$ and $\mu/\lambda$ contains boxes in rows exactly $\{j_1,j_2,\dots,j_k\}$. Suppose the box in $\nu/\lambda$ corresponds to inserting $r0$, the edge between $\gamma$ and $\mu$ has no label, and $\mu/\nu$ has no box in row $i$, then $\nu/\lambda$ is one box in row $i$. \item[(R11)] If $\gamma/\mu$ is one box in row $i+1$ for some $i>0$, the edge between $\gamma$ and $\mu$ has no label, and $\mu/\nu$ has a box in row $i$, then $\lambda=\nu$ and the edge between them is labeled $i$. \item[(R7)] If $\gamma/\mu$ is one box in column $j+1$ for some $j>0$, the edge between $\gamma$ and $\mu$ is labeled $c$, and $\mu/\nu$ has no box in column $j$, then $\nu/\lambda$ is one box in column $j$ and the edge between $\nu$ and $\lambda$ is labeled $c$. \item[(R15)] If $\gamma/\mu$ is one box in column $j+1$ for some $j>0$, the edge between $\gamma$ and $\mu$ is labeled $c$, and $\mu/\nu$ has a box in column $j$, then $\nu=\lambda$ and the edge between them is labeled $j$ and $c$. \item[(R6)] If $\gamma=\mu$, the edge between them is labeled $i+1$ for some $i>0$, $\mu/\nu$ has a box in row $i+1$, and $\mu_i\neq \mu_{i+1}+1$, then $\nu/\lambda$ is one box in row $i$. \item[(R9)] If $\gamma=\mu$, the edge between them is labeled $i+1$ for some $i>0$, $\mu/\nu$ has no box in row $i+1$, then $\lambda=\nu$ and the edge between them is labeled $i+1$. \item[(R10)] If $\gamma=\mu$, the edge between them is labeled $i+1$ for some $i>0$, $\mu/\nu$ has a box in row $i+1$, and $\mu_i=\mu_{i+1}+1$, then $\lambda=\nu$ and the edge between them is labeled $i$. \item[(R8)] If $\gamma=\mu$, the edge between them is labeled $j+1$ and $c$ for some $j>0$, $\mu/\nu$ has a box in column $j+1$, and the $j^{th}$ and $j+1^{th}$ columns of $\mu$ are not the same size, then $\nu/\lambda$ is one box in column $j$. \item[(R12)] If $\gamma=\mu$, the edge between them is labeled $j+1$ and $c$ for some $j>0$, and the bottom box of column $j+1$ is in the last row of $\mu$, then $\lambda=\nu$ and the edge between them is labeled with the bottom row of $\nu$. \item[(R13)] If $\gamma=\mu$, the edge between them is labeled $j+1$ and $c$ for some $j>0$, $\mu/\nu$ has no box in column $j+1$, then $\lambda=\nu$ and the edge between them is labeled $j+1$ and $c$. \item[(R14)] If $\gamma=\mu$, the edge between them is labeled $j+1$ and $c$ for some $j>0$, $\mu/\nu$ has a box in column $j+1$, and the $j^{th}$ and $j+1^{th}$ columns of $\mu$ are the same size, then $\lambda=\nu$ and the edge between them is labeled $j$ and $c$. \end{itemize} \end{enonce*} \section{Major examples: Young--Fibonacci lattice} \label{sec:YF} \subsection{M\"obius deformation of the Young--Fibonacci lattice} In order to describe the M\"obius deformation of the Young--Fibonacci lattice, we first need to determine its M\"obius function. \begin{theo} Let $X>Y$ be elements in the Young--Fibonacci lattice and suppose $X$ has $n$ edges below it. Then \[ \mu(Y,X)=\begin{cases} n-1 & \text{if }2Y=X \\ -1 & \text{if $X$ covers $Y$} \\ 0 & \text{otherwise} \end{cases} \] \end{theo} \begin{proof} Suppose $X>Y$. If $\rho(X)=\rho(Y)+1$, then clearly, $\mu(Y,X)=-1$. If $\rho(X)=\rho(Y)+2$ and $X=2Y$, then $\mu(Y,X)=n-1$ since $2Y$ covers exactly the elements that cover $Y$. If $X\neq 2Y$, then it can be checked that $X$ covers exactly one element that covers $Y$. Therefore $\mu(Y,X)=0$. Assume now $\rho(X)\geq\rho(Y)+2$. We will argue that $\mu(Y,X)=0$ by induction on $\rho(X)$. The base case $\rho(X)=\rho(Y)+2$ was just proved. Let us argue the step of induction. There are two cases. \begin{itemize} \item We have $2Y < X$. In this case, we argue that $\sum_{Y\leq W < X} \mu(Y,W)=0$. Indeed, $\sum_{Y\leq W\leq2Y} \mu(Y,W)=0$. If $W$ is in the interval $[Y,X]$ but not in $[Y,2Y]$, then $W$ does not cover $Y$ and $W\neq 2Y$. Thus by the inductive hypothesis $\mu(Y,W)=0$. \item We have $2Y \not < X$. We claim there is only one $Z$ that covers $Y$ such that $Z < X$. Indeed, since the Young--Fibonacci lattice is a lattice, and since the join of any two distinct such $Z$'s is $2Y$, we would have a contradiction. Then $\mu(Y,Y)+\mu(Y,Z)=1 + (-1)=0$. For the rest of $Y < W < X$ we have $\mu(Y,W)=0$ by the induction assumption.\qedhere \end{itemize} \end{proof} By the previous result, for each element $X$ in the Young--Fibonacci lattice, the M\"obius deformation is formed by adding an upward-oriented loop for each of the $n$ elements $X$ covers and adding $n-1$ downward-oriented edges from $X$ to $Y$ if $X=2Y$. For example, there are 2 edges from 221 to 21. The first few ranks are shown below. \[ \begin{tikzpicture}[scale=.9] \ytableausetup{boxsize=.15cm} \node (empty) at (0,0) {$\varnothing$}; \node (1) at (0,1) {\begin{ytableau} $ $ \end{ytableau}}; \node (11) at (1,2) {\begin{ytableau} $ $ & $ $ \end{ytableau}}; \node (2) at (-1,2) {\begin{ytableau} $ $ \\ $ $ \end{ytableau}}; \node (12) at (-2,3) {\begin{ytableau} \none & $ $ \\ $ $ & \end{ytableau}}; \node (21) at (0,3) {\begin{ytableau} $ $ & \none \\ $ $ & $ $ \end{ytableau}}; \node (111) at (2,3) {\begin{ytableau} $ $ & & \end{ytableau}}; \node (112) at (-3,4) {\begin{ytableau} \none & \none & $ $ \\ $ $ & & \end{ytableau}}; \node (22) at (-1,4) {\begin{ytableau} $ $ & \\ $ $ & \end{ytableau}}; \node (121) at (0,4) {\begin{ytableau} \none & $ $ & \none \\ $ $ & & \end{ytableau}}; \node (211) at (1,4) {\begin{ytableau} $ $ & \none & \none \\ $ $ & & \end{ytableau}}; \node (1111) at (3,4) {\begin{ytableau} $ $ & & & \end{ytableau}}; \draw (empty) -- (1) --(11)--(111)--(1111) (1)--(2)--(12)--(112) (11)--(21)--(22) (1) to [out=60, in=100, distance=.5cm] (1) (2) to [out=60, in=100, distance=.5cm] (2) (11) to [out=60, in=100, distance=.5cm] (11) (12) to [out=60, in=100, distance=.5cm] (12) (21) to [out=-60, in=-100, distance=.5cm] (21) (21) to [out=-60, in=-100, distance=.7cm] (21) (111) to [out=60, in=100, distance=.5cm] (111) (112) to [out=60, in=100, distance=.5cm] (112) (22) to [out=60, in=100, distance=.5cm] (22) (22) to [out=60, in=100, distance=.7cm] (22) (121) to [out=60, in=100, distance=.5cm] (121) (211) to [out=60, in=100, distance=.5cm] (211) (211) to [out=60, in=100, distance=.7cm] (211) (1111) to [out=60, in=100, distance=.5cm] (1111) (2)--(21)--(211) (111)--(211) (21)--(121) (12)--(22); \end{tikzpicture}\hspace{.05in} \begin{tikzpicture}[scale=.9] \ytableausetup{boxsize=.15cm} \node (empty) at (0,0) {$\varnothing$}; \node (1) at (0,1) {\begin{ytableau} $ $ \end{ytableau}}; \node (11) at (1,2) {\begin{ytableau} $ $ & $ $ \end{ytableau}}; \node (2) at (-1,2) {\begin{ytableau} $ $ \\ $ $ \end{ytableau}}; \node (12) at (-2,3) {\begin{ytableau} \none & $ $ \\ $ $ & \end{ytableau}}; \node (21) at (0,3) {\begin{ytableau} $ $ & \none \\ $ $ & $ $ \end{ytableau}}; \node (111) at (2,3) {\begin{ytableau} $ $ & & \end{ytableau}}; \node (112) at (-3,4) {\begin{ytableau} \none & \none & $ $ \\ $ $ & & \end{ytableau}}; \node (22) at (-1,4) {\begin{ytableau} $ $ & \\ $ $ & \end{ytableau}}; \node (121) at (0,4) {\begin{ytableau} \none & $ $ & \none \\ $ $ & & \end{ytableau}}; \node (211) at (1,4) {\begin{ytableau} $ $ & \none & \none \\ $ $ & & \end{ytableau}}; \node (1111) at (3,4) {\begin{ytableau} $ $ & & & \end{ytableau}}; \draw (empty) -- (1) --(11)--(111)--(1111) (1)--(2)--(12)--(112) (11)--(21)--(22) (2)--(21)--(211) (111)--(211) (21)--(121) (12)--(22) (21)--(1) (22)--(2) (211)--(11); \end{tikzpicture} \] \ytableausetup{boxsize=.5cm} \begin{theo} The M\"obius deformation of the Young--Fibonacci lattice forms a dual filtered graph with \[ DU-UD=D+I. \] \end{theo} \begin{proof} Suppose that shape $X$ covers shape $Y$, and first assume that $\rho(Y)=\rho(X)-1$. The up-down paths from $X$ to $Y$ that consist of a loop at $X$ followed by following the edge from $X$ to $Y$ can be counted by the number of loops at $X$, i.e. the number of edges below $X$ in the Young--Fibonacci lattice. In the second type of up-down path, we start at $X$, move up to a distinct shape $W$, and then move down to $Y$. The only $W$ with $\rho(W)=\rho(Y)+2$ that cover $Y$ is the $W$ defined by $W=2Y$. This $W$ covers $X$ by definition of the Young--Fibonacci lattice. To count the number of paths through $W$, we need to count the number of edges from $W$ to $Y$. This number is the same as one fewer than the number edges below $W$ in $\mathbb{YF}$, which is the same as one fewer than the number of edges above $Y$ in $\mathbb{YF}$. To count down-up paths, we first count the paths that consist of the edge from $X$ to $Y$ followed by a loop at $Y$. These can be counted by the number of loops at $Y$ or, in other words, the one fewer than the number of edges above $Y$ in $\mathbb{YF}$. The second type of down-up paths involve traveling from $X$ down to some $Z$ with $\rho(Z)+2=\rho(X)$ and then going up to $Y$. There is a unique such $Z$ defined by $2Z=X$, and $Y$ covers this $Z$. We thus need to count the number of ways to get from $X$ to $Z$, which is the same as one fewer than the number of edges below $X$ in $\mathbb{YF}$. Putting the previous two arguments together, $[Y](DU-UD)(X)=1$ in this case, as desired. Now suppose $\rho(Y)=\rho(X)-2$. The only up-down paths from $X$ to $Y$ consist of a loop at $X$ followed by an edge from $X$ to $Y$. There are \[ (\#\{\text{edges below $X$ in $\mathbb{YF}$}\})(\#\{\text{edges below $X$ in $\mathbb{YF}$}\}-1) \] such paths. To count down-up paths, we must count the number of ways to choose an edge from $X$ to $Y$ and then choose a loop of $Y$. There are \[ (\#\{\text{edges below $X$ in $\mathbb{YF}$}\}-1)(\#\{\text{edges above $Y$ in $\mathbb{YF}$}\}-1) \] such paths. Since \[ \#\{\text{edges down from $X$ in $\mathbb{YF}$}\}=\#\{\text{edges above $Y$ in $\mathbb{YF}$}\}, \] we have that \[ [Y](DU-UD)(X)=\#\{\text{edges below $X$ in $\mathbb{YF}$}\}-1=[Y]D(X).\qedhere \] \end{proof} \subsection{K-Young--Fibonacci insertion} \label{sec:KYFinsertion} As with the previous examples of M\"obius construction, we describe an insertion procedure that corresponds to the M\"obius deformation of the Young--Fibonacci lattice, which is an analogue of the Young--Fibonacci insertion of Fomin. We recommend~\cite{F} for details about Young--Fibonacci insertion. In this analogue, any walk upward from $\varnothing$ will correspond to a recording tableau and any walk downward to $\varnothing$ will correspond to an insertion tableau. (See Example~\ref{ex:KYFwalk}.) We begin by describing the insertion tableaux in this setting. \begin{defi}\label{def:KYFtableau} A \emph{$K$-Young--Fibonacci (KYF) tableau} is a filling of a snakeshape with positive integers such that \renewcommand{\theenumi}{\roman{enumi}} \begin{enumerate} \item \label{i} for any pair \begin{ytableau} B \\ A \end{ytableau} the inequality $A\leq B$ holds; \item \label{ii} to the right of any \begin{ytableau} B \\ A \end{ytableau}, there are no numbers from the interval $[A,B]$ in either the upper or lower rows; \item \label{iii} if the position above \begin{ytableau} A \end{ytableau} is not occupied yet, then to the right of \begin{ytableau} A \end{ytableau} there are no numbers greater than or equal to $A$ in either the lower or upper rows; \item \label{iv} any pair \begin{ytableau} A \\ A \end{ytableau} must come before any single box \begin{ytableau} B \end{ytableau} and must not be in rightmost column of the snakeshape. In addition, $A$ may not be the smallest entry in the snakeshape. \end{enumerate} \end{defi} \begin{exem} The three snakeshapes below are valid KYF tableaux. \[ \begin{ytableau} \none & 3 & 4 & \none & 7 \\ 9 & 2 & 1 & 8 & 6 & 5 \end{ytableau}\hspace{.5in} \begin{ytableau} 2 & 3 & \none & \none & 5 \\ 2 & 1 & 7 & 6 & 4 \end{ytableau}\hspace{.5in} \begin{ytableau} 4 & 5 & \none & \none & 2 \\ 4 & 5 & 6 & 3 & 1 \end{ytableau} \] The snakeshapes below are not valid KYF tableaux. The first violates condition~\eqref{iii}, the second violates condition~\eqref{ii}, and the third, fourth, and fifth violate condition~\eqref{iv}. \[ \begin{ytableau} \none & 3 & 4 \\ 4 & 2 & 1 \end{ytableau}\hspace{.4in} \begin{ytableau} 3 & 4 & \none \\ 2 & 1 & 4 \end{ytableau}\hspace{.4in} \begin{ytableau} 4 & 6 & \none & \none & 2 \\ 4 & 5 & 7 & 3 & 2 \end{ytableau}\hspace{.4in} \begin{ytableau} 3 & 2 \\ 1 & 2 \end{ytableau}\hspace{.4in} \begin{ytableau} 1 & 3 \\ 1 & 2 \end{ytableau} \] \end{exem} Let $\tau$ be a valid KYF tableau. We show how to insert positive integer $x$ into $\tau$ to obtain a new valid KYF tableau that may or may not be different than $\tau$. Notice that this insertion procedure is different than Hecke insertion and shifted Hecke insertion in that the algorithm does not proceed row-by-row or column-by-column. As before, we designate a specific box of the resulting tableau, $\tau'$, as being the box where the insertion terminated. We will later use this notion to define recording tableaux. The rules for inserting any positive integer $x$ into $\tau$ are as follows: \renewcommand{\theenumi}{YF\arabic{enumi}} \begin{enumerate} \item \label{YF1} If $x$ is equal to the smallest entry in $\tau$, then $\tau=\tau'$. In this case, we say the insertion terminated in the top cell of the first column of $\tau=\tau'$. If this is not the case, continue to step 2. \begin{exem} Inserting $1$ into the tableau on the left or $2$ into the tableau on the right will not change the tableaux. \[ \begin{ytableau} \none & 2 & \none \\ 4 & 1 & 3 \end{ytableau}\hspace{1in} \begin{ytableau} 3 & \none & \none \\ 2 & 5 & 4 \end{ytableau} \] \end{exem} \item \label{YF2} Attach a new box \begin{ytableau} x \end{ytableau} just to the left of $\tau$ in the lower row. \item \label{YF3} Find all the entries of $\tau$ that are greater than or equal to $x$ and sort them: \[ x\leq a_1\leq a_2\leq\dots\leq a_k. \] If in $\tau$ we have \begin{ytableau} A \\ A \end{ytableau}, then we consider the $A$ in the upper row to be the larger of the two. \item \label{YF4} If $a_i=a_{i+1}$, then replace $a_{i+1}$ with $*$. \item \label{YF5} Now put a box \begin{ytableau} \bullet \end{ytableau} just above \begin{ytableau} x \end{ytableau} and move the $a_i$ chainwise according to the following rule: $a_1$ moves into the new box, $a_2$ moves to $a_1$'s original position, $a_3$ moves to $a_2$'s original position, etc. The box that was occupied by $a_k$ disappears. If it was located in the lower row, then the left and right parts of the snake are concatenated. \item \label{YF6} If there is a box with $*$ and no box directly above it, delete this box and concatenate the left and right parts of the snake. If this happens, we say the insertion terminated at the box in the upper row of the column directly to the right of this concatenation. Otherwise, a box was added in the insertion process, and we say the insertion terminated at this new box. \item \label{YF7} Replace any pair \begin{ytableau} A \\ $*$ \end{ytableau} with \begin{ytableau} A \\ A \end{ytableau}. \end{enumerate} \begin{exem} Let's insert 3 into $\tau=$\begin{ytableau} 3 & 4 & \none \\ 2 & 4 & 1 \end{ytableau}. We first attach \begin{ytableau} 3 \end{ytableau} as shown below. \[ \begin{ytableau} \none & 3 & 4 & \none \\ 3 & 2 & 4 & 1 \end{ytableau} \] Next, we locate and order \[ 3\leq(a_1=3)\leq(a_2=4)\leq(a_3=4), \] and we replace $a_3$ with $*$. After shifting the boxes as in~\eqref{YF5}, we have \[ \begin{ytableau} 3 & 4 & \none & \none \\ 3 & 2 & $*$ & 1 \end{ytableau} \] We then delete the box with $*$ to obtain the final KYF tableau below. \[ \begin{ytableau} 3 & 4 & \none \\ 3 & 2 & 1 \end{ytableau} \] This insertion terminates at the box at the top of the third column. Notice also that inserting 1 into $\tau$ does not change the tableau, and this insertion terminates at the box at the top of the first column. \end{exem} \begin{exem} We insert 2 into KYF tableau \begin{ytableau} \none & \none & 2 & \none \\ 4 & 3 & 2 & 1 \end{ytableau}. We first attach a box containing 2 to the left of the original tableau. We then locate and order \[ 2\leq(a_1=2)\leq(a_2=2)\leq(a_3=3)\leq(a_4=4). \] We replace $a_2$ with $*$ and shift the boxes to obtain \[ \begin{ytableau} 2 & \none & 3 & \none \\ 2 & 4 & $*$ & 1 \end{ytableau} \] After performing the last step of the insertion procedure, we end with the tableau shown below. \[ \begin{ytableau} 2 & \none & 3 & \none \\ 2 & 4 & 3 & 1 \end{ytableau} \] This insertion terminated at the box at the top of the first column of the resulting tableau. \end{exem} As usual, for a word $w=w_1w_2\dots w_n$, we define $P_{YF}(w)$ by setting \[ P_{YF}(w_1\dots w_k)=P_{YF}(w_1\dots w_{k-1}) \leftarrow w_k. \] \begin{exem}\label{ex:1334241} The sequence of KYF tableaux below shows the intermediate tableaux obtained in computing $P_{YF}(1334241)$, which is shown on the right. \[ \begin{ytableau} \none \\ 1 \end{ytableau}\hspace{.2in}\begin{ytableau} \none & \none \\ 3 & 1 \end{ytableau}\hspace{.2in}\begin{ytableau} 3 & \none \\ 3 & 1 \end{ytableau}\hspace{.2in} \begin{ytableau} \none & 3 & \none \\ 4 & 3 & 1 \end{ytableau}\hspace{.2in} \begin{ytableau} 3 & 4 & \none \\ 2 & 4 & 1 \end{ytableau}\hspace{.2in} \begin{ytableau} 4 & 3 & \none \\ 4 & 2 & 1 \end{ytableau}\hspace{.2in} \begin{ytableau} 4 & 3 & \none \\ 4 & 2 & 1 \end{ytableau}\hspace{.2in} \] \end{exem} We need the next definition to define the recording tableaux for KYF insertion. \pagebreak \begin{defi}\label{def:KYFsetvalued} A \emph{standard set-valued KYF tableau} is a snakeshape whose boxes are filled with finite, nonempty subsets of positive integers that satisfy the following conditions, where $\bar{A},\bar{B},\bar{C}$ are subsets, $\bar{A}< \bar{B}$ when $\max(\bar{A})<\min(\bar{B})$, and the letters $[n]$ are used exactly once for some $n$: \renewcommand{\theenumi}{\roman{enumi}} \begin{enumerate} \item for any pair \begin{ytableau} \scriptstyle{\bar{B}} \\ \scriptstyle{\bar{A}} \end{ytableau} the inequality $\bar{A}< \bar{B}$ holds; \item to the right of any \begin{ytableau} \scriptstyle{\bar{B}} \\ \scriptstyle{\bar{A}} \end{ytableau}, there are no numbers from the interval $[\max(\bar{A}),\linebreak\min(\bar{B})]$ in either the upper or lower rows; \item if the position above \begin{ytableau} \scriptstyle{\bar{A}} \end{ytableau} is not occupied yet, then to the right of \begin{ytableau} \scriptstyle{\bar{A}} \end{ytableau} there are no entries greater than min($\bar{A}$) in either the lower or upper rows; \end{enumerate} \end{defi} A recording tableau for a word $w=w_1w_2\dots w_n$ is a standard set-valued KYF tableau and is obtained as follows. Begin with $Q_{YF}(\varnothing)=\varnothing$. If the insertion of $w_k$ into $P_{YF}(w_1\dots w_{k-1})$ resulted in adding a new box to $P_{YF}(w_1\dots w_{k-1})$, add this same box with label $k$ to $Q_{YF}(w_1\dots w_{k-1})$ to obtain $Q_{YF}(w_1\dots w_k)$. If the insertion of $w_k$ into $P_{YF}(w_1\dots w_{k-1})$ did not change the shape of $P_{YF}(w_1\dots w_{k-1})$, obtain $Q_{YF}(w_1\dots w_k)$ from $Q_{YF}(w_1\dots w_{k-1})$ by adding the label $k$ to the box where the insertion terminated. \begin{exem}\label{ex:KYFwalk} In Example~\ref{ex:1334241}, we computed $P_{YF}(1334241)$. We repeat this computation on the top row and show the corresponding steps of building $Q_{YF}(1334241)$ on the bottom row. \begin{gather*} \begin{ytableau} \none \\ 1 \end{ytableau}\hspace{.2in} \begin{ytableau} \none & \none \\ 3 & 1 \end{ytableau}\hspace{.2in} \begin{ytableau} 3 & \none \\ 3 & 1 \end{ytableau}\hspace{.2in} \begin{ytableau} \none & 3 & \none \\ 4 & 3 & 1 \end{ytableau}\hspace{.2in} \begin{ytableau} 3 & 4 & \none \\ 2 & 4 & 1 \end{ytableau}\hspace{.2in} \begin{ytableau} 4 & 3 & \none \\ 4 & 2 & 1 \end{ytableau}\hspace{.2in} \begin{ytableau} 4 & 3 & \none \\ 4 & 2 & 1 \end{ytableau} \\[0.5em] \begin{ytableau} \none \\ 1 \end{ytableau}\hspace{.2in} \begin{ytableau} \none & \none \\ 2 & 1 \end{ytableau}\hspace{.2in} \begin{ytableau} 3 & \none \\ 2 & 1 \end{ytableau}\hspace{.2in} \begin{ytableau} \none & 3 & \none \\ 4 & 2 & 1 \end{ytableau}\hspace{.2in} \begin{ytableau} 5 & 3 & \none \\ 4 & 2 & 1 \end{ytableau}\hspace{.2in} \begin{ytableau} 5 & 3 & \none \\ 4 & 2 & 16 \end{ytableau}\hspace{.2in} \begin{ytableau} 57 & 3 & \none \\ 4 & 2 & 16 \end{ytableau} \end{gather*} The top row below shows the walk in $G_1$ corresponding to the recording tableau. Here, we must pair the loops on each shape to its inner corners. In the walk shown, the last two steps use distinct loops at the shape 221. The second row below shows the walk in $G_2$ corresponding to the insertion tableau. \ytableausetup{boxsize=.15in} \begin{gather*} \left\{\varnothing,\ydiagram{0,1},\ydiagram{0,2},\ydiagram{1,2},\ydiagram{1+1,3}, \ydiagram{2,3}, \ydiagram{2,3},\ydiagram{2,3}\right\} \\ \left\{\ydiagram{2,3},\ydiagram{1,2},\ydiagram{0,2},\ydiagram{0,1},\varnothing\right\} \end{gather*} \end{exem} \ytableausetup{boxsize=.2in} We next define a reverse insertion procedure so that given a pair $(P_{Y\mk F}(w),Q_{Y\mk F}(w))$, we can recover $w=w_1\dots w_n$. First locate the box containing the largest label of $Q_{YF}(w)$, call the label $n$ and its column $c$, and find the corresponding box in $P_{YF}(w)$. Let $x$ denote the label in the leftmost box of the bottom row of $P_{YF}(w)$. \renewcommand{\theenumi}{rYF\arabic{enumi}} \begin{enumerate} \item \label{rYF1} If the label $n$ of $Q$ was not the only label in its box and was located in the upper row of the first column, then $P_{YF}(w)=P_{YF}(w_1\dots w_{n-1}) \leftarrow s$, where $s$ is the smallest entry in $P_{YF}(w_1\dots w_{n-1})$. Finally, $Q_{YF}(w_1\dots w_{n-1})$ is obtained from $Q_{YF}(w)$ by removing the label $n$. \end{enumerate} In all remaining cases, $P_{YF}(w)=P_{YF}(w_1\dots w_{n-1}) \leftarrow x$, and we describe how to construct $P_{YF}(w_1\dots w_{n-1})$. In each case, $Q_{YF}(w_1\dots w_{n-1})$ is obtained from $Q_{YF}(w)$ by removing the label $n$. If $n$ is the only label in its box, the box is removed. \begin{enumerate}\setcounter{enumi}{1} \item \label{rYF2} If the label $n$ of $Q$ was the only label in its box: \begin{enumerate} \item Delete the leftmost square in the bottom row. \item Let $k$ denote the largest entry in $P_{YF}(w)$, and sort the entries of $P_{YF}(w)$ as shown below: \[ x\leq b_1\leq b_2\leq\dots\leq b_t=k. \] If we have \begin{ytableau} A \\ A \end{ytableau}, then we consider the $A$ in the upper row to be the larger of the two. \item If $b_i=b_{i+1}$, replace $b_{i}$ with $*$. \item Move the $b_i$ chainwise according the following rule: $b_1$ moves into $b_2$'s position, $b_2$ moves into $b_3$'s position, etc until $b_{t-1}$ moves into $b_t$'s position. The box that was occupied by $b_1$ disappears. \item Place $b_t$ in the position determined by the shape of $Q_{S,n-1}$. \item Replace any pair \begin{ytableau} $*$ \\ A \end{ytableau} with \begin{ytableau} A \\ A \end{ytableau}. \end{enumerate} \item \label{rYF3} If the label $n$ of $Q$ was not the only label in its box and the largest entry in $P_{YF}(w)$ is $k$: \begin{enumerate} \item Add the column \begin{ytableau} \bullet \\ k \end{ytableau} directly to the left of column $c$ to $P_{YF}(w)$. \item Sort the entries of $P_{YF}(w)$ as shown below: \[ k=b_1\geq b_2\geq b_2 \dots\geq x=b_t. \] If we have \begin{ytableau} A \\ A \end{ytableau}, then we consider the $A$ in the upper row to be the larger of the two. \item If $b_i=b_{i+1}$, replace $b_{i+1}$ with $*$. \item Move the $b_i$ chainwise according to the following rule: $b_1$ moves into the new box \begin{ytableau} \bullet \end{ytableau}, $b_2$ moves to $b_1$'s original position, $b_3$ moves to $b_2$'s original position, etc. The box that was occupied by $b_t=x$ disappears. \item Replace any pair \begin{ytableau} $*$ \\ A \end{ytableau} with \begin{ytableau} A \\ A \end{ytableau}. \end{enumerate} \end{enumerate} The steps above clearly reverse the KYF insertion steps, giving us the result below. \begin{theo} KYF insertion and reverse KYF insertion define mutually inverse bijections between the set of words on $\mathbb{N}$ and the set of pairs $(P_{YF},Q_{YF})$ consisting of a KYF tableau and a set-valued KYF tableau of the same shape. \end{theo} \begin{proof} Omitted for brevity. \end{proof} \subsection{KYF growth and decay}\label{sec:KYFgrowth} As before, given any word $w=w_1w_2\dots w_k$, containing $n\leq k$ distinct numbers, we can create an $n \times k$ array with an $X$ in the $w_i^{th}$ square from the bottom of column $i$. Note that there can be multiple $X$'s in the same row but is at most one $X$ per column. We will label the corners of each square with a snakeshape, label some of the horizontal edges of the squares with a specific inner corner by writing the column of the inner corner, and label some vertical edges corresponding to where a 2 was added to the bottom shape to obtain the top shape. For example, if the corner at the bottom of the vertical edge is labeled with 221, the corner at the top is labeled 2221, and the vertical edge has label 3, this means that the third column of 2's in 2221 is the column that was added when going from 221 to 2221. We begin by labeling all corners in the bottom row and left side of the diagram with the empty shape, $\varnothing$. To complete the labeling of the corners, suppose the corners $\mu$, $\lambda$, and $\nu$ are labeled, where $\mu$, $\lambda$, and $\nu$ are as in the picture below. We label $\gamma$ according to the following rules. \[ \begin{tikzpicture}[scale=1] \node (A) at (-1,-1) {$\lambda$}; \node (B) at (1,-1) {$\nu$}; \node (C) at (-1,1) {$\mu$}; \node (D) at (1,1) {$\gamma$}; \draw (A) -- (B) (C) -- (D) (B) -- (D) (A) -- (C); \end{tikzpicture} \] \begin{itemize} \item \emph{If the square contains an X:} \begin{itemize} \item[(1)] If $\lambda=\nu=\varnothing$, then $\gamma=\mu=1$ and the top edge is labeled 1. \item[(2)] If $\lambda=\mu=\nu$, then $\gamma=1\lambda$. \item[(3)] If $\mu=2\lambda$ and the left edge is labeled $i$, then $\gamma=2\lambda$, the top edge is labeled $i+1$, and the right edge is labeled~1. \item[(4)] If $\mu\neq\lambda$, $\mu\neq 2\lambda$, and $\mu\neq1$, then $\gamma=2\lambda$ and the right edge is labeled~1. \end{itemize} \begin{center} \begin{tikzpicture}[scale=.9] \node (A) at (-1,-1) {$\varnothing$}; \node (B) at (1,-1) {$\varnothing$}; \node (C) at (-1,1) {1}; \node (D) at (1,1) {1}; \node (E) at (0,0) {$X$}; \node (F) at (0,1.25){1}; \draw (A) -- (B) (C) -- (D) (B) -- (D) (A) -- (C); \end{tikzpicture}\hspace{.15in} \begin{tikzpicture}[scale=.9] \node (A) at (-1,-1) {$\lambda$}; \node (B) at (1,-1) {$\lambda$}; \node (C) at (-1,1) {$\lambda$}; \node (D) at (1,1) {1$\lambda$}; \node (E) at (0,0) {$X$}; \draw (A) -- (B) (C) -- (D) (B) -- (D) (A) -- (C); \end{tikzpicture}\hspace{.15in} \begin{tikzpicture}[scale=.9] \node (A) at (-1,-1) {$\lambda$}; \node (B) at (1,-1) {$\lambda$}; \node (C) at (-1,1) {$2\lambda$}; \node (D) at (1,1) {2$\lambda$}; \node (E) at (0,0) {$X$}; \node (F) at (0,1.25) {$i+1$}; \node (E) at (-1.25,0) {$i$}; \node (G) at (1.25,0) {$1$}; \draw (A) -- (B) (C) -- (D) (B) -- (D) (A) -- (C); \end{tikzpicture}\hspace{.15in} \begin{tikzpicture}[scale=.9] \node (A) at (-1,-1) {$\lambda$}; \node (B) at (1,-1) {$\lambda$}; \node (C) at (-1,1) {$\mu$}; \node (D) at (1,1) {2$\lambda$}; \node (E) at (0,0) {$X$}; \node (G) at (1.25,0) {$1$}; \draw (A) -- (B) (C) -- (D) (B) -- (D) (A) -- (C); \end{tikzpicture} \end{center} \item \emph{If the square does not contain an X and $\mu=\lambda$ or if the square does not contain an X and $\nu=\lambda$ with no edge label between $\lambda$ and $\nu$:} \begin{itemize} \item[(5)] If $\mu=\lambda$, then set $\gamma=\nu$ and label the top edge with the same label as the bottom edge if one exists. If $\nu=\lambda$, then $\gamma=\mu$ with the right edge labeled with the same label as the left edge if such a label exists. \end{itemize} \begin{center} \begin{tikzpicture}[scale=1] \node (A) at (-1,-1) {$\lambda$}; \node (B) at (1,-1) {$\nu$}; \node (C) at (-1,1) {$\lambda$}; \node (D) at (1,1) {$\nu$}; \node (E) at (0,1.25) {i}; \node (F) at (0,-.75){i}; \draw (A) -- (B) (C) -- (D) (B) -- (D) (A) -- (C); \end{tikzpicture}\hspace{1in} \begin{tikzpicture}[scale=1] \node (A) at (-1,-1) {$\lambda$}; \node (B) at (1,-1) {$\lambda$}; \node (C) at (-1,1) {$\mu$}; \node (D) at (1,1) {$\mu$}; \node (E) at (-1.25,0) {$i$}; \node (G) at (1.25,0) {$i$}; \draw (A) -- (B) (C) -- (D) (B) -- (D) (A) -- (C); \end{tikzpicture} \end{center} \item \emph{If the square does not contain an X, $\nu=\lambda$, and the bottom edge is labeled 1:} \begin{itemize} \item[(6)] If $\nu=\lambda$ and the bottom edge is labeled 1, then $\gamma=\mu$, the top edge is labeled 1, and the label on the left edge (if one exists) is the same as the label on the right edge. \end{itemize} \begin{center} \begin{tikzpicture}[scale=1] \node (A) at (-1,-1) {$\lambda$}; \node (B) at (1,-1) {$\lambda$}; \node (C) at (-1,1) {$\mu$}; \node (D) at (1,1) {$\mu$}; \node (E) at (0,-.75) {$1$}; \node (G) at (0,1.25) {$1$}; \node (H) at (-1.25,0) {$j$}; \node (I) at (1.25,0) {$j$}; \draw (A) -- (B) (C) -- (D) (B) -- (D) (A) -- (C); \end{tikzpicture} \end{center} \goodbreak \item \emph{If no previous cases apply, then set $\gamma=2\lambda$ and follow the rule below:} \begin{itemize} \item[(7)] If the bottom edge is labled $i$, then label the right edge $i$. If the left edge is labled $j$, then label the top edge $j+1$. \end{itemize} \begin{center} \begin{tikzpicture}[scale=1] \node (A) at (-1,-1) {$\lambda$}; \node (B) at (1,-1) {$\nu$}; \node (C) at (-1,1) {$\mu$}; \node (D) at (1,1) {$2\lambda$}; \node (E) at (0,-.75) {$i$}; \node (G) at (1.25,0) {$i$}; \draw (A) -- (B) (C) -- (D) (B) -- (D) (A) -- (C); \end{tikzpicture}\hspace{.5in} \begin{tikzpicture}[scale=1] \node (A) at (-1,-1) {$\lambda$}; \node (B) at (1,-1) {$\nu$}; \node (C) at (-1,1) {$\mu$}; \node (D) at (1,1) {$2\lambda$}; \node (E) at (-1.25,0) {$j$}; \node (G) at (0,1.25) {$j+1$}; \draw (A) -- (B) (C) -- (D) (B) -- (D) (A) -- (C); \end{tikzpicture}\hspace{.5in} \begin{tikzpicture}[scale=1] \node (A) at (-1,-1) {$\lambda$}; \node (B) at (1,-1) {$\nu$}; \node (C) at (-1,1) {$\mu$}; \node (D) at (1,1) {$2\lambda$}; \node (F) at (0,-.75) {$i$}; \node (H) at (1.25,0) {$i$}; \node (E) at (-1.25,0) {$j$}; \node (G) at (0,1.25) {$j+1$}; \draw (A) -- (B) (C) -- (D) (B) -- (D) (A) -- (C); \end{tikzpicture} \end{center} \end{itemize} We call the resulting array the KYF growth diagram of $w$. For example, continuing with the word from Example~\ref{ex:1334241}, $w=1334241$, we would have the diagram below. \begin{exem} Below is the KYF growth diagram for the word 1334241. \begin{center} \begin{tikzpicture}[scale=1] \node (00) at (0,0) {$\varnothing$}; \node (10) at (1,0) {$\varnothing$}; \node (20) at (2,0) {$\varnothing$}; \node (30) at (3,0) {$\varnothing$}; \node (40) at (4,0) {$\varnothing$}; \node (50) at (5,0) {$\varnothing$}; \node (01) at (0,1) {$\varnothing$}; \node (.5.5) at (.5,.5) {$X$}; \node (11) at (1,1) {$1$}; \node (21) at (2,1) {$1$}; \node (31) at (3,1) {$1$}; \node (41) at (4,1) {$1$}; \node (51) at (5,1) {$1$}; \node (02) at (0,2) {$\varnothing$}; \node (12) at (1,2) {$1$}; \node (22) at (2,2) {$1$}; \node (32) at (3,2) {$1$}; \node (1.52.5) at (1.5,2.5) {$X$}; \node (42) at (4,2) {$1$}; \node (52) at (5,2) {$11$}; \node (03) at (0,3) {$\varnothing$}; \node (13) at (1,3) {$1$}; \node (23) at (2,3) {$11$}; \node (33) at (3,3) {$21$}; \node (43) at (4,3) {$21$}; \node (53) at (5,3) {$21$}; \node (2.52.5) at (2.5,2.5) {$X$}; \node (04) at (0,4) {$\varnothing$}; \node (14) at (1,4) {$1$}; \node (24) at (2,4) {$11$}; \node (34) at (3,4) {$21$}; \node (44) at (4,4) {$121$}; \node (54) at (5,4) {$221$}; \node (3.53.5) at (3.5,3.5) {$X$}; \node (4.51.5) at (4.5,1.5) {$X$}; \node (5,53.5) at (5.5,3.5) {$X$}; \node (60) at (6,0) {$\varnothing$}; \node (61) at (6,1) {$1$}; \node (62) at (6,2) {$11$}; \node (63) at (6,3) {$21$}; \node (64) at (6,4) {$221$}; \node (70) at (7,0) {$\varnothing$}; \node (71) at (7,1) {$1$}; \node (72) at (7,2) {$11$}; \node (73) at (7,3) {$21$}; \node (74) at (7,4) {$221$}; \node (6.5.5) at (6.5,.5) {$X$}; \node (6.51.15) at (6.5,1.15) {\tiny 1}; \node (6.52.15) at (6.5,2.15) {\tiny 1}; \node (6.53.15) at (6.5,3.15) {\tiny 1}; \node (6.54.15) at (6.5,4.15) {\tiny 1}; \node (6.93.5) at (6.9,3.5) {\tiny 1}; \node (2.92.5) at (2.9,2.5) {\tiny 1}; \node (3.92.5) at (3.9,2.5) {\tiny 1}; \node (5.93.5) at (5.9,3.5) {\tiny 1}; \node (4.93.5) at (4.9,3.5) {\tiny 2}; \node (4.53.1) at (4.5,3.15) {\tiny 2}; \node (5.54.1) at (5.5,4.15) {\tiny 3}; \draw (00)--(10)--(20)--(30)--(40)--(50)--(60)--(70) (01)--(11)--(21)--(31)--(41)--(51)--(61)--(71) (02)--(12)--(22)--(32)--(42)--(52)--(62)--(72) (03)--(13)--(23)--(33)--(43)--(53)--(63)--(73) (04)--(14)--(24)--(34)--(44)--(54)--(64)--(74) (00)--(01)--(02)--(03)--(04) (10)--(11)--(12)--(13)--(14) (20)--(21)--(22)--(23)--(24) (30)--(31)--(32)--(33)--(34) (40)--(41)--(42)--(43)--(44) (50)--(51)--(52)--(53)--(54) (60)--(61)--(62)--(63)--(64) (70)--(71)--(72)--(73)--(74); \end{tikzpicture} \end{center} \end{exem} Let $\mu_0=\varnothing \subseteq \mu_1 \subseteq \dots \mu_k$ be the sequence of snakeshapes across the top of the growth diagram, and let $\nu_0=\varnothing \subseteq \nu_1 \subseteq \dots \nu_n$ be the sequence of snakeshapes on the right side of the KYF growth diagram. These sequences correspond to KYF tableaux $Q(w)$ and $P(w)$, respectively. If the edge between $\nu_i$ and $\nu_{i+1}$ is labeled $j$, then $2\nu_i=\nu_{i+1}$, and a column of $i$'s is added in the $j^{th}$ column of $\nu_i$ to obtain $\nu_{i+1}$. If the edge between $\mu_i$ and $\mu_{i+1}$ is labeled $j$, then $\mu_i=\mu_{i+1}$ and the label $i+1$ of $Q(w_1\dots w_{i+1})$ is placed in the box at the top of the $j^{th}$ column of $Q(w_1\dots w_i)$. In the example above, we have \[ P= \begin{ytableau} 4 & 3 & \none \\ 4 & 2 & 1 \end{ytableau}\hspace{1in} Q= \begin{ytableau} 57 & 3 & \none \\ 4 & 2 & 16 \end{ytableau} \] which agrees with the insertion and recording tableau from Example~\ref{ex:1334241}. As for Hecke insertion and shifted Hecke insertion, this is not a coincidence. \begin{theo} For any word $w$, the KYF tableau and set-valued KYF tableau $P$ and $Q$ obtained from the sequence of snakeshapes across the right side of the KYF growth diagram for $w$ and across the top of the KYF growth diagram for $w$, respectively, are $P_{YF}(w)$ and $Q_{YF}(w)$, the KYF insertion and recording tableau for $w$. \end{theo} \begin{proof} Recall the definitions of $T(i,j)$ and $R(i,j)$ from the proof of Theorem~\ref{thm:Heckegrowth}. We define them analogously in this context and prove the analogous result by induction on $i+j$. The desired statement is clearly true when $i=0$ or $j=0$. Suppose we are considering some $T(t,s)$ with $s,t>0$. Assume also the $X$ in column $s$ is in row $r$. We may or may not have $r=t$. As in the previous growth diagram proofs, we have the following claims. \begin{enonce}{Claim} Oriented as in the square above, $|\nu/\lambda|\leq1$. \end{enonce} \begin{enonce}{Claim} Oriented as in the square above, to obtain $\mu$ from $\lambda$, we add either one box or a column of 2 boxes. \end{enonce} Rule 1 follows from the fact that inserting $t$ into the tableau \begin{ytableau} t \end{ytableau} does not change the tableau. Rules 2 applies when inserting positive integer $t$ that is strictly larger than all other entries of the KYF tableau. Thus a box with $t$ will be added directly to the left of the tableau. In Rule 3, we are adding integer $t$ to a tableau that already has 2 boxes labeled $t$ in the $i^{th}$ column, and $t$ is the largest integer in the tableau. Following the insertion rules, we end with a column of $t$'s in the first column, hence the right edge is labeled 1. The special corner of this insertion is in the $(i+1)^{th}$ column, the column where the $t$ on the top row of the original KYF tableau was deleted in the insertion procedure. In Rule 4, there is exactly one $t$ in $T(t,s-1)$. Thus, inserting a $t$ will result in a tableau where the first column has two boxes filled with a $t$. If $\lambda=\nu$ as in Rule 5, then $r>t$. Thus no integer is being inserted as we move from $\mu$ to $\gamma$, so $\mu=\gamma$ and the edge labels are unchanged. Similarly, if $\lambda=\mu$, then there is no $X$ to the left of the square we are considering, and so no boxes labeled $t$ in the $T(t,s)$. Thus there is no change in the insertion and recording tableaux. Rule 6 follows directly from insertion rule YF1. In considering Rule 7, note that $r](212) edge node[right]{$ $} (312); \path[->] (3213) edge [bend right=70] (4213); \path[->] (3412) edge [bend left=40] (3124); \end{tikzpicture}}\vspace{2em} \caption{The upward-oriented edges of the Pieri construction of KPR as described in Example~\ref{ex:KPR}.}\label{fig:tabgraphup} } \end{figure} \begin{figure}\vspace{2em} {\tiny \rotatebox{90}{\begin{tikzpicture}[scale=1] \node (empty) at (0,1) {$\varnothing$}; \node (1) at (0,2) {$\young(1)$}; \node (21) at (-2,3) {$\young(1,2)$}; \node (12) at (2,3) {$\young(12)$}; \node (321) at (-4,5) {$\young(1,2,3)$}; \node (213) at (-2,5) {$\young(13,2)$}; \node (212) at (0,5) {$\young(12,2)$}; \node (312) at (2,5) {$\young(12,3)$}; \node (123) at (4,5) {$\young(123)$}; \node (4321) at (-9,7) {$\young(1,2,3,4)$}; \node (3214) at (-8,7) {$\young(14,2,3)$}; \node (4213) at (-7,7){$\young(13,2,4)$}; \node (4312) at (-6,7) {$\young(12,3,4)$}; \node (3213) at (-5,7) {$\young(13,2,3)$}; \node (3212) at (-4,7) {$\young(12,2,3)$}; \node (3412) at (-3,7){$\young(12,34)$}; \node (2413) at (-2,7) {$\young(13,24)$}; \node (2312) at (-.5,7) {$\young(12,23)$}; \node (3123) at (1,7) {$\young(123,3)$}; \node (2134) at (2.5,7) {$\young(134,2)$}; \node (3124) at (4,7) {$\young(124,3)$}; \node (4123) at (5.5,7) {$\young(123,4)$}; \node (2123) at (7,7) {$\young(123,2)$}; \node (1234) at (8.5,7) {$\young(1234)$}; \node (32312) at (-2,8) {$\young(12,23,3)$}; \node (23123) at (-.5,8) {$\young(123,23)$}; \node (32123) at (2,8) {$\young(123,2,3)$}; \node (323123) at (0,9) {$\young(123,23,3)$}; \draw (empty)--(1)--(21)--(321)--(4321) (321)--(3214) (21) to [bend left=40] (3213) (21)--(213) (1)--(212)--(3212) (212)--(2123) (212)--(2312) (12)--(312) (12) to [bend right=40] (3123) (12)--(123) (1)--(12) (213)--(2134) (213)--(2413) (213)--(4213) (312)--(3124) (312)--(3412) (312)--(4312) (123)--(1234) (123)--(4123) (212)--(32312) (212) to [bend left=40] (23123) (212) to [bend right=10] (32123) (212) to [bend right=15] (323123); \end{tikzpicture}}\vspace{2em} \caption{The downward-oriented edges of the Pieri construction of KPR as described in Example~\ref{ex:KPR}.}\label{fig:tabgraphdown} } \end{figure} \end{exem} \subsection{Malvenuto--Reutenauer deformations} \label{sec:MR} \begin{exem}\label{ex:PermTrees} Figure~\ref{fig:permtrees} shows dual graphs where vertices are permutations. On the left, a permutation $\sigma$ covers $\pi$ if $\pi$ is obtained from $\sigma$ by deleting the rightmost number (in terms of position in the permutation) and standardizing. On the right, a permutation $\sigma$ covers $\pi$ if $\pi$ is obtained from $\sigma$ by deleting the largest number in the permutation. There are other similar constructions, which can be found in~\cite[Example~2.6.8]{F}. \begin{figure} \begin{tikzpicture}[scale=.75] \node (empty) at (0,0) {$\varnothing$}; \node (1) at (0,1) {1}; \node (21) at (-2,3) {21}; \node (12) at (2,3) {12}; \node (321) at (-3.5,5) {321}; \node (213) at (-2,5) {213}; \node (312) at (-.5,5) {312}; \node (123) at (3.5,5) {123}; \node (132) at (2,5) {132}; \node (231) at (.5,5) {231}; \draw (empty)--(1)--(21)--(321) (312)--(21)--(213) (1)--(12)--(123) (231)--(12)--(132); \end{tikzpicture} \hspace{.15in} \begin{tikzpicture}[scale=.75] \node (empty) at (0,0) {$\varnothing$}; \node (1) at (0,1) {1}; \node (21) at (-2,3) {21}; \node (12) at (2,3) {12}; \node (321) at (-3.5,5) {321}; \node (213) at (-2,5) {213}; \node (312) at (-.5,5) {312}; \node (123) at (3.5,5) {123}; \node (132) at (2,5) {132}; \node (231) at (.5,5) {231}; \draw (empty)--(1)--(21)--(321) (231)--(21)--(213) (1)--(12)--(123) (312)--(12)--(132); \end{tikzpicture} \\ \begin{tikzpicture}[scale=.75] \node (empty) at (0,0) {$\varnothing$}; \node (1) at (0,1) {1}; \node (21) at (-2,3) {21}; \node (12) at (2,3) {12}; \node (321) at (-3.5,5) {321}; \node (213) at (-2,5) {213}; \node (312) at (-.5,5) {312}; \node (123) at (3.5,5) {123}; \node (132) at (2,5) {132}; \node (231) at (.5,5) {231}; \draw (empty)--(1)--(21)--(321) (312)--(21)--(213) (1)--(12)--(123) (231)--(12)--(132); \end{tikzpicture} \hspace{.1in} \begin{tikzpicture}[scale=.75] \node (empty) at (0,0) {$\varnothing$}; \node (1) at (0,1) {1}; \node (21) at (-2,3) {21}; \node (12) at (2,3) {12}; \node (321) at (-3.5,5) {321}; \node (213) at (-2,5) {213}; \node (312) at (-.5,5) {312}; \node (123) at (3.5,5) {123}; \node (132) at (2,5) {132}; \node (231) at (.5,5) {231}; \draw (empty)--(1)--(21)--(321) (231)--(21)--(213) (1)--(12)--(123) (312)--(12)--(132) (12)--(empty) (213)--(1) (231)--(1) (123) to [bend right=5] (1) (123) to [bend left=5] (empty); \end{tikzpicture} \caption{The top row shows the dual graded graph with permutations for vertices as described in Example~\ref{ex:PermTrees}. The bottom row is the corresponding Pieri deformation.}\label{fig:permtrees} \end{figure} Consider the Hopf algebra of permutations with the shuffle product and coproduct defined by $\Delta(w)=\sum std(u)\otimes std(v)$, where the concatenation of $u$ and $v$ is $w$ and $std(w)$ sends $w$ to the unique permutation with the same relative order. For example, $std(1375)=1243$. Take $d$ to be the operator that deletes the rightmost letter of the permutation. Then we see that $a_1(v,w)$ is the coefficient of $v$ in $d(w)$. We create a Pieri deformation by letting $f=1+12+123+\cdots$ and $a_2(v,w)$ be the coefficient of $w$ in $f\cdot v$. Clearly $d(f)=\varnothing+f$, and we use Lemma~\ref{lem:derivation} to see that $d$ is a derivation. It then follows from Theorem~\ref{thm:pieri} that the resulting graph is a dual filtered graph. This dual filtered graph is shown in Figure~\ref{fig:permtrees}. \end{exem} \begin{exem}\label{ex:mMR} We next describe a $K$-theoretic analogue of the Malvenuto--Reutenauer Hopf algebra. For details, see~\cite{LP}. A small multi-permutation or $\mathfrak{m}$-permutation of $[n]$ is a word $w$ in the alphabet $1,2,\dots,n$ such that no two consecutive letters in $w$ are equal. Now let the small multi-Malvenuto--Reutenauer Hopf algebra, $\mathfrak{m}$MR be the free $\mathbb{Z}$-module of arbitrary $\mathbb{Z}$-linear combinations of multi-permutations. Recall the definition of the multishuffle product from Example~\ref{ex:L}. Given two $\mathfrak{m}$-permutations $w=w_1\dots w_k$ and $u=u_1\dots u_l$, define their product to be the multishuffle product of $w$ with $u[n]$, where $w$ contains exactly the numbers $1,2,\dots,n$ and $u[n]=(u_1+n)(u_2+n)\dots(u_l+n)$. Let $st(w)$ send a word $w$ to the unique $\mathfrak{m}$-permutation $u$ of the same length such that $w_i\leq w_j$ if and only if $u_i\leq u_j$ for each $1\leq i,j\leq l(w)$. Define the coproduct in $\mathfrak{m}$MR by $\Delta(w)=st(\blacktriangle(w))$, where $\blacktriangle(w)$ is the cuut coproduct defined in Example~\ref{ex:L}. Using $g=1$, $d=\xi\circ\Delta$, and $f=1$, we form the dual filtered graph partially shown below. Notice that $d(w_1\dots w_k)=w_1\dots w_k + w_1\dots w_{k-1}$, so $d(f)=\varnothing+f$. \[ \begin{tikzpicture}[scale=.8] \node (empty) at (0,0) {$\varnothing$}; \node (1) at (0,1) {1}; \node (12) at (-2,2) {12}; \node (21) at (2,2) {21}; \node (121) at (-3.5,4) {121}; \node (123) at (-2.5,4) {123}; \node (132) at (-1.5,4) {132}; \node (312) at (-.5,4) {312}; \node (213) at (.5,4) {213}; \node (231) at (1.5,4) {231}; \node (321) at (2.5,4) {321}; \node (212) at (3.5,4) {212}; \draw (empty)--(1)--(12)--(123) (12)--(132) (12)--(231) (12)--(121) (21)--(212) (21)--(312) (21)--(213) (1)--(21)--(321) (12)--(121) (21)--(212) (1) to [out=60,in=100,distance=.5cm] (1) (21) to [out=-60,in=-100,distance=.5cm] (21) (12) to [out=-60,in=-100,distance=.5cm] (12) (121) to [out=60,in=100,distance=.5cm] (121) (212) to [out=60,in=100,distance=.5cm] (212) (321) to [out=60,in=100,distance=.5cm] (321) (132) to [out=60,in=100,distance=.5cm] (132) (123) to [out=60,in=100,distance=.5cm] (123) (312) to [out=60,in=100,distance=.5cm] (312) (213) to [out=60,in=100,distance=.5cm] (213) (231) to [out=60,in=100,distance=.5cm] (231); \end{tikzpicture}\hspace{.1in} \begin{tikzpicture}[scale=.8] \node (empty) at (0,0) {$\varnothing$}; \node (1) at (0,1) {1}; \node (12) at (-2,2) {12}; \node (21) at (2,2) {21}; \node (121) at (-3.5,4) {121}; \node (123) at (-2.5,4) {123}; \node (132) at (-1.5,4) {132}; \node (312) at (-.5,4) {312}; \node (213) at (.5,4) {213}; \node (231) at (1.5,4) {231}; \node (321) at (2.5,4) {321}; \node (212) at (3.5,4) {212}; \draw (empty)--(1)--(12)--(123) (12)--(132) (12)--(312) (1)--(21)--(321) (21)--(231) (21)--(213) (121) to [bend right=40] (1) (212) to [bend left=40] (1); \end{tikzpicture} \] \end{exem} \subsection{Stand-alone examples} \begin{exem}\label{ex:FibonacciGraph} There is another graph with the same set of vertices as the Young--Fibonacci lattice called the Fibonacci graph. The vertices of the Fibonacci graph are words on the alphabet $\{1,2\}$, or snakeshapes, and a word $w$ is covered by $w'$ if $w'$ is obtained from $w$ by adding a 1 at the end or by changing any 1 into a 2. In the graph that is dual to the Fibonacci graph, $w$ is covered by $w'$ if $w$ is obtained from $w'$ by deleting a 1, and the multiplicity of the edge between $w$ and $w'$ is the number of ways to delete a 1 from $w'$ to get $w$. The pair form a dual graded graph shown below, see~\cite[Example~2.3.7]{F}, where the numbers next to the edges denote multiplicity. \[ \begin{tikzpicture}[scale=.8] \node (empty) at (0,-1) {$\varnothing$}; \node (1) at (0,1) {1}; \node (11) at (0,3) {11}; \node (2) at (1.5,3) {2}; \node (111) at (0,5) {111}; \node (21) at (1.5,5) {21}; \node (12) at (3,5) {12}; \node (1111) at (0,7) {1111}; \node (211) at (1.5,7) {211}; \node (121) at (3,7) {121}; \node (112) at (4.5,7) {112}; \node (22) at (6,7) {22}; \draw (empty)--(1)--(11)--(111)--(1111) (1)--(2) (11)--(12)--(22) (11)--(21)--(22) (111)--(211) (111)--(121) (111)--(112) (2)--(21)--(211) (12)--(121); \end{tikzpicture} \hspace{.2in} \begin{tikzpicture}[scale=.8] \node (empty) at (0,-1) {$\varnothing$}; \node (1) at (0,1) {1}; \node (11) at (0,3) {11}; \node (2) at (1.5,3) {2}; \node (111) at (0,5) {111}; \node (21) at (1.5,5) {21}; \node (12) at (3,5) {12}; \node (1111) at (0,7) {1111}; \node (211) at (1.5,7) {211}; \node (121) at (3,7) {121}; \node (112) at (4.5,7) {112}; \node (22) at (6,7) {22}; \node (label2) at (-.2,2) {\tiny{2}}; \node (label3) at (-.2,4) {\tiny{3}}; \node at (-.2,6) {\tiny{4}}; \node at (1.3,6) {\tiny{2}}; \node at (3.95,6) {\tiny{2}}; \draw (empty)--(1)--(11)--(111)--(1111) (2)--(21)--(211) (2)--(12)--(112) (21)--(121)--(12); \end{tikzpicture} \] We construct a Pieri deformation of this dual graded graph by adding downward-oriented edges so that in the resulting set of downward-oriented edges, there is an edge from $w'$ to $w$ for every way $w$ can be obtained from $w'$ by deleting at least one 1. For example, there are six edges from 1111 to 11 since there are six ways to delete two 1's from 1111 to obtain 11. \[ \begin{tikzpicture}[scale=.8] \node (empty) at (0,-1) {$\varnothing$}; \node (1) at (0,1) {1}; \node (11) at (0,3) {11}; \node (2) at (1.5,3) {2}; \node (111) at (0,5) {111}; \node (21) at (1.5,5) {21}; \node (12) at (3,5) {12}; \node (1111) at (0,7) {1111}; \node (211) at (1.5,7) {211}; \node (121) at (3,7) {121}; \node (112) at (4.5,7) {112}; \node (22) at (6,7) {22}; \draw (empty)--(1)--(11)--(111)--(1111) (1)--(2) (11)--(12)--(22) (11)--(21)--(22) (111)--(211) (111)--(121) (111)--(112) (2)--(21)--(211) (12)--(121); \end{tikzpicture} \begin{tikzpicture}[scale=.8] \node (empty) at (0,-1) {$\varnothing$}; \node (1) at (0,1) {1}; \node (11) at (0,3) {11}; \node (2) at (1.5,3) {2}; \node (111) at (0,5) {111}; \node (21) at (1.5,5) {21}; \node (12) at (3,5) {12}; \node (1111) at (0,7) {1111}; \node (211) at (1.5,7) {211}; \node (121) at (3,7) {121}; \node (112) at (4.5,7) {112}; \node (22) at (6,7) {22}; \node (label2) at (-.2,2) {\tiny{2}}; \node (label3) at (-.2,4) {\tiny{3}}; \node at (-.2,6) {\tiny{4}}; \node at (1.3,6) {\tiny{2}}; \node at (3.5,6) {\tiny{2}}; \node at (-.75,5) {\tiny{6}}; \node at (-.75,3) {\tiny{3}}; \node at (.8,4.5) {\tiny{4}}; \draw (empty)--(1)--(11)--(111)--(1111) (2)--(21)--(211) (2)--(12)--(112) (21)--(121)--(12) (121)--(2) (11) to [bend right=30] (empty) (111) to [bend left=40] (empty) (111) to [bend right=30] (1) (1111) to [bend right=40] (empty) (1111) to [bend left=30] (1) (1111) to [bend right=40] (11) (211) to [bend left=20] (2) (112) to [bend left=20] (2); \end{tikzpicture} \] \begin{theo} The resulting graph is a dual filtered graph. \end{theo} \begin{proof} Consider an algebra structure on words in alphabet $\{1,2\}$ with shuffle product, as in~\cite{F}. Consider $d$ to be the operator that changes any $2$ into a $1$ or deletes the last digit if it is $1$. According to~\cite[Lemma~2.3.9]{F}, $d$ is a derivation such that the coefficient of $v$ in $d(w)$ is the multiplicity $a_1(v,w)$ for the Fibonacci graph. Take $f=1 + 11 + 111 + \cdots$. It is easy to see that $d(f)= id + f$ and that the coefficient of $w$ in $fv$ is the multiplicity $a_2(v,w)$. Thus, Theorem~\ref{thm:pieri} applies, and the statement follows. \end{proof} \end{exem} \begin{exem}\label{ex:polys} The dual filtered graph on the polynomial ring shown below is that mentioned in Section~\ref{sec:differential}. We take $U$ to be multiplication by $x$ and $D=e^{\frac{\partial}{\partial x}}-1$. It is easy to check that $DU-UD=D+I$, so the result is a dual filtered graph. \[ \begin{tikzpicture} \node (1) at (0,0) {1}; \node (x) at (0,2) {$x$}; \node (x2) at (0,4) {$x^2$}; \node (x3) at (0,6) {$x^3$}; \node (x4) at (0,8) {$x^4$}; \node (x5) at (0,10) {$x^5$}; \draw (1)--(x)--(x2)--(x3)--(x4)--(x5); \end{tikzpicture} \hspace{1in} \begin{tikzpicture} \node (1) at (0,0) {1}; \node (x) at (0,2) {$x$}; \node (x2) at (0,4) {$x^2$}; \node (x3) at (0,6) {$x^3$}; \node (x4) at (0,8) {$x^4$}; \node (x5) at (0,10) {$x^5$}; \node at (-.1,9) {\tiny{5}}; \node at (-.1,7) {\tiny{4}}; \node at (-.1,5) {\tiny{3}}; \node at (-.1,3) {\tiny{2}}; \node at (.6,4) {\tiny{3}}; \node at (-.55,6) {\tiny{6}}; \node at (-1.1,5) {\tiny{4}}; \node at (.57,7) {\tiny{10}}; \node at (1.05,6) {\tiny{10}}; \node at (1.7,5) {\tiny{5}}; \draw (1)--(x)--(x2)--(x3)--(x4)--(x5) (x2) to [bend right=20] (1) (x3) to [bend left=30] (1) (x3) to [bend left=20] (x) (x4) to [bend right=20] (x2) (x4) to [bend right=30] (x) (x4) to [bend right=40] (1) (x5) to [bend left=20] (x3) (x5) to [bend left=30] (x2) (x5) to [bend left=40] (x) (x5) to [bend left=50] (1); \end{tikzpicture} \] \end{exem} \section{Enumerative theorems via up-down calculus} \label{sec:enum} Let $\varnothing$ 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. \begin{theo} For any dual filtered graph, the coefficient of $\varnothing$ in $D^k U^n (\varnothing)$ is $T(n,k)$. \end{theo} \begin{proof} We think of replacing the fragments $DU$ inside the word by either $UD$, $D$, or $1$. This way the initial word gets rewritten until there is no $DU$ in any of the terms: \[ D^k U^n= D^{k-1} U D U^{n-1} + D^k U^{n-1} + D^{k-1} U^{n-1}=\cdots. \] Only the terms of the form $U^t$ that appear at the end can contribute to the coefficient we are looking for, since $D (\varnothing)=0$. Among those, only the terms $U^0=1$ can contribute. Thus, we are looking for all the terms where $D$'s and $U$'s eliminated each other. It is easy to see that each $D$ eliminates at least one $U$, and each $U$ must be eliminated by some $D$. The number of ways to match $D$'s with $U$'s in this way is exactly $T(n,k)$. \end{proof} Let $f^{\lambda}$ be the number of increasing tableaux of shape $\lambda$. Let $g^{\lambda}_n$ be the number of set-valued tableaux of shape $\lambda$ and content $1, \dots, n$. Let $F(n)$ denote the \emph{Fubini number}, or \emph{ordered Bell number} - the number of ordered set partitions of $[n]$. \begin{coro} We have \[ \sum_{|\lambda|\leq n} f^{\lambda} g^{\lambda}_n= F(n). \] \end{coro} \begin{proof} The left side is clearly the coefficient of $\varnothing$ in $(D + D^2 + \dots + D^n) U^n (\varnothing)$. It remains to note that $\sum_{k=1}^n T(n,k)= F(n)$. \end{proof} This is the analogue of the famous Frobenius--Young identity. Of course, this also follows from bijectivity 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. \begin{theo} For any dual filtered graph the coefficient of $\varnothing$ in $(D+U)^n (\varnothing)$ is equal to the number of set partitions of $[n]$ with parts of size at least $2$. \end{theo} \begin{proof} As before, the desired coefficient is equal to the number of ways for all $D$'s to eliminate all $U$'s via the commutation relation. Each factor in the product \[ (D+U)(D+U)\cdots(D+U) \] thus either eliminates one of the factors to the right of it or is eliminated by a factor to the left. Grouping together such factors, we get a set partition with parts of size at least $2$. On the other hand, any such set partition corresponds to a choice of $D$ in the first factor of each part and of $U$'s in the rest. Thus, it corresponds to term $1$ after such $D$'s eliminate such $U$'s. The statement follows. \end{proof} \longthanks{We thank Vic Reiner, Alexander Garver, and Thomas Lam for helpful discussions. We thank the reviewers for valuable suggestions for exposition.} \bibliographystyle{amsplain-ac} \bibliography{ALCO_Patrias_35} \end{document}