Laplacian matrices and spanning trees of tree graphs
Annales de la Faculté des sciences de Toulouse : Mathématiques, Série 6, Tome 26 (2017) no. 2, pp. 235-261.

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.

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.

Publié le :
DOI : https://doi.org/10.5802/afst.1532
@article{AFST_2017_6_26_2_235_0,
     author = {Biane, Philippe and Chapuy, Guillaume},
     title = {Laplacian matrices and spanning trees of tree graphs},
     journal = {Annales de la Facult\'e des sciences de Toulouse : Math\'ematiques},
     pages = {235--261},
     publisher = {Universit\'e Paul Sabatier, Toulouse},
     volume = {Ser. 6, 26},
     number = {2},
     year = {2017},
     doi = {10.5802/afst.1532},
     language = {en},
     url = {http://www.numdam.org/articles/10.5802/afst.1532/}
}
Biane, Philippe; Chapuy, Guillaume. Laplacian matrices and spanning trees of tree graphs. Annales de la Faculté des sciences de Toulouse : Mathématiques, Série 6, Tome 26 (2017) no. 2, pp. 235-261. doi : 10.5802/afst.1532. http://www.numdam.org/articles/10.5802/afst.1532/

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

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

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

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

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

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

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

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

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