zbMATH — the first resource for mathematics

The component graph of the uniform spanning forest: transitions in dimensions \(9,10,11,\ldots\). (English) Zbl 07109859
Summary: We prove that the uniform spanning forests of \(\mathbb{Z}^d\) and \(\mathbb{Z}^{\ell}\) have qualitatively different connectivity properties whenever \(\ell >d \geq 4\). In particular, we consider the graph formed by contracting each tree of the uniform spanning forest down to a single vertex, which we call the component graph. We introduce the notion of ubiquitous subgraphs and show that the set of ubiquitous subgraphs of the component graph changes whenever the dimension changes and is above 8. To separate dimensions 5, 6, 7, and 8, we prove a similar result concerning ubiquitous subhypergraphs in the component hypergraph. Our result sharpens a theorem of Benjamini, Kesten, Peres, and Schramm, who proved that the diameter of the component graph increases by one every time the dimension increases by four.

60D05 Geometric probability and stochastic geometry
60K35 Interacting random processes; statistical mechanics type models; percolation theory
PDF BibTeX Cite
Full Text: DOI arXiv
[1] Barlow, MT; Murugan, M., Stability of the elliptic Harnack inequality, Ann. Math. (2), 187, 777-823, (2018) · Zbl 1450.35131
[2] Benjamini, I.; Kesten, H.; Peres, Y.; Schramm, O., Geometry of the uniform spanning forest: transitions in dimensions \(4,8,12,...\), Ann. Math. (2), 160, 465-491, (2004) · Zbl 1071.60006
[3] Benjamini, I.; Lyons, R.; Peres, Y.; Schramm, O., Uniform spanning forests, Ann. Probab., 29, 1-65, (2001) · Zbl 1016.60009
[4] Broman, E.I., Tykesson, J., et al.: Connectedness of poisson cylinders in Euclidean space. In: Annales de l’Institut Henri Poincaré, Probabilités et Statistiques, vol. 52, pp. 102-126. Institut Henri Poincaré, Paris (2016) · Zbl 1333.60197
[5] Delmotte, T., Parabolic harnack inequality and estimates of markov chains on graphs, Revista matemática iberoamericana, 15, 181-232, (1999) · Zbl 0922.60060
[6] Fabes, EB; Stroock, DW, A new proof of Moser’s parabolic Harnack inequality using the old ideas of Nash, Arch. Ration. Mech. Anal., 96, 327-338, (1986) · Zbl 0652.35052
[7] Godsil, CD; Imrich, W.; Seifter, N.; Watkins, ME; Woess, W., A note on bounded automorphisms of infinite graphs, Graphs Comb., 5, 333-338, (1989) · Zbl 0714.05029
[8] Grimmett, GR; Winkler, SN, Negative association in uniform forests and connected graphs, Random Struct. Algorithms, 24, 444-460, (2004) · Zbl 1048.60007
[9] Häggström, O., Random-cluster measures and uniform spanning trees, Stoch. Process. Appl., 59, 267-275, (1995) · Zbl 0840.60089
[10] Hebisch, W.; Saloff-Coste, L., Gaussian estimates for Markov chains and random walks on groups, Ann. Probab., 21, 673-709, (1993) · Zbl 0776.60086
[11] Hodges, W.: Model Theory. Encyclopedia of Mathematics and Its Applications, vol. 42. Cambridge University Press, Cambridge (1993)
[12] Hutchcroft, T.: Indistinguishability of collections of trees in the uniform spanning forest. Preprint (2018) · Zbl 1391.60021
[13] Hutchcroft, T.; Nachmias, A., Indistinguishability of trees in uniform spanning forests, Probab. Theory Related Fields, 168, 113-152, (2017) · Zbl 1407.60019
[14] Hutchcroft, T., Nachmias, A.: Uniform spanning forests of planar graphs. arXiv preprint arXiv:1603.07320 (2016) · Zbl 1422.60022
[15] Kumagai, T.: Random Walks on Disordered Media and Their Scaling Limits, Volume 2101 of Lecture Notes in Mathematics. Springer, Cham (2014). Lecture notes from the 40th Probability Summer School held in Saint-Flour, 2010, École d’Été de Probabilités de Saint-Flour. [Saint-Flour Probability Summer School]
[16] Lacoin, H.; Tykesson, J., On the easiest way to connect \(k\) points in the random interlacements process, ALEA Latin Am. J. Probab. Math Stat., 10, 505-524, (2013) · Zbl 1277.60177
[17] Lawler, GF, A self-avoiding random walk, Duke Math. J., 47, 655-693, (1980) · Zbl 0445.60058
[18] Li, X.: Percolative properties of Brownian interlacements and its vacant set. arXiv preprint arXiv:1610.08204 (2016)
[19] Lyons, R.; Peres, Y.; Schramm, O., Markov chain intersections and the loop-erased walk, Annales de l’institut Henri Poincaré (B) Probabilités et Statistiques, 39, 779-791, (2003) · Zbl 1030.60035
[20] Lyons, R.; Schramm, O., Indistinguishability of percolation clusters, Ann. Probab., 27, 1809-1836, (1999) · Zbl 0960.60013
[21] Pemantle, R., Choosing a spanning tree for the integer lattice uniformly, Ann. Probab., 19, 1559-1574, (1991) · Zbl 0758.60010
[22] Procaccia, EB; Tykesson, J.; etal., Geometry of the random interlacement, Electron. Commun. Probab., 16, 76, (2011) · Zbl 1254.60018
[23] Procaccia, E.B., Zhang, Y.: Connectivity properties of branching interlacements. arXiv preprint arXiv:1612.00406 (2016) · Zbl 1406.60121
[24] Ráth, B., Sapozhnikov, A.: Connectivity properties of random interlacement and intersection of random walks. arXiv preprint arXiv:1012.4711 (2010)
[25] Spencer, J.: The Strange Logic of Random Graphs, vol. 22. Springer, Berlin (2001) · Zbl 0976.05001
[26] Sznitman, A-S, Vacant set of random interlacements and percolation, Ann. Math. (2), 171, 2039-2087, (2010) · Zbl 1202.60160
[27] Timár, A., Indistinguishability of the components of random spanning forests, Ann. Probab., 46, 2221-2242, (2018) · Zbl 1430.60020
[28] Trofimov, VI, Graphs with polynomial growth, Sbornik Math., 51, 405-417, (1985) · Zbl 0565.05035
[29] Wilson, D.B.: Generating random spanning trees more quickly than the cover time. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing (Philadelphia, PA, 1996), pp. 296-303. ACM, New York (1996) · Zbl 0946.60070
[30] Woess, W.: Random Walks on Infinite Graphs and Groups. Cambridge Tracts in Mathematics, vol. 138. Cambridge University Press, Cambridge (2000) · Zbl 0951.60002
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.