A family of matrix-tree multijections
Algebraic Combinatorics, Volume 4 (2021) no. 5, pp. 795-822.

For a natural class of r×n integer matrices, we construct a non-convex polytope which periodically tiles n . 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.

Received:
Revised:
Accepted:
Published online:
DOI: https://doi.org/10.5802/alco.181
Classification: 05B45,  52C40,  52C22,  05E45
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 = {https://alco.centre-mersenne.org/articles/10.5802/alco.181/}
}
TY  - JOUR
AU  - McDonough, Alex
TI  - A family of matrix-tree multijections
JO  - Algebraic Combinatorics
PY  - 2021
DA  - 2021///
SP  - 795
EP  - 822
VL  - 4
IS  - 5
PB  - MathOA foundation
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.181/
UR  - https://doi.org/10.5802/alco.181
DO  - 10.5802/alco.181
LA  - en
ID  - ALCO_2021__4_5_795_0
ER  - 
McDonough, Alex. A family of matrix-tree multijections. Algebraic Combinatorics, Volume 4 (2021) no. 5, pp. 795-822. doi : 10.5802/alco.181. https://alco.centre-mersenne.org/articles/10.5802/alco.181/

[1] Bacher, Roland; de la Harpe, Pierre; Nagnibeda, Tatiana 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 1478029 | Zbl 0891.05062

[2] Backman, Spencer; Baker, Matthew; Yuen, Chi Ho Geometric bijections for regular matroids, zonotopes, and Ehrhart theory, Forum Math. Sigma, Volume 7 (2019), Paper no. e45, 37 pages | Article | MR 4061968 | Zbl 1429.52017

[3] Bak, Per; Tang, Chao; Wiesenfeld, Kurt Self-organized criticality, Phys. Rev. A (3), Volume 38 (1988) no. 1, pp. 364-374 | Article | MR 949160 | Zbl 1230.37103

[4] Beck, Matthias; Robins, Sinai Computing the continuous discretely: Integer-point enumeration in polyhedra, Undergraduate Texts in Mathematics, Springer, New York, 2007, xviii+226 pages | MR 2271992

[5] Bernardi, Olivier Tutte polynomial, subgraphs, orientations and sandpile model: new connections via embeddings, Electron. J. Combin., Volume 15 (2008) no. 1, Paper no. R109, 53 pages | MR 2438581 | Zbl 1179.05048

[6] Biggs, Norman L. Chip-firing and the critical group of a graph, J. Algebraic Combin., Volume 9 (1999) no. 1, pp. 25-45 | Article | MR 1676732 | Zbl 0919.05027

[7] Biggs, Norman L.; Winkler, Peter Chip-firing and the chromatic polynomial, Volume 9, 1997 (CDAM Research Report Series, LSE-CDAM-97-03)

[8] Chaiken, Seth; Kleitman, Daniel J. Matrix tree theorems, J. Combinatorial Theory Ser. A, Volume 24 (1978) no. 3, pp. 377-381 | Article | MR 480115 | Zbl 0376.05032

[9] Duval, Art M.; Klivans, Caroline J.; Martin, Jeremy L. Simplicial matrix-tree theorems, Trans. Amer. Math. Soc., Volume 361 (2009) no. 11, pp. 6073-6114 | Article | MR 2529925 | Zbl 1207.05227

[10] Duval, Art M.; Klivans, Caroline J.; Martin, Jeremy L. Critical groups of simplicial complexes, Ann. Comb., Volume 17 (2013) no. 1, pp. 53-70 | Article | MR 3027573 | Zbl 1263.05124

[11] Duval, Art M.; Klivans, Caroline J.; Martin, Jeremy L. Cuts and flows of cell complexes, J. Algebraic Combin., Volume 41 (2015) no. 4, pp. 969-999 | Article | MR 3342708 | Zbl 1333.05323

[12] Gioan, Emeric Enumerating degree sequences in digraphs and a cycle-cocycle reversing system, European J. Combin., Volume 28 (2007) no. 4, pp. 1351-1366 | Article | MR 2305596 | Zbl 1114.05024

[13] Gioan, Emeric Circuit-cocircuit reversing systems in regular matroids, Ann. Comb., Volume 12 (2008) no. 2, pp. 171-182 | Article | MR 2428903 | Zbl 1228.05111

[14] Godsil, Chris; Royle, Gordon Algebraic Graph Theory, Graduate Texts in Mathematics, 207, Springer-Verlag New York, 2001

[15] Holroyd, Alexander E.; Levine, Lionel; Mészáros, Karola; Peres, Yuval; Propp, James; Wilson, David B. 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 | Article | MR 2477390

[16] Jekel, David; Levy, Avi; Dana, Will; Stromme, Austin; Litterell, Collin 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 | Article | MR 3799052 | Zbl 1387.05153

[17] Klivans, Caroline J. The mathematics of chip-firing, Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, FL, 2019, xii+295 pages | MR 3889995

[18] Lorenzini, Dino J. Groups of components of Néron models of Jacobians, Compositio Math., Volume 73 (1990) no. 2, pp. 145-160 | MR 1046735 | Zbl 0737.14008

[19] Majumdar, Satya N.; Dhar, Deepak Equivalence between the Abelian sandpile model and the q0 limit of the Potts model, Physica A: Statistical Mechanics and its Applications, Volume 185 (1992) no. 1-4, pp. 129-145 | Article

[20] McDonough, Alex Higher-Dimensional Sandpile Groups and Matrix-Tree Multijections (2021) (Ph. D. Thesis)

[21] Merino, Criel Matroids, the Tutte polynomial and the chip firing game. (1999) (Ph. D. Thesis)

[22] Oxley, James G. Matroid theory, Oxford Graduate Texts in Mathematics, 3, Oxford University Press, USA, 2006

[23] Pagaria, Roberto Orientable arithmetic matroids, Discrete Math., Volume 343 (2020) no. 6, Paper no. 111872, 8 pages | Article | MR 4067961 | Zbl 1437.05041

[24] Yuen, Chi Ho Geometric Bijections of Graphs and Regular Matroids (2018) (Ph. D. Thesis)

[25] Zaslavsky, Thomas 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 | Article | MR 357135

Cited by Sources: