Geometric Bijections for Regular Matroids, Zonotopes, and Ehrhart Theory

Abstract

Let $M$ be a regular matroid. The Jacobian group $\mathrm{Jac}(M)$ of $M$ is a finite abelian group whose cardinality is equal to the number of bases of $M$. This group generalizes the definition of the Jacobian group (also known as the critical group or sandpile group) $\mathrm{Jac}(G)$ of a graph $G$ (in which case bases of the corresponding regular matroid are spanning trees of $G$). There are many explicit combinatorial bijections in the literature between the Jacobian group of a graph $\mathrm{Jac}(G)$ and spanning trees. However, most of the known bijections use vertices of $G$ in some essential way and are inherently "non-matroidal". In this paper, we construct a family of explicit and easy-to-describe bijections between the Jacobian group of a regular matroid $M$ and bases of $M$, many instances of which are new even in the case of graphs. We first describe our family of bijections in a purely combinatorial way in terms of orientations; more specifically, we prove that the Jacobian group of $M$ admits a canonical simply transitive action on the set $\mathcal{G}(M)$ of circuit-cocircuit reversal classes of $M$, and then define a family of combinatorial bijections ${\beta }_{\sigma ,{\sigma }^{\ast }}$ between $\mathcal{G}(M)$ and bases of $M$. (Here $\sigma$ (resp. ${\sigma }^{\ast }$) is an acyclic signature of the set of circuits (resp. cocircuits) of $M$.) We then give a geometric interpretation of each such map $\beta ={\beta }_{\sigma ,{\sigma }^{\ast }}$ in terms of zonotopal subdivisions which is used to verify that $\beta$ is indeed a bijection. Finally, we give a combinatorial interpretation of lattice points in the zonotope $Z$; by passing to dilations we obtain a new derivation of Stanley's formula linking the Ehrhart polynomial of $Z$ to the Tutte polynomial of $M$.

v2: 39 pages, 5 figures, include a partial extension to realizable oriented matroids (cf. Section 1.5); v3: improved exposition

References in corpus (2)

• Fourientation activities and the Tutte polynomial
• A Polyhedral Proof of the Matrix Tree Theorem

Cited by in corpus (7)

• Kirchhoff's theorem for Prym varieties
• A family of matrix-tree multijections
• Rotor-Routing Induces the Only Consistent Sandpile Torsor Structure on Plane Graphs
• A Consistent Sandpile Torsor Algorithm for Regular Matroids
• Semi-polytope decomposition of a Generalized permutohedron
• Fragmenting any Parallelepiped into a Signed Tiling
• Extension-lifting Bijections for Oriented Matroids