\documentclass[finalversion]{FPSAC2024}
\articlenumber{2}

\usepackage{tabu}
\usepackage{makecell}

\usepackage{mathrsfs}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem{conjecture}{Conjecture}
\newtheorem{proposition}{Proposition}
\newtheorem{question}{Question}
\newtheorem{problem}{Problem}

\theoremstyle{definition}
\newtheorem{definition}{Definition}
\newtheorem{example}{Example}
\newtheorem{remark}{Remark}

\newcommand{\ZZ}{\mathbb{Z}}
\DeclareMathOperator{\TPro}{TPro}
\DeclareMathOperator{\Pro}{Pro}
\DeclareMathOperator{\Bro}{Bro}
\DeclareMathOperator{\lcm}{lcm}
\DeclareMathOperator{\jdt}{jdt}
\DeclareMathOperator{\Rot}{Rot}
\DeclareMathOperator{\cyc}{cyc}
\DeclareMathOperator{\rev}{rev}
\newcommand{\Coll}{\mathrm{Coll}}
\newcommand{\Orb}{\mathrm{Orb}}
\newcommand{\Comp}{\mathsf{Comp}}
\newcommand{\Path}{\mathsf{Path}}
\newcommand{\Cycle}{\mathsf{Cycle}}
\newcommand{\s}{\mathsf{s}}
\newcommand{\cc}{\mathsf{c}}
\newcommand{\vv}{{{\bf v}}}
\newcommand{\stand}{\mathrm{stand}}

\newcommand{\CD}[1]{\textcolor{red}{\textsf{#1}}}

\newcommand{\dfn}[1]{\textcolor{blue}{\emph{#1}}}


\title[Toric and Permutoric Promotion]{Toric and Permutoric Promotion}

\author{Colin Defant\thanks{\href{mailto:colindefant@gmail.com}{colindefant@gmail.com}. Supported by the National Science Foundation under Award No.\ 2201907 and by a Benjamin Peirce Fellowship at Harvard University.}\addressmark{1},
Rachana Madhukara\thanks{\href{mailto:rachanam@mit.edu}{rachanam@mit.edu}.}\addressmark{2}, \and 
Hugh Thomas\thanks{\href{mailto:thomas.hugh_r@uqam.ca}{thomas.hugh\_r@uqam.ca}.}\addressmark{3}}


\address{\addressmark{1}Department of Mathematics, Harvard University, Cambridge, MA 02139, USA\\ 
\addressmark{2}Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139, USA\\ 
\addressmark{3}Lacim, UQAM, Montréal, QC, H3C 3P8 Canada
}

\received{}


%\revised{}

\abstract{We introduce \emph{toric promotion} as a cyclic analogue of Sch\"utzenberger's promotion operator. Toric promotion acts on the set of labelings of a graph $G$; it is defined as the composition of certain toggle operators, listed in a natural cyclic order. We provide a surprisingly simple description of the orbit structure of toric promotion when $G$ is a forest. We then consider more general permutoric promotion operators, which are defined as compositions of the same toggle operators, but in permuted orders. When $G$ is a path graph, we provide a complete description of the orbit structures of all permutoric promotion operators, showing that they satisfy the cyclic sieving phenomenon. }


\keywords{promotion, cyclic analogue, cyclic sieving, toggle operator}

\usepackage[backend=bibtex]{biblatex}
\addbibresource{PermutoricBib.bib}

\renewbibmacro{in:}{}


\begin{document}

\maketitle

This is an extended abstract for the articles \cite{DefantToric} and \cite{Permutoric}. The first of these articles---written by the first author---focuses on toric promotion, while the second article---written by all three authors---concerns the more general permutoric promotion operators. 

\section{Introduction}\label{SecIntro}

In his study of the Robinson--Schensted--Knuth correspondence, Sch\"utzenberger \cite{Schutzenberger1, Schutzenberger2} introduced a beautiful bijective operator called \emph{promotion}, which acts on the set of linear extensions of a finite poset. Haiman \cite{Haiman} and Malvenuto--Reutenauer \cite{Malvenuto} found that promotion could be defined as a composition of local \emph{toggle operators} (also called \emph{Bender--Knuth involutions}). Promotion is now one of the most extensively studied operators in the field of dynamical algebraic combinatorics.

Following the approach first considered by Malvenuto and Reutenauer \cite{Malvenuto}, we define promotion on labelings of graphs instead of linear extensions of posets. Let $G=(V,E)$ be a graph with $n$ vertices. A \dfn{labeling} of $G$ is a bijection $V\to \mathbb Z/n\mathbb Z$. We denote the set of labelings of $G$ by $\Lambda_G$. Given distinct $a,b\in\mathbb Z/n\mathbb Z$, let $(a\,\,b)$ be the transposition that swaps $a$ and $b$. For $i\in\ZZ/n\ZZ$, the \dfn{toggle} operator $\tau_i\colon \Lambda_G\to\Lambda_G$ is defined by 
\[
\tau_i(\sigma)=\begin{cases} (i\,\,i+1)\circ \sigma & \mbox{if } \{\sigma^{-1}(i),\sigma^{-1}(i+1)\}\not\in E; \\ \sigma & \mbox{if } \{\sigma^{-1}(i),\sigma^{-1}(i+1)\}\in E. \end{cases}
\]
In other words, $\tau_i$ swaps the labels $i$ and $i+1$ if those labels are assigned to nonadjacent vertices of $G$, and it does nothing otherwise. Define \dfn{promotion} to be the operator $\Pro\colon\Lambda_G\to\Lambda_G$ given by \[\Pro=\tau_{n-1}\cdots\tau_2\tau_1.\] Here and in the sequel, concatenation of operators represents composition. 

A recent trend in algebraic combinatorics aims to find cyclic analogues of more traditional ``linear'' objects (see \cite{AdinCyclic,Develin} and the references therein). In the same vein, we introduce a cyclic analogue of promotion called \dfn{toric promotion}; this is the operator $\TPro\colon\Lambda_G\to\Lambda_G$ given by \[\TPro=\tau_{n}\tau_{n-1}\cdots\tau_2\tau_1=\tau_n\Pro.\] 

Our first main result reveals that toric promotion has remarkably nice dynamical properties when $G$ is a forest. 

\begin{theorem}[\cite{DefantToric}]\label{thm:toric_main}
Let $G$ be a forest with $n\geq 2$ vertices, and let $\sigma\in\Lambda_G$ be a labeling. The orbit of toric promotion containing $\sigma$ has size $(n-1)t/\gcd(t,n)$, where $t$ is the number of vertices in the connected component of $G$ containing $\sigma^{-1}(1)$. In particular, if $G$ is a tree, then every orbit of $\TPro\colon\Lambda_G\to\Lambda_G$ has size $n-1$.
\end{theorem}

\Cref{thm:toric_main} stands in stark contrast to the wild dynamics of promotion on most forests. For example, even when $G$ is a path graph with $7$ vertices, the order of $\Pro\colon\Lambda_G\to\Lambda_G$ is $3224590642072800$, whereas all orbits of $\TPro\colon\Lambda_G\to\Lambda_G$ have size $6$. 

We now consider a generalization of toric promotion in which the toggle operators $\tau_1,\ldots,\tau_n$ can be composed in any order. Let $[n]=\{1,\ldots,n\}$, and let $\pi\colon[n]\to \mathbb Z/n\mathbb Z$ be a bijection. The \dfn{permutoric promotion} operator $\TPro_\pi\colon\Lambda_G\to\Lambda_G$ is defined by \[\TPro_\pi=\tau_{\pi(n)}\cdots\tau_{\pi(2)}\tau_{\pi(1)}.\] 


One would ideally hope to have an extension of \Cref{thm:toric_main} to arbitrary permutoric promotion operators. Unfortunately, trying to completely describe the orbit structure of $\TPro_\pi\colon\Lambda_G\to\Lambda_G$ for arbitrary forests $G$ and arbitrary permutations $\pi$ seems to be very difficult. However, it turns out that we \emph{can} do this when $G$ is a path. To state our main result, we need a bit more terminology. 


Let $[k]_q=\frac{1-q^k}{1-q}=1+q+\cdots+q^{k-1}$ and $[k]_q!=[k]_q[k-1]_q\cdots[1]_q$. The \dfn{$q$-binomial coefficient} ${k\brack r}_q$ is the polynomial $\dfrac{[k]_q!}{[r]_q![k-r]_q!}\in\mathbb C[q]$.

Let $X$ be a finite set, and let $f\colon X\to X$ be an invertible map of order $\omega$ (i.e., $\omega$ is the smallest positive integer such that $f^\omega(x)=x$ for all $x\in X$). Let $F(q)\in\mathbb C[q]$ be a polynomial in the variable $q$. Following \cite{CSPDefinition}, we say the triple $(X,f,F(q))$ \dfn{exhibits the cyclic sieving phenomenon} if for every integer $k$, the number of elements of $X$ fixed by $f^k$ is $F(e^{2\pi ik/\omega})$. 

Although we view the set $\mathbb Z/n\mathbb Z$ as a ``cyclic'' object, it will often be convenient to identify 
$\mathbb Z/n\mathbb Z$ with the ``linear'' set $[n]$ and consider the total ordering of its elements given by $1<2<\cdots<n$. If $\pi\colon[n]\to\ZZ/n\ZZ$ is a bijection, then a \dfn{cyclic descent} of $\pi^{-1}$ is an element $i\in\mathbb Z/n\mathbb Z$ such that $\pi^{-1}(i)>\pi^{-1}(i+1)$ (note that $n$ is permitted to be a cyclic descent). 

Let $\Path_n$ and $\Cycle_n$ be the $n$-vertex path graph and cycle graph, respectively. In \cite{DefantToric}, the first author conjectured that for every bijection 
$\pi\colon[n]\to\mathbb Z/n\mathbb Z$, the order of $\TPro_\pi\colon\Lambda_{\Path_n}\to\Lambda_{\Path_n}$ is $d(n-d)$, where $d$ is the number of cyclic descents of $\pi^{-1}$. Our next main theorem not only proves this conjecture, but also determines the entire orbit structure of $\TPro_\pi$ in this case. 

\begin{theorem}[\cite{Permutoric}]\label{thm:main}
Let $\pi\colon[n]\to\ZZ/n\ZZ$ be a bijection, and let $d$ be the number of cyclic descents of $\pi^{-1}$. The order of the permutoric promotion operator $\TPro_\pi\colon\Lambda_{\Path_n}\to\Lambda_{\Path_n}$ is $d(n-d)$. Moreover, the following triple exhibits the cyclic sieving phenomenon: \[\left(\Lambda_{\Path_n},\TPro_\pi,n(d-1)!(n-d-1)![n-d]_{q^d}{n-1\brack d-1}_{q}\right).\] \end{theorem}

Note that when $d=1$, the sieving polynomial in \Cref{thm:main} is $n(n-2)![n-1]_q$, which agrees with \Cref{thm:toric_main}. 

\begin{remark}
\Cref{thm:toric_main} determines the orbit structure of toric promotion when $G$ is a forest. It is still open to understand the dynamics of toric promotion for other graphs, including cycles. \Cref{thm:main} determines the orbit structure of any permutoric promotion operator when $G$ is a path. It would be interesting to gain a better understanding of $\TPro_\pi$ when $G$ is another type of tree, even when $\pi^{-1}$ has just $2$ cyclic descents. 
\end{remark}

In \cref{sec:permutoric}, we summarize some of the main ideas that go into the proof of \cref{thm:main}, referring the reader to our full article \cite{Permutoric} for the (quite involved) details that we have omitted. We also briefly summarize a proof of \cref{thm:toric_main} in \cref{sec:toric}, though we refer the reader to \cite{DefantToric} for a full proof. 

\section{Dynamics of Permutoric Promotion}\label{sec:permutoric} 

As before, fix a bijection $\pi\colon [n]\to\ZZ/n\ZZ$, and let $d$ be the number of cyclic descents of $\pi^{-1}$. We assume from now on that $G$ is the path graph $\Path_n$ so that $\TPro_\pi$ is an operator on $\Lambda_{\Path_n}$. Given a finite set $X$ and an invertible map $f\colon X\to X$, we write $\Orb_f$ for the set of orbits of $f$. 

\subsection{A Reduction} 

Let $\Comp_d(n)$ denote the set of compositions of $n$ with $d$ parts (i.e., $d$-tuples of positive integers that sum to $n$). There is a natural \dfn{rotation} operator $\Rot_{n,d}\colon\Comp_d(n)\to\Comp_d(n)$ defined by $\Rot_{n,d}(a_1,a_2,\ldots,a_d)=(a_2,\ldots,a_d,a_1)$.  Reiner, Stanton, and White \cite{CSPDefinition} proved that the triple $\left(\Comp_d(n),\Rot_{n,d},{n-1 \brack d-1}_q\right)$ exhibits the cyclic sieving phenomenon. As it turns out, this result is responsible for the factor of ${n-1 \brack d-1}_q$ in the sieving polynomial in \cref{thm:main}. 

Let $\cyc\colon\Lambda_{\Path_n}\to\Lambda_{\Path_n}$ be the \dfn{cyclic shift} operator given by ${(\cyc(\sigma))(v)=\sigma(v)+1}$. 
Let $\Phi_{n,d}\colon\Lambda_{\Path_n}\to\Lambda_{\Path_n}$ be the operator 
\begin{align*}
\cyc^d\prod_{i=n-d}^1(\tau_i\tau_{i+1}\cdots\tau_{i+d-1})=\cyc^d(\tau_{n-d}\tau_{n-d+1}\cdots\tau_{n-1})\cdots(\tau_2\tau_3\cdots\tau_{d+1})(\tau_1\tau_2\cdots\tau_d).
\end{align*}
Using the identity $\cyc\tau_i=\tau_{i+1}\cyc$ together with the fact that $\tau_i$ and $\tau_j$ commute whenever $j\not\in\{i-1,i+1\}$, one can show (see \cite{Permutoric} for details) that 
\begin{equation}\label{eq:PhiTPro}
\Phi_{n,d}^{n/\gcd(n,d)}=\TPro_\pi^{\lcm(d,n-d)}.
\end{equation}
Using a result about \emph{friends-and-strangers graphs} from \cite{DefantFriends}, one can prove that every orbit of $\Phi_{n,d}$ has size divisible by $n/\gcd(n,d)$ (see \cite[Lemma~6.3]{Permutoric}). A substantial portion of our full article is devoted to proving that every orbit of $\TPro_\pi$ has size divisible by $\lcm(d,n-d)$ (see \cite[Proposition~5.1]{Permutoric}). 
Together with \eqref{eq:PhiTPro}, these divisibility results allow us to transfer the problem of describing the orbit structure of $\TPro_\pi$ to that of describing the orbit structure of $\Phi_{n,d}$. Thus, we deduce \cref{thm:main} from the following proposition and the fact that $\left(\Comp_d(n),\Rot_{n,d},{n-1 \brack d-1}_q\right)$ exhibits the cyclic sieving phenomenon.  

\begin{proposition}\label{prop:PhiRot}
There is a map $\Omega\colon\Orb_{\Phi_{n,d}}\to\Orb_{\Rot_{n,d}}$ such that $|\Omega(\mathcal O)|=\frac{d}{n}|\mathcal O|$ for every $\mathcal O\in\Orb_{\Phi_{n,d}}$ and $|\Omega^{-1}(\widehat{\mathcal O})|=d!(n-d)!$ for every $\widehat{\mathcal O}\in\Orb_{\Rot_{n,d}}$. 
\end{proposition}

\subsection{Sliding Stones and Colliding Coins}
We now discuss how to construct the map $\Omega$ from \Cref{prop:PhiRot}. Code implementing several of the combinatorial constructions described in this section can be found at \url{https://cocalc.com/hrthomas/permutoric-promotion/implementation}.

For each integer $k$, let $\theta_k=\tau_{q+d+1-r}$, where $q$ and $r$ are the unique integers satisfying $k=qd+r$ and $1\leq r\leq d$. Let \[\nu_\ell=\theta_{d\ell}\theta_{d\ell-1}\cdots\theta_{d(\ell-1)+2}\theta_{d(\ell-1)+1}.\] Observe that $\theta_{k+dn}=\theta_k$ for all integers $k$. We have \[\Phi_{n,d}=\cyc^d\theta_{d(n-d)}\cdots\theta_2\theta_1=\cyc^d\nu_{n-d}\cdots\nu_2\nu_1.\] By combining the identity $\cyc\tau_i=\tau_{i+1}\cyc$ with the fact that $\cyc^n$ is the identity map, one can easily verify that 
$\Phi_{n,d}^{m}=\theta_{md(n-d)}\cdots\theta_2\theta_1=\nu_{m(n-d)}\cdots\nu_2\nu_1$
whenever $m$ is a positive multiple of $n/\gcd(n,d)$. 

Define a \dfn{state} to be a pair $(\sigma,t)\in\Lambda_{\Path_n}\times\ZZ$; we call $\sigma$ the \dfn{labeling} of the state and say that the state is at \dfn{time} $t$. A \dfn{timeline} is a bi-infinite sequence $\mathcal T=(\sigma_t,t)_{t\in\ZZ}$ of states such that $\sigma_t=\nu_t(\sigma_{t-1})$ for all $t\in\ZZ$. Note that every state belongs to a unique timeline. For $\sigma\in\Lambda_{\Path_n}$, let $\mathcal T_\sigma$ be the unique timeline containing the state $(\sigma,0)$. 

Let $v_1,\ldots,v_n$ be the vertices of $\Path_n$, listed from left to right. For each $\ell\in[n]$, let $\vv_\ell$ be a formal symbol associated to $v_\ell$; we will call $\vv_\ell$ a \dfn{replica}. Let $\s_1,\ldots,\s_d$ be stones of different colors. We define the \dfn{stones diagram} of a state $(\sigma,t)$ as follows. Start with a copy of $\Cycle_n$, whose vertices we identify with $\mathbb Z/n\mathbb Z$. Place $\s_1,\ldots,\s_d$ on the vertices $t+d,\ldots,t+1$, respectively. Then place each replica $\vv_\ell$ on the vertex $\sigma(v_\ell)$ of $\Cycle_n$; if this vertex already has a stone sitting on it, then we place the replica on top of the stone. 

Suppose we have a timeline $\mathcal T=(\sigma_t,t)_{t\in\ZZ}$. We want to describe how the stones diagrams of the states evolve as we move through the timeline. We will imagine transforming the stones diagram of $(\sigma_{t-1},t-1)$ into that of $(\sigma_t,t)$ via a sequence of $d$ \dfn{small steps}. The $i$-th small step moves $\s_i$ one space clockwise. Now, $(\theta_{d(t-1)+i}\cdots\theta_{d(t-1)+1})(\sigma_{t-1})$ is obtained from $(\theta_{d(t-1)+i-1}\cdots\theta_{d(t-1)+1})(\sigma_{t-1})$ by applying the operator $\theta_{d(t-1)+i}=\tau_{t+d-i}$. If this operator has no effect, then we do not move any of the replicas $\vv_1,\ldots,\vv_n$ during the $i$-th small step (in this case, the stone $\s_i$ slides from underneath one replica to underneath a different replica). Otherwise, $\theta_{d(t-1)+i}$ has the effect of swapping the labels $t+d-i$ and $t+d-i+1$, so we swap the replicas that were sitting on the vertices $t+d-i$ and $t+d-i+1$ (in this case, the stone $\s_{i}$ carries the replica sitting on it along with it as it slides). \Cref{Fig5} illustrates these small steps for a particular example with $n=8$, $d=3$, and $t=1$. 

\begin{figure}[ht]
  \begin{center}{\includegraphics[height=3.4cm]{PermutoricPIC26}}
  \end{center}
  \caption{The $d=3$ small steps transforming the stones diagram of a state at time $0$ into the stones diagram of the next state at time $1$.}\label{Fig5}
\end{figure}

Now consider $d$ coins of different colors such that the set of colors of the coins is the same as the set of colors of the stones. We define the \dfn{coins diagram} of a state $(\sigma,t)$ as follows. Start with a copy of $\Path_n$. For each $i\in[d]$, there is a replica $\vv_\ell$ sitting on the stone $\s_i$ in the stones diagram of $(\sigma,t)$; place the coin with the same color as the stone $\s_i$ on the vertex $v_\ell$ (see \Cref{FigNewA,Fig6}). Note that the set of vertices of $\Path_n$ occupied by coins is $\{\sigma^{-1}(t+1),\ldots,\sigma^{-1}(t+d)\}$. 


Consider how the coins diagrams evolve as we move through a timeline $\mathcal T=(\sigma_t,t)_{t\in\ZZ}$. Let us transform the stones diagram of $(\sigma_{t-1},t-1)$ into that of $(\sigma_t,t)$ via the $d$ small steps described above. Let $\vv_\ell$ be the replica sitting on $\s_i$ right before the $i$-th small step, and let $\vv_{\ell'}$ be the replica sitting on the vertex one step clockwise from $\s_i$ right before the $i$-th small step. When $\s_i$ moves in the $i$-th small step, it will either carry its replica $\vv_\ell$ along with it or slide from underneath $\vv_\ell$ to underneath $\vv_{\ell'}$; the latter occurs if and only if $\ell'=\ell\pm 1$. In the former case, no coins move during the $i$-th small step; in the latter case, a coin moves from $v_\ell$ to the adjacent vertex $v_{\ell'}$ (which did not have a coin on it right before this small step).  

If we watch the coins diagrams evolve as we move through the timeline, then by the previous paragraph, the coins will move around on $\Path_n$, but they will never move through each other. Therefore, it makes sense to name the coins $\cc_1,\ldots,\cc_d$ in the order they appear along the path from left to right, and this naming only depends on the timeline (not the specific state in the timeline). Define a \dfn{traffic jam} to be a maximal nonempty collection of coins that occupy a contiguous block of vertices (so the vertices occupied by the coins in a particular traffic jam induce a connected subgraph of $\Path_n$). Note that a traffic jam could have just a single coin. We say a traffic jam \dfn{touches a wall} if it contains a coin that occupies $v_1$ or $v_n$. 

At any time, a coin has an idea of the direction in which it expects to move next (our coins are conscious now). Note that this is not necessarily the direction in which it will move next because it may change its mind before it moves. The way that a coin $\cc$ decides which direction it expects to move is as follows. Suppose $\cc$ currently occupies vertex $v_j$, and suppose the coins in the traffic jam containing $\cc$ occupy the vertices $v_r,v_{r+1},\ldots,v_s$. The coin $\cc$ looks at the stones diagram and reads ahead in the clockwise direction, starting from the stone of its color, and it determines whether it first sees $\vv_{r-1}$ or $\vv_{s+1}$. If it first sees $\vv_{r-1}$, it expects to move left; if it first sees $\vv_{s+1}$, it expects to move right. If $r-1$ is not the index of a replica (because $r=1$), the first replica that $\cc$ sees will be $\vv_{s+1}$; similarly, if $s+1$ is not the index of a replica (because $s=n$), the first replica $\cc$ sees will be $\vv_{r-1}$. 

\Cref{FigNewA} shows several stones diagrams and coins diagrams. In each coins diagram, an arrow has been placed over each coin to indicate which direction it expects to move. 

\begin{lemma}[\cite{Permutoric}]\label{lem:move_expected} 
When a coin moves, it moves in the direction that it expects to move. 
\end{lemma}


The importance of understanding the direction in which a coin expects to move is that it will enable us to understand \dfn{collisions}. 
There are \dfn{two-coins collisions}, which involve two coins that occupy adjacent vertices of $\Path_n$; there are \dfn{left-wall collisions}, which can occur when $\cc_1$ occupies $v_1$; and there are \dfn{right-wall collisions}, which can occur when $\cc_d$ occupies $v_n$. 
The prototypical examples of collisions are when two non-adjacent coins move to become adjacent or when a coin moves to become adjacent to a wall, but other examples are possible when traffic jams of size greater than 1 are involved.

The precise definition of a two-coins collision that occurs in a traffic jam that does not touch a wall is as follows. We say coins $\cc_i$ and $\cc_{i+1}$ are \dfn{butting heads} if they occupy adjacent vertices and $\cc_i$ expects to move right while $\cc_{i+1}$ expects to move left. We say $\cc_{i}$ and $\cc_{i+1}$ are involved in a two-coins collision at a small step if they are not butting heads immediately before the small step and they are butting heads immediately after the small step. 
This can happen either because the two coins were not adjacent prior to the small step, but it can also happen because the two coins were adjacent but one of them changed its mind about the direction it expected to move. 

The definition of a collision has to be slightly modified when considering a traffic jam that touches a wall; the reader may refer to \cite{Permutoric} for details.
%Consider first the case when a small step occurs during which a coin $\cc$ moves so as to join a traffic jam that touches the wall. At the same time, $\cc$ changes its mind so that it now expects to move away from the wall that the traffic jam touches. Nonetheless, if there is a coin $\cc'$ adjacent to $\cc$ after the small step, we still count this as a two-coins collision between $\cc$ and $\cc'$. (We can imagine that there was a brief instant of time right after $\cc$ moved to join the traffic jam but right before it changed its mind about which way it expected to move, thus resulting in $\cc$ butting heads with $\cc'$ very briefly.)
%Similarly, if $\cc$ moved onto $v_1$ (respectively, $v_n$) during this small step (so it is in a traffic jam of size $1$ that touches a wall), then we count this as a left-wall (respectively, right-wall) collision. 

%We now discuss how to define a collision that occurs in the ``interior'' of a traffic jam of size at least $2$ that touches a wall. In such a traffic jam, all the coins always want to move away from the wall, so by the above definition, there would be no collisions within the traffic jam. However, this is not what we want. Instead, suppose we are considering a coin $\cc_i$ that occupies $v_j$. Assume the coins in the traffic jam containing $\cc_i$ occupy vertices $v_{1},v_2,\ldots,v_k$, where $j<k$. Thus, we are assuming the traffic jam touches the left wall, but the symmetrical considerations apply if the traffic jam touches the right wall.
%The stone with the same color as $\cc_i$ carries the replica
%$\vv_{j}$. Suppose there is a small step during which the stone with the same color as $\cc_i$ slides through $\vv_{k+1}$, carrying $\vv_j$ along with it as it slides. Note that $\cc_i$ does not move during this small step. In this case, we say $\cc_i$ collides with $\cc_{i-1}$ (or is involved in a left-wall collision if $i=1$). To explain heuristically why this collision occurs, we can imagine that $\cc_i$ has a ``flicker of confusion'' when it sees the stone with its same color slide through $\vv_{k+1}$. When it sees this, $\cc_i$ ``thinks'' it should change its mind and expect to move left. But then it realizes that it cannot expect to move left because it is in a traffic jam that touches the left wall, so it quickly goes back to expecting to move right. During this brief instant, the collision occurs because $\cc_i$ ``thinks'' it should be butting heads with $\cc_{i-1}$ (or with the left wall if $i=1$).  

We say a collision occurs at time $t$ if it occurs during a small step between times $t-1$ and $t$. 



\begin{example}
Suppose $n=6$ and $d=3$. \Cref{FigNewA} shows some stones diagrams and coins diagrams evolving over time. At each stage, the arrow over a coin points in the direction that the coin expects to move. Collisions are indicated in the coins diagrams by stars, and each star is colored to indicate which stone moves in the small step during which the collision occurs. %Note that the right-wall collision at time $5$ (marked with a gold star in the first small step after time $4$) occurs because $\cc_3$ has a ``flicker of confusion'' when the gold stone $\s_1$ slides through $\vv_4$ (carrying $\vv_6$ along with it as it slides). 
\hfill $\lozenge$
\end{example}
\begin{figure}
  \begin{center}{\includegraphics[width=\linewidth]{PermutoricPIC21}}
  \end{center}
\caption{The evolution of stones diagrams and coins diagrams over time, with each individual small step illustrated. At each moment, we have drawn an arrow over each coin to indicate which direction it expects to move. Each collision is indicated by a star whose color is the same as that of the stone that moved to cause the collision. Each labeling is depicted in red numbers below the path.}\label{FigNewA}
\end{figure}

\begin{example}\label{exam:3}
Suppose $n=6$ and $d=3$. \Cref{Fig6} shows the stones diagrams and coins diagrams of a particular timeline at times $0,1,\ldots,17$. For brevity, we have not shown the individual small steps. All of the collisions the occur at time $t$ (i.e., during the small steps between time $t-1$ and time $t$) are indicated in the coins diagram at time $t$. The color of the star can be used to determine the small step during which the collision occurs. One can check that the states in this timeline are periodic with period $18$. 
\hfill $\lozenge$
\end{example}


\begin{figure}
  \begin{center}{\includegraphics[width=\linewidth]{PermutoricPIC22}}
  \end{center}
\caption{The stones diagrams and coins diagrams of the states in a timeline at times $0,1,\ldots,17$. Here, $n=6$ and $d=3$. The collisions that occur during the small steps between times $t-1$ and $t$ are represented by color-coded stars in the coins diagram at time $t$. Each labeling is depicted by the red numbers below the path. }\label{Fig6}
\end{figure}
 
Let $\Coll_{\mathcal T}$ be the set of all collisions that take place in the coins diagrams of the states of the timeline $\mathcal T$. We define a directed graph with vertex set $\Coll_{\mathcal T}$ by drawing an arrow from a collision $\kappa$ to a collision $\kappa'$ whenever there is a coin involved in both $\kappa$ and $\kappa'$ and the collision $\kappa$ occurs before $\kappa'$. Let $(\Coll_{\mathcal T},\leq_{\mathcal T})$ be the transitive closure of this directed graph. Let ${\bf H}_{\mathcal T}$ be the Hasse diagram of $(\Coll_{\mathcal T},\leq_{\mathcal T})$. This Hasse diagram, which is one of our primary tools, has the shape of a bi-infinite chain link fence (see \Cref{Fig7}). Suppose $\kappa_1\lessdot_{\mathcal T}\kappa_2$ is an edge in ${\bf H}_{\mathcal T}$. Then $\kappa_1$ and $\kappa_2$ are collisions that both use some coin $\cc$; we define the \dfn{energy} of this edge, denoted $\mathcal E(\kappa_1\lessdot_{\mathcal T}\kappa_2)$, to be the number of different vertices that $\cc$ occupies between these two collisions, including the vertices occupied by $\cc$ when the collisions occur. More generally, if $\kappa_1\lessdot_{\mathcal T}\kappa_2\lessdot_{\mathcal T}\cdots\lessdot_{\mathcal T}\kappa_r$ is a saturated chain in ${\bf H}_{\mathcal T}$, then we write $\mathcal E(\kappa_1\lessdot_{\mathcal T}\kappa_2\lessdot_{\mathcal T}\cdots\lessdot_{\mathcal T}\kappa_r)$ for the tuple $(\mathcal E(\kappa_1\lessdot_{\mathcal T}\kappa_2),\ldots,\mathcal E(\kappa_{r-1}\lessdot_{\mathcal T}\kappa_r))$ of energies of the edges in the chain.

\begin{figure}[ht]
  \begin{center}{\includegraphics[height=4.5cm]{PermutoricPIC27}}
  \end{center}
\caption{The Hasse diagram ${\bf H}_{\mathcal T}$, where $\mathcal T$ is the timeline containing the states whose stones diagrams and coins diagrams are shown in \Cref{Fig6}. We have drawn the Hasse diagram sideways (to save vertical space), so each cover relation $\kappa\lessdot_{\mathcal T}\kappa'$ is drawn with $\kappa$ to the left of $\kappa'$. Each collision is represented by a star whose color is the same as that of the stone that moved to cause the collision. Blue numbers indicate the times when the collisions occur. Edges are labeled by their energies. }\label{Fig7}
\end{figure}



A \dfn{diamond} in ${\bf H}_{\mathcal T}$ consists of collisions $\kappa_1,\kappa_2,\kappa_3,\kappa_4$ together with four edges given by cover relations $\kappa_1\lessdot_{\mathcal T}\kappa_2$, $\kappa_1\lessdot_{\mathcal T}\kappa_3$, $\kappa_2\lessdot_{\mathcal T}\kappa_4$, $\kappa_3\lessdot_{\mathcal T}\kappa_4$. 
A \dfn{half-diamond} in ${\bf H}_{\mathcal T}$ consists of collisions $\kappa_1',\kappa_2',\kappa_3'$, where $\kappa_1'$ and $\kappa_3'$ are either both left-wall collisions or both right-wall collisions, together with two edges given by cover relations $\kappa_1'\lessdot_{\mathcal T}\kappa_2'$ and $\kappa_2'\lessdot_{\mathcal T}\kappa_3'$. 
 Our arguments rely crucially on the following lemma. 


\begin{lemma}[\cite{Permutoric}]\label{lem:half-diamond}
In any half-diamond in the Hasse diagram $\bf H_{\mathcal T}$, the two edges have the same energy. In any diamond in the Hasse diagram $\bf H_{\mathcal T}$, opposite edges have the same energy. 
\end{lemma}

%\begin{proof}
%Fix a half-diamond in ${\bf H}_{\mathcal T}$ with edges given by the cover relations $\kappa_1'\lessdot_{\mathcal T}\kappa_2'\lessdot_{\mathcal T}\kappa_3'$. By symmetry, we may assume $\kappa_1'$ and $\kappa_3'$ are both left-wall collisions. Then $\kappa_1'$ and $\kappa_3'$ occur when $\cc_1$ occupies $v_1$. Say $\kappa_2'$ occurs when $\cc_1$ occupies $v_m$. Both edges of the half-diamond have energy $m$.  
%\end{proof}


%\begin{proof}
%Fix a diamond in ${\bf H}_{\mathcal T}$ with edges given by cover relations $\kappa_1\lessdot_{\mathcal T}\kappa_2$, $\kappa_1\lessdot_{\mathcal T}\kappa_3$, $\kappa_2\lessdot_{\mathcal T}\kappa_4$, $\kappa_3\lessdot_{\mathcal T}\kappa_4$. Say the collision $\kappa_1$ involves coins $\cc_i$ and $\cc_{i+1}$ and takes place when $\cc_i$ occupies vertex $v_m$ and $\cc_{i+1}$ occupies vertex $v_{m+1}$. Without loss of generality, suppose $\kappa_2$ involves $\cc_i$ and $\kappa_3$ involves $\cc_{i+1}$. Then $\kappa_2$ occurs when $\cc_i$ occupies some vertex $v_k$ with $k\leq m$, and $\kappa_3$ occurs when $\cc_{i+1}$ occupies some vertex $v_\ell$ with $\ell\geq m+1$. The collision $\kappa_4$ involves the coins $\cc_i$ and $\cc_{i+1}$. We claim that $\kappa_4$ occurs when $\cc_i$ occupies $v_{k+\ell-m-1}$ and $\cc_{i+1}$ occupies $v_{k+\ell-m}$; this will imply that the edges $\kappa_1\lessdot_{\mathcal T}\kappa_2$ and $\kappa_3\lessdot_{\mathcal T} \kappa_4$ both have energy $m-k+1$ and that the edges $\kappa_1\lessdot_{\mathcal T}\kappa_3$ and $\kappa_2\lessdot_{\mathcal T} \kappa_4$ both have energy $\ell-m$. 


%By symmetry, we may assume that $m-k\leq \ell-m-1$. Let $x,y\in[d]$ be such that $\s_x$ and $\s_y$ are the stones with the same colors as $\cc_i$ and $\cc_{i+1}$, respectively. 
%Consider starting at the time when $\kappa_1$ occurs and watching the stones diagrams and coins diagrams evolve as we move forward in time. We will assume that $k<m$, that $x>y$, and that $\cc_i$ moves from $v_m$ to $v_{m-1}$ before $\cc_{i+1}$ moves from $v_{m+1}$ to $v_{m+2}$; the other cases are similar. Let $t_0$ be the first time after the collision $\kappa_1$ when $\cc_i$ moves from $v_m$ to $v_{m-1}$. The coin $\cc_i$ will move from $v_m$ to $v_{m-1}$ and then to $v_{m-2}$ and so on until reaching $v_k$; it will then turn around and move back across $v_{k+1},\ldots,v_m$ and then continue on toward $v_{k+\ell-m-1}$. For $j\in\{k,\ldots,k+\ell-m-1\}$, let $\zeta_j$ be the amount of time that $\cc_i$ spends on $v_j$ during this trip. The coin $\cc_{i+1}$ stays on $v_{m+1}$ for some time after $t_0$; it then moves to the right until reaching $v_{\ell}$, where it turns around and heads back to $v_{k+\ell-m+1}$. For $j'\in\{m+1,\ldots,\ell\}$, let $\xi_{j'}$ be the amount of time after $t_0$ that $\cc_{i+1}$ spends on $v_{j'}$ during this trip. 


%By analyzing the stones diagrams, one can show that $\zeta_j=\xi_{j'}=n-d$ for all $j\in\{k,\ldots,m-1\}$ and all $j'\in\{k+\ell-m+1,\ldots,\ell\}$. Similarly, $\zeta_j=\xi_{j+1}$ for all $j\in\{m,\ldots,k+\ell-m-1\}$. Let $N=(m-k)(n-d)+\sum_{j=m}^{k+\ell-m-1}\zeta_j$. At time $t_0+N$, either the coin $\cc_i$ moves from $v_{k+\ell-m-1}$ to $v_{k+\ell-m}$, or the coin $\cc_{i+1}$ moves from $v_{k+\ell-m+1}$ to $v_{k+\ell-m}$. It follows from the assumption that $x>y$ that, in fact, $\cc_{i+1}$ moves from $v_{k+\ell-m+1}$ to $v_{k+\ell-m}$ at time $t_0+N$. This proves the claim.  
%\end{proof}


For each collision $\kappa\in\Coll_{\mathcal T}$, let $\varphi(\kappa)$ be the collision involving the same set of coins as $\kappa$ that occurs next after $\kappa$. In other words, if $\kappa$ is the bottom element of a diamond (respectively, half-diamond), then $\varphi(\kappa)$ is the top element of that same diamond (respectively, half-diamond). We extend this notation to saturated chains in ${\bf H}_{\mathcal T}$ (including edges) by letting $\varphi(\kappa_1\lessdot_{\mathcal T}\kappa_2\lessdot_{\mathcal T}\cdots\lessdot_{\mathcal T}\kappa_m)=\varphi(\kappa_1)\lessdot_{\mathcal T}\varphi(\kappa_2)\lessdot_{\mathcal T}\cdots\lessdot_{\mathcal T}\varphi(\kappa_m)$. We define the \dfn{period} of ${\bf H}_{\mathcal T}$ to be the smallest positive integer $p$ such that $e$ and $\varphi^p(e)$ have the same energy for every edge $e$ of ${\bf H}_{\mathcal T}$. A \dfn{transversal} of ${\bf H}_{\mathcal T}$ is a saturated chain $\mathscr T=(\kappa_0\lessdot_{\mathcal T}\kappa_1\lessdot_{\mathcal T}\cdots\lessdot_{\mathcal T}\kappa_d)$ such that $\kappa_0$ is a left-wall collision, $\kappa_d$ is a right-wall collision, and $\kappa_i$ involves the stones $\cc_i$ and $\cc_{i+1}$ for every $i\in[d-1]$. In other words, a transversal is a saturated chain that moves from left to right across ${\bf H}_{\mathcal T}$. We define the \dfn{energy composition} of $\mathscr T$ to be the tuple $\mathcal{E}(\mathscr T)=(\varepsilon_1,\ldots,\varepsilon_d)$, where $\varepsilon_i$ is the energy of the edge $\kappa_{i-1}\lessdot_{\mathcal T}\kappa_i$; note that $\mathcal{E}(\mathscr T)\in\Comp_d(n)$. 



\begin{lemma}[\cite{Permutoric}]\label{lem:ERot}
Let $\mathcal T$ be a timeline, and let $\mathscr T$ be a transversal of ${\bf H}_{\mathcal T}$. Then $\mathcal{E}(\varphi(\mathscr T))=\Rot_{n,d}(\mathcal{E}(\mathscr T))$. The period of ${\bf H}_{\mathcal T}$ is equal to the size of the orbit of $\Rot_{n,d}$ containing $\mathcal{E}(\mathscr T)$. 
\end{lemma}

\begin{proof}
The second statement follows from the first because, by \Cref{lem:half-diamond}, the energies of all edges in ${\bf H}_{\mathcal T}$ are determined by the energy composition of a single transversal of ${\bf H}_{\mathcal T}$. The first statement is also immediate from \Cref{lem:half-diamond}. 
\end{proof}

\begin{example}
Suppose $n=6$ and $d=3$. Let ${\bf H}_{\mathcal T}$ be the Hasse diagram from \Cref{Fig7}, and let $\mathscr T=(\kappa_0\lessdot_{\mathcal T}\kappa_1\lessdot_{\mathcal T}\kappa_2\lessdot_{\mathcal T}\kappa_3)$ be the transversal consisting of the collisions that occur at times $2,5,6,10$. Then $\mathcal{E}(\mathscr T)=(2,1,3)\in\Comp_3(6)$. The period of ${\bf H}_{\mathcal T}$ is $3$, which is the size of the $\Rot_{6,3}$-orbit containing $(2,1,3)$. The transversal $\varphi(\mathscr T)$ consists of both the collisions that occur at time $8$ along with the collisions at times $13$ and $16$. We have $\mathcal{E}(\varphi(\mathscr T))=(1,3,2)=\Rot_{6,3}(\mathcal{E}(\mathscr T))$. Similarly, $\mathcal{E}(\varphi^2(\mathscr T))=(3,2,1)=\Rot_{6,3}^2(\mathcal{E}(\mathscr T))$. \hfill $\lozenge$ 
\end{example}


For $k,t\in\ZZ$, let $\sigma_t^{(k)}=\cyc^{-k}(\sigma_{t+k})$. It follows immediately from the definition of a timeline that the sequence $\mathcal T^{(k)}=(\sigma_t^{(k)},t)_{t\in\ZZ}$ is also a timeline; that is, $\nu_t(\sigma_{t-1}^{(k)})=\sigma_t^{(k)}$ for all $t\in\ZZ$. Furthermore, the stones diagram of $(\sigma_t^{(k)},t)$ is obtained from that of $(\sigma_{t+k},t+k)$ by moving all stones and replicas $k$ positions counterclockwise. It follows that the coins diagrams of $(\sigma_t^{(k)},t)$ and $(\sigma_{t+k},t+k)$ are identical. Therefore, if $\kappa$ is a collision in $\Coll_{\mathcal T^{(k)}}$ that occurs at time $t$, then there is a collision $\psi_k(\kappa)\in\Coll_{\mathcal T}$ that occurs at time $t+k$. The resulting map $\psi_k\colon\Coll_{\mathcal T^{(k)}}\to\Coll_{\mathcal T}$ is an isomorphism from $(\Coll_{\mathcal T^{(k)}},\leq_{\mathcal T^{(k)}})$ to $(\Coll_{\mathcal T},\leq_{\mathcal T})$; furthermore, under this isomorphism, corresponding edges of the Hasse diagrams ${\bf H}_{\mathcal T^{(k)}}$ and ${\bf H}_{\mathcal T}$ have the same energy. 

Recall that we write $\mathcal T_\sigma$ for the unique timeline containing the state $(\sigma,0)$. It follows from \Cref{lem:ERot} that the energy compositions of the transversals of ${\bf H}_{\mathcal T_\sigma}$ form a single orbit $\widetilde\Omega(\sigma)$ of $\Rot_{n,d}$. If $\mathcal T_\sigma=(\sigma_t,t)_{t\in\ZZ}$ (so $\sigma_0=\sigma$), then $\Phi_{n,d}(\sigma_0)=\sigma_0^{(n-d)}$, so $\mathcal T_{\Phi_{n,d}(\sigma_0)}=\mathcal T_\sigma^{(n-d)}$. Using the isomorphism $\psi_{n-d}$, we find that $\widetilde\Omega(\sigma_0)=\widetilde\Omega(\Phi_{n,d}(\sigma_0))$. Thus, we obtain a map \[\Omega\colon\Orb_{\Phi_{n,d}}\to\Orb_{\Rot_{n,d}}\] that sends the $\Phi_{n,d}$-orbit containing a labeling $\mu$ to $\widetilde\Omega(\mu)$. In \cite{Permutoric}, we prove that this map satisfies the conditions in \Cref{prop:PhiRot}; we omit the proof here. 

\section{Toric Promotion on a Forest}\label{sec:toric}

Let us briefly mention how the perspective of stones and coins diagrams can be used to prove \cref{thm:toric_main}. Let $G=(V,E)$ be a forest. Let $v_1,\ldots,v_n$ be the vertices of $G$, and let ${\bf v}_1,\ldots,{\bf v}_n$ be their replicas. We can represent a labeling $\sigma\in\Lambda_G$ by placing each replica ${\bf v}_k$ on the vertex $\sigma(v_k)$ of $\Cycle_n$. We again place a stone on a vertex of $\Cycle_n$ to indicate which toggle we are about to apply, and we put a coin on the vertex of $G$ whose replica sits on the stone. 

Let $T$ be the connected component of $G$ containing $\sigma^{-1}(1)$; this is the connected component on which the coin always sits. Let $t$ be the number of vertices of $T$. As we apply the sequence of toggles $\tau_1,\tau_2,\ldots$ (repeating cyclically), the coin will move around to all of the vertices in $T$. One can show that for all vertices $v_j,v_{j'}\in V$ such that $v_j$ is in $T$ and $j\neq j'$, there is a unique time in the interval $[1,t(n-1)]$ during which ${\bf v}_j$ sits on the stone and ${\bf v}_{j'}$ sits one space clockwise of the stone. This implies that if $v_k$ is a vertex of degree $\delta$ in $T$, then there are $n-\delta-1$ times in the interval $[1,t(n-1)]$ when $\vv_k$ rides clockwise one space on the stone, and there are $t-\delta-1$ times in the interval $[1,t(n-1)]$ when $\vv_k$ moves counterclockwise one space because the stone slides through it. On the other hand, if $v_k$ is a vertex that is not in $T$, then $\vv_k$ never rides on the stone, and there are $t$ times in the interval $[1,t(n-1)]$ when $\vv_k$ moves counterclockwise one space because the stone slides through it. It follows that applying $t(n-1)$ toggles has the effect of rotating the stone and all of the replicas counterclockwise by $t$. This implies the desired result.   
\printbibliography

\end{document}