Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2408.05611 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _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 |