# zbMATH — the first resource for mathematics

Geometric bijections for regular matroids, zonotopes, and Ehrhart theory. (English) Zbl 1429.52017
Summary: Let $$M$$ be a regular matroid. The Jacobian group $$\operatorname{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) $$\operatorname{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 $$\operatorname{Jac}(G)$$ and spanning trees. However, most of the known bijections use vertices of $$G$$ in some essential way and are inherently ‘nonmatroidal’. 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$$ (respectively $$\sigma^\ast)$$ is an acyclic signature of the set of circuits (respectively 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$$.

##### MSC:
 52B40 Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) 05C31 Graph polynomials 05E18 Group actions on combinatorial structures 52B20 Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) 05B35 Combinatorial aspects of matroids and geometric lattices
Full Text:
##### References:
  An, Y., Baker, M., Kuperberg, G. and Shokrieh, F., ‘Canonical representatives for divisor classes on tropical curves and the Matrix-Tree Theorem’, inForum of Mathematics, SigmaVol. 2 (Cambridge University Press, Cambridge, United Kingdom, 2014), e24. · Zbl 1306.05013  Bacher, R., La Harpe, P. De and Nagnibeda, T., ‘The lattice of integral flows and the lattice of integral cuts on a finite graph’, Bull. Soc. Math. France125(2) (1997), 167-198. · Zbl 0891.05062  Backman, S., ‘Riemann-Roch theory for graph orientations’, Adv. Math.309 (2017), 655-691. · Zbl 1355.05140  Backman, S., ‘Partial graph orientations and the Tutte polynomial’, Adv. Appl. Math.94 (2018), 103-119. · Zbl 1378.05093  Backman, S., Hopkins, S. and Traldi, L., ‘Fourientation activities and the Tutte polynomial’, European J. Combin.67 (2018), 40-60. · Zbl 1371.05133  Baker, M. and Faber, X., ‘Metrized graphs, Laplacian operators, and electrical networks’, inQuantum Graphs and their Applications, (American Mathematical Society, Providence, RI, 2006), 15-33. · Zbl 1114.94025  Baker, M. and Shokrieh, F., ‘Chip-firing games, potential theory on graphs, and spanning trees’, J. Combin. Theory Ser. A120(1) (2013), 164-182. · Zbl 1408.05089  Baker, M. and Wang, Y., ‘The Bernardi process and torsor structures on spanning trees’, Int. Math. Res. Not. IMRN16 (2018), 5120-5147. · Zbl 1404.05027  Bernardi, O., ‘Tutte polynomial, subgraphs, orientations and sandpile model: new connections via embeddings’, Electron. J. Combin.15(1) (2008). · Zbl 1179.05048  Björner, A., Las Vergnas, M., Sturmfels, B., White, N. and Ziegler, G. M., Oriented Matroids, (Cambridge University Press, Cambridge, 1999).  Bohne, J., ‘Eine kombinatorische Analyse zonotopaler Raumaufteilungen’, PhD Thesis, Universität Bielefeld, 1992. · Zbl 0836.52008  Chan, M., Church, T. and Grochow, J. A., ‘Rotor-routing and spanning trees on planar graphs’, Int. Math. Res. Not. IMRN11 (2015), 3225-3244. · Zbl 1314.05045  Chan, M., Glass, D., Macauley, M., Perkinson, D., Werner, C. and Yang, Q., ‘Sandpiles, spanning trees, and plane duality’, SIAM J. Discrete Math.29(1) (2015), 461-471. · Zbl 1327.05342  Cori, R. and Le Borgne, Y., ‘The sand-pile model and Tutte polynomials’, Adv. Appl. Math.30(1-2) (2003), 44-52. Formal Power Series and Algebraic Combinatorics (Scottsdale, AZ, 2001). · Zbl 1030.05058  D’Adderio, M. and Moci, L., ‘Ehrhart polynomial and arithmetic Tutte polynomial’, European J. Combin.33(7) (2012), 1479-1483. · Zbl 1245.05068  Dall, A. and Pfeifle, J., ‘A polyhedral proof of the Matrix Tree Theorem’, Preprint, 2014,arXiv:1404.3876.  Dress, A., Oriented matroids and Penrose-type tilings, August 1989. Lecture at the ‘Symposium on Combinatorics and Geometry’, organized by A. Björner, KTH Stockholm.  Dyer, M. and Frieze, A., ‘Random walks, totally unimodular matrices, and a randomised dual simplex algorithm’, Math. Program.64(1, Ser. A) (1994), 1-16. · Zbl 0820.90066  Ehrhart, E., ‘Sur les polyèdres homothétiques bordés à n dimensions’, C. R. Acad. Sci.254 (1962). · Zbl 0100.27602  Gioan, E., ‘Correspondance naturelle entre bases et réorientations des matroïes orientés, PhD Thesis, University of Bordeaux 1, 2002.  Gioan, E., ‘Enumerating degree sequences in digraphs and a cycle–cocycle reversing system’, European J. Combin.28(4) (2007), 1351-1366. · Zbl 1114.05024  Gioan, E., ‘Circuit–cocircuit reversing systems in regular matroids’, Ann. Combin.12(2) (2008), 171-182. · Zbl 1228.05111  Gioan, E. and Las Vergnas, M., ‘Activity preserving bijections between spanning trees and orientations in graphs’, Discrete Math.298(1) (2005), 169-188. · Zbl 1070.05026  Godsil, C. and Royle, G. F., Algebraic Graph Theory, Vol. 207, (Springer, New York, 2013). · Zbl 0968.05002  Hopkins, S. and Perkinson, D., ‘Bigraphical arrangements’, Trans. Amer. Math. Soc.368(1) (2016), 709-725.  Lipton, R., ‘A new approach to random spanning trees’, 2009. Available at https://rjlipton.wordpress.com/2009/07/15/a-new-approach-to-random-spanning-trees/.  Maurer, S., ‘Matrix generalizations of some theorems on trees, cycles and cocycles in graphs’, SIAM J. Appl. Math.30(1) (1976), 143-148. · Zbl 0364.05021  Merino, C., ‘Matroids, the Tutte polynomial and the chip firing game’, PhD Thesis, University of Oxford, 1999.  Oxley, J., Matroid Theory, 2nd edn, (Oxford University Press, Oxford, 2011).  Perkinson, D., Yang, Q. and Yu, K., ‘G-parking functions and tree inversions’, Combinatorica37(2) (2017), 269-282. · Zbl 1399.05006  Schrijver, A., Theory of Linear and Integer Programming, (Wiley, New York, 1998). · Zbl 0970.90052  Shephard, G. C., ‘Combinatorial properties of associated zonotopes’, Canad. J. Math.26 (1974), 302-321. · Zbl 0287.52005  Shokrieh, F., ‘Matroids and their Jacobians’, in preparation. · Zbl 1231.05173  Stanley, R. P., ‘A zonotope associated with graphical degree sequences’, inApplied Geometry and Discrete Mathematics, (American Mathematical Society, Providence, RI, 1991), 555-570. · Zbl 0737.05057  Su, Y. and Wagner, D. G., ‘The lattice of integer flows of a regular matroid’, J. Combin. Theory Ser. B100(6) (2010), 691-703. · Zbl 1231.05064  Welsh, D., ‘The Tutte polynomial’, Random Structures Algorithms15(3-4) (1999), 210-228. Statistical Physics Methods in Discrete Probability, Combinatorics, and Theoretical Computer Science (Princeton, NJ, 1997).  Welsh, D. and Gale, A., ‘The complexity of counting problems’, inAspects of Complexity (Kaikoura, 2000), (de Gruyter, Berlin, 2001), 115-153. · Zbl 0988.68086  Yuen, C. H., ‘Geometric bijections between spanning trees and break divisors’, J. Combin. Theory Ser. A152 (2017), 159-189. · Zbl 1369.05035  Ziegler, G. M., Lectures on Polytopes, (Springer, New York, 1995). · Zbl 0823.52002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.