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.
Revised: 2019-09-10
Accepted: 2019-10-15
Published online: 2020-04-01
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}, pages = {471--482}, publisher = {MathOA foundation}, volume = {3}, number = {2}, year = {2020}, 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] Counting colorful multi-dimensional trees, Combinatorica, Volume 12 (1992) no. 3, pp. 247-260 | Article | MR 1195888 | Zbl 0773.05038
[2] Directed rooted forests in higher dimension, Electron. J. Combin., Volume 23 (2016) no. 4, 20 pages | Article | MR 3604793 | Zbl 1353.05131
[3] 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] Simplicial matrix-tree theorems, Trans. Am. Math. Soc., Volume 361 (2009) no. 11, pp. 6073-6114 | Article | MR 2529925 | Zbl 1207.05227
[5] 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] Determinants of Laplacians on graphs, Topology, Volume 32 (1993) no. 1, pp. 35-46 | Article | MR 1204404 | Zbl 0780.05041
[7] Enumeration of -acyclic simplicial complexes, Isr. J. Math., Volume 45 (1983) no. 4, pp. 337-351 | Article | MR 720308 | Zbl 0535.57011
[8] 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] Covariant Symanzik identities (2016) (https://arxiv.org/abs/1607.05201)
[10] Quantum spanning forests (2019) (In preparation)
[11] Spanning forests and the vector bundle Laplacian, Ann. Probab., Volume 39 (2011) no. 5, pp. 1983-2017 | Article | MR 2884879 | Zbl 1252.82029
[12] Ü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] Random complexes and -Betti numbers, J. Topol. Anal., Volume 1 (2009) no. 2, pp. 153-175 | Article | MR 2541759 | Zbl 1369.05107
[14] Random matrices, Pure and Applied Mathematics (Amsterdam), Volume 142, Elsevier/Academic Press, Amsterdam, 2004, xviii+688 pages | MR 2129906 | Zbl 1107.15019
[15] 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] Signed graphs, Discrete Appl. Math., Volume 4 (1982) no. 1, pp. 47-74 | Article | MR 676405 | Zbl 0476.05080
[17] A combinatorial approach to matrix algebra, Discrete Math., Volume 56 (1985), pp. 61-72 | Article | MR 808086 | Zbl 0609.05008