Skip to Main content Skip to Navigation
Conference papers

Meander Graphs

Abstract : We consider a Markov chain Monte Carlo approach to the uniform sampling of meanders. Combinatorially, a meander $M = [A:B]$ is formed by two noncrossing perfect matchings, above $A$ and below $B$ the same endpoints, which form a single closed loop. We prove that meanders are connected under appropriate pairs of balanced local moves, one operating on $A$ and the other on $B$. We also prove that the subset of meanders with a fixed $B$ is connected under a suitable local move operating on an appropriately defined meandric triple in $A$. We provide diameter bounds under such moves, tight up to a (worst case) factor of two. The mixing times of the Markov chains remain open.
Complete list of metadata

Cited literature [23 references]  Display  Hide  Download

https://hal.inria.fr/hal-01215076
Contributor : Coordination Episciences Iam <>
Submitted on : Tuesday, October 13, 2015 - 3:06:16 PM
Last modification on : Wednesday, July 31, 2019 - 3:24:16 PM
Long-term archiving on: : Thursday, April 27, 2017 - 12:12:19 AM

File

dmAO0142.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01215076, version 1

Collections

Citation

Christine E. Heitsch, Prasad Tetali. Meander Graphs. 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), 2011, Reykjavik, Iceland. pp.469-480. ⟨hal-01215076⟩

Share

Metrics

Record views

246

Files downloads

1007