Séminaire Lotharingien de Combinatoire, 80B.94 (2018), 11 pp.

Spencer Backman, Matthew Baker, and Chi Ho Yuen

Geometric Bijections for Regular Matroids, Zonotopes, and Ehrhart Theory

Abstract. Let M be a regular matroid. The Jacobian group Jac(M) of M is a finite abelian group whose cardinality is equal to the number of {\em bases} of M. This group generalizes the definition of the Jacobian group (also known as the critical group or sandpile group) 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 Jac(G) and spanning trees. However, most of the known bijections use {\em vertices} of G in some essential way and are inherently "non-matroidal". In this work, 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 G(M) of circuit-cocircuit reversal classes of M, and then define a family of combinatorial bijections βσ,σ* between G(M) and bases of M. (Here σ (resp. σ*) is an acyclic signature of the set of circuits (resp. cocircuits) of M.) We then give a geometric interpretation of each such map β = βσ,σ* in terms of zonotopal subdivisions which is used to verify that β 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.


Received: November 14, 2017. Accepted: February 17, 2018. Final version: April 1, 2018.

The following versions are available: