ALGEBRAIC COMBINATORICS

no. 2
A colourful path to matrix-tree theorems
Algebraic Combinatorics, Volume 3 (2020) no. 2, pp. 471-482.

In this short note, we revisit Zeilberger’s proof of the classical matrix-tree theorem and give a unified concise proof of variants of this theorem, some known and some new.

Received: 2019-03-14
Revised: 2019-09-11
Accepted: 2019-10-16
Published online: 2020-04-01
DOI: https://doi.org/10.5802/alco.100
Classification: 05C30,  05C22,  15A15
Keywords: matrix-tree theorem, graph, forests, cycles, Laplacian, determinant, Q-determinant, holonomy, ordered products, simplicial complexes, pseudoforests, circular and bicircular matroids 
@article{ALCO_2020__3_2_471_0,
     author = {Kassel, Adrien and L\'evy, Thierry},
     title = {A colourful path to matrix-tree theorems},
     journal = {Algebraic Combinatorics},
     publisher = {MathOA foundation},
     volume = {3},
     number = {2},
     year = {2020},
     pages = {471-482},
     doi = {10.5802/alco.100},
     language = {en},
     url={alco.centre-mersenne.org/item/ALCO_2020__3_2_471_0/}
}
Kassel, Adrien; Lévy, Thierry. A colourful path to matrix-tree theorems. Algebraic Combinatorics, Volume 3 (2020) no. 2, pp. 471-482. doi : 10.5802/alco.100. https://alco.centre-mersenne.org/item/ALCO_2020__3_2_471_0/

[1] Adin, Ron M. Counting colorful multi-dimensional trees, Combinatorica, Volume 12 (1992) no. 3, pp. 247-260 | Article | MR 1195888 | Zbl 0773.05038

[2] Bernardi, Olivier; Klivans, Caroline J. Directed rooted forests in higher dimension, Electron. J. Combin., Volume 23 (2016) no. 4, Paper 4.35, 20 pages | Article | MR 3604793 | Zbl 1353.05131

[3] Chaiken, Seth A combinatorial proof of the all minors matrix tree theorem, SIAM J. Algebraic Discrete Methods, Volume 3 (1982) no. 3, pp. 319-329 | Article | MR 666857 | Zbl 0495.05018

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

[5] Duval, Art M.; Klivans, Caroline J.; Martin, Jeremy L. Simplicial and cellular trees, Recent trends in combinatorics (IMA Vol. Math. Appl.) Volume 159, Springer, [Cham], 2016, pp. 713-752 | Article | MR 3526429 | Zbl 1354.05151

[6] Forman, Robin Determinants of Laplacians on graphs, Topology, Volume 32 (1993) no. 1, pp. 35-46 | Article | MR 1204404 | Zbl 0780.05041

[7] Kalai, Gil Enumeration of ℚ-acyclic simplicial complexes, Isr. J. Math., Volume 45 (1983) no. 4, pp. 337-351 | Article | MR 720308

[8] Kassel, Adrien Learning about critical phenomena from scribbles and sandpiles, Modélisation Aléatoire et Statistique — Journées MAS 2014 (ESAIM, Proc. Surv.) Volume 51 (2015), pp. 60-73 | Article | MR 3440791 | Zbl 1336.60190

[9] Kassel, Adrien; Lévy, Thierry Covariant Symanzik identities (2016) (https://arxiv.org/abs/1607.05201)

[10] Kassel, Adrien; Lévy, Thierry Quantum spanning forests (2019) (In preparation)

[11] Kenyon, Richard Spanning forests and the vector bundle Laplacian, Ann. Probab., Volume 39 (2011) no. 5, pp. 1983-2017 | Article | MR 2884879 | Zbl 1252.82029

[12] Kirchhoff, G. Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird, Ann. Phys. und Chem., Volume 72 (1847) no. 12, pp. 497-508 | Article

[13] Lyons, Russell Random complexes and ℓ 2 -Betti numbers, J. Topol. Anal., Volume 1 (2009) no. 2, pp. 153-175 | Article | MR 2541759

[14] Mehta, Madan Lal Random matrices, Pure and Applied Mathematics (Amsterdam), Volume 142, Elsevier/Academic Press, Amsterdam, 2004, xviii+688 pages | MR 2129906 | Zbl 1107.15019

[15] Moore, Eliakim H. On the determinant of an Hermitian matrix of quaternionic elements, Bull. Amer. Math. Soc., Volume 28 (1922) no. 4, p. 161-162 (Conference abstract available at https://doi.org/10.1090%2FS0002-9904-1922-03536-7) | Zbl 48.0128.07

[16] Zaslavsky, Thomas Signed graphs, Discrete Appl. Math., Volume 4 (1982) no. 1, pp. 47-74 | Article | MR 676405 | Zbl 0476.05080

[17] Zeilberger, Doron A combinatorial approach to matrix algebra, Discrete Math., Volume 56 (1985), pp. 61-72 | Article | MR 808086 | Zbl 0609.05008