# Self-Avoiding Walks and Connective Constants

• Geoffrey R. Grimmett
• Zhongyang Li
Conference paper
Part of the Springer Proceedings in Mathematics & Statistics book series (PROMS, volume 300)

## Abstract

The connective constant $$\mu (G)$$ of a quasi-transitive graph G is the asymptotic growth rate of the number of self-avoiding walks (SAWs) on G from a given starting vertex. We survey several aspects of the relationship between the connective constant and the underlying graph G.

• We present upper and lower bounds for $$\mu$$ in terms of the vertex-degree and girth of a transitive graph.

• We discuss the question of whether $$\mu \ge \phi$$ for transitive cubic graphs (where $$\phi$$ denotes the golden mean), and we introduce the Fisher transformation for SAWs (that is, the replacement of vertices by triangles).

• We present strict inequalities for the connective constants $$\mu (G)$$ of transitive graphs G, as G varies.

• As a consequence of the last, the connective constant of a Cayley graph of a finitely generated group decreases strictly when a new relator is added, and increases strictly when a non-trivial group element is declared to be a further generator.

• We describe so-called graph height functions within an account of ‘bridges’ for quasi-transitive graphs, and indicate that the bridge constant equals the connective constant when the graph has a unimodular graph height function.

• A partial answer is given to the question of the locality of connective constants, based around the existence of unimodular graph height functions.

• Examples are presented of Cayley graphs of finitely presented groups that possess graph height functions (that are, in addition, harmonic and unimodular), and that do not.

• The review closes with a brief account of the ‘speed’ of SAW.

## Keywords

Self-avoiding walk Connective constant Regular graph Transitive graph Quasi-transitive graph Cubic graph Golden mean Fisher transformation Cayley graph Bridge constant Locality theorem Graph height function Unimodularity Speed

## Notes

### Acknowledgements

This work was supported in part by the Engineering and Physical Sciences Research Council under grant EP/I03372X/1. GRG acknowledges valuable conversations with Alexander Holroyd concerning Questions 7 and 10, and the hospitality of UC Berkeley during the completion of the work. ZL acknowledges support from the Simons Foundation under grant #351813, and the National Science Foundation under grant DMS-1608896.

## References

1. 1.
Aizenman, M., Grimmett, G.R.: Strict monotonicity of critical points in percolation and ferromagnetic models. J. Stat. Phys. 63, 817–835 (1991)
2. 2.
Alm, S.E., Janson, S.: Random self-avoiding walks on one-dimensional lattices. Commun. Stat. Stoch. Models 6, 169–212 (1990)
3. 3.
Babai, L.: Vertex-transitive graphs and vertex-transitive maps. J. Graph Theory 15, 587–627 (1991)
4. 4.
Babai, L.: Automorphism groups, isomorphism, reconstruction. In: Graham, R.L., Grötschel, M., Lovász, L. (eds.) Handbook of Combinatorics, vol. II, pp. 1447–1540. Elsevier, Amsterdam (1995)Google Scholar
5. 5.
Balister, P., Bollobás, B., Riordan, O.: Essential enhancements revisited (2014). https://arxiv.org/abs/1402.0834
6. 6.
Bauerschmidt, R., Brydges, D.C., Slade, G.: Renormalisation group analysis of 4D spin models and self-avoiding walk. In: Proceedings ICMP, Santiago de Chile (2015). https://arxiv.org/abs/1602.04048
7. 7.
Bauerschmidt, R., Duminil-Copin, H., Goodman, J., Slade, G.: Lectures on self-avoiding walks. In: Ellwood, D., Newman, C.M., Sidoravicius, V., Werner, W. (eds.) Probability and Statistical Physics in Two and More Dimensions, Clay Mathematics Institute Proceedings, vol. 15, pp. 395–476. CMI/AMS publication (2012)Google Scholar
8. 8.
Benjamini, I.: Self avoiding walk on the seven regular triangulations (2016). https://arxiv.org/abs/1612.04169
9. 9.
Benjamini, I., Nachmias, A., Peres, Y.: Is the critical percolation probability local? Probab. Theory Relat. Fields 149, 261–269 (2011)
10. 10.
Benjamini, I., Schramm, O.: Percolation beyond $$\mathbb{Z}^{d}$$, many questions and a few answers. Electron. Commun. Probab. 1, 71–82 (1996)
11. 11.
Benjamini, I., Schramm, O.: Recurrence of distributional limits of finite planar graphs. Electron. J. Probab. 6 (2001). Article 23Google Scholar
12. 12.
Bezuidenhout, C., Grimmett, G.R., Kesten, H.: Strict inequality for critical values of Potts models and random-cluster processes. Commun. Math. Phys. 158, 1–16 (1993)
13. 13.
Boutillier, C., de Tilière, B.: The critical Z-invariant Ising model via dimers: locality property. Commun. Math. Phys. 301, 473–516 (2011)
14. 14.
Day, M.M.: Amenable semigroups. Illinois J. Math. 1, 509–544 (1957)
15. 15.
Diestel, R., Leader, I.: A conjecture concerning a limit of non-Cayley graphs. J. Alg. Comb. 14, 17–25 (2001)
16. 16.
Dodziuk, J.: Difference equations, isoperimetric inequality and transience of certain random walks. Trans. Am. Math. Soc. 284, 787–794 (1984)
17. 17.
Duminil-Copin, H., Glazman, A., Hammond, A., Manolescu, I.: On the probability that self-avoiding walk ends at a given point. Ann. Probab. 44, 955–983 (2016)
18. 18.
Duminil-Copin, H., Hammond, A.: Self-avoiding walk is sub-ballistic. Commun. Math. Phys. 324, 401–423 (2013)
19. 19.
Duminil-Copin, H., Smirnov, S.: The connective constant of the honeycomb lattice equals $$\sqrt{2+\sqrt{2}}$$. Ann. Math. 175, 1653–1665 (2012)
20. 20.
Dvořák, Z., Mohar, B.: Spectral radius of finite and infinite planar graphs and of graphs of bounded genus. J. Comb. Theory Ser. B 100, 729–739 (2010)
21. 21.
Fisher, M.E.: On the dimer solution of planar Ising models. J. Math. Phys. 7, 1776–1781 (1966)
22. 22.
Flory, P.: Principles of Polymer Chemistry. Cornell University Press, Ithaca (1953)Google Scholar
23. 23.
Frauenkron, H., Causo, M.S., Grassberger, P.: Two-dimensional self-avoiding walks on a cylinder. Phys. Rev. E 59, R16–R19 (1999)
24. 24.
Gilch, L.A., Müller, S.: Counting self-avoiding walks on free products of graphs. Discrete Math. 340, 325–332 (2017)
25. 25.
Grimmett, G.R.: Potts models and random-cluster processes with many-body interactions. J. Stat. Phys. 75, 67–121 (1994)
26. 26.
Grimmett, G.R.: Percolation, 2nd edn. Springer, Berlin (1999)
27. 27.
Grimmett, G.R.: The Random-Cluster Model. Springer, Berlin (2006). http://www.statslab.cam.ac.uk/~grg/books/rcm.html
28. 28.
Grimmett, G.R.: Three theorems in discrete random geometry. Probab. Surv. 8, 403–441 (2011)
29. 29.
Grimmett, G.R., Holroyd, A.E., Peres, Y.: Extendable self-avoiding walks. Ann. Inst. Henri Poincaré D 1, 61–75 (2014)
30. 30.
Grimmett, G.R., Li, Z.: Counting self-avoiding walks (2013). https://arxiv.org/abs/1304.7216
31. 31.
Grimmett, G.R., Li, Z.: Self-avoiding walks and the Fisher transformation. Electron. J. Comb. 20, 14 p. (2013). Paper 47Google Scholar
32. 32.
Grimmett, G.R., Li, Z.: Strict inequalities for connective constants of transitive graphs. SIAM J. Discrete Math. 28, 1306–1333 (2014)
33. 33.
Grimmett, G.R., Li, Z.: Bounds on the connective constants of regular graphs. Combinatorica 35, 279–294 (2015)
34. 34.
Grimmett, G.R., Li, Z.: Cubic graphs and the golden mean. Discret. Math. (2019)Google Scholar
35. 35.
Grimmett, G.R., Li, Z.: Connective constants and height functions for Cayley graphs. Trans. Am. Math. Soc. 369, 5961–5980 (2017)
36. 36.
Grimmett, G.R., Li, Z.: Self-avoiding walks and amenability. Electron. J. Comb. 24, 24 p. (2017). Paper P4.38Google Scholar
37. 37.
Grimmett, G.R., Li, Z.: Locality of connective constants. Discret. Math. 341, 3483–3497 (2018)
38. 38.
Grimmett, G.R., Li, Z.: Weighted self-avoiding walks. J. Algebraic Comb. (2019)Google Scholar
39. 39.
Guttmann, A.J., Parviainen, R., Rechnitzer, A.: Self-avoiding walks and trails on the $$3.12^2$$ lattice. J. Phys. A: Math. Gen. 38, 543–554 (2005)
40. 40.
Gwynne, E., Miller, J.: Convergence of the self-avoiding walk on random quadrangulations to SLE$$_{8/3}$$ on $$\sqrt{8/3}$$-Liouville quantum gravity (2016). https://arxiv.org/abs/1608.00956
41. 41.
Hammersley, J.M.: Percolation processes II. The connective constant. Proc. Camb. Phil. Soc. 53, 642–645 (1957)
42. 42.
Hammersley, J.M., Morton, W.: Poor man’s Monte Carlo. J. R. Stat. Soc. B 16, 23–38 (1954)
43. 43.
Hammersley, J.M., Welsh, D.J.A.: Further results on the rate of convergence to the connective constant of the hypercubical lattice. Q. J. Math. 13, 108–110 (1962)
44. 44.
Jensen, I.: A parallel algorithm for the enumeration of self-avoiding polygons on the square lattice. J. Phys. A: Math. Gen. 36, 5731–5745 (2003)
45. 45.
Jensen, I.: Improved lower bounds on the connective constants for two-dimensional self-avoiding walks. J. Phys. A: Math. Gen. 37, 11521–11529 (2004)
46. 46.
Jensen, I., Guttman, A.J.: Self-avoiding walks, neighbour-avoiding walks and trails on semiregular lattices. J. Phys. A: Math. Gen. 31, 8137–8145 (1998)
47. 47.
Kesten, H.: Full Banach mean values on countable groups. Math. Scand. 7, 146–156 (1959)
48. 48.
Kesten, H.: Symmetric random walks on groups. Trans. Am. Math. Soc. 92, 336–354 (1959)
49. 49.
Kesten, H.: On the number of self-avoiding walks. J. Math. Phys. 4, 960–969 (1963)
50. 50.
Lacoin, H.: Existence of a non-averaging regime for the self-avoiding walk on a high-dimensional infinite percolation cluster. J. Stat. Phys. 154, 1461–1482 (2014)
51. 51.
Lacoin, H.: Non-coincidence of quenched and annealed connective constants on the supercritical planar percolation cluster. Probab. Theory Relat. Fields 159, 777–808 (2014)
52. 52.
Lawler, G., Schramm, O., Werner, W.: On the scaling limit of planar self-avoiding walk. In: Proceedings of Symposium Pure Mathematics, vol. 72, pp. 339–364 (2004)Google Scholar
53. 53.
Li, Z.: Local statistics of realizable vertex models. Commun. Math. Phys. 304, 723–763 (2011)
54. 54.
Li, Z.: Critical temperature of periodic Ising models. Commun. Math. Phys. 315, 337–381 (2012)
55. 55.
Li, Z.: Positive speed self-avoiding walks on graphs with more than one end (2016). https://arxiv.org/abs/1612.02464
56. 56.
Lyons, R., Peres, Y.: Probability on Trees and Networks. Cambridge University Press, New York (2016). http://mypage.iu.edu/~rdlyons/
57. 57.
58. 58.
Madras, N., Wu, C.: Self-avoiding walks on hyperbolic graphs. Comb. Probab. Comput. 14, 523–548 (2005)
59. 59.
Martineau, S.: The set of connective constants of Cayley graphs contains a Cantor space. Electron. Comm. Probab. 22 (2017). Paper No. 12Google Scholar
60. 60.
Martineau, S., Tassion, V.: Locality of percolation for Abelian Cayley graphs. Ann. Probab. 45, 1247–1277 (2017)
61. 61.
Mohar, B.: Isoperimetric inequalities, growth, and spectrum of graphs. Lin. Alg. Appl. 103, 119–131 (1988)
62. 62.
Mohar, B.: Some relations between analytic and geometric properties of infinite graphs. Discret. Math. 95, 193–219 (1991). Directions in infinite graph theory and combinatorics, Cambridge (1989)
63. 63.
Nachmias, A., Peres, Y.: Non-amenable Cayley graphs of high girth have $$p_c < p_u$$ and mean-field exponents. Electron. Commun. Probab. 17, 1–8 (2012)
64. 64.
Neumann, J.v.: Zur allgemeinen Theorie des Masses. Fund. Math. 13, 73–116 (1929)Google Scholar
65. 65.
Nienhuis, B.: Exact critical points and critical exponents of $$\rm O$$($$n$$) models in two dimensions. Phys. Rev. Lett. 49, 1062–1065 (1982)
66. 66.
Orr, W.J.C.: Statistical treatment of polymer solutions at infinite dilution. Trans. Faraday Soc. 43, 12–27 (1947)
67. 67.
Pak, I., Smirnova-Nagnibeda, T.: On non-uniqueness of percolation on non-amenable Cayley graphs. Comptes Rendus de l’Académie des Sciences-Series I-Mathematics 33, 495–500 (2000)
68. 68.
Pönitz, A., Tittmann, P.: Improved upper bounds for self-avoiding walks on $$\mathbb{Z}^d$$. Electron. J. Comb. 7 (2000). Paper R21Google Scholar
69. 69.
Renault, D.: The vertex-transitive TLF-planar graphs. Discret. Math. 309, 2815–2833 (2009)
70. 70.
Schonmann, R.H.: Multiplicity of phase transitions and mean-field criticality on highly non-amenable graphs. Commun. Math. Phys. 219, 271–322 (2001)
71. 71.
Thom, A.: A remark about the spectral radius. Int. Math. Res. Notices 10, 2856–2864 (2015)
72. 72.
Woess, W.: Random Walks on Infinite Graphs and Groups. Cambridge University Press, Cambridge (2000)
73. 73.
Zeilberger, D.: Self-avoiding walks, the language of science, and Fibonacci numbers. J. Stat. Plann. Inference 54, 135–138 (1996)