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.

Matt Baker's Math Blog

Thoughts on number theory, graphs, dynamical systems, tropical geometry, pedagogy, puzzles, and the p-adics

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

Leave a Reply Cancel reply

Share this:

Like this:

Related

Leave a Reply Cancel reply