← All problems

Subexponential pattern matching for permutations avoiding a fixed pattern

7 years old · traced to

Let tt be a text permutation of length nn, let π\pi be a pattern permutation, and let σ\sigma be an arbitrary permutation of length O(1)O(1). Suppose that π\pi avoids σ\sigma.

Fixed-pattern avoidance conjecture. The permutation pattern matching problem with text tt and pattern π\pi can be solved in time 2o(n)2^{o(n)}.

This conjecture would unify and generalize several subexponential algorithms for restricted families of permutations. The source states that characterizing the base c(π)c(\pi) of the Stanley–Wilf bound remains a deep open question, and presents this as a natural open direction.

References
  1. László Kozma, “Faster and simpler algorithms for finding large patterns in permutations”, arXiv:1902.08809 (2019).

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.