DMTCS Proceedings, 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010)

Font Size:  Small  Medium  Large

Weakly directed self-avoiding walks

Axel Bacher, Mireille Bousquet-Mélou

Abstract


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.
Résumé. Nous définissons une nouvelle famille de chemins auto-évitants (CAE) sur le réseau carré, appelés chemins faiblement dirigés. Ces chemins ont une caractérisation simple en termes des ponts irréductibles qui les composent. Nous déterminons leur série génératrice. Cette série a une structure de singularités complexe et n'est en particulier pas D-finie. La constante de croissance est environ 2,54, ce qui est supérieur à toutes les familles naturelles de SAW étudiées jusqu'à présent, mais inférieur aux CAE généraux (dont la constante est environ 2,64). Nous prouvons également que la distance moyenne entre les extrémités du chemin croît linéairement. Enfin, nous étudions une variante diagonale du modèle.

Full Text: PostScript PDF

Valid XHTML 1.0 Transitional