Meander Graphs

Résumé : Nous considérons une approche de Monte Carlo par chaîne de Markov pour l'échantillonnage uniforme des méandres. Combinatoirement, un méandre $M = [A : B]$ est constitué par deux couplages (matchings) parfaits sans intersection $A$ et $B$, définis sur le même ensemble de points alignés, et qui forment une boucle fermée simple lorsqu'on dessine $A$ "vers le haut'' et $B$ "vers le bas''. Nous montrons que les méandres sont connectés sous l'action de paires appropriées de mouvements locaux équilibrés, l'un opérant sur $A$ et l'autre sur $B$. Nous montrons également que le sous-ensemble de méandres avec un $B$ fixe est connecté sous l'action de mouvements locaux définis sur des "triplets méandriques'' de $A$. Nous fournissons des bornes sur les diamètres pour de tels mouvements, exactes à un facteur 2 près (dans le pire des cas). Les temps de mélange des chaînes de Markov demeurent une question ouverte.
Type de document :
Communication dans un congrès
Bousquet-Mélou, Mireille and Wachs, Michelle and Hultman, Axel. 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), 2011, Reykjavik, Iceland. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AO, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), pp.469-480, 2011, DMTCS Proceedings
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01215076
Contributeur : Coordination Episciences Iam <>
Soumis le : mardi 13 octobre 2015 - 15:06:16
Dernière modification le : mardi 7 mars 2017 - 15:13:10
Document(s) archivé(s) le : jeudi 27 avril 2017 - 00:12:19

Fichier

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

Identifiants

  • HAL Id : hal-01215076, version 1

Collections

Citation

Christine E. Heitsch, Prasad Tetali. Meander Graphs. Bousquet-Mélou, Mireille and Wachs, Michelle and Hultman, Axel. 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), 2011, Reykjavik, Iceland. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AO, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), pp.469-480, 2011, DMTCS Proceedings. 〈hal-01215076〉

Partager

Métriques

Consultations de la notice

86

Téléchargements de fichiers

128