\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 rx$ 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)