Invariants

G is a finite undirected connected graph; L is its laplacian matrix; c is a chip configuration on G. Following Taoran's idea, we're going to look for linear invariants of parallel chip-firing, i.e. invariants of the form

$f\cdot c = \sum_{v\in V} f(v)c(v)$.

Invariant means that $f \cdot c = f \cdot Uc$ for all chip configurations $c$, where $Uc$ denotes the parallel update of $c$ (every unstable site fires once).

1. Show that if $Lf=0$ then $f \cdot c$ is an invariant.

2. Show that the kernel of L is 1-dimensional spanned by the all 1's vector. What invariant does this choice of f correspond to?

3. f is called "harmonic mod 1" if $Lf \in Z^n$. In other words, Lf has only integer values (even though f may not). For example, on a 2 by n cylinder with n even the function that is 1/6 on even vertices and -1/6 on odd vertices is harmonic mod 1. Show that if f is harmonic mod 1, then $f \cdot c$ mod 1 is an invariant.

4. Find all harmonic mod 1 functions on the cycle graph of size n (hint there are n of them).

5. Show that on any graph the harmonic mod 1 functions form a group under addition.

6. Show that this group is isomorphic to the sandpile group of G.

page revision: 4, last edited: 28 Jul 2011 14:41