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

%\newtheorem{thm}{Theorem}
%\newtheorem{lem}{Lemma}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\usepackage{tikz}
\usepackage{tikz-cd}
\usetikzlibrary{calc}
\usepackage{blkarray}
\usepackage{graphicx,float,subfigure}

\usepackage{lipsum}

\DeclareMathOperator{\SL}{SL}
\DeclareMathOperator{\Read}{\mathsf{Read}}
\DeclareMathOperator{\adj}{\mathsf{adj}}
\DeclareMathOperator{\sgn}{\mathsf{sgn}}
\DeclareMathOperator{\wt}{\mathsf{wt}}
\DeclareMathOperator{\area}{\mathsf{area}}
\DeclareMathOperator{\level}{\mathsf{level}}
\DeclareMathOperator{\tp}{\mathsf{tp}}
\DeclareMathOperator{\bounce}{\mathsf{bounce}}
\DeclareMathOperator{\dinv}{\mathsf{dinv}}
\DeclareMathOperator{\diags}{\mathsf{diags}}
\DeclareMathOperator{\flats}{\mathsf{flats}}
\DeclareMathOperator{\NSP}{NSP}
\DeclareMathOperator{\NDP}{NDP}
\DeclareMathOperator{\LNDP}{LNDP}
\DeclareMathOperator{\SLNDP}{SLNDP}
\DeclareMathOperator{\AD}{AD}
\DeclareMathOperator{\ASM}{ASM}
\DeclareMathOperator{\T}{\mathcal{T}}
\newcommand{\Q}{\mathbb Q}
\newcommand{\N}{\mathbb N}
\newcommand{\R}{\mathbb R}
\newcommand{\F}{\mathbb F}
\newcommand{\Z}{\mathbb Z}
\newcommand{\C}{\mathbb C}

%% define your title in the usual way
\title[Domino Tilings and Macdonald Polynomials]{Domino Tilings and Macdonald Polynomials}

%% 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[Ian Cavey and Yi-Lin Lee]{\texorpdfstring{
Ian Cavey \thanks{\href{mailto:cavey@illinois.edu}{cavey@illinois.edu}}\addressmark{1} 
%
and Yi-Lin Lee \thanks{\href{mailto:yillee@iu.edu}{yillee@iu.edu}}\addressmark{2}
}{
Ian Cavey  
%
and Yi-Lin Lee 
}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, University of Illinois Urbana-Champaign, Urbana, IL, USA \\ \addressmark{2}Department of Mathematics, Indiana University, Bloomington, IN, USA}

%% 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{
There is a general bijection between domino tilings of planar regions in the square lattice and families of non-intersecting Schr\"oder-like paths contained in the region. Motivated by this bijection, we study domino tilings of certain regions $R_\lambda$, indexed by partitions $\lambda$, weighted according to generalized area and dinv statistics. These statistics arise from the $q,t$-Catalan combinatorics and Macdonald polynomials. We present a formula for the generating polynomial of these domino tilings in terms of the Bergeron--Garsia nabla operator. When $\lambda = (n^n)$ is a square shape, domino tilings of $R_\lambda$ are equivalent to those of the Aztec diamond of order $n$. In this case, we give a new product formula for the resulting polynomials by domino shuffling and its connection with alternating sign matrices. In particular, we obtain a combinatorial proof of the joint symmetry of the generalized area and dinv statistics.
}

%% 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{Alternating sign matrices; domino tilings; domino shuffling; nabla operator; $q,t$-Catalan combinatorics; symmetric functions.}

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

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

\begin{document}

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




\section{Introduction}

The study of Macdonald polynomials has produced many interesting combinatorial objects, often expressed as weighted sums over sets of lattice paths. Perhaps the most famous and well-studied such objects are the $q,t$-Catalan numbers introduced by Garsia and Haiman \cite{GH96}, which can be defined combinatorially as the sum over Dyck paths weighted by the $\area$ and $\dinv$ statistics (see the book \cite{H08} and the references therein). Among the many generalizations of the $q,t$-Catalan numbers are the extension to 
{\parfillskip=0pt \par} \noindent
Schr\"oder paths defined by Egge, Haglund, Killpatrick, and Kremer \cite{EHKK03}, and to nested families of Dyck paths due to Loehr and Warrington \cite{LW08}. All of these objects have natural interpretations in terms of the \textit{nabla operator} $\nabla$, introduced by Bergeron and Garsia \cite{BG99}, on the ring of symmetric functions $\Lambda$ in the countably infinite set of variables $\{x_i\}_{i \geq 1}$ with coefficients in the field of rational functions $\Q(q,t)$.

The nabla operator $\nabla$ is the unique $\Q(q,t)$-linear map on $\Lambda$ such that $
\nabla(\tilde{H}_\mu)=q^{n(\mu')}t^{n(\mu)}\tilde{H}_\mu$ for all $\mu$, where $\tilde{H}_\mu$ is the modified Macdonald polynomial studied by Macdonald \cite{Mac88} and appearing in Garsia and Haiman's work on diagonal harmonics \cite{GH96}, $\mu'$ is the conjugate of a partition $\mu$, and $n(\mu) =\sum (i-1)\mu_i$. One can obtain interesting combinatorial objects by applying $\nabla$ to elements of some basis of $\Lambda$ and expanding the result in terms of another basis or, equivalently, taking the Hall inner product $\langle \cdot,\cdot \rangle$ with an element of the dual basis. Some of the classical bases of $\Lambda$ are $m_{\mu}$ (monomial), $e_{\mu}$ (elementary), $h_{\mu}$ (complete homogeneous) and $s_{\mu}$ (Schur), each are indexed by partitions $\mu$. Note that $s_{(n)} = h_n$ and $s_{(1^n)} = e_n$.

We list some of these combinatorial objects in \Cref{tab.nabla}. For other formulas of this kind, see \cite{LW08}. 
%
\begin{table}[htb!]
\centering
\begin{tabular}{c|c|c}
  \hline
  Algebraic Object & Combinatorial Model & Special Case of \Cref{thm:MacdonaldIntro} \\
  \hline
  $\langle \nabla(e_n),e_n\rangle$ & the $q,t$-Catalan numbers \cite{GH96,GH02} & $\lambda = (1^n)$ and $d=0$\\
  \hline
  $\langle \nabla(e_n),h_d e_{n-d}\rangle$ & the $q,t$--Schr\"oder numbers \cite{EHKK03,Hag04} & $\lambda = (1^n)$ \\
  \hline
  $\sgn(\lambda)\langle \nabla(s_{\lambda}),e_{n}\rangle$ & the $\lambda$-family of Dyck paths \cite{LW08} & $d=0$\\
  \hline
\end{tabular}
\caption{Some combinatorial objects 
 of the nabla operator.}\label{tab.nabla}
\end{table}
%

Given a partition $\lambda = (\lambda_1,\dots,\lambda_\ell)$, Loehr and Warrington \cite{LW08} consider strictly nested collections of Dyck paths with starting points $(0,0),(1,1),(2,2),\dots$, and ending points determined by $\lambda$ in the following way. Decompose the Ferrer's diagram of $\lambda$ into border strips and label each column with the length of the strip whose rightmost box is in that column (and with label $0$ if there is no such strip) as shown in \Cref{fig:lambda} for the partition $\lambda = (4,4,3,3,3,1)$. Let $n_0,\dots,n_k$ denote these labels read from right to left where $k=\lambda_1-1$. A \textit{$\lambda$-family of Dyck paths} is a $(k+1)$-tuple $\pi = (\pi_0,\dots,\pi_k)$ of pairwise non-intersecting lattice paths, where each $\pi_i$ is a lattice path consisting of unit north $(0,1)$ and east $(1,0)$ steps that lies weakly above the diagonal $y=x$, starts at $(i,i)$, and ends at $(i+n_i,i+n_i)$. 

\begin{figure}[ht]
    \centering
    \subfigure[]{\label{fig:lambda}\includegraphics[height=0.2\textwidth]{443331.eps}}
    \hspace{10mm}
    \subfigure[]{\label{fig:paths}\includegraphics[height=0.2\textwidth]{paths.eps}}
    \hspace{10mm}
    \subfigure[]{\label{fig:tilingpaths}\includegraphics[height=0.2\textwidth]{tilingpath.eps}}
    \caption{(a) The decomposition of $\lambda = (4,4,3,3,3,1)$ into border strips of lengths $(n_0,n_1,n_2,n_3)=(9,6,0,3)$. (b) A $\lambda$-family of Schr\"oder paths for $\lambda = (4,4,3,3,3,1)$ with 5 diagonal steps. (c) The region $R_\lambda$ for $\lambda = (4,4,3,3,3,1)$ with the domino tiling that corresponds to the $\lambda$-family in \Cref{fig:paths}.}
\end{figure} 

In this extended abstract, we present the Schr\"oder generalization of these nested families of paths. Using the same notation as for the Dyck paths, a $\lambda$\textit{-family of Schr\"oder paths} is a $(k+1)$-tuple $\pi = (\pi_0,\dots,\pi_k)$ of pairwise non-intersecting lattice paths, where each $\pi_i$ is a lattice path consisting of unit north $(0,1)$, east $(1,0)$, and diagonal $(1,1)$ steps that lies weakly above the diagonal $y=x$, starts at $(i,i)$, and ends at $(i+n_i,i+n_i)$. \Cref{fig:paths} shows a $\lambda$-family of paths for the partition in \Cref{fig:lambda}. Let $\mathcal{S}_\lambda$ denote the set of all $\lambda$-families of Schr\"oder paths and $\mathcal{S}_{\lambda,d}$ the set of all $\lambda$-families of Schr\"oder paths with $d$ total diagonal steps among all the paths. 

We define $\area$ and $\dinv$ statistics for $\mathcal{S}_{\lambda,d}$ (see \Cref{sec:statistics}) that specialize to the corresponding statistics in the cases of $\lambda$-families of Dyck paths, (single) Schr\"oder paths, and (single) Dyck paths. Our first result expresses $\lambda$-families of Schr\"oder paths weighted according to these statistics in the language of Macdonald polynomials. In the following formula $\sgn(\lambda) = \pm 1$ is a sign factor introduced by Loehr and Warrington whose definition is recalled in \Cref{sec:statistics}.
 
\begin{theorem}\label{thm:MacdonaldIntro}
    For any partition $\lambda \vdash n$ and $0\leq d\leq n$,
    \begin{equation}\label{eq.thm1}
        \sum_{\pi\in \mathcal{S}_{\lambda,d}} q^{\area(\pi)}t^{\dinv(\pi)} = \sgn(\lambda) \langle \nabla(s_\lambda),h_d \, e_{n-d} \rangle.
    \end{equation}
\end{theorem}

\Cref{thm:MacdonaldIntro} is the common generalization of several formulas relating $q,t$-Catalan combinatorics to Macdonald polynomials through the nabla operator (\Cref{tab.nabla}). 

Our present interest in these polynomials is due to a general bijection \cite{LRS01} between domino tilings of regions $R$ on the square lattice and families of non-intersecting 
{\parfillskip=0pt \par} \noindent
Schr\"oder-like paths contained in $R$ (see \Cref{sec:bijection}). A \textit{domino tiling} of $R$ is a covering of $R$ using dominoes (union of two unit squares sharing an edge) without gaps or overlaps. Let $\T(R)$ be the set of domino tilings of $R$. Motivated by this bijection, we define below a region $R_\lambda$ whose domino tilings correspond to $\mathcal{S}_\lambda$. This region is related to the Aztec diamond introduced by Elkies, Kuperberg, Larsen, and Propp \cite{EKLP1, EKLP2} in 1992. One goal of this paper is to establish a bridge between the rich combinatorics surrounding domino tilings of the Aztec diamond (and similar regions) and $q,t$-Catalan combinatorics. 

The \textit{Aztec diamond} of order $n$, denoted by $\AD_{n}$, is the union of all unit squares inside the diamond-shaped region $\{(x,y) \in \mathbb{R}^2 : |x|+|y| \leq n+1 \}$. Given a partition $\lambda$ decomposed into border strips of lengths $(n_0,\dots,n_k)$ as above, $R_\lambda$ is defined as a certain subset of the upper-half, $y\geq 0$, of $\AD_{n_0+1}$. Equip the Aztec diamond with the checkerboard coloring so that the unit squares along the top right side are colored black. Label the boxes in the bottom row of the top half of the Aztec diamond $0,0,1,1,2,2,\dots,n_0,n_0$ from left to right. The region $R_\lambda$ is defined by removing from this region the white boxes in the bottom row labeled $0,1,\dots,k$ and the black boxes in the bottom row labeled $i+n_i$ for each $i=0,\dots,k$. \Cref{fig:tilingpaths} shows the domino tiling of $R_\lambda$ corresponding to the $\lambda$-family in \Cref{fig:paths}.

Passing through this bijection \cite{LRS01}, we define statistics $\area$, $\dinv$, and $\diags$ directly on domino tilings of $R_\lambda$ that agree with the corresponding statistics on $\mathcal{S}_\lambda$ (see \Cref{sec:statistics}). We then study the following weighted sums over domino tilings in the set $\T(R_\lambda)$ motivated by \Cref{thm:MacdonaldIntro}:
%
\begin{equation}\label{eq.P-polynomial}
    P_\lambda(z;q,t) := \sum_{T\in \T(R_\lambda)} z^{\diags(T)}q^{\area(T)}t^{\dinv(T)} = \sgn(\lambda)\sum_{d=0}^{n}z^d \langle \nabla(s_\lambda),h_d \, e_{n-d} \rangle.
\end{equation}
%
An immediate consequence of \Cref{thm:MacdonaldIntro} is the symmetry of $P_\lambda(z;q,t)$ in the variables $q$ and $t$.
 
\begin{corollary}\label{cor:symmetry}
    For all partitions $\lambda$, we have $P_\lambda(z;q,t)=P_\lambda(z;t,q)$.
\end{corollary}
 
As is often the case in $q,t$-Catalan combinatorics, the joint symmetry of the $\area$ and $\dinv$ statistics remains mysterious combinatorially, but we give a direct combinatorial proof of \Cref{cor:symmetry} for the special cases when $\lambda =(n^n)$.

A special role is played by the partitions of square shape, $\lambda =(n^n)$, in which case the region $R_{\lambda}$ reduces to $\AD_n$. For convenience, we write 
%
\begin{equation}\label{eq.ADdef}
    \AD_n(z;q,t)= P_{(n^n)}(z;q,t).
\end{equation}
%
Surprisingly, the combinatorics of alternating sign matrices and domino shuffling introduced in \cite{EKLP1,EKLP2} interact well with the $\area$, $\dinv$ and $\diags$ statistics coming from $q,t$-Catalan combinatorics. We use this machinery to prove the following product formula for $\AD_n(z;q,t)$. 
 
\begin{theorem}\label{thm:introAD}
    When $\lambda = (n^n)$ is a partition of square shape, we have the product formula
    \begin{equation}\label{eq.ADproduct}
        \AD_n(z;q,t) = (qt)^{n^2(n-1)/2}\prod_{i,j\geq0 \text{ and }i+j<n}(z+q^it^j).
    \end{equation}
\end{theorem}
 
Specializing all variables to $1$, we recover the well-known fact that the number of domino tilings of $\AD_n$ is $2^{n(n+1)/2}.$ This product formula is similar to the formula given in \cite{EKLP1,EKLP2} weighted according to different statistics. In fact, our statistic $\diags(T)$ is the same as their statistic $v(T)$ counting vertical dominoes up to a simple change of variables. Our $\area(T)$ statistic is similar to their rank statistic $r(T)$, although they are not the same, and our $\dinv(T)$ statistic appears to be completely new. Since our proof of \Cref{thm:introAD} is entirely combinatorial and \eqref{eq.ADproduct} is evidently symmetric in $q$ and $t$, we obtain a direct proof (not using \Cref{thm:MacdonaldIntro}) of the $q,t$-symmetry in \Cref{cor:symmetry} for $\lambda = (n^n)$.

This extended abstract is organized as follows. In \Cref{sec:prelim}, we define statistics on $\lambda$-families of Schr\"oder paths and domino tilings, and state some background information on related combinatorics of alternating sign matrices and domino shuffling. In \Cref{sec:Mac}, we indicate how \Cref{thm:MacdonaldIntro} can be obtained from the Loehr--Warrington formula \cite{LW08,BHMPS,KO24}. In \Cref{sec:pfAD}, we discuss the special case when $\lambda=(n^n)$.

\section{Preliminaries}\label{sec:prelim}

\subsection{Statistics on Families of Nested Schr\"oder Paths}\label{sec:statistics}

We define $\area$, $\dinv$, and $\diags$ statistic statistics for $\lambda$-families of Schr\"oder paths building upon the statistics for Schr\"oder paths and $\lambda$-families of Dyck paths, see \cite{EHKK03} and \cite{LW08} for their detailed original definitions.

Let $\lambda = (\lambda_1,\dots,\lambda_\ell)$ be a partition and $\pi = (\pi_0,\dots,\pi_k)$ a $\lambda$-family of Schr\"oder paths $\mathcal{S}_{\lambda}$, where $k=\lambda_1-1$. For each path $\pi_j$ in $\pi$, we define $\diags(\pi_j)$ to be the number of diagonal $(1,1)$ steps in the path $\pi_j$, and set $\diags(\pi) = \sum_j \diags(\pi_j)$. The $\lambda$-family $\pi$ in \Cref{fig:paths} has $\diags(\pi) = 2+2+1=5$.

A triangle with vertices $(c, d)$, $(c+1,d)$ and $(c+1,d+1)$ for some integers $c,d$ is called an \emph{area triangle}. The \emph{area} of a path $\pi_j$, $\area(\pi_j)$, is the total number of area triangles below $\pi_j$ and above the diagonal $y=x$, and set $\area(\pi) = \sum_j \area(\pi_j)$. The $\lambda$-family in \Cref{fig:paths} has area $27+11+0=38$.

To define the $\dinv$ statistic, we designate certain pairs of steps in the paths $\pi$ to be \emph{dinv pairs} and record the total number of such pairs. As shown in \Cref{fig:dinvpairs}, dinv pairs are the four types of pairs of north or diagonal steps in some, possibly different, paths in $\pi$. As in \cite{LW08}, the \emph{dinv adjustment} of $\lambda$ is $\adj(\lambda) = \sum_{j:n_j>0}(\lambda_1-1-j)$, and the \emph{sign} of $\lambda$ is $\sgn(\lambda) = (-1)^{\adj(\lambda)}$. The $\dinv$ of a $\lambda$-family $\pi$ is defined to be the quantity
\begin{equation}\label{eq.defdinv}
    \dinv(\pi) = \adj(\lambda) + \#\{ \text{dinv pairs in } \pi \}.
\end{equation}
Our running example in \Cref{fig:paths} has $\sgn(\lambda) = -1$ and $\dinv(\pi) = 5+29 = 34$. 
%
\begin{figure}[hbt!]
    \centering
    \includegraphics[scale=0.12]{dinvpairs0.eps}
    \caption{The four types of dinv pairs. The dotted lines indicate the alignment of the pairs of edges relative to some translation of the diagonal $y=x$.}
    \label{fig:dinvpairs}
\end{figure}
%


\subsection{Bijection with Domino Tilings and Statistics}\label{sec:bijection}

In general, there is a bijection \cite{LRS01} between domino tilings of a region $R$ on the square lattice and families of non-intersecting paths contained in $R$. In particular, domino tilings of $R_\lambda$ are in bijection with $\lambda$-families of Schr\"oder paths. This bijection is described below.

Given a domino tiling of $R_\lambda$, the corresponding family of paths is given by decorating each of the four types of dominoes that can appear relative to the checkerboard coloring with a (possibly empty) path step as shown in \Cref{fig:key}. Regarding each of these path steps as oriented from left to right, each step enters a domino in a black square and exits a domino in a white square. The union of all of these individual path steps therefore forms a collection of non-intersecting paths in $R_\lambda$. The starting points of these paths are the black squares in $R_\lambda$ such that the white square immediately to its left is not in $R_\lambda$ and the ending points of these paths are the white squares in $R_\lambda$ such that the black square immediately to its right is not in $R_\lambda$. 
%
\begin{figure}[hbt!]
    \centering
    \includegraphics[height=0.07\textwidth]{dominobij.eps}
    \caption{The four types of dominoes and their corresponding path steps.}
    \label{fig:key}
\end{figure} 
%

One can view the resulting family of paths as $\lambda$-family of Schr\"oder paths by a change of coordinates that amounts to rotating $45^\circ$ counterclockwise and rescaling so that the longest path begins at $(0,0)$ and ends at $(n_0,n_0)$; see \Cref{fig:paths,fig:tilingpaths}. Conversely, given a $\lambda$-family of Schr\"oder paths, we can undo the affine transformation above to obtain a family of paths in $R_\lambda$. We then cover $R_{\lambda}$ with dominoes based on the four configurations in \Cref{fig:key}.

Let $T$ be a domino tiling of $R_{\lambda}$ and $U(T)$ (resp., $H(T)$) be the collection of all vertical (resp., horizontal) dominoes in which the bottom (resp., left) unit square is colored black. These two particular types of domino correspond to the up and diagonal steps of its $\lambda$-family of Schr\"oder paths. The $\diags$ statistic is given by $\diags(T) = |H(T)|$.

Recall that the $\area$ statistic counts the total number of area triangles of each path. This can be expressed as a sum over the ``area'' of each vertical domino in $U(T)$ and horizontal domino in $H(T)$, where each $\area$ contribution depends on the $y$-coordinate of that domino. To be more precise, for a vertical domino $d_u \in H(T)$ and a horizontal domino $d_h \in U(T)$ whose bottom edge lies on $y=i$, define $\area(d_u) = \area(d_h) = i$. Then the $\area$ statistic can be reinterpreted as
\begin{equation}\label{eq.def-domino-area}
    \area(T) = \sum_{d_u \in U(T)} \area(d_u) + \sum_{d_h \in H(T)} \area(d_h).
\end{equation}
%
\begin{figure}[hbt!]
    \centering
    \includegraphics[height=0.1\textwidth]{dominopairsfpsac.eps}
    \caption{The four types of domino pairs. The dotted lines indicate the alignment of dominoes.}
    \label{fig:dominopairs}
\end{figure}
%

The $\dinv$ pairs in \Cref{fig:dinvpairs} are equivalent to the domino pairs shown in \Cref{fig:dominopairs}. So, the $\dinv$ statistic is given by     \begin{equation}\label{eq.def-domino-dinv}
    \dinv(T) = \adj(\lambda) + \#\{ \text{domino pairs in } T \}.
\end{equation}

%================================


\subsection{Alternating Sign Matrices and Aztec Diamonds}\label{sec:ASMAD}

An alternating sign matrix (ASM) of order $n$ is an $n \times n$ matrix with entries $0, 1$ or $-1$ such that all row and column sums are equal to $1$ and the non-zero entries alternate in sign in each row and column. Mills, Robbins, and Rumsey introduced them \cite{MRR83} in the early 1980s. The connection between ASMs and domino tilings of the Aztec diamond was initially discovered in \cite{EKLP1, EKLP2}. They showed that the number of domino tilings of the Aztec diamond can be expressed as a weighted enumeration of ASMs. This connection was made explicit later by Ciucu \cite[Section 2]{Ciucu96}, the idea is stated as follows. 

For two integers $x$ and $y$, we say a (lattice) point $(x,y)$ in $\AD_n$ is \emph{even} (resp., \emph{odd}) if $x+y$ and $n$ have the same (resp., opposite) parity. For each domino tiling $T$ of $\AD_n$, we first add four unit segments connecting points $(0,n)$ with $(0,n+1)$, $(-n,0)$ with $(-(n+1),0)$, $(0,-n)$ with $(0,-(n+1))$, and $(n,0)$ with $(n+1,0)$. Second, we define the maps $M_e$ and $M_o$ below.
%
\begin{equation}\label{eq.ASMAD}
    M_e(v_e) = \begin{cases}
         1 & \text{if $\deg(v_o)=4$,} \\
         0 & \text{if $\deg(v_o)=3$,} \\
        -1 & \text{if $\deg(v_o)=2$,}
          \end{cases} \text{\quad and \quad} 
    M_o(v_o) = \begin{cases}
         1 & \text{if $\deg(v_e)=2$,} \\
         0 & \text{if $\deg(v_e)=3$,} \\
        -1 & \text{if $\deg(v_e)=4$,}
          \end{cases}
\end{equation}
%
where $\deg(\cdot)$ is the degree of an even point $v_e$ or odd point $v_o$ by viewing a domino tiling as a graph. Finally, the image of all even (resp., odd) points under the map $M_e$ (resp., $M_o$) forms a square array (which is an ASM) of size $n$ (resp., $n+1$); see \Cref{fig:ASMAD1,fig:ASMAD2}. We write $M_e(T)$ and $M_o(T)$ for such ASMs that correspond to $T$.
%
\begin{figure}[ht]
    \centering
    \subfigure[]{\label{fig:ASMAD1}\includegraphics[height=0.25\textwidth]{ASMAD1.eps}}
    \hspace{10mm}
    \subfigure[]{\label{fig:ASMAD2}\includegraphics[height=0.25\textwidth]{ASMAD2.eps}}
    %\hspace{2mm}
    \caption{(a) An example of $M_e(T)$ where $T \in \T(\AD_3)$, even points are marked in red. (b) An example of $M_o(T^{\prime})$ where $T^{\prime} \in \T(\AD_4)$, odd points are marked in red.}
\end{figure}
%


\subsection{Domino Shuffling}\label{sec:introshuffling}

Recall that we equip $\AD_n$ the checkerboard coloring so that the unit squares along the top right side are black. Domino shuffling \cite{EKLP1,EKLP2} is a process that involves moving dominoes in a specific way, we follow closely their idea and summarize it below. Given a domino tiling $T$ of $\AD_n$, if we can find a $2 \times 2$ block in $T$ (consisting of two horizontal or two vertical dominoes), then we say this $2 \times 2$ block is \emph{even} (resp., \emph{odd}) if the top right unit square in this block is black (resp., white). An \emph{odd-deficient} (resp., \emph{even-deficient}) tiling of $T$ is obtained from $T$ by removing all odd (resp., even) blocks of $T$. 

Domino shuffling is a map $S$ which sends an odd-deficient tiling $T_o$ of order $n$ to an even-deficient tiling $T_e = S(T_o)$ of order $n+1$ by the following actions: (1) slide a vertical domino in which the bottom square is black of $T_o$ one unit to its left, (2) slide a vertical domino in which the top square is black of $T_o$ one unit to its right, (3) slide a horizontal domino in which the left square is black of $T_o$ one unit above it, and (4) slide a horizontal domino in which the right square is black of $T_o$ one unit below it. We should emphasize that the colors are moved along with dominoes in our case (in \cite{EKLP1,EKLP2}, the colors are swapped after shuffling, so our terminologies are slightly different from theirs). See \Cref{fig:Todd,fig:Teven} for an example.

Suppose that a domino tiling $T$ of $\AD_n$ contains $m$ odd blocks. Let $T_o$ be the odd-deficient tiling of $T$ and $T_e = S(T_o)$. The key facts are listed below: (1) $T_e$ has $m+n+1$ even blocks, (2) the center of an odd (resp., even) block is assigned $-1$ (resp., $1$) under the map $M_e$ (resp., $M_o$), and (3) the ASMs $M_e(T_o)$ and $M_o(T_e)$ are identical. 



\section{On the Proof of \texorpdfstring{\Cref{thm:MacdonaldIntro}}{Theorem 1.1}}\label{sec:Mac}

The Loehr--Warrington formula gives the monomial expansion of $\nabla(s_\lambda)$ for any Schur function $s_\lambda$ as a sum over labeled, weakly-nested $\lambda$-families of Dyck paths. We describe these objects informally below, referring to \cite{LW08} for the rigorous definitions. The formula involves nested families of Dyck paths $(\pi_0,\dots,\pi_k)$ with the same starting and ending points as our $\lambda$-families of Schr\"oder paths that are allowed to touch and share vertical steps but may not cross, may not share horizontal steps, and no path can meet the starting point of any other path. A labeling is an assignment of nonnegative integers to the vertical steps of these paths such that the labels on consecutive vertical steps in each path increase from bottom to top, and whenever labels $r<r'$, on paths $\pi_i$ and $\pi_{i'}$ respectively, appear in the same column with $r'$ one row above $r$ we have $i<i'$. Let $\LNDP_\lambda$ denote the set of all pairs $(\pi,w)$ where $\pi$ is a weakly-nested $\lambda$-family of Dyck paths and $w$ is a labeling as described above. 

Loehr and Warrington \cite{LW08} define $\area$ and $\dinv$ statistics on pairs $(\pi,w)\in \LNDP_\lambda$. The Loehr--Warrington formula, recently proved by Blasiak, Haiman, Morse, Pun, and Seelinger \cite{BHMPS} and by Kim and Oh \cite{KO24}, states that for any partition $\lambda$,
\begin{equation}\label{eqn:LW}
    \nabla(s_\lambda) = \sgn(\lambda) \sum_{(\pi,w)\in \LNDP_\lambda} q^{\area(\pi,w)}t^{\dinv(\pi,w)}x^w,
\end{equation}
where $x^w = \prod_i x_i^{\#i\text{'s in }w}$. We briefly sketch how \Cref{thm:MacdonaldIntro} can be obtained from \eqref{eqn:LW}, following Haglund's argument in the single Schr\"oder path case (\cite[Chapter 6]{H08}). 

Since $\{h_\mu\}$ and $\{m_\mu\}$ are dual bases, the coefficient $\langle \nabla(s_\lambda),h_\mu\rangle$ can be computed as the $\area$ and $\dinv$ weighted sum over those $(\pi,w)\in \LNDP_\lambda$ such that there are $\mu_i$ $i$'s in the labeling $w$, in which case we write $\wt(w)= \mu$. A labeling is called \emph{standard} if $\wt(w) = (1,\dots,1)$, and we write $\SLNDP_\lambda$ for the set of all standard labeled $\lambda$-families of weakly nested Dyck paths. Following \cite[Chapter 6]{H08}, one can define a \emph{standardization} operation on labelings $w\mapsto w'$ which gives an $\area$ and $\dinv$-preserving bijection between $\{ (\pi,w)\in \LNDP_\lambda | \wt(w) = \mu\}$ and the set of $(\pi,w') \in \SLNDP_\lambda$ such that the \emph{reading word} of $w'$ with respect to a certain reading order is a $\mu$-shuffle. As in the single path case, the reading order for these labelings is from top to bottom along diagonals starting from the furthest diagonal from $y=x$, and for labels on coinciding vertical edges, we break ties by reading labels from the weakly innermost path to the weakly outermost path.

By \cite[Theorem 6.10]{H08}, $\langle \nabla(s_\lambda),h_d e_{|\lambda|-d}\rangle$ is the $\area$ and $\dinv$-weighted sum over $(\pi,w)$ in $\SLNDP_\lambda$ such that the reading word of $w$ is a shuffle of the decreasing sequence $|\lambda|-d,\dots,1$ and the increasing sequence $|\lambda|-d+1,\dots,|\lambda|.$ Such labeled paths can be interpreted as $\lambda$-families of Schr\"oder paths by replacing pairs of consecutive vertical and horizontal steps with diagonal steps whenever the label on the vertical step is from the increasing sequence $|\lambda|-d+1,\dots,|\lambda|$. One checks that this defines an $\area$ and $\dinv$ preserving bijection between such labeled $\lambda$-families of (weakly-)nested Dyck paths and $\lambda$-families of (strictly-)nested Schr\"oder paths with $d$ diagonals, which gives \Cref{thm:MacdonaldIntro}.



\section{Partitions of Square Shape}\label{sec:pfAD}

When $\lambda = (n^n)$, domino tilings of $R_{\lambda}$ reduce to domino tilings of \emph{extended} $\AD_n$ where the region outside $\AD_n$ is forced to be covered by vertical dominoes. In this case, the dinv adjustment simplifies to $\adj(\lambda) = \binom{n}{2}$, so the $\dinv$ of a domino tiling $T$ of the extended $\AD_n$ reduces to
\begin{equation}\label{eq.def-domino-dinv-reduce}
    \dinv(T) = \binom{n}{2} + \#\{ \text{domino pairs in } T \}.
\end{equation} 

\begin{example}
    \Cref{tab:AD2example} shows $8$ weighted domino tilings of the extended $\AD_2$ where the original $\AD_2$ is enclosed by bold edges. One can check that their total weight factors into $\AD_2(z;q,t) = (qt)^2 (z+1)(z+q)(z+t)$, which agrees with \eqref{eq.ADproduct}.
\end{example}
%
\begin{table}[htb!]
    \centering
    \begin{tabular}{c|c|c|c}
        %\hline 
            \includegraphics[width=0.16\linewidth]{AD1.eps}
            &  \includegraphics[width=0.16\linewidth]{AD2.eps} &  \includegraphics[width=0.16\linewidth]{AD3.eps} & \includegraphics[width=0.16\linewidth]{AD4.eps} \\
        $z^3q^2t^2$ & $z^2q^2t^3$ & $z^2q^2t^2$ & $z^1q^2t^3$ \\
         \hline
        \includegraphics[width=0.16\linewidth]{AD5.eps} & \includegraphics[width=0.16\linewidth]{AD6.eps} & \includegraphics[width=0.16\linewidth]{AD7.eps} & \includegraphics[width=0.16\linewidth]{AD8.eps} \\
        $z^2q^3t^2$ & $z^1q^3t^2$ & $z^1q^3t^3$ & $z^0q^3t^3$
         %\hline
    \end{tabular}
    \caption{The weight $z^{\diags(T)}q^{\area(T)}t^{\dinv(T)}$ of each domino tiling $T$ of the extended $\AD_2$.}
    \label{tab:AD2example}
\end{table}





For a domino tiling $T$ of the extended $\AD_n$, its corresponding \emph{extended} ASM is obtained from the ASM $M_e(T|_{\AD_n})$ (when restricting $T$ to $\AD_n$; see \Cref{sec:ASMAD}) by adding a triangular array of $0$'s of size $n$ on the southwestern and southeastern sides, respectively. The resulting extended ASM is a triangular array of size $2n+1$ (see \Cref{fig:extasm}). 

Given a domino tiling $T$ of the extended $\AD_n$ with $m$ odd blocks. Let $T_o$ be the odd-deficient tiling of $T$ and $\hat{T}_o$ be the tiling obtained from $T_o$ by completing all odd blocks with two \emph{horizontal} dominoes. Define $\diags$ and $\dinv$ of $T_o$ as usual, and define $\area$ of $T_o$ by $\area(T_o) = \area(\hat{T}_o)$. 

To apply the domino shuffling (\Cref{sec:introshuffling}), we restrict $T_o$ to $\AD_n$ and apply the domino shuffling to obtain the even-deficient tiling of $\AD_{n+1}$; note that there are $m+n+1$ even blocks. Let $T_e$ be such even-deficient tiling of the extended $\AD_{n+1}$ where the region outside $\AD_{n+1}$ is covered by vertical dominoes (see \Cref{fig:Todd,fig:Teven}). We write $\hat{T}_e$ for the tiling obtained from $T_e$ by completing all even blocks with two \emph{horizontal} dominoes. Similarly, define $\diags$ and $\dinv$ of $T_e$ as usual, and define $\area$ of $T_e$ by $\area(T_e) = \area(\hat{T}_e)$. We can prove how the $\area$ and $\dinv$ statistics interact with the domino shuffling in the following proposition.
 
\begin{proposition}\label{prop:stat-shuffle}
    Let $T$ be a domino tiling of the extended $\AD_n$ with $m$ odd blocks, $T_o$ the odd-deficient tiling of $T$, and $T_e$ the even-deficient tiling under the domino shuffling of $T_o$. Then
    \begin{align}\label{eq:area-shuffle}
        \area(T_e) &= \area(T_o) - \diags(T_o) + n(2n+1) - m,\quad \text{and}\\
        \dinv(T_e) & = \dinv(T_o) + n(3n+1)/2.
    \end{align}
\end{proposition}
 
\begin{figure}[ht]
    \centering
    \subfigure[]{\label{fig:Todd}\includegraphics[height=0.15\textwidth]{Todddot.png}}
    \hspace{1mm}
    \subfigure[]{\label{fig:Teven}\includegraphics[height=0.19\textwidth]{Tevendot.png}}
    %\hspace{2mm}
    \subfigure[]{\label{fig:extasm}\includegraphics[height=0.175\textwidth]{extasm.png}}
    \caption{(a) An odd-deficient tiling $T_o$ of the domino tiling given in \Cref{fig:ASMAD1}, even points are marked in red. (b) The even-deficient tiling $T_e$ under the domino shuffling of $T_o$, odd points are marked in red. (c) The extended ASM $M_e(T_o) = M_o(T_e)$.}\label{fig.shuffleexample}
\end{figure}

The key idea of proving \Cref{prop:stat-shuffle} is based on interpreting the $\area$ and $\dinv$ statistics on $T$ as some statistics on its extended ASM $M_e(T)$. We label each row from bottom to top of $M_e(T)$ by $1$ to $2n+1$ and define two statistics on $M_e(T)$ as follows. Suppose $x$ is an entry of $M_e(T)$ at row $i$, then the \emph{level} of $x$ is defined to be $\level(x)=i$. The \emph{top partial sum} of $x$, denoted $\tp(x)$, is defined to be the sum of all entries of $M_e(T)$ located from rows $i+1$ to $2n+1$ and to the right of $x$ on the same row. Considering the tilings $\hat{T}_o$ and $\hat{T}_e$, we can show that the $\area$ contribution from each odd and even block is given by the $\level$ statistic.
 
\begin{lemma}\label{lem:area-level}
    Let $d_h \in H(\hat{T}_o)$ be a horizontal domino contained in an odd block of $\hat{T}_o$ and $d^{\prime}_h \in H(\hat{T}_e)$ be a horizontal domino contained in an even block of $\hat{T}_e$. Let $x$ be an entry of $M_e(T_o)$ corresponding to the center of an odd or even block. Then 
    \begin{equation}\label{eq.area-level}
       \level(x)-1 = \begin{cases}
         \area(d_h) & \text{if $x=-1$,} \\
         \area(d^{\prime}_h) & \text{if $x=1$.} 
          \end{cases}
    \end{equation}
\end{lemma}
In \Cref{fig:Teven,fig:extasm}, the even block shown in green corresponds to the entry $x=1$ in the green box. The $\area$ of the horizontal domino in that even block is given by $\level(x)-1 = 4-1 = 3$. 

Let $T$ be a domino tiling of the extended $\AD_n$. We say an entry $x$ of $M_e(T)$ (or $M_o(T)$) is \emph{associated} with a domino of $T$ if $x = M_e(v)$ (or $M_o(v)$) and $v$ is the midpoint of the longer edge of that domino. Let $A(T_o)$ (resp., $A(T_e)$) be the collection of entries $x$ of $M_e(T_o)$ (resp., $M_o(T_e)$) such that $x$ is associated with a vertical domino of $U(T_o)$ (resp., $U(T_e)$) except for those touch the line $y=0$ and is not in the Aztec diamond region. We can show that the number of domino pairs of $T_o$ or $T_e$ is given by the $\tp$ statistic. 
 
\begin{lemma}
    Let $T$, $T_o$, and $T_e$ be as in \Cref{prop:stat-shuffle}. Then
    \begin{align}
        \#\{ \text{domino pairs in $T_o$}\} & = \sum_{x \in A(T_o)} (\tp(x)-1) + (n-1)^2, \text{ and } \\
        \#\{ \text{domino pairs in $T_e$}\} & = \sum_{x \in A(T_e)} (\tp(x)-1) + n^2.
    \end{align}
\end{lemma}

\acknowledgements{
The authors are grateful to James Haglund and Nicholas Loehr for useful conversations.
}

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