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

Less than 1 year old · traced to

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−πi∣≤m}.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 m≥1m\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.

References

Primary source

Nathaniel Nadler, “On 132-Avoiding Permutations with an Adjacency Constraint”, arXiv:2604.22135 (2026).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.