Graph Jacobian (Sandpile group) usages

353 Views Asked by At

Let $\Gamma$ be a graph (say, finite) and $S_\Gamma$ be it's Jacobian (also known as the sandpile group or Picard group). I'm wondering about what fundamental things one can learn about $\Gamma$ from studying $S_\Gamma$?

I know one connection is that it helps view a finite graph as a discrete Riemann surface. I've also seen some results on graph coloring that utilize properties of the Jacobian. Also, the area of sandpile models with some randomness are widely studied nowadays.

I'm more interested in just what one can learn about $\Gamma$ from it's Jacobian, for example about graph cycles, cliques, colorings, connectedness, etc. In other words, if I have a graph $\Gamma$, what can I learn from $S_\Gamma$ that's not so obvious from just looking at $\Gamma$?

1

There are 1 best solutions below

0
On

The order of this group is equal to the number of spanning forests of the graph. Compute the 2-sylow subgroup of this group and look at the number of cyclic factors in a direct sum decomposition; this number is the dimension of the so-called "bicycle space" of the graph (bicycles are subgraphs that are both edge-cuts and have even degree at each vertex; they form a vector space over the field of two elements).

The group can be read off from the Smith normal form of the Laplacian matrix of the graph. The number of connected components of the graph is one less than the number of zeroes appearing on the diagonal of the Smith normal form.

See the surveys by Dino Lorenzini, papers by Biggs, or the relevant chapters in Godsil-Royle for more information. The group also goes by the popular name "critical group" and has connection to some chip-firing games on the vertices of the graph.