تقرير
Counting Permutation Patterns with Multidimensional Trees
العنوان: | Counting Permutation Patterns with Multidimensional Trees |
---|---|
المؤلفون: | Beniamini, Gal, Lavee, Nir |
سنة النشر: | 2024 |
المجموعة: | Computer Science Mathematics |
مصطلحات موضوعية: | Computer Science - Data Structures and Algorithms, Mathematics - Combinatorics |
الوصف: | 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. |
نوع الوثيقة: | Working Paper |
URL الوصول: | http://arxiv.org/abs/2407.04971 |
رقم الأكسشن: | edsarx.2407.04971 |
قاعدة البيانات: | arXiv |
الوصف غير متاح. |