hw5s.tex

\documentclass[numbers=enddot,12pt,final,onecolumn,notitlepage]{scrartcl}%
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[all,cmtip]{xy}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{comment}
\usepackage{color}
\usepackage{hyperref}
\usepackage{ifthen}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{needspace}
\usepackage{tabls}
\usepackage{epigraph}
\newcounter{exer}
\theoremstyle{definition}
\newtheorem{theo}{Theorem}[section]
\newenvironment{theorem}[1][]
{\begin{theo}[#1]\begin{leftbar}}
{\end{leftbar}\end{theo}}
\newtheorem{lem}[theo]{Lemma}
\newenvironment{lemma}[1][]
{\begin{lem}[#1]\begin{leftbar}}
{\end{leftbar}\end{lem}}
\newtheorem{prop}[theo]{Proposition}
\newenvironment{proposition}[1][]
{\begin{prop}[#1]\begin{leftbar}}
{\end{leftbar}\end{prop}}
\newtheorem{defi}[theo]{Definition}
\newenvironment{definition}[1][]
{\begin{defi}[#1]\begin{leftbar}}
{\end{leftbar}\end{defi}}
\newtheorem{remk}[theo]{Remark}
\newenvironment{remark}[1][]
{\begin{remk}[#1]\begin{leftbar}}
{\end{leftbar}\end{remk}}
\newtheorem{coro}[theo]{Corollary}
\newenvironment{corollary}[1][]
{\begin{coro}[#1]\begin{leftbar}}
{\end{leftbar}\end{coro}}
\newtheorem{conv}[theo]{Convention}
\newenvironment{condition}[1][]
{\begin{conv}[#1]\begin{leftbar}}
{\end{leftbar}\end{conv}}
\newtheorem{quest}[theo]{Question}
\newenvironment{algorithm}[1][]
{\begin{quest}[#1]\begin{leftbar}}
{\end{leftbar}\end{quest}}
\newtheorem{warn}[theo]{Warning}
\newenvironment{conclusion}[1][]
{\begin{warn}[#1]\begin{leftbar}}
{\end{leftbar}\end{warn}}
\newtheorem{conj}[theo]{Conjecture}
\newenvironment{conjecture}[1][]
{\begin{conj}[#1]\begin{leftbar}}
{\end{leftbar}\end{conj}}
\newtheorem{exam}[theo]{Example}
\newenvironment{example}[1][]
{\begin{exam}[#1]\begin{leftbar}}
{\end{leftbar}\end{exam}}
\newtheorem{exmp}[exer]{Exercise}
\newenvironment{exercise}[1][]
{\begin{exmp}[#1]\begin{leftbar}}
{\end{leftbar}\end{exmp}}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\let\cupnonlimits\bigcup
\let\capnonlimits\bigcap
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\renewcommand{\bigcup}{\cupnonlimits\limits}
\renewcommand{\bigcap}{\capnonlimits\limits}
\setlength\tablinesep{3pt}
\setlength\arraylinesep{3pt}
\setlength\extrarulesep{3pt}
\voffset=0cm
\hoffset=-0.7cm
\setlength\textheight{22.5cm}
\setlength\textwidth{15.5cm}
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\newcommand{\id}{\operatorname{id}}
\newcommand{\rev}{\operatorname{rev}}
\newcommand{\conncomp}{\operatorname{conncomp}}
\newcommand{\conn}{\operatorname{conn}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\powset}[2][]{\ifthenelse{\equal{#2}{}}{\mathcal{P}\left(#1\right)}{\mathcal{P}_{#1}\left(#2\right)}}
% $\powset[k]{S}$ stands for the set of all $k$-element subsets of
% $S$. The argument $k$ is optional, and if not provided, the result
% is the whole powerset of $S$.
\newcommand{\set}[1]{\left\{ #1 \right\}}
% $\set{...}$ yields $\left\{ ... \right\}$.
\newcommand{\abs}[1]{\left| #1 \right|}
% $\abs{...}$ yields $\left| ... \right|$.
\newcommand{\tup}[1]{\left( #1 \right)}
% $\tup{...}$ yields $\left( ... \right)$.
\newcommand{\ive}[1]{\left[ #1 \right]}
% $\ive{...}$ yields $\left[ ... \right]$.
\newcommand{\verts}[1]{\operatorname{V}\left( #1 \right)}
% $\verts{...}$ yields $\operatorname{V}\left( ... \right)$.
\newcommand{\edges}[1]{\operatorname{E}\left( #1 \right)}
% $\edges{...}$ yields $\operatorname{E}\left( ... \right)$.
\newcommand{\arcs}[1]{\operatorname{A}\left( #1 \right)}
% $\arcs{...}$ yields $\operatorname{A}\left( ... \right)$.
\newcommand{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
% $\underbrack{...1}{...2}$ yields
% $\underbrace{...1}_{\substack{...2}}$. This is useful for doing
% local rewriting transformations on mathematical expressions with
% justifications.
\newcommand{\are}{\ar@{-}}
% In an xymatrix environment, $\are$ gives an arrow without
% arrowhead. I use this to represent edges in graphs.
\newcommand{\arebi}[1][]{\ar@{<-}@/_/[#1] \ar@/^/[#1]}
% In an xymatrix environment, $\arebi$ gives two arrows with
% opposite direction. I use this to represent edges in
% bidirected digraphs.
\ihead{Math 5707 Spring 2017 (Darij Grinberg): homework set 5}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\begin{center}
\textbf{Math 5707 Spring 2017 (Darij Grinberg): homework set 5}

\textbf{Solution sketches.}

\textbf{extended and generalized version, with an introduction to sandpile theory (\today).}
\end{center}

\epigraph{This tale grew in the telling.}{J. R. R. Tolkien}

\tableofcontents

\subsection{Reminders}

See the
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17s/nogra.pdf}{lecture notes}
and also the
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17s/}{handwritten notes}
for relevant material.
See also
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17s/hw2s.pdf}{the solutions to homework set 2}
\cite{hw2s}
for various conventions and notations that are in use here.

\subsection{Sandpiles: the basic results}

Let me recall the definitions of the basic concepts on chip-firing
done in class.
Various sources on this material are
\cite{BjoLov92} (and, less directly, \cite{BjLoSh91}),
\cite{HLMPPW13}, \cite[Lectures 29--31]{Musike09} and \cite{CorPet16}.
(None of these is as readable as I would like to have it, but the
whole subject is about 30 years old, with most activity very
recent...
Also, be aware of incompatible notations, as well as of the fact that
some of the sources only consider undirected graphs.)
The particular case of the ``integer lattice'' graph has attracted
particular attention due to the mysterious pictures it generates;
see \url{http://www.math.cmu.edu/~wes/sand.html#next-page} for some
of these pictures, as well as
\url{http://www.math.cornell.edu/~levine/apollonian-slides.pdf} for a
talk with various illustrations.

Let me give a survey of the basics of the theory.
(Due to a reliance on constructive proofs, this survey is
unfortunately longer than I expected it to be.)

\subsubsection{Configurations, $\ZZ$-configurations and toppling}

We refer to \cite{hw2s} for the definition of a multidigraph, as well
as for the definitions of walks, paths, circuits and cycles in a
multidigraph.

If $v$ is a vertex of a multidigraph $\tup{V, A, \phi}$, then the
\textit{outdegree} $\deg^+ v$ of $v$ is defined to be the number
of all arcs $a \in A$ whose source is $v$.
Similarly,
if $v$ is a vertex of a multidigraph $\tup{V, A, \phi}$, then the
\textit{indegree} $\deg^- v$ of $v$ is defined to be the number
of all arcs $a \in A$ whose target is $v$.

An arc $a$ of a multidigraph is said to be a \textit{loop}
if the source of $a$ is the target of $a$.

Fix a multidigraph $D = \tup{V, A, \phi}$.

\begin{definition}
A \textit{configuration} (on $D$) means a map $f : V \to \NN$.
(Recall that $\NN = \set{0, 1, 2, \ldots}$.)

A configuration is also called a \textit{chip configuration} or
\textit{sandpile}.

We like to think of a configuration as a way to place
a finite number of game chips on the vertices of $D$:
Namely, the configuration $f$ corresponds to placing
$f \tup{v}$ chips on the vertex $v$ for each $v \in V$.
The chips are understood to be undistinguishable, so the
only thing that matters is how many of them are placed on
each given vertex.
Sometimes, we speak of grains of sand instead of chips.
\end{definition}

\begin{definition}
A \textit{$\ZZ$-configuration} (on $D$) means a map
$f : V \to \ZZ$.
We shall regard each configuration as a $\ZZ$-configuration
(since $\NN \subseteq \ZZ$).
\end{definition}

\begin{definition}
Let $f : V \to \ZZ$ be a $\ZZ$-configuration.

\textbf{(a)} A vertex $v \in V$ is said to be
\textit{active} in $f$ if and only if
$f\tup{v} \geq \deg^+ v$.
(Recall that $\deg^+ v$ is the outdegree of $v$.)

\textbf{(b)} The $\ZZ$-configuration $f$ is said to be
\textit{stable} if no vertex $v \in V$ is active in $f$.
\end{definition}

Thus, a $\ZZ$-configuration $f : V \to \ZZ$ is stable
if and only if each vertex $v \in V$ satisfies
$f \tup{v} < \deg^+ v$.

Notice that there are only finitely many stable configurations
(because if $f$ is a stable configuration, then, for each
$v \in V$, the stability of $f$ implies $f \tup{v} \leq \deg^+ v$,
whereas the fact that $f$ is a configuration implies
$f \tup{v} \geq 0$; but these two inequalities combined
leave only finitely many possible values for $f \tup{v}$).

\begin{definition} \label{def.chip.add-configs}
The set $\ZZ^V$ of all $\ZZ$-configurations can be equipped with
operations of addition and subtraction, defined as follows:

\begin{itemize}
 \item For any two $\ZZ$-configurations $f : V \to \ZZ$ and
       $g : V \to \ZZ$, we define a $\ZZ$-configuration
       $f + g : V \to \ZZ$ by setting
       \[
        \tup{f + g} \tup{v}
        = f \tup{v} + g \tup{v}
        \qquad \text{ for each } v \in V .
       \]

 \item For any two $\ZZ$-configurations $f : V \to \ZZ$ and
       $g : V \to \ZZ$, we define a $\ZZ$-configuration
       $f - g : V \to \ZZ$ by setting
       \[
        \tup{f - g} \tup{v}
        = f \tup{v} - g \tup{v}
        \qquad \text{ for each } v \in V .
       \]
\end{itemize}

These operations of addition and subtraction satisfy the
standard rules (e.g., we always have
$\tup{f+g} + h = f + \tup{g+h}$ and
$\tup{f-g} - h = f - \tup{g+h}$).
Hence, we can write terms like $f + g + h$ or $f - g - h$
without having to explicitly place parentheses.

Also, we can define a ``zero configuration'' $0 : V \to \ZZ$,
which is the configuration that sends each $v \in V$ to the
number $0$.
(Hopefully, the dual use of the symbol $0$ for both the number
$0$ and this zero configuration is not too confusing.)

Also, for each $\ZZ$-configuration $f : V \to \ZZ$ and each
integer $N$, we define a $\ZZ$-configuration $Nf : V \to \ZZ$
by
\[
\tup{Nf} \tup{v} = N f \tup{v}
\qquad \text{ for each } v \in V .
\]
\end{definition}

\begin{definition}
Let $f : V \to \ZZ$ be any $\ZZ$-configuration.
Then, $\sum f$ shall denote the integer
$\sum_{v \in V} f \tup{v}$.

This integer $\sum f$ is called the \textit{degree} of $f$.
\end{definition}

If $f$ is a configuration, then $\sum f$ is the total
number of chips in $f$.

It is easy to see that any two $\ZZ$-configurations $f$ and
$g$ satisfy $\sum \tup{f+g} = \sum f + \sum g$ and
$\sum \tup{f-g} = \sum f - \sum g$.
Also, any $N \in \ZZ$ and any $\ZZ$-configuration $f$
satisfy $\sum \tup{Nf} = N \sum f$.

\begin{proposition} \label{prop.chip.sum-greater}
Let $f$ be a configuration.
Let $h = \sum f$ and $w \in V$.
Then, $f \tup{w} \leq h$.
\end{proposition}

\begin{proof}[Proof of Proposition~\ref{prop.chip.sum-greater} (sketched).]
We have $h = \sum f = \sum_{v \in V} f \tup{v}$;
this is a sum of nonnegative integers (since $f$ is a
configuration).
But a sum of nonnegative integers is always $\geq$ to
each of its addends.
Hence, $\sum_{v \in V} f \tup{v} \geq f \tup{w}$.
Thus, $h = \sum_{v \in V} f \tup{v} \geq f \tup{w}$.
This proves Proposition~\ref{prop.chip.sum-greater}.
\end{proof}

\begin{definition}
\label{def.iverson}
We shall use the \textit{Iverson bracket notation}:
If $\mathcal{A}$ is any logical statement, then we define
an integer $\ive{ \mathcal{A} } \in \set{0, 1}$ by
\[
\ive{ \mathcal{A} } =
\begin{cases}
1, & \text{if }\mathcal{A}\text{ is true};\\
0, & \text{if }\mathcal{A}\text{ is false}
\end{cases}
.
\]
For example, $\ive{1+1=2} =1$ (since $1+1=2$ is true), whereas
$\ive{1+1=1} =0$ (since $1+1=1$ is false).
\end{definition}

\begin{definition}
If $v$ and $w$ are any two vertices of $D$, then
$a_{v, w}$ shall denote the number of all arcs of $D$ having
source $v$ and target $w$.
This is a nonnegative integer.
\end{definition}
(Note that $a_{v, w}$ might be $> 1$, since $D$ is a multidigraph.
Note also that $a_{v, v}$ might be nonzero, since loops are
allowed.)

\begin{definition}
Let $v \in V$ be a vertex.
Then, a $\ZZ$-configuration $\Delta v$ is defined by setting
\[
 \tup{\Delta v} \tup{w}
 = \ive{w = v} \deg^+ v - a_{v, w}
  \qquad \text{ for all } w \in V .
\]
\end{definition}

Let us unpack the definition of $\Delta v$ we just gave:
It says that
\[
\tup{\Delta v} \tup{w} = - a_{v, w}
\qquad \text{ for each vertex } w \in V \text{ distinct from } v
\]
(because if $w$ is distinct
from $v$, then $\ive{w = v} = 0$);
and it says that
\[
\tup{\Delta v} \tup{v} = \deg^+ v - a_{v, v} .
\]

\begin{definition}
Let $v \in V$ be a vertex.
Then, \textit{firing $v$} is the operation on
$\ZZ$-configurations (i.e., formally speaking, the mapping from
$\ZZ^V$ to $\ZZ^V$) that sends each $\ZZ$-configuration
$f : V \to \ZZ$ to $f - \Delta v$.

We sometimes say ``toppling $v$'' instead of ``firing $v$''.
\end{definition}

If $f : V \to \NN$ is a configuration, then the
$\ZZ$-configuration $f - \Delta v$ obtained by firing $v$ can be
described as follows:
The vertex $v$ ``donates'' $\deg^+ v$ of its chips to its
neighbors, by sending one chip along each of its outgoing arcs
(i.e., for each arc having source $v$, the vertex $v$ sends one
chip along this arc to the target of this arc).
Thus, the number of chips on $v$ (weakly) decreases, while the
number of chips on each other vertex (weakly) increases.
Of course, the resulting $\ZZ$-configuration $f - \Delta v$ is
not necessarily a configuration.
In fact, it is a configuration if the vertex $v$ is
active in $f$,
and also in some other cases:

\begin{proposition} \label{prop.chip.fire-conf}
Let $f : V \to \NN$ be a configuration.
Let $v \in V$.

\textbf{(a)} If the vertex $v$ is active in $f$, then
$f - \Delta v$ is a configuration.

\textbf{(b)} If $f - \Delta v$ is a configuration, and if
$D$ has no loops with source and target $v$, then
the vertex $v$ is active in $f$.
\end{proposition}

Note that the converse of
Proposition~\ref{prop.chip.fire-conf} \textbf{(a)} does not
hold when $D$ has loops with source and target $v$.

\begin{proof}[Proof of Proposition~\ref{prop.chip.fire-conf} (sketched).]
\textbf{(a)} Assume that the vertex $v$ is active in $f$.
Thus, $f \tup{v} \geq \deg^+ v$.
Hence,
\[
\tup{f - \Delta v} \tup{v}
= \underbrace{\tup{ f \tup{v} }}_{\geq \deg^+ v}
  - \underbrace{\tup{ \tup{\Delta v} \tup{v} }}_{= \deg^+ v - a_{v, v} }
\geq \deg^+ v - \tup{\deg^+ v - a_{v, v}} = a_{v, v} \geq 0 .
\]
Also, each vertex $w \in V$ distinct from $v$ satisfies
\[
\tup{f - \Delta v} \tup{w}
= f \tup{w}
  - \underbrace{\tup{ \tup{\Delta v} \tup{w} }}_{= - a_{v, w} \leq 0 }
\geq f \tup{w} \geq 0
\]
(since $f$ is a configuration).
Combining these two inequalities, we conclude that
$\tup{f - \Delta v} \tup{w} \geq 0$
for each $w \in V$.
In other words, $f - \Delta v$ is a configuration.
This proves Proposition~\ref{prop.chip.fire-conf} \textbf{(a)}.

\textbf{(b)} Assume that $f - \Delta v$ is a configuration.
Also, assume that $D$ has no loops with source and target $v$.
Thus, $a_{v, v} = 0$.
Now, $\tup{f - \Delta v} \tup{v} \geq 0$ (since
$f - \Delta v$ is a configuration), so that
\begin{align*}
0 &\leq \tup{f - \Delta v} \tup{v}
= f \tup{v}
  - \underbrace{\tup{ \tup{\Delta v} \tup{v} }}_{= \deg^+ v - a_{v, v} }
= f \tup{v} - \tup{\deg^+ v - a_{v, v}} \\
&= f \tup{v} - \deg^+ v + \underbrace{a_{v, v}}_{= 0}
= f \tup{v} - \deg^+ v .
\end{align*}
In other words, $f \tup{v} \geq \deg^+ v$. In other words,
the vertex $v$ is active in $f$.
This proves Proposition~\ref{prop.chip.fire-conf} \textbf{(b)}.
\end{proof}

\begin{proposition} \label{prop.chip.sumDv=0}
We have $\sum \tup{\Delta v} = 0$ for each vertex $v \in V$.
\end{proposition}

\begin{proof}[Proof of Proposition~\ref{prop.chip.sumDv=0} (sketched).]
Let $v\in V$ be any vertex. Then,
\begin{align*}
\sum\left(  \Delta v\right)    & =\sum_{w\in V}\underbrace{\left(  \Delta
v\right)  \left(  w\right)  }_{=\left[  w=v\right]  \deg^{+}v-a_{v,w}}%
=\sum_{w\in V}\left(  \left[  w=v\right]  \deg^{+}v-a_{v,w}\right)  \\
& =\underbrace{\sum_{w\in V}\left[  w=v\right]  }_{=1}\deg^{+}%
v-\underbrace{\sum_{w\in V}a_{v,w}}_{\substack{=\left(  \text{the number of
all arcs with source }v\right)  \\=\deg^{+}v}}\\
& =\deg^{+}v-\deg^{+}v=0.
\end{align*}
This proves Proposition~\ref{prop.chip.sumDv=0}.
\end{proof}

Thus,
\[
\sum \tup{f - \Delta v}
= \sum f - \underbrack{\sum \tup{\Delta v}}{= 0 \\ \text{(by Proposition~\ref{prop.chip.sumDv=0})}}
= \sum f
\]
for each $\ZZ$-configuration $f : V \to \ZZ$ and each vertex $v$.
In other words, firing a vertex $v$ does not change the degree of
a $\ZZ$-configuration.

\subsubsection{Legal and stabilizing sequences}

The word ``sequence'' shall always mean ``finite sequence''
(which is the same as ``finite list'' or ``tuple'').

We shall now study the effects of repeatedly firing vertices
of $D$ (that is, firing several vertices one after the other).
If $v_1, v_2, \ldots, v_k$ are finitely many elements of $V$,
and if $f : V \to \ZZ$ is any $\ZZ$-configuration,
then firing the vertices $v_1, v_2, \ldots, v_k$
(one after the other, in this order) results in the
$\ZZ$-configuration
$f - \Delta v_1 - \Delta v_2 - \cdots - \Delta v_k$.
This shows, in particular, that the order in which we fire
the vertices does not matter for the final result
(i.e., firing them in any other order would yield the same
resulting $\ZZ$-configuration);
however, the intermediate configurations of course do depend
on the order.

\begin{definition}
Let $f : V \to \ZZ$ be a $\ZZ$-configuration.

Let $\tup{v_1, v_2, \ldots, v_k}$ be a sequence of vertices of
$D$.

\textbf{(a)} The sequence $\tup{v_1, v_2, \ldots, v_k}$ is said
to be \textit{legal} for $f$ if for each
$i \in \set{1, 2, \ldots, k}$, the vertex $v_i$ is active in
the $\ZZ$-configuration
$f - \Delta v_1 - \Delta v_2 - \cdots - \Delta v_{i-1}$.

\textbf{(b)} The sequence $\tup{v_1, v_2, \ldots, v_k}$ is said
to be \textit{stabilizing} for $f$ if the $\ZZ$-configuration
$f - \Delta v_1 - \Delta v_2 - \cdots - \Delta v_k$ is stable.
\end{definition}

What is the rationale behind the notions of ``legal'' and
``stabilizing''?
A sequence of vertices provides a way to modify a
$\ZZ$-configuration by first firing the first vertex in the
sequence, then firing the second, and so on.
The sequence is said to be \textit{legal} (for $f$) if only
active vertices are being fired in this process
(i.e., each vertex that gets fired is active at the time of
its firing);
thus, in particular, if $f$ was a configuration, then
it remains a configuration throughout this process
(i.e., at no point does a vertex have a negative number of
chips)\footnote{This follows from
Proposition~\ref{prop.chip.fire-conf} \textbf{(a)}
(applied repeatedly).
\par
If our multidigraph $D$ has no loops, then
the converse is also true:
If the configuration remains a configuration throughout the
process, then the sequence is legal.
(This follows from
Proposition~\ref{prop.chip.fire-conf} \textbf{(b)}.)
But if $D$ has loops, this is not always the case.}.
The sequence is said to be \textit{stabilizing} (for $f$) if
the $\ZZ$-configuration resulting from it at the very end is
stable.

We notice some obvious consequences of the definitions:

\begin{proposition} \label{prop.chip.obvious}
Let $f$ be a $\ZZ$-configuration.

\textbf{(a)}
 If $f$ is a configuration, and if
       a sequence $\tup{v_1, v_2, \ldots, v_k}$ is legal
       for $f$, then all of the
       $\ZZ$-configurations
       $f - \Delta v_1 - \Delta v_2 - \cdots - \Delta v_i$
       for $i \in \set{0, 1, \ldots, k}$ are actually
       configurations.

\textbf{(b)}
 If a sequence $\tup{v_1, v_2, \ldots, v_k}$ is legal
       for $f$, then each prefix of this
       sequence (i.e., each sequence of the form
       $\tup{v_1, v_2, \ldots, v_i}$ for some
       $i \in \set{0, 1, \ldots, k}$) is legal for $f$ as
       well.

\textbf{(c)}
  If a sequence $\tup{v_1, v_2, \ldots, v_k}$ is
       stabilizing for $f$, then each
       permutation of this sequence (i.e., each sequence of
       the form
       $\tup{v_{\sigma\tup{1}}, v_{\sigma\tup{2}}, \ldots,
             v_{\sigma\tup{k}}}$ for a permutation
       $\sigma$ of $\set{1, 2, \ldots, k}$) is stabilizing
       for $f$ as well.

\textbf{(d)}
  If $\tup{v_1, v_2, \ldots, v_k}$ is a legal sequence
       for $f$, then
       $\tup{v_1, v_2, \ldots, v_k}$ is stabilizing if and
       only if there exist no $v \in V$ such that the
       sequence $\tup{v_1, v_2, \ldots, v_k, v}$ is legal.
\end{proposition}

An important property of chip-firing is the following result
(sometimes called the ``least action principle''):

\begin{theorem} \label{thm.chip.lap}
Let $f : V \to \ZZ$ be any $\ZZ$-configuration.
Let $\ell$ and $s$ be two sequences of vertices of $D$ such
that $\ell$ is legal for $f$ while $s$ is stabilizing for $f$.
Then, $\ell$ is a subpermutation of $s$.
\end{theorem}

Here, we are using the following notation:

\begin{definition}
Let $\tup{p_1, p_2, \ldots, p_u}$ and
$\tup{q_1, q_2, \ldots, q_v}$ be two finite sequences.
Then, we say that $\tup{p_1, p_2, \ldots, p_u}$ is
a \textit{subpermutation} of $\tup{q_1, q_2, \ldots, q_v}$
if and only if, for each object $t$, the following holds:
The number of $i \in \set{1, 2, \ldots, u}$ satisfying
$p_i = t$ is less or equal to the number of
$j \in \set{1, 2, \ldots, v}$ satisfying $q_j = t$.

Equivalently, the sequence $\tup{p_1, p_2, \ldots, p_u}$ is
a subpermutation of the sequence $\tup{q_1, q_2, \ldots, q_v}$
if and only if you can obtain the former from the latter by
removing some entries and permuting the remaining entries.
(``Some'' allows for the possibility of ``zero''.)
\end{definition}

Our proof of Theorem \ref{thm.chip.lap} relies on the following
simple facts about subpermutations (whose proofs are left
to the reader):

\begin{lemma} \label{lem.subper.simple-stuff}
\textbf{(a)} Any permutation of a finite sequence $s$ is a
subpermutation of $s$.

\textbf{(b)} If three finite sequences $a$, $b$ and $c$ have
the property that $a$ is a subpermutation of $b$, and that
$b$ is a subpermutation of $c$, then
$a$ is a subpermutation of $c$.

\textbf{(c)} If $\tup{a_1, a_2, \ldots, a_N}$
and $\tup{b_1, b_2, \ldots, b_M}$ are two finite sequences
such that $N > 0$ and $M > 0$ and $a_1 = b_1$,
and if the sequence $\tup{a_2, a_3, \ldots, a_N}$ is a
subpermutation of $\tup{b_2, b_3, \ldots, b_M}$, then
the sequence $\tup{a_1, a_2, \ldots, a_N}$ is a
subpermutation of $\tup{b_1, b_2, \ldots, b_M}$.

\textbf{(d)} If two finite sequences $a$ and $b$ are such
that $a$ is a subpermutation of $b$ and $b$ is a subpermutation
of $a$, then $a$ is a permutation of $b$.

\textbf{(e)} Any subpermutation of a finite sequence $s$ is
at most as long as $s$.
\end{lemma}

\begin{proof}[Proof of Theorem \ref{thm.chip.lap} (sketched).]
We shall prove Theorem \ref{thm.chip.lap} by induction on the length of $\ell$.

\textit{Induction base:} Theorem \ref{thm.chip.lap} is obvious when the length
of $\ell$ is $0$.

\textit{Induction step:} Fix a positive integer $N$. Assume (as the induction
hypothesis) that Theorem \ref{thm.chip.lap} is true when the sequence $\ell$
has length $N-1$. We must prove that Theorem \ref{thm.chip.lap} is true when
the sequence $\ell$ has length $N$.

So let $f$, $\ell$ and $s$ be as in Theorem \ref{thm.chip.lap}, and assume
that $\ell$ has length $N$. We must then prove that $\ell$ is a subpermutation
of $s$.

Write the sequence $s$ in the form $s=\left(  s_{1},s_{2},\ldots,s_{M}\right)
$.

Write the sequence $\ell$ in the form $\ell=\left(  \ell_{1},\ell_{2}%
,\ldots,\ell_{N}\right)  $ (this is possible, since $\ell$ has length $N$).
The entry $\ell_{1}$ exists (since $N$ is positive). Clearly, the vertex
$\ell_{1}$ is active in $f$ (because $\ell_{1}$ is the first entry of a
sequence that is legal for $f$). In other words, $f\left(  \ell_{1}\right)
\geq\deg^{+}\left(  \ell_{1}\right)  $.

Now, we claim that $\ell_{1}\in\left\{  s_{1},s_{2},\ldots,s_{M}\right\}  $.
Indeed, assume the contrary. Thus, $\ell_{1}\notin\left\{  s_{1},s_{2}%
,\ldots,s_{M}\right\}  $. In other words, $\ell_{1}\neq s_{i}$ for each
$i\in\left\{  1,2,\ldots,M\right\}  $. Hence, for each $i\in\left\{
1,2,\ldots,M\right\}  $, the definition of $\Delta s_{i}$ yields
\begin{equation}
\left(  \Delta s_{i}\right)  \left(  \ell_{1}\right)  =\underbrace{\left[
\ell_{1}=s_{i}\right]  }_{\substack{=0\\\text{(since }\ell_{1}\neq
s_{i}\text{)}}}\deg^{+}\left(  s_{i}\right)  -\underbrace{a_{s_{i},\ell_{1}}%
}_{\geq0}\leq0.\label{pf.thm.chip.lap.4}%
\end{equation}
But the sequence $\left(  s_{1},s_{2},\ldots,s_{M}\right)  =s$ is stabilizing;
in other words, the $\ZZ$-configuration $f-\Delta s_{1}-\Delta
s_{2}-\cdots-\Delta s_{M}$ is stable. Thus, in particular,
\[
\left(  f-\Delta s_{1}-\Delta s_{2}-\cdots-\Delta s_{M}\right)  \left(
\ell_{1}\right)  <\deg^{+}\left(  \ell_{1}\right)  \leq f\left(  \ell
_{1}\right)
\]
(since $f\left(  \ell_{1}\right)  \geq\deg^{+}\left(  \ell_{1}\right)  $).
Hence,%
\[
f\left(  \ell_{1}\right)  >\left(  f-\Delta s_{1}-\Delta s_{2}-\cdots-\Delta
s_{M}\right)  \left(  \ell_{1}\right)  =f\left(  \ell_{1}\right)  -\sum
_{i=1}^{M}\underbrace{\left(  \Delta s_{i}\right)  \left(  \ell_{1}\right)
}_{\substack{\leq0\\\text{(by (\ref{pf.thm.chip.lap.4}))}}}\geq f\left(
\ell_{1}\right)  ,
\]
which is absurd. This contradiction completes our proof of $\ell_{1}%
\in\left\{  s_{1},s_{2},\ldots,s_{M}\right\}  $.

In other words, $\ell_{1}$ is an entry of the sequence $s$. Thus, there exists
a permutation $t$ of the sequence $s$ such that $\ell_{1}$ is the
\textbf{first} entry of $t$. Consider such a $t$. Write $t$ in the form
$t=\left(  t_{1},t_{2},\ldots,t_{M}\right)  $. (This is possible, since $t$
has length $M$, being a permutation of the length-$M$ sequence $s$.)

We know that $\ell_{1}$ is the first entry of the sequence $t=\left(
t_{1},t_{2},\ldots,t_{M}\right)  $. In other words, $\ell_{1}=t_{1}$. In
particular, $M>0$.

Recall that $\left(  t_{1},t_{2},\ldots,t_{M}\right)  =t$ is a permutation of
the sequence $\left(  s_{1},s_{2},\ldots,s_{M}\right)  =s$. Thus, $f-\Delta
t_{1}-\Delta t_{2}-\cdots-\Delta t_{M}=f-\Delta s_{1}-\Delta s_{2}%
-\cdots-\Delta s_{M}$.

We have
\begin{align*}
& \left(  f-\Delta\underbrace{\ell_{1}}_{=t_{1}}\right)  -\Delta t_{2}-\Delta
t_{3}-\cdots-\Delta t_{M}\\
& =\left(  f-\Delta t_{1}\right)  -\Delta t_{2}-\Delta t_{3}-\cdots-\Delta
t_{M}\\
& =f-\Delta t_{1}-\Delta t_{2}-\cdots-\Delta t_{M}=f-\Delta s_{1}-\Delta
s_{2}-\cdots-\Delta s_{M}.
\end{align*}
Hence, the $\ZZ$-configuration $\left(  f-\Delta\ell_{1}\right)
-\Delta t_{2}-\Delta t_{3}-\cdots-\Delta t_{M}$ is stable (since the
$\ZZ$-configuration $f-\Delta s_{1}-\Delta s_{2}-\cdots-\Delta s_{M}$
is stable). In other words, the sequence $\left(  t_{2},t_{3},\ldots
,t_{M}\right)  $ is stabilizing for the $\ZZ$-configuration
$f-\Delta\ell_{1}$.

On the other hand, the sequence $\left(  \ell_{1},\ell_{2},\ldots,\ell
_{N}\right)  =\ell$ is legal for $f$. Hence, for each $i\in\left\{
2,3,\ldots,N\right\}  $, the vertex $\ell_{i}$ is active in the $\ZZ%
$-configuration $f-\Delta\ell_{1}-\Delta\ell_{2}-\cdots-\Delta\ell_{i-1}$. In
other words, for each $i\in\left\{  2,3,\ldots,N\right\}  $, the vertex
$\ell_{i}$ is active in the $\ZZ$-configuration $\left(  f-\Delta
\ell_{1}\right)  -\Delta\ell_{2}-\Delta\ell_{3}-\cdots-\Delta\ell_{i-1}$
(since
$f-\Delta\ell_{1}-\Delta\ell_{2}-\cdots-\Delta\ell_{i-1}
= \left(  f-\Delta
\ell_{1}\right)  -\Delta\ell_{2}-\Delta\ell_{3}-\cdots-\Delta\ell_{i-1}$).
Renaming $i$ as $i+1$ in this fact, we obtain the following: For each
$i\in\left\{  1,2,\ldots,N-1\right\}  $, the vertex $\ell_{i+1}$ is active in
the $\ZZ$-configuration $\left(  f-\Delta\ell_{1}\right)  -\Delta
\ell_{2}-\Delta\ell_{3}-\cdots-\Delta\ell_{i}$. In other words, the sequence
$\left(  \ell_{2},\ell_{3},\ldots,\ell_{N}\right)  $ is legal for the
$\ZZ$-configuration $f-\Delta\ell_{1}$. Moreover, this sequence has
length $N-1<N$.

Hence, by the induction hypothesis, we can apply Theorem \ref{thm.chip.lap} to
$f-\Delta\ell_{1}$, $\left(  \ell_{2},\ell_{3},\ldots,\ell_{N}\right)  $ and
$\left(  t_{2},t_{3},\ldots,t_{M}\right)  $ instead of $f$, $\ell$ and $t$. We
thus conclude that the sequence $\left(  \ell_{2},\ell_{3},\ldots,\ell
_{N}\right)  $ is a subpermutation of $\left(  t_{2},t_{3},\ldots
,t_{M}\right)  $. Hence, Lemma \ref{lem.subper.simple-stuff} \textbf{(c)}
(applied to $a_{i}=\ell_{i}$ and $b_{j}=t_{j}$) shows that the sequence
$\left(  \ell_{1},\ell_{2},\ldots,\ell_{N}\right)  $ is a subpermutation of
$\left(  t_{1},t_{2},\ldots,t_{M}\right)  $ (since $N>0$ and $M>0$ and
$\ell_{1}=t_{1}$). In other words, the sequence $\ell$ is a subpermutation of
$t$ (since $\ell=\left(  \ell_{1},\ell_{2},\ldots,\ell_{N}\right)  $ and
$t=\left(  t_{1},t_{2},\ldots,t_{M}\right)  $).

But the sequence $t$ is a permutation of $s$, and thus a subpermutation of $s$
(by Lemma \ref{lem.subper.simple-stuff} \textbf{(a)}). Hence, Lemma
\ref{lem.subper.simple-stuff} \textbf{(b)} (applied to $a=\ell$, $b=t$ and
$c=s$) shows that the sequence $\ell$ is a subpermutation of $s$. This
completes the induction step. Thus, Theorem \ref{thm.chip.lap} is proven.
\end{proof}

\begin{corollary} \label{cor.chip.lap-cor}
Let $f : V \to \NN$ be any configuration.
Let $\ell$ and $\ell'$ be two sequences of vertices of $D$
that are both legal and stabilizing for $f$.
Then:

\textbf{(a)} The sequence $\ell'$ is a permutation of $\ell$.

In particular:

\textbf{(b)} The sequences $\ell$ and $\ell'$ have the
same length.

\textbf{(c)} For each $t \in V$, the number of times $t$
appears in $\ell'$ equals the number of times $t$ appears in
$\ell$.

\textbf{(d)} The configuration obtained from $f$ by firing
all vertices in $\ell$ (one after the other) equals the
configuration obtained from $f$ by firing
all vertices in $\ell'$ (one after the other).
\end{corollary}

\begin{proof}[Proof of Corollary~\ref{cor.chip.lap-cor} (sketched).]
Theorem \ref{thm.chip.lap} (applied to $\ell^{\prime}$ instead of $s$) shows
that $\ell$ is a subpermutation of $\ell^{\prime}$. But Theorem
\ref{thm.chip.lap} (applied to $\ell^{\prime}$ and $\ell$ instead of $\ell$
and $s$) shows that $\ell^{\prime}$ is a subpermutation of $\ell$. Hence,
Lemma \ref{lem.subper.simple-stuff} \textbf{(d)} (applied to $a=\ell^{\prime}$
and $b=\ell$) shows that $\ell^{\prime}$ is a permutation of $\ell$. This
proves part \textbf{(a)} of Corollary~\ref{cor.chip.lap-cor}. Parts
\textbf{(b)} and \textbf{(c)} follow immediately from part \textbf{(a)}. Part
\textbf{(d)} also follows from part \textbf{(a)}, because we know that the
order in which we fire a sequence of vertices does not matter for the final
result (so any permutation of a sequence yields the same configuration as the
sequence itself).
\end{proof}

\subsubsection{Concatenation of legal sequences}

For the next lemma, we need a simple piece of notation:

\begin{definition} \label{def.concat}
\textbf{(a)} If $u=\left(  u_{1},u_{2},\ldots,u_{p}\right)  $ and $v=\left(
v_{1},v_{2},\ldots,v_{q}\right)  $ are two finite sequences, then $u\ast v$
denote the sequence $\left(  u_{1},u_{2},\ldots,u_{p},v_{1},v_{2},\ldots
,v_{q}\right)  $. This sequence $u\ast v$ is called the \textit{concatenation}
of the sequences $u$ and $v$.

\textbf{(b)} If $u$ is a finite sequence, and if $k\in\mathbb{N}$, then
$u^{\ast k}$ denotes the sequence $\underbrace{u\ast u\ast\cdots\ast
u}_{k\text{ times}}$. (This is well-defined, since the operation of
concatenation is associative. Notice that $u^{\ast0}$ is the empty sequence
$\left(  {}\right)  $.)
\end{definition}

\begin{lemma}
\label{lem.chip.leg-concat1}
Let $f : V \to \ZZ$ be a $\ZZ$-configuration.
Let $u$ be a legal sequence for $f$.
Let $g$ be the $\ZZ$-configuration obtained from $f$
by firing all vertices in $u$
(that is, $g=f-\Delta u_{1}-\Delta u_{2}-\cdots-\Delta u_{p}$, where $u$ is
written in the form $u=\left(  u_{1},u_{2},\ldots,u_{p}\right)  $).
Let $v$ be a legal sequence for $g$.
Then, $u\ast v$ is a legal sequence for $f$.
\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.chip.leg-concat1} (sketched).] Write the sequence $u$
in the form $u=\left(  u_{1},u_{2},\ldots,u_{p}\right)  $. Write the sequence
$v$ in the form $v=\left(  v_{1},v_{2},\ldots,v_{q}\right)  $. Then, the
definition of $u\ast v$ yields  $u\ast v=\left(  u_{1},u_{2},\ldots
,u_{p},v_{1},v_{2},\ldots,v_{q}\right)  $.

We want to prove that the sequence $u\ast v$ is legal for $f$. In other words,
we want to prove that the sequence $\left(  u_{1},u_{2},\ldots,u_{p}%
,v_{1},v_{2},\ldots,v_{q}\right)  $ is legal for $f$ (since $u\ast v=\left(
u_{1},u_{2},\ldots,u_{p},v_{1},v_{2},\ldots,v_{q}\right)  $). In other words,
we want to prove that if we start with the $\mathbb{Z}$-configuration $f$, and
fire the vertices $u_{1},u_{2},\ldots,u_{p},v_{1},v_{2},\ldots,v_{q}$ one by
one (from first to last), then each vertex we fire is active at the time of firing.

This process can be subdivided into two phases: The phase where we fire the
first $p$ vertices $u_{1},u_{2},\ldots,u_{p}$ will be called \textit{phase
}$1$. It is followed by a phase where we fire the next $q$ vertices, which are
$v_{1},v_{2},\ldots,v_{q}$; this latter phase will be called \textit{phase
}$2$.

We must prove that each vertex we fire in our process is active at the time of
firing. We call this the \textit{activity claim}. This claim is obvious for
the first $p$ vertices being fired (because these are the vertices
$u_{1},u_{2},\ldots,u_{p}$, and we already know that the sequence $\left(
u_{1},u_{2},\ldots,u_{p}\right)  =u$ is legal for $f$); in other words, the
activity claim is obvious for the vertices fired in phase $1$. It thus remains
to prove the activity claim for the vertices fired in phase $2$.

In phase $1$, the $\mathbb{Z}$-configuration $f$ is transformed by firing all
vertices in $u$ (because the vertices $u_{1},u_{2},\ldots,u_{p}$ are precisely
the vertices in $u$). Thus, the $\mathbb{Z}$-configuration obtained at the end
of phase $1$ is $g$ (because $g$ is \textbf{defined} as the $\mathbb{Z}%
$-configuration obtained from $f$ by firing all vertices in $u$). In phase
$2$, this $\mathbb{Z}$-configuration $g$ is transformed further by firing the
vertices $v_{1},v_{2},\ldots,v_{q}$. Since the sequence $\left(  v_{1}%
,v_{2},\ldots,v_{q}\right)  $ is legal for $g$, we thus conclude that these
vertices are active at the time of firing (in phase $2$). Hence, the activity
claim for the vertices fired in phase $2$ is proven. As we have explained,
this completes our proof of Lemma \ref{lem.chip.leg-concat1}.
\end{proof}

\begin{lemma}
\label{lem.chip.leg-concat2}Let $f:V\rightarrow\mathbb{Z}$ be a $\mathbb{Z}%
$-configuration. Let $u=\left(  u_{1},u_{2},\ldots,u_{p}\right)  $ be a legal
sequence for $f$ such that $\Delta u_{1}+\Delta u_{2}+\cdots+\Delta u_{p}=0$.
Let $k\in\mathbb{N}$. Then, the sequence $u^{\ast k}$ is legal for $f$.
\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.chip.leg-concat2} (sketched).] We want to prove that%
\begin{equation}
\text{the sequence }u^{\ast k}\text{ is legal for }%
f.\label{pf.lem.chip.leg-concat2.goal}%
\end{equation}
We shall prove this by induction over $k$:

\textit{Induction base:} The sequence $u^{\ast0}=\left(  {}\right)  $ (the
empty sequence) is clearly legal for $f$. In other words,
(\ref{pf.lem.chip.leg-concat2.goal}) holds for $k=0$. This completes the
induction base.

\textit{Induction step:} Let $K\in\mathbb{N}$. Assume that
(\ref{pf.lem.chip.leg-concat2.goal}) holds for $k=K$. We must prove that
(\ref{pf.lem.chip.leg-concat2.goal}) holds for $k=K+1$.

We have assumed that (\ref{pf.lem.chip.leg-concat2.goal}) holds for $k=K$. In
other words, the sequence $u^{\ast K}$ is legal for $f$.

Let $g$ be the $\mathbb{Z}$-configuration obtained from $f$ by firing all
vertices in $u$. Thus,
\[
g=f-\Delta u_{1}-\Delta u_{2}-\cdots-\Delta u_{p}=f-\underbrace{\left(  \Delta
u_{1}+\Delta u_{2}+\cdots+\Delta u_{p}\right)  }_{=0}=f.
\]
Hence, the sequence $u^{\ast K}$ is legal for $g$ (since the sequence $u^{\ast
K}$ is legal for $f$). Thus, Lemma \ref{lem.chip.leg-concat1} (applied to
$v=u^{\ast K}$) shows that the sequence $u\ast u^{\ast K}$ is legal for $f$.
In other words, the sequence $u^{\ast\left(  K+1\right)  }$ is legal for $f$
(since $u^{\ast\left(  K+1\right)  }=u\ast u^{\ast K}$). In other words,
(\ref{pf.lem.chip.leg-concat2.goal}) holds for $k=K+1$. This completes the
induction step.

Thus, (\ref{pf.lem.chip.leg-concat2.goal}) is proven. This proves Lemma
\ref{lem.chip.leg-concat2}.
\end{proof}

\begin{lemma} \label{lem.chip.leg-repeat}
Let $f : V \to \ZZ$ be a $\ZZ$-configuration.
Let $\ell=\left(  \ell_{1},\ell_{2},\ldots,\ell_{k}\right)  $
be a legal sequence for $f$.
Let $i$ and $j$ be two elements of $\set{0, 1, \ldots, k}$ such that
$i < j$ and
\begin{equation}
f-\Delta\ell_{1}-\Delta\ell_{2}-\cdots-\Delta\ell_{i}=f-\Delta\ell_{1}%
-\Delta\ell_{2}-\cdots-\Delta\ell_{j}.\label{eq.lem.chip.leg-repeat.cond}%
\end{equation}
Then:

\textbf{(a)} For every $r\in\mathbb{N}$, the sequence $\left(  \ell_{1}%
,\ell_{2},\ldots,\ell_{i}\right)  \ast\left(  \ell_{i+1},\ell_{i+2}%
,\ldots,\ell_{j}\right)  ^{\ast r}$ is legal for $f$. (This is the sequence
which begins with $\ell_{1},\ell_{2},\ldots,\ell_{i}$ and then goes on
repeating the $j-i$ elements $\ell_{i+1},\ell_{i+2},\ldots,\ell_{j}$ for a
total of $r$ times.)

\textbf{(b)} There exist legal sequences (for $f$) of arbitrary length.
\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.chip.leg-repeat} (sketched).] If we subtract
$f-\Delta\ell_{1}-\Delta\ell_{2}-\cdots-\Delta\ell_{i}$ from both sides of
(\ref{eq.lem.chip.leg-repeat.cond}), we obtain%
\[
0=-\Delta\ell_{i+1}-\Delta\ell_{i+2}-\cdots-\Delta\ell_{j}.
\]
Thus,%
\begin{equation}
\Delta\ell_{i+1}+\Delta\ell_{i+2}+\cdots+\Delta\ell_{j}%
=0.\label{pf.lem.chip.leg-repeat.zerosum}%
\end{equation}


\textbf{(a)} Let $r\in\mathbb{N}$. The sequence $\left(  \ell_{1},\ell
_{2},\ldots,\ell_{k}\right)  $ is legal for $f$. Thus, its prefix $\left(
\ell_{1},\ell_{2},\ldots,\ell_{i}\right)  $ is also legal for $f$.

Let $g$ be the $\mathbb{Z}$-configuration obtained from $f$ by firing all
vertices in $\left(  \ell_{1},\ell_{2},\ldots,\ell_{i}\right)  $. Thus,
$g=f-\Delta\ell_{1}-\Delta\ell_{2}-\cdots-\Delta\ell_{i}$. Then, the sequence
$\left(  \ell_{i+1},\ell_{i+2},\ldots,\ell_{j}\right)  $ is legal for
$g$\ \ \ \ \footnote{\textit{Proof.} We need to show that for each
$p\in\left\{  1,2,\ldots,j-i\right\}  $, the vertex $\ell_{i+p}$ is active in
the $\mathbb{Z}$-configuration $g-\Delta\ell_{i+1}-\Delta\ell_{i+2}%
-\cdots-\Delta\ell_{i+p-1}$.
\par
So let $p\in\left\{  1,2,\ldots,j-i\right\}  $. Then, the vertex $\ell_{i+p}$
is active in the $\mathbb{Z}$-configuration $f-\Delta\ell_{1}-\Delta\ell
_{2}-\cdots-\Delta\ell_{i+p-1}$ (since the sequence $\left(  \ell_{1},\ell
_{2},\ldots,\ell_{k}\right)  $ is legal for $f$). In view of%
\begin{align*}
f-\Delta\ell_{1}-\Delta\ell_{2}-\cdots-\Delta\ell_{i+p-1}  &
=\underbrace{\left(  f-\Delta\ell_{1}-\Delta\ell_{2}-\cdots-\Delta\ell
_{i}\right)  }_{=g}-\Delta\ell_{i+1}-\Delta\ell_{i+2}-\cdots-\Delta
\ell_{i+p-1}\\
& =g-\Delta\ell_{i+1}-\Delta\ell_{i+2}-\cdots-\Delta\ell_{i+p-1},
\end{align*}
this rewrites as follows: The vertex $\ell_{i+p}$ is active in the
$\mathbb{Z}$-configuration $g-\Delta\ell_{i+1}-\Delta\ell_{i+2}-\cdots
-\Delta\ell_{i+p-1}$. But this is precisely what we needed to show.}. Hence,
Lemma \ref{lem.chip.leg-concat2} (applied to $g$, $j-i$, $\left(  \ell
_{i+1},\ell_{i+2},\ldots,\ell_{j}\right)  $, $\ell_{i+h}$ and $r$ instead of
$f$, $p$, $u$, $u_{h}$ and $k$) shows that the sequence $\left(  \ell
_{i+1},\ell_{i+2},\ldots,\ell_{j}\right)  ^{\ast r}$ is legal for $g$ (because
of (\ref{pf.lem.chip.leg-repeat.zerosum})). Hence, Lemma
\ref{lem.chip.leg-concat1} (applied to $\left(  \ell_{1},\ell_{2},\ldots
,\ell_{i}\right)  $ and $\left(  \ell_{i+1},\ell_{i+2},\ldots,\ell_{j}\right)
^{\ast r}$ instead of $u$ and $v$) yields that $\left(  \ell_{1},\ell
_{2},\ldots,\ell_{i}\right)  \ast\left(  \ell_{i+1},\ell_{i+2},\ldots,\ell
_{j}\right)  ^{\ast r}$ is a legal sequence for $f$. This proves Lemma
\ref{lem.chip.leg-repeat} \textbf{(a)}.

\textbf{(b)} We must show that for each $r\in\mathbb{N}$, there exists a legal
sequence for $f$ of length $r$.

So let us fix $r\in\mathbb{N}$. From $i<j$, we obtain $j-i\geq1$. Lemma
\ref{lem.chip.leg-repeat} \textbf{(a)} shows that the sequence $\left(
\ell_{1},\ell_{2},\ldots,\ell_{i}\right)  \ast\left(  \ell_{i+1},\ell
_{i+2},\ldots,\ell_{j}\right)  ^{\ast r}$ is legal for $f$. This sequence has
length $i+r\underbrace{\left(  j-i\right)  }_{\geq1}\geq\underbrace{i}_{\geq
0}+r\geq r$. Hence, the first $r$ entries of this sequence form a sequence of
length $r$. This sequence is legal for $f$ (being a prefix of the legal
sequence $\left(  \ell_{1},\ell_{2},\ldots,\ell_{i}\right)  \ast\left(
\ell_{i+1},\ell_{i+2},\ldots,\ell_{j}\right)  ^{\ast r}$). Hence, we have
found a legal sequence for $f$ of length $r$. This proves Lemma
\ref{lem.chip.leg-repeat} \textbf{(b)}.
\end{proof}

\subsubsection{Bounds on legal sequences}

This section is of technical nature; it will later be helpful
in constructive proofs and algorithms.
You should probably skip it at first read.

Let us state a simple lemma for future use:
\begin{lemma} \label{lem.chip.sum-fire}
Let $f : V \to \ZZ$ be a $\ZZ$-configuration.
Let $v_1, v_2, \ldots, v_N$ be any vertices of $D$.
Then,
\[
\sum \tup{f - \Delta v_1 - \Delta v_2 - \cdots - \Delta v_N}
= \sum f .
\]
\end{lemma}

\begin{proof}[Proof of Lemma~\ref{lem.chip.sum-fire}.]
We have
\begin{align*}
&  \sum\left(  f-\Delta v_{1}-\Delta v_{2}-\cdots-\Delta v_N\right)
\\
&  =\sum f-\sum\left(  \Delta v_{1}\right)  -\sum\left(  \Delta v
_{2}\right)  -\cdots-\sum\left(  \Delta v_N\right)
 =\sum f
\end{align*}
(since Proposition \ref{prop.chip.sumDv=0} yields
$\sum\left(  \Delta v_{j}\right)  =0\text{ for each }j\in\left\{
1,2,\ldots,N\right\}$).
This proves Lemma~\ref{lem.chip.sum-fire}.
\end{proof}

Next we state some inequality-type facts about legal sequences:

\begin{lemma} \label{lem.chip.leg-hineq}
Let $f : V \to \NN$ be a configuration.
Let $h = \sum f$.
Let $\tup{\ell_1, \ell_2, \ldots, \ell_N}$ be a legal sequence for $f$.
Then, $\deg^+ \tup{\ell_i} \leq h$ for each
$i \in \set{1, 2, \ldots, N}$.
\end{lemma}

\begin{proof}[Proof of Lemma~\ref{lem.chip.leg-hineq} (sketched).]
Fix $i\in\left\{  1,2,\ldots,N\right\}  $.

The sequence $\left(  \ell_{1},\ell_{2},\ldots,\ell_{N}\right)  $ is legal for
$f$. Thus, the vertex $\ell_{i}$ is active in the $\ZZ$-configuration
$f-\Delta\ell_{1}-\Delta\ell_{2}-\cdots-\Delta\ell_{i-1}$ (by the definition
of a legal sequence). In other words, $\left(  f-\Delta\ell_{1}-\Delta\ell
_{2}-\cdots-\Delta\ell_{i-1}\right)  \left(  \ell_{i}\right)  \geq\deg
^{+}\left(  \ell_{i}\right)  $.

But the sequence $\left(  \ell_{1},\ell_{2},\ldots,\ell_{N}\right)  $ is legal
for $f$. Thus, $f-\Delta\ell_{1}-\Delta\ell_{2}-\cdots-\Delta\ell_{i-1}$ is a
configuration (since $f$ is a configuration). Moreover,
Lemma~\ref{lem.chip.sum-fire} (applied to $i-1$ and $\ell_p$
instead of $N$ and $v_p$) yields
$\sum\left(  f-\Delta\ell_{1}-\Delta\ell_{2}-\cdots-\Delta\ell_{i-1}\right)
= \sum f =h$.
Hence, Proposition \ref{prop.chip.sum-greater} (applied to $f-\Delta\ell
_{1}-\Delta\ell_{2}-\cdots-\Delta\ell_{i-1}$ and $\ell_i$ instead of $f$ and $w$)
yields $\left(  f-\Delta\ell_{1}-\Delta\ell_{2}-\cdots-\Delta\ell
_{i-1}\right)  \left( \ell_i \right)  \leq h$. Hence,%
\[
h\geq\left(  f-\Delta\ell_{1}-\Delta\ell_{2}-\cdots-\Delta\ell_{i-1}\right)
\tup{ \ell_i }
\geq\deg^{+}\left(  \ell_{i}\right)  .
\]
This proves Lemma~\ref{lem.chip.leg-hineq}.
\end{proof}

\begin{lemma} \label{lem.chip.leg-bound1}
Let $f : V \to \NN$ be a configuration.
Let $h = \sum f$.
Let $\ell$ be a legal sequence for $f$.

Let $a$ be an arc of $D$.
Let $u$ be the source of $a$, and let $v$ be the target of $a$.

\textbf{(a)}
If $u$ appears more than $h$ times in the sequence $\ell$,
then $v$ must appear at least once in the sequence $\ell$.

\textbf{(b)}
Fix $k \in \NN$.
If $u$ appears more than $kh$ times in the sequence $\ell$,
then $v$ must appear at least $k$ times in the sequence $\ell$.
\end{lemma}

\begin{proof}[Proof of Lemma~\ref{lem.chip.leg-bound1} (sketched).]
\textbf{(b)} Assume that $u$ appears more than $kh$ times in the sequence
$\ell$. We must prove that $v$ must appear at least $k$ times in the sequence
$\ell$.

Assume the contrary. Thus, $v$ appears less than $k$ times in the sequence
$\ell$. In other words, $v$ appears at most $k-1$ times in the sequence $\ell$.

Write the sequence $\ell$ in the form $\ell=\left(  \ell_{1},\ell_{2}%
,\ldots,\ell_{N}\right)  $. Then, $\left(  \ell_{1},\ell_{2},\ldots,\ell
_{N}\right)  =\ell$ is a legal sequence for $f$. Hence, $f-\Delta\ell
_{1}-\Delta\ell_{2}-\cdots-\Delta\ell_{N}$ is a configuration (since $f$ is a
configuration). Denote this configuration by $f^{\prime}$. Thus, $f^{\prime
}=f-\Delta\ell_{1}-\Delta\ell_{2}-\cdots-\Delta\ell_{N}$.

At least one arc of $D$ has source $u$ and target $v$ (namely,
$a$). Thus, $a_{u,v}\geq1$. Thus,%
\begin{equation}
a_{w,v}\geq\left[  w=u\right]  \qquad\text{for each vertex }w\in V
\label{pf.lem.chip.leg-bound1.1}%
\end{equation}
(because if $w\neq u$, then this is obvious, but for $w=u$ it follows from
$a_{u,v}\geq1$).

From $f^{\prime}=f-\Delta\ell_{1}-\Delta\ell_{2}-\cdots-\Delta\ell_{N}$, we
obtain%
\begin{align*}
\sum f^{\prime}  &  =\sum\left(  f-\Delta\ell_{1}-\Delta\ell_{2}-\cdots
-\Delta\ell_{N}\right) \\
&  =\sum f\qquad\left(
\text{by Lemma~\ref{lem.chip.sum-fire}, applied to } v_p = \ell_p
\right) \\
&  =h.
\end{align*}
Hence, Proposition \ref{prop.chip.sum-greater} (applied to $f^{\prime}$ and
$v$ instead of $f$ and $w$) yields $f^{\prime}\left(  v\right)  \leq h$.

Also, $f\left(  v\right)  \geq0$ (since $f$ is a configuration). Furthermore,
every $i\in\left\{  1,2,\ldots,N\right\}  $ satisfies%
\begin{align}
\left(  \Delta\ell_{i}\right)  \left(  v\right)    & =\left[  v=\ell
_{i}\right]  \underbrace{\deg^{+}\left(  \ell_{i}\right)  }_{\substack{\leq
h\\\text{(by Lemma \ref{lem.chip.leg-hineq})}}}-\underbrace{a_{\ell_{i},v}%
}_{\substack{\geq\left[  \ell_{i}=u\right]  \\\text{(by
(\ref{pf.lem.chip.leg-bound1.1}))}}}\qquad \left(  \text{by the
definition of }\Delta\ell_{i}\right)  \nonumber\\
& \leq\left[  v=\ell_{i}\right]  h-\left[  \ell_{i}=u\right]
.\label{pf.lem.chip.leg-bound1.3}%
\end{align}


But $f^{\prime}=f-\Delta\ell_{1}-\Delta\ell_{2}-\cdots-\Delta\ell_{N}$.
Hence,
\begin{align*}
f^{\prime}\left(  v\right)   &  =\left(  f-\Delta\ell_{1}-\Delta\ell
_{2}-\cdots-\Delta\ell_{N}\right)  \left(  v\right)  =\underbrace{f\left(
v\right)  }_{\geq0}-\sum_{i=1}^{N}\left(  \Delta\ell_{i}\right)  \left(
v\right) \\
&\geq -\sum_{i=1}^{N}\underbrace{\left(  \Delta\ell_{i}\right)  \left(
v\right)  }_{\substack{\leq\left[  v=\ell_{i}\right]  h-\left[  \ell
_{i}=u\right]  \\\text{(by (\ref{pf.lem.chip.leg-bound1.3}))}}}
 \geq -\sum_{i=1}^{N}\left(  \left[  v=\ell_{i}\right]  h-\left[  \ell
_{i}=u\right]  \right)  \\
&  =-\underbrace{\sum_{i=1}^{N}\left[  v=\ell_{i}\right]  }%
_{\substack{=\left(  \text{the number of all }i\in\left\{  1,2,\ldots
,N\right\}  \text{ such that }v=\ell_{i}\right)  \\\leq k-1\\\text{(since
}v\text{ appears at most }k-1\text{ times in the sequence }\ell\text{)}}}h\\
&  \qquad +\underbrace{\sum_{i=1}^{N}\left[  \ell_{i}=u\right]
}_{\substack{=\left(  \text{the number of all }i\in\left\{  1,2,\ldots
,N\right\}  \text{ such that }\ell_{i}=u\right)  \\>kh\\\text{(since }u\text{
appears more than }kh\text{ times in the sequence }\ell\text{)}}}\\
&  >-\left(  k-1\right)  h+kh=h.
\end{align*}
This contradicts $f^{\prime}\left(  v\right)  \leq h$. This contradiction
proves that our assumption was wrong. Thus, Lemma~\ref{lem.chip.leg-bound1}
\textbf{(b)} is proven.

\textbf{(a)} Lemma~\ref{lem.chip.leg-bound1} \textbf{(a)} follows by applying
Lemma~\ref{lem.chip.leg-bound1} \textbf{(b)} to $k=1$.
\end{proof}

\begin{lemma} \label{lem.chip.leg-bound1b}
Let $f : V \to \NN$ be a configuration.
Let $h = \sum f$.
Let $\ell$ be a legal sequence for $f$.

Let $u$ and $v$ be two vertices of $D$ such that there exists
a path of length $d$ from $u$ to $v$.

If $u$ appears at least $h^0 + h^1 + \cdots + h^d$
times in the sequence $\ell$,
then $v$ must appear at least once in the sequence $\ell$.
\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.chip.leg-bound1b}.] We shall prove Lemma
\ref{lem.chip.leg-bound1b} by induction over $d$:

\textit{Induction base:} If $d=0$, then $u=v$. Thus, if $d=0$, then Lemma
\ref{lem.chip.leg-bound1b} holds for obvious reasons. This completes the
induction base.

\textit{Induction step:} Fix a positive integer $e$. Assume (as the induction
hypothesis) that Lemma \ref{lem.chip.leg-bound1b} holds for $d=e-1$. We must
show that Lemma \ref{lem.chip.leg-bound1b} holds for $d=e$.

Let $f$, $h$, $\ell$, $u$, $v$ and $d$ be as in Lemma
\ref{lem.chip.leg-bound1b}, and assume that $d=e$. Assume that $u$ appears at
least $h^{0}+h^{1}+\cdots+h^{d}$ times in the sequence $\ell$. We must show
that $v$ must appear at least once in the sequence $\ell$.

There exists a path of length $d$ from $u$ to $v$. Fix such a path, and let
$w$ be its second vertex. (This is well-defined, since this path has length
$d=e>0$.) Then, the path can be split into a single arc from $u$ to $w$, and a
path of length $d-1$ from $w$ to $v$. Let us denote this arc from $u$ to $w$
by $a$. Thus, $a$ is an arc with source $u$ and target $w$.

We have assumed that $u$ appears at least $h^{0}+h^{1}+\cdots+h^{d}$ times in
the sequence $\ell$. Since%
\begin{align*}
h^{0}+h^{1}+\cdots+h^{d}  & =\underbrace{h^{0}}_{=1>0}+\underbrace{h^{1}%
+h^{2}+\cdots+h^{d}}_{=\left(  h^{0}+h^{1}+\cdots+h^{d-1}\right)  h}
>\left(  h^{0}+h^{1}+\cdots+h^{d-1}\right)  h,
\end{align*}
we thus conclude that $u$ appears more than $\left(  h^{0}+h^{1}%
+\cdots+h^{d-1}\right)  h$ times in the sequence $\ell$. Thus,
Lemma~\ref{lem.chip.leg-bound1} \textbf{(b)} (applied to $h^{0}+h^{1}%
+\cdots+h^{d-1}$ and $w$ instead of $k$ and $v$) shows that $w$ must appear at
least $h^{0}+h^{1}+\cdots+h^{d-1}$ times in the sequence $\ell$.

But $d-1=e-1$ (since $d=e$). Hence, by the induction hypothesis, we can apply
Lemma \ref{lem.chip.leg-bound1b} to $w$ and $d-1$ instead of $u$ and $d$
(since there exists a path of length $d-1$ from $w$ to $v$). We thus conclude
that $v$ must appear at least once in the sequence $\ell$. This completes the
induction step. Thus, Lemma \ref{lem.chip.leg-bound1b} is proven.
\end{proof}

\begin{proposition} \label{prop.chip.leg-everyone-fires}
Let $f : V \to \NN$ be a configuration.
Let $h = \sum f$.
Let $\ell$ be a legal sequence for $f$.
Let $n = \abs{V}$.

Let $q$ be a vertex of $D$ such that for each vertex
$u \in V$, there exists a path from $u$ to $q$.

If the length of $\ell$ is
$> \tup{n-1} \tup{ h^1 + h^2 + \cdots + h^{n-1} }$,
then $q$ must appear at least once in the sequence $\ell$.
\end{proposition}

\begin{proof}
[Proof of Proposition \ref{prop.chip.leg-everyone-fires}.] Assume that the
length of $\ell$ is $>\left(  n-1\right)  \left(  h^{1}+h^{2}+\cdots
+h^{n-1}\right)  $. We must prove that $q$ must appear at least once in the
sequence $\ell$.

Assume the contrary. Thus, $q$ never appears in the sequence $\ell$. Hence,
all entries of $\ell$ are elements of $V\setminus\left\{  q\right\}  $.

Now, let $u\in V\setminus\left\{  q\right\}  $ be arbitrary. Then,%
\begin{equation}
u\text{ appears at most }h^{1}+h^{2}+\cdots+h^{n-1}\text{ times in the
sequence }\ell.\label{pf.prop.chip.leg-everyone-fires.1}%
\end{equation}


[\textit{Proof of (\ref{pf.prop.chip.leg-everyone-fires.1}):} Assume the
contrary.\footnote{Yes, this is a proof by contradiction inside a proof by
contradiction.} Thus, $u$ appears more than $h^{1}+h^{2}+\cdots+h^{n-1}$ times
in the sequence $\ell$. In other words, $u$ appears at least $\left(
h^{1}+h^{2}+\cdots+h^{n-1}\right)  +1$ times in the sequence $\ell$.

But $u\in V\setminus\left\{  q\right\}  \subseteq V$. Thus, there exists a
path from $u$ to $q$ (by one of the assumptions of Proposition
\ref{prop.chip.leg-everyone-fires}). Consider such a path $\mathbf{p}$. Let
$d$ be the length of this path $\mathbf{p}$. The vertices of this path
$\mathbf{p}$ are distinct (since it is a path), and belong to the $n$-element
set $V$. Thus, this path $\mathbf{p}$ has at most $n$ vertices; in other
words, it has length $\leq n-1$. In other words, $d\leq n-1$ (since we have
denoted the length of the path $\mathbf{p}$ by $d$). Hence, $n-1\geq d$.

But recall that $u$ appears at least $\left(  h^{1}+h^{2}+\cdots
+h^{n-1}\right)  +1$ times in the sequence $\ell$. Thus, $u$ appears at least%
\begin{align*}
\left(  h^{1}+h^{2}+\cdots+h^{n-1}\right)  +\underbrace{1}_{=h^{0}}  &
=\left(  h^{1}+h^{2}+\cdots+h^{n-1}\right)  +h^{0}=h^{0}+h^{1}+\cdots
+h^{n-1}\\
& \geq h^{0}+h^{1}+\cdots+h^{d}
\qquad \left( \text{since } n-1 \geq d \right)
\end{align*}
times in the sequence $\ell$. Hence, Lemma \ref{lem.chip.leg-bound1b} (applied
to $v=q$) yields that $q$ must appear at least once in the sequence $\ell$
(since there exists a path of length $d$ from $u$ to $q$ (namely, the path
$\mathbf{p}$)). This contradicts the fact that $q$ never appears in the
sequence $\ell$. This proves (\ref{pf.prop.chip.leg-everyone-fires.1}).]

Now, forget that we fixed $u$. We thus have proven
(\ref{pf.prop.chip.leg-everyone-fires.1}) for each $u\in V\setminus\left\{
q\right\}  $.

Notice that $\left\vert V\setminus\left\{  q\right\}  \right\vert
=\underbrace{\left\vert V\right\vert }_{=n}-1=n-1$. In other words, there are
$n-1$ elements of $V\setminus\left\{  q\right\}  $.

The sequence $\ell$ consists of elements of $V\setminus\left\{  q\right\}  $
(since all entries of $\ell$ are elements of $V\setminus\left\{  q\right\}
$), and contains each of these elements at most $h^{1}+h^{2}+\cdots+h^{n-1}$
times (by (\ref{pf.prop.chip.leg-everyone-fires.1})). Hence, it has at most
$\left(  n-1\right)  \left(  h^{1}+h^{2}+\cdots+h^{n-1}\right)  $ elements in
total (because there are $n-1$ elements of $V\setminus\left\{  q\right\}  $).
In other words, the length of $\ell$ is $\leq\left(  n-1\right)  \left(
h^{1}+h^{2}+\cdots+h^{n-1}\right)  $. This contradicts the fact that the
length of $\ell$ is $>\left(  n-1\right)  \left(  h^{1}+h^{2}+\cdots
+h^{n-1}\right)  $. This shows that our assumption was wrong; this proves
Proposition \ref{prop.chip.leg-everyone-fires}.
\end{proof}

\begin{proposition} \label{prop.chip.leg-period-a}
Let $f : V \to \NN$ be a configuration.
Let $h = \sum f$.
Let $\ell = \tup{\ell_1, \ell_2, \ldots, \ell_k}$ be a
legal sequence for $f$.
Let $i \in \set{0, 1, \ldots, k}$.
Let
$g = f - \Delta \ell_1 - \Delta \ell_2 - \cdots - \Delta \ell_i$
be the configuration obtained from $f$ by firing the vertices
$\ell_1, \ell_2, \ldots, \ell_i$.

Then, $g \in \set{0, 1, \ldots, h}^V$.
(In other words, $g \tup{v} \in \set{0, 1, \ldots, h}$
for each $v \in V$.)
\end{proposition}

\begin{proof}
[Proof of Proposition \ref{prop.chip.leg-period-a}.] Fix $v\in V$.

The sequence $\ell$ is legal for $f$. Thus, the sequence
$\left( \ell_1, \ell_2, \ldots, \ell_i \right)$ (being a prefix of $\ell$)
is also legal for $f$.
Hence,
$f-\Delta\ell_{1}-\Delta\ell_{2}-\cdots-\Delta\ell_i$ is a
configuration (since $f$ is a configuration). In other words, $g$ is a
configuration (since $g=f-\Delta\ell_{1}-\Delta\ell_{2}-\cdots-\Delta\ell_i
$). Thus, $g\left(  v\right)  \geq0$.

On the other hand, from $g=f-\Delta\ell_{1}-\Delta\ell_{2}-\cdots-\Delta
\ell_i$, we obtain%
\begin{align*}
\sum g &  =\sum\left(  f-\Delta\ell_{1}-\Delta\ell_{2}-\cdots-\Delta\ell_i\right)  \\
&  =\sum f\qquad\left(
\text{by Lemma~\ref{lem.chip.sum-fire}, applied to } N = i \text{ and }
v_p = \ell_p
\right)  \\
&  =h.
\end{align*}
Hence, Proposition \ref{prop.chip.sum-greater} (applied to $g$ and $v$ instead
of $f$ and $w$) shows that $g\left(  v\right)  \leq h$. Combined with
$g\left(  v\right)  \geq0$, this yields $g\left(  v\right)  \in\left\{
0,1,\ldots,h\right\}  $.

Now, forget that we fixed $v$. We thus have shown that $g\left(  v\right)
\in\left\{  0,1,\ldots,h\right\}  $ for each $v\in V$. In other words,
$g\in\left\{  0,1,\ldots,h\right\}  ^{V}$.
This proves
Proposition~\ref{prop.chip.leg-period-a}.
\end{proof}

\begin{proposition} \label{prop.chip.leg-period-b}
Let $f : V \to \NN$ be a configuration.
Let $h = \sum f$.
Let $n = \abs{V}$.
Let $\ell$ be a legal sequence for $f$.
If the sequence $\ell$ has length
$\geq \tup{h+1}^n$, then there exist legal sequences (for $f$)
of arbitrary length.
\end{proposition}

\begin{proof}
[Proof of Proposition \ref{prop.chip.leg-period-b}.] Assume that the sequence
$\ell$ has length $\geq\left(  h+1\right)  ^{n}$. We must prove that there
exist legal sequences (for $f$) of arbitrary length.

Write the sequence $\ell$ in the form
$\ell = \tup{\ell_1, \ell_2, \ldots, \ell_k}$.
Thus, $k\geq\left(  h+1\right)  ^{n}$ (since
$\ell$ has length $\geq\left(  h+1\right)  ^{n}$).

For each $i\in\left\{  0,1,\ldots,k\right\}  $, we have $f-\Delta\ell
_{1}-\Delta\ell_{2}-\cdots-\Delta\ell_{i}\in\left\{  0,1,\ldots,h\right\}
^{V}$ (by Proposition \ref{prop.chip.leg-period-a}, applied to $g=f-\Delta
\ell_{1}-\Delta\ell_{2}-\cdots-\Delta\ell_{i}$). In other words, all the $k+1$
configurations $f-\Delta\ell_{1}-\Delta\ell_{2}-\cdots-\Delta\ell_{i}$ (with
$i\in\left\{  0,1,\ldots,k\right\}  $) belong to the set $\left\{
0,1,\ldots,h\right\}  ^{V}$. But the set $\left\{  0,1,\ldots,h\right\}  ^{V}$
has exactly $\left(  h+1\right)  ^{n}$ elements\footnote{since%
\[
\left\vert \left\{  0,1,\ldots,h\right\}  ^{V}\right\vert =\left\vert \left\{
0,1,\ldots,h\right\}  \right\vert ^{\left\vert V\right\vert }=\left(
h+1\right)  ^{n}\ \ \ \ \ \ \ \ \ \ \left(  \text{because }\left\vert \left\{
0,1,\ldots,h\right\}  \right\vert =h+1\text{ and }\left\vert V\right\vert
=n\right)
\]
}. Since $k+1>k\geq\left(  h+1\right)  ^{n}$, we thus conclude (by the
pigeonhole principle) that two of the $k+1$ configurations $f-\Delta\ell
_{1}-\Delta\ell_{2}-\cdots-\Delta\ell_{i}$ (with $i\in\left\{  0,1,\ldots
,k\right\}  $) must be equal (because all these $k+1$ configurations belong to
$\left\{  0,1,\ldots,h\right\}  ^{V}$). In other words, there exist two
elements $i$ and $j$ of $\left\{  0,1,\ldots,k\right\}  $ satisfying $i<j$ and%
\[
f-\Delta\ell_{1}-\Delta\ell_{2}-\cdots-\Delta\ell_{i}=f-\Delta\ell_{1}%
-\Delta\ell_{2}-\cdots-\Delta\ell_{j}.
\]
Consider these $i$ and $j$. Then, Lemma \ref{lem.chip.leg-repeat} \textbf{(b)}
yields that there exist legal sequences (for $f$) of arbitrary length. This
proves Proposition \ref{prop.chip.leg-period-b}.
\end{proof}

\subsubsection{Finitary and infinitary configurations, and stabilization}

\begin{definition}
Let $f : V \to \NN$ be a configuration.

We say that $f$ is \textit{finitary} if there
exists a sequence of vertices that is stabilizing for $f$.
Otherwise, we say that $f$ is \textit{infinitary}.
\end{definition}

\begin{theorem} \label{thm.chip.dichotomy}
Let $f : V \to \NN$ be a configuration.
Then, exactly one of the following two statements holds:

\begin{itemize}
\item \textit{Statement 1:}
      The configuration $f$ is finitary. \par
      There exists a sequence $s$ of vertices that is both
      legal and stabilizing for $f$. \par
      All such sequences are permutations of $s$.
      \par
      All legal sequences (for $f$) are subpermutations
      of $s$, and in particular are at most as long as $s$.

\item \textit{Statement 2:}
      The configuration $f$ is infinitary. \par
      There exists no stabilizing sequence for $f$. \par
      There exist legal sequences for $f$ of arbitrary length.
      More precisely, each legal sequence for $f$ can be
      extended to a longer legal sequence.
\end{itemize}
\end{theorem}

\begin{proof}[Proof of Theorem~\ref{thm.chip.dichotomy}.]
Set $h=\sum f$ and $n=\left\vert V\right\vert $.

Consider the following simple algorithm:

\begin{itemize}
\item Start with the configuration $f$.

\item Search for an active vertex. If you find one, fire it. Keep doing so
until you \textbf{either} can no longer find an active vertex \textbf{or} you
have fired $\left(  h+1\right)  ^{n}$ many vertices\footnote{Of course, many
of these vertices will be equal.}.

\item Say you are in \textit{Case 1} if you have stopped because you could no
longer find an active vertex. Say you are in \textit{Case 2} if you have
stopped because you have fired $\left(  h+1\right)  ^{n}$ many vertices.
\end{itemize}

Now, let us consider Case 1 first. In this case, you have stopped because you
could no longer find an active vertex. Thus, you have arrived at a stable
configuration. Let $s$ be the sequence of vertices you have fired during the
algorithm (from first to last). Then, the sequence $s$ is legal (because you
have only fired active vertices) and stabilizing (since you have arrived at a
stable configuration). Thus, there exists a sequence of vertices that is both
legal and stabilizing for $f$ (namely, $s$). In particular, there exists a
sequence of vertices that is stabilizing for $f$. In other words, $f$ is
finitary. Thus, $f$ is not infinitary. Hence, Statement 2 cannot hold.

Furthermore, Corollary~\ref{cor.chip.lap-cor} \textbf{(a)} shows that every
sequence of vertices that is both legal and stabilizing is a permutation of
$s$. In other words, all such sequences are permutations of $s$.

Finally, Theorem \ref{thm.chip.lap} shows that all legal sequences (for $f$)
are subpermutations of $s$ (since $s$ is stabilizing), and therefore in
particular are at most as long as $s$ (since a subpermutation of $s$ is always
at most as long as $s$).

Hence, Statement 1 holds. Thus, exactly one of the two Statements 1 and 2
holds (namely, Statement 1, but not Statement 2).
Theorem~\ref{thm.chip.dichotomy} is thus proven in Case 1.

Let us now consider Case 2. In this case, you have stopped because you have
fired $\left(  h+1\right)  ^{n}$ many vertices. Let $\ell$ be the sequence of
vertices you have fired during the algorithm (from first to last). Then, the
sequence $\ell$ is legal (because you have only fired active vertices) and has
length $\left(  h+1\right)  ^{n}$ (since you have fired $\left(  h+1\right)
^{n}$ many vertices). Hence, Proposition \ref{prop.chip.leg-period-b} shows
that there exist legal sequences (for $f$) of arbitrary length. Thus, there
exists no stabilizing sequence for $f$\ \ \ \ \footnote{\textit{Proof.} Let
$s$ be a stabilizing sequence for $f$. Then, there exists a legal sequence
$\ell$ for $f$ that is longer than $s$ (since there exist legal sequences (for
$f$) of arbitrary length). Consider such an $\ell$. But Theorem
\ref{thm.chip.lap} shows that $\ell$ is a subpermutation of $s$. Hence, $\ell$
is at most as long as $s$ (since a subpermutation of $s$ is always at most as
long as $s$). This contradicts the fact that $\ell$ is longer than $s$.
\par
Now, forget that we fixed $s$. We thus have found a contradiction for each
stabilizing sequence $s$ for $f$. Thus, there exists no stabilizing sequence
for $f$.}. Hence, the configuration $f$ is infinitary.
In other words, $f$ is not finitary. Therefore,
Statement 1 does not hold.

Each legal sequence for $f$ can be extended to a longer legal
sequence\footnote{\textit{Proof.} Let $\ell$ be a legal sequence for $f$. We
must prove that $\ell$ can be extended to a longer legal sequence.
\par
The sequence $\ell$ is not stabilizing (since there exists no stabilizing
sequence for $f$). Thus, if we start with $f$ and fire all vertices of $\ell$,
we end up with a configuration $f^{\prime}$ that is not stable. Hence, the
configuration $f^{\prime}$ has at least one active vertex; consider such a
vertex, and denote it by $v$. Append the vertex $v$ to the end of the sequence
$\ell$, and denote the resulting sequence by $\ell^{\prime}$. Then,
$\ell^{\prime}$ is a legal sequence for $f$ (since $v$ is an active vertex in
$f^{\prime}$). Thus, $\ell$ can be extended to a longer legal sequence
(namely, to $\ell^{\prime}$). Qed.}. Thus, Statement 2 holds. Thus, exactly
one of the two Statements 1 and 2 holds (namely, Statement 2, but not
Statement 1). Theorem~\ref{thm.chip.dichotomy} is thus proven in Case 2.

We have now proven Theorem~\ref{thm.chip.dichotomy} in both Cases 1 and 2.
Hence, Theorem~\ref{thm.chip.dichotomy} is always proven.
\end{proof}

How do we actually tell whether a given configuration $f$
is finitary or infinitary?
We simply follow the algorithm given in the proof of
Proposition~\ref{prop.chip.leg-period-b}:
Keep firing active vertices over and over until either no
more active vertices remain, or you have fired
$\tup{h+1}^n$ many times
(where $h = \sum f$ and $n = \abs{V}$).
In the former case, $f$ is finitary (and the sequence
of vertices you have fired is a legal stabilizing sequence
for $f$).
In the latter case, $f$ is infinitary (by
Proposition~\ref{prop.chip.leg-period-b},
since the sequence of vertices you have fired is a
legal sequence of length $\geq \tup{h+1}^n$).
Needless to say, this algorithm is extremely slow and
inefficient in practice, but to some extent this slowness
is unavoidable:
A finitary configuration may require a huge number of firings
before it stabilizes.
Nevertheless, there are faster algorithms in many particular
cases; this is a subject of ongoing research.

There are also criteria which, in certain cases, guarantee
that a configuration is finitary or infinitary.
For example, the following is not hard to show:

\begin{proposition} \label{prop.chip.infinitary-by-pigeon}
Let $f : V \to \NN$ be a
configuration with $\sum f > \abs{A} - \abs{V}$.
Then, $f$ is infinitary.
\end{proposition}

\begin{proof}[Proof of Proposition~\ref{prop.chip.infinitary-by-pigeon}.]
Let $s$ be a sequence of vertices that is stabilizing for $f$.
We shall derive a contradiction.

Let $g$ be the configuration obtained from $f$ by
firing the vertices in $s$.
Thus, $g$ is stable (since $s$ is stabilizing for $f$).
In other words, there are no active vertices in $g$.

Write the sequence $s$ in the form
$s = \tup{s_1, s_2, \ldots, s_N}$.
Then, $g = f - \Delta s_1 - \Delta s_2 - \cdots - \Delta s_N$
(since $g$ is obtained from $f$ by firing the vertices in $s$).
Hence,
$\sum g
= \sum \tup{f - \Delta s_1 - \Delta s_2 - \cdots - \Delta s_N}
= \sum f$
(by Lemma~\ref{lem.chip.sum-fire}, applied to $v_i = s_i$).

A well-known fact
(shown, e.g., during \cite[solution to Exercise 4]{hw2s})
says that
$\sum_{v \in V} \deg^+ v = \abs{A}$.
Thus,
\[
\sum_{v \in V} \tup{\deg^+ v - 1}
= \underbrace{\sum_{v \in V} \deg^+ v}_{= \abs{A}}
- \underbrace{\sum_{v \in V} 1}_{= \abs{V}}
= \abs{A} - \abs{V}.
\]
But the definition of $\sum g$ yields
\begin{equation}
\sum_{v \in V} g \tup{v} = \sum g = \sum f
> \abs{A} - \abs{V}
= \sum_{v \in V} \tup{\deg^+ v - 1} .
\label{pf.prop.chip.infinitary-by-pigeon.2}
\end{equation}
Hence, there exists at least one $v \in V$ satisfying
$g \tup{v} > \deg^+ v - 1$
(because otherwise, each $v \in V$ would satisfy
$g \tup{v} \leq \deg^+ v - 1$,
so that
we would get 
$\sum_{v \in V} \underbrace{g \tup{v}}_{\leq \deg^+ v - 1}
\leq \sum_{v \in V} \tup{\deg^+ v - 1}$,
which would contradict
\eqref{pf.prop.chip.infinitary-by-pigeon.2}).
In other words, there exists at least one $v \in V$ satisfying
$g \tup{v} \geq \deg^+ v$
(since $g \tup{v}$ and $\deg^+ v$ are integers).
In other words, there exists at least one active vertex
$v \in V$ in $g$.
This contradicts the fact that there are no active vertices in $g$.

Now, forget that we fixed $s$.
We thus have obtained a contradiction
whenever $s$ is a sequence of vertices that is stabilizing for $f$.
Hence, there exists no sequence of vertices that is stabilizing
for $f$.
In other words, $f$ is infinitary.
This proves Proposition~\ref{prop.chip.infinitary-by-pigeon}.
\end{proof}

Conversely, the results of
Exercise~\ref{exe.chip.adj-cycles} can be viewed as
bounds on $\sum f$ that guarantee that $f$ must be
finitary.

\begin{definition} \label{def.chip.stabilization}
Let $f : V \to \NN$ be a finitary configuration.
Then, Statement 1 in Theorem~\ref{thm.chip.dichotomy} must
hold.
Therefore, there exists a sequence $s$ of vertices that is both
legal and stabilizing for $f$.
The \textit{stabilization} of $f$ means
the configuration obtained from $f$ by firing
all vertices in $s$ (one after the other).
(This does not depend on the choice of $s$, because of
Corollary~\ref{cor.chip.lap-cor} \textbf{(d)}.)

The stabilization of $f$ is denoted by $f^\circ$.
\end{definition}

\subsubsection{$q$-stabilization}

Something similar holds if we forbid firing a specific
vertex:

\begin{definition}
Let $q \in V$.
Let $f : V \to \ZZ$ be a $\ZZ$-configuration.

The $\ZZ$-configuration $f$ is said to be
\textit{$q$-stable} if no vertex $v \in V$ except
(possibly) $q$ is active in $f$.
\end{definition}

So the vertex $q$ may and may not be active in a
$q$-stable configuration; but no other vertex is allowed
to be active.

\begin{definition}
Let $q \in V$.

Let $f : V \to \ZZ$ be a $\ZZ$-configuration.

Let $\tup{v_1, v_2, \ldots, v_k}$ be a sequence of vertices of
$D$.

\textbf{(a)} The sequence $\tup{v_1, v_2, \ldots, v_k}$ is said
to be \textit{$q$-legal} for $f$ if it is legal and does not
contain the vertex $q$.

\textbf{(b)} The sequence $\tup{v_1, v_2, \ldots, v_k}$ is said
to be \textit{$q$-stabilizing} for $f$ if the $\ZZ$-configuration
$f - \Delta v_1 - \Delta v_2 - \cdots - \Delta v_k$ is
$q$-stable (i.e., has no active vertices except (possibly) $q$).
\end{definition}

We can now define ``$q$-finitary'' and ``$q$-infinitary''
and obtain an analogue of Theorem~\ref{thm.chip.dichotomy}.
But the most commonly considered case is that when $q$ is
a ``global sink'' (a vertex with no outgoing arcs, and which
is reachable from any vertex),
and in this case \textbf{every} configuration is
$q$-finitary.
Let us state this as its own result:

\begin{theorem} \label{thm.chip.dichotomy-q}
Let $f : V \to \NN$ be a configuration.
Let $q \in V$.
Assume that for each vertex $u \in V$, there exists a path
from $u$ to $q$.
Then, there exists a sequence $s$ of vertices that is both
$q$-legal and $q$-stabilizing for $f$.
All such sequences are permutations of $s$.
All $q$-legal sequences (for $f$) are subpermutations
of $s$, and in particular are at most as long as $s$.
\end{theorem}

Before we can prove this, let us state the analogue of
Theorem~\ref{thm.chip.lap} for $q$-legal and
$q$-stabilizing sequences:

\begin{theorem} \label{thm.chip.lap-q}
Let $f : V \to \ZZ$ be any $\ZZ$-configuration.
Let $q \in V$.
Let $\ell$ and $s$ be two sequences of vertices of $D$ such
that $\ell$ is $q$-legal for $f$ while $s$ is
$q$-stabilizing for $f$.
Then, $\ell$ is a subpermutation of $s$.
\end{theorem}

\begin{proof}[Proof of Theorem~\ref{thm.chip.lap-q}.]
This proof is completely analogous to the proof
of Theorem~\ref{thm.chip.lap} above.
(Of course, you should use that none of the $\ell_i$
can be equal to $q$.)
\end{proof}

We also get an analogue of Corollary~\ref{cor.chip.lap-cor}:

\begin{corollary} \label{cor.chip.lap-cor-q}
Let $f : V \to \NN$ be any configuration.
Let $q \in V$.
Let $\ell$ and $\ell'$ be two sequences of vertices of $D$
that are both $q$-legal and $q$-stabilizing for $f$.
Then:

\textbf{(a)} The sequence $\ell'$ is a permutation of $\ell$.

In particular:

\textbf{(b)} The sequences $\ell$ and $\ell'$ have the
same length.

\textbf{(c)} For each $t \in V$, the number of times $t$
appears in $\ell'$ equals the number of times $t$ appears in
$\ell$.

\textbf{(d)} The configuration obtained from $f$ by firing
all vertices in $\ell$ (one after the other) equals the
configuration obtained from $f$ by firing
all vertices in $\ell'$ (one after the other).
\end{corollary}

\begin{proof}[Proof of Corollary~\ref{cor.chip.lap-cor-q}.]
This proof is completely analogous to the proof
of Corollary~\ref{cor.chip.lap-cor} above.
(Of course, Theorem~\ref{thm.chip.lap-q} needs to be used
now instead of Theorem~\ref{thm.chip.lap}.)
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm.chip.dichotomy-q}.]
This is somewhat similar to how we proved Theorem \ref{thm.chip.dichotomy},
but there will be a twist.

Set $h=\sum f$ and $n=\left\vert V\right\vert $.

Consider the following simple algorithm:

\begin{itemize}
\item Start with the configuration $f$.

\item Search for an active vertex distinct from $q$. If you find one, fire it.
Keep doing so until you \textbf{either} can no longer find an active vertex
distinct from $q$ \textbf{or} you have fired $\left(  n-1\right)  \left(
h^{1}+h^{2}+\cdots+h^{n-1}\right) +1 $ many vertices\footnote{Of course, many of
these vertices will be equal.}.

\item Say you are in \textit{Case 1} if you have stopped because you could no
longer find an active vertex distinct from $q$. Say you are in \textit{Case 2}
if you have stopped because you have fired $\left(  n-1\right)  \left(
h^{1}+h^{2}+\cdots+h^{n-1}\right) +1 $ many vertices.
\end{itemize}

Now, let us consider Case 1 first. In this case, you have stopped because you
could no longer find an active vertex distinct from $q$. Thus, you have
arrived at a $q$-stable configuration. Let $s$ be the sequence of vertices you
have fired during the algorithm (from first to last). Then, the sequence $s$
is $q$-legal (because you have only fired active vertices distinct from $q$)
and $q$-stabilizing (since you have arrived at a $q$-stable configuration).
Thus, there exists a sequence of vertices that is both $q$-legal and
$q$-stabilizing for $f$ (namely, $s$). Hence,
Corollary~\ref{cor.chip.lap-cor-q} \textbf{(a)} shows that every sequence of
vertices that is both $q$-legal and $q$-stabilizing is a permutation of $s$.
In other words, all such sequences are permutations of $s$.

Finally, Theorem \ref{thm.chip.lap-q} shows that all $q$-legal sequences (for
$f$) are subpermutations of $s$ (since $s$ is $q$-stabilizing), and therefore
in particular are at most as long as $s$ (since a subpermutation of $s$ is
always at most as long as $s$). Theorem~\ref{thm.chip.dichotomy-q} is thus
proven in Case 1.

Let us now consider Case 2. In this case, you have stopped because you have
fired $\left(  n-1\right)  \left(  h^{1}+h^{2}+\cdots+h^{n-1}\right) +1 $ many
vertices. Let $\ell$ be the sequence of vertices you have fired during the
algorithm (from first to last). Then, the sequence $\ell$ is legal (because
you have only fired active vertices) and has length $\left(  n-1\right)
\left(  h^{1}+h^{2}+\cdots+h^{n-1}\right) +1 $ (since you have fired $\left(
n-1\right)  \left(  h^{1}+h^{2}+\cdots+h^{n-1}\right) +1 $ many vertices).
Also, the sequence $\ell$ does not contain the vertex $q$ (since you have only
fired vertices distinct from $q$).

The length of the sequence $\ell$ is \newline
$\left(  n-1\right)  \left(  h^{1}%
+h^{2}+\cdots+h^{n-1}\right)  +1>\left(  n-1\right)  \left(  h^{1}%
+h^{2}+\cdots+h^{n-1}\right)  $. Hence, Proposition
\ref{prop.chip.leg-everyone-fires} shows that $q$ must appear at least once in
the sequence $\ell$. This contradicts the fact that the sequence $\ell$ does
not contain the vertex $q$. This contradiction shows that Case 2 cannot
happen. Thus, the only possible case is Case 1.

But we have proven Theorem~\ref{thm.chip.dichotomy-q} in Case 1. Thus,
Theorem~\ref{thm.chip.dichotomy-q} always holds.
\end{proof}

\begin{definition}
Let $f : V \to \NN$ be a configuration.
Let $q \in V$.
Assume that for each vertex $u \in V$, there exists a path
from $u$ to $q$.
Then, Theorem~\ref{thm.chip.dichotomy-q} shows that
there exists a sequence $s$ of vertices that is both
$q$-legal and $q$-stabilizing for $f$.
The \textit{$q$-stabilization} of $f$ means
the configuration obtained from $f$ by firing
all vertices in $s$ (one after the other).
(This does not depend on the choice of $s$, because of
Corollary~\ref{cor.chip.lap-cor-q} \textbf{(d)}.)
\end{definition}


\subsection{Exercise \ref{exe.chip.better-bounds}: better
bounds for legal sequences}

The following exercise improves on the bound given in
Proposition~\ref{prop.chip.leg-period-b} and
also on the one given in
Proposition~\ref{prop.chip.leg-everyone-fires}\footnote{To
  see that Exercise~\ref{exe.chip.better-bounds} \textbf{(b)}
  improves on the bound given in
  Proposition~\ref{prop.chip.leg-everyone-fires},
  we need to check that
  $\tup{n-1} \tup{ h^1 + h^2 + \cdots + h^{n-1} } + 1
  \geq \dbinom{n+h-1}{n-1}$.
  This is easy for $n \leq 1$ (in fact, the case
  $n = 0$ is impossible due to the existence of a
  $q \in V$, and the case $n = 1$ is an equality
  case).
  In the remaining case $n \geq 2$,
  the stronger inequality
  $1 + h^1 + h^2 + \cdots + h^{n-1}
  \geq \dbinom{n+h-1}{n-1}$
  can be proven by a simple induction
  over $n$.}.
I don't know whether the improved bounds can be further
improved.

\begin{exercise} \label{exe.chip.better-bounds}
Fix a multidigraph $D = \tup{V, A, \phi}$.
Let $f : V \to \NN$ be a configuration.
Let $h = \sum f$.
Let $n = \abs{V}$.
Assume that $n > 0$.

Let $\ell = \tup{\ell_1, \ell_2, \ldots, \ell_k}$ be a
legal sequence for $f$ having length
$k \geq \dbinom{n+h-1}{n-1}$.

Prove the following:

\textbf{(a)} There exist legal sequences (for $f$) of
arbitrary length.

\textbf{(b)} Let $q$ be a vertex of $D$ such that for each vertex
$u \in V$, there exists a path from $u$ to $q$.
Then, $q$ must appear at least once in the sequence $\ell$.

[\textbf{Hint:}
For \textbf{(a)}, apply the same pigeonhole-principle argument
as for Proposition~\ref{prop.chip.leg-period-b}.]
\end{exercise}

In the solution of Exercise \ref{exe.chip.better-bounds}, the following
classical fact will turn out useful:

\begin{proposition}
\label{prop.multichoose}Let $n\in\mathbb{N}$ and $h\in\mathbb{N}$ be such that
$n>0$. The number of $n$-tuples $\left(  a_{1},a_{2},\ldots,a_{n}\right)  $ of
nonnegative integers satisfying $a_{1}+a_{2}+\cdots+a_{n}=h$ is $\dbinom
{n+h-1}{n-1}$.
\end{proposition}

\begin{proof}
[Proof of Proposition \ref{prop.multichoose}.]See, for example,
\url{https://math.stackexchange.com/questions/36250/number-of-monomials-of-certain-degree}
for a proof of this fact (in the language of monomials). Or see \cite[\S 1.2]%
{Stanle11} (search for \textquotedblleft weak composition\textquotedblright%
\ and read the first paragraph that comes up).
Or see \cite[Proposition 13.3]{Galvin} (in the case $h > 0$; but the case
$h = 0$ is trivial).
\end{proof}

\begin{proof}
[Hints to Exercise \ref{exe.chip.better-bounds}.]For each $i\in\left\{
0,1,\ldots,k\right\}  $, the $\ZZ$-configuration $f-\Delta\ell
_{1}-\Delta\ell_{2}-\cdots-\Delta\ell_{i}$ is a configuration (since the
sequence $\left(  \ell_{1},\ell_{2},\ldots,\ell_{k}\right)  $ is legal for
$f$). Moreover, each of the $k+1$ configurations $f-\Delta\ell_{1}-\Delta
\ell_{2}-\cdots-\Delta\ell_{i}$ (with $i\in\left\{  0,1,\ldots,k\right\}  $)
has exactly $h$ chips\footnote{\textit{Proof.} Let $i\in\left\{
0,1,\ldots,k\right\}  $. Then,%
\begin{align*}
\sum\underbrace{\left(  f-\Delta\ell_{1}-\Delta\ell_{2}-\cdots-\Delta\ell
_{i}\right)  }_{=f-\sum_{j=1}^{i}\Delta\ell_{j}}  &  =\sum\left(  f-\sum
_{j=1}^{i}\Delta\ell_{j}\right)  =\underbrace{\sum f}_{=h}-\sum_{j=1}%
^{i}\underbrace{\sum\left(  \Delta\ell_{j}\right)  }%
_{\substack{=0\\\text{(since }\sum\left(  \Delta v\right)  =0\\\text{for each
vertex }v\text{)}}}\\
&  =h-\underbrace{\sum_{j=1}^{i}0}_{=0}=h.
\end{align*}
In other words, the configuration $f-\Delta\ell_{1}-\Delta\ell_{2}%
-\cdots-\Delta\ell_{i}$ has exactly $h$ chips.}.

There exist precisely $\dbinom{n+h-1}{n-1}$ configurations having exactly $h$
chips\footnote{\textit{Proof.} Recall that $\mathbb{N}$ denotes the set of
nonnegative integers.
\par
Let $v_{1},v_{2},\ldots,v_{n}$ be the vertices of $D$ (listed with no
repetitions). Then, there is a bijection%
\begin{align*}
\left\{  \text{configurations on }D\right\}   &  \rightarrow\mathbb{N}^{n},\\
f  &  \mapsto\left(  f\left(  v_{1}\right)  ,f\left(  v_{2}\right)
,\ldots,f\left(  v_{n}\right)  \right)  .
\end{align*}
This bijection restricts to a bijection%
\begin{align*}
\left\{  \text{configurations on }D\text{ having exactly }h\text{
chips}\right\}   &  \rightarrow\left\{  \left(  a_{1},a_{2},\ldots
,a_{n}\right)  \in\mathbb{N}^{n}\ \mid\ a_{1}+a_{2}+\cdots+a_{n}=h\right\}
,\\
f  &  \mapsto\left(  f\left(  v_{1}\right)  ,f\left(  v_{2}\right)
,\ldots,f\left(  v_{n}\right)  \right)
\end{align*}
(since the number of chips in a configuration $f$ on $D$ is $\sum f=f\left(
v_{1}\right)  +f\left(  v_{2}\right)  +\cdots+f\left(  v_{n}\right)  $).
Hence,%
\begin{align*}
&  \left\vert \left\{  \text{configurations on }D\text{ having exactly
}h\text{ chips}\right\}  \right\vert \\
&  =\left\vert \left\{  \left(  a_{1},a_{2},\ldots,a_{n}\right)  \in
\mathbb{N}^{n}\ \mid\ a_{1}+a_{2}+\cdots+a_{n}=h\right\}  \right\vert \\
&  =\dbinom{n+h-1}{n-1}\qquad \left(  \text{by Proposition
\ref{prop.multichoose}}\right)  .
\end{align*}
In other words, there exist precisely $\dbinom{n+h-1}{n-1}$ configurations
having exactly $h$ chips.}. Since $k+1>k\geq\dbinom{n+h-1}{n-1}$, we thus
conclude (by the pigeonhole principle) that two of the $k+1$ configurations
$f-\Delta\ell_{1}-\Delta\ell_{2}-\cdots-\Delta\ell_{i}$ (with $i\in\left\{
0,1,\ldots,k\right\}  $) must be equal (because all these $k+1$ configurations
are configurations having exactly $h$ chips). In other words, there exist two
elements $i$ and $j$ of $\left\{  0,1,\ldots,k\right\}  $ satisfying $i<j$ and%
\begin{equation}
f-\Delta\ell_{1}-\Delta\ell_{2}-\cdots-\Delta\ell_{i}=f-\Delta\ell_{1}%
-\Delta\ell_{2}-\cdots-\Delta\ell_{j}. \label{sol.chip.better-bounds.ivsj}%
\end{equation}
Consider these $i$ and $j$.
Hence, Lemma~\ref{lem.chip.leg-repeat} \textbf{(a)} shows that
there exist legal sequences (for $f$) of arbitrary length.
This solves Exercise \ref{exe.chip.better-bounds} \textbf{(a)}.

\textbf{(b)} Define an $r \in \NN$ by
$r = \tup{n - 1} \tup{ h^1 + h^2 + \cdots + h^{n-1} } + 1$.
Let $\ell^{\prime}$ be the sequence
$\left(  \ell_{1}%
,\ell_{2},\ldots,\ell_{i}\right)  \ast\left(  \ell_{i+1},\ell_{i+2}%
,\ldots,\ell_{j}\right)  ^{\ast r}$.
Lemma~\ref{lem.chip.leg-repeat} \textbf{(b)} thus shows that
this sequence $\ell^\prime$ is legal for $f$.
But the length of this sequence $\ell^{\prime}$ is
\begin{align*}
\underbrace{i}_{\geq0}+r\underbrace{\left(  j-i\right)  }_{\substack{\geq
1\\\text{(since }i<j\text{)}}}  &  \geq0+r\cdot1=r=\left(  n-1\right)  \left(
h^1 + h^2 + \cdots + h^{n-1} \right)  +1\\
&  >\left(  n-1\right)  \left(  h^1 + h^2 + \cdots + h^{n-1} \right)  .
\end{align*}
Hence, Proposition \ref{prop.chip.leg-everyone-fires} (applied to
$\ell^{\prime}$ instead of $\ell$) yields that $q$ must appear at least once
in the sequence $\ell^{\prime}$. Therefore, $q$ must also appear at least once
in the sequence $\ell$ (since each entry of $\ell^{\prime}$ is an entry of
$\ell$). This solves Exercise \ref{exe.chip.better-bounds} \textbf{(b)}.
\end{proof}

\subsection{Exercise \ref{exe.chip.examples}: examples of chip-firing}

We identify each simple digraph $\tup{V, A}$ with the multidigraph
$\tup{V, A, \iota}$, where $\iota$ is the map $V \to A \times A$ that
sends each arc $a \in A$ to itself.

\Needspace{15cm}
\begin{exercise} \label{exe.chip.examples}
\textbf{(a)} Let $D$ be the following simple digraph:
\[
\xymatrix{
 u \ar[r] & v \ar[r] & q
}
\]
(i.e., the digraph $D$ with three vertices
$u, v, q$ and two arcs $uv, vq$).

Let $k$ be a positive integer.
Consider the configuration $g_k$ on $D$ which has $k$ chips at $u$
and $0$ chips at each other vertex.

Find the $q$-stabilization of $g_k$.

\textbf{(b)} Let $D$ be the following simple digraph:
\[
\xymatrix{
 u \are[r] & v \ar[r] & q
}
\]
where a curve without an arrow stands for one arc in each
direction.
(Thus, formally speaking, the digraph $D$ has three vertices
$u, v, q$ and three arcs $uv, vu, vq$.)

Let $k$ be a positive integer.
Consider the configuration $g_k$ on $D$ which has $k$ chips at $u$
and $0$ chips at each other vertex.

Find the $q$-stabilization of $g_k$.

\textbf{(c)} Let $D$ be the following simple digraph:
\[
\xymatrix{
 & v \are[dl] \are[dr] \ar[dd] \\
 u \are[rr] \ar[dr] & & w \ar[dl] \\
 & q
}
\]
where a curve without an arrow stands for one arc in each
direction.
(Thus, formally speaking, the digraph $D$ has four vertices
$u, v, w, q$ and nine arcs
$uv, vu, vw, wv, wu, uw, uq, vq, wq$.)

Let $k \geq 2$ be an integer.
Consider the configuration $f_k$ on $D$ which has $k$ chips at each
vertex (i.e., which has $f_k \tup{v'} = k$ for each
$v' \in \set{u, v, w, q}$).

Find the $q$-stabilization of $f_k$.
\end{exercise}

Before we approach this exercise, let us introduce a simple notation:

\begin{definition}
\label{def.firearrow}If $k$ and $k^{\prime}$ are two configurations on $D$,
then $k\overset{\ast}{\rightarrow}k^{\prime}$ shall mean that there exists a
legal sequence $\ell$ for $k$ such that firing all vertices in $\ell$ (one
after the other) transforms $k$ into $k^{\prime}$. Thus, we have defined a
binary relation $\overset{\ast}{\rightarrow}$ on the set of all configurations
of $D$.
\end{definition}

\begin{proposition}
\label{prop.firearrow.1}\textbf{(a)} The binary relation $\overset{\ast
}{\rightarrow}$ is reflexive (i.e., each configuration $k$ satisfies
$k\overset{\ast}{\rightarrow}k$) and transitive (i.e., every three
configurations $k_{1}$, $k_{2}$ and $k_{3}$ satisfying $k_{1}\overset{\ast
}{\rightarrow}k_{2}$ and $k_{2}\overset{\ast}{\rightarrow}k_{3}$ satisfy
$k_{1}\overset{\ast}{\rightarrow}k_{3}$).

\textbf{(b)} If $c$, $k$ and $k^{\prime}$ are three configurations satisfying
$k\overset{\ast}{\rightarrow}k^{\prime}$, then $c+k\overset{\ast}{\rightarrow
}c+k^{\prime}$.
\end{proposition}

\begin{proof}
[Proof of Proposition \ref{prop.firearrow.1} (sketched).]\textbf{(a)} Each
configuration $k$ satisfies $k\overset{\ast}{\rightarrow}k$ (because the empty
sequence $\left(  {}\right)  $ is legal for $k$, and clearly firing all
vertices in the empty sequence $\left(  {}\right)  $ transforms $k$ into $k$).
Thus, the relation $\overset{\ast}{\rightarrow}$ is reflexive. It now remains
to prove that the relation $\overset{\ast}{\rightarrow}$ is transitive.

Let $k_{1}$, $k_{2}$ and $k_{3}$ be three configurations satisfying
$k_{1}\overset{\ast}{\rightarrow}k_{2}$ and $k_{2}\overset{\ast}{\rightarrow
}k_{3}$. We shall show that $k_{1}\overset{\ast}{\rightarrow}k_{3}$.

From $k_{1}\overset{\ast}{\rightarrow}k_{2}$, we conclude that there exists a
legal sequence $\ell_{1}$ for $k_{1}$ such that firing all vertices in
$\ell_{1}$ transforms $k_{1}$ into $k_{2}$. Consider this $\ell_{1}$.

From $k_{2}\overset{\ast}{\rightarrow}k_{3}$, we conclude that there exists a
legal sequence $\ell_{2}$ for $k_{2}$ such that firing all vertices in
$\ell_{2}$ transforms $k_{2}$ into $k_{3}$. Consider this $\ell_{2}$.

Write the sequences $\ell_{1}$ and $\ell_{2}$ as $\ell_{1}=\left(  v_{1}%
,v_{2},\ldots,v_{p}\right)  $ and $\ell_{2}=\left(  w_{1},w_{2},\ldots
,w_{q}\right)  $. Let $\ell$ be the sequence $\ell_1 \ast \ell_2
= \left(  v_{1},v_{2},\ldots ,v_{p},w_{1},w_{2},\ldots,w_{q}\right)  $.
(We are using the notation from Definition~\ref{def.concat} here.)
Then, firing all vertices in
$\ell$ transforms $k_{1}$ into $k_{3}$ (because the first $p$ firings
transform $k_{1}$ into $k_{2}$, and from there on the remaining $q$ firings
take us to $k_{3}$). Moreover, this sequence
$\ell = \ell_1 \ast \ell_2$ is legal for $k_1$
(by Lemma~\ref{lem.chip.leg-concat1}, applied to
$k_1$, $\ell_1$, $k_2$ and $\ell_2$
instead of $f$, $u$, $g$ and $v$).

We thus have found a legal sequence $\ell$ for $k_{1}$ such that firing all
vertices in $\ell$ (one after the other) transforms $k_{1}$ into $k_{3}$.
Hence, such a legal sequence $\ell$ exists. In other words, $k_{1}%
\overset{\ast}{\rightarrow}k_{3}$ (by the definition of the relation
$\overset{\ast}{\rightarrow}$).

We thus have shown that every three configurations $k_{1}$, $k_{2}$ and
$k_{3}$ satisfying $k_{1}\overset{\ast}{\rightarrow}k_{2}$ and $k_{2}%
\overset{\ast}{\rightarrow}k_{3}$ satisfy $k_{1}\overset{\ast}{\rightarrow
}k_{3}$. In other words, the relation $\overset{\ast}{\rightarrow}$ is
transitive. This proves Proposition \ref{prop.firearrow.1} \textbf{(a)}.

\textbf{(b)} Let $c$, $k$ and $k^{\prime}$ be three configurations satisfying
$k\overset{\ast}{\rightarrow}k^{\prime}$.

From $k\overset{\ast}{\rightarrow}k^{\prime}$, we conclude that there exists a
legal sequence $\ell$ for $k$ such that firing all vertices in $\ell$
transforms $k$ into $k^{\prime}$. Consider this $\ell$.

The sequence $\ell$ is legal for $k$, and thus also for $c+k$ (since $\left(
c+k\right)  \left(  v\right)  =\underbrace{c\left(  v\right)  }_{\geq
0}+k\left(  v\right)  \geq k\left(  v\right)  $ for each vertex $v$ of $D$).
Moreover, firing all vertices in $\ell$ transforms $c+k$ into $c+k^{\prime}$
(since firing all vertices in $\ell$ transforms $k$ into $k^{\prime}$). Hence,
we have found a legal sequence $\ell$ for $c+k$ such that firing all vertices
in $\ell$ (one after the other) transforms $c+k$ into $c+k^{\prime}$. Hence,
such a legal sequence $\ell$ exists. In other words, $c+k\overset{\ast
}{\rightarrow}c+k^{\prime}$ (by the definition of the relation $\overset{\ast
}{\rightarrow}$). This proves Proposition \ref{prop.firearrow.1} \textbf{(b)}.
\end{proof}

Similar facts hold for $q$-stabilization:

\begin{definition}
\label{def.firearrow-q}Let $q$ be a vertex of $D$. If $k$ and $k^{\prime}$ are
two configurations on $D$, then $k\underset{q}{\overset{\ast}{\rightarrow}%
}k^{\prime}$ shall mean that there exists a $q$-legal sequence $\ell$ for $k$
such that firing all vertices in $\ell$ (one after the other) transforms $k$
into $k^{\prime}$. Thus, we have defined a binary relation
$\underset{q}{\overset{\ast}{\rightarrow}}$ on the set of all configurations
of $D$.
\end{definition}

\begin{proposition}
\label{prop.firearrow-q.1}Let $q$ be a vertex of $D$.

\textbf{(a)} The binary relation $\underset{q}{\overset{\ast}{\rightarrow}}$
is reflexive (i.e., each configuration $k$ satisfies
$k\underset{q}{\overset{\ast}{\rightarrow}}k$) and transitive (i.e., every
three configurations $k_{1}$, $k_{2}$ and $k_{3}$ satisfying $k_{1}%
\underset{q}{\overset{\ast}{\rightarrow}}k_{2}$ and $k_{2}%
\underset{q}{\overset{\ast}{\rightarrow}}k_{3}$ satisfy $k_{1}%
\underset{q}{\overset{\ast}{\rightarrow}}k_{3}$).

\textbf{(b)} If $c$, $k$ and $k^{\prime}$ are three configurations satisfying
$k\underset{q}{\overset{\ast}{\rightarrow}}k^{\prime}$, then
$c+k\underset{q}{\overset{\ast}{\rightarrow}}c+k^{\prime}$.
\end{proposition}

\begin{proof}
[Proof of Proposition \ref{prop.firearrow-q.1} (sketched).]Analogous to the
proof of Proposition \ref{prop.firearrow.1}.
\end{proof}

\begin{proof}
[Hints to Exercise \ref{exe.chip.examples}.]\textbf{(a)} We shall write each
configuration $f$ on $D$ as the triple $\left(  f\left(  u\right)  ,f\left(
v\right)  ,f\left(  q\right)  \right)  $. Thus, $g_{k}=\left(  k,0,0\right)  $.

For each $h\in\left\{  0,1,\ldots,k\right\}  $, define a configuration $z_{h}$
by $z_{h}=\left(  k-h,0,h\right)  $.

Now, for each $h\in\left\{  0,1,\ldots,k-1\right\}  $, we have%
\[
z_{h}\underset{q}{\overset{\ast}{\rightarrow}}z_{h+1}%
\]
\footnote{\textit{Proof.} Let $h\in\left\{  0,1,\ldots,k-1\right\}  $. The
sequence $\left(  u,v\right)  $ is $q$-legal for $z_{h}$, and firing all
vertices in this sequence transforms $z_{h}$ into $z_{h+1}$ (because this
firing process looks as follows:%
\[
z_{h}=\left(  k-h,0,h\right)  \overset{\text{fire }u}{\longrightarrow}\left(
k-h-1,1,h\right)  \overset{\text{fire }v}{\longrightarrow}\left(
k-h-1,0,h+1\right)  =\left(  k-\left(  h+1\right)  ,0,h+1\right)  =z_{h+1}%
\]
). Hence, $z_{h}\underset{q}{\overset{\ast}{\rightarrow}}z_{h+1}$.}. Hence,%
\[
z_{0}\underset{q}{\overset{\ast}{\rightarrow}}z_{1}\underset{q}{\overset{\ast
}{\rightarrow}}z_{2}\underset{q}{\overset{\ast}{\rightarrow}}z_{3}%
\underset{q}{\overset{\ast}{\rightarrow}}\cdots\underset{q}{\overset{\ast
}{\rightarrow}}z_{k-1}\underset{q}{\overset{\ast}{\rightarrow}}z_{k}.
\]
Since the relation $\underset{q}{\overset{\ast}{\rightarrow}}$ is transitive,
we thus have $z_{0}\underset{q}{\overset{\ast}{\rightarrow}}z_{k}$. In other
words, $g_{k}\underset{q}{\overset{\ast}{\rightarrow}}\left(  0,0,k\right)  $
(since $z_{0}=\left(  k-0,0,0\right)  =\left(  k,0,0\right)  =g_{k}$ and
$z_{k}=\left(  k-k,0,k\right)  =\left(  0,0,k\right)  $). Since the
configuration $\left(  0,0,k\right)  $ is $q$-stable, this shows that $\left(
0,0,k\right)  $ is the $q$-stabilization of $g_{k}$.

\textbf{(b)} We shall write each configuration $f$ on $D$ as the triple
$\left(  f\left(  u\right)  ,f\left(  v\right)  ,f\left(  q\right)  \right)
$. Thus, $g_{k}=\left(  k,0,0\right)  $.

For each $h\in\left\{  0,1,\ldots,k\right\}  $, define a configuration $z_{h}$
by $z_{h}=\left(  k-h,0,h\right)  $.

Now, for each $h\in\left\{  0,1,\ldots,k-2\right\}  $, we have%
\[
z_{h}\underset{q}{\overset{\ast}{\rightarrow}}z_{h+1}%
\]
\footnote{\textit{Proof.} Let $h\in\left\{  0,1,\ldots,k-2\right\}  $. The
sequence $\left(  u,u,v\right)  $ is $q$-legal for $z_{h}$, and firing all
vertices in this sequence transforms $z_{h}$ into $z_{h+1}$ (because this
firing process looks as follows:%
\begin{align*}
&  z_{h}=\left(  k-h,0,h\right)  \overset{\text{fire }u}{\longrightarrow
}\left(  k-h-1,1,h\right)  \overset{\text{fire }u}{\longrightarrow}\left(
k-h-2,2,h\right) \\
&  \overset{\text{fire }v}{\longrightarrow}\left(  k-h-1,0,h+1\right)
=\left(  k-\left(  h+1\right)  ,0,h+1\right)  =z_{h+1}%
\end{align*}
). Hence, $z_{h}\underset{q}{\overset{\ast}{\rightarrow}}z_{h+1}$.}. Hence,%
\[
z_{0}\underset{q}{\overset{\ast}{\rightarrow}}z_{1}\underset{q}{\overset{\ast
}{\rightarrow}}z_{2}\underset{q}{\overset{\ast}{\rightarrow}}z_{3}%
\underset{q}{\overset{\ast}{\rightarrow}}\cdots\underset{q}{\overset{\ast
}{\rightarrow}}z_{k-2}\underset{q}{\overset{\ast}{\rightarrow}}z_{k-1}.
\]
\footnote{This chain of relations can consist of a single configuration (and
$0$ relation signs) when $k=1$. There is nothing wrong about this!} Since the
relation $\underset{q}{\overset{\ast}{\rightarrow}}$ is transitive and
reflexive, we thus have $z_{0}\underset{q}{\overset{\ast}{\rightarrow}}%
z_{k-1}$. In other words, $g_{k}\underset{q}{\overset{\ast}{\rightarrow}%
}\left(  1,0,k-1\right)  $ (since $z_{0}=\left(  k-0,0,0\right)  =\left(
k,0,0\right)  =g_{k}$ and $z_{k-1}=\left(  k-\left(  k-1\right)
,0,k-1\right)  =\left(  1,0,k-1\right)  $).

Combining this with $\left(  1,0,k-1\right)  \underset{q}{\overset{\ast
}{\rightarrow}}\left(  0,1,k-1\right)  $ (because firing the legal sequence
$\left(  u\right)  $ transforms the configuration $\left(  1,0,k-1\right)  $
into $\left(  0,1,k-1\right)  $), we obtain $g_{k}\underset{q}{\overset{\ast
}{\rightarrow}}\left(  0,1,k-1\right)  $. Since the configuration $\left(
0,1,k-1\right)  $ is $q$-stable, this shows that $\left(  0,1,k-1\right)  $ is
the $q$-stabilization of $g_{k}$.

\textbf{(c)} We shall write each configuration $f$ on $D$ as the $4$-tuple
$\left(  f\left(  u\right)  ,f\left(  v\right)  ,f\left(  w\right)  ,f\left(
q\right)  \right)  $. Thus, $f_{k}=\left(  k,k,k,k\right)  $.

For each $h\in\left\{  0,1,\ldots,k\right\}  $, define a configuration $z_{h}$
by $z_{h}=\left(  k-h,k-h,k-h,k+3h\right)  $.

Now, for each $h\in\left\{  0,1,\ldots,k-3\right\}  $, we have%
\[
z_{h}\underset{q}{\overset{\ast}{\rightarrow}}z_{h+1}%
\]
\footnote{\textit{Proof.} Let $h\in\left\{  0,1,\ldots,k-3\right\}  $. The
sequence $\left(  u,v,w\right)  $ is $q$-legal for $z_{h}$, and firing all
vertices in this sequence transforms $z_{h}$ into $z_{h+1}$ (because this
firing process looks as follows:%
\begin{align*}
z_{h}  &  =\left(  k-h,k-h,k-h,k+3h\right) \\
&  \overset{\text{fire }u}{\longrightarrow}\left(
k-h-3,k-h+1,k-h+1,k+3h+1\right)  \overset{\text{fire }v}{\longrightarrow
}\left(  k-h-2,k-h-2,k-h+2,k+3h+2\right) \\
&  \overset{\text{fire }w}{\longrightarrow}\left(
k-h-1,k-h-1,k-h-1,k+3h+3\right) \\
&  =\left(  k-\left(  h+1\right)  ,k-\left(  h+1\right)  ,k-\left(
h+1\right)  ,k+3\left(  h+1\right)  \right)  =z_{h+1}%
\end{align*}
). Hence, $z_{h}\underset{q}{\overset{\ast}{\rightarrow}}z_{h+1}$.}. Hence,%
\[
z_{0}\underset{q}{\overset{\ast}{\rightarrow}}z_{1}\underset{q}{\overset{\ast
}{\rightarrow}}z_{2}\underset{q}{\overset{\ast}{\rightarrow}}z_{3}%
\underset{q}{\overset{\ast}{\rightarrow}}\cdots\underset{q}{\overset{\ast
}{\rightarrow}}z_{k-3}\underset{q}{\overset{\ast}{\rightarrow}}z_{k-2}.
\]
\footnote{This chain of relations can consist of a single configuration (and
$0$ relation signs) when $k=2$. There is nothing wrong about this!} Since the
relation $\underset{q}{\overset{\ast}{\rightarrow}}$ is transitive and
reflexive, we thus have $z_{0}\underset{q}{\overset{\ast}{\rightarrow}}%
z_{k-2}$. In other words, $f_{k}\underset{q}{\overset{\ast}{\rightarrow}%
}\left(  2,2,2,4k-6\right)  $ (since $z_{0}=\left(  k-0,k-0,k-0,k+3\cdot
0\right)  =\left(  k,k,k,k\right)  =f_{k}$ and $z_{k-2}=\left(  k-\left(
k-2\right)  ,k-\left(  k-2\right)  ,k-\left(  k-2\right)  ,k+3\left(
k-2\right)  \right)  =\left(  2,2,2,4k-6\right)  $). Since the configuration
$\left(  2,2,2,4k-6\right)  $ is $q$-stable, this shows that $\left(
2,2,2,4k-6\right)  $ is the $q$-stabilization of $f_{k}$.
\end{proof}

\subsection{Exercise \ref{exe.chip.adj-cycles}: a lower bound
on the degree of an infinitary configuration}

\subsubsection{The exercise}

% We shall use the notation
% $\operatorname{s}\tup{a}$ for the source of an arc
% $a \in A$.
% We shall also the notation
% $\operatorname{t}\tup{a}$ for the target of an arc
% $a \in A$.

\begin{exercise} \label{exe.chip.adj-cycles}
Assume that the multidigraph $D$ is strongly connected.
Let $f : V \to \NN$ be an infinitary configuration.

\textbf{(a)} Prove that $D$ cannot have more than
$\sum f$ vertex-disjoint cycles.
(A set of cycles is said to be \textit{vertex-disjoint}
if no two distinct cycles in the set have a vertex in
common.)

\textbf{(b)} Prove that $D$ cannot have more than
$\sum f$ arc-disjoint cycles.
(A set of cycles is said to be \textit{arc-disjoint}
if no two distinct cycles in the set have an arc in
common.)
\end{exercise}

Exercise~\ref{exe.chip.adj-cycles} \textbf{(b)} is
\cite[Theorem 2.2]{BjoLov92}, but the proof given there
is vague and unrigorous.

\subsubsection{Solution to part \textbf{(a)}}

We shall first solve Exercise \ref{exe.chip.adj-cycles} \textbf{(a)}.
First, let us introduce a simple notation:

\begin{definition}
\label{def.chip.cycle-non-void}Let $g:V\rightarrow\mathbb{N}$ be a
configuration. Let $c$ be a cycle of $D$. We say that the cycle $c$ is
\textit{non-void} in $g$ if and only if there exists at least one vertex $v$
on $c$ satisfying $g\left(  v\right)  \geq1$. (In other words, the cycle $c$
is non-void in $g$ if and only if at least one vertex of $c$ has at least one
chip in $g$.)
\end{definition}

In the following lemma, we shall use the notation from Definition
\ref{def.firearrow}.

\begin{lemma}
\label{lem.chip.adj-cycles.cycles-preserve}Let $g:V\rightarrow\mathbb{N}$ and
$g^{\prime}:V\rightarrow\mathbb{N}$ be two configurations such that
$g\overset{\ast}{\rightarrow}g^{\prime}$. Let $c$ be a cycle of $D$ such that
$c$ is non-void in $g$. Then, $c$ is non-void in $g^{\prime}$.
\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.chip.adj-cycles.cycles-preserve} (sketched).]We must
merely show that whenever we fire a vertex $w$ in $g$, the cycle $c$ remains
non-void. But this is easy:

We know that there exists at least one vertex $v$ on $c$ satisfying $g\left(
v\right)  \geq1$ (since $c$ is non-void in $g$). Consider this $v$. Now:

\begin{itemize}
\item If $w=v$, then the vertex that follows $v$ on the cycle $c$ gains at
least one chip when we fire $w$; thus, the cycle $c$ remains non-void in this case.

\item If $w\neq v$, then the vertex $v$ does not lose any chips when we fire
$w$; thus, the cycle $c$ remains non-void in this case as well.
\end{itemize}

This concludes the proof of Lemma \ref{lem.chip.adj-cycles.cycles-preserve}.
\end{proof}

\begin{proof}
[Hints to Exercise \ref{exe.chip.adj-cycles}.]\textbf{(a)}
Let $h=\sum f$. Thus, we must prove that $D$ cannot have more than $h$
vertex-disjoint cycles.

The configuration
$f$ is infinitary. Thus, there exist arbitrarily long legal sequences for $f$.
In particular, there exists a legal sequence $\ell=\left(  \ell_{1},\ell
_{2},\ldots,\ell_{k}\right)  $ for $f$ of length $k>\left(  n-1\right)
\left( h^1 + h^2 + \cdots + h^{n-1} \right)  $. Consider this $\ell$.

Each vertex of $D$ appears at least once in the sequence $\ell$%
\ \ \ \ \footnote{\textit{Proof.} Let $q$ be a vertex of $D$. We must show
that $q$ appears at least once in the sequence $\ell$.
\par
For each vertex $u\in V$, there exists a path from $u$ to $q$ (since $D$ is
strongly connected). Hence, Proposition \ref{prop.chip.leg-everyone-fires}
shows that $q$ appears at least once in the sequence $\ell$.}.

Let $f^{\prime}$ be the configuration obtained from $f$ by firing the vertices
in $\ell$ (one after the other). Each cycle of $D$ is non-void in $f^{\prime}%
$\ \ \ \ \footnote{\textit{Proof.} Let $c$ be a cycle of $D$. We must then
show that $c$ is non-void in $f^{\prime}$.
\par
For each $i\in\left\{  0,1,\ldots,k\right\}  $, we define $f_{i}$ to be the
configuration
$f - \Delta \ell_1 - \Delta \ell_2 - \cdots - \Delta \ell_i$
obtained from $f$ by firing the vertices $\ell_{1},\ell
_{2},\ldots,\ell_{i}$ (in this order). (This is indeed a configuration, since
the sequence $\ell$ is legal.) Thus, $f_{0}\overset{\ast}{\rightarrow}%
f_{1}\overset{\ast}{\rightarrow}\cdots\overset{\ast}{\rightarrow}f_{k}$.
Notice that $f_{0}=f$ and $f_{k}=f^{\prime}$ (by the definition of $f^{\prime
}$).
\par
Pick a vertex $v$ on the cycle $c$. Then, $v$ appears at least once in the
sequence $\ell$ (since each vertex of $D$ appears at least once in the
sequence $\ell$). In other words, there exists some $i\in\left\{
1,2,\ldots,k\right\}  $ satisfying $\ell_{i}=v$. Consider this $i$.
\par
The vertex $v$ lies on the cycle $c$, and thus there exists at
least one arc with source $v$ (namely, the arc of the cycle $c$
emanating from $v$). In other words, $\deg^+ v \geq 1$.
\par
The
sequence $\left( \ell_1, \ell_2, \ldots, \ell_k \right)$ is legal for $f$.
Thus,
the vertex $\ell_{i}$ is active in the configuration
$f - \Delta \ell_1 - \Delta \ell_2 - \cdots - \Delta \ell_{i-1}
= f_{i-1}$ (since this is how $f_{i-1}$ is defined).
In other words, $f_{i-1}\left(  \ell_{i}\right)  \geq
\deg^+\left(  \ell_{i}\right)$.
In other words, $f_{i-1}\left(  v\right) \geq \deg^+ \tup{v}$
(since $\ell_{i}=v$). Hence, $f_{i-1} \tup{v} \geq \deg^+ \tup{v}
\geq 1$.
Thus, the cycle $c$ is non-void in $f_{i-1}$. But
$f_{i-1}\overset{\ast}{\rightarrow}f_{k}$ (since $f_{0}\overset{\ast
}{\rightarrow}f_{1}\overset{\ast}{\rightarrow}\cdots\overset{\ast
}{\rightarrow}f_{k}$, and since the relation $\overset{\ast}{\rightarrow}$ is
transitive). Hence, the cycle $c$ is non-void in $f_{k}$ (by Lemma
\ref{lem.chip.adj-cycles.cycles-preserve}, applied to $g=f_{i-1}$ and
$g^{\prime}=f_{k}$). In other words, the cycle $c$ is non-void in $f^{\prime}$
(since $f_{k}=f^{\prime}$). Qed.}.

Recall that we must prove that $D$ cannot have more than $h$
vertex-disjoint cycles.

Assume the contrary. Thus, $D$ has more than $h$ vertex-disjoint cycles. In
other words, there exist $h+1$ vertex-disjoint cycles $c_{1},c_{2}%
,\ldots,c_{h+1}$. Consider these cycles $c_{1},c_{2},\ldots,c_{h+1}$. All
these cycles are non-void in $f^{\prime}$ (since each cycle of $D$ is non-void
in $f^{\prime}$), and of course are vertex-disjoint. Thus, the configuration
$f^{\prime}$ has $h+1$ vertex-disjoint non-void cycles. Thus, it has a chip on
each of these cycles. Consequently, it has at least $h+1$ chips. In other
words, $\sum f^{\prime}\geq h+1$.

But $f^{\prime}$ is obtained from $f$ by firing vertices. Hence, $\sum
f^{\prime}=\sum f$ (since firing vertices does not change the total number of
chips). Thus, $\sum f=\sum f^{\prime}\geq h+1$, which contradicts $\sum
f=h<h+1$. This contradiction proves that our assumption was wrong, qed.
\end{proof}

\subsubsection{Solution to part \textbf{(b)}}

Our next goal is to solve Exercise \ref{exe.chip.adj-cycles} \textbf{(b)}.
Our solution is going to be a rigorous version of
\cite[proof of Theorem 2.2]{BjoLov92}.\footnote{This is one of
  those cases where
  making a proof rigorous is difficult and makes the proof
  much longer.}
We first need to prepare by introducing notations and showing lemmas.

We begin by introducing some notations:

\begin{definition}
Let $f : V \to \ZZ$ and $g : V \to \ZZ$ be two
$\ZZ$-configurations on a multidigraph $D = \tup{V, A, \phi}$.
Then, we say that $f\geq g$ if and only if each $v \in V$
satisfies $f \tup{v} \geq g \tup{v}$.
\end{definition}

Thus, a $\ZZ$-configuration $f : V \to \ZZ$ is a
configuration if and only if $f \geq 0$ (where $0$ means the
``zero configuration'' $0 : V \to \ZZ$).

\begin{definition}
Let $v\in V$ be a vertex of a multidigraph $D=\left(  V,A,\phi
\right)  $. Then, a configuration $\delta_{v}:V\rightarrow\mathbb{N}$ is
defined by setting
\[
\delta_{v}\left(  w\right)  =%
\begin{cases}
1, & \text{if }w=v;\\
0, & \text{if }w\neq v
\end{cases}
\qquad\text{ for all }w\in V.
\]
(Roughly speaking, $\delta_{v}$ is the configuration having $1$ chip at vertex
$v$ and no further chips.)
\end{definition}

Thus, each $\ZZ$-configuration $f:V\rightarrow\ZZ$ satisfies
$f=\sum_{v\in V}f\left(  v\right)  \delta_{v}$. Notice that $\sum\delta_{v}=1$
for each $v\in V$.

\begin{definition}
\label{def.chip.adj-cycles.K-captured}Consider a multidigraph
$D=\left(  V,A,\phi\right)  $.

\textbf{(a)} If $c$ is a cycle of $D$, then $\operatorname*{V}\left(
c\right)  $ shall mean the set of all vertices on $c$.

\textbf{(b)} Let $K$ be a set of cycles of $D$. Let $f:V\rightarrow\ZZ$
be a $\ZZ$-configuration on $D$. We say that $f$ is $K$%
\textit{-captured} if and only if we can choose a vertex $v_{c}\in
\operatorname*{V}\left(  c\right)  $ for each cycle $c\in K$ such that
$f\geq\sum_{c\in K}\delta_{v_c}$.
\end{definition}

The notion of \textquotedblleft$K$-captured\textquotedblright\ $\ZZ%
$-configurations is somewhat subtle. Intuitively speaking, a $\mathbb{Z}%
$-configuration $f$ is $K$-captured if and only if (pretending that the chips
in $f$ are distinguishable) we can assign to each cycle $c\in K$ a specific
chip in $f$ that lies on a vertex of $c$, without having to assign the same
chip to two different cycles. Notice that the vertices $v_{c}$ in Definition
\ref{def.chip.adj-cycles.K-captured} \textbf{(b)} need not be distinct.
(Intuitively speaking, this means that the chips assigned to different cycles
may lie on the same vertices -- but they must not be the same chip.)

We notice that if a $\mathbb{Z}$-configuration $f:V\rightarrow\mathbb{Z}$ is
$K$-captured for some set $K$ of cycles of $D$, then $f$ is a configuration
(since the vertices $v_{c}$ from Definition
\ref{def.chip.adj-cycles.K-captured} \textbf{(b)} satisfy $f\geq\sum_{c\in
K}\delta_{v_{c}}\geq0$). Also, we notice that a $\mathbb{Z}$-configuration
$f:V\rightarrow\mathbb{Z}$ is $\varnothing$-captured if and only if $f$ is a configuration.

\begin{lemma}
\label{lem.chip.adj-cycles.capture-size}Let $f:V\rightarrow\mathbb{Z}$ be a
$\ZZ$-configuration on a multidigraph $D=\left(  V,A,\phi\right)  $. Let
$K$ be a set of cycles of $D$ such that $f$ is $K$-captured.
Then, $\sum f\geq\left\vert K\right\vert $.
\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.chip.adj-cycles.capture-size}.] We know that $f$ is
$K$-captured. In other words, we can choose a vertex $v_{c}\in
\operatorname*{V}\left(  c\right)  $ for each cycle $c\in K$ such that
$f\geq\sum_{c\in K}\delta_{v_{c}}$. Consider these vertices $v_{c}$.

Now,%
\begin{align*}
\sum f  & =\sum_{p\in V}\underbrace{f\left(  p\right)  }_{\substack{\geq
\left(  \sum_{c\in K}\delta_{v_{c}}\right)  \left(  p\right)  \\\text{(since
}f\geq\sum_{c\in K}\delta_{v_{c}}\text{)}}}\geq\sum_{p\in V}\left(  \sum_{c\in
K}\delta_{v_{c}}\right)  \left(  p\right)  =\sum_{p\in V}\sum_{c\in K}%
\delta_{v_{c}}\left(  p\right)  \\
& =\sum_{c\in K}\underbrace{\sum_{p\in V}\delta_{v_{c}}\left(  p\right)
}_{\substack{=\sum\delta_{v_{c}}=1\\\text{(since }\sum\delta_{v}=1\text{ for
each }v\in V\text{)}}}=\sum_{c\in K}1=\left\vert K\right\vert .
\end{align*}
This proves Lemma \ref{lem.chip.adj-cycles.capture-size}.
\end{proof}

The following lemma will be crucial:

\begin{lemma}
\label{lem.chip.adj-cycles.capture}Let $f:V\rightarrow\mathbb{Z}$ be a
$\ZZ$-configuration on a multidigraph $D=\left(  V,A,\phi\right)  $. Let
$w\in V$ be a vertex such that $w$ is active in $f$. Let $C$ be a set of
arc-disjoint cycles of $D$. Let $C_{w}=\left\{  c\in C\ \mid\ w\in
\operatorname*{V}\left(  c\right)  \right\}  $. Let $K\subseteq C$ be such
that $f$ is $K$-captured.
Then, the $\ZZ$-configuration $f-\Delta w$ is $K\cup C_{w}$-captured.
\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.chip.adj-cycles.capture}.]We know that $f$ is
$K$-captured. In other words, we can choose a vertex $v_{c}\in
\operatorname*{V}\left(  c\right)  $ for each cycle $c\in K$ such that
$f\geq\sum_{c\in K}\delta_{v_{c}}$. Consider these vertices $v_{c}$.

Notice that $K\cup C_{w}\subseteq C$ (since $K\subseteq C$ and $C_{w}\subseteq
C$).

For each $c\in K\cup C_{w}$, we define a vertex $u_{c}\in\operatorname*{V}%
\left(  c\right)  $ by%
\[
u_{c}=%
\begin{cases}
v_{c}, & \text{if }w\notin\operatorname*{V}\left(  c\right)  ;\\
\left(  \text{the vertex succeeding }w\text{ on the cycle }c\right)  , &
\text{if }w\in\operatorname*{V}\left(  c\right)
\end{cases}
.
\]
(This definition makes sense, because $v_{c}$ is a well-defined element of
$\operatorname*{V}\left(  c\right)  $ whenever $w\notin\operatorname*{V}%
\left(  c\right)  $\ \ \ \ \footnote{\textit{Proof.} Assume that
$w\notin\operatorname*{V}\left(  c\right)  $. Then, $c\notin C_{w}$ (by the
definition of $C_{w}$). Combining this with $c\in K\cup C_{w}$, we obtain
$c\in\left(  K\cup C_{w}\right)  \setminus C_{w}\subseteq K$. Hence, $v_{c}$
is a well-defined element of $\operatorname*{V}\left(  c\right)  $.}.)

Now, we claim that%
\begin{equation}
\left(  f-\Delta w\right)  \left(  p\right)  \geq\left(  \sum_{c\in K\cup
C_{w}}\delta_{u_{c}}\right)  \left(  p\right)  \qquad\text{for every }p\in
V.\label{pf.lem.chip.adj-cycles.capture.ineq}%
\end{equation}


[\textit{Proof of (\ref{pf.lem.chip.adj-cycles.capture.ineq}):} Let $p\in V$.
We must prove the inequality (\ref{pf.lem.chip.adj-cycles.capture.ineq}).

Notice that%
\begin{align}
\left(  \sum_{c\in K\cup C_{w}}\delta_{u_{c}}\right)  \left(  p\right)   &
=\sum_{c\in K\cup C_{w}}\underbrace{\delta_{u_{c}}\left(  p\right)  }_{=%
\begin{cases}
1, & \text{if }p=u_{c};\\
0, & \text{if }p\neq u_{c}%
\end{cases}
}=\sum_{c\in K\cup C_{w}}%
\begin{cases}
1, & \text{if }p=u_{c};\\
0, & \text{if }p\neq u_{c}%
\end{cases}
\nonumber\\
&  =\left\vert \left\{  c\in K\cup C_{w}\ \mid\ p=u_{c}\right\}  \right\vert
.\label{pf.lem.chip.adj-cycles.capture.ineq.rhs}%
\end{align}


The definition of $\Delta w$ yields
\begin{equation}
\left(  \Delta w\right)  \left(  p\right)  =\left[  p=w\right]  \deg
^{+}w-a_{w,p}.\label{pf.lem.chip.adj-cycles.capture.ineq.Deltawp}%
\end{equation}


Let $Q=\left\{  c\in K\setminus C_{w}\ \mid\ p=v_{c}\right\}  $. Then, it is
not hard to see that%
\begin{equation}
f\left(  p\right)  -\left[  p=w\right]  \deg^{+}w\geq\left\vert Q\right\vert
\label{pf.lem.chip.adj-cycles.capture.ineq.c2.1b}%
\end{equation}
\footnote{\textit{Proof of (\ref{pf.lem.chip.adj-cycles.capture.ineq.c2.1b}):}
We are in one of the following two cases:
\par
\textit{Case 1:} We have $p=w$.
\par
\textit{Case 2:} We have $p\neq w$.
\par
First, let us consider Case 1. In this case, we have $p=w$. Recall that $w$ is
active in $f$. Thus, $f\left(  w\right)  \geq\deg^{+}w$.
\par
But there is no $c\in K\setminus C_{w}$ satisfying $p=v_{c}$. (In fact, if
such a $c$ would exist, then it would satisfy $w=p=v_{c}\in\operatorname*{V}%
\left(  c\right)  $, which (in view of $c\in K\setminus C_{w}\subseteq
K\subseteq C$) would yield $c\in C_{w}$ (by the definition of $C_{w}$), which
would contradict $c\in K\setminus C_{w}$.)
\par
Now, $Q=\left\{  c\in K\setminus C_{w}\ \mid\ p=v_{c}\right\}  =\varnothing$
(since there is no $c\in K\setminus C_{w}$ satisfying $p=v_{c}$). Hence,
$\left\vert Q\right\vert =\left\vert \varnothing\right\vert =0$. Now,%
\begin{align*}
f\left(  \underbrace{p}_{=w}\right)  -\underbrace{\left[  p=w\right]
}_{\substack{=1\\\text{(since }p=w\text{)}}}\deg^{+}w  & =f\left(  w\right)
-\deg^{+}w\geq0\ \ \ \ \ \ \ \ \ \ \left(  \text{since }f\left(  w\right)
\geq\deg^{+}w\right)  \\
& =\left\vert Q\right\vert .
\end{align*}
Thus, (\ref{pf.lem.chip.adj-cycles.capture.ineq.c2.1b}) is proven in Case 1.
\par
Let us now consider Case 2. In this case, we have $p\neq w$. But $Q=\left\{
c\in\underbrace{K\setminus C_{w}}_{\subseteq K}\ \mid\ p=v_{c}\right\}
\subseteq\left\{  c\in K\ \mid\ p=v_{c}\right\}  $, so that $\left\vert
Q\right\vert \leq\left\vert \left\{  c\in K\ \mid\ p=v_{c}\right\}
\right\vert $.
\par
Recall that $f\geq\sum_{c\in K}\delta_{v_{c}}$. Hence,%
\begin{align*}
f\left(  p\right)   &  \geq\left(  \sum_{c\in K}\delta_{v_{c}}\right)  \left(
p\right)  =\sum_{c\in K}\underbrace{\delta_{v_{c}}\left(  p\right)  }_{=%
\begin{cases}
1, & \text{if }p=v_{c};\\
0, & \text{if }p\neq v_{c}%
\end{cases}
}=\sum_{c\in K}%
\begin{cases}
1, & \text{if }p=v_{c};\\
0, & \text{if }p\neq v_{c}%
\end{cases}
\\
&  =\left\vert \left\{  c\in K\ \mid\ p=v_{c}\right\}  \right\vert
\geq\left\vert Q\right\vert \ \ \ \ \ \ \ \ \ \ \left(  \text{since
}\left\vert Q\right\vert \leq\left\vert \left\{  c\in K\ \mid\ p=v_{c}%
\right\}  \right\vert \right)  .
\end{align*}
Now,%
\[
f\left(  p\right)  -\underbrace{\left[  p=w\right]  }%
_{\substack{=0\\\text{(since }p\neq w\text{)}}}\deg^{+}w=f\left(  p\right)
\geq\left\vert Q\right\vert .
\]
Thus, (\ref{pf.lem.chip.adj-cycles.capture.ineq.c2.1b}) is proven in Case 2.
\par
Hence, we have proven (\ref{pf.lem.chip.adj-cycles.capture.ineq.c2.1b}) in
both possible cases 1 and 2. This completes the proof of
(\ref{pf.lem.chip.adj-cycles.capture.ineq.c2.1b}).}.

On the other hand, let $R=\left\{  c\in K\cup C_{w}\ \mid\ p=u_{c}\right\}
\setminus Q$. Then, the sets $Q$ and $R$ are disjoint, and satisfy $\left\{
c\in K\cup C_{w}\ \mid\ p=u_{c}\right\}  \subseteq Q\cup R$. Hence,%
\begin{equation}
\left\vert \left\{  c\in K\cup C_{w}\ \mid\ p=u_{c}\right\}  \right\vert
\leq\left\vert Q\cup R\right\vert =\left\vert Q\right\vert +\left\vert
R\right\vert \label{pf.lem.chip.adj-cycles.capture.ineq.c2.4}%
\end{equation}
(since $Q$ and $R$ are disjoint). Moreover, $R\subseteq C$%
\ \ \ \ \footnote{\textit{Proof.} We have $R=\left\{  c\in K\cup C_{w}%
\ \mid\ p=u_{c}\right\}  \setminus Q\subseteq\left\{  c\in K\cup C_{w}%
\ \mid\ p=u_{c}\right\}  \subseteq K\cup C_{w}\subseteq C$.}. Thus, any two
cycles in $R$ are arc-disjoint\footnote{\textit{Proof.} We have $R\subseteq
C$. Hence, any two cycles in $R$ are arc-disjoint (since $C$ is a set of
arc-disjoint cycles).}.

But if $c$ is an element of $R$, then the arc with source $w$ that belongs to
the cycle $c$ is a well-defined element of $\left\{  \text{arcs of }D\text{
having source }w\text{ and target }p\right\}  $%
\ \ \ \ \footnote{\textit{Proof.} Recall that%
\begin{equation}
R=\left\{  c\in K\cup C_{w}\ \mid\ p=u_{c}\right\}  \setminus Q=\left\{  c\in
K\cup C_{w}\ \mid\ p=u_{c}\text{ and }c\notin Q\right\}
.\label{pf.lem.chip.adj-cycles.capture.ineq.c2.fn3.pf.1}%
\end{equation}
\par
Now, let $c$ be an element of $R$. Thus, $c$ is an element of $K\cup C_{w}$
satisfying $p=u_{c}$ and $c\notin Q$ (by
(\ref{pf.lem.chip.adj-cycles.capture.ineq.c2.fn3.pf.1})).
\par
Assume (for the sake of contradiction) that $w\notin\operatorname*{V}\left(
c\right)  $. Hence, $c\notin C_{w}$ (by the definition of $C_{w}$, since $c\in
K\cup C_{w}\subseteq C$). Combining this with $c\in K\cup C_{w}$, we obtain
$c\in\left(  K\cup C_{w}\right)  \setminus C_{w}=K\setminus C_{w}$.
\par
But the definition of $u_{c}$ yields $u_{c}=v_{c}$ (since $w\notin%
\operatorname*{V}\left(  c\right)  $). Thus, $p=u_{c}=v_{c}$. Thus, $c\in
K\setminus C_{w}$ and $p=v_{c}$. Hence, $c\in Q$ (by the definition of $Q$).
This contradicts $c\notin Q$. This contradiction shows that our assumption
(that $w\notin\operatorname*{V}\left(  c\right)  $) was false. Hence, we must
have $w\in\operatorname*{V}\left(  c\right)  $. In other words, the vertex $w$
lies on the cycle $c$. Thus, the arc with source $w$ that belongs to the cycle
$c$ is well-defined.
\par
It remains to prove that this arc is an element of $\left\{  \text{arcs of
}D\text{ having source }w\text{ and target }p\right\}  $. In other words, it
remains to prove that this arc has source $w$ and target $p$. Since it clearly
has source $w$, we thus only need to show that it has target $p$.
\par
We have $w\in\operatorname*{V}\left(  c\right)  $. The definition of $u_{c}$
thus yields $u_{c}=\left(  \text{the vertex succeeding }w\text{ on the cycle
}c\right)  $.
\par
Hence, $p=u_{c}=\left(  \text{the vertex succeeding }w\text{ on
the cycle }c\right)  $. Therefore, the arc with source $w$ that belongs to the
cycle $c$ has target $p$. This completes our proof.}. Hence, the map%
\begin{align*}
R &  \rightarrow\left\{  \text{arcs of }D\text{ having source }w\text{ and
target }p\right\}  ,\\
c &  \mapsto\left(  \text{the arc with source }w\text{ that belongs to the
cycle }c\right)
\end{align*}
is well-defined. This map is furthermore injective\footnote{\textit{Proof.}
This is because any two cycles in $R$ are arc-disjoint.}. Hence,%
\[
\left\vert R\right\vert \leq\left\vert \left\{  \text{arcs of }D\text{ having
source }w\text{ and target }p\right\}  \right\vert =a_{w,p}%
\]
(by the definition of $a_{w,p}$). Thus,
(\ref{pf.lem.chip.adj-cycles.capture.ineq.c2.4}) becomes%
\begin{align*}
\left\vert \left\{  c\in K\cup C_{w}\ \mid\ p=u_{c}\right\}  \right\vert  &
\leq\underbrace{\left\vert Q\right\vert }_{\substack{\leq f\left(  p\right)
-\left[  p=w\right]  \deg^{+}w\\\text{(by
(\ref{pf.lem.chip.adj-cycles.capture.ineq.c2.1b}))}}}+\underbrace{\left\vert
R\right\vert }_{\leq a_{w,p}}\leq f\left(  p\right)  -\left[  p=w\right]
\deg^{+}w+a_{w,p}\\
& =f\left(  p\right)  -\underbrace{\left(  \left[  p=w\right]  \deg
^{+}w-a_{w,p}\right)  }_{\substack{=\left(  \Delta w\right)  \left(  p\right)
\\\text{(by (\ref{pf.lem.chip.adj-cycles.capture.ineq.Deltawp}))}}}=f\left(
p\right)  -\left(  \Delta w\right)  \left(  p\right)  \\
& =\left(  f-\Delta w\right)  \left(  p\right)  .
\end{align*}
Hence,%
\[
\left(  f-\Delta w\right)  \left(  p\right)  \geq\left\vert \left\{  c\in
K\cup C_{w}\ \mid\ p=u_{c}\right\}  \right\vert =\left(  \sum_{c\in K\cup
C_{w}}\delta_{u_{c}}\right)  \left(  p\right)
\]
(by (\ref{pf.lem.chip.adj-cycles.capture.ineq.rhs})). Hence,
(\ref{pf.lem.chip.adj-cycles.capture.ineq}) is proven.]

From (\ref{pf.lem.chip.adj-cycles.capture.ineq}), we obtain $f-\Delta
w\geq\sum_{c\in K\cup C_{w}}\delta_{u_{c}}$.

Thus, the $\ZZ$-configuration $f-\Delta w$ is $K\cup C_{w}$-captured (since
$u_{c}\in\operatorname*{V}\left(  c\right)  $ for each $c\in K\cup C_{w}$).
This proves Lemma \ref{lem.chip.adj-cycles.capture}.
\end{proof}

\begin{corollary}
\label{cor.chip.adj-cycles.captures}
Let $f:V\rightarrow\mathbb{Z}$ be a
$\ZZ$-configuration on a multidigraph $D=\left(  V,A,\phi\right)  $. Let
$\left(  \ell_{1},\ell_{2},\ldots,\ell_{k}\right)  $ be a legal sequence for
$f$. Let $C$ be a set of arc-disjoint cycles of $D$. Let $C_{w}=\left\{  c\in
C\ \mid\ w\in\operatorname*{V}\left(  c\right)  \right\}  $ for each $w\in
V$.  Let $K\subseteq C$ be such that $f$ is $K$-captured. Then, the
$\ZZ$-configuration $f-\Delta\ell_{1}-\Delta\ell_{2}-\cdots-\Delta\ell_{k}$ is
$K\cup C_{\ell_{1}}\cup C_{\ell_{2}}\cup\cdots\cup C_{\ell_{k}}$-captured.
\end{corollary}

\begin{proof}
[Proof of Corollary \ref{cor.chip.adj-cycles.captures}.] We will show that for
each $i\in\left\{  0,1,\ldots,k\right\}  $,
\begin{equation}
\text{the } \ZZ\text{-configuration }f-\Delta\ell_{1}-\Delta\ell_{2}-\cdots-\Delta\ell
_{i}\text{ is }K\cup C_{\ell_{1}}\cup C_{\ell_{2}}\cup\cdots\cup C_{\ell_{i}%
}\text{-captured.}\label{pf.cor.chip.adj-cycles.captures.i}%
\end{equation}


[\textit{Proof of (\ref{pf.cor.chip.adj-cycles.captures.i}):} We shall prove
(\ref{pf.cor.chip.adj-cycles.captures.i}) by induction over $i$:

\textit{Induction base:} If $i=0$, then
(\ref{pf.cor.chip.adj-cycles.captures.i}) simply states that the $\ZZ$-configuration
$f$ is $K$-captured. This is true, because it was an assumption. This
completes the induction base.

\textit{Induction step:} Let $j\in\left\{  0,1,\ldots,k\right\}  $ be
positive. Assume that (\ref{pf.cor.chip.adj-cycles.captures.i}) holds for
$i=j-1$. We must show that (\ref{pf.cor.chip.adj-cycles.captures.i}) holds for
$i=j$.

We have assumed that (\ref{pf.cor.chip.adj-cycles.captures.i}) holds for
$i=j-1$. In other words,
\[
\text{the }\ZZ\text{-configuration }f-\Delta\ell_{1}-\Delta\ell_{2}-\cdots-\Delta
\ell_{j-1}\text{ is }K\cup C_{\ell_{1}}\cup C_{\ell_{2}}\cup\cdots\cup
C_{\ell_{j-1}}\text{-captured.}%
\]
But the vertex $\ell_{j}$ is active in the $\ZZ$-configuration $f-\Delta\ell
_{1}-\Delta\ell_{2}-\cdots-\Delta\ell_{j-1}$ (since the sequence $\left(
\ell_{1},\ell_{2},\ldots,\ell_{k}\right)  $ is legal for $f$). Hence, Lemma
\ref{lem.chip.adj-cycles.capture} (applied to $f-\Delta\ell_{1}-\Delta\ell
_{2}-\cdots-\Delta\ell_{j-1}$, $\ell_{j}$ and $K\cup C_{\ell_{1}}\cup
C_{\ell_{2}}\cup\cdots\cup C_{\ell_{j-1}}$ instead of $f$, $w$ and $K$) shows
that the $\ZZ$-configuration $\left(  f-\Delta\ell_{1}-\Delta\ell_{2}-\cdots
-\Delta\ell_{j-1}\right)  -\Delta\ell_{j}$ is $\left(  K\cup C_{\ell_{1}}\cup
C_{\ell_{2}}\cup\cdots\cup C_{\ell_{j-1}}\right)  \cup C_{\ell_{j}}%
$-captured\footnote{since $K\cup C_{\ell_{1}}\cup C_{\ell_{2}}\cup\cdots\cup
C_{\ell_{j-1}}\subseteq C$ (since both $K$ and each $C_{w}$ are subsets of
$C$)}. In other words, the $\ZZ$-configuration $f-\Delta\ell_{1}-\Delta\ell
_{2}-\cdots-\Delta\ell_{j}$ is $K\cup C_{\ell_{1}}\cup C_{\ell_{2}}\cup
\cdots\cup C_{\ell_{j}}$-captured. In other words,
(\ref{pf.cor.chip.adj-cycles.captures.i}) holds for $i=j$. This completes the
induction step. Thus, (\ref{pf.cor.chip.adj-cycles.captures.i}) is proven by induction.]

Now, applying (\ref{pf.cor.chip.adj-cycles.captures.i}) to $i=k$, we obtain
the claim of Corollary \ref{cor.chip.adj-cycles.captures}.
\end{proof}

\begin{proof}
[Solution to Exercise \ref{exe.chip.adj-cycles} \textbf{(b)} (sketched).]
Assume the contrary. Thus, $D$ has more than $\sum f$ arc-disjoint cycles. In
other words, there exists a set $C$ of arc-disjoint cycles of $D$ such that
$\left\vert C\right\vert >\sum f$. Consider this $C$.

Set $h=\sum f$. Thus, $\left\vert C\right\vert >\sum f=h$.

Set $n = \abs{V}$. From $\abs{C} > h \geq 0$, we conclude that the
set $C$ is nonempty, so that $D$ has at least one cycle.
Thus, $D$ has at least one vertex.
In other words, $n > 0$.

Let $C_{w}=\left\{  c\in C\ \mid\ w\in\operatorname*{V}\left(  c\right)
\right\}  $ for each $w\in V$.

The configuration $f$ is infinitary. Hence, there exist legal sequences (for
$f$) of arbitrary length. In particular, this shows that there exists a legal
sequence $\ell=\left(  \ell_{1},\ell_{2},\ldots,\ell_{k}\right)  $ for $f$
having length $k\geq\dbinom{n+h-1}{n-1}$. Consider such an $\ell$.

Each vertex $q$ of $D$ must appear  at least once in the sequence $\ell
$\ \ \ \ \footnote{\textit{Proof.} Let $q$ be a vertex of $D$. Then, for each
vertex $u\in V$, there exists a path from $u$ to $q$ (since the multidigraph
$D$ is strongly connected). Hence, Exercise \ref{exe.chip.better-bounds}
\textbf{(b)} shows that $q$ must appear at least once in the sequence $\ell$.
Qed.}. Thus, $C_{\ell_{1}}\cup C_{\ell_{2}}\cup\cdots\cup C_{\ell_{k}}%
=C$\ \ \ \ \footnote{\textit{Proof.} Clearly, $C_{w}\subseteq C$ for each
$w\in V$. Thus, $C_{\ell_{1}}\cup C_{\ell_{2}}\cup\cdots\cup C_{\ell_{k}%
}\subseteq C$.
\par
On the other hand, let $c\in C$. Thus, $c$ is a cycle of $D$. Hence, there
exists some $v\in\operatorname*{V}\left(  c\right)  $. Consider this $v$.
Then, $v$ must appear at least once in the sequence $\ell$ (since each vertex
$q$ of $D$ must appear at least once in the sequence $\ell$). In other words,
there exists some $i\in\left\{  1,2,\ldots,k\right\}  $ such that $v=\ell_{i}%
$. Consider this $i$. Now, from $\ell_{i}=v\in\operatorname*{V}\left(
c\right)  $, we obtain $c\in C_{\ell_{i}}$ (by the definition of $C_{\ell_{i}%
}$). Therefore, $c\in C_{\ell_{i}}\subseteq C_{\ell_{1}}\cup C_{\ell_{2}}%
\cup\cdots\cup C_{\ell_{k}}$.
\par
Now, forget that we fixed $c$. We thus have proven that $c\in C_{\ell_{1}}\cup
C_{\ell_{2}}\cup\cdots\cup C_{\ell_{k}}$ for each $c\in C$. In other words,
$C\subseteq C_{\ell_{1}}\cup C_{\ell_{2}}\cup\cdots\cup C_{\ell_{k}}$.
Combining this with $C_{\ell_{1}}\cup C_{\ell_{2}}\cup\cdots\cup C_{\ell_{k}%
}\subseteq C$, we obtain $C_{\ell_{1}}\cup C_{\ell_{2}}\cup\cdots\cup
C_{\ell_{k}}=C$.}.

But the configuration $f$ is $\varnothing$-captured (since any configuration
is $\varnothing$-captured). Hence, Corollary
\ref{cor.chip.adj-cycles.captures} (applied to $K=\varnothing$) shows that the
$\ZZ$-configuration $f-\Delta\ell_{1}-\Delta\ell_{2}-\cdots-\Delta\ell_{k}$ is
$\varnothing\cup C_{\ell_{1}}\cup C_{\ell_{2}}\cup\cdots\cup C_{\ell_{k}}%
$-captured. In other words, the $\ZZ$-configuration $f-\Delta\ell_{1}-\Delta\ell
_{2}-\cdots-\Delta\ell_{k}$ is $C$-captured (since $\varnothing\cup
C_{\ell_{1}}\cup C_{\ell_{2}}\cup\cdots\cup C_{\ell_{k}}=C_{\ell_{1}}\cup
C_{\ell_{2}}\cup\cdots\cup C_{\ell_{k}}=C$). Hence, Lemma
\ref{lem.chip.adj-cycles.capture-size} (applied to $f-\Delta\ell_{1}-\Delta\ell
_{2}-\cdots-\Delta\ell_{k}$ and $C$ instead of $f$ and $K$) yields%
\[
\sum\left(  f-\Delta\ell_{1}-\Delta\ell_{2}-\cdots-\Delta\ell_{k}\right)
\geq\left\vert C\right\vert >h.
\]
Since%
\begin{align*}
& \sum\underbrace{\left(  f-\Delta\ell_{1}-\Delta\ell_{2}-\cdots-\Delta
\ell_{k}\right)  }_{=f-\sum_{i=1}^{k}\Delta\ell_{i}}\\
& =\sum\left(  f-\sum_{i=1}^{k}\Delta\ell_{i}\right)  =\sum f-\sum_{i=1}%
^{k}\underbrace{\sum\Delta\ell_{i}}_{\substack{=0\\\text{(since }\sum\Delta
v=0\text{ for each }v\in V\text{)}}}=\sum f-\underbrace{\sum_{i=1}^{k}0}%
_{=0}=\sum f,
\end{align*}
this rewrites as $\sum f>h$. This contradicts $h=\sum f$. This contradiction
completes the solution of Exercise \ref{exe.chip.adj-cycles} \textbf{(b)}.
\end{proof}

Now that we have solved Exercise \ref{exe.chip.adj-cycles} \textbf{(b)}, we
can obtain a second solution to Exercise \ref{exe.chip.adj-cycles}
\textbf{(a)}:

\begin{proof}
[Second solution to Exercise \ref{exe.chip.adj-cycles} \textbf{(a)} (sketched).]
Assume the contrary. Thus, $D$ has more than $\sum f$ vertex-disjoint cycles.
Hence, $D$ has more than $\sum f$ arc-disjoint cycles (since vertex-disjoint
cycles are automatically arc-disjoint). But this contradicts Exercise
\ref{exe.chip.adj-cycles} \textbf{(b)}.  This contradiction completes the
solution of Exercise \ref{exe.chip.adj-cycles} \textbf{(a)}.
\end{proof}

% Here is an old, INCORRECT hint to Exercise \ref{exe.chip.adj-cycles} \textbf{(b)}:
%
% [\textbf{Hint:} Reduce part \textbf{(b)} to part
% \textbf{(a)} by constructing the following
% multidigraph $D'$:
%
% \begin{itemize}
% \item The vertices of $D'$ shall be the vertices of
      % $D$ as well as $\abs{A}$ new vertices.
      % Namely, we add a new vertex $v_a$ for each
      % arc $a \in A$ of $D$.
% \item The arcs of $D'$ are the following:
      % For each arc $a \in A$ of $D$, we build two
      % new arcs $a_1$ and $a_2$ with
      % \begin{align*}
      % \operatorname{s} \tup{a_1} = \operatorname{s} \tup{a};
      % &\qquad
      % \operatorname{t} \tup{a_1} = v_a;
      % \\
      % \operatorname{s} \tup{a_2} = v_a;
      % &\qquad
      % \operatorname{t} \tup{a_2} = \operatorname{t} \tup{a} .
      % \end{align*}
      % The arcs of $D'$ shall be these new arcs $a_1$
      % and $a_2$ for all $a \in A$ (but not the original
      % arcs of $D$).
% \end{itemize}
%
% For each configuration $f$ on $D$, construct a
% configuration $f'$ on $D'$ such that any legal
% sequence for $f$ can be translated into a (longer)
% legal sequence for $f'$.]

\subsection{Exercise \ref{exe.chip.assoc}: an associativity
law for stabilizations}

Recall Definition~\ref{def.chip.stabilization}.

\begin{exercise} \label{exe.chip.assoc}
Let $f : V \to \NN$, $g : V \to \NN$ and $h : V \to \NN$
be three configurations such that both configurations
$f$ and $g + h$ are finitary, and such that the
configuration $f + \tup{g + h}^\circ$ is also finitary.

Prove the following:

\textbf{(a)} The configurations $f + g$ and $h$ are also
finitary.

\textbf{(b)} The configurations $f + g + h$ and
$\tup{f + g}^\circ + h$ are also finitary, and
satisfy
\[
\tup{f + g + h}^\circ
= \tup{f + \tup{g + h}^\circ}^\circ
= \tup{\tup{f + g}^\circ + h}^\circ .
\]
\end{exercise}

In order to solve Exercise \ref{exe.chip.assoc}, we shall use the notations
from Definition \ref{def.firearrow}. We also state a few simple lemmas:

\begin{lemma}
\label{lem.chip.finitary-less}Let $c:V\rightarrow\mathbb{N}$ and
$d:V\rightarrow\mathbb{N}$ be two configurations such that $c+d$ is finitary.
Then, $c$ and $d$ are finitary.
\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.chip.finitary-less} (sketched).]The configuration
$c+d$ is finitary. Thus, there exists a stabilizing sequence $s$ for $c+d$.
Consider this $s$.

Firing the vertices in $s$ (one after the other) transforms the configuration
$c+d$ into a stable $\mathbb{Z}$-configuration $z$ (since $s$ is stabilizing).
Consider this $z$.

The $\mathbb{Z}$-configuration $z$ is stable. In other words, no vertex of $V$
is active in $z$. In other words, $z\left(  v\right)  <\deg^+ v$ for each
$v\in V$. Hence,
\[
\left(  z-d\right)  \left(  v\right)  =z\left(  v\right)
-\underbrace{d\left(  v\right)  }_{\geq0}\leq z\left(  v\right)  < \deg^+ v
\]
for each $v\in V$. In other words, no vertex of $V$ is active in $z-d$. In
other words, the $\mathbb{Z}$-configuration $z-d$ is stable.

But firing the vertices in $s$ (one after the other) transforms the
configuration $c$ into the $\mathbb{Z}$-configuration $z-d$ (since firing the
vertices in $s$ (one after the other) transforms the configuration $c+d$ into
the $\mathbb{Z}$-configuration $z$). Thus, the sequence $s$ is stabilizing for
$c$ (since the $\mathbb{Z}$-configuration $z-d$ is stable). Hence, there
exists a stabilizing sequence for $c$. In other words, $c$ is finitary.
Similarly, $d$ is finitary. This proves Lemma \ref{lem.chip.finitary-less}.
\end{proof}

\begin{lemma}
\label{lem.chip.finitary-arrow}Let $c:V\rightarrow\mathbb{N}$ and
$d:V\rightarrow\mathbb{N}$ be two configurations such that $c\overset{\ast
}{\rightarrow}d$.

\textbf{(a)} If $c$ is finitary, then $d$ is finitary and satisfies $c^{\circ
}=d^{\circ}$.

\textbf{(b)} If $d$ is finitary, then $c$ is finitary and satisfies $c^{\circ
}=d^{\circ}$.
\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.chip.finitary-arrow} (sketched).]From $c\overset{\ast
}{\rightarrow}d$, we conclude that there exists a legal sequence $\ell_{1}$
for $c$ such that firing all vertices in $\ell_{1}$ transforms $c$ into $d$.
Consider this $\ell_{1}$.

\textbf{(b)} Assume that $d$ is finitary. Hence, the stabilization $d^{\circ}$
is well-defined, and is a stable configuration (by the definition of
stabilization). Also, $d^{\circ}$ is obtained from $d$ by firing vertices from
a legal sequence (by the definition of $d^{\circ}$). Hence, $d\overset{\ast
}{\rightarrow}d^{\circ}$. From $c\overset{\ast}{\rightarrow}d\overset{\ast
}{\rightarrow}d^{\circ}$, we obtain $c\overset{\ast}{\rightarrow}d^{\circ}$
(since the relation $\overset{\ast}{\rightarrow}$ is transitive). Since
$d^{\circ}$ is stable, this shows that $c$ is finitary, and that $d^{\circ}$
is the stabilization of $c$.

Now, $c^{\circ}$ is well-defined (since $c$ is finitary) and satisfies
$d^{\circ}=c^{\circ}$ (since $d^{\circ}$ is the stabilization of $c$). In
other words, $c^{\circ}=d^{\circ}$. This proves Lemma
\ref{lem.chip.finitary-arrow} \textbf{(b)}.

\textbf{(a)} Assume that $c$ is finitary.

Let us first show that $d$ is finitary.

Indeed, assume the contrary. Thus, $d$ is infinitary. Hence, there exist
arbitrarily long legal sequences for $d$. In other words, for each
$N\in\mathbb{N}$, there exists a legal sequence for $d$ having length $\geq N$.

Fix $N\in\mathbb{N}$. Then, there exists a legal sequence for $d$ having
length $\geq N$ (as we have just seen). Fix such a legal sequence, and denote
it by $\ell_{2}$.

Write the sequences $\ell_{1}$ and $\ell_{2}$ as $\ell_{1}=\left(  v_{1}%
,v_{2},\ldots,v_{p}\right)  $ and $\ell_{2}=\left(  w_{1},w_{2},\ldots
,w_{q}\right)  $. Let $\ell$ be the sequence $\ell_1 \ast \ell_2
= \left(  v_{1},v_{2},\ldots ,v_{p},w_{1},w_{2},\ldots,w_{q}\right)  $.
(We are using the notation from Definition~\ref{def.concat} here.)
This sequence
$\ell = \ell_1 \ast \ell_2$ is legal for $c$
(by Lemma~\ref{lem.chip.leg-concat1}, applied to
$c$, $\ell_1$, $d$ and $\ell_2$
instead of $f$, $u$, $g$ and $v$).
Moreover, the length of $\ell$ is $\underbrace{p}_{\geq0}+q\geq
q=\left(  \text{the length of }\ell_{2}\right)  \geq N$ (since $\ell_{2}$ has
length $\geq N$). Thus, there exists a legal sequence for $c$ having length
$\geq N$ (namely, $\ell$).

Now, forget that we fixed $N$. We thus have showed that for each
$N\in\mathbb{N}$, there exists a legal sequence for $c$ having length $\geq N$
(namely, $\ell$). In other words, there exist arbitrarily long legal sequences
for $c$. In other words, $c$ is infinitary. This contradicts the fact that $c$
is finitary. This contradiction shows that our assumption was false. Thus, we
have proven that $d$ is finitary.

Lemma \ref{lem.chip.finitary-arrow} \textbf{(b)} thus yields $c^{\circ
}=d^{\circ}$. This proves Lemma \ref{lem.chip.finitary-arrow} \textbf{(a)}.
\end{proof}

\begin{proof}
[Hints to Exercise \ref{exe.chip.assoc}.]For each finitary configuration $k$,
we have%
\begin{equation}
k\overset{\ast}{\rightarrow}k^{\circ} \label{sol.chip.assoc.1}%
\end{equation}
(because $k^{\circ}$ is obtained from $k$ by firing vertices from a legal
sequence). Hence, $g+h\overset{\ast}{\rightarrow}\left(  g+h\right)  ^{\circ}%
$. Thus, Proposition \ref{prop.firearrow.1} \textbf{(b)} (applied to $c=f$ and
$k=g+h$ and $k^{\prime}=\left(  g+h\right)  ^{\circ}$) yields
$f+g+h\overset{\ast}{\rightarrow}f+\left(  g+h\right)  ^{\circ}$.

But the configuration $f+\left(  g+h\right)  ^{\circ}$ is also finitary. Thus,
(\ref{sol.chip.assoc.1}) (applied to $k=f+\left(  g+h\right)  ^{\circ}$)
yields $f+\left(  g+h\right)  ^{\circ}\overset{\ast}{\rightarrow}\left(
f+\left(  g+h\right)  ^{\circ}\right)  ^{\circ}$. Thus,%
\[
f+g+h\overset{\ast}{\rightarrow}f+\left(  g+h\right)  ^{\circ}\overset{\ast
}{\rightarrow}\left(  f+\left(  g+h\right)  ^{\circ}\right)  ^{\circ}.
\]
Since the configuration $\left(  f+\left(  g+h\right)  ^{\circ}\right)
^{\circ}$ is stable, we thus conclude that $f+g+h$ is finitary, and
furthermore that the configuration $\left(  f+\left(  g+h\right)  ^{\circ
}\right)  ^{\circ}$ is the stabilization of $f+g+h$. Thus,
\begin{equation}
\left(  f+g+h\right)  ^{\circ}=\left(  f+\left(  g+h\right)  ^{\circ}\right)
^{\circ}. \label{sol.chip.assoc.4}%
\end{equation}


The configuration $f+g+h$ is finitary. Hence, Lemma
\ref{lem.chip.finitary-less} (applied to $c=f+g$ and $d=h$) shows that the
configurations $f+g$ and $h$ are also finitary. This solves Exercise
\ref{exe.chip.assoc} \textbf{(a)}.

\textbf{(b)} Applying (\ref{sol.chip.assoc.1}) to $k=f+g$, we obtain
$f+g\overset{\ast}{\rightarrow}\left(  f+g\right)  ^{\circ}$. Thus,
Proposition \ref{prop.firearrow.1} \textbf{(b)} (applied to $c=h$ and $k=f+g$
and $k^{\prime}=\left(  f+g\right)  ^{\circ}$) yields $h+f+g\overset{\ast
}{\rightarrow}h+\left(  f+g\right)  ^{\circ}$. Thus, $f+g+h=h+f+g\overset{\ast
}{\rightarrow}h+\left(  f+g\right)  ^{\circ}=\left(  f+g\right)  ^{\circ}+h$.
Hence, Lemma \ref{lem.chip.finitary-arrow} \textbf{(a)} (applied to $c=f+g+h$
and $d=\left(  f+g\right)  ^{\circ}+h$) shows that the configuration $\left(
f+g\right)  ^{\circ}+h$ is finitary and satisfies
\begin{equation}
\left(  f+g+h\right)  ^{\circ}=\left(  \left(  f+g\right)  ^{\circ}+h\right)
^{\circ} \label{sol.chip.assoc.5}%
\end{equation}
(since the configuration $f+g+h$ is finitary). Combining
(\ref{sol.chip.assoc.4}) and (\ref{sol.chip.assoc.5}), we obtain%
\[
\left(  f+g+h\right)  ^{\circ}=\left(  f+\left(  g+h\right)  ^{\circ}\right)
^{\circ}=\left(  \left(  f+g\right)  ^{\circ}+h\right)  ^{\circ}.
\]
This completes the solution of Exercise \ref{exe.chip.assoc} \textbf{(b)}.
\end{proof}

\subsection{Exercise \ref{exe.chip.Z2}: chip-firing on
the integer lattice}

Now, we shall briefly discuss chip-firing on the
integer lattice $\ZZ^2$; this is one of the most famous
cases of chip-firing, leading to some of the pretty
pictures.
For examples and illustrations, check out
\cite{Ellenb15} as well as some of the links above.

We have not defined infinite graphs in class; the
theory of infinite graphs involves some subtleties that
would take us too far.
However, for this particular exercise, we need only a
specific infinite graph, which is fairly simple.

\begin{definition}
\textbf{(a)} A \textit{locally finite multigraph} means
a triple $\tup{V, E, \phi}$, where $V$ and $E$ are sets
and $\phi : E \to \powset[2]{V}$ is a map having the
following property:
\begin{enumerate}
\item[(*)] For each $v \in V$, there exist only finitely
many $e \in E$ satisfying $v \in \phi \tup{e}$.
\end{enumerate}

Most of the concepts defined for (usual) multigraphs still
make sense for locally finite multigraphs.
In particular, the elements of $V$ are called the
vertices, and the elements of $E$ are called the
edges.
The property (*) says that each vertex is contained in
only finitely many edges; this allows us to define
the degree of a vertex.

\textbf{(b)} The \textit{integer lattice} shall mean
the locally finite multigraph defined as follows:
\begin{itemize}
\item The vertices of the integer lattice are the
      pairs $\tup{i, j}$ of two integers $i$ and $j$.
      In other words, the vertex set of the integer
      lattice is
        $\ZZ^2 = \set{ \tup{i, j} \ \mid \ i \in \ZZ
                        \text{ and } j \in \ZZ }$.
      We view these vertices as points in the
      plane, and draw the multigraph accordingly.
\item Two vertices of the integer lattice are
      adjacent if and only if they have distance $1$
      (as points in the plane).
      In other words, a vertex $\tup{i, j}$ is
      adjacent to the four vertices
      $\tup{i+1, j}, \tup{i, j+1}, \tup{i-1, j},
      \tup{i, j-1}$ and no others.
\end{itemize}

\textbf{(c)} You can guess how locally finite
multidigraphs are defined.
Each locally finite multigraph can be regarded as a
locally finite multidigraph by replacing each edge
by a pair of two arcs (directed in both possible
directions).
\end{definition}

Let us show a piece of the integer lattice, viewed as
a locally finite multigraph:
\[
\xymatrix{
& \are[d] & \are[d] & \are[d] & \\
\are[r] & \tup{-1, 1} \are[d] \are[r] & \tup{0, 1} \are[d] \are[r] & \tup{1, 1} \are[d] \are[r] & \\
\are[r] & \tup{-1, 0} \are[d] \are[r] & \tup{0, 0} \are[d] \are[r] & \tup{1, 0} \are[d] \are[r] & \\
\are[r] & \tup{-1, -1} \are[d] \are[r] & \tup{0, -1} \are[d] \are[r] & \tup{1, -1} \are[d] \are[r] & \\
& & & &
}
\]
And here is it again, viewed as a locally finite
multidigraph:
\[
\xymatrix{
& \arebi[d] & \arebi[d] & \arebi[d] & \\
\arebi[r] & \tup{-1, 1} \arebi[d] \arebi[r] & \tup{0, 1} \arebi[d] \arebi[r] & \tup{1, 1} \arebi[d] \arebi[r] & \\
\arebi[r] & \tup{-1, 0} \arebi[d] \arebi[r] & \tup{0, 0} \arebi[d] \arebi[r] & \tup{1, 0} \arebi[d] \arebi[r] & \\
\arebi[r] & \tup{-1, -1} \arebi[d] \arebi[r] & \tup{0, -1} \arebi[d] \arebi[r] & \tup{1, -1} \arebi[d] \arebi[r] & \\
& & & &
}
\]

\begin{exercise} \label{exe.chip.Z2}
Let $f$ be a configuration on the integer lattice
(where we view the integer lattice as a locally
finite multidigraph).
(The notion of a configuration and related notions
are defined in the same way as for usual, finite
multidigraphs.)

Assume that only finitely many vertices $v \in \ZZ^2$
satisfy $f \tup{v} \neq 0$.
(Thus, the total number of chips $\sum f$ is finite.)

An edge $e$ of the integer lattice is
said to be \textit{non-void} in $f$ if and only if
at least one of the endpoints of $e$ has at least one
chip in $f$.

Prove the following:

\textbf{(a)} If an edge of the integer lattice is
non-void in $f$, then this edge remains non-void after
firing any legal sequence of vertices.
(``Firing a sequence'' means firing all the vertices
in the sequence, one after the other.)

\textbf{(b)} The total number of configurations that
can be obtained from $f$ by firing a legal sequence
of vertices is finite.

\textbf{(c)} If we fire any vertex, then the
sum $\sum_{\tup{i, j} \in \ZZ^2} f \tup{\tup{i, j}}
\cdot \tup{i + j}^2$ increases.

\textbf{(d)} The configuration $f$ is finitary (so its
stabilization is well-defined).
\end{exercise}

This exercise gives the reason why pictures such as the
ones in \cite{Ellenb15} exist (although it does not
explain their shapes and patterns).

\begin{proof}
[Hints to Exercise \ref{exe.chip.Z2}.]\textbf{(a)} Recall that we view the
integer lattice as a locally finite multidigraph. Thus, each edge $e$ of the
integer lattice is not an actual edge, but really is two arcs $\left(
u,v\right)  $ and $\left(  v,u\right)  $ (where $u$ and $v$ are its
endpoints). These two arcs form a cycle, which we denote by $c_{e}$ (we choose
arbitrarily which vertex to begin this cycle at). Clearly, $e$ is non-void in
a configuration $f$ if and only if the cycle $c_{e}$ is non-void in $f$ (where
the notion of \textquotedblleft non-void\textquotedblright\ for a cycle is
understood as in Definition \ref{def.chip.cycle-non-void}). Thus, Exercise
\ref{exe.chip.Z2} \textbf{(a)} follows from Lemma
\ref{lem.chip.adj-cycles.cycles-preserve} (at least if we extend the latter
lemma to locally finite multidigraphs).

\textbf{(b)} For each configuration $g$, we shall denote by $S_{g}$ the set
$\left\{  v\in\mathbb{Z}^{2}\ \mid\ g\left(  v\right)  \neq0\right\}  $.
Clearly, if $\sum g$ is finite, then the set $S_{g}$ is finite. Thus, in
particular, the set $S_{g}$ is finite whenever the configuration $g$ is
obtained from $f$ by repeatedly firing vertices.

Now, we make the following observation:

\begin{statement}
\textit{Observation 1:} If a configuration $g^{\prime}$ is obtained from a
configuration $g$ by firing an active vertex, then each $v\in S_{g^{\prime}}$
either belongs to $S_{g}$ or has at least one neighbor in $S_{g}$.
\end{statement}

Observation 1 is easy to check.

Using Observation 1, Exercise \ref{exe.chip.Z2} \textbf{(a)}, and
straightforward induction (over the length of the legal sequence), we can
argue the following observation:

\begin{statement}
\textit{Observation 2:} If a configuration $g^{\prime}$ is obtained from a
configuration $g$ by firing a legal sequence of vertices, then for each $v\in
S_{g^{\prime}}$, there exists a vertex $w\in S_{g}$ and a walk $p$ from $w$ to
$v$ such that each edge of $p$ is non-void in $g^{\prime}$.
\end{statement}

Now, let $h=\sum f$. Define a subset $T$ of $\mathbb{Z}^{2}$ by%
\[
T=\left\{  v\in\mathbb{Z}^{2}\ \mid\ \text{there exists some }w\in S_{f}\text{
such that }d\left( w, v \right)  \leq4h\right\}  .
\]
We call this set $T$ the $4h$\textit{-neighborhood of }$S_{f}$. This set $T$
is finite (since $S_{f}$ is finite).

Let $f^{\prime}$ be a configuration obtained from the configuration $f$ by
firing a legal sequence of vertices. Let $v\in S_{f^{\prime}}$. Then,
Observation 2 (applied to $g=f$ and $g^{\prime}=f^{\prime}$) shows that there
exists a vertex $w\in S_{f}$ and a walk $p$ from $w$ to $v$ such that each
edge of $p$ is non-void in $f^{\prime}$. Consider these $w$ and $p$. We WLOG
assume that the walk $p$ is a path (since otherwise, we can simply remove
cycles from $p$ until $p$ becomes a path). Since $\sum f^{\prime}=\sum f=h$,
there cannot be more than $4h$ edges that are non-void in $f^{\prime}$ (since
each chip makes only $4$ edges non-void, and there can be overlap). Thus, the
path $p$ cannot have more than $4h$ edges (since each edge of $p$ is non-void
in $f^{\prime}$). In other words, the length of the path $p$ is $\leq4h$.
Thus, there exists a path of length $\leq4h$ from $w$ to $v$ (namely, the path
$p$). Hence, $d\left(  w,v\right)  \leq4h$.
Hence, $v\in T$ (by the definition of $T$, because $w\in S_{f}$).

Now, forget that we fixed $v$. We thus have shown that $v\in T$ for each $v\in
S_{f^{\prime}}$. In other words, $S_{f^{\prime}}\subseteq T$. Hence,
$f^{\prime}\left(  v\right)  =0$ for each $v\in\mathbb{Z}^{2}\setminus T$
(because of the definition of $S_{f^{\prime}}$).
Moreover, $f^{\prime}\left(  v\right)  \in\left\{  0,1,\ldots,h\right\}  $ for
each $v\in T$ (since $f^{\prime}\left(  v\right)  \leq\sum f^{\prime}=h$).

Now, forget that we fixed $f^{\prime}$. We thus have proven that each
configuration $f^{\prime}$ obtained from the configuration $f$ by firing a
legal sequence of vertices satisfies
\begin{align*}
f^{\prime}\left(  v\right)   &  =0\qquad \text{for each }%
v\in\mathbb{Z}^{2}\setminus T,\qquad \text{and}\\
f^{\prime}\left(  v\right)   &  \in\left\{  0,1,\ldots,h\right\}
\qquad \text{for each }v\in T.
\end{align*}
Thus, all the configurations $f^{\prime}$ obtained from the configuration $f$ by
firing a legal sequence of vertices can be regarded as maps from $T$ to
$\left\{  0,1,\ldots,h\right\}  $. Of course, there are only finitely many
such maps; thus, there are only finitely many configurations that can be
obtained from $f$ by firing a legal sequence of vertices. This solves Exercise
\ref{exe.chip.Z2} \textbf{(b)}.

\textbf{(c)} Firing a given vertex $\left(  p,q\right)  $ results in four
chips disappearing from this vertex and reappearing on its four adjacent
vertices $\left(  p+1,q\right)  ,\left(  p-1,q\right)  ,\left(  p,q+1\right)
,\left(  p,q-1\right)  $. Thus, the value of $\sum_{\left(  i,j\right)
\in\mathbb{Z}^{2}}f\left(  \left(  i,j\right)  \right)  \cdot\left(
i+j\right)  ^{2}$ increases by%
\[
\left(  \left(  p+1\right)  +q\right)  ^{2}+\left(  \left(  p-1\right)
+q\right)  ^{2}+\left(  p+\left(  q+1\right)  \right)  ^{2}+\left(  p+\left(
q-1\right)  \right)  ^{2}-4\left(  p+q\right)  ^{2}=4.
\]
In particular, it increases. This solves Exercise \ref{exe.chip.Z2}
\textbf{(c)}.

\textbf{(d)} Let $\ell=\left(  \ell_{1},\ell_{2},\ldots,\ell_{k}\right)  $ be
a legal sequence for $f$. Then, for each $i\in\left\{  0,1,\ldots,k\right\}
$, the $\mathbb{Z}$-configuration $f-\Delta\ell_{1}-\Delta\ell_{2}%
-\cdots-\Delta\ell_{i}$ is a configuration; denote this configuration by
$f_{i}$. For each $i\in\left\{  0,1,\ldots,k\right\}  $, the configuration
$f_{i}$ is obtained from $f$ by firing a legal sequence of vertices.

But each $p\in\left\{  1,2,\ldots,k\right\}  $ satisfies
\[
\sum_{\left(  i,j\right)  \in\mathbb{Z}^{2}}f_{p-1}\left(  \left(  i,j\right)
\right)  \cdot\left(  i+j\right)  ^{2}<\sum_{\left(  i,j\right)  \in
\mathbb{Z}^{2}}f_{p}\left(  \left(  i,j\right)  \right)  \cdot\left(
i+j\right)  ^{2}%
\]
(by Exercise \ref{exe.chip.Z2} \textbf{(c)}, because the configuration $f_{p}$
is obtained from $f_{p-1}$ by firing the vertex $\ell_{p}$). Thus, the
sequence%
\[
\left(  \sum_{\left(  i,j\right)  \in\mathbb{Z}^{2}}f_{p}\left(  \left(
i,j\right)  \right)  \cdot\left(  i+j\right)  ^{2}\right)  _{p\in\left\{
0,1,\ldots,k\right\}  }%
\]
is strictly increasing. Hence, its entries are distinct. Thus, the
configurations $f_{0},f_{1},\ldots,f_{k}$ are distinct.

Recall that for each $i\in\left\{  0,1,\ldots,k\right\}  $, the configuration
$f_{i}$ is obtained from $f$ by firing a legal sequence of vertices. But
Exercise \ref{exe.chip.Z2} \textbf{(b)} shows that the total number of such
configurations is finite. Hence, if $k$ is large enough, then two of the
configurations $f_{0},f_{1},\ldots,f_{k}$ are equal. This contradicts the fact
that the configurations $f_{0},f_{1},\ldots,f_{k}$ are distinct. Hence, $k$
cannot be large enough.

Now, forget that we fixed $k$. We thus have shown that if $\ell=\left(
\ell_{1},\ell_{2},\ldots,\ell_{k}\right)  $ is a legal sequence for $f$, then
$k$ cannot be arbitrarily large. In other words, $f$ does not have arbitrarily
long legal sequences. In other words, $f$ is finitary. This solves Exercise
\ref{exe.chip.Z2} \textbf{(d)}.
\end{proof}

\subsection{Exercise \ref{exe.aco.score-vector}: acyclic
orientations are determined by their score vectors}

Now, we leave the chip-firing setting.

Roughly speaking, an \textit{orientation} of
a multigraph $G$ is a way to assign to each edge of $G$
a direction (thus making it an arc).
If the resulting \textbf{digraph} has no cycles, then
this orientation will be called \textit{acyclic}.
A rigorous way to state this definition is the
following:

\begin{definition} \label{def.aco.aco}
Let $G = \tup{V, E, \psi}$ be a multigraph.

\textbf{(a)} An \textit{orientation} of $G$ is a map
$\phi : E \to V \times V$ such that each $e \in E$
has the following property:
If we write $\phi \tup{e}$ in the form
$\phi \tup{e} = \tup{u, v}$, then
$\psi \tup{e} = \set{u, v}$.

\textbf{(b)} An orientation $\phi$ of $G$ is said to
be \textit{acyclic} if and only if the multidigraph
$\tup{V, E, \phi}$ has no cycles.
\end{definition}

\begin{example}
Let $G = \tup{V, E, \psi}$ be the following multigraph:
\[
\xymatrix{
& 2 \are[dl]^a \are@/_2pc/[dl]_b \are[dr]^c \\
1 \are[rr]_d & & 3
}
\]
Then, the following four maps $\phi$ are orientations of $G$:
\begin{itemize}
\item the map sending $a$ to $\tup{1, 2}$, sending $b$ to
      $\tup{1, 2}$, sending $c$ to $\tup{3, 2}$, and
      sending $d$ to $\tup{1, 3}$;
\item the map sending $a$ to $\tup{2, 1}$, sending $b$ to
      $\tup{1, 2}$, sending $c$ to $\tup{3, 2}$, and
      sending $d$ to $\tup{3, 1}$;
\item the map sending $a$ to $\tup{1, 2}$, sending $b$ to
      $\tup{1, 2}$, sending $c$ to $\tup{2, 3}$, and
      sending $d$ to $\tup{1, 3}$;
\item the map sending $a$ to $\tup{1, 2}$, sending $b$ to
      $\tup{1, 2}$, sending $c$ to $\tup{2, 3}$, and
      sending $d$ to $\tup{3, 1}$.
\end{itemize}
Here are the multidigraphs $\tup{V, E, \phi}$ corresponding to
these four maps (in the order mentioned):
\[
\begin{tabular}{|c|c|c|c|}
\xymatrix{
& 2 \ar@{<-}[dl]^a \ar@{<-}@/_2pc/[dl]_b \ar@{<-}[dr]^c \\
1 \ar[rr]_d & & 3
} &
\xymatrix{
& 2 \ar[dl]^a \ar@{<-}@/_2pc/[dl]_b \ar@{<-}[dr]^c \\
1 \ar@{<-}[rr]_d & & 3
} &
\xymatrix{
& 2 \ar@{<-}[dl]^a \ar@{<-}@/_2pc/[dl]_b \ar[dr]^c \\
1 \ar[rr]_d & & 3
} &
\xymatrix{
& 2 \ar@{<-}[dl]^a \ar@{<-}@/_2pc/[dl]_b \ar[dr]^c \\
1 \ar@{<-}[rr]_d & & 3
}
\end{tabular}
\]
Only the first and the third of these orientations
$\phi$ are acyclic (since only the first and the third
of these multidigraphs have no cycles).
\end{example}

\begin{exercise} \label{exe.aco.score-vector}
Let $G = \tup{V, E, \psi}$ be a multigraph.

Prove the following:

\textbf{(a)} If $\phi$ is any acyclic orientation of $G$,
and if $V \neq \varnothing$,
then there exists a $v \in V$ such that no arc of the
multidigraph $\tup{V, E, \phi}$ has target $v$.

\textbf{(b)} If $\phi_1$ and $\phi_2$ are two acyclic orientations
of $G$ such that each $v \in V$ satisfies
\[
\deg^+_{\tup{V, E, \phi_1}} v = \deg^+_{\tup{V, E, \phi_2}} v ,
\]
then $\phi_1 = \phi_2$.
\end{exercise}

Our solution to Exercise \ref{exe.aco.score-vector} uses the
following fact:

\begin{proposition} \label{prop.mt3.deg-cycle-muldir}
Let $D = \tup{V, A, \phi}$ be a multidigraph with $\abs{V} > 0$.
Assume that each vertex $v \in V$ satisfies $\deg^- v > 0$. 
Then, $D$ has at least one cycle.
\end{proposition}

\begin{proof}[Proof of Proposition~\ref{prop.mt3.deg-cycle-muldir}.]
Proposition~\ref{prop.mt3.deg-cycle-muldir} is simply the
obvious generalization of
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17s/mt1s.pdf}{Exercise 3 on
Midterm 1} to multidigraphs;
it is proven in precisely the same way.
\end{proof}

\begin{proof}
[Hints to Exercise \ref{exe.aco.score-vector}.]\textbf{(a)} Let $\phi$ be any
acyclic orientation of $G$. Thus, the multidigraph $\left(  V,E,\phi\right)  $
has no cycles.

Assume that $V\neq\varnothing$. Then, $\left\vert V\right\vert >0$.

If each vertex $v\in V$ satisfies $\deg_{\left(  V,E,\phi\right)  }^{-}v>0$,
then the multidigraph $\left(  V,E,\phi\right)  $ has at least one
cycle\footnote{This follows from
Proposition~\ref{prop.mt3.deg-cycle-muldir} (applied to
$\tup{V, E, \phi}$ and $E$ instead of $D$ and $A$).}.
Therefore, not each vertex $v\in V$ satisfies $\deg_{\left(
V,E,\phi\right)  }^{-}v>0$ (because the multidigraph $\left(  V,E,\phi\right)
$ has no cycles). In other words, there exists a vertex $v\in V$ satisfying
$\deg_{\left(  V,E,\phi\right)  }^{-}v=0$. In other words, there exists a
$v\in V$ such that no arc of the multidigraph $\left(  V,E,\phi\right)  $ has
target $v$. This solves Exercise \ref{exe.aco.score-vector} \textbf{(a)}.

\textbf{(b)} We shall solve Exercise \ref{exe.aco.score-vector} \textbf{(b)}
by induction over $\left\vert V\right\vert $.

The \textit{induction base} (the case when $\left\vert V\right\vert =0$) is
obvious (because in this case there are no edges, and thus there is only one
possible orientation).

Now, we come to the \textit{induction step}: Let $N\in\mathbb{N}$ be positive.
Assume (as the induction hypothesis) that Exercise \ref{exe.aco.score-vector}
\textbf{(b)} holds whenever $\left\vert V\right\vert =N-1$. We must now prove
that Exercise \ref{exe.aco.score-vector} \textbf{(b)} also holds whenever
$\left\vert V\right\vert =N$.

So let $G$, $V$, $E$ and $\psi$ be as in Exercise \ref{exe.aco.score-vector}
\textbf{(b)}, and assume that $\left\vert V\right\vert =N$. Let $\phi_{1}$ and
$\phi_{2}$ be two acyclic orientations of $G$ such that each $v\in V$
satisfies
\begin{equation}
\deg_{\left(  V,E,\phi_{1}\right)  }^{+}v=\deg_{\left(  V,E,\phi_{2}\right)
}^{+}v. \label{sol.aco.score-vector.b.1}%
\end{equation}
We must then prove that $\phi_{1}=\phi_{2}$.

We have $\left\vert V\right\vert =N>0$, thus $V\neq\varnothing$. Hence,
Exercise \ref{exe.aco.score-vector} \textbf{(a)} (applied to $\phi=\phi_{1}$)
shows that there exists a $v\in V$ such that no arc of the multidigraph
$\left(  V,E,\phi_{1}\right)  $ has target $v$. Fix such a $v$, and denote it
by $w$. Thus, no arc of the multidigraph $\left(  V,E,\phi_{1}\right)  $ has
target $w$. Hence, $\deg_{\left(  V,E,\phi_{1}\right)  }^{-}w=0$.

But $\phi_{1}$ is an orientation of $G$. Hence, some of the edges of $G$ that
contain $w$ become arcs with source $w$ in $\phi_{1}$, whereas the remaining
edges of $G$ that contain $w$ become arcs with target $w$ in $\phi_{1}$.
Therefore,
\begin{equation}
\deg_{\left(  V,E,\phi_{1}\right)  }^{-}w+\deg_{\left(  V,E,\phi_{1}\right)
}^{+}w=\deg_{G}w. \label{sol.aco.score-vector.b.deg+deg1}%
\end{equation}
Similarly,%
\begin{equation}
\deg_{\left(  V,E,\phi_{2}\right)  }^{-}w+\deg_{\left(  V,E,\phi_{2}\right)
}^{+}w=\deg_{G}w. \label{sol.aco.score-vector.b.deg+deg2}%
\end{equation}


Now, (\ref{sol.aco.score-vector.b.deg+deg1}) yields%
\[
\deg_{G}w=\underbrace{\deg_{\left(  V,E,\phi_{1}\right)  }^{-}w}_{=0}%
+\deg_{\left(  V,E,\phi_{1}\right)  }^{+}w=\deg_{\left(  V,E,\phi_{1}\right)
}^{+}w=\deg_{\left(  V,E,\phi_{2}\right)  }^{+}w
\]
(by (\ref{sol.aco.score-vector.b.1}), applied to $v=w$). Hence,%
\[
\deg_{\left(  V,E,\phi_{2}\right)  }^{+}w=\deg_{G}w=\deg_{\left(  V,E,\phi
_{2}\right)  }^{-}w+\deg_{\left(  V,E,\phi_{2}\right)  }^{+}%
w\qquad \left(  \text{by (\ref{sol.aco.score-vector.b.deg+deg2}%
)}\right)  .
\]
Subtracting $\deg_{\left(  V,E,\phi_{2}\right)  }^{+}w$ from both sides of
this equality, we find $0=\deg_{\left(  V,E,\phi_{2}\right)  }^{-}w$. Hence,
no arc of the multidigraph $\left(  V,E,\phi_{2}\right)  $ has target $w$.

Now, we see that
\begin{equation}
\text{each edge }e\text{ of }G\text{ satisfying }w\in\psi\left(  e\right)
\text{ satisfies }\phi_{1}\left(  e\right)  =\phi_{2}\left(  e\right)
\label{sol.aco.score-vector.b.wine}%
\end{equation}
\footnote{\textit{Proof of (\ref{sol.aco.score-vector.b.wine}):} Let $e$ be an
edge of $G$ satisfying $w\in\psi\left(  e\right)  $. Write $\psi\left(
e\right)  $ in the form $\psi\left(  e\right)  =\left\{  u,w\right\}  $ for
some $u\in V$. Then, $\phi_{1}\left(  e\right)  $ is either $\left(
u,w\right)  $ or $\left(  w,u\right)  $. But since no arc of the multidigraph
$\left(  V,E,\phi_{1}\right)  $ has target $w$, we cannot have $\phi
_{1}\left(  e\right)  =\left(  u,w\right)  $. Hence, we have $\phi_{1}\left(
e\right)  =\left(  w,u\right)  $. Similarly, $\phi_{2}\left(  e\right)
=\left(  w,u\right)  $ (since no arc of the multidigraph $\left(  V,E,\phi
_{2}\right)  $ has target $w$). Hence, $\phi_{1}\left(  e\right)  =\left(
w,u\right)  =\phi_{2}\left(  e\right)  $. This proves
(\ref{sol.aco.score-vector.b.wine}).}.

On the other hand, let $G^{\prime}=\left(  V^{\prime},E^{\prime},\psi^{\prime
}\right)  $ be the multigraph obtained from $G$ by removing the vertex $w$ and
all edges containing $w$. (Thus, $V^{\prime}=V\setminus\left\{  w\right\}  $,
$E^{\prime}=\left\{  e\in E\ \mid\ w\notin\psi\left(  e\right)  \right\}  $
and $\psi^{\prime}=\psi\mid_{E^{\prime}}$.) Notice that $\left\vert V^{\prime
}\right\vert =\left\vert V\setminus\left\{  w\right\}  \right\vert
=\underbrace{\left\vert V\right\vert }_{=N}-1=N-1$.

Let $\phi_{1}^{\prime}$ and $\phi_{2}^{\prime}$ be the two orientations of the
multigraph $G^{\prime}$ obtained by restricting $\phi_{1}$ and $\phi_{2}$.
(Thus, $\phi_{1}^{\prime}=\phi_{1}\mid_{E^{\prime}}$ and $\phi_{2}^{\prime
}=\phi_{2}\mid_{E^{\prime}}$.) Clearly, the orientation $\phi_{1}^{\prime}$ is
acyclic (since each cycle of the multidigraph $\left(  V^{\prime},E^{\prime
},\phi_{1}^{\prime}\right)  $ would be a cycle of the multidigraph $\left(
V,E,\phi_{1}\right)  $, but the latter multidigraph has no cycles since
$\phi_{1}$ is acyclic). Similarly, the orientation $\phi_{2}^{\prime}$ is acyclic.

Each $v\in V^{\prime}$ satisfies%
\[
\deg_{\left(  V^{\prime},E^{\prime},\phi_{1}^{\prime}\right)  }^{+}%
v=\deg_{\left(  V^{\prime},E^{\prime},\phi_{2}^{\prime}\right)  }^{+}v
\]
\footnote{\textit{Proof.} Let $v\in V^{\prime}$. Thus, $v\in V^{\prime
}=V\setminus\left\{  w\right\}  $, so that $v\in V$ and $v\neq w$.
\par
Now, recall that no arc of the multidigraph $\left(  V,E,\phi_{1}\right)  $
has target $w$. Hence, each arc of the multidigraph $\left(  V,E,\phi
_{1}\right)  $ having source $v$ is also an arc of the multidigraph $\left(
V^{\prime},E^{\prime},\phi_{1}^{\prime}\right)  $. Therefore, the arcs of the
multidigraph $\left(  V,E,\phi_{1}\right)  $ having source $v$ are precisely
the arcs of the multidigraph $\left(  V^{\prime},E^{\prime},\phi_{1}^{\prime
}\right)  $ having source $v$. Therefore, $\deg_{\left(  V^{\prime},E^{\prime
},\phi_{1}^{\prime}\right)  }^{+}v=\deg_{\left(  V,E,\phi_{1}\right)  }^{+}v$.
Similarly, $\deg_{\left(  V^{\prime},E^{\prime},\phi_{2}^{\prime}\right)
}^{+}v=\deg_{\left(  V,E,\phi_{2}\right)  }^{+}v$. Now,%
\begin{align*}
\deg_{\left(  V^{\prime},E^{\prime},\phi_{1}^{\prime}\right)  }^{+}v  &
=\deg_{\left(  V,E,\phi_{1}\right)  }^{+}v=\deg_{\left(  V,E,\phi_{2}\right)
}^{+}v\qquad \left(  \text{by (\ref{sol.aco.score-vector.b.1}%
)}\right) \\
&  =\deg_{\left(  V^{\prime},E^{\prime},\phi_{2}^{\prime}\right)  }^{+}v,
\end{align*}
qed.}. Hence, the induction hypothesis (applied to $G^{\prime}$, $V^{\prime}$,
$E^{\prime}$, $\psi^{\prime}$, $\phi_{1}^{\prime}$ and $\phi_{2}^{\prime}$
instead of $G$, $V$, $E$, $\psi$, $\phi_{1}$ and $\phi_{2}$) shows that
$\phi_{1}^{\prime}=\phi_{2}^{\prime}$ (since $\left\vert V^{\prime}\right\vert
=N-1$).

Thus,%
\begin{equation}
\text{each edge }e\text{ of }G\text{ satisfying }w\notin\psi\left(  e\right)
\text{ satisfies }\phi_{1}\left(  e\right)  =\phi_{2}\left(  e\right)
\label{sol.aco.score-vector.b.wnine}%
\end{equation}
\footnote{\textit{Proof of (\ref{sol.aco.score-vector.b.wnine}):} Let $e$ be
an edge of $G$ satisfying $w\notin\psi\left(  e\right)  $. Then, $e$ is an
edge of the multigraph $G^{\prime}$ (by the definition of $G^{\prime}$).
Hence, $\phi_{1}^{\prime}\left(  e\right)  $ and $\phi_{2}^{\prime}\left(
e\right)  $ are well-defined. Moreover, $\phi_{1}^{\prime}$ is a restriction
of $\phi_{1}$; hence, $\phi_{1}^{\prime}\left(  e\right)  =\phi_{1}\left(
e\right)  $. Similarly, $\phi_{2}^{\prime}\left(  e\right)  =\phi_{2}\left(
e\right)  $. Now, $\phi_{1}\left(  e\right)  =\underbrace{\phi_{1}^{\prime}%
}_{=\phi_{2}^{\prime}}\left(  e\right)  =\phi_{2}^{\prime}\left(  e\right)
=\phi_{2}\left(  e\right)  $. This proves (\ref{sol.aco.score-vector.b.wnine}%
).}. Combining this with (\ref{sol.aco.score-vector.b.wine}), we conclude that
each edge $e$ of $G$ satisfies $\phi_{1}\left(  e\right)  =\phi_{2}\left(
e\right)  $. In other words, we have $\phi_{1}=\phi_{2}$.

Thus, we have proven that Exercise \ref{exe.aco.score-vector} \textbf{(b)}
also holds whenever $\left\vert V\right\vert =N$. This completes the induction
step. Hence, Exercise \ref{exe.aco.score-vector} \textbf{(b)} is solved.
\end{proof}

[\textit{Remark:}
Exercise \ref{exe.aco.score-vector} \textbf{(b)} remains valid
even if we don't require the orientation $\phi_2$ to be acyclic.
The above solution to this exercise still works in this
generality (mutatis mutandis).]

\subsection{Exercise \ref{exe.flows-cuts.cut-lattice}: the
lattice structure on minimum cuts}

Let us recall some terminology from
\cite{lec16}:

\begin{itemize}
\item A \textit{network} consists of:
      \begin{itemize}
      \item a simple digraph $\tup{V, A}$;
      \item two distinct vertices $s \in V$ and $t \in V$,
            called the \textit{source} and the \textit{sink},
            respectively (although we do not require $s$ to
            have indegree $0$ or $t$ to have outdegree $0$);
      \item a function $c : A \to \QQ_+$, called the
            \textit{capacity function}.
            (Here, $\QQ_+$ means the set
            $\set{ x \in \QQ \mid x \geq 0 }$.)
      \end{itemize}

\item Given a network consisting of a digraph
      $\tup{V, A}$, a source $s \in V$ and a sink $t \in V$,
      and a capacity function $c : A \to \QQ_+$, we define
      the following notations:
      \begin{itemize}
      \item For any subset $S$ of $V$, we let $\overline{S}$
            denote the subset $V \setminus S$ of $V$.
      \item If $P$ and $Q$ are two subsets of $V$, then
            $\ive{P, Q}$ shall mean the set of all arcs
            $a \in A$ whose source belongs to $P$ and whose
            target belongs to $Q$.
            (In other words,
            $\ive{P, Q} = A \cap \tup{P \times Q}$.)
      \item If $P$ and $Q$ are two subsets of $V$, then the
            number $c \tup{P, Q} \in \QQ_+$ is defined by
            \[
            c \tup{P, Q} = \sum_{a \in \ive{P, Q}} c \tup{a} .
            \]
      \end{itemize}
\end{itemize}

We also refer to lecture 16 \cite{lec16} for the definition of a flow
(which is not necessary for the following problem, but may
be helpful).

\begin{exercise} \label{exe.flows-cuts.cut-lattice}
Consider a network consisting of a simple digraph
$\tup{V, A}$, a source $s \in V$ and a sink $t \in V$,
and a capacity function $c : A \to \QQ_+$
such that $s \neq t$.

An \textit{$s$-$t$-cutting subset} shall mean a subset
$S$ of $V$ satisfying $s \in S$ and $t \notin S$.

Let $m$ denote the minimum possible value of
$c \tup{S, \overline{S}}$ where $S$ ranges over the
$s$-$t$-cutting subsets.
(Recall that this is the maximum value of a
flow, according to the
maximum-flow-minimum-cut theorem.)

An $s$-$t$-cutting subset $S$ is said to be
\textit{cut-minimal} if it satisfies
$c \tup{S, \overline{S}} = m$.

Let $X$ and $Y$ be two cut-minimal $s$-$t$-cutting subsets.
Prove that $X \cap Y$ and $X \cup Y$ also are
cut-minimal $s$-$t$-cutting subsets.
\end{exercise}

Exercise~\ref{exe.flows-cuts.cut-lattice} is not new;
it appears, e.g., in \cite[Corollary 3]{PicQue80}\footnote{To
  be fully precise, the version in
  \cite[Corollary 3]{PicQue80} differs by having $c$ be
  a map $A \to \RR_{> 0}$ (where $\RR_{> 0}$ is the set of
  all positive reals) instead of having $c$ be a map
  $A \to \QQ_+$. But the difference is unsubstantial,
  and roughly the same proofs work for both results.}.

In our solution of Exercise \ref{exe.flows-cuts.cut-lattice}, we shall use
some further material from
\cite{lec16}. Namely, we shall use the concept of flows, and the following fact:

\begin{lemma}
\label{lem.flows-cuts.flow-estimate}Consider a network consisting of a
simple digraph
$\left(  V,A\right)  $, a source $s\in V$ and a sink $t\in V$, and a capacity
function $c:A\rightarrow\mathbb{Q}_{+}$ such that $s\neq t$. Let $f$ be a flow
on this network.

Let $S$ be a subset of $V$ satisfying $s\in S$ and $t\notin S$.

\textbf{(a)} We have $\left\vert f\right\vert \leq c\left(  S,\overline
{S}\right)  $.

\textbf{(b)} We have $\left\vert f\right\vert =c\left(  S,\overline{S}\right)
$ if and only if
\begin{equation}
\left(  \text{each }a\in\left[  \overline{S},S\right]  \text{ satisfies
}f\left(  a\right)  =0\right)  \label{eq.lem.flows-cuts.flow-estimate.b.1}
\end{equation}
and
\begin{equation}
\left(  \text{each }a\in\left[  S,\overline{S}\right]  \text{ satisfies
}f\left(  a\right)  =c\left(  a\right)  \right)
.\label{eq.lem.flows-cuts.flow-estimate.b.2}%
\end{equation}

\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.flows-cuts.flow-estimate} (sketched).]\textbf{(a)}
This is precisely \cite[Proposition 1.7 \textbf{(c)}]{lec16}.

\textbf{(b)} This is precisely \cite[Proposition 1.7 \textbf{(d)}]{lec16}.
\end{proof}

\begin{proof}
[Hints to Exercise \ref{exe.flows-cuts.cut-lattice}.]From the
max-flow-min-cut-theorem (specifically, \cite[Theorem 1.10]{lec16}), we know
that%
\begin{align*}
 \max\left\{  \left\vert f\right\vert \ \mid\ f\text{ is a flow}\right\}
&  =\min\left\{  c\left(  S,\overline{S}\right)  \ \mid
\ \underbrace{S\subseteq V\text{; }s\in S\text{; }t\notin S}%
_{\Longleftrightarrow\ \left(  S\text{ is an }s\text{-}t\text{-cutting subset
of }V\right)  }\right\} \\
&  =\min\left\{  c\left(  S,\overline{S}\right)  \ \mid\ S\text{ is an
}s\text{-}t\text{-cutting subset of }V\right\} \\
&  =m\qquad \left(  \text{by the definition of }m\right)  .
\end{align*}
Hence, there exists a flow $f$ with $\left\vert f\right\vert =m$. Consider
such an $f$.

The subset $X$ is $s$-$t$-cutting; thus, $X$ is a subset of $V$ satisfying
$s\in X$ and $t\notin X$.

The subset $Y$ is $s$-$t$-cutting; thus, $Y$ is a subset of $V$ satisfying
$s\in Y$ and $t\notin Y$.

We have $c\left(  X,\overline{X}\right)  =m$ (since $X$ is cut-minimal) and
$c\left(  Y,\overline{Y}\right)  =m$ (since $Y$ is cut-minimal). Thus,
$\left\vert f\right\vert =m=c\left(  X,\overline{X}\right)  $ and $\left\vert
f\right\vert =m=c\left(  Y,\overline{Y}\right)  $.

We have $s\in X\cap Y$ (since $s\in X$ and $s\in Y$) and $s\in X\cup Y$
(likewise). We have $t\notin X\cup Y$ (since $t\notin X$ and $t\notin Y$) and
$t\notin X\cap Y$ (likewise). The subset $X\cap Y$ of $V$ is $s$-$t$-cutting
(since $s\in X\cap Y$ and $t\notin X\cap Y$). Similarly, the subset $X\cup Y$
of $V$ is $s$-$t$-cutting.

Lemma \ref{lem.flows-cuts.flow-estimate} \textbf{(b)} (applied to $S=X$) shows
that $\left\vert f\right\vert =c\left(  X,\overline{X}\right)  $ if and only
if
\begin{equation}
\left(  \text{each }a\in\left[  \overline{X},X\right]  \text{ satisfies
}f\left(  a\right)  =0\right)  \label{sol.flows-cuts.cut-lattice.X1}%
\end{equation}
and%
\begin{equation}
\left(  \text{each }a\in\left[  X,\overline{X}\right]  \text{ satisfies
}f\left(  a\right)  =c\left(  a\right)  \right)
.\label{sol.flows-cuts.cut-lattice.X2}%
\end{equation}
Therefore, (\ref{sol.flows-cuts.cut-lattice.X1}) and
(\ref{sol.flows-cuts.cut-lattice.X2}) hold (since $\left\vert f\right\vert
=c\left(  X,\overline{X}\right)  $).

Lemma \ref{lem.flows-cuts.flow-estimate} \textbf{(b)} (applied to $S=Y$) shows
that $\left\vert f\right\vert =c\left(  Y,\overline{Y}\right)  $ if and only
if
\begin{equation}
\left(  \text{each }a\in\left[  \overline{Y},Y\right]  \text{ satisfies
}f\left(  a\right)  =0\right)  \label{sol.flows-cuts.cut-lattice.Y1}%
\end{equation}
and%
\begin{equation}
\left(  \text{each }a\in\left[  Y,\overline{Y}\right]  \text{ satisfies
}f\left(  a\right)  =c\left(  a\right)  \right)
.\label{sol.flows-cuts.cut-lattice.Y2}%
\end{equation}
Therefore, (\ref{sol.flows-cuts.cut-lattice.Y1}) and
(\ref{sol.flows-cuts.cut-lattice.Y2}) hold (since $\left\vert f\right\vert
=c\left(  Y,\overline{Y}\right)  $).

Now,
\begin{equation}
\left(  \text{each }a\in\left[  \overline{X\cap Y},X\cap Y\right]  \text{
satisfies }f\left(  a\right)  =0\right)
\label{sol.flows-cuts.cut-lattice.cap1}%
\end{equation}
\footnote{\textit{Proof of (\ref{sol.flows-cuts.cut-lattice.cap1}):} Let
$a\in\left[  \overline{X\cap Y},X\cap Y\right]  $. We must prove that
$f\left(  a\right)  =0$.
\par
We have $a\in\left[  \overline{X\cap Y},X\cap Y\right]  $. Thus, $a=\left(
u,v\right)  $ for some $u\notin X\cap Y$ and $v\in X\cap Y$. Consider these
$u$ and $v$.
\par
We have $v\in X\cap Y\subseteq Y$. Hence, if $u\notin Y$, then $\left(
u,v\right)  \in\left[  \overline{Y},Y\right]  $. Thus, if $u\notin Y$, then
$a=\left(  u,v\right)  \in\left[  \overline{Y},Y\right]  $. Therefore, if
$u\notin Y$, then (\ref{sol.flows-cuts.cut-lattice.Y1}) shows that $f\left(
a\right)  =0$. Thus, for the rest of this proof, we WLOG assume that $u\notin
Y$ does not hold. Hence, $u\in Y$. Now, $u\in Y$ but $u\notin X\cap Y$. Hence,
$u\in Y\setminus\left(  X\cap Y\right)  =Y\setminus X$, so that $u\notin X$.
But $v\in X\cap Y\subseteq X$. Hence, $\left(  u,v\right)  \in\left[
\overline{X},X\right]  $, so that $a=\left(  u,v\right)  \in\left[
\overline{X},X\right]  $. Thus, (\ref{sol.flows-cuts.cut-lattice.X1}) shows
that $f\left(  a\right)  =0$. This proves
(\ref{sol.flows-cuts.cut-lattice.cap1}).} and%
\begin{equation}
\left(  \text{each }a\in\left[  X\cap Y,\overline{X\cap Y}\right]  \text{
satisfies }f\left(  a\right)  =c\left(  a\right)  \right)
\label{sol.flows-cuts.cut-lattice.cap2}%
\end{equation}
\footnote{\textit{Proof of (\ref{sol.flows-cuts.cut-lattice.cap2}):} Let
$a\in\left[  X\cap Y,\overline{X\cap Y}\right]  $. We must prove that
$f\left(  a\right)  =c\left(  a\right)  $.
\par
We have $a\in\left[  X\cap Y,\overline{X\cap Y}\right]  $. Thus, $a=\left(
u,v\right)  $ for some $u\in X\cap Y$ and $v\notin X\cap Y$. Consider these
$u$ and $v$.
\par
We have $u\in X\cap Y\subseteq Y$. Hence, if $v\notin Y$, then $\left(
u,v\right)  \in\left[  Y,\overline{Y}\right]  $. Thus, if $v\notin Y$, then
$a=\left(  u,v\right)  \in\left[  Y,\overline{Y}\right]  $. Therefore, if
$v\notin Y$, then $f\left(  a\right)  =c\left(  a\right)  $ follows
immediately from (\ref{sol.flows-cuts.cut-lattice.Y2}). Thus, for the rest of
this proof, we WLOG assume that $v\notin Y$ does not hold. Hence, $v\in Y$.
Now, $v\in Y$ but $v\notin X\cap Y$. Hence, $v\in Y\setminus\left(  X\cap
Y\right)  =Y\setminus X$, so that $v\notin X$. But $u\in X\cap Y\subseteq X$.
Hence, $\left(  u,v\right)  \in\left[  X,\overline{X}\right]  $. Thus,
$a=\left(  u,v\right)  \in\left[  X,\overline{X}\right]  $. Hence,
(\ref{sol.flows-cuts.cut-lattice.X2}) shows that $f\left(  a\right)  =c\left(
a\right)  $. This proves (\ref{sol.flows-cuts.cut-lattice.cap2}).}.

But Lemma \ref{lem.flows-cuts.flow-estimate} \textbf{(b)} (applied to $S=X\cap
Y$) shows that $\left\vert f\right\vert =c\left(  X\cap Y,\overline{X\cap
Y}\right)  $ if and only if (\ref{sol.flows-cuts.cut-lattice.cap1}) and
(\ref{sol.flows-cuts.cut-lattice.cap2}) hold. Hence, $\left\vert f\right\vert
=c\left(  X\cap Y,\overline{X\cap Y}\right)  $ (since
(\ref{sol.flows-cuts.cut-lattice.cap1}) and
(\ref{sol.flows-cuts.cut-lattice.cap2}) hold). Thus, $c\left(  X\cap
Y,\overline{X\cap Y}\right)  =\left\vert f\right\vert =m$. In other words, the
$s$-$t$-cutting subset $X\cap Y$ of $V$ is cut-minimal.

Furthermore,
\begin{equation}
\left(  \text{each }a\in\left[  \overline{X\cup Y},X\cup Y\right]  \text{
satisfies }f\left(  a\right)  =0\right)
\label{sol.flows-cuts.cut-lattice.cup1}%
\end{equation}
\footnote{\textit{Proof of (\ref{sol.flows-cuts.cut-lattice.cup1}):} Let
$a\in\left[  \overline{X\cup Y},X\cup Y\right]  $. We must prove that
$f\left(  a\right)  =0$.
\par
We have $a\in\left[  \overline{X\cup Y},X\cup Y\right]  $. In other words,
$a=\left(  u,v\right)  $ for some $u\notin X\cup Y$ and $v\in X\cup Y$.
Consider these $u$ and $v$.
\par
From $u\notin X\cup Y$, we obtain $u\notin X$ and $u\notin Y$. Hence, if $v\in
X$, then $\left(  u,v\right)  \in\left[  \overline{X},X\right]  $. Thus, if
$v\in X$, then $a=\left(  u,v\right)  \in\left[  \overline{X},X\right]  $.
Hence, if $v\in X$, then $f\left(  a\right)  =0$ follows immediately from
(\ref{sol.flows-cuts.cut-lattice.X1}). Thus, for the rest of this proof, we
WLOG assume that $v\in X$ does not hold. Hence, $v\notin X$. Now, $v\in X\cup
Y$ but $v\notin X$. Hence, $v\in\left(  X\cup Y\right)  \setminus X=Y\setminus
X\subseteq Y$. But $u\notin Y$. Thus, $\left(  u,v\right)  \in\left[
\overline{Y},Y\right]  $. Therefore, $a=\left(  u,v\right)  \in\left[
\overline{Y},Y\right]  $. Hence, (\ref{sol.flows-cuts.cut-lattice.Y1}) shows
that $f\left(  a\right)  =0$. This proves
(\ref{sol.flows-cuts.cut-lattice.cup1}).} and%
\begin{equation}
\left(  \text{each }a\in\left[  X\cup Y,\overline{X\cup Y}\right]  \text{
satisfies }f\left(  a\right)  =c\left(  a\right)  \right)
\label{sol.flows-cuts.cut-lattice.cup2}%
\end{equation}
\footnote{\textit{Proof of (\ref{sol.flows-cuts.cut-lattice.cup2}):} Let
$a\in\left[  X\cup Y,\overline{X\cup Y}\right]  $. We must prove that
$f\left(  a\right)  =c\left(  a\right)  $.
\par
We have $a\in\left[  X\cup Y,\overline{X\cup Y}\right]  $. In other words,
$a=\left(  u,v\right)  $ for some $u\in X\cup Y$ and $v\notin X\cup Y$.
Consider these $u$ and $v$.
\par
From $v\notin X\cup Y$, we obtain $v\notin X$ and $v\notin Y$. Hence, if $u\in
X$, then $\left(  u,v\right)  \in\left[  X,\overline{X}\right]  $. Thus, if
$u\in X$, then $a=\left(  u,v\right)  \in\left[  X,\overline{X}\right]  $.
Therefore, if $u\in X$, then $f\left(  a\right)  =c\left(  a\right)  $ follows
immediately from (\ref{sol.flows-cuts.cut-lattice.X2}). Thus, for the rest of
this proof, we WLOG assume that $u\in X$ does not hold. Hence, $u\notin X$.
Now, $u\in X\cup Y$ but $u\notin X$. Hence, $u\in\left(  X\cup Y\right)
\setminus X=Y\setminus X\subseteq Y$. But $v\notin Y$. Thus, $\left(
u,v\right)  \in\left[  Y,\overline{Y}\right]  $. Now, $a=\left(  u,v\right)
\in\left[  Y,\overline{Y}\right]  $. Hence,
(\ref{sol.flows-cuts.cut-lattice.Y2}) shows that $f\left(  a\right)  =c\left(
a\right)  $. This proves (\ref{sol.flows-cuts.cut-lattice.cup2}).}.

But Lemma \ref{lem.flows-cuts.flow-estimate} \textbf{(b)} (applied to $S=X\cup
Y$) shows that $\left\vert f\right\vert =c\left(  X\cup Y,\overline{X\cup
Y}\right)  $ if and only if (\ref{sol.flows-cuts.cut-lattice.cup1}) and
(\ref{sol.flows-cuts.cut-lattice.cup2}) hold. Hence, $\left\vert f\right\vert
=c\left(  X\cup Y,\overline{X\cup Y}\right)  $ (since
(\ref{sol.flows-cuts.cut-lattice.cup1}) and
(\ref{sol.flows-cuts.cut-lattice.cup2}) hold). Thus, $c\left(  X\cup
Y,\overline{X\cup Y}\right)  =\left\vert f\right\vert =m$. In other words, the
$s$-$t$-cutting subset $X\cup Y$ of $V$ is cut-minimal. Exercise
\ref{exe.flows-cuts.cut-lattice} is thus shown.
\end{proof}

\begin{thebibliography}{99999999}

\bibitem[BjoLov92]{BjoLov92}
Anders Bj\"orner, L\'aszl\'o Lov\'asz,
\textit{Chip-firing games on directed graphs},
J. Algebraic Combinatorics 1 (1991), pp. 305--328,
revised version, July 1992.
\newline\url{http://www.cs.elte.hu/~lovasz/morepapers/abacus.pdf}

\bibitem[BjLoSh91]{BjLoSh91}
Anders Bj\"orner, L\'aszl\'o Lov\'asz, P. W. Shor,
\textit{Chip-firing games on graphs},
Europ. J. Comb. 12 (1991), pp. 283--291.
\newline\url{http://www.cs.elte.hu/~lovasz/morepapers/chips.pdf}

\bibitem[CorPet16]{CorPet16}
Scott Corry, David Perkinson,
\textit{Divisors and Sandpiles},
draft of 28 January 2018.
\newline\url{http://people.reed.edu/~davidp/divisors_and_sandpiles/}

\bibitem[Ellenb15]{Ellenb15}
Jordan Ellenberg,
\textit{The Amazing, Autotuning Sandpile},
Nautilus, 2 April 2015.
\newline\url{http://nautil.us/issue/23/dominoes/the-amazing-autotuning-sandpile}

\bibitem[ForFul74]{ForFul74}
L. R. Ford, D. R. Fulkerson,
\textit{Flows in Networks},
Princeton University Press,
sixth printing 1974.

\bibitem[Galvin17]{Galvin}David Galvin, \textit{Basic discrete mathematics}, 13
December 2017.\newline
\url{http://www.cip.ifi.lmu.de/~grinberg/t/17f/60610lectures2017-Galvin.pdf}

\bibitem[Grinbe17a]{hw2s}
Darij Grinberg,
\textit{UMN, Spring 2017, Math 5707: homework set \#2 with solutions},
\newline\url{http://www.cip.ifi.lmu.de/~grinberg/t/17s/hw2s.pdf} .

\bibitem[Grinbe17b]{lec16}
Darij Grinberg,
\textit{UMN, Spring 2017, Math 5707: Lecture 16 (flows and cuts in networks)},
\newline\url{http://www.cip.ifi.lmu.de/~grinberg/t/17s/5707lec16.pdf} .

\bibitem[HLMPPW13]{HLMPPW13}
Alexander E. Holroyd, Lionel Levine, Karola M\'esz\'aros,
Yuval Peres, James Propp, David B. Wilson,
\textit{Chip-Firing and Rotor-Routing on Directed Graphs},
arXiv:0801.3306v4.
\newline\url{https://arxiv.org/abs/0801.3306v4}

\bibitem[Musike09]{Musike09}
Gregg Musiker,
\textit{18.312: Algebraic Combinatorics, Spring 2009},
MIT OpenCourseWare.
\newline\url{https://ocw.mit.edu/courses/mathematics/18-312-algebraic-combinatorics-spring-2009/readings-and-lecture-notes/}

\bibitem[PicQue80]{PicQue80}
Jean-Claude Picard, Maurice Queyranne,
\textit{On the structure of all minimum cuts in a network and applications},
Mathematical Programming,
December 1982, Volume 22, Issue 1, pp. 121--121.
\newline\url{https://link.springer.com/article/10.1007/BF01581031}

\bibitem[Stanle11]{Stanle11}Richard P. Stanley, \textit{Enumerative
Combinatorics, volume 1}, Cambridge University Press, 2011. \newline%
\url{http://math.mit.edu/~rstan/ec/ec1/}

\end{thebibliography}

\end{document}