Finite-state structure conjecture for 132-avoiding permutations with bounded adjacency

From papers

Let SnS_n be the symmetric group, and let An(m)A_n^{(m)} be the class

An(m)={πSn:π avoids 132 and πi+1πim}.A_n^{(m)} = \{\pi \in S_n: \pi \text{ avoids } 132 \text{ and } |\pi_{i+1}-\pi_i| \le m\}.

Here, mm is a fixed integer with m1m\geq 1. Finite-state structure conjecture. The class An(m)A_n^{(m)} 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 {An(m)}\{A_n^{(m)}\} and a rational generating function. The conjecture is motivated by the complete structural analysis for m=2m=2, 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

No solutions have been posted yet.