Random two-component spanning forests
Kassel, Adrien ; Kenyon, Richard ; Wu, Wei
Annales de l'I.H.P. Probabilités et statistiques, Tome 51 (2015), p. 1457-1464 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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 ℝ d .

We study random two-component spanning forests (2SF) 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 ℝ d .

Publié le : 2015-01-01
DOI : https://doi.org/10.1214/14-AIHP625 
@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},
     volume = {51},
     year = {2015},
     pages = {1457-1464},
     doi = {10.1214/14-AIHP625},
     mrnumber = {3414453},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 1457-1464. doi : 10.1214/14-AIHP625. http://gdmltest.u-ga.fr/item/AIHPB_2015__51_4_1457_0/

[1] I. Benjamini, R. Lyons, Y. Peres and O. Schramm. Uniform spanning forests. Ann. Probab. 29 (2001) 1–65. | MR 1825141 | Zbl 1016.60009

[2] R. Burton and R. Pemantle. Local characteristics, entropy, and limit theorems for spanning trees and domino tilings via transfer impedances. Ann. Probab. 21 (3) (1993) 1329–1371. | MR 1235419 | Zbl 0785.60007

[3] P. G. Doyle and J. L. Snell. Random Walks and Electric Networks. Carus Mathematical Monographs 22. Mathematical Association of America, Washington, DC, 1984. | MR 920811 | Zbl 0583.60065

[4] E. V. Ivashkevich, D. V. Ktitarev and V. B. Priezzhev. Waves of topplings in an Abelian sandpile. Phys. A 209 (1994) 347–360.

[5] A. Kassel and R. Kenyon. Random curves on surfaces induced by the Laplacian determinant. Preprint, 2012. Available at arXiv:1211.6974.

[6] A. Kassel and D. B. Wilson. The looping rate and sandpile density of planar graphs. Preprint, 2014. Available at arXiv:1402.4169.

[7] R. W. Kenyon and D. B. Wilson. Spanning trees of graphs on surfaces and the intensity of loop-erased random walk on ℤ 2 . Preprint, 2011. Available at arXiv:1107.3377. | MR 2737268

[8] G. Kirchhoff. Ü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] G. F. Lawler and V. Limic. Random Walk: A Modern Introduction. Cambridge Studies in Advanced Mathematics 123. Cambridge Univ. Press, Cambridge, 2010. | MR 2677157 | Zbl 1210.60002

[10] L. Levine and Y. Peres. The looping constant of ℤ d . Random Structures Algorithms 45 (2014) 1–13. | MR 3231081 | Zbl 06334114

[11] W. Myrvold. Counting k-component forests of a graph. Networks 22 (7) (1992) 647–652. | MR 1189292 | Zbl 0773.90084

[12] G. Pólya. Torsional rigidity, principal frequency, electrostatic capacity, and symmetrization. Quart. Appl. Math. 6 (1948) 267–277. | MR 26817 | Zbl 0037.25301

[13] D. B. Wilson. 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 1427525 | Zbl 0946.60070