Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.....

share|improve this question
    
I haven't made any progress on proving or disproving the more precise question --- but I sure had fun playing around with these permutations! I highly recommend it as a holiday diversion. If I haven't made any mistakes, the m.p.q. holds also for the 4-cycle C_4 and the square-with-diagonal K_4-minus-one-edge (at least with the usual cyclic ordering). –  Tom Church Dec 16 '11 at 5:13
    
Cool -- I think I agree about C_4 (but didn't do it carefully enough to be sure) and then I didn't brave the 5-edge graph. The K_4 should be a very interesting example, since it has a big automorphism group to play with! –  JSE Dec 16 '11 at 5:32
    
I thought it is known that the sandpile group acts f.p.f. on the set of spanning trees, thus making it into a principal homogeneous space. Are the torsors you talk about the same objects as principal homogeneous spaces? –  Dima Pasechnik Mar 25 '12 at 5:37
    
something along these lines: each spanning tree $T$ defines a bijection $f_T$ from the set $\mathcal{T}$ of spanning trees to the sandpile group. Take the compositions $f_{T'}^{-1}\circ f_T$, for $T,T'\in\mathcal{T}$. They generate a permutation group on $\mathcal{T}$, isomorphic to the sandpile group. Maybe actually nobody proved anything this? –  Dima Pasechnik Mar 25 '12 at 5:44
    
Dima -- yes, "torsor" and "principal homogeneous space" are synonyms, at least in my usage. –  JSE Mar 25 '12 at 20:35

1 Answer 1

up vote 17 down vote accepted

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. 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.

share|improve this answer
    
Beautiful answer, Tom! –  Andy Putman Aug 14 '13 at 16:24
    
Rock and roll!! –  JSE Aug 15 '13 at 3:25
1  
and how about Eulerian digraphs? In this case the question about the torsor makes perfect sense too. –  Dima Pasechnik Aug 26 '13 at 7:32

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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