DMTCS Proceedings, 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014)

Font Size:  Small  Medium  Large

Weakly prudent self-avoiding bridges

Axel Bacher, Nicholas R. Beaton

Abstract


We define and enumerate a new class of self-avoiding walks on the square lattice, which we call weakly prudent bridges. Their definition is inspired by two previously-considered classes of self-avoiding walks, and can be viewed as a combination of those two models. We consider several methods for recursively generating these objects, each with its own advantages and disadvantages, and use these methods to solve the generating function, obtain very long series, and randomly generate walks of arbitrary size. We find that the growth constant of these walks is approximately 2.58, which is larger than that of any previously-solved class of self-avoiding walks. &bigskip;
Résumé. Nous définissons et énumérons une nouvelle classe de chemins auto-évitants sur le réseau carré appelés ponts faiblement prudents. Leur définition est inspirée par deux classe précédemment étudiées et peut être vue comme une combinaison de ces deux modèles. Nous considérons plusieurs méthodes pour engendrer récursivement ces objets, chacune ayant ses avantages et désavantages, et utilisons ces méthodes pour déterminer la série génératrice, calculer un grand nombre de coefficients, et engendrer aléatoirement des chemins de taille arbitraire. Nous montrons que la constance de croissance de nos chemins est approximativement 2,58, ce qui est supérieur à celle des classes précédemment considérées.

Full Text: PostScript PDF

Valid XHTML 1.0 Transitional