Random walks on Coxeter interchange graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908654954872832 |
|---|---|
| author | Buckland, Matthew Kolesnik, Brett Mitchell, Rivka Przybyłowski, Tomasz |
| author_facet | Buckland, Matthew Kolesnik, Brett Mitchell, Rivka Przybyłowski, Tomasz |
| contents | A tournament is an orientation of a graph. Vertices are players and edges are games, directed away from the winner. Kannan, Tetali and Vempala and McShine showed that tournaments with given score sequence can be rapidly sampled, via simple random walks on the interchange graphs of Brualdi and Li. These graphs are generated by the cyclically directed triangle, in the sense that traversing an edge corresponds to the reversal of such a triangle in a tournament.
We study Coxeter tournaments on Zaslavsky's signed graphs. These tournaments involve collaborative and solitaire games, as well as the usual competitive games. The interchange graphs are richer in complexity, as a variety of other generators are involved. We prove rapid mixing by an intricate application of Bubley and Dyer's method of path coupling, using a delicate re-weighting of the graph metric. Geometric connections with the Coxeter permutahedra introduced by Ardila, Castillo, Eur and Postnikov are discussed. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_17210 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Random walks on Coxeter interchange graphs Buckland, Matthew Kolesnik, Brett Mitchell, Rivka Przybyłowski, Tomasz Combinatorics Probability 05C20, 11P21, 17B22, 20F55, 51F15, 51M20, 52B05, 60J10, 62J15 A tournament is an orientation of a graph. Vertices are players and edges are games, directed away from the winner. Kannan, Tetali and Vempala and McShine showed that tournaments with given score sequence can be rapidly sampled, via simple random walks on the interchange graphs of Brualdi and Li. These graphs are generated by the cyclically directed triangle, in the sense that traversing an edge corresponds to the reversal of such a triangle in a tournament. We study Coxeter tournaments on Zaslavsky's signed graphs. These tournaments involve collaborative and solitaire games, as well as the usual competitive games. The interchange graphs are richer in complexity, as a variety of other generators are involved. We prove rapid mixing by an intricate application of Bubley and Dyer's method of path coupling, using a delicate re-weighting of the graph metric. Geometric connections with the Coxeter permutahedra introduced by Ardila, Castillo, Eur and Postnikov are discussed. |
| title | Random walks on Coxeter interchange graphs |
| topic | Combinatorics Probability 05C20, 11P21, 17B22, 20F55, 51F15, 51M20, 52B05, 60J10, 62J15 |
| url | https://arxiv.org/abs/2401.17210 |