Advertisement

Self-Avoiding Walks and Connective Constants

  • Geoffrey R. GrimmettEmail author
  • Zhongyang Li
Conference paper
  • 316 Downloads
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)MathSciNetCrossRefGoogle Scholar
  2. 2.
    Alm, S.E., Janson, S.: Random self-avoiding walks on one-dimensional lattices. Commun. Stat. Stoch. Models 6, 169–212 (1990)MathSciNetzbMATHCrossRefGoogle Scholar
  3. 3.
    Babai, L.: Vertex-transitive graphs and vertex-transitive maps. J. Graph Theory 15, 587–627 (1991)MathSciNetzbMATHCrossRefGoogle Scholar
  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)MathSciNetzbMATHCrossRefGoogle Scholar
  10. 10.
    Benjamini, I., Schramm, O.: Percolation beyond \(\mathbb{Z}^{d}\), many questions and a few answers. Electron. Commun. Probab. 1, 71–82 (1996)CrossRefMathSciNetzbMATHGoogle Scholar
  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)MathSciNetzbMATHCrossRefGoogle Scholar
  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)MathSciNetzbMATHCrossRefGoogle Scholar
  14. 14.
    Day, M.M.: Amenable semigroups. Illinois J. Math. 1, 509–544 (1957)MathSciNetzbMATHCrossRefGoogle Scholar
  15. 15.
    Diestel, R., Leader, I.: A conjecture concerning a limit of non-Cayley graphs. J. Alg. Comb. 14, 17–25 (2001)MathSciNetzbMATHCrossRefGoogle Scholar
  16. 16.
    Dodziuk, J.: Difference equations, isoperimetric inequality and transience of certain random walks. Trans. Am. Math. Soc. 284, 787–794 (1984)MathSciNetzbMATHCrossRefGoogle Scholar
  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)MathSciNetzbMATHCrossRefGoogle Scholar
  18. 18.
    Duminil-Copin, H., Hammond, A.: Self-avoiding walk is sub-ballistic. Commun. Math. Phys. 324, 401–423 (2013)MathSciNetzbMATHCrossRefGoogle Scholar
  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)CrossRefMathSciNetzbMATHGoogle Scholar
  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)MathSciNetzbMATHCrossRefGoogle Scholar
  21. 21.
    Fisher, M.E.: On the dimer solution of planar Ising models. J. Math. Phys. 7, 1776–1781 (1966)CrossRefGoogle Scholar
  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)CrossRefGoogle Scholar
  24. 24.
    Gilch, L.A., Müller, S.: Counting self-avoiding walks on free products of graphs. Discrete Math. 340, 325–332 (2017)MathSciNetzbMATHCrossRefGoogle Scholar
  25. 25.
    Grimmett, G.R.: Potts models and random-cluster processes with many-body interactions. J. Stat. Phys. 75, 67–121 (1994)MathSciNetzbMATHCrossRefGoogle Scholar
  26. 26.
    Grimmett, G.R.: Percolation, 2nd edn. Springer, Berlin (1999)zbMATHCrossRefGoogle Scholar
  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)MathSciNetzbMATHCrossRefGoogle Scholar
  29. 29.
    Grimmett, G.R., Holroyd, A.E., Peres, Y.: Extendable self-avoiding walks. Ann. Inst. Henri Poincaré D 1, 61–75 (2014)MathSciNetzbMATHCrossRefGoogle Scholar
  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)MathSciNetzbMATHCrossRefGoogle Scholar
  33. 33.
    Grimmett, G.R., Li, Z.: Bounds on the connective constants of regular graphs. Combinatorica 35, 279–294 (2015)MathSciNetzbMATHCrossRefGoogle Scholar
  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)MathSciNetzbMATHCrossRefGoogle Scholar
  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)MathSciNetzbMATHCrossRefGoogle Scholar
  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)CrossRefMathSciNetzbMATHGoogle Scholar
  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)MathSciNetzbMATHCrossRefGoogle Scholar
  42. 42.
    Hammersley, J.M., Morton, W.: Poor man’s Monte Carlo. J. R. Stat. Soc. B 16, 23–38 (1954)MathSciNetzbMATHGoogle Scholar
  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)MathSciNetzbMATHCrossRefGoogle Scholar
  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)MathSciNetCrossRefGoogle Scholar
  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)MathSciNetzbMATHCrossRefGoogle Scholar
  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)MathSciNetzbMATHCrossRefGoogle Scholar
  47. 47.
    Kesten, H.: Full Banach mean values on countable groups. Math. Scand. 7, 146–156 (1959)MathSciNetzbMATHCrossRefGoogle Scholar
  48. 48.
    Kesten, H.: Symmetric random walks on groups. Trans. Am. Math. Soc. 92, 336–354 (1959)MathSciNetzbMATHCrossRefGoogle Scholar
  49. 49.
    Kesten, H.: On the number of self-avoiding walks. J. Math. Phys. 4, 960–969 (1963)MathSciNetzbMATHCrossRefGoogle Scholar
  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)MathSciNetzbMATHCrossRefGoogle Scholar
  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)MathSciNetzbMATHCrossRefGoogle Scholar
  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)MathSciNetzbMATHCrossRefGoogle Scholar
  54. 54.
    Li, Z.: Critical temperature of periodic Ising models. Commun. Math. Phys. 315, 337–381 (2012)MathSciNetzbMATHCrossRefGoogle Scholar
  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.
    Madras, N., Slade, G.: Self-Avoiding Walks. Birkhäuser, Boston (1993)zbMATHGoogle Scholar
  58. 58.
    Madras, N., Wu, C.: Self-avoiding walks on hyperbolic graphs. Comb. Probab. Comput. 14, 523–548 (2005) MathSciNetzbMATHCrossRefGoogle Scholar
  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)MathSciNetzbMATHCrossRefGoogle Scholar
  61. 61.
    Mohar, B.: Isoperimetric inequalities, growth, and spectrum of graphs. Lin. Alg. Appl. 103, 119–131 (1988)MathSciNetzbMATHCrossRefGoogle Scholar
  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)MathSciNetzbMATHCrossRefGoogle Scholar
  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)CrossRefMathSciNetzbMATHGoogle Scholar
  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)CrossRefMathSciNetGoogle Scholar
  66. 66.
    Orr, W.J.C.: Statistical treatment of polymer solutions at infinite dilution. Trans. Faraday Soc. 43, 12–27 (1947)CrossRefGoogle Scholar
  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)zbMATHCrossRefGoogle Scholar
  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)MathSciNetzbMATHCrossRefGoogle Scholar
  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)MathSciNetzbMATHCrossRefGoogle Scholar
  71. 71.
    Thom, A.: A remark about the spectral radius. Int. Math. Res. Notices 10, 2856–2864 (2015)MathSciNetzbMATHGoogle Scholar
  72. 72.
    Woess, W.: Random Walks on Infinite Graphs and Groups. Cambridge University Press, Cambridge (2000)zbMATHCrossRefGoogle Scholar
  73. 73.
    Zeilberger, D.: Self-avoiding walks, the language of science, and Fibonacci numbers. J. Stat. Plann. Inference 54, 135–138 (1996)MathSciNetzbMATHCrossRefGoogle Scholar

Copyright information

© Springer Nature Singapore Pte Ltd. 2019

Authors and Affiliations

  1. 1.Statistical Laboratory, Centre for Mathematical SciencesCambridge UniversityCambridgeUK
  2. 2.Department of MathematicsUniversity of ConnecticutStorrsUSA

Personalised recommendations