Mixing on Generalized Associahedra
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913465250086912 |
|---|---|
| author | Chang, William Defant, Colin Frishberg, Daniel |
| author_facet | Chang, William Defant, Colin Frishberg, Daniel |
| contents | Eppstein and Frishberg recently proved that the mixing time for the simple random walk on the $1$-skeleton of the associahedron is $O(n^3\log^3 n)$. We obtain similar rapid mixing results for the simple random walks on the $1$-skeleta of the type-$B$ and type-$D$ associahedra. We adapt Eppstein and Frishberg's technique to obtain the same bound of $O(n^3\log^3 n)$ in type $B$ and a bound of $O(n^{13} \log^2 n)$ in type $D$; in the process, we establish an expansion bound that is tight up to logarithmic factors in type $B$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_05611 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Mixing on Generalized Associahedra Chang, William Defant, Colin Frishberg, Daniel Combinatorics Data Structures and Algorithms Probability Eppstein and Frishberg recently proved that the mixing time for the simple random walk on the $1$-skeleton of the associahedron is $O(n^3\log^3 n)$. We obtain similar rapid mixing results for the simple random walks on the $1$-skeleta of the type-$B$ and type-$D$ associahedra. We adapt Eppstein and Frishberg's technique to obtain the same bound of $O(n^3\log^3 n)$ in type $B$ and a bound of $O(n^{13} \log^2 n)$ in type $D$; in the process, we establish an expansion bound that is tight up to logarithmic factors in type $B$. |
| title | Mixing on Generalized Associahedra |
| topic | Combinatorics Data Structures and Algorithms Probability |
| url | https://arxiv.org/abs/2408.05611 |