Griddings of permutations and hardness of pattern matching

We study the complexity of the decision problem known as Permutation Pattern Matching, or PPM. The input of PPM consists of a pair of permutations \(\tau\) (the ‘text’) and \(\pi\) (the ‘pattern’), and the goal is to decide whether \(\tau\) contains \(\pi\) as a subpermutation. On general inputs, PPM is known to be \(\mathsf{NP}\)-complete by a result of Bose, Buss and Lubiw. In this talk, we will focus on restricted instances of PPM where the text is assumed to avoid a fixed (small) pattern \(\sigma\); this restriction is known as \(\operatorname{Av}(\sigma)\)-PPM. It has been previously shown that \(\operatorname{Av}(\sigma)\)-PPM is polynomial for any \(\sigma\) of size at most \(3\), while it is \(\mathsf{NP}\)-hard for any \(\sigma\) containing a monotone subsequence of length four. We present a new hardness reduction which allows us to show, in a uniform way, that \(\operatorname{Av}(\sigma)\)-PPM is hard for every \(\sigma\) of size at least \(6\), for every \(\sigma\) of size \(5\) except the symmetry class of 41352, as well as for every \(\sigma\) symmetric to one of the three permutations 4321, 4312 and 4231. Moreover, assuming the exponential time hypothesis, none of these hard cases of \(\operatorname{Av}(\sigma)\)-PPM can be solved in time \(2^{o(n/\log n)}\).