5
$\begingroup$

The famous chip firing game (which is closely related to sandpile models) goes like this:

Place chips at the vertices of a graph. REPEATEDLY: If a vertex $v$ of degree $d_{v}$ has at least $d_{v}$ chips, then it "fires" a chip along each of its incident edges. If there is vertex which can fire, the game is over.

Remarkably, whether a game terminates only depends on the graph and the initial configuration of chips (and not on the vertices chose to fire during the game). Even more remarkably, the length of the game (the number of fired vertices) does not depend on the actual play but rather only on the graph and the initial configuration.

Tardos and Bjorner-Lovasz-Shor have given well-known bounds for the length of the game.

On the other hand, there is a vast literature which studies the "critical group" (aka "sandpile group") of a graph, which is strictly speaking for a slightly different but related game (the so-called dollar game).

QUESTION: I am wondering if there is some connection between the duration of the chip firing game and the order of the critical group.

This is based on the vague intuition that the larger the group, the more opportunities the game has to terminate and so it can be expected to end rather sooner than later. But I may be completely off the mark here (for instance, I am mixing both games in my reasoning...).

Any thoughts on this highly appreciated.

Improve this question
$\endgroup$
10
  • 2
    $\begingroup$ Do you mean if there is NO vertex which can fire, then the game is over? Also, could you include a definition of the "critical group"? Nice question by the way, +1. $\endgroup$
    – Nick Gill
    Commented Aug 14, 2014 at 16:26
  • $\begingroup$ I think without the definition of what you call the "critical group", your question is unclear. Probably your definition of "critical group" is not this one? -- If this question would have been posted by a new user, I'd therefore vote to close as "unclear what you are asking". $\endgroup$
    – Stefan Kohl ♦
    Commented Aug 15, 2014 at 14:15
  • $\begingroup$ For definitions of sandpile terms, see arxiv.org/abs/1112.6163. At any rate, the order of the critical group is the number of spanning trees of $G$, which is the determinant of the reduced Laplacian. BLS give a bound on the length of the game in terms of the smallest nonzero eigenvalue of the Laplacian. $\endgroup$
    – Sam Hopkins
    Commented Aug 15, 2014 at 14:33
  • $\begingroup$ @SamHopkins, that sounds like an answer to me! $\endgroup$
    – Nick Gill
    Commented Aug 15, 2014 at 15:41
  • 1
    $\begingroup$ @FelixGoldberg: that's true. But keep in mind there is the subtle distinction between configurations (distributions of sand on the nonsink vertices) and divisors (distributions of sand on all the vertices). So above I am wrong to say the stable divisors form a monoid; it is the stable configurations which do. $\endgroup$
    – Sam Hopkins
    Commented Aug 16, 2014 at 14:16

1 Answer 1

Reset to default
2
$\begingroup$

Here is an example that ought to convince you that no bound like this can exist. Let $\ell(G,N)$ (for $N$ sufficiently small) denote the maximum length of a game on the graph $G$ that terminates and involves $N$ chips. Let $P_n$ denote the path graph on $n$ vertices and $S_n$ the star graph on $n$ vertices. It's not hard to see that $\ell(S_n,N) = N$ while $\ell(P_n,N) = \Theta(N^2)$. However, because they are trees, both $P_n$ and $S_n$ have trivial critical groups.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Note that this example also runs exactly opposite to the intuition mentioned by the OP: for $P_n$ we have $2^{n-2}$ stable states, while for $S_n$ we have $n-1$ stable states. So $P_n$ has more states to terminate into. However, the (worst-case) stopping time is much longer for $P_n$ than $S_n$. $\endgroup$
    – Sam Hopkins
    Commented Aug 16, 2014 at 5:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .