Families of prudent self-avoiding walks

Résumé : Un chemin auto-évitant sur le réseau carré est $\textit{prudent}$, s'il ne fait jamais un pas en direction d'un point qu'il a déjà visité. Préa est le premier à avoir cherché à énumérer ces chemins, en 1997. Pour 4 classes naturelles de chemins prudents, il donne un système de relations de récurrence, impliquant la longueur des chemins et plusieurs paramètres "catalytiques'' supplémentaires. La première classe a une série génératrice simple, rationnelle. La deuxième a une série algébrique (quadratique) (Duchi, FPSAC'05). Nous comptons ici les chemins de la troisième classe, et observons un saut de complexité: la série obtenue n'est ni algébrique, ni même différentiellement finie. La quatrième classe, celle des chemins prudents généraux, résiste encore. Cependant, nous définissons un modèle isotrope de chemins prudents sur réseau triangulaire, que nous résolvons de nouveau, la série obtenue n'est pas différentiellement finie. Nous étudions aussi la vitesse d'éloignement de ces chemins, et proposons des algorithmes de génération aléatoire.
Type de document :
Communication dans un congrès
Krattenthaler, Christian and Sagan, Bruce. 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008), 2008, Viña del Mar, Chile. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AJ, 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008), pp.167-180, 2008, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01185162
Contributeur : Coordination Episciences Iam <>
Soumis le : mercredi 19 août 2015 - 11:42:59
Dernière modification le : jeudi 11 janvier 2018 - 06:20:17
Document(s) archivé(s) le : vendredi 20 novembre 2015 - 10:33:33

Fichier

dmAJ0115.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01185162, version 1

Collections

Citation

Mireille Bousquet-Mélou. Families of prudent self-avoiding walks. Krattenthaler, Christian and Sagan, Bruce. 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008), 2008, Viña del Mar, Chile. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AJ, 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008), pp.167-180, 2008, DMTCS Proceedings. 〈hal-01185162〉

Partager

Métriques

Consultations de la notice

145

Téléchargements de fichiers

95