Given a permutation σ, what is the maximum number of copies of σ that a permutation on n symbols may contain

Definitions and mathematical statement

Let $\sigma\in S_k$ be a fixed permutation, where $S_k$ denotes the permutations of $\{1,\ldots,k\}$. An occurrence of $\sigma$ in $\pi\in S_n$ is an increasing index sequence $1\le i_1<\cdots<i_k\le n$ such that \[ \pi(i_a)<\pi(i_b)\quad\Longleftrightarrow\quad \sigma(a)<\sigma(b) \qquad(1\le a,b\le k). \] Let $\operatorname{occ}_\sigma(\pi)$ count these index sets and put \[ M_\sigma(n)=\max_{\pi\in S_n}\operatorname{occ}_\sigma(\pi), \qquad d_\sigma(n)=\frac{M_\sigma(n)}{\binom nk} \quad(n\ge k). \] Determine the extremal function $M_\sigma(n)$ for general prescribed patterns, including its leading asymptotic behavior and the structure of permutations attaining or approaching the maximum. The limiting normalized value is the packing density of the pattern; identifying its value is part of the general problem.

Occurrences may overlap in positions, and the selected positions need not be consecutive. Thus this is classical pattern packing, not the packing of disjoint blocks or consecutive patterns. The normalization counts all possible $k$-subsets of positions, so its value lies in $[0,1]$. The pattern $\sigma$ remains fixed as $n$ grows, and answers can depend strongly on its order structure; a formula for one pattern need not extend to every pattern.

Short English statement

For a prescribed permutation pattern, determine the largest possible number of its occurrences and its asymptotic packing density.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3100032 (AMR-030-0032), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Cooper - Combinatorial Problems I Like (2020 snapshot), Permutations, source-order bullet 32. Original source indexed by AMR-030-0032. https://people.math.sc.edu/cooper/combprob.html.