Chip-Firing Graph Configurations

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram CDF Player or other Wolfram Language products.

Requires a Wolfram Notebook System

Edit on desktop, mobile and cloud with any Wolfram Language product.

This Demonstration shows a chip-firing game, which is also referred to as an Abelian sandpile model. Starting with a simple weighted directed graph and a number of chips to be distributed among the vertices of , a new graph is constructed with a vertex for each distribution of chips and an edge corresponding to each valid chip firing.

[more]

A vertex with out-degree and chips can fire chips, one to each neighbor, reducing its store of chips to . A vertex is not allowed to go into debt by firing more chips than it has in stock, although this variation is occasionally considered.

The graphic displays the interactions between different chip distributions.

[less]

Contributed by: Ken Levasseur (July 2018)
(UMass Lowell)
Open content licensed under CC BY-NC-SA


Snapshots


Details

If has vertices and there is a supply of chips to be distributed within the graph, there are

ways to distribute the chips. The chip-firing graph for with chips consists of vertices, one for each distribution of the chips. Directed edges of are drawn from one weighted graph to another if all valid chip-firing moves from the first weighted graph produces the second.

To run this Demonstration, select the number of vertices in and the number of chips. Then toggle the presence/absence of each edge. Mousing over any edge of the chip-firing graph displays the change in distribution of chips.

References

[1] N. L. Biggs. "Chip-Firing and the Critical Group of a Graph," Journal of Algebraic Combinatorics, 9(1), 1999 pp. 25–45. doi:10.1023/A:1018611014097.

[2] A. E. Holroyd, L. Levine, K. Mészáros, Y. Peres, J. Propp and D. B. Wilson, "Chip-Firing and Rotor-Routing on Directed Graphs," In and Out of Equilibrium 2. Progress in Probability (V. Sidoravicius and M. E. Vares, eds.), Vol. 60, Basel: Birkhäuser Verlag, 2008 pp. 331–364. doi:10.1007/978-3-7643-8786-0_ 17.

[3] J. van den Heuvel, "Algorithmic Aspects of a Chip-Firing Game," Combinatorics, Probability and Computing, 10(6), 2001 505–529. doi:10.1017/S0963548301004886.



Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.
Send