%% 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[submission]{FPSAC2019}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

\articlenumber{79}
\addbibresource{79.bib}

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


\usepackage{latexsym,
 graphicx,
 enumerate, 
 paralist,
 tabmac,
	anyfontsize
}
\usepackage[dvipsnames]{xcolor}

\graphicspath{{figures/}}

\theoremstyle{plain}
   \newtheorem{theorem}{Theorem}[section]
   \newtheorem{proposition}[theorem]{Proposition}
   \newtheorem{prop}[theorem]{Proposition}
   \newtheorem{lemma}[theorem]{Lemma}
   \newtheorem{corollary}[theorem]{Corollary}
   \newtheorem{conjecture}[theorem]{Conjecture}
   \newtheorem{problem}[theorem]{Problem}
   \newtheorem*{theorem*}{Theorem}
   \newtheorem{defprop}[theorem]{Definition--Proposition}
\theoremstyle{definition}
   \newtheorem{definition}[theorem]{Definition}
   \newtheorem{example}[theorem]{Example}
   \newtheorem{examples}[theorem]{Examples}
   \newtheorem{question}[theorem]{Question}
   \newtheorem{remark}[theorem]{Remark}
   \newtheorem{convention}[theorem]{Convention}
   \newtheorem*{main}{Main Question}

\numberwithin{equation}{section}


\newcommand\qbin[3]{\left[\genfrac{}{}{0pt}{}{#1}{#2}\right]_{#3}}
\newcommand\hook[2]{{\left( #2-#1, 1^{#1} \right)}}


\newcommand\Symm{\mathfrak{S}}

\newcommand\xx{{\mathbf{x}}}
\newcommand\yy{{\mathbf{y}}}
\newcommand{\boldt}{\mathbf{t}}
\newcommand{\boldr}{{\bf r}}
\newcommand{\boldalpha}{{\boldsymbol{\alpha}}}
\newcommand{\boldbeta}{{\boldsymbol{\beta}}}
\newcommand\abs{\operatorname{abs}}
\newcommand\mult{\operatorname{mult}}
\newcommand\defining{\operatorname{def}}
\newcommand\rad{\operatorname{rad}}
\newcommand\corad{\operatorname{corad}}
\newcommand\rank{\operatorname{rank}}
\newcommand\codim{\operatorname{codim}}
\newcommand\one{\mathbf{1}}
\newcommand\Sym{\operatorname{Sym}}
\newcommand\Hom{\operatorname{Hom}}
\newcommand\Cat{\operatorname{Cat}}
\newcommand\Hilb{\operatorname{Hilb}}
\newcommand\Conj{\operatorname{Conj}}
\newcommand\Ind{\operatorname{Ind}}
\newcommand\Par{\operatorname{Par}}
\newcommand\Frac{\operatorname{Frac}}
\newcommand\Irr{\operatorname{Irr}}
\newcommand\Aut{\operatorname{Aut}}
\newcommand\Tr{\operatorname{Tr}}
\newcommand\wt{\operatorname{wt}}
\newcommand\maj{\operatorname{maj}}
\newcommand\sgn{\operatorname{sgn}}
\newcommand\normchi{\widetilde{\chi}}
\newcommand\Class{\operatorname{Cl}}
\newcommand\Nref{\operatorname{N^{\operatorname{ref}}}}
\newcommand\Nhyp{\operatorname{N^{\operatorname{hyp}}}}
\newcommand\hcprod{{*}}
\newcommand\rk{\operatorname{rk}}
\newcommand{\ibar}{\bar\imath}
\newcommand{\jbar}{\bar\jmath}
\newcommand\Span{\operatorname{span}}
\newcommand{\diag}{\operatorname{diag}}
\newcommand{\inv}{\operatorname{inv}}
\newcommand{\std}{\operatorname{std}}
\newcommand{\destd}{\operatorname{destd}}
\newcommand{\Des}{\operatorname{Des}}
\newcommand\affS{\widetilde{\Symm}}
\newcommand{\charge}{\operatorname{ch}}
\newcommand{\ol}[1]{\overline{#1}}
\newcommand{\Green}{\mathcal{Q}}

\newcommand{\ambcs}{\overset{\textrm{AMBC}}{\longleftrightarrow}}

\newcommand{\defn}[1]{{\it {#1}}}
\newcommand{\type}[1]{\mathrm{#1}}

\newcommand\OOO{{\mathcal{O}}}
\newcommand\RRR{{\mathcal{R}}}
\newcommand{\AAA}{{\mathcal{A}}}
\newcommand{\DDD}{{\mathcal{D}}}

\newcommand\CCC{{\mathbf{C}}}
\newcommand\ccc{{\mathbf{c}}}

\newcommand\llambda{{\underline{\lambda}}}

\newcommand\CC{{\mathbb{C}}}
\newcommand\ZZ{{\mathbb{Z}}}
\newcommand\NN{{\mathbb{N}}}
\newcommand\QQ{{\mathbb{Q}}}
\newcommand\RR{{\mathbb{R}}}
\newcommand\FF{{\mathbb{F}}}
\newcommand\Gr{{\mathbb{G}}}


\newcommand{\RRSS}{\operatorname{RRSS}}


\newcommand{\La}{\Lambda}
\newcommand{\la}{\lambda}
\newcommand{\tw}[1]{\widetilde{#1}}
\newcommand{\wh}[1]{\widehat{#1}}
\newcommand{\ov}[1]{\overline{#1}}
\newcommand{\rsks}{\overset{\textrm{RSK}}{\longleftrightarrow}}
\newcommand{\SSYT}{{\rm{SSYT}}}
\newcommand{\SYT}{{\rm{SYT}}}
\newcommand{\RC}{{\rm{RC}}}
\newcommand{\CLR}{{\rm{CLR}}}
\newcommand{\trRC}{{\rm{tr_{RC}}}}
\newcommand{\trLR}{{\rm{tr_{LR}}}}
\newcommand{\tr}{{\rm{tr}}}
\newcommand{\ev}{{\rm{ev}}}
\newcommand{\sort}{{\rm{sort}}}
\DeclareMathOperator{\pr}{pr}
\newcommand{\ds}{\displaystyle}







%% define your title in the usual way
\title[Affine evacuation]{An affine generalization of evacuation}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author[Chmutov, Frieden, Kim, Lewis, Yudovina]{Michael Chmutov\thanks{MC was supported in part by NSF grant DMS-1503119}, Gabriel Frieden\addressmark{1}\thanks{GF was supported in part by NSF grants DMS-1464693 and DMS-0943832}, Dongkwan Kim\addressmark{2}, Joel B. Lewis\addressmark{3}\thanks{JBL was supported in part by NSF grant DMS-1401792}, \and Elena Yudovina}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Laboratoire de combinatoire et d'informatique math\'ematique, Universit\'e du Qu\'ebec \`a Montr\'eal, Montr\'eal, QC, Canada \\ \addressmark{2}Department of Mathematics, University of Minnesota, Minneapolis, MN, USA \\ \addressmark{3}Department of Mathematics, George Washington University, Washington, D.C., 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{We establish the existence of an involution on tabloids that is analogous to Sch\"utzenberger's evacuation map on standard Young tableaux.  We find that the number of its fixed points is given by evaluating a certain Green's polynomial at $q = -1$, and satisfies a "domino-like" recurrence relation.  
}

%% put your French abstract here, or comment this out if you don't have one
\resumetitle{R\'esum\'e}
\resume{Nous montrons l'existence d'une involution sur les tablo\"ids qui est analogue \`a l'application \'evacuation de Sch\"utzenberger sur les tableaux de Young standards. Nous trouvons que le nombre de points fix\'es par cette application est \'egal \`a la valeur d'un certain polyn\^ome de Green pour $q = -1$, et il satisfait une r\'ecurrence analogue \`a celle des dominos.
}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{evacuation, affine symmetric group, combinatorial $R$-matrix, Green's polynomial, Kostka--Foulkes polynomial, $q=-1$ phenomenon, domino tableaux}

%% 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, ie. [xx, yy] in the text

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

%\addbibresource{CFKLY_extended_abstract.bib}

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

This extended abstract concerns an analogue for the affine symmetric group of the operation called \emph{evacuation} (or \emph{Sch\"utzenberger's involution}) associated to the finite symmetric group $\Symm_n$. We begin by summarizing a few combinatorial highlights of the finite story.  Evacuation is an involution on standard Young tableaux of a given shape, which corresponds, under the Robinson--Schensted bijection, to a natural involution on the symmetric group of permutations. There are many combinatorial algorithms to compute evacuation, none of which is completely straightforward.  However, for certain nice shapes (notably, rectangles), it can be described in very simple terms.  Evacuation also has interesting enumerative properties: its fixed points are counted by an instance of Stembridge's \emph{$q = -1$ phenomenon} and are in bijection with \emph{domino tableaux} of the same shape. This story is recalled in more detail in \cref{sec:finite,sec: q=-1}. 

Our project is to construct a parallel story for the \emph{affine symmetric group} $\affS_n$.  This group is an infinite analogue of the symmetric group, and much of the beautiful combinatorics and representation theory of the symmetric group can be extended to the affine setting.  We give its formal definition in \cref{sec:affine}. The analogue of the Robinson--Schensted correspondence for $\affS_n$ is the \emph{affine matrix ball construction} (AMBC) described by Chmutov--Pylyavskyy--Yudovina \cite{CPY}, based on the work of Shi \cite{Shi_GRS}, associating to each affine permutation two \emph{tabloids} and some additional data. Our first main theorem (\cref{evacuation exists theorem}) establishes the existence of an affine analogue of evacuation, in the following sense: there is a natural involution on $\affS_n$ which corresponds, via AMBC, to an involution on tabloids. This involution agrees with the usual evacuation map when restricted to tabloids that happen to be tableaux, and it has a particularly simple form when computed on tabloids of rectangular shape. We give a combinatorial algorithm by which the map may be computed in general (\cref{thm: alg for e}).

In \cref{sec:self-evacuating}, we consider the fixed points of the affine evacuation map.  Our second main result (\cref{main counting theorem}) establishes that the fixed points of affine evacuation are counted by an evaluation of a Green's polynomial at $q = -1$, and (using results of the third-named author) that they satisfy a recurrence with a domino flavor. One of the key steps in the proof is an evaluation of the Kostka--Foulkes polynomials at $q=-1$ (\cref{thm: KF at -1}). We mention some open problems in \cref{sec: open}.

The proofs of our results can be found in \cite{CFKLY}, of which this is an extended abstract. For more discussion of the representation-theoretic aspects of this work, see the companion paper \cite{KimInvolution} by the third-named author.



%____________________________________________________________________________





\section{Background}
\subsection{Finite symmetric group}
\label{sec:finite}

We begin by describing the story that we hope to emulate in the affine setting.  For further background, we recommend \cite[Ch.~7]{EC2}.

\subsubsection{Finite permutations}
There are many ways to represent permutations in the symmetric group $\Symm_n$. One may write them in \emph{one-line notation}, that is, as words containing each element of $[n] := \{1, \ldots, n\}$ exactly once; as $n \times n$ \emph{permutation matrices}; or as the elements of the \emph{Coxeter group} of type $A_{n - 1}$, having generators $\{s_1, \ldots, s_{n - 1}\}$ and relations $s_i^2 = 1$, $s_is_js_i = s_js_is_j$ if $i - j = \pm1$, and $s_is_j = s_js_i$ otherwise. As a permutation, $s_i$ is the \emph{simple transposition} that exchanges $i$ and $i + 1$.  It is convenient to represent the relations among the $s_i$ by the associated \emph{Dynkin diagram}:
\[
\resizebox{.3\textwidth}{!}{\input{figures/dd_a.pspdftex}}
\]

The \emph{longest element} $w_0$ in $\Symm_n$ is the permutation with one-line notation $n(n-1) \cdots 1$. Conjugation by $w_0$ is an involution on $\Symm_n$ that may be realized by sending the word $w_1 \cdots w_n$ to its "reverse-complement" $(n + 1 - w_n) \cdots (n + 1 - w_1)$; by rotating the permutation matrix by $180$ degrees around its center; or by substituting $s_i \longleftrightarrow s_{n - i}$ in any expression for a permutation as a product of simple transpositions. This last description corresponds to the unique nontrivial automorphism of the Dynkin diagram.


\subsubsection{Tableaux, Robinson--Schensted, and evacuation}
\label{sec:tableaux and RS}
A \emph{partition} $\lambda = \langle \lambda_1, \ldots, \lambda_d \rangle$ of $n$ is a finite, weakly decreasing sequence of positive integers such that $\lambda_1 + \ldots + \lambda_d = n$.  To indicate that $\lambda$ is a partition of $n$, we write $\lambda \vdash n$, or $|\lambda| = n$; to indicate that $\la$ has $d$ parts, we write $\ell(\la) = d$. A partition may be represented visually by its \emph{Young diagram}, a left-aligned array of boxes having $\lambda_i$ boxes in the $i$th row from the top.  A \emph{standard Young tableau} of \emph{shape} $\lambda$ is a filling of the Young diagram of $\lambda$ with the numbers $1, \ldots, |\lambda|$, each used once, such that numbers increase down columns and from left to right across rows.


The \emph{Robinson--Schensted correspondence} (abbreviated \emph{RS} in this paper) is a combinatorial bijection between $\Symm_n$ and pairs $(P, Q)$ of standard Young tableaux of the same shape $\lambda \vdash n$. It plays a central role in both the combinatorics and representation theory of the symmetric group.

While RS does not interact well with the group operation of $\Symm_n$ in general, in the case of conjugation by $w_0$ its behavior is well-understood: there is an involution $e$ on the set of standard Young tableaux of any fixed shape $\lambda$ such that if $w$ in $\Symm_n$ corresponds to $(P, Q)$ under RS, then $w_0 w w_0$ corresponds to $(e(P), e(Q))$. Sch\"utzenberger named this map \emph{evacuation}, and showed that it may be computed by using his \emph{jeu-de-taquin promotion} operation to successively "evacuate" the entries of $T$. Alternatively, evacuation may be computed by rotating $T$ 180 degrees, replacing each entry $i$ with $n+1-i$, and restoring the resulting tableau to its original shape using \emph{jeu de taquin}.




\subsection{Affine symmetric group}
\label{sec:affine}

In this section, we describe the affine analogues of permutations, tableaux, and RS.

\subsubsection{Affine permutations}
Abstractly, the \emph{affine symmetric group} $\affS_n$ is the Coxeter group of affine type $\widetilde{A}_{n - 1}$, having generators $\{s_0, s_1, \ldots, s_{n - 1}\}$ and relations $s_i^2 = 1$, $s_is_js_i = s_js_is_j$ if $i - j \equiv\pm1 \pmod{n}$, and $s_is_j = s_js_i$ otherwise.  The corresponding Dynkin diagram is
\[
\resizebox{.3\textwidth}{!}{\input{figures/dd_aa.pspdftex}}
\] 
The group elements may be represented as certain periodic bijections of the integers \cite{Lusztig, Erikssons}: we say that a bijection $w: \ZZ \to \ZZ$ is an \emph{affine permutation}\footnote{Technically, the objects defined here are the \emph{extended} affine permutations; the elements of the affine symmetric group satisfy the extra condition $\sum_{i=1}^n w(i) = \sum_{i=1}^n i = \frac{n(n+1)}{2}$. This distinction is not important in what follows.} if $w(i + n) = w(i) + n$ for all $i \in \ZZ$. We will typically write $w_i$ in place of $w(i)$. Such permutations may be represented in \emph{window notation}, that is, as words $[w_1, w_2, \ldots, w_n]$ of length $n$ containing one representative of each equivalence class of integers modulo $n$. They may also be represented as infinite periodic permutation matrices, having rows and columns indexed by $\ZZ$, one nonzero entry in each row and column, and periodicity under translation by $(n, n)$. We identify the (finite) symmetric group with the subgroup of $\affS_n$ generated by $s_1, \ldots, s_{n-1}$, or equivalently, with the affine permutations whose representation in window notation is a permutation of $1, \ldots, n$.

Because $\affS_n$ is infinite, there is no longest element by which to conjugate.  However, there is a natural group automorphism $r: \affS_n \to \affS_n$ that may be characterized in several equivalent ways. In terms of the Dynkin diagram, it is the extension of the diagram automorphism interchanging the simple generators
$
s_i \longleftrightarrow s_{n - i}
$
for $i \in [n - 1]$ and fixing $s_0$. In terms of the window notation, it is "reverse-complement": $[w_1, \ldots,  w_n]$ becomes $[n + 1 - w_n, \ldots, n + 1 - w_1]$. In terms of the permutation matrix, it is the rotation by $180$ degrees that preserves the square $[n] \times [n]$. Note that the restriction of this automorphism to the symmetric group agrees with conjugation by $w_0$.





\subsubsection{Tabloids and AMBC}
\label{sec:AMBC}

Let $[\ol{n}]$ be the set of equivalence classes of integers modulo $n$, and for an integer $i$ let $\ol{i}$ denote the class containing $i$. Given a partition $\lambda \vdash n$, a \emph{tabloid} of shape $\lambda$ is an equivalence class of fillings of the Young diagram of $\lambda$ with $[\ol{n}]$ (with each element used exactly once), where two fillings are considered equivalent if they differ only in the arrangement of elements within rows.  Thus, tabloids are equinumerous with \emph{row-strict tableaux} filled bijectively with $[n]$, in which entries are required to increase along rows (but there is no column condition).


The analogue of RS for $\affS_n$ is the \emph{affine matrix ball construction} (\emph{AMBC}) \cite{CPY}, which sends each affine permutation to a triple $(P, Q, \rho)$ where $P$ and $Q$ are tabloids of the same shape $\lambda \vdash n$, and the \emph{weight vector} $\rho$ is an integer vector of length $\ell(\la)$ satisfying certain inequalities. The reverse map $\Psi: (P, Q, \rho) \mapsto w \in \affS_n$ is defined on all triples $(P, Q, \rho)$ consisting of two tabloids of the same shape and an integer weight vector of the correct length; when restricted to weight vectors satisfying the appropriate inequalities, it is the inverse of AMBC. In particular, if $w = \Psi(P,Q,\rho)$, then we have $w \ambcs (P,Q,\rho')$ for some weight vector $\rho'$. The weight vector does not play a role in this abstract.



%____________________________________________________________________________


\section{Affine evacuation}
\label{sec:defining evacuation}

Given the nice interaction of conjugation by $w_0$ with the RS correspondence, it is natural to ask whether the involution $r$ interacts with AMBC in a similar way. Our first main result shows that this is indeed the case.

\begin{theorem}
\label{evacuation exists theorem}
There is an involution $e$ on the set of tabloids of shape $\lambda$ such that if $w \ambcs (P, Q, \rho)$ then $r(w) \ambcs (e(P), e(Q), \rho')$ for some weight $\rho'$.
\end{theorem}



We call this involution \emph{affine evacuation}. In the remainder of this section, we discuss an algorithm, based on the \emph{combinatorial $R$-matrix}, for computing affine evacuation. In this context, we think of a tabloid as a tuple of its rows, and the combinatorial $R$-matrix gives a natural way to re-order the rows. We now define the combinatorial $R$-matrix, starting with the two-row case. (Our definition allows the rows to have repeated entries, although we do not need this generality in the tabloid setting.)

A \emph{semistandard Young tableau} of shape $\lambda$ is a filling of the Young diagram of $\lambda$ with positive integers so that the result is strictly increasing down columns and weakly increasing across rows. The \emph{content} of a semistandard Young tableau is the integer vector $\langle a_1, a_2, \ldots \rangle$, where $a_i$ is the number of $i$'s in the tableau. Let $B^k$ denote the set of semistandard Young tableaux of shape $\langle k \rangle$ with entries in $[n]$.

\begin{definition}
\label{defn: comb R}
The \emph{combinatorial $R$-matrix} is the map
\[
R : B^{k_2} \times B^{k_1} \rightarrow B^{k_1} \times B^{k_2}
\]
that sends $(a,b) \mapsto (a',b')$, according to the following algorithm:

Write the multiset of entries in $a$ and $b$ horizontally, in increasing order. Below each entry of $a$ (respectively, $b$), place a right (resp., left) parenthesis. For a given number, the right parentheses should occur before the left parentheses. Recursively remove pairs of the form $( \quad )$ until there remain $\alpha$ right parentheses, followed by $\beta$ left parentheses. Replace these remaining symbols with $\beta$ right parentheses, followed by $\alpha$ left parentheses. Add back the removed parentheses, and let $a'$ (resp., $b'$) be the multiset of numbers above a right (resp., left) parenthesis.
\end{definition}





\begin{example}
Let
\[
a = \tableau[sY]{\textcolor{red}{2},\textcolor{red}{3},\textcolor{red}{4},\textcolor{red}{5},\textcolor{red}{5},\textcolor{red}{5},\textcolor{red}{7}} \in B^7, \quad\quad\quad b = \tableau[sY]{\textcolor{blue}{1},\textcolor{blue}{1},\textcolor{blue}{1},\textcolor{blue}{2},\textcolor{blue}{4},\textcolor{blue}{5},\textcolor{blue}{5},\textcolor{blue}{6},\textcolor{blue}{6}} \in B^9.
\]
Carrying out the algorithm, we obtain
\[
\begin{array}{cccccccccccccccc}
\textcolor{blue}{1} & \textcolor{blue}{1} & \textcolor{blue}{1} & \textcolor{red}{2} & \textcolor{blue}{2} & \textcolor{red}{3} & \textcolor{red}{4} & \textcolor{blue}{4} & \textcolor{red}{5} & \textcolor{red}{5} & \textcolor{red}{5} & \textcolor{blue}{5} & \textcolor{blue}{5} & \textcolor{blue}{6} & \textcolor{blue}{6} & \textcolor{red}{7} \\
( & ( & ( & ) & ( & ) & ) & ( & ) & ) & ) & ( & ( & ( & ( & )
\end{array}
\]
\[
\begin{array}{cccccccccccccccc}
\textcolor{blue}{1} & \textcolor{blue}{1} & \textcolor{blue}{1} & \textcolor{red}{2} & \textcolor{blue}{2} & \textcolor{red}{3} & \textcolor{red}{4} & \textcolor{blue}{4} & \textcolor{red}{5} & \textcolor{red}{5} & \textcolor{red}{5} & \textcolor{blue}{5} & \textcolor{blue}{5} & \textcolor{blue}{6} & \textcolor{blue}{6} & \textcolor{red}{7} \\
&&&&&&&&&& ) & ( & ( & ( &&
\end{array}
\]
\[
\begin{array}{cccccccccccccccc}
\textcolor{blue}{1} & \textcolor{blue}{1} & \textcolor{blue}{1} & \textcolor{red}{2} & \textcolor{blue}{2} & \textcolor{red}{3} & \textcolor{red}{4} & \textcolor{blue}{4} & \textcolor{red}{5} & \textcolor{red}{5} & \textcolor{red}{5} & \textcolor{cyan}{5} & \textcolor{cyan}{5} & \textcolor{blue}{6} & \textcolor{blue}{6} & \textcolor{red}{7} \\
&&&&&&&&&& ) & ) & ) & ( &&
\end{array}
\]
so two 5's are "transferred" by the combinatorial $R$-matrix to produce the pair $(a', b')$:
\[
a' = \tableau[sY]{\textcolor{red}{2},\textcolor{red}{3},\textcolor{red}{4},\textcolor{red}{5},\textcolor{red}{5},\textcolor{red}{5},\textcolor{cyan}{5},\textcolor{cyan}{5},\textcolor{red}{7}} \in B^9, \quad\quad\quad b' = \tableau[sY]{\textcolor{blue}{1},\textcolor{blue}{1},\textcolor{blue}{1},\textcolor{blue}{2},\textcolor{blue}{4},\textcolor{blue}{6},\textcolor{blue}{6}} \in B^7.
\]
\end{example}

\begin{remark}
The combinatorial $R$-matrix of \cref{defn: comb R} is a special case of an isomorphism coming from affine crystal theory. The algorithm for $R$ given above is due to Nakayashiki and Yamada \cite[Rule 3.11]{NakayashikiYamada}. Shimozono has observed that the combinatorial $R$-matrix can also be described in terms of jeu-de-taquin \cite[Ex.~4.10]{ShimozonoDummies}.
\end{remark}



Next, we extend this definition to the case of $d$ rows.  Let $k_1, \ldots, k_d$ be a sequence of positive integers, and set $B^{k_d, \ldots, k_1} = B^{k_d} \times \cdots \times B^{k_1}$. For $i = 1, \ldots, d-1$, define
\[
R_i : B^{k_d, \ldots, k_{i+1}, k_i, \ldots, k_1} \rightarrow B^{k_d, \ldots, k_i, k_{i+1}, \ldots, k_1}
\]
to be the map that applies the combinatorial $R$-matrix to the factors $B^{k_{i+1}} \times B^{k_i}$ and leaves the other factors alone.  Remarkably, these maps generate an action of the symmetric group.

\begin{proposition}[see {\cite[Prop.~4.7 and Thm.~4.8]{ShimozonoDummies}}]
\label{prop:R braid}
The maps $R_i$ satisfy the relations $R_i^2 = \mathrm{id}$, $R_i R_j = R_j R_i$ if $|i-j| > 1$, and $R_i R_{i+1} R_i = R_{i+1} R_i R_{i+1}$.
Thus, for any permutation $\sigma \in \Symm_d$, there is a well-defined map $R_\sigma : B^{k_d, \ldots, k_1} \rightarrow B^{k_{\sigma(d)}, \ldots, k_{\sigma(1)}}$.  Moreover, if $(k_d, \ldots, k_1) = (k_{\sigma(d)}, \ldots, k_{\sigma(1)})$, then $R_\sigma$ is the identity.
\end{proposition}

A \emph{composition} of $n$ is a sequence $\mu = \langle \mu_1, \ldots, \mu_d \rangle$ of positive integers such that $n = \mu_1 + \cdots + \mu_d$. We extend the definition of Young diagram from partitions to compositions in the natural way. Consequently, we may speak of the set $\mathcal{T}(\mu)$ of tabloids of shape $\mu$ for any composition $\mu$. We identify $\mathcal{T}(\mu)$ with the set of elements of $B^{\mu_d, \ldots, \mu_1}$ of content $\langle 1^n \rangle$ by treating each row of a tabloid as a one-row tableau with entries in $[n]$. For each $\sigma \in \Symm_d$, this identification induces a map $R_\sigma : \mathcal{T}(\mu) \rightarrow \mathcal{T}(\sigma(\mu))$, which we also call the combinatorial $R$-matrix. We now state our algorithm for computing affine evacuation.

\begin{theorem}
\label{thm: alg for e}
Given a tabloid $T \in \mathcal{T}(\mu)$, the affine evacuation $e(T)$ may be computed as follows:
\begin{enumerate}
\item reverse the order of the rows of $T$, thus obtaining a tabloid in $\mathcal{T}(w_0(\mu))$;
\item replace each entry $\ol{i}$ with $\ol{n+1-i}$;
\item apply $R_{w_0}$ to restore the tabloid to its original shape.
\end{enumerate}
\end{theorem}


\begin{remark}
By \cref{prop:R braid}, the action of the combinatorial $R$-matrix on tabloids of rectangular shape is trivial, so for tabloids of rectangular shape, affine evacuation simply reverses the order of the rows and replaces each $\ol{i}$ with $\ol{n+1-i}$.
\end{remark}

\begin{remark}
Given a tabloid $T$, let $\tw{T}$ be the associated row-strict tableau. If $\tw{T}$ is a standard Young tableau (i.e., if it has increasing columns), then $\tw{e(T)}$ is equal to the ordinary evacuation of $\tw{T}$ \cite[Prop. 3.9]{CFKLY}. This validates our repetition of the symbol $e$ for both finite and affine evacuation.
\end{remark}

\begin{remark}
Two other methods of computing affine evacuation are discussed in \cite[\S3.4-5]{CFKLY}. The first uses RSK, ordinary evacuation, and Lascoux and Sch\"utzenberger's symmetric group action on semistandard Young tableaux \cite{LascouxSchutzenberger}; the second is based on a description of AMBC as an asymptotic version of RS.
\end{remark}









%____________________________________________________________________________


\section{Enumeration of self-evacuating tabloids}
\label{sec:self-evacuating}
\label{sec: counting fixed points}

Given any group action on a set, it is natural to ask about the fixed points of the action.  In the case of evacuation, this is to ask about the \emph{self-evacuating} tableaux and tabloids.  In the finite case, these fixed points have a fascinating enumeration, which we recount in \cref{sec: q=-1}. In \cref{sec: self-evac} we present and discuss \cref{main counting theorem}, our affine analogue, which gives the enumeration of self-evacuating tabloids of a given shape. We conclude in \cref{sec: open} with some open problems.

\subsection{Self-evacuating tableaux, domino tableaux, and $q = -1$}
\label{sec: q=-1}
When $|\lambda|$ is even, a \emph{domino tableau} of shape $\lambda$ is a division of the cells of the Young diagram of $\lambda$ into pairs of adjacent cells ("dominoes") that are numbered by the integers $1, \ldots, |\lambda|/2$ in such a way that for each $k$, the union of the dominoes numbered $1, \ldots, k$ is again a Young diagram.  For example, the three domino tableaux of shape $\langle 4, 2\rangle$ are
\[
\resizebox{.5\textwidth}{!}{\input{figures/dominoes_1.pspdftex}}
\]
If $|\lambda|$ is odd, the definition is the same except that the box in the top-left corner forms a one-cell "monomino."
  
The number $f^\lambda$ of standard Young tableaux of shape $\lambda$ is given by the \emph{hook-length formula}:
$
\ds f^\lambda = \frac{n!}{\prod_{c \in \lambda} h_c}.
$
Here $c$ runs over the cells of the Young diagram of $\lambda$ and $h_c$ is the \emph{hook-length} of $c$, i.e., the number of boxes that are in the same row as $c$ and weakly to its right or in the same column and weakly below it.  This number has a natural \emph{$q$-analogue}
\[
f^\lambda(q) := \frac{[n]!_q}{\prod_{c \in \lambda} [h_c]_q},
\]
where for a nonnegative integer $k$ we define $[k]_q := 1 + q + \ldots + q^{k - 1}$ and $[k]!_q := [1]_q \cdot [2]_q \cdots [k]_q$, so that $f^\lambda(1) = f^\lambda$.  It is not clear from this definition, but in fact $f^\lambda(q)$ is a polynomial in $q$ whose coefficients are positive integers.  (It is the generating function for tableaux by a statistic called \emph{comaj} \cite{Krattenthaler}; see also \cite[p.~243]{Macdonald}.)

Let $\chi^\lambda$ denote the irreducible character of the symmetric group indexed by $\lambda$.  We will denote by $\chi^\lambda_\mu$ the result of evaluating $\chi^\lambda$ on a permutation of cycle type $\mu$.  Let $\rho_2(n)$ be the cycle type of $w_0$ in $\Symm_n$, that is, $\rho_2(n)$ is the partition $\langle 2^{n/2} \rangle$ if $n$ is even and $\langle 2^{(n - 1)/2}, 1 \rangle$ if $n$ is odd.  Finally, for a partition $\lambda$, let $b(\lambda) = \sum_i (i-1) \lambda_i$.

The following theorem shows how these objects are bound together with fixed points of evacuation.

\begin{theorem}[{\cite[Thm.~4.3]{Stembridge} and \cite[Thm.~3.1]{StanleyEvac}}]
\label{counting self-evacuating tableaux}
For any partition $\lambda$, there is a bijection between self-evacuating standard Young tableaux of shape $\lambda$ and domino tableaux of shape $\lambda$.  Moreover, the number of these tableaux is equal to both $(-1)^{b(\lambda)} \cdot \chi^\lambda_{\rho_2(n)}$ and $f^\lambda(-1)$.
\end{theorem}

This theorem provides an example of the \emph{$q = -1$ phenomenon} (and more generally the \emph{cyclic sieving phenomenon}), whereby a natural enumerating polynomial for a set gives, upon substitution of $-1$ (or a root of unity) for the variable, the number of fixed points of the set under a natural involution (or cyclic action).


\subsection{Self-evacuating tabloids}
\label{sec: self-evac}
In this section, we present our main enumeration theorem; it is an affine analogue of \cref{counting self-evacuating tableaux}, giving the enumeration of self-evacuating tabloids of a given shape $\lambda$. We begin with some background definitions necessary for the statement of the theorem.


For partitions $\la$ and $\mu$, the \emph{Kostka--Foulkes polynomials} $K_{\la \mu}(q)$ are defined to be the transition coefficients between the Schur and Hall--Littlewood bases of the ring of symmetric functions \cite[\S III.6]{Macdonald}. They appear in a variety of combinatorial, representation theoretic, and algebro-geometric contexts (see \cite{KostkaExpository} for a nice survey). Lascoux and Sch\"utzenberger proved that $K_{\la \mu}(q)$ is the generating function over $\SSYT(\la, \mu)$ (the set of semistandard Young tableaux of shape $\la$ and content $\mu$) with respect to a statistic called \emph{charge} \cite{LScharge}.


\emph{Green's polynomials} were introduced by Green in his study \cite{Green} of the representation theory of the finite general linear groups. Following \cite[\S III.7]{Macdonald}, we take as their definition the formula
\begin{equation*}
\label{eq: Green expression}
\Green^\mu_{\rho}(q) = \sum_{\la} \chi^\la_{\rho} \tw{K}_{\la \mu}(q),
\end{equation*}
where $\tw{K}_{\la \mu}(q) = q^{b(\mu)} K_{\la \mu}(q^{-1})$ is the generating function over $\SSYT(\la,\mu)$ with respect to \emph{cocharge}. Springer and Hotta showed that $\Green^\mu_\rho(q)$, viewed as a function of $\rho$, is the graded character of the symmetric group action on the cohomology of the type $A$ Springer fiber associated to the partition $\mu$ (up to tensoring with the sign character) \cite{HottaSpringer}.

We now state our enumeration theorem.

\begin{theorem}
\label{main counting theorem}
Suppose that $\lambda = \langle \lambda_1^{m_1}, \lambda_2^{m_2}, \ldots, \lambda_k^{m_k} \rangle$ is a partition of $n$ having $k$ distinct part-sizes.  For $1 \leq i \leq k$, let $\lambda\mathord{\downarrow}^{(\lambda_i)}_{(\lambda_i - 2)}$ be the partition formed by replacing a part of $\lambda$ of size $\lambda_i$ with one of size $\lambda_i - 2$, and let $\lambda\mathord{\downarrow}^{(\lambda_i, \lambda_i)}_{(\lambda_i - 1, \lambda_i - 1)}$ be the partition formed by replacing two parts of $\lambda$ of size $\lambda_i$ with two parts of size $\lambda_i - 1$. Then for $n \geq 2$, the number $t(\lambda)$ of self-evacuating tabloids of shape $\lambda$ satisfies the recurrence relation
\[
t(\lambda) = \sum_{\substack{i \colon \lambda_i \geq 2, \\ m_i \textrm{ is odd}}} t\left(\lambda\mathord{\downarrow}^{(\lambda_i)}_{(\lambda_i - 2)}\right) + \sum_{i=1}^k 2\left\lfloor \frac{m_i}{2} \right\rfloor \cdot t\left(\lambda\mathord{\downarrow}^{(\lambda_i, \lambda_i)}_{(\lambda_i - 1, \lambda_i - 1)}\right).
\]
Moreover, $t(\lambda)$ is given by the evaluation of a Green's polynomial at $q = -1$:
\begin{equation}
\label{eq: Green eval}
t(\lambda) = \Green^\lambda_{\rho_2(n)}(-1),
\end{equation}
where as above, $\rho_2(n)$ is the cycle type of $w_0 \in \Symm_n$.
\end{theorem}

\begin{remark}
Although we do not have an affine analogue of domino tableaux, it is tempting to view the first sum in the recurrence relation as removing a horizontal domino (i.e., two cells in a single row) from $\lambda$, while the second sum removes a vertical domino (i.e., two cells in adjacent rows).
\end{remark}

\begin{remark}
The third-named author has shown that when $\lambda$ corresponds to a nilpotent conjugacy class in the Lie algebra of type $B_n$ or $C_n$, the number $\Green^\lambda_{\rho_2(n)}(-1)$ is the Euler characteristic of the associated (type $B_n$ or $C_n$) Springer fiber \cite[Main Thm. 2]{KimSpringer}. For comparison, it follows from the above-mentioned result of Hotta and Springer that the Euler characteristic of the type $A_{n-1}$ Springer fiber associated to $\lambda$ is equal to $\Green^\lambda_{\langle 1^n \rangle}(1)$.
\end{remark}


\begin{remark}
The evaluation of the Green's polynomial in \eqref{eq: Green eval} is not an instance of the $q = -1$ phenomenon, because $\Green^\lambda_{\rho_2(n)}(q)$ has both positive and negative coefficients, and so does not count tabloids by a statistic. In fact, the evaluation of this polynomial at $q = 1$ is often zero \cite[\S III.7, Ex.~6]{Macdonald}.
\end{remark}



The recurrence relation in \cref{main counting theorem} is deduced from \eqref{eq: Green eval} using a recurrence relation for Green's polynomial evaluations at $-1$ established by the third-named author \cite[Prop.~10.3]{KimSpringer}. Equation \eqref{eq: Green eval} is proved by using RSK and \cref{counting self-evacuating tableaux} to reduce to an evaluation of the Kostka--Foulkes polynomials at $q = -1$, which we now explain.

Lascoux and Sch\"utzenberger defined a shape-preserving, content-permuting action of the symmetric group on semistandard tableaux \cite{LascouxSchutzenberger}; this action was later found to coincide with the Weyl group action on type $A$ crystals generated by root string reflections. Let $e_d$ be the usual (semistandard) evacuation on tableaux with entries at most $d$, and let $\tau_d$ be the Lascoux--Sch\"utzenberger action of $w_0 \in \Symm_d$ on such tableaux (these maps are described in more detail in \cite[\S3.4]{CFKLY}). Define $e_d^* = \tau_d \circ e_d = e_d \circ \tau_d$.

\begin{theorem}
\label{thm: KF at -1}
The number of elements of ${\rm SSYT}(\la,\mu)$ fixed by $e^*_d$ (where $d$ is the number of parts of $\mu$) is given by
$
(-1)^{b(\la)} \tw{K}_{\la \mu}(-1).
$
\end{theorem}

The key tool in the proof of \cref{thm: KF at -1} is Kirillov and Reshetikhin's bijection between semistandard tableaux and \emph{rigged configurations} \cite{KirResh}, which sheds light on the relationship between the cocharge of a tableau and its image under $e_d^*$.

\begin{remark}
In contrast to the Green's polynomial evaluation \eqref{eq: Green eval}, \cref{thm: KF at -1} is an example of the $q=-1$ phenomenon. In the case where all part multiplicities of $\mu$ are even, the result of the theorem can be pieced together from results of Stembridge and Lascoux--Leclerc--Thibon, as explained in \cite[Remark 4.8]{CFKLY}.
\end{remark}


\subsection{Open problems}
\label{sec: open}

\subsubsection{Other symmetries}

Rhoades proved that when $\lambda$ is a rectangular partition, the $q$-analogue of the hook-length polynomial $f^\lambda(q)$ exhibits the cyclic sieving phenomenon with respect to promotion of standard tableaux \cite{Rhoades}. In our setting, the analogue of promotion is the map which increases all entries of a tabloid by 1 mod $n$. This cyclic action on tabloids is one of the original examples of the cyclic sieving phenomenon (using the obvious $q$-analogue of the multinomial coefficient) \cite[Prop. 4.4]{RSW}.

One can also consider the involution obtained by composing the cyclic action on tabloids with affine evacuation. When $n$ is odd, this map is conjugate to affine evacuation, and thus has the same number of fixed points. When $n$ is even, however, this involution has a different number of fixed points. We conjecture that the number of fixed points of this involution also satisfies the recursion of \cref{main counting theorem} (with different initial conditions), and that it is equal to a different Green's polynomial evaluated at $q = -1$ \cite[Conj. 5.2]{CFKLY}.

For more on these symmetries and their connection to AMBC, see \cite[\S 5.2]{CFKLY}.


\subsubsection{Domino tabloids?}

The major enumerative problem suggested by our work is to give a direct bijective proof of the recurrence relation in \cref{main counting theorem}. Unfortunately, we have been able to give such a proof only in the cases that $\ell(\lambda) = 1$ (trivial) or $2$. One possible route to such a proof would be to define a notion of "domino tabloids," whose enumeration satisfies the recurrence, and which can be put in bijection with the fixed points of affine evacuation. One might expect these (hypothetical) domino tabloids to play a role in combinatorics or representation theory similar to the role played by domino tableaux (for more on this, see \cite[\S 5.1]{CFKLY} and the references therein).



\acknowledgements{The authors are grateful to Kevin Dilks, for initially suggesting the idea of generalizing evacuation in this context; to Sam Hopkins and Thomas McConville, who informed us of our parallel work on related questions; to Brendon Rhoades, for helpful conversations about Kostka--Foulkes polynomials; to Pavlo Pylyavskyy, for numerous conversations; and to Vic Reiner, for many fruitful questions and suggestions.}




%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
%\bibliography{CFKLY_extended_abstract}
%\bibliographystyle{alpha-abbrvsort}
\printbibliography


\end{document}




