Random two-component spanning forests. (English. French summary) Zbl 1334.82011

The authors study random two-component spanning forests, that is subgraphs of a given finite graph \(\mathcal{G}\) in \(\mathbb{R}^d,\) containing no cycles and having two connected components. They give formulas for the size of these components, and study some properties regarding their vertices and edges.


82B20 Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics
05C81 Random walks on graphs
Full Text: DOI arXiv Euclid


[1] I. Benjamini, R. Lyons, Y. Peres and O. Schramm. Uniform spanning forests. Ann. Probab. 29 (2001) 1-65. · 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. · 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. · 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. · Zbl 0850.82005
[5] A. Kassel and R. Kenyon. Random curves on surfaces induced by the Laplacian determinant. Preprint, 2012. Available at . arXiv:1211.6974 · Zbl 1377.82037
[6] A. Kassel and D. B. Wilson. The looping rate and sandpile density of planar graphs. Preprint, 2014. Available at . arXiv:1402.4169 · Zbl 1342.82035
[7] R. W. Kenyon and D. B. Wilson. Spanning trees of graphs on surfaces and the intensity of loop-erased random walk on \(\mathbb{Z}^{2}\). Preprint, 2011. Available at . arXiv:1107.3377 · Zbl 1230.60009
[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. · Zbl 1210.60002
[10] L. Levine and Y. Peres. The looping constant of \(\mathbb{Z}^{d}\). Random Structures Algorithms 45 (2014) 1-13. · Zbl 1316.60067
[11] W. Myrvold. Counting \(k\)-component forests of a graph. Networks 22 (7) (1992) 647-652. · Zbl 0773.90084
[12] G. Pólya. Torsional rigidity, principal frequency, electrostatic capacity, and symmetrization. Quart. Appl. Math. 6 (1948) 267-277. · 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. · Zbl 0946.60070
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.