ALGEBRAIC COMBINATORICS

no. 5
A family of matrix-tree multijections
McDonough, Alex1
1 Brown University Department of Mathematics 151 Thayer St. Providence RI 02912, USA
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: 10.5802/alco.181
Classification: 05B45, 52C40, 52C22, 05E45
Keywords: sandpile group, multijection, arithmetic matroid
McDonough, Alex 1

1 Brown University Department of Mathematics 151 Thayer St. Providence RI 02912, USA
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@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
SP  - 795
EP  - 822
VL  - 4
IS  - 5
PB  - MathOA foundation
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.181/
DO  - 10.5802/alco.181
LA  - en
ID  - ALCO_2021__4_5_795_0
ER  - 
%0 Journal Article
%A McDonough, Alex
%T A family of matrix-tree multijections
%J Algebraic Combinatorics
%D 2021
%P 795-822
%V 4
%N 5
%I MathOA foundation
%U https://alco.centre-mersenne.org/articles/10.5802/alco.181/
%R 10.5802/alco.181
%G en
%F ALCO_2021__4_5_795_0
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 | Zbl

[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 | DOI | MR | Zbl

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

[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

[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 | Zbl

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

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

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

[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 | DOI | MR

[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 | DOI | MR | Zbl

[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

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

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

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

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

[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 | DOI | MR | Zbl

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

[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 | DOI | MR

Cited by Sources: