Finite-state structure conjecture for 132-avoiding permutations with bounded adjacency
Finite-state structure conjecture for 132-avoiding permutations with bounded adjacency
Let be the symmetric group, and let be the class
Here, is a fixed integer with . Finite-state structure conjecture. The class admits a finite structural decomposition into a bounded collection of states determined by the local configuration near the beginning of the permutation. Transitions between these states depend only on this local information.
If true, the class would admit a finite transition-system description, implying a linear recurrence with constant coefficients for and a rational generating function. The conjecture is motivated by the complete structural analysis for , but no general proof is supplied.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Nathaniel Nadler, “On 132-Avoiding Permutations with an Adjacency Constraint”, arXiv:2604.22135 (2026).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.