7
$\begingroup$

Let $n \geq k$. We say that a permutation $\sigma \in S_n$ contains a permutation (or "pattern") $\tau \in S_k$ if there is a substring of $k$ (not necessarily consecutive) elements of $\sigma$ ordered like $\tau$. For example, the permutation $\sigma=24513$ contains $132$, since the string $243$ in $\sigma$ has the same relative order as $132$.

Similarly, it contains $123$ (the string $245$), $213$ (the string $213$), $231$ (the string $451$) and $312$ (the string $513$). The only length-$3$ pattern it does not contain is $321$.

Question: Given a permutation $\tau \in S_k$, is it possible to find a value of $n$ and a permutation $\sigma \in S_n$ such that $\sigma$ contains every pattern of length $k$ except $\tau$?

Overly Ambitious Generalization: Given a permutation $\sigma \in S_n$ and a $k \leq n$, let $T_k(\sigma)$ be the set of patterns of length $k$ contained in $\sigma$. For a fixed integer $k$, what sets of patterns can possibly appear as $T_k(\sigma)$ for some $\sigma$?

For large $k$, almost all subsets do not ever occur as a $T_k(\sigma)$. One way to see this: By Erdős–Szekeres every permutation with $n>(k-1)^2$ contains either $123\dots k$ or $k\dots 321$. There's less than $(k^2)!$ other choices for $\sigma$, each of which contains at most $\binom{k^2}{k}$ patterns. So at most $\binom{k^2}{k} (k^2)!$ subsets containing neither $123\dots k$ nor $k \dots 321$ ever appear as a $T_k$, which is much smaller than the total number of subsets not containing those two patterns.


The first question arose out of a discussion I had with a computer science graduate student about the complexity of testing for pattern containment. Most of the work I've seen on pattern-avoiding permutations has focused more on enumerating them, and I'd appreciate any references to other work done on relationships between various pattern containments.

$\endgroup$
  • 1
    $\begingroup$ Very interesting question. I do not know if it has been studied. Here is a paper that gives a construction of a $\sigma \in S_n$ containing every $\tau \in S_k$, for relatively small $n$. You could see if this construction can be modified to avoid one specific $\tau$ while leaving the others, but this could be hard. I have not read it myself. $\endgroup$ – Jair Taylor Aug 27 '18 at 2:45
5
+100
$\begingroup$

Let $k\ge2,\ m=k!-1,\ n=km=k(k!-1).$

Claim. Given any permutation $\tau\in S_k,$ we can construct a permutation $\sigma\in S_n$ which contains every pattern of length $k$ except $\tau.$

Proof. Without loss of generality, we assume that $\tau(1)\gt\tau(k).$

Let $S_k\setminus\{\tau\}=\{\pi_1,\pi_2,\dots,\pi_m\}.$

Write $\{1,2,\dots,n\}=K_1\cup K_2\cup\cdots\cup K_m,$ where $K_i=\{(i-1)k+1,(i-1)k+2,\dots,(i-1)k+k\}.$

Define $\sigma\in S_n$ so that each of the sets $K_i$ is fixed by $\sigma,$ and $\sigma|K_i$ realizes the pattern $\pi_i.$

The permutation $\sigma$ clearly contains each of the patterns $\pi_i;$ on the other hand, it follows from the assumption $\tau(1)\gt\tau(k)$ that $\sigma$ does not contain the pattern $\tau.$

Example. Suppose $\tau=(2,3,1),$ meaning that $\tau(1)=2,\tau(2)=3,\tau(3)=1.$
Then $k=3,m=5,n=15,$ $S_3\setminus\{\tau\}=\{\pi_1,\pi_2,\pi_3,\pi_4,\pi_5\}=\{(1,2,3),(1,3,2),(2,1,3),(3,1,2),(3,2,1)\},$ $K_1=\{1,2,3\},K_2=\{4,5,6\},K_3=\{7,8,9\},K_4=\{10,11,12\},K_5=\{13,14,15\},$ and $\sigma=(1,2,3,\ 4,6,5,\ 8,7,9,\ 12,10,11,\ 15,14,13).$

Remark. Of course this construction does not produce the shortest possible permutation $\sigma;$
in the example with $\tau=(2,3,1),$ that would be $\sigma=(4,1,3,2,5).$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.