Parity problem for pattern-avoidance sequences
Parity problem for pattern-avoidance sequences
For a finite set of permutation patterns , let denote the number of permutations in avoiding all patterns in . Parity problem. The problem of deciding whether
for every is undecidable. The authors present this as an open problem extending their undecidability theorem and expect their methods may eventually prove it, although substantially more work is required.
Sources & referencesView supporting material
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
Sign in to submit a solution.
No solutions have been posted yet.