\documentstyle[11pt,amssymbols]{article}
\oddsidemargin 0in
\topmargin 0in
%\headheight 0in
%\headsep 0in
\textheight 8.2 in
\textwidth 16cm
\hsize=7.5in
\vsize=11.0in


%\setlength{\oddsidemargin}{0.5in}
%\setlength{\evensidemargin}{0.5in}
%\setlength{\topmargin}{0in}
%\setlength{\textheight}{8.2in}
%\setlength{\textwidth}{6in}
%\oddsidemargin 0in
%\topmargin 0in
%\headheight 0in
%\headsep 0in
%\textheight 23.5cm
%\textwidth 16cm
%\hsize=7.5in
%\vsize=11.0in

\font\tenmsym=msym10
\font\sevenmsym=msym7
\font\fivemsym=msym5
\newfam\msymfam \def\msym{\fam\msymfam\tenmsym}
\textfont\msymfam=\tenmsym
\scriptfont\msymfam=\sevenmsym
\scriptscriptfont\msymfam=\fivemsym

% theorems and such

\newtheorem{emtheorem}{Theorem}
\newtheorem{emlemma}[emtheorem]{Lemma}
\newtheorem{emcorollary}[emtheorem]{Corollary}
\newtheorem{emproposition}[emtheorem]{Proposition}
\newtheorem{emobservation}[emtheorem]{Observation}
\newtheorem{emremark}[emtheorem]{Remark}
\newtheorem{emconjecture}[emtheorem]{Conjecture}
\newtheorem{emfact}[emtheorem]{Fact}

\newenvironment{theorem}{\begin{emtheorem}\em\sl}{\end{emtheorem}}
\newenvironment{lemma}{\begin{emlemma}\em\sl}{\end{emlemma}}
\newenvironment{corollary}{\begin{emcorollary}\em\sl}{\end{emcorollary}}
\newenvironment{proposition}{\begin{emproposition}\em\sl}{\end{emproposition}}
\newenvironment{observation}{\begin{emobservation}\em}{\end{emobservation}}
\newenvironment{remark}{\begin{emremark}\em}{\end{emremark}}
\newenvironment{fact}{\begin{emfact}\em}{\end{emfact}}
\newenvironment{conjecture}{\begin{emconjecture}\em}{\end{emconjecture}}

\newcommand{\qed}{ \mbox{$\Box$}\vspace{1mm} }
\newcommand{\proof}{ \mbox{\sc Proof. } }
\newcommand{\definition}{\vspace{.4cm}\noindent  \mbox{\bf Definition. } }
\newcommand{\example}{\vspace{.4cm}\noindent  \mbox{\bf Example. } }
\newcommand{\mod}{\mathop{\rm mod}}
\newcommand{\supp}{\mathop{\rm supp}}
\newcommand{\proofone}{ \mbox{\sc Proof of Theorem 1. } }

\begin{document}
\bibliographystyle{alpha}
\baselineskip=18pt
\title {\vspace{-20mm}\Huge\bf Pebblings}
\author{{\Large\sc Henrik Eriksson}\\
{NADA, KTH},
{ S-100 44 Stockholm},
{ Sweden}\\
{\tt henrik@nada.kth.se}}
\date{\small Submitted:  June 15, 1994; Accepted: April 5, 1995}
\maketitle
\pagestyle{myheadings}   
\markright{\sc the electronic journal of combinatorics 2 (1995), \#R7\hfill}
\thispagestyle{empty}


\begin{abstract}
  The analysis of chessboard pebbling by Fan Chung, Ron Graham, John Morrison 
  and Andrew Odlyzko is strengthened and generalized, first to higher dimension
  and then to arbitrary posets.  

\noindent{\bf Subject Classification:} 
Primary 05A15; secondary 05E99.
\end{abstract}


\section{The pebbling game}

The pebbling game of Kontsevich is played on the grid points of the first
quadrant.  One starts with a single pebble on the origin and a
move consists of replacing any pebble with two pebbles, one
above and one to the right of the vanishing pebble:
\begin{picture}(40,10)(-10,-1)
\put(-5,-5){\line(1,0){20}}
\put(-5,-5){\line(0,1){20}}
\put(-5,15){\line(1,0){10}}
\put( 5,15){\line(0,-1){10}}
\put(15,-5){\line(0,1){10}}
\put( 5, 5){\line(1,0){10}}
\put(0,0){\circle{7}}
\put(10,0){\circle*{1}}
\put(0,10){\circle*{1}}
\put(19,5){\thicklines\vector(1,0){15}}
\end{picture}
\begin{picture}(30,8)(-10,-1)
\put(-5,-5){\line(1,0){20}}
\put(-5,-5){\line(0,1){20}}
\put(-5,15){\line(1,0){10}}
\put( 5,15){\line(0,-1){10}}
\put(15,-5){\line(0,1){10}}
\put( 5, 5){\line(1,0){10}}
\put(10,0){\circle{7}}
\put(0,10){\circle{7}}
\put(0,0){\circle*{1}}
\end{picture}.  However, only one pebble is allowed on each grid point.

The original problem, posed by Kontsevich in 1981, was to show that the ten 
grid-points closest to the origin, $\{(i,j) \mid i+j\le 3\}$, form an 
{\em unavoidable set},
meaning that every game position has at least one pebble in this set.  The 
intended proof was the following.

To a pebble at $(i,j)$ assign the weight $2^{-i-j}$.  That makes the total 
weight of the pebbles equal to 1 in all positions, for each move splits
a pebble into two, half as heavy, and the total weight was 1 to start with.
With at most one pebble on each point, all grid points outside the ten-point
triangle can carry at most 
$\sum_{i,j\ge 0} 2^{-i-j} -(1+\frac{2}{2}+\frac{3}{4}+\frac{4}{8}) 
  = \frac{3}{4}$, so some pebble must be left in the triangle.

Shortly afterwards, A. Khodulev \cite{Kh} made the surprising observation,
that already the five-point set
\begin{picture}(33,10)(-5,0)
\put( 0, 0){\line(1,0){25}}
\put( 0, 0){\line(0,1){15}}
\put( 0, 0){\circle*{4}}
\put(10, 0){\circle*{4}}
\put( 0,10){\circle*{4}}
\put(10,10){\circle*{4}}
\put(20, 0){\circle*{4}}
\put(20,10){\circle*{1}}
\end{picture}
is unavoidable. The first complete proof appeared thirteen
years later in the American Mathematical Monthly \cite{FGMO},
in which Chung, Graham, Morrison and Odlyzko also gave
new enumerative results.

The purpose of this paper is to extend these results to the 
higher dimension analogues of the pebbling game and to a
more general poset version.

\section{Pebbling in ${\bf Z}^n$}

The $n$-dimensional version of the game, suggested by Paul Vaderlind \cite{V},
uses the integer grid points of
the first orthant.  One starts with a single pebble on the origin and
a legal move replaces a pebble by $n$ pebbles, each one step away in
the $n$ coordinate directions.


The {\em weight} of a pebble with coordinates $(x_1,\ldots,x_n)$ is
$n^{-x_1-\cdots -x_n}$ and it is obvious that the total weight of
all pebbles is unchanged by a move in the pebbling game.  If there
were a pebble on each point in the first orthant, the total weight
would be 
$$ \sum_{x_i\ge 0} n^{-x_1-x_2-\cdots} = 
   \left(\sum_{i=0}^\infty n^{-i}\right)^n = 
   (1-\frac{1}{n})^{-n} \rightarrow e 
   \mbox{\quad when\ } n\rightarrow\infty$$

Weight calculations can be used to prove that a certain point set is
unavoidable, for example the seven-point set in ${\Bbb Z}^6$ consisting of
the origin and its six neighbours in the positive orthant. The total weight
that can be carried on all other orthant grid points is
$$ (1-\frac{1}{6})^{-6}-1 -\frac{1}{6} -\frac{1}{6}-\frac{1}{6} -\frac{1}{6} -
    \frac{1}{6} -\frac{1}{6} =  0.98598\ldots \ ,$$
but the total pebble weight is one.

Dimension six is the lowest dimension in which this kind of proof will work,
but in fact the following is true.
\begin{proposition}\label{trident}
  The four-point set in ${\Bbb Z}^n$, $n\ge 3$ consisting of the origin and
three neighbour points is unavoidable.
\end{proposition}
\begin{proof}
  Consider the unit cube defined by the four-point set.  When the four points
  have been emptied, three other points on the cube will have received two 
  pebbles each, one of which must be sent along to the $(1,1,1)$-point. 
  But in a legal game, no point will receive more than two pebbles, as shown in
  the proof of Proposition \ref{nk} below.\qed
\end{proof}

 Proofs of this kind are greatly facilitated if several pebbles are allowed to
occupy the same point, at least temporarily.
 The following result appears as Lemma 3
in \cite{FGMO} in the two-dimensional case and will be proved in
much greater generality in our next section, so let us just state it as
a fact.
\begin{fact}
  If a configuration of pebbles with at most one pebble per point is
  reachable by moves which allow stacking of pebbles, then it is also
  reachable by moves which do not allow stacking.
\end{fact}

The {\em level} of an orthant point is the sum of its coordinates.
Thus, level zero contains the origin only, level one has $n$ points,
level two $n(n+1)/2$ points etc.  The following {\em level trimming} 
procedure for
determining whether or not a set of points, $X$, is unavoidable
is given in \cite{FGMO}.  Starting at level zero and proceeding one
level at a time, perform the moves required to remove all pebbles from
a point in $X$ or all but one pebble from a point not in $X$. Stacking
of pebbles is allowed. 

The following fact is not completely obvious, but again, a much more
general statement will be proved in the next section.

\begin{fact}
  The configuration after trimming levels 0 through $k$ is independent
  of the order in which the moves are performed. The set $X$ is
  unavoidable if and only if the trimming procedure can go on for
  ever without running out of pebbles.
\end{fact}

Level trimming supplies a polynomial time algorithm to determine whether or 
not a given set $X$ is unavoidable, as stated in the next proposition. Let us
warn the reader that a much better result will appear in Theorem \ref{better}.

\begin{proposition}\label{nk}
  Let level $k$ be the last one containing a point from $X\subset{\Bbb Z}^n$ 
  and consider the configurations after trimming levels 
  $1,2,\ldots, nk$.
  The set $X$ is unavoidable if and only if none of these contains
  a point with three or more pebbles on it at any stage.
\end{proposition}
\begin{proof}
  In the one-dimensional case, there are no unavoidable sets and no 
  three pebble points. The two-dimensional case is a consequence of Theorem 1 
  in \cite{FGMO}, so we can assume $n\ge 3$.  
  If there are three or more pebbles on a point,
  $x=(x_1,x_2,x_3,\ldots )$, at least two of these must propagate to each of
  the points $(x_1+1,x_2,x_3,\ldots )$, $(x_1,x_2+1,x_3,\ldots )$ and
  $(x_1,x_2,x_3+1,\ldots )$ (an equilateral triangle on the next level).
  On the next level, each point in the triangle $(x_1+1,x_2+1,x_3,\ldots )$, 
  $(x_1,x_2+1,x_3+1,\ldots )$ and $(x_1+1,x_2,x_3+1,\ldots )$ receives at
  least two pebbles from the triangle below, one of which must be sent on
  to the point $x'=(x_1+1,x_2+1,x_3+1,\ldots )$.  So now there are at 
  least three pebbles on $x'$  and the game goes on forever. 

  Now, assume that there are no three-pebble points on level $k+1$.
  This implies that each point sends at most one pebble to its neighbours on
  the next level.  
  Level $k+1$ intersects the coordinate axes in $n$ points, none of which can
  have more than one pebble, so they send no pebbles to their neighbours.
  Therefore, on level $k+2$ the axis points have zero pebbles and the axis
  neighbours at most one pebble.  Iterating the argument, we find that on
  level $k+m$, all points with distance less than $m$ from an axis have at most
  one pebble. The center point on level $nk$ is $(k,k,\ldots,k)$ and with 
  $m=(n-1)k$, we see that all other points have at most one pebble. Therefore,
  when level $nk$ has been trimmed, the game is over. \qed
\end{proof}

A byproduct of the proof is a polynomial bound for the length of the game 
corresponding to an {\em avoidable set} $X$. Again, a much better bound will
appear in Theorem \ref{better}.
Let us now consider the connection between an avoidable set $X$ and the end 
position after the game.  Points in $X$ that are never touched by a pebble
are of no consequence, but modulo these uninteresting points, the 
correspondence is in fact bijective.

\begin{definition}
  The {\em voidance set} of a (finite) pebbling game consists of all points 
  in ${\Bbb Z}^n$  that at some stage were pebble points but end up empty.
\end{definition}

As defined, the voidance set seems to depend on the particular sequence of
moves leading to the final position, but in our next section,
(Proposition \ref{voidance}), we shall show
that games leading to the same position have the same voidance set.
\begin{fact}
  A reachable game position is completely specified by its voidance set.
\end{fact}


As combinatorial objects, voidance sets are more tractable than
reachable positions, not to mention pebbling games.  A hundred-point
voidance set in ${\Bbb Z}^2$ might correspond to a position with 
a thousand pebbles, which in turn may arise from zillions of 
different move sequences.

It turns out that the points that are played in a two-dimensional pebbling 
game form a characteristic configuration bounded by two lattice paths.  
A corresponding voidance set is the set of left and lower boundary points
on these paths.

\begin{definition}
  A {\em polyominoid set} in ${\Bbb Z}^2$ 
  consists of all points on or between two
  lattice paths with common starting point and common ending point.
  As demonstrated in Fig.\ref{polyominoids}, the paths may be partially 
  or totally coincident,
  but without loss of generality, we may assume that they are not strictly
  crossing.  We call $(x,y)$ a {\em left boundary point} if $(x-1,y)$ is not
  in the polyominoid and a {\em lower boundary point} if $(x,y-1)$ is not
  in the polyominoid.
\end{definition}

\medskip
\begin{observation}
Polyominoid sets correspond bijectively to parallelogram polyominoes in the 
sense of M.Delest and X.Viennot \cite{DV}.
If the left path is translated one step upwards, the lower path one step 
to the right, and the terminal points are rejoined in the obvious way, we get a
polyomino of the parallelogram type.
\end{observation}

\begin{figure}[h]
\begin{picture}(35,0)
\end{picture}
\begin{picture}(85,40)
\put(0,0){\circle*{3.5}}
\put(10,0){\circle*{3.5}}
\put(0,10){\circle*{3.5}}
\put(0,0){\line(1,0){10}}
\put(0,0){\line(0,1){10}}
\put(10,0){\line(1,0){10}}
\put(0,10){\line(1,0){10}}
\put(20,0){\circle*{3.5}}
\put(10,10){\circle*{3.5}}
\put(20,0){\line(1,0){10}}
\put(30,0){\circle*{3.5}}
\put(10,10){\line(0,1){20}}
\put(30,0){\line(0,1){10}}
\put(10,20){\circle*{3.5}}
\put(30,10){\circle*{3.5}}
\put(10,30){\circle*{3.5}}
\put(40,10){\circle*{3.5}}
\put(10,30){\line(1,0){10}}
\put(30,10){\line(1,0){20}}
\put(50,10){\line(0,1){30}}
\put(20,30){\circle*{3.5}}
\put(30,20){\circle*{3.5}}
\put(30,30){\circle*{3.5}}
\put(50,20){\circle*{3.5}}
\put(20,30){\line(0,1){10}}
\put(20,40){\line(1,0){30}}
\put(20,40){\circle*{3.5}}
\put(30,40){\circle*{3.5}}
\put(50,20){\circle*{3.5}}
\put(50,30){\circle*{3.5}}
\put(50,10){\circle*{3.5}}
\put(50,40){\circle*{3.5}}
\put(40,20){\circle*{3.5}}
\put(40,30){\circle*{3.5}}
\put(40,40){\circle*{3.5}}
\put(20,10){\circle*{3.5}}
\put(20,20){\circle*{3.5}}
\put(65,20){\Large$\leftrightarrow$}
\end{picture}
\begin{picture}(75,40)
\put(0,0){\circle{4}}
\put(0,0){\line(1,0){10}}
\put(10,0){\circle{4}}
\put(10,0){\line(1,0){10}}
\put(20,0){\circle{4}}
\put(10,0){\line(0,1){20}}
\put(20,0){\line(0,1){10}}
\put(10,10){\circle{4}}
\put(20,10){\circle*{3.5}}
\put(10,20){\circle{4}}
\put(30,10){\circle{4}}
\put(10,20){\line(1,0){10}}
\put(20,10){\line(1,0){20}}
\put(40,10){\line(0,1){20}}
\put(20,20){\circle*{3.5}}
\put(30,20){\circle*{3.5}}
\put(40,20){\circle*{3.5}}
\put(20,20){\line(0,1){10}}
\put(20,30){\line(1,0){20}}
\put(20,30){\circle{4}}
\put(30,30){\circle*{3.5}}
\put(40,20){\circle*{3.5}}
\put(40,30){\circle*{3.5}}
\put(40,10){\circle{4}}
\end{picture} 
\begin{picture}(80,40)
\put(0,0){\circle*{3.5}}
\put(10,0){\circle*{3.5}}
\put(0,10){\circle*{3.5}}
\put(0,0){\line(1,0){10}}
\put(10,0){\line(1,0){10}}
\put(20,10){\line(1,0){10}}
\put(10,0){\circle*{3.5}}
\put(20,0){\circle*{3.5}}
\put(0,0){\line(0,1){30}}
\put(0,10){\circle*{3.5}}
\put(0,20){\circle*{3.5}}
\put(20,0){\line(0,1){10}}
\put(30,10){\line(0,1){10}}
\put(30,20){\line(1,0){20}}
\put(10,10){\circle*{3.5}}
\put(20,10){\circle*{3.5}}
\put(10,20){\circle*{3.5}}
\put(10,30){\circle*{3.5}}
\put(0,30){\circle*{3.5}}
\put(0,30){\line(1,0){20}}
\put(50,20){\line(0,1){20}}
\put(20,30){\line(0,1){10}}
\put(20,20){\circle*{3.5}}
\put(20,30){\circle*{3.5}}
\put(30,20){\circle*{3.5}}
\put(30,20){\circle*{3.5}}
\put(40,20){\circle*{3.5}}
\put(50,20){\circle*{3.5}}
\put(50,20){\line(0,1){10}}
\put(20,40){\line(1,0){30}}
\put(20,40){\circle*{3.5}}
\put(30,30){\circle*{3.5}}
\put(30,40){\circle*{3.5}}
\put(40,20){\circle*{3.5}}
\put(50,20){\circle*{3.5}}
\put(40,40){\circle*{3.5}}
\put(50,40){\circle*{3.5}}
\put(40,30){\circle*{3.5}}
\put(50,30){\circle*{3.5}}
\put(30,10){\circle*{3.5}}
\put(60,20){\Large$\leftrightarrow$}
\end{picture}
\begin{picture}(75,40)
\put(0,0){\circle{4}}
\put(0,0){\line(1,0){10}}
\put(10,10){\line(1,0){10}}
\put(10,0){\circle{4}}
\put(0,0){\line(0,1){20}}
\put(0,10){\circle{4}}
\put(10,0){\line(0,1){10}}
\put(20,10){\line(0,1){20}}
\put(10,10){\circle*{3.5}}
\put(10,20){\circle*{3.5}}
\put(0,20){\circle{4}}
\put(0,20){\line(1,0){40}}
\put(40,20){\line(0,1){10}}
\put(20,20){\circle*{3.5}}
\put(30,20){\circle{4}}
\put(40,20){\circle{4}}
\put(40,20){\line(0,1){10}}
\put(20,30){\line(1,0){20}}
\put(20,30){\circle{4}}
\put(30,30){\circle*{3.5}}
\put(40,20){\circle{4}}
\put(40,30){\circle*{3.5}}
\put(20,10){\circle{4}}
\end{picture}
\caption{Two  polyominoes with polyominoids and left-lower boundary points.
\label{polyominoids}}
\end{figure}

Not counting the left lower point (the origin of coordinates), a polyominoid
set with height $h$ and width $w$ has $h$ left and $w$ lower boundary points,
so the cardinality of the voidance set is $w+h+1$, one more than the length
of each path.

The following enumeration result is classical in the context of polyominoes
and noncrossing lattice paths, see \cite{DV} and \cite{GV}.  Still, for
conveniency we give the proof in the polyominoid case.
\begin{proposition}\label{Catalan}
  The number of polyominoid sets with lattice paths of length $k$, i.e.\ 
  with $k+1$ left and lower boundary points, is the Catalan number
$$ C_{k+1}=\frac{1}{k+2} {2k+2\choose k+1} = {2k\choose k} - {2k\choose k-2}$$
\end{proposition}
\begin{proof}
  A lattice path of length $k$ can be represented as a binary $k$-vector.
  A pair of paths with common terminal points means two binary vectors, 
  $\bf u$, $\bf v$, with the same number of ones.  Complementing the second
  vector and concatenating it to the first vector,  one gets a $2k$-vector
  with $k$ ones, and there are ${2k\choose k}$ of these.

  The polyominoid (weakly noncrossing) condition is
$\sum_1^r u_i \le \sum_1^r v_i $ for all $1\le r \le k$.  Otherwise, let
$r'$ be the first index for which 
$\sum_1^{r'} u_i =1+ \sum_1^{r'} v_i $ and let us switch the $(k-r')$-tails
between $\bf u$ and $\bf v$.  Now, there are two more ones in the first vector,
$\bf u'$, than in the second, $\bf v'$, and as for every such pair, 
$r'$ can be defined as above, the correspondence is bijective.  
Finally, the complemented concatenation trick shows that these nonpolyominoid 
pairs are $2k\choose k-2$. \qed
\end{proof}

\begin{proposition}\label{Z2polyominoid}
  The points played in a pebbling game on ${\Bbb Z}^2$ form a polyominoid.
\end{proposition}
\begin{proof}
As this is a special case of the last proposition of this paper, let us
just sketch the easy proof.  Assume that the level trimming procedure
has been carried out up to level $k$ and that the set of played points
is polyominoid so far. The two lattice paths bound a diagonal segment of
points on level $k$, and these transmit pebbles to diagonal
segment of neighbours on level $k+1$.  All points of this segment, except
possibly the left and right extremes, receive two pebbles and must be
played, so it is clear that the lattice paths can be extended to level $k+1$.
\qed
\end{proof}

Every pebbling game in  ${\Bbb Z}^2$ defines a polyominoid, viz.\ the set of
all points that have been played.
In ${\Bbb Z}^n$, the play may of course use all $n$ dimensions, but the
set of points that have been played still form a polyominoid set,
although folded and meandering through the dimensions.

\begin{definition}
  A {\em folded polyominoid set} in  ${\Bbb Z}^n$ is defined by a consistent
  labelling of the edges of a polyominoid set with coordinate directions.
  Consistency means that for each square in the polyominoid, adjacent sides
  have different labels but opposite sides have the same label. Thus, for a
  polyominoid with height $h$ and width $w$, it is sufficient to specify
  $h+w$ labels, for example on the left and lower edges.
\end{definition}

\begin{figure}[h]
\begin{picture}(75,40)(-100,0)
\put(0,0){\circle*{3.5}}
\put(10,0){\circle*{3.5}}
\put(0,10){\circle*{3.5}}
\put(10,10){\circle*{3.5}}
\put(10,20){\circle*{3.5}}
\put(0,20){\circle*{3.5}}
\put(20,20){\circle*{3.5}}
\put(30,20){\circle*{3.5}}
\put(40,20){\circle*{3.5}}
\put(20,30){\circle*{3.5}}
\put(30,30){\circle*{3.5}}
\put(40,20){\circle*{3.5}}
\put(40,30){\circle*{3.5}}
\put(20,10){\circle*{3.5}}
\put(3.5,-1){\tiny x}
\put(3.5,9){\tiny x}
\put(3.5,19){\tiny x}
\put(13.5,9){\tiny z}
\put(13.5,19){\tiny z}
\put(23.5,19){\tiny x}
\put(33.5,29){\tiny y}
\put(23.5,29){\tiny x}
\put(33.5,19){\tiny y}
\put(-1.5,4){\tiny y}
\put(8.5,4){\tiny y}
\put(-1.5,14){\tiny y}
\put(8.5,14){\tiny y}
\put(18.5,14){\tiny y}
\put(18.5,23.5){\tiny z}
\put(28.5,23.5){\tiny z}
\put(38.5,23.5){\tiny z}
\end{picture}
\begin{picture}(75,40)(-130,0)
\put(0,0){\circle*{3.5}}
\put(0,0){\line(1,0){10}}
\put(10,10){\line(1,0){10}}
\put(10,0){\circle*{3.5}}
\put(0,0){\line(0,1){20}}
\put(0,10){\circle*{3.5}}
\put(10,0){\line(0,1){10}}
\put(20,10){\line(0,1){20}}
\put(10,10){\circle*{3.5}}
\put(10,20){\circle*{3.5}}
\put(0,20){\circle*{3.5}}
\put(0,20){\line(1,0){40}}
\put(40,20){\line(0,1){10}}
\put(20,20){\circle*{3.5}}
\put(30,20){\circle*{3.5}}
\put(40,20){\circle*{3.5}}
\put(40,20){\line(0,1){10}}
\put(20,30){\line(1,0){20}}
\put(20,30){\circle*{3.5}}
\put(30,30){\circle*{3.5}}
\put(40,20){\circle*{3.5}}
\put(40,30){\circle*{3.5}}
\put(20,10){\circle*{3.5}}
\put(3,-4){\tiny x}
\put(13,6){\tiny z}
\put(23,16){\tiny x}
\put(33,16){\tiny y}
\put(-4,4){\tiny y}
\put(-4,14){\tiny y}
\put(16,24){\tiny z}
\put(80,20){${\bf u}=(y,y,0,0,z,0,0)$}
\put(80,0){${\bf v}=(x,0,z,0,x,y,0)$}
\end{picture}
\caption{A folded polyominoid with left-lower labels and label vectors.}
\label{folded}
\end{figure}

Labelling of left and lower edges may be seen as distribution of $k$ labels 
over $2k$ places, namely the pair of $k$-vectors $\bf u$ and $\bf v$ defining
the boundary paths. Unlabelled places contain zeroes.
There are of course compatibility restrictions on this
distribution and these can be stated concisely if we introduce the
notation $|{\bf u}_{\ldots r}|$ for the number of labels in the initial 
$r$-segment of $\bf u$.  Thus, moving $r$ steps along the left boundary
path, we go  $|{\bf u}_{\ldots r}|$ steps upward and  $r-|{\bf u}_{\ldots r}|$ 
steps to the right.  And moving $r$ steps along the lower boundary
path, we go  $|{\bf v}_{\ldots r}|$ steps to the right and  
$r-|{\bf v}_{\ldots r}|$ steps upwards. 

\begin{theorem}\label{higher}
  For pebbling in  ${\Bbb Z}^n$ with $n\ge 3$, the following combinatorial
  objects correspond bijectively to each other.
\begin{enumerate}
\item Reachable positions with the highest pebble on level $k+1$.
\item Voidance sets of cardinality $k+1$.
\item Folded polyominoids with boundary path
      lengths $k$.
\item Pairs of integer $k$-vectors, $\bf u$ and $\bf v$, with a total of $k$
      nonzero elements (labels) in $\{1,\ldots,n\}$, such that
\begin{enumerate}
      \item if for any $0\le r<k$, 
            $|{\bf u}_{\ldots r}|+|{\bf v}_{\ldots r}|=r$
            then $u_{r+1}\le v_{r+1}$,
      \item $|{\bf u}_{\ldots r}|+|{\bf v}_{\ldots r}|\ge r$ for all
            $1\le r\le k$,
      \item if the same label occurs in $u_i$ and $v_j$, then
            $|{\bf u}_{\ldots i}|+|{\bf v}_{\ldots j}|\le \max(i,j)$.
\end{enumerate}
\end{enumerate}
\end{theorem}
\begin{proof}
  The folded polyominoid characterization of reachable positions in  
  ${\Bbb Z}^n$ will emerge as a corollary of Proposition \ref{polyominoid}.
  In dimension three and higher, no node is played twice (this will
  be proved in Proposition \ref{lambda}), so the voidance set consists of all
  left and lower boundary points of the folded polyominoid, and we have
  already noted that their cardinality is $k+1$.

  A folded polyominoid may be unfolded in the $xy$-plane in at least two ways
  ($xy$-reflections), more if there are intermediate singleton levels,
  but condition $(a)$ uniquely defines the left and lower boundary vectors 
  $\bf u$ and $\bf v$. For both paths reach the same point in $r$ steps
  if and only if  $|{\bf u}_{\ldots r}|+|{\bf v}_{\ldots r}|=r$.  

  Similarly, condition $(b)$ expresses the fact that the left path should
  keep to the left of the lower path. (The binary vectors in the proof of
  Proposition \ref{Catalan} correspond to our vectors in a somewhat confusing way:
  the nonzero labels in $\bf u$ mean binary zeroes and zero labels mean binary
  ones, in $\bf v$ it is the other way around.)

  Condition $(c)$ means that the horisontal strip to the right of the vertical
  segment $u_i$ must not intersect the vertical strip above the horizontal
  segment $v_j$.  Either $v_j$ is to the left of $u_i$, which implies
  $|{\bf v}_{\ldots j}|\le i-|{\bf u}_{\ldots i}|$, or $u_i$ is below $v_j$,
  which means $|{\bf u}_{\ldots i}|\le j-|{\bf v}_{\ldots j}|$.  
  \qed
\end{proof}

\medskip
The beautiful enumeration result for two-dimensional polyominoids makes one
hope for some similar formula for folded polyominoids.  If one exists, it has
eluded this author so far.  The conditions in the theorem makes computer
calculations of these numbers easy and we include a table of them. Note the
Catalan numbers in the second column!  The row $k=2$ is $n(3n-1)/2$ and it can
be proved that row $k$ is a $k$-th degree polynomial in $n$.

\begin{figure}[h]\label{table}
\centering{
\begin{tabular}{|l|r|r|r|r|r|r|}\hline
$f_{k,n}$ &$n=1$ &$n=2$ &$n=3$ &$n=4$ &$n=5$ &$n=6$ \\ \hline
$k=0$&1&1&1&1&1&1\\ \hline
$k=1$&1&2&3&4&5&6\\ \hline
$k=2$&1&5&12&22&35&51\\ \hline
$k=3$&1&14&57&148&305&546\\ \hline
$k=4$&1&42&300&1126&3045&6756\\ \hline
$k=5$&1&132&1680&9220&32985&91236\\ \hline
\end{tabular}}
\caption{Number of folded polyominoes in ${\protect\Bbb Z}^n$ 
with circumference $2k$.}
\end{figure}

The theorem does not apply to the two-dimensional case, for the same 
polyominoid may correspond to several voidance sets.  The reason is that
some points in the polyominoid may be played twice.  Which points?  First,
they must receive two pebbles, so their left and lower neighbours are in
the polyominoid. Second, their right and upper neighbours must be emptied,
so these must be a left and a lower boundary point. It follows that a twice
played point must be a singleton on its level.  The result of the second
play is that two old voidance points are replaced by one new voidance point.
\begin{picture}(60,15)(-15,10)
\put(0,10){\line(1,0){20}}
\put(10,0){\line(0,1){20}}
\put(0,0){\circle*{3.5}}
\put(0,10){\circle*{3.5}}
\put(10,0){\circle*{3.5}}
\put(10,10){\circle*{3.5}}
\put(20,20){\circle*{3.5}}
\put(10,20){\circle{4}}
\put(20,10){\circle{4}}
\put(29,8){$\bf\rightarrow$}
\end{picture}
\begin{picture}(30,15)(0,10)
\put(0,10){\line(1,0){20}}
\put(10,0){\line(0,1){20}}
\put(0,0){\circle*{3.5}}
\put(0,10){\circle*{3.5}}
\put(10,0){\circle*{3.5}}
\put(10,10){\circle{4}}
\put(20,20){\circle*{3.5}}
\put(10,20){\circle*{3.5}}
\put(20,10){\circle*{3.5}}
\end{picture}.
Let us call this configuration a {\em crossing}.
\medskip
\begin{theorem}
  For pebbling in ${\Bbb Z}^2$, reachable positions with the highest
  pebble on level $k+1$ correspond bijectively to folded polyominoids
  with boundary pathlengths $k$ and with any subset of the crossings marked 
  as voidance points. 
  The generating function for the number of such reachable positions is
$$ g(x)=\frac{1-6x+4x^2+4x^3+\sqrt{1-4x}}{2(1-6x+8x^2-4x^4)} =
        1+2x+5x^2+14x^3+43x^4+140x^5+\cdots$$
  with asymptotic behaviour $g_k\sim \mbox{const}\cdot G^k$, where 
  $G=4.112\ldots$.

  Voidance sets of cardinality $k+1$ correspond bijectively to folded
  polyominoids with boundary lengths $k+t$ and with $t$ crossings marked as
  voidance points, $t\ge 0$.  The generating function for the number of
  such voidance sets is
$$ h(x)=\frac{2-11x+12x^2+x\sqrt{1-4x}}{2(1-7x+14x^2-9x^3)} =
        1+2x+5x^2+15x^3+51x^4+187x^5+\cdots$$
  with asymptotic behaviour $h_k\sim\mbox{const}\cdot G^k$, where 
  $G= 4.147\ldots$.
\end{theorem}

\begin{proof}
 Knowing that the number of unmarked polyominoids is $C_{k+1}$, we can
 write down a recursion
$$ g_k=C_{k+1}+\sum_{r=2}^{k-2}(C_{r+1}-2\, C_r)(g_{k-r}-2\, g_{k-r-1})$$
 with the following interpretation. Let $r$ be the level where the first 
 marked crossing appears.  Then $C_{r+1}-2\, C_r$ is the number of unmarked
 polyominoids ending with a 
\begin{picture}(40,15)(-15,0)
\put(0,10){\line(1,0){10}}
\put(10,0){\line(0,1){10}}
\put(0,0){\circle*{3.5}}
\put(0,10){\circle*{3.5}}
\put(10,0){\circle*{3.5}}
\put(10,10){\circle*{3.5}}
\end{picture}
on level $r$, for we have to subtract polyominoids ending with 
\begin{picture}(20,10)(-5,0)
\put(0,10){\line(1,0){10}}
\put(10,10){\circle*{3.5}}
\put(0,10){\circle*{3.5}}
\end{picture}
or
\begin{picture}(15,10)(0,0)
\put(10,0){\line(0,1){10}}
\put(10,0){\circle*{3.5}}
\put(10,10){\circle*{3.5}}
\end{picture}.
By the same reasoning, the number of marked polyominoids starting with
\begin{picture}(30,15)(-10,0)
\put(0,0){\line(1,0){10}}
\put(0,0){\line(0,1){10}}
\put(0,0){\circle*{3.5}}
\put(0,10){\circle*{3.5}}
\put(10,0){\circle*{3.5}}
\put(10,10){\circle*{3.5}}
\end{picture} 
and reaching $k-r$ levels is $g_{k-r}-2\, g_{k-r-1}$.

It is well-known that the Catalan numbers have the generating function
$(1+\sqrt{1-4x})/2x$. Standard manipulations and hard work (thanks, Maple!)
produce the expression for $g(x)$.

The recursion for $h_k$ is derived analogously, the only difference being
that each marked crossing reduces the number of voidance points and has
to be compensated for:
$$ h_k=C_{k+1}+\sum_{r=2}^{k-1}(C_{r+1}-2\, C_r)(h_{k-r+1}-2\, h_{k-r})\ .$$

The roots of the denominators determine the asymptotic exponents (see the
chapter by Odlyzko in \cite{HC}) as 1/(smallest root). Exponents greater than
four were to be expected, since $C_k\sim \mbox{const}\cdot 4^k$.
\qed
\end{proof}
\medskip

An important part of the paper by Chung, Graham, Morrison and Odlyzko is the 
enumeration of minimal unavoidable sets in ${\Bbb Z}^2$. The asymptotic 
expression found is 
$\mbox{const}\cdot \gamma^k$ with $\gamma={4.147\ldots}$, 
exactly our result when counting voidance sets!  
The agreement is hardly a coincidence, for in
Proposition \ref{mus} of next section, we prove that {\em a minimal unavoidable
set is a voidance set with an extra point}.  The extra point must be chosen
such that level trimming becomes infinite and such that deletion of any other
point makes level trimming finite again.

\begin{theorem}
  Every minimal unavoidable set in ${\Bbb Z}^2$ can be constructed from
  the left and lower boundary points of a marked polyominoid by adding
  a polyominoid point on the second highest level.

  The generating function for the number of minimal unavoidable sets of 
  cardinality $k$ is
$$ m(x)=x^3\,\frac{(1-3x+x^2)\sqrt{1-4x}-1+5x-x^2-6x^3}{1-7x+14x^2-9x^3} =
        4x^5+22x^6+98x^7+412x^8+\cdots$$
  with asymptotic behaviour $m_k\sim\mbox{const}\cdot H^k$, where 
  $H= 4.147\ldots$.
  \end{theorem}
\begin{proof}
 Let us look at all possibilities of adding an extra unavoidable point to
 a marked polyominoid ending like
\begin{picture}(20,10)(-5,0)
\put(-5,10){\line(1,0){15}}
\put(10,-5){\line(0,1){15}}
\put(10,10){\circle*{3.5}}
\put(0,10){\circle*{3.5}}
\put(10,0){\circle*{3.5}}
\end{picture},
i.e.\  a point that cannot be emptied by further play.
Positions outside the polyominoid can be emptied, for adding such a
point means building a larger polyominoid, e.g.
\begin{picture}(30,10)(-5,0)
\put(-5,10){\line(1,0){25}}
\put(10,0){\line(1,0){10}}
\put(20,0){\line(0,1){10}}
\put(10,10){\circle*{3.5}}
\put(20,10){\circle*{3.5}}
\put(0,10){\circle*{3.5}}
\put(10,0){\circle*{3.5}}
\put(20,0){\circle{4.0}}
\end{picture}.
The corner point can also be emptied by building a new
marked crossing
\begin{picture}(27,15)(-3,7)
\put(0,10){\line(1,0){20}}
\put(10,0){\line(0,1){20}}
\put(0,10){\circle*{3.5}}
\put(10,0){\circle*{3.5}}
\put(10,10){\circle{4}}
\put(20,20){\circle*{3.5}}
\put(10,20){\circle*{3.5}}
\put(20,10){\circle*{3.5}}
\end{picture}.
Other polyominoid points, however, really are unavoidable (for emptying
them would stack three pebbles somewhere), but only the corner
neighbours produce {\em minimal} unavoidable sets.  In, for example,
\begin{picture}(30,10)(-5,0)
\put(-5,10){\line(1,0){25}}
\put(20,0){\line(0,1){10}}
\put(10,10){\circle*{3.5}}
\put(20,10){\circle*{3.5}}
\put(0,10){\circle*{1.5}}
\put(0,10){\circle{4.0}}
\put(20,0){\circle*{3.5}}
\end{picture},
the last lower boundary point could be deleted.

So either of the corner neighbours in
\begin{picture}(20,10)(-5,0)
\put(-5,10){\line(1,0){15}}
\put(10,-5){\line(0,1){15}}
\put(10,10){\circle*{3.5}}
\put(0,10){\circle*{3.5}}
\put(10,0){\circle*{3.5}}
\end{picture},
produces a minimal unavoidable set together with the left and lower
boundary points.  The same reasoning for the special cases
\begin{picture}(20,10)(-5,0)
\put(-5,10){\line(1,0){15}}
\put(2,0){\line(1,0){8}}
\put(10,0){\line(0,1){10}}
\put(10,10){\circle*{3.5}}
\put(0,10){\circle*{3.5}}
\put(10,0){\circle{4.0}}
\end{picture}
et cetera shows that the configurations
\begin{picture}(20,10)(-5,0)
\put(-5,10){\line(1,0){15}}
\put(10,3){\line(0,1){7}}
\put(10,10){\circle*{3.5}}
\put(0,10){\circle*{3.5}}
\end{picture}
and
\begin{picture}(10,10)(5,0)
\put(0,10){\line(1,0){10}}
\put(10,-5){\line(0,1){15}}
\put(10,10){\circle*{3.5}}
\put(10,0){\circle*{3.5}}
\end{picture}
always produce one minimal unavoidable set each, and those are all
there are.

Counting marked polyominoids ending in 
\begin{picture}(20,10)(-5,0)
\put(-5,10){\line(1,0){15}}
\put(10,3){\line(0,1){7}}
\put(10,10){\circle*{3.5}}
\put(0,10){\circle*{3.5}}
\end{picture}
is a simple matter.  There are $h_{k-2}-2h_{k-3}$ of type
\begin{picture}(20,10)(-5,0)
\put(1,10){\line(1,0){9}}
\put(10,1){\line(0,1){9}}
\put(10,10){\circle*{3.5}}
\end{picture}
and from these we subtract $h_{k-3}-h_{k-4}$ of type
\begin{picture}(20,10)(-5,0)
\put(0,10){\line(1,0){10}}
\put(10,3){\line(0,1){7}}
\put(0,3){\line(0,1){7}}
\put(10,10){\circle*{3.5}}
\put(0,10){\circle{4.0}}
\end{picture},
so the result is $h_{k-2}-3h_{k-3}+h_{k-4}$.
The symmetric case gives a factor two and the final expression is
$m_k=2(h_{k-2}-3h_{k-3}+h_{k-4})$. 

The generating function $m(x)$ and the asymptotic expression for $m_k$ 
follow immediately from the corresponding results for $h(x)$.\qed
\end{proof}
\medskip

There are four four-point unavoidable sets in ${\Bbb Z}^3$.  The origin and
its three neighbours was proved unavoidable in Proposition \ref{trident}.
The square 
\begin{picture}(30,15)(-10,0)
\put(0,0){\line(1,0){10}}
\put(0,10){\line(1,0){10}}
\put(0,0){\line(0,1){10}}
\put(10,0){\line(0,1){10}}
\put(0,0){\circle{4.0}}
\put(0,10){\circle{4.0}}
\put(10,0){\circle{4.0}}
\put(10,10){\circle{4.0}}
\end{picture} 
in any coordinate plane is also unavoidable, for no point may be fired twice
in dimension $n\ge 3$.
These two examples of minimal unavoidable sets in ${\Bbb Z}^n$ are, in fact, 
generic.

\begin{theorem}
  Every minimal unavoidable set in ${\Bbb Z}^n$ can be constructed from
  the left and lower boundary points of a folded polyominoid by adding one of
  the following points.
\begin{itemize}
\item The highest point of the folded polyominoid (unless it is already a
      left or lower boundary point).
\item A point that forms an isoceles triangle with the two corner neighbours 
      (provided that the folded polyominoid ends with a 
\begin{picture}(30,15)(-10,0)
\put(0,10){\line(1,0){10}}
\put(10,0){\line(0,1){10}}
\put(0,10){\circle*{3.5}}
\put(10,0){\circle*{3.5}}
\put(10,10){\circle*{3.5}}
\end{picture}).
\end{itemize}
\end{theorem}
\begin{proof}
  Simpler than the two-dimensional case. One just has to test all positions 
  of an extra point.\qed
\end{proof}

Now, at last, we can state the optimal version of Proposition \ref{nk}.
\begin{theorem}\label{better}
  Let level $k$ in ${\Bbb Z}^n$ be the last one containing a point from $X$ 
  and consider the configurations after trimming levels $1,\ldots ,k+1$. The 
  set $X$ is unavoidable if no three-pebble point occurs during this game.
  If $X$ is avoidable, level trimming will come to an end no later than after 
  level $2k$.
\end{theorem}
\begin{proof}
  The truth of the statement for our minimal unavoidable sets can be 
  established  easily enough by a direct check and since each unavoidable
  set contains a minimal one, the rest is clear.  The analogous method
  applied to the voidance sets proves the other half of the statement.\qed
\end{proof}

\section{Pebbling a poset}

The pebbling game generalizes immediately to any digraph, but to preserve
its essential features we restrict ourselves to infinite but
locally finite posets with \^ 0 and without maximal elements.
The game board is the Hasse diagram, one starts with a single pebble on  
\^ 0 and a move consists of removing a pebble from any node $x$ and adding
a pebble to each node {\em covering} $x$, that is to each $u>x$ such that
there is no $v$ with $u>v>x$. 

Following Bj{\"o}rner, Lov\'asz and Shor \cite{BLS}, we say that node
$x$ is {\em fired}. It is illegal to fire a node unless all of its
covering nodes are empty, but we also consider a stacking variant of
the game in which pebbles are allowed to accumulate, at least temporarily.

The {\em shot count} is a record of the number of times each node has been
fired during a game, so it is a function from nodes to nonnegative integers.
\begin{proposition}
Different move sequences lead to the same position if and only if
they have the same shot count.
\end{proposition}
\begin{proof}
 A node $x$ that was fired $f(x)$ times has got $\sum f(y) -f(x)$ pebbles, 
  where the sum is taken over all nodes $y$ covered by $x$.  \qed
\end{proof}

\noindent
The bijective correspondence between reachable positions and shot counts is
useful, for shot counts are less complex combinatorial objects.
A simple characterization of shot counts comes next.
\begin{proposition}\label{shotcount}
  A finite distribution $f$ of nonnegative integers over the nodes is a shot 
  count of a legal game if and only if there is a 0 or a 1 on \^ 0 and for 
  every other node $x$, the difference $\sum f(y) -f(x)= 0$ or $1$, where the 
  sum is taken over all nodes $y$ covered by $x$.
\end{proposition}
\begin{proof}
  A game with shot count $f$ is defined by the following rule.  Always fire
  a maximal node in the subset of nodes $x$ that have a pebble and have not
  been fired $f(x)$ times yet.  Simple verifications. \qed
\end{proof}

\begin{proposition}
  If a configuration of pebbles with at most one pebble per node is
  reachable by moves which allow stacking of pebbles, then it is also
  reachable by moves which do not allow stacking.
\end{proposition}
\begin{proof}
  A consequence of the previous proposition.    \qed
\end{proof}

The last three propositions have the flavour of {\em strong convergence},
a concept introduced by Anders Bj\"orner and developed in \cite{E}. 
A game is strongly convergent if either
\begin{itemize}
\item every possible game has the same length and ends in the same terminal 
      position, or 
\item every game goes on for ever.  
\end{itemize}
Since the posets we are interested in are infinite, there are no terminal 
positions unless we restrict legal moves in the following way.  Choose an
arbitrary subset of nodes $X$ as {\em nodes to be emptied} and call a
pebble {\em obstructing} if it is in $X$ or (recursive definition!)  covers an
obstructing pebble (i.e.\ its node covers the other pebble's node).

\begin{proposition}
  With the new rule that only obstructing pebbles may be moved, pebbling is
  strongly convergent for every poset and for every set $X$ of nodes to be 
  emptied.  
\end{proposition}
\begin{proof}
  As shown by Kimmo Eriksson, strong convergence of a game is equivalent to 
  the {\em polygon property}, i.e.\ from any position where two
  different plays, $x$ and $y$, are possible, either there are two play 
  sequences of equal length, one starting with $x$, the other with $y$
  and leading to the same position, or there are two infinite play
  sequences, one starting with $x$ and the other with $y$.  

  In a pebbling game position where
  two nodes, $x$ and $y$, can be fired, there are two cases.
  Either there is a finite play sequence in which both nodes are fired,
  assume that its shot count is $f$.  One can play either $x$ or $y$ first,
  and the algorithm in the proof of Proposition  \ref{shotcount} then defines the
  rest of a sequence leading to the same position.  Or, there is an infinite
  sequence, for as long as one of the obstructing pebbles $x, y$ is unplayed, 
  there is certainly some playable node left.

\noindent
  So the pebbling game has the polygon property and is therefore strongly
  convergent. \qed
\end{proof}

In the corresponding stacking version of the game, more moves are allowed,
but the terminal position will be the same. A pebble is obstructing if it is
stacked or in $X$ or covers an obstructing pebble.
\begin{proposition}
  The stacking version of the game in which only obstructing pebbles may be
  moved is strongly convergent.
\end{proposition}
\begin{proof}
  A consequence of the previous three propositions.  Note that the shot
count determines the length of the game.\qed
\end{proof}

To find out whether a set $X$ is unavoidable, one can play the game level
after level, allowing temporary stacking of pebbles.  The {\em level} of
a node $x$ is the length of the shortest path from \^ 0 to $x$. Starting
at level zero and proceeding one level at a time, one fires all obstructing
pebbles on that level.  This is called {\em level trimming}.
\begin{proposition}
  The set $X$ is unavoidable if and only if the level trimming procedure
  can go on forever, without running out of obstructing pebbles.
\end{proposition}
\begin{proof}
  Suppose that $X$ can be emptied in a finite game with shot count $f$.
It is obvious that the trimming procedure has a shot count $g$ with
$g\le f$, componentwise, and the proposition follows from this.\qed
\end{proof}

\begin{definition}
  The {\em voidance set} of a game consists of all points that at some
  stage were visited by a pebble but are empty by the end of the game.
\end{definition} 
\medskip
\begin{proposition}\label{voidance}
  There is a one-to-one-to-one correpondence between reachable positions, 
  shot counts and voidance sets.
\end{proposition}
\begin{proof}
  There is only one small thing left to prove, namely that the shot count
  $f$ can be reconstructed from its voidance set.  It is evident that level 
  trimming produces one candidate, say $f^*$, with only absolutely necessary
  firings, so $f^*\le f$ componentwise.  Suppose that there are nodes $x$ 
  for which $f^*(x)<f(x)$, and choose such a node on the lowest possible
  level. Level trimming must leave a pebble on $x$ since it can be fired once 
  more, therefore $x$ is not in the voidance set of $f^*$, but it is in the
  voidance set of $f$, contrary to our assumption.\qed
\end{proof}

A set $X$ is {\em minimal unavoidable} if all strict subsets of $X$ are
avoidable. A characterization of minimal unavoidable sets is easy
as soon as all voidance sets are known, for we have the following result.
\begin{proposition}\label{mus}
  Let $X$ be a minimal unavoidable set and $x$ a node on the highest
  level in $X$.  Then $X-\{ x\}$ is a voidance set.
\end{proposition}
\begin{proof}
Because of the minimality, $X-\{ x\}$ is avoidable, so level trimming is a
finite procedure.  Any uninteresting point $y\in X$, untouched in this level 
trimming, would be as uninteresting in the continued infinite level trimming 
of $X$, for the influence of $x$ is noticeable only on higher levels.
Therefore, $X-\{ y\}$ would still be unavoidable, contradicting minimality.
\qed
\end{proof}
\medskip 

In the sequel, we shall concentrate on shot counts, as characterized by
Proposition  \ref{shotcount}.  The {\em support} of a shot count is the subposet
of nodes that have been fired, i.e.\ with nonzero shot count.
In the ${\Bbb Z}^n$ case, this subposet has very nice properties, and the
reason for this turns out to be that the poset of points in the first
orthant has V-completion.

\begin{definition}
  A poset $P$ has{\em V-completion} if whenever $y_1$ and $y_2$ cover $x$,
there is 
\begin{picture}(30,13)(-32,20)
\put(7,3){\line(-1,1){10}}
\put(13,3){\line(1,1){10}}
\put(9,29){\line(-1,-1){10}}
\put(11,29){\line(1,-1){10}}
\put(8,0){$x$}
\put(8,30){$z$}
\put(-6,15){$y_1$}
\put(20,15){$y_2$}
\end{picture} \\
a node $z$ covering both $y_1$ and $y_2$.
\end{definition}

\begin{proposition}\label{v}
 For a poset $P$ with V-completion, the support of any
 shot count is a {\em ranked poset} (even if $P$ is not) and has a
 {\em unique maximal element} (even though $P$ has not).
\end{proposition}
\begin{proof}
 The support $\supp f$ also has V-completion, for if $x, y_1, y_2$ are
 in $\supp f$ (see illustration above),
 by Proposition \ref{shotcount} we get $f(z)\ge f(y_1)+f(y_2)-1\ge 1$, so $z$
 is also in the support.  V-completion is the simplest case of the
 polygon property, so there is strong convergence and a unique terminal,
 i.e.\ maximal node.
 All paths to this terminal have equal length and this provides the ranking.
 \qed
\end{proof}

\begin{corollary}
  For a pebbling game in ${\Bbb Z}^n$, let $k$ be the highest level on
  which pebbles have been fired.  Then, exactly one firing took place
  on level $k$.
\end{corollary}

\noindent
Unexpectedly, the characterization of reachable pebble positions is
somewhat more difficult in the plane than in higher dimensions.  The
reason is that in higher ${\Bbb Z}^n$, {\em every node is
covered by at least three nodes}.

Such a poset must be infinite, so the triple-cover property
never applies to the subset $\supp f$ for any shot count $f$.  However,
a more interesting property follows, namely the dual of V-completion.

\begin{definition}
  A poset $P$ has {\em $\Lambda$-completion} if whenever $z$ covers $y_1$ and 
  $y_2$, there is
\begin{picture}(30,13)(-22,20)
\put(7,3){\line(-1,1){10}}
\put(13,3){\line(1,1){10}}
\put(9,29){\line(-1,-1){10}}
\put(11,29){\line(1,-1){10}}
\put(8,0){$x$}
\put(8,30){$z$}
\put(-6,15){$y_1$}
\put(20,15){$y_2$}
\end{picture} \\
 a node $x$ covered by both $y_1$ and $y_2$.
\end{definition}

\begin{proposition}\label{lambda}
  If a poset $P$ has V-completion and if every node is covered by at least
  three nodes, then 
  $f(x)=1$ for any shot count $f$ and any node $x$ in $\supp f$.  Further,
  $\supp f$ has $\Lambda$-completion. 
\end{proposition}

\begin{proof}
  In order to carry out a (finite) induction proof of the statement $f(x)=1$,
  we shall need a stronger induction assumption.

$Q(n)$: Level $n$ and all higher levels of $\supp f$ have $f(x)=1$ and contain
no tridents
\begin{picture}(35,10)(-7,0)
\put(0,0){\line(1,1){10}}
\put(10,0){\line(0,1){10}}
\put(20,0){\line(-1,1){10}}
\put(0,0){\circle*{4}}
\put(10,0){\circle*{4}}
\put(20,0){\circle*{4}}
\put(10,10){\circle*{4}}
\end{picture}
or
\begin{picture}(35,13)(-7,3)
\put(0,10){\line(1,-1){10}}
\put(10,0){\line(0,1){10}}
\put(20,10){\line(-1,-1){10}}
\put(0,10){\circle*{4}}
\put(10,10){\circle*{4}}
\put(20,10){\circle*{4}}
\put(10,0){\circle*{4}}
\end{picture},
nor any of the following zig-zag shapes:
\begin{picture}(30,10)(-3,0)
\put(0,0){\line(0,1){10}}
\put(20,0){\line(0,1){10}}
\put(0,0){\line(1,1){10}}
\put(10,0){\line(1,1){10}}
\put(0,10){\line(1,-1){10}}
\put(10,10){\line(1,-1){10}}
\put(0,0){\circle*{4}}
\put(10,0){\circle*{4}}
\put(20,0){\circle*{4}}
\put(0,10){\circle*{4}}
\put(10,10){\circle*{4}}
\put(20,10){\circle*{4}}
\end{picture},
\begin{picture}(40,10)(-3,0)
\put(0,0){\line(0,1){10}}
\put(30,0){\line(0,1){10}}
\put(0,0){\line(1,1){10}}
\put(10,0){\line(1,1){10}}
\put(20,0){\line(1,1){10}}
\put(0,10){\line(1,-1){10}}
\put(10,10){\line(1,-1){10}}
\put(20,10){\line(1,-1){10}}
\put(0,0){\circle*{4}}
\put(10,0){\circle*{4}}
\put(20,0){\circle*{4}}
\put(30,0){\circle*{4}}
\put(0,10){\circle*{4}}
\put(10,10){\circle*{4}}
\put(20,10){\circle*{4}}
\put(30,10){\circle*{4}}
\end{picture},
\begin{picture}(50,10)(-3,0)
\put(0,0){\line(0,1){10}}
\put(40,0){\line(0,1){10}}
\put(0,0){\line(1,1){10}}
\put(10,0){\line(1,1){10}}
\put(20,0){\line(1,1){10}}
\put(30,0){\line(1,1){10}}
\put(0,10){\line(1,-1){10}}
\put(10,10){\line(1,-1){10}}
\put(20,10){\line(1,-1){10}}
\put(30,10){\line(1,-1){10}}
\put(0,0){\circle*{4}}
\put(10,0){\circle*{4}}
\put(20,0){\circle*{4}}
\put(30,0){\circle*{4}}
\put(40,0){\circle*{4}}
\put(0,10){\circle*{4}}
\put(10,10){\circle*{4}}
\put(20,10){\circle*{4}}
\put(30,10){\circle*{4}}
\put(40,10){\circle*{4}}
\end{picture} $,\ldots$

By Proposition  \ref{v}, the assumption is true for the very highest level. 
From $Q(n)$, one can infer $Q(n-1)$, as follows. 
A trident 
\begin{picture}(35,10)(-7,0)
\put(0,0){\line(1,1){10}}
\put(10,0){\line(0,1){10}}
\put(20,0){\line(-1,1){10}}
\put(0,0){\circle*{4}}
\put(10,0){\circle*{4}}
\put(20,0){\circle*{4}}
\put(10,10){\circle*{4}}
\end{picture}
on level $n-1$ would mean $f(z)\ge 2$ on level $n$.  A trident
\begin{picture}(35,13)(-7,3)
\put(0,10){\line(1,-1){10}}
\put(10,0){\line(0,1){10}}
\put(20,10){\line(-1,-1){10}}
\put(0,10){\circle*{4}}
\put(10,10){\circle*{4}}
\put(20,10){\circle*{4}}
\put(10,0){\circle*{4}}
\end{picture}
can be V-completed to either
\begin{picture}(30,10)(-3,0)
\put(0,0){\line(0,1){10}}
\put(20,0){\line(0,1){10}}
\put(0,0){\line(1,1){10}}
\put(10,0){\line(1,1){10}}
\put(0,10){\line(1,-1){10}}
\put(10,10){\line(1,-1){10}}
\put(0,0){\circle*{4}}
\put(10,0){\circle*{4}}
\put(20,0){\circle*{4}}
\put(0,10){\circle*{4}}
\put(10,10){\circle*{4}}
\put(20,10){\circle*{4}}
\put(10,-10){\circle*{4}}
\put(10,-10){\line(1,1){10}}
\put(10,-10){\line(-1,1){10}}
\put(10,-10){\line(0,1){10}}
\end{picture},
a forbidden zig-zag, or 
\begin{picture}(30,10)(-3,0)
\put(0,0){\line(1,1){10}}
\put(10,0){\line(0,1){10}}
\put(20,0){\line(-1,1){10}}
\put(0,0){\circle*{4}}
\put(10,0){\circle*{4}}
\put(20,0){\circle*{4}}
\put(10,10){\circle*{4}}
\put(10,-10){\circle*{4}}
\put(10,-10){\line(1,1){10}}
\put(10,-10){\line(-1,1){10}}
\put(10,-10){\line(0,1){10}}
\end{picture},
a forbidden trident.  

\medskip
A node $x$ on level $n-1$ with $f(x)\ge 2$ will have at least
three covering nodes $y_1, y_2, y_3$ in $P$ and since
$f(y_i)\ge 1$, that means a forbiddent trident.
Finally, if there is a zig-zag on level $n-1$, V-completion gives either a
zig-zag or a trident on level $n$.

Thus, we have proved $Q(0)$ and the first part of the proposition.  We now
assume that there is some $\Lambda$-shape that cannot be completed to a
quadrangle.  Let the shortest completing polygon have bottom element $x$.
We know that such a polygon exists, for $x$ may be \^ 0.  Completing the
bottom V we get $z$, distinct from $u_1$ and $v_1$ in the figure (or there
would be a shorter polygon).\par 
\begin{picture}(100,30)(-53,-5)
\put(0,0){\line(0,1){10}}
\put(20,0){\line(0,1){10}}
\put(0,0){\circle*{4}}
\put(20,0){\circle*{4}}
\put(10,-10){\circle*{4}}
\put(10,-10){\line(1,1){10}}
\put(10,-10){\line(-1,1){10}}
\put(-11.5,-4){$u_0$}
\put(22,-4){$v_0$}
\put(7,-17.5){$x$}
\end{picture} {\Large$\Rightarrow$}
\begin{picture}(70,30)(-23,-5)
\put(0,0){\line(0,1){10}}
\put(0,0){\line(1,1){10}}
\put(20,0){\line(0,1){10}}
\put(20,0){\line(-1,1){10}}
\put(0,0){\circle*{4}}
\put(0,10){\circle*{4}}
\put(20,10){\circle*{4}}
\put(20,0){\circle*{4}}
\put(10,10){\circle*{4}}
\put(10,-10){\circle*{4}}
\put(10,-10){\line(1,1){10}}
\put(10,-10){\line(-1,1){10}}
\put(-11.5,6){$u_1$}
\put(-11.5,-4){$u_0$}
\put(22,6){$v_1$}
\put(22,-4){$v_0$}
\put(7,-17.5){$x$}
\put(8,12.5){$z$}
\end{picture}
{\Large$\Rightarrow$}
\begin{picture}(70,35)(-23,-5)
\put(20,10){\line(-2,3){7}}
\put(0,10){\line(2,3){7}}
\put(0,0){\line(0,1){20}}
\put(0,0){\line(1,1){10}}
\put(20,0){\line(0,1){20}}
\put(20,0){\line(-1,1){10}}
\put(10,10){\line(1,3){4}}
\put(10,10){\line(-1,3){4}}
\put(0,0){\circle*{4}}
\put(0,10){\circle*{4}}
\put(20,10){\circle*{4}}
\put(20,0){\circle*{4}}
\put(10,10){\circle*{4}}
\put(10,-10){\circle*{4}}
\put(0,20){\circle*{4}}
\put(20,20){\circle*{4}}
\put(6.7,20){\circle*{4}}
\put(13.3,20){\circle*{4}}
\put(10,-10){\line(1,1){10}}
\put(10,-10){\line(-1,1){10}}
\put(-11.5,16){$u_2$}
\put(-11.5,6){$u_1$}
\put(-11.5,-4){$u_0$}
\put(22,16){$v_2$}
\put(22,6){$v_1$}
\put(22,-4){$v_0$}
\put(7,-17.5){$x$}
\put(3,22.5){$z'$}
\put(11,22.5){$z''$}
\end{picture}\medskip

\noindent
Now, there are two V-s to be completed and the same argument shows
that $z'$ and $z''$ must be distinct from $u_2$ and $v_2$, but also
distinct from each other, for we cannot have a trident
\begin{picture}(35,10)(-7,0)
\put(0,0){\line(1,1){10}}
\put(10,0){\line(0,1){10}}
\put(20,0){\line(-1,1){10}}
\put(0,0){\circle*{4}}
\put(10,0){\circle*{4}}
\put(20,0){\circle*{4}}
\put(10,10){\circle*{4}}
\end{picture}.

  
Iterating, we move up level for level and the final $\Lambda$-shape
($u_n=v_n$)
must produce a zig-zag, contradicting the $Q$-property just proved. \qed
\end{proof}\medskip

Scrutinizing the proof, one finds that the assumption about triple covers
in $P$ is used only to prove $f(x)=1$, which in turn is used only to prove
nonexistence of 
\begin{picture}(31,10)(-7,0)
\put(0,0){\line(1,1){10}}
\put(10,0){\line(0,1){10}}
\put(20,0){\line(-1,1){10}}
\put(0,0){\circle*{4}}
\put(10,0){\circle*{4}}
\put(20,0){\circle*{4}}
\put(10,10){\circle*{4}}
\end{picture}-tridents.
  Thus, there is a weaker form of the proposition with the advantage that
it can be applied to ${\Bbb Z}^2$.

\begin{proposition}\label{notrident}
  If a poset $P$ has V-completion and $f$ is a shot count such that $\supp f$
  has no 
  \begin{picture}(31,10)(-7,0)
\put(0,0){\line(1,1){10}}
\put(10,0){\line(0,1){10}}
\put(20,0){\line(-1,1){10}}
\put(0,0){\circle*{4}}
\put(10,0){\circle*{4}}
\put(20,0){\circle*{4}}
\put(10,10){\circle*{4}}
\end{picture}-tridents, then $\supp f$ has $\Lambda$-completion.
\end{proposition}

\begin{remark}
  The subposets $\supp f$ of the last two propositions contain no tridents or
zig-zags, but they may contain the X-shape
\begin{picture}(20,10)(-3,0)
\put(0,0){\line(0,1){10}}
\put(10,0){\line(0,1){10}}
\put(0,0){\line(1,1){10}}
\put(10,0){\line(-1,1){10}}
\put(0,0){\circle*{4}}
\put(10,0){\circle*{4}}
\put(0,10){\circle*{4}}
\put(10,10){\circle*{4}}
\end{picture}.
  By repeated V-completion upwards and $\Lambda$-completion downwards, one
finds that an X-shape must be part of a {\em dihedral interval}, 
e.g. this one: 
\begin{picture}(12,15)(-13,15)
\put(10,0){\line(-1,-2){5}}
\put(0,0){\line(1,-2){5}}
\put(0,0){\line(0,1){20}}
\put(10,0){\line(0,1){20}}
\put(0,0){\line(1,1){10}}
\put(10,0){\line(-1,1){10}}
\put(0,10){\line(1,1){10}}
\put(10,10){\line(-1,1){10}}
\put(10,20){\line(-1,2){5}}
\put(0,20){\line(1,2){5}}
\put(5,-10){\circle*{4}}
\put(0,0){\circle*{4}}
\put(10,0){\circle*{4}}
\put(0,10){\circle*{4}}
\put(0,20){\circle*{4}}
\put(10,10){\circle*{4}}
\put(10,20){\circle*{4}}
\put(5,30){\circle*{4}}
\end{picture}\\
(This is the Bruhat poset of the dihedral group $I_2(4)$.)
The poset $P$ may continue below\\ 
the V and above the $\Lambda$, but on the levels in-between
there are no nodes outside the dihedral interval.  This is an easy consequence 
of Proposition \ref{v}.  Therefore, all dihedral intervals, if any, may be 
replaced by quadrangles
\begin{picture}(20,12)(-1,-3)
\put(-1,-1){\line(1,1){10}}
\put(17,-1){\line(-1,1){10}}
\put(-1,1){\line(1,-1){10}}
\put(17,1){\line(-1,-1){10}}
\put(0,0){\circle*{4}}
\put(16,0){\circle*{4}}
\put(8,-8){\circle*{4}}
\put(8,8){\circle*{4}}
\end{picture},
while maintaining the shot count properties.  Conversely, if a shot count poset
has some level with only two nodes on it, then the quadrangle containg these 
nodes may be expanded into a dihedral interval.  Therefore, a characterization
of shot count posets may as well assume that there are no X-shapes.
\end{remark}

  The following characterization is valid for all ${\Bbb Z}^n$ but its main
result is that everything may be considered as taking place in ${\Bbb Z}^2$.
The pebbling game may meander through all $n$ dimensions, 
but the poset structure of the shot count is planar.

\begin{proposition}\label{polyominoid}
 If a pebbling game is played on a poset $P$ with V-completion 
and the nodes that have been fired form a subposet without
\begin{picture}(31,10)(-7,0)
\put(0,0){\line(1,1){10}}
\put(10,0){\line(0,1){10}}
\put(20,0){\line(-1,1){10}}
\put(0,0){\circle*{4}}
\put(10,0){\circle*{4}}
\put(20,0){\circle*{4}}
\put(10,10){\circle*{4}}
\end{picture}-tridents or X-shapes
\begin{picture}(20,10)(-3,0)
\put(0,0){\line(0,1){10}}
\put(10,0){\line(0,1){10}}
\put(0,0){\line(1,1){10}}
\put(10,0){\line(-1,1){10}}
\put(0,0){\circle*{4}}
\put(10,0){\circle*{4}}
\put(0,10){\circle*{4}}
\put(10,10){\circle*{4}}
\end{picture}, 
then this subposet is isomorphic to a polyominoid subset of
${\Bbb Z}^2$.
\end{proposition}
\begin{proof}
Assume that the embedding has been constructed for levels zero through $k$, 
so the last two levels look something like
\begin{picture}(60,10)(-3,0)
\put(0,0){\line(1,1){10}}
\put(20,0){\line(1,1){10}}
\put(40,0){\line(1,1){10}}
\put(10,10){\line(1,-1){10}}
\put(30,10){\line(1,-1){10}}
\put(0,0){\circle*{4}}
\put(20,0){\circle*{4}}
\put(40,0){\circle*{4}}
\put(10,10){\circle*{4}}
\put(30,10){\circle*{4}}
\put(50,10){\circle*{4}}
\end{picture}.
V-completion forces an extension to level $k+1$ and $\Lambda$-extension
justifies it. Since 
\begin{picture}(31,10)(-7,0)
\put(0,0){\line(1,1){10}}
\put(10,0){\line(0,1){10}}
\put(20,0){\line(-1,1){10}}
\put(0,0){\circle*{4}}
\put(10,0){\circle*{4}}
\put(20,0){\circle*{4}}
\put(10,10){\circle*{4}}
\end{picture}-tridents cannot occur, everything is specified except
whether the boundary points on level $k$ have single or double covers.
In both cases, the embedding is straight-forward.
\end{proof}

\section{Conclusions and acknowledgements}

The pebbling game is closely related to the {\em checker jumping game},
where a move looks like 
\begin{picture}(50,10)(-5,-3)
\put(-5,-5){\line(1,0){30}}
\put(-5,-5){\line(0,1){10}}
\put(-5, 5){\line(1,0){30}}
\put(25,-5){\line(0,1){10}}
\put(0,0){\circle{7}}
\put(10,0){\circle{7}}
\put(20,0){\circle*{1}}
\put(29,1){\thicklines\vector(1,0){15}}
\end{picture}
\begin{picture}(40,10)(-10,-3)
\put(-5,-5){\line(1,0){30}}
\put(-5,-5){\line(0,1){10}}
\put(-5, 5){\line(1,0){30}}
\put(25,-5){\line(0,1){10}}
\put(0,0){\circle*{1}}
\put(10,0){\circle*{1}}
\put(20,0){\circle{7}}
\end{picture}, in any direction. 
The main difference seems to be that pebbling
moves create pebbles while checker jumps annihilate checkers, but
that is only a superficial discrepancy.  If checkers were small and
empty gridpoints large, a natural interpretation of the move
\begin{picture}(50,10)(-5,-3)
\put(-5,-5){\line(1,0){30}}
\put(-5,-5){\line(0,1){10}}
\put(-5, 5){\line(1,0){30}}
\put(25,-5){\line(0,1){10}}
\put(0,0){\circle{5}}
\put(10,0){\circle{5}}
\put(20,0){\circle*{7}}
\put(29,1){\thicklines\vector(1,0){15}}
\end{picture}
\begin{picture}(40,10)(-10,-3)
\put(-5,-5){\line(1,0){30}}
\put(-5,-5){\line(0,1){10}}
\put(-5, 5){\line(1,0){30}}
\put(25,-5){\line(0,1){10}}
\put(0,0){\circle*{7}}
\put(10,0){\circle*{7}}
\put(20,0){\circle{5}}
\end{picture}
would be that a black spot is created!
Exactly the same invariant weight method can be used in both games, but for
some reason, it is much more successful in checker jumping.  In fact, 
the bounds stemming from weight considerations are sharp for the natural
reachability problems solved by Eriksson and Lindstr\"om \cite{EL},
but far from sharp in pebbling.

Our interpretation of pebbling as a strongly convergent
game demonstrates the similarity with the {\em chip firing} game of Bj\"orner,
Lov\'asz and Shor \cite{BLS}. Chips can accumulate on the nodes and when
a node is fired, it sends one chip to each neighbour. Some of the chip firing
analysis can be applied to pebbling, but the most interesting part focuses
on recurrent positions, and that phenomenon cannot occur in pebbling.

No, pebbling has its own special features and the most astonishing is the
uniform structure of reachable positions, regardless of whether the game is
played on ${\Bbb Z}^3$, ${\Bbb Z}^{17}$ or any poset satisfying a few
regularity conditions.  In all cases, the same combinatorial object emerges:
the folded polyominoid. In addition to the geometric and game interpretations
there are several others.  The set of paths leading from the origin to the
highest point of the polyominoid may be seen as a set of words in an 
$n$-letter alphabet and this is often, but not always, an equivalence class
corresponding to some commutation relations (a {\em trace} according to
Cartier and Foata \cite{CF}).  Of special interest is the {\em Coxeter group}
case and many folded polyominoids occur as intervals in the Cayley graph of
the appropriate Coxeter group, as shown in \cite{E1}.  
Finally, a {\em heap of pieces} in the sense
of Viennot \cite{Vi} can be associated to every folded polyominoid in a 
number of ways.

Paul Vaderlind, who drew my attention to the pebbling game,
also independently discovered Proposition \ref{nk} and analysed a
generalization to acyclic digraphs, not presented in this paper.
Interesting identities involving our generating functions $g$ and $h$  
were found by Douglas Rogers (unpublished).

\begin{thebibliography}{ABC}
\frenchspacing
\bibitem{BLS} A. Bj{\"o}rner, L. Lov\'asz and P. W. Shor,
{\sl Chip-firing games on graphs}, European J.Combin. {\bf 12}, 1991, 283--291.

\bibitem{CF} P. Cartier and D. Foata, {\sl Probl\`emes combinatoires de 
commutations et r\'earrangements}, Lecture Notes in Maths {\bf 85}, 1969,
Springer, Berlin.

\bibitem{FGMO} F. Chung, R. Graham, J. Morrison and A. Odlyzko,
{\sl Pebbling a chessboard}, Amer. Math. Monthly {\bf 102}, 1995, 113--123.

\bibitem{DV} M. Delest and X. Viennot, {\sl Algebraic languages and polyominoes
enumeration}, Theoretical Computer Science {\bf 34}, 1984, 169--206.

\bibitem{EL} H. Eriksson and B. Lindstr\"om,
{\sl Twin checker jumping}, to appear in European J.Combin., 1995.

\bibitem{E1} H. Eriksson,
{\sl Computational and combinatorial aspects of Coxeter groups}, PhD thesis, 
KTH, Stockholm, 1994.

\bibitem{E} K. Eriksson,
{\sl Strong convergence and Coxeter groups}, PhD thesis, KTH, Stockholm, 1993.

\bibitem{GV} I. Gessel and X. Viennot,
{\sl Binomial determinants, paths and hook length formulae},
Advances in Math. {\bf 58}, 1985, 300--321.

\bibitem{HC} R.L. Graham, M. Gr\"otschel and L. Lov\'asz, editors,
{\sl Handbook of Combinatorics},
North--Holland, 1993. To appear.

\bibitem{Kh} A. Khodulev, {\sl Pebble spreading}, Kvant, July 1982, 28--31. (
In Russian.)

\bibitem{K} M. Kontsevich, Problem M715, Kvant, Nov. 1981, p21. (In Russian.)

\bibitem{V} P. Vaderlind, Stockholm University, 1993. (Personal communication.)

\bibitem{Vi} X. Viennot,
{\sl Heaps of pieces, I: Basic definitions and combinatorial lemmas}, in
{\sl Combinatoire \'enum\'erative}, Lecture Notes in Maths {\bf 1234}, 1986,
321--350, Springer, Berlin.


\end{thebibliography}

\end{document}