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.

[Note added April 2019: this conjecture has now been proved! See this paper by Backman, Santos, and Yuen.]

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:

WordPress.com Logo

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

Google photo

You are commenting using your Google 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 )

Connecting to %s