Cycle Counting and Character Expectations Using Alternating Structures
Formal Languages and Automata Theory
Summary
The authors build on previous work connecting the w-cycle theorem, which counts cycles in graphs related to words, with character expectations from word measures. They introduce new concepts called alternating stackings and alternating bislim structures that improve the original w-cycle theorem for many words. They show that most words can be analyzed using these new tools, which strengthens prior results and helps prove some conjectures about these word measures for generic cases. Although they prove three known conjectures for typical words, they also find exceptions for two of them.
w-cycle theoremword measuresstackingsbislim structuresalternating stackingsalternating bislim structurescharacter expectationsgeneric wordsconjectures in combinatorial group theory
Authors
Noam Ta Shma
Abstract
Recently, two related papers [arXiv:2412.13941, arXiv:2409.03626] found a connection between two subjects: the w-cycle theorem, which is a theorem about counting appearances of cycles reading out a word w in certain graphs, and character expectations on word measures. The w-cycle theorem was proven independently by [arXiv:1410.2540] using stackings and by [arXiv:1410.2579] using bislim structures. In the current work, we generalize stackings and bislim structures to alternating stackings and alternating bislim structures. We show how this significantly strengthens the w-cycle theorem for words admitting such alternating structures, and as a result, also strengthens the recent results of [arXiv:2412.13941] and [arXiv:2409.03626]. We show that generic words admit alternating bislim structures, and therefore, the strengthened results hold for generic words. Using our new machinery, we address conjectures of Wilton, of Hanany-Puder and of Puder-Shomroni. We prove that all three conjectures hold for generic words, but we also find counterexamples for the first two.