Alternating Stackings and Word Measures

Let Γ be a labeled and directed graph. The w-cycle theorem bounds the number of cycles which are labeled by a word w in Γ. Louder and Wilton (2017) proved the w-cycle theorem using a combinatorial object they called a stacking. We generalize stackings to k-alternating stackings, sketch Louder and Wilton's proof, and show that k-alternating stackings give stronger bounds.

 

Given a word w, its word measure is a distribution on S_n given by w(σ _1, ... , σ_r) where σ_1, ... , σ_r are uniformly random permutations, e.g., for w=[x, y] its measure is a random commutator w(σ, τ) = [σ, τ]. Given a character χ of S_n, we ask what is its expectation over the word measure, i.e., the expectation of χ(w(σ_1, ... , σ_r)).  Cassidy (2024) bounded the expectation using stackings. We extend Cassidy's method with k-alternating stackings, proving that a conjecture of Hannani and Puder (2020) holds with high probability.