Families of Markov Chains with Compatible Symmetric-Group Actions
Eric Ramos, Graham White · SIAM Journal on Applied Algebra and Geometry · 2025
Abstract. For each [Formula: see text], let [Formula: see text] denote the Kneser graph, whose vertices are labeled by [Formula: see text]-element subsets of [Formula: see text] and whose edges indicate that the corresponding subsets are disjoint. Fixing [Formula: see text] and allowing [Formula: see text] to vary, one obtains a family of nested graphs, each equipped with a natural action by a symmetric group [Formula: see text] 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 [Formula: see text]-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 ].