Weakly directed self-avoiding walks. (English) Zbl 1230.82027
Summary: We define a new family of self-avoiding walks (SAW) on the square lattice, called weakly directed walks. These walks have a simple characterization in terms of the irreducible bridges that compose them. We determine their generating function. This series has a complex singularity structure and in particular, is not D-finite. The growth constant is approximately 2.54 and is thus larger than that of all natural families of SAW enumerated so far (but smaller than that of general SAW, which is about 2.64). We also prove that the end-to-end distance of weakly directed walks grows linearly. Finally, we study a diagonal variant of this model.
MSC:
| 82B41 | Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics |
| 82B20 | Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics |
Keywords:
enumeration; self-avoiding walks; partially directed bridges; non-D-finite series; random generationReferences:
| [1] | Alm, S. E.; Janson, S., Random self-avoiding walks on one-dimensional lattices, Comm. Statist. Stoch. Models, 6, 2, 169-212 (1990) · Zbl 0702.60063 |
| [2] | A. Bacher, M. Bousquet-Mélou, Weakly directed self-avoiding walks, in: FPSAC 2010, DMTCS Proceedings, 2010, pp. 473-484.; A. Bacher, M. Bousquet-Mélou, Weakly directed self-avoiding walks, in: FPSAC 2010, DMTCS Proceedings, 2010, pp. 473-484. · Zbl 1374.05014 |
| [3] | Banderier, C.; Bousquet-Mélou, M.; Denise, A.; Flajolet, P.; Gardy, D.; Gouyou-Beauchamps, D., Generating functions for generating trees, Discrete Math., 246, 1-3, 29-55 (2002) · Zbl 0997.05007 |
| [4] | Bousquet-Mélou, M., Families of prudent self-avoiding walks, J. Combin. Theory Ser. A, 117, 3, 313-344 (2010) · Zbl 1228.05026 |
| [5] | Bousquet-Mélou, M.; Petkovšek, M., Linear recurrences with constant coefficients: the multivariate case, Discrete Math., 225, 1-3, 51-75 (2000) · Zbl 0963.05005 |
| [6] | Bousquet-Mélou, M.; Ponty, Y., Culminating paths, Discrete Math. Theor. Comput. Sci., 10, 2 (2008) · Zbl 1196.05007 |
| [7] | D. Brydges, G. Slade, Renormalisation group analysis of weakly self-avoiding walk in dimensions four and higher, in: Proceedings of the International Congress of Mathematicians, Hyderabad, India, 2010, arXiv:1003.4484; D. Brydges, G. Slade, Renormalisation group analysis of weakly self-avoiding walk in dimensions four and higher, in: Proceedings of the International Congress of Mathematicians, Hyderabad, India, 2010, arXiv:1003.4484 · Zbl 1230.82028 |
| [8] | de Gennes, P. G., Exponents for the excluded volume problem as derived by the Wilson method, Phys. Lett. A, 38, 5, 339-340 (1972) |
| [9] | Dethridge, J. C.; Guttmann, A. J., Prudent self-avoiding walks, Entropy, 8, 283-294 (2008) · Zbl 1179.82070 |
| [10] | E. Duchi, On some classes of prudent walks, in: FPSAC ʼ05, Taormina, Italy, 2005.; E. Duchi, On some classes of prudent walks, in: FPSAC ʼ05, Taormina, Italy, 2005. |
| [11] | Duchon, Ph.; Flajolet, Ph.; Louchard, G.; Schaeffer, G., Boltzmann samplers for the random generation of combinatorial structures, Combin. Probab. Comput., 13, 4-5, 577-625 (2004) · Zbl 1081.65007 |
| [12] | Duminil-Copin, H.; Smirnov, S., The connective constant of the honeycomb lattice equals \(\sqrt{2 + \sqrt{2}} (2010)\) · Zbl 1253.82012 |
| [13] | Duplantier, B.; Kostov, I. K., Geometrical critical phenomena on a random surface of arbitrary genus, Nuclear Phys. B, 340, 2-3, 491-541 (1990) |
| [14] | Flajolet, P.; Sedgewick, R., Analytic Combinatorics (2009), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1165.05001 |
| [15] | Foata, D., A noncommutative version of the matrix inversion formula, Adv. Math., 31, 330-349 (1979) · Zbl 0418.15004 |
| [16] | Guttmann, A. J.; Conway, A. R., Square lattice self-avoiding walks and polygons, Ann. Comb., 5, 3-4, 319-345 (2001) · Zbl 0988.05010 |
| [17] | Guttmann, A. J.; Wormald, N. C., On the number of spiral self-avoiding walks, J. Phys. A, 17, L271-L274 (1984) |
| [18] | 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. Oxf. II Ser., 13, 108-110 (1962) · Zbl 0123.00304 |
| [19] | Hopcroft, J. E.; Motwani, R.; Ullman, J. D., Introduction to Automata Theory, Languages and Computation (2006), Addison-Wesley |
| [20] | Jensen, I., Improved lower bounds on the connective constants for two-dimensional self-avoiding walks, J. Phys. A, 37, 48, 11521-11529 (2004) · Zbl 1063.82014 |
| [21] | Jensen, I.; Guttmann, A. J., Self-avoiding polygons on the square lattice, J. Phys. A, 32, 26, 4867-4876 (1999) · Zbl 0938.82019 |
| [22] | Kennedy, T., A faster implementation of the pivot algorithm for self-avoiding walks, J. Stat. Phys., 106, 3-4, 407-429 (2002) · Zbl 1001.82061 |
| [23] | Kesten, H., On the number of self-avoiding walks, J. Math. Phys., 4, 7, 960-969 (1963) · Zbl 0122.36502 |
| [24] | Lawler, G. F.; Schramm, O.; Werner, W., On the scaling limit of planar self-avoiding walk, (Fractal Geometry and Applications: A Jubilee of Benoît Mandelbrot, Part 2. Fractal Geometry and Applications: A Jubilee of Benoît Mandelbrot, Part 2, Proc. Sympos. Pure Math., vol. 72 (2004), Amer. Math. Soc.: Amer. Math. Soc. Providence, RI), 339-364 · Zbl 1069.60089 |
| [25] | Madras, N.; Slade, G., The Self-Avoiding Walk, Probab. Appl. (1993), Birkhäuser Boston Inc.: Birkhäuser Boston Inc. Boston, MA · Zbl 0780.60103 |
| [26] | Nienhuis, B., Exact critical point and critical exponents of \(O(n)\) models in two dimensions, Phys. Rev. Lett., 49, 15, 1062-1065 (1982) |
| [27] | Privman, V., Spiral self-avoiding walks, J. Phys. A, 16, 15, L571-L573 (1983) |
| [28] | Prodinger, H., The kernel method: a collection of examples, Sem. Lothar. Combin. (2003/2004), 50:Art. B50f, 19 pp. (electronic) · Zbl 1063.05011 |
| [29] | Rechnitzer, A.; van Rensburg, E. J. Janse, Canonical Monte Carlo determination of the connective constant of self-avoiding walks, J. Phys. A, 35, 42, L605-L612 (2002) · Zbl 1038.82034 |
| [30] | Stanley, R. P., Enumerative Combinatorics. Vol. 1, Cambridge Stud. Adv. Math., vol. 49 (1997), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0889.05001 |
| [31] | Viennot, X. G., Heaps of pieces, (I: Basic Definitions and Combinatorial Lemmas, vol. 1234/1986 (1986), Springer: Springer Berlin, Heidelberg), 321-350 · Zbl 0618.05008 |
| [32] | Zeilberger, D., Symbol-crunching with the transfer-matrix method in order to count skinny physical creatures, Integers (2000), pages A9, 34 pp. (electronic) · Zbl 0954.82006 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
