In an earlier post, I described the dollar game played on a finite graph , and mentioned (for the “borrowing binge variant”) that the total number of borrowing moves required to win the game is independent of which borrowing moves you do in which order. A similar phenomenon occurs for the pentagon game described in this post.
In this post, I’ll first present a simple general theorem due to Mikkel Thorup which implies both of these facts (and also applies to many other ‘chip firing games’ in the literature). Then, following Anders Björner, Laszlo Lovasz, and Peter Shor, I’ll explain how to place such results into the context of greedoid languages, which have interesting connections to matroids, Coxeter groups, and other much-studied mathematical objects.
Firing games and strong convergence
As motivation for the general theorem, we quickly recall the “borrowing binge” variant of the dollar game. Let be a connected finite graph with vertex set . (For simplicity, we assume that is simple, i.e., that it has no parallel or loop edges.) Let be an initial configuration, which is an assignment of some integer number of dollars to each vertex. A vertex with a negative number of dollars is said to be in debt. A legal move in the game consists of selecting a vertex which is in debt and then “borrowing” a dollar from each neighbor (which means replacing with and , for each neighbor of , with ). The goal of the game is to get every vertex out of debt.
Here is an abstraction of this game. A firing game consists of a set and a firing rule which assigns to each finite sequence (including the empty sequence ) of (not necessarily distinct) elements of a subset of . (In the context of the dollar game described in the previous paragraph, and is the set of vertices which are in debt after performing borrowing moves at in that order.)
We think of as the set of “legal moves” in the game once the sequence of moves has been played. More formally, a sequence of legal moves is either a finite sequence with and for all or an infinite sequence with and for all .
A legal game is either (i) the empty sequence (if ), (ii) a finite sequence of legal moves with , or (iii) an infinite sequence of legal moves . For a legal game , we define to be 0 in case (i), in case (ii), and in case (iii). We call a legal game finite (or terminating) if it has finite length, and infinite (or non-terminating) otherwise.
A firing game is called strongly convergent if either all legal games are infinite, or all legal games are finite and for every legal game and every the natural number is independent of . (In the context of the dollar game, the latter condition means that the number of times each vertex of performs a borrowing move is independent of the sequence of legal moves played. This, in turn, implies that both the total number of moves and the final configuration of dollars are independent of any choices made, assuming that the game is winnable.) In particular, when the firing game is strongly convergent, all legal firing games have the same length.
Following Thorup, we say that a firing rule is monotone if if for any two finite sequences and of legal moves such that for all and for some , the assertion implies . Note that the dollar game is monotone, since if Alice plays the sequence of moves and Bob plays , the conditions for all and imply that Bob has borrowed from each vertex at least as many times as Alice has, and they have borrowed the same number of times from vertex . In this case, it’s easy to see that if is in debt for Alice then it must also be in debt for Bob.
Theorem 1: Every monotone firing game is strongly convergent.
Proof (Thorup): Let be legal games. Without loss of generality, we may assume that and that . We need to show that for every .
If for all then we’re done. So assume, for the sake of contradiction, that this is not the case. Let be the smallest index such that for some . Then , for all , and . Moreover, since is a legal sequence of moves we must have . By monotonicity, it follows that , contradicting the fact that . Q.E.D.
Application to other games
We give three sample applications of Theorem 1:
- Consider the same dollar game described above, but where the initial configuration is allowed to take arbitrary real values, as opposed to integer values, at each vertex. The integrality condition was never used in verifying the hypotheses of Theorem 1, so we conclude that this generalized dollar game is also strongly convergent.
- Following Mozes, consider the generalization of the “pentagon game” in which we’re given an -gon and an initial configuration consisting of a real number for each vertex of . This time, a legal move consists of choosing a vertex with , and replacing with and each with a neighbor of with . Theorem 1 implies (as originally proved by Mozes by a more complicated argument) that this game is strongly convergent, and in particular that if the game is finite then both the total number of moves and the final configuration are independent of any choices made.
- Following Diaconis and Fulton, consider the firing game where for each we are given an infinite deck of cards, with each card labeled by an element of . (Technical hypothesis: assume that for any infinite subset of , there are infinitely many cards belonging to decks at elements of which are labeled by elements not in .) Suppose that a finite number of chips are placed at each element of , and that to each we have associated a positive integer called the tolerance of . A legal move consists of choosing some having more than chips, moving one of the chips at to the site labeled by the top card of the deck at , and throwing this card away. Theorem 1 implies (as originally proved by Diaconis and Fulton) that this game is strongly convergent, and in particular that if the game is finite then both the total number of moves and the final configuration are independent of any choices made.
Let be a set, which for simplicity we take to be finite. Let denote the set of all words in the alphabet , including the empty word . (In technical jargon, is the underlying set of the free monoid over .) By convention, we will use Greek letters to denote words and Latin letters to denote letters.
- denotes the concatenation of .
- denotes the length of .
- denotes the letter count of , i.e., is the number of times appears in .
A language is a non-empty subset of words in . A language is called simple if no word contains any repeated letters.
A greedoid language is a language satisfying the following two axioms:
- (Left hereditary) If then .
- (Augmentation) If and , there exists a letter such that .
The name comes from the fact that there is a bijection between simple greedoid languages and greedoids.
A maximal word in is a word such that implies . It is possible for the set of maximal words in to be empty (which implies that there are arbitrarily long words in ). A basic property of greedoid languages is the following fact, whose proof we leave as an exercise:
Lemma 1: In a greedoid language, any two maximal words have the same length.
Examples of greedoid languages
The following are examples of greedoid languages (the list is by no mean exhaustive):
- The language consisting of the empty word, together with all words such that is a legal sequence of moves in the (borrowing-only version of the) dollar game associated to a pair , is a greedoid language. This language is, in general, not simple. The dollar game is winnable if and only if there exists a maximal word.
- If is a matroid on , the language whose alphabet is and whose words are all permutations of independent sets in is a simple greedoid language.
- An antimatroid on is a non-empty collection of subsets of , called the feasible sets, such that (i) the union of two feasible sets is feasible, and (ii) if is a non-empty feasible set, there exists such that is also feasible. If is an antimatroid on , the language whose alphabet is and whose words are all permutations of feasible sets is a simple greedoid language.
- A Coxeter group is a pair consisting of a group and a finite generating subset such that (i) every element of has order 2, and (ii) has a presentation using generators from and relations of the form with and . Examples include the symmetries of a regular convex polytope and the Weyl group of a simple complex Lie group. A word in the alphabet is reduced if there is no shorter word representing the same element of . If is a finite Coxeter group, the set of reduced words is a (non-simple) greedoid language; this follows from the strong exchange condition, which characterizes Coxeter groups among all groups generated by involutions. In particular, any two maximal reduced words in a Coxeter group have the same length.
The connection to firing games
Björner, Lovasz, and Shor proved a general result about greedoid languages which is similar in spirit to Theorem 1. In order to state their result, we make the following definition:
A language is called an antimatroid with repetition if it is left-hereditary and satisfies the following additional axioms:
- If , , and then .
- If and are distinct elements of with and , then .
(The reason for the name is that there is a bijection between simple antimatroids with repetion and antimatroids.)
Theorem 2 (Björner-Lovasz-Shor): If is an antimatroid with repetition, then is a greedoid language and any two maximal words have the same letter count (i.e., are rearrangements of each other).
This implies Theorem 1, since it is straightforward to check that the language consisting of the empty word, together with all words such that is a legal sequence of moves in some monotone firing game, is an antimatroid with repetition.
(1) The greedoid language associated to a matroid or Coxeter group is typically not an antimatroid with repetition. It’s clear that the conclusion of Theorem 2 is not true for matroids, since maximal words correspond to bases. An example of a Coxeter group whose associated language is not an antimatroid with repetition is the symmetric group with . In this case, , and in particular and are maximal words which are not rearrangements of one another.
(2) There are many greedoids which are neither matroids nor antimatroids. For example, let be a directed graph rooted at . Then the edge sets of directed subtrees rooted at and directed away from are the feasible sets of a greedoid which is neither a matroid nor an antimatroid. For many more examples, theorems, and motivation (including an explanation for the name “greedoid”), see this survey paper by Björner and Lovasz.
(3) The greedoids associated to both matroids and antimatroids are examples of interval greedoids, which Chan and Pak have recently shown (using a completely new method) satisfy log-concavity properties analogous to those established by Adiprasito-Huh-Katz, Brändén-Huh, et. al. in their celebrated work on combinatorial Hodge theory. Interval greedoids can be thought of as simple greedoid languages satisfying the following strong augmentation property:
- (Strong augmentation) If and , then contains a subword of length such that .
(Here is a subword of if for some indices .) Examples of greedoid languages satisfying the strong augmentation property include matroid languages, antimatroids with repetition (so in particular the greedoid languages coming from monotone firing games), and the greedoid languages associated to a Coxeter group.
(4) There is a generalization of the -gon game called the “numbers game” which Eriksson has shown to be intimately related to the theory of Coxeter groups. In this related paper, Eriksson presents a theorem and proof very similar to Theorem 1 above which he discovered independently of Thorup.
(5) There is a series of papers by Bond and Levine on Abelian networks which provides another general framework for understanding strongly convergent games.