Pattern matching in (213,231)-avoiding permutations

Original · EN

Given permutations σ∈ Sₖ and π∈ Sₙ with k<n, the pattern matching problem is to decide whether π matches σ as an order-isomorphic subsequence. We give a linear-time algorithm in case both π and σ avoid the two size-3 permutations 213 and 231. For the special case where only σ avoids 213 and 231, we present a O(max(kn²,n²((n))) time algorithm. We extend our research to bivincular patterns that avoid 213 and 231 and present a O(kn⁴) time algorithm. Finally we look at the related problem of the longest subsequence which avoids 213 and 231.