The Circuit-Cocircuit Reversal System and Torsor Structures on Spanning Trees

The Jacobian of a finite graph G is a finite abelian group whose cardinality is equal to the number of spanning trees of G.  In this earlier post, I discussed a family of combinatorial bijections between elements of {\rm Jac}(G) and the set {\mathcal T}(G) of spanning trees of G.  I also discussed the fact that for plane graphs, these Bernardi bijections come from a natural simply transitive action of {\rm Jac}(G) on {\mathcal T}(G) (or, more precisely, a natural isomorphism class of such actions).

In the present post, I’d like to discuss a different family of simply transitive actions of {\rm Jac}(G) on {\mathcal T}(G) discovered by myself, Spencer Backman (a former student of mine), and Chi Ho Yuen (a current student of mine).  One virtue of our construction is that it generalizes in a natural way from graphs to regular matroids.  (We will mostly stick to the graphical case in this post, but will insert some comments about extensions to regular and/or oriented matroids.  A regular matroid can be thought of, rather imprecisely, as the smallest natural class of objects which contain graphs and admit a duality theory generalizing duality for planar graphs. Regular matroids are special cases of the more general concept of oriented matroids.)

One of the main new ideas in [BBY] (as we will henceforth refer to our paper) is to use the torsor {\rm Pic}^{g-1}(G) as an intermediate object rather than {\rm Pic}^{g}(G).  The latter is canonically isomorphic (as a {\rm Jac}(G)-torsor) to the set of break divisors on G; the former is isomorphic to the circuit-cocircuit reversal system, which we now introduce.

The circuit-cocircuit reversal system

The central object of this post will be the circuit-cocircuit reversal system {\mathcal G}(G) of a connected graph G, introduced in 2007 by Emeric Gioan.  We review the definition (see also this previous post).  An oriented circuit in G is a directed simple closed cycle C in G.  An oriented cocircuit C^* in G is the set of all directed edges connecting A to B, where A \coprod B is a partition of the vertices of G into disjoint connected subsets A and B.  An orientation of G is a choice, for each (undirected) edge e of G, of one of the two directed edges corresponding to it.  A set X of directed edges of G is compatible with an orientation {\mathcal O} if every edge in the support of X is oriented the same way in X and {\mathcal O}.  A circuit reversal consists of replacing an orientation {\mathcal O} by the orientation {\mathcal O}' in which all elements of some {\mathcal O}-compatible oriented circuit C are reversed; we define cocircuit reversals similarly.  Two orientations {\mathcal O},{\mathcal O}' are circuit-cocircuit equivalent if they differ by a finite sequence of circuit and cocircuit reversals.

Definition: The circuit-cocircuit reversal system {\mathcal G}(G) is the set of equivalence classes of orientations with respect to the circuit-cocircuit equivalence relation.

The same definitions allow us to define {\mathcal G}(M) for any oriented matroid M.  Using a deletion-contraction argument, Gioan proved:

Theorem (Gioan):  The cardinality of {\mathcal G}(G) is equal to the number of spanning trees of G.  More generally, for any regular matroid M the cardinality of {\mathcal G}(M) is equal to the number of bases of M.

My student Chi Ho Yuen proves a converse of sorts in this paper:

Theorem (Yuen): For any oriented matroid M, the cardinality of {\mathcal G}(M) is less than or equal to the number of bases of M, with equality if and only if M is regular.

Action of the Jacobian group on {\mathcal G}

As first observed by Backman, there is a natural bijection between {\mathcal G}(G) and {\rm Pic}^{g-1}(G) which extends to a natural isomorphism of {\rm Jac}(G)-sets.  The bijection from {\mathcal G}(G) to {\rm Pic}^{g-1}(G) takes the equivalence class of an orientation {\mathcal O} to the linear equivalence class of the divisor {\rm div}({\mathcal O}), as defined in this post. To prove that this map is a bijection, one uses the preliminary observations that two orientations {\mathcal O},{\mathcal O}' are circuit-equivalent (i.e., they differ by a sequence of circuit reversals) iff  {\rm div}({\mathcal O}) = {\rm div}({\mathcal O}'), and that if {\mathcal O},{\mathcal O}' are cocircuit equivalent then their associated divisors are linearly equivalent (since reversing an oriented cocircuit can be expressed as a linear combination of chip-firing moves).

The group {\rm Jac}(G) = {\rm Pic}^0(G) acts on {\rm Pic}^{g-1}(G) by translation, and it admits a natural action on {\mathcal G}(G) as well.  To define this action, first note that every element of {\rm Pic}^0(G) can be written as a finite sum of elements of the form [\partial \vec{e}], where \partial \vec{e} = (w)-(v) for a directed edge \vec{e} = vw and [D] denotes the linear equivalence class of a divisor D.  So it suffices, by linearity, to define the action of such an element.  One first proves that for every directed edge \vec{e} and every equivalence class in {\mathcal G}(G), there is at least one orientation {\mathcal O} in this class for which \vec{e} is oriented compatibly.  We then define \partial \vec{e} \cdot [{\mathcal O}] := [{\mathcal O}'], where {\mathcal O}' is obtained from {\mathcal O} by reversing \vec{e}.  It can be shown that this gives a well-defined action for which the map {\mathcal G}(G) \to {\rm Pic}^{g-1}(G) defined above is equivariant.

A similar recipe gives a natural action of {\rm Jac}(M) on {\mathcal G}(M) for any regular matroid M, modulo the fact that we have not yet defined the group {\rm Jac}(M).  The simplest way to define this group, for our purposes, is as follows.  Let M be a regular matroid on the ground set E, and let C_1(M,{\mathbb Z}) be the group of integer 1-chains on E (in the sense of algebraic topology).  Then {\rm Jac}(M) is the quotient of C_1(M,{\mathbb Z}) by the subgroup generated by all oriented circuits and oriented cocircuits (thought of as 1-chains).

The group {\rm Jac}(M) acts on {\mathcal G}(M) by the rule [\vec{e}] \cdot [{\mathcal O}] := [{\mathcal O}'], where {\mathcal O}' means the same thing as above.  (Here [\vec{e}] denotes the class of \vec{e} in {\rm Jac}(M), and the action is extended by linearity to all elements of {\rm Jac}(M).)

Theorem (BBY): If M is a regular matroid, the natural action of {\rm Jac}(M) on {\mathcal G}(M) is simply transitive.

The key point here is that although {\rm Pic}^{d}(M) does not make sense in general for regular matroids (since there are no vertices and hence no divisors), we can still make sense of the {\rm Jac}(M)-set “{\rm Pic}^{g-1}(M)” by defining it to be {\mathcal G}(M).

Bijections between spanning trees and circuit-cocircuit equivalence classes

Let us return, for simplicity, to the language of graphs.  Since there is a natural simply transitive action of {\rm Jac}(G) on {\mathcal G}(G), in order to give a simply transitive action of {\rm Jac}(G) on the set {\mathcal T}(G) of spanning trees of G, it suffices to give a bijection from {\mathcal T}(G) to {\mathcal G}(G).  We will define a whole family of such bijections which depend on the choice of certain auxiliary data.  For plane graphs, these auxiliary data will be (almost) canonically defined.

A circuit signature \sigma assigns to each unoriented circuit \underline{C} of G one of the two oriented circuits with support \underline{C}.   A circuit signature is called acyclic if there is no nonnegative integral linear dependence \sum a_{\underline{C}} \sigma(\underline{C})=0, and induced if there is a vector w \in {\mathbb R}^E such that w \cdot \sigma(\underline{C})>0 for all unoriented circuits \underline{C}.  The Farkas Lemma in convex geometry / linear programming shows:

Lemma: A circuit signature is acyclic iff it is induced.

We define (acyclic, resp. induced) cocircuit signatures similarly.

Acyclic circuit (resp. cocircuit) signatures always exist.  For example, fix a total order and reference orientation on the set of edges of G, and orient each circuit (resp. cocircuit) compatibly with the reference orientation of its smallest edge.

Given T \in {\mathcal T}(G) and e \not\in T, let C(T,e) be the associated fundamental circuit, i.e., the unique circuit contained in T \cup \{ e \}.  Similarly, given e \in T, let C^*(T,e) be the associated fundamental cocircuit, i.e., the unique cocircuit contained in the complement of T \backslash \{ e \}.

Now, given a pair (\sigma,\sigma^*) consisting of a circuit and cocircuit signature, respectively, we can define a map from {\mathcal T}(G) to {\mathcal G}(G) as follows.  Let T \in {\mathcal T}(G).  For e \not\in T, orient e according to its orientation in \sigma(C(T,e)).  For e \in T, orient e according to its orientation in \sigma^*(C^*(T,e)).  Call the resulting orientation {\mathcal O}_T, and let \beta(T) \in {\mathcal G}(G) be the equivalence class of {\mathcal O}_T.

The main theorem of [BBY] is:

Theorem (BBY): If \sigma and \sigma^* are acyclic, then \beta is a bijection.

This theorem holds more generally when we replace G by any regular matroid M if we define the map \beta from bases of M to {\mathcal G}(M) exactly as above.

When G is a plane graph, we can take \sigma to be the function which chooses the counterclockwise orientation for each circuit.  This signature is easily checked to be acyclic.  If we fix a planar embedding of dual graph \hat{G} (dual to the embedding of G), we can use the same rule (but with clockwise instead of counterclockwise orientations) to give an acyclic circuit signature of \hat{G}, and this naturally induces an acyclic cocircuit signature \sigma^* of G.  It turns out that the corresponding map \beta affords a simply transitive action of {\rm Jac}(G) on {\mathcal T}(G) which is isomorphic to the Bernardi action described in my earlier post.

Main idea of the proof of the main theorem

The proof in [BBY] that each of the maps \beta = \beta_{\sigma,\sigma^*} is a bijection is based on polyhedral geometry.   The signature \sigma is used to define a polyhedral complex whose maximal faces correspond to spanning trees of G and whose minimal faces (vertices) correspond to certain distinguished orientations of G.  The signature \sigma^* is used to define a shifting map which associates a vertex to each maximal face, and hence a distinguished orientation to each spanning tree.  Passing to the associated equivalence class yields a geometrically defined bijection between {\mathcal T}(G) and {\mathcal G}(G) which we prove coincides with the map \beta.  See Section 1.3 of [BBY] for a more detailed overview.

We do not know a “direct” combinatorial proof of the main theorem.

Conjectural extension to oriented matroids

Define an orientation {\mathcal O} of an oriented matroid M to be \sigma-compatible with respect to a circuit signature \sigma if every oriented circuit C compatible with {\mathcal O} is in the image of \sigma.  (These are the “distinguished” orientations referred to in the above proof sketch.)

Lemma (BBY): If M is a regular matroid, then every circuit-cocircuit equivalence class of orientations contains a unique orientation which is both \sigma-compatible and \sigma^*-compatible.  (We call such orientations (\sigma,\sigma^*)-compatible.)

Without assuming regularity, we can still prove:

Theorem: Let M be an oriented matroid and \sigma,\sigma^* be circuit and cocircuit signatures, respectively, coming from an edge-ordering and reference orientation.  Then:

(1) The number of (\sigma,\sigma^*)-compatible orientations of M is equal to the number of bases of M.

(2) For every basis B of M, the orientation {\mathcal O}_B (defined as in the case of graphs) is (\sigma,\sigma^*)-compatible.

Letting \beta' = \beta'_{\sigma,\sigma^*} denote the map B \mapsto {\mathcal O}_B from bases of M to (\sigma,\sigma^*)-compatible orientations of M, we see that the source and target of \beta' have the same cardinality.  However, we do not currently know (unless M is regular or, more generally, representable over {\mathbb R}) whether \beta' is injective (or equivalently, surjective).  But computations with some non-representable oriented matroids by my undergraduate student Libby Taylor strongly suggest:

Conjecture: For any oriented matroid M and signatures \sigma,\sigma^* coming from an edge-ordering and reference orientation, the map \beta' is a bijection.

There may be a more general definition of “acyclic signature” for which the conjecture holds, but so far we have only experimented with this particular situation.

Concluding remarks

(1) The polyhedral complex alluded to above is in fact a zonotopal tiling.  Lattice points of the ambient zonotope Z correspond to \sigma-compatible orientations of M, and more generally every point of Z corresponds in a natural way to a unique \sigma-compatible continuous orientation of M.  See Section 1.4 of [BBY] for further details.

(2) The connection between \sigma-compatible orientations and lattice points of Z provides a new proof of Stanley’s formula E_Z(q) = q^r T_M(1 + 1/q, 1) relating the Tutte polynomial T_M(x,y) of the rank r regular matroid M to the Ehrhart polynomial E_Z(q) of the zonotope associated to M.  See Section 5 of [BBY] for further details.

(3) Since the bijections \beta_{\sigma,\sigma^*} are computable, and it is easy to randomly sample elements of {\rm Jac}(M), our results provide an algorithm for randomly sampling bases of a regular matroid.  The resulting algorithm seems to be new even for the case of graphs.

(4) For a discussion of the relationship between the circuit-cocircuit reversal system and the Riemann-Roch theorem for graphs, see this post.








Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s