Ballisticity of the self-avoiding walk on nonamenable transitive graphs: the one-ended case

The self-avoiding walk (SAW) on an infinite graph is conjectured to be ballistic — to have positive speed, equivalently mean-square-displacement exponent $\nu=1$ — on every nonamenable vertex-transitive graph. Li (J. Combin. Theory Ser. A, 2020) records this conjecture for nonamenable bounded-degree graphs and proved positive speed only for quasi-transitive graphs with more than one end satisfying symmetric cut-set assumptions, and for selected Cayley graphs of multi-ended groups. Later work removed most of these hypotheses: Madras–Wu, Benjamini, and Panagiotis settled the regular tessellations of the hyperbolic plane; Hutchcroft settled transitive graphs with nonunimodular transitive automorphism subgroups; and Lehner–Lindorfer–Panagiotis (2025) proved ballisticity with exponential tail on every transitive graph with infinitely many ends, strictly generalizing Li's theorems. The transitive cases that remain open are essentially the one-ended ones outside the range of the known positive-speed criteria: whether the uniform $n$ -step SAW on a one-ended nonamenable vertex-transitive graph admitting no nonunimodular transitive automorphism action — for instance a Cayley graph of a one-ended nonamenable group such as a surface group with a generic generating set — is ballistic.

Background

A self-avoiding walk (SAW) is a path in a graph that visits no vertex more than once; SAWs model long linear polymers and are central objects of combinatorial probability. On an infinite, connected, locally finite graph $G$ with root $o$ , let $c_n$ be the number of $n$ -step SAWs starting at $o$ and let $P_n$ be the uniform probability measure on these walks. The exponential growth rate $\mu=\lim c_n^{1/n}$ is the connective constant. A central question is the typical displacement of the endpoint: writing $d_G$ for graph distance and $(w_0,\dots,w_n)$ for a walk sampled from $P_n$ , one asks whether $d_G(w_0,w_n)$ grows linearly in $n$ . The SAW has positive speed (is ballistic) when this holds for an overwhelming majority of walks, and the mean-square-displacement exponent $\nu$ , defined by $\langle d_G(w_0,w_n)^2\rangle\asymp n^{2\nu}$ (equality up to constant factors), equals 1 exactly when displacement is linear; sub-ballistic behavior corresponds to $\nu<1$ .

The answer depends on the large-scale geometry of the graph. A graph is vertex-transitive if its automorphism group acts transitively on vertices (quasi-transitive if with finitely many orbits). It is amenable if it admits Følner sets — finite vertex sets whose edge boundary is negligible relative to their size — and nonamenable otherwise; for transitive graphs nonamenability is equivalent to a positive isoperimetric (Cheeger) constant, and it implies exponential volume growth (the converse fails: amenable transitive graphs of exponential growth exist, e.g. the Baumslag–Solitar group $BS(1,2)=\langle a,t\mid tat^{-1}=a^2\rangle$ ). The number of ends measures, as a supremum over finite deleted vertex sets, how many infinite connected components can remain after deleting a finite set; a classical theorem asserts that a quasi-transitive graph has either one, two, or infinitely many ends. For a transitive group $\Gamma$ of automorphisms with vertex stabilizers $\Gamma_x$ , unimodularity means that the cardinalities $|\Gamma_x y|$ and $|\Gamma_y x|$ coincide for all vertices $x,y$ ; this always holds for a group acting on its own Cayley graph by left translations, and graphs admitting a transitive nonunimodular subgroup form a special degenerate class.

The known picture splits by geometry. On the hypercubic lattices $\mathbb{Z}^d$ with $d\ge 2$ , Duminil-Copin and Hammond proved the SAW is sub-ballistic in every dimension; on regular trees it is a non-backtracking walk (it never immediately returns along the edge it just traversed) and is trivially ballistic. In negative curvature positive speed is expected everywhere: Madras and Wu (2005) proved it for regular tilings of the hyperbolic plane of sufficiently high degree; Nachmias and Peres (2012) gave the perturbative sufficient criterion $(d-1)\rho<\mu$ , with $\rho$ the spectral radius of the simple random walk, which applies to nonamenable Cayley graphs of high girth; Gilch and Müller (2017) handled free products of quasi-transitive graphs. Li (2020) proved that on quasi-transitive graphs with more than one end whose complementary components after deleting a finite cut set have suitable symmetry under a quasi-transitive automorphism group (Assumptions 1.1–1.2 of that paper), SAWs with linear end-to-end displacement have the same exponential growth rate as all SAWs, giving positive speed; applications include the square grid in an infinite cylinder and, via Stallings' splitting theorem (a structure theorem describing finitely generated groups with more than one end as amalgamated free products or HNN extensions over finite subgroups), the existence of a locally finite Cayley graph with positive speed for every finitely generated group with more than one end. Benjamini (2016) proved linear expected displacement on the 7-regular planar triangulation and on 1-skeletons of reflection-generated lattices in the hyperbolic spaces $\mathbb{H}^n$ .

Two later developments removed most structural assumptions. Hutchcroft (2019) proved ballisticity with exponential tail and $c_n\asymp\mu^n$ (i.e., $c_n$ bounded above and below by constant multiples of $\mu^n$ ) on every transitive graph whose automorphism group admits a transitive nonunimodular subgroup, including products $T_k\times\mathbb{Z}^d$ of a $k$ -regular tree with $\mathbb{Z}^d$ ; his paper states the general conjecture explicitly. Panagiotis (2024) proved that on every regular tessellation of the hyperbolic plane the SAW is ballistic, by showing that self-avoiding walks of length $n$ outnumber self-avoiding polygons (closed self-avoiding walks) exponentially, a property that implies ballisticity on any vertex-transitive graph. Finally, Lehner, Lindorfer, and Panagiotis (2025), using quasi-transitive group-invariant tree decompositions (decompositions of a graph into parts arranged along a tree, which endow SAW restrictions with a spatial Markov property) and an argument in the spirit of Kesten's pattern theorem (which asserts that any fixed finite pattern that can occur in a SAW occurs with positive density in all but exponentially few long SAWs), proved that on every transitive graph with infinitely many ends the $n$ -step SAW is ballistic with exponentially high probability and $c_n$ grows like $\mu^n$ up to a constant factor.

After these results, the conjecture recorded in Li's introduction — that $\nu=1$ for SAWs on nonamenable graphs of bounded degree — remains open; the open core addressed here is the transitive one-ended case with no nonunimodular transitive automorphism action that is not a regular hyperbolic tessellation and lies outside the range of the positive-speed criteria above, while the non-transitive instances are not covered by the cited results. The basic open examples are Cayley graphs of one-ended nonamenable finitely generated groups, such as surface groups or other one-ended hyperbolic groups (finitely generated groups whose Cayley graphs are Gromov-hyperbolic, meaning all geodesic triangles are uniformly thin), equipped with generating sets for which the graph is not a planar regular tessellation.

Problem Statement

Prove or disprove the following conjecture: for every infinite, connected, locally finite, vertex-transitive nonamenable graph $G$ with root $o$ , there exist constants $c,t>0$ (depending on $G$ ) such that the uniform measure $P_n$ on $n$ -step self-avoiding walks from $o$ satisfies

$P_n\big(d_G(w_0,w_n)\ge cn\big)\ \ge\ 1-e^{-tn}$

for every $n\ge 1$ , where $(w_0,\dots,w_n)$ is a walk sampled from $P_n$ . In particular, the conjecture asserts that the mean-square-displacement exponent $\nu$ equals 1 on every such graph and that every weak limit of the measures $P_n$ (an infinite self-avoiding walk) has positive speed. This exponential-tail bound is stronger than the positive-speed conclusion recorded in the introduction of Li (2020) — that $\nu=1$ for SAWs on nonamenable graphs of bounded degree — and, together with the conclusion $c_n\asymp\mu^n$ , it is the general conjecture formulated explicitly by Hutchcroft (2019).

Since the cases of transitive graphs with infinitely many ends (Lehner–Lindorfer–Panagiotis 2025, combined with Hutchcroft 2019 for automorphism groups fixing an end) and of transitive graphs admitting a transitive nonunimodular automorphism subgroup (Hutchcroft 2019) are settled affirmatively, as are the regular tessellations of the hyperbolic plane (Madras–Wu 2005; Panagiotis 2024; Benjamini 2016), the open part addressed here is ballisticity on one-ended nonamenable vertex-transitive graphs with no nonunimodular transitive automorphism action and lying outside the range of the known positive-speed criteria (such as the high-girth criterion $(d-1)\rho<\mu$ of Nachmias and Peres 2012) — for example, the Cayley graph of a surface group $\langle a,b,c,d\mid [a,b][c,d]\rangle$ or of any other one-ended nonamenable finitely generated group, taken with a generating set for which the graph is not a regular hyperbolic tessellation.

The natural quasi-transitive extension — replacing vertex-transitive by quasi-transitive — is a related question that remains open.

References

Zhongyang Li, Positive speed self-avoiding walks on graphs with more than one end, Journal of Combinatorial Theory, Series A 175 (2020), 105257. DOI: 10.1016/j.jcta.2020.105257, https://doi.org/10.1016/j.jcta.2020.105257 (arXiv:1612.02464, https://arxiv.org/abs/1612.02464)
Florian Lehner, Christian Lindorfer, Christoforos Panagiotis, Self-avoiding walk is ballistic on graphs with more than one end, Forum of Mathematics, Sigma 13 (2025), e179. DOI: 10.1017/fms.2025.10131, https://doi.org/10.1017/fms.2025.10131 (arXiv:2403.13121, https://arxiv.org/abs/2403.13121)
Tom Hutchcroft, Self-avoiding walk on nonunimodular transitive graphs, The Annals of Probability 47 (2019). DOI: 10.1214/18-AOP1322, https://doi.org/10.1214/18-AOP1322 (arXiv:1709.10515, https://arxiv.org/abs/1709.10515)
Christoforos Panagiotis, Self-avoiding walks and polygons on hyperbolic graphs, Journal of Graph Theory 106 (2024), 435–473. DOI: 10.1002/jgt.23087, https://doi.org/10.1002/jgt.23087 (arXiv:1908.00127, https://arxiv.org/abs/1908.00127)
Neal Madras and C. Chris Wu, Self-avoiding walks on hyperbolic graphs, Combinatorics, Probability and Computing 14 (2005), 523–548. DOI: 10.1017/S0963548305006772, https://doi.org/10.1017/S0963548305006772
Itai Benjamini, Self avoiding walk on the seven regular triangulation, arXiv preprint (2016). arXiv: 1612.04169, https://arxiv.org/abs/1612.04169
Itai Benjamini and Christoforos Panagiotis, Hyperbolic self avoiding walk, Electronic Communications in Probability 26 (2021). DOI: 10.1214/21-ECP388, https://doi.org/10.1214/21-ECP388 (arXiv:2007.03534, https://arxiv.org/abs/2007.03534)
Hugo Duminil-Copin and Alan Hammond, Self-avoiding walk is sub-ballistic, Communications in Mathematical Physics 324 (2013), 401–423. DOI: 10.1007/s00220-013-1811-1, https://doi.org/10.1007/s00220-013-1811-1 (arXiv:1205.0401, https://arxiv.org/abs/1205.0401)
Hugo Duminil-Copin and Stanislav Smirnov, The connective constant of the honeycomb lattice equals sqrt(2+sqrt 2), Annals of Mathematics 175 (2012), 1653–1665. DOI: 10.4007/annals.2012.175.3.14, https://doi.org/10.4007/annals.2012.175.3.14
Dmitrii Krachun and Christoforos Panagiotis, Quantitative sub-ballisticity of self-avoiding walk on the hexagonal lattice, The Annals of Probability 54 (2026). DOI: 10.1214/24-AOP1730, https://doi.org/10.1214/24-AOP1730
Lorenz A. Gilch and Sebastian Müller, Counting self-avoiding walks on free products of graphs, Discrete Mathematics 340 (2017), 325–332. DOI: 10.1016/j.disc.2016.08.018, https://doi.org/10.1016/j.disc.2016.08.018
Asaf Nachmias and Yuval Peres, Non-amenable Cayley graphs of high girth have $p_c < p_u$ and mean-field exponents, Electronic Communications in Probability 17 (2012). DOI: 10.1214/ecp.v17-2139, https://doi.org/10.1214/ecp.v17-2139