What is the sandpile torsor?

Question

Let G be a finite undirected connected graph. A divisor on G is an element of the free abelian group Div(G) on the vertices of G (or an integer-valued function on the vertices.) Summing over all vertices gives a homomorphism from Div(G) to Z which we call degree.

For each vertex v, let D(v) be the divisor

$d_v v - \sum_{w \sim v} w$

where $d_v$ is the valence of v and $v \sim w$ means "$v$ and $w$ are adjacent."

Note that D(v) has degree 0. The subgroup of Div(G) generated by the D(v) is called the group of principal divisors. We denote by Pic(G) the quotient of Div(G) by the group generated by the principal divisors, and by Pic^0(G) the kernel of the degree map from Pic(G) to Z.

The notation here suggests that I am really thinking about algebraic curves, not graphs; and that's in some part true! In the work of Matt Baker and his collaborators you can find a really beautiful translation of much of the foundational theory of algebraic curves (Riemann-Roch, Brill-Noether, etc.) into this language.

But that's not really what this question is about.

Lots of people study this abelian group, maybe most notably statistical physicists and probabilists who study dynamical processes on graphs. In those communities, Pic^0(G) is called the sandpile group, because of its relation with the abelian sandpile model.

But that's also not really what this question is about.

What this question is about is the following fact: by the matrix-tree theorem, the number of spanning trees of G is equal to |Pic^0(G)|.

When one encounters a finite set that has the same cardinality as a finite group, but the set does not have any visible natural group structure, one's fancy lightly turns to thoughts of torsors. So:

QUESTION: Is the set S of spanning trees of G naturally a torsor for the sandpile group Pic^0(G)? If so, how can we describe this "sandpile torsor?"

(By "naturally" we mean "functorially" -- in particular, this torsor should be equivariant for the automorphism group of G.)

That question is rather vague, so let me make it more precise, and at the same time try to argue that in at least some cases the question is not ridiculously speculative. The paper "Chip-Firing and Rotor-Routing on Directed Graphs," by (deep breath) Alexander E. Holroyd, Lionel Levine, Karola Meszaros, Yuval Peres, James Propp and David B. Wilson, contains a very interesting construction of a "local" torsor structure for the sandpile group. Suppose G is a planar graph -- or more generally any graph endowed with a cyclic ordering of the edges incident to each vertex. Then the "rotor-router process" described in Holroyd et al gives S the structure of a Pic^0(G)-torsor! (See Def 3.11 - Cor 3.18) This would seem to answer my question; except that the torsor structure they define depends, a priori, on the choice of a vertex of G. A better way to describe their result is as follows: for each v, let S_v be the set of oriented spanning trees of G with v as root. Then the rotor-router model realizes S_v as a torsor for the group Pic(G) / $\mathbf{Z}$ v.

But S_v is naturally identified with S (just forget the orientation) and the natural map Pic^0(G) -> Pic(G) / $\mathbf{Z}$ v is an isomorphism. So for each choice of v, the rotor-router construction endows S with the structure of Pic^0(G)-torsor. Now one can ask:

QUESTION (more precise): Are the torsor structures provided by the rotor-router model in fact independent of v? Do they in fact provide a Pic^0(G)-torsor structure on S which is functorial for maps compatible with the cyclic edge-orderings, and in particular for automorphisms of G as a planar graph? If this is false in general, is there some nice class of graphs G for which it's true?

REMARK: If you are used to thinking about algebraic curves, like me, your first instinct might be "well, surely if the set of spanning trees is a torsor for Pic^0, it must be Pic^d for some d." But I don't think this can be right. Here's an example: let G be a 4-cycle, which we think of as embedded in the plane. Now the stabilizer of a vertex v in the planar automorphism group of the graph is a group of order 2, generated by a reflection of the square across the diagonal containing v. In particular, you can see instantly that no spanning tree in S is fixed by this group; the involution acts as a double flip on the four spanning trees in S. On the other hand, Pic^d(G) is always going to have a fixed point for this action: namely, the divisor d*v.

REMARK 2: Obviously the correct thing to do is to compute a bunch of examples, which might instantly give negative answers to these questions! But it gets a bit tiring to do this by hand; I checked that everything is OK for the complete graph on 3 vertices (in which case the torsor actualy is Pic^1(G)) and then I ran out of steam. But sage has built-in sandpile routines.....

Answer 1

Answer: The Pic⁰(G)-torsor structure is independent of the vertex v if and only if G is a planar ribbon graph.

This is the main theorem of "Rotor-routing and spanning trees on planar graphs", by Melody Chan, Thomas Church, and Joshua Grochow, which we just posted to the arXiv [later published in IMRN]. Quoting from the introduction:

The proof is based on three key ideas. First, the rotor-routing action of the sandpile group on spanning trees can be partially modeled via rotor-routing on unicycles ([HLMPPW, §3]). This is a related dynamical system with the property that rotor-routing becomes periodic, rather than terminating after finitely many steps.

The second main idea is that the independence of the sandpile action on spanning trees can be described in terms of reversibility of cycles. We introduce the notion of reversibility (previously considered in [HLMPPW] only for planar graphs), and prove that reversibility is a well-defined property of cycles in a ribbon graph. We also establish a relation between reversibility and basepoint-independence.

Third, reversibility is closely related to whether a cycle separates the surface corresponding to the ribbon graph into two components. We prove that these conditions are almost equivalent. Moreover, although they are not equivalent for individual cycles, we prove that all cycles are reversible if and only if all cycles are separating, in which case the ribbon graph is planar.

We're grateful to Jordan for the question, which turned out to have a much more interesting answer than we expected! We're also grateful to Math Overflow for providing a venue for this question.

Answer 2

I recently wrote "Rotor-Routing Induces the Only Consistent Sandpile Torsor Algorithm Structure" with Ankan Ganguly which was inspired by this question (and, more directly, a conjecture by Klivans). As one may surmise from the title, we show that the sandpile torsors that comes from rotor-routing on plane graphs are in a sense unique.

We use the term sandpile torsor algorithm to mean a map from the set of plane graphs to the set of sandpile torsor actions (i.e. free transitive actions of the sandpile group on the spanning trees). Rotor-routing actually defines 4 sandpile torsor algorithms which have the same structure: clockwise rotor-routing, counterclockwise rotor-routing, inverse clockwise rotor-routing, and inverse counterclockwise rotor-routing.

The first major challenge in this project was figuring out how to define a consistent sandpile torsor algorithm. In particular, the torsors we obtain on different graphs should be related in some way. With this in mind, we looked at how rotor-routing interacts with contraction and deletion and found a remarkable property.

Let $G$ be a plane graph and suppose $c$ and $s$ are two vertices joined by an edge. Then $c-s$ is a representative for some equivalence class of $Pic^0(G)$. Let $T$ be a spanning tree of $G$ and $T'$ be the spanning tree we get by acting on $T$ by $c-s$ using rotor-routing.

1. For an arbitrary $e \in T \cap T'$ (not incident to both $c$ and $s$), consider the plane graph $G/e$. If we act on $T\setminus e$ by $c-s$ using rotor-routing, then we get $T' \setminus e$.
2. For an arbitrary $e \not\in T \cup T'$, consider the plane graph $G\setminus e$. If we act on $T$ by $c-s$ using rotor-routing, then we get $T'$.

We use these properties to define consistent sandpile torsor algorithms (along with a third property that lets us restrict to 2-connected plane graphs). The bulk of the paper is spent proving that any sandpile torsor algorithm satisfying the properties of consistency must be equivalent to one of the 4 torsor algorithms coming from rotor-routing.

This was a really fun project and I'd love to talk more about it if anyone has any questions or comments. Thanks to Jordan Ellenberg for posing the question and to everyone who has worked toward answering it!

Answer 3

If the ribbon graph $G$ is planar, then one can interpret the rotor-routing torsor as an action of $Pic^0(D_E)$ on $Pic^d(D_E)$ where $D_E$ is the medial graph. More precisely:

As the paper "Rotor-routing and spanning trees on planar graphs", by Melody Chan, Thomas Church, and Joshua Grochow shows, the rotor-routing torsor is independent of the vertex v if and only if the ribbon structure is planar. But the definition of rotor routing depends on the auxiliary vertex.

For planar ribbon graphs, one can also give a canonical definition for the rotor-routing torsor (using no fixed vertex, or reference orientation for the graph). This is explained in our paper "The sandpile group of a trinity and a canonical definition for the planar Bernardi action" by Tamás Kálmán, Seunghun Lee and Lilla Tóthmérész. (The paper concerns a slightly more general case. This note concentrates only on the graph case, hence it is much more easy to read.)

Our definition also shows that the planar rotor-routing torsor is an action of $Pic^0(D_E)$ on $Pic^d(D_E)$ where $D_E$ is the medial graph and $d=|V|-1$. Let me try to explain this in a short way.

Let $G=(V,E)$ be a planar ribbon graph. Let $D_E = (E,A)$ be the directed medial graph of $G$, which is an Eulerian digraph whose vertex set is the edge set $E$ of $G$, and an arc points from edge $e_1$ to edge $e_2$ if $e_1$ and $e_2$ are both incident to some vertex $v$ in $G$, and $e_2$ follows $e_1$ at $v$ in the ribbon structure.

Since $D_E$ is an Eulerian digraph, it also has a sandpile group, and the divisors of $Pic^0(D_E)$ are integer-valued functions on $E$. We show that $Pic^0(D_E)$ is canonically isomorphic to both $Pic^0(G)$ and to $Pic^0(G^*)$. (The definition of the isomorphism is also canonical, it does not use any reference orientation.) Moreover, the characteristic vectors of the spanning trees of $G$ naturally correspond to $Pic^{|V|-1}(D_E)$: That is, each equivalence class of $Pic^{|V|-1}(D_E)$ contains exactly one spanning tree.

It turns out that the planar rotor-routing torsor is the action of $Pic^0(D_E)$ on $Pic^{|V|-1}(D_E)$, composed with the canonical isomorphism between $Pic^0(G)$ and $Pic^0(D_E)$.

For this definition, the compatibility of the action with planar duality follows almost immediately.

One can also partially address the Eulerian case. Rotor-routing (with root vertex v) acts on the arborescences rooted at v. It is known that if a digraph is Eulerian, then for any v, the number of arborescences rooted at v is the same. Hence one could potentially ask if rotor-routing with different root vertices acts "the same way" on arborescences. However, for general digraphs, it is not clear how arborescences with different root vertices correspond to each other. (For undirected graphs, one can "forget orientations" and that solves the problem.) We showed that if an Eulerian digraph is embedded into the plane so that around each vertex, in- and out-edges alternate, then one can give a correspondence between arborescences with different roots, and the canonical definition of rotor-routing can be generalized to this case as well.