REFERENCES for the class of 25 April 2018
-----------------------------------------

Today I have briefly spoken about sandpiles (aka chip-firing) on digraphs. Let me list some resources roughly in order of increasing readability:

Popular expositions and illustrations:

1) A pop-sci article (but written by a mathematician, and written well) on the case of the infinite 2-dimensional checkerboard: http://nautil.us/issue/23/dominoes/the-amazing-autotuning-sandpile

2) The result of putting 2^n chips at the origin of the checkerboard and then stabilizing (shown in class): http://www.math.cmu.edu/~wes/sand.html (needs javascript).

3) A WebGL interactive sandpile simulator: http://people.reed.edu/~davidp/web_sandpiles/ (sadly lacking documentation). Here is the most basic functionality explained: When you click on a cell, it adds 1 grain to the cell and then stabilizes the result (i.e., fires a legal stabilizing sequence of vertices). The colors blue, yellow, cyan and brown represent 0, 1, 2 and 3 grains, respectively. (And white represents 4 or more grains, which happens during the stabilization process but disappears at the end of it.) At the beginning every cell has 3 grains -- so once you add one single grain, a chain reaction erupts. The borders of the checkerboard are understood to connect to the "sink" -- i.e., any grain sent by a border cell to a neighbor that is outside of the checkerboard is considered to be thrown away. (The four corners of the checkerboard are connected to the sink by two edges each -- so each time you topple one of the corners, you lose *two* grains.) This guarantees that stabilization always happens (i.e., each configuration is finitary).

Theorems and proofs:

4) Elementary proofs of the fundamental results (e.g., the fact that any two legal stabilizing sequences yield the same stable configuration; also the fact that q-stabilization exists): http://www.cip.ifi.lmu.de/~grinberg/t/17s/hw5s.pdf (Sections 0.2, 0.4 and 0.7 are the most useful).

5) I learned much of the subject from the "Holroyd et al." paper https://arxiv.org/abs/0801.3306 , but it is somewhat advanced (proofs are terse and some abstract algebra is presumed). Examples are really good, though.

6) A graduate-level textbook in progress: http://people.reed.edu/~davidp/divisors_and_sandpiles/ (shows connections to Riemann surfaces, simplicial complexes and other things).

7) There is a cool recent variation of the model, where instead of n undistinguishable grains of sand you put n labelled balls (labels 1, 2, ..., n) on the origin of the integer line (i.e., the infinite path, aka the infinite 1D checkerboard). Then, when "toppling", you don't just randomly hand out two balls to the two neighbors, but instead you pick two balls and hand the one with the smaller label to the left neighbor and hand the one with the larger label to the right neighbor. For example, if n = 3, then at the beginning all 3 balls 1, 2, 3 are on the origin, but after a toppling you will have either 123 or 132 or 213 (read from left to right). So the result does depend on the choices...

... unless n is even, in which case it doesn't! This is a hard result recently found by Hopkins, McConville and Propp (see their paper "Sorting via chip-firing", published in the Electronic Journal of Combinatorics, downloadable from http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p13/pdf ). See the introduction of their paper for a better description than mine as well. Unlike the unlabelled-grains model, this one probably does *not* generalize to arbitrary graphs.

8) Gregg Musiker, the go-to person for sandpiles at UMN: http://www-users.math.umn.edu/~musiker/

9) Talk slides (2015) about recent research with fancy examples: http://www.math.cornell.edu/~levine/apollonian-slides.pdf (goes far beyond combinatorics, I don't understand most of it).