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