Families of Markov Chains with Compatible Symmetric-Group Actions\ast

For each n, r \geq 0, let KG(n, r) denote the Kneser graph, 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 \frakSn such that these actions are compatible. Collections of graphs of this type are common in algebraic combinatorics and include families such as Johnson graphs, crown graphs, and rook graphs. In previous work [RW], 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 [RW], later refined in [RSW], 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 considered by Chung and Yau [CY]. 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 cutoff phenomenon, originally presented by Aldous and Diaconis [AD] and Diaconis [D].