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.
Best Answer
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).$