%% 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]{FPSAC2024}
\articlenumber{70}
%% 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[alphabetic]{amsrefs}
%\usepackage[shortlabels]{enumitem}
%\usepackage{hyperref}
\usepackage{mathtools}
\usepackage{tikz}
%\usepackage{xcolor}
\usepackage{shuffle}
\usepackage{ifthen}
\usepackage{footmisc}

\usepackage{algorithm}
\usepackage{algpseudocode}

\algrenewcommand\algorithmicrequire{\textbf{Input:}}
\algrenewcommand\algorithmicensure{\textbf{Output:}}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{conjecture}{Conjecture}
\newtheorem{corollary}{Corollary}
\newtheorem{proposition}{Proposition}

\theoremstyle{definition}
\newtheorem{definition}{Definition}
\newtheorem{remark}{Remark}
\newtheorem{example}{Example}
\newtheorem*{warning}{Warning}



\usepackage{lipsum}

%% define your title in the usual way
\title[Shuffle theorem and sandpiles]{Shuffle theorems and sandpiles}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author[D'Adderio, Dukes, Iraci, Lazar, Le Borgne, and Vanden Wyngaerd]{Michele D'Adderio\addressmark{1}\thanks{\href{mailto:michele.dadderio@unipi.it}{michele.dadderio@unipi.it}. Partially supported by PRIN 2022A7L229 \emph{ALTOP}.},  Mark Dukes\addressmark{2}\thanks{\href{mailto:mark.dukes@ucd.ie}{mark.dukes@ucd.ie}}, Alessandro Iraci\addressmark{1}\thanks{\href{mailto:alessandro.iraci@unipi.it}{alessandro.iraci@unipi.it}}, Alexander Lazar\addressmark{3}\thanks{\href{mailto:alexander.leo.lazar@ulb.be}{alexander.leo.lazar@ulb.be}. Supported by ARC \footnotesize{``From algebra to combinatorics, and back.''}}, Yvan Le Borgne\addressmark{4}\thanks{\href{mailto:yvan.le-borgne@u-bordeaux.fr}{yvan.le-borgne@u-bordeaux.fr}. Partially supported by  ANR COMBIN\'E ANR-19-CE48-0011.}, \and Anna Vanden Wyngaerd\addressmark{3}\thanks{\href{mailto:anna.vanden.wyngaerd@ulb.be}{anna.vanden.wyngaerd@ulb.be}. Supported by ARC \footnotesize{``From algebra to combinatorics, and back.''}}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Dipartimento di Matematica, Università di Pisa, Pisa, PI, 56127, Italia \\ \addressmark{2}School of Mathematics and Statistics, University College Dublin, Belfield, Dublin 4, Ireland \\ \addressmark{3}Département de Mathématique, Université Libre de Bruxelles, Bruxelles, 1050, Belgique \\ \addressmark{4}LaBRI - Université Bordeaux 1, 33405 Talence cedex, France}

%% 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{We provide an explicit description of the recurrent configurations of the sandpile model on a family of graphs $\widehat{G}_{\mu,\nu}$, which we call \emph{clique-independent} graphs, indexed by two compositions $\mu$ and $\nu$. Moreover, we define a \emph{delay} statistic on these configurations, and we show that, together with the usual \emph{level} statistic, it can be used to provide a new combinatorial interpretation of the celebrated \emph{shuffle theorem} of Carlsson and Mellit. More precisely, we will see how to interpret the polynomials $\langle\nabla e_n, e_\mu h_\nu\rangle$ in terms of these configurations.}

%% 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{Shuffle theorem, sandpile model, recurrent configurations}

%% 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{bibliogr.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}

\newcommand{\area}{\mathsf{area}}
\newcommand{\dinv}{\mathsf{dinv}}
\newcommand{\pmaj}{\mathsf{pmaj}}
\newcommand{\lev}{\mathsf{level}}
\newcommand{\del}{\mathsf{delay}}
\newcommand{\maj}{\mathsf{maj}}

\newcommand{\D}{\mathsf{D}}
\newcommand{\LD}{\mathsf{LD}}
\newcommand{\PF}{\mathsf{PF}}

\newcommand{\anna}[1]{\textcolor{purple}{Anna: #1}}

\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}

\subsection{Shuffle theorem}

The \emph{shuffle theorem} of Carlsson and Mellit \cite{CarlssonMellitShuffle} is a recent breakthrough that provided a positive solution to a long-standing conjecture about a combinatorial formula for the Frobenius characteristic of the so-called diagonal harmonics. More precisely, this theorem provides the monomial expansion of the symmetric function $\nabla e_n$, where $e_n$ is the elementary symmetric function of degree $n$ in the variables $x_1,x_2,\dots$, and $\nabla$ is the famous \emph{nabla} operator introduced by Bergeron and Garsia in the 90's. In this formula, to each \emph{labelled Dyck path} of size $n$ corresponds a monomial, where the variables $x_1,x_2,\dots$ keep track of the labels, while the variables $q$ and $t$ keep track of the bistatistic ($\dinv$, $\area$).

In \cite{LoehrRemmel_pmaj} Loehr and Remmel provided an alternative combinatorial interpretation of the same symmetric function in terms of the same objects, but using the bistatistic ($\area$, $\pmaj$). In particular, they showed bijectively that the two combinatorial formulas coincide. In the present article we show that this last combinatorial formula has a natural interpretation in terms of the sandpile model.

\subsection{Sandpile model} \label{sec:sandpile}

The \emph{(abelian) sandpile model} is a combinatorial dynamical system on graphs first introduced by Bak, Tang and Wiesenfeld \cite{BakTangWiesenfeld} in the context of ``self-organized criticality'' in statistical mechanics. The sandpile model (and variants of it) have found applications in a wide variety of mathematical contexts including enumerative combinatorics, tropical geometry, and Brill--Noether theory, among others: see \cite{Klivans_Sandpiles} for a nice introductory monograph. \textit{In the present article we only consider the sandpile model with a sink}.

A well-known link between the combinatorics of this dynamical system and the one of the underlying graph is given by the so-called \emph{recurrent configurations} (see Definition~\ref{def:recurrent}). For example, the recurrent configurations of the sandpile model are in bijection with the spanning trees of the graph (see e.g.\ \cite{CoriLeBorgne_Tutte}).

If the underlying graph presents some symmetries, then it is natural to look at the recurrent configurations ``modulo'' those symmetries. For example, for the complete graph we can identify recurrent configurations that are the same up to a permutation of the vertices (not moving the sink): perhaps not surprisingly, we still get an interesting combinatorics, as in this case we find Catalan many such ``sorted'' configurations.


More formally, consider the sandpile model on a graph $G$, and let $\mathsf{Aut}(G)$ be the automorphism group of $G$. Consider a subgroup $\Gamma$ of the stabilizer of the sink. Now $\Gamma$ acts naturally on the set $\mathsf{Rec}(G)$ of recurrent configurations: we are interested in the orbits of this action, that we will call \emph{sorted recurrent configurations}.

\subsection{Main result}

We will consider an explicit family of graphs $\widehat{G}_{\mu,\nu}$ indexed by pairs of compositions $\mu$ and $\nu$. For such a graph $\widehat{G}_{\mu,\nu}$ we will look at a subgroup $\Gamma$ of its automorphism group that will be isomorphic to the Young subgroup $\mathfrak{S}_\mu\times \mathfrak{S}_\nu$ of the symmetric group $\mathfrak{S}_n$, where $n=|\mu|+|\nu|$. We denote by $\mathsf{SortRec}(\mu,\nu)$ the set of the corresponding sorted recurrent configurations of $\widehat{G}_{\mu,\nu}$.

For every recurrent configuration $\kappa$ of $\widehat{G}_{\mu,\nu}$, we will define a new statistic, called the \emph{delay} of $\kappa$ (denoted $\del(\kappa)$), which we will couple with the usual \emph{level} statistic (denoted $\lev(\kappa)$). To state our main result, we need a few more definitions.

Given a composition $\mu=(\mu_1,\mu_2,\dots)$, we denote by $e_\mu$ the product $e_{\mu_1}e_{\mu_2}\cdots$, and similarly $h_\mu=h_{\mu_1}h_{\mu_2}\cdots$, where $h_n$ is the complete homogeneous symmetric function of degree $n$. Finally, we denote by $\langle - ,-\rangle$ the Hall scalar product on symmetric functions.
\begin{theorem} \label{thm:main}
	For every pair of compositions $\mu$, $\nu$ such that $n=|\mu|+|\nu|$ we have
	\[\langle \nabla e_n, e_\mu h_\nu \rangle =\sum_{\kappa\in \mathsf{SortRec}(\mu,\nu)}q^{\lev(\kappa)}t^{\del(\kappa)}.\]
\end{theorem}
Notice that for $\mu=\varnothing$, the coefficient $\langle \nabla e_n, h_\nu  \rangle$ is simply the coefficient of $x^\nu=x_1^{\nu_1}x_2^{\nu_2}\cdots$ in $\nabla e_n$, hence this formula gives in particular a new combinatorial interpretation of the monomial expansion of the symmetric function $\nabla e_n$ in terms of the sandpile model.

The idea of the proof is to show that the sorted recurrent configurations with the bistatistic ($\lev$, $\del$) correspond bijectively to the labelled Dyck paths predicted by the shuffle theorem with the bistatistic ($\area$, $\pmaj$).

\subsection{Comments}

\cref{thm:main} extends several previous results in the literature: the case $\widehat{G}_{\varnothing,(n)}$ was already worked out in \cite{CoriLeBorgne_Kn}, (a slight modification of) the case $\widehat{G}_{(m,n-m),\varnothing}$ already appears in \cite{ADDHL_Narayana,DukesLeBorgne_Kmn}, while the case $\widehat{G}_{(m),(n-m)}$ is dealt with in \cite{DeryckeDukesLeBorgneSplitgraphs}.

Other articles in which sorted recurrent configurations make their appearance are for example \cite{ADDL_two_op} and \cite{DAdderioLeBorgne_Kmn}. It should be noticed that the works \cite{CoriLeBorgne_Kn} and \cite{DAdderioLeBorgne_Kmn} inspired the results in \cite{CoolsPanizzut_Kn} and \cite{CDJP_Kmn} respectively, which belong to tropical geometry and Brill-Noether theory.

We hope that the findings in the present article motivate further investigation of sorted recurrent configurations, and their relation to other parts of mathematics.


\section{Combinatorics of the shuffle theorem}\label{sec:shufflethm}

%Originally discovered by Haiman, the dinv statistic for labelled Dyck paths appears on paper for the first time probably in \cite{HHLRU-2005}. 
For every $n\in \N$, we set $[n]:=\{1,2,\dots,n\}$.

\smallskip

\noindent The pmaj statistic was first introduced in \cite{LoehrRemmel_pmaj}. The area statistic is classical.

\begin{definition}
	A \emph{Dyck path} of size $n$ is a lattice path going from $(0,0)$ to $(n,n)$, using only north and east steps and staying weakly above the line $x=y$ (also called the \emph{main diagonal}). A \emph{labelled Dyck path} is a Dyck path whose vertical steps are labelled with (not necessarily distinct) positive integers such that, when placing the labels in the square to the right of its step, the labels appearing in each column are strictly increasing from bottom to top. For us, a \emph{parking function}\footnote{These are in bijection with the functions $f \colon [n] \rightarrow [n]$ such that $ \# \{ 1 \leq j \leq n \mid f(j) \geq i \} \leq n+1-i$, by defining $f(i)$ to be the column of the label $i$.} of size $n$ is a labelled Dyck path of size $n$ whose labels are precisely the elements of $[n]$. See Figure~\ref{fig:LDP_config} for an example.
\end{definition}

The set of all parking functions of size $n$ is denoted by $\PF(n)$.

%\begin{figure}[!ht]
%	\centering
%	
%	\begin{tikzpicture}[scale=0.6]
%		\draw[gray!60, thin] (0,0) grid (8,8) (0,0) -- (8,8);
%		\draw[blue!60, line width = 1.6pt] (0,0)|-(2,3)|-(5,5)|-(6,7)|-(8,8);
%		
%		\draw
%		(0.5,0.5) circle(0.4 cm) node {$2$}
%		(0.5,1.5) circle(0.4 cm) node {$4$}
%		(0.5,2.5) circle(0.4 cm) node {$5$}
%		(2.5,3.5) circle(0.4 cm) node {$1$}
%		(2.5,4.5) circle(0.4 cm) node {$3$}
%		(5.5,5.5) circle(0.4 cm) node {$2$}
%		(5.5,6.5) circle(0.4 cm) node {$6$}
%		(6.5,7.5) circle(0.4 cm) node {$1$};
%	\end{tikzpicture}
%	
%	\caption{A labelled Dyck path.}
%	\label{fig:LDP}
%\end{figure}


\begin{figure}[!ht]
	\centering

	\begin{tikzpicture}[scale=0.5]
		\draw[gray!60, thin] (0,0) grid (12,12) (0,0) -- (12,12);
		\draw[blue!60, line width = 1.6pt] (0,0)|-(1,5)|-(3,7)|-(7,9)|-(8,10)|-(12,12);

		\draw
		(0.5,0.5) circle(0.4 cm) node {\textcolor{red}{\footnotesize{$3$}}}
		(0.5,1.5) circle(0.4 cm) node {\textcolor{blue}{\footnotesize{$5$}}}
		(0.5,2.5) circle(0.4 cm) node {\textcolor{olive}{\footnotesize{$6$}}}
		(0.5,3.5) circle(0.4 cm) node {\footnotesize{$9$}}
		(0.5,4.5) circle(0.4 cm) node {\scriptsize{$10$}}
		(1.5,5.5) circle(0.4 cm) node {\textcolor{olive}{\footnotesize{$7$}}}
		(1.5,6.5) circle(0.4 cm) node {\scriptsize{$11$}}
		(3.5,7.5) circle(0.4 cm) node {\textcolor{red}{\footnotesize{$2$}}}
		(3.5,8.5) circle(0.4 cm) node {\textcolor{olive}{\footnotesize{$8$}}}
		(7.5,9.5) circle(0.4 cm) node {\textcolor{blue}{\footnotesize{$4$}}}
		(8.5,10.5) circle(0.4 cm) node {\textcolor{red}{\footnotesize{$1$}}}
		(8.5,11.5) circle(0.4 cm) node {\scriptsize{$12$}};
%		(3.5,0.5) node {\textcolor{red}{\small{X}}}
%		(8.5,0.5) node {\textcolor{red}{\small{X}}}
%		(8.5,7.5) node {\textcolor{red}{\small{X}}}
%		(7.5,1.5) node {\textcolor{blue}{\small{X}}};
		% <YLB>
		\foreach \i in {1,...,12}{
				\draw node[anchor=east] at (-1.2,\i-0.5) {\small $a_{\i}(D)=$};
			}
		\foreach \i/\j in {1/0,2/1,3/2,4/3,5/4,6/4,7/5,8/4,9/5,10/2,11/2,12/3}{
				\draw node at (-1,\i-0.5) {\small$\j$};
			}
		\draw node[anchor=east] at (-0.5,-0.5) {\small $\area(D) = 35$};
		% </YLB>
	\end{tikzpicture}

	\caption{An element $D$ of $\PF((4,3);(3,2))$.}
	\label{fig:LDP_config}
\end{figure}

%\begin{definition}
%A \emph{parking function} of size $n$ is a function $f \colon [n] \rightarrow [n]$ such that $ \# \{ 1 \leq j \leq n \mid f(j) \geq i \} \leq n+1-i$.
%\end{definition}
%
%We denote by $\PF(n)$ the set of all the parking functions of size $n$. These are in bijective correspondence with the subset of labelled Dyck paths of size $n$ whose labels are exactly the numbers from $1$ to $n$. More explicitly, a parking function $f$ corresponds to the labelled Dyck path with label $i$ in column $f(i)$ for $1 \leq i \leq n$. We will identify a parking function with the corresponding labelled Dyck path.

%\begin{definition}
%	An \emph{area word} is a (finite) string of symbols $a_1 a_2 \cdots a_n$ in a well-ordered alphabet such that if $a_i < a_{i+1}$ then $a_{i+1}$ is the successor of $a_i$ in the alphabet.
%\end{definition}
%
%Other than the usual alphabet $\mathbb{N} = 0 < 1 < 2 < \dots$ it will be useful for our purposes to introduce the alphabet $\overline{\mathbb{N}} \coloneqq 0 < \bar{0} < 1 < \bar{1} < 2 < \dots$.

\begin{definition}
	Given $D\in \PF(n)$, we define its \emph{area word} to be the string of integers $a(D) = a_1(D) \cdots a_n(D)$ where $a_i(D)$ is the number of whole squares in the $i$-th row (from the bottom) between the path and the main diagonal. We define the \emph{area} of $D$ as \[ \area(D) \coloneqq \sum_{i=1}^n a_i(D). \]
\end{definition}

\begin{example} \label{ex:area}
	The area word of the path in Figure \ref{fig:LDP_config} is $012344545223$ and its area is $35$.
\end{example}
% Notice that the area word of a Dyck path is an area word in the alphabet $\mathbb{N}$.

%\begin{definition}
%	Let $D \in \D(n)$. We define its \emph{bounce path} as a lattice path from $(0,0)$ to $(n,n)$ computed in the following way: it starts in $(0,0)$ and travels north until it encounters the beginning of an east step of $D$, then it turns east until it hits the main diagonal, then it turns north again, and so on; thus it continues until it reaches $(n,n)$. 
%\end{definition}
%
%We label the vertical steps of the bounce path starting from $0$ and increasing the labels by $1$ every time the path hits the main diagonal (so the steps in the first vertical segment of the path are labelled with $0$, the ones in the next vertical segment are labelled with $1$, and so on). We define the \emph{bounce word} of $D$ to be the string $b(D) = b_1(D) \cdots b_n(D)$ where $b_i(D)$ is the label attached to the $i$-th vertical step of the bounce path.

%\begin{figure}[!ht]
%	\centering
%	
%	\begin{tikzpicture}[scale=0.6]
%		\draw[gray!60, thin] (0,0) grid (8,8) (0,0) -- (8,8);
%		\draw[blue!60, line width = 1.6pt] (0,0)|-(2,3)|-(5,5)|-(6,7)|-(8,8);
%		
%		\draw[dashed, ultra thick, opacity=0.6] (0,0) |- (3,3) |- (5,5) |- (7,7) |- (8,8);
%		
%		\draw
%		(-0.5,0.5) node {$0$}
%		(-0.5,1.5) node {$0$}
%		(-0.5,2.5) node {$0$}
%		(-0.5,3.5) node {$1$}
%		(-0.5,4.5) node {$1$}
%		(-0.5,5.5) node {$2$}
%		(-0.5,6.5) node {$2$}
%		(-0.5,7.5) node {$3$};
%	\end{tikzpicture}
%	
%	\caption{Construction of the bounce path and the bounce word (left).}
%	\label{fig:bouncepath-dyck}
%\end{figure}

%\begin{definition}
%	We define the statistic \emph{bounce} on $\D(n)$ and $\LD(n)$ as \[ \bounce(D) \coloneqq \sum_{i=1}^n b_i(D). \]
%\end{definition}

%\begin{definition}\label{def: inversion LD}
%	Let $D \in \LD(n)$. For $1 \leq i < j \leq n$, we say that the pair $(i,j)$ is an \emph{inversion} if
%	\begin{itemize}
%		\item either $a_i(D) = a_j(D)$ and $l_i(D) < l_j(D)$ (\emph{primary inversion}),
%		\item or $a_i(D) = a_j(D) + 1$ and $l_i(D) > l_j(D)$ (\emph{secondary inversion}).
%	\end{itemize}
%	Then we define $d_i \coloneqq \# \{ i < j \leq n \mid (i,j) \; \text{is an inversion} \}$.
%\end{definition}
%
%\begin{definition}\ \label{def: dinv LD}
%	We define the statistic \emph{dinv} on $D\in \LD(n)$ as \[ \dinv(D) \coloneqq \sum_{i=1}^n d_i(D). \] 
%\end{definition}
%
%The number of primary and secondary inversions are referred to as \emph{primary} and \emph{secondary dinv} respectively. The labelled Dyck path in Figure~\ref{fig:LDP} has dinv equal to $6$. Its inversions are $(2,7), (4,7)$ (primary), and $(2,6), (3,4), (3,8), (5,8)$ (secondary).
%
%\begin{definition} \label{def: dinv reading word LD}
%	Let $D \in \LD(n)$. We define its \emph{dinv reading word} as the sequence of the labels read starting from the ones in the main diagonal going bottom to top, left to right; next the ones in the diagonal $x+y=1$ bottom to top, left to right; then the ones in the diagonal $x+y=2$ and so on.
%\end{definition}
%
%For example, the labelled Dyck path in Figure~\ref{fig:LDP} has dinv reading word $22416153$.

To introduce the other statistic, we need a couple of definitions.

\begin{definition}
	Let $a_1 a_2 \cdots a_k$ be a string of integers. We define its \emph{descent set} \[ \mathsf{Des}(a_1 a_2 \cdots a_k) \coloneqq \{ 1 \leq i \leq k-1 \mid a_i > a_{i+1} \} \] and its \emph{major index} $\mathsf{maj}(a_1 a_2 \cdots a_k)$ as the sum of the elements of the descent set.
\end{definition}

\begin{definition}
	Let $D \in \PF(n)$. We define its \emph{parking word} $p(D)$ as follows.

	Let $C_1$ be the multiset containing the labels appearing in the first column of $D$, and let $p_1(D) \coloneqq \max C_1$. At step $i$, let $C_i$ be the multiset obtained from $C_{i-1}$ by removing $p_{i-1}(D)$ and adding all the labels in the $i$-th column of the $D$; let \[ p_i(D) \coloneqq \max \, \{x \in C_i \mid x \leq p_{i-1}(D) \} \] if this last set is non-empty, and \[p_i(D) \coloneqq \max \, C_i\] otherwise. We finally define the parking word of $D$ as $p(D) \coloneqq p_1(D) \cdots p_n(D)$.
\end{definition}

\begin{definition}
	We define the statistic \emph{pmaj} on $D\in \PF(n)$ as \[ \pmaj(D) \coloneqq \mathsf{maj}(p_n(D) \cdots p_1(D)). \]
\end{definition}

\begin{example}\label{ex:parking_word} For example, the parking word of the parking function $D$ in Figure~\ref{fig:LDP_config} is\footnote{\label{note_bars}We put a bar on the two-digit numbers not to confuse them.} $\overline{1\! 0} 9 7 6 5 3 2\overline{1\!1} 8 41\overline{1\! 2}$. In fact, we have $C_1 = \{3,4,5,6,9,10\}$, $C_2 = \{3,4,5,6,9,7,11\}$, $C_3 = \{3,4,5,6,7,11\}$, and so on. The descent set of the reverse is $\{1,5\}$, so $\pmaj(D) =6$. %Notice that $\pmaj(D) \leq \bounce(D)$, and if $l_i(D) = i$ (or, more generally, if all the labels are in strictly increasing order), then the equality holds. The converse is not true in general.
\end{example}
\begin{definition}
	For $D \in \PF(n)$ we set $l_i(D)$ to be the label of the $i$-th vertical step. Then the \emph{pmaj reading word} of $D$ is the sequence $l_1(D) \cdots l_n(D)$, i.e. the sequence of the labels read bottom to top.
\end{definition}

\noindent For example, the labelled Dyck path in Figure~\ref{fig:LDP_config} has pmaj reading word $\textcolor{red}{3}\textcolor{blue}{5}\textcolor{olive}{6}9\overline{1\! 0} \textcolor{olive}{7}\overline{1\!1} \textcolor{red}{2}\textcolor{olive}{8}\textcolor{blue}{4}\textcolor{red}{1}\overline{1\! 2}$.
%
%To each labelled Dyck path we associate a monomial in the variables $x_1,x_2,\dots$: for $D\in \LD(n)$ we set \[ x^D \coloneqq \prod_{i=1}^n x_{l_i(D)}. \]

Given two compositions $\mu=(\mu_1,\mu_2,\dots)$ and $\nu=(\nu_1,\nu_2,\dots)$ with $|\mu|+|\nu|=n$, let $K_{\mu_1}=\{n,n-1,\dots, n-\mu_1+1\}$, $K_{\mu_2}=\{n-\mu_1, n-\mu_1-1,\dots,n-\mu_1-\mu_2+1\}$, and so on, and let $I_{\nu_1}=\{1,2,\dots, \nu_1\}$, $I_{\nu_2}=\{\nu_1+1,\nu_1+2,\dots, \nu_1+\nu_2\}$, and so on. Notice that the sets $K_{\mu_1},K_{\mu_2},\dots$, $I_{\nu_1},I_{\nu_2},\dots$ form a partition of $[n]$.

Let now $\uparrow\!\! K_{\mu_i}$ be the word consisting of the elements of $K_{\mu_i}$ in increasing order: for example $\uparrow\!\! K_{\mu_1}=(n-\mu_1+1) (n-\mu_1+2) \cdots (n-1) n$.
Similarly, let $\downarrow\!\! I_{\nu_j}$ be the word consisting of the elements of $I_{\nu_j}$ in decreasing order: for example $\downarrow\!\! I_{\nu_1}=\nu_1 (\nu_1-1)\cdots 21$.

Consider the shuffle
\[ \mathsf{W}(\mu;\nu)\coloneqq \uparrow\!\! K_{\mu_1} \shuffle \uparrow\!\! K_{\mu_2} \shuffle\cdots \shuffle \uparrow\!\! K_{\mu_{\ell(\mu)}} \shuffle  \downarrow\!\! I_{\nu_1} \shuffle \downarrow\!\! I_{\nu_1} \shuffle \cdots \shuffle \downarrow\!\! I_{\nu_{\ell(\nu)}},\]
which we can think of as a set of permutations in $\mathfrak{S}_n$ in one-line notation. Let $\PF(\mu;\nu)$ be the set of parking functions whose pmaj reading word is in $\mathsf{W}(\mu;\nu)$.

\noindent For example\footref{note_bars}, $\mathsf{W}((4,3);(3,2))=9\overline{1\! 0}\,  \overline{1\! 1}\,  \overline{1\! 2} \shuffle \textcolor{olive}{678} \shuffle \textcolor{blue}{54}\shuffle \textcolor{red}{321}$, and the pmaj reading word of the parking function $D$ in Figure~\ref{fig:LDP_config} belongs to it, so that $D\in \mathsf{W}((4,3);(3,2))$.

We can now state the shuffle theorem in the form that is suitable for our purposes: this is a combination of the main results in \cite{CarlssonMellitShuffle} and \cite{LoehrRemmel_pmaj} combined with \emph{superization}: see  \cite[Chapter~6]{Haglund-Book-2008}.
\begin{theorem}\label{thm:shuffle_pmaj}
	For every pair of compositions $\mu$ and $\nu$ with $|\mu|+|\nu|=n$ we have
	\[\langle\nabla e_n,e_\mu h_\nu \rangle=\sum_{D\in \PF(\mu;\nu)}q^{\area(D)}t^{\pmaj(D)}.\]
\end{theorem}

\section{The clique-independent graphs \texorpdfstring{$\widehat{G}_{\mu,\nu}$}{Gmunu}}

\begin{definition}
	Let $\mu, \nu$ be two compositions (i.e.\ tuples of positive integers). Set $n=|\mu|+|\nu|$. We define a graph $G_{\mu,\nu}$ with set of vertices $[n]:=\{1,2,\dots,n\}$ consisting of the following \emph{components}\footnote{Notice that the notation is coherent with the one used in Section~\ref{sec:shufflethm}.}:
	\begin{itemize}
		\item $\ell(\mu)$ \emph{clique components}, i.e.\ complete graphs, $K_{\mu_1}, K_{\mu_2},\dots$, on $\mu_1, \mu_k,\dots$ vertices respectively. The vertices of $K_{\mu_1}$ are $n,n-1,\dots, n-\mu_1+1$; the vertices of $K_{\mu_2}$ are $n-\mu_1, n-\mu_1-1,\dots,n-\mu_1-\mu_2+1$; and so on.
		\item $\ell(\nu)$ \emph{independent components}, i.e.\ graphs without edges, $I_{\nu_1}, I_{\nu_2},\dots$, on $\nu_1, \nu_2,\dots$ vertices respectively; the vertices of $I_{\nu_1}$ are $1,2,\dots, \nu_1$; the vertices of $I_{\nu_2}$ are $\nu_1+1,\nu_1+2,\dots, \nu_1+\nu_2$; and so on.
	\end{itemize}
	Finally, two vertices in distinct components are always connected by an edge.
\end{definition}

\begin{example}
	If $\mu = \emptyset$, then $G_{\emptyset,\nu}$ is the complete multipartite graph $K_{\nu_1,\nu_2,\dots}$. If $\nu = \emptyset$, then $G_{\mu,\emptyset}$ is isomorphic to the complete graph $K_{|\mu|}$; however, for our purposes we will distinguish between $G_{(|\mu|),\emptyset}$ and $G_{(\mu_1,\mu_2,\dots),\emptyset}$, as we will consider the action of different groups of automorphisms, which will lead to different sorted configurations.
\end{example}

Given one of our labelled graphs $G_{\mu,\nu}$, we define the graph $\widehat{G}_{\mu,\nu}$ simply as $G_{\mu,\nu}$ to which we add a vertex $0$, and we connect it with every other vertex. We will consider the sandpile on $\widehat{G}_{\mu,\nu}$, where $0$ is the sink. Figure~\ref{fig:graph-munu} is an illustration of the graph $\widehat{G}_{(4,\textcolor{olive}{3}),(\textcolor{red}{3},\textcolor{blue}{2})}$.

\begin{figure}
	\centering
	\def\radius{4.8}
	\def\mythick{1.4pt}
	\begin{tikzpicture}[every node/.style={circle,thick,draw,inner sep=1.6pt},scale=0.6]
			\coordinate (0) at (0,0) {};
			\foreach \i in {1,...,12}{
					\coordinate (\i) at (60 + \i*30:\radius) {};
				}
			\def\col{gray!40}
			\foreach \i in {1,...,12}{
					\foreach \j in {\i,...,12}{
							\ifthenelse{\(\i<4 \AND \j<4\) \OR \(\i = 4 \AND \j = 5\)}{\def\col{white}}{}
							\draw[\col] (\i) -- (\j);
						}}
			\foreach \i in {6,...,8}{
				\foreach \j in {\i,...,8}{
					\draw[line width = \mythick,olive] (\i) -- (\j);
				}
			}
			\foreach \i in {9,...,12}{
				\foreach \j in {\i,...,12}{
					\draw[line width = \mythick] (\i) -- (\j);
				}
			}
			\def\col{red}
			\foreach \i in {1,...,12}{
					\draw[gray] (\i)--(0);
					\ifnum\i>3\relax \def\col{blue}\fi
					\ifnum\i>5\relax \def\col{olive}\fi
					\ifnum\i>8\relax \def\col{black}\fi
					\node[\col, fill = white] at (\i) {$\i$};
				}
			\node[gray, fill = white] at (0) {$0$};
	\end{tikzpicture}
	\caption{The graph $\widehat{G}_{(4,\textcolor{olive}{3}),(\textcolor{red}{3},\textcolor{blue}{2})}$.}\label{fig:graph-munu}
\end{figure}

\section{Basics of the sandpile model}\label{sec:basics-sandpile}

In the present work with a \emph{graph} we will always mean a simple graph, i.e.\ a graph with no loops and no multiple edges.

\begin{definition}
	Let $G$ be a finite, undirected graph on the vertex set $\{0,1,\dots,n\}$.

	A \emph{configuration} of the \emph{sandpile (model) on }$G$ is a map $\kappa: [n]\cup\{0\}\to \Z$ that assigns a (integer) number of ``grains of sand'' to each vertex of $G$.

	If $0\leq \kappa(v) \leq \deg(v)$, we say that $v$ is \emph{stable}, and otherwise it is \emph{unstable}. Any vertex can \emph{topple} (or \emph{fire}), and ``donate a single grain'' to each of its neighbors: the result is a new configuration $\kappa'$ in which $\kappa'(v) = \kappa(v) - \deg(v)$ and for any $w\neq v$ \[\kappa'(w) = \begin{cases} \kappa(w) + 1, & \text{if }(v,w) \text{ is an edge}\\ \kappa(w), & \text{otherwise.}\end{cases}\]
	For any $v \in \{0,\dots,n\}$ we write $\phi_v$ for the \emph{toppling operator} at vertex $v$. That is $\phi_v(\kappa)$ is a new configuration obtained from $\kappa$ by toppling the vertex $v$.

	The vertex $0$ is special in this model, and we call it the \emph{sink}, while we call all the others \emph{nonsink} vertices. We say that a configuration $\kappa$ is \emph{non-negative} if all of its nonsink vertices are non-negative, \emph{stable} if all of its nonsink vertices are stable, and \emph{unstable} if at least one of its nonsink vertices is unstable.

\end{definition}
\begin{remark}
	Notice that the notion of stable configuration has no dependency on the value on the sink. Therefore, as it is customary, we will ignore the value of a configuration on the sink, and consider the configurations as restricted on the nonsink vertices. Moreover, we will identify every configuration $\kappa$ with the word $\kappa(n)\kappa(n-1)\cdots \kappa(2)\kappa(1)$.
\end{remark}
\begin{example} \label{ex:kappa_config}
	% I have checked this example via computer. Anna
	Consider the graph $\widehat{G}_{(4,\textcolor{olive}{3}),(\textcolor{red}{3},\textcolor{blue}{2})}$ (see Figure~\ref{fig:graph-munu}), whose vertices are $\{0\}\cup [12]$, and let $0$ be the sink. The configuration $\kappa$ given by\footref{note_bars}  $3\overline{1\! 0}\, \overline{1\! 1}\, \overline{1\! 1} \textcolor{olive}{8 \overline{1\! 0}\, \overline{1\! 1}}\, \textcolor{blue}{\overline{1\! 0} 4} \textcolor{red}{9 7 3}$ is a stable configuration. We compute a few topplings:
	\begin{align*}
	\phi_0(\kappa) & =4\overline{1\! 1}\, \overline{1\! 2}\, \overline{1\! 2} \textcolor{olive}{9 \overline{1\! 1}\, \overline{1\! 2}}\, \textcolor{blue}{\overline{1\! 1} 5} \textcolor{red}{\overline{1\! 0} 8 4},\\ (\phi_{\overline{1\! 0}}\!\circ\!\phi_0)(\kappa)& =5\overline{1\! 2} 0 \overline{1\! 3}\, \textcolor{olive}{\overline{1\! 0}\, \overline{1\! 2}\, \overline{1\! 3}}\, \textcolor{blue}{\overline{1\! 2} 6} \textcolor{red}{\overline{1\! 1} 9 5},\\
	(\phi_{9}\!\circ\!\phi_{\overline{1\! 0}}\!\circ\!\phi_0)(\kappa) & =6\overline{1\! 3}\, 11 \textcolor{olive}{\overline{1\! 1}\, \overline{1\! 3}\, \overline{1\! 4}}\, \textcolor{blue}{\overline{1\! 3} 7} \textcolor{red}{\overline{1\! 2}\, \overline{1\! 0} 6}, \\	(\phi_{7}\!\circ\! \phi_{9}\!\circ\!\phi_{\overline{1\! 0}}\!\circ\!\phi_0)(\kappa) & =7\overline{1\! 4}\, 22 \textcolor{olive}{\overline{1\! 2} 1 \overline{1\! 5}}\, \textcolor{blue}{\overline{1\! 4} 8} \textcolor{red}{\overline{1\! 3}\, \overline{1\! 1} 7},\\
	(\phi_{6}\!\circ\!\phi_{7}\!\circ\! \phi_{9}\!\circ\!\phi_{\overline{1\! 0}}\!\circ\!\phi_0)(\kappa) & =8\overline{1\! 5}\, 33 \textcolor{olive}{\overline{1\! 3} 2 3} \textcolor{blue}{\overline{1\! 5} 9} \textcolor{red}{\overline{1\! 4}\, \overline{1\! 2} 8},\\ (\phi_{5}\!\circ\!\phi_{6}\!\circ\!\phi_{7}\!\circ\! \phi_{9}\!\circ\!\phi_{\overline{1\! 0}}\!\circ\!\phi_0)(\kappa) & =9\overline{1\! 6}\, 4 4 \textcolor{olive}{\overline{1\! 4} 3 4} \textcolor{blue}{4 9} \textcolor{red}{\overline{1\! 5}\, \overline{1\! 3} 9},\\ (\phi_{3}\!\circ\!\phi_{5}\!\circ\!\phi_{6}\!\circ\!\phi_{7}\!\circ\! \phi_{9}\!\circ\!\phi_{\overline{1\! 0}}\!\circ\!\phi_0)(\kappa) & =\overline{1\! 0}\, \overline{1\! 7}\, 5 5 \textcolor{olive}{\overline{1\! 5} 4 5} \textcolor{blue}{5 \overline{1\! 0}} \textcolor{red}{5 \overline{1\! 3} 9},\\ (\phi_{2}\!\circ\!\phi_{3}\!\circ\!\phi_{5}\!\circ\!\phi_{6}\!\circ\!\phi_{7}\!\circ\! \phi_{9}\!\circ\!\phi_{\overline{1\! 0}}\!\circ\!\phi_0)(\kappa) &=\overline{1\! 1}\, \overline{1\! 8}\, 6 6 \textcolor{olive}{\overline{1\! 6} 5 6} \textcolor{blue}{6 \overline{1\! 1}} \textcolor{red}{5 3 9}.
	\end{align*}
\end{example}
\begin{definition}\label{def:recurrent}
	Let $\kappa$ be a stable configuration, and consider the configuration $\phi_0(\kappa)$. We say that $\kappa$ is \emph{recurrent}\footnote{In the literature ``recurrent'' is sometimes used in a broader sense than in this paper. Configurations that are recurrent in our sense are called \emph{critical} in these settings.} if there is an order of all the nonsink vertices such that toppling the vertices in that order we always stay non-negative. Of course at the end of this sequence of topplings we will be back to $\kappa$. More precisely, a configuration $\kappa$ is recurrent if there is a permutation $\sigma=\sigma_1\sigma_2\cdots \sigma_n\in \mathfrak{S}_n$ such that
	\[\phi_0(\kappa),(\phi_{\sigma(1)}\circ \phi_0)(\kappa),(\phi_{\sigma(2)}\circ\phi_{\sigma(1)}\circ \phi_0)(\kappa),\dots,(\phi_{\sigma(n)}\circ \cdots \circ \phi_{\sigma(1)}\circ \phi_0)(\kappa)=\kappa\]
	are all non-negative configurations. In this case, $\sigma$ is the \emph{toppling word} of this sequence of topplings, and we say that this sequence \emph{verifies the recurrence} of $\kappa$.
\end{definition}

\begin{example} \label{ex:verify_recurrence}
	% I have checked this example via computer. Anna
	The configuration $\kappa=3\overline{1\! 0}\, \overline{1\! 1}\, \overline{1\! 1} \textcolor{olive}{8 \overline{1\! 0}\, \overline{1\! 1}}\, \textcolor{blue}{\overline{1\! 0} 4} \textcolor{red}{9 7 3}$ is a recurrent configuration for $\widehat{G}_{(4,\textcolor{olive}{3}),(\textcolor{red}{3},\textcolor{blue}{2})}$: indeed it is easy to check that $\sigma=\overline{1\! 0} 9 7 6 5 3 2\overline{1\!1} 8 41\overline{1\! 2}$ verifies the recurrence of $\kappa$ (cf.\ Example~\ref{ex:parking_word}).
\end{example}
\begin{remark}\label{rem:recurrence_definition}
	It is well known (see e.g.\ \cite[Theorem~2.4]{ADDL_two_op}) that the condition for $\kappa$ to be recurrent is equivalent to say that starting from $\phi_0(\kappa)$ there is no proper (possibly empty) subset $A$ of $[n]$ such that toppling all the vertices of $A$ brings $\phi_0(\kappa)$ to a stable configuration.
\end{remark}

%If $\kappa_1, \kappa_2, \dots, \kappa_k$ form a sequence of configurations such that $\kappa_i$ is obtained from $\kappa_{i+1}$ by toppling vertex $v_{i}$ for all $i=1,2,\dots,k-1$, then we say that $v_1,v_2,\dots,v_{k-1}$ is the \emph{toppling word} of this sequence of topplings. 

\begin{definition}
	Given a recurrent configuration $\kappa$ of $G$, we define its \emph{level} as
	\[\lev(\kappa):=-|E_s(G)|+\sum_{i=1}^n \kappa(i)\]
	where $E_s(G)$ is the set of edges of $G$ that are not incident to the sink.
\end{definition}

It is well-known that $\lev(\kappa)\geq 0$, and there exists a recurrent configuration of level $0$ if $G$ is connected \cite{MerinoLopez}.
\begin{remark} \label{rmk:level_Gmunu}
	For $\widehat{G}_{\mu,\nu}$ with $|\mu|+|\nu|=n$ we have
	\[|E_s(\widehat{G}_{\mu,\nu})|=\binom{n}{2}-\sum_{i\geq 0}\binom{\nu_i}{2}.\]
\end{remark}
\begin{example} \label{ex:level}
	The configuration  $\kappa=3\overline{1\! 0}\, \overline{1\! 1}\, \overline{1\! 1} \textcolor{olive}{8 \overline{1\! 0}\, \overline{1\! 1}}\, \textcolor{blue}{\overline{1\! 0} 4} \textcolor{red}{9 7 3}$ for $\widehat{G}_{(4,\textcolor{olive}{3}),(\textcolor{red}{3},\textcolor{blue}{2})}$ has level
	\[\lev(\kappa)=-\binom{12}{2}+\binom{\textcolor{red}{3}}{2}+\binom{\textcolor{blue}{2}}{2}+97=35.\]
\end{example}

\section{Toppling algorithm and \texorpdfstring{$\del$}{delay}} \label{sec:algo}

Consider the sandpile on a graph $G$ with vertices $\{0\}\cup [n]$, where $0$ is the sink. Let $\kappa$ be a recurrent configuration of $G$. Consider Algorithm~\ref{alg:toppling}.


%
%\medskip
%
%INPUT: the graph $G$ and a recurrent configuration $\kappa$.
%
%- Step 0: topple the sink, i.e.\ compute $\phi_0(\kappa)$.
%
%- Loop: scanning all the nonsink vertices $i$ from $n$ to $1$ in decreasing order, check if the vertex $i$ is unstable: if it is unstable, topple it, otherwise move on to the next vertex.
%
%- Iterate the Loop until you toppled all the nonsink vertices.
%
%OUTPUT: the toppling word of the sequence of nonsink vertices in the order they have been toppled.

\noindent Before discussing the algorithm, let us look at an example.
\begin{example} \label{ex:algo}
	Consider again the configuration $\kappa$ from Example~\ref{ex:kappa_config}: in that example we actually computed the sequence of toppling given by the first iteration of the \textbf{for} loop of Algorithm~\ref{alg:toppling} applied to $\kappa$. We compute the second iteration of the \textbf{for} loop: \begin{align*}
	(\phi_{\overline{1\! 1}}\!\circ\!\phi_{2}\!\circ\!\phi_{3}\!\circ\!\phi_{5}\!\circ\!\phi_{6}\!\circ\!\phi_{7}\!\circ\! \phi_{9}\!\circ\!\phi_{\overline{1\! 0}}\!\circ\!\phi_0)(\kappa)&=\overline{1\! 2}6 7 7 \textcolor{olive}{\overline{1\! 7} 6 7} \textcolor{blue}{7 \overline{1\! 2}} \textcolor{red}{6 4 \overline{1\! 0}},\\
	(\phi_{8}\!\circ\!\phi_{\overline{1\! 1}}\!\circ\!\phi_{2}\!\circ\!\phi_{3}\!\circ\!\phi_{5}\!\circ\!\phi_{6}\!\circ\!\phi_{7}\!\circ\! \phi_{9}\!\circ\!\phi_{\overline{1\! 0}}\!\circ\!\phi_0)(\kappa)&=\overline{1\! 3}7 8 8 \textcolor{olive}{5 7 8} \textcolor{blue}{8 \overline{1\! 3}} \textcolor{red}{7 5 \overline{1\! 1}},\\
	(\phi_{4}\!\circ\!\phi_{8}\!\circ\!\phi_{\overline{1\! 1}}\!\circ\!\phi_{2}\!\circ\!\phi_{3}\!\circ\!\phi_{5}\!\circ\!\phi_{6}\!\circ\!\phi_{7}\!\circ\! \phi_{9}\!\circ\!\phi_{\overline{1\! 0}}\!\circ\!\phi_0)(\kappa)&=\overline{1\! 4}8 9 9 \textcolor{olive}{6 8 9} \textcolor{blue}{8 2} \textcolor{red}{8 6 \overline{1\! 2}},\\
	(\phi_{1}\!\circ\!\phi_{4}\!\circ\!\phi_{8}\!\circ\!\phi_{\overline{1\! 1}}\!\circ\!\phi_{2}\!\circ\!\phi_{3}\!\circ\!\phi_{5}\!\circ\!\phi_{6}\!\circ\!\phi_{7}\!\circ\! \phi_{9}\!\circ\!\phi_{\overline{1\! 0}}\!\circ\!\phi_0)(\kappa)&=\overline{1\! 5}9 \overline{1\! 0}\, \overline{1\! 0} \textcolor{olive}{7 9 \overline{1\! 0}} \textcolor{blue}{9 3} \textcolor{red}{8 6 2},
	\end{align*}
	and finally the third and last iteration of the \textbf{for} loop:
	\begin{align*}
	(\phi_{\overline{1\! 2}}\!\circ\!\phi_{1}\!\circ\!\phi_{4}\!\circ\!\phi_{8}\!\circ\!\phi_{\overline{1\! 1}}\!\circ\!\phi_{2}\!\circ\!\phi_{3}\!\circ\!\phi_{5}\!\circ\!\phi_{6}\!\circ\!\phi_{7}\!\circ\! \phi_{9}\!\circ\!\phi_{\overline{1\! 0}}\!\circ\!\phi_0)(\kappa)&=3\overline{1\! 0}\, \overline{1\! 1}\, \overline{1\! 1} \textcolor{olive}{8 \overline{1\! 0}\, \overline{1\! 1}}\, \textcolor{blue}{\overline{1\! 0} 4} \textcolor{red}{9 7 3}=\kappa.
	\end{align*}
	Hence, the output of Algorithm~\ref{alg:toppling} applied to $\kappa$ is the word $\overline{1\! 0} 9 7 6 5 3 2\overline{1\!1} 8 41\overline{1\! 2}$ (cf.\ Example~\ref{ex:parking_word} and Example~\ref{ex:verify_recurrence}).

\end{example}
\begin{algorithm}
	\caption{Toppling algorithm}\label{alg:toppling}
	\begin{algorithmic}
		\Require A graph $G$ and a recurrent configuration $\kappa$
		\Ensure The word of nonsink vertices in the order they have been toppled%\Comment{It will be $W\subseteq S\cup\{v\}$}
		\State Topple the sink, i.e.\ compute $\phi_0(\kappa)$
		\State Initialize the output word as empty
		\While{there are nonsink vertices that are untoppled}
		\For{$i$ going from $n$ to $1$ (in decreasing order)}
		\If{vertex $i$ is unstable}
		\State Topple vertex $i$
		\State Append $i$ to the output word
		\EndIf
		\EndFor
		\EndWhile
	\end{algorithmic}
\end{algorithm}

Observe that by construction the algorithm terminates: since $\kappa$ is recurrent,  $\phi_0(\kappa)$ is non-negative and at least one of the vertices adjacent to the sink is unstable; then every time we topple we stay non-negative, and since $\kappa$ is recurrent the process must go through all the nonsink vertices (otherwise we found a subset $A$ of nonsink vertices such that after we topple its vertices we are in a stable configuration, cf.\ Remark~\ref{rem:recurrence_definition}).

By construction the algorithm outputs a toppling sequence that verifies the recurrence of $\kappa$.
We can now define our new statistic on recurrent configurations.
\begin{definition}
	Let $\kappa$ be a recurrent configuration of $G$. For every $i\in [n]$, let $r_i(\kappa)$ be the number of \textbf{for} loop iterations in Algorithm~\ref{alg:toppling} that occurred before the one in which the vertex $i$ is toppled (so if $i$ is toppled in the first iteration, then $r_i(\kappa)=0$). Then we define the \emph{delay} of $\kappa$ as
	\[\del(\kappa):=\sum_{i=1}^nr_i(\kappa).\]
\end{definition}
\begin{remark}
	If $\sigma$ is the output of Algorithm~\ref{alg:toppling} applied to $\kappa$, then clearly
	\[\del(\kappa)=\maj(\sigma_n\sigma_{n-1}\cdots \sigma_1).\]
\end{remark}
\begin{example} \label{ex:delay}
	For the configuration $\kappa$ of Example~\ref{ex:kappa_config}, we got in Example~\ref{ex:algo} that Algorithm~\ref{alg:toppling} gives $\sigma=\overline{1\! 0} 9 7 6 5 3 2\overline{1\!1} 8 41\overline{1\! 2}$, so that $\del(\kappa)=\maj (\overline{1\! 2} 1 4 8 \overline{1\!1} 2 3 5 6 7 9 \overline{1\! 0})=1+5=6$. Indeed, looking at the computation of the algorithm, we find that the word $r_1(\kappa)r_2(\kappa)\cdots$ in this case is indeed $100100010012$, whose letters add up to $6$ (cf.\ Example~\ref{ex:parking_word}).
\end{example}

\section{Sorted recurrent configurations of \texorpdfstring{$\widehat{G}_{\mu,\nu}$}{Gmunu}} \label{sec:SortRec}
%\section{Sorted recurrent configurations of \texorpdfstring{$\widehat{G}_{\mu,\nu}$}{Gm,n}.} 



Consider the Young subgroup $\mathfrak{S}_\mu\times \mathfrak{S}_\nu$ of the symmetric group $\mathfrak{S}_n$ consisting of the permutations that preserve the components of $G_{\mu,\nu}$. We want to consider configurations ``modulo'' the natural action of $\mathfrak{S}_\mu\times \mathfrak{S}_\nu$ on the set of configurations. More precisely, a \emph{sorted configuration}\footnote{The relation with the general definition of \emph{sorted configuration} given in Section~\ref{sec:sandpile} is simply that we are picking a specific convenient element in each orbit.} of the sandpile on $\widehat{G}_{\mu,\nu}$ is a configuration $\kappa$ that is weakly decreasing inside each clique component of $\widehat{G}_{\mu,\nu}$ and weakly increasing inside each independent component of $\widehat{G}_{\mu,\nu}$: if $i,j\in K_{\mu_r}$ and $i<j$, then $\kappa(i)\leq \kappa(j)$; if $i,j\in I_{\nu_s}$ and $i<j$, then $\kappa(i)\geq \kappa(j)$.

\begin{example} \label{ex:sorted_recurrent_config}
	The configuration $\kappa=3\overline{1\! 0}\, \overline{1\! 1}\, \overline{1\! 1} \textcolor{olive}{8 \overline{1\! 0}\, \overline{1\! 1}}\, \textcolor{blue}{\overline{1\! 0} 4} \textcolor{red}{9 7 3}$ is a sorted recurrent configuration for $\widehat{G}_{(4,\textcolor{olive}{3}),(\textcolor{red}{3},\textcolor{blue}{2})}$ (recall that in our notation $\kappa=\kappa(n)\kappa(n-1)\cdots \kappa(1)$).
\end{example}

Let $\kappa$ be a sorted recurrent configuration of $\widehat{G}_{\mu,\nu}$. Let $\sigma\in \mathfrak{S}_n$ be the toppling word produced by Algorithm~\ref{alg:toppling} applied to $\kappa$.

For every independent component $I_{\nu_s}$ of $G_{\mu,\nu}$, we order its vertices in decreasing order, and if $v^{(s)}_j$ is the $j$-th vertex of $I_{\nu_s}$, we set \[\widetilde{\kappa}(v^{(s)}_j):=\kappa(v^{(s)}_j)+\nu_s-j.\]

\noindent For every vertex $v$ in a clique component $K_{\mu_r}$ we set
\[\widetilde{\kappa}(v):=\kappa(v).\]
%Given $\widehat{G}_{\mu,\nu}$, let $\widehat{G}_{\mu\sqcup \nu,\varnothing}$ be the labelled graph obtained from $\widehat{G}_{\mu,\nu}$ by turning its independent components into clique components, i.e.\ by adding all the missing edges. Naturally, we can define what is a sorted configuration for $\widehat{G}_{\mu\sqcup \nu,\varnothing}$ in the same way as we did for $\widehat{G}_{\mu,\nu}$. 
%\begin{lemma} \label{lem:indep_reduction}
%	If $\kappa$ is a sorted stable configuration for $\widehat{G}_{\mu,\nu}$, then $\widetilde{\kappa}$ is sorted stable for $\widehat{G}_{\mu\sqcup \nu,\varnothing}$. Moreover, if  $\sigma\in \mathfrak{S}_n$ is the toppling word produced by the algorithm in Section~\ref{sec:algo} applied to $\kappa$ on $\widehat{G}_{\mu,\nu}$, then $\sigma$ is also the toppling  toppling word produced by the algorithm in Section~\ref{sec:algo} applied to $\widetilde{\kappa}$ on $\widehat{G}_{\mu\sqcup \nu,\varnothing}$.
%\end{lemma}
%\begin{proof}
%	The statement about stability is clear, since for every $r$ the degree of the vertices in $I_{\nu_r}$ went up by $\nu_r-1$. The fact that if $\kappa$ is sorted, then $\widetilde{\kappa}$ is sorted is also straightforward. 
%	
%	About $\sigma$: let us focus on a given component. If we topple a vertex in a different component, the effect on the values on the vertices of our component is the same in $\widehat{G}_{\mu,\nu}$ and in $\widehat{G}_{\mu\sqcup \nu,\varnothing}$. If our given component is a clique component, then toppling one of its vertices is going to have the same effect in $\widehat{G}_{\mu,\nu}$ and in $\widehat{G}_{\mu\sqcup \nu,\varnothing}$ on the values on the vertices of our component.
%	
%	Suppose now that our given component is an independent component $I_{\nu_r}$, and suppose that until we reach it for the first time, the algorithm did exactly the same topplings in $\widehat{G}_{\mu,\nu}$ and in $\widehat{G}_{\mu\sqcup \nu,\varnothing}$: the key observation is that if the vertices of $I_{\nu_r}$ in decreasing order are $v_1,v_2,\dots,v_{\nu_r}$, then for every $i\in [\nu_r]$ we have
%	\[\deg_{\widehat{G}_{\mu,\nu}}(v_i)-\kappa(v_i)= \deg_{\widehat{G}_{\mu\sqcup \nu,\varnothing}}(v_i)-\widetilde{\kappa}(v_i)+i-1=n-\widetilde{\kappa}(v_i)+i-1.\]
%	So, from what we have said until now, $v_1$ is toppled in the first iteration of the Loop of the algorithm on $\kappa$ if and only if it is toppled in the first iteration of the Loop of the algorithm on $\widetilde{\kappa}$. Moreover, if $v_1$ is toppled in $\widehat{G}_{\mu\sqcup \nu,\varnothing}$ it increases by $1$ the values of the configuration on $v_2,v_3,\dots,v_{\mu_r}$, while it does not change the corresponding values in $\widehat{G}_{\mu\sqcup \nu,\varnothing}$: hence $v_2$ is toppled in $\widehat{G}_{\mu,\nu}$ if and only if it is toppled in $\widehat{G}_{\mu\sqcup \nu,\varnothing}$. If $v_2$ is toppled, then it increases by $1$ the values of the configuration on $v_3,v_4,\dots,v_{\mu_r}$, and so on. Iterating this reasoning we see that the algorithm produces indeed the same toppling word in the two situations.
%\end{proof}
%\begin{remark}
%Notice that (cf.\ Remark~\ref{rmk:level_Gmunu}) for a sorted recurrent configuration $\kappa$ of $\widehat{G}_{\mu,\nu}$ we have
%\begin{align*}
%\lev(\kappa) &=-|E_s(\widehat{G}_{\mu,\nu})|+\sum_{i=1}^n\kappa(i)\\
%&=-\binom{n}{2}+\sum_{i\geq 1}\binom{\nu_i}{2}+\sum_{i=1}^n\kappa(i)\\
%& = -\binom{n}{2}+\sum_{i=1}^n\widetilde{\kappa}(i)
%\end{align*}
%\end{remark}
\noindent For every $i\in [n]$, we set
\[u_{\sigma^{-1}(i)}:=\sigma^{-1}(i)+\widetilde{\kappa}(i)-n.\]
\begin{example} \label{ex:u}
	For the configuration $\kappa=3\overline{1\! 0}\, \overline{1\! 1}\, \overline{1\! 1} \textcolor{olive}{8 \overline{1\! 0}\, \overline{1\! 1}}\, \textcolor{blue}{\overline{1\! 0} 4} \textcolor{red}{9 7 3}$ in Example~\ref{ex:sorted_recurrent_config}, we found in Example~\ref{ex:algo} that Algorithm~\ref{alg:toppling} gives $\sigma=\overline{1\! 0} 9 7 6 5 3 2\overline{1\!1} 8 41\overline{1\! 2}$. Hence $\widetilde{\kappa}=3\overline{1\! 0}\, \overline{1\! 1}\, \overline{1\! 1} \textcolor{olive}{8 \overline{1\! 1}\, \overline{1\! 1}}\, \textcolor{blue}{\overline{1\! 1} 4} \textcolor{red}{\overline{1\! 1} 8 3}$, and the word $u:=u_1u_2\cdots$ is $011345365223$.
\end{example}

Given a permutation $\sigma=\sigma(1)\sigma(2)\cdots \sigma(n)$, we add $\sigma(0):=0$ in front of it, and we define its \emph{runs} as its maximal consecutive decreasing substrings. Now for every $i\in [n]$, we define $w_{\sigma^{-1}(i)}=w_{\sigma^{-1}(i)}(\sigma)$ as
\begin{align*}
	w_{\sigma^{-1}(i)}(\sigma) & :=\#\{\text{numbers in the same run of $i$ and larger than $i$}\}                                                       \\
	                           & \hspace{-2cm}+\#\{\text{numbers smaller than $i$ in the run immediately to the left of the one containing $i$}\}.
\end{align*}
\begin{example}\label{ex:w}
	The runs of $\sigma=\overline{1\! 0} 9 7 6 5 3 2\overline{1\!1} 8 4 1\overline{1\! 2}$ are separated by bars: $0| \overline{1\! 0} 9 7 6 5 3 2|\overline{1\!1} 8 4 1 | \overline{1\! 2}$, so that the word $w=w_1(\sigma)w_2(\sigma)\cdots $ is $123456776434$.
\end{example}

The following propositions characterize the sorted recurrent configurations of $\widehat{G}_{\mu,\nu}$.
\begin{proposition} \label{prop:recurrent_inequalities}
	Let $\kappa$ be a sorted recurrent configuration of $\widehat{G}_{\mu,\nu}$. Let $\sigma\in \mathfrak{S}_n$ be the toppling word produced by Algorithm~\ref{alg:toppling} applied to $\kappa$. Then for every $i\in [n]$
	\[0\leq u_{\sigma^{-1}(i)}< w_{\sigma^{-1}(i)}.\]
\end{proposition}
%\begin{proof}
%	By Lemma~\ref{lem:indep_reduction}, $\sigma$ is also the toppling word computed by the algorithm on $\widetilde{\kappa}$ in $\widehat{G}_{\mu\sqcup \nu,\varnothing}$.
%	
%	The first observation is that $u_{\sigma^{-1}(i)}$ is the value of the configuration on $i$ at the moment that we must topple $i$ (i.e.\ $\sigma^{-1}(i)$=\#$\{$vertices (including the sink) toppled before $i\}$ plus $\kappa(i)$) minus the degree of $i$ in $\widehat{G}_{\mu\sqcup \nu,\varnothing}$ (i.e.\ $n-\widetilde{\kappa}(i)+\kappa(i)$). Since we are toppling $i$ in the algorithm, this quantity must be $\geq 0$. 
%	
%	The second observation is that $w_{\sigma^{-1}(i)}$ is the number of vertices toppled during the algorithm between the time we checked $i$ in the last iteration of the Loop before the one in which we toppled $i$ and the time we actually toppled $i$: hence, because of the previous observation, this number is clearly strictly greater than $u_{\sigma^{-1}(i)}$. This completes the proof of the proposition.
%\end{proof}
%
%We have a converse of the previous proposition.
\begin{proposition}
	Let $\kappa$ be a sorted stable configuration of $\widehat{G}_{\mu,\nu}$, and let $\sigma\in \mathfrak{S}_n$ be such that for every $i\in [n]$
	\[0\leq u_{\sigma^{-1}(i)}< w_{\sigma^{-1}(i)}.\]
	Then $\kappa$ is recurrent and $\sigma$ is the toppling word given by Algorithm~\ref{alg:toppling} applied to $\kappa$.
\end{proposition}
%\begin{proof}
%	To show that $\kappa$ is recurrent it is enough to show that, after we topple the sink, if we topple the nonsink vertices in the order given by $\sigma$, then at any time we have a non-negative configuration. But combining the two observations in the proof of Proposition~\ref{prop:recurrent_inequalities}, this is precisely what the inequality $0\leq u_{\sigma^{-1}(i)}$ guarantees.
%	
%	Using again those observations, the inequality $u_{\sigma^{-1}(i)}< w_{\sigma^{-1}(i)}$ guarantees that, after toppling the sink,  following the toppling sequence $\sigma$ the vertex $i$ does not become unstable in a Loop iteration of the algorithm before the one is supposed to topple. This shows that $\sigma$ is indeed the output of the algorithm, completing the proof of the proposition.
%\end{proof}
\noindent We omit the proofs, but an instance can be checked by comparing Examples~\ref{ex:u}~and~\ref{ex:w}.

\section{Bijection with parking functions}

We now provide a bijection between recurrent sorted configurations of $\widehat{G}_{\mu,\nu}$ and the parking functions in $\PF(\mu;\nu)$.

%Let $\uparrow\!\! K_{\mu_i}$ be the word consisting of the vertices of the component $K_{\mu_i}$ of $G_{\mu,\nu}$ in increasing order: for example $\uparrow\!\! K_{\mu_1}=(n-\mu_1+1) (n-\mu_1+2) \cdots (n-1) n$.
%Similarly, let $\downarrow\!\! I_{\nu_j}$ be the word consisting of the vertices of the component $I_{\nu_j}$ of $G_{\mu,\nu}$ in decreasing order: for example $\downarrow\!\! I_{\nu_1}=\nu_1 (\nu_1-1)\cdots 21$.
%
%Consider the shuffle 
%\[ \mathsf{W}(\mu;\nu)=\uparrow\!\! K_{\mu_1} \shuffle \uparrow\!\! K_{\mu_2} \shuffle\cdots \shuffle \uparrow\!\! K_{\mu_{\ell(\mu)}} \shuffle  \downarrow\!\! I_{\nu_1} \shuffle \downarrow\!\! I_{\nu_1} \shuffle \cdots \shuffle \downarrow\!\! I_{\nu_{\ell(\nu)}}.\]
%
%Let $\mathsf{PF}(\mu,\nu)$ be the set of parking functions whose parking word lies in $\mathsf{W}(\mu,\nu)$. 

Let $\mathsf{SortRec}(\mu,\nu)$ be the set of sorted recurrent configurations of $\widehat{G}_{\mu,\nu}$.
Define the function $\Phi:\mathsf{SortRec}(\mu,\nu)\to \mathsf{PF}(\mu,\nu)$ in the following way: given $\kappa\in \mathsf{SortRec}(\mu,\nu)$, in the notation of Section~\ref{sec:SortRec}, we set $\Phi(\kappa)$ to be the (unique) parking function of size $n=|\mu|+|\nu|$ such that the label $i$ occurs in column $n-\widetilde{\kappa}(i)$ (we number the columns increasingly from left to right) for every $i\in [n]$.
\begin{example} \label{ex:bijection}
	The parking function $D\in \PF((4,3);(3,2))$ in Figure~\ref{fig:LDP_config} is the image $\Phi(\kappa)$ of the configuration $\kappa$ in Example~\ref{ex:kappa_config} ($\widetilde{\kappa}$ is computed in Example~\ref{ex:u}).
\end{example}

We can finally state the main result of our article.
\begin{theorem}
	The map $\Phi$ is a well-defined bijection such that $\area(\Phi(\kappa))=\lev(\kappa)$ and such that the $\sigma$ obtained from the Algorithm~\ref{alg:toppling} applied to $\kappa$ equals the pmaj word of $\Phi(\kappa)$, so that $\pmaj(\Phi(\kappa))=\del(\kappa)$.
\end{theorem}
Now Theorem~\ref{thm:main} is an immediate consequence of this result combined with Theorem~\ref{thm:shuffle_pmaj}. It can be checked in the instance of Example~\ref{ex:bijection} (cf.\ Examples~\ref{ex:algo},~\ref{ex:delay},~\ref{ex:parking_word},~\ref{ex:area}~and~\ref{ex:level}).

%The proof of our theorem relies on \cite[Theorem~44]{LoehrRemmel_pmaj}.
%\begin{proposition}
%	The map $\Phi$ is a well-defined bijection.
%\end{proposition}
%\begin{proof}
%	We need to show (1) that the map $\Phi$ is well defined, i.e.\ that our definition of $\Phi(\kappa)$ actually gives a parking function in $\mathsf{PF}(\mu,\nu)$, and (2) that $\Phi$ is bijective.
%	
%	For (1): let $\kappa\in \mathsf{SortRec}(\mu,\nu)$, and let $\sigma\in \mathfrak{S}_n$ be the toppling word given by the algorithm of Section~\ref{sec:algo} applied to $\kappa$. Recall the definition of the vector $u=u(\sigma):=(u_1,u_2,\dots,u_n)$, i.e. for every $i\in [n]$
%	\[ \sigma^{-1}(i)-u_{\sigma^{-1}(i)} =n-\widetilde{\kappa}(i).\]
%	
%	Hence we can see $\Phi$ as the map sending the pair $(\sigma,u)$, which by Proposition~\ref{prop:recurrent_inequalities} satisfies $0\leq u_i<w_i(\sigma)$ for every $i\in [n]$, into the labelled Dyck path whose label $i$ occurs in column $\sigma^{-1}(i)-u_{\sigma^{-1}(i)}$.
%	
%	Now we can apply Theorem~44 in [Loehr-Remmel ``Conjectured Combinatorial Models...'' Electr. J. Comb.], which we restate in our notation.\footnote{To match the notation in [LR????], one should keep in mind that the ingredients of the occurring formulas are computed on the reverse word $\sigma(n)\sigma(n-1)\cdots \sigma(1)$, so that the positions $\sigma^{-1}(i)$ get complemented to $n+1$, etc.; also, the map $\Phi$ is called ``$G$''.}
%	\begin{theorem}[Loehr-Remmel bijection] \label{thm:Loehr_Remmel}
%		Via the map $\Phi$ the pairs $(\sigma,u)$ with $0\leq u_j<w_j(\sigma)$ for every $j\in [n]$ are sent bijectively onto the elements of $\mathsf{PF}(n)$, in such a way that $\sum_{j=1}^n(j-u_j)$ goes into area and $\sigma$ is the pmaj word of the image, which implies that $\mathsf{maj}(\sigma_{n}\sigma_{n-1}\cdots \sigma_1)$ goes into pmaj.
%	\end{theorem}
%	It remains to observe that, since $\kappa$ is sorted (recall the definition at the end of Section~\ref{sec:graphs}), by construction the algorithm applied to $\kappa$ produces a toppling word $\sigma$ in $\mathsf{W}(\mu;\nu)$.
%\end{proof}
%In fact the above argument, using Theorem~\ref{thm:Loehr_Remmel}, provides the following immediate corollary.
%\begin{corollary}
%	The map $\Phi$ is a well-defined bijection that sends $\sum_{j=1}^n(n-\widetilde{\kappa}(i))$ into area and the $\sigma$ obtained from the algorithm from Section~\ref{sec:algo} applied to $\kappa$ into the pmaj word of the image, which implies that $\mathsf{maj}(\sigma(n)\sigma(n-1)\cdots \sigma(1))$ goes into pmaj.
%\end{corollary}
%
%
%TO BE CONTINUED...



%\begin{figure}
%\centering
%\includegraphics[width=0.5\textwidth]{plot}
%\caption{A plot of a function.}
%\label{fig:plot}
%\end{figure}



%\acknowledgements{Grants...}

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