Séminaire Lotharingien de Combinatoire, 91B.18 (2024), 12 pp.
Changxin Ding
A Framework Unifying Some Bijections for Graphs and Its Connection to Lawrence Polytopes
Abstract.
Let G be a connected graph. The Jacobian group (also known as the
Picard group or sandpile group) of G is a finite abelian group whose
cardinality equals the number of spanning trees of G. The Jacobian
group admits a canonical simply transitive action on the set
R(G) of cycle-cocycle reversal classes of orientations of
G. Hence one can construct combinatorial bijections between spanning
trees of G and R(G) to build connections between
spanning trees and the Jacobian group. The geometric bijections
(defined by Backman, Baker, and Yuen) and the Bernardi bijections are
two important examples. In this paper, we construct a new family of
such bijections that includes both. Our bijections depend on a pair of
atlases (different from the ones in manifold theory) that abstract and
generalize certain common features of the two known bijections. The
definitions of these atlases are derived from triangulations and
dissections of the Lawrence polytopes associated to G. The acyclic
cycle signatures and cocycle signatures used to define the geometric
bijections correspond to regular triangulations. Our bijections can
extend to subgraph-orientation correspondences. Most of our results
hold for regular matroids. We present our work in the language of
fourientations, which are a generalization of orientations.
Received: November 15, 2023.
Accepted: February 15, 2024.
Final version: April 1, 2024.
The following versions are available: