Pebblings Sweden

                           henrik@nada.kth.se

Submitted: June 15, 1994; Accepted: April 5, 1995

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. Subject Classification: Primary 05A15; secondary 05E99.

1 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: [figure] [figure] . 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) | i + j ≤ 3}, form an 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 ∑_{i,j≥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 [10] made the surprising observation, that already the fivepoint set [figure] is unavoidable. The first complete proof appeared thirteen years later in the American Mathematical Monthly [3], 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.

2 Pebbling in Z^{n}

The n-dimensional version of the game, suggested by Paul Vaderlind [12], 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 weight of a pebble with coordinates (x_{1}, …, x_{n}) is n^{−x_{1}−···−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

∑_{x_{i}≥0}n^{−x_{1}−x_{2}−···} = (∑_{i=0}^{∞}n^{−i})^{n} = (1 − \frac{1}{n})^{−n} → e when n → ∞

Weight calculations can be used to prove that a certain point set is unavoidable, for example the seven-point set in ^{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 …,

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.

Proposition 1 The four-point set in ^{n}, n ≥ 3 consisting of the origin and three neighbour points is unavoidable.

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 4 below. □

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 [3] 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.

Fact 2 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.

The 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 level trimming procedure for determining whether or not a set of points, X, is unavoidable is given in [3]. 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.

Fact 3 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.

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 13.

Proposition 4 Let level k be the last one containing a point from X ⊂ ^{n} and consider the configurations after trimming levels 1, 2, …, 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.

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 [3], so we can assume n ≥ 3. If there are three or more pebbles on a point, x = (x_{1}, x_{2}, x_{3}, …), at least two of these must propagate to each of the points (x_{1}+1, x_{2}, x_{3}, …), (x_{1}, x_{2}+1, x_{3}, …) and (x_{1}, x_{2}, x_{3}+1, …) (an equilateral triangle on the next level). On the next level, each point in the triangle (x_{1} + 1, x_{2} + 1, x_{3}, …), (x_{1}, x_{2} + 1, x_{3} + 1, …) and (x_{1} + 1, x_{2}, x_{3} + 1, …) 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, …). 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, …, 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. □

A byproduct of the proof is a polynomial bound for the length of the game corresponding to an avoidable set X. Again, a much better bound will appear in Theorem 13. 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.

Definition. The voidance set of a (finite) pebbling game consists of all points in ^{n} that at some stage were pebble points but end up empty.

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 20), we shall show that games leading to the same position have the same voidance set.

Fact 5 A reachable game position is completely specified by its voidance set.

As combinatorial objects, voidance sets are more tractable than reachable positions, not to mention pebbling games. A hundred-point voidance set in ^{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.

Definition. A polyominoid set in ^{2} consists of all points on or between two lattice paths with common starting point and common ending point. As demonstrated in Fig.1, 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 left boundary point if (x − 1, y) is not in the polyominoid and a lower boundary point if (x, y − 1) is not in the polyominoid.

Observation 6 Polyominoid sets correspond bijectively to parallelogram polyominoes in the sense of M.Delest and X.Viennot [4]. 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.

[figure: ↔; ↔]

Figure 1: Two polyominoes with polyominoids and left-lower boundary points.

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 [4] and [8]. Still, for conveniency we give the proof in the polyominoid case.

Proposition 7 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}\binom{2k + 2}{k + 1} = \binom{2k}{k} − \binom{2k}{k − 2}

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, u, 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 \binom{2k}{k} of these.

The polyominoid (weakly noncrossing) condition is ∑_{1}^{r} u_{i} ≤ ∑_{1}^{r} v_{i} for all 1 ≤ r ≤ k. Otherwise, let r′ be the first index for which ∑_{1}^{r′} u_{i} = 1 + ∑_{1}^{r′} v_{i} and let us switch the (k − r′)-tails between u and v. Now, there are two more ones in the first vector, u′, than in the second, 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 \binom{2k}{k−2}. □

Proposition 8 The points played in a pebbling game on ^{2} form a polyominoid.

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. □

Every pebbling game in ^{2} defines a polyominoid, viz. the set of all points that have been played. In ^{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.

Definition. A folded polyominoid set in ^{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.

[figure: x; x; x; z; z; x; y; x; y; y; y; y; y; y; z; z; z; x; z; x; y; y; y; z; u = (y, y, 0, 0, z, 0, 0); v = (x, 0, z, 0, x, y, 0)]

Figure 2: A folded polyominoid with left-lower labels and label vectors.

Labelling of left and lower edges may be seen as distribution of k labels over 2k places, namely the pair of k-vectors u and 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 |u_{...r}| for the number of labels in the initial r-segment of u. Thus, moving r steps along the left boundary path, we go |u_{...r}| steps upward and r − |u_{...r}| steps to the right. And moving r steps along the lower boundary path, we go |v_{...r}| steps to the right and r − |v_{...r}| steps upwards.

Theorem 9 For pebbling in ^{n} with n ≥ 3, the following combinatorial objects correspond bijectively to each other.

1. Reachable positions with the highest pebble on level k + 1.

2. Voidance sets of cardinality k + 1.

3. Folded polyominoids with boundary path lengths k.

4. Pairs of integer k-vectors, u and v, with a total of k nonzero elements (labels) in {1, …, n}, such that

(a) if for any 0 ≤ r < k, |u_{...r}| + |v_{...r}| = r then u_{r+1} ≤ v_{r+1},
(b) |u_{...r}| + |v_{...r}| ≥ r for all 1 ≤ r ≤ k,
(c) if the same label occurs in u_{i} and v_{j}, then |u_{...i}| + |v_{...j}| ≤ max(i, j).

Proof. The folded polyominoid characterization of reachable positions in ^{n} will emerge as a corollary of Proposition 27. In dimension three and higher, no node is played twice (this will be proved in Proposition 24), 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 u and v. For both paths reach the same point in r steps if and only if |u_{...r}| + |v_{...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 7 correspond to our vectors in a somewhat confusing way: the nonzero labels in u mean binary zeroes and zero labels mean binary ones, in 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 |v_{...j}| ≤ i − |u_{...i}|, or u_{i} is below v_{j}, which means |u_{...i}| ≤ j − |v_{...j}|. □

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{matrix}f_{k,n} & n = 1 & n = 2 & n = 3 & n = 4 & n = 5 & n = 6 \\ k = 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ k = 1 & 1 & 2 & 3 & 4 & 5 & 6 \\ k = 2 & 1 & 5 & 12 & 22 & 35 & 51 \\ k = 3 & 1 & 14 & 57 & 148 & 305 & 546 \\ k = 4 & 1 & 42 & 300 & 1126 & 3045 & 6756 \\ k = 5 & 1 & 132 & 1680 & 9220 & 32985 & 91236 \end{matrix}

Figure 3: Number of folded polyominoes in ^{n} with circumference 2k.

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. [figure: →] [figure] . Let us call this configuration a crossing.

Theorem 10 For pebbling in ^{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} + ⋯

with asymptotic behaviour g_{k} ∼ const · G^{k}, where G = 4.112 . . ..

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 ≥ 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} + ⋯

with asymptotic behaviour h_{k} ∼ const · G^{k}, where G = 4.147 . . ..

Proof. Knowing that the number of unmarked polyominoids is C_{k+1}, we can write down a recursion

g_{k} = C_{k+1} + ∑_{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 [figure] on level r, for we have to subtract polyominoids ending with [figure] or [figure]. By the same reasoning, the number of marked polyominoids starting with [figure] 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} + ∑_{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 [9]) as 1/(smallest root). Exponents greater than four were to be expected, since C_{k} ∼ const · 4^{k}. □

An important part of the paper by Chung, Graham, Morrison and Odlyzko is the enumeration of minimal unavoidable sets in ^{2}. The asymptotic expression found is const · γ^{k} with γ = 4.147 …, exactly our result when counting voidance sets! The agreement is hardly a coincidence, for in Proposition 21 of next section, we prove that 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.

Theorem 11 Every minimal unavoidable set in ^{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} + ⋯

with asymptotic behaviour m_{k} ∼ const · H^{k}, where H = 4.147 . . ..

Proof. Let us look at all possibilities of adding an extra unavoidable point to a marked polyominoid ending like [figure], 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. [figure]. The corner point can also be emptied by building a new marked crossing [figure]. Other polyominoid points, however, really are unavoidable (for emptying them would stack three pebbles somewhere), but only the corner neighbours produce minimal unavoidable sets. In, for example, [figure], the last lower boundary point could be deleted.

So either of the corner neighbours in [figure], produces a minimal unavoidable set together with the left and lower boundary points. The same reasoning for the special cases [figure] et cetera shows that the configurations [figure] and [figure] always produce one minimal unavoidable set each, and those are all there are.

Counting marked polyominoids ending in [figure] is a simple matter. There are h_{k−2} − 2h_{k−3} of type and from these we subtract h_{k−3}−h_{k−4} of type [figure], 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). □

There are four four-point unavoidable sets in ^{3}. The origin and its three neighbours was proved unavoidable in Proposition 1. The square [figure] in any coordinate plane is also unavoidable, for no point may be fired twice in dimension n ≥ 3. These two examples of minimal unavoidable sets in ^{n} are, in fact, generic.

Theorem 12 Every minimal unavoidable set in ^{n} can be constructed from the left and lower boundary points of a folded polyominoid by adding one of the following points.

• The highest point of the folded polyominoid (unless it is already a left or lower boundary point).

• A point that forms an isoceles triangle with the two corner neighbours (provided that the folded polyominoid ends with a [figure] ).

Proof. Simpler than the two-dimensional case. One just has to test all positions of an extra point. □

Now, at last, we can state the optimal version of Proposition 4.

Theorem 13 Let level k in ^{n} be the last one containing a point from X and consider the configurations after trimming levels 1, …, 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.

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. □

3 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 covering x, that is to each u > x such that there is no v with u > v > x.

Following Björner, Lovász and Shor [1], we say that node x is 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 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.

Proposition 14 Different move sequences lead to the same position if and only if they have the same shot count.

Proof. A node x that was fired f(x) times has got ∑ f(y) − f(x) pebbles, where the sum is taken over all nodes y covered by x. □ 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.

Proposition 15 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 ∑ f(y) − f(x) = 0 or 1, where the sum is taken over all nodes y covered by x.

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. □

Proposition 16 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.

Proof. A consequence of the previous proposition. □

The last three propositions have the flavour of strong convergence, a concept introduced by Anders Björner and developed in [7]. A game is strongly convergent if either

• every possible game has the same length and ends in the same terminal position, or

• every game goes on for ever.

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 nodes to be emptied and call a pebble obstructing if it is in X or (recursive definition!) covers an obstructing pebble (i.e. its node covers the other pebble’s node).

Proposition 17 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.

Proof. As shown by Kimmo Eriksson, strong convergence of a game is equivalent to the 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 15 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. So the pebbling game has the polygon property and is therefore strongly convergent. □

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.

Proposition 18 The stacking version of the game in which only obstructing pebbles may be moved is strongly convergent.

Proof. A consequence of the previous three propositions. Note that the shot count determines the length of the game. □

To find out whether a set X is unavoidable, one can play the game level after level, allowing temporary stacking of pebbles. The 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 level trimming.

Proposition 19 The set X is unavoidable if and only if the level trimming procedure can go on forever, without running out of obstructing pebbles.

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 ≤ f, componentwise, and the proposition follows from this. □

Definition. The 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.

Proposition 20 There is a one-to-one-to-one correpondence between reachable positions, shot counts and voidance sets.

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^{∗} ≤ 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. □

A set X is 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.

Proposition 21 Let X be a minimal unavoidable set and x a node on the highest level in X. Then X − {x} is a voidance set.

Proof. Because of the minimality, X −{x} is avoidable, so level trimming is a finite procedure. Any uninteresting point y ∈ 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. □

In the sequel, we shall concentrate on shot counts, as characterized by Proposition 15. The support of a shot count is the subposet of nodes that have been fired, i.e. with nonzero shot count. In the ^{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.

Definition. A poset P hasV-completion if whenever y_{1} and y_{2} cover x, there is [figure: x; z; y_{1}; y_{2}] a node z covering both y_{1} and y_{2}.

Proposition 22 For a poset P with V-completion, the support of any shot count is a ranked poset (even if P is not) and has a unique maximal element (even though P has not).

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 15 we get f(z) ≥ f(y_{1}) + f(y_{2}) − 1 ≥ 1, so z is also in the support. Vcompletion 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. □

Corollary 23 For a pebbling game in ^{n}, let k be the highest level on which pebbles have been fired. Then, exactly one firing took place on level k.

Unexpectedly, the characterization of reachable pebble positions is somewhat more difficult in the plane than in higher dimensions. The reason is that in higher ^{n}, 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 Vcompletion.

Definition. A poset P has Λ-completion if whenever z covers y_{1} and y_{2}, there is [figure: x; z; y_{1}; y_{2}] a node x covered by both y_{1} and y_{2}.

Proposition 24 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 Λ-completion.

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 [figure] or [figure] , nor any of the following zig-zag shapes: [figure], [figure], [figure] , …

By Proposition 22, the assumption is true for the very highest level. From Q(n), one can infer Q(n − 1), as follows. A trident [figure] on level n − 1 would mean f(z) ≥ 2 on level n. A trident [figure] can be V-completed to either [figure], a forbidden zig-zag, or [figure], a forbidden trident.

A node x on level n − 1 with f(x) ≥ 2 will have at least three covering nodes y_{1}, y_{2}, y_{3} in P and since f(y_{i}) ≥ 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 Λ-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).

[figure: u_{0}; v_{0}; x] ⇒ [figure: u_{1}; u_{0}; v_{1}; v_{0}; x; z] ⇒ [figure: u_{2}; u_{1}; u_{0}; v_{2}; v_{1}; v_{0}; x; z′; z′′]

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 [figure] .

Iterating, we move up level for level and the final Λ-shape (u_{n} = v_{n}) must produce a zig-zag, contradicting the Q-property just proved. □

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 [figure]-tridents. Thus, there is a weaker form of the proposition with the advantage that it can be applied to ^{2}.

Proposition 25 If a poset P has V-completion and f is a shot count such that supp f has no [figure]-tridents, then supp f has Λ-completion.

Remark 26 The subposets supp f of the last two propositions contain no tridents or zig-zags, but they may contain the X-shape [figure]. By repeated V-completion upwards and Λ-completion downwards, one finds that an X-shape must be part of a dihedral interval, e.g. this one: [figure] (This is the Bruhat poset of the dihedral group I_{2}(4).) The poset P may continue below the V and above the Λ, but on the levels in-between there are no nodes outside the dihedral interval. This is an easy consequence of Proposition 22. Therefore, all dihedral intervals, if any, may be replaced by quadrangles [figure], 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.

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

Proposition 27 If a pebbling game is played on a poset P with V-completion and the nodes that have been fired form a subposet without [figure]-tridents or X-shapes [figure], then this subposet is isomorphic to a polyominoid subset of ^{2}.

Proof. Assume that the embedding has been constructed for levels zero through k, so the last two levels look something like [figure]. V-completion forces an extension to level k + 1 and Λ-extension justifies it. Since [figure]-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.