For a natural class of integer matrices, we construct a non-convex polytope which periodically tiles . From this tiling, we provide a family of geometrically meaningful maps from a generalized sandpile group to a set of generalized spanning trees which give multijective proofs for several higher-dimensional matrix-tree theorems. In particular, these multijections can be applied to graphs, regular matroids, cell complexes with a torsion-free spanning forest, and representable arithmetic matroids with a multiplicity one basis. This generalizes a bijection given by Backman, Baker, and Yuen and extends work by Duval, Klivans, and Martin.
Revised:
Accepted:
Published online:
Keywords: sandpile group, multijection, arithmetic matroid
@article{ALCO_2021__4_5_795_0, author = {McDonough, Alex}, title = {A family of matrix-tree multijections}, journal = {Algebraic Combinatorics}, pages = {795--822}, publisher = {MathOA foundation}, volume = {4}, number = {5}, year = {2021}, doi = {10.5802/alco.181}, language = {en}, url = {http://www.numdam.org/articles/10.5802/alco.181/} }
McDonough, Alex. A family of matrix-tree multijections. Algebraic Combinatorics, Volume 4 (2021) no. 5, pp. 795-822. doi : 10.5802/alco.181. http://www.numdam.org/articles/10.5802/alco.181/
[1] The lattice of integral flows and the lattice of integral cuts on a finite graph, Bull. Soc. Math. France, Volume 125 (1997) no. 2, pp. 167-198 | MR | Zbl
[2] Geometric bijections for regular matroids, zonotopes, and Ehrhart theory, Forum Math. Sigma, Volume 7 (2019), e45, 37 pages | DOI | MR | Zbl
[3] Self-organized criticality, Phys. Rev. A (3), Volume 38 (1988) no. 1, pp. 364-374 | DOI | MR | Zbl
[4] Computing the continuous discretely: Integer-point enumeration in polyhedra, Undergraduate Texts in Mathematics, Springer, New York, 2007, xviii+226 pages | MR
[5] Tutte polynomial, subgraphs, orientations and sandpile model: new connections via embeddings, Electron. J. Combin., Volume 15 (2008) no. 1, R109, 53 pages | MR | Zbl
[6] Chip-firing and the critical group of a graph, J. Algebraic Combin., Volume 9 (1999) no. 1, pp. 25-45 | DOI | MR | Zbl
[7] Chip-firing and the chromatic polynomial, Volume 9, 1997 (CDAM Research Report Series, LSE-CDAM-97-03)
[8] Matrix tree theorems, J. Combinatorial Theory Ser. A, Volume 24 (1978) no. 3, pp. 377-381 | DOI | MR | Zbl
[9] Simplicial matrix-tree theorems, Trans. Amer. Math. Soc., Volume 361 (2009) no. 11, pp. 6073-6114 | DOI | MR | Zbl
[10] Critical groups of simplicial complexes, Ann. Comb., Volume 17 (2013) no. 1, pp. 53-70 | DOI | MR | Zbl
[11] Cuts and flows of cell complexes, J. Algebraic Combin., Volume 41 (2015) no. 4, pp. 969-999 | DOI | MR | Zbl
[12] Enumerating degree sequences in digraphs and a cycle-cocycle reversing system, European J. Combin., Volume 28 (2007) no. 4, pp. 1351-1366 | DOI | MR | Zbl
[13] Circuit-cocircuit reversing systems in regular matroids, Ann. Comb., Volume 12 (2008) no. 2, pp. 171-182 | DOI | MR | Zbl
[14] Algebraic Graph Theory, Graduate Texts in Mathematics, 207, Springer-Verlag New York, 2001
[15] Chip-firing and rotor-routing on directed graphs, In and out of equilibrium. 2 (Progr. Probab.), Volume 60, Birkhäuser, Basel, 2008, pp. 331-364 | DOI | MR
[16] Algebraic properties of generalized graph Laplacians: resistor networks, critical groups, and homological algebra, SIAM J. Discrete Math., Volume 32 (2018) no. 2, pp. 1040-1110 | DOI | MR | Zbl
[17] The mathematics of chip-firing, Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, FL, 2019, xii+295 pages | MR
[18] Groups of components of Néron models of Jacobians, Compositio Math., Volume 73 (1990) no. 2, pp. 145-160 | MR | Zbl
[19] Equivalence between the Abelian sandpile model and the limit of the Potts model, Physica A: Statistical Mechanics and its Applications, Volume 185 (1992) no. 1-4, pp. 129-145 | DOI
[20] Higher-Dimensional Sandpile Groups and Matrix-Tree Multijections, Ph. D. Thesis, Brown University (2021)
[21] Matroids, the Tutte polynomial and the chip firing game., Ph. D. Thesis, University of Oxford (1999)
[22] Matroid theory, Oxford Graduate Texts in Mathematics, 3, Oxford University Press, USA, 2006
[23] Orientable arithmetic matroids, Discrete Math., Volume 343 (2020) no. 6, 111872, 8 pages | DOI | MR | Zbl
[24] Geometric Bijections of Graphs and Regular Matroids, Ph. D. Thesis, Georgia Tech (2018)
[25] Facing up to arrangements: face-count formulas for partitions of space by hyperplanes, Mem. Amer. Math. Soc., 1, Amer. Math. Soc., 1975 no. 154, vii+102 pages | DOI | MR
Cited by Sources: