Counting Permutation Patterns with Multidimensional Trees

We consider the well-studied pattern counting problem: given a permutation π ∈ mathbbSn and an integer k > 1, count the number of order-isomorphic occurrences of every pattern τ ∈ mathbbSk in π. Our first result is an widetildeO(n2)-time algorithm for k=6 and k=7. The proof relies heavily on a new family of graphs that we introduce, called pattern-trees. Every such tree corresponds to an integer linear combination of permutations in mathbbSk, and is associated with linear extensions of partially ordered sets. We design an evaluation algorithm for these combinations, and apply it to a family of linearly-independent trees. For k=8, we show a barrier: the subspace spanned by trees in the previous family has dimension exactly |mathbbS8| - 1, one less than required. Our second result is an widetildeO(n7/4)-time algorithm for k=5. This algorithm extends the framework of pattern-trees by speeding-up their evaluation in certain cases. A key component of the proof is the introduction of pair-rectangle-trees, a data structure for dominance counting.