logo AFST
Laplacian matrices and spanning trees of tree graphs
Philippe Biane; Guillaume Chapuy
Annales de la Faculté des sciences de Toulouse : Mathématiques, Serie 6, Volume 26 (2017) no. 2, p. 235-261

If G is a strongly connected finite directed graph, the set 𝒯G of rooted directed spanning trees of G is naturally equipped with a structure of directed graph: there is a directed edge from any spanning tree to any other obtained by adding an outgoing edge at its root vertex and deleting the outgoing edge of the endpoint. Any Schrödinger operator on G, for example the Laplacian, can be lifted canonically to 𝒯G. We show that the determinant of such a lifted Schrödinger operator admits a remarkable factorization into a product of determinants of the restrictions of Schrödinger operators on subgraphs of G and we give a combinatorial description of the multiplicities using an exploration procedure of the graph. A similar factorization can be obtained from earlier ideas of C. Athanasiadis, but this leads to a different expression of the multiplicities, as signed sums on which the nonnegativity is not apparent. We also provide a description of the block structure associated with this factorization.

As a simple illustration we reprove a formula of Bernardi enumerating spanning forests of the hypercube, that is closely related to the graph of spanning trees of a bouquet. Several combinatorial questions are left open, such as giving a bijective interpretation of the results.

Si G est un graphe fini, orienté et fortement connexe, l’ensemble 𝒯G de ses arbres couvrants enracinés et orientés a une structure naturelle de graphe orienté : pour chaque arbre couvrant et chaque arête partant de la racine on construit l’arbre obtenu en rajoutant cette arête à l’arbre initial et en supprimant l’arête issue du but de l’arête ajoutée. Un opérateur de Schrödinger sur G (par exemple le Laplacien) peut se relever canoniquement au graphe 𝒯G. Nous montrons que le déterminant de cet opérateur de Schrödinger se factorise en un produit de déterminants obtenus en restreignant l’opérateur de Schrödinger sur G à certains sous-graphes fortement connexes et nous donnons une description combinatoire des multiplicités, obtenue par un procédé d’exploration du graphe. Une factorisation semblable peut se déduire de résultats antérieurs d’Athanasiadis mais l’expression des multiplicités ainsi obtenue est sous la forme d’une somme signée, dont la positivité n’est pas apparente. Notre preuve fait également apparaître la structure en blocs de l’opérateur relevé qui explique la factorisation.

Nous déduisons de cette factorisation une nouvelle preuve d’une formule de Bernardi qui compte les arbres couvrants d’un hypercube. Nous laissons toutefois ouvertes plusieurs questions, notamment celle de donner une preuve bijective de nos résultats.

Published online : 2017-04-13
DOI : https://doi.org/10.5802/afst.1532
@article{AFST_2017_6_26_2_235_0,
     author = {Philippe Biane and Guillaume Chapuy},
     title = {Laplacian matrices and spanning trees of tree graphs},
     journal = {Annales de la Facult\'e des sciences de Toulouse : Math\'ematiques},
     publisher = {Universit\'e Paul Sabatier, Toulouse},
     volume = {Ser. 6, 26},
     number = {2},
     year = {2017},
     pages = {235-261},
     doi = {10.5802/afst.1532},
     language = {en},
     url = {https://afst.centre-mersenne.org/item/AFST_2017_6_26_2_235_0}
}
Biane, Philippe; Chapuy, Guillaume. Laplacian matrices and spanning trees of tree graphs. Annales de la Faculté des sciences de Toulouse : Mathématiques, Serie 6, Volume 26 (2017) no. 2, pp. 235-261. doi : 10.5802/afst.1532. afst.centre-mersenne.org/item/AFST_2017_6_26_2_235_0/

[1] Venkat Anantharam; Pantelis Tsoucas A proof of the Markov chain tree theorem, Stat. Probab. Lett., Tome 8 (1989) no. 2, pp. 189-192 | Article

[2] Christos A. Athanasiadis Spectra of some interesting combinatorial matrices related to oriented spanning trees on a directed graph, J. Algebr. Comb., Tome 5 (1996) no. 1, pp. 5-11 | Article

[3] Olivier Bernardi On the spanning trees of the hypercube and other products of graphs, Electron. J. Comb., Tome 19 (2012) no. 4 (Paper 51, 16 pages, electronic only)

[4] Philippe Biane Polynomials associated with finite Markov chains, Séminaire de Probabilités XLVII (Lecture Notes in Mathematics) Tome 2137, Springer, 2015, pp. 249-262

[5] Lionel Levine Sandpile groups and spanning trees of directed line graphs, J. Comb. Theory, Tome 118 (2011) no. 2, pp. 350-364 | Article

[6] Russell Lyons; Yuval Peres Probability on trees and networks (Cambridge University Press, to appear. Current version available at http://pages.iu.edu/~rdlyons/prbtree/prbtree.html)

[7] Jeremy L. Martin; Victor Reiner Factorizations of some weighted spanning tree enumerators, J. Comb. Theory, Tome 104 (2003) no. 2, pp. 287-300 | Article

[8] Eugene Seneta Non-negative matrices and Markov chains, Springer Series in Statistics, Springer, 2006, xiii+287 pages

[9] Richard P. Stanley Enumerative combinatorics II, Cambridge Studies in Advanced Mathematics, Tome 62, Cambridge University Press, 1999, xii+581 pages