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…..
Best Answer
Answer: The Pic0(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:
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.