Decidability of parity and Wilf-equivalence for single forbidden permutations

From papers

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.

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

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

Solutions 0

No solutions have been posted yet.