%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2023}
\articlenumber{82}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

%\usepackage{amsmath,amsthm,amssymb}
\usepackage{mathrsfs}
%\usepackage[shortlabels]{enumitem}
\usepackage{stmaryrd}
\usepackage{shuffle}
\usepackage{multicol} %multiple columns
\usepackage{mathtools}
\usepackage{commath}%for \abs
\usepackage{ytableau}
 
\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\F}{\mathbb{F}}
\renewcommand{\P}{\mathbb{P}}
\newcommand{\Kappa}{\mathcal{K}}
\newcommand{\ori}{\overline{\mathbf{o}}}


\newcommand{\qand}{\quad \text{and}\quad}
\newcommand{\vect}{\vec}
\newcommand{\lp}{\left(}
\newcommand{\rp}{\right)}
\newcommand{\lb}{\left[}
\newcommand{\rb}{\right]}
\newcommand{\lc}{\left\{}
\newcommand{\rc}{\right\}}
\newcommand{\lab}{\left|}
\newcommand{\rab}{\right|}
\newcommand{\normal}{\mathrel{\unlhd}}
\DeclareMathOperator{\im}{im}
\DeclareMathOperator{\curl}{curl}
\DeclareMathOperator{\diver}{div}
\DeclareMathOperator{\sgn}{sgn}
\DeclareMathOperator{\Ht}{ht}
\DeclareMathOperator{\Wt}{wt}
\newcommand{\ra}{\rightarrow}
\renewcommand{\Re}{\mathbb{R}}
\newcommand{\Nat}{\mathbb{N}}
\newcommand{\sB}{\mathcal{B}}
\newcommand{\sM}{\mathcal{M}}
\newcommand{\sF}{\mathcal{F}}
\DeclareRobustCommand*{\ora}{\overrightarrow}  %%% Use me for A(D,k)
\renewcommand{\phi}{\varphi}
\newcommand{\eps}{\varepsilon}
\DeclareMathOperator{\Real}{Re}
\DeclareMathOperator{\Imag}{Im}
\DeclareMathOperator{\inv}{inv}
\DeclareMathOperator{\inc}{Inc}
\DeclareMathOperator{\des}{des}
\DeclareMathOperator{\asc}{asc}
\DeclareMathOperator{\DES}{DES}
\DeclareMathOperator{\fix}{fix} %fixed points for involutions
\DeclareMathOperator{\Hess}{Hess}
\DeclareMathOperator{\ch}{ch}


 \usepackage{tikz}
\usetikzlibrary{calc}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{cor}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{question}[theorem]{Question}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{problem}[theorem]{Problem}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{example}[theorem]{Example}
\usepackage{caption}
\usepackage{subcaption}


%% define your title in the usual way
\title{RSK for \textbf{3}-free posets}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Kyle Celano\addressmark{1}\thanks{\href{mailto:kac265@miami.edu}{kac265@miami.edu}.}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, University of Miami, Miami, FL \\}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{A long-standing open problem is to find an RSK-like correspondence between permutations and pairs of tableaux coming from Gasharov’s decomposition of Stanley’s chromatic symmetric functions into Schur functions. In this, we present such a correspondence $RSK_P$ for incomparability graphs of $\mathbf{3}$-free posets $P$ that moreover preserve the descent and inversion statistics. We then extend $RSK_P$ to bijections from proper colorings and multicolorings providing new combinatorial proofs for the Schur expansions of Gasharov for the chromatic symmetric function, of Shareshian--Wachs for the chromatic quasisymmetric function, and of Hwang for the multichromatic quasisymmetric function, and its refinement to equivalence classes of acyclic orientations in the case that $P$ is $\mathbf{3}$-free.}

%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{symmetric functions, RSK algorithms, chromatic symmetric functions}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations; i.e., [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
\addbibresource{sample.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

\section{Introduction}
The famous Robinson-Schensted-Knuth $RSK$ correspondence is a bijection 

\begin{equation}\label{rsk bijection syt}
    \mathfrak{S}_n\to \bigsqcup_{\lambda\vdash n}SYT_\lambda\times SYT_\lambda    
    \end{equation}
where $\mathfrak{S}_n$ is the set of permutations on $[n]:=\{1,\dots,n\}$ and $SYT_\lambda$ is the set of standard Young tableaux of shape $\lambda$. This is a \textit{row-insertion} algorithm taking each letter $w_i$ of a permutation $w=w_{1}\cdots w_n\in \mathfrak{S}_n$ and inserting into a pair $(T_{i-1},R_{i-1})$ of size $i-1$ by a \textit{bumping} procedure in $T_{i-1}$ and a \textit{recording} procedure in $R_{i-1}$ to make a pair $(T_i,R_i)$ of size $i$. The bijection takes $w$ to $(T_n,R_n)$ (see \cite[Chapter 7]{stanley_1999}). 

A general form of $RSK$ is a bijection 
\begin{equation}\label{rsk ssytssyt}
\mathcal{P}^n\to \bigsqcup_{\lambda\vdash n}SSYT_\lambda\times SSYT_\lambda \end{equation}
where $SSYT_\lambda$ is the set of semistandard Young tableaux of shape $\lambda$ and where $\mathcal{P}^n$ is the set of size $n$ generalized permutations, which are multisets $\{\binom{u_i}{v_i}\}_{i=1}^n$ of biletters $\binom{u_i}{v_i}$ where $u_i$ and $v_i$ are positive integers. These can be written as two-line arrays so that if 
\[\binom{u}{v}=\lp\begin{array}{cccc}
     u_1&u_2&\dots&u_n  \\
     v_1&v_2&\dots&v_n 
\end{array}\rp\]
 then $u$ is weakly increasing and if $u_i=u_j$ and $i<j$, then $v_i<v_j$. This general $RSK$ inserts the \textit{bottom} word $v$ into the first tableau and records the procedure with \textit{top} word~$u$.
 
 If we restrict to when the top word $u$ is $12\cdots n$, we get a bijection from the set $\P^n$ of length $n$ words on the alphabet $\P$ of positive integers \begin{equation}\label{rsk bijection ssyt}
  \P^n \to \bigsqcup_{\lambda\vdash n}SSYT_\lambda\times SYT_\lambda.
\end{equation}
If we restrict to when the bottom word $v$ is a permutation in $\mathfrak{S}_n$, we get another bijection  \begin{equation}\label{rsk bijection ssyt upsidedown}
  \{(u,v)\in \mathcal{P}^n\mid v\in \mathfrak{S}_n
  \}\to \bigsqcup_{\lambda\vdash n}SYT_\lambda\times SSYT_\lambda.  
\end{equation} 

The bijection (\ref{rsk bijection ssyt}) provides a combinatorial proof of the decomposition of the complete homogeneous symmetric function $h_{1^n}$ in terms of Schur functions 
\[h_{1^{n}}= \sum_{\lambda\vdash n}f^\lambda s_\lambda\]
and the bijection (\ref{rsk bijection syt}) provides a bijective proof of
\[n!=\sum_{\lambda\vdash n}(f^\lambda)^2\]
where $f^\lambda$ is the number of standard Young tableaux of shape $\lambda\vdash n.$ 

Gasharov \cite{gasharov_1996} obtains the following decomposition of Stanley's chromatic symmetric function \cite{stanley_1995} for the incomparability graph $\inc(P)$ of a $(\mathbf{3+1})$-free poset $P$,

\begin{equation}\label{eq: gash} X_{\inc(P)}(\mathbf{x},t)=\sum_{\lambda\vdash n}f^{P}_\lambda s_\lambda
\end{equation}
where $f^P_{\lambda}$ counts a certain class of Young tableaux $\mathcal{T}_{P,\lambda}$ called \textit{$P$-tableaux} of shape $\lambda$.\footnote{Definitions to be given in the next section} This specializes to 
\begin{equation}\label{eq: gash n}
    n!=\sum_{\lambda\vdash n}f^\lambda_P f^\lambda.
\end{equation}
Gasharov obtains (\ref{eq: gash}) by applying Jacobi--Trudi and then a sign-reversing involution. A long-standing open problem then is to find an \textit{$RSK$-like} bijection proving (\ref{eq: gash}) and (\ref{eq: gash n}) directly. 

Progress has been made on this problem for certain classes of $(\mathbf{3}+\mathbf{1})$-free posets by Sundquist--Wagner--West and Chow \cite{SUNDQUIST199736,chow_1999} for a large class of subposets and Kim--Pylyavskyy \cite{kim-pylyavskyy_2020} for a slightly smaller one.

In this extended abstract\footnote{See \cite{celano_2022} for the full paper}, we first note that proper colorings can be represented as generalized permutations whose bottom word is a permutation and hence (\ref{eq: gash}) is equivalent to existence of a bijection analogous to that in (\ref{rsk bijection ssyt upsidedown}). We then construct a relatively simple $RSK$-like bijection when $P$ is $\mathbf{3}$-free (or, length at most 1): this row-insertion algorithm inserts bottom letters of a generalized permutation representing the coloring and records the procedure with the top word, just as in $RSK$. 
Although the previous algorithms apply to much broader classes of posets, ours is much simpler. 

Also, for $\mathbf{3}$-free natural unit interval orders, our $RSK$ gives a bijective proof of the Shareshian--Wachs \cite{SW, shareshian_wachs_2016} refinement of (\ref{eq: gash}) for chromatic quasisymmetric functions. Hwang \cite{hwang_2022} further generalizes (\ref{eq: gash}) to multichromatic quasisymmetric functions, which involve multicolorings of a graph. By viewing these multicolorings as generalized permutations, we extend our $RSK$ to a bijective map from multicolorings to pairs of semistandard $P$-tableaux and semistandard Young tableaux, thereby attaining an analogue to a dual form of (\ref{rsk ssytssyt}). This provides a bijective proof of Hwang's generalization in the case of $\mathbf{3}$-free natural unit interval orders. Moreover, we can restrict our $RSK$ to colorings of Hwang's equivalence classes of acyclic orientations, which provides a bijective proof of the Schur expansion for his pieces of the chromatic quasisymmetric function in the case of $\mathbf{3}$-free natural unit interval orders.

This extended abstract is organized as follows: In Section 2, we provide the relevant definitions and background for chromatic (quasi)symmetric functions and $P$-tableaux. In Section 3, we describe the $RSK$ for $3$-free posets on permutations (\cref{RSKP Definition}, \cref{RSKP Theorem}) and then show how to extend $RSK$ to obtain bijective proofs of the Schur expansions of Gasharov, Shareshian--Wachs (\cref{RSKP color Theorem}) and Hwang (\cref{RSKP multicolor,rskp acyclic theorem}).

    \section{Chromatic Symmetric Functions and \texorpdfstring{$P$}{}-tableaux}
    Stanley's \textit{chromatic symmetric function} \cite{stanley_1995} is defined for a graph $G=([n],E)$ to be
    \[X_G(\mathbf{x})=\sum_{\kappa\in \Kappa(G)}x_{\kappa(1)}\cdots x_{\kappa(n)}\]
    where $\Kappa(G)$ is the set of proper colorings of $G$. The incomparability graph of a poset $P$, denoted $\inc(P)$, is the graph whose vertices are the elements of $P$ and whose edges correspond to pairs of incomparable elements of $P$.

    A $\textit{$P$-tableau}$\footnote{This is the conjugate version of Gasharov's original definition \cite{gasharov_1996}. We make this change to more naturally describe the algorithm as a row-insertion algorithm.} is a Young tableau of size $|P|=n$ filled with the elements of $P$ such that 
    \begin{itemize}
        \item each element of $P$ appears exactly once,
        \item if $x$ is immediately to the left of $y$, then $x\not>_Py$, and 
        \item if $x$ is immediately above of $y$, then $x<_Py$.
    \end{itemize}
    See \cref{fig:poset and ptableaux example} for an example.
    
    \begin{figure}[t]
        \centering
        \ytableausetup{nosmalltableaux}
    \begin{tikzpicture}
  \node (one) at (-6,-4) {$1$};
  \node (two) at (-5,-4) {$2$};
  \node (three) at (-4,-4) {$3$};
  \node (four) at (-6,-2) {$4$};
  \node (five) at (-5,-2) {$5$};
  \node (six) at (-4,-2) {$6$};
  \draw (one) -- (four)
        (one) -- (five)
        (one) -- (six)
        (two) -- (five)
        (two) -- (six)
        (three) -- (six);
  \node (pair) at (0,-3) {$\begin{ytableau}
  3&1&2&4\\
  6&5
  \end{ytableau}$};
\end{tikzpicture}
        \caption{A poset $P$ and a $P$-tableaux}
        \label{fig:poset and ptableaux example}
    \end{figure}
    
    Let $\mathcal{T}_{P,\lambda}$ be the set of $P$-tableaux of shape $\lambda$ and $f^{\lambda}_P=|\mathcal{T}_{P,\lambda}|$. Recall that a poset is \textit{($\mathbf{a+b}$)-free} if it contains no induced subposet that is the disjoint union of an $a$-chain and a $b$-chain. For a partition $\lambda$, let $\lambda^*$ denote its conjugate. Then, Gasharov showed the following by applying the Jacobi--Trudi identity and then a sign-reversing involution.
    \begin{theorem}[\text{\cite[Theorem 4]{gasharov_1996}}]\label{theorem: gash}
     For a ($\mathbf{3+1}$)-free poset $P$, $X_{\inc(P)}(\mathbf{x})=\sum_{\lambda\vdash n }f^{\lambda}_P s_{\lambda^*}$.
    \end{theorem}
    % A \textit{row-strict} Young tableau is one where the rows strictly increase and the columns weakly increase. Let $RST_\lambda$ be the set of row-strict tableaux of shape $\lambda$. The conjugate of a semistandard Young tableau is a row-strict tableau. Hence, the monomials of the right-hand side of Gasharov's expansion correspond to pairs $(T,R)$ where $T$ is a $P$-tableau and $R$ is a row-strict tableau of the same shape. We identify the set of permutations $\mathfrak{S}_n$ with the subset $\{\kappa_{w}\}_{w\in \mathfrak{S}_n}\subset \Kappa(G)$ given by $\kappa_w(i)=w^{-1}(i)$ for $w\in \mathfrak{S}_n$ (why we do this is will be apparent later, see \cref{remark: invg for w}). Thus, our problem of finding an appropriate $RSK$ that would provide direct bijective proofs of Theorem $\ref{theorem: gash}$ and (\ref{eq: gash n}) is as follows.
     A \textit{row-strict} Young tableau is one where the rows strictly increase and the columns weakly increase. Let $RST_\lambda$ be the set of row-strict tableaux of shape $\lambda$. If $R\in RST_\lambda$, then its conjugate $R^*\in SSYT_{\lambda^*}$. Hence, $s_{\lambda^*}=\sum_{R\in RST_\lambda}x^{m_1(R)}x^{m_2(R)}\cdots$ where $m_i(R)$ is the number of times $i$ appears in $R$.  We identify the set of permutations $\mathfrak{S}_n$ with the subset $\{\kappa_{w}\}_{w\in \mathfrak{S}_n}\subset \Kappa(G)$ given by $\kappa_w(i)=w^{-1}(i)$ for $w\in \mathfrak{S}_n$ (why we do this is will be apparent later, see \cref{remark: invg for w}). Thus, our problem of finding an appropriate $RSK$ that would provide direct bijective proofs of \cref{theorem: gash} and (\ref{eq: gash n}) is as follows.
    \begin{problem}\label{RSK Problem}
    For a $(\mathbf{3+1})$-free poset $P$ with $G=\inc(P)$, find an \textit{$RSK$-like} bijection \[RSK_P:\Kappa(G)\to \bigsqcup_{\lambda\vdash n}\mathcal{T}_{P,\lambda}\times RST_{\lambda}\] which restricts to a bijection \[RSK_P:\mathfrak{S}_{n}\to \bigsqcup_{\lambda\vdash n}\mathcal{T}_{P,\lambda}\times SYT_{\lambda}.\]
    \end{problem} 
    A \textit{natural unit interval order} (or, NUIO) is a $(\mathbf{3+1})$-free and $(\mathbf{2+2}$)-free poset with a certain natural labeling. Let $G=\inc(P)$ for a natural unit interval order $P$. The Shareshian--Wachs \cite{SW,shareshian_wachs_2016} \textit{chromatic quasisymmetric function} for $G$ is
    \[X_G(\mathbf{x},t)=\sum_{\kappa\in \Kappa(G)}t^{\des(\kappa)}x_{\kappa(1)}\cdots x_{\kappa(n)}\]
    where $\des(\kappa)$ is the number of edges $ij\in E$ such that $i<j$ and $\kappa(i)>\kappa(j)$. This quasisymmetric function specializes to Stanley's chromatic symmetric function by setting $t=1$.  Shareshian and Wachs prove that $X_{G}(\mathbf{x},t)$ is in fact a symmetric function. For a $P$-tableaux $T\in \mathcal{T}_P$ define
    \[\inv_G(T)=\#\{xy\in E\mid \text{$x<y$ and $x$ is to the right of $y$}\}.\]
    Let $f^{\lambda}_{P,i}$ be the number of $P$-tableaux $T$ with $\lambda(T)=\lambda$ and $\inv_G(T)=i$.
    
    \begin{theorem}[\text{\cite[Theorem 6.3]{shareshian_wachs_2016} }]\label{theorem: sw schur}
    For a natural unit interval order $P$, 
    \begin{equation}\label{sw schur}
    X_{\inc(P)}(\mathbf{x},t)=\sum_{i\geq 0}t^{i}\sum_{\lambda\vdash n}f^\lambda_{P,i}s_{\lambda^*}.\end{equation} 
    \end{theorem} 
  
    Hence, for $RSK_P$ to prove (\ref{sw schur}) bijectively, it must additionally satisfy: \begin{equation}\label{invG prev}
        \text{If $P$ is a NUIO and $RSK_P(\kappa)=(T,R)$ then $\des(\kappa)=\inv_G(T)$}.
    \end{equation}

    \begin{remark}\label{remark: invg for w}
    For $w\in \mathfrak{S}_n$, the Shareshian--Wachs \textit{$G$-inversion statistic} \cite{SW,shareshian_wachs_2016}  is
    \[\inv_G(w)=\#\{\{w(i),w(j)\}\in E\mid i<j,w(i)>w(j)\}.\] 
     The $G$-inversion statistic $\inv_G(w)$ is a natural extension of the classical inversion $\inv(w)$ statistic to the graphs we are considering. If $\kappa_w\in \Kappa(G)$ is defined by $\kappa_w(i)=w^{-1}(i)$, then $\des(\kappa_w)=\inv_G(w)$. Hence, (\ref{invG prev}) for the restriction to $\mathfrak{S}_n$ is that if $RSK_P(w)=(T,R)$, then $\inv_G(w)=\inv_G(T)$.
    \end{remark}
    
    In the next section, we will present an $RSK_P$  solving \cref{RSK Problem} which additionally satisfies (\ref{invG prev}) for $\mathbf{3}$-free posets.
    
    \begin{remark} The class of
    $\mathbf{3}$-free posets have been studied extensively in the literature of chromatic quasisymmetric functions under a few different, but equivalent, definitions.
\begin{itemize}
    \item They are \textit{length} 1 or 0 posets and their incomparability graphs are unit interval orders with bipartite complement as in Abreu--Nigro \cite{abreu_nigro_2021}.
    \item They correspond to \textit{abelian} Hessenberg varieties as in Harada--Precup \cite{Harada-Precup_2017}.
    \item They correspond to Dyck paths with \textit{bounce number} 1 or 0 as in Cho--Huh \cite{Cho-Huh_2017}.
\end{itemize}
The commonality between each of the definitions and interpretations of $\mathbf{3}$-free posets is that the resulting theory for chromatic quasisymmetric functions and Hessenberg varieties is quite nice and allows for one to prove $e$-positivity in a variety of ways. Therefore, one should expect an $RSK$ for $\mathbf{3}$-free posets to be just as nice.  
\end{remark}

    
    \section{RSK for 3-free posets}
     In this section, we assume that $P$ is a $\mathbf{3}$-free poset with incomparability graph $G$. Hence, any $P$-tableau $T$ has at most 2 rows.
     %Moreover, we will use the \textit{conjugate} definitions of $P$-tableaux and $\inv_G(T)$ to the ones above, meaning a $P$-tableaux $T$ satisfies
    % \begin{itemize}
    %     \item If $x$ is immediately to the left of $y$, then $x\not>_Py$, and 
    %     \item If $x$ is immediately above of $y$, then $x<_Py$.
    % \end{itemize}
    % and $\inv_G(T)$ be the number of edges $ij\in E$ such that $i<j$ but $i$ is to the right of $j$ in $T$.
    \subsection{\texorpdfstring{$RSK_P$}{} for permutations}
      We will define a row-insertion algorithm that inserts the letters of permutation $w=w_1\cdots w_n$ one by one to make a series of pairs $(T_1,R_1),\dots,(T_n,R_n)$ of $P$-tableau $T_i$ and standard Young tableau $R_i$ with same shape.

To do so, we must describe a series of \textit{local moves} on $P$-arrays (which are defined to be $P$-tableaux in columns only). Given a $(1,2,1)$ subshape of a $P$-array $T$, we change it into a (2,1,1) shape with the same entries
\[\ytableausetup{nosmalltableaux}
\begin{ytableau}z&*(green)x&\omega\\
\none &*(green)y\end{ytableau}\longrightarrow \begin{ytableau} *(green)\tilde{z}&\tilde{x}&\tilde{\omega}\\*(green)\tilde{y}
\end{ytableau}
 \]

 Define the change according to the 4 cases as shown in \cref{fig:local moves}.
 \begin{figure}[h!]
     \centering
\begin{tikzpicture}

\node (1s) at (-2.75,.5) {$(1)$};
\node (1) at (1,0) {
\ytableausetup{nosmalltableaux}
\begin{tikzpicture}
\node (T) at (.5,0) {$\begin{ytableau}z&*(green)x&\omega\\
\none &*(green)y\end{ytableau}$};
\node (U) at (3.5,0) {$\begin{ytableau}
*(green)x&y&\omega\\
*(green)z
\end{ytableau}$};
\draw[-to] (T)--(U); 

\node at (-1.5,.5) {$z>_P x$};
% \node (x) at (-1.5,-.5) {$x$};
% \node (y) at (-1.5,.5) {$y$};
% \node (z) at (-2,.5) {$z$};
% \node (omega) at (-1,-.5) {$\omega$};
% \draw (x)--(y);
% \draw (x)--(z);
\end{tikzpicture}


};

%%%%%%%% local move (2) SW %%%%%%%%%%%%%%
\node (2s) at (-2.75,-1.5) {$(2a)$};
\node (2) at (1,-2) {
\ytableausetup{nosmalltableaux}
\begin{tikzpicture}
\node (T) at (.5,0) {$\begin{ytableau}z&*(green)x&\omega\\
\none &*(green)y\end{ytableau}$};
\node (U) at (3.5,0) {$\begin{ytableau}
*(green)x&z&\omega\\
*(green)y
\end{ytableau}$};
\draw[-to] (T)--(U); 

\node at (-1.5,.5) {$z\not>_P x$};
\node at (-1.5,0) {$z\not<_P y$};
\node at (-1.5,-.5) {$z\not>_P \omega $};
\end{tikzpicture}

};

%%%%%%%% local move (2e) NE %%%%%%%%%%%%%%
\node (2es) at (5.3,.5) {$(2b)$};
\node (2e) at (9,0) {
\ytableausetup{nosmalltableaux}
\begin{tikzpicture}
\node (T) at (.5,0) {$\begin{ytableau}z&*(green)x&\omega\\
\none &*(green)y\end{ytableau}$};
\node (U) at (3.5,0) {$\begin{ytableau}
*(green)\omega &z&x\\
*(green)y
\end{ytableau}$};
\draw[-to] (T)--(U); 
\node at (-1.5,.5) {$z\not>_P x$};
\node at (-1.5,0) {$z\not<_P y$};
\node at (-1.5,-.5) {$z>_P \omega $};
\end{tikzpicture}
};

%%%%%%%% local move (2e) NE %%%%%%%%%%%%%%
\node (3s) at (5.3,-1.5) {$(3)$};
\node (3) at (9,-2) {
\ytableausetup{nosmalltableaux}
\begin{tikzpicture}
\node (T) at (.5,0) {$\begin{ytableau}z&*(green)x&\omega\\
\none &*(green)y\end{ytableau}$};
\node (U) at (3.5,0) {$\begin{ytableau}
*(green)z &x&\omega\\
*(green)y
\end{ytableau}$};
\draw[-to] (T)--(U); 
\node at (-1.5,.5) {$z\not>_P x$};
\node at (-1.5,0) {$z<_P y$};
\end{tikzpicture}

};
\end{tikzpicture}
     \caption{The 4 local moves}
     \label{fig:local moves}
 \end{figure}
 

\begin{definition}[RSK for $\mathbf{3}$-free $P$]\label{RSKP Definition} Let $P$ be a $\mathbf{3}$-free poset and let $w\in \mathfrak{S}_n$.
\begin{enumerate}
    \item For $w_1$, define
    \[T_1=\begin{ytableau}w_1\end{ytableau}\qquad R_1 = \begin{ytableau}1
    \end{ytableau}\]
    \item Suppose $w_{1},\dots,w_{i-1}$ have been inserted forming a pair $(T_{i-1},R_{i-1})$ of $P$-tableau and standard Young tableaux, respectively, of the same shape $\lambda$ with $|\lambda|=i-1$.  
    \begin{enumerate}
        \item[(a)] If $w_i$ is not smaller in $P$ than the last number of the first row of $T_{i-1}$, then place $w_i$ at the end of the row creating $T_i$.
        \item[(b)] Otherwise, suppose $T_{i-1}$ looks like
        
        \[
        \ytableausetup
  {boxsize=2em}
        \begin{ytableau}
        ~&\none[\cdots]&&x_{k+1}&x_k&x_{k-1}&\none[\cdots]&x_1\\
        ~&\none[\cdots]&
        \end{ytableau}
        \] 
and let $x_k$ be the leftmost element of the first row such that $x_j>_P w_i$ for all $j\leq k$ (so, $x_{k+1}\not>_P w_i$). Then replace $x_k$ by $w_i$ and place $x_k$ in the cell directly below its old cell (this is empty because $P$ is $\mathbf{3}$-free). Then, apply the \textit{local moves} moving this new domino to the left until we have a partition shape. Call this new tableau $T_i$.
    \end{enumerate}
    \noindent In either case, if $c$ is the new cell of $T_i$, set $R_i(c)=i$.
    \end{enumerate}
We write $RSK_P(w)=(T,R)$ for the result after inserting the final letter of $w$.
\end{definition}
\begin{example} Let $P$ be as in \cref{fig:poset and ptableaux example} and suppose we have
\[\ytableausetup{smalltableaux}
(T_5,R_5)\ =\ \lp
\begin{ytableau}
3&4&2&5&6\\
\end{ytableau}\ ,\ \begin{ytableau}
1&2&3&4&5\\
\end{ytableau}\rp\]
and we want to insert $w_6=1$. Then we need 3 local moves, which we indicate with an arrow.
\[\begin{ytableau}
3&4&2&*(green)1&6\\
\none & \none &\none & *(green)5
\end{ytableau}
\xrightarrow[\quad]{(3)}
\begin{ytableau}
3&4&*(green)2&1&6\\
\none & \none &*(green)5 
\end{ytableau}
\xrightarrow[\quad]{(2b)}
\begin{ytableau}
3&*(green)1&4&2&6\\
\none & *(green)5 
\end{ytableau}
\xrightarrow[\quad]{(2a)}
\begin{ytableau}
*(green)1&3&4&2&6\\
*(green)5 
\end{ytableau}
\]
\end{example}

\begin{example}\label{RSKP example}
Let $P$ be as in \cref{fig:poset and ptableaux example} and let $w=361452$. We show the full $RSK_P$ for $w$ in \cref{fig:RSKP example}. If we apply a local move during the insertion step to compute $T_i$, we show them to the left of the corresponding step.

\begin{figure}[h!]
    \centering
    \[\ytableausetup{smalltableaux}
\begin{array}{rc|clc}
    T_i &\quad&\quad &R_i&\qquad\ \qquad\ \qquad    \\[12pt]
    \begin{ytableau}
    3
    \end{ytableau}
& & &
    \begin{ytableau}
    1
    \end{ytableau}\\
    \begin{ytableau}
    3&6
    \end{ytableau}
& & &
    \begin{ytableau}
    1&2
    \end{ytableau}\\
    \begin{ytableau}
    3&*(green)1\\\none&*(green)6
    \end{ytableau}\xrightarrow[\quad]{(3)}
    \begin{ytableau}
    *(green)3&1\\*(green)6
    \end{ytableau}
& & &
    \begin{ytableau}
    1&2\\3
    \end{ytableau}\\[12pt]
    \begin{ytableau}
    3&1&4\\6
    \end{ytableau}
& & &
    \begin{ytableau}
    1&2&4\\3
    \end{ytableau}\\[12pt]
    \begin{ytableau}
    3&1&4&5\\6
    \end{ytableau}
& & &
    \begin{ytableau}
    1&2&4&5\\3
    \end{ytableau}\\
    \begin{ytableau}
    3&1&4&*(green)2\\6&\none&\none&*(green)5
    \end{ytableau}\xrightarrow[\quad]{(2a)}
    \begin{ytableau}
    3&1&*(green)2&4\\6&\none&*(green)5
    \end{ytableau}
    \xrightarrow[\quad]{(3)}
    \begin{ytableau}
    3&*(green)1&2&4\\6&*(green)5
    \end{ytableau}
& & &
    \begin{ytableau}
    1&2&4&5\\3&6
    \end{ytableau}\\
\end{array}
\]
    \caption{$RSK_P(361452)$}
    \label{fig:RSKP example}
\end{figure}


\end{example}

\begin{theorem}\label{RSKP Theorem}
For $\mathbf{3}$-free $P$, the above algorithm $w\mapsto (T,R)$ is a bijection 
\[RSK_P:\mathfrak{S}_{n}\to \bigsqcup_{\lambda\vdash n }\mathcal{T}_{P,\lambda}\times SYT_\lambda\]
such that if $P$ is additionally a natural unit interval order and $RSK_P(w)=(T,R)$, then $\inv_G(w)=\inv_G(T).$
\end{theorem}
\begin{proof}[Proof (Idea)]
One needs to check that 
\begin{enumerate}
    \item[(1)] local moves create $P$-tableaux,
    \item[(2)] each local move has a unique \textit{inverse} local move, and
    \item[(3)] each local move preserves $G$-inversions when $P$ is a natural unit interval order.
\end{enumerate}
Then (1) plus $\mathbf{3}$-free gives a well-definition; (2) gives the bijective property; and (3) plus the definition of the insertion gives (\ref{invG prev}).
\end{proof}
\begin{example}
In \cref{RSKP example}, we have $\inv_G(w)=\inv_G(T)=5$. See \cref{fig:full RSKP} for a complete example for $n=3$.
\end{example}
\begin{figure}[h!]
    \centering
    \begin{tikzpicture}
  \node (1) at (0,0) {$1$};
  \node (2) at (1,1) {$2$};
  \node (3) at (0,2) {$3$};
  \draw (1)--(3);
  \node (table) at (7,.7) {\begin{tabular}{ll}
$123\mapsto \lp \begin{ytableau} 1&2&3
\end{ytableau},
\begin{ytableau}1&2&3\end{ytableau}\rp$&$132\mapsto \lp \begin{ytableau} 1&3&2
\end{ytableau},
\begin{ytableau}1&2&3\end{ytableau}\rp$\\
$213\mapsto \lp \begin{ytableau} 2&1&3
\end{ytableau},
\begin{ytableau}1&2&3\end{ytableau}\rp$&$312\mapsto \lp \begin{ytableau} 1&2\\3
\end{ytableau},
\begin{ytableau}1&3\\2\end{ytableau}\rp$
\\
$231\mapsto \lp \begin{ytableau} 1&2\\3
\end{ytableau},
\begin{ytableau}1&2\\3\end{ytableau}\rp$&
$321\mapsto \lp \begin{ytableau} 3&2&1
\end{ytableau},
\begin{ytableau}1&2&3\end{ytableau}\rp$
\end{tabular}};
\end{tikzpicture}
    \caption{$RSK_P$ for a poset $P$ on $[3]$}
    \label{fig:full RSKP}
\end{figure}
Hence, \cref{RSKP Theorem} provides a new combinatorial proof of (\ref{eq: gash n}) when $P$ is $\mathbf{3}$-free.
% \subsubsection{Descents and \texorpdfstring{$P$}{}-descents}
 For $w\in \mathfrak{S}_n$, let $\DES(w)$ be the usual descent set of a permutation. For a standard Young tableaux $R$ define $\DES(R)=\{i\in [n-1]\mid \text{ $i+1$ is below $i$}\}.$
 Then classical $RSK$ has the property that if $RSK(w)=(T,R)$, then $\DES(w)=\DES(R)$. For a poset $P$, define $\DES_P(w)=\{i\in [n-1]\mid w_i>_Pw_{i+1}\}.$
 Then $RSK_P$ also ``preserves descents", meaning the following.
    \begin{prop}\label{prop: descent pres}
    For $3$-free posets $P$, if $RSK_P(w)=(T,R)$, then $\DES_P(w)=\DES(R)$.
    \end{prop}
    \begin{example}
    In \cref{RSKP example}, we have $\DES_P(w)=\DES(R)=\{2,5\}$.
    \end{example}
    \begin{remark}
    Chow \cite{chow_1999} points out that the Sundquist--Wagner--West algorithm preserves descents only on a subclass of the posets considered in \cite{SUNDQUIST199736}. This smaller subclass does not contain $\mathbf{3}$-free posets. The Kim--Pylyavskyy algorithm satisfies the similar property that $\DES(R)=\{n-d\mid d\in \DES_P(w)\}$.
    \end{remark}
\subsection{Proper colorings}
While section 3.1 was just for permutations, it serves as the foundation for an $RSK_P$ of colorings. For each proper coloring $\kappa\in \Kappa(G)$, form the generalized permutation $\{\binom{\kappa(i)}{i}\}_{i=1}^n$ of biletters.  Then write this as a two-line array 
\[\binom{\overline{\kappa}}{w}=\lp\begin{array}{cccc}
     \kappa(w_1)&\kappa(w_2)&\dots&\kappa(w_n)  \\
     w_1&w_2&\dots&w_n 
\end{array}\rp\]
so that $\overline{\kappa}=(\kappa(w_1)\leq \kappa(w_2)\leq \cdots\leq \kappa(w_n))$ and if $\kappa(w_i)=\kappa(w_j)$ and $i<j$, then $w_i>w_j$.
\begin{example}
Let $P$ be as in \cref{fig:poset and ptableaux example} and let $\kappa$ be the coloring of $\inc(P)$ below
\[\begin{tikzpicture}
  \node (G) at (-3,-3) {$G$};
  \node (a) at (-2,-3) {$1$};
  \node (b) at (-1,-3) {$2$};
  \node (c) at (0,-3) {$3$};
  \node (d) at (1,-3) {$4$};
  \node (e) at (2,-3) {$5$};
  \node (f) at (3,-3) {$6$};
  \node (1) at (-2,-2.5) {$3$};
  \node (2) at (-1,-2.5) {$2$};
  \node (3) at (0,-2.5) {$1$};
  \node (4) at (1,-2.5) {$3$};
  \node (5) at (2,-2.5) {$2$};
  \node (6) at (3,-2.5) {$1$};
  \node (k) at (-3,-2.5) {$\kappa$};
  \draw (a)--(b)--(c)--(d)--(e)--(f);
  \draw (a) to[out=-40,in=-140] (c);
  \draw (b) to[out=-40,in=-140] (d);
  \draw (c) to[out=-40,in=-140] (e);
  \draw (d) to[out=-40,in=-140] (f);
  %\draw[-to] (3.5,-2.75) to (4.5,-2.75);
  \node (kw) at (7.5,-2.75) { $\begin{pmatrix}
  \overline{\kappa}\\w
  \end{pmatrix}=
  \begin{pmatrix}
  1&1&2&2&3&3\\
  6&3&5&2&4&1
  \end{pmatrix}
  $};
\end{tikzpicture}\]
\end{example}

Then, the general $RSK_P$ inserts the bottom word $w$ (which is a permutation) to get a $P$-tableau $T$ as in \cref{RSKP Definition} and records the procedure in $R$ with the top word $\overline{\kappa}$. Our choice of 2-line array ensures that if $\kappa(w_i)=\kappa(w_{i+1})$, then $w_i>_P w_{i+1}$, so $\kappa(w_i)$ and $\kappa(w_{i+1})$ will be in separate rows of $R$, and hence $R$ will be \textit{row-strict}.

% \begin{remark}
% These generalized permutations have no \textit{repeated} biletters. Hence, this is really a \textit{dual} RSK, so the conjugation of one of the tableaux is to be expected.
% \end{remark}

\begin{theorem}\label{RSKP color Theorem}
For $\mathbf{3}$-free $P$, the above algorithm $\kappa\mapsto (T,R)$ is bijection 
\[RSK_P:\mathcal{K}(G)\to \bigsqcup_{\lambda\vdash n }\mathcal{T}_{P,\lambda}\times RST_{\lambda}\]
such that if $RSK_P(w)=(T,R)$ and $P$ is additionally a natural unit interval order, then $\des(\kappa)=\inv_G(T).$ Moreover, restricting this map to $\mathfrak{S}_n$ gives the bijection in \cref{RSKP Theorem}.
\end{theorem}

 \cref{RSKP color Theorem} hence provides new combinatorial proofs of the Schur bases expansions given in \cref{theorem: gash,theorem: sw schur} when $P$ is $\mathbf{3}$-free.
\begin{remark}
By applying $(P,\omega)$-partition reciprocity, the monomials of $\omega X_G(\mathbf{x},t)$ are seen to be indexed by pairs $(\ori,\kappa)$ of acyclic orientations $\ori$ and \textit{weak colorings} $\kappa$ of $\ori$, meaning $x\to y$ in $\ori$ implies that $\kappa(x)\leq \kappa(y)$. In the full paper \cite{celano_2022}, we extend $RSK_P$ to this collection. 
\end{remark}
% \subsubsection{2 row shapes for other posets}
% One common extension of the study of $X_G(\mathbf{x},t)$ for $\mathbf{3}$-free posets is that the results generalize to the coefficients of $s_\lambda$ and $e_\lambda$ when $\lambda^*$ has at most 2 rows. $RSK_P$ can be similarly extended. Let $P$ for just this subsection be any $(\mathbf{3+1})$-free poset. For $w\in\mathfrak{S}_n$, say a \textbf{$P$-decreasing subsequence} of length $\ell$ of $w$ is a subsequence $w_{i_1}>_P w_{i_2}>_P \cdots>_P w_{i_\ell}$ where $i_1<\cdots<i_\ell$. Let $\mathfrak{S}^{P,2}_n$ be the collection of $w\in \mathfrak{S}_n$ that do not contain a $P$-decreasing subsequence of length $3$. Note that if $P$ is $\mathbf{3}$-free, then $\mathfrak{S}^{P,2}_n=\mathfrak{S}_n$. Under very mild adjustments to the local moves (1) and (3) to account for $3$-chains, we can extend $RSK_P$ to this case.  
% \begin{theorem}\label{all posets} For all  $(\mathbf{3+1})$-free posets $P$, 
% \[RSK_P:\mathfrak{S}^{P,2}_n\to \bigsqcup_{\substack{\lambda\vdash n\\\lambda_3=0}}\mathcal{T}_{P,\lambda}\times SYT_\lambda\]
%  is a statistic-preserving bijection.
%  \end{theorem}
% The extension to colorings is carried out the same way: call $\Kappa^2(G)$ the set of colorings whose permutation $w$ (in the above sense) is in $S_n^{P,2}$. Then we have a statistic perserving bijection
% \[RSK_P:\Kappa^{2}(G)\to \bigsqcup_{\substack{\lambda\vdash n\\\lambda_3=0}}\mathcal{T}_{P,\lambda}\times SSYT_\lambda\]

% \subsection{Weak Colorings-Cut?}
% The Shareshian--Wachs proof of the $F$-basis expansion starts by writing
% \[X_G(\mathbf{x},t)=\sum_{\ori\in O(G)}t^{\des(\ori)}\sum_{\kappa\in \mathcal{C}(\ori)}x_\kappa\]
% where $O(G)$ is the set of acyclic orientations $\ori$ of $G$ and a coloring $\kappa$ is in $\mathcal{C}(\ori)$ if $i\to j$ in $\ori$ implies that $\kappa(i)\leq\kappa(j)$. The number $\des(\ori)$ is the set of arcs $i\to j$ such that $i<j$. By $(P,\omega)$-reciprocity, we can express the dual of the chromatic quasisymmetric function as
% \[\omega X_G(\mathbf{x},t)=\sum_{\ori\in O(G)}t^{\des(\ori)}\sum_{\kappa\in \mathcal{C}^{\leq}(\ori)}x_\kappa\]
% where $\kappa\in \mathcal{C}^{\leq}(\ori)$ if $i\to j$ in $\ori$ implies that $\kappa(i)\leq \kappa(j)$, in which we say $\kappa$ is a \textit{weak coloring} compatible with $\ori$ (cf. Section 4 of \cite{stanley_1995} for $t=1$). Since $\omega(s_\lambda)=s_{\lambda^*}$, this implies we can make a similar RSK-like bijection from the set $\bigsqcup_{\ori\in O(G)}\mathcal{C}^{\leq}(\ori)$. Under very minor alterations, $RSK_P$ can be adapted to this situation as $RSK_P^*$
% \begin{cor}
%  If $P$ is $\mathbf{3}$-free, then $RSK_P^*$ is a bijection
%  \[RSK_P^*:\bigsqcup_{\ori\in O(G)}\mathcal{C}^{\leq}(\ori)\to \bigsqcup_{\lambda\vdash n} \mathcal{T}_{P,\lambda}\times SSYT_\lambda\]
%  such that if $RSK^*_P(\ori,\kappa)=(T,R)$ and $P$ is a natural unit interval order, then $\des(\ori)=\inv_G(T)$. Moreover, this restricts to the bijection in \cref{RSKP Theorem}.
% \end{cor}
 \subsection{Proper multicolorings}\label{section: multicoloring}
 We now come to the fullest generality of $RSK_P$, mirroring the dual of the RSK bijection (\ref{rsk ssytssyt}). A \textit{proper multicoloring} of a graph $G$ is a map $\kappa$ that assigns each vertex $i$ a finite set $\kappa(i)\subset \P$ such that if $ij\in E$ then $\kappa(i)\cap \kappa(j)=\emptyset$. Let $\mathcal{MK}_n(G)$ be the set of proper colorings so that $\sum_{v\in G}|\kappa(v)|=n$. We can turn a multicoloring $\kappa\in \mathcal{MK}_n(G)$ into a generalized permutation $\binom{\overline{\kappa}}{w}$ of length $n$ analogously to how we did colorings. See \cref{example: multi}.
\begin{example}\label{example: multi}
Let $P$ be as in \cref{fig:poset and ptableaux example} and let $\kappa$ be the multicoloring of $\inc(P)$ below
\[\begin{tikzpicture}
  \node (G) at (-3,-3) {$G$};
  \node (a) at (-2,-3) {$1$};
  \node (b) at (-1,-3) {$2$};
  \node (c) at (0,-3) {$3$};
  \node (d) at (1,-3) {$4$};
  \node (e) at (2,-3) {$5$};
  \node (f) at (3,-3) {$6$};
  \node (1) at (-2,-2.5) {$3$};
  \node (1a) at (-2,-2) {$4$};
  \node (2) at (-1,-2.5) {$2$};
  \node (2a) at (-1,-2) {$5$};
  \node (2b) at (-1,-1.5) {$7$};
  \node (3) at (0,-2.5) {$1$};
  \node (3a) at (0,-2) {$6$};
  \node (4) at (1,-2.5) {$3$};
  \node (5) at (2,-2.5) {$2$};
  \node (5a) at (2,-2) {$4$};
  \node (6) at (3,-2.5) {$1$};
  \node (k) at (-3,-2.5) {$\kappa$};
  \draw (a)--(b)--(c)--(d)--(e)--(f);
  \draw (a) to[out=-40,in=-140] (c);
  \draw (b) to[out=-40,in=-140] (d);
  \draw (c) to[out=-40,in=-140] (e);
  \draw (d) to[out=-40,in=-140] (f);
  %\draw[-to] (3.5,-2.75) to (4.5,-2.75);
  \node (kw) at (8.5,-2.75) { $\begin{pmatrix}
  \overline{\kappa}\\w
  \end{pmatrix}=\lp
  \begin{array}{cccccccccccc}
  1&1&2&2&3&3&4&5&5&6&7\\
  6&3&5&2&4&1&1&5&2&3&2
  \end{array}\rp
  $};
\end{tikzpicture}\]
% Then $w=415263$ and $\tilde{\kappa}=112233$.
\end{example}
 
 Hence, the analogous version of (\ref{rsk ssytssyt})\footnote{More precisely, a \textit{dual} form of $RSK$. } is a bijection
 
 \[RSK_P:\mathcal{MK}_n(G)\to \bigsqcup_{\lambda\vdash n}\mathcal{SST}_{P,\lambda}\times RST_{\lambda}\]
 where $\mathcal{SST}_{P,\lambda}$ is the set of \textit{semistandard} $P$-tableaux (meaning you can repeat elements of $P$) of shape $\lambda$. For a multicoloring $\kappa$ of $G$, let the \textit{type} $\mu$ of a multicoloring $\kappa$ be the composition $\mu=(|\kappa(1)|,|\kappa(2)|,\dots)$ and let $\des(\kappa)$ be the number of pairs $\{(a,i),(b,j)\}$ such that if $a\in \kappa(i)$, $b\in \kappa(j)$, $ij\in E(G)$ and $i<j$, then $a>b$. The definition of $\inv_G(T)$ is easily extended to $T\in \mathcal{SST}_{P,\lambda}$.

\begin{theorem}\label{RSKP multicolor}
 If $P$ is $\mathbf{3}$-free, then for each $n$, $RSK_P$ is a bijection
 \[RSK_P:\mathcal{MK}_n(G)\to \bigsqcup_{\lambda\vdash n} \mathcal{SST}_{P,\lambda}\times RST_{\lambda}\]
 such that if $RSK_P(\kappa)=(T,R)$, then the type of $\kappa$ is the content of $T$.  If $P$ is additionally a natural unit interval order, then $\des(\kappa)=\inv_G(T)$.
\end{theorem}
 
When $P$ is $\mathbf{3}$-free, \cref{RSKP multicolor} provides new bijective proofs of Gasharov's Schur expansion \cite[Theorem 4]{gasharov_1996} of the multichromatic symmetric function $X_G(\mathbf{x};\mu)$ and when $P$ is a natural unit interval order, Hwang's expansion \cite[Theorem 4.19]{hwang_2022} of the multichromatic quasisymmetric function $X_G(\mathbf{x},t;\mu)$ of type $\mu$. These are both defined analogously to their chromatic versions,
\[X_G(\mathbf{x},t;\mu)=\sum_{\lambda\vdash n}|\mathcal{SST}_{P,\lambda,\mu}|s_\lambda\qquad X_G(\mathbf{x},t;\mu)=\sum_{i\geq 0}t^i\sum_{\lambda\vdash n}|\mathcal{SST}_{P,\lambda,\mu,i}|s_\lambda\]
 where $\mathcal{SST}_{P,\lambda,\mu,i}$ is the set of $T\in \mathcal{SST}_{P,\lambda}$ with content $\mu$ and $\inv_G(T)=i$ and $\mathcal{SST}_{P,\lambda,\mu}=\bigsqcup_{i\geq 0}\mathcal{SST}_{P,\lambda,\mu,i}$. In particular, we get a direct combinatorial proof that for each composition $\mu=(\mu_1,\mu_2,\dots)$ of $n$, we have
 \[\binom{n}{\mu}=\sum_{\lambda\vdash n}|\mathcal{SST}_{P,\lambda,\mu}|f^\lambda.\]
 
%  The \textit{type} of a multicoloring $\kappa$ is the vector $\mu=(\mu_1,\mu_2,\dots,\mu_n)$ with $\mu_i=\#\kappa(i).$ Let $\mathcal{MK}(G,\mu)$ be the multicolorings of type $\mu$. In \cite{stanley_1995}, Stanley also defines the \textit{multichromatic quasisymmetric function} of type $\mu$ to be 
%  \[X_{G}(\mathbf{x};\mu)=\sum_{\kappa\in \mathcal{MK}(G,\mu)}x_\kappa\qquad \text{where}\quad x_\kappa=\prod_{i=1}^n\prod_{j\in \kappa(i)}x_j\]
%  where $\des(\kappa)$ is the number of pairs $(\{i,a\},\{j,b\})$ such that $a\in \kappa(i)$, $b\in \kappa(j)$, $i<j$ and $a>b$.
% Hence, setting $\mu=(1^n)$ yields $X_G(\mathbf{x},t)$. Gasharov obtains the Schur expansion of this function by using \textit{semistandard} $P$-tableaux which are $P$-tableaux in which one may repeat elements which has an analogous $\inv_G$ statistic. The \textit{content} of a semistandard $P$-tableaux $T$ is the vector $\mu=(\mu_1,\dots)$ where $\mu_i$ is the number of times $i$ is repeated in $T$. Hence, if $\mu=(1^n)$, then $T$ is a (standard) $P$-tableau. If $\mathcal{SST}_{P,\lambda,\mu}$ is the set of semistandard $P$-tableaux of shape $\lambda$ and content $\mu$ then Gasharov shows that
%  \begin{equation}\label{hwang schur}
%  X_G(\mathbf{x},\mu)=\sum_{\lambda\vdash n}|\mathcal{SST}_{P,\lambda,\mu}|s_\lambda.\end{equation}
%  Hence, the analogous version of (\ref{rsk ssytssyt}) is
% \[RSK_P:\mathcal{MK}(G)\to \bigsqcup_{\lambda\vdash n}\mathcal{SST}_{P,\lambda}\times RST_{\lambda}\]
% such if $RSK_P(\kappa)=(T,R)$ then type of $\kappa$ is the content of $T$. 

% To define $RSK_P$, one turns a multicoloring into an acyclic digraph by replacing a vertex $i$ of $G$ by the directed complete graph on $\kappa(i)$ with its edges pointed toward lower values and then orienting edges between complete graphs in the usual way. This is called a \textit{heap}. From here, one can make a word $w$ to insert via $RSK_P$, define an analogous increasing word $\tilde{\kappa}$, and obtain a reverse generalized permutation $\binom{\tilde{\kappa}}{w}$. This completely generalizes the construction for $\Kappa(G)$.
% For a multicoloring $\kappa$, let $\des(\kappa)$ be the number of pairs $\{(a,i),(b,j)\}$ such that if $a\in \kappa(i)$, $b\in \kappa(j)$ and $i<j$, then $a>b$. 


% In addition to proving $(\ref{hwang schur})$ bijectively for $\mathbf{3}$-free posets, this also proves Hwang's Schur expansion of multichromatic \textit{quasi}symmetric function \cite[Theorem 4.19]{hwang_2022} when $P$ is a $\mathbf{3}$-free natural unit interval order.

% \begin{remark}
% The Schur expansion of $X_G(\mathbf{x};\mu)$ implies that for all compositions $\mu=(\mu_1,\dots,\mu_n)$ of $n$ we have 
% \[\binom{n}{\mu_1,\mu_2,\dots,\mu_n}=\sum_{\lambda\vdash n}|\mathcal{SST}_{P,\lambda,\mu}|f^\lambda\]
% and \cref{RSKP multicolor} provides a combinatorial proof of this when $P$ is $\mathbf{3}$-free. 
% \end{remark}
\subsubsection{Equivalence Classes of Acyclic Orientations}
Hwang \cite{hwang_2022} gives a further refinement of $X_G(\mathbf{x},t;\mu)$, but we will just discuss the case of $\mu=(1^n)$ for clarity here. A \textit{local flip} of an acyclic orientation $\ori$ changes $a\to b\leftarrow c$ to $a\leftarrow b\to c$ provided $a$ and $c$ are covered by $b$ in the poset induced by $\ori$. Say $\ori'$ is \textit{equivalent} to $\ori$ if it is related by a sequence of local flips, and let $[\ori]$ be its equivalence class. Note that if $\ori'\in [\ori]$ then $\des(\ori')=\des(\ori)$. Let $\mathcal{K}(G,[\ori])$ be the set of colorings that are \textit{compatible} (in a sense) with an $\ori'\in [\ori]$ and define a quasisymmetric function
\[X_{G,[\ori]}(\mathbf{x})=\sum_{\kappa\in \Kappa(G,[\ori])}x_\kappa\]
Note that $X_G(\mathbf{x},t)=\sum_{[\ori]}t^{\des(\ori)}X_{G,[\ori]}(\mathbf{x},t)$. When $G=\inc(P)$ for a natural unit interval order $P$, Hwang uses noncommutative symmetric function theory to prove that this is a symmetric function with Schur expansion
\[X_{G,[\ori]}(\mathbf{x})=\sum_{T\in \mathcal{T}_{P,[\ori]}}s_{\lambda(T)}.\]
where $\mathcal{T}_{P,[\ori]}$ is some set of $P$-tableaux that are \textit{compatible} (in a sense) with an $\ori'\in [\ori]$. All $T\in \mathcal{T}_{P,[\ori]}$ have $\inv_G(T)=\des(\ori)$. We prove this expansion bijectively using $RSK_P$. Let $\mathcal{T}_{P,[\ori],\lambda}$ be the set of $T\in \mathcal{T}_{P,[\ori]}$ with shape $\lambda$.
\begin{theorem}\label{rskp acyclic theorem}
Let $P$ be a  $\mathbf{3}$-free natural unit interval order. For each acyclic orientation $\ori$ of $G=\inc(P)$, $RSK_P$ restricts to a bijection
 \[RSK_P:\Kappa(G,[\ori])\to \bigsqcup_{
 \lambda\vdash n} \mathcal{T}_{P,[\ori],\lambda}\times RST_{\lambda}\]
\end{theorem}

\begin{remark}\label{remark: beast}
   We show that $RSK_P$ can be extended to the \textit{beast} poset (\cref{fig:beast}) or more generally the \textit{beastly} poset\footnote{This is the second $e$-positive class of posets considered by Cho and Huh \cite{Cho-Huh_2017} with $\mathbf{3}$-free being the first.} (\cref{fig:beastly}). The beast poset is explicitly avoided in the previous algorithms \cite{SUNDQUIST199736,kim-pylyavskyy_2020}.
    \begin{figure}[h!]
        \centering
        \begin{subfigure}[b]{0.35\textwidth}
         \centering
        \begin{tikzpicture}
    \node (2) at (0,0) {$2$};
    \node (1) at (1,-1) {$1$};
    \node (3) at (1,0) {$3$};
    \node (5) at (1,1) {$5$};
    \node (4) at (2,0) {$4$};
    \draw (2)--(5)--(3)--(1)--(4);
    \end{tikzpicture}
         \caption{The beast poset}
         \label{fig:beast}
     \end{subfigure}
        \begin{subfigure}[b]{0.6\textwidth}
         \centering
        \begin{tikzpicture}
    \node (2) at (-3,0) {$2$};
    \node (mdots) at (-2,0) {$\dots$};
    \node (m1) at (-1,0) {$m-1$};
    \node (1) at (1,-1) {$1$};
    \node (m) at (0,0) {$m$};
    \node (mrdots) at (1,0) {$\dots$};
    \node (n) at (1,1) {$n$};
    \node (n1) at (5,0) {$n-1$};
    \node (M1) at (2,0) {$r$};
    \node (M2) at (3,0) {$r+1$};
    \node (M1dots) at (4,0) {$\dots$};
    \draw (m1)--(n)--(m)--(1)--(M1);
    \draw (2)--(n);
    \draw (1)--(n1);
    \draw (1)--(M2);
    \draw (n)--(M1);
    \end{tikzpicture}
         \caption{The beastly poset}
         \label{fig:beastly}
     \end{subfigure}
     \caption*{}
     \label{fig: beast and beastly}
    \end{figure}
    \end{remark}

\acknowledgements{I would like to thank my advisor Michelle Wachs for her great help in the preparation of this extended abstract. I would also like to thank the reviewers for their helpful comments.}

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography



\end{document}
