Meander Graphs
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 appropri...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2011-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/2926/pdf |
| _version_ | 1797270393027821568 |
|---|---|
| author | Christine E. Heitsch Prasad Tetali |
| author_facet | Christine E. Heitsch Prasad Tetali |
| author_sort | Christine E. Heitsch |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T02:03:33Z |
| format | Article |
| id | doaj.art-fd7eee7f0ea04f1180d1243aa6fb9ce6 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:03:33Z |
| publishDate | 2011-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-fd7eee7f0ea04f1180d1243aa6fb9ce62024-03-07T14:49:33ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502011-01-01DMTCS Proceedings vol. AO,...Proceedings10.46298/dmtcs.29262926Meander GraphsChristine E. Heitsch0Prasad Tetali1School of Mathematics - Georgia Institute of TechnologySchool of Mathematics - Georgia Institute of TechnologyWe 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.https://dmtcs.episciences.org/2926/pdfnoncrossing partitionsperfect matchingsmarkov chain monte carlocombinatorial enumeration[math.math-co] mathematics [math]/combinatorics [math.co][info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| spellingShingle | Christine E. Heitsch Prasad Tetali Meander Graphs Discrete Mathematics & Theoretical Computer Science noncrossing partitions perfect matchings markov chain monte carlo combinatorial enumeration [math.math-co] mathematics [math]/combinatorics [math.co] [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| title | Meander Graphs |
| title_full | Meander Graphs |
| title_fullStr | Meander Graphs |
| title_full_unstemmed | Meander Graphs |
| title_short | Meander Graphs |
| title_sort | meander graphs |
| topic | noncrossing partitions perfect matchings markov chain monte carlo combinatorial enumeration [math.math-co] mathematics [math]/combinatorics [math.co] [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| url | https://dmtcs.episciences.org/2926/pdf |
| work_keys_str_mv | AT christineeheitsch meandergraphs AT prasadtetali meandergraphs |