%% 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[final]{FPSAC2022}
%% 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}

%\theoremstyle{theorem}
\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{quest}[thm]{Question}
\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}
\theoremstyle{remark}
\newtheorem{rem}[thm]{Remark}
\newtheorem{exam}[thm]{Example}

\usepackage{algorithm}
\usepackage{algpseudocode}

\usepackage{color, tikz}
\usetikzlibrary{patterns}
\usetikzlibrary{arrows.meta}
\usetikzlibrary{calc}
\newcommand\blfootnote[1]{%
  \begingroup
  \renewcommand\thefootnote{}\footnote{#1}%
  \addtocounter{footnote}{-1}%
  \endgroup}

%\usepackage{lipsum}

%% define your title in the usual way
\title[Sandpile Torsor Algorithm Structures]{Rotor-Routing Induces the Only Consistent Sandpile Torsor Structure on Plane Graphs}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author[A.~Ganguly and A.~MacDonough]{Ankan Ganguly\thanks{\href{mailto:ankan\_ganguly@brown.edu}{ankan\_ganguly@brown.edu}}\addressmark{1} \and Alex McDonough\thanks{\href{mailto:amcd@ucdavis.edu}{amcd@ucdavis.edu}} \addressmark{2}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Applied Mathematics, Brown University. Supported by the United States Army Research Office under grant number W911NF2010133. \\ \addressmark{2}Department of Mathematics, University of California, Davis}

%% 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{A sandpile torsor algorithm is a map which associates each plane graph (\textit{i.e.}\ planar embedding) with a free transitive action of its sandpile group on its spanning trees. We define a notion of consistency, which requires a torsor algorithm to be preserved with respect to a certain class of contractions and deletions. We then show that the rotor-routing sandpile torsor algorithm (which is equivalent to the Bernardi algorithm) is consistent. Furthermore, we demonstrate that there are only three other consistent algorithms, which all have the same structure as rotor-routing. This proves a conjecture of Klivans. The paper corresponding to this extended abstract can be found at \cite{AnkanAlex}. }

%% 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{sandpile group, sandpile torsor, rotor-routing}

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



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Miscellaneous New Commands %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\argmin}{\operatorname{argmin}}
\newcommand{\Aut}{\operatorname{Aut}}
\newcommand{\Col}{\operatorname{Col}}
\newcommand{\Div}{\operatorname{Div}}
\newcommand{\Prin}{\operatorname{Prin}}
\newcommand{\End}{\operatorname{End}}
\newcommand{\Gal}{\operatorname{Gal}}
\newcommand{\Image}{\operatorname{Image}}
\newcommand{\indeg}{\operatorname{indeg}}
\newcommand{\Jac}{\operatorname{Jac}}
\newcommand{\ord}{\operatorname{ord}}
\newcommand{\outdeg}{\operatorname{outdeg}}
\newcommand{\Pic}{\operatorname{Pic}}
\newcommand{\rank}{\operatorname{rank}}
\newcommand{\Lspan}{\operatorname{span}}
\newcommand{\Lcone}{\operatorname{Cone}}
\newcommand{\sign}{\operatorname{sign}}
\newcommand{\im}{\operatorname{im}}
\newcommand{\onechip}{[c-s]}
\newcommand{\rotorto}{\rightsquigarrow}
\newcommand{\rotorequiv}{\leftrightsquigarrow}
\newcommand{\rotoract}[3]{#1\langle #2,#3 \rangle}
\newcommand{\frotoract}[5]{#1_{(#2,#3)}\langle #4,#5 \rangle}

%%%%%%%%%%%%%%%%%%%%%%%%%
% Calligraphic Alphabet %
%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\D}{{\bf D}}
\newcommand{\Z}{{\mathbb Z}}
\newcommand{\R}{{\mathbb R}}
\newcommand{\C}{{\mathbb C}}
\newcommand{\Q}{{\mathbb Q}}
\newcommand{\Acal}{{\mathcal A}}
\newcommand{\Bcal}{{\mathcal B}}
\newcommand{\Ccal}{{\mathcal C}}
\newcommand{\Dcal}{{\mathcal D}}
\newcommand{\Ecal}{{\mathcal E}}
\newcommand{\F}{{\mathcal F}}
\newcommand{\Fcal}{{\mathcal F}}
\newcommand{\Gcal}{{\mathcal G}}
\newcommand{\Hcal}{{\mathcal H}}
\newcommand{\Ical}{{\mathcal I}}
\newcommand{\Jcal}{{\mathcal J}}
\newcommand{\Kcal}{{\mathcal K}}
\newcommand{\Lcal}{{\mathcal L}}
\newcommand{\Mcal}{{\mathcal M}}
\newcommand{\Ncal}{{\mathcal N}}
\newcommand{\Ocal}{{\mathcal O}}
\newcommand{\Ofrak}{{\mathfrak O}}
\newcommand{\Pcal}{{\mathcal P}}
\newcommand{\Qcal}{{\mathcal Q}}
\newcommand{\Rcal}{{\mathcal R}}
\newcommand{\Scal}{{\mathcal S}}
\newcommand{\T}{{\mathcal T}}
\newcommand{\Ucal}{{\mathcal U}}
\newcommand{\Vcal}{{\mathcal V}}
\newcommand{\Wcal}{{\mathcal W}}
\newcommand{\Xcal}{{\mathcal X}}
\newcommand{\Ycal}{{\mathcal Y}}
\newcommand{\Zcal}{{\mathcal Z}}

\newcommand{\what}{\widehat}
\DeclareMathOperator{\id}{id}
\newcommand{\wtilde}{\widetilde}
\newcommand{\val}{{\operatorname{val}}}
\newcommand{\la}{{\langle}}
\newcommand{\ra}{{\rangle}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\anote}[1]{\par 
  \framebox{\begin{minipage}[c]{0.95 \textwidth}\color{blue} ALEX'S NOTE:
      #1 \color{black}\end{minipage}}\par}
      
\newcommand{\gnote}[1]{\par 
  \framebox{\begin{minipage}[c]{0.95 \textwidth}\color{red} ANKAN'S NOTE:
      #1 \color{black}\end{minipage}}\par}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

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

Let $G$ be a finite connected multigraph. The \emph{sandpile group} of $G$, which we denote $\Pic^0(G)$, is a finite abelian group given by the cokernal of the \emph{graph Laplacian matrix} over the integers. A remarkable fact, which follows from Kirchhoff's matrix-tree theorem, is that the size of $\Pic^0(G)$ is equal to the number of \emph{spanning trees} of $G$ (see \cite[Theorem 7.3]{Biggs}). The traditional proof of this result is non-bijective, and for many graphs, no  automorphism invariant bijections exist unless $G$ is given additional structure (see \cite[Theorem 8.1]{Wagner}). This problem is often resolved by working with \emph{ribbon graphs}. 

Let $\chi$ specify a cyclic ordering on the edges adjacent to each vertex of $G$. The pair $(G,\chi)$ is called a \emph{ribbon graph}. Holroyd \textit{et al.}\ demonstrated that the \emph{rotor-routing algorithm} induces a \emph{free transitive group action} of $\Pic^0(G)$ on $\T(G)$, which depends on the ribbon structure $\chi$ and a choice of \emph{sink} vertex~\cite{Holroyd}. In particular, this makes $\T(G)$ a $\Pic^0(G)$-\emph{torsor}, so we will call such an action a \emph{sandpile torsor action}.

On a MathOverflow post, Ellenberg asked if there exist certain classes of ribbon graphs for which natural sandpile torsor actions can be defined without requiring a sink vertex~\cite{JSE}. Chan, Church, and Grochow resolved this question by showing that the rotor-routing sandpile torsor action on $(G,\chi)$ is independent of the sink vertex if and only if $(G,\chi)$ is a \emph{plane graph}~\cite[Theorem 2]{CCG}.\footnote{Following the language of~\cite{BW}, we distinguish between a \emph{plane graph}, which is a particular planar embedding, and a \emph{planar graph} which is a graph where such an embedding exists.} With this result in mind, we define a \emph{sandpile torsor algorithm} to be a function which assigns a sandpile torsor action to every plane graph $(G,\chi)$ independent of the choice of sink vertex. 

Another sink-dependent sandpile torsor action is given by the \emph{Bernardi algorithm}~\cite{Bernardi}, which is distinct from rotor-routing on non-planar ribbon graphs. Baker and Wang showed that the restriction of the Bernardi algorithm to plane graphs is also a sandpile torsor algorithm~\cite[Theorem 5.1]{BW}. Furthermore, they showed that this sandpile torsor algorithm is equivalent to the rotor-routing algorithm (when restricted to plane graphs)~\cite[Theorem 7.1]{BW}. This surprising equivalence motivated the following conjecture by Klivans, which we prove in this paper. 

\begin{conj}[{\cite[Conjecture 4.7.17]{Klivans}}]\label{conj:klivans}
For plane graphs, there is only one sandpile torsor structure. 
\end{conj}

One of the challenges in resolving this conjecture is that one must introduce a reasonable definition of \emph{sandpile torsor structure}. The rotor-routing sandpile torsor algorithm follows a simple set of rules that can be applied to any plane graph. With this in mind, we posit that any definition of \emph{sandpile torsor structure} should include some notion of consistency of induced sandpile torsor actions between different plane graphs. However, it is difficult to find a suitable consistency condition because there is no general map between the sandpile groups of different graphs which preserves their structure. The key insight that motivated the writing of this paper is the formulation of a contraction-deletion based definition of consistency (see Definition~\ref{def:consistent} and Figure~\ref{fig:consistent}).\\

\textbf{There are two main results in this paper}. In Theorem~\ref{thm:rrconsistent}, we show that rotor-routing is \emph{consistent}. In Theorem~\ref{thm:onestructure} we show that there are only 3 other consistent sandpile torsor algorithms, which can be obtained from rotor-routing by reversing the cyclic order on the vertices, taking the inverse action, or both. We say that these algorithms all have the same \emph{structure} as rotor-routing. One powerful tool that we introduce is Proposition~\ref{prop:sourceturn}, which implies that on any 2-connected graph, it is possible to transform one spanning tree to any other by repeatedly swapping leaf edges with edges not on the tree.

\section{Background and Definitions}\
\subsection{Divisors, Ribbon Graphs, and the Sandpile Group}
In this section, we use much of the notation from~\cite{CCG}. See also~\cite{divisorsbook,Klivans} for more information on sandpile groups and chip-firing.

Let $G$ be a finite, connected, undirected graph with vertices $V(G)$ and edges $E(G)$. We allow multiple edges but not loop edges. For an edge $e \in E(G)$, we write $i(e)$ for the unordered pair of vertices incident to $e$, which we write in set notation.

\begin{defn}
The group $\Div^0(G)$ of \emph{degree-0 divisors} of $G$ is given by

\[\Div^0(G) := \left\{\sum_{v \in V(G)}n_vv\mid n_v\in\Z, \sum_{v \in V(G)}n_v = 0\right\}.\]

 For $D = \sum n_v v$, if there exists an $s \in V(G)$ such that $n_v \geq 0$ for $v \neq s$, then we say that $D \in \Div^0_s(G)$.
\end{defn}

 Note that while $\Div^0(G)$ is a group, $\Div_s^0(G)$ is a \emph{monoid} because its nonzero elements lack inverses. The \emph{Laplacian matrix} $\Delta$ of $G$ is the symmetric matrix defined by $\Delta = \text{deg}(G) - A$, where $A$ is the adjacency matrix of $G$ and $\text{deg}(G)$ is the $|V(G)|\times |V(G)|$ diagonal matrix such that $\text{deg}(G)_{vv} = \text{deg}(v)$ for every $v \in V(G)$.

\begin{defn}
The \emph{sandpile group} of $G$, denoted $\text{Pic}^0(G)$, is the quotient
\[\Pic^0(G) := \Div^0(G)/\im_\Z(\Delta).\]
\end{defn} 

One way to explore properties of $\Pic^0(G)$ is in terms of ``chip-firing'', also called ``the dollar game'', which we describe below. 

Each element $D := \sum_{v\in V(G)} n_vv\in \Div^0(G)$ may be viewed as a configuration of ``chips'' placed on the vertices of $G$, also allowing negative ``debt'' chips (where the total number of chips matches the total amount of debt). Note that elements of $\Div^0_s(G)$ have all of their debt on the sink. In this context, divisors are also called \emph{chip configurations}. Given a chip configuration $D$, we may ``fire'' a vertex $v \in V(G)$ by removing $\deg(v)$ chips from $v$ and placing one chip on each of the neighbors of $v$. That is, $v$ ``gifts'' a chip to each of its neighbors. For our purposes, we allow a vertex to fire regardless of the number of chips, even if this puts the vertex in debt. 

Each row of the Laplacian corresponds to a vertex firing. Thus, the image of the Laplacian describes an equivalence relation on chip configurations, where $D_1$ and $D_2$ are \emph{firing equivalent} if $D_2$ can be obtained from $D_1$ by a sequence of vertex firings. This means that two chip configurations are firing equivalent precisely when they are both representatives of the same equivalence class of $\Pic^0(G)$. 

Throughout this paper, we will put brackets around a divisor to indicate the corresponding equivalence class of $\Pic^0(G)$. As discussed in the previous paragraph, for $D,D' \in \Div^0(G)$, $[D] = [D']$ if and only if these two divisors are firing equivalent. We consider $D,D' \in \Div^0_s(G)$ to be firing equivalent if they are firing equivalent as elements of $\Div^0(G)$.

Let $\mathcal T(G)$ be the set of spanning trees of $G$. For convenience, we will treat each $T \in \T(G)$ as a subset of $E(G)$ when discussing set containment and as a subgraph of $G$ when contracting or deleting edges. The following is a version of Kirchhoff's celebrated matrix-tree theorem. 

\begin{thm}[Sandpile Matrix-Tree Theorem for Graphs~{\cite[Theorem 7.3]{Biggs}}]\label{thm:mtt}
\[|\Pic^0(G)| = |\mathcal T(G)|.\] 
\end{thm}

 Theorem~\ref{thm:mtt} implies the existence of bijections between equivalence classes of $\Pic^0(G)$ and elements of $\mathcal T(G)$. However, in order to define sufficiently ``natural'' bijections, we will need to give $G$ some additional structure (see~\cite{Wagner} and \cite{CCG} for discussion on the need for additional structure). 

Let $\chi$ be a function which maps each $v \in V(G)$ to a cyclic order of edges around $v$. The pair $(G,\chi)$ is called a \emph{ribbon graph}. Suppose that $G$ can be drawn in a plane such that for every $v \in V(G)$, $\chi(v)$ gives the edges incident to $v$ in counterclockwise order. Then, $(G,\chi)$ is called a \emph{plane graph}. A graph $G$ is called \emph{planar} if there exists some $\chi$ such that $(G,\chi)$ is a plane graph. 

Suppose $e \in E(G)$ with $i(e) = \{v,w\}$. We will write $\chi(v,e)$ for the edge after $e$ that is incident to $v$ with respect to $\chi$. 

%A \emph{ribbon graph isomorphism} is a standard graph isomorphism between two ribbon graphs that respects the cyclic order assigned to both ribbon graphs. A \emph{ribbon graph automorphism} is a ribbon graph isomorphism from a ribbon graph to itself. It is well-known that any ribbon graph isomorphism $\phi$ from $(G,\chi)$ to $(G',\chi')$ induces an bijection from $\T(G)$ to $\T(G')$ and isomorphisms from $\Div^0(G)$ to $\Div^0(G')$, $\Div^0_s(G)$ to $\Div^0_{\phi(s)}(G')$ and $\Pic^0(G)$ to $\Pic^0(G')$.

\begin{defn}
\label{def::auto}
Let $(G,\chi)$ and $(G',\chi')$ be two ribbon graphs. Then a \emph{ribbon graph isomorphism} is a bijection, $\phi: V(G)\cup E(G) \to V(G')\cup E(G')$ such that $\phi(V(G)) = V(G')$ and for any $e \in E(G)$ such that $i(e) = \{v_1,v_2\}$,

\begin{enumerate}
    \item $i(\phi(e)) = \{\phi(v_1),\phi(v_2)\}$;
    \item $\phi(\chi(v_i,e)) = \chi'(\phi(v_i),\phi(e))$, for $i \in \{1,2\}$.
\end{enumerate}

 A \emph{ribbon graph automorphism} is a ribbon graph isomorphism from a ribbon graph to itself.
\end{defn}

\begin{lem}
Any ribbon graph isomorphism from $(G,\chi)$ to $(G',\chi')$ induces an bijection from $\T(G)$ to $\T(G')$. Furthermore, \(\phi\) induces an isomorphism $\phi^{\text{Div}}$ from $\Div^0(G)$ to $\Div^0(G')$ which also describes isomorphisms from $\Div^0_s(G)$ to $\Div^0_{\phi(s)}(G')$ and $\Pic^0(G)$ to $\Pic^0(G')$.
\end{lem}


\subsection{Sandpile Torsor Actions and Sandpile Torsor Algorithms}
Given a ribbon graph $(G,\chi)$ and a vertex $s \in V(G)$, we will work with a function $\alpha_{(G,\chi,s)}: \Div_s^0(G) \times \T(G) \to \T(G)$ which belongs to a specific class of \emph{monoid actions}.

\begin{defn}\label{def:torsor}
A function of the form $\what \alpha_{(G,\chi,s)}$ is called a \textit{sink-dependent sandpile torsor action} if for any $T\in \T(G)$, and $D,D' \in \Div_s^0(G)$, the following properties are satisfied:
\begin{enumerate}
\item $\what \alpha_{(G,\chi,s)}(D,T) = \what\alpha_{(G,\chi,s)}(D',T)$ if and only if $[D] = [D'].$
\item $\what \alpha_{(G,\chi,s)}([0],T) = T$.
    \item  $\what \alpha_{(G,\chi,s)}(D+D',T) = \what \alpha_{(G,\chi,s)}(D,\what \alpha_{(G,\chi,s)}(D',T))$. 
    \item For any $T' \in \T(G)$, there exists some $D'' \in \Div_s^0(G)$ such that $\what \alpha_{(G,\chi,s)}(D'',T) = T'$. 
\end{enumerate}
\end{defn}

\begin{defn}
The function $\what \alpha$ is called a \textit{sink-dependent sandpile torsor algorithm} if for any ribbon graph $(G,\chi)$ and $s \in V(G)$, the following conditions hold:
\begin{enumerate}
\item  $\what \alpha_{(G,\chi,s)}$ is a sink-dependent sandpile torsor action.

\item For any ribbon graph isomorphism $\phi$ from $(G,\chi)$ to $(G',\chi')$, and any $D \in \Div_s^0(G)$,
\[\phi(\what \alpha_{(G,\chi,s)}(D,T)) = \what \alpha_{(G',\chi',\phi(s))}(\phi^{\text{Div}}(D),\phi(T)).\]
\end{enumerate}
\end{defn}

\begin{defn}\label{def:STA}
For every \emph{plane graph} $(G,\chi)$, let $\alpha_{(G,\chi)}$ be an action of $\Pic^0(G)$ on $\T(G)$. We call $\alpha$ a \textit{sandpile torsor algorithm} if there is a sink-dependent sandpile torsor algorithm $\what \alpha$ such that for every \emph{plane graph} $(G,\chi)$, $s \in V(G)$, $D \in \Div_s^0(G)$, and $T \in \T(G)$, 
\[\alpha_{(G,\chi)}([D],T) = \what \alpha_{(G,\chi,s)}(D,T).\]
We call a specific action of the form $\alpha_{(G,\chi)}$ a \emph{sandpile torsor action}. 
\end{defn}

\begin{rem}
If we were to replace \emph{plane graph} with \emph{ribbon graph} in Definition~\ref{def:STA}, then it would follow that no sandpile torsor algorithms exist (see~\cite[Figure 1]{alextorsors}). 
\end{rem}

%Notice that a sandpile torsor algorithm $\alpha$ is uniquely defined by a sink-dependent sandpile torsor algorithm $\what \alpha$ which satisfies the following condition: For every plane graph $(G,\chi)$, $s,s' \in V(G)$, $D \in \Div_s^0(G)$, $D' \in \Div_{s'}^0(G)$, and $T \in \T(G)$, we have:
Notice that a sandpile torsor algorithm $\alpha$ is uniquely defined by a sink-dependent sandpile torsor algorithm $\what \alpha$ such that for every plane graph $(G,\chi)$, $s,s' \in V(G)$, $D \in \Div_s^0(G)$, $D' \in \Div_{s'}^0(G)$, and $T \in \T(G)$, 
\begin{equation}\label{eq:sinkinvariant}\what\alpha_{(G,\chi,s)}(D,T) = \what \alpha_{(G,\chi,s')}(D',T) \text{ if and only if } [D] = [D'].\end{equation}

Two well-known sink-dependent sandpile torsor algorithms are the \emph{rotor-routing algorithm} and the \emph{Bernardi algorithm}. These algorithms are distinct in general, and their constructions appear unrelated~\cite[Figure 9]{BW}. However, both algorithms satisfy \eqref{eq:sinkinvariant}~\cite{CCG,BW}, and they both define the same sandpile torsor algorithm~\cite[Theorem 7.1]{BW}. This surprising equivalence inspired Conjecture~\ref{conj:klivans}, which asks if this sandpile torsor algorithm is in some sense unique. We will not explicitly work with the Bernardi algorithm in this paper, but we encourage the curious reader to see~\cite{BW} for its construction, as well as~\cite{Yuengeometric} for an alternate perspective when restricting to plane graphs. 


\subsection{Rotor-Routing}

Let $(G,\chi)$ be a ribbon graph and $s \in V(G)$. 
\begin{defn}
A \emph{rotor configuration with sink $s$} is an assignment of an incident edge to every vertex of $G$ except for $s$. Given a rotor configuration $\rho$ and $x \in V(G) \setminus s$, we write $\rho\la x \ra$ for the edge assigned to $x$. 
\end{defn}

 We will call these edges \emph{rotors}. It is useful to visualize a rotor $\rho\la x\ra$ as a directed edge adjacent to $x$ and oriented away from $x$. Given a fixed sink $s \in V(G)$, any tree $T \in \T(G)$ can be uniquely represented by a rotor configuration $T_s$ such that for all $x \in V(G)\setminus\{s\}$,  $T_s\la x\ra$ is the unique edge in $T$ incident to $x$ along the path from $x$ to $s$. Then, $T_s$ describes an orientation of the edges of $T$ such that each edge is directed toward $s$. Given a sandpile element of the form $c-s \in \Div^0_s(G)$ for some $c,s \in V(G)$ (which we will call the chip and sink vertices respectively), Algorithm \ref{alg:rotor} describes a sequence of rotor configurations in which at each step, a single rotor rotates according to the cyclic order $\chi$ (on a plane graph, this would be a counterclockwise rotation). The output rotor configuration will be of the form $T'_s$ for some other spanning tree $T' \in \T(G)$, which we will use to construct a sink-dependent sandpile torsor algorithm $r$. 
%and visualize them as edges adjacent to $varrows whose tail is fixed and whose head can spin around. Given any $T \in \T(G)$, we can obtain a rotor configuration with sink $s$ by directing each edge toward $s$ along $T$. We will denote this rotor configuration by $T_s$. 
%Consider the following algorithm:

\begin{algorithm}
\caption{Single-chip rotor-routing}\label{alg:rotor}
\hspace*{\algorithmicindent} \textbf{Input:} A tree $T\in \T(G)$ and a divisor of the form $c-s \in \Div_s^0(G)$.  \\
\hspace*{\algorithmicindent} \textbf{Output:} The rotor configuration $\rho$ with sink vertex $s$.
\begin{algorithmic}
\State Initialize the rotor configuration $\rho = T_s$.
\State Initialize a ``traveling'' vertex $x$ at $c$. We call $x$ a \emph{chip}.
\While{ $x \not= s$}
\State Update $\rho$: $\rho \la x \ra = \chi(x,\rho \la x \ra)$. \Comment{rotate the rotor at $x$ by one position.}
\State Replace $x$ with the other vertex incident to $\rho \la x \ra$. \Comment{move $x$ across the rotor.}
\EndWhile\\
\Return $\rho$.
\end{algorithmic}
\end{algorithm}

 Algorithm~\ref{alg:rotor} was first explored by Priezzhev \textit{et al.}\ under the name \emph{Eulerian walkers model}~\cite{eulerianwalkers}. By \cite[Lemma 3.10]{Holroyd}, the final rotor $\rho$ in Algorithm~\ref{alg:rotor} is acyclic which implies the existence of a unique tree $T'\in \T(G)$ such that $T'_s = \rho$. Then, for the inputs $c,s \in V(G)$ and $T \in \T(G)$, we can define the mapping $r_{(G,\chi,s)}(c-s,T) := T'$ where $T'_s = \rho$ is the output of Algorithm~\ref{alg:rotor}.

Holroyd \textit{et al.}\ showed how this model could be used to define a sink-dependent sandpile torsor action on any ribbon graph $(G,\chi)$. Fix any $D = \sum_{v \in V(G)}n_vv\in \Div^0_s(G)$ and let $N := -n_s$. Note that $D = \sum_{i=1}^{N} (c_i - s)$ for some sequence of vertices $(c_1,\dots,c_{N})$. Let $T^0 = T$, and for each $i \in [1,N]$, let $T^i = \what r_{(G,\chi,s)}(c_i-s,T^{i-1})$. Then, we define $\what r_{(G,\chi,s)}(D,T) := T^{N}$. By \cite[Corollary 2.6]{Holroyd}, $T^{N}$ does not depend on the ordering of $(c_1,\dots,c_{N})$. Thus, $\what r_{(G,\chi,s)}$ is a well-defined monoid action of $\Div^0_s(G)$ on $\T(G)$. 


%We construct this algorithm below and will denote it by $r$. 

%Suppose that we are given $T \in \T(G)$, $s \in V(G)$, and $D \in \Div^0_s(G)$. If $D$ can be written in the form $c-s$ for some $c$, then to get $r_{(G,\chi)}(c-s,T)$, we apply Algorithm~\ref{alg:rotor} to the rotor configuration $T_s$ and the chip $c$. By~\cite[Lemma 3.10]{Holroyd}, the resulting rotor configuration is acyclic, which means it is equal to $T'_s$ for some $T' \in \T(G)$. We define $r_{(G,\chi)}(c-s,T) = T'$.

%In general, we can always write $D = \sum (c_i - s)$ for some $\{c_1,\dots, c_i\}$. To compute $r_{(G,\chi)}(T,D)$ we successively apply Algorithm~\ref{alg:rotor} to each $c_i$. By~\cite[Corollary 2.6]{Holroyd}, we get the same final result regardless of which order the $c_i$ are chosen. Thus, for every $(G,\chi)$, $r_{(G,\chi)}$ is a well-defined action of $\Div^0_s(G)$ on $\T(G)$. 

\begin{thm}[{\cite[Theorem 2.5]{LL}}]
The rotor-routing algorithm $\what r$ constructed above is a sink-dependent sandpile torsor algorithm. 
\end{thm}

Chan, Church, and Grochow proved that, on plane graphs, the rotor-routing action does not depend on the choice of sink vertex, which implies the following result: 

\begin{thm}{\cite[Theorem 2]{CCG}}\label{thm:rristorsor}
The rotor-routing algorithm $\what r$ satisfies (\ref{eq:sinkinvariant}). In particular, it defines a sandpile torsor algorithm $r$. 
\end{thm}

\section{Rotor-Routing is Consistent}

In this section, we introduce the notion of \emph{consistency} of sandpile torsor algorithms and show that the rotor-routing algorithm is consistent. 

Throughout this section, $(G,\chi)$ is a plane graph, $f \in E(G)$, and $i(f) = \{c,s\}$. For $e \in E(G)$, we write $G \setminus e$ for the graph we obtain from $G$ by \emph{deleting} edge $e$ and $G/e$ for the graph we obtain by \emph{contracting} the edge $e$. After contracting $e$, we also remove all loop edges because these cannot occur on any spanning tree and have no effect on the rotor-routing algorithm. 

\begin{defn}\label{def:condelchi} Let $(G,\chi)$ be a ribbon graph with $e \in E(G)$, where $i(e) = \{x,y\}$. 
\begin{itemize}
    \item Define $\chi\setminus e$ to be equal to $\chi$, except with $e$ removed from $\chi(x)$ and $\chi(y)$.
    \item Suppose that after removing edges parallel to $e$, $\chi(x) = (e,e_1,e_2,\dots,e_p)$ and $\chi(y) = (e,\what e_1,\what e_2,\dots,\what e_l)$. Define $\chi/e$ to be equal to $\chi$ except that on the contracted edge $z$, we have 
    \[(\chi/e)(z) := (e_1,e_2,\dots,e_p,\what e_1,\what e_2,\dots,\what e_l).\] 
\end{itemize}
\end{defn}

Notice that $(G\setminus e,\chi\setminus e)$ and $(G/e,\chi/e)$ are both plane graphs. If $(G',\chi')$ can be obtained from $(G,\chi)$ through deletion and contraction, we say $(G',\chi')$ is a \emph{minor} of~$(G,\chi)$. 
\begin{defn}\label{def:consistent}
A sandpile torsor algorithm $\alpha$ is \emph{consistent} if for every plane graph $(G,\chi)$, every choice of $f \in E(G)$, and every choice of $T \in \T(G)$, the following three properties hold (where we define $\{c,s\} = i(f)$):
\begin{enumerate}
\item For any $e \in E(G)$ such that $i(e) \neq \{c,s\}$, if $e \in T\cap \alpha_{(G,\chi)}(\onechip,T)$, then
    \[\alpha_{(G,\chi)}(\onechip,T)\setminus {e} = \alpha_{(G/ {e},\chi/e)}(\onechip,T\setminus e).\]
\item For any $e \in E(G)$, if $e \notin T\cup \alpha_{(G,\chi)}(\onechip,T)$, then
    \[ \alpha_{(G,\chi)}(\onechip,T) = \alpha_{(G\setminus {e},\chi\setminus {e})}(\onechip,T).\]
    \item For any $e \in E(G)\setminus f$, if there is a cut vertex $x$ such that all paths from $e$ to $f$ pass through $x$, then
    \[ e \in T \text{ if and only if } e \in \alpha_{(G,\chi)}(\onechip, T).\]
    \end{enumerate}
\end{defn}


The first two conditions of Definition~\ref{def:consistent} are illustrated by Figure~\ref{fig:consistent}. The third condition says that we can treat two subgraphs joined at a cut vertex independently. 

\begin{prop}\label{prop:rrpart3}
Condition 3 of Definition~\ref{def:consistent} is satisfied by the rotor-routing algorithm. 
\end{prop}

By requiring consistent sandpile torsor algorithms to satisfy Condition 3, we simplify the proofs of many of the results in Section~\ref{sec:unique}. However, we are not convinced that this condition is necessary. 
\begin{quest}\label{quest:con3unneeded}
Is Condition 3 of Definition~\ref{def:consistent} implied by the other two?
\end{quest}

\begin{thm}\label{thm:rrconsistent} The rotor-routing sandpile torsor algorithm is consistent. 
\end{thm}

 We reduce this result to 6 specific cases. If an edge $e$ is in both $T$ and $T' := r_{(G,\chi)}(\onechip,T)$, then the rotor at $e$ may be untouched during rotor-routing, it may complete a full rotation, or it could be oriented in opposite directions in $T_s$ and $T'_s$. When the edge $e$ is in neither tree, the travelling vertex may never have crossed $e$, it may have crossed $e$ in both directions, or it may have only crossed $e$ in one direction. For some of these cases, the path of the traveling vertex will change after deleting or contracting $e$, but we show that it still crosses the same edges, just in a different order. The planarity condition comes into play for the final case (where the edge is crossed in one direction). We apply tools developed by Chan, Church, and Grochow to show that this case is never realized~\cite{CCG}. 


\section{Uniqueness of Consistent Torsor Algorithms}\label{sec:unique}
In this section, we classify the consistent sandpile torsor algorithms. In particular, we show that every consistent sandpile torsor algorithm must either be rotor-routing, or one of three related algorithms which we say have the same \textit{structure} as rotor-routing. 

For any ribbon graph $(G,\chi)$, let $\overline \chi$ be the reverse cyclic order around each vertex. Notice that if $(G,\chi)$ is a plane graph, then $(G,\overline \chi)$ is a plane graph as well (simply reflect the planar embedding of $(G,\chi)$ to get a planar embedding of $(G,\overline{\chi})$).

\begin{defn}
Suppose $\alpha$ is a sandpile torsor algorithm. Define $\overline{\alpha}$, $\alpha^{-1}$, and $\overline{\alpha}^{-1}$ such that for any plane graph $(G,\chi)$, $S \in \Pic^0(G)$, and $T \in \mathcal T(G)$, we have:
\[\alpha_{(G,\chi)}(S,T) = \overline{\alpha}_{(G,\overline \chi)}(S,T) = \alpha^{-1}_{(G,\chi)}(-S,T) = \overline{\alpha}^{-1}_{(G,\overline \chi)}(-S,T).\]
\end{defn}

 If $\alpha$ is the rotor-routing algorithm, then $\overline{\alpha}$ reverses the direction in which the rotors turn, $\alpha^{-1}$ switches the role of the chip and sink, and $\overline{\alpha}^{-1}$ makes both of these changes. 

\begin{prop}\label{prop:otherts}
If $\alpha$ is a consistent sandpile torsor algorithm, then $\overline{\alpha}$, $\alpha^{-1}$ and $\overline{\alpha}^{-1}$ are distinct consistent sandpile torsor algorithms.
\end{prop}

\begin{defn}
Sandpile torsor algorithms $\alpha$ and $\beta$ have the same \textit{sandpile torsor structure} if $\beta \in \{\alpha,\overline{\alpha},\alpha^{-1},\overline{\alpha}^{-1}\}$. 
\end{defn}

 Our goal will be to prove the following version of Conjecture~\ref{conj:klivans}. 

\begin{thm}\label{thm:onestructure}
Every consistent sandpile torsor algorithm has the same sandpile torsor structure as the rotor-routing algorithm. 
\end{thm}

 To show that a sandpile torsor algorithm $\alpha$ is equivalent to rotor-routing, it suffices to check that $\alpha$ and $r$ are equivalent for all $T \in \T(G)$ on a generating set of $\Pic^0(G)$. In fact, we can further simplify the task by applying the following result. 

\begin{prop}\label{prop:sourceturn}
Suppose that $(G,\chi)$ is a 2-connected ribbon graph, $T, \widehat T \in \T(G)$, and $s \in V(G)$. It is possible to transform $T_s$ to $\widehat T_s$ by only rotating rotors with indegree 0 (with respect to the current rotor configuration). 
\end{prop}

 We prove this proposition by defining a partial order on spanning trees such that $\widehat T$ is the unique minimal element. We then show that for any $T \in \T(G)\setminus \widehat{T}$, it is always possible to rotate rotors with indegree 0 to reach some $T'$ that is smaller than $T$ with respect to our partial order. This is further discussed in Figure~\ref{fig:sourceturn}.

\begin{defn}
Let $T \in \T(G)$ and $c,s\in V(G)$. The pair $(c-s,T)$ is called a \emph{source-turn pair} if $c$ is only incident to a single edge of $T$, and $i(\chi(c,T_s\la c \ra)) = \{c,s\}$.  
\end{defn}

 Notice that if $(c-s,T)$ is a source-turn pair, then $T' := r_{(G,\chi)}([c-s],T)$ rotates the indegree 0 rotor at $c$ by one position without changing any other rotors on the graph. Furthermore, setting $s'$ to be the unique vertex such that $\{c,s'\} = i(\chi(c,T'_s\la c\ra))$, we have that $(c-s',T')$ is also a source-turn pair. Therefore, repeated application of the rotor-routing algorithm can be used to freely rotate the rotor at $c$ without changing any other rotors on the graph. This implies the following corollary of Proposition~\ref{prop:sourceturn}. 

\begin{cor}\label{cor:sourceenough}
Let $(G,\chi)$ be a 2-connected plane graph. If $\alpha_{(G,\chi)}([c-s],T) = r_{(G,\chi)}([c-s],T)$ whenever $(c-s,T)$ is a source-turn pair, then $\alpha_{(G,\chi)} = r_{(G,\chi)}$. 
\end{cor}

We now sketch a proof of Theorem~\ref{thm:onestructure}. Let $\alpha$ be a consistent sandpile torsor algorithm and $(G,\chi)$ be a 2-connected plane graph. Suppose for the sake of induction that $\alpha_{(G',\chi')} = r_{(G',\chi')}$ for all 2-connected minors $(G',\chi')$ of $(G,\chi)$. By Corollary~\ref{cor:sourceenough}, the result follows if we show that $\alpha_{(G,\chi)}([c-s],T) = r_{(G,\chi)}([c-s],T)$ for every source-turn pair $(c-s,T)$. 

Let $(c-s,T)$ be an arbitrary source-turn pair, and suppose that $\alpha_{(G,\chi)}([c-s],T) = \what T \not= r_{(G,\chi)}([c-s],T)$. By applying properties of Definition~\ref{def:consistent}, one can show that
\begin{equation}
\label{eq:nonsharededges}
E(G)\setminus (T\Delta \what T) \subseteq \{f,g\},
\end{equation}
where $\Delta$ denotes the symmetric difference operator. This leaves us with 4 cases to consider corresponding to the 4 subsets of $\{f,g\}$. The bulk of our argument is spent resolving these cases using a variety of contraction/deletion tricks, properties of $\Pic^0(G)$, tools developed by Chan, Church, and Grochow, and other techniques (see~\cite{AnkanAlex}). 

\section{Generalization to Regular Matroids}

\emph{Regular matroids} also have associated \emph{sandpile groups}~\cite{Merino}. Given a regular matroid $M$ and a choice of \emph{acyclic circuit and cocircuit signatures}, Backman, Baker, and Yuen defined an explicit free transitive action of the sandpile group of $M$ on its \emph{bases}~\cite{BBY}. We call such an action a \emph{matroidal sandpile torsor algorithm}. We can naturally generalize the notions of \emph{consistency} and \emph{sandpile torsor structure} to this context (see \cite[Section 6]{AnkanAlex}). We conclude with the natural extension of Conjecture~\ref{conj:klivans} to regular matroids.

\begin{conj}\label{quest:allcompat}
For regular matroids, there is only one sandpile torsor structure. 
\end{conj}

\acknowledgements{The authors would like to thank Caroline Klivans for initially suggesting the project and for helpful discussion as well as Richard Kenyon for suggesting we look for properties involving contractions and deletions. Finally, we thank Cyrus Peterpaul for many fruitful discussions on this topic. }

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

\begin{figure}[t]
\begin{center}
\begin{tikzpicture}[scale= 0.9]
    
    \tikzstyle{pt} = [circle,fill,inner sep=1pt,minimum size = 1.5mm]
    \tikzstyle{coin} = [draw,circle,inner sep=1pt,minimum size = 2mm]
    
    \begin{scope}[shift={(0,0)}]
    \node[pt] (ha) at (0,0) {};
    \node[pt](hb) at (1,0){} ;
    \node[pt,label={west:{$s$}}](hc) at (0,1){};
    \node[pt,label={east:{$c$}}](hd) at (1,1){};
    \end{scope} 
    
    \begin{scope}[shift={(2.5,0)}]
    \node[pt] (a) at (0,0) {};
    \node[pt](b) at (1,0){} ;
    \node[pt](c) at (0,1){};
    \node[coin](d) at (1,1){};
    \end{scope} 
    
    \begin{scope}[shift={(5,0)}]
    \node[coin](2a) at (0,0) {};
    \node[pt](2b) at (1,0){} ;
    \node[pt](2c) at (0,1){};
    \node[pt](2d) at (1,1){};
    \end{scope}
    
    \begin{scope}[shift={(7.5,0)}]
    \node[pt](3a) at (0,0) {};
    \node[pt](3b) at (1,0){} ;
    \node[coin](3c) at (0,1){};
    \node[pt](3d) at (1,1){};
    \end{scope}
    
    \begin{scope}[shift={(10,0)}]
    \node[pt](3ea) at (0,0) {};
    \node[pt](3eb) at (1,0){} ;
    \node[pt,label={west:{$s$}}](3ec) at (0,1){};
    \node[pt,label={east:{$c$}}](3ed) at (1,1){};
    \end{scope}
    
    \begin{scope}[shift={(0,-3)}]
    \node[pt] (4ha) at (0,0) {};
    \node[pt,label={west:{$s$}}](4hc) at (0,1){};
    \node[pt,label={east:{$c$}}](4hd) at (1,1){};
    \end{scope}
    
    \begin{scope}[shift={(2.5,-3)}]
    \node[pt](4a) at (0,0) {};
    \node[pt](4c) at (0,1){};
    \node[coin](4d) at (1,1){};
    \end{scope}
    
    \begin{scope}[shift={(5,-3)}]
    \node[coin](5a) at (0,0) {};
    \node[pt](5c) at (0,1){};
    \node[pt](5d) at (1,1){};
    \end{scope}
    
    \begin{scope}[shift={(7.5,-3)}]
    \node[pt](6a) at (0,0) {};
    \node[coin](6c) at (0,1){};
    \node[pt](6d) at (1,1){};
    \end{scope}
    
    \begin{scope}[shift={(10,-3)}]
    \node[pt](6ea) at (0,0) {};
    \node[pt,label={west:{$s$}}](6ec) at (0,1){};
    \node[pt,label={east:{$c$}}](6ed) at (1,1){};
    \end{scope}
    
    \begin{scope}[shift={(0,-6)}]
    \node[pt](7ha) at (0,0) {};
    \node[pt](7hb) at (1,0){} ;
    \node[pt,label={west:{$s$}}](7hc) at (0,1){};
    \node[pt,label={east:{$c$}}](7hd) at (1,1){};
    \end{scope}
    
    \begin{scope}[shift={(2.5,-6)}]
    \node[pt](7a) at (0,0) {};
    \node[pt](7b) at (1,0){} ;
    \node[pt](7c) at (0,1){};
    \node[coin](7d) at (1,1){};
    \end{scope}
    
    \begin{scope}[shift={(5,-6)}]
    \node[coin](8a) at (0,0) {};
    \node[pt](8b) at (1,0){} ;
    \node[pt](8c) at (0,1){};
    \node[pt](8d) at (1,1){};
    \end{scope}
    
    \begin{scope}[shift={(7.5,-6)}]
    \node[pt](9a) at (0,0) {};
    \node[pt](9b) at (1,0){} ;
    \node[coin](9c) at (0,1){};
    \node[pt](9d) at (1,1){};
    \end{scope}
    
    \begin{scope}[shift={(10,-6)}]
    \node[pt](9ea) at (0,0) {};
    \node[pt](9eb) at (1,0){} ;
    \node[pt,label={west:{$s$}}](9ec) at (0,1){};
    \node[pt,label={east:{$c$}}](9ed) at (1,1){};
    \end{scope}
    
    
    %\begin{scope}[shift={(0,-3)}]
    %\node[label={west:{\large$s$}}] (4a) at (0,0) {};
    %\node(4b) at (1,0){} ;
    %\node(4c) at (2,0){};
    %\node(4d) at (3,0){};
    
    %\node(4a2) at (0,1) {};
    %\node(4b2) at (1,1){} ;
    %\node(4c2) at (2,1){};
    %\node(4d2) at (3,1){};
    
    %\node(4a3) at (0,2) {};
    %\node(4b3) at (1,2){} ;
    %\node(4c3) at (2,2){};
    %\node(4d3) at (3,2){};
    %\end{scope}
    
    %\begin{scope}[shift={(5,-3)}]
    %\node[label={west:{\large$s$}}] (5a) at (0,0) {};
    %\node(5b) at (1,0){} ;
    %\node(5c) at (2,0){};
    %\node(5d) at (3,0){};
    
    %\node(5a2) at (0,1) {};
    %\node(5b2) at (1,1){} ;
    %\node(5c2) at (2,1){};
    %\node(5d2) at (3,1){};
    
    %\node(5a3) at (0,2) {};
    %\node(5b3) at (1,2){} ;
    %\node(5c3) at (2,2){};
    %\node(5d3) at (3,2){};
    %\end{scope}
    
    %\begin{scope}[shift={(10,-3)}]
    %\node[label={west:{\large$s$}}] (6a) at (0,0) {};
    %\node(6b) at (1,0){} ;
    %\node(6c) at (2,0){};
    %\node(6d) at (3,0){};
    
    %\node(6a2) at (0,1) {};
    %\node(6b2) at (1,1){} ;
    %\node(6c2) at (2,1){};
    %\node(6d2) at (3,1){};
    
    %\node(6a3) at (0,2) {};
    %\node(6b3) at (1,2){} ;
    %\node(6c3) at (2,2){};
    %\node(6d3) at (3,2){};
    %\end{scope}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
    \tikzstyle{every node} = [draw = none,fill = none,scale = .8]
    
    \node(o) at (0.5,1.5){\Large$T$}; \node(o) at (10.5,1.5) {\Large$T'$};
    
    \node(o) at (0.5,-1.5){\Large$T/{e_1}$};
    \node(o) at (10.5,-1.5) {\Large$T'/{e_1}$};
    
    \node(o) at (0.5,-4.5){\Large$T$};
    \node(o) at (10.5,-4.5){\Large$T'$};
    
    \node(o) at (-1.5,0.5){\Large(a):};
    \node(o) at (-1.5,-2.5){\Large(b):};
    \node(o) at (-1.5,-5.5){\Large(c):};
    
    \draw[dotted] (hc) -- (ha) -- node [below]{$e_2$}(hb);
    
    \draw[dotted] (c) -- (a) -- (b);
    
    \draw[dotted] (2d) -- (2c) -- (2a) -- (2b);
    
    \draw[dotted] (3d) -- (3c);
    \draw[dotted] (3a) -- (3b);
    
    \draw[dotted] (3ed) -- (3ec);
    \draw[dotted] (3ea) -- (3eb);
    
    \draw[dotted] (4hc) -- (4ha);
    \draw[dotted] (4ha) to [bend right = 45] (4hd);
    
    \draw[dotted] (4c) -- (4a);
    \draw[dotted] (4a) to [bend right = 45] (4d);
    
    \draw[dotted] (5d) -- (5c) -- (5a);
    \draw[dotted] (5a) to [bend right = 45] (5d);
    
    \draw[dotted] (6d) -- (6c);
    \draw[dotted] (6a) to [bend right = 45] (6d);
    
    \draw[dotted] (6ed) -- (6ec);
    \draw[dotted] (6ea) to [bend right = 45] (6ed);
    
    \draw[dotted] (7hc) -- (7ha);
    
    \draw[dotted] (7c) -- (7a);
    
    \draw[dotted] (8d) -- (8c) -- (8a);
    
    \draw[dotted] (9d) -- (9c);
    
    \draw[dotted] (9ed) -- (9ec);
    
    %\draw[dotted](4a) --(4d)--(4d3) -- (4a3) -- (4a);
    %\draw[dotted](4b) --(4b3);
    %\draw[dotted](4c) --(4c3);
    %\draw[dotted](4a2) --(4d2);
    
    %\draw[dotted](5a) --(5d)--(5d3) -- (5a3) -- (5a);
    %\draw[dotted](5b) --(5b3);
    %\draw[dotted](5c) --(5c3);
    %\draw[dotted](5a2) --(5d2);
    
    %\draw[dotted](6a) --(6d)--(6d3) -- (6a3) -- (6a);
    %\draw[dotted](6b) --(6b3);
    %\draw[dotted](6c) --(6c3);
    %\draw[dotted](6a2) --(6d2);
    
    \draw (ha) -- (hd);
    \draw (hb) -- node[right]{$e_1$}(hd);
    \draw (hd) -- (hc) ;
    
    \draw [-{Latex[length=2mm,width=1.5mm]}](a) --(d);
    \draw [-{Latex[length=2mm,width=1.5mm]}](b) -- (d);
    \draw [-{Latex[length=2mm,width=1.5mm]}](d) -- (c) ;
    
    \draw [-{Latex[length=2mm,width=1.5mm]}](2a) --(2d);
    \draw [-{Latex[length=2mm,width=1.5mm]}](2b) --(2d);
    \draw [-{Latex[length=2mm,width=1.5mm]}](2d) --(2a);
    
    \draw [-{Latex[length=2mm,width=1.5mm]}](3a) --(3c);
    \draw [-{Latex[length=2mm,width=1.5mm]}](3b) --(3d);
    \draw [-{Latex[length=2mm,width=1.5mm]}](3d) --(3a);
    
    \draw (3ea) --(3ec);
    \draw (3eb) --(3ed);
    \draw (3ed) --(3ea);
    
    \draw (4ha) --(4hd);
    \draw (4hd) --(4hc);
    
    \draw [-{Latex[length=2mm,width=1.5mm]}](4a) --(4d);
    \draw [-{Latex[length=2mm,width=1.5mm]}](4d) --(4c);
    
    \draw [-{Latex[length=2mm,width=1.5mm]}](5a) --(5d);
    \draw [-{Latex[length=2mm,width=1.5mm]}](5d) --(5a);
    
    \draw [-{Latex[length=2mm,width=1.5mm]}](6a) --(6c);
    \draw [-{Latex[length=2mm,width=1.5mm]}](6d) --(6a);
    
    \draw (6ea) --(6ec);
    \draw (6ed) --(6ea);
    
    \draw (7ha) --(7hd);
    \draw (7hb) --(7hd);
    \draw (7hd) --(7hc);
    
    \draw [-{Latex[length=2mm,width=1.5mm]}](7a) --(7d);
    \draw [-{Latex[length=2mm,width=1.5mm]}](7b) --(7d);
    \draw [-{Latex[length=2mm,width=1.5mm]}](7d) --(7c);
    
    \draw [-{Latex[length=2mm,width=1.5mm]}](8a) --(8d);
    \draw [-{Latex[length=2mm,width=1.5mm]}](8b) --(8d);
    \draw [-{Latex[length=2mm,width=1.5mm]}](8d) --(8a);
    
    \draw [-{Latex[length=2mm,width=1.5mm]}](9a) --(9c);
    \draw [-{Latex[length=2mm,width=1.5mm]}](9b) --(9d);
    \draw [-{Latex[length=2mm,width=1.5mm]}](9d) --(9a);
    
    \draw (9ea) --(9ec);
    \draw (9eb) --(9ed);
    \draw (9ed) --(9ea);
    
\end{tikzpicture}
\caption{An example of the rotor-routing algorithm demonstrating that rotor-routing is consistent on a graph $(G,\chi)$, where $\chi$ denotes counterclockwise rotation. We denote the chip $x$ by a hollow vertex. Figure 1(a) illustrates, using the rotor-routing algorithm, that $T' = r_{(G,\chi)}([c-s],T)$. Figure 1(b) illustrates how the rotor-routing algorithm commutes with contraction: $T'/e_1 = r_{(G/e_1,\chi)}([c-s],T/e_1)$. Figure 1(c) illustrates how the rotor-routing algorithm commutes with deletion: $T' = r_{(G\setminus e_2,\chi)}([c-s],T)$.}
\label{fig:consistent}
\end{center}
\end{figure}

\begin{figure}[t]
\begin{center}
\begin{tikzpicture}[scale = 0.9]
    
    \tikzstyle{every node} = [circle,fill,inner sep=1pt,minimum size = 1.5mm]
    \node[label={west:{\large$s$}}] (a) at (0,0) {};
    \node(b) at (1,0){} ;
    \node(c) at (2,0){};
    \node(d) at (3,0){};
    
    \node(a2) at (0,1) {};
    \node[label={south east:{$x$}}](b2) at (1,1){} ;
    \node(c2) at (2,1){};
    \node(d2) at (3,1){};
    
    \node(a3) at (0,2) {};
    \node(b3) at (1,2){} ;
    \node(c3) at (2,2){};
    \node(d3) at (3,2){};

    
    \begin{scope}[shift={(5,0)}]
    \node[label={west:{\large$s$}}] (2a) at (0,0) {};
    \node(2b) at (1,0){} ;
    \node(2c) at (2,0){};
    \node(2d) at (3,0){};
    
    \node(2a2) at (0,1) {};
    \node[label={south east:{$x$}}](2b2) at (1,1){} ;
    \node(2c2) at (2,1){};
    \node(2d2) at (3,1){};
    
    \node(2a3) at (0,2) {};
    \node(2b3) at (1,2){} ;
    \node(2c3) at (2,2){};
    \node(2d3) at (3,2){};
    \end{scope}
    
    \begin{scope}[shift={(10,0)}]
    \node[label={west:{\large$s$}}] (3a) at (0,0) {};
    \node(3b) at (1,0){} ;
    \node(3c) at (2,0){};
    \node(3d) at (3,0){};
    
    \node(3a2) at (0,1) {};
    \node[label={south east:{$x$}}](3b2) at (1,1){} ;
    \node(3c2) at (2,1){};
    \node(3d2) at (3,1){};
    
    \node(3a3) at (0,2) {};
    \node(3b3) at (1,2){} ;
    \node(3c3) at (2,2){};
    \node(3d3) at (3,2){};
    \end{scope}
    
    %\begin{scope}[shift={(0,-3)}]
    %\node[label={west:{\large$s$}}] (4a) at (0,0) {};
    %\node(4b) at (1,0){} ;
    %\node(4c) at (2,0){};
    %\node(4d) at (3,0){};
    
    %\node(4a2) at (0,1) {};
    %\node(4b2) at (1,1){} ;
    %\node(4c2) at (2,1){};
    %\node(4d2) at (3,1){};
    
    %\node(4a3) at (0,2) {};
    %\node(4b3) at (1,2){} ;
    %\node(4c3) at (2,2){};
    %\node(4d3) at (3,2){};
    %\end{scope}
    
    %\begin{scope}[shift={(5,-3)}]
    %\node[label={west:{\large$s$}}] (5a) at (0,0) {};
    %\node(5b) at (1,0){} ;
    %\node(5c) at (2,0){};
    %\node(5d) at (3,0){};
    
    %\node(5a2) at (0,1) {};
    %\node(5b2) at (1,1){} ;
    %\node(5c2) at (2,1){};
    %\node(5d2) at (3,1){};
    
    %\node(5a3) at (0,2) {};
    %\node(5b3) at (1,2){} ;
    %\node(5c3) at (2,2){};
    %\node(5d3) at (3,2){};
    %\end{scope}
    
    %\begin{scope}[shift={(10,-3)}]
    %\node[label={west:{\large$s$}}] (6a) at (0,0) {};
    %\node(6b) at (1,0){} ;
    %\node(6c) at (2,0){};
    %\node(6d) at (3,0){};
    
    %\node(6a2) at (0,1) {};
    %\node(6b2) at (1,1){} ;
    %\node(6c2) at (2,1){};
    %\node(6d2) at (3,1){};
    
    %\node(6a3) at (0,2) {};
    %\node(6b3) at (1,2){} ;
    %\node(6c3) at (2,2){};
    %\node(6d3) at (3,2){};
    %\end{scope}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
    \tikzstyle{every node} = [draw = none,fill = none,scale = .8]
    
    \node(o) at (1.5,2.5){\Large$T_s$};
    \node(o) at (6.5,2.5){\Large$T_s'$};
    \node(o) at (11.5,2.5){\Large$\widehat T_s$};
    
    
    \draw[dotted](a) --(d)--(d3) -- (a3) -- (a);
    \draw[dotted](b) --(b3);
    \draw[dotted](c) --(c3);
    \draw[dotted](a2) --(d2);
    
    \draw[dotted](2a) --(2d)--(2d3) -- (2a3) -- (2a);
    \draw[dotted](2b) --(2b3);
    \draw[dotted](2c) --(2c3);
    \draw[dotted](2a2) --(2d2);
    
    \draw[dotted](3a) --(3d)--(3d3) -- (3a3) -- (3a);
    \draw[dotted](3b) --(3b3);
    \draw[dotted](3c) --(3c3);
    \draw[dotted](3a2) --(3d2);
    
    
    %\draw[dotted](4a) --(4d)--(4d3) -- (4a3) -- (4a);
    %\draw[dotted](4b) --(4b3);
    %\draw[dotted](4c) --(4c3);
    %\draw[dotted](4a2) --(4d2);
    
    %\draw[dotted](5a) --(5d)--(5d3) -- (5a3) -- (5a);
    %\draw[dotted](5b) --(5b3);
    %\draw[dotted](5c) --(5c3);
    %\draw[dotted](5a2) --(5d2);
    
    %\draw[dotted](6a) --(6d)--(6d3) -- (6a3) -- (6a);
    %\draw[dotted](6b) --(6b3);
    %\draw[dotted](6c) --(6c3);
    %\draw[dotted](6a2) --(6d2); 
    
    \draw [-{Latex[length=2mm,width=1.5mm]}](a2) --(a);
    \draw [-{Latex[length=2mm,width=1.5mm]}](b2) --(a2);
    \draw [-{Latex[length=2mm,width=1.5mm]}](b3) --(b2);
    \draw [-{Latex[length=2mm,width=1.5mm]}](a3) --(b3);
    \draw [-{Latex[length=2mm,width=1.5mm]}](c3) --(b3);
    \draw [-{Latex[length=2mm,width=1.5mm]}](b) --(a);
    \draw [-{Latex[length=2mm,width=1.5mm]}](c) --(b);
    \draw [-{Latex[length=2mm,width=1.5mm]}](d) --(c);
    \draw [-{Latex[length=2mm,width=1.5mm]}](c2) --(c);
    \draw [-{Latex[length=2mm,width=1.5mm]}](d2) --(c2);
    \draw [-{Latex[length=2mm,width=1.5mm]}](d3) --(d2);
    
    \draw [-{Latex[length=2mm,width=1.5mm]}](2a2) --(2a);
    \draw [-{Latex[length=2mm,width=1.5mm]}](2b2) --(2b);
    \draw [-{Latex[length=2mm,width=1.5mm]}](2b3) --(2a3);
    \draw [-{Latex[length=2mm,width=1.5mm]}](2a3) --(2a2);
    \draw [-{Latex[length=2mm,width=1.5mm]}](2c3) --(2d3);
    \draw [-{Latex[length=2mm,width=1.5mm]}](2b) --(2a);
    \draw [-{Latex[length=2mm,width=1.5mm]}](2c) --(2b);
    \draw [-{Latex[length=2mm,width=1.5mm]}](2d) --(2c);
    \draw [-{Latex[length=2mm,width=1.5mm]}](2c2) --(2c);
    \draw [-{Latex[length=2mm,width=1.5mm]}](2d2) --(2c2);
    \draw [-{Latex[length=2mm,width=1.5mm]}](2d3) --(2d2);
    
    \draw [-{Latex[length=2mm,width=1.5mm]}](3a2) --(3a);
    \draw [-{Latex[length=2mm,width=1.5mm]}](3b2) --(3b);
    \draw [-{Latex[length=2mm,width=1.5mm]}](3b3) --(3b2);
    \draw [-{Latex[length=2mm,width=1.5mm]}](3a3) --(3b3);
    \draw [-{Latex[length=2mm,width=1.5mm]}](3c3) --(3b3);
    \draw [-{Latex[length=2mm,width=1.5mm]}](3b) --(3a);
    \draw [-{Latex[length=2mm,width=1.5mm]}](3c) --(3b);
    \draw [-{Latex[length=2mm,width=1.5mm]}](3d) --(3c);
    \draw [-{Latex[length=2mm,width=1.5mm]}](3c2) --(3c);
    \draw [-{Latex[length=2mm,width=1.5mm]}](3d2) --(3d);
    \draw [-{Latex[length=2mm,width=1.5mm]}](3d3) --(3d2);
    
\end{tikzpicture}
\caption{All of the indegree 0 rotors in $T_s$ are in the same final position as they are in $\widehat T_s$, so their are no immediate moves to get ``closer'' to $\widehat T_s$. However, it is possible to reach $T'_s$ which has rotor $x$ in the correct position after only moving rotors that are further from $s$ than $x$ (with respect to $\widehat T$). This general method is used for Proposition~\ref{prop:sourceturn}.   }
\label{fig:sourceturn}
\end{center}
\end{figure}
\end{document}
