DOAJ Open Access 2011

Meander Graphs

Christine E. Heitsch Prasad Tetali

Lihat Sumber DOI

Abstrak

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.

Topik & Kata Kunci

Mathematics

Penulis (2)

Christine E. Heitsch

Prasad Tetali

Format Sitasi

APA MLA BibTeX

Heitsch, C.E., Tetali, P. (2011). Meander Graphs. https://doi.org/10.46298/dmtcs.2926

Akses Cepat

Lihat di Sumber doi.org/10.46298/dmtcs.2926

Informasi Jurnal

Tahun Terbit: 2011
Sumber Database: DOAJ
DOI: 10.46298/dmtcs.2926
Akses: Open Access ✓