Evitando exactamente un patrón de permutación

Question

Deje $n \geq k$. Decimos que una permutación $\sigma \in S_n$ contiene una permutación (o "patrón") $\tau \in S_k$ si no es una subcadena de $k$ (no necesariamente consecutivos) elementos de la $\sigma$ pedido como $\tau$. Por ejemplo, la permutación $\sigma=24513$ contiene $132$, ya que la cadena de $243$ $\sigma$ tiene el mismo orden relativo en $132$.

Del mismo modo, contiene $123$ (la cadena $245$), $213$ (la cadena $213$), $231$ (la cadena de $451$) y $312$ (la cadena $513$). La única longitud-$3$ patrón no contiene es $321$.

Pregunta: Dada una permutación $\tau \in S_k$, es posible encontrar un valor de $n$ y una permutación $\sigma \in S_n$ tal que $\sigma$ contiene todos los patrones de longitud $k$ con la excepción de $\tau$?

Demasiado Ambicioso Generalización: Dada una permutación $\sigma \in S_n$$k \leq n$, vamos a $T_k(\sigma)$ ser el conjunto de patrones de longitud $k$$\sigma$. Por un entero $k$, lo que pone de patrones, posiblemente, puede aparecer como $T_k(\sigma)$ algunos $\sigma$?

Para un gran $k$, casi todos los subconjuntos de hacer no siempre ocurren como $T_k(\sigma)$. Una manera de ver esto: Por Erdős–Szekeres cada permutación con $n>(k-1)^2$ contiene $123\dots k$ o $k\dots 321$. Hay menos de $(k^2)!$ otras opciones para $\sigma$, cada uno de los cuales contiene en la mayoría de las $\binom{k^2}{k}$ patrones. Así que en la mayoría de los $\binom{k^2}{k} (k^2)!$ subconjuntos que contienen ni $123\dots k$ ni $k \dots 321$, aparecen siempre como un $T_k$, que es mucho menor que el número total de subconjuntos no contiene los dos patrones.

---

La primera pregunta que surgió de una discusión que tuve con un licenciado en informática estudiante acerca de la complejidad de la prueba para el patrón de contención. La mayoría de los trabajos que he visto en el patrón de evitar permutaciones se ha centrado más en la enumeración de ellos, y agradecería cualquier referencia a otros trabajos realizados en las relaciones entre los diversos patrón de contenedores.

Answer 1

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

La reclamación. Dado cualquier permutación $\tau\in S_k,$ podemos construir una permutación $\sigma\in S_n$ que contiene todos los patrones de longitud $k$ con la excepción de $\tau.$

Prueba. Sin pérdida de generalidad, suponemos que $\tau(1)\gt\tau(k).$

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

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

Definir $\sigma\in S_n$, de modo que cada uno de los conjuntos de $K_i$ es fijo por $\sigma,$ $\sigma|K_i$ da cuenta de que el patrón de $\pi_i.$

La permutación $\sigma$ claramente contiene cada uno de los patrones de $\pi_i;$ por otro lado, se sigue de la hipótesis de $\tau(1)\gt\tau(k)$ que $\sigma$ no contienen el patrón de $\tau.$

Ejemplo. Supongamos $\tau=(2,3,1),$ lo que significa que $\tau(1)=2,\tau(2)=3,\tau(3)=1.$
Entonces $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\},$ y $\sigma=(1,2,3,\ 4,6,5,\ 8,7,9,\ 12,10,11,\ 15,14,13).$

Observación. Por supuesto, esta construcción no producir el menor posible permutación $\sigma;$
en el ejemplo con $\tau=(2,3,1),$ que sería $\sigma=(4,1,3,2,5).$