parallel chip-firing problems

In these problems, $G=(V,E)$ is a finite connected undirected graph with $n$ vertices and $m$ edges. Notation:

  • $\sigma$ denotes a chip configuration on $G$.
  • $U \sigma$ is the chip configuration obtained by firing all unstable vertices in $\sigma$.
  • $a(\sigma)$ is the activity of $\sigma$.
  • $|\sigma| = \sum_{v \in V} \sigma(v)$ is the number of chips in $\sigma$.
  • $d(v)$ is the degree of vertex $v$.

1. Complimentary configurations. Let $\sigma$ and $\tau$ be two chip configurations on $G$ satisfying $\sigma + \tau = 2d -1$. (In other words, $\sigma(v) + \tau(v) = 2d(v) - 1$ for all vertices $v$.)

  • Show that every vertex $v$ is either unstable for $\sigma$ or unstable for $\tau$, but not both.
  • Show that $U\sigma + U\tau = 2d-1$.
  • Conclude that $a(\sigma) + a(\tau) = 1$.

Problem 1 is useful because it allows you to assume in many proofs that $a(\sigma) \leq \frac12$. The case $a(\sigma)>\frac12$ then follows by applying the proof to $\tau = 2d-1-\sigma$.

2. All vertices have the same activity. We could define activity of a particular vertex: $a_v(\sigma) = \lim_{t \to \infty} \alpha_v(t) /t$ where $\alpha_v(t)$ is the number of times $v$ fires in the first $t$ time steps. Prove that $a_v(\sigma) = a_w(\sigma)$ for all vertices $v$ and $w$.

3. Stairs of height 0 and 1. Prove that

  • If $|\sigma| < m$ then $a(\sigma)=0$.
  • If $|\sigma| > 3m-n$ then $a(\sigma)=1$.

(Hint: once you've done the first part, you can use problem 1 to deduce the second part.)

If you get stuck on problems 1-3, take a look a the paper by Prisner. If you don't find what you need in there, post on the discussion board and I will track down the right reference.

4. Staircase of a cycle graph. Let $G=C_n$ be the cycle graph of length $n$ for $n$ even. In this problem you'll show that the staircase of $C_n$ has three stairs: height $0$, $\frac12$ and $1$. Prove that

  • If $|\sigma|<n$ then $a(\sigma)=0$.
  • If $|\sigma| = n$ then $a(\sigma) = \frac{k}{n}$ for some integer $0 \leq k \leq \frac{n}{2}$.
  • If $n < |\sigma| < 2n$ then $a(\sigma)=\frac12$.
  • If $|\sigma| = 2n$ then $a(\sigma) = \frac{k}{n}$ for some integer $\frac{n}{2} \leq k \leq n$.
  • If $2n < |\sigma|$ then $a(\sigma)=1$.
  • What changes if $n$ is odd?

This is a challenging problem. If you get stuck take a look at the two references on parallel chip-firing on the cycle graph. If you solve any of these exercises, please tex up and post the solution! I'd especially like to see a nice writeup of problem 4, since this is a known result but one that is not easy to extract from the papers. Those of you working on the "period 2" problem on ladder graphs will find the case $n < |\sigma| < 2n$ of problem 4 especially useful.