تقرير
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 |
| الوصف غير متاح. |