Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Weakly directed self ...
Conference paper

Weakly directed self-avoiding walks

Axel Bacher (1), Mireille Bousquet-Mélou ORCID (1) (2)
(1) Laboratoire Bordelais de Recherche en Informatique
(2) Centre National de la Recherche Scientifique
Download article
Open on HAL
Imported on
January 31, 2017
Published on
December 31, 2009
Last modified on
March 31, 2025
Volume
DMTCS Proceedings vol. AN, 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010)
Proceedings
DOI
10.46298/dmtcs.2883
License
https://about.hal.science/hal-authorisation-v1
Indicators
564
Views
689
Downloads

Weakly directed self-avoiding walks

Axel Bacher (1), Mireille Bousquet-Mélou ORCID (1) (2)
(1) Laboratoire Bordelais de Recherche en Informatique
(2) Centre National de la Recherche Scientifique
Abstract
English
We define a new family of self-avoiding walks (SAW) on the square lattice, called $\textit{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.
French
Nous définissons une nouvelle famille de chemins auto-évitants (CAE) sur le réseau carré, appelés $\textit{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é 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.
Keywords
  • [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • Enumeration
  • Self-avoiding walks
Cited by

Source: OpenCitations

  • Weakly directed self-avoiding walks

    Journal of Combinatorial Theory Series A

    Authors : Axel Bacher, Mireille Bousquet-Mélou ORCID

    Journal reference : Volume 118, 2011, pp. 2365-2391

    DOI : 10.1016/j.jcta.2011.06.001
Preview
Loading PDF preview...