Sandpiles and the Vicsek fractal
This picture shows an example of a stable configuration in the abelian sandpile model on a square lattice. This is a rectangular square array of a large number of pixels, each with one of four possible colours (white, green, purple and gold) corresponding to the numbers 0, 1, 2 and 3 respectively. These numbers represent stacks of tokens which are often identified with grains of sand, hence the term “sandpile”. The tokens can also be identified with stackable objects, like the letter tiles in the board game Upwords, shown below.
In the game of Upwords, it is illegal to create a stack that has more than five tiles in it. The sandpile model on a square lattice can then be thought of as a large Upwords board, but with unlabelled tiles. Each pixel in the sandpile can contain a stack up to three tiles high. Creating a stack higher than this is allowed, but it causes the stack to become unstable and to topple. In this case, one takes the top four tiles off the excessively tall stack, and distributes one tile to each of the stack’s four neighbours. This process may in turn cause other stacks to topple, in a kind of avalanche. The picture at the top shows the result if one repeatedly topples a single stack of 30 million tokens on a sufficiently large grid.
The sandpile model has some interesting properties when played on a finite graph. In this case, it is convenient to designate one of the vertices as a sink. The sink never topples and can support arbitrarily high stacks. The picture above shows what happens on the complete graph with four vertices, in which each of the four vertices is connected to all three of the others. In each of the five situations, the sink is the top right vertex, shown in red. Each vertex has three neighbours, which means it is allowed to support a stack of up to 3−1=2 tokens. This restriction does not apply to the sink vertex, whose value can be ignored. An arrow shows what happens when one adds a token to the lower left vertex and then applies toppling operations until a stable configuration is reached.
A stable configuration is called recurrent if it can be obtained from any other stable configuration by increasing some of the numbers if necessary, then applying toppling operations and ignoring the value of the sink vertex. An example of a recurrent configuration is the one where each vertex holds the maximum stable number of tokens. Two recurrent configurations can be “added” by adding the number of tokens at each vertex, and then applying toppling operations. The interesting thing about this operation is that it makes the set of recurrent configurations into an abelian group. This means that there is an identity element, which by definition does nothing when added to another element. Another property is that each recurrent configuration has an additive inverse. One might think that the identity element would have a value of zero at each vertex, but this configuration is not recurrent. In fact, the identity elements for square grids of various sizes have a surprisingly complicated fractal-like structure, as shown in the animation above; here, the colours black, green, purple and gold represent the numbers 0, 1, 2, and 3, respectively.
The recent paper Sandpiles on the Vicsek fractal explode with probability ¼ by Nico Heizmann, Robin Kaiser, and Ecaterina Sava-Huss studies properties of the abelian sandpile model on the Vicsek fractal graph. This is an infinite graph formed by the iterative procedure shown above: the (n+1)-st level of the graph is formed from four copies of the graph at the n-th level, by connecting the middle four vertices in all possible ways. As before, the top right vertex is designated as the sink. The identity element of the graph at level 3 is shown below; here, the colours blue, orange, and red represent the numbers 2, 4, and 5 respectively.
The main result of the paper is that if one picks a random stable configuration of the Vicsek fractal and then adds a single token to a predetermined vertex, there is a 1 in 4 chance that this will cause an endless avalanche that never stabilizes. The authors also determine the structure of the sandpile groups for the finite graphs obtained at each stage of the iteration.
Picture credits and relevant links
The top sandpile picture is by colt_browning and the animation is by Moritz Lang. Both these pictures appear on Wikipedia’s page on the Abelian sandpile model.
The photograph of the Upwords board is my own.
The other three diagrams come from the paper by Nico Heizmann, Robin Kaiser, and Ecaterina Sava-Huss.
Wikipedia has a page on the Vicsek fractal.
The board game Upwords was originally marketed by the Milton Bradley Company.
Substack management by Buzz & Hum.