Self-avoiding walk is ballistic on graphs with more than one end

Lehner, Florian ; Lindorfer, Christian ; Panagiotis, Christoforos

Forum of Mathematics, Sigma, Tome 13 (2025) no. 1, p. e179

Résumé

We prove that on any transitive graph G with infinitely many ends, a self-avoiding walk of length n is ballistic with extremely high probability, in the sense that there exist constants $c,t>0$ such that $\mathbb {P}_n(d_G(w_0,w_n)\geq cn)\geq 1-e^{-tn}$ for every $n\geq 1$. Furthermore, we show that the number of self-avoiding walks of length n grows asymptotically like $\mu _w^n$, in the sense that there exists $C>0$ such that $\mu _w^n\leq c_n\leq C\mu _w^n$ for every $n\geq 1$. These results generalise earlier work by Li (J. Comb. Theory Ser. A, 2020). The key to this greater generality is that in contrast to Li’s approach, our proof does not require the existence of a special structure that enables the construction of separating patterns. Our results also extend more generally to quasi-transitive graphs with infinitely many ends, satisfying the additional technical property that there is a quasi-transitive group of automorphisms of G which does not fix an end of G.

Détail

DOI : 10.1017/fms.2025.10131

Bibliographie

[1] Alm, S. E. and Janson, S., ‘Random self-avoiding walks on one-dimensional lattices’, Comm. Statist. Stochastic Models 6(2) (1990), 169–212. Google Scholar

[2] Bauerschmidt, R., Duminil-Copin, H., Goodman, J. and Slade, G., ‘Lectures on self-avoiding walks’, in Probability and Statistical Physics in Two and More Dimensions of Clay Math. Proc., 395–467 (Amer. Math. Soc., Providence, RI, 2012). Google Scholar

[3] Benjamini, I., ‘Self -avoiding walk on the seven regular triangulation’, arXiv preprint (2016). Google Scholar | arXiv

[4] Benjamini, I. and Panagiotis, C., ‘Hyperbolic self -avoiding walk’, Electron. Commun. Probab. 26 (2021), 1–5. Google Scholar | DOI

[5] Ceccherini-Silberstein, T. and Woess, W., ‘Growth and ergodicity of context-free languages’, Trans. Amer. Math. Soc. 354(11) (2002), 4597–4625. Google Scholar | DOI

[6] Duminil-Copin, H., Ganguly, S., Hammond, A. and Manolescu, I., ‘Bounding the number of self-avoiding walks: Hammersley–Welsh with polygon insertion’, Ann. Probab. 48(4) (2020). Google Scholar

[7] Duminil-Copin, H., Glazman, A., Hammond, A. and Manolescu, I., ‘On the probability that self-avoiding walk ends at a given point’, Ann. Probab. 44(2) (2016), 955–983. Google Scholar | DOI

[8] Duminil-Copin, H. and Hammond, A., ‘Self-avoiding walk is sub-ballistic’, Comm. Math. Phys. 324(2) (2013), 401–423. Google Scholar | DOI

[9] Duminil-Copin, H. and Smirnov, S., ‘The connective constant of the honeycomb lattice equals ’, Ann. of Math. (2) 175(3) (2012), 1653–1665. Google Scholar | DOI

[10] Dunwoody, M. J., ‘Cutting up graphs’, Combinatorica 2(1) (1982), 15–23. Google Scholar | DOI

[11] Dunwoody, M. J. and Krön, B., ‘Vertex cuts’, J. Graph Theory 80(2) (2015), 136–171. Google Scholar | DOI

[12] Flory, P. J., Principles of Polymer Chemistry (Cornell University Press, 1953). Google Scholar

[13] Georgakopoulos, A. and Wendland, A., ‘A study of 2-ended graphs via harmonic functions’, arXiv preprint (2023). Google Scholar | arXiv

[14] Gilch, L. A. and Müller, S., ‘Counting self-avoiding walks on free products of graphs’, Discrete Math. 340(3) (2017), 325–332. Google Scholar | DOI

[15] Grimmett, G. and Li, Z., ‘Self-Avoiding Walks and the Fisher Transformation’, Electron. J. Combin., 20(P47) (2013). Google Scholar | DOI

[16] Grimmett, G. and Li, Z., ‘Strict inequalities for connective constants of transitive graphs’, SIAM J. Discrete Math., 28(3) (2014), 1306–1333. Google Scholar | DOI

[17] Grimmett, G. and Li, Z., ‘Bounds on connective constants of regular graphs’, Combinatorica 35(3) (2015), 279–294. Google Scholar | DOI

[18] Grimmett, G. and Li, Z., ‘Connective constants and height functions for Cayley graphs’, Trans. Amer. Math. Soc. 369(8) (2017), 5961–5980. Google Scholar | DOI

[19] Grimmett, G. and Li, Z., ‘Self-Avoiding Walks and Amenability’, Electron. J. Combin. 24(4) (2017), 4–38. Google Scholar | DOI

[20] Grimmett, G. and Li, Z., ‘Locality of connective constants’, Discrete Math. 341(12) (2018), 3483–3497. Google Scholar | DOI

[21] Grimmett, G. and Li, Z., ‘Cubic graphs and the golden mean’, Discrete Math. 343(111638) (2020). Google Scholar | DOI

[22] Grimmett, G., Peres, Y. and Holroyd, A., ‘Extendable self-avoiding walks’, Ann. Inst. Henri Poincaré D 1 (2014), 61–75. Google Scholar | DOI

[23] Grimmett, G. R. and Li, Z., ‘Self-avoiding walks and connective constants’, in Sojourns in Probability Theory and Statistical Physics. III. Interacting Particle Systems and Random Walks, a Festschrift for Charles M. Newman, 215–241 (Singapore: Springer; Shanghai: NYU Shanghai, 2019). Google Scholar

[24] Halin, R., ‘Über die Maximalzahl fremder unendlicher Wege in Graphen’, Math. Nachr. 30 (1965), 63–85. Google Scholar | DOI

[25] Halin, R., ‘Automorphisms and endomorphisms of infinite locally finite graphs’, Abh. Math. Sem. Univ. Hamburg 39 (1973), 251–283. Google Scholar | DOI

[26] Halin, R., ‘S-functions for graphs’, J. Geom. 8(1–2) (1976), 171–186. Google Scholar | DOI

[27] Hamann, M., Lehner, F., Miraftab, B. and Rühmann, T., ‘A Stallings type theorem for quasi-transitive graphs’, J. Combin. Theory Ser. B 157 (2022), 40–69. Google Scholar | DOI

[28] Hammersley, J. M., ‘Percolation processes. II. The connective constant’, Proc. Cambridge Philos. Soc. 53 (1957), 642–645. Google Scholar | DOI

[29] Hammersley, J. M. and Welsh, D. J. A., ‘Further results on the rate of convergence to the connective constant of the hypercubical lattice’, Q. J. Math. 13(1) (1962), 108–110. Google Scholar | DOI

[30] Hara, T. and Slade, G., ‘The lace expansion for self-avoiding walk in five or more dimensions’, Rev. Math. Phys. 4(2) (1992), 235–327. Google Scholar | DOI

[31] Hara, T. and Slade, G., ‘Self-avoiding walk in five or more dimensions I. The critical behaviour’, Comm. Math. Phys. 147(1) (1992), 101–136. Google Scholar | DOI

[32] Hutchcroft, T., ‘Self-avoiding walk on nonunimodular transitive graphs’, Ann. Probab. 47(5) (2019), 2801–2829. Google Scholar | DOI

[33] Kesten, H., ‘On the Number of Self-Avoiding Walks’, J. Math. Phys. 4(7) (1963), 960–969. Google Scholar | DOI

[34] Kesten, H., ‘On the Number of Self-Avoiding Walks. II.’, J. Math. Phys. 5(8) (1964), 1128–1137. Google Scholar | DOI

[35] Krachun, D. and Panagiotis, C., ‘Quantitative sub-ballisticity of self-avoiding walk on the hexagonal lattice’, Ann. Probab. (to appear, 2023). Google Scholar

[36] Lehner, F. and Lindorfer, C., ‘Self-avoiding walks and multiple context-free languages’, Comb. Theory 3(1) (2023), 50. Id/No 18. Google Scholar

[37] Li, Z., ‘Positive speed self-avoiding walks on graphs with more than one end’, J. Combin. Theory Ser. A 175 (2020), 105257. Google Scholar | DOI

[38] Madras, N. and Slade, G., The Self-Avoiding Walk, Modern Birkhäuser Classics (Birkhäuser/Springer, New York, 2013). Reprint of the 1993 original. Google Scholar | DOI

[39] Madras, N. and Wu, C., ‘Self-avoiding walks on hyperbolic graphs’, Comb. Probab. Comput. (2005), 523–548. Google Scholar | DOI

[40] Nachmias, A. and Peres, Y., ‘Non-amenable Cayley graphs of high girth have and mean-field exponents’, Electron. Commun. Probab. 17 (2012). Google Scholar | DOI

[41] Panagiotis, C., ‘Self-avoiding walks and polygons on hyperbolic graphs’, J. Graph Theory 106(3) (2024), 435–473. Google Scholar | DOI

[42] Robertson, N. and Seymour, P. D., ‘Graph minors. III. Planar tree-width’, J. Combin. Theory Ser. B 36(1) (1984), 49–64. Google Scholar | DOI

[43] Schaefer, H. H., Banach Lattices and Positive Operators (Springer, Berlin, Heidelberg, 1974). Google Scholar | DOI