<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 5 Issue 3" %>
Square Lattice Self-Avoiding Walks and Polygons
A.J. Guttmann1 and A.R. Conway2
1Department of Mathematics and Statistics, The University of Melbourne, Parkville, Victoria 3010, Australia
2Silicon Genetics, 2601 Spring Street, Redwood City, CA 94063, USA
Annals of Combinatorics 5 (3) p.319-345 September, 2001
AMS Subject Classification: 05A15
We give an algorithm for the enumeration of self-avoiding walks on the (anisotropic) square lattice. Application of the algorithm on a 1024 processor Intel Paragon supercomputer resulted in a 51 term series. For (isotropic) square lattice self-avoiding polygons, a related algorithm has produced a 90 term series. Careful analysis provides compelling evidence for simple rational values of the exponents in both the dominant and subdominant terms in the asymptotic form of the coefficients. We also advance compelling arguments --- but not a proof --- that the generating function for SAW is not differentiably finite. The corresponding result for SAP has recently been proved.
Keywords: enumeration, self-avoiding walks, polygons


1.  H.W.J. Blöte, T.W. Burkhardt, and I. Guim, Universality class of trails in two dimensions, J. Phys. A: Math. Gen. 30 (1997) 413每421.

2.  R. Brak, A.J. Guttmann, and S.G. Whittington, On the behaviour of collapsing linear and branched polymers, J. Math. Chem. 8 (1991) 255每268.

3.  J.L. Cardy and A.J. Guttmann, Universal amplitude combinations for self-avoiding walks, polygons and trails, J. Phys. A 26 (1993) 2485每2494.

4.  T.C. Choy, R.J. Fleming, and S.R. Shannon, Corrections to scaling in two-dimensional polymer statistics, Phys. Rev. B 53 (1996) 2175每2178.

5.  A.R. Conway and A.J. Guttmann, Algebraic techniques for enumerating self-avoiding walks on the square lattice, J. Phys. A: Math. Gen. 26 (1993) 1519每1534.

6.  A.R. Conway and A.J. Guttmann, Square lattice self-avoiding walks and corrections to scaling,Phys. Rev. Lett. 77 (1996) 5284每5287.

7.  I.G. Enting, Series expansions from the finite lattice method, J. Phys. A. 10 (1977) 801每805.

8.  I.G. Enting and A.J. Guttmann, Polygons on the square, L and Manhattan lattices, J. Phys. A: Math. Gen. 18 (1985) 1007每1017.

9.  I.G. Enting and A.J. Guttmann, The size and number of rings on the square lattice, J. Phys. A: Math. Gen. 21 (1988) L165每172.

10.  I.G. Enting and A.J. Guttmann, The number of convex polygons on the square and honeycomb lattices, J. Phys. A: Math. Gen. 21 (1988) L467每474.

11.  I.G. Enting and A.J. Guttmann, Polygons on the honeycomb lattice, J. Phys. A: Math. Gen. 22 (1989) 1371每1384.

12.  I.G. Enting and A.J. Guttmann, On the solvability of some statistical mechanical systems, Phys. Rev. Lett. 76 (1996) 344每347.

13.  I.G. Enting and A.J. Guttmann, unpublished.

14.  M.E. Fisher and M.F. Sykes, Excluded-volume problem and the Ising model of ferromagnetism, Phys. Rev. 114 (1959) 45每58.

15.  D.S. Gaunt, S.G. Whittington, and T.C. Yu, Free-energy of self-interacting uniform stars, J. Phys. A: Math. Gen. 30 (1997) 4607每4614.

16.  A.J. Guttmann, On two dimensional self-avoiding random walks, J. Phys. A: Math. Gen. 17 (1984) 455每468.

17.  A.J. Guttmann, On the critical behaviour of self-avoiding walks, J. Phys. A: Math. Gen. 20 (1987) 1839每1854.

18.  A.J. Guttmann, Asymptotic analysis of coefficients, In: Phase Transitions and Critical Phenomena, Vol. 13, C. Domb and J. Lebowitz, Eds., Academic Press, London, 1989, pp. 1每234.

19.  A.J. Guttmann, Indicators of solvability for lattice models, Discrete Math. 217 (2000) 167每 189.

20.  A.J. Guttmann, D.L. Hunter, N. Jan, S. Joseph, D. MacDonald, and L.L. Mosely, Selfavoiding walks on the simple-cubic lattice, J. Phys. A, 33 (2000) 5973每5983.

21.  A.J. Guttmann and I. Jensen, Self-avoiding polygons on the square lattice, J. Phys. A: Math. Gen. 32 (1999) 4867每4876.

22.  A.J. Guttmann, P.D. Roberts, M.F. Sykes, and M.G. Watts, The asymptotic behaviour of self-avoiding walks and returns on a lattice, J. Phys. A: Math. Gen. 5 (1972) 653每660.

23.  A.J. Guttmann and J.S. Wang, The extension of self-avoiding random walk series in 2 dimensions, J. Phys. A: Math. Gen. 24 (1991) 3107每3109.

24.  A.J. Guttmann and S.G. Whittington, Two-dimensional lattice embeddings of connected graphs of cyclomatic index two, J. Phys. A 11 (1978) 721每729.

25.  J.M. Hammersley, The number of polygons on a lattice, Proc. Camb. Phil. Soc. 57 (1961) 516每523.

26.  J.M. Hammersley and J.W. Morton, Poor Man*s Monte Carlo, J. Royal. Stat. Soc. Ser. B 16 (1954) 23每38.

27.  J.M. Hammersley and D.J.A.Welsh, Further results on the rate of convergence to the connective constant of the hypercubical lattice, Q. J. Math. (Oxford, 2nd series) 13 (1962) 108每110.

28.  T. Hara and G. Slade, Self-avoiding walk in five or more dimensions. I. The critical behaviour, Commun. Math. Phys. 147 (1992) 101每136.

29.  T. Hara and G. Slade, The lace expansion for self-avoiding walks in five or more dimensions, Rev. Math. Phys. 4 (1992) 235每327.

30.  T. Hara, G. Slade, and A.D. Sokal, New lower bounds on the self-avoiding walk connective constant, J. Stat. Phys. 72 (1993) 479每517.

31.  P.C. Hemmer and S. Hemmer, An average self-avoiding random walk on the square lattice lasts 71 steps, J. Chem. Phys. 81 (1984) 584每585.

32.  B.J. Hiley and M.F. Sykes, Probability of initial ring-closure in the restricted random walk of a macromolecule, J. Chem. Phys. 34 (1961) 1531每1537.

33.  E. Hille and R.S. Phillips, Functional Analysis and Semigroups, A.M.S. Colloq. Publ. 31, Providence, R.I.

34.  B.D. Hughes, Random walks and random environments, Vol. 1, Clarendon Press, Oxford, 1995.

35.  D.L. Hunter, N. Jan, K. Kelly, and D. MacDonald, Self-avoiding walks in two to five dimensions. Exact enumerations and series study, J. Phys A: Math. Gen. 25 (1992) 1429每1440.

36.  H. Kesten, On the number of self-avoiding walks, J. Math. Phys. 4 (1963) 960每969.

37.  H. Kesten, On the number of self-avoiding walks II, J. Math. Phys. 5 (1964) 1128每1137.

38.  R.S. Lehman and G.H. Weiss, A study of the restricted random walk, J. SIAM 6 (1958) 257每278.

39.  N. Madras, A rigorous bound on the critical exponent for the number of lattice trees, animals and polygons, J. Stat. Phys. 78 (1995) 681每699.

40.  N. Madras and G. Slade, The Self-Avoiding Walk, Birkhäuser, Boston每Basel每Berlin, 1993.

41.  J.P. Maffar, B. Masand, S. Redner, and U. Wilensky, An extension of the two-dimensional self-avoiding walk series on the square lattice, J. Phys. A: Math. Gen. 25 (1992) L365每369.

42.  B. Nienhuis, Exact critical points and critical exponents of O(n) models in two dimensions, Phys. Rev. Lett. 49 (1982) 1062每1065.

43.  G.L. O*Brien, Monotonicity of the number of self-avoiding walks, J. Stat. Phys. 59 (1990) 969每979.

44.  E. Orlandini, E.J.J. van Rensburg, M.C. Tesi, and S.G. Whittington, Interacting self-avoiding walks and polygons in three dimensions, J. Phys. A: Math. Gen. 29 (1996) 2451每2464.

45.  W.J.C. Orr, Statistical treatment of polymer solutions at infinite dilution, Trans. Faraday Soc. 43 (1947) 12每27.

46.  A. Rechnitzer, Some problems in the counting of lattice animals, polyominoes, polygons and walks, Ph.D. Thesis, The University of Melbourne, 2001.

47.  H. Saleur, Conformal invariance for polymers and percolation, J. Phys A: Math. Gen. 20 (1987) 455每470.

48.  C.E. Soteros and S.G. Whittington, Contacts in self-avoiding walks and polygons, J. Phys. A: Math. Gen. 34 (2001) 4009每4040.

49.  M.F. Sykes, Some counting theorems in the theory of the Ising model and the excluded volume problem, J. Math. Phys. 2 (1961) 52每62.