Si est un graphe fini, orienté et fortement connexe, l’ensemble 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 (par exemple le Laplacien) peut se relever canoniquement au graphe . 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 à 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 is a strongly connected finite directed graph, the set of rooted directed spanning trees of 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 , for example the Laplacian, can be lifted canonically to . 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 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.
Philippe Biane 1 ; Guillaume Chapuy 2
CC-BY 4.0
@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},
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 = {https://afst.centre-mersenne.org/articles/10.5802/afst.1532/}
}
TY - JOUR AU - Philippe Biane AU - Guillaume Chapuy TI - Laplacian matrices and spanning trees of tree graphs JO - Annales de la Faculté des sciences de Toulouse : Mathématiques PY - 2017 SP - 235 EP - 261 VL - 26 IS - 2 PB - Université Paul Sabatier, Toulouse UR - https://afst.centre-mersenne.org/articles/10.5802/afst.1532/ DO - 10.5802/afst.1532 LA - en ID - AFST_2017_6_26_2_235_0 ER -
%0 Journal Article %A Philippe Biane %A Guillaume Chapuy %T Laplacian matrices and spanning trees of tree graphs %J Annales de la Faculté des sciences de Toulouse : Mathématiques %D 2017 %P 235-261 %V 26 %N 2 %I Université Paul Sabatier, Toulouse %U https://afst.centre-mersenne.org/articles/10.5802/afst.1532/ %R 10.5802/afst.1532 %G en %F AFST_2017_6_26_2_235_0
Philippe Biane; Guillaume Chapuy. 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. https://afst.centre-mersenne.org/articles/10.5802/afst.1532/
[1] A proof of the Markov chain tree theorem, Stat. Probab. Lett., Volume 8 (1989) no. 2, pp. 189-192 | DOI
[2] 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 | DOI
[3] 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] Polynomials associated with finite Markov chains, Séminaire de Probabilités XLVII (Lecture Notes in Mathematics), Volume 2137, Springer, 2015, pp. 249-262
[5] Sandpile groups and spanning trees of directed line graphs, J. Comb. Theory, Volume 118 (2011) no. 2, pp. 350-364 | DOI
[6] Probability on trees and networks (Cambridge University Press, to appear. Current version available at http://pages.iu.edu/~rdlyons/prbtree/prbtree.html)
[7] Factorizations of some weighted spanning tree enumerators, J. Comb. Theory, Volume 104 (2003) no. 2, pp. 287-300 | DOI
[8] Non-negative matrices and Markov chains, Springer Series in Statistics, Springer, 2006, xiii+287 pages
[9] Enumerative combinatorics II, Cambridge Studies in Advanced Mathematics, 62, Cambridge University Press, 1999, xii+581 pages
Cité par Sources :