Patrón de permutación

En matemáticas combinatorias e informática teórica , un patrón de permutación (clásico) es una subpermutación de una permutación más larga . Cualquier permutación puede escribirse en notación de una línea como una secuencia de entradas que representan el resultado de aplicar la permutación a la secuencia 123...; por ejemplo, la secuencia 213 representa la permutación de tres elementos que intercambia los elementos 1 y 2. Si π y σ son dos permutaciones representadas de esta manera (estos nombres de variables son estándar para permutaciones y no están relacionados con el número pi ), entonces se dice que π contiene a σ como un patrón si alguna subsecuencia de las entradas de π tiene el mismo orden relativo que todas las entradas de σ.

Por ejemplo, la permutación π contiene el patrón 213 siempre que π tenga tres entradas x , y y z que aparecen dentro de π en el orden x ... y ... z pero cuyos valores están ordenados como y  < x < z , el mismo orden que los valores en la permutación 213.   

La permutación 32415 de cinco elementos contiene el patrón 213 de varias maneras diferentes: 3··15, ··415, 32··5, 324·· y ·2·15 forman tríos de entradas con el mismo orden que 213. Cabe destacar que las entradas no tienen por qué ser consecutivas. Cada una de las subsecuencias 315, 415, 325, 324 y 215 se denomina copia, instancia u ocurrencia del patrón. El hecho de que π contenga σ se expresa de forma más concisa como σ ≤ π.

Si una permutación π no contiene un patrón σ, se dice que π evita σ. La permutación 51342 evita 213; tiene diez subsecuencias de tres entradas, pero ninguna de estas diez subsecuencias tiene el mismo orden que 213.

Desde 2003 se celebra anualmente una conferencia internacional dedicada a los patrones de permutación y temas relacionados, denominada Permutation Patterns .

Se puede argumentar que Percy MacMahon ( 1915 ) fue el primero en demostrar un resultado en este campo con su estudio de las "permutaciones reticulares". ^{[ 1 ]} En particular, MacMahon muestra que las permutaciones que se pueden dividir en dos subsecuencias decrecientes (es decir, las permutaciones que evitan el 123) se cuentan mediante los números de Catalan . ^{[ 2 ]} 

Otro resultado inicial de gran importancia en el campo es el teorema de Erdős-Szekeres ; en lenguaje de patrones de permutación, el teorema establece que para cualesquiera enteros positivos a y b, toda permutación de longitud al menos ${\displaystyle (a-1)(b-1)+1}$debe contener el patrón${\displaystyle 1,2,3,\dots ,a}$o el patrón${\displaystyle b,b-1,\dots ,2,1}$.

El estudio de los patrones de permutación comenzó en serio con la consideración de Donald Knuth sobre la ordenación por pilas en 1968. ^{[ 3 ]} Knuth demostró que la permutación π puede ordenarse por una pila si y solo si π evita 231, y que las permutaciones ordenables por pilas se enumeran mediante los números de Catalan . ^{[ 4 ]} Knuth también planteó preguntas sobre la ordenación con deques . En particular, la pregunta de Knuth sobre cuántas permutaciones de n elementos se pueden obtener con el uso de un deque sigue abierta. ^{[ 5 ]} Poco después, Robert Tarjan ( 1972 ) investigó la ordenación por redes de pilas, ^{[ 6 ]} mientras que Vaughan Pratt ( 1973 ) demostró que la permutación π puede ser ordenada por una deque si y solo si para todo k , π evita 5,2,7,4,...,4 k +1,4 k − 2,3,4 k ,1, y 5,2,7,4,...,4 k +3,4 k ,1,4 k +2,3, y toda permutación que se pueda obtener de cualquiera de estas intercambiando los dos últimos elementos o el 1 y el 2. ^{[ 7 ]} Debido a que esta colección de permutaciones es infinita (de hecho, es el primer ejemplo publicado de una anticadena infinita de permutaciones), no está inmediatamente claro cuánto tiempo lleva decidir si una permutación puede ser ordenada por una deque. Rosenstiehl y Tarjan (1984) presentaron posteriormente un algoritmo de tiempo lineal (en la longitud de π) que determina si π puede ser ordenado por una cola doble. ^{[ 8 ]}  

En su artículo, Pratt comentó que este orden de patrones de permutación “parece ser el único orden parcial en permutación que surge de manera simple y natural” y concluye señalando que “desde un punto de vista abstracto”, el orden de patrones de permutación “es incluso más interesante que las redes que estábamos caracterizando”. ^{[ 7 ]}

Un objetivo destacado en el estudio de patrones de permutación es la enumeración de permutaciones que evitan una permutación fija (y típicamente corta) o un conjunto de permutaciones. Sea Av _n (B) el conjunto de permutaciones de longitud n que evitan todas las permutaciones en el conjunto B. (En el caso de que B sea un conjunto único, digamos { β }, se usa la abreviatura Av _n ( β ) en su lugar). Como se mencionó anteriormente, MacMahon y Knuth demostraron que |Av _n (123)| = |Av _n (231)| = C _n , el n- ésimo número de Catalan. Por lo tanto, estas son clases combinatorias isomorfas .

Simion y Schmidt (1985) fue el primer artículo que se centró exclusivamente en la enumeración. Entre otros resultados, Simion y Schmidt contaron permutaciones pares e impares que evitaban un patrón de longitud tres, contaron permutaciones que evitaban dos patrones de longitud tres y dieron la primera prueba biyectiva de que las permutaciones que evitan 123 y 231 son equinumerosas. ^{[ 9 ]} Desde su artículo, se han dado muchas otras biyecciones; véase Claesson y Kitaev (2008) para una revisión. ^{[ 10 ]}

En general, si |Av _n ( β )| = |Av _n ( σ )| para todo n , entonces se dice que β y σ son equivalentes de Wilf . Muchas equivalencias de Wilf se derivan del hecho trivial de que |Av _n ( β )| = |Av _n ( β ^{− 1} )| = |Av _n ( β ^rev )| para todo n , donde β ^{− 1} denota el inverso de β y β ^rev denota el reverso de β . (Estas dos operaciones generan el grupo diedral D ₈ con una acción natural sobre matrices de permutación ). Sin embargo, también hay numerosos ejemplos de equivalencias de Wilf no triviales (como la que existe entre 123 y 231):

• Stankova (1994) demostró que las permutaciones 1342 y 2413 son equivalentes de Wilf. ^{[ 11 ]}
• Stankova y West (2002) demostraron que para cualquier permutación β , las permutaciones 231 ⊕ β y 312 ⊕ β son equivalentes a Wilf, donde ⊕ denota la operación de suma directa . ^{[ 12 ]}
• Backelin, West y Xin (2007) demostraron que para cualquier permutación β y cualquier entero positivo m , las permutaciones 12... m ⊕ β y m ...21 ⊕ β son equivalentes a Wilf. ^{[ 13 ]}  

De estas dos equivalencias de Wilf y las simetrías inversa y reversa, se deduce que existen tres secuencias diferentes |Av _n ( β )| donde β tiene una longitud de cuatro:

A finales de la década de 1980, Richard Stanley y Herbert Wilf conjeturaron que para cada permutación β , existe una constante K tal que |Av _n ( β )| < K ⁿ . Esto se conoció como la conjetura de Stanley-Wilf hasta que fue demostrada por Adam Marcus y Gábor Tardos . ^{[ 16 ]}

Una clase de permutación , también conocida como clase de patrón (principalmente en trabajos antiguos) o simplemente clase de permutaciones, es un conjunto descendente en el orden de patrones de permutación. Cada clase se puede definir mediante las permutaciones mínimas que no se encuentran dentro de ella, su base . Así, la base para las permutaciones ordenables por pila es {231}, mientras que se sabe que la base para las permutaciones ordenables por cola doble es infinita. La función generadora de una clase es Σ x ^|π|, donde la suma se toma sobre todas las permutaciones π de la clase.

Como el conjunto de permutaciones bajo el orden de contención forma un poset , es natural preguntarse sobre su función de Möbius , un objetivo presentado explícitamente por primera vez por Wilf (2002) . ^{[ 17 ]} El objetivo en tales investigaciones es encontrar una fórmula para la función de Möbius de un intervalo [σ, π] en el poset de patrones de permutación que sea más eficiente que la definición recursiva ingenua. El primer resultado de este tipo fue establecido por Sagan y Vatter (2006) , quienes dieron una fórmula para la función de Möbius de un intervalo de permutaciones en capas . ^{[ 18 ]} Posteriormente, Burstein et al. (2011) generalizaron este resultado a intervalos de permutaciones separables . ^{[ 19 ]}

Se sabe que, asintóticamente, al menos el 39,95% de todas las permutaciones π de longitud n satisfacen μ(1, π)=0 (es decir, la función principal de Möbius es igual a cero), ^{[ 20 ]} pero para cada n existen permutaciones π tales que μ(1, π) es una función exponencial de n . ^{[ 21 ]}

Dada una permutación${\displaystyle \tau }$(llamado el texto ) de longitud${\displaystyle n}$y otra permutación${\displaystyle \pi }$de longitud${\displaystyle k}$(llamado patrón ), el problema de coincidencia de patrones de permutación (PPM) pregunta si${\displaystyle \pi }$está contenido en${\displaystyle \tau }$Cuando ambos${\displaystyle n}$y${\displaystyle k}$Se consideran variables, se sabe que el problema es NP-completo , y el problema de contar el número de tales coincidencias es #P-completo . ^{[ 22 ]} Sin embargo, PPM se puede resolver en tiempo lineal cuando k es una constante. De hecho, Guillemot y Marx ^{[ 23 ]} demostraron que PPM se puede resolver en tiempo${\displaystyle 2^{O(k^{2}\log k)}\cdot n}$, lo que significa que es tratable con parámetros fijos con respecto a${\displaystyle k}$.

Existen varias variantes del problema PPM, como lo analizan Bruner y Lackner. ^{[ 24 ]} Por ejemplo, si se requiere que la coincidencia consista en entradas contiguas, el problema se puede resolver en tiempo polinomial. ^{[ 25 ]} Se obtiene una variante natural diferente cuando el patrón se restringe a una clase de permutación propia.${\displaystyle {\mathcal {C}}}$Este problema se conoce como${\displaystyle {\mathcal {C}}}$-Patrón PPM y se demostró que es resoluble en tiempo polinomial para permutaciones separables . ^{[ 22 ]} Posteriormente, Jelínek y Kynčl ^{[ 26 ]} resolvieron completamente la complejidad de${\displaystyle {\mbox{Av}}(\sigma)}$-Patrón PPM demostrando que es resoluble en tiempo polinomial cuando${\displaystyle \sigma }$es igual a uno de 1, 12, 21, 132, 231, 312 o 213 y NP-completo en caso contrario.

Otra variante se da cuando tanto el patrón como el texto están restringidos a una clase de permutación adecuada.${\displaystyle {\mathcal {C}}}$, en cuyo caso el problema se llama${\displaystyle {\mathcal {C}}}$-PPM. Por ejemplo, Guillemot y Vialette ^{[ 27 ]} demostraron que${\displaystyle {\mbox{Av}}(321)}$-PPM podría resolverse en${\displaystyle O(k^{2}n^{6})}$tiempo. Albert , Lackner, Lackner y Vatter ^{[ 28 ]} posteriormente lo redujeron a${\displaystyle O(kn)}$y demostraron que el mismo límite se cumple para la clase de permutaciones fusionadas asimétricas . Además, preguntaron si el${\displaystyle {\mathcal {C}}}$-El problema PPM se puede resolver en tiempo polinomial para cada clase de permutación propia fija.${\displaystyle {\mathcal {C}}}$Esta pregunta fue respondida negativamente por Jelínek y Kynčl, quienes demostraron que${\displaystyle {\mbox{Av}}(4321)}$-PPM es de hecho NP-completo. ^{[ 26 ]} Más tarde, Jelínek, Opler y Pekárek ^{[ 29 ]} demostraron que${\displaystyle {\mbox{Av}}(\sigma)}$-PPM es NP-completo para cualquier${\displaystyle \sigma }$de longitud al menos 4 no simétrica a una de 3412, 3142, 4213, 4123 o 41352.

Se dice que la permutación π es β- óptima si ninguna permutación de la misma longitud que π tiene más copias de β. En su discurso ante la reunión de SIAM sobre Matemáticas Discretas en 1992, Wilf definió la densidad de empaquetamiento de la permutación β de longitud k como

${\displaystyle \lim _{n\rightarrow \infty }{\frac {{\text{número de copias de }}\beta {\text{ en una }}\beta {\text{-permutación óptima de longitud }}n}{\displaystyle {n \choose k}}}.}$

Un argumento no publicado de Fred Galvin muestra que la cantidad dentro de este límite no es creciente para n ≥ k , y por lo tanto el límite existe. Cuando β es monótono, su densidad de empaquetamiento es claramente 1, y las densidades de empaquetamiento son invariantes bajo el grupo de simetrías generado por inverso y reverso, por lo que para permutaciones de longitud tres, hay solo una densidad de empaquetamiento no trivial. Walter Stromquist (no publicado) resolvió este caso al mostrar que la densidad de empaquetamiento de 132 es 2 √ 3 − 3   , aproximadamente 0.46410.

Para permutaciones β de longitud cuatro, hay (debido a simetrías) siete casos a considerar:

Para las tres permutaciones desconocidas, existen límites y conjeturas. Price (1997) utilizó un algoritmo de aproximación que sugiere que la densidad de empaquetamiento de 1324 es alrededor de 0,244. ^{[ 30 ]} Birzhan Batkeyev (inédito) construyó una familia de permutaciones que muestra que la densidad de empaquetamiento de 1342 es al menos el producto de las densidades de empaquetamiento de 132 y 1432, aproximadamente 0,19658. Se conjetura que esta es la densidad de empaquetamiento precisa de 1342. Presutti y Stromquist (2010) proporcionaron un límite inferior para la densidad de empaquetamiento de 2413. Este límite inferior, que puede expresarse en términos de una integral, es aproximadamente 0,10474, y se conjetura que es la verdadera densidad de empaquetamiento. ^{[ 32 ]}

Un k - superpatrón es una permutación que contiene todas las permutaciones de longitud k . Por ejemplo, 25314 es un 3-superpatrón porque contiene todas las 6 permutaciones de longitud 3. Se sabe que ^los k -superpatrones deben tener una longitud de al menos k² ^/ e² , donde e ≈ 2,71828 es el número de Euler , ^{[ 33 ]} y que existen k -superpatrones de longitud ⌈( ^k² + 1 )/2⌉. ^{[ 34 ]} Se conjetura que este límite superior es el mejor posible, salvo términos de orden inferior. ^{[ 35 ]}   

El tipo de patrón definido anteriormente, en el que las entradas no necesitan aparecer consecutivamente, se denomina patrón clásico (de permutación). Si se requiere que las entradas sean consecutivas, entonces el patrón se denomina patrón consecutivo .

Existen varias formas en que se ha generalizado la noción de "patrón". Por ejemplo, un patrón vincular es una permutación que contiene guiones que indican qué pares adyacentes de entradas no tienen por qué aparecer consecutivamente. Por ejemplo, la permutación 314265 tiene dos copias del patrón punteado 2 − 31 − 4, dadas por las entradas 3426 y 3425. Para un patrón punteado β y cualquier permutación π, escribimos β(π) para el número de copias de β en π. Así, el número de inversiones en π es 2 − 1(π), mientras que el número de descensos es 21(π). Además, el número de valles en π es 213(π) + 312(π), mientras que el número de picos es 231(π) + 132(π). Estos patrones fueron introducidos por Babson y Steingrímsson (2000) , quienes demostraron que casi todas las estadísticas mahonianas conocidas podían expresarse en términos de permutaciones vinculares. ^{[ 36 ]} Por ejemplo, el índice Major de π es igual a 1 − 32(π) + 2 − 31(π) + 3 − 21(π) + 21(π).

Otra generalización es la de un patrón con barras , en el que algunas de las entradas están con barras. Para que π evite el patrón con barras β, significa que cada conjunto de entradas de π que forman una copia de las entradas sin barras de β puede extenderse para formar una copia de todas las entradas de β. West (1993) introdujo este tipo de patrones en su estudio de permutaciones que podían ordenarse pasándolas dos veces por una pila. ^{[ 37 ]} (Nótese que la definición de West de ordenar dos veces por una pila no es la misma que ordenar con dos pilas en serie). Otro ejemplo de patrones con barras aparece en el trabajo de Bousquet-Mélou y Butler (2007) , quienes demostraron que la variedad Schubert correspondiente a π es localmente factorial si y solo si π evita 1324 y 21 3 54. ^{[ 38 ]}

• PermLab: software para patrones de permutación , mantenido por Michael Albert .
• Base de datos de evitación de patrones de permutación , mantenida por Bridget Tenner .
• PermPAL: The Permutation Pattern Avoidance Library , una base de datos de teoremas derivados algorítmicamente sobre clases de permutaciones, mantenida por Christian Bean, Émile Nadeau, Jay Pantone y Henning Ulfarsson.