Polynomial mixing time of edge flips on quadrangulations
| Autor: | Caraceni, Alessandra, Stauffer, Alexandre |
|---|---|
| Rok vydání: | 2018 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | We establish the first polynomial upper bound for the mixing time of random edge flips on rooted quadrangulations: we show that the spectral gap of the edge flip Markov chain on quadrangulations with $n$ faces admits, up to constants, an upper bound of $n^{-5/4}$ and a lower bound of $n^{-11/2}$. In order to obtain the lower bound, we also consider a very natural Markov chain on plane trees (or, equivalently, on Dyck paths) and improve the previous lower bound for its spectral gap obtained by Shor and Movassagh. Comment: New version with the addition of Lemma 4.2 to Section 4 |
| Databáze: | arXiv |
| Externí odkaz: |
|