ALGEBRAIC COMBINATORICS

no. 2
A colourful path to matrix-tree theorems
Kassel, Adrien1; Lévy, Thierry2
1 CNRS, UMPA École Normale Supérieure de Lyon 46, allée d’Italie F-69007 Lyon, France
2 LPSM Sorbonne Université 4, place Jussieu F-75005 Paris, France
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:
Revised:
Accepted:
Published online:
DOI: 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
Kassel, Adrien 1; Lévy, Thierry 2

1 CNRS, UMPA École Normale Supérieure de Lyon 46, allée d’Italie F-69007 Lyon, France
2 LPSM Sorbonne Université 4, place Jussieu F-75005 Paris, France
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@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
AU  - Kassel, Adrien
AU  - Lévy, Thierry
TI  - A colourful path to matrix-tree theorems
JO  - Algebraic Combinatorics
PY  - 2020
SP  - 471
EP  - 482
VL  - 3
IS  - 2
PB  - MathOA foundation
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.100/
DO  - 10.5802/alco.100
LA  - en
ID  - ALCO_2020__3_2_471_0
ER  - 
%0 Journal Article
%A Kassel, Adrien
%A Lévy, Thierry
%T A colourful path to matrix-tree theorems
%J Algebraic Combinatorics
%D 2020
%P 471-482
%V 3
%N 2
%I MathOA foundation
%U https://alco.centre-mersenne.org/articles/10.5802/alco.100/
%R 10.5802/alco.100
%G en
%F 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/articles/10.5802/alco.100/

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Cited by Sources: