%% 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]{FPSAC2025}
\articlenumber{25}
%% 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}
%Adding our packages

% \usepackage[utf8]{inputenc}
\usepackage{amsmath,amsfonts}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{graphicx}
% \usepackage[shortlabels]{enumitem}
% \usepackage{genyoungtabtikz}
\usepackage[boxsize=1.2em]{ytableau}
\usepackage{cancel}
\usepackage[normalem]{ulem}
\usepackage{multicol}
\usepackage{hyperref}
\usepackage{cleveref}
\usepackage{pgfmath}
\usepackage{tikz}
\usepackage{listofitems}
\usetikzlibrary{calc, backgrounds}


%For putting a picture into tikz
\usetikzlibrary{matrix,  positioning, patterns, backgrounds}
\tikzset{
    every matrix/.append style={
        matrix of math nodes,
        nodes in empty cells,
        inner sep=3pt,
        outer sep=0pt,
        column sep=-\pgflinewidth,
        row sep=-\pgflinewidth,
        },
    mylargenode/.style={
        text centered,
        text width=30pt,
        text height=20pt,
        text depth=10pt,
    },
    mylongnode/.style={
        text centered,
        text width=20pt,
        text height=40pt,
        text depth=30pt,
    },
    mysmallnode/.style={
        text centered,
        text width=20pt,
        text height=20pt,
        text depth=10pt,
    },
    mylonglargenode/.style={
        text centered,
        text width=30pt,
        text height=40pt,
        text depth=30pt,
    },
}

\allowdisplaybreaks


\def\ncfigskip{\hskip 1.08truein}
\def\sa{\vskip .125truein}
\def\ses{\ = \ }
\def\ds{\displaystyle}
\def\repatop#1#2{{\genfrac{}{}{0pt}{}{#1}{#2}}}
\def\allowhooks{tunnel hooks}
\def\allowhook{tunnel hook}
\def\allowhookfilling{tunnel hook covering}
\def\THC{tunnel hook covering}
\def\allowhookfillings{tunnel hook coverings}
\def\allowcell{tunnel cell}
\def\allowcells{tunnel cells}
\def\Allowhooks{Tunnel hooks}
\def\Allowcells{Tunnel cells}
\def\borderhooks{boundary hooks}
\def\bordercells{boundary cells}
\def\borderhook{boundary hook}
\def\bordercell{boundary cell}
\def\border{boundary}
\def\TunnelCells{Tunnel Cells}
\def\THF{THC}
\def\THCc{content}
%It would be really easy to make this THC!  
% \def\THC{THC}
\def\GBPR{GBPR}
\def\BGPR{\GBPR}
\def\tunnelhooks{\allowhooks}
\def\T{T}
\def\S{S}
\def\P{P}
\def\eps{\epsilon}

\renewcommand{\models}{\vDash}

\def\mur{\mu}%originally \mu^{(r)}
\def\murmin{\mu}%originally \mu^{(r-1)}
\def\mufive{\mu}%originally \mu^{(5)}
\def\muiplus{\mu}%originally \mu^{(i+1)}
\def\mui{\mu}%originally \mu^{(i)}

\def\trian{\diamond}

\def\h{\mathfrak{h}}
\def\B{\mathfrak{b}}
\def\r{\mathfrak{r}}
\def\f{\mathfrak{f}}
\def\H{\mathfrak{H}}
\def\Z{\mathbb{Z}}
\def\c{\tau}
\def\n{\xi}
%\def\KM{\mathfrak{K}}
\def\K{\mathbf{K}}
\def\HS{H}
\def\tc{\c_r}
\def\td{t}
\def\ws{k}
\def\ri{r}
\def\j{q}
\def\p{p}

\def\t{\mathfrak{t}}
%\newtheorem{Theorem}[thm]{Theorem}
\newtheorem{thm}{Theorem}
%\newtheorem{Definition}{thm}{Definition}
% \newtheorem{ex}[thm]{Example}
\newtheorem{Note}[thm]{Note}
%\newtheorem{defn}[def]{Definition}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{proc}[thm]{Procedure}
\newtheorem{conj}[thm]{Conjecture}

\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}
\newtheorem{ex}[thm]{Example}
\newtheorem{remark}[thm]{Remark}
\newtheorem{ill}[thm]{Illustration}
%\newtheorem{ex}{Example}[Theorem]
%\usepackage{xcolor}
\newtheorem{alg}[thm]{Algorithm}
\numberwithin{thm}{section}

%\definecolor{lightblue}{rgb}{.678, .847,.902}
\definecolor{lightblue}{rgb}{.85,.9,.96}
\definecolor{lightpurple}{rgb}{.9,.5,.9}
\definecolor{lightred}{rgb}{.9,.7,.7}
\definecolor{grey}{rgb}{.85,.85,.85}
\newcommand{\tcred}[1]{\textcolor{red}{#1}}

\def\sign{\epsilon}
\def\calN{\mathcal{N}}
\def\calT{\mathcal{T}}
\def\calB{\mathcal{B}}
\def\Alpha{\mathcal{A}}
\def\K{\tilde{K}}
\def\iK{\tilde{K}^{-1}}
\def\heart{\heartsuit}
\def\diamond{\diamondsuit}
\def\trip{\mathcal{T}}
\def\THCcontent{content}

%%% Section 2 pairs
\def\pairskkinv{A_{\alpha,\beta}}
\def\pairskkinvone{A_{\alpha,\alpha}}
\def\pairskkinvsym{B_{\lambda,\mu}}

%%% Section 3 pairs

\def\pairs{C_{\alpha,\beta}}
\def\pairone{C_{\alpha,\alpha}}

%%% Section 4 pairs
\def\sympairs{E_{\lambda,\mu}}
\def\sympairsbig{F_{\lambda,\mu}}



%\Yboxdimx{30pt}
% \Ylinecolour{black}
% \Ynodecolour{black!50!black}

\newcommand{\circl}[1]{\raisebox{.5pt}{\textcircled{\raisebox{-.9pt} {#1}}}}

\DeclareMathOperator{\I}{\mathfrak{S}}
\DeclareMathOperator{\dI}{\mathfrak{S}^{\star}}
\DeclareMathOperator{\Sym}{Sym}
\DeclareMathOperator{\SSYT}{SSYT}
\def\SYM{\Sym}
\DeclareMathOperator{\NSym}{NSym}
\def\NSYM{\NSym}
\DeclareMathOperator{\QSym}{QSym}
%\def\QSYM{QSym}
\DeclareMathOperator{\spin}{bank}
\def\munu{\mu/\nu}
\DeclareMathOperator{\munuhat}{\mu/\nu^{(r-1)}}
\DeclareMathOperator{\munurplus}{\mu/\nu^{(r)}}
\DeclareMathOperator{\SHF}{THC}
%\DeclareMathOperator{\THC}{THC}
\DeclareMathOperator{\taxi}{taxi}
\DeclareMathOperator{\aug}{aug}
\DeclareMathOperator{\fl}{flat}
\DeclareMathOperator{\ndet}{\mathfrak{det}}
\DeclareMathOperator{\tr}{tr}
\DeclareMathOperator{\Ri}{\mathcal{R}}
\DeclareMathOperator{\sh}{sh}
\def\P{\mathcal{P}}
\DeclareMathOperator{\diamon}{\mathcal{C}_?}
\DeclareMathSymbol{\shortminus}{\mathbin}{AMSa}{"39}
\DeclareMathOperator{\DES}{DES}
\DeclareMathOperator{\ASC}{ASC}
\DeclareMathOperator{\down}{down}
\DeclareMathOperator{\sgn}{sgn}
\DeclareMathOperator{\dec}{dec}
\DeclareMathOperator{\perm}{perm}
%\DeclareMathOperator{\THCcontent}{content}
%Declared math operators must be used in math mode--Kyle
%Then this should be a \def
\DeclareMathOperator{\thc}{THC}

\usepackage{lipsum}

%% define your title in the usual way
\title[NSym inverse Kostka identity]{A new proof of an inverse Kostka matrix problem posed by E\u{g}ecio\u{g}lu and Remmel and related identities in Sym and NSym}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
%% for more than 3 names, use the Oxford comma: One Author, Two Author, Red Author, \and Blue Author
%\author{\texorpdfstring{Kyle Celano}{Kyle Celano}}
% \address{Dept. of Mathematics, Wake Forest University, Winston-Salem, NC 27109}
% \curraddr{}
% \email{celanok@wfu.edu}
% \thanks{}


\author{\texorpdfstring{Edward E. Allen\thanks{\href{mailto:allene@wfu.edu}{allene@wfu.edu}.}\addressmark{1}, Kyle Celano\thanks{\href{mailto:celanok@wfu.edu}{celanok@wfu.edu}.}\addressmark{1}, \and Sarah K. Mason\thanks{\href{mailto:masonsk@wfu.edu}{masonsk@wfu.edu}. Sarah K. Mason was partially supported by an AMS-Simons PUI grant.}\addressmark{1}}{Edward E. Allen, Kyle Celano, and Sarah K. Mason}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}{Dept. of Mathematics, Wake Forest University, Winston-Salem, NC 27109 }}

%% 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{
E\u{g}ecio\u{g}lu and Remmel provide a combinatorial proof (using special rim hook tableaux) that the Kostka matrix times its inverse equals the identity matrix and pose the problem of proving the reverse identity (that the inverse Kostka matrix times the Kostka matrix equals the identity) combinatorially. Sagan and Lee prove a special case of this identity using overlapping special rim hook tableaux. Loehr and Mendes provide a full proof using bijective matrix algebra that relies on the E\u{g}ecio\u{g}lu--Remmel map.  In this extended abstract, we solve the problem in full generality independent of the E\u{g}ecio\u{g}lu--Remmel bijection.  To do this, we start by proving NSym versions of both Kostka matrix identities using the tunnel hook coverings recently introduced by the first and third authors.  Then we modify our sign-reversing involutions to reduce to Sym.
}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Kostka matrix, immaculate functions, sign-reversing involutions}

%% 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, giveninits]{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{Background and Introduction}

The complete homogeneous functions $\{ h_{\lambda} \}_{\lambda \vdash n}$ and Schur functions $\{s_{\lambda}\}_{\lambda \vdash n}$ (where $\lambda \vdash n$ means $\lambda$ is a partition of $n$) are bases for the vector space $\Sym$ of symmetric functions.  The Kostka matrix $K$ is the transition matrix from $h$ to $s$ whose entries $K_{\lambda,\mu}$ count the number of semistandard Young tableaux of shape $\lambda$ and content $\mu$.  The inverse Kostka matrix $K^{-1}$ is the transition matrix from $s$ to $h$ whose coefficients are computed via the Jacobi--Trudi formula $s_{\lambda}=\det(h_{\lambda_i-i+j})$~\cite{Mac95}.  E\u{g}ecio\u{g}lu and Remmel~\cite{EgeRem90} interpret these coefficients as \emph{special rim hook tableaux} and use this to prove the identity $K K^{-1}=I$ combinatorially, leaving the combinatorial proof of $K^{-1}K=I$ as an open problem.

\begin{thm}[\cite{EgeRem90}]\label{ERthm}
If $\delta_{\lambda,\mu}$ is the Kronecker delta, then $\sum_{\nu} K_{\lambda,\nu} K^{-1}_{\nu,\mu} = \delta_{\lambda,\mu}$.

\end{thm}

Our first main result is the generalization of \Cref{ERthm} to the vector space $\NSym$ of \emph{noncommutative symmetric functions}.  Here $\K$ is the transition matrix from \emph{complete homogeneous noncommutative symmetric functions}~\cite{GKLLRT95} to \emph{immaculate functions}~\cite{BBSSZ14}.

\begin{thm}\label{Th:One}
Let $\alpha, \beta,$ and $\gamma$ be compositions of $n$.  Let $\K_{\alpha,\gamma}$ be the number of \emph{immaculate tableaux} of shape $\alpha$ and content $\gamma$ and let $\iK_{\gamma,\beta}$ be the number of \emph{tunnel hook coverings} of \THCc\ $\gamma$ and shape $\beta$.  Then $\sum_{\gamma} \K_{\alpha,\gamma} \iK_{\gamma,\beta}= \delta_{\alpha, \beta}.$
\end{thm}

Sagan and Lee~\cite{SagLee03} prove the last column (indexed by $(1^n)$) of the identity $K^{-1}K=I$, i.e., $\sum_\nu K^{-1}_{\lambda,\nu} K^{\textcolor{white}{-1}}_{\nu,(1^n)} = \delta_{\lambda,(1^n)}$. 
Loehr and Mendes~\cite{LoeMen06} use bijective matrix algebra to convert the E\u{g}ecio\u{g}lu--Remmel map into a proof of the $K^{-1}K=I$ identity.  Our combinatorial proof of $K^{-1}K=I$ begins with a proof of the $\NSym$ version which we then algorithmically reduce to $\Sym$.

%We provide a combinatorial proof of $K^{-1}K=I$ independent of the E\u{g}ecio\u{g}lu--Remmel map by first proving the $\NSym$ version and then algorithmically reducing our results to $\Sym$.

\begin{thm}\label{Th:Two}
Under the same hypotheses as in \Cref{Th:One}, we have $\sum_\gamma \iK_{\alpha,\gamma} \K_{\gamma,\beta}= \delta_{\alpha, \beta}.$
\end{thm}

We next modify our sign-reversing involution so that it applies to pairs consisting of tunnel hook coverings and semistandard Young tableaux.  This provides a solution to the problem posed by E\u{g}ecio\u{g}lu and Remmel~\cite{EgeRem90} in full generality without relying on the E\u{g}ecio\u{g}lu--Remmel map.

\begin{thm}\label{Th:Three}
If $\delta_{\lambda,\mu}$ is the Kronecker delta, then $\sum_\nu K^{-1}_{\lambda,\nu} K_{\nu,\mu} = \delta_{\lambda,\mu}.$
\end{thm}

In this extended abstract, Ferrers diagrams of partitions are written in English notation with $(i,j)$ designating the cell in the $i$th row from the top and $j$th column from the left.  Let $\ell(\alpha)$ denote the length of a composition $\alpha$.  Permutations are written in one-line notation; that is, for $\sigma \in S_n$, if $\sigma(i)=\sigma_i$ then we write $\sigma=[\sigma_1,\sigma_2,\ldots,\sigma_n]$.
Transpositions, on the other hand,
are represented by $s_i=(i,i+1)\in S_n$.
We multiply permutations from right to left so that $\sigma\tau=[\sigma_{\tau_1}, \sigma_{\tau_2},\ldots,\sigma_{\tau_n}]$ where $\tau=[\tau_1,\ldots,\tau_n] \in S_n$.

\subsection{Immaculate functions and NSym Kostka matrices} 
$NSym$ is the algebra generated by the noncommutative elements
$\{ H_i \}_{i \in \mathbb{Z}_{\geq 0}}$.
The $H_i$ can be thought of as the noncommutative analogues
of the complete homogeneous functions $h_i$ in $\Sym.$
Similar to Schur functions, we can define the \emph{immaculate functions} 
in terms of a Jacobi--Trudi-like determinant as
$\mathfrak{S}_\alpha=\mathfrak{det}(H_{\alpha_i-i+j})$, where $\alpha\vDash n$ (meaning $\alpha$ is a composition of $n$) and $\mathfrak{det}()$
is the noncommutative Laplace expansion of the determinant 
from row 1 through row $\ell.$ Immaculate functions were first defined in of \cite{BBSSZ14} in terms of \textit{noncommutative Berenstein operators} 
% \kyle{Is there some other way of saying ``BBSSZ used a different but equivalent definition''?}
with the Jacobi--Trudi-like identity following \cite[Theorem 3.27]{BBSSZ14}. Similar to the $\Sym$ case, we can define the $\NSym$ Kostka matrix
$\tilde K_{\alpha,\beta}$ for compositions $\alpha$ and $\beta$ by
$H_\beta=\sum_{\alpha} \tilde K_{\alpha,\beta} \mathfrak{S}_\alpha$.


\begin{defn}[{\cite[Definition 3.9]{BBSSZ14}}]
Let 
%$\alpha$ and $\beta$ be compositions of a fixed positive integer $n$. 
$\alpha,\beta \vDash n$.
An \emph{immaculate tableau} of \emph{shape} $\alpha$ and \emph{content} $\beta$ is a labeling of the boxes of the diagram of
shape 
$\alpha$ by positive integers in such a way that 
%\begin{itemize}
    %\item 
    the number of boxes labeled by $i$ is $\beta_i$,
    %\item 
    the sequence of entries in each row, from left to right, is weakly increasing, and
    %\item 
    the sequence of entries in the first column, from top to bottom, is strictly increasing.
%\end{itemize}
Let $IT_{\alpha,\beta}$ denote the set of immaculate tableaux of shape $\alpha$ and content~$\beta$.
\end{defn}

\begin{thm}[{\cite{BBSSZ14}}]
    For compositions $\alpha,\beta$, we have $\K_{\alpha,\beta}=|IT_{\alpha,\beta}|$.
\end{thm}



\subsection{Tunnel hook coverings}

A GBPR diagram \cite{AM23} is a generalization of a Ferrers diagram where
the cells are colored grey, blue, purple, or red.  Let $\mu=(\mu_1,\mu_2,\ldots,\mu_\ell)$ be an integer sequence and let $\nu=(\nu_1,\nu_2,\ldots,\nu_\ell)$ be a weak composition.  A GBPR diagram $D_{\mu/\nu}$ of shape $\mu/\nu$ is constructed as follows.

\begin{enumerate}
\item For $1 \le i \le \ell$, place $\nu_i$ grey cells in row $i$. 

%\item For each $1 \le i \le \ell$, place red and blue cells into row $i$ by the following:
\begin{enumerate}
\item If $\mu_i >0$ and $\nu_i \le \mu_i,$ place $\mu_i-\nu_i$ blue cells in row $i$ situated immediately to the right of the grey cells. 

\item If $\mu_i>0$ and $\mu_i < \nu_i,$ place $\nu_i-\mu_i$ red cells in row $i$ situated immediately to the right of the grey cells.

\item If $\mu_i \le 0,$ place $|\mu_i|+\nu_i$ red cells  in row $i$ situated immediately to the right of the grey cells.
\end{enumerate}

\item Any cell that is not colored grey, red, or blue is purple. 
\end{enumerate}

Boundary cells are blue, purple, or red cells
in the GBPR diagram
that are vertically, horizontally, or diagonally adjacent to grey cells.  A \emph{tunnel hook} $\h(j,\c_j)$ starting in row $j$ and ending in terminal cell $\c_j=(p_j,q_j)$
includes all blue and red cells in row $j$, one purple cell in row $j$ if there are no blue or red cells in row $j$, and
all of the boundary cells in rows $j+1 \le i \le p_j.$ The \emph{sign} of $\h(j,\c_j)$ is $\sgn(\h(j,\c_j))=(-1)^{p_j-j}$.
A {\emph \allowhookfilling~($\SHF$)} of the GBPR diagram $D_{\mu/\nu^{(0)}}$, where $\nu^{(0)}=(0,0,\hdots)$,
is constructed using the following procedure.

\begin{proc}[\cite{AM23}]\label{A:THC} 
Consider a sequence $\mu=(\mu_1, \mu_2, \hdots , \mu_\ell) \in \mathbb{Z}^\ell$ and a partition $\nu^{(0)}=(\nu_1, \nu_2 , \hdots , \nu_\ell)$ 
in which $\nu_i=0$ for $1 \le i \le \ell$.  Start with the diagram $\mathcal{D}_{\mu/\nu^{(0)}}$
and repeat the following steps, once for each value of $r$ from $1$ to $\ell$.
\begin{enumerate}

\item 
Choose a \allowhook~$\h(r,\c_r)$ in $D_{\mu/\nu^{(r-1)}}$.  Set 
$
%$$
\Delta_r=\Delta(\h(r,\c_r))=|\h(r,\c_r)|-2 \rho_r - \psi_r
$
%$$
where $\rho_r$ and $\psi_r$ are the number
of red cells and purple cells, respectively, in row $r$
that are included in $h(r,\c_r).$

\item{\label{St:grey}} For each $1 \le i \le \ell$, let $\eta_i^{(r)}$ be the number of cells in row $i$ of $\h(r,\c_r)$ and let $\nu^{(r)}$ be the sequence defined for $1 \le i \le \ell$ by
%$$
$\nu_{i}^{(r)}=\nu_{i}^{(r-1)}+\eta_{i}^{(r)}.$
%$$

\item{\label{St:gbpr}} Construct the \GBPR~diagram $D_{\mu/\nu^{(r)}}$. 

\end{enumerate}
Let $T=\bigl(\h(1,\c_1), \h(2,\c_2), \ldots, \h(\ell,\c_\ell)\bigr)$ be the resulting THC and set
$\Delta(T) = (\Delta_1, \hdots , \Delta_\ell)$. 
%\end{enumerate}
\end{proc}
\noindent
If $\fl(\alpha)$ is the sequence obtained by removing the zeros for an integer sequence $\alpha=(\alpha_1,\alpha_2,\ldots,\alpha_\ell)$, we call $\fl(\Delta(T))$ the \emph{\THCc} of $T$.  For a tunnel hook covering $T=\bigl(\h(1,\c_1), \h(2,\c_2), \ldots, \h(\ell,\c_\ell)\bigr)$, define the \textit{sign} of $T$ to be
%\[
$\sgn(T)=\prod_{i=1}^\ell \sgn(\h(i,\c_i))$
%\]
%For an example of a \THC, please see \Cref{fig:SRT permutation}.
For integer sequences $\alpha$ and $\beta$, let $\thc_{\alpha,\beta}$ be the set of tunnel hook coverings of \THCc{} $\alpha$ and shape $\beta$.
\begin{thm}[\cite{AM23}]
For compositions $\alpha,\beta$ of a positive integer $n$, we have
\[
\iK_{\alpha,\beta}=\sum_{T\in \thc_{\alpha,\beta}}\sgn(T)
\]
\end{thm}


 An important ingredient in the proof of the above theorem is the association of a unique permutation to each \THC{}~of a diagram.
 First,  the \emph{$d^{th}$ diagonal} $\mathcal{L}_d$
 of a GBPR diagram of shape $\alpha$
 is the set of all cells of the form $(d+k,1+k)$ for some $k \in \Z^{\ge 0}$; that is,  $\mathcal{L}_d=\{(d+k,1+k)\mid k\in \Z^{\ge 0}\}$. 
 %\begin{defn}
      For a \THC{} $T=\bigl(\h(1,\c_1), \h(2,\c_2), \ldots, \h(\ell,\c_\ell)\bigr)$, its \textit{permutation} $\sigma\in S_\ell$, denoted $\perm(T)$, is given by setting $\sigma(i)=j$ if $\c_i\in \mathcal{L}_j$
      for each $i\in [\ell].$ See \Cref{fig:SRT permutation} for an example.
 %\end{defn}

\begin{thm}[\cite{AM23}]\label{Th:THC_and_Perms}
For each composition $\alpha$, the map $T\mapsto \perm(T)$ is a bijection from tunnel hook coverings of shape $\alpha$ to permutations of $\ell(\alpha)$ such that $\sgn(T)=\sgn(\perm(T))$. 
\end{thm}
We use the permutation of a \THC{} to construct the sign-reversing involutions necessary to prove $K\iK=\iK K=I$ combinatorially.
We need the following two lemmas. Recall that for compositions $\alpha$ and $\beta$ of $n$, we say $\alpha$ \emph{dominates} $\beta$, denoted $\alpha\trianglerighteq \beta$, if $\alpha_1+\cdots+\alpha_i\geq \beta_1+\cdots+\beta_i$ for all $i\in [n]$, where we pad the ends of compositions with zeros as necessary to make the comparisons. 
\begin{lem}[Dominance Lemma for IT {\cite{BBSSZ14}}]\label{lem:dom-lem-IT}
    For $\alpha,\beta\vDash n$, if $\alpha \triangleleft \beta$, then $IT_{\alpha,\beta}=\emptyset$. Moreover, if $\alpha=\beta$, then $|IT_{\alpha,\beta}|=1.$
\end{lem}
\begin{lem}[Dominance Lemma for THC]\label{lem:dom-lem-thc}
    For $\alpha,\beta\vDash n$, if $\alpha \triangleleft \beta$, then $\thc_{\alpha,\beta}=\emptyset$ Moreover, if $\alpha=\beta$, then $\thc_{\alpha,\beta}$ has 1 element and it is of positive sign.
\end{lem}
%\begin{remark}
%   $\thc_{\alpha,\beta}=\emptyset$  is a stronger statement than $\iK_{\alpha,\beta}=0$ since the latter is merely a signed sum of the former.
%\end{remark}
\begin{figure}
   \centering
$T$\ \  $=$\ \ \begin{minipage}{.3\textwidth}
    
\begin{tikzpicture}[yscale=-1,scale=.5]

% L is your composition/partition
\def\L{{8, 7, 7, 4}}
\pgfmathsetmacro{\len}{dim(\L)}

\foreach \y in {1,...,\len}{
   \pgfmathsetmacro{\j}{\L[\y-1]}
   \foreach \i in {1,...,\j}{
      \draw (\i-.5,\y-.5) rectangle (\i+.5,\y+.5);
       }
}

% Define initial and terminal nodes of tunnel hooks. 
\tikzset{every node/.style={inner sep=-4pt,color=blue}}
\node (1i) at (8,1) {1};
\node (2i) at (7,2) {2};
\node (3i) at (7,3) {3};
\node (4i) at (4,4) {4};
% \node (5i) at (4,5) {5};
% \node (6i) at (4,6) {6};
% \node (7i) at (2,7) {7};

\tikzset{every node/.style={inner sep=-4pt,color=red}}
\node (1t) at (1,1) {1};
\node (2t) at (1,3) {3};
\node (3t) at (1,4) {4};
\node (4t) at (3,4) {};
\node at (3+.25,4-.25) { 2};
% \node (5t) at (1,9) {9};
% \node (6t) at (2,6) {};
% \node at (2+.25,6-.25) {5};
% \node (7t) at (2,9) {};
% \node at (2+.25,9-.25) {8};
% Draw hooks. You have to manually find the points.
\begin{scope}[on background layer]
\tikzset{every path/.style={line width = 7pt,color=black,line cap=round,opacity=.15,rounded corners}}
\draw (1i)--(1t);
\draw (2i)--(1,2)--(2t);
\draw (3i)--(2,3)--(2,4)--(3t);
\draw (4i)--(4t);
% \draw (5i)--(1,5)--(5t);
% \draw (6i)--(6t);
% \draw (7i)--(7t);
\end{scope}
% Additional lines. 
\tikzset{every path/.style={line width=.5pt,color=red}}
% \draw (1-.5,1-.5)--( $(1t) + (.5,.5)$ );
 \draw (1-.5,2-.5)--($(4t)+(.5,.5)$);
 %\draw (1-.5,3-.5)--($(2t)+(.5,.5)$);
% \draw (1-.5,4-.5)--($(2t)+(.5,.5)$);
\end{tikzpicture}\end{minipage} 
\(\displaystyle \perm(T)=\binom{\textcolor{blue}{1\ 2\ 3\ 4}}{\textcolor{red}{1\ 3\ 4\ 2}}\)
   \caption{The permutation (in 2-line notation) associated to a tunnel hook covering.}
   \label{fig:SRT permutation}
\end{figure}
\section{A combinatorial proof of Theorem 1.1}\label{section:k-k-inv}

In this section, we provide a combinatorial proof that $\K\iK=I$. For compositions $\alpha,\beta$ of $n$, we have
\[(\K\iK)_{\alpha\beta}=\sum_{\gamma\vDash n}\K_{\alpha,\gamma}\iK_{\gamma,\beta}=\sum_{(S,T)\in \pairskkinv}\sgn(T)\]
where $\pairskkinv$ is the set of pairs $(S,T)$ such that
%\begin{itemize}
    %\item 
    $\S$ is an immaculate tableau of shape $\alpha$,
    %\item 
    $\T$ is a \THC{} of shape $\beta$, and
    %\item 
    the content of $\S$ is identical to the \THCc{} of~$\T$.
%\end{itemize}
To prove the matrix identity $\K \iK=I$ combinatorially, we generalize the approach from the $\Sym$ case~\cite{EgeRem90}.  Specifically, we prove the following.
\begin{enumerate}
    \item  If $\alpha\neq \beta,$ there is a sign-reversing involution $\phi_{\alpha,\beta}$ on $\pairskkinv$.
    \item If $\alpha=\beta$,  $\pairskkinvone$ contains exactly one pair $(S,T)$, and $\sgn(T)=1.$
\end{enumerate}

We start with the latter.
\begin{lem}\label{lem:diag-pairs-k-kinv-1}
    For any composition $\alpha$, $\pairskkinvone$ contains exactly one pair $(S,T)$, and for this pair $(S,T)$, we have $\perm(T)=id$.
\end{lem}

For $\alpha\neq \beta$, we construct the sign-reversing involution recursively.
\begin{alg}\label{alg:KKinverse-row-labeling}
    Suppose $\alpha$ and $\beta$ are distinct 
    compositions of $n$ and let $(S,T)\in \pairskkinv$ of say mutual content $\gamma=(\gamma_1,\dots,\gamma_\ell)$. We construct another pair $\phi_{\alpha,\beta}(S,T)=(U,V)\in \pairskkinv$. Let $S^1$ denote the first row of $S$ and set $\sigma=\perm(T).$
    \begin{enumerate}
        \item Pick $\j$ such that $\j$ appears in $S^1$ and $\sigma(\j)\geq \sigma(k)$ for all $k \in S^1$.
        \item Suppose $\sigma(\j)=1$.  Then $\j$ is the only entry in $S^1$ and therefore $\j=1$.
        \begin{enumerate}
            \item Remove $S^1$ from $S$ and decrease all other entries in $S$ by 1 to make an immaculate tableau $\overline{S}$ with content $\overline{\gamma}=(\gamma_2,\dots,\gamma_{\ell})$ and shape $\overline{\alpha}=(\alpha_2,\dots,\alpha_\ell)$. Remove the tunnel hook starting in row 1 of $T$ to make a \THC{} $\overline{T}$ of content $\overline{\gamma}$ and shape $\overline{\beta}=(\beta_2,\dots,\beta_\ell)$. \item Apply the map $\phi_{\overline{\alpha},\overline{\beta}}$ on $(\overline{S},\overline{T})$ to produce $(\overline{U},\overline{V})$. 
            \item Increase all entries of $\overline{U}$ by 1 and append $S^1$ to make $U$. Append the first row of $T$ to the top of $\overline{V}$ to make $V$.
        \end{enumerate} 
        \item Suppose $\sigma(\j)>1$. 
        \begin{enumerate}
            \item Let $V$ be the unique \THC{} of shape $\beta$ with $\perm(V)=s_{\sigma(\j)-1}\sigma$.
             \item Let $U$ be obtained by turning a $\j$ in $S^1$ into $\p=\sigma^{-1}(\sigma(\j)-1)$ and then sorting the first row weakly increasingly.
        \end{enumerate}
    \end{enumerate}
\end{alg}

See \Cref{fig:KKinverse-example} for an example.

\begin{thm}
    Let $\alpha,\beta\vDash n$ have length $\ell$. Given a pair $(S,T)\in \pairskkinv$, \Cref{alg:KKinverse-row-labeling} is a sign-reversing involution.  Moreover, let $\phi_{\alpha,\beta}(S,T) = (U,V)$.  If $\p$ and $\j$ are chosen as in the description of \Cref{alg:KKinverse-row-labeling}, we have
    \[\Delta_k(V)=\begin{cases}
    \Delta_{\p}(T)+1&k=\p\\
    \Delta_{\j}(T)-1&k=\j\\
    \Delta_k(T)&k\not\in \{\p,\j\},
    \end{cases}\]  for all $1 \le k \le \ell$.
%\end{enumerate}
\end{thm}
\begin{proof}[\textit{Proof (Sketch).}] 
Let $(S,T)\in \pairskkinv$, let $S^1$ be the first row of $S$, and set $\sigma=\perm(T)$.  First verify the validity of the recursive step by assuming $\sigma(\j)=1$ and proving $\j=1$ and every entry in $S^1$ is $1$.  Then removing this first row and applying the algorithm to the resulting pair produces the desired result.  

Next verify the nonrecursive step by supposing $\sigma(\j)>1$ and noting that $s_{\sigma(\j)-1}\sigma$ is indeed a permutation with opposite sign as $\sigma$.  Since the size $\Delta_{k}$(T) of the tunnel hook starting in row $k$ of $T$ is $\beta_k-k+\sigma_k$ for each $k$, if $\p=\sigma^{-1}(\sigma(\j)-1)$, then
\[\Delta_{\j}(V)=\beta_{\j}-{\j}+\perm(V)_{\j}=\beta_{\j}-{\j}+\perm(T)_{\j}-1=\Delta_{\j}(T)-1,\]
\[\Delta_{\p}(V)=\beta_{\p}-\p+\perm(V)_{\p}=\beta_{\p}-\p+\perm(T)_{\p}+1= \Delta_{\p}(T)+1.\]

Since no other entries in the permutation are altered by applying the transposition $s_{\sigma(q)-1}$, we have $\Delta_k(V)=\Delta_k(T)$ for all $k \not= \p,\j$, as desired.

For $U$, observe that there are at least two distinct numbers in $S^1$ and that there is an occurrence of $\j$ in $S^1$ that is not the first element of $S^1$.  Hence, the entries in the leftmost column of $U$ must strictly increase since they will equal those in the leftmost column of $S$.  Therefore $U$ is an immaculate tableau.
\end{proof}

\begin{figure}
    \centering
    $\begin{minipage}{.45\textwidth}\begin{tikzpicture}
            
        \node at (0,-.2) {\ytableaushort{11111{\tcred{4}}4,222234,\none\none\none{\none[S]}}};
        \node at (3.5,0) {\begin{tikzpicture}[yscale=-1,scale=.5]
% L is your composition/partition
\def\L{{5,2,1,5}}
\pgfmathsetmacro{\len}{dim(\L)}

\foreach \y in {1,...,\len}{
    \pgfmathsetmacro{\j}{\L[\y-1]}
    \foreach \i in {1,...,\j}{
        \draw (\i-.5,\y-.5) rectangle (\i+.5,\y+.5);
        }
}
% \draw[fill=red,opacity=.5] (4-.5,4-.5) rectangle (5+.5,4+.5);
\node at (5,1) {1};
\node at (2,2) {};
\node at (1,3) {};
\node at (1,1) {1};
\node at (5,4) {$4$};
\node at (3,4) {\tcred{2}};
\node at (3,5) {$T$};
\begin{scope}[on background layer]
\tikzset{every path/.style={line width = 7pt,color=black,line cap=round,opacity=.25,rounded corners}}
\draw (5,1)--(1,1);
\draw (2,2)--(1,2)--(1,4);
\draw (2,3)--(2,4);
\draw (5,4)--(3,4);
\end{scope}

\end{tikzpicture}};\end{tikzpicture}\vspace{-4mm}\[\perm(T)=[1,4,3,\tcred{2}]\]\end{minipage}\xrightarrow[]{\quad} \begin{minipage}{.45\textwidth}\begin{tikzpicture}
    
\node at (0,-.24) {$\ytableaushort{11111{\tcred{1}}4,222234,\none\none\none{\none[U]}}$};
\node at (3.5,0) {\begin{tikzpicture}[yscale=-1,scale=.5]
% L is your composition/partition
\def\L{{5,2,1,5}}
\pgfmathsetmacro{\len}{dim(\L)}

\foreach \y in {1,...,\len}{
    \pgfmathsetmacro{\j}{\L[\y-1]}
    \foreach \i in {1,...,\j}{
        \draw (\i-.5,\y-.5) rectangle (\i+.5,\y+.5);
        }
}
% \draw[fill=red,opacity=.5] (4-.5,4-.5) rectangle (5+.5,4+.5);
\node at (5,1) {$1$};
\node at (1,2) {\tcred{2}};
\node at (2,2) {};
\node at (1,3) {};
\node at (5,4) {$4$};
\node at (4,4) {1};
\node at (3,5) {$V$};
\begin{scope}[on background layer]
\tikzset{every path/.style={line width = 7pt,color=black,line cap=round,opacity=.25,rounded corners}}
\draw (5,1)--(1,1)--(1,2);
\draw (2,2)--(2,3)--(1,3)--(1,4);
\draw (3,3)--(3,4)--(2,4);
\draw (5,4)--(4,4);
\end{scope}

\end{tikzpicture}};\end{tikzpicture}\vspace{-4mm}\[\perm(V)=[\tcred{2},4,3,1]\]
\end{minipage}
$
    \caption{An example of \Cref{alg:KKinverse-row-labeling}. Here $q=4$. }
    \label{fig:KKinverse-example}

\end{figure}

We use \Cref{alg:KKinverse-row-labeling} to provide a new combinatorial proof of the classical Kostka matrix identity $KK^{-1}=I$. 
 From \cite{AM23}, for each $\lambda,\mu\vdash n$ we have
\begin{equation}\label{eq:kostka-in-terms-thc}K^{-1}_{\lambda,\mu}=\sum_{\substack{\alpha\vDash n\\\dec(\alpha)=\lambda}}\sum_{T\in \thc_{\alpha,\mu}}\sgn(T),\end{equation}
where $\dec(\alpha)$ is the partition obtained by writing the composition $\alpha$ in weakly decreasing order. Let $\pairskkinvsym$ be the set of pairs $(S,T)$ where $S$ is a semistandard Young tableau of shape $\lambda$ and 
%\begin{itemize}
    %\item 
    $T$ is a \THC{} of shape $\mu$ and \THCc{} $\alpha$ such that $\dec(\alpha)$ is the content of $S$.
%\end{itemize} 
Then for $\lambda\neq \mu$, we define a map $\chi_{\lambda,\mu}:\pairskkinvsym\to \pairskkinvsym$ exactly the same as in \Cref{alg:KKinverse-row-labeling}, except we replace Step (3b) by the procedure described in \cite[p.\ 71]{EgeRem90} to produce a semistandard Young tableau of the desired type. 
\begin{thm}
    For all $\lambda,\mu\vdash n$ such that $\lambda\neq \mu$, $\chi_{\lambda,\mu}$ is a sign-reversing involution.
\end{thm}

Therefore, our combinatorial proof of $\K \iK=I$ reduces to a new combinatorial proof of $K K^{-1}=I$ in the $\Sym$ case, different from the one found by E\~{g}ecio\~{g}lu and Remmel~\cite{EgeRem90}.

\section{A combinatorial proof of \texorpdfstring{\Cref{Th:Two}}{Theorem Two}}
\label{section:k-inv-k}

The goal of this section is to prove that $(\iK \K)_{\alpha,\beta}=\delta_{\alpha,\beta}$ for all compositions $\alpha,\beta$ of $n$. The combinatorial interpretations of these matrices imply that
\begin{equation}\label{Eq:KinvK}(\iK \K)_{\alpha,\beta}=\sum_{\gamma\vDash n}\iK_{\alpha,\gamma}\K_{\gamma,\beta}=\sum_{(T,S)\in \pairs}\sgn(T),
\end{equation}
where $\pairs$ is the set of pairs $(T,S)$ such that
%\begin{itemize}
%    \item 
    $\T$ is a 
    THC with content $\alpha$,
 %   \item 
    $\S$ is a immaculate tableau of content $\beta$, and
%    \item 
$sh(\S)=sh(T)$.  We prove the following.
\begin{enumerate}\item 
If $\alpha\neq \beta,$ there is a sign-reversing involution $\psi_{\alpha,\beta}$ on $\pairs$.
\item If $\alpha=\beta$, then $\pairs$ contains exactly one pair $(T,S)$.  Moreover, $\sgn(T)=1$.
\end{enumerate}
We start with the latter point.  This is the same as \Cref{lem:diag-pairs-k-kinv-1} \textit{mutatis mutandis}.
\begin{lem}
For any composition $\alpha$, $\pairone$ contains exactly one pair $(T,S)$ and for this pair, we have $\perm(T)=id$.
\end{lem}
%    For any composition $\alpha$, $\pairskkinvone$ contains exactly one pair $(S,T)$, and for this pair $(S,T)$, we have $\perm(T)=id$.
% \kyle{This does not look exactly like \Cref{lem:diag-pairs-k-kinv-1}. If we make it look like that, we can remove the definition of ``superstandard''.}


%\begin{Note}\kyle{Should the note environment be italicized? I feel that this is closer to a remark.}
%Fix $n$ to be a positive integer greater than $1$ and 

% Moreover, \Cref{lem:dom-lem-IT} implies that the superstandard tableau of shape $\alpha$ cannot appear in $\pairs$ unless $\alpha=\beta$.

%Let $\alpha=(\alpha_1,\ldots,\alpha_{\ell})$ be a composition of $n$. Each \THC{} $T$ of a GBPR diagram of shape $\alpha$ corresponds to a permutation $\perm(T)\in S_{\ell(\alpha)}$ (\Cref{Th:THC_and_Perms}).  
%We can extend this permutation to $S_n$ by setting $\sigma_i=i$ for $\ell(\alpha)<i \le n$.
%\label{Note:Extending}
%\end{Note}

Assume $\alpha \not= \beta$.  We describe a sign-reversing involution $\psi_{\alpha,\beta}$ on $D_{\alpha,\beta}$ recursively.  In the following, let $\sigma=\perm(T)$ be the permutation associated to $T$ (\Cref{Th:THC_and_Perms}), embedded into $S_n$ by setting $\sigma_i=i$ for $\ell(\alpha)<i \le n$.

\begin{alg}
\label{alg: involution}
Let $\alpha,\beta\vDash n$ where $n>1$ and $\alpha\neq \beta$, let $(T,S)\in \pairs$ with $\alpha \not= \beta$, and set $\sigma=\perm(T)$. We construct another pair $\psi_{\alpha,\beta}(T,S)=(V,U)\in \pairs$ as follows.
\begin{enumerate}
 \item Let $m$ be the maximum element of $S$. Let $\Ri = \{ \sigma_r | m \textrm{ appears in row } r \; \mathrm{ of } \; S \}$.  Select $r$ such that $\sigma_r$ is the minimal element of $\Ri$.
\item Suppose $\sigma_{\ri}=\ri$ and $S$ has only $m$'s in row $\ri$.  Note that this means row $r$ is the last row of $S$ and $m$ only appears in row $r$ of $S$; otherwise the row containing $m$ above row $r$ would have a lower $\sigma$ value.
   \begin{enumerate}
    \item Let $\overline{S}$ be $S$ with its final row removed. Define $\overline{\sigma}\in S_{n-1}$ by setting 
        \[\overline{\sigma}_i=\begin{cases}
            \sigma_i&i<\ri\\
            i&i \ge \ri.
        \end{cases}\]
    Let $\overline{T}$ be the tunnel hook covering whose shape is the shape of $T$ minus the final row with associated permutation $\overline{\sigma}$.   \item Set $(\overline{V},\overline{U})=\psi_{\overline{\alpha},\overline{\beta}}(\overline{T},\overline{\S})$ where $\overline{\alpha}=(\alpha_1,\dots,\alpha_{\ell(\alpha)-1})$ and $\overline{\beta}=(\beta_1,\dots,\beta_{\ell(\beta)-1})$. Let $\overline{\tau} \in S_{n-1}$ be the permutation associated to $\overline{V}$. 
    \item Define $U$ by reattaching the row of $m$'s to the end of $\overline{U}$. If $r'$ is the row of $m$'s in $U$, then define $\tau\in S_n$ by setting, for all $i\in [n]$,
        \[\tau_k=\begin{cases}
            \overline{\tau}_i&i<r'\\
            i&i \ge r'.
        \end{cases}\]
        \end{enumerate}
        \item  Suppose either $\sigma_r=r$ and the final row is not all $m$'s or $\sigma_r \not= r$.
        \begin{enumerate}
            \item Set $U(c)=S(c) $ for all cells $c$ except for the last cell of row $\ri$.  Append a cell with value $m$ to the end of row $\p=\sigma^{-1}(\j+1)$, where $\j=\sigma_r$.
            \item Let $V$ be the THC of shape $sh(U)$ with $\perm(V)=s_{\j}\sigma$.
        \end{enumerate}
        % \item Set $\psi_{\alpha,\beta}(T,S)=(V,U).$\kyle{Is this line completely necessary? We say ``We define $\psi_{\alpha,\beta}(T,S)=(V,U)$ as follows.'' Then, we describe how to get $V$ and $U$. }
\end{enumerate}
\end{alg}

% The algorithm for our involution $\psi_{\alpha,\beta}$ is algebraic, exact, and relatively easy to implement in code.
%\Ed{If we decide to keep this sentence, we probably need to move to another place.  Here is feels out of place.}
%\kyle{Maybe after the definition?}
See \Cref{ex:kinvk} for an example of this algorithm.  The properties of the output of our involution are described in the following Theorem.

\begin{thm}\label{Prop:AlgOutput}
    Assume that Algorithm \ref{alg: involution} applied to $(T,S) \in \pairs$ produces a pair $(V,U)\in \pairs$.  Let $\sigma=\perm(T)$ and $\tau=\perm(V)$.  Then
    %with $\beta=sh(U)$, we have
    \begin{enumerate}
%\item $\beta_r=\alpha_r-1, \beta_s=\alpha_s+1,$ and $\beta_i = \alpha_i$ for all $i \not= r,s$,
\item $\beta_i - i + \tau_i = \alpha_i-i + \sigma_i$ for all $1 \le i \le n$,
where $\beta=sh(U)$
and $\alpha=sh(S)$,
\item $\sgn(\tau)=-\sgn(\sigma)$, and
\item $U(c)=S(c)$ for all cells $c$ in the diagram, except for the last cell in row $r$ and in row $\p$.
\end{enumerate}
\end{thm}
It is not hard to see that $U$ is an immaculate tableau.  To prove~\Cref{Prop:AlgOutput}, we first show that $\j<n$ in Step (3) of Algorithm \ref{alg: involution} so that $\tau \in S_n.$  Then, we prove Property (1) of \Cref{Prop:AlgOutput}.  Properties (2) and (3), however, are immediate from Step (3) of the algorithm.  
% \Ed{As an idea, we could start cutting from here and continue through the proof of Proposition 3.7.  That would cut out a page but the most of the story is still here.  Perhaps we leave Proposition 3.7 but without its proof.}
We need the following Lemmas for our proof.

\begin{lem}\label{lem:one_col}
    Let $\alpha,\beta\vDash n$, $(T,S)\in \pairs$ and $\ri$ be as in \Cref{alg: involution}. If $\perm(T)_{\ri}=n$, then $sh(S)=(1^n)$ and $\beta=(1^n)$. If $(V,U)=\psi_{\alpha,\beta}(T,S)$ and $\perm(T)_r \ne n$, then $sh(U)$ is a composition of $n$.
\end{lem}
% \begin{lem}
% Let $(V,U)=\psi_{\alpha,\beta}(T,S)$ for some $\alpha,\beta\vDash n$ and $(T,S)\in \pairs$. If $\perm(T)_r \ne n$, then $sh(U)$ is a composition of $n$.
% \end{lem}

Now, we are ready to complete the proof of \Cref{Prop:AlgOutput}.


\begin{proof}[Proof of \Cref{Prop:AlgOutput}. Property (1) of \Cref{Prop:AlgOutput}]

We need to prove that $\beta_i - i + \tau_i = \alpha_i-i + \sigma_i$ for all $1 \le i \le n$.  The algorithm either begins with Step (3) or applies Step (2) (possibly several times) before applying Step (3).  First assume the algorithm begins with Step (3).  By construction, $\beta_i-i+\tau_i = \alpha_i - i + \sigma_i$ for $i \not= r,\p$.  We also have $\beta_r-r+\tau_r = \alpha_r-1-r+\sigma_r+1 = \alpha_r -r +\sigma_r$ and $\beta_\p-\p+\tau_\p = \alpha_\p+1 - \p + \sigma_\p-1 = \alpha_\p-\p+\sigma_\p$.

Next assume the algorithm begins with $k$ applications of Step (2), where $1 \le k < \ell(\alpha)$.  This means apply Steps (2a) and (2b) a total of $k$ times, then apply Step (3) once, then apply step (2c) a total of $k$ times. Since $\beta_i=\alpha_i$ and $\tau_i =\sigma_i$  for all $i \not= \p, r$, we have $\beta_i-i+\tau_i = \alpha_i - i + \sigma_i \ge 0$ for $i \not= \p, r$.  Since rows $r$ and $\p$ change via Step 3, as do the corresponding permutation entries, we again have $\beta_r-r+\tau_r = \alpha_r-1-r+\sigma_r+1 = \alpha_r -r +\sigma_r$ and $\beta_\p-\p+\tau_\p = \alpha_\p+1 - \p + \sigma_\p-1 = \alpha_\p-\p+\sigma_\p$.
\end{proof}

\begin{prop}
Algorithm \ref{alg: involution} is an involution.  That is, if $(V,U)$ is the image of $(T,S)$  under Algorithm \ref{alg: involution}, then $(T,S)$ is the image of $(V,U)$.
% \kyle{Maybe delete this second sentence}
\end{prop}


\begin{proof}
Algorithm \ref{alg: involution} begins with either Step (2) or Step (3).  We show that under both cases, the algorithm is an involution.

% \vskip .06truein

Case 1: \textit{Algorithm \ref{alg: involution} begins with Step (3).}
Recall that $r$ is chosen so that $\sigma(r)=\j$ where $\j$ is the smallest element of $\Ri$.  Step (3b) places $m$ into row $\p$ where $\sigma(\p)=\j+1.$
Furthermore, note that since $\tau=s_\j\sigma$
we have $\tau(\p)=\j.$  Let $\mathcal{R}'=\{ \tau_r | m \textrm{ appears in row r of } U\}$.  If $m$ appears exactly once in row $r$ and $m$ does not appear in row $\p$ of $S$, then ${\mathcal R}=\mathcal{R}'$.  If $m$ appears more than once in row $r$ of $S$ and does not appear in row $\p$ of $S$, then ${\mathcal R}'={\mathcal R} \cup \{\j+1\}$.  
If $m$ appears exactly once in row $r$
and at least once in row $\p$ then
${\mathcal R}'={\mathcal R} \setminus \{j+1\}.$
In all of the previous cases, $\j$ is the smallest entry in $\bar{\mathcal R}.$
Algorithm \ref{alg: involution} applies
$s_\j$ to $\tau$ yielding $s_\j \tau=s_\j^2\sigma=\sigma.$  Also,
the algorithm moves $m$ from row $\p$ in $U$
to row $r$ yielding our original pair
$(T,S).$

% \vskip .06truein

Case 2: \textit{Algorithm \ref{alg: involution} begins with Step (2).}  Let $m$ be the largest entry in $S$ and 
% assume the last $k$ rows of $S$ (with $0<k<\ell(\alpha)$) satisfy the following properties.
assume there is a $k<\ell(\alpha)$ such that for each $1\leq i\leq k$, all entries in row $\ell(\alpha)-i$ equal $m-i$ and $\sigma(\ell(\alpha)-i)=\ell(\alpha)-i.$ Algorithm~\ref{alg: involution} first applies Steps (2a) and (2b) a total of $k$ times to produce a pair $(\overline{\sigma},\overline{S})$, where we abuse notation and use just one overline to represent repeated iterations of Steps (2a) and (2b).  Next, Step (3) is applied, resulting in the pair $(\overline{V},\overline{U})$.  Finally, Step (2c) is applied a total of $k$ times, resulting in the pair $(V,U)$.  Applying Algorithm~\ref{alg: involution} to the pair $(V,U)$ first reduces the pair to $(\overline{V},\overline{U})$ by repeated application of Steps (2a) and (2b).  The proof of the case beginning with Step (3) now applies to this pair, so that the result of Step (3) is $(\overline{T},\overline{S})$.  Repeated application of Step (2c) then produces the initial pair $(T, S)$, as desired.
\end{proof}

\begin{figure}[ht]
    \centering
\begin{minipage}{.3\textwidth}\begin{tikzpicture}[yscale=-1,scale=.55]

% L is your composition/partition
\def\L{{4,3,4}}
\pgfmathsetmacro{\len}{dim(\L)}

% Draws diagram. 
% Commment out <<\node at (\i,\y) {(\i,\y)};>> if you don't want the coordinates.
\foreach \y in {1,...,\len}{
    \pgfmathsetmacro{\j}{\L[\y-1]}
    \foreach \i in {1,...,\j}{
        \draw (\i-.5,\y-.5) rectangle (\i+.5,\y+.5);
         %\node at (\i,\y) {(\i,\y)};
        }
}
% Draws tableau. 
\setsepchar{\\/,/ }
\readlist\LS{1,1,2,6\\2,3,5\\4,4,6,6}
\pgfmathsetmacro{\lens}{\listlen\LS[]}
\foreach \y in {1,...,\lens}{
    \pgfmathsetmacro{\j}{\L[\y-1]}
    \foreach \i in {1,...,\j}{
        % \draw (\i-.5,\y-.5) rectangle (\i+.5,\y+.5);
        \node at (\i,\y) {\LS[\y,\i]};
        }
}
\node at (-1,2) {$(S,T)\ =\ $};

% Define initial and terminal nodes of tunnel hooks. 
\tikzset{every node/.style={inner sep=-4pt}}
% % Draw hooks. You have to manually find the points.
\begin{scope}[on background layer]
\tikzset{every path/.style={line width = 7pt,color=black,line cap=round,opacity=.15,rounded corners}}
\draw (4,1)--(1,1)--(1,3);
\draw (3,2)--(2,2)--(2,3);
\draw (4,3)--(3,3);
\end{scope}

\end{tikzpicture}
\end{minipage}
$\xrightarrow[]{}$
\begin{minipage}{.3\textwidth}
\begin{tikzpicture}[yscale=-1,scale=.55]

% L is your composition/partition
\def\L{{4,4,3}}
\pgfmathsetmacro{\len}{dim(\L)}

% Draws diagram. 
% Commment out <<\node at (\i,\y) {(\i,\y)};>> if you don't want the coordinates.
\foreach \y in {1,...,\len}{
    \pgfmathsetmacro{\j}{\L[\y-1]}
    \foreach \i in {1,...,\j}{
        \draw (\i-.5,\y-.5) rectangle (\i+.5,\y+.5);
         %\node at (\i,\y) {(\i,\y)};
        }
}
% Draws tableau. 
\setsepchar{\\/,/ }
\readlist\LS{1,1,2,6\\2,3,5,6\\4,4,6}
\pgfmathsetmacro{\lens}{\listlen\LS[]}
\foreach \y in {1,...,\lens}{
    \pgfmathsetmacro{\j}{\L[\y-1]}
    \foreach \i in {1,...,\j}{
        % \draw (\i-.5,\y-.5) rectangle (\i+.5,\y+.5);
        \node at (\i,\y) {\LS[\y,\i]};
        }
}
\node at (-1,2) {$(U,V)\ =\ $};

% Define initial and terminal nodes of tunnel hooks. 
\tikzset{every node/.style={inner sep=-4pt}}
% % Draw hooks. You have to manually find the points.
\begin{scope}[on background layer]
\tikzset{every path/.style={line width = 7pt,color=black,line cap=round,opacity=.15,rounded corners}}
\draw (4,1)--(1,1)--(1,3);
\draw (4,2)--(2,2);
\draw (3,3)--(2,3);
\end{scope}

\end{tikzpicture}
\end{minipage}
\caption{An example of \Cref{alg: involution}}
\label{fig:THC-alg4-ex-general}
\end{figure}

\begin{ex}{\label{ex:kinvk}}  For $\alpha=(2,2,1,2,1,3)$ and $\beta=(6,3,2)$, consider the pair $(S,T)\in \pairs$ in \Cref{fig:THC-alg4-ex-general}, where we superimpose the two objects, both of shape $(4,3,4)$. The \THCc{} of $T$ is $(6,3,2)$, corresponding to the permutation $\sigma=[3,2,1,4,\cdots]$. Rows $1$ and $3$ contain the maximal element $m=6$. Since $\sigma_1=3>1=\sigma_3$, we set $r=3$ in Algorithm~\ref{alg: involution}.

Since $\sigma_r=1\neq n$, we move from Step (1) directly to Step (3) in the algorithm. Since $\sigma_3=1=:q$, we have $\tau=[3,1,2,4,\cdots]$. We move the cell in row $r=3$ to row $p=\sigma^{-1}(1+1)=2$ to create $U$ of shape $(4,4,3)$, and then $V$ define to be the unique \THC{} with shape $(4,4,3)$ and \THCc{} $(6,3,2)$.

% Let $n=15$ and consider the following \THC{} of a standard immaculate tableau of shape $\alpha=(3,3,3,3,3)$ seen in \Cref{fig:THC-alg4-ex}.  
%   The type of this \THC{} is $\Delta=(5,6,4,0,0,\dots)$, corresponding to the permutation $\sigma=35412\cdots$, and the cell containing $n=15$ is highlighted in red.  This cell is in row $4$, so that $r=4$ in Algorithm~\ref{alg: involution}.

% Since $\alpha_r=3 \not=1$, we move from Step (1) directly to Step (3) in the algorithm.  Since $\sigma_4=1$, set $\tau=(1,2)\sigma=35421\cdots,$ and then  we have $s=\sigma^{-1}(2)=5$.  Since $\alpha_4>1$, we set $\beta_5=\hat{\alpha}_5+1=3+1=4, \beta_4=\alpha_4-1=3-1=2,$ and $\beta_j=\alpha_j$ for $j=1,2,3$.  Therefore $\beta=(3,3,3,2,4)$, and in Step (4) we place the value $15$ into the cell that was added in row 5  to obtain the standard immaculate tableau $U$ depicted below, superimposed with its \THC.
\end{ex}







\section{Reduction to the Sym Case}
\label{section: kinv-k-sym}

In this section, we provide a combinatorial proof that $K^{-1}K=I$ by utilizing our algorithm for showing $\iK \K=I$ from \Cref{section:k-inv-k}.  In particular, we extend \Cref{alg: involution} to pairs of the form $(T,S)$,
where $T$ is a $\thc$ of \THCc~$\alpha$ and $S$ is a semistandard Young tableau (rather than an immaculate tableau) of shape $\sh(T)$.

% From \cite{AM23}, we have for each $\lambda,\mu\vdash n$ that
% \begin{equation}K^{-1}_{\lambda,\mu}=\sum_{\substack{\alpha\vDash n\\\dec(\alpha)=\lambda}}\sum_{T\in \thc_{\alpha,\mu}}\sgn(T),\end{equation}
% where $\dec(\alpha)$ is the partition obtained by writing a composition $\alpha$ in weakly decreasing order. 
%
% Recall that for each $\mu\vdash n$, there is a sign-preserving injection from the set of tunnel hook coverings of shape $\mu$ to the set of permutations $S_n$. 
For $\lambda,\mu\vdash n$, let $\sympairs$ be the set of pairs $(T,S)$ such that 
%\begin{itemize}
%\item 
$T$ is \THC{}  of \THCc{} $\alpha$ with $\dec(\alpha)=\lambda$ and
%\item 
$S$ is a semistandard Young tableau of shape $sh(T)$ and content $\mu$.
%\end{itemize}
Note that $S$ is partition shaped. Then writing $K^{-1}_{\lambda,\mu}$ as a signed sum of tunnel hook coverings as in \Cref{eq:kostka-in-terms-thc}, we have
\begin{equation}\label{eq: KinvK-sym-setup}
(K^{-1}K)_{\lambda,\mu}=\sum_{(T,S)\in \sympairs}\sgn(T).\end{equation}
We prove \Cref{Th:Three} by exhibiting a sign-reversing involution on $\sympairs$ when $\lambda\neq \mu$.

Define $\sympairsbig$ to be the set of pairs $(T,S)$ as above, except we assume $\lambda\neq \mu$ and replace the condition that ``$S$ is a semistandard Young tableau'' with ``$S$ is an immaculate tableau.''  Note that the shape of $S$ does not need to be a partition. 

For an element $(T,S) \in \sympairsbig$, say that $c$ is a \emph{bad cell} of $S$ if the position above $c$ is either not a cell in $S$ or is a cell in $S$ and contains a number that is larger than or equal to the number in the cell $c$. We have the following two observations.
\begin{enumerate}
    \item If $(T,S)\in \sympairs$, then applying \Cref{alg: involution} to $(T,S)$ produces an element of $\sympairsbig.$
    \item Let $(T,S)\in \sympairsbig$. Then $S$ has a bad cell if and only if $(T,S)\not\in \sympairs.$
\end{enumerate}

In order to describe our involution on $\sympairs$, it is useful to describe an involution on $\sympairsbig\setminus \sympairs.$ This map takes heavy inspiration from the sign-reversing involution that Gasharov used in a Schur positivity proof for certain chromatic symmetric functions \cite{gasharov_1996}.

\begin{defn}
For $\lambda,\mu\vdash n$ such that $\lambda\neq \mu$, define a map
$b_{\lambda,\mu }:\sympairsbig\setminus \sympairs\to \sympairsbig\setminus \sympairs$
algorithmically as follows.  
\begin{enumerate}
\item Let $(V,U)\in \sympairsbig\setminus \sympairs$ where $V$ has \THCc~$\beta$ with $\dec(\beta)=\lambda$. 
\item Let $i$ be the leftmost column of $U$ containing a bad cell and let $t$ be the largest value such that row $t$ contains a bad cell in column $i$.  Swap the cells of $U$ in the sets
%\[
$A=\{(t,j)\in U \mid j>i\},$
%\qquad 
and
$B=\{(t-1,j)\in U \mid j\geq i\}$
%\]
to create $U'$. 
\item Let $V'$ be the THC of shape $\sh(U')$ such that $\perm(V')=\perm(V) s_{t-1}.$ 
\item Set $b_{\lambda,\mu}(V,U)=(V',U')$.
\end{enumerate}
\end{defn}
\begin{lem}
For all $\lambda,\mu\vdash n$ with $\lambda\neq \mu$, $b_{\lambda,\mu}$ is a sign-reversing involution on $\sympairsbig\setminus\sympairs$.
\end{lem}

\begin{alg}\label{alg: sym involution FULL}
Let $\lambda,\mu\vdash n$ such that $\lambda\neq \mu$. Let $(T, S)\in \sympairs$. 

\begin{enumerate}
\item Apply Algorithm~\ref{alg: involution} to $(T,S)$ to get $(V,U)$. If $(V,U) \in \sympairs$, then output $(V,U)$.
% \kyle{This got messed up. Maybe ``Let $(V,U)=\psi_{\alpha,\beta}(T,S)$. If $(V,u)\in \sympairs$, then $(V,U)$ is output.'' Add a ``recall $\psi_{\alpha,\beta}$ from \Cref{alg: involution}''}
% \item Let $(V,U)=\psi_{\alpha,\beta}(T,S)$. If $(V,u)\in \sympairs$, then $(V,U)$ is output.
\item Otherwise, let $(V',U')=b_{\lambda,\mu}(V,U)$ and then go back to Step (1).
\item Repeat steps (1) and (2) until $(V,U)\in \sympairs$.
\end{enumerate}
\end{alg}

\begin{thm}
    For $\lambda,\mu\vdash n$ with $\lambda\neq \mu$, \Cref{alg: sym involution FULL} is a sign-reversing involution on $\sympairs.$
\end{thm}

\begin{proof}
Turn $\sympairsbig$ into a graph by connecting $(V,U)$ to $(V',U')$ if they are related by either
\begin{enumerate}
    \item $(V',U')$ is output of $(V,U)$ under \Cref{alg: involution}, or
    \item  $(V,U)\in \sympairsbig\setminus \sympairs$ and $b_{\lambda,\mu}(V,U)=(V',U')$.
\end{enumerate}
Since both \Cref{alg: involution} and $b_{\lambda,\mu}$ are involutions, every vertex of $\sympairsbig$ has degree $1$ or $2$.  Hence $\sympairsbig$ is a disjoint union of paths or cycles (which are all finite since $\sympairsbig$ is finite).  

Every element of $\sympairs$ must have degree one while every element of $\sympairsbig\setminus \sympairs$ must have degree two since only \Cref{alg: involution} can produce an element of $\sympairs$.  Therefore every connected component involving an element of $\sympairs$ must be a path with an odd number of vertices whose endpoints are in $\sympairs$.  Thus, \Cref{alg: sym involution FULL} is an involution, and sign-reversing since every path has an odd number of vertices.
\end{proof}

\begin{ex}
    \Cref{fig:sym-involu-full-ex} depicts \Cref{alg: sym involution FULL} applied to a pair $(S,T)\in \sympairs$ for $\lambda=(4,2,1)$ and $\mu=(2,2,2,2)$. The $(1)$ and $(2)$ above the arrows indicates which step is performed for the preceding pair. The circled number indicates the bad cell for $(2)$.
\end{ex}

 Although our map differs from the Loehr--Mendes bijection~\cite{LoeMen06}, we conjecture that when our map is restricted to standard Young tableaux, our map is equivalent to the $\Sym$ version of Sagan and Lee~\cite{SagLee03}. 




   \begin{figure}
    \centering
$\begin{tikzpicture}[yscale=-1,scale=.55]

% L is your composition/partition
\def\L{{4,2,2}}
\pgfmathsetmacro{\len}{dim(\L)}

% Draws diagram. 
% Commment out <<\node at (\i,\y) {(\i,\y)};>> if you don't want the coordinates.
\foreach \y in {1,...,\len}{
    \pgfmathsetmacro{\j}{\L[\y-1]}
    \foreach \i in {1,...,\j}{
        \draw (\i-.5,\y-.5) rectangle (\i+.5,\y+.5);
         %\node at (\i,\y) {(\i,\y)};
        }
}
% Draws tableau. 
\setsepchar{\\/,/ }
\readlist\LS{1,1,4,4\\2,2\\3,3}
\pgfmathsetmacro{\lens}{\listlen\LS[]}
\foreach \y in {1,...,\lens}{
    \pgfmathsetmacro{\j}{\L[\y-1]}
    \foreach \i in {1,...,\j}{
        % \draw (\i-.5,\y-.5) rectangle (\i+.5,\y+.5);
        \node at (\i,\y) {\LS[\y,\i]};
        }
}


% Define initial and terminal nodes of tunnel hooks. 
\tikzset{every node/.style={inner sep=-4pt}}
% % Draw hooks. You have to manually find the points.
\begin{scope}[on background layer]
\tikzset{every path/.style={line width = 7pt,color=black,line cap=round,opacity=.15,rounded corners}}
\draw (4,1)--(1,1)--(1,2);
\draw (2-.25,2)--(2+.25,2);
\draw (2,3)--(1,3);
\end{scope}

\end{tikzpicture}\ \begin{minipage}{.05\textwidth}\vspace{-1.8cm}$\xrightarrow{(1)}$
\end{minipage}\ \begin{tikzpicture}[yscale=-1,scale=.55]

% L is your composition/partition
\def\L{{3,2,3}}
\pgfmathsetmacro{\len}{dim(\L)}

% Draws diagram. 
% Commment out <<\node at (\i,\y) {(\i,\y)};>> if you don't want the coordinates.
\foreach \y in {1,...,\len}{
    \pgfmathsetmacro{\j}{\L[\y-1]}
    \foreach \i in {1,...,\j}{
        \draw (\i-.5,\y-.5) rectangle (\i+.5,\y+.5);
         %\node at (\i,\y) {(\i,\y)};
        }
}
% Draws tableau. 
\setsepchar{\\/,/ }
\readlist\LS{1,1,4\\2,2\\3,3,\circl{4}}
\pgfmathsetmacro{\lens}{\listlen\LS[]}
\foreach \y in {1,...,\lens}{
    \pgfmathsetmacro{\j}{\L[\y-1]}
    \foreach \i in {1,...,\j}{
        % \draw (\i-.5,\y-.5) rectangle (\i+.5,\y+.5);
        \node at (\i,\y) {\LS[\y,\i]};
        }
}


% Define initial and terminal nodes of tunnel hooks. 
\tikzset{every node/.style={inner sep=-4pt}}
% % Draw hooks. You have to manually find the points.
\begin{scope}[on background layer]
\tikzset{every path/.style={line width = 7pt,color=black,line cap=round,opacity=.15,rounded corners}}
\draw (3,1)--(1,1)--(1,3);
\draw (2-.25,2)--(2+.25,2);
\draw (3,3)--(2,3);
\end{scope}

\end{tikzpicture}\ \begin{minipage}{.05\textwidth}\vspace{-1.8cm}$\xrightarrow{(2)}$ \end{minipage}\ \begin{tikzpicture}[yscale=-1,scale=.55]

% L is your composition/partition
\def\L{{3,2,3}}
\pgfmathsetmacro{\len}{dim(\L)}

% Draws diagram. 
% Commment out <<\node at (\i,\y) {(\i,\y)};>> if you don't want the coordinates.
\foreach \y in {1,...,\len}{
    \pgfmathsetmacro{\j}{\L[\y-1]}
    \foreach \i in {1,...,\j}{
        \draw (\i-.5,\y-.5) rectangle (\i+.5,\y+.5);
         %\node at (\i,\y) {(\i,\y)};
        }
}
% Draws tableau. 
\setsepchar{\\/,/ }
\readlist\LS{1,1,4\\2,2\\3,3,4}
\pgfmathsetmacro{\lens}{\listlen\LS[]}
\foreach \y in {1,...,\lens}{
    \pgfmathsetmacro{\j}{\L[\y-1]}
    \foreach \i in {1,...,\j}{
        % \draw (\i-.5,\y-.5) rectangle (\i+.5,\y+.5);
        \node at (\i,\y) {\LS[\y,\i]};
        }
}


% Define initial and terminal nodes of tunnel hooks. 
\tikzset{every node/.style={inner sep=-4pt}}
% % Draw hooks. You have to manually find the points.
\begin{scope}[on background layer]
\tikzset{every path/.style={line width = 7pt,color=black,line cap=round,opacity=.15,rounded corners}}
\draw (3,1)--(1,1)--(1,3);
\draw (2,2)--(2,3);
\draw (3-.25,3)--(3+.25,3);
\end{scope}

\end{tikzpicture}
\ \begin{minipage}{.05\textwidth}\vspace{-1.8cm}$\xrightarrow[]{(1)}$ \end{minipage}\ \begin{tikzpicture}[yscale=-1,scale=.55]

% L is your composition/partition
\def\L{{3,3,2}}
\pgfmathsetmacro{\len}{dim(\L)}

% Draws diagram. 
% Commment out <<\node at (\i,\y) {(\i,\y)};>> if you don't want the coordinates.
\foreach \y in {1,...,\len}{
    \pgfmathsetmacro{\j}{\L[\y-1]}
    \foreach \i in {1,...,\j}{
        \draw (\i-.5,\y-.5) rectangle (\i+.5,\y+.5);
         %\node at (\i,\y) {(\i,\y)};
        }
}
% Draws tableau. 
\setsepchar{\\/,/ }
\readlist\LS{1,1,4\\2,2,\circl{4}\\3,3}
\pgfmathsetmacro{\lens}{\listlen\LS[]}
\foreach \y in {1,...,\lens}{
    \pgfmathsetmacro{\j}{\L[\y-1]}
    \foreach \i in {1,...,\j}{
        % \draw (\i-.5,\y-.5) rectangle (\i+.5,\y+.5);
        \node at (\i,\y) {\LS[\y,\i]};
        }
}


% Define initial and terminal nodes of tunnel hooks. 
\tikzset{every node/.style={inner sep=-4pt}}
% % Draw hooks. You have to manually find the points.
\begin{scope}[on background layer]
\tikzset{every path/.style={line width = 7pt,color=black,line cap=round,opacity=.15,rounded corners}}
\draw (3,1)--(1,1)--(1,3);
\draw (3,2)--(2,2);
\draw (2-.25,3)--(2+.25,3);
\end{scope}

\end{tikzpicture}
\ \begin{minipage}{.05\textwidth}\vspace{-1.8cm}$\xrightarrow[]{(2)}$ \end{minipage}\ 
\begin{tikzpicture}[yscale=-1,scale=.55]

% L is your composition/partition
\def\L{{2,4,2}}
\pgfmathsetmacro{\len}{dim(\L)}

% Draws diagram. 
% Commment out <<\node at (\i,\y) {(\i,\y)};>> if you don't want the coordinates.
\foreach \y in {1,...,\len}{
    \pgfmathsetmacro{\j}{\L[\y-1]}
    \foreach \i in {1,...,\j}{
        \draw (\i-.5,\y-.5) rectangle (\i+.5,\y+.5);
         %\node at (\i,\y) {(\i,\y)};
        }
}
% Draws tableau. 
\setsepchar{\\/,/ }
\readlist\LS{1,1\\2,2,4,4\\3,3}
\pgfmathsetmacro{\lens}{\listlen\LS[]}
\foreach \y in {1,...,\lens}{
    \pgfmathsetmacro{\j}{\L[\y-1]}
    \foreach \i in {1,...,\j}{
        % \draw (\i-.5,\y-.5) rectangle (\i+.5,\y+.5);
        \node at (\i,\y) {\LS[\y,\i]};
        }
}


% Define initial and terminal nodes of tunnel hooks. 
\tikzset{every node/.style={inner sep=-4pt}}
% % Draw hooks. You have to manually find the points.
\begin{scope}[on background layer]
\tikzset{every path/.style={line width = 7pt,color=black,line cap=round,opacity=.15,rounded corners}}
\draw (2,1)--(1,1);
\draw (4,2)--(1,2)--(1,3);
\draw (2-.25,3)--(2+.25,3);
\end{scope}

\end{tikzpicture}
$ 
\medskip

$
\ \begin{minipage}{.05\textwidth}\vspace{-2.4cm}$\xrightarrow[]{(1)}$ \end{minipage}\ \begin{tikzpicture}[yscale=-1,scale=.55]

% L is your composition/partition
\def\L{{2,3,2,1}}
\pgfmathsetmacro{\len}{dim(\L)}

% Draws diagram. 
% Commment out <<\node at (\i,\y) {(\i,\y)};>> if you don't want the coordinates.
\foreach \y in {1,...,\len}{
    \pgfmathsetmacro{\j}{\L[\y-1]}
    \foreach \i in {1,...,\j}{
        \draw (\i-.5,\y-.5) rectangle (\i+.5,\y+.5);
         %\node at (\i,\y) {(\i,\y)};
        }
}
% Draws tableau. 
\setsepchar{\\/,/ }
\readlist\LS{1,1\\2,2,\circl{4}\\3,3\\4}
\pgfmathsetmacro{\lens}{\listlen\LS[]}
\foreach \y in {1,...,\lens}{
    \pgfmathsetmacro{\j}{\L[\y-1]}
    \foreach \i in {1,...,\j}{
        % \draw (\i-.5,\y-.5) rectangle (\i+.5,\y+.5);
        \node at (\i,\y) {\LS[\y,\i]};
        }
}


% Define initial and terminal nodes of tunnel hooks. 
\tikzset{every node/.style={inner sep=-4pt}}
% % Draw hooks. You have to manually find the points.
\begin{scope}[on background layer]
\tikzset{every path/.style={line width = 7pt,color=black,line cap=round,opacity=.15,rounded corners}}
\draw (2,1)--(1,1);
\draw (3,2)--(1,2)--(1,4);
\draw (2-.25,3)--(2+.25,3);
\draw (2-.25,4)--(2+.25,4);
\end{scope}

\end{tikzpicture}\ \begin{minipage}{.05\textwidth}\vspace{-2.4cm}$\xrightarrow{(2)}$ \end{minipage}\ \begin{tikzpicture}[yscale=-1,scale=.55]

% L is your composition/partition
\def\L{{2,3,2,1}}
\pgfmathsetmacro{\len}{dim(\L)}

% Draws diagram. 
% Commment out <<\node at (\i,\y) {(\i,\y)};>> if you don't want the coordinates.
\foreach \y in {1,...,\len}{
    \pgfmathsetmacro{\j}{\L[\y-1]}
    \foreach \i in {1,...,\j}{
        \draw (\i-.5,\y-.5) rectangle (\i+.5,\y+.5);
         %\node at (\i,\y) {(\i,\y)};
        }
}
% Draws tableau. 
\setsepchar{\\/,/ }
\readlist\LS{1,1\\2,2,4\\3,3\\4}
\pgfmathsetmacro{\lens}{\listlen\LS[]}
\foreach \y in {1,...,\lens}{
    \pgfmathsetmacro{\j}{\L[\y-1]}
    \foreach \i in {1,...,\j}{
        % \draw (\i-.5,\y-.5) rectangle (\i+.5,\y+.5);
        \node at (\i,\y) {\LS[\y,\i]};
        }
}


% Define initial and terminal nodes of tunnel hooks. 
\tikzset{every node/.style={inner sep=-4pt}}
% % Draw hooks. You have to manually find the points.
\begin{scope}[on background layer]
\tikzset{every path/.style={line width = 7pt,color=black,line cap=round,opacity=.15,rounded corners}}
\draw (2,1)--(1,1)--(1,4);
\draw (3,2)--(2,2);
\draw (2-.25,3)--(2+.25,3);
\draw (2-.25,4)--(2+.25,4);
\end{scope}

\end{tikzpicture}\ \begin{minipage}{.05\textwidth}\vspace{-2.4cm}$\xrightarrow{(1)}$ \end{minipage}\ \begin{tikzpicture}[yscale=-1,scale=.55]

% L is your composition/partition
\def\L{{2,2,3,1}}
\pgfmathsetmacro{\len}{dim(\L)}

% Draws diagram. 
% Commment out <<\node at (\i,\y) {(\i,\y)};>> if you don't want the coordinates.
\foreach \y in {1,...,\len}{
    \pgfmathsetmacro{\j}{\L[\y-1]}
    \foreach \i in {1,...,\j}{
        \draw (\i-.5,\y-.5) rectangle (\i+.5,\y+.5);
         %\node at (\i,\y) {(\i,\y)};
        }
}
% Draws tableau. 
\setsepchar{\\/,/ }
\readlist\LS{1,1\\2,2\\3,3,\circl{4}\\4}
\pgfmathsetmacro{\lens}{\listlen\LS[]}
\foreach \y in {1,...,\lens}{
    \pgfmathsetmacro{\j}{\L[\y-1]}
    \foreach \i in {1,...,\j}{
        % \draw (\i-.5,\y-.5) rectangle (\i+.5,\y+.5);
        \node at (\i,\y) {\LS[\y,\i]};
        }
}


% Define initial and terminal nodes of tunnel hooks. 
\tikzset{every node/.style={inner sep=-4pt}}
% % Draw hooks. You have to manually find the points.
\begin{scope}[on background layer]
\tikzset{every path/.style={line width = 7pt,color=black,line cap=round,opacity=.15,rounded corners}}
\draw (2,1)--(1,1)--(1,4);
\draw (2,2)--(2,3);
\draw (3-.25,3)--(3+.25,3);
\draw (2-.25,4)--(2+.25,4);
\end{scope}

\end{tikzpicture}
\ \begin{minipage}{.05\textwidth}\vspace{-2.4cm}$\xrightarrow{(2)}$ \end{minipage}\ \begin{tikzpicture}[yscale=-1,scale=.55]

% L is your composition/partition
\def\L{{2,2,3,1}}
\pgfmathsetmacro{\len}{dim(\L)}

% Draws diagram. 
% Commment out <<\node at (\i,\y) {(\i,\y)};>> if you don't want the coordinates.
\foreach \y in {1,...,\len}{
    \pgfmathsetmacro{\j}{\L[\y-1]}
    \foreach \i in {1,...,\j}{
        \draw (\i-.5,\y-.5) rectangle (\i+.5,\y+.5);
         %\node at (\i,\y) {(\i,\y)};
        }
}
% Draws tableau. 
\setsepchar{\\/,/ }
\readlist\LS{1,1\\2,2\\3,3,4\\4}
\pgfmathsetmacro{\lens}{\listlen\LS[]}
\foreach \y in {1,...,\lens}{
    \pgfmathsetmacro{\j}{\L[\y-1]}
    \foreach \i in {1,...,\j}{
        % \draw (\i-.5,\y-.5) rectangle (\i+.5,\y+.5);
        \node at (\i,\y) {\LS[\y,\i]};
        }
}


% Define initial and terminal nodes of tunnel hooks. 
\tikzset{every node/.style={inner sep=-4pt}}
% % Draw hooks. You have to manually find the points.
\begin{scope}[on background layer]
\tikzset{every path/.style={line width = 7pt,color=black,line cap=round,opacity=.15,rounded corners}}
\draw (2,1)--(1,1)--(1,4);
\draw (2-.25,2)--(2+.25,2);
\draw (3,3)--(2,3);
\draw (2-.25,4)--(2+.25,4);
\end{scope}

\end{tikzpicture}
\ \begin{minipage}{.05\textwidth}\vspace{-2.4cm}$\xrightarrow{(1)}$ \end{minipage}\ \begin{tikzpicture}[yscale=-1,scale=.55]

% L is your composition/partition
\def\L{{2,2,2,2}}
\pgfmathsetmacro{\len}{dim(\L)}

% Draws diagram. 
% Commment out <<\node at (\i,\y) {(\i,\y)};>> if you don't want the coordinates.
\foreach \y in {1,...,\len}{
    \pgfmathsetmacro{\j}{\L[\y-1]}
    \foreach \i in {1,...,\j}{
        \draw (\i-.5,\y-.5) rectangle (\i+.5,\y+.5);
         %\node at (\i,\y) {(\i,\y)};
        }
}
% Draws tableau. 
\setsepchar{\\/,/ }
\readlist\LS{1,1\\2,2\\3,3\\4,4}
\pgfmathsetmacro{\lens}{\listlen\LS[]}
\foreach \y in {1,...,\lens}{
    \pgfmathsetmacro{\j}{\L[\y-1]}
    \foreach \i in {1,...,\j}{
        % \draw (\i-.5,\y-.5) rectangle (\i+.5,\y+.5);
        \node at (\i,\y) {\LS[\y,\i]};
        }
}


% Define initial and terminal nodes of tunnel hooks. 
\tikzset{every node/.style={inner sep=-4pt}}
% % Draw hooks. You have to manually find the points.
\begin{scope}[on background layer]
\tikzset{every path/.style={line width = 7pt,color=black,line cap=round,opacity=.15,rounded corners}}
\draw (2,1)--(1,1)--(1,4);
\draw (2-.25,2)--(2+.25,2);
\draw (2,3)--(2,4);
\draw (3-.25,4)--(3+.25,4);
\end{scope}

\end{tikzpicture}
$
    \caption{An example of {\Cref{alg: sym involution FULL}}}
    \label{fig:sym-involu-full-ex}
\end{figure}
% \acknowledgements{\lipsum[20]}

% \bibliographystyle{amsplain}

% \bibliography{FPSAC FILES/sample}



%% 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

\printbibliography

\end{document}
