The Jacobian of a finite graph is a finite abelian group whose cardinality is equal to the number of spanning trees of . In this earlier post, I discussed a family of combinatorial bijections between elements of and the set of spanning trees of . I also discussed the fact that for plane graphs, these Bernardi bijections come from a natural simply transitive action of on (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 on 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 as an intermediate object rather than . The latter is canonically isomorphic (as a -torsor) to the set of break divisors on ; 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 of a connected graph , introduced in 2007 by Emeric Gioan. We review the definition (see also this previous post). An oriented circuit in is a directed simple closed cycle in . An oriented cocircuit in is the set of all directed edges connecting to , where is a partition of the vertices of into disjoint connected subsets and . An orientation of is a choice, for each (undirected) edge of , of one of the two directed edges corresponding to it. A set of directed edges of is compatible with an orientation if every edge in the support of is oriented the same way in and . A circuit reversal consists of replacing an orientation by the orientation in which all elements of some -compatible oriented circuit are reversed; we define cocircuit reversals similarly. Two orientations are circuit-cocircuit equivalent if they differ by a finite sequence of circuit and cocircuit reversals.
Definition: The circuit-cocircuit reversal system is the set of equivalence classes of orientations with respect to the circuit-cocircuit equivalence relation.
The same definitions allow us to define for any oriented matroid . Using a deletion-contraction argument, Gioan proved:
Theorem (Gioan): The cardinality of is equal to the number of spanning trees of . More generally, for any regular matroid the cardinality of is equal to the number of bases of .
My student Chi Ho Yuen proves a converse of sorts in this paper:
Theorem (Yuen): For any oriented matroid , the cardinality of is less than or equal to the number of bases of , with equality if and only if is regular.
Action of the Jacobian group on
As first observed by Backman, there is a natural bijection between and which extends to a natural isomorphism of -sets. The bijection from to takes the equivalence class of an orientation to the linear equivalence class of the divisor , as defined in this post. To prove that this map is a bijection, one uses the preliminary observations that two orientations are circuit-equivalent (i.e., they differ by a sequence of circuit reversals) iff , and that if 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 acts on by translation, and it admits a natural action on as well. To define this action, first note that every element of can be written as a finite sum of elements of the form , where for a directed edge and denotes the linear equivalence class of a divisor . So it suffices, by linearity, to define the action of such an element. One first proves that for every directed edge and every equivalence class in , there is at least one orientation in this class for which is oriented compatibly. We then define , where is obtained from by reversing . It can be shown that this gives a well-defined action for which the map defined above is equivariant.
A similar recipe gives a natural action of on for any regular matroid , modulo the fact that we have not yet defined the group . The simplest way to define this group, for our purposes, is as follows. Let be a regular matroid on the ground set , and let be the group of integer 1-chains on (in the sense of algebraic topology). Then is the quotient of by the subgroup generated by all oriented circuits and oriented cocircuits (thought of as 1-chains).
The group acts on by the rule , where means the same thing as above. (Here denotes the class of in , and the action is extended by linearity to all elements of .)
Theorem (BBY): If is a regular matroid, the natural action of on is simply transitive.
The key point here is that although 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 -set “” by defining it to be .
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 on , in order to give a simply transitive action of on the set of spanning trees of , it suffices to give a bijection from to . 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 assigns to each unoriented circuit of one of the two oriented circuits with support . A circuit signature is called acyclic if there is no nonnegative integral linear dependence , and induced if there is a vector such that for all unoriented circuits . 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 , and orient each circuit (resp. cocircuit) compatibly with the reference orientation of its smallest edge.
Given and , let be the associated fundamental circuit, i.e., the unique circuit contained in . Similarly, given , let be the associated fundamental cocircuit, i.e., the unique cocircuit contained in the complement of .
Now, given a pair consisting of a circuit and cocircuit signature, respectively, we can define a map from to as follows. Let . For , orient according to its orientation in . For , orient according to its orientation in . Call the resulting orientation , and let be the equivalence class of .
The main theorem of [BBY] is:
Theorem (BBY): If and are acyclic, then is a bijection.
This theorem holds more generally when we replace by any regular matroid if we define the map from bases of to exactly as above.
When is a plane graph, we can take 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 (dual to the embedding of ), we can use the same rule (but with clockwise instead of counterclockwise orientations) to give an acyclic circuit signature of , and this naturally induces an acyclic cocircuit signature of . It turns out that the corresponding map affords a simply transitive action of on 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 is a bijection is based on polyhedral geometry. The signature is used to define a polyhedral complex whose maximal faces correspond to spanning trees of and whose minimal faces (vertices) correspond to certain distinguished orientations of . The signature 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 and which we prove coincides with the map . 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 of an oriented matroid to be -compatible with respect to a circuit signature if every oriented circuit compatible with is in the image of . (These are the “distinguished” orientations referred to in the above proof sketch.)
Lemma (BBY): If is a regular matroid, then every circuit-cocircuit equivalence class of orientations contains a unique orientation which is both -compatible and -compatible. (We call such orientations -compatible.)
Without assuming regularity, we can still prove:
Theorem: Let be an oriented matroid and be circuit and cocircuit signatures, respectively, coming from an edge-ordering and reference orientation. Then:
(1) The number of -compatible orientations of is equal to the number of bases of .
(2) For every basis of , the orientation (defined as in the case of graphs) is -compatible.
Letting denote the map from bases of to -compatible orientations of , we see that the source and target of have the same cardinality. However, we do not currently know (unless is regular or, more generally, representable over ) whether 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 and signatures coming from an edge-ordering and reference orientation, the map is a bijection.
[Note added April 2019: this conjecture has now been proved! See this paper by Backman, Santos, and Yuen.]
(1) The polyhedral complex alluded to above is in fact a zonotopal tiling. Lattice points of the ambient zonotope correspond to -compatible orientations of , and more generally every point of corresponds in a natural way to a unique -compatible continuous orientation of . See Section 1.4 of [BBY] for further details.
(2) The connection between -compatible orientations and lattice points of provides a new proof of Stanley’s formula relating the Tutte polynomial of the rank regular matroid to the Ehrhart polynomial of the zonotope associated to . See Section 5 of [BBY] for further details.
(3) Since the bijections are computable, and it is easy to randomly sample elements of , 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.