From what I understand, given a graph, the Jacobian group and the Sandpile group refer to the same object. Until now, I have been computing this group in the way detailed in Chapter 1 of this undergraduate thesis. The approach is to use a theorem that says for any graph $G$ on $n$ vertices, $$ \text{Jac}(G) \cong \mathbb{Z}^{n-1}/\text{im}\left(\tilde{\Delta}\right), $$ where $\tilde{\Delta}$ is the reduced Laplacian of the graph. To find the image of $\tilde{\Delta}$, it is first reduced to Smith normal form. I am looking for more insight into the process and was wondering if anyone could explain or link an alternative method for arriving at the Jacobian of a graph. In particular, I am interested in graphs of hypercubes.
3
-
1$\begingroup$ The SNF seems to me to be the fastest way to compute the isomorphism type of the Jacobian of arbitrary graphs. There are other things you could want though... like representatives (recurrent configurations or superstable configurations). $\endgroup$– Sam HopkinsCommented Feb 3, 2017 at 14:04
-
$\begingroup$ Hi! Thank you for the response! I would indeed like the isomorphism type of the Jacobian, but I'm not necessarily concerned with efficiency. I'm looking for intuition about the Jacobian and was hoping to find a different method that might shed a different light on the subject. $\endgroup$– Aaron BagheriCommented Feb 13, 2017 at 10:56
-
$\begingroup$ I recommend this book in progress as a starting point to learn about Jacobians of graphs: people.reed.edu/~davidp/divisors_and_sandpiles. In particular, Exercise 12.3 might be interesting to you: it shows that deleting an edge from your graph G can increase the minimal number of generators of the Jacobian. $\endgroup$– Sam HopkinsCommented Feb 14, 2017 at 18:45
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
In a survey article on chip-firing, the sandpile group is defined on page 7 (definition 2.7) as $$\mathbb{Z}^{n-1} / \mathbb{Z}^{n-1} \tilde{\Delta}$$
Note that the authors use $\Delta'(G)$ to denote the reduced Laplacian. In the paper, $\mathbb{Z}^{n-1} \Delta'(G)$ refers to the abelian group generated by taking integer-linear combinations of the rows of $\Delta'(G)$, which I assume is what you mean by $im(\tilde{\Delta})$.
This gives a related, but alternative way of arriving at the Jacobian/Sandpile group: each element of the group corresponds to the a recurrent chip configuration in the chip-firing game (Corollary 2.16).
The chip-firing game is a variation of the lending-and-borrowing game described in the thesis you've linked. In chip-firing, no vertex is allowed to go into debt, and the game terminates if a sequence of lending moves results in no vertex being able to lend without going into debt (such a configuration is stable). A recurrent chip configuration is a stable configuration with the additional property that it is accessible (Definition 2.11).
Referenced: Holroyd, Alexander E., et al. "Chip-firing and rotor-routing on directed graphs." In and Out of Equilibrium 2. Birkhäuser Basel, 2008. 331-364.
-
$\begingroup$ You say "Here $\mathbb Z^{n - 1}\Delta'(G)$ refers to …", but you haven't used $\mathbb Z^{n - 1}\Delta'(G)$. Did you mean $\mathbb Z^{n - 1}\tilde\Delta$? $\endgroup$– LSpiceCommented Nov 20, 2018 at 14:47
-
$\begingroup$ I just meant to clarify that $\Delta'(G)$ in the linked paper refers to the same thing as $\tilde \Delta$ does in this question (the reduced Laplacian), since that notation is defined in an earlier section of the paper and I was linking to the middle of it. $\endgroup$ Commented Nov 21, 2018 at 4:45