×

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
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] 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
[2] 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
[3] Backman, S., ‘Riemann-Roch theory for graph orientations’, Adv. Math.309 (2017), 655-691. · Zbl 1355.05140
[4] Backman, S., ‘Partial graph orientations and the Tutte polynomial’, Adv. Appl. Math.94 (2018), 103-119. · Zbl 1378.05093
[5] Backman, S., Hopkins, S. and Traldi, L., ‘Fourientation activities and the Tutte polynomial’, European J. Combin.67 (2018), 40-60. · Zbl 1371.05133
[6] 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
[7] 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
[8] 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
[9] Bernardi, O., ‘Tutte polynomial, subgraphs, orientations and sandpile model: new connections via embeddings’, Electron. J. Combin.15(1) (2008). · Zbl 1179.05048
[10] Björner, A., Las Vergnas, M., Sturmfels, B., White, N. and Ziegler, G. M., Oriented Matroids, (Cambridge University Press, Cambridge, 1999).
[11] Bohne, J., ‘Eine kombinatorische Analyse zonotopaler Raumaufteilungen’, PhD Thesis, Universität Bielefeld, 1992. · Zbl 0836.52008
[12] 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
[13] 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
[14] 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
[15] D’Adderio, M. and Moci, L., ‘Ehrhart polynomial and arithmetic Tutte polynomial’, European J. Combin.33(7) (2012), 1479-1483. · Zbl 1245.05068
[16] Dall, A. and Pfeifle, J., ‘A polyhedral proof of the Matrix Tree Theorem’, Preprint, 2014,arXiv:1404.3876.
[17] 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.
[18] 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
[19] Ehrhart, E., ‘Sur les polyèdres homothétiques bordés à n dimensions’, C. R. Acad. Sci.254 (1962). · Zbl 0100.27602
[20] Gioan, E., ‘Correspondance naturelle entre bases et réorientations des matroïes orientés, PhD Thesis, University of Bordeaux 1, 2002.
[21] Gioan, E., ‘Enumerating degree sequences in digraphs and a cycle–cocycle reversing system’, European J. Combin.28(4) (2007), 1351-1366. · Zbl 1114.05024
[22] Gioan, E., ‘Circuit–cocircuit reversing systems in regular matroids’, Ann. Combin.12(2) (2008), 171-182. · Zbl 1228.05111
[23] 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
[24] Godsil, C. and Royle, G. F., Algebraic Graph Theory, Vol. 207, (Springer, New York, 2013). · Zbl 0968.05002
[25] Hopkins, S. and Perkinson, D., ‘Bigraphical arrangements’, Trans. Amer. Math. Soc.368(1) (2016), 709-725.
[26] 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/.
[27] 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
[28] Merino, C., ‘Matroids, the Tutte polynomial and the chip firing game’, PhD Thesis, University of Oxford, 1999.
[29] Oxley, J., Matroid Theory, 2nd edn, (Oxford University Press, Oxford, 2011).
[30] Perkinson, D., Yang, Q. and Yu, K., ‘G-parking functions and tree inversions’, Combinatorica37(2) (2017), 269-282. · Zbl 1399.05006
[31] Schrijver, A., Theory of Linear and Integer Programming, (Wiley, New York, 1998). · Zbl 0970.90052
[32] Shephard, G. C., ‘Combinatorial properties of associated zonotopes’, Canad. J. Math.26 (1974), 302-321. · Zbl 0287.52005
[33] Shokrieh, F., ‘Matroids and their Jacobians’, in preparation. · Zbl 1231.05173
[34] 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
[35] 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
[36] 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).
[37] Welsh, D. and Gale, A., ‘The complexity of counting problems’, inAspects of Complexity (Kaikoura, 2000), (de Gruyter, Berlin, 2001), 115-153. · Zbl 0988.68086
[38] Yuen, C. H., ‘Geometric bijections between spanning trees and break divisors’, J. Combin. Theory Ser. A152 (2017), 159-189. · Zbl 1369.05035
[39] 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.