WIXLIB

WHAT IS a sandpile?Lionel Levine and James ProppAn abelian sandpile is a collection of indistinguishable chips distributed among the vertices ofa graph. More precisely, it is a function fromthe vertices to the nonnegative integers, indicating how many chips are at each vertex. A vertex is called unstable if it has at least as manychips as its degree, and an unstable vertex cantopple by sending one chip to each neighboringvertex. Note that toppling one vertex may causeneighboring vertices to become unstable. If thegraph is connected and infinite, and the numberof chips is finite, then all vertices become stable after finitely many topplings. An easy lemmasays that the final stable configuration is independent of the order of topplings (this is the reason for calling sandpiles “abelian”). For instance,start with a large pile of chips at the origin of thesquare grid Z2 and perform topplings until every vertex is stable. The process gives rise toa beautiful large-scale pattern (Figure 1). Moregenerally, one obtains different patterns by starting with a constant number h 2d 2 of chips ateach site in Zd and adding n chips at the origin;see Figure 3 for two examples.Sandpile dynamics have been invented numerous times, attached to such names as chipfiring, the probabilistic abacus, and the dollargame. The name “sandpile” comes from statistical physics, where the model was proposed ina famous 1987 paper of Bak, Tang and Wiesenfeld as an example of self-organized criticality, orthe tendency of physical systems to drive themselves toward critical, barely stable states. In theoriginal BTW model, chips are added at randomvertices of an N N box in Z2 . Each time a chipis added, it may cause an avalanche of topplings.If this avalanche reaches the boundary, then topplings at the boundary cause chips to disappearfrom the system. In the stationary state, the distribution of avalanche sizes has a power-law tail:very large avalanches occur quite frequently (e.g.,the expected number of topplings in an avalanchegoes to infinity with N ).To any finite connected graph G we can associate an abelian group K(G), called the sandpilegroup. This group is an isomorphism invariant ofthe graph and reflects certain combinatorial information about the graph. To define the group,we single out one vertex of G as the sink andignore chips that fall into the sink. The operation of addition followed by stabilization gives theset M of all stable sandpiles on G the structure ofa commutative monoid. An ideal of M is a subset J M satisfying σJ J for all σ M . Thesandpile group K(G) is the minimal ideal of M(i.e., the intersection of all ideals). The minimalideal of a finite commutative monoid is alwaysa group. (We encourage readers unfamiliar withthis remarkable fact to prove it for themselves.)One interesting feature of constructing a groupin this manner is that it is not at all obviouswhat the identity element is! Indeed, for manygraphs G the identity element of K(G) is a highlynontrivial object with intricate structure (Figure 2).To realize the sandpile group in a more concrete way, we can view sandpiles σ as elementsof the free abelian group ZV , where V is the setof non-sink vertices of G. Toppling a vertex vcorresponds to adding the vector v to σ, where d(v) if v w, v,w 1if v w, 0otherwise.Here v w denotes adjacency in G, and d(v) isthe degree of vertex v. This observation suggeststhat we view two vectors σ, τ ZV as equivalentif and only if their difference lies in the Z-linearspan of the vectors v .The sandpiles lying in the minimal ideal of Mare called recurrent. It turns out that each equivalence class in ZV contains exactly one recurrentsandpile, and henceK(G) ZV / ZV .1

2The matrix ( v,w ) is called the reducedLaplacian of G (it is reduced because it does notinclude the row and column corresponding to thesink vertex). According to the matrix-tree theorem, the determinant det counts the numberof spanning trees of G. This determinant is alsothe index of the subgroup ZV in ZV , and so theorder of the sandpile group equals the number ofspanning trees.A refinement relates sandpiles to the Tuttepolynomial T (x, y) of G. The number of spanning trees of G equals T (1, 1). By a theorem ofMerino López, T (1, y) equals the sum of y σ m δover all recurrent sandpiles σ, where δ is the degree of the distinguished sink vertex, m is thenumber of edges of G, and σ denotes the number of chips in σ.The sandpile group gives algebraic manifestations to many classical enumerations of spanningtrees. For example, Cayley’s formula nn 2 for thenumber of spanning trees of the complete graphKn becomesIn particular, u obeys the inequalities(1)(2)u 0,σ u d 1.One can show that the sandpile toppling rule implies a kind of least action principle: the odometer function is the pointwise minimum of allinteger-valued functions u satisfying (1) and (2).The least action principle says that sandpilesare “lazy” in a rather strong sense: even if weallow “illegal” toppling sequences that result insome vertices having a negative number of chips,we cannot stabilize σ in fewer topplings than occur in the sandpile dynamics. What is more,sandpiles are locally lazy: not only is the totalnumber of topplings minimized, but each vertexdoes the minimum amount of work required of itto produce a stable final configuration.The least action principle characterizes theodometer function as the solution to a type ofvariational problem in partial differential equan 2tions called an obstacle problem. The problemK(Kn ) (Zn ).takes its name from an equivalent formulation inThe formula mn 1 nm 1 for the number of span- which one is given a function called the obstaning trees of the complete bipartite graph be- cle and asked to find the smallest superharmoniccomesfunction lying above it.n 2m 2The obstacle problem for the sandpile odomeK(Km,n ) Zmn (Zm ) (Zn ).ter has one extra wrinkle, which is the constraintThe name “sandpile group” is due to Dhar, whothat u be integer valued. Relaxing this conused the group to analyze the BTW sandpilestraint yields the odometer function for a differmodel.ent model called the divisible sandpile, in whichA deep analogy between graphs and algebraicthe discrete chips are replaced by a continucurves can be traced back implicitly to a 1970ous amount of mass which may be subdividedtheorem of Raynaud, which relates the compoarbitrarily finely during topplings. The divisinent group of the Neron model of the Jacobianble sandpile has dramatically different behavior:of a curve to the Laplacian matrix of an associstarting with mass m at the origin in Z2 , one obated graph. In this analogy, the sandpile grouptains a region Am of fully occupied sites, borderedof the graph plays a role analogous to the Picardby a strip of partly filled sites. The set Am is verygroup of the curve. Many of the authors whonearly circular, reflecting the rotational symmeexplored this analogy chose different names fortry of the continuous Laplacian. Amazingly, thethe sandpile group, including “group of compoanisotropy as well as the intricate patterns of Fignents” (Lorenzini), “Jacobian group” (Bacher eture 1 arise entirely from the extra integrality conal.) and “critical group” (Biggs). Recent work ofstraint.Baker and Norine carries the analogy further byTwo fundamental features of sandpiles in latproving a Riemann-Roch theorem for graphs.tices Zd remain unexplained by theorems. One isThe odometer of a sandpile σ is the functionscale invariance: large sandpiles look like scaledon vertices defined byup small sandpiles. The picture in Figure 1,u(v) # of times v topplesrescaled by a factor of 1/ n, appears to havea limit as n . The limit is a function f onduring the stabilization of σ.the unit square [0, 1]2 which is locally constantThe final stable configuration τ is given in termson an open dense subset. Each region where fof σ and u byis constant corresponds to a patch on which theτ σ u.sandpile configuration is periodic. The second

3unexplained feature is dimensional reduction: ddimensional slices of (d 1)-dimensional sandpileslook like d-dimensional sandpiles, except in a region near the origin. Figure 3 compares a sandpile in Z2 with a 2-dimensional slice of a sandpilein Z3 .As a way of measuring avalanches, Dhar considered the odometer function associated with theoperation of adding a single chip to a sandpile.Starting from the stationary state and adding asingle chip at v, let uv (w) be the expected number of times w topples. When the system stabilizes, it is again in the stationary state, so theexpected net change in height from topplings is uv (w) δv,w (here δ is Kronecker’s delta). Inother words,uv (w) ( 1 )v,w .The entry ( 1 )v,w of the inverse reducedLaplacian matrix has a natural interpretation interms of random walks: it is the expected number of visits to w by a random walk on G startedat v and stopped when it first visits the sink. Forexample, if G is the cube of side length n in Zd(d 3) with sink at the boundary of the cube,then this expectation has order v w 2 d for v, waway from the boundary. Summing over w, wesee that the expected number of topplings diverges as n . The situation is even moreextreme for d 2: the expected number of timeseach individual site near v topples goes to infinitywith n.References[1] D. Dhar, Theoretical studies of self-organized criticality, Physica A 369 (2006), 29–70.[2] A. Holroyd, L. Levine, K. Mészáros, Y. Peres, J. Proppand D. B. Wilson, Chip-firing and rotor-routing ondirected graphs, 2008. http://arxiv.org/abs/0801.3306[3] F. Redig, Mathematical aspects of the abelian sandpilemodel, Les Houches lecture notes, 2005. http://www.math.leidenuniv.nl/ redig/sandpilelectures.pdf

Figure 1. Stable sandpile of n 106 chips in Z2 . Color scheme: sitescolored blue have 3 chips, purple 2 chips, red 1 chip, white 0 chips.1

Figure 2. Identity element of the sandpile group of the 521 521square grid graph, with sink at the boundary. Color scheme: sitescolored blue have 3 chips, green 2 chips, red 1 chip, orange 0 chips.

Figure 3. Top: A two-dimensional slice through the origin of the sandpile of n 5 · 106 particles in Z3 on background height h 4. Bottom:The sandpile of m 47465 particles in Z2 on background height h 2.Color scheme on left: sites colored blue have 5 particles, turquoise 4,yellow 3, red 2, gray 1, white 0. On right: blue 3 particles, turquoise 2,yellow 1, red 0.

ter has one extra wrinkle, which is the constraint that u be integer valued. Relaxing this con-straint yields the odometer function for a differ-ent model called the divisible sandpile,inwhich the discrete chips are replaced by a continu-ous amount of mass which may be subdivided arbitrarily finely during topplings. The divisi-