Christine E. Heitsch ; Prasad Tetali
-
Meander Graphs
dmtcs:2926 -
Discrete Mathematics & Theoretical Computer Science,
January 1, 2011,
DMTCS Proceedings vol. AO, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011)
-
https://doi.org/10.46298/dmtcs.2926
Meander GraphsArticle
Authors: Christine E. Heitsch 1; Prasad Tetali 1
NULL##NULL
Christine E. Heitsch;Prasad Tetali
1 School of Mathematics - Georgia Institute of Technology
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.
Information Inequalities and Combinatorial Applications; Funder: National Science Foundation; Code: 0701043
Bibliographic References
1 Document citing this article
Elizabeth Drellich;Heather C. Smith, Foundations for undergraduate research in mathematics, Folding Words Around Trees: Models Inspired by RNA, pp. 1-28, 2020, 10.1007/978-3-030-37853-0_1.