Nous étudions la mesure uniforme sur les forêts couvrantes à deux composantes connexes d’un graphe fini et donnons des formules pour les deux premiers moments de la taille des composantes, les probabilités d’inclusion d’un ou deux sommets dans la même composante, et la probabilité qu’une arête sépare les composantes. Nous calculons la limite des ces quantités lorsque l’on considère une suite de graphes finis qui tend vers un graphe infini périodique dans .
We study random two-component spanning forests (SF) of finite graphs, giving formulas for the first and second moments of the sizes of the components, vertex-inclusion probabilities for one or two vertices, and the probability that an edge separates the components. We compute the limit of these quantities when the graph tends to an infinite periodic graph in .
@article{AIHPB_2015__51_4_1457_0, author = {Kassel, Adrien and Kenyon, Richard and Wu, Wei}, title = {Random two-component spanning forests}, journal = {Annales de l'I.H.P. Probabilit\'es et statistiques}, pages = {1457--1464}, publisher = {Gauthier-Villars}, volume = {51}, number = {4}, year = {2015}, doi = {10.1214/14-AIHP625}, mrnumber = {3414453}, zbl = {1334.82011}, language = {en}, url = {http://www.numdam.org/articles/10.1214/14-AIHP625/} }
TY - JOUR AU - Kassel, Adrien AU - Kenyon, Richard AU - Wu, Wei TI - Random two-component spanning forests JO - Annales de l'I.H.P. Probabilités et statistiques PY - 2015 SP - 1457 EP - 1464 VL - 51 IS - 4 PB - Gauthier-Villars UR - http://www.numdam.org/articles/10.1214/14-AIHP625/ DO - 10.1214/14-AIHP625 LA - en ID - AIHPB_2015__51_4_1457_0 ER -
%0 Journal Article %A Kassel, Adrien %A Kenyon, Richard %A Wu, Wei %T Random two-component spanning forests %J Annales de l'I.H.P. Probabilités et statistiques %D 2015 %P 1457-1464 %V 51 %N 4 %I Gauthier-Villars %U http://www.numdam.org/articles/10.1214/14-AIHP625/ %R 10.1214/14-AIHP625 %G en %F AIHPB_2015__51_4_1457_0
Kassel, Adrien; Kenyon, Richard; Wu, Wei. Random two-component spanning forests. Annales de l'I.H.P. Probabilités et statistiques, Tome 51 (2015) no. 4, pp. 1457-1464. doi : 10.1214/14-AIHP625. http://www.numdam.org/articles/10.1214/14-AIHP625/
[1] Uniform spanning forests. Ann. Probab. 29 (2001) 1–65. | DOI | MR | Zbl
, , and .[2] Local characteristics, entropy, and limit theorems for spanning trees and domino tilings via transfer impedances. Ann. Probab. 21 (3) (1993) 1329–1371. | MR | Zbl
and .[3] Random Walks and Electric Networks. Carus Mathematical Monographs 22. Mathematical Association of America, Washington, DC, 1984. | MR | Zbl
and .[4] Waves of topplings in an Abelian sandpile. Phys. A 209 (1994) 347–360. | DOI
, and .[5] Random curves on surfaces induced by the Laplacian determinant. Preprint, 2012. Available at arXiv:1211.6974. | MR
and .[6] The looping rate and sandpile density of planar graphs. Preprint, 2014. Available at arXiv:1402.4169. | MR | Zbl
and .[7] Spanning trees of graphs on surfaces and the intensity of loop-erased random walk on . Preprint, 2011. Available at arXiv:1107.3377. | MR
and .[8] Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme geführt wird. Ann. Phys. Chem. 72 (1847) 497–508.
.[9] Random Walk: A Modern Introduction. Cambridge Studies in Advanced Mathematics 123. Cambridge Univ. Press, Cambridge, 2010. | MR | Zbl
and .[10] The looping constant of . Random Structures Algorithms 45 (2014) 1–13. | DOI | MR | Zbl
and .[11] Counting -component forests of a graph. Networks 22 (7) (1992) 647–652. | MR | Zbl
.[12] Torsional rigidity, principal frequency, electrostatic capacity, and symmetrization. Quart. Appl. Math. 6 (1948) 267–277. | DOI | MR | Zbl
.[13] Generating random spanning trees more quickly than the cover time. In Proceedings of the Twenty-Eigth Annual ACM Symposium on the Theory of Computing (Philadelphia, PA, 1996) 296–303. ACM, New York, 1996. | MR | Zbl
.Cité par Sources :