Annals of Combinatorics 3 (1999) 357-384

A Pattern Theorem for Lattice Clusters

Neal Madras

Department of Mathematics and Statistics, York University, 4700 Keele St., Toronto,Ontario, M3J 1P3, Canada

Received Feburary 5, 1999

AMS Subject Classification: 82B41, 60K35, 82B43

Abstract. We consider general classes of lattice clusters, including various kinds of animals and trees on different lattices. We prove that if a given local configuration (``pattern'') of sites and bonds can occur in large clusters, then for some constant c>0, it occurs at least cn times in most clusters of size n. An analogous theorem for self-avoiding walks was proven in 1963 by Kesten [9]. We use the pattern theorem to prove the convergence of limn→∞an+1/an, where an is the number of clusters of size n, up to translation. The results also apply to weighted sums, and in particular, we can take an to be the probability that the percolation cluster containing the origin consists of exactly n sites. Another consequence is strict inequality of connective constants for sublattices and for certain subclasses of clusters.

Keywords: self-avoiding walk, lattice animal, percolation, pattern theorem, growth constant


1.  E.A. Bender, Z.-C. Gao, and L.B. Richmond, Submaps of maps. I. General 0--1 laws, J. Combin. Theory Ser. B 55 (1992) 104–117.

2.  J.W.S. Cassels, An Introduction to the Theory of Numbers, Springer-Verlag, Berlin, 1959.

3.  A.R. Conway, R. Brak, and A.J. Guttmann, Directed animals on two-dimensional lattices, J. Phys. A: Math. Gen. 26 (1993) 3085–3091.

4.  G. Grimmett, Percolation, Springer-Verlag, New York, 1989.

5.  J.M. Hammersley and K.W. Morton, Poor man's Monte Carlo, J. Roy. Stat. Soc. B 16 (1954) 23–38.

6.  T. Hara and G. Slade, The number and size of branched polymers in high dimensions, J. Stat. Phys. 67 (1992) 1009–1038.

7.  E.J. Janse van Rensburg and N. Madras, Metropolis Monte Carlo simulation of lattice animals, J. Phys. A: Math. Gen. 30 (1997) 8035–8066.

8.  E.J. Janse van Rensburg, E. Orlandini, D.W. Sumners, M.C. Tesi, and S.G. Whittington, Entanglement complexity of lattice ribbons, J. Stat. Phys. 85 (1996) 103–130.

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

10.  D.A. Klarner, Cell growth problems, Canad. J. Math. 19 (1967) 851–863.

11.  D.J. Klein, Rigorous results for branched polymers with excluded volume, J. Chem. Phys. 75 (1981) 5186–5189.

12.  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.

13.  N. Madras and G. Slade, The Self-Avoiding Walk, Birkhäuser, Boston, 1993.

14.  N. Madras, C.E. Soteros, and S.G. Whittington, Statistics of lattice animals, J. Phys. A: Math. Gen. 21 (1988) 4617–4635.

15.  N. Madras, C.E. Soteros, S.G. Whittington, J.L. Martin, M.F. Sykes, S. Flesia, and D.S. Gaunt, The free energy of a collapsing branched polymer, J. Phys. A: Math. Gen. 23 (1990) 5327–5350.

16.  C.E. Soteros and S.G. Whittington, Lattice animals: Rigorous results and wild guesses, In: Disorder in Physical Systems, G.R. Grimmett and D.J.A. Welsh, Eds., Oxford University Press, New York, 1990, pp. 323–335.

17.  E. Swierczak and A.J. Guttmann, Self-avoiding walks and polygons on non-Euclidean lattices, J. Phys. A: Math. Gen. 29 (1996) 7485–7500.

18.  C. Vanderzande, Lattice Models of Polymers, Cambridge University Press, Cambridge, 1998.

Get the DVI| PS | PDF file of this abstract.