Mireille Bousquet-Mélou - Families of prudent self-avoiding walks

dmtcs:3627 - Discrete Mathematics & Theoretical Computer Science, January 1, 2008, DMTCS Proceedings vol. AJ, 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008) - https://doi.org/10.46298/dmtcs.3627
Families of prudent self-avoiding walks

Authors: Mireille Bousquet-Mélou ORCID-iD1

  • 1 Laboratoire Bordelais de Recherche en Informatique

A self-avoiding walk on the square lattice is $\textit{prudent}$, if it never takes a step towards a vertex it has already visited. Préa was the first to address the enumeration of these walks, in 1997. For 4 natural classes of prudent walks, he wrote a system of recurrence relations, involving the length of the walks and some additional "catalytic'' parameters. The generating function of the first class is easily seen to be rational. The second class was proved to have an algebraic (quadratic) generating function by Duchi (FPSAC'05). Here, we solve exactly the third class, which turns out to be much more complex: its generating function is not algebraic, nor even $D$-finite. The fourth class ―- general prudent walks ―- still defeats us. However, we design an isotropic family of prudent walks on the triangular lattice, which we count exactly. Again, the generating function is proved to be non-$D$-finite. We also study the end-to-end distance of these walks and provide random generation procedures.


Volume: DMTCS Proceedings vol. AJ, 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008)
Section: Proceedings
Published on: January 1, 2008
Imported on: May 10, 2017
Keywords: enumeration,self-avoiding walks,$D$-finite generating functions,[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo ARXIV 1302.2796
Source : ScholeXplorer IsRelatedTo DOI 10.1088/1751-8113/46/23/235001
Source : ScholeXplorer IsRelatedTo DOI 10.48550/arxiv.1302.2796
  • 10.48550/arxiv.1302.2796
  • 10.1088/1751-8113/46/23/235001
  • 10.1088/1751-8113/46/23/235001
  • 1302.2796
Endless self-avoiding walks

1 Document citing this article

Consultation statistics

This page has been seen 467 times.
This article's PDF has been downloaded 136 times.