Families of Markov chains with compatible symmetric-group actions

arXiv1810.08475MaRDI QIDQ6308484FDOQ6308484

Authors: Eric Ramos, Graham White 

Publication date: 19 October 2018

Abstract: For each $n,rgeq0$, let $KG(n,r)$ denote the Kneser Graph; that whose vertices are labeled by $r$-element subsets of $n$, and whose edges indicate that the corresponding subsets are disjoint. Fixing $r$ and allowing $n$ to vary, one obtains a family of nested graphs, each equipped with a natural action by a symmetric group $S_n$, such that these actions are compatible. Collections of graphs of this type are common in algebraic combinatorics and include families such as the Johnson Graphs, Crown Graphs and Rook Graphs. In previous work, the authors systematically studied families of this type using the language of representation stability and FI-modules. In that work, it is shown that such families of graphs exhibit a large variety of asymptotic regular behaviors. The present work applies the theory developed in that previous work, later refined in work of the authors and Speyer, to study random walks on the graphs of such families. We show that the moments of hitting times exhibit rational function behavior asymptotically. By consequence we conclude similar facts about the entries of the discrete Green's functions, as defined by Chung and Yau. Finally, we illustrate how the algebro-combinatorial structure of the graphs in these families give bounds on the mixing times of random walks on those graphs. We suggest some possible directions for future study, including of the appearance, or not, of the cut-off phenomenon, originally presented by Diaconis.

This page was built for publication: Families of Markov chains with compatible symmetric-group actions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6308484)