Decidability of parity and Wilf-equivalence for single forbidden permutations

About 11 years old · traced to

Let F\mathcal{F} and F′\mathcal{F}' be forbidden sets of permutation patterns with ∣F∣=∣F′∣=1|\mathcal{F}|=|\mathcal{F}'|=1. Single-permutation decidability conjecture. Both the parity problem for Cn(F)C_n(\mathcal{F}) and the Wilf-equivalence problem for Cn(F)C_n(\mathcal{F}) and Cn(F′)C_n(\mathcal{F}') are decidable. The paper presents this as a belief about a restricted case of the preceding open problems, in contrast with the conjectured undecidability for arbitrary finite forbidden sets.

References

Primary source

Scott Garrabrant and Igor Pak, “Pattern avoidance is not P-recursive”, arXiv:1505.06508 (2015).

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.