4
$\begingroup$

How we can prove each finite Abelian group is the sandpile group for some graph ?

$\endgroup$
  • $\begingroup$ Why do you know this to be true? $\endgroup$ – Igor Rivin Sep 22 '13 at 1:24
  • $\begingroup$ I have been reading this in a paper.Primers for the algebraic geometry of Sandpiles. $\endgroup$ – Hamed Khalilian Sep 22 '13 at 8:37
  • $\begingroup$ By the structure theorem for finitely generated modules over a principal ideal domain, every finite Abelian group can be expressed as a direct product of cyclic groups. Do you have a method of implementing cyclic groups as graphs, together with some way of combining graphs so as to multiply their sandpile groups? If so, that solves your question. $\endgroup$ – Adam P. Goucher Sep 22 '13 at 8:54
  • $\begingroup$ Thanks for the hint but that's exactly the difficult part of the question that I don't know how to show. $\endgroup$ – Hamed Khalilian Sep 22 '13 at 10:09
  • $\begingroup$ The second part is easy (the group of a disjoint union is the product of the groups), but I am having some trouble finding graphs with cyclic sandpile groups (products of two cyclic groups are common). $\endgroup$ – Igor Rivin Sep 22 '13 at 14:05
6
$\begingroup$

Modulo $2$-torsion any abelian group is the sandpile group of a connected simple graph. It appears that there is some trouble with the cyclic group of order $2$. Still, you can get away with at worst using two edges between two vertices.

To see that the Sandpile group of a cycle is cyclic simply put its Laplacian matrix into diagonal form using integer row and column operations (this is trivial). To get multiplicativity it is easiest to use an alternative presentation of the sandpile group: It is $Z^\#/Z$ where $Z$ is the cycle space of $G$ and $Z^\#$ is the dual lattice (see Godsil and Royle for a textbook treatment or Bacher, de la Harpe, Nagnebeda).

If $G$ and $H$ are connected at a single vertex (forming $G \cdot H$) then their cycle spaces factor as a direct sum and thus $K(G \cdot H) = K(G) \oplus K(H)$, where $K(-)$ is the sandpile group of $-$. Now string a bunch of cycles together to get any abelian group is the sandpile group of a connected graph where any pair of vertices is connected by at most two edges.

$\endgroup$
2
$\begingroup$

This paper: https://arxiv.org/abs/1410.5144 has more to say about which groups arise as the sandpile group of simple graphs, which is indeed a delicate question.

EDIT: One result they prove, relevant to the original question, is that if $H$ is any abelian group, then there is some $k_0$ depending on $H$ such that $H \times (\mathbb{Z}/2\mathbb{Z})^k$ is not the sandpile group of any simple graph for any $k \geq k_0$.

$\endgroup$
1
$\begingroup$

The paper the OP cites states this fact as obvious (page 6), but if you look at their indicated argument, it only works for multigraphs. (in which case there are many ways to skin that particular cat, in particular joining two trees by $m$ parallel edges should give a cyclic group of order $m.$ I have no idea if the statement is even true if you restrict to simple graphs. In fact, if the graph has $p$ spanning trees (where $p$) is prime, its sandpile group is $\mathbb{Z}/p \mathbb{Z}$ and according to this question there is always a graph with a prescribed tree number, so this gives you sandpile groups with all square-free orders.

$\endgroup$
  • $\begingroup$ The graph with tree number $p$ is just the cycle $C_p$, so perhaps there is a more elementary way to check that its sandpile group is $\mathbb Z/p\mathbb Z$? $\endgroup$ – Will Sawin Sep 22 '13 at 19:24
  • $\begingroup$ True. I assume this also implies that the cycle $C_n$ has group $\mathbb{Z}/n \mathbb{Z},$ which does the trick for all finite abelian groups. $\endgroup$ – Igor Rivin Sep 22 '13 at 19:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.