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:
Accepted:
Published online:
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
Author's affiliations:
@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 = {https://alco.centre-mersenne.org/articles/10.5802/alco.100/} }
TY - JOUR TI - A colourful path to matrix-tree theorems JO - Algebraic Combinatorics PY - 2020 DA - 2020/// SP - 471 EP - 482 VL - 3 IS - 2 PB - MathOA foundation UR - https://alco.centre-mersenne.org/articles/10.5802/alco.100/ UR - https://doi.org/10.5802/alco.100 DO - 10.5802/alco.100 LA - en ID - ALCO_2020__3_2_471_0 ER -
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/articles/10.5802/alco.100/
[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, Paper no. Paper 4.35, 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), 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 (87b:05016) | Zbl: 0609.05008
Cited by Sources: