WorksMathematics
Labeled Chip-Firing on Ordered Directed Graphs
Abstract
We study labeled chip-firing on rooted directed graphs where for each vertex , the children of are linearly ordered. When a vertex fires, the selected chips are sent to its children in increasing order. We show that homomorphisms preserving these child choices transport legal firing sequences. We then consider the directed lattice and ask which chips can reach a given vertex. We give a recurrence for the smallest reachable label when sufficiently many chips are present and show that consecutive pairing attains this minimum. Finally, we determine the largest reachable label by symmetry and prove that the reachable labels form an interval when the number of initial chips is sufficiently large.
Introduction
Unlabeled Chip-Firing Games
Chip-firing on a directed graph is a single-player game in which chips, a discrete commodity, are distributed among the vertices of a graph. A vertex of positive outdegree can fire if it contains at least as many chips as its outdegree. It then sends one chip to each of its children. Once no vertex can fire, the game stops; in this case, the resulting distribution of chips is called the stable configuration; see § 2 for formal definitions.
When the chips are indistinguishable, this game is called unlabeled chip-firing. A fundamental property of unlabeled chip-firing on directed graphs is the following global confluence result.
Theorem 1 ([1 Theorem 1.1]). Let be a directed graph with finitely many vertices, and let be an initial configuration of chips on . Starting from , continue firing vertices as long as a legal move is available. Either every such game continues forever, or every such game terminates. In the latter case, the final configuration and the number of times each vertex fires do not depend on the firing choices.
The same result holds for infinite directed graphs with finite outdegrees and finitely many initial chips. It follows from the least action principle and halting dichotomy for abelian networks; see [2 Lemmas 4.3 and 4.4], where infinite underlying graphs are allowed. For completeness, we give a proof in Lemma 2.
Labeled Chip-Firing
In labeled chip-firing, a variant of the chip-firing game, the chips are distinguishable. Here, the chips are labeled by integers. When a vertex fires, we pick chips and send one to each child of . Which chip is sent to which child depends on the chips’ labels. Labeled chip-firing was originally studied by Hopkins, McConville, and Propp [4] in the one-dimensional lattice setting. Since then, it has been studied in the context of undirected binary trees [10, 7] and also directed trees [5, 6].
In labeled chip-firing, the confluence property does not always hold, thereby opening a new field of study focused on the variety of stable configurations that can be obtained.
Example 1. Consider the directed binary tree with chips 1, 2, 3, 4 at the root. We can see in Figure 1 that if we fire pair (1, 2) at the root first and continue to stability, as opposed to firing pair (2, 3) at the root first and continuing to stability, we obtain two different stable configurations.

Figure 1. Example of confluence breaking
Motivation and Contribution
Two basic questions in labeled chip-firing are as follows:
Which stable configurations can occur?
How many possible stable configurations are there?
In [5, 9, 6], we studied these questions for directed -ary trees. Recursive methods are particularly useful on directed trees because once two chips follow different branches, they cannot meet again.
Another basic problem in labeled chip-firing is to understand which labels can reach which vertices. In the setting of directed -ary trees, we studied this question in [6].
In this paper, we extend the study to ordered directed graphs in general, where different paths may merge. As our example, we use the lattice .
Our main tool is an order-preserving homomorphism between rooted directed graphs. Such a homomorphism pushes labeled chip-firing strategies forward: if a chip can reach a vertex in the source graph, then the same chip can reach the image vertex in the target graph. We apply this principle to the natural homomorphism from the -ary tree to the lattice for .
We then study reachability questions for , including the dependence on the number of initial chips, an exact recursive description of the eventual smallest and largest reachable labels, an eventual interval theorem, asymptotic estimates, and bounds on the region where the elementary lower bound is sharp.
Roadmap
In Section 2, we introduce the labeled chip-firing game on rooted directed graphs, our running examples, and the tree results that we use later. Section 3 explains how homomorphisms transport firing sequences and relates the tree and line graphs to other ordered directed graphs. In Section 4, we apply these results to trees and lattices.
In Section 5, we study which labels can reach a given vertex of the two-dimensional lattice. For sufficiently many initial chips, we give a recurrence determining the smallest reachable label, obtain the largest by symmetry, and prove that every label between these extremes is reachable. We show that a strategy based on pairing chips consecutively in increasing order attains the minimum. We also derive an asymptotic formula and give bounds on where the elementary lower bound is sharp.
Definitions and Preliminaries
Chip-Firing on Ordered Directed Graphs
We first recall common terminology used to describe directed graphs. In a directed graph , for each directed edge , we say that vertex is a parent of , and the vertex is a child of . Our directed graphs are rooted; for each directed graph , we have a designated vertex , called the root. We say that a vertex is on layer if the shortest path that exists from to takes edges. In this paper, we assume that all directed graphs have a root. Also, we assume that for any directed graph , all vertices of have finite outdegree and can be reached by a path starting at the root of . We assume there are no parallel directed edges.
To define chip-firing, we formally introduce a class of directed graphs endowed with additional information about each vertex’s children. An ordered directed graph is a directed graph in which the children of each vertex have a linear order . A traversal string records a sequence of child choices starting at the root: at step , we move to the th child of the current vertex. We write for the vertex reached by these choices. The empty string corresponds to the root.
A vertex may have several traversal strings. Every vertex has exactly one traversal string if and only if the graph is a rooted directed tree. If has children, then its th child is for , where denotes the string obtained by appending to .
Let be an ordered directed graph. A configuration is a placement of chips on the vertices of . In labeled chip-firing, the chips are distinguishable and are labeled by consecutive positive integers.
A vertex can fire if and it contains at least chips. To fire , we choose chips at . If these chips have labels
then chip is sent to the th child of . Thus, the order of the children determines where the chosen chips go. The vertices with outdegree zero do not fire. A firing sequence is a finite sequence of legal firings. Formally, a firing sequence is a finite sequence of ordered pairs such that, for each , the vertex is the th vertex that is fired and is the set of chips fired in the th firing, where and and, after the first firings, every chip in is located at .
A configuration is stable if no vertex can fire. A strategy is a choice, at each step, of a vertex that can fire together with the chips to be fired from that vertex. A strategy is complete if its final configuration is stable.
The labeled game has the same underlying unlabeled chip movement as ordinary chip-firing: firing a vertex sends one chip to each child. Therefore, whenever the corresponding unlabeled chip-firing game terminates, every complete strategy fires each vertex the same number of times. Unless otherwise stated, we start with chips at the root.
We say that chip reaches a vertex if it is at at some time during the game, including the initial configuration. It passes through if it is later fired from , and it lands at if it is at in the final stable configuration. On a graph with directed cycles, a chip may pass through a vertex and later land there.
We recall the following standard confluence result for unlabeled chip-firing on possibly infinite directed graphs; see [2 Theorem 4.6]. We include a direct proof for completeness.
Lemma 2. Let be a possibly infinite directed graph with finite outdegrees, and let be an initial configuration of finitely many unlabeled chips. If one finite legal firing sequence reaches a stable configuration, then every game continued while a legal move is available terminates. The final configuration and the number of times each vertex fires are independent of the firing choices.
Proof. Fix a finite legal firing sequence reaching a stable configuration , and let be the number of times it fires vertex . We claim that every finite legal firing sequence fires each vertex at most times.
Otherwise, consider the first firing that would exceed one of these bounds, and let be the vertex about to fire. Immediately before this firing, let be the number of times each vertex has fired. Then for every , and . Writing , the number of chips at is
The last inequality holds because is stable and has positive outdegree. This contradicts the legality of the proposed firing. The sums are finite because and have finite support. Consequently, every legal firing sequence has length at most , so every game continued while a legal move is available terminates. If is the firing-count function of another complete game, the claim gives . Interchanging the two games gives , so . The initial configuration and these firing counts determine the final configuration.
Running Examples
We introduce our running examples: the -ary tree, the lattice of nonnegative integer points in -dimensional space, and the line graph. For the tree and lattice, we assume that . We also assume that the root is at the top, and the children are numbered left to right.
Example 2. Consider the -ary tree, a directed tree where every vertex has children. The -ary tree was the setting for the chip-firing game studied in [5, 9, 6]. This -ary tree is an ordered directed graph, since its children are ordered left to right.
We illustrate the directed binary tree, i.e., the case of the -ary tree, in Figure 2, with the traversal strings of each vertex in the first 4 layers.

Figure 2. Traversal strings for the first 4 layers of a directed binary tree
Example 3. Consider the -dimensional lattice of nonnegative integer points . We let denote this lattice, rooted at the origin . The vertex set is and the edge set is the set . In this paper, for each point in , we order the children of so that is before if and only if .
We illustrate the case of this lattice in Figure 3, which was the setting of the unlabeled chip-firing game in Inagaki et al. [8]. When we fire a vertex , we select labeled chips and, for each , send the th smallest chip out of the selected chips to the th child . We repeat this game until no vertex can fire. Figure 4 illustrates this game on , starting with chips at the origin.
Figure 3. The graph .

Figure 4. (a) Initial configuration with 8 chips. (b) Configuration after firing pairs (1, 2), (3, 4), (5, 6), and (7, 8) from the root. (c) Configuration after firing pairs (1, 5), (3, 7) from the vertex (1, 0) and firing pairs (2, 6), (4, 8) from the vertex (0, 1). (d) Configuration after firing the pair of chips from vertex (2, 0), the pair of chips from vertex (0, 2), and firing pairs (2, 4) and (5, 7) from vertex (1, 1). (e) Configuration after firing the pair (2, 3) from vertex (2, 1) and firing the pair (4, 7) from vertex (1, 2). (f) Stable configuration after firing the pair (3, 4) from vertex (2, 2). Figure 4: A labeled chip-firing game on the lattice starting with 8 chips at the origin.
Throughout this subsection, we use the following visual convention for : the first child of a vertex is drawn below on the left, and the second child is drawn below on the right. In coordinates, the first child of is , and the second child is , as seen in Figure 3.
Definition 1. Let be the ordered directed line with vertex set and root . For each , the vertex has two children: and . We order these children so that is the first child of , and is the second child of .
Example 4. The ordered directed line is illustrated in Figure 5.
Figure 5. The line graph
Homomorphisms
We now define the notion of homomorphisms for ordered directed graphs, which are analogous to the standard notion of graph homomorphisms. For ordered directed graphs and , a homomorphism from to is a function such that:
For all , the outdegree of is equal to that of .
If is the th child of , then is the th child of .
A homomorphism need not preserve the root. We call it root-preserving if it sends the root of the source graph to the root of the target graph.
Consider the directed binary tree from Example 2. Also consider the 2-dimensional lattice from Example 3. Consider the map that sends to , where and are the numbers of occurrences of and in , respectively. Appending to increases by , and appending increases by . Thus preserves the first and second children. Since both graphs have outdegree , the map is a homomorphism.
Example 5. Consider vertex which has children and . These vertices correspond to , , and respectively, and is a parent of both and . This is illustrated in Figure 6.
(a) Vertex is adjacent to and in the binary tree
(b) Vertex is adjacent to vertices and in the 2D lattice
Figure 6. Example of the homomorphism between the directed binary tree and the 2D lattice
Prior Results on -ary Trees
We recall a result on labeled chip-firing on directed -ary trees.
Lemma 3 [6 Theorem 6.2]. Consider labeled chip-firing on , starting with chips at the root. Let be a traversal string of length . The labels that can land at are exactly the integers in the interval
Automata and Tournaments Viewpoint
An ordered directed graph with constant outdegree can be viewed as a possibly infinite deterministic automaton whose alphabet is . Reading the word means starting at the root and successively following the th child. The unfolding of this automaton is the rooted tree whose vertices are finite traversal strings, with an edge from to for each . Thus the unfolding is the -ary tree . The natural map sends each traversal string to the vertex of the original graph that it reaches.
The lattice is a quotient of , obtained by identifying words that lead to the same vertex. For , the directed line is another quotient. The homomorphisms considered below are precisely the maps that preserve these child choices.
We can also interpret labeled chip-firing as a sequence of -player contests. The chips are the players, with smaller labels representing higher rankings. Whenever a vertex fires, the selected chips compete in one round: the th smallest chip finishes in th place and advances to the th child.
Thus, in the tree , a vertex records the complete sequence of finishing positions attained by every player that reaches it, whereas in the lattice , a vertex records only the totals: every player reaching this vertex has finished in th place exactly times. Graph records the signed displacement of a chip: moving to the first child decreases the coordinate by , while moving to the second child increases the coordinate by .
In the binary case, each round is an ordinary head-to-head match, in which first place may be viewed as a win and second place as a loss. Consequently, a vertex of records a sequence of wins and losses, a vertex of records their totals, and the corresponding vertex of the line graph records their signed difference.
Results on Homomorphisms
Homomorphisms
Definition 2. Let be a positive integer, let and be ordered directed graphs, let , and let
be a homomorphism. Suppose
is a finite legal firing sequence on starting with chips at , where the th firing selects the set of chips at .
We define the push-forward of to be the formal sequence
Thus, at each step, we fire at the same set of chips that was fired at . The following lemma shows that every firing in this sequence is legal. The game on starts with the same chips at .
Lemma 4 (Push-forward lemma). The push-forward of every finite legal firing sequence on is a finite legal firing sequence on .
More precisely, let be the set of chips at after the first firings of , and let be the set of chips at after the first firings of . Then, for every , we have
Consequently, if the trajectory of a chip under is
then its trajectory under is
Proof. We show by induction that after each firing, every chip in is at the image of its position in . This is true initially, as all chips start at in the chip-firing game on .
Suppose the statement holds before the th firing. The chips in are at in , so they are all at in . Since and have the same outdegree, firing at is legal. If a selected chip moves to the th child of , then, in the chip-firing game on , chip moves to the th child of , which is the image of that child. The other chips do not move.
Thus the assertion holds after the th firing. The identity
and the statement about trajectories follow. □
Theorem 5. Let and be ordered directed graphs, let , and let be a homomorphism. Suppose the two games start with chips at and , respectively. Then, for every , the set of chips that can reach in is a subset of the set of chips that can reach in .
Proof. Suppose chip can reach in . Take a finite legal firing sequence that ends immediately after chip first reaches . By Lemma 4, its push-forward is a legal firing sequence in , and the trajectory of is obtained by applying to its trajectory in . Hence chip reaches in . □
Theorem 6. Let be a homomorphism of ordered directed graphs, and let . Suppose that the unlabeled chip-firing game starting with chips at in terminates. Then the game starting with chips at in also terminates.
For , let be the number of times fires in the corresponding complete game. Then, for every , we have
Proof. By Lemma 4, every finite legal firing sequence in pushes forward to a legal sequence of the same length in . Since the latter game terminates, the proof of Lemma 2 bounds the length of every legal firing sequence by the length of a stabilizing sequence. The same bound therefore applies in , so that game also terminates.
Choose a complete strategy in and push it forward. For each , the resulting sequence fires exactly
times. Continue this legal sequence to a stable configuration in . The additional firings can only increase the firing count at , and confluence identifies the final count with .
Universality
We show that is the universal unfolding for labeled chip-firing on ordered directed graphs of constant outdegree : every such graph is obtained from by identifying vertices that have the same image under the unique root-preserving homomorphism. This proposition is the specialization, for the alphabet , of the standard fact that the Cayley graph of the free monoid is the universal directed unfolding of a deterministic automaton [3 MRS11].
Proposition 7 (Universality of the -ary tree). Let be an integer, and let be an ordered directed graph such that every vertex has outdegree and every vertex is reachable from the root. Then there is a unique root-preserving homomorphism . Moreover, this homomorphism is surjective. Consequently, graph is obtained from by identifying two vertices whenever they have the same image under .
Proof. For a traversal string , let be the vertex of reached by following the child choices in from the root. The empty string maps to the root.
Appending to means taking the th child. Thus is the th child of . Since both graphs have constant outdegree , the map is a homomorphism.
Any root-preserving homomorphism must follow these same child choices, so is unique. Every vertex of is reachable from the root and therefore equals for some . Hence is surjective.
Finally, if , then for every . Thus, identifying vertices with the same image respects the ordered children, and the resulting graph is isomorphic to .
Corollary 8. Let , let be an ordered directed graph such that every vertex has outdegree , and let be the unique root-preserving homomorphism. Fix , and start both games with chips at their respective roots. Then every finite legal firing sequence on pushes forward to a finite legal firing sequence on by firing, at , the same chips that were fired at .
Moreover, if chip follows the sequence of vertices
in , then under the pushed-forward sequence on , chip follows
We close by recording the complementary fact to Proposition 7: On the tree , changing the order of the children at each vertex gives an isomorphic game.
Definition 3. Let be a rooted directed graph in which every vertex has positive outdegree. An ordering of is a choice, for each vertex , of a linear order on the children of . Each ordering makes into an ordered directed graph.
Definition 4. An isomorphism of ordered directed graphs is a bijective homomorphism whose inverse is also a homomorphism.
Proposition 9. Let be the underlying directed graph of , and let and be orderings of . Then there is a unique root-preserving isomorphism .
Proof. Set . Suppose has been defined, let be the children of , and let be the children of . Setting is forced, and since every vertex of other than the root has a unique parent, this defines on all of . It restricts to a bijection between the children of and those of for every , hence is bijective, and it carries the th child to the th child by construction, so and are homomorphisms. □
Corollary 10. With as above and both games starting with chips at the root, a chip can reach a vertex in the game on if and only if can reach in the game on . Moreover, the map induces a bijection between the reachable stable configurations of the two games. In particular, for , the choice of ordering on is made without loss of generality.
Proof. Theorem 5 applied to gives one inclusion, and applied to gives the other. Lemma 4 applied to and to shows that is a bijection between the finite legal firing sequences of the two games, carrying stable configurations to stable configurations. □
The Line Graph
We showed a special role of the tree graph . We now discuss the complementary quotient graph . For , this graph is the line graph , which we defined in § 2.2.
Definition 5. Let and let be the quotient map. Let be the ordered directed graph with vertex set and root . Each vertex has children , ordered so that is before if and only if .
The restriction of to is a root-preserving homomorphism from to , since it preserves each child choice. It is surjective: adding a sufficiently large multiple of gives a nonnegative representative of every class in .
Example 6. Let . The map identifies with , sending to and to . Thus is the line graph with vertex set and root , in which each vertex has first child and second child .
Example 7. Take . Since , the underlying undirected graph of is the triangular lattice. If , then , so is well defined on . Thus, we can view as assigning colors to the vertices of . Every edge in increases by 1, so is a proper 3-coloring, and each elementary triangle , , uses all three colors. Finally, the map is injective on each layer of , so that layer embeds in as a triangular array inside the color class .
The characterization of maps to the line extends to . For a traversal string , let
where is the number of occurrences of in .
Proposition 11. Let , and let be an ordered directed graph in which every vertex has outdegree and is reachable from the root. There exists a root-preserving homomorphism
if and only if, whenever traversal strings and reach the same vertex of , we have
If such a homomorphism exists, it is unique and surjective.
Proof. A root-preserving homomorphism must send the endpoint of a traversal string to . Thus it can exist only if this value is independent of the traversal string chosen to reach a vertex. By the definition of , this is exactly the stated condition. The same observation proves uniqueness.
Conversely, suppose the condition holds. If reaches , set
This is well defined and sends the root to . Appending to adds to , so the th child of maps to the th child of . Since both outdegrees are , the map is a homomorphism.
Finally, every class in has a nonnegative representative . Choose a traversal string containing exactly occurrences of for each . Its endpoint in maps to , proving surjectivity. □
Remark. For every , the map is injective on each individual layer. Indeed, if and lie in the same layer and , then for some integer . Summing the coordinates gives , so and .
Definition 6. Let be an ordered directed graph in which every vertex has outdegree 2 and every vertex is reachable from the root. For a binary string , define its signed weight by
We say that is signed-rankable if, whenever two traversal strings and reach the same vertex of , we have
For , Proposition 11 gives the following characterization of signed-rankable graphs in which every vertex has outdegree 2.
Proposition 12. Let be an ordered directed graph in which every vertex has outdegree 2 and every vertex is reachable from the root. Then there exists a root-preserving homomorphism
if and only if is signed-rankable. Moreover, if such a homomorphism exists, then it is unique.
Proof. For , the condition in Proposition 11 is equivalent to
which is exactly signed-rankability. The result follows by identifying with .
Corollary 13. There are unique root-preserving homomorphisms
They are given by
for a binary traversal string , and
Proof. Every vertex of has a unique traversal string. Every traversal string reaching in contains exactly occurrences of 1 and occurrences of 2, so its signed weight is . Thus both graphs are signed-rankable, and Proposition 12 gives the stated homomorphisms and their uniqueness.
Trees and Lattices
We now apply our results from § 3 to relate the labeled chip-firing game on the -ary tree to the one on the -dimensional lattice .
Consider the map defined as follows. For a traversal string , map the tree vertex to
This is a homomorphism from to . Thus, Theorem 5 implies the following corollary.
Corollary 14. Consider the chip-firing game on the -ary tree starting with chips at the root and the chip-firing game on the -dimensional lattice starting with chips at the root. Let be a traversal string of length . Let be a chip with label in . If chip can reach in the chip-firing game on , then chip can reach vertex in the chip-firing game on .
Here is an example showing that the converse direction in the corollary above is false.
Example 8. Consider the case and , so that we start with chips at the root. Let . The corresponding lattice vertex is . We show that chip 3 can reach in the lattice , but cannot reach the tree vertex in . Indeed, fire the pairs of chips and at the root, leaving the other chips unused. Then fire at vertex and at vertex . Chips 2 and 3 now meet at . Firing this pair sends chip 2 to vertex and chip 3 to vertex .
On the other hand, Lemma 3 shows that the chips that can reach in the binary tree are precisely
Hence chip 3 cannot reach . The same calculation applies to the strings 212 and 221. Thus chip 3 cannot reach any tree vertex that maps to .
The number of chips reaching a vertex in also has a simple description in the first layers. The multinomial coefficient counts the tree vertices that map to the given vertex in .
Proposition 15. Let and . In any complete strategy on starting with chips at the origin, a vertex on layer is reached by exactly
chips.
If , then fires exactly
times and retains no chips in the stable configuration.
Proof. The arrival formula holds at the root. Suppose , and it holds on layer . Each parent of lies on a layer less than and receives a multiple of chips. In a complete strategy, it therefore sends one th of its chips to each child.
Adding the contributions from all parents of gives
This proves the arrival formula by induction. If , the number of arriving chips is divisible by . Since the lattice is acyclic, every arriving chip is counted only once, and the vertex fires exactly the arrival count divided by , leaving no chips behind.
Smallest and Largest Chips
Dependence on the Total Number of Chips
The smallest chip that can reach a vertex may depend on the total number of chips.
Example 9. Consider the following ordered directed graph. The root is . Its first child is , and its second child is . The vertex will be our target vertex. The first child of is again , and the second child of is some vertex . All remaining vertices may be completed by attaching ordinary binary trees, so that every vertex has outdegree 2 and the game terminates.
For , the smallest chip that can reach is 2. If we have 4 chips, the smallest chip that can reach is 1. Indeed, fire the pairs and at the root. Then receives chips 1, 3, and firing this pair sends chip 1 to .
The same is true for the lattice graph . We wrote some programs, and here are two examples where the smallest chip that can reach a fixed vertex of depends on the total number of chips.
Example 10. Consider the vertex . For , the smallest chip that can reach this vertex is 10, while for , the smallest chip is 8.
Moreover, the smallest chip that can reach a fixed vertex of can depend on even when is restricted to powers of 2. We also checked the following example with a program.
Example 11. Consider the vertex . For , the smallest chip that can reach it is 27, while for it is 24.
We now look at the smallest chip that can reach a given vertex of when the number of chips is relatively large.
Definition 7. For nonnegative integers and , let be the smallest chip that can reach in some finite game starting with chips at the origin, where may vary.
Every vertex of is the image of a tree vertex under the homomorphism from the preceding section, so it is reachable in some finite game. Also, extra chips may always be left unused until the desired chip arrives. Consequently, once chip can reach , it can do so in every game starting with a larger number of chips. Thus is also the smallest reachable label for all sufficiently large . This is a reachability question, not necessarily a question about the final stable configuration.
We start with a simple lower bound. Note that we do not assume here that we have sufficiently many chips.
Lemma 16. Let . If chip reaches vertex , then it satisfies
Proof. We induct on the layer . The assertion holds at the root, where every chip has a label between and . Suppose chips are fired at . By the induction hypothesis, we have
Hence , so chip satisfies the required bounds at . Similarly, we have , so chip satisfies them at . Thus every firing preserves the bounds.
These bounds also imply that every game on terminates. Indeed, every occupied vertex satisfies , so the sum of the chips’ layer numbers is at most . Each firing increases this sum by .
Corollary 17. We have .
Our next goal is to calculate and find where this lower bound is sharp.
Small Chips and Consecutive Pairing
Suppose we want to know whether a chip with label at most can reach our target. Call chips small and all other chips large. A small chip can move to the first child by being paired with a large chip. Moving to the second child is harder: it must be paired with another small chip.
Example 12. Suppose and a vertex contains chips . Fire the pairs and . The first child receives two small chips, and , while the second child receives one small chip, . The large chip allows the last small chip to move to the first child rather than remain at the vertex.
More generally, suppose a vertex contains small chips and an even total number of chips. List all its chips in increasing order and pair consecutive chips. If is odd, the last small chip is paired with the first large chip. Thus the numbers of small chips sent to the first and second children are, respectively,
The second number is as large as possible: every small chip sent to the second child needs another small chip as its partner.
We use this rule at every vertex. Fix a nonnegative integer , and start with chips. Process the vertices layer by layer, beginning at the root. At each vertex, wait for all incoming chips, list them in increasing order, and fire consecutive pairs. Stop after processing all vertices in layers less than . We call this the consecutive-pairing strategy. The pairings do not depend on the cutoff .
Why start with a power of 2? The following lemma shows that no chip is left unpaired before the target layer.
Lemma 18. Under consecutive pairing starting with chips, every vertex before layer receives an even number of chips. More precisely, a vertex with receives
Proof. Extend the consecutive-pairing sequence to a complete strategy, which is possible by the termination argument above. All subsequent firings occur in layers at least , so they do not change the arrival counts in layers at most . The formula follows from Proposition 15 with and . If , then the factor is even.
To study , we may take . If we are also tracking chips , choose large enough that . At every processed vertex, the large chips provide the partners needed whenever the number of small chips is odd; we do not have to route auxiliary chips separately.
For each nonnegative integer , the vertices form diagonal , which extends downward to the left in our drawing. The vertices on this diagonal are indexed by their first coordinate. A first-child move stays on the same diagonal and increases this index by 1. A second-child move enters the next diagonal and preserves the index.
Example 13. Let us return to the vertex . Start with eight chips and fire consecutive pairs. The root sends chips 1, 3, 5, 7 to and chips 2, 4, 6, 8 to . At these vertices, fire
Then receives chips 2, 3, 6, 7. Firing and sends chip 3 to .
For , two small chips enter diagonal 1: chip 2 enters at , and chip 3 enters at . Chip 2 then moves along diagonal 1 to , so the two small chips meet there. Firing them together sends chip 3 to , so one small chip enters diagonal 2. For , only chip 2 enters diagonal 1. It has no small partner, so these pairings send no small chip to diagonal 2.
Computing the Smallest Chip
The preceding example suggests counting the small chips entering an initial segment of a diagonal. This is easier than keeping track of all labels or all individual vertex counts.
Definition 8. Let be the number of small chips that enter diagonal at vertices whose first coordinate is at most under consecutive pairing. For , an entry into diagonal is a move from to for some . Subsequent moves along diagonal are not counted again. For , we count the initial placement of the small chips at the root.
For each count, choose with . The count does not depend on this choice: at every processed vertex, the numbers of small chips sent to its children depend only on the number of incoming small chips. Induction over the layers therefore gives the same small-chip counts whenever is large enough.
Example 14. For and , the cumulative counts in Example 13 are
| 0 | 2 | 2 | 3 | 3 |
| 1 | 1 | 1 | 1 | 2 |
| 2 | 0 | 0 | 0 | 1 |
For instance, the two small chips entering diagonal 1 at and give . The entry counts the small chip entering diagonal 2 at .
The recurrence for these counts is particularly simple: add two previous entries, divide by 2, and round down.
Lemma 19. For every positive integer , we have
For and , we have
Proof. The initial conditions follow from the definition. To obtain the recurrence, consider the firings at . Write
Thus small chips have entered diagonal at vertices with first coordinate at most , and of them have already moved to diagonal at vertices with first coordinate less than $a. No chips remain at the previously processed vertices. Consequently, the other small chips reach . Consecutive pairing sends of them to . Including the earlier entries into diagonal gives
The local rule sends as many small chips as possible to the second child. However, this alone does not prove that the whole strategy is optimal: sending fewer small chips to the second child leaves more available farther along the current diagonal. Cumulative counts let us compare these possibilities.
Proposition 20. In any finite legal firing sequence, the number of chips among entering diagonal at vertices with first coordinate at most is at most . Consecutive pairing attains these bounds simultaneously in every fixed finite portion of the lattice, provided is large enough.
Proof. For an arbitrary finite firing sequence, let count the same diagonal entries. We may assume that the game starts with at least chips, since missing chips may be added and left unused.
Put and . Of the small chips entering diagonal at vertices with first coordinate at most , the that leave for diagonal at vertices with first coordinate less than cannot reach . Some other chips may remain at earlier vertices. Hence at most small chips reach .
Each small chip sent from to its second child needs another small chip as its partner. Also, a chip visits a lattice vertex at most once. Thus
The initial values of and agree. Since the expression on the right is nondecreasing in both inputs, induction on gives . The equality for consecutive pairing is Lemma 19.
There is one more point to check. A positive value of tells us that a small chip enters diagonal at a vertex with first coordinate at most , rather than necessarily at . But every processed vertex with small chips sends small chips to its first child. Therefore, once a small chip enters this part of diagonal , some small chip reaches under consecutive pairing. Conversely, any small chip reaching must have entered diagonal at a vertex with .
We can now compute the smallest chip that can reach when we play the chip-firing game with sufficiently many chips.
Theorem 21. For nonnegative integers and , we have
Moreover, consecutive pairing starting with chips sends chip to .
Proof. Let . By Lemma 18, the consecutive-pairing strategy starting with chips sends chips to . If all chips are called small, then , so the minimum in Equation (2) exists and is at most .
Let be that minimum. By Proposition 20, no chip with label smaller than can reach in any game. On the other hand, consecutive pairing with chips sends some small chip to , by the preceding observation. Its label is at most and cannot be smaller than . Hence it is chip , and .
A separate strategy is not needed for each target vertex. In fact, consecutive pairing realizes both extreme reachable labels at every vertex in the first layers.
Corollary 22. Fix , and start with chips. Under consecutive pairing, for every vertex with , both chips
reach . These are, respectively, the smallest and largest chips that can reach this vertex in the -chip game.
Proof. Fix and put . By Theorem 21, we have . The small-chip counts do not depend on once and . Thus some chip among reaches under consecutive pairing. No smaller chip can ever reach this vertex, so chip itself reaches it. The pairings do not depend on the target vertex or on the cutoff , so this holds simultaneously for all vertices under consideration.
Now interchange the coordinates and replace each label by . Every vertex that is processed has an even number of chips, by Lemma 18. Reversing an even-ordered list preserves its consecutive pairs, while interchanging the smaller and larger member of each pair. The coordinate interchange also swaps the two children. Starting from the symmetric initial configuration, induction over the layers therefore shows that the sets of arriving chips are preserved by this transformation.
Since chip reaches , chip reaches in the same strategy. Any larger reachable label would, after the same reflection, give a label smaller than reaching , which is impossible.
Example 15. Let us compute . From Example 14, we have and . The counts are nondecreasing in , either by their definition or by the recurrence. Therefore . Similarly, the recurrence gives and , so . This agrees with the sixteen-chip computation in Example 10.
Table 1 shows the values of computed from the recurrence. The corresponding array is now recorded in the OEIS as sequence A397913 [11].
Consequences and Special Cases
The construction gives an explicit meaning to “sufficiently many chips.”
Corollary 23. If , then the smallest and largest chips that can reach are, respectively,
Proof. Theorem 21 gives a firing sequence using chips in which chip reaches . In a larger game, repeat this sequence and leave the additional chips unused until that arrival. No smaller chip can reach the vertex, by the definition of .
For the largest chip, interchange the two coordinates and replace each label by . This identifies the smallest reachable label at with the largest reachable label at .
Remark. The bound is sufficient, not necessarily the smallest possible bound. For example, the minimum is already attained with 16 chips, although the bound gives 32. For smaller , a vertex may be reachable even though the eventual minimum label cannot yet reach it.
The preceding corollary determines the smallest and largest chips that can reach a vertex . In the next proposition, we show that every label between these extremes can reach when the total number of chips is sufficiently large. But first, we introduce new notation. Fix nonnegative integers and , and write
Proposition 24. If
then the set of labels that can reach in the -chip game is exactly
In particular, the condition is sufficient.
Proof. By Corollary 23, in the -chip game there is a firing sequence sending chip to , and there is a firing sequence sending chip to . For any integer with , replace every label in either sequence by . All comparisons between selected chips are preserved. Therefore, the resulting sequence is legal in the -chip game: we use chips and leave the other chips unused until the desired arrival.
Applying these shifts to the first sequence shows that every label in
can reach . Applying them to the second sequence gives every label in
These two integer intervals overlap or are adjacent whenever
which is equivalent to . Their union is therefore . By Corollary 23, all labels outside this interval cannot reach the vertex .
The strategies used for different labels may be different. The proposition concerns reachability, not the labels in a single stable configuration.
Corollary 25. The columns in Table 1 are nonincreasing, and the rows are strictly increasing. Equivalently,
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 1 | 2 | 4 | 8 | 16 | 32 | 64 | 128 | 256 |
| 1 | 1 | 2 | 3 | 4 | 8 | 15 | 24 | 40 | 64 |
| 2 | 1 | 2 | 3 | 4 | 5 | 8 | 15 | 24 | 32 |
| 3 | 1 | 2 | 3 | 4 | 5 | 6 | 8 | 15 | 24 |
| 4 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 15 |
Table 1. The smallest chip that can reach when sufficiently many chips are present.
Proof. By definition, we have , since the former also counts entries at . Theorem 21 gives .
Now suppose . At some earlier time, chip must have moved from diagonal to diagonal . It was therefore paired with a smaller chip at some vertex with . Thus . By the first part, we have
:::
The first two rows of Table 1, corresponding to and , admit more explicit descriptions.
Example 16. For , the recurrence repeatedly halves the number of small chips:
Consequently, we have .
To compute , we count entries into diagonal only at and . For example, when , the values of for are . Allowing entries at lets one small chip enter diagonal , whereas entering at would require eight small chips.
Recall that is the 2-adic valuation of .
Proposition 26. For every , we have
Proof. For , Equation (1) gives
Starting with and applying this identity repeatedly gives
This can also be checked by induction; the identity for an integer allows the nested floors to be combined.
For each positive integer , we have
Summing over gives
If , all terms with vanish, so the sum on the left is the numerator in Equation (3). Hence exactly when that sum is at least .
If , both conditions already hold: we have , and the sum is at least . The proposition now follows from Theorem 21.
The formula in Proposition 26 also describes the growth of the smallest reachable label. For , increasing the first coordinate from 0 to 1 strictly reduces this label.
Corollary 27. As , we have
Proof. Put
The identity in the preceding proof gives
Indeed, removing the floors changes the sum by .
Let . By Proposition 26, we have
Since , it follows that
As , taking logarithms gives , and hence . Substituting back gives .
Where the Lower Bound Is Attained
By Lemma 16, any chip that reaches has label at least . We now look at the vertices where this lower bound is sharp. For example, when , the bound is sharp for . When , the bound is sharp for .
Let be the least first coordinate for which , and let be the greatest second coordinate for which this equality holds. Thus
The proof below shows that both quantities are well defined. Since is nonincreasing in and bounded below by , we also have
Thus the function describes the boundary for each fixed second coordinate, while the function describes it for each fixed first coordinate.
To study this boundary, it is useful to record the numbers of new small chips entering a diagonal at each vertex, rather than their cumulative counts. These are the successive differences . This notation will be used only in the boundary argument.
Example 17. Start with four small chips. The lists of new entries into successive diagonals are
At vertex , two small chips are sent to and two to . Vertex then sends one small chip to . The remaining small chip continues along diagonal 0 without creating any more entries into diagonal 1.
Thus, the number of new entries drops by one at each successive diagonal. On diagonal 3, the only small chip that can appear is chip 4, and it first enters at index 1. Therefore we have .
The same drop by one occurs for any nonempty list of new entries. To see this, process the vertices of the diagonal in order of increasing first coordinate until all incoming entries have been used. Past the last incoming entry, repeated rounding up after division by eventually leaves one small chip, which continues along the diagonal without producing any more entries into the next diagonal. Every other small chip enters the next diagonal.
We can determine the entries into the next diagonal in finitely many steps. Once only that last chip remains, we stop the calculation and omit it from the next diagonal’s list. Every finite part of the calculation is realized by consecutive pairing with a sufficiently large power of chips.
The following result describes how the boundary moves.
Lemma 28. For every , we have
Consequently, for every , we have
Proof. For a finitely supported list of new entries into a diagonal, let be the list of new entries into the next diagonal. We call this operation diagonal reduction. The entries of each list are indexed by the first coordinate. To compute the reduction, set and let
Here is the number of small chips continuing to the first child. Stop once all incoming entries have been used and the carry is . Also set .
Let be the list of new entries into diagonal when there are small chips. Equivalently,
where denotes one small chip entering at index . Write for the total number of small chips in the list. As explained above, every nonempty diagonal reduction omits exactly one chip. Hence
After reductions, exactly one small chip enters the diagonal. By Lemma 16, this must be chip . Theorem 21 shows that it enters diagonal at the least first coordinate for which chip can reach . In particular, the value is well defined, and
We record two properties of diagonal reduction. First, the operation is monotone: if entry by entry, then . This follows directly from the formulas for the outputs and carries. Second, the nonzero entries of every nonempty occupy consecutive indices. This is true initially. If the occupied indices of the incoming list are consecutive, then after the first positive input, the carry stays positive through the occupied indices. The outputs there are positive, except possibly at the smallest occupied index. Beyond the last input, they stay positive until the carry becomes 1.
Adding one small chip. Compare and for . By monotonicity and the size formula, their difference is one extra chip. We claim that its index is at most one greater than the largest occupied index of .
This is true initially. Suppose the claim holds before a reduction in which the smaller list contains at least two small chips. Let and be the largest occupied indices of the smaller list before and after reduction. Since the occupied indices are consecutive, we have . Indeed, if is the only occupied index, the entry there is at least 2, so the reduced list has a chip at index . Otherwise, the positive carry from the preceding occupied index produces a chip at index . Thus .
The extra chip therefore has index at most . Until it produces an extra output, it continues as an extra unit of carry. If no extra output has appeared by index , then the total input at index increases from 1 to 2, producing an extra output there. This proves the claim by induction.
Put . At diagonal , we have
for some . Reducing a list with two small chips leaves one chip in the greater of their two indices. Hence is either or , proving the first pair of inequalities.
Adding two small chips. Now compare and for . Their difference consists of two extra chips. If is the smallest occupied index of the smaller list, we claim that neither extra chip has an index less than , and at most one has index .
This is true initially. Suppose it holds before a reduction, with at least two small chips in the smaller list. If the entry at index is at least 2, the reduced list still begins at index . A single extra chip at index produces no output there, so the claim remains true.
If the entry at index equals 1, the reduced list begins at index , since the occupied indices are consecutive. No extra output can appear at an index less than . At most two extra inputs can reach index , making its total input at most 3. Hence, at most one extra output appears at index . This proves the claim relative to the new smallest occupied index .
Again put . On diagonal , the larger list consists of the chip at and two extra chips, neither with index less than and at most one with index . If some chip has index greater than , let be the largest occupied index.
Since the occupied indices are consecutive and there is a chip at index , a positive carry reaches index . Together with the chip already there, it produces an output at index . The resulting list has two chips, so its next reduction leaves one chip at the greater of their two indices, which is at least .
Otherwise, the three-chip list is either or . In both cases its next reduction is , followed by . Again . Substituting proves .
Finally, the function satisfies and , and its successive increments are 0 or 1. Therefore, the function is unbounded and takes every nonnegative integer value either once or twice. This shows that is finite. Replacing by adds exactly the second coordinates with .
The boundary lemma gives a region where the lower bound is attained.
Proposition 29. We have , and, for every , we have
Consequently,
whereas, for every , we have
In particular, if , , and , then the smallest and largest chips that can reach are, respectively,
Proof. The formula gives . Example 17 gives , so . On the other hand, Lemma 28 gives . Thus .
Each subsequent increment of is at least 1 and at most 2. Therefore, for , we have
Since is nondecreasing, we know that, for each fixed , the lower bound is attained exactly when . This proves the assertions about .
Finally, if and , then both and . Corollary 23 gives the claimed extreme labels.
Acknowledgments
The first and second authors are employed by the MIT Department of Mathematics. The third author is supported by Harvard College.
All figures in this paper were generated using TikZ via mathcha.io and exported as PDF. The writing was assisted by Claude and ChatGPT.
References
- [1]Anders Björner and László Lovász. Chip-firing games on directed graphs. J. Algebraic Combin., 1(4):305–328, 1992.DOI
- [2]Benjamin Bond and Lionel Levine. Abelian networks I. Foundations and examples. SIAM J. Discrete Math., 30(2):856–874, 2016.arxiv.org/abs/1309.3445
- [3]Didier Caucal. Cayley graphs of basic algebraic structures. Discrete Math. Theor. Comput. Sci., 21(1):Paper No. 16, 19, 2019.
- [4]Sam Hopkins, Thomas McConville, and James Propp. Sorting via chip-firing. Electron. J. Combin., 24(3):Paper No. 3.13, 20, 2017.DOI
- [5]Ryota Inagaki, Tanya Khovanova, and Austin Luo. Chip firing on directed k-ary trees. Enumer. Comb. Appl., 5(2):Paper No. S2R16, 14, 2025.arxiv.org/abs/2410.23265
- [6]Ryota Inagaki, Tanya Khovanova, and Austin Luo. Labeled Chip-Firing on Directed k-ary Trees and Where Chips Land. Preprint, arXiv:2506.20656 [math.CO] (2025), 2025.arxiv.org/abs/2506.20656
- [7]Ryota Inagaki, Tanya Khovanova, and Austin Luo. On chip-firing on undirected binary trees: R. inagaki et al. Annals of Combinatorics, pages 1–27, 2025.DOI
- [8]Ryota Inagaki, Tanya Khovanova, and Austin Luo. Chip-firing on the Lattice of Nonnegative Integer Points. Preprint, arXiv:2601.09125 [math.CO] (2026), 2026.arxiv.org/abs/2601.09125
- [9]Ryota Inagaki, Tanya Khovanova, and Austin Luo. Permutation-based strategies for labeled chip-firing on k-ary trees. Discrete Mathematics & Theoretical Computer Science, vol. 28:2, Jan 2026.DOI
- [10]Gregg Musiker and Son Nguyen. Labeled chip-firing on binary trees with 2ⁿ − 1 chips. Ann. Comb., 28(4):1167–1197, 2024.DOI
- [11]OEIS Foundation Inc. The On-Line Encyclopedia of Integer Sequences, 2026. Published electronically at http://oeis.org.



