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 Connect in order to contact the contributor
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

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, ⟨10.46298/dmtcs.2926⟩. ⟨hal-01215076⟩

Share

Metrics

Record views

162

Files downloads

582