18 312 Algebraic Combinatorics Lionel Levine Lecture 23 Lecture date May 10 2011 1 Notes by David Thomas Abelian Sandpile Model Definition 1 sink sandpile chips Let G V E be a finite connected undirected graph with a sink vertex z Then a sandpile is a map V Z 0 such that v number of chips at vertex v Definition 2 stable unstable A vertex v which is not a sink is unstable if v d v where d v is the degree of v Otherwise is is stable Definition 3 topple If v is unstable it can topple giving rise to a new sandpile 0 w v d v for w v w 1 when w and v are neighbors and w otherwise The inspiration behind these names comes from the following example Consider grains of sand being droped onto a sandpile As the sand in the pile increases there is a trickling down effect which corresponds to toppling See the image below Now consider the following exapmle where G C5 23 1 Notice that toppling vertics in a different order leads to the same final result We will prove a theorem about this after developing a few more definitions If v V let v w d v w v 1 if w is neighbor of v and 0 otherwise Then toppling vertex v corresponds to setting 0 Av Definition 4 legal sequence A sequence x1 xk V is a legal toppling sequence for if i xi d xi for all i 1 k where 1 and i 1 i xi for i 1 k 1 Definition 5 stabilizing A sequence y1 yl is stabilizing for if y1 yl w d w 1 for all w V z where z is the sink In the pentagon example above we see thta 1 2 1 5 1 5 1 2 1 5 2 1 and 1 2 5 1 are all legal and stabilizing for 3 1 0 0 1 Notice that the legal and stabilizing sequences are all permutations of each other This inspires the following theorem Theorem 6 Abelian Property If x1 xk and y1 yl are both legal and stabilizing for then k l and there exists Sk such that xi y i for all i 1 k We will get more millage out of the next lemma which implies the abelian property Lemma 7 If x1 xk is legal for and y1 yl is stabilizing for then k l and there exists Sl such that xi y i for all i 1 k Proof Induct on k x legal implies x1 d x1 Notice that toppling any vertex v 6 x does not decrease x1 y stabilizing implies that there exists j such that yj x1 Set i j The sequence yj y1 yj 1 yj 1 yl is stabilizing for which implies y1 yj 1 yj 1 yl is stabilizing for 2 1 x1 Also x2 xk is legal for 2 By inductive hypothesis x2 xk is a permutation of a subsequence of y1 yj 1 yj 1 yl 2 Definition 8 sandpile monoid The sandpile monoid of G z is M G z stable sandpiles Vo Z 0 where Vo V z with operation 1 2 1 2 o Definition 9 stabilization The stabilization o of is o x1 xk where x1 xk is a legal stabilizing sequence for See the example below 23 2 Now M is a monoid because it is associative 1 2 o 3 o 1 2 3 o 1 2 3 o o and has an identity 0 o Theorem 10 Let M be a finite commutative monoid Then J group T I M I ideal I is an abelian Proof Given x J claim x J J ie J J and y x y is a permutation of J First note that J itself is an ideal J M I M I M I J Now will show x J is an ideal x J M x J M x J and since J is minimal ideal J x J Hence x J J Now will show the existence of an identity element Let x J J be a permutation with x y x y The exists n 1 such that xn y y Then nx y y for all y J and we can let e nx Then e y y for all y J and e is unique because e e e0 e0 e is our identity Now define x n 1 x so x x nx e Then x is inverse of x Hence this is an abelian group 2 Definition 11 sandpile group The T I M G z I ideal I sandpile group of G z is K G z For the last ten minutes of lecture Professor Levine showed some examples of sandpiles and talked about research in the field 23 3 23 4