Approximate Counting of Permutation Patterns
Abstract
We consider the problem of counting the copies of a length-\(k\) pattern \(\sigma\) in a sequence \(f : [n] \to \mathbb{R}\), where a copy is a subset of indices \(i_1 \lt \dots \lt i_k \in [n]\) such that \(f(i_j) \lt f(i_\ell)\) if and only if \(\sigma(j) \lt \sigma(\ell)\). This problem is motivated by a range of connections and applications in ranking, nonparametric statistics, combinatorics, and fine-grained complexity, especially when \(k\) is a small fixed constant.
Fields of Study & Subjects
Limits and Structures in Graph Theory
Markov Chains and Monte Carlo Methods
Advanced Combinatorial Mathematics
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Pages
- 5914–5940
- Publication date
- 1 January 2026
- Language
- EN