Counting Permutation Patterns with Multidimensional Trees
<|reference_start|>Counting Permutation Patterns with Multidimensional Trees: We consider the well-studied pattern counting problem: given a permutation $\pi \in \mathbb{S}_n$ and an integer $k > 1$, count the number of order-isomorphic occurrences of every pattern $\tau \in \mathbb{S}_k$ in $\pi$.   Our first result is an $\widetilde{\mathcal{O}}(n^2)$-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 $\mathbb{S}_k$, 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 $|\mathbb{S}_8| - 1$, one less than required.   Our second result is an $\widetilde{\mathcal{O}}(n^{7/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.<|reference_end|>
@article{beniamini2024counting,
    title={Counting Permutation Patterns with Multidimensional Trees},
    author={Gal Beniamini, Nir Lavee},
    journal={arXiv preprint arXiv:2407.04971},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.04971},
    primaryClass={cs.DS math.CO}
}