Random two-component spanning forests

Kassel, Adrien; Kenyon, Richard; Wu, Wei

doi:10.1214/14-AIHP625

Kassel, Adrien ; Kenyon, Richard ; Wu, Wei

Annales de l'I.H.P. Probabilités et statistiques, Tome 51 (2015) no. 4, pp. 1457-1464.

Résumé
Abstract

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 ( $2$ 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 $ℝ^{d}$ .

MR Zbl

DOI : 10.1214/14-AIHP625

Mots-clés : two-component spanning forests, mean resistance, torsional rigidity

@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://archive.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://archive.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://archive.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://archive.numdam.org/articles/10.1214/14-AIHP625/

Bibliographie
Cité par

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

[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 | Zbl

[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 | Zbl

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

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

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

[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

[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 | Zbl

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

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

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

[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 | Zbl

Cité par Sources :