\documentclass[12pt,final,notitlepage,onecolumn,german]{article}%
\usepackage[all,cmtip]{xy}
\usepackage{lscape}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amsmath}%
\setcounter{MaxMatrixCols}{30}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{CSTFile=LaTeX article (bright).cst}
%TCIDATA{Created=Sat Mar 27 17:33:36 2004}
%TCIDATA{LastRevised=Thursday, November 10, 2011 23:59:06}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\newcommand{\id}{\operatorname*{id}}
\voffset=-2.5cm
\hoffset=-2.5cm
\setlength\textheight{24cm}
\setlength\textwidth{15.5cm}
\begin{document}

\begin{center}
\textbf{Chip-Firing and Rotor-Routing on Directed Graphs}

\textit{Alexander E. Holroyd, Lionel Levine, Karola M\'{e}sz\'{a}ros, Yuval
Peres, James Propp and David B. Wilson}

arXiv:0801.3306v3

\textbf{Errata, questions and addenda (Darij Grinberg)}

\bigskip
\end{center}

\begin{itemize}
\item \textbf{Page 3, definition of the Laplacian:} You write:%
\[
\Delta_{ij}=\left\{
\begin{array}
[c]{c}%
-a_{ij}\ \ \ \ \ \ \ \ \ \ \text{for }i\neq j,\\
d_{i}-a_{ii}\ \ \ \ \ \ \ \ \ \ \text{for }i=j
\end{array}
\right.  .
\]
It should be pointed out that $d_{i}$ is a shorthand notation for $d_{v_{i}}$.

\item \textbf{Page 3, definition of "fire":} You write: "An active vertex $v$
can \textbf{fire}, resulting in a new chip configuration $\sigma^{\prime}$
obtained by moving one chip along each of the $d_{v}$ edges emanating from
$v$". At this point it would help to explicitly state that chips moving to the
sink simply disappear (i. e., are forgotten). Otherwise readers might think
that we keep track of how many chips went into the sink (this is a
misunderstanding I had first) or that edges to the sink are not counted in the
degree of a vertex (this is also a misunderstanding).

\item \textbf{Page 3, Lemma 2.2:} In part 2 of the lemma, $\sigma_{m}$ should
be $\sigma_{m}^{\prime}$.

\item \textbf{Page 3, Lemma 2.2:} One very pedantic remark: The $n$ in Lemma
2.2 has nothing to do with the $n$ on the upper half of page 3. The $n$ in
Lemma 2.2 is the index of the last element of the sequence $\sigma_{0},$
$\sigma_{1},$ $...,$ $\sigma_{n}$, whereas the $n$ on the upper half of page 3
is the number of vertices of $G$. Some danger of confusion arises in the proof
of Lemma 2.2 (and probably in a few other places in the paper), where you are
speaking of a vertex $v_{n}$ which has nothing to do with the $v_{n}$ from the
upper half of page 3. Maybe you should mention the ambiguity of $n$ in some
footnote. (The same ambiguous use of $n$ appears in Lemma 3.9 and its proof.)

\item \textbf{Page 4, proof of Lemma 2.2:} You write: "Then $v_{i},v_{1}%
,v_{2},...,v_{i-1},v_{i+1},...,v_{n}$ is a permissible firing sequence". I
think it is permissible only if $i$ is defined as the \textit{first} index $k$
satisfying $v_{k}=v_{1}^{\prime}$ (and not just as some arbitrary index $k$
satisfying $v_{k}=v_{1}^{\prime}$). Of course, this is easy to fix (just
define $i$ this way).

\item \textbf{Page 5, proof of Lemma 2.4:} You write: "and $d_{v_{r-1}}$ such
chips will cause $v_{r-1}$ to fire once". Maybe this would be clearer if you
replace the word "cause" by "allow" (at least it would be clearer this way to
me), because until we know that each chip configuration stabilizes, we cannot
speak of "causing" here (in fact, one could imagine that we fire some subset
of vertices again and again, and never come to fire $v_{r-1}$ even though
$d_{v_{r-1}}$ chips have accumulated at $v_{r-1}$).

\item \textbf{Page 5:} What is the Theorem 4.8 you refer to when you write
"see Theorem 4.8 for a better bound"?

\item \textbf{Page 6, proof of Lemma 2.8:} I think this proof only shows that
the order of $\mathcal{S}\left(  G\right)  $ is the \textit{absolute value} of
the determinant of $\Delta^{\prime}\left(  G\right)  $. In fact, in order to
have the volume of any parallelepiped equal to the determinant of the matrix
from its edge-vectors, we need our volumes to be \textit{signed} - but the
index of a lattice is the \textit{unsigned} volume of its fundamental
domain.\newline What is needed to fix the proof is an argument why $\det
\Delta^{\prime}\left(  G\right)  \geq0$. I don't see how to prove this
combinatorially. We can prove this by a mix of algebra and continuity
arguments: The matrix $\Delta^{\prime}\left(  G\right)  $ is (weakly)
diagonally dominant, and the determinant of a (weakly) diagonally dominant
matrix is always $\geq0$ (this is a limiting case of the inequality proved
in\newline http://www.artofproblemsolving.com/Forum/viewtopic.php?t=176225 ).

\item \textbf{Page 6, Definition 2.11:} At this point, I believe it would be
useful to make one rather trivial observation which you are tacitly using
several times in the subsequent proofs (or at least I believe you use
it).\newline There are two ways to interpret your definition of
"accessible":\newline\textit{First interpretation:} A chip configuration
$\sigma$ is \textbf{accessible} if from any other chip configuration it is
possible to obtain $\sigma$ by \textit{first} adding some chips and
\textit{then} selectively firing active vertices.\newline\textit{Second
interpretation:} A chip configuration $\sigma$ is \textbf{accessible} if from
any other chip configuration it is possible to obtain $\sigma$ by a sequence
of operations, each of which is either an addition of a chip or a firing of an
active vertex.\newline The observation is now that these two interpretations
are equivalent.\newline\textit{Proof.} If we \textit{first} fire an active
vertex in a chip configuration $\tau$, and \textit{then} add some chip, then
we could have just as well \textit{first} added the chip to the configuration
$\tau$ and \textit{then} fired the vertex (because adding the chip can never
make any active vertex non-active). Therefore, if we have a sequence of
operations, each of which is either an addition of a chip or a firing of an
active vertex, then we can move all the "addition-of-a-chip" operations to the
front and all of the "firing-of-an-active-vertex" operations to the end of
this sequence. Hence, the second interpretation is equivalent to the first interpretation.

\item \textbf{Page 7:} What is the Lemma 4.6 you refer to when you write
"cluster-firing and superstabilization as described in Definition 4.3 and
Lemma 4.6"?

\item \textbf{Page 7, proof of Lemma 2.13:} You write "$\beta\geq\left[
d_{\max}+\left(  -m\right)  \right]  \left(  \delta-\delta^{\circ}\right)
\geq d_{\max}\left(  \delta-\delta^{\circ}\right)  \geq d_{\max}$". I think
this is wrong, because $\beta=\alpha+\left[  d_{\max}+\left(  -m\right)
\right]  \left(  \delta-\delta^{\circ}\right)  $ does not yield $\beta
\geq\left[  d_{\max}+\left(  -m\right)  \right]  \left(  \delta-\delta^{\circ
}\right)  $. What you mean is that%
\begin{align*}
\beta &  =\alpha+\left[  d_{\max}+\left(  -m\right)  \right]  \left(
\delta-\delta^{\circ}\right)  =\alpha+\left(  -m\right)  \underbrace{\left(
\delta-\delta^{\circ}\right)  }_{\geq1}+d_{\max}\left(  \delta-\delta^{\circ
}\right) \\
&  \geq\underbrace{\alpha+\left(  -m\right)  }_{\geq0}+d_{\max}\left(
\delta-\delta^{\circ}\right)  \geq d_{\max}\underbrace{\left(  \delta
-\delta^{\circ}\right)  }_{\geq1}\geq d_{\max}.
\end{align*}


\item \textbf{Page 7, Lemma 2.14:} This lemma is nice, but I think that the
actual fact you repeatedly use (for example, when you write "by Lemma 2.14" in
the proof of Lemma 2.15) is the following strengthening:\newline\textbf{Lemma
2.14a:} Let $\epsilon=\left(  2\delta\right)  -\left(  2\delta\right)
^{\circ}$, where $\delta$ is given by $\delta\left(  v\right)  =d_{v}$ as
before. If $\sigma$ is recurrent, and $k\geq0$ is an integer, then $\left(
\sigma+k\epsilon\right)  ^{\circ}=\sigma$.\newline\textit{Proof.} Induct over
$k$. The induction base ($k=0$) is clear (since $\sigma$ is recurrent and thus
stable).\newline For the induction step, assume that $\left(  \sigma
+k\epsilon\right)  ^{\circ}=\sigma$, and try to prove that $\left(
\sigma+\left(  k+1\right)  \epsilon\right)  ^{\circ}=\sigma$.\newline Indeed
there is a fact which I call the "partial stabilization lemma", and which
states that any two chip configurations $\alpha$ and $\beta$ satisfy $\left(
\alpha+\beta\right)  ^{\circ}=\left(  \alpha+\beta^{\circ}\right)  ^{\circ}$.
Applied to $\alpha=\epsilon$ and $\beta=\sigma+k\epsilon$, this fact yields
$\left(  \epsilon+\sigma+k\epsilon\right)  ^{\circ}=\left(  \epsilon+\left(
\sigma+k\epsilon\right)  ^{\circ}\right)  ^{\circ}$. Since $\left(
\sigma+k\epsilon\right)  ^{\circ}=\sigma$ and $\epsilon+\sigma+k\epsilon
=\sigma+\left(  k+1\right)  \epsilon$, this rewrites as $\left(
\sigma+\left(  k+1\right)  \epsilon\right)  ^{\circ}=\left(  \epsilon
+\sigma\right)  ^{\circ}$. Thus, $\left(  \sigma+\left(  k+1\right)
\epsilon\right)  ^{\circ}=\left(  \epsilon+\sigma\right)  ^{\circ}=\left(
\sigma+\epsilon\right)  ^{\circ}=\sigma$ (by Lemma 2.14), completing the
induction step. Lemma 2.14a is thus proven.

%\newline\newline\textit{Alternative proof of Lemma 2.14a.} Induct
%over $k$. The induction base ($k=0$) is clear (since $\sigma$ is recurrent and
%thus stable).\newline For the induction step, assume that $\left(
%\sigma+k\epsilon\right)  ^{\circ}=\sigma$, and try to prove that $\left(
%\sigma+\left(  k+1\right)  \epsilon\right)  ^{\circ}=\sigma$.\newline Indeed
%there is a fact (which is, strangely enough, not in your text) stating that
%any three chip configurations $\alpha$, $\beta$ and $\gamma$ satisfy $\left(
%\alpha+\left(  \beta+\gamma\right)  ^{\circ}\right)  ^{\circ}=\left(
%\alpha+\beta+\gamma\right)  ^{\circ}=\left(  \left(  \alpha+\beta\right)
%^{\circ}+\gamma\right)  ^{\circ}$. Applied to $\alpha=\epsilon$, $\beta
%=\sigma$ and $\gamma=k\epsilon$, this yields $\left(  \epsilon+\left(
%\sigma+k\epsilon\right)  ^{\circ}\right)  ^{\circ}=\left(  \epsilon
%+\sigma+k\epsilon\right)  ^{\circ}=\left(  \left(  \epsilon+\sigma\right)
%^{\circ}+k\epsilon\right)  ^{\circ}$. Since $\left(  \sigma+k\epsilon\right)
%^{\circ}=\sigma$ and $\epsilon+\sigma+k\epsilon=\sigma+\left(  k+1\right)
%\epsilon$, this rewrites as $\left(  \epsilon+\sigma\right)  ^{\circ}=\left(
%\sigma+\left(  k+1\right)  \epsilon\right)  ^{\circ}=\left(  \left(
%\epsilon+\sigma\right)  ^{\circ}+k\epsilon\right)  ^{\circ}$. Thus, $\left(
%\sigma+\left(  k+1\right)  \epsilon\right)  ^{\circ}=\left(  \epsilon
%+\sigma\right)  ^{\circ}=\left(  \sigma+\epsilon\right)  ^{\circ}=\sigma$ (by
%Lemma 2.14), completing the induction.


\item \textbf{Page 7, Lemma 2.14:} I am just wondering: Why do you formulate
this lemma for $\epsilon=\left(  2\delta\right)  -\left(  2\delta\right)
^{\circ}$ rather than for $\epsilon=\delta-\delta^{\circ}$ ? Unless I am
mistaken, the proof of Lemma 2.14 works just as well if the definition of
$\epsilon$ is replaced by $\epsilon=\delta-\delta^{\circ}$. The only
difference I can see between $\left(  2\delta\right)  -\left(  2\delta\right)
^{\circ}$ and $\delta-\delta^{\circ}$ is that $\left(  2\delta\right)
-\left(  2\delta\right)  ^{\circ}$ is accessible (while $\delta-\delta^{\circ
}$ is not necessarily - at least I don't see a proof that it is). But you
don't seem to ever use the accessibility of $\left(  2\delta\right)  -\left(
2\delta\right)  ^{\circ}$ ...

\item \textbf{Page 11, proof of Lemma 2.17:} You write: "If (4) holds, there
is a chip configuration $\alpha$ such that $\left(  \sigma+\alpha\right)
^{\circ}=\sigma$ and $\alpha$ is nonzero on at least one vertex of each
strongly connected component of $G$". Here you seem to be using the the
following (not completely trivial) fact:\newline\textbf{Lemma 2.14b:} If some
stable chip configuration $\sigma$ and some chip configurations $\alpha_{1}$,
$\alpha_{2}$, $...$, $\alpha_{k}$ satisfy $\left(  \sigma+\alpha_{1}\right)
^{\circ}=\left(  \sigma+\alpha_{2}\right)  ^{\circ}=...=\left(  \sigma
+\alpha_{k}\right)  ^{\circ}=\sigma$, then $\left(  \sigma+\alpha_{1}%
+\alpha_{2}+...+\alpha_{k}\right)  ^{\circ}=\sigma$.\newline\textit{Proof.} We
will prove that every $i\in\left\{  0,1,...,k\right\}  $ satisfies $\left(
\sigma+\alpha_{1}+\alpha_{2}+...+\alpha_{i}\right)  ^{\circ}=\sigma$.\newline
Indeed, let us prove this by induction over $i$: The induction base ($i=0$) is
clear (since $\sigma$ is stable).\newline For the induction step, let
$i\in\left\{  1,2,...,k\right\}  $. Assume that $\left(  \sigma+\alpha
_{1}+\alpha_{2}+...+\alpha_{i-1}\right)  ^{\circ}=\sigma$, and try to prove
that $\left(  \sigma+\alpha_{1}+\alpha_{2}+...+\alpha_{i}\right)  ^{\circ
}=\sigma$.\newline Applying the "partial stabilization lemma" (which I quoted
above in the proof of Lemma 2.14a) to $\alpha=\alpha_{i}$ and $\beta
=\sigma+\alpha_{1}+\alpha_{2}+...+\alpha_{i-1}$, we obtain $\left(  \alpha
_{i}+\sigma+\alpha_{1}+\alpha_{2}+...+\alpha_{i-1}\right)  ^{\circ}=\left(
\alpha_{i}+\left(  \sigma+\alpha_{1}+\alpha_{2}+...+\alpha_{i-1}\right)
^{\circ}\right)  ^{\circ}$. Since $\alpha_{i}+\sigma+\alpha_{1}+\alpha
_{2}+...+\alpha_{i-1}=\sigma+\alpha_{1}+\alpha_{2}+...+\alpha_{i}$ and
$\left(  \sigma+\alpha_{1}+\alpha_{2}+...+\alpha_{i-1}\right)  ^{\circ}%
=\sigma$, this rewrites as $\left(  \sigma+\alpha_{1}+\alpha_{2}%
+...+\alpha_{i}\right)  ^{\circ}=\left(  \alpha_{i}+\sigma\right)  ^{\circ}$.
Thus, $\left(  \sigma+\alpha_{1}+\alpha_{2}+...+\alpha_{i}\right)  ^{\circ
}=\left(  \alpha_{i}+\sigma\right)  ^{\circ}=\left(  \sigma+\alpha_{i}\right)
^{\circ}=\sigma$. This completes the induction step.\newline We have thus
proven by induction that every $i\in\left\{  0,1,...,k\right\}  $ satisfies
$\left(  \sigma+\alpha_{1}+\alpha_{2}+...+\alpha_{i}\right)  ^{\circ}=\sigma$.
Applied to $i=k$, this yields $\left(  \sigma+\alpha_{1}+\alpha_{2}%
+...+\alpha_{k}\right)  ^{\circ}=\sigma$. We have thus proven Lemma 2.14b.

\item \textbf{Page 11, proof of Lemma 2.17:} You write: "Moreover, $\left(
\sigma+\beta\right)  ^{\circ}=\sigma$." It took me a while to figure out why
this is so. Here is my proof:\newline Since $\beta$ is obtained from $k\alpha$
by selective firing, we see that $\sigma+\beta$ is obtained from
$\sigma+k\alpha$ by selective firing. Thus, $\left(  \sigma+\beta\right)
^{\circ}=\left(  \sigma+k\alpha\right)  ^{\circ}$. Since Lemma 2.14b (applied
to $\alpha_{1}=\alpha$, $\alpha_{2}=\alpha$, $...$, $\alpha_{k}=\alpha$)
yields $\left(  \sigma+k\alpha\right)  ^{\circ}=\sigma$, we obtain $\left(
\sigma+\beta\right)  ^{\circ}=\left(  \sigma+k\alpha\right)  ^{\circ}=\sigma
$.\newline So much for my proof of $\left(  \sigma+\beta\right)  ^{\circ
}=\sigma$. Is this argument more complicated than what you had in mind?
Because I find it strange that you leave this to the reader (after all, you
haven't even explicitly stated Lemma 2.14b).

\item \textbf{Page 11:} The formula%
\[
\sum_{w}\Delta_{v,w}^{\prime}f\left(  w\right)  =\sigma\left(  v\right)
\]
should be%
\[
\sum_{w}\Delta_{v,w}^{\prime}f\left(  w\right)  =\sigma\left(  v\right)
\operatorname{mod}1.
\]


\item \textbf{Page 13, proof of Lemma 3.4:} You write: "this same directed
occurs within $\rho$". This should be "this same directed cycle occurs within
$\rho$" (you forgot the word "cycle").

\item \textbf{Page 14, proof of Lemma 3.7:} You write: "and hence the edge
from $v_{i}$ to $v_{i+1}$ was traversed more recently than the edge from
$v_{i-1}$ to $v_{i}$". Since both of these edges might have been traversed
several times, I would find it clearer if you replaced this by "and hence the
last time the chip was at $v_{i+1}$ is later than the last time it was at
$v_{i}$" (or something similar - I don't think my sentence is good English,
but I assume you get what I mean).

\item \textbf{Page 14, proof of Lemma 3.9:} You write: "then some permutation
of $v$ agrees with $v^{\prime}$ in the first $i$ terms". I believe that, for
the induction to work as intended, this should be amended to "then some
\textit{legal} permutation of $v$ agrees with $v^{\prime}$ in the first $i$
terms", where a sequence of vertices of $G$ is said to be \textit{legal} if it
is possible to fire the vertices in the order of this sequence. Otherwise, it
is not clear why "the vertices $v_{1},v_{2},...,v_{i-1},v_{j},v_{i}%
,v_{i+1},...,v_{j-1},v_{j+1},...,v_{n}$ can be fired in that order" (since we
don't know whether the sequence $v$ itself was legal to begin with!).\newline
Alternatively, you could also leave the "then some permutation of $v$ agrees
with $v^{\prime}$ in the first $i$ terms" part as it is, but then "the
vertices $v_{1},v_{2},...,v_{i-1},v_{j},v_{i},v_{i+1},...,v_{j-1}%
,v_{j+1},...,v_{n}$ can be fired in that order" is not literally true, unless
you allow vertices to host a negative number of chips.

\item \textbf{Page 16, proof of Lemma 3.10:} You write: "where the induction
hypothesis states that every path leads to either the sink or to the chip". I
think it would be more precise to say that "where the induction hypothesis
states that every sufficiently long path leads either to the sink or through
the chip".

\item \textbf{Page 17, Definition 3.11:} The formula%
\[
\sigma\left(  \rho\right)  =\left(  \prod_{v\in V\left(  G\right)  }%
E_{v}^{\sigma\left(  v\right)  }\right)  \rho
\]
should be%
\[
\sigma\left(  \rho\right)  =\left(  \prod_{v\in V\left(  G\right)
\diagdown\left\{  \operatorname{sink}\right\}  }E_{v}^{\sigma\left(  v\right)
}\right)  \rho.
\]


\item \textbf{Page 19, proof of Lemma 3.16:} You write: "Since $\rho$ is
reachable from $\rho^{\prime}$ ". But why is $\rho$ reachable from
$\rho^{\prime}$ ? This is again something that took me a while to figure out.
What you seem to be using here is the following lemma:\newline\textbf{Lemma
3.16a.} Let $G$ be a digraph, and let $\rho$ be a rotor configuration. Let
$\ell\in\mathbb{N}$. Let $\sigma_{1}$, $\sigma_{2}$, $...$, $\sigma_{\ell}$ be
chip configurations such that $\rho$ is reachable from $\sigma_{i}\left(
\rho\right)  $ for every $i\in\left\{  1,2,...,\ell\right\}  $. Then, $\rho$
is reachable from $\left(  \sigma_{1}+\sigma_{2}+...+\sigma_{\ell}\right)
\left(  \rho\right)  $.\newline\textit{Proof.} For every $i\in\left\{
1,2,...,\ell\right\}  $, there exists some chip configuration $\tau_{i}$ such
that $\tau_{i}\left(  \sigma_{i}\left(  \rho\right)  \right)  =\rho$ (since
$\rho$ is reachable from $\sigma_{i}\left(  \rho\right)  $). Consider this
$\tau_{i}$. Then, $\left(  \tau_{i}+\sigma_{i}\right)  \left(  \rho\right)
=\tau_{i}\left(  \sigma_{i}\left(  \rho\right)  \right)  =\rho$. Thus,
$\left(  \tau_{\ell}+\sigma_{\ell}\right)  \rho=\rho$, $\left(  \tau_{\ell
-1}+\sigma_{\ell-1}\right)  \rho=\rho$, $...$, $\left(  \tau_{1}+\sigma
_{1}\right)  \rho=\rho$. Now,%
\begin{align*}
&  \left(  \tau_{1}+\tau_{2}+...+\tau_{\ell}\right)  \left(  \left(
\sigma_{1}+\sigma_{2}+...+\sigma_{\ell}\right)  \left(  \rho\right)  \right)
\\
&  =\left(  \underbrace{\left(  \tau_{1}+\tau_{2}+...+\tau_{\ell}\right)
+\left(  \sigma_{1}+\sigma_{2}+...+\sigma_{\ell}\right)  }_{=\left(  \tau
_{1}+\sigma_{1}\right)  +\left(  \tau_{2}+\sigma_{2}\right)  +...+\left(
\tau_{\ell}+\sigma_{\ell}\right)  }\right)  \left(  \rho\right) \\
&  =\left(  \left(  \tau_{1}+\sigma_{1}\right)  +\left(  \tau_{2}+\sigma
_{2}\right)  +...+\left(  \tau_{\ell}+\sigma_{\ell}\right)  \right)  \left(
\rho\right) \\
&  =\left(  \tau_{1}+\sigma_{1}\right)  \left(  \left(  \tau_{2}+\sigma
_{2}\right)  \left(  ...\left(  \left(  \tau_{\ell-1}+\sigma_{\ell-1}\right)
\underbrace{\left(  \left(  \tau_{\ell}+\sigma_{\ell}\right)  \rho\right)
}_{=\rho}\right)  \right)  \right) \\
&  =\left(  \tau_{1}+\sigma_{1}\right)  \left(  \left(  \tau_{2}+\sigma
_{2}\right)  \left(  ...\left(  \left(  \tau_{\ell-2}+\sigma_{\ell-2}\right)
\underbrace{\left(  \left(  \tau_{\ell-1}+\sigma_{\ell-1}\right)  \rho\right)
}_{=\rho}\right)  \right)  \right) \\
&  =...\\
&  =\left(  \tau_{1}+\sigma_{1}\right)  \rho=\rho.
\end{align*}
Hence, $\rho$ is reachable from $\left(  \sigma_{1}+\sigma_{2}+...+\sigma
_{\ell}\right)  \left(  \rho\right)  $. This proves Lemma 3.16a.\newline You
apply Lemma 3.16a to $\sigma_{j}=\mathbf{1}_{v_{j}}$ (where $\mathbf{1}%
_{v_{j}}$ is the chip configuration consisting of a single chip at $v_{j}$),
thus obtaining that $\rho$ is reachable from $\left(  \mathbf{1}_{v_{1}%
}+\mathbf{1}_{v_{2}}+...+\mathbf{1}_{v_{\ell}}\right)  \left(  \rho\right)  $.
In other words, $\rho$ is reachable from $\left(  \prod\limits_{i}E_{v_{i}%
}\right)  \rho$. Then you apply Lemma 3.16a to $k$ and $\prod\limits_{i}%
E_{v_{i}}$ instead of $\ell$ and $\sigma_{j}$, thus concluding that $\rho$ is
reachable from $\left(  \prod\limits_{i}E_{v_{i}}\right)  ^{k}\rho$. Since
$\rho^{\prime}=\left(  \prod\limits_{i}E_{v_{i}}\right)  ^{k}\rho$, this
yields that $\rho$ is reachable from $\rho^{\prime}$.\newline Is this really
the argument you intended?

\item \textbf{Page 19, proof of Corollary 3.18:} You write: "The rows of
$\Delta^{\prime}\left(  G\right)  $ corresponding to vertices in $S$ sum to
zero". This is ambiguous. The sum of the rows of $\Delta^{\prime}\left(
G\right)  $ corresponding to vertices in $S$ is \textit{not} the zero vector
(unless the indegree of every vertex of $S$ happens to be equal to its
outdegree). What you probably wanted to say is that each row of $\Delta
^{\prime}\left(  G\right)  $ corresponding to a vertex in $S$ has its entries
adding up to $0$, and its only entries are in the columns corresponding to
vertices in $S$. (This yields that if we WLOG assume that the columns
corresponding to the vertices in $S$ are the first $k$ columns of
$\Delta^{\prime}\left(  G\right)  $, and the rows corresponding to the rows in
$S$ are the first $k$ rows of $\Delta^{\prime}\left(  G\right)  $, then
$\Delta^{\prime}\left(  G\right)  $ is a lower block-triangular matrix, and
its upper left part has determinant $0$, so that the whole matrix
$\Delta^{\prime}\left(  G\right)  $ must also have determinant $0$.)

\item \textbf{Page 20, proof of Proposition 3.21:} You write: "Since $h$ is a
harmonic function on $G$ ". I think that $h$ is harmonic on $V\left(
G\right)  \diagdown Z$ only. Thus you should only consider edges $e=\left(
u,v\right)  $ with $u\notin Z$. Can't we actually improve the inequality (1)
by summing only over such edges $e$ on the right hand side? I mean, any other
edge will neither ever be used by a random walk stopped on first hitting $Z$,
nor will it ever be switched by a rotor-router walk stopped on first hitting
$Z$.

\item \textbf{Page 21, proof of Proposition 3.21:} You write: "We assign
weight $\sum_{v}\operatorname*{wt}\left(  \rho\left(  v\right)  \right)  $ to
a rotor configuration $\rho$". I would replace $\rho$ by $\tau$ here, since
$\rho$ already stands for the (fixed!) initial rotor configuration (whose
weight is $0$ since $\operatorname*{wt}\left(  \rho\left(  v\right)  \right)
=0$ for every vertex $v$).

\item \textbf{Page 21, the very first line of Section 4:} Replace $G=\left(
E,V\right)  $ by $G=\left(  V,E\right)  $.

\item \textbf{Page 21, the fourth line of Section 4:} You claim that
"equivalently, $G$ has a sink and every other vertex has out-degree that is at
least as large as its in-degree". I don't think the word "equivalently" is
appropriate here. Surely, if $G$ is an Eulerian digraph with sink, then $G$
has a sink and every other vertex has out-degree that is at least as large as
its in-degree. But the converse doesn't hold: If $G$ has a sink and every
other vertex has out-degree that is at least as large as its in-degree, then
we can add some edges starting at the sink to ensure that every in-degree in
the resulting graph becomes equal to the corresponding out-degree, but nothing
guarantees us that the resulting graph is strongly connected.

\item \textbf{Page 21, the sixth line of Section 4:} You write: "Such a tour
exists if and only if $G$ is Eulerian." I am being really pedantic here, but
no - such a tour can also exist if $G$ consists of an Eulerian graph and some
isolated vertices ;)

\item \textbf{Page 21, proof of Lemma 4.1:} You write: "By the "(4)
$\Longrightarrow$ (1)" part of Lemma 2.17, if $\left(  \sigma+\beta\right)
^{\circ}=\sigma$, then $\sigma$ is recurrent." Are you claiming that every
strongly connected component of $G$ contains some vertex $v$ such that
$\beta\left(  v\right)  >0$ ? This is wrong. Counterexample: Consider a
directed cycle on $4$ vertices. Remove one edge. You get an Eulerian digraph
with sink. Each of its strongly connected components consists of one vertex
only; in particular, the vertex opposite to the sink forms a strongly
connected component, but its $\beta$-value is $0$.\newline Here is how you can
fix this part of the proof:\newline We need something slightly stronger than
the "(4) $\Longrightarrow$ (1)" part of Lemma 2.17. We can get it by adding
another equivalent assertion to Lemma 2.17:\newline(5) There exists an
epidemic chip configuration $\alpha$ such that $\sigma$ is reachable from
$\sigma+\alpha$. Here, a chip configuration $\alpha$ is said to be
\textit{epidemic} if for every vertex $v$ of $G$, there exists a vertex $w$ of
$G$ such that $\alpha\left(  w\right)  >0$ and such that there exists a path
from $w$ to $v$.\newline The proof of (4) $\Longrightarrow$ (5) is obvious,
and the proof of (5) $\Longrightarrow$ (1) is the same as the proof of (4)
$\Longrightarrow$ (1) given in your paper.\newline Now, we claim that in the
situation of Lemma 4.1, the chip configuration $\beta$ is epidemic. In fact,
let $v$ be a vertex of $G$. By the definition of an Eulerian digraph with
sink, the digraph $G$ was obtained by taking an Eulerian digraph $G^{\prime}$
and deleting all the edges from one vertex $s$. Consider such a $G^{\prime}$.
Since $G^{\prime}$ is Eulerian, there exists an Eulerian tour of $G^{\prime}$.
Let us walk \textit{backwards} along this tour, starting at the vertex $v$,
until we reach the vertex $s$ for the first time (with one exception: if
$v=s$, then we walk backwards until we reach the vertex $s$ for the
\textit{second} time). Then, go a step forward again. Let $w$ be the vertex in
which we land. Then, $w$ is the endpoint of an edge from $s$, so that
$\beta\left(  w\right)  >0$, but on the other hand, there exists a path from
$w$ to $v$ in $G$ (namely, we can reach $v$ from $w$ by walking forward along
the Eulerian tour, without ever using an edge from $s$). This shows that
$\beta$ is epidemic, and we can apply the "(5) $\Longrightarrow$ (1)" part of
Lemma 2.17, qed.

\item \textbf{Page 21, proof of Lemma 4.1:} You write: "The rows of
$\Delta^{\prime}$ are linearly independent". Do you have a quick proof for
this seemingly obvious statement? The best proof I can come up with is
nontrivial: Since $G$ is an Eulerian digraph with sink, its sink is a global
sink, and thus it has an oriented spanning tree rooted at the sink. Therefore,
Corollary 3.18 yields that $\det\Delta^{\prime}\left(  G\right)  \geq1$, so
that $\Delta^{\prime}=\Delta^{\prime}\left(  G\right)  $ is nonsingular, i.
e., the rows of $\Delta^{\prime}$ are linearly independent. But this looks
like an overkill argument...

\item \textbf{Page 22, second line of the page:} You write: "Then $\sigma$ is
recurrent if and only if every non-sink vertex fires in the stabilization of
$\sigma+\beta$." I don't think this is true (take $\sigma$ to be a
configuration consisting of very big numbers), but there we can make it true
either by replacing "fires" by "fires exactly once" or by requiring $\sigma$
to be stable. Here are my proofs of this:\newline\textit{Statement 1:} If
$\sigma$ is a chip configuration such that every non-sink vertex fires exactly
once in the stabilization of $\sigma+\beta$, then $\sigma$ is
recurrent.\newline\textit{Statement 2:} If $\sigma$ is a stable chip
configuration such that every non-sink vertex fires at least once in the
stabilization of $\sigma+\beta$, then $\sigma$ is recurrent.\newline%
\textit{Proof of Statement 1:} Let $\sigma$ be a chip configuration such that
every non-sink vertex fires exactly once in the stabilization of $\sigma
+\beta$. Then, $\left(  \sigma+\beta\right)  ^{\circ}=\sigma+\beta
-\sum\limits_{i=1}^{n-1}\Delta_{i}^{\prime}$ (using the notations of the proof
of Lemma 4.1). Since $\beta=\sum\limits_{i=1}^{n-1}\Delta_{i}^{\prime}$, this
yields $\left(  \sigma+\beta\right)  ^{\circ}=\sigma$, and thus $\sigma$ is
recurrent (this is shown just as in the proof of Lemma 4.1). This proves
Statement 1.\newline Before proving Statement 2, we show something
stronger:\newline\textit{Statement 3:} If $\sigma$ is a stable chip
configuration, then every non-sink vertex fires at most once in the
stabilization of $\sigma+\beta$.\newline\textit{Proof of Statement 3:} Assume
the contrary. Then, there exists a stable chip configuration $\sigma$ such
that some non-sink vertex fires more than once in the stabilization of
$\sigma+\beta$. Consider such a $\sigma$. Let $v_{1},v_{2},...,v_{n}$ be the
vertices fired in the stabilization of $\sigma+\beta$ (in this order). Then,
there exists some $j$ such that some $i<j$ satisfies $v_{j}=v_{i}$ (because
some non-sink vertex fires more than once in the stabilization of
$\sigma+\beta$). Consider the smallest such $j$, and consider the
corresponding $i$. Clearly, no two of the vertices $v_{1},v_{2},...,v_{j-1}$
are equal (else, our $j$ wouldn't be the \textit{smallest} $j$ such that some
$i<j$ satisfies $v_{j}=v_{i}$). Just before the vertex $v_{i}=v_{j}$ fired the
first time (at step $i$), it had $\left(  \sigma+\beta\right)  \left(
v_{i}\right)  +\sum\limits_{k=1}^{i-1}a_{v_{k},v_{i}}$ chips (since it had
$\left(  \sigma+\beta\right)  \left(  v_{i}\right)  $ chips at the beginning,
and at step $k$ it obtained $a_{v_{k},v_{i}}$ chips from firing $v_{k}$).
After it fired the first time, it therefore had $\left(  \sigma+\beta\right)
\left(  v_{i}\right)  +\sum\limits_{k=1}^{i-1}a_{v_{k},v_{i}}%
-\operatorname*{outdeg}\left(  v_{i}\right)  +a_{v_{i},v_{i}}$ chips. Just
before it fired the second time (at step $j$), it thus had $\left(
\sigma+\beta\right)  \left(  v_{i}\right)  +\sum\limits_{k=1}^{i-1}%
a_{v_{k},v_{i}}-\operatorname*{outdeg}\left(  v_{i}\right)  +a_{v_{i},v_{i}%
}+\sum\limits_{k=i+1}^{j-1}a_{v_{k},v_{i}}$ chips (since at step $k$ it
obtained $a_{v_{k},v_{i}}$ chips from firing $v_{k}$). This number of chips
must be $\geq\operatorname*{outdeg}\left(  v_{i}\right)  $ (since firing the
vertex $v_{i}$ at step $j$ is allowed). Thus,%
\[
\left(  \sigma+\beta\right)  \left(  v_{i}\right)  +\sum\limits_{k=1}%
^{i-1}a_{v_{k},v_{i}}-\operatorname*{outdeg}\left(  v_{i}\right)
+a_{v_{i},v_{i}}+\sum\limits_{k=i+1}^{j-1}a_{v_{k},v_{i}}\geq
\operatorname*{outdeg}\left(  v_{i}\right)  .
\]
In other words,%
\begin{align*}
0  &  \leq\left(  \sigma+\beta\right)  \left(  v_{i}\right)  +\sum
\limits_{k=1}^{i-1}a_{v_{k},v_{i}}-\operatorname*{outdeg}\left(  v_{i}\right)
+a_{v_{i},v_{i}}+\sum\limits_{k=i+1}^{j-1}a_{v_{k},v_{i}}%
-\operatorname*{outdeg}\left(  v_{i}\right) \\
&  =\underbrace{\left(  \sigma+\beta\right)  \left(  v_{i}\right)  }%
_{=\sigma\left(  v_{i}\right)  +\beta\left(  v_{i}\right)  }+\underbrace{\sum
\limits_{k=1}^{i-1}a_{v_{k},v_{i}}+a_{v_{i},v_{i}}+\sum\limits_{k=i+1}%
^{j-1}a_{v_{k},v_{i}}}_{=\sum\limits_{k=1}^{j-1}a_{v_{k},v_{i}}}%
-\operatorname*{outdeg}\left(  v_{i}\right)  -\operatorname*{outdeg}\left(
v_{i}\right) \\
&  =\underbrace{\sigma\left(  v_{i}\right)  }%
_{\substack{<\operatorname*{outdeg}\left(  v_{i}\right)  \\\text{(since
}\sigma\text{ is stable)}}}+\underbrace{\beta\left(  v_{i}\right)
}_{=\operatorname*{outdeg}\left(  v_{i}\right)  -\operatorname*{indeg}\left(
v_{i}\right)  }+\sum\limits_{k=1}^{j-1}a_{v_{k},v_{i}}-\operatorname*{outdeg}%
\left(  v_{i}\right)  -\operatorname*{outdeg}\left(  v_{i}\right) \\
&  <\operatorname*{outdeg}\left(  v_{i}\right)  +\operatorname*{outdeg}\left(
v_{i}\right)  -\operatorname*{indeg}\left(  v_{i}\right)  +\sum\limits_{k=1}%
^{j-1}a_{v_{k},v_{i}}-\operatorname*{outdeg}\left(  v_{i}\right)
-\operatorname*{outdeg}\left(  v_{i}\right) \\
&  =\sum\limits_{k=1}^{j-1}a_{v_{k},v_{i}}-\operatorname*{indeg}\left(
v_{i}\right)  .
\end{align*}
But for every $k\in\left\{  1,2,...,j-1\right\}  $, the number $a_{v_{k}%
,v_{i}}$ counts all edges from $v_{k}$ to $v_{i}$. Hence, the sum
$\sum\limits_{k=1}^{j-1}a_{v_{k},v_{i}}$ counts all edges from vertices in
$\left\{  v_{1},v_{2},...,v_{j-1}\right\}  $ to $v_{i}$, each of them only
once (since no two of the vertices $v_{1},v_{2},...,v_{j-1}$ are equal), and
thus $\sum\limits_{k=1}^{j-1}a_{v_{k},v_{i}}\leq\operatorname*{indeg}\left(
v_{i}\right)  $. Hence,%
\[
0<\underbrace{\sum\limits_{k=1}^{j-1}a_{v_{k},v_{i}}}_{\leq
\operatorname*{indeg}\left(  v_{i}\right)  }-\operatorname*{indeg}\left(
v_{i}\right)  \leq\operatorname*{indeg}\left(  v_{i}\right)
-\operatorname*{indeg}\left(  v_{i}\right)  =0,
\]
which is a contradiction. Our assumption must therefore be wrong, and
Statement 3 is proven.\newline\textit{Proof of Statement 2:} Let $\sigma$ be a
stable chip configuration such that every non-sink vertex fires at least once
in the stabilization of $\sigma+\beta$. By Statement 3, every non-sink vertex
must have fired at most once in the stabilization of $\sigma+\beta$. Thus,
every non-sink vertex must have fired \textit{exactly} once in the
stabilization of $\sigma+\beta$. Statement 1 now yields that $\sigma$ is
recurrent, so that Statement 2 is proven.

\item \textbf{Page 22, proof of Lemma 4.2:} The proof ends with the words
"which implies $\sigma$ is recurrent by Lemma 2.17." I guess you mean Lemma
4.1 rather than Lemma 2.17 here.

\item \textbf{Page 23, discussion of "multicluster-firing":} You write: "Since
the digraph is Eulerian, $C_{m}$ may be cluster-fired". It took me half a day
to realize why this is true, and my proof is not trivial:\newline Denote by
$\sigma$ the initial chip configuration, before cluster-firing. We have to
show that the configuration $\sigma-\sum\limits_{i\in C_{m}}\Delta_{i}%
^{\prime}$ is nonnegative. In order to do this, it is enough to show that
$\left(  \sigma-\sum\limits_{i\in C_{m}}\Delta_{i}^{\prime}\right)  \left(
v\right)  \geq0$ for every $v\in V\left(  G\right)  $. Since this is obvious
when $v\notin C_{m}$, we can WLOG assume $v\in C_{m}$. Since we can
"multicluster-fire" the multiset union of $C_{m}$, $C_{m-1}$, $...$, $C_{1}$,
we have $\left(  \sigma-\sum\limits_{k=1}^{m}\sum\limits_{i\in C_{k}}%
\Delta_{i}^{\prime}\right)  \left(  v\right)  \geq0$. This rewrites as
$\sigma\left(  v\right)  -\sum\limits_{k=1}^{m}\sum\limits_{i\in C_{k}}%
\Delta_{i}^{\prime}\left(  v\right)  \geq0$.\newline We will now show that
$\sum\limits_{i\in C_{k}}\Delta_{i}^{\prime}\left(  v\right)  \leq0$ for every
$k\in\left\{  1,2,...,m-1\right\}  $. In fact, let $k\in\left\{
1,2,...,m-1\right\}  $ be arbitrary. Then, $v\in C_{m}\subseteq C_{k}$, so
that%
\begin{align*}
\sum\limits_{i\in C_{k}}\Delta_{i}^{\prime}\left(  v\right)   &
=\underbrace{\Delta_{v}^{\prime}\left(  v\right)  }_{=-\operatorname*{outdeg}%
v+a_{v,v}}+\sum\limits_{\substack{i\in C_{k};\\i\neq v}}\underbrace{\Delta
_{i}^{\prime}\left(  v\right)  }_{\substack{=a_{i,v}\\\text{(since }i\neq
v\text{)}}}=\left(  -\operatorname*{outdeg}v+a_{v,v}\right)  +\sum
\limits_{\substack{i\in C_{k};\\i\neq v}}a_{i,v}\\
&  =\underbrace{a_{v,v}+\sum\limits_{\substack{i\in C_{k};\\i\neq v}}a_{i,v}%
}_{=\sum\limits_{i\in C_{k}}a_{i,v}\leq\sum\limits_{i\in V\left(  G\right)
}a_{i,v}=\operatorname*{indeg}v}-\underbrace{\operatorname*{outdeg}%
v}_{\substack{\geq\operatorname*{indeg}v\\\text{(since }G\text{ is an
Eulerian}\\\text{digraph with sink)}}}\leq\operatorname*{indeg}%
v-\operatorname*{indeg}v=0.
\end{align*}
\newline Now,%
\begin{align*}
\left(  \sigma-\sum\limits_{i\in C_{m}}\Delta_{i}^{\prime}\right)  \left(
v\right)   &  =\sigma\left(  v\right)  -\sum\limits_{i\in C_{m}}\Delta
_{i}^{\prime}\left(  v\right) \\
&  =\left(  \sigma\left(  v\right)  -\sum\limits_{k=1}^{m}\sum\limits_{i\in
C_{k}}\Delta_{i}^{\prime}\left(  v\right)  \right)  +\underbrace{\left(
\sum\limits_{k=1}^{m}\sum\limits_{i\in C_{k}}\Delta_{i}^{\prime}\left(
v\right)  -\sum\limits_{i\in C_{m}}\Delta_{i}^{\prime}\left(  v\right)
\right)  }_{=\sum\limits_{k=1}^{m-1}\sum\limits_{i\in C_{k}}\Delta_{i}%
^{\prime}\left(  v\right)  }\\
&  =\underbrace{\left(  \sigma\left(  v\right)  -\sum\limits_{k=1}^{m}%
\sum\limits_{i\in C_{k}}\Delta_{i}^{\prime}\left(  v\right)  \right)  }%
_{\geq0}+\sum\limits_{k=1}^{m-1}\underbrace{\sum\limits_{i\in C_{k}}\Delta
_{i}^{\prime}\left(  v\right)  }_{\geq0}\geq0.
\end{align*}
We have thus proven that every vertex $v$ of $G$ satisfies $\left(
\sigma-\sum\limits_{i\in C_{m}}\Delta_{i}^{\prime}\right)  \left(  v\right)
\geq0$. Thus, the configuration $\sigma-\sum\limits_{i\in C_{m}}\Delta
_{i}^{\prime}$ is nonnegative, so that $C_{m}$ can be cluster-fired from
$\sigma$.

\item \textbf{Page 24, definition of superstabilization:} You write: "We call
the configuration $\sigma_{n}$ in Corollary 4.6 the
\textbf{superstabilization} of $\sigma_{0}$." But why does every chip
configuration actually have a superstabilization?\newline I think this follows
from an analogue of Lemma 2.4:\newline\textbf{Lemma.} For any Eulerian digraph
$G$ with sink, every chip configuration on $G$ can be superstabilized.
Moreover, \textit{any} sequence of allowed cluster-firings eventually has to
stop.\newline\textit{Proof.} For every chip configuration $\sigma$ on $G$, let
$c\left(  \sigma\right)  $ denote the total number of chips in $\sigma$. This
number is $c\left(  \sigma\right)  =\sum\limits_{v\in V\diagdown\left\{
s\right\}  }\sigma\left(  v\right)  $, where $V=V\left(  G\right)  $ and where
$s$ is the sink of $G$.\newline For every vertex $v$ of $G$, let $t\left(
v\right)  $ be the length of the shortest path from $v$ to $s$ in $G$. (Note
that $t\left(  s\right)  =0$.)\newline Let $v_{1},v_{2},...,v_{n-1}$ be an
ordering of $V\diagdown\left\{  s\right\}  $ such that $t\left(  v_{1}\right)
\leq t\left(  v_{2}\right)  \leq...\leq t\left(  v_{n-1}\right)  $.\newline
For every chip configuration $\sigma$ on $G$, let $u\left(  \sigma\right)  $
denote the sequence $\left(  c\left(  \sigma\right)  ,-\sigma\left(
v_{1}\right)  ,-\sigma\left(  v_{2}\right)  ,...,-\sigma\left(  v_{n-1}%
\right)  \right)  $.\newline It is easy to see that whenever we perform an
allowed cluster-firing on a chip configuration $\sigma$, then the resulting
chip configuration $\sigma^{\prime}$ satisfies $u\left(  \sigma^{\prime
}\right)  <u\left(  \sigma\right)  $ with respect to the lexicographic
ordering.\footnote{\textit{Proof.} In fact, let $A$ be the subset we use for
cluster-firing. There exists some $i\in\left\{  1,2,...,n-1\right\}  $ such
that $v_{i}\in A$ (since $A$ is a nonempty subset of $V\diagdown\left\{
s\right\}  =\left\{  v_{1},v_{2},...,v_{n-1}\right\}  $). Take the
\textit{smallest} such $i$. Let $w$ be the second vertex on the shortest path
from $v_{i}$ to $s$. Then, there exists an edge from $v_{i}$ to $w$, and we
have $t\left(  w\right)  <t\left(  v_{i}\right)  $. We distinguish between two
cases:\newline\textit{Case 1:} The vertex $w$ is the sink $s$. In this case,
cluster-firing $A$ results in at least one chip (namely, one of the chips at
$v_{i}$) being moved into the sink (and thus disappearing). Hence, $c\left(
\sigma^{\prime}\right)  <c\left(  \sigma\right)  $ and thus $u\left(
\sigma^{\prime}\right)  <u\left(  \sigma\right)  $ (by the definition of
lexicographic ordering).\newline\textit{Case 2:} The vertex $w$ is not the
sink $s$. Then, $w=v_{j}$ for some $j\in\left\{  1,2,...,n-1\right\}  $.
Consider this $j$. Then, $t\left(  w\right)  =t\left(  v_{j}\right)  $. Thus,
$t\left(  w\right)  <t\left(  v_{i}\right)  $ becomes $t\left(  v_{j}\right)
<t\left(  v_{i}\right)  $. Hence, $j<i$ (because $t\left(  v_{1}\right)  \leq
t\left(  v_{2}\right)  \leq...\leq t\left(  v_{n-1}\right)  $). Consequently,
the vertex $v_{j}$ is not in $A$ (since $i$ was defined as the
\textit{smallest} $i\in\left\{  1,2,...,n-1\right\}  $ such that $v_{i}\in
A$). Hence, cluster-firing $A$ increases the number of chips at $v_{j}$ by at
least $1$ (since at least one chip gets fired from $v_{i}$ to $w=v_{j}$,
whereas $v_{j}$ itself does not fire). In other words, $\sigma^{\prime}\left(
v_{j}\right)  \geq\sigma\left(  v_{j}\right)  +1$. Moreover, for every
$k\in\left\{  1,2,...,i-1\right\}  $, cluster-firing $A$ does not decrease the
number of chips at $v_{k}$ (because $k<i$, so that $v_{k}\notin A$ (since $i$
was defined as the \textit{smallest} $i\in\left\{  1,2,...,n-1\right\}  $ such
that $v_{i}\in A$)). In other words, $\sigma^{\prime}\left(  v_{k}\right)
\geq\sigma\left(  v_{k}\right)  $ for every $k\in\left\{  1,2,...,i-1\right\}
$. Combined with the fact that $\sigma^{\prime}\left(  v_{j}\right)
\geq\sigma\left(  v_{j}\right)  +1$ and that $c\left(  \sigma^{\prime}\right)
\leq c\left(  \sigma\right)  $ (because cluster-firing does not increase the
number of chips), this shows that $u\left(  \sigma^{\prime}\right)  <u\left(
\sigma\right)  $.\newline We have thus showed that $u\left(  \sigma^{\prime
}\right)  <u\left(  \sigma\right)  $ in both cases.}\newline Now, let us start
with a chip configuration $\sigma$ and iteratively cluster-fire nonempty
subsets of $V\diagdown\left\{  s\right\}  $, as long as we can find subsets we
are allowed to cluster-fire. Then, each cluster-firing lowers the value of
$u\left(  \sigma\right)  $ in the lexicographic ordering. But there are only
finitely many possible values of $u\left(  \sigma\right)  $ that can occur
during our iterative cluster-firing (because iterative cluster-firing can only
decrease but never increase$\ c\left(  \sigma\right)  $, and for every fixed
$c\left(  \sigma\right)  $ there are only finitely many possibilities for
$\sigma\left(  v_{1}\right)  ,$ $\sigma\left(  v_{2}\right)  ,$ $...,$
$\sigma\left(  v_{n-1}\right)  $). Thus, our iterative cluster-firing has to
come to an end at some point (i. e., after sufficiently many cluster-firings
our chip configuration becomes superstable). The Lemma is proven.\newline Note
that the Lemma just proven is a generalization of Lemma 2.4, since every
allowed chip-firing operation is an allowed cluster-firing operation (with the
cluster being a one-element subset of $V\left(  G\right)  $). Thus the above
proof of the Lemma can also be seen as an alternative proof of Lemma 2.4.

\item \textbf{Page 26, proof of Lemma 4.9:} You write: "Since $G$ is strongly
connected, we may apply this same argument to every state in the future
history of the system, with every vertex of $G$ playing the role of $w$." It
would be better (for people with a small memory, like me) to state why this
holds (namely, because of Lemma 3.6).

\item \textbf{Page 26, Corollary 4.10:} Replace $\mathcal{T}\left(
G,v\right)  $ by $\mathcal{T}\left(  G,w\right)  $.

\item \textbf{Page 26, proof of Corollary 4.10:} On the first line of this
proof, $\prod\limits_{u\in V}$ should be $\prod\limits_{v\in V}$.

\item \textbf{Page 27, proof of Corollary 4.11:} On the fourth line of this
proof, $\rho\left(  v\right)  =e^{-}$ should be replaced by $\rho^{-}\left(
v\right)  =e^{-}$. Besides, on the third line of the proof, I would replace
"obtained from $\rho$"\ by "obtained from $\rho\mid_{G^{\prime}}$" (to make
clear that "the edge immediately preceding $e$ in the cyclic ordering of the
edges emanating from $v$" does not mean an edge pointing outside of
$\mathcal{C}$).

\item \textbf{Page 27, proof of Lemma 4.12:} The claim that the sandpile group
$\mathcal{S}\left(  G_{v}\right)  $ is "also isomorphic to $\mathbb{Z}%
^{n}\diagup\mathbb{Z}^{n}\Delta\left(  G\right)  $" is wrong, unless you mean
something different by $\Delta\left(  G\right)  $ than the Laplacian of $G$
you defined on page 3. (The group $\mathbb{Z}^{n}\diagup\mathbb{Z}^{n}%
\Delta\left(  G\right)  $ is actually infinite, since every element of
$\mathbb{Z}^{n}\Delta\left(  G\right)  $ has the sum of its coordinates equal
to $0$.) In reality, the sandpile group $\mathcal{S}\left(  G_{v}\right)  $ is
isomorphic to $\mathbb{Z}_{0}^{n}\diagup\mathbb{Z}^{n}\Delta\left(  G\right)
$, where $\mathbb{Z}_{0}^{n}$ is the subgroup
\[
\left\{  x\in\mathbb{Z}^{n}\ \mid\ \text{the sum of the coordinates of
}x\text{ is }0\right\}
\]
of $\mathbb{Z}^{n}$.\newline To be honest I would explain this proof
differently (with less words and more algebra):\newline Let $i:\mathbb{Z}%
^{n-1}\rightarrow\mathbb{Z}_{0}^{n}$ (where $\mathbb{Z}_{0}^{n}$ is defined as
above) be the $\mathbb{Z}$-module isomorphism which maps every vector $\left(
x_{1},x_{2},...,x_{n-1}\right)  $ to $\left(  x_{1},x_{2},...,x_{n-1}%
,-x_{1}-x_{2}-...-x_{n-1}\right)  $.\newline If $d$ denotes any row of
$\Delta^{\prime}\left(  G\right)  $, then $i\left(  d\right)  $ is the
corresponding row of $\Delta\left(  G\right)  $ (because every row of
$\Delta\left(  G\right)  $ has its entries sum up to $0$), so that $i\left(
d\right)  \in\mathbb{Z}^{n}\Delta\left(  G\right)  $. Thus, $i\left(
\mathbb{Z}^{n-1}\Delta^{\prime}\left(  G\right)  \right)  \subseteq
\mathbb{Z}^{n}\Delta\left(  G\right)  $.\newline On the other hand,
$\mathbb{Z}^{n}\Delta\left(  G\right)  $ is the $\mathbb{Z}$-module generated
by the rows of $\Delta\left(  G\right)  $. Since the last row of
$\Delta\left(  G\right)  $ equals minus the sum of all other rows of
$\Delta\left(  G\right)  $, this yields that $\mathbb{Z}^{n}\Delta\left(
G\right)  $ is the $\mathbb{Z}$-module generated by the first $n-1$ rows of
$\Delta\left(  G\right)  $. But since each of these first $n-1$ rows of
$\Delta\left(  G\right)  $ lies in $i\left(  \mathbb{Z}^{n-1}\Delta^{\prime
}\left(  G\right)  \right)  $ (in fact, if $d$ is one of the first $n-1$ rows
of $\Delta\left(  G\right)  $, then $d=i\left(  d^{\prime}\right)  $, where
$d^{\prime}$ is the corresponding row of $\Delta^{\prime}\left(  G\right)  $),
this yields that $\mathbb{Z}^{n}\Delta\left(  G\right)  \subseteq i\left(
\mathbb{Z}^{n-1}\Delta^{\prime}\left(  G\right)  \right)  $. Combined with
$i\left(  \mathbb{Z}^{n-1}\Delta^{\prime}\left(  G\right)  \right)
\subseteq\mathbb{Z}^{n}\Delta\left(  G\right)  $, this yields $i\left(
\mathbb{Z}^{n-1}\Delta^{\prime}\left(  G\right)  \right)  =\mathbb{Z}%
^{n}\Delta\left(  G\right)  $. Hence, $i$ induces a $\mathbb{Z}$-module
isomorphism $\mathbb{Z}^{n-1}\diagup\mathbb{Z}^{n-1}\Delta^{\prime}\left(
G\right)  \rightarrow\mathbb{Z}_{0}^{n}\diagup\mathbb{Z}^{n}\Delta\left(
G\right)  $. Thus, $\mathbb{Z}^{n-1}\diagup\mathbb{Z}^{n-1}\Delta^{\prime
}\left(  G\right)  \cong\mathbb{Z}_{0}^{n}\diagup\mathbb{Z}^{n}\Delta\left(
G\right)  $, which is precisely what we wanted to show.

\item \textbf{Page 28, about Lemma 5.3:} You write: "The next lemma uses
cycle-popping to give a constructive proof of the injectivity of the chip
addition operators $E_{v}$ on acyclic stack configurations. In the case of
periodic rotor stacks, we gave a non-constructive proof in Lemma
3.10."\newline But doesn't Lemma 5.3 rather prove \textit{surjectivity}? (And
surjectivity was already constructively proven - in the case of periodic rotor
stacks - in Lemma 3.10.)

\item \textbf{Page 29, after the proof of Lemma 5.3:} You write: "then the
unique path in $\rho_{0}$ from $v$ to the sink is the \textbf{loop-erasure} of
the path taken by rotor-router walk started at $v$ with initial configuration
$\rho^{\prime}$." First, what does "loop-erasure" mean? (In general, if we
have some directed path with loops, then we can remove them one by one but the
outcome depends on the order in which they were removed. Thus, I think, a
precise definition of "loop-erasure" would be necessary.) Second, how is this proven?

\item \textbf{References:} Judging by Sportiello's website (
http://wwwteor.mi.infn.it/\symbol{126}sportiel/ ), the preprint [CPS07] is now
avaliable on arXiv as arXiv:0809.3416.
\end{itemize}

\end{document}

% What comes now is a proof I wrote up to convince myself it wasn't wrong. It's completely unreadable.

[I am currently done reading the text except for Proposition 3.21 and its proof.]

Now, to something else: Since you don't give a proof of Theorem 5.1 (on page
28), let me do it. First a lemma:

\textbf{Lemma 5.1a.} Let $G$ be a digraph with a global sink. Let $\rho^{0}$
be an infinitive stack configuration on $G$. There exist finitely many cycles
$\mathcal{C}_{1}$, $\mathcal{C}_{2}$, $...$, $\mathcal{C}_{m}$ such that the
stack configuration $\mathcal{C}_{m}\mathcal{C}_{m-1}...\mathcal{C}_{1}%
\rho^{0}$ is acyclic.

\textit{Proof of Lemma 5.1a.} Let $V$ denote the set $V\left(  G\right)  $.
Let $s$ be the sink of $G$.

In the following, whenever $S$ is a subset of $V$, an $S$\textit{-cycle} will
mean a cycle in $G$ all of whose vertices lie in $S$. In particular, this
yields that every cycle in $G$ is a $V$-cycle, whereas no cycle is a
$\varnothing$-cycle. More interestingly, every cycle in $G$ is a
$V\diagdown\left\{  s\right\}  $-cycle, since no cycle can contain $s$.

Whenever $\tau$ is a stack configuration on $G$, a $\tau$\textit{-cycle} will
mean a cycle all of whose edges belong to the rotor $\tau_{0}$. It is clear
(from the definition of "acyclic") that a stack configuration $\tau$ is
acyclic if and only if there exists no $\tau$-cycle.

If $\mathcal{D}$ is a sequence\footnote{Here and in the following, "sequence"
always means "finite or infinite sequence". All sequences (finite or infinite)
are assumed to begin with a $1$-st element (so that bi-infinite sequences are
not considered to be sequences!).} and $i$ is a positive integer, we denote by
$\mathcal{D}_{i}$ the $i$-th element of the sequence $\mathcal{D}$ (as long as
such an element exists).

If $\tau$ is a stack configuration, then a $\tau$-\textit{cycle sequence} will
mean a sequence $\mathcal{D}$ of cycles in $G$ with the following
property:\footnote{\textit{Warning:} A $\tau$-cycle sequence is not the same
as a sequence of $\tau$-cycles!}

\textbf{(*)} Whenever $i$ is a positive integer for which the element
$\mathcal{D}_{i}$ exists, this element $\mathcal{D}_{i}$ is a $\left(
\mathcal{D}_{i-1}\mathcal{D}_{i-2}...\mathcal{D}_{1}\tau\right)  $-cycle.

Clearly, if $\tau$ is a stack configuration, if $\mathcal{D}$ is a $\tau
$-cycle sequence and $i$ is a positive integer for which the element
$\mathcal{D}_{i}$ exists, then the stack configuration $\mathcal{D}%
_{i}\mathcal{D}_{i-1}...\mathcal{D}_{1}\tau$ results from the stack
configuration $\mathcal{D}_{i-1}\mathcal{D}_{i-2}...\mathcal{D}_{1}\tau$ by
reverse popping the stack at each vertex lying on the cycle $\mathcal{D}_{i}$.
As a consequence of this, we see that if $\tau$ is a stack configuration, if
$\mathcal{D}$ is a $\tau$-cycle sequence and $I$ is a positive integer for
which the element $\mathcal{D}_{I}$ exists, then the stack configuration
$\mathcal{D}_{I}\mathcal{D}_{I-1}...\mathcal{D}_{1}\tau$ results from the
stack configuration $\tau$ by reverse popping the stack at each non-sink
vertex $x$ of $G$ for a total of $k_{x}$ times, where $k_{x}$ is the number of
$i\in\left\{  1,2,...,I\right\}  $ such that the cycle $\mathcal{D}_{i}$
contains the vertex $x$.

Now we will show that, for every subset $S$ of $V\diagdown\left\{  s\right\}
$,

\textbf{(1)} for every infinitive stack configuration $\tau$, every $\tau
$-cycle sequence consisting of $S$-cycles is finite.

\textit{Proof of \textbf{(1)}:} We will prove \textbf{(1)} by strong induction
over $\left\vert S\right\vert $:

The induction base (that is, the case $\left\vert S\right\vert =0$) is trivial
(since $\left\vert S\right\vert =0$ yields $S=\varnothing$, and every sequence
consisting of $\varnothing$-cycles is empty\footnote{This is because there are
no $\varnothing$-cycles.}).

Now to the induction step: Let $\lambda\in\mathbb{N}$ be positive. Assume (as
the induction hypothesis) that \textbf{(1)} is proven for every subset $S$ of
$V\diagdown\left\{  s\right\}  $ satisfying $\left\vert S\right\vert <\lambda
$. Now let us prove \textbf{(1)} for every subset $S$ of $V\diagdown\left\{
s\right\}  $ satisfying $\left\vert S\right\vert =\lambda$:

Let $S$ be a subset of $V\diagdown\left\{  s\right\}  $ satisfying $\left\vert
S\right\vert =\lambda$. Let $\tau$ be an infinitive stack configuration.

Let $\mathcal{D}$ be a $\tau$-cycle sequence consisting of $S$-cycles. We are
going to show that $\mathcal{D}$ is finite.

First, we notice that $S$ is nonempty (since $\left\vert S\right\vert
=\lambda$ is positive), and thus there exists some $v_{0}\in S$. Consider this
$v_{0}$. Since $s$ is a global sink of $G$, there exists a (directed) path
from $v_{0}$ to $s$ in $G$. This path starts in a vertex in $S$ (namely, in
$v_{0}\in S$), but ends in a vertex not in $S$ (namely, in $s\notin S$), so it
must leave the set $S$ somewhere. Thus, there exists an edge of $G$ whose tail
lies in $S$ but whose head does not lie in $S$. Let $e$ be such an edge, let
$v$ be its tail, and let $w$ be its head. Then, $v\in S$ and $w\notin S$.

Let $k$ be a nonnegative integer such that $\tau_{-k}\left(  v\right)  =e$
(such a $k$ exists since $\tau$ is infinitive). We now distinguish between two cases:

\textit{Case 1:} There exist at least $k$ different positive integers $i$ such
that the cycle $\mathcal{D}_{i}$ contains the vertex $v$.

\textit{Case 2:} There exist less than $k$ different positive integers $i$
such that the cycle $\mathcal{D}_{i}$ contains the vertex $v$.

First, consider Case 2. In this case, there exist less than $k$ different
positive integers $i$ such that the cycle $\mathcal{D}_{i}$ contains the
vertex $v$. Let $I$ be the highest such integer $i$. Then, none of the cycles
$\mathcal{D}_{I+1},$ $\mathcal{D}_{I+2},$ $\mathcal{D}_{I+3},$ $...$ contains
the vertex $v$. Hence, $\mathcal{D}_{I+1},$ $\mathcal{D}_{I+2},$
$\mathcal{D}_{I+3},$ $...$ are $S\diagdown\left\{  v\right\}  $-cycles (since
we know they are $S$-cycles). The sequence $\left(  \mathcal{D}_{I+1}%
,\mathcal{D}_{I+2},\mathcal{D}_{I+3},...\right)  \ \ \ $ \footnote{The
notation $\left(  \mathcal{D}_{I+1},\mathcal{D}_{I+2},\mathcal{D}%
_{I+3},...\right)  $ does \textit{not} mean that this sequence is necessarily
infinite. (It might even be empty.) This notation simply means that we don't
want to specify whether this sequence is infinite or finite.} is a $\left(
\mathcal{D}_{I}\mathcal{D}_{I-1}...\mathcal{D}_{1}\tau\right)  $-cycle
sequence (since $\mathcal{D}$ is a $\tau$-cycle sequence) consisting of
$S\diagdown\left\{  v\right\}  $-cycles (because $\mathcal{D}_{I+1},$
$\mathcal{D}_{I+2},$ $\mathcal{D}_{I+3},$ $...$ are $S\diagdown\left\{
v\right\}  $-cycles). Since $\left\vert S\diagdown\left\{  v\right\}
\right\vert <\left\vert S\right\vert =\lambda$, we can now apply \textbf{(1)}
to $S\diagdown\left\{  v\right\}  $ and $\mathcal{D}_{I}\mathcal{D}%
_{I-1}...\mathcal{D}_{1}\tau$ instead of $S$ and $\tau$ (by the induction
hypothesis)\footnote{Here we are tacitly using the fact that the stack
configuration $\mathcal{D}_{I}\mathcal{D}_{I-1}...\mathcal{D}_{1}\tau$ is
infinitive. (This, however, is very easy to see using the condition that
$\tau$ is infinitive.)}, and conclude that every $\left(  \mathcal{D}%
_{I}\mathcal{D}_{I-1}...\mathcal{D}_{1}\tau\right)  $-cycle sequence
consisting of $S\diagdown\left\{  v\right\}  $-cycles is finite. Since
$\left(  \mathcal{D}_{I+1},\mathcal{D}_{I+2},\mathcal{D}_{I+3},...\right)  $
is a $\left(  \mathcal{D}_{I}\mathcal{D}_{I-1}...\mathcal{D}_{1}\tau\right)
$-cycle sequence consisting of $S\diagdown\left\{  v\right\}  $-cycles, we
thus conclude that $\left(  \mathcal{D}_{I+1},\mathcal{D}_{I+2},\mathcal{D}%
_{I+3},...\right)  $ is finite. Hence, $\mathcal{D}$ is finite in Case 2.

Now let us consider Case 1. In this case, there exist at least $k$ different
positive integers $i$ such that the cycle $\mathcal{D}_{i}$ contains the
vertex $v$. Let $i_{1},i_{2},...,i_{k}$ be the first $k$ such positive
integers, in increasing order. Let $I=i_{k}$. Then, $k$ is the number of
$i\in\left\{  1,2,...,I\right\}  $ such that the cycle $\mathcal{D}_{i}$
contains the vertex $v$.

The stack configuration $\mathcal{D}_{I}\mathcal{D}_{I-1}...\mathcal{D}%
_{1}\tau$ is obtained from the stack configuration $\tau$ by reverse popping
the stacks at some vertices; more precisely, for every non-sink vertex $x$,
the stack $\left(  \mathcal{D}_{I}\mathcal{D}_{I-1}...\mathcal{D}_{1}%
\tau\right)  \left(  x\right)  $ is the result of reverse popping the stack
$\tau\left(  x\right)  $ for a total of $k_{x}$ times, where $k_{x}$ is the
number of $i\in\left\{  1,2,...,I\right\}  $ such that the cycle
$\mathcal{D}_{i}$ contains the vertex $x$. Since $k_{v}=k$ (because $k$ is the
number of $i\in\left\{  1,2,...,I\right\}  $ such that the cycle
$\mathcal{D}_{i}$ contains the vertex $v$), this yields that the stack
$\left(  \mathcal{D}_{I}\mathcal{D}_{I-1}...\mathcal{D}_{1}\tau\right)
\left(  v\right)  $ is the result of reverse popping the stack $\tau\left(
v\right)  $ for a total of $k$ times. Thus, $\left(  \mathcal{D}%
_{I}\mathcal{D}_{I-1}...\mathcal{D}_{1}\tau\right)  _{0}\left(  v\right)
=\tau_{-k}\left(  v\right)  =e$.

Now, we will show that

\textbf{(2)} for every integer $j\geq I$ for which the element $\mathcal{D}%
_{j}$ exists, we have $\left(  \mathcal{D}_{j}\mathcal{D}_{j-1}...\mathcal{D}%
_{1}\tau\right)  _{0}\left(  v\right)  =e$.\ \ \ \ \footnote{\textit{Proof of
\textbf{(2)}:} We will prove \textbf{(2)} by induction over $j$:\newline The
induction base (the case $j=I$) follows from $\left(  \mathcal{D}%
_{I}\mathcal{D}_{I-1}...\mathcal{D}_{1}\tau\right)  _{0}\left(  v\right)
=e$.\newline Now to the induction step: Let $j\geq I$ be an integer for which
the elements $\mathcal{D}_{j}$ and $\mathcal{D}_{j+1}$ exist. Assume that
$\left(  \mathcal{D}_{j}\mathcal{D}_{j-1}...\mathcal{D}_{1}\tau\right)
_{0}\left(  v\right)  =e$. We must now prove that $\left(  \mathcal{D}%
_{j+1}\mathcal{D}_{j}...\mathcal{D}_{1}\tau\right)  _{0}\left(  v\right)
=e$.\newline By \textbf{(*)}, applied to $j+1$ instead of $i$, we see that
$\mathcal{D}_{j+1}$ is a $\left(  \mathcal{D}_{j}\mathcal{D}_{j-1}%
...\mathcal{D}_{1}\tau\right)  $-cycle. On the other hand, $\mathcal{D}_{j+1}$
must be an $S$-cycle (since $\mathcal{D}$ is a sequence of $S$-cycles), so it
cannot pass through $w$ (because $w\notin S$). Thus, it cannot pass through
$v$ (because if it would pass through $v$, then, being a $\left(
\mathcal{D}_{j}\mathcal{D}_{j-1}...\mathcal{D}_{1}\tau\right)  $-cycle, it
would also have to pass through the head of the edge $\left(  \mathcal{D}%
_{j}\mathcal{D}_{j-1}...\mathcal{D}_{1}\tau\right)  _{0}\left(  v\right)  $;
but this head is $w$ (because $\left(  \mathcal{D}_{j}\mathcal{D}%
_{j-1}...\mathcal{D}_{1}\tau\right)  _{0}\left(  v\right)  =e$ and because the
head of $e$ is $w$), and we know that it cannot pass through $w$). Hence, when
$\mathcal{D}_{j+1}$ is applied to the stack configuration $\mathcal{D}%
_{j}\mathcal{D}_{j-1}...\mathcal{D}_{1}\tau$, the stack at $v$ is not being
reverse popped. Hence, $\left(  \mathcal{D}_{j+1}\left(  \mathcal{D}%
_{j}\mathcal{D}_{j-1}...\mathcal{D}_{1}\tau\right)  \right)  _{0}\left(
v\right)  =\left(  \mathcal{D}_{j}\mathcal{D}_{j-1}...\mathcal{D}_{1}%
\tau\right)  _{0}\left(  v\right)  =e$. Since $\mathcal{D}_{j+1}\left(
\mathcal{D}_{j}\mathcal{D}_{j-1}...\mathcal{D}_{1}\tau\right)  =\mathcal{D}%
_{j+1}\mathcal{D}_{j}...\mathcal{D}_{1}\tau$, this rewrites as $\left(
\mathcal{D}_{j+1}\mathcal{D}_{j}...\mathcal{D}_{1}\tau\right)  _{0}\left(
v\right)  =e$. This completes the induction step. \textbf{(2)} is thus
proven.}

As a consequence:

\textbf{(3)} for every integer $j\geq I$ for which the element $\mathcal{D}%
_{j+1}$ exists, the cycle $\mathcal{D}_{j+1}$ does not contain the vertex
$v$.\ \ \ \ \footnote{\textit{Proof of \textbf{(3)}:} Let $j\geq I$ be an
integer for which the element $\mathcal{D}_{j+1}$ exists. By \textbf{(*)},
applied to $j+1$ instead of $i$, we see that $\mathcal{D}_{j+1}$ is a $\left(
\mathcal{D}_{j}\mathcal{D}_{j-1}...\mathcal{D}_{1}\tau\right)  $-cycle. On the
other hand, $\mathcal{D}_{j+1}$ must be an $S$-cycle (since $\mathcal{D}$ is a
sequence of $S$-cycles), so it cannot pass through $w$ (because $w\notin S$).
Thus, it cannot pass through $v$ (because if it would pass through $v$, then,
being a $\left(  \mathcal{D}_{j}\mathcal{D}_{j-1}...\mathcal{D}_{1}%
\tau\right)  $-cycle, it would also have to pass through the head of the edge
$\left(  \mathcal{D}_{j}\mathcal{D}_{j-1}...\mathcal{D}_{1}\tau\right)
_{0}\left(  v\right)  $; but this head is $w$ (because $\left(  \mathcal{D}%
_{j}\mathcal{D}_{j-1}...\mathcal{D}_{1}\tau\right)  _{0}\left(  v\right)  =e$
and because the head of $e$ is $w$), and we know that it cannot pass through
$w$). This proves \textbf{(3)}.}

In other words, none of the cycles $\mathcal{D}_{I+1},$ $\mathcal{D}_{I+2},$
$\mathcal{D}_{I+3},$ $...$ contains the vertex $v$. Now, continuing as in Case
2, we can show that $\mathcal{D}$ is finite.

Hence, in both cases 1 and 2, we have proven that $\mathcal{D}$ is finite. We
have thus seen that for our subset $S$ and for every infinitive stack
configuration $\tau$, every $\tau$-cycle sequence consisting of $S$-cycles is
finite. In other words, \textbf{(1)} holds for our subset $S$ (which was
chosen as an arbitrary subset of $V\diagdown\left\{  s\right\}  $ satisfying
$\left\vert S\right\vert =\lambda$). This completes the induction step. Hence,
by induction, \textbf{(1)} is proven for all subsets $S$ of $V\diagdown
\left\{  s\right\}  $.

Now, applying \textbf{(1)} to $S=V\diagdown\left\{  s\right\}  $, we obtain that:

\textbf{(4)} for every infinitive stack configuration $\tau$, every $\tau
$-cycle sequence consisting of $V\diagdown\left\{  s\right\}  $-cycles is finite.

Since every cycle is a $V\diagdown\left\{  s\right\}  $-cycle, \textbf{(4)} yields:

\textbf{(5)} for every infinitive stack configuration $\tau$, every $\tau
$-cycle sequence is finite.

Now let us prove Lemma 5.1a: Let $\rho^{0}$ be an infinitive stack
configuration on $G$. We recursively construct a $\rho^{0}$-cycle sequence
$\mathcal{D}$ by the following algorithm:

- Initialize $\mathcal{D}$ as an empty sequence.

- \textbf{Start loop.} Let $i$ be the current length of the sequence
$\mathcal{D}$ (so that $\mathcal{D}$ is currently an $i$-element sequence). If
$\mathcal{D}_{i}\mathcal{D}_{i-1}...\mathcal{D}_{1}\rho^{0}$ is an acyclic
stack configuration, then break out of the loop and declare the sequence
$\mathcal{D}$ as finished. If not, there exists a $\left(  \mathcal{D}%
_{i}\mathcal{D}_{i-1}...\mathcal{D}_{1}\rho^{0}\right)  $-cycle. Pick such a
cycle\footnote{If you wish to avoid the axiom of choice here, you can decide
to pick the lowermost cycle in some pre-chosen ordering on all cycles of $G$.}
and denote it by $\mathcal{D}_{i+1}$, thus extending the sequence
$\mathcal{D}$ to $i+1$ elements. \textbf{End loop.}

This algorithm either terminates, yielding a finite $\rho^{0}$-cycle sequence
$\mathcal{D}$, or it goes on forever, yielding (in the limit) an infinite
$\rho^{0}$-cycle sequence $\mathcal{D}$. But the latter case is impossible
(due to \textbf{(5)}, applied to $\tau=\rho^{0}$). Hence, we must be in the
former case. That is, the algorithm terminates, yielding a finite $\rho^{0}%
$-cycle sequence $\mathcal{D}$. Let $i$ be the number of elements of this
sequence. Then, the algorithm must have terminated after $i$ iterations of the
loop; thus, the configuration $\mathcal{D}_{i}\mathcal{D}_{i-1}...\mathcal{D}%
_{1}\rho^{0}$ is acyclic.

We have hence found finitely many cycles $\mathcal{C}_{1}$, $\mathcal{C}_{2}$,
$...$, $\mathcal{C}_{m}$ such that the stack configuration $\mathcal{C}%
_{m}\mathcal{C}_{m-1}...\mathcal{C}_{1}\rho^{0}$ is acyclic (namely, $m=i$ and
$\mathcal{C}_{k}=\mathcal{D}_{k}$). This proves Lemma 5.1a.

Lemma 5.1a was one half of Theorem 5.1. To prove the other half, let us show a
result which can be called an "abelian property"\ of cycle-popping (it is an
analogue of Lemmas 2.2 and 3.9):

\textbf{Lemma 5.1b.} Let $G$ be a digraph with a global sink. Let $\tau$ be a
stack configuration on $G$ (not necessarily infinitive).

Let $\mathcal{C}=\left(  \mathcal{C}_{1},\mathcal{C}_{2},...,\mathcal{C}%
_{m}\right)  $ and $\mathcal{C}^{\prime}=\left(  \mathcal{C}_{1}^{\prime
},\mathcal{C}_{2}^{\prime},...,\mathcal{C}_{\ell}^{\prime}\right)  $ be two
finite sequences of cycles of $G$.

\textbf{(a)} Assume that the stack configuration $\mathcal{C}_{m}%
\mathcal{C}_{m-1}...\mathcal{C}_{1}\tau$ is acyclic, and that $\mathcal{C}%
^{\prime}$ is a $\tau$-cycle sequence. Then $\ell\leq m$ and moreover, the
sequence $\mathcal{C}^{\prime}$ is a permutation of a subsequence of
$\mathcal{C}$.

\textbf{(b)} Assume that both stack configurations $\mathcal{C}_{m}%
\mathcal{C}_{m-1}...\mathcal{C}_{1}\tau$ and $\mathcal{C}_{\ell}^{\prime
}\mathcal{C}_{\ell-1}^{\prime}...\mathcal{C}_{1}^{\prime}\tau$ are acyclic,
and that both sequences $\mathcal{C}$ and $\mathcal{C}^{\prime}$ are $\tau
$-cycle sequences. Then $\ell=m$, $\mathcal{C}_{m}\mathcal{C}_{m-1}%
...\mathcal{C}_{1}\tau=\mathcal{C}_{\ell}^{\prime}\mathcal{C}_{\ell-1}%
^{\prime}...\mathcal{C}_{1}^{\prime}\tau$, and moreover, the sequence
$\mathcal{C}^{\prime}$ is a permutation of the sequence $\mathcal{C}$.

\textit{Remark:} Here we are using the following definitions (which we already
made in the proof of Lemma 5.1a):

- Whenever $\tau$ is a stack configuration on $G$, a $\tau$\textit{-cycle}
will mean a cycle all of whose edges belong to the rotor $\tau_{0}$. It is
clear (from the definition of "acyclic") that a stack configuration $\tau$ is
acyclic if and only if there exists no $\tau$-cycle.

- If $\mathcal{D}$ is a sequence\footnote{Here and in the following,
"sequence" always means "finite or infinite sequence". All sequences (finite
or infinite) are assumed to begin with a $1$-st element (so that bi-infinite
sequences are not considered to be sequences!).} and $i$ is a positive
integer, we denote by $\mathcal{D}_{i}$ the $i$-th element of the sequence
$\mathcal{D}$ (as long as such an element exists).

- If $\tau$ is a stack configuration on the digraph $G$, then a $\tau
$-\textit{cycle sequence} will mean a sequence $\mathcal{D}$ of cycles in $G$
with the following property:\footnote{\textit{Warning:} A $\tau$-cycle
sequence is not the same as a sequence of $\tau$-cycles!}

\textbf{(*)} Whenever $i$ is a positive integer for which the element
$\mathcal{D}_{i}$ exists, this element $\mathcal{D}_{i}$ is a $\left(
\mathcal{D}_{i-1}\mathcal{D}_{i-2}...\mathcal{D}_{1}\tau\right)  $-cycle.

\textit{Proof of Lemma 5.1b.}\footnote{The following proof is a calque of your
proof of Lemma 2.2 (although I have written it as an induction proof, whereas
you are arguing about a minimal counterexample).} \textbf{(a)} Before we start
proving this lemma, we notice some general facts about cycle popping:

\textbf{(6)} If $\mathcal{D}$ and $\mathcal{E}$ are two cycles such that
$\mathcal{D}\cap\mathcal{E}=\varnothing$\ \ \ \ \footnote{Here and in the
following, whenever $\mathcal{D}$ and $\mathcal{E}$ are two cycles, we denote
by $\mathcal{D}\cap\mathcal{E}$ the set of all vertices common to both cycles
$\mathcal{D}$ and $\mathcal{E}$.}, and if $\kappa$ is a stack configuration
such that $\mathcal{D}$ is a $\kappa$-cycle, then $\mathcal{D}$ is also a
$\left(  \mathcal{E}\kappa\right)  $-cycle.\footnote{\textit{Proof of
\textbf{(6)}:} Let $\mathcal{D}$ and $\mathcal{E}$ be two cycles such that
$\mathcal{D}\cap\mathcal{E}=\varnothing$, and let $\kappa$ be a stack
configuration such that $\mathcal{D}$ is a $\kappa$-cycle.
\par
The definition of $\mathcal{E}\kappa$ yields that $\left(  \mathcal{E}%
\kappa\right)  \left(  v\right)  =\kappa\left(  v\right)  $ for every vertex
$v$ not on the cycle $\mathcal{E}$. Hence, in particular, $\left(
\mathcal{E}\kappa\right)  \left(  v\right)  =\kappa\left(  v\right)  $ for
every vertex $v$ on the cycle $\mathcal{D}$ (since $\mathcal{D}\cap
\mathcal{E}=\varnothing$, and thus every vertex $v$ on the cycle $\mathcal{D}$
is not on the cycle $\mathcal{E}$). Thus, $\left(  \mathcal{E}\kappa\right)
_{0}\left(  v\right)  =\kappa_{0}\left(  v\right)  $ for every vertex $v$ on
the cycle $\mathcal{D}$.
\par
But each edge of the cycle $\mathcal{D}$ has the form $\kappa_{0}\left(
v\right)  $ for some vertex $v$ on the cycle $\mathcal{D}$ (since
$\mathcal{D}$ is a $\kappa$-cycle). Since $\kappa_{0}\left(  v\right)
=\left(  \mathcal{E}\kappa\right)  _{0}\left(  v\right)  $ for every vertex
$v$ on the cycle $\mathcal{D}$, this can be rewritten as follows: Each edge of
the cycle $\mathcal{D}$ has the form $\left(  \mathcal{E}\kappa\right)
_{0}\left(  v\right)  $ for some vertex $v$ on the cycle $\mathcal{D}$. Thus,
$\mathcal{D}$ is an $\left(  \mathcal{E}\kappa\right)  $-cycle. This proves
\textbf{(6)}.}

\textbf{(7)} If $\kappa$ is a stack configuration, and if $\mathcal{D}$ and
$\mathcal{E}$ are two $\kappa$-cycles which have a vertex in common, then
$\mathcal{D}=\mathcal{E}$. (Here, cycles are considered as subgraphs of $G$,
so that $\mathcal{D}=\mathcal{E}$ means that the vertices of $\mathcal{D}$ are
the same as the vertices of $\mathcal{E}$ and the edges of $\mathcal{D}$ are
the same as the edges of $\mathcal{E}$.)\ \ \ \ \footnote{\textit{Proof of
\textbf{(7)}:} Let $\kappa$ be a stack configuration, and let $\mathcal{D}$
and $\mathcal{E}$ be two $\kappa$-cycles which have a vertex in common. Let
$v$ be this vertex. Let $e_{1},$ $e_{2},$ $e_{3},$ $...$ be the edges of the
cycle $\mathcal{D}$ in the order they appear when we walk along the cycle
$\mathcal{D}$ starting at $v$ (of course, the infinitely many edges $e_{1},$
$e_{2},$ $e_{3},$ $...$ will not be pairwise distinct). Let $f_{1},$ $f_{2},$
$f_{3},$ $...$ be the edges of the cycle $\mathcal{E}$ in the order they
appear when we walk along the cycle $\mathcal{E}$ starting at $v$. Let us
prove that every positive integer $i$ satisfies $e_{i}=f_{i}$. In fact, we
will prove this by induction over $i$:
\par
\textit{Induction base:} The edge $e_{1}$ starts at $v$ (because it is the
first edge that appears when we walk along the cycle $\mathcal{D}$ starting at
$v$). Since $e_{1}$ is an edge of the rotor $\kappa_{0}$ (because
$\mathcal{D}$ is a $\kappa$-cycle, whereas $e_{1}$ is an edge of $\mathcal{D}%
$), this yields that $e_{1}=\kappa_{0}\left(  v\right)  $. Similarly,
$f_{1}=\kappa_{0}\left(  v\right)  $. Thus, $e_{1}=f_{1}$. In other words,
$e_{i}=f_{i}$ is proven for $i=1$. This completes the induction base.
\par
\textit{Induction step:} Let $j$ be a positive integer. Assume that
$e_{i}=f_{i}$ holds for $i=j$. We now will prove that $e_{i}=f_{i}$ holds for
$i=j+1$.
\par
Since $e_{i}=f_{i}$ holds for $i=j$, we have $e_{j}=f_{j}$. Let $t$ be the
tail of the edge $e_{j}=f_{j}$. Now, the edge $e_{j+1}$ starts at the tail of
$e_{j}$ (since $e_{1},$ $e_{2},$ $e_{3},$ $...$ are the edges of the cycle
$\mathcal{D}$ in the order they appear when we walk along the cycle
$\mathcal{D}$ starting at $v$). Since the tail of $e_{j}$ is $t$, this yields
that the edge $e_{j+1}$ starts at $t$. Since $e_{j+1}$ is an edge of the rotor
$\kappa_{0}$ (because $\mathcal{D}$ is a $\kappa$-cycle, whereas $e_{j+1}$ is
an edge of $\mathcal{D}$), this yields that $e_{j+1}$ is the edge of the rotor
$\kappa_{0}$ starting at $t$. In other words, $e_{j+1}=\kappa_{0}\left(
t\right)  $. Similarly, $f_{j+1}=\kappa_{0}\left(  t\right)  $. Thus,
$e_{j+1}=f_{j+1}$. In other words, $e_{i}=f_{i}$ is proven for $i=j+1$. This
completes the induction step. Thus, the induction is done.
\par
We have thus shown that every positive integer $i$ satisfies $e_{i}=f_{i}$.
Thus, $\left\{  e_{1},e_{2},e_{3},...\right\}  =\left\{  f_{1},f_{2}%
,f_{3},...\right\}  $. Since $\left\{  e_{1},e_{2},e_{3},...\right\}  $ is the
set of edges of the cycle $\mathcal{D}$ (by the definition of $e_{1},$
$e_{2},$ $e_{3},$ $...$), whereas $\left\{  f_{1},f_{2},f_{3},...\right\}  $
is the set of edges of the cycle $\mathcal{E}$, this yields that the set of
edges of the cycle $\mathcal{D}$ equals the set of edges of the cycle
$\mathcal{E}$. Thus, $\mathcal{D}=\mathcal{E}$ (because two cycles whose sets
of edges are equal must be equal). This proves \textbf{(7)}.}

As a consequence of these facts, we have:

\textbf{(8)} If $\kappa$ is a stack configuration, and if $\mathcal{D}$ and
$\mathcal{E}$ are two $\kappa$-cycles such that $\mathcal{D}\neq\mathcal{E}$,
then $\mathcal{D}$ is also a $\left(  \mathcal{E}\kappa\right)  $-cycle, and
$\mathcal{E}$ is also a $\left(  \mathcal{D}\kappa\right)  $-cycle, and we
have $\mathcal{D}\left(  \mathcal{E}\kappa\right)  =\mathcal{E}\left(
\mathcal{D}\kappa\right)  $.\ \ \ \ \footnote{\textit{Proof of \textbf{(8)}:}
Let $\kappa$ be a stack configuration, and $\mathcal{D}$ and $\mathcal{E}$ be
two $\kappa$-cycles such that $\mathcal{D}\neq\mathcal{E}$.
\par
The cycles $\mathcal{D}$ and $\mathcal{E}$ have no vertex in common (because
otherwise, we would be able to apply \textbf{(7)} and obtain that
$\mathcal{D}=\mathcal{E}$ , contradicting $\mathcal{D}\neq\mathcal{E}$). In
other words, $\mathcal{D}\cap\mathcal{E}=\varnothing$. Using \textbf{(6)},
this yields that $\mathcal{D}$ is a $\left(  \mathcal{E}\kappa\right)
$-cycle.
\par
Applying the same reasoning to $\mathcal{D}$ and $\mathcal{E}$ instead of
$\mathcal{E}$ and $\mathcal{D}$, we conclude that $\mathcal{E}$ is a $\left(
\mathcal{D}\kappa\right)  $-cycle.
\par
The stack configuration $\mathcal{E}\left(  \mathcal{D}\kappa\right)  $
results from the stack configuration $\mathcal{D}\kappa$ by reverse popping
the stack at every vertex on the cycle $\mathcal{E}$ (by the definition of
$\mathcal{E}\left(  \mathcal{D}\kappa\right)  $, since $\mathcal{E}$ is a
$\left(  \mathcal{D}\kappa\right)  $-cycle). On the other hand, the stack
configuration $\mathcal{D}\kappa$ results from the stack configuration
$\kappa$ by reverse popping the stack at every vertex on the cycle
$\mathcal{D}$ (by the definition of $\mathcal{D}\kappa$, since $\mathcal{D}$
is a $\kappa$-cycle). Combining the previous two sentences, we conclude that:
\par
\textbf{(9)} The stack configuration $\mathcal{E}\left(  \mathcal{D}%
\kappa\right)  $ results from the stack configuration $\kappa$ by first
reverse popping the stack at every vertex on the cycle $\mathcal{D}$ (this
yields the stack configuration $\mathcal{D}\kappa$) and then reverse popping
the stack at every vertex on the cycle $\mathcal{E}$.
\par
By interchanging the roles of $\mathcal{D}$ and $\mathcal{E}$ in this
argument, we conclude that:
\par
\textbf{(10)} The stack configuration $\mathcal{D}\left(  \mathcal{E}%
\kappa\right)  $ results from the stack configuration $\kappa$ by first
reverse popping the stack at every vertex on the cycle $\mathcal{E}$ (this
yields the stack configuration $\mathcal{E}\kappa$) and then reverse popping
the stack at every vertex on the cycle $\mathcal{D}$.
\par
Now, it is clear that in \textbf{(10)}, we can interchange the
\textquotedblright reverse popping the stack at every vertex on the cycle
$\mathcal{E}$ \textquotedblright\ and \textquotedblright reverse popping the
stack at every vertex on the cycle $\mathcal{D}$ \textquotedblright\ steps
(because the resulting stack configuration does not depend on in which order
we reverse pop the stacks, as long as we do not change the choice which stacks
to reverse pop). Upon this interchange, \textbf{(10)} transforms into:
\par
\textbf{(11)} The stack configuration $\mathcal{D}\left(  \mathcal{E}%
\kappa\right)  $ results from the stack configuration $\kappa$ by first
reverse popping the stack at every vertex on the cycle $\mathcal{D}$ (this
yields the stack configuration $\mathcal{D}\kappa$) and then reverse popping
the stack at every vertex on the cycle $\mathcal{E}$.
\par
Comparing this with \textbf{(9)}, we conclude that the stack configuration
$\mathcal{D}\left(  \mathcal{E}\kappa\right)  $ equals the stack configuration
$\mathcal{E}\left(  \mathcal{D}\kappa\right)  $.
\par
We thus have proven $\mathcal{D}\left(  \mathcal{E}\kappa\right)
=\mathcal{E}\left(  \mathcal{D}\kappa\right)  $. This completes the proof of
\textbf{(8)}.}

At least the last part of this statement can be somewhat generalized:

\textbf{(12)} If $\kappa$ is a stack configuration, and if $\mathcal{D}$ and
$\mathcal{E}$ are two $\kappa$-cycles, then $\mathcal{D}\left(  \mathcal{E}%
\kappa\right)  =\mathcal{E}\left(  \mathcal{D}\kappa\right)  $%
.\ \ \ \ \footnote{\textit{Proof of \textbf{(12)}:} Let $\kappa$ be a stack
configuration, and $\mathcal{D}$ and $\mathcal{E}$ be two $\kappa$-cycles.
Then, we distinguish between two cases:
\par
\textit{Case 1:} We have $\mathcal{D}=\mathcal{E}$.
\par
\textit{Case 2:} We have $\mathcal{D}\neq\mathcal{E}$.
\par
In Case 1, it is immediately clear that $\mathcal{D}\left(  \mathcal{E}%
\kappa\right)  =\mathcal{E}\left(  \mathcal{D}\kappa\right)  $. In Case 2, the
equality $\mathcal{D}\left(  \mathcal{E}\kappa\right)  =\mathcal{E}\left(
\mathcal{D}\kappa\right)  $ follows from \textbf{(8)}. Thus, in both cases, we
have proven the equality $\mathcal{D}\left(  \mathcal{E}\kappa\right)
=\mathcal{E}\left(  \mathcal{D}\kappa\right)  $. Hence, $\mathcal{D}\left(
\mathcal{E}\kappa\right)  =\mathcal{E}\left(  \mathcal{D}\kappa\right)  $
always holds, so that \textbf{(12)} is proven.}

We are now ready to start proving Lemma 5.1b.

\textbf{(a)} Let us prove Lemma 5.1b \textbf{(a)} by induction over $m$:

The \textit{induction base} (the case $m=0$) is very
easy\footnote{\textit{Proof.} Assume that $m=0$.
\par
Then, the stack configuration $\tau$ is acyclic (since the stack configuration
$\mathcal{C}_{m}\mathcal{C}_{m-1}...\mathcal{C}_{1}\tau$ is acyclic, but
$m=0$), so that there exist no $\tau$-cycles. If the sequence $\mathcal{C}%
^{\prime}$ would have at least one element, then the element $\mathcal{C}%
_{1}^{\prime}$ would exist, and this element $\mathcal{C}_{1}^{\prime}$ would
be a $\tau$-cycle (since $\mathcal{C}^{\prime}$ is a $\tau$-cycle sequence),
contradicting to the fact that there are no $\tau$-cycles. Hence, the sequence
$\mathcal{C}^{\prime}$ \textit{cannot} have at least one element. In other
words, the sequence $\mathcal{C}^{\prime}$ is empty. Thus, $\ell=0$. This
immediately yields $\ell\leq m$, and moreover, the sequence $\mathcal{C}%
^{\prime}$ is a permutation of a subsequence of $\mathcal{C}$ (because
$\mathcal{C}^{\prime}$ is the empty sequence). This proves Lemma 5.1a
\textbf{(a)} in the case $m=0$. In other words, this completes the induction
base.}.

Now to the \textit{induction step}: Let $\mu$ be a positive integer. Assume
(as our induction hypothesis) that Lemma 5.1b \textbf{(a)} holds whenever
$m=\mu-1$. We will now show that Lemma 5.1b \textbf{(a)} also holds whenever
$m=\mu$.

In fact, let $\tau$ be a stack configuration on $G$. Let $\mathcal{C}=\left(
\mathcal{C}_{1},\mathcal{C}_{2},...,\mathcal{C}_{m}\right)  $ and
$\mathcal{C}^{\prime}=\left(  \mathcal{C}_{1}^{\prime},\mathcal{C}_{2}%
^{\prime},...,\mathcal{C}_{\ell}^{\prime}\right)  $ be two finite sequences of
cycles of $G$ such that $m=\mu$. Assume that the stack configuration
$\mathcal{C}_{m}\mathcal{C}_{m-1}...\mathcal{C}_{1}$ is acyclic, and that
$\mathcal{C}^{\prime}$ is a $\tau$-cycle sequence. We are now going to show
that $\ell\leq m$ and that the sequence $\mathcal{C}^{\prime}$ is a
permutation of a subsequence of $\mathcal{C}$.

We distinguish between two cases:

\textit{Case 1:} The sequence $\mathcal{C}$ is a $\tau$-cycle sequence.

\textit{Case 2:} The sequence $\mathcal{C}$ is not a $\tau$-cycle sequence.

First, let us consider Case 1:

If $\ell=0$, then it is clear that $\ell\leq m$ and that the sequence
$\mathcal{C}^{\prime}$ is a permutation of a subsequence of $\mathcal{C}$.
Thus, in the following, we can WLOG assume that $\ell\neq0$. Thus, the
sequence $\mathcal{C}^{\prime}$ has at least one element, so that the element
$\mathcal{C}_{1}^{\prime}$ is well-defined.

Since $\mathcal{C}^{\prime}=\left(  \mathcal{C}_{1}^{\prime},\mathcal{C}%
_{2}^{\prime},...,\mathcal{C}_{\ell}^{\prime}\right)  $ is a $\tau$-cycle
sequence, we can apply \textbf{(*)} to $i=1$ and $\mathcal{D}=\mathcal{C}%
^{\prime}$. We conclude that $\mathcal{C}_{1}^{\prime}$ is a $\tau$-cycle. In
other words, $\mathcal{C}_{1}^{\prime}$ is a $\left(  \mathcal{C}%
_{0}\mathcal{C}_{0-1}...\mathcal{C}_{1}\tau\right)  $-cycle.

On the other hand, $\mathcal{C}_{1}^{\prime}$ is not a $\left(  \mathcal{C}%
_{m}\mathcal{C}_{m-1}...\mathcal{C}_{1}\tau\right)  $-cycle (since
$\mathcal{C}_{m}\mathcal{C}_{m-1}...\mathcal{C}_{1}\tau$ is acyclic, so there
is no $\left(  \mathcal{C}_{m}\mathcal{C}_{m-1}...\mathcal{C}_{1}\tau\right)
$-cycle). Thus, there exists an $i\in\left\{  0,1,...,m\right\}  $ such that
$\mathcal{C}_{1}^{\prime}$ is not a $\left(  \mathcal{C}_{i}\mathcal{C}%
_{i-1}...\mathcal{C}_{1}\tau\right)  $-cycle (namely, $i=m$ qualifies).
Consider the \textit{smallest} such $i$. Then, $\mathcal{C}_{1}^{\prime}$ is
not a $\left(  \mathcal{C}_{i}\mathcal{C}_{i-1}...\mathcal{C}_{1}\tau\right)
$-cycle, but $\mathcal{C}_{1}^{\prime}$ is a $\left(  \mathcal{C}%
_{j}\mathcal{C}_{j-1}...\mathcal{C}_{1}\tau\right)  $-cycle for every
nonnegative integer $j<i$. We have $i\neq0$ (since $\mathcal{C}_{1}^{\prime}$
is not a $\left(  \mathcal{C}_{i}\mathcal{C}_{i-1}...\mathcal{C}_{1}%
\tau\right)  $-cycle, but we know that $\mathcal{C}_{1}^{\prime}$ is a
$\left(  \mathcal{C}_{0}\mathcal{C}_{0-1}...\mathcal{C}_{1}\tau\right)
$-cycle). Thus, $i\geq1$, so that $i-1\geq0$. Thus, $\mathcal{C}_{1}^{\prime}$
is a $\left(  \mathcal{C}_{i-1}\mathcal{C}_{i-2}...\mathcal{C}_{1}\tau\right)
$-cycle (this is clear by substituting $j=i-1$ into the fact that
$\mathcal{C}_{1}^{\prime}$ is a $\left(  \mathcal{C}_{j}\mathcal{C}%
_{j-1}...\mathcal{C}_{1}\tau\right)  $-cycle for every nonnegative integer
$j<i$).

By \textbf{(*)} (applied to $\mathcal{D}=\mathcal{C}$), we know that
$\mathcal{C}_{i}$ is a $\left(  \mathcal{C}_{i-1}\mathcal{C}_{i-2}%
...\mathcal{C}_{1}\tau\right)  $-cycle.

If $\mathcal{C}_{1}^{\prime}\neq\mathcal{C}_{i}$, then $\mathcal{C}%
_{1}^{\prime}$ is a $\left(  \mathcal{C}_{i}\left(  \mathcal{C}_{i-1}%
\mathcal{C}_{i-2}...\mathcal{C}_{1}\tau\right)  \right)  $-cycle (by
\textbf{(8)}, applied to $\mathcal{D}=\mathcal{C}_{1}^{\prime}$,
$\mathcal{E}=\mathcal{C}_{i}$ and $\kappa=\mathcal{C}_{i-1}\mathcal{C}%
_{i-2}...\mathcal{C}_{1}\tau$), contradicting to the fact that $\mathcal{C}%
_{1}^{\prime}$ is not a $\left(  \mathcal{C}_{i}\mathcal{C}_{i-1}%
...\mathcal{C}_{1}\tau\right)  $-cycle (this is a contradiction because
$\mathcal{C}_{i}\left(  \mathcal{C}_{i-1}\mathcal{C}_{i-2}...\mathcal{C}%
_{1}\tau\right)  $ is the same as $\mathcal{C}_{i}\mathcal{C}_{i-1}%
...\mathcal{C}_{1}\tau$). Hence, we cannot have $\mathcal{C}_{1}^{\prime}%
\neq\mathcal{C}_{i}$. Thus, $\mathcal{C}_{1}^{\prime}=\mathcal{C}_{i}$.

Now we are going to prove that

\textbf{(13)} for every $j\in\left\{  0,1,...,i-1\right\}  $, we have
$\mathcal{C}_{1}^{\prime}\left(  \mathcal{C}_{j}\mathcal{C}_{j-1}%
...\mathcal{C}_{1}\tau\right)  =\mathcal{C}_{j}\mathcal{C}_{j-1}%
...\mathcal{C}_{1}\left(  \mathcal{C}_{1}^{\prime}\tau\right)  $.

\textit{Proof of \textbf{(13)}:} We will prove \textbf{(13)} by induction over
$j$. The \textit{induction base} (the case $j=0$) is trivially true (since it
boils down to $\mathcal{C}_{1}^{\prime}\tau=\mathcal{C}_{1}^{\prime}\tau$).

Now to the \textit{induction step}: Let $k\in\left\{  0,1,...,i-1\right\}  $
be such that \textbf{(13)} holds for $j=k-1$. Now we have to prove that
\textbf{(13)} holds for $j=k$.

Since \textbf{(13)} holds for $j=k-1$, we have $\mathcal{C}_{1}^{\prime
}\left(  \mathcal{C}_{k-1}\mathcal{C}_{k-2}...\mathcal{C}_{1}\tau\right)
=\mathcal{C}_{k-1}\mathcal{C}_{k-2}...\mathcal{C}_{1}\left(  \mathcal{C}%
_{1}^{\prime}\tau\right)  $.

Now, $\mathcal{C}_{1}^{\prime}$ is a $\left(  \mathcal{C}_{k-1}\mathcal{C}%
_{k-2}...\mathcal{C}_{1}\tau\right)  $-cycle (this follows from substituting
$j=k-1$ in the fact that $\mathcal{C}_{1}^{\prime}$ is a $\left(
\mathcal{C}_{j}\mathcal{C}_{j-1}...\mathcal{C}_{1}\tau\right)  $-cycle for
every nonnegative integer $j<i$), and $\mathcal{C}_{k}$ is a $\left(
\mathcal{C}_{k-1}\mathcal{C}_{k-2}...\mathcal{C}_{1}\tau\right)  $-cycle (by
\textbf{(*)}, since $\mathcal{C}$ is a $\tau$-cycle sequence). Thus,
\textbf{(12)} (applied to $\mathcal{C}_{k-1}\mathcal{C}_{k-2}...\mathcal{C}%
_{1}\tau$, $\mathcal{C}_{1}^{\prime}$ and $\mathcal{C}_{k}$ instead of
$\kappa$, $\mathcal{D}$ and $\mathcal{E}$) yields $\mathcal{C}_{1}^{\prime
}\left(  \mathcal{C}_{k}\left(  \mathcal{C}_{k-1}\mathcal{C}_{k-2}%
...\mathcal{C}_{1}\tau\right)  \right)  =\mathcal{C}_{k}\left(  \mathcal{C}%
_{1}^{\prime}\left(  \mathcal{C}_{k-1}\mathcal{C}_{k-2}...\mathcal{C}_{1}%
\tau\right)  \right)  $. Now,%
\begin{align*}
\mathcal{C}_{1}^{\prime}\left(  \underbrace{\mathcal{C}_{k}\mathcal{C}%
_{k-1}...\mathcal{C}_{1}\tau}_{=\mathcal{C}_{k}\left(  \mathcal{C}%
_{k-1}\mathcal{C}_{k-2}...\mathcal{C}_{1}\tau\right)  }\right)   &
=\mathcal{C}_{1}^{\prime}\left(  \mathcal{C}_{k}\left(  \mathcal{C}%
_{k-1}\mathcal{C}_{k-2}...\mathcal{C}_{1}\tau\right)  \right)  =\mathcal{C}%
_{k}\left(  \underbrace{\mathcal{C}_{1}^{\prime}\left(  \mathcal{C}%
_{k-1}\mathcal{C}_{k-2}...\mathcal{C}_{1}\tau\right)  }_{=\mathcal{C}%
_{k-1}\mathcal{C}_{k-2}...\mathcal{C}_{1}\left(  \mathcal{C}_{1}^{\prime}%
\tau\right)  }\right) \\
&  =\mathcal{C}_{k}\left(  \mathcal{C}_{k-1}\mathcal{C}_{k-2}...\mathcal{C}%
_{1}\left(  \mathcal{C}_{1}^{\prime}\tau\right)  \right)  =\mathcal{C}%
_{k}\mathcal{C}_{k-1}...\mathcal{C}_{1}\left(  \mathcal{C}_{1}^{\prime}%
\tau\right)  .
\end{align*}
In other words, \textbf{(13)} holds for $j=k$. This completes the induction
step. Thus, the induction proof of \textbf{(13)} is completed.

Applying \textbf{(13)} to $j=i-1$, we obtain $\mathcal{C}_{1}^{\prime}\left(
\mathcal{C}_{i-1}\mathcal{C}_{i-2}...\mathcal{C}_{1}\tau\right)
=\mathcal{C}_{i-1}\mathcal{C}_{i-2}...\mathcal{C}_{1}\left(  \mathcal{C}%
_{1}^{\prime}\tau\right)  $. Now,%
\begin{align*}
\mathcal{C}_{m}\mathcal{C}_{m-1}...\mathcal{C}_{1}\tau &  =\mathcal{C}%
_{m}\mathcal{C}_{m-1}...\mathcal{C}_{i+1}\left(  \underbrace{\mathcal{C}_{i}%
}_{=\mathcal{C}_{1}^{\prime}}\left(  \mathcal{C}_{i-1}\mathcal{C}%
_{i-2}...\mathcal{C}_{1}\tau\right)  \right)  =\mathcal{C}_{m}\mathcal{C}%
_{m-1}...\mathcal{C}_{i+1}\left(  \underbrace{\mathcal{C}_{1}^{\prime}\left(
\mathcal{C}_{i-1}\mathcal{C}_{i-2}...\mathcal{C}_{1}\tau\right)
}_{=\mathcal{C}_{i-1}\mathcal{C}_{i-2}...\mathcal{C}_{1}\left(  \mathcal{C}%
_{1}^{\prime}\tau\right)  }\right) \\
&  =\mathcal{C}_{m}\mathcal{C}_{m-1}...\mathcal{C}_{i+1}\left(  \mathcal{C}%
_{i-1}\mathcal{C}_{i-2}...\mathcal{C}_{1}\left(  \mathcal{C}_{1}^{\prime}%
\tau\right)  \right)  =\mathcal{C}_{m}\mathcal{C}_{m-1}...\mathcal{C}%
_{i+1}\mathcal{C}_{i-1}\mathcal{C}_{i-2}...\mathcal{C}_{1}\left(
\mathcal{C}_{1}^{\prime}\tau\right)  .
\end{align*}
Thus, the stack configuration $\mathcal{C}_{m}\mathcal{C}_{m-1}...\mathcal{C}%
_{i+1}\mathcal{C}_{i-1}\mathcal{C}_{i-2}...\mathcal{C}_{1}\left(
\mathcal{C}_{1}^{\prime}\tau\right)  $ is acyclic (since the stack
configuration $\mathcal{C}_{m}\mathcal{C}_{m-1}...\mathcal{C}_{1}\tau$ is
acyclic). Also, it is clear that $\left(  \mathcal{C}_{2}^{\prime}%
,\mathcal{C}_{3}^{\prime},...,\mathcal{C}_{\ell}^{\prime}\right)  $ is a
$\left(  \mathcal{C}_{1}^{\prime}\tau\right)  $-cycle sequence (since
$\mathcal{C}^{\prime}$ is a $\tau$-cycle sequence). Thus, Lemma 5.1b
\textbf{(a)} (applied to $\mathcal{C}_{1}^{\prime}\tau$, $m-1$, $\ell-1$,
$\left(  \mathcal{C}_{1},\mathcal{C}_{2},...,\mathcal{C}_{i-1},\mathcal{C}%
_{i+1},\mathcal{C}_{i+2},...,\mathcal{C}_{m}\right)  $ and $\left(
\mathcal{C}_{2}^{\prime},\mathcal{C}_{3}^{\prime},...,\mathcal{C}_{\ell
}^{\prime}\right)  $ instead of $\tau$, $m$, $\ell$, $\mathcal{C}$ and
$\mathcal{C}^{\prime}$) yields that\footnote{In fact, we \textit{are} allowed
to apply Lemma 5.1b \textbf{(a)} to $\mathcal{C}_{1}^{\prime}\tau$, $m-1$,
$\ell-1$, $\left(  \mathcal{C}_{1},\mathcal{C}_{2},...,\mathcal{C}%
_{i-1},\mathcal{C}_{i+1},\mathcal{C}_{i+2},...,\mathcal{C}_{m}\right)  $ and
$\left(  \mathcal{C}_{2}^{\prime},\mathcal{C}_{3}^{\prime},...,\mathcal{C}%
_{\ell}^{\prime}\right)  $ instead of $\tau$, $m$, $\ell$, $\mathcal{C}$ and
$\mathcal{C}^{\prime}$, because we have $m-1=\mu-1$ (since $m=\mu$) and
because we know (from our induction hypothesis) that Lemma 5.1b \textbf{(a)}
holds whenever $m=\mu-1$.} $\ell-1\leq m-1$, and moreover, that the sequence
$\left(  \mathcal{C}_{2}^{\prime},\mathcal{C}_{3}^{\prime},...,\mathcal{C}%
_{\ell}^{\prime}\right)  $ is a permutation of a subsequence of $\left(
\mathcal{C}_{1},\mathcal{C}_{2},...,\mathcal{C}_{i-1},\mathcal{C}%
_{i+1},\mathcal{C}_{i+2},...,\mathcal{C}_{m}\right)  $.

Since $\ell-1\leq m-1$, we obviously have $\ell\leq m$.

Now, for every sequence $\mathcal{X}$ and every $s\in\mathbb{N}$ such that the
element $\mathcal{X}_{s}$ exists, let us denote by $\mathcal{X}_{\diagdown s}$
the sequence that results if we remove the $s$-th element from the sequence
$\mathcal{X}$. In other words, for every sequence $\mathcal{X}$ and every
$s\in\mathbb{N}$ such that the element $\mathcal{X}_{s}$ exists, let us denote
by $\mathcal{X}_{\diagdown s}$ the sequence $\left(  \mathcal{X}%
_{1},\mathcal{X}_{2},...,\mathcal{X}_{s-1},\mathcal{X}_{s+1},\mathcal{X}%
_{s+2},...\right)  $\ \ \ \ \footnote{The notation $\left(  \mathcal{X}%
_{1},\mathcal{X}_{2},...,\mathcal{X}_{s-1},\mathcal{X}_{s+1},\mathcal{X}%
_{s+2},...\right)  $ does \textit{not} mean that this sequence is necessarily
infinite. (It might even end with $\mathcal{X}_{s-1}$, so that neither
$\mathcal{X}_{s+1}$ and $\mathcal{X}_{s+2}$ would be well-defined.) This
notation simply means that we don't want to specify whether this sequence is
infinite or finite.}. Then, clearly, $\left(  \mathcal{C}_{1},\mathcal{C}%
_{2},...,\mathcal{C}_{i-1},\mathcal{C}_{i+1},\mathcal{C}_{i+2},...,\mathcal{C}%
_{m}\right)  =\mathcal{C}_{\diagdown i}$ and $\left(  \mathcal{C}_{2}^{\prime
},\mathcal{C}_{3}^{\prime},...,\mathcal{C}_{\ell}^{\prime}\right)
=\mathcal{C}_{\diagdown1}^{\prime}$. Thus, the fact that the sequence $\left(
\mathcal{C}_{2}^{\prime},\mathcal{C}_{3}^{\prime},...,\mathcal{C}_{\ell
}^{\prime}\right)  $ is a permutation of a subsequence of $\left(
\mathcal{C}_{1},\mathcal{C}_{2},...,\mathcal{C}_{i-1},\mathcal{C}%
_{i+1},\mathcal{C}_{i+2},...,\mathcal{C}_{m}\right)  $ rewrites as follows:
The sequence $\mathcal{C}_{\diagdown1}^{\prime}$ is a permutation of a
subsequence of $\mathcal{C}_{\diagdown i}$.

Now, we need a trivial fact:

\textbf{(14)} if we have two finite sequences $\mathcal{X}$ and $\mathcal{Y}$
and two positive integers $\alpha$ and $\beta$ such that the elements
$\mathcal{X}_{\alpha}$ and $\mathcal{Y}_{\beta}$ exist and satisfy
$\mathcal{X}_{\alpha}=\mathcal{Y}_{\beta}$ and such that $\mathcal{X}%
_{\diagdown\alpha}$ is a permutation of a subsequence of $\mathcal{Y}%
_{\diagdown\beta}$, then $\mathcal{X}$ is a permutation of a subsequence of
$\mathcal{Y}$.

\textit{Proof of \textbf{(14)}:} Let $\mathcal{X}$ and $\mathcal{Y}$ be two
sequences and $\alpha$ and $\beta$ be two positive integers such that the
elements $\mathcal{X}_{\alpha}$ and $\mathcal{Y}_{\beta}$ exist and satisfy
$\mathcal{X}_{\alpha}=\mathcal{Y}_{\beta}$ and such that $\mathcal{X}%
_{\diagdown\alpha}$ is a permutation of a subsequence of $\mathcal{Y}%
_{\diagdown\beta}$.

Let $p$ be the length of the sequence $\mathcal{X}$, and $q$ be the length of
the sequence $\mathcal{Y}$.

Since $\mathcal{X}_{\diagdown\alpha}$ is a permutation of a subsequence of
$\mathcal{Y}_{\diagdown\beta}$, there exists an injective map $f:\left\{
1,2,...,p\right\}  \diagdown\left\{  \alpha\right\}  \rightarrow\left\{
1,2,...,q\right\}  \diagdown\left\{  \beta\right\}  $ such that every
$t\in\left\{  1,2,...,p\right\}  \diagdown\left\{  \alpha\right\}  $ satisfies
$\mathcal{X}_{t}=\mathcal{Y}_{f\left(  t\right)  }$%
\ \ \ \ \footnote{\textit{Proof.} The sequence $\mathcal{X}_{\diagdown\alpha}$
is a permutation of a subsequence of $\mathcal{Y}_{\diagdown\beta}$. In other
words, there exists a bijection $g:\left\{  1,2,...,p-1\right\}
\rightarrow\left\{  1,2,...,q-1\right\}  $ such that every $s\in\left\{
1,2,...,p-1\right\}  $ satisfies $\left(  \mathcal{X}_{\diagdown\alpha
}\right)  _{s}=\left(  \mathcal{Y}_{\diagdown\beta}\right)  _{g\left(
s\right)  }$. Consider such a $g$.
\par
Define a map $\pi:\left\{  1,2,...,p-1\right\}  \rightarrow\left\{
1,2,...,p\right\}  \diagdown\left\{  \alpha\right\}  $ by%
\[
\left(  \pi\left(  t\right)  =\left\{
\begin{array}
[c]{c}%
t,\ \ \ \ \ \ \ \ \ \ \text{if }t<\alpha;\\
t+1,\ \ \ \ \ \ \ \ \ \ \text{if }t\geq\alpha
\end{array}
\right.  \ \ \ \ \ \ \ \ \ \ \text{for every }t\in\left\{
1,2,...,p-1\right\}  \right)  .
\]
This map $\pi$ is known to be well-defined and bijective (in fact, $\pi$ is
the only monotonically increasing bijection $\left\{  1,2,...,p-1\right\}
\rightarrow\left\{  1,2,...,p\right\}  \diagdown\left\{  \alpha\right\}  $).
\par
Every $s\in\left\{  1,2,...,p-1\right\}  $ satisfies $\left(  \mathcal{X}%
_{\diagdown\alpha}\right)  _{s}=\left\{
\begin{array}
[c]{c}%
\mathcal{X}_{s},\ \ \ \ \ \ \ \ \ \ \text{if }s<\alpha;\\
\mathcal{X}_{s+1},\ \ \ \ \ \ \ \ \ \ \text{if }s\geq\alpha
\end{array}
\right.  $ (since $\mathcal{X}_{\diagdown\alpha}=\left(  \mathcal{X}%
_{1},\mathcal{X}_{2},...,\mathcal{X}_{\alpha-1},\mathcal{X}_{\alpha
+1},\mathcal{X}_{\alpha+2},...,\mathcal{X}_{p}\right)  $).
\par
Now we will show that every $t\in\left\{  1,2,...,p-1\right\}  $ satisfies
$\left(  \mathcal{X}_{\diagdown\alpha}\right)  _{t}=\mathcal{X}_{\pi\left(
t\right)  }$.
\par
\textit{Proof.} Let $t\in\left\{  1,2,...,p-1\right\}  $. The formula $\left(
\mathcal{X}_{\diagdown\alpha}\right)  _{s}=\left\{
\begin{array}
[c]{c}%
\mathcal{X}_{s},\ \ \ \ \ \ \ \ \ \ \text{if }s<\alpha;\\
\mathcal{X}_{s+1},\ \ \ \ \ \ \ \ \ \ \text{if }s\geq\alpha
\end{array}
\right.  $, applied to $s=t$, yields $\left(  \mathcal{X}_{\diagdown\alpha
}\right)  _{t}=\left\{
\begin{array}
[c]{c}%
\mathcal{X}_{t},\ \ \ \ \ \ \ \ \ \ \text{if }t<\alpha;\\
\mathcal{X}_{t+1},\ \ \ \ \ \ \ \ \ \ \text{if }t\geq\alpha
\end{array}
\right.  $. Now, we distinguish between two cases:
\par
\textit{Case 1:} We have $t<\alpha$.
\par
\textit{Case 2:} We have $t\geq\alpha$.
\par
First consider Case 1: In this case, $t<\alpha$ and $\pi\left(  t\right)
=\left\{
\begin{array}
[c]{c}%
t,\ \ \ \ \ \ \ \ \ \ \text{if }t<\alpha;\\
t+1,\ \ \ \ \ \ \ \ \ \ \text{if }t\geq\alpha
\end{array}
\right.  =t$ (since $t<\alpha$). But%
\begin{align*}
\left(  \mathcal{X}_{\diagdown\alpha}\right)  _{t}  &  =\left\{
\begin{array}
[c]{c}%
\mathcal{X}_{t},\ \ \ \ \ \ \ \ \ \ \text{if }t<\alpha;\\
\mathcal{X}_{t+1},\ \ \ \ \ \ \ \ \ \ \text{if }t\geq\alpha
\end{array}
\right.  =\mathcal{X}_{t}\ \ \ \ \ \ \ \ \ \ \left(  \text{since }%
t<\alpha\right) \\
&  =\mathcal{X}_{\pi\left(  t\right)  }\ \ \ \ \ \ \ \ \ \ \left(  \text{since
}t=\pi\left(  t\right)  \right)  .
\end{align*}
Thus,$\mathcal{\ }\left(  \mathcal{X}_{\diagdown\alpha}\right)  _{t}%
=\mathcal{X}_{\pi\left(  t\right)  }$ holds in Case 1.
\par
Next consider Case 2: In this case, $t\geq\alpha$ and $\pi\left(  t\right)
=\left\{
\begin{array}
[c]{c}%
t,\ \ \ \ \ \ \ \ \ \ \text{if }t<\alpha;\\
t+1,\ \ \ \ \ \ \ \ \ \ \text{if }t\geq\alpha
\end{array}
\right.  =t+1$ (since $t\geq\alpha$). But%
\begin{align*}
\left(  \mathcal{X}_{\diagdown\alpha}\right)  _{t}  &  =\left\{
\begin{array}
[c]{c}%
\mathcal{X}_{t},\ \ \ \ \ \ \ \ \ \ \text{if }t<\alpha;\\
\mathcal{X}_{t+1},\ \ \ \ \ \ \ \ \ \ \text{if }t\geq\alpha
\end{array}
\right.  =\mathcal{X}_{t+1}\ \ \ \ \ \ \ \ \ \ \left(  \text{since }%
t\geq\alpha\right) \\
&  =\mathcal{X}_{\pi\left(  t\right)  }\ \ \ \ \ \ \ \ \ \ \left(  \text{since
}t+1=\pi\left(  t\right)  \right)  .
\end{align*}
Thus,$\mathcal{\ }\left(  \mathcal{X}_{\diagdown\alpha}\right)  _{t}%
=\mathcal{X}_{\pi\left(  t\right)  }$ holds in Case 2.
\par
Hence, $\left(  \mathcal{X}_{\diagdown\alpha}\right)  _{t}=\mathcal{X}%
_{\pi\left(  t\right)  }$ has been proven in both Cases 1 and 2. Thus,
$\left(  \mathcal{X}_{\diagdown\alpha}\right)  _{t}=\mathcal{X}_{\pi\left(
t\right)  }$ always holds. This completes the proof that every $t\in\left\{
1,2,...,p-1\right\}  $ satisfies $\left(  \mathcal{X}_{\diagdown\alpha
}\right)  _{t}=\mathcal{X}_{\pi\left(  t\right)  }$.
\par
Define a map $\eta:\left\{  1,2,...,q-1\right\}  \rightarrow\left\{
1,2,...,q\right\}  \diagdown\left\{  \beta\right\}  $ by%
\[
\left(  \eta\left(  t\right)  =\left\{
\begin{array}
[c]{c}%
t,\ \ \ \ \ \ \ \ \ \ \text{if }t<\beta;\\
t+1,\ \ \ \ \ \ \ \ \ \ \text{if }t\geq\beta
\end{array}
\right.  \ \ \ \ \ \ \ \ \ \ \text{for every }t\in\left\{
1,2,...,q-1\right\}  \right)  .
\]
This map $\eta$ is known to be well-defined and bijective (in fact, $\eta$ is
the only monotonically increasing bijection $\left\{  1,2,...,q-1\right\}
\rightarrow\left\{  1,2,...,q\right\}  \diagdown\left\{  \beta\right\}  $).
\par
Above we have proved that every $t\in\left\{  1,2,...,p-1\right\}  $ satisfies
$\left(  \mathcal{X}_{\diagdown\alpha}\right)  _{t}=\mathcal{X}_{\pi\left(
t\right)  }$. If we repeat the argument that we used to prove this, but this
time with $p$, $\mathcal{X}$, $\alpha$ and $\pi$ replaced by $q$,
$\mathcal{Y}$, $\beta$ and $\eta$, then we conclude that every $t\in\left\{
1,2,...,q-1\right\}  $ satisfies $\left(  \mathcal{Y}_{\diagdown\beta}\right)
_{t}=\mathcal{Y}_{\eta\left(  t\right)  }$.
\par
Now, $\eta$ is a bijection and thus injective. Also, $\pi$ is a bijection, so
that the inverse map $\pi^{-1}$ exists and is a bijection as well. In
particular, $\pi^{-1}$ is injective. Define a map $f:\left\{
1,2,...,p\right\}  \diagdown\left\{  \alpha\right\}  \rightarrow\left\{
1,2,...,q\right\}  \diagdown\left\{  \beta\right\}  $ by $f=\eta\circ
g\circ\pi^{-1}$. Since $\eta$, $g$ and $\pi^{-1}$ are injective, the
composition $\eta\circ g\circ\pi^{-1}$ is injective; hence, $f=\eta\circ
g\circ\pi^{-1}$ is injective.
\par
Now we will show that every $t\in\left\{  1,2,...,p\right\}  \diagdown\left\{
\alpha\right\}  $ satisfies $\mathcal{X}_{t}=\mathcal{Y}_{f\left(  t\right)
}$.
\par
\textit{Proof.} Let $t\in\left\{  1,2,...,p\right\}  \diagdown\left\{
\alpha\right\}  $. Let $s=\pi^{-1}\left(  t\right)  $. Then, $t=\pi\left(
s\right)  $. But%
\begin{align*}
\left(  \mathcal{X}_{\diagdown\alpha}\right)  _{s}  &  =\left(  \mathcal{Y}%
_{\diagdown\beta}\right)  _{g\left(  s\right)  }=\mathcal{Y}_{\eta\left(
g\left(  s\right)  \right)  }\ \ \ \ \ \ \ \ \ \ \left(  \text{by the formula
}\left(  \mathcal{Y}_{\diagdown\beta}\right)  _{t}=\mathcal{Y}_{\eta\left(
t\right)  }\text{, applied to }g\left(  s\right)  \text{ instead of }t\right)
\\
&  =\mathcal{Y}_{f\left(  t\right)  }\ \ \ \ \ \ \ \ \ \ \left(  \text{since
}\eta\left(  g\left(  \underbrace{s}_{=\pi^{-1}\left(  t\right)  }\right)
\right)  =\eta\left(  g\left(  \pi^{-1}\left(  t\right)  \right)  \right)
=\underbrace{\left(  \eta\circ g\circ\pi^{-1}\right)  }_{=f}\left(  t\right)
=f\left(  t\right)  \right)
\end{align*}
Compared with%
\begin{align*}
\left(  \mathcal{X}_{\diagdown\alpha}\right)  _{s}  &  =\mathcal{X}%
_{\pi\left(  s\right)  }\ \ \ \ \ \ \ \ \ \ \left(  \text{by the formula
}\left(  \mathcal{X}_{\diagdown\alpha}\right)  _{t}=\mathcal{X}_{\pi\left(
t\right)  }\text{, applied to }s\text{ instead of }t\right) \\
&  =\mathcal{X}_{t}\ \ \ \ \ \ \ \ \ \ \left(  \text{since }\pi\left(
s\right)  =t\right)  ,
\end{align*}
this yields $\mathcal{X}_{t}=\mathcal{Y}_{f\left(  t\right)  }$. This
completes the proof that every $t\in\left\{  1,2,...,p\right\}  \diagdown
\left\{  \alpha\right\}  $ satisfies $\mathcal{X}_{t}=\mathcal{Y}_{f\left(
t\right)  }$.
\par
We have thus found an injective map $f:\left\{  1,2,...,p\right\}
\diagdown\left\{  \alpha\right\}  \rightarrow\left\{  1,2,...,q\right\}
\diagdown\left\{  \beta\right\}  $ such that every $t\in\left\{
1,2,...,p\right\}  \diagdown\left\{  \alpha\right\}  $ satisfies
$\mathcal{X}_{t}=\mathcal{Y}_{f\left(  t\right)  }$.}. Consider such an $f$.
Now, let $F$ be the map $\left\{  1,2,...,p\right\}  \rightarrow\left\{
1,2,...,q\right\}  $ given by%
\[
\left(  F\left(  t\right)  =\left\{
\begin{array}
[c]{c}%
f\left(  t\right)  ,\ \ \ \ \ \ \ \ \ \ \text{if }t\neq\alpha;\\
\beta,\ \ \ \ \ \ \ \ \ \ \text{if }t=\alpha
\end{array}
\right.  \ \ \ \ \ \ \ \ \ \ \text{for every }t\in\left\{  1,2,...,p\right\}
\right)  .
\]
Then, this map $F$ is still injective (since any two elements $t_{1}$ and
$t_{2}$ of $\left\{  1,2,...,p\right\}  $ such that $F\left(  t_{1}\right)
=F\left(  t_{2}\right)  $ satisfy $t_{1}=t_{2}$%
\ \ \ \ \footnote{\textit{Proof.} Let $t_{1}$ and $t_{2}$ be elements of
$\left\{  1,2,...,p\right\}  $ such that $F\left(  t_{1}\right)  =F\left(
t_{2}\right)  $.
\par
We will now show that $t_{1}=t_{2}$. To this end, we distinguish between four
cases:
\par
\textit{Case 1:} We have $t_{1}\neq\alpha$ and $t_{2}\neq\alpha$.
\par
\textit{Case 2:} We have $t_{1}=\alpha$ and $t_{2}\neq\alpha$.
\par
\textit{Case 3:} We have $t_{1}\neq\alpha$ and $t_{2}=\alpha$.
\par
\textit{Case 4:} We have $t_{1}=\alpha$ and $t_{2}=\alpha$.
\par
First, consider Case 1. In this case, the definition of $F\left(
t_{1}\right)  $ shows that $F\left(  t_{1}\right)  =\left\{
\begin{array}
[c]{c}%
f\left(  t_{1}\right)  ,\ \ \ \ \ \ \ \ \ \ \text{if }t\neq\alpha;\\
\beta,\ \ \ \ \ \ \ \ \ \ \text{if }t=\alpha
\end{array}
\right.  =f\left(  t_{1}\right)  $ (since $t_{1}\neq\alpha$) and similarly
$F\left(  t_{2}\right)  =f\left(  t_{2}\right)  $, so that $f\left(
t_{1}\right)  =F\left(  t_{1}\right)  =F\left(  t_{2}\right)  =f\left(
t_{2}\right)  $, and thus $t_{1}=t_{2}$ (since $f$ is injective).
\par
Now, consider Case 2: In this case, the definition of $F\left(  t_{1}\right)
$ shows that $F\left(  t_{1}\right)  =\left\{
\begin{array}
[c]{c}%
f\left(  t_{1}\right)  ,\ \ \ \ \ \ \ \ \ \ \text{if }t\neq\alpha;\\
\beta,\ \ \ \ \ \ \ \ \ \ \text{if }t=\alpha
\end{array}
\right.  =f\left(  t_{1}\right)  $ (since $t_{1}\neq\alpha$) , whereas the
definition of $F\left(  t_{2}\right)  $ shows that $F\left(  t_{2}\right)
=\left\{
\begin{array}
[c]{c}%
f\left(  t_{2}\right)  ,\ \ \ \ \ \ \ \ \ \ \text{if }t\neq\alpha;\\
\beta,\ \ \ \ \ \ \ \ \ \ \text{if }t=\alpha
\end{array}
\right.  =\beta$ (since $t_{2}=\alpha$), so that $\beta=F\left(  t_{2}\right)
=F\left(  t_{1}\right)  =f\left(  t_{1}\right)  \in\left\{  1,2,...,q\right\}
\diagdown\left\{  \beta\right\}  $, which is clearly a contradiction. Hence,
Case 2 is impossible.
\par
Similarly, we can see that Case 3 is impossible.
\par
Finally, it is clear that we have $t_{1}=t_{2}$ in Case 4 (because
$t_{1}=\alpha=t_{2}$ in Case 4).
\par
So we have proven that $t_{1}=t_{2}$ in each of the Cases 1 and 4. These two
cases cover all possibilities (since Cases 2 and 3 are impossible). Thus,
$t_{1}=t_{2}$ must always hold, qed.}), and every $t\in\left\{
1,2,...,p\right\}  $ satisfies $\mathcal{X}_{t}=\mathcal{Y}_{F\left(
t\right)  }$\ \ \ \ \footnote{\textit{Proof.} Let $t\in\left\{
1,2,...,p\right\}  $. We distinguish between two cases:
\par
\textit{Case 1:} We have $t\neq\alpha$.
\par
\textit{Case 2:} We have $t=\alpha$.
\par
First, consider Case 1. In this case, the definition of $F\left(  t\right)  $
shows that $F\left(  t\right)  =\left\{
\begin{array}
[c]{c}%
f\left(  t\right)  ,\ \ \ \ \ \ \ \ \ \ \text{if }t\neq\alpha;\\
\beta,\ \ \ \ \ \ \ \ \ \ \text{if }t=\alpha
\end{array}
\right.  =f\left(  t\right)  $ (since $t\neq\alpha$), so that $\mathcal{Y}%
_{F\left(  t\right)  }=\mathcal{Y}_{f\left(  t\right)  }$. Thus, in Case 1, we
have $\mathcal{X}_{t}=\mathcal{Y}_{f\left(  t\right)  }=\mathcal{Y}_{F\left(
t\right)  }$.
\par
Now let us consider Case 2. In this case, $\mathcal{X}_{t}=\mathcal{X}%
_{\alpha}$ (since $t=\alpha$), but the definition of $F\left(  t\right)  $
shows that $F\left(  t\right)  =\left\{
\begin{array}
[c]{c}%
f\left(  t\right)  ,\ \ \ \ \ \ \ \ \ \ \text{if }t\neq\alpha;\\
\beta,\ \ \ \ \ \ \ \ \ \ \text{if }t=\alpha
\end{array}
\right.  =\beta$ (since $t=\alpha$), and therefore $\mathcal{Y}_{F\left(
t\right)  }=\mathcal{Y}_{\beta}$. Hence, in Case 2, we have $\mathcal{X}%
_{t}=\mathcal{X}_{\alpha}=\mathcal{Y}_{\beta}=\mathcal{Y}_{F\left(  t\right)
}$.
\par
Thus, in each of the two cases, we have shown that $\mathcal{X}_{t}%
=\mathcal{Y}_{F\left(  t\right)  }$. Hence, $\mathcal{X}_{t}=\mathcal{Y}%
_{F\left(  t\right)  }$ always holds.}. So we have found an injective map
$F:\left\{  1,2,...,p\right\}  \rightarrow\left\{  1,2,...,q\right\}  $ such
that every $t\in\left\{  1,2,...,p\right\}  $ satisfies $\mathcal{X}%
_{t}=\mathcal{Y}_{F\left(  t\right)  }$. This shows that $\mathcal{X}$ is a
permutation of a subsequence of $\mathcal{Y}$. This proves \textbf{(14)}.

So let us continue with the proof of Lemma 5.1b \textbf{(a)} in Case 1: We
know that the elements $\mathcal{C}_{1}^{\prime}$ and $\mathcal{C}_{i}$ exist
and satisfy $\mathcal{C}_{1}^{\prime}=\mathcal{C}_{i}$, and we know that the
sequence $\mathcal{C}_{\diagdown1}^{\prime}$ is a permutation of a subsequence
of $\mathcal{C}_{\diagdown i}$. Hence, \textbf{(14)} (applied to
$\mathcal{C}^{\prime}$, $\mathcal{C}$, $1$ and $i$ instead of $\mathcal{X}$,
$\mathcal{Y}$, $\alpha$ and $\beta$) yields that $\mathcal{C}^{\prime}$ is a
permutation of a subsequence of $\mathcal{C}$.

Thus, in Case 1, we have shown that $\ell\leq m$ and that the sequence
$\mathcal{C}^{\prime}$ is a permutation of a subsequence of $\mathcal{C}$.

Now let us consider Case 2. In this case, the sequence $\mathcal{C}$ is not a
$\tau$-cycle sequence. In other words, there exists some positive integer $i$
for which the element $\mathcal{C}_{i}$ exists but for which this element
$\mathcal{C}_{i}$ is not a $\left(  \mathcal{C}_{i-1}\mathcal{C}%
_{i-2}...\mathcal{C}_{1}\tau\right)  $-cycle. Consider such an integer $i$.
Clearly, $i\in\left\{  1,2,...,m\right\}  $ (since the element $\mathcal{C}%
_{i}$ exists). Since $\mathcal{C}_{i}$ is not a $\left(  \mathcal{C}%
_{i-1}\mathcal{C}_{i-2}...\mathcal{C}_{1}\tau\right)  $-cycle, we have
$\mathcal{C}_{i}\left(  \mathcal{C}_{i-1}\mathcal{C}_{i-2}...\mathcal{C}%
_{1}\tau\right)  =\mathcal{C}_{i-1}\mathcal{C}_{i-2}...\mathcal{C}_{1}\tau$
(by the definition of $\mathcal{C}_{i}\left(  \mathcal{C}_{i-1}\mathcal{C}%
_{i-2}...\mathcal{C}_{1}\tau\right)  $).

Now let $\mathcal{D}$ be the sequence $\left(  \mathcal{C}_{1},\mathcal{C}%
_{2},...,\mathcal{C}_{i-1},\mathcal{C}_{i+1},\mathcal{C}_{i+2},...,\mathcal{C}%
_{m}\right)  $. Clearly, $\mathcal{D}$ is a subsequence of $\mathcal{C}$ and
has length $m-1$. Besides, $\mathcal{D}_{j}=\left\{
\begin{array}
[c]{c}%
\mathcal{C}_{j},\ \ \ \ \ \ \ \ \ \ \text{if }j<i;\\
\mathcal{C}_{j+1},\ \ \ \ \ \ \ \ \ \ \text{if }j\geq i
\end{array}
\right.  $ for every $j\in\left\{  1,2,...,m-1\right\}  $ (by the definition
of $\mathcal{D}$), so that%
\begin{align*}
\mathcal{D}_{m-1}\mathcal{D}_{m-2}...\mathcal{D}_{1}\tau &  =\mathcal{C}%
_{m}\mathcal{C}_{m-1}...\mathcal{C}_{i+1}\mathcal{C}_{i-1}\mathcal{C}%
_{i-2}...\mathcal{C}_{1}\tau\\
&  =\mathcal{C}_{m}\mathcal{C}_{m-1}...\mathcal{C}_{i+1}\left(
\underbrace{\mathcal{C}_{i-1}\mathcal{C}_{i-2}...\mathcal{C}_{1}\tau
}_{=\mathcal{C}_{i}\left(  \mathcal{C}_{i-1}\mathcal{C}_{i-2}...\mathcal{C}%
_{1}\tau\right)  =\mathcal{C}_{i}\mathcal{C}_{i-1}\mathcal{C}_{i-2}%
...\mathcal{C}_{1}\tau}\right) \\
&  =\mathcal{C}_{m}\mathcal{C}_{m-1}...\mathcal{C}_{i+1}\left(  \mathcal{C}%
_{i}\mathcal{C}_{i-1}\mathcal{C}_{i-2}...\mathcal{C}_{1}\tau\right)
=\mathcal{C}_{m}\mathcal{C}_{m-1}...\mathcal{C}_{1}\tau.
\end{align*}
Hence, $\mathcal{D}_{m-1}\mathcal{D}_{m-2}...\mathcal{D}_{1}\tau$ is an
acyclic stack configuration (since $\mathcal{C}_{m}\mathcal{C}_{m-1}%
...\mathcal{C}_{1}\tau$ is an acyclic stack configuration).

Thus, Lemma 5.1b \textbf{(a)} (applied to $m-1$ and $\mathcal{D}$ instead of
$m$ and $\mathcal{C}$) yields that\footnote{In fact, we \textit{are} allowed
to apply Lemma 5.1b \textbf{(a)} to $m-1$ and $\mathcal{D}$ instead of $m$ and
$\mathcal{C}$, because we have $m-1=\mu-1$ (since $m=\mu$) and because we know
(from our induction hypothesis) that Lemma 5.1b \textbf{(a)} holds whenever
$m=\mu-1$.} $\ell\leq m-1$, and moreover, that the sequence $\mathcal{C}%
^{\prime}$ is a permutation of a subsequence of $\mathcal{D}$.

So we know that the sequence $\mathcal{C}^{\prime}$ is a permutation of a
subsequence of $\mathcal{D}$. Since every subsequence of $\mathcal{D}$ is a
subsequence of $\mathcal{C}$ (because $\mathcal{D}$ itself is a subsequence of
$\mathcal{C}$), this shows that the sequence $\mathcal{C}$' is a permutation
of a subsequence of $\mathcal{C}$.

We also have $\ell\leq m-1\leq m$.

Thus, in Case 2, we have shown that $\ell\leq m$ and that the sequence
$\mathcal{C}^{\prime}$ is a permutation of a subsequence of $\mathcal{C}$.

Altogether, we have now shown \textit{in each of the Cases 1 and 2} that
$\ell\leq m$ and that the sequence $\mathcal{C}^{\prime}$ is a permutation of
a subsequence of $\mathcal{C}$. Therefore we conclude that, in every case,
$\ell\leq m$ and the sequence $\mathcal{C}^{\prime}$ is a permutation of a
subsequence of $\mathcal{C}$, whenever ) and $\mathcal{C}=\left(
\mathcal{C}_{1},\mathcal{C}_{2},...,\mathcal{C}_{m}\right)  $ and
$\mathcal{C}^{\prime}=\left(  \mathcal{C}_{1}^{\prime},\mathcal{C}_{2}%
^{\prime},...,\mathcal{C}_{\ell}^{\prime}\right)  $ are two finite sequences
of cycles of $G$ such that $m=\mu$ and such that the stack configuration
$\mathcal{C}_{m}\mathcal{C}_{m-1}...\mathcal{C}_{1}\tau$ is acyclic and
$\mathcal{C}^{\prime}$ is a $\tau$-cycle sequence. In other words, we have
proven that Lemma 5.1b \textbf{(a)} holds whenever $m=\mu$. This completes the
induction step.

Thus, Lemma 5.1b \textbf{(a)} is proven.

\textbf{(b)} Assume that both stack configurations $\mathcal{C}_{m}%
\mathcal{C}_{m-1}...\mathcal{C}_{1}\tau$ and $\mathcal{C}_{\ell}^{\prime
}\mathcal{C}_{\ell-1}^{\prime}...\mathcal{C}_{1}^{\prime}\tau$ are acyclic,
and that both sequences $\mathcal{C}$ and $\mathcal{C}^{\prime}$ are $\tau
$-cycle sequences. Lemma 5.1b \textbf{(a)} yields that $\ell\leq m$, and
moreover, that the sequence $\mathcal{C}^{\prime}$ is a permutation of a
subsequence of $\mathcal{C}$. Hence, there exists a subsequence $\mathcal{D}$
of $\mathcal{C}$ such that $\mathcal{C}^{\prime}$ is a permutation of
$\mathcal{D}$. Consider such a subsequence $\mathcal{D}$. Clearly, the
sequences $\mathcal{C}^{\prime}$ and $\mathcal{D}$ have the same length (since
$\mathcal{C}^{\prime}$ is a permutation of $\mathcal{D}$). Since the length of
$\mathcal{C}^{\prime}$ is $\ell$, this yields that the length of $\mathcal{D}$
must also be $\ell$.

Lemma 5.1b \textbf{(a)} (applied to $\mathcal{C}^{\prime}$, $\mathcal{C}$,
$\ell$ and $m$ instead of $\mathcal{C}$, $\mathcal{C}^{\prime}$, $m$ and
$\ell$) yields that $m\leq\ell$, and moreover, that the sequence $\mathcal{C}$
is a permutation of a subsequence of $\mathcal{C}^{\prime}$. Since $\ell\leq
m$ and $m\leq\ell$, we have $\ell=m$. Thus, the length of $\mathcal{D}$ is $m$
(since the length of $\mathcal{D}$ is $\ell$). Hence $\mathcal{D}$ is a
subsequence of $\mathcal{C}$ having length $m$. But since the only subsequence
of $\mathcal{C}$ having length $m$ is the sequence $\mathcal{C}$ itself
(because $\mathcal{C}$ itself has length $m$, and thus every subsequence of
$\mathcal{C}$ other than $\mathcal{C}$ itself must have length $<m$), this
yields that $\mathcal{D}$ is the sequence $\mathcal{C}$ itself. Since
$\mathcal{C}^{\prime}$ is a permutation of $\mathcal{D}$, we thus conclude
that $\mathcal{C}^{\prime}$ is a permutation of $\mathcal{C}$. Now, using
Lemma 5.1c (see below) we obtain $\mathcal{C}_{m}\mathcal{C}_{m-1}%
...\mathcal{C}_{1}\tau=\mathcal{C}_{\ell}^{\prime}\mathcal{C}_{\ell-1}%
^{\prime}...\mathcal{C}_{1}^{\prime}\tau$. This completes the proof of Lemma
5.1b \textbf{(b)}.

Now Lemma 5.1b is completely proven.

We owe a further lemma (which we used in the proof of Lemma 5.1b \textbf{(b)}):

\textbf{Lemma 5.1c.} Let $G$ be a digraph with a global sink. Let $\tau$ be a
stack configuration on $G$ (not necessarily infinitive).

Let $\mathcal{C}=\left(  \mathcal{C}_{1},\mathcal{C}_{2},...,\mathcal{C}%
_{m}\right)  $ and $\mathcal{C}^{\prime}=\left(  \mathcal{C}_{1}^{\prime
},\mathcal{C}_{2}^{\prime},...,\mathcal{C}_{\ell}^{\prime}\right)  $ be two
finite $\tau$-cycle sequences such that $\mathcal{C}$ is a permutation of
$\mathcal{C}^{\prime}$.

Then, $\mathcal{C}_{m}\mathcal{C}_{m-1}...\mathcal{C}_{1}\tau=\mathcal{C}%
_{\ell}^{\prime}\mathcal{C}_{\ell-1}^{\prime}...\mathcal{C}_{1}^{\prime}\tau$.

\textit{Proof of Lemma 5.1c.} We recall a general fact about cycle-popping
which we proved during our proof of Lemma 5.1a:

\textbf{(15)} If $\mathcal{D}$ is a $\tau$-cycle sequence and $I$ is a
positive integer for which the element $\mathcal{D}_{I}$ exists, then the
stack configuration $\mathcal{D}_{I}\mathcal{D}_{I-1}...\mathcal{D}_{1}\tau$
results from the stack configuration $\tau$ by reverse popping the stack at
each non-sink vertex $x$ of $G$ for a total of $k_{x}$ times, where $k_{x}$ is
the number of $i\in\left\{  1,2,...,I\right\}  $ such that the cycle
$\mathcal{D}_{i}$ contains the vertex $x$.

Now let us prove Lemma 5.1c: For every non-sink vertex $x$ of $G$, let $k_{x}$
be the number of $i\in\left\{  1,2,...,m\right\}  $ such that the cycle
$\mathcal{C}_{i}$ contains the vertex $x$. Then, \textbf{(15)} (applied to $m$
and $\mathcal{C}$ instead of $I$ and $\mathcal{D}$) yields that

\textbf{(16)} the stack configuration $\mathcal{C}_{m}\mathcal{C}%
_{m-1}...\mathcal{C}_{1}\tau$ results from the stack configuration $\tau$ by
reverse popping the stack at each non-sink vertex $x$ of $G$ for a total of
$k_{x}$ times.

On the other hand, we know that $\mathcal{C}$ is a permutation of
$\mathcal{C}^{\prime}$. In other words, there exists a bijection
$\beta:\left\{  1,2,...,m\right\}  \rightarrow\left\{  1,2,...,\ell\right\}  $
such that every $i\in\left\{  1,2,...,m\right\}  $ satisfies $\mathcal{C}%
_{i}=\mathcal{C}_{\beta\left(  i\right)  }^{\prime}$. Now, for every non-sink
vertex $x$ of $G$, we have%
\begin{align*}
k_{x}  &  =\left(  \text{the number of }i\in\left\{  1,2,...,m\right\}  \text{
such that the cycle }\mathcal{C}_{i}\text{ contains the vertex }x\right) \\
&  =\left(  \text{the number of }i\in\left\{  1,2,...,m\right\}  \text{ such
that the cycle }\mathcal{C}_{\beta\left(  i\right)  }^{\prime}\text{ contains
the vertex }x\right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{since }\mathcal{C}_{i}=\mathcal{C}%
_{\beta\left(  i\right)  }^{\prime}\right) \\
&  =\left(  \text{the number of }i\in\left\{  1,2,...,\ell\right\}  \text{
such that the cycle }\mathcal{C}_{i}^{\prime}\text{ contains the vertex
}x\right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{here, we substituted }i\text{ for }%
\beta\left(  i\right)  \text{, since }\beta:\left\{  1,2,...,m\right\}
\rightarrow\left\{  1,2,...,\ell\right\}  \text{ is a bijection}\right)  .
\end{align*}
In other words, for every non-sink vertex $x$ of $G$, the number $k_{x}$ is
the number of $i\in\left\{  1,2,...,\ell\right\}  $ such that the cycle
$\mathcal{C}_{i}^{\prime}$ contains the vertex $x$. Therefore, \textbf{(15)}
(applied to $\ell$ and $\mathcal{C}^{\prime}$ instead of $I$ and $\mathcal{D}%
$) yields that

\textbf{(17)} the stack configuration $\mathcal{C}_{\ell}^{\prime}%
\mathcal{C}_{\ell-1}^{\prime}...\mathcal{C}_{1}^{\prime}\tau$ results from the
stack configuration $\tau$ by reverse popping the stack at each non-sink
vertex $x$ of $G$ for a total of $k_{x}$ times.

Comparing \textbf{(16)} with \textbf{(17)}, we obtain that the stack
configuration $\mathcal{C}_{m}\mathcal{C}_{m-1}...\mathcal{C}_{1}\tau$ is the
same as the stack configuration $\mathcal{C}_{\ell}^{\prime}\mathcal{C}%
_{\ell-1}^{\prime}...\mathcal{C}_{1}^{\prime}\tau$. In other words,
$\mathcal{C}_{m}\mathcal{C}_{m-1}...\mathcal{C}_{1}\tau=\mathcal{C}_{\ell
}^{\prime}\mathcal{C}_{\ell-1}^{\prime}...\mathcal{C}_{1}^{\prime}\tau$.

Lemma 5.1c is thus proven. This fills the gap in the proof of Lemma 5.1b.

However, we are not done proving Theorem 5.1 yet. For that, we need a few more
lemmas - but very simple ones. First, a definition:

\textbf{Definition.} Let $G$ be a digraph with a global sink. Let $\tau$ be a
stack configuration on $G$ (not necessarily infinitive).

If $\mathcal{C}=\left(  \mathcal{C}_{1},\mathcal{C}_{2},...,\mathcal{C}%
_{m}\right)  $ is a $\tau$-cycle sequence such that the stack configuration
$\mathcal{C}_{m}\mathcal{C}_{m-1}...\mathcal{C}_{1}\tau$ is acyclic, then the
stack configuration $\mathcal{C}_{m}\mathcal{C}_{m-1}...\mathcal{C}_{1}\tau$
is said to be an \textit{acyclization} of $\tau$.

We will now show that every stack configuration $\tau$ has at most one
acyclization (even though it can often be obtained through different $\tau
$-cycle sequences $\mathcal{C}$). Later we will see that every infinitive
stack configuration $\tau$ has at least one acyclization. This will yield,
every infinitive stack configuration $\tau$ has exactly one acyclization. But
first things first:

The definition of an "acyclization" shows that:

\textbf{(18)} if $G$ be a digraph with a global sink, if $\tau$ is a stack
configuration on $G$, and if $\mathcal{C}=\left(  \mathcal{C}_{1}%
,\mathcal{C}_{2},...,\mathcal{C}_{m}\right)  $ is a $\tau$-cycle sequence such
that the stack configuration $\mathcal{C}_{m}\mathcal{C}_{m-1}...\mathcal{C}%
_{1}\tau$ is acyclic, then the stack configuration $\mathcal{C}_{m}%
\mathcal{C}_{m-1}...\mathcal{C}_{1}\tau$ is an acyclization of $\tau$.

And conversely, the definition of an "acyclization" shows that:

\textbf{(19)} if $G$ be a digraph with a global sink, if $\tau$ and
$\tau^{\prime}$ are two stack configurations on $G$ such that $\tau^{\prime}$
is an acyclization of $\tau$, then there exists a $\tau$-cycle sequence
$\mathcal{C}=\left(  \mathcal{C}_{1},\mathcal{C}_{2},...,\mathcal{C}%
_{m}\right)  $ such that the stack configuration $\mathcal{C}_{m}%
\mathcal{C}_{m-1}...\mathcal{C}_{1}\tau$ is acyclic and $\tau^{\prime
}=\mathcal{C}_{m}\mathcal{C}_{m-1}...\mathcal{C}_{1}\tau$.

Now to our lemmas:

\textbf{Lemma 5.1d.} Let $G$ be a digraph with a global sink. Let $\tau$ be a
stack configuration on $G$ (not necessarily infinitive). Then, any two
acyclizations of $\tau$ are equal.

\textit{Proof of Lemma 5.1d.} Let $\tau^{\prime}$ and $\tau^{\prime\prime}$ be
two acyclizations of $\tau$.

Since $\tau^{\prime}$ is an acyclization of $\tau$, there exists a $\tau
$-cycle sequence $\mathcal{C}=\left(  \mathcal{C}_{1},\mathcal{C}%
_{2},...,\mathcal{C}_{m}\right)  $ such that the stack configuration
$\mathcal{C}_{m}\mathcal{C}_{m-1}...\mathcal{C}_{1}\tau$ is acyclic and
$\tau^{\prime}=\mathcal{C}_{m}\mathcal{C}_{m-1}...\mathcal{C}_{1}\tau$ (due to
\textbf{(19)}). Consider this sequence $\mathcal{C}$.

Since $\tau^{\prime\prime}$ is an acyclization of $\tau$, there exists a
$\tau$-cycle sequence $\mathcal{C}^{\prime}=\left(  \mathcal{C}_{1}^{\prime
},\mathcal{C}_{2}^{\prime},...,\mathcal{C}_{\ell}^{\prime}\right)  $ such that
the stack configuration $\mathcal{C}_{\ell}^{\prime}\mathcal{C}_{\ell
-1}^{\prime}...\mathcal{C}_{1}^{\prime}\tau$ is acyclic and $\tau
^{\prime\prime}=\mathcal{C}_{\ell}^{\prime}\mathcal{C}_{\ell-1}^{\prime
}...\mathcal{C}_{1}^{\prime}\tau$ (due to \textbf{(19)}, with $\tau^{\prime}$,
$\mathcal{C}$ and $m$ replaced by $\tau^{\prime\prime}$, $\mathcal{C}^{\prime
}$ and $\ell$). Consider this sequence $\mathcal{C}^{\prime}$.

Now, Lemma 5.1b \textbf{(b)} yields $\mathcal{C}_{m}\mathcal{C}_{m-1}%
...\mathcal{C}_{1}\tau=\mathcal{C}_{\ell}^{\prime}\mathcal{C}_{\ell-1}%
^{\prime}...\mathcal{C}_{1}^{\prime}\tau$. Hence, $\tau^{\prime}%
=\mathcal{C}_{m}\mathcal{C}_{m-1}...\mathcal{C}_{1}\tau=\mathcal{C}_{\ell
}^{\prime}\mathcal{C}_{\ell-1}^{\prime}...\mathcal{C}_{1}^{\prime}\tau
=\tau^{\prime\prime}$.

We have thus proven that any two acyclizations $\tau^{\prime}$ and
$\tau^{\prime\prime}$ of $\tau$ satisfy $\tau^{\prime}=\tau^{\prime\prime}$.
In other words, any two acyclizations of $\tau$ are equal. This proves Lemma 5.1d.

Next we show that we don't need $\tau$-cycle sequences to obtain acyclizations:

\textbf{Lemma 5.1e.} Let $G$ be a digraph with a global sink. Let $\tau$ be a
stack configuration on $G$ (not necessarily infinitive). Let $\mathcal{C}%
=\left(  \mathcal{C}_{1},\mathcal{C}_{2},...,\mathcal{C}_{m}\right)  $ be a
sequence of cycles of $G$ such that the stack configuration $\mathcal{C}%
_{m}\mathcal{C}_{m-1}...\mathcal{C}_{1}\tau$ is acyclic. Then, the stack
configuration $\mathcal{C}_{m}\mathcal{C}_{m-1}...\mathcal{C}_{1}\tau$ is an
acyclization of $\tau$.

If you believe this lemma is trivial, you are right: The only "trick" in
proving Lemma 5.1e is to turn the sequence $\mathcal{C}=\left(  \mathcal{C}%
_{1},\mathcal{C}_{2},...,\mathcal{C}_{m}\right)  $ into a $\tau$-cycle
sequence by removing the $i$-th entries for all $i\in\left\{
1,2,...,m\right\}  $ for which $\mathcal{C}_{i}$ is not a $\left(
\mathcal{C}_{i-1}\mathcal{C}_{i-2}...\mathcal{C}_{1}\tau\right)  $-cycle.
These removals don't change the stack configuration $\mathcal{C}%
_{m}\mathcal{C}_{m-1}...\mathcal{C}_{1}\tau$. However, since this argument is
not so easy to formalize, here is a slightly different argument to prove Lemma 5.1e:

\textit{Proof of Lemma 5.1e.} We are going to prove Lemma 5.1e by induction
over $m$:

\textit{Induction base:} For $m=0$, Lemma 5.1e holds\footnote{In fact, assume
that $m=0$. Then, $\mathcal{C}=\left(  \mathcal{C}_{1},\mathcal{C}%
_{2},...,\mathcal{C}_{m}\right)  $ is the empty sequence, and thus a $\tau
$-cycle sequence (since the empty sequence is clearly a $\tau$-cycle
sequence). Hence, $\mathcal{C}=\left(  \mathcal{C}_{1},\mathcal{C}%
_{2},...,\mathcal{C}_{m}\right)  $ is a $\tau$-cycle sequence such that the
stack configuration $\mathcal{C}_{m}\mathcal{C}_{m-1}...\mathcal{C}_{1}\tau$
is acyclic. By \textbf{(18)}, this yields that $\mathcal{C}_{m}\mathcal{C}%
_{m-1}...\mathcal{C}_{1}\tau$ is an acyclization of $\tau$.
\par
Thus we have shown that $\mathcal{C}_{m}\mathcal{C}_{m-1}...\mathcal{C}%
_{1}\tau$ is an acyclization of $\tau$. In other words, Lemma 5.1e holds in
the case $m=0$.}. This completes the induction base.

\textit{Induction step:} Let $\mu$ be a positive integer. Assume that Lemma
5.1e holds whenever $m=\mu-1$. Now let us prove Lemma 5.1 whenever $m=\mu$.

Let $G$ be a digraph with a global sink. Let $\tau$ be a stack configuration
on $G$ (not necessarily infinitive). Let $\mathcal{C}=\left(  \mathcal{C}%
_{1},\mathcal{C}_{2},...,\mathcal{C}_{m}\right)  $ be a sequence of cycles of
$G$ such that the stack configuration $\mathcal{C}_{m}\mathcal{C}%
_{m-1}...\mathcal{C}_{1}\tau$ is acyclic and such that $m=\mu$. We are going
to show that the stack configuration $\mathcal{C}_{m}\mathcal{C}%
_{m-1}...\mathcal{C}_{1}\tau$ is an acyclization of $\tau$.

The stack configuration $\mathcal{C}_{m}\mathcal{C}_{m-1}...\mathcal{C}%
_{2}\left(  \mathcal{C}_{1}\tau\right)  =\mathcal{C}_{m}\mathcal{C}%
_{m-1}...\mathcal{C}_{1}\tau$ is acyclic. Hence, Lemma 5.1e (applied to $m-1$,
$\mathcal{C}_{1}\tau$ and $\left(  \mathcal{C}_{2},\mathcal{C}_{3}%
,...,\mathcal{C}_{m}\right)  $ instead of $m$, $\tau$ and $\mathcal{C}$)
yields that\footnote{In fact, we \textit{are} allowed to apply Lemma 5.1e to
$m-1$, $\mathcal{C}_{1}\tau$ and $\left(  \mathcal{C}_{2},\mathcal{C}%
_{3},...,\mathcal{C}_{m}\right)  $ instead of $m$, $\tau$ and $\mathcal{C}$,
because $m-1=\mu-1$ (since $m=\mu$) and because we assumed that Lemma 5.1
holds whenever $m=\mu-1$.} the stack configuration $\mathcal{C}_{m}%
\mathcal{C}_{m-1}...\mathcal{C}_{2}\left(  \mathcal{C}_{1}\tau\right)  $ is an
acyclization of $\mathcal{C}_{1}\tau$. By \textbf{(19)} (with $\tau$,
$\tau^{\prime}$, $\mathcal{C}$ and $m$ replaced by $\mathcal{C}_{1}\tau$,
$\mathcal{C}_{m}\mathcal{C}_{m-1}...\mathcal{C}_{2}\left(  \mathcal{C}_{1}%
\tau\right)  $, $\mathcal{D}$ and $k$), this yields that there exists a
$\left(  \mathcal{C}_{1}\tau\right)  $-cycle sequence $\mathcal{D}=\left(
\mathcal{D}_{1},\mathcal{D}_{2},...,\mathcal{D}_{k}\right)  $ such that the
stack configuration $\mathcal{D}_{k}\mathcal{D}_{k-1}...\mathcal{D}_{1}\left(
\mathcal{C}_{1}\tau\right)  $ is acyclic and satisfies $\mathcal{D}%
_{k}\mathcal{D}_{k-1}...\mathcal{D}_{1}\left(  \mathcal{C}_{1}\tau\right)
=\mathcal{C}_{m}\mathcal{C}_{m-1}...\mathcal{C}_{2}\left(  \mathcal{C}_{1}%
\tau\right)  $. Consider this sequence $\mathcal{D}=\left(  \mathcal{D}%
_{1},\mathcal{D}_{2},...,\mathcal{D}_{k}\right)  $.

We distinguish between two cases:

\textit{Case 1:} The cycle $\mathcal{C}_{1}$ is a $\tau$-cycle.

\textit{Case 2:} The cycle $\mathcal{C}_{1}$ is not a $\tau$-cycle.

Let us consider Case 1 first: In this case, we are going to show that $\left(
\mathcal{C}_{1},\mathcal{D}_{1},\mathcal{D}_{2},...,\mathcal{D}_{k}\right)  $
is a $\tau$-cycle sequence. In fact (according to the definition of a $\tau
$-cycle sequence), this will be proven once we can show the following two assertions:

- The cycle $\mathcal{C}_{1}$ is a $\tau$-cycle.

- For every $i\in\left\{  0,1,...,m\right\}  $, the cycle $\mathcal{D}_{i}$ is
a $\left(  \mathcal{D}_{i-1}\mathcal{D}_{i-2}...\mathcal{D}_{1}\mathcal{C}%
_{1}\tau\right)  $-cycle.

But the first of these two assertions is clearly satisfied (since we are in
Case 1), and the second of these two assertions is satisfied as
well\footnote{\textit{Proof.} For every $i\in\left\{  0,1,...,m\right\}  $,
the cycle $\mathcal{D}_{i}$ is a $\left(  \mathcal{D}_{i-1}\mathcal{D}%
_{i-2}...\mathcal{D}_{1}\left(  \mathcal{C}_{1}\tau\right)  \right)  $-cycle
(by \textbf{(*)} (applied to $\mathcal{C}_{1}\tau$ instead of $\tau$), since
$\mathcal{D}$ is a $\left(  \mathcal{C}_{1}\tau\right)  $-cycle sequence).
Since $\mathcal{D}_{i-1}\mathcal{D}_{i-2}...\mathcal{D}_{1}\left(
\mathcal{C}_{1}\tau\right)  =\mathcal{D}_{i-1}\mathcal{D}_{i-2}...\mathcal{D}%
_{1}\mathcal{C}_{1}\tau$, this rewrites as follows: For every $i\in\left\{
0,1,...,m\right\}  $, the cycle $\mathcal{D}_{i}$ is a $\left(  \mathcal{D}%
_{i-1}\mathcal{D}_{i-2}...\mathcal{D}_{1}\mathcal{C}_{1}\tau\right)  $-cycle.
In other words, the second assertion is indeed satisfied.}. Hence, both of
these assertions are shown. So we have proven that $\left(  \mathcal{C}%
_{1},\mathcal{D}_{1},\mathcal{D}_{2},...,\mathcal{D}_{k}\right)  $ is a $\tau
$-cycle sequence. Also, the stack configuration $\mathcal{D}_{k}%
\mathcal{D}_{k-1}...\mathcal{D}_{1}\mathcal{C}_{1}\tau=\mathcal{D}%
_{k}\mathcal{D}_{k-1}...\mathcal{D}_{1}\left(  \mathcal{C}_{1}\tau\right)  $
is acyclic. Hence, \textbf{(18)} (applied to $\left(  \mathcal{C}%
_{1},\mathcal{D}_{1},\mathcal{D}_{2},...,\mathcal{D}_{k}\right)  $ and $k+1$
instead of $\mathcal{C}$ and $m$) shows that the stack configuration
$\mathcal{D}_{k}\mathcal{D}_{k-1}...\mathcal{D}_{1}\mathcal{C}_{1}\tau$ is an
acyclization of $\tau$. Since%
\[
\mathcal{D}_{k}\mathcal{D}_{k-1}...\mathcal{D}_{1}\mathcal{C}_{1}%
\tau=\mathcal{D}_{k}\mathcal{D}_{k-1}...\mathcal{D}_{1}\left(  \mathcal{C}%
_{1}\tau\right)  =\mathcal{C}_{m}\mathcal{C}_{m-1}...\mathcal{C}_{2}\left(
\mathcal{C}_{1}\tau\right)  =\mathcal{C}_{m}\mathcal{C}_{m-1}...\mathcal{C}%
_{1}\tau,
\]
this yields that the stack configuration $\mathcal{C}_{m}\mathcal{C}%
_{m-1}...\mathcal{C}_{1}\tau$ is an acyclization of $\tau$.

Now, let us consider Case 2: In this case, we recall that the stack
configuration $\mathcal{C}_{m}\mathcal{C}_{m-1}...\mathcal{C}_{2}\left(
\mathcal{C}_{1}\tau\right)  $ is an acyclization of $\mathcal{C}_{1}\tau$.
Since $\mathcal{C}_{m}\mathcal{C}_{m-1}...\mathcal{C}_{2}\left(
\mathcal{C}_{1}\tau\right)  =\mathcal{C}_{m}\mathcal{C}_{m-1}...\mathcal{C}%
_{1}\tau$ and $\mathcal{C}_{1}\tau=\tau$ (since $\mathcal{C}_{1}$ is not a
$\tau$-cycle), this rewrites as follows: The stack configuration
$\mathcal{C}_{m}\mathcal{C}_{m-1}...\mathcal{C}_{1}\tau$ is an acyclization of
$\tau$.

Hence, in each of the two possible cases 1 and 2, we have proven that the
stack configuration $\mathcal{C}_{m}\mathcal{C}_{m-1}...\mathcal{C}_{1}\tau$
is an acyclization of $\tau$. Thus, it is proven that, under the conditions of
Lemma 5.1e, the stack configuration $\mathcal{C}_{m}\mathcal{C}_{m-1}%
...\mathcal{C}_{1}\tau$ is an acyclization of $\tau$ whenever $m=\mu$. In
other words, Lemma 5.1e is proven whenever $m=\mu$. This completes the
induction step. Hence, the induction proof of Lemma 5.1e is completed.

From Lemma 5.1e, we conclude:

\textbf{Lemma 5.1f.} Let $G$ be a digraph with a global sink. Let $\tau$ be a
stack configuration on $G$ (not necessarily infinitive).

Let $\mathcal{C}=\left(  \mathcal{C}_{1},\mathcal{C}_{2},...,\mathcal{C}%
_{m}\right)  $ and $\mathcal{C}^{\prime}=\left(  \mathcal{C}_{1}^{\prime
},\mathcal{C}_{2}^{\prime},...,\mathcal{C}_{\ell}^{\prime}\right)  $ be two
finite sequences of cycles of $G$ such that the stack configurations
$\mathcal{C}_{m}\mathcal{C}_{m-1}...\mathcal{C}_{1}\tau$ and $\mathcal{C}%
_{\ell}^{\prime}\mathcal{C}_{\ell-1}^{\prime}...\mathcal{C}_{1}^{\prime}\tau$
are acyclic. Then, $\mathcal{C}_{m}\mathcal{C}_{m-1}...\mathcal{C}_{1}%
\tau=\mathcal{C}_{\ell}^{\prime}\mathcal{C}_{\ell-1}^{\prime}...\mathcal{C}%
_{1}^{\prime}\tau$.

\textit{Proof of Lemma 5.1f.} Lemma 5.1e yields that the stack configuration
$\mathcal{C}_{m}\mathcal{C}_{m-1}...\mathcal{C}_{1}\tau$ is an acyclization of
$\tau$. But Lemma 5.1e (applied to $\mathcal{C}^{\prime}$ and $\ell$ instead
of $\mathcal{C}$ and $m$) yields that the stack configuration $\mathcal{C}%
_{\ell}^{\prime}\mathcal{C}_{\ell-1}^{\prime}...\mathcal{C}_{1}^{\prime}\tau$
is an acyclization of $\tau$. Hence, $\mathcal{C}_{m}\mathcal{C}%
_{m-1}...\mathcal{C}_{1}\tau$ and $\mathcal{C}_{\ell}^{\prime}\mathcal{C}%
_{\ell-1}^{\prime}...\mathcal{C}_{1}^{\prime}\tau$ are two acyclizations of
$\tau$. Since any two acyclizations of $\tau$ are equal (by Lemma 5.1d), we
can thus conclude that $\mathcal{C}_{m}\mathcal{C}_{m-1}...\mathcal{C}_{1}%
\tau=\mathcal{C}_{\ell}^{\prime}\mathcal{C}_{\ell-1}^{\prime}...\mathcal{C}%
_{1}^{\prime}\tau$. This proves Lemma 5.1f.

Theorem 5.1 is now clearly true, because the first assertion of Theorem 5.1
follows from Lemma 5.1a, while the second assertion of Theorem 5.1 follows
from Lemma 5.1f.


