JOURNAL OF
ALGEBRAIC
COMBINATORICS

Home > Vol 10, No 2 (1999)

Norman Biggs

The 'dollar game' represents a kind of diffusion process on a graph. Under the rules of the game some cofigurations are both stable and recurrent, and these are known as critical cofigurations. The set of critical configurations can be given the structure of an abelian group, and it turns out that the order of the group is the tree-number of the graph. Each critical configuration can be assigned a positive weight, and the generating function that enumerates critical configurations according to weight is a partial evaluation of the Tutte polynomial of the graph. It is shown that the weight enumerator can also be interpreted as a growth function, which leads to the conclusion that the (partial) Tutte polynomial itself is a growth function.

1. R. Bacher, P. de la Harpe, and T. Nagnibeda, “The lattice of integral flows and the lattice of integral coboundaries of a finite graph,” Bull. Soc. Math. de France 125 (1997), 167-198.
2. N.L. Biggs, Algebraic Graph Theory, 2nd edition, Cambridge University Press, 1993.
3. N.L. Biggs, “Algebraic potential theory on graphs,” Bull. London Math. Soc. 29 (1997), 641-682.
4. N.L. Biggs, “Chip-firing and the critical group of a graph,” J. Alg. Combin. 9 (1999), 25-45.
5. A. Bj\ddot orner, L. Lovász, and P. Shor, “Chip-firing games on graphs,” Europ. J. Combinatorics 12 (1991), 283-291.
6. A. Gabrielov, “Avalanches, sandpiles and Tutte decomposition,” The Gelfand Mathematical Seminars 1990- 92, Birkhauser, Boston, MA, 1993, pp. 19-26.
7. A. Gabrielov, “Abelian avalanches and Tutte polynomials,” Physica A 195 (1993), 253-274.
8. C. Greene and T. Zaslavsky, “On the interpretation of Whitney numbers through arrangements of hyperplanes, zonotopes, non-Radon partitions, and orientations of graphs,” Trans. Amer. Math. Soc. 280 (1983), 97-126.
9. C. Merino Lopez, “Chip-firing and the Tutte polynomial,” Annals of Combinatorics 1 (1997), 253-260.
10. L. Lovász and P. Winkler, “Mixing of random walks and other diffusions on a graph,” in Surveys in Combinatorics 1995, P. Rowlinson (Ed.), Cambridge University Press, 1995, 119-154.
11. T. Nagnibeda, “Jacobian of a finite graph,” in Harmonic Functions on Graphs, A. Koranyi (Ed.), AMS Contemporary Mathematics Series, 1997.
12. R.P. Stanley, “Cohen-Macaulay complexes,” in Higher Combinatorics, M. Aigner (Ed.), Reidel Publishing, Dordrecht and Boston, 1977.
13. W.T. Tutte, “A contribution to the theory of chromatic polynomials,” Canad. Math. J. 6 (1954), 80-91.
14. D.J.A. Welsh, “Complexity: Knots, colourings and counting,” LMS Lecture Notes Series 186, Cambridge University Press, 1993.