Permutación separable

Estructuración por bloques de la matriz de permutación (transpuesta) de la permutación separable (4,5,2,1,3,8,6,7) y el correspondiente árbol binario etiquetado; los colores indican la profundidad en el árbol.

En matemáticas combinatorias , una permutación separable es una permutación que se puede obtener de la permutación trivial 1 mediante sumas directas y sumas sesgadas . ^{[ 1 ]} Las permutaciones separables pueden caracterizarse por los patrones de permutación prohibidos 2413 y 3142; ^{[ 2 ]} también son las permutaciones cuyos grafos de permutación son cografos y las permutaciones que realizan los órdenes parciales serie-paralelo . Es posible comprobar en tiempo polinomial si una permutación separable dada es un patrón en una permutación mayor, o encontrar el subpatrón común más largo de dos permutaciones separables.

Bose, Buss y Lubiw (1998) definen una permutación separable como aquella que posee un árbol separador : un árbol binario con raíz en el que los elementos de la permutación aparecen (en orden de permutación) en las hojas del árbol, y en el que los descendientes de cada nodo del árbol forman un subconjunto contiguo de estos elementos. Cada nodo interior del árbol es un nodo positivo, en el que todos los descendientes del hijo izquierdo son menores que todos los descendientes del nodo derecho, o un nodo negativo, en el que todos los descendientes del nodo izquierdo son mayores que todos los descendientes del nodo derecho. Puede haber más de un árbol para una permutación dada: si dos nodos adyacentes en el mismo árbol tienen el mismo signo, pueden ser reemplazados por un par de nodos diferente mediante una operación de rotación de árbol .

Cada subárbol de un árbol separador puede interpretarse como una permutación separable más pequeña, cuyos valores de elementos están determinados por la forma y el patrón de signos del subárbol. Un árbol de un nodo representa la permutación trivial; un árbol cuyo nodo raíz es positivo representa la suma directa de las permutaciones dadas por sus dos subárboles hijos; y un árbol cuyo nodo raíz es negativo representa la suma asimétrica de las permutaciones dadas por sus dos subárboles hijos. De esta manera, un árbol separador es equivalente a la construcción de la permutación mediante sumas directas y asimétricas, partiendo de la permutación trivial.

Como demuestran Bose, Buss y Lubiw (1998) , las permutaciones separables también pueden caracterizarse en términos de patrones de permutación : una permutación es separable si y solo si no contiene ni 2413 ni 3142 como patrón. ^{[ 2 ]}

Las permutaciones separables también tienen una caracterización de la geometría algebraica : si una colección de polinomios reales distintos tienen todos valores iguales en algún número x , entonces la permutación que describe cómo cambia el orden numérico de los polinomios en x es separable, y toda permutación separable puede realizarse de esta manera. ^{[ 3 ]}

Las permutaciones separables se enumeran mediante los números de Schröder . Es decir, hay una permutación separable de longitud uno, dos de longitud dos, y en general el número de permutaciones separables de una longitud dada (comenzando con longitud uno) es

1, 2, 6, 22, 90, 394, 1806, 8558, .... (secuencia A006318 en el OEIS )

Este resultado fue demostrado para una clase de matrices de permutación equivalentes a las permutaciones separables por Shapiro y Stephens (1991) , utilizando una forma canónica del árbol de separación en la que el hijo derecho de cada nodo tiene un signo diferente al del propio nodo y aplicando luego la teoría de las funciones generadoras a estos árboles. Otra demostración, que se aplica más directamente a las permutaciones separables, fue dada por West (1995) . ^{[ 4 ]}

Bose, Buss y Lubiw (1998) demostraron que es posible determinar en tiempo polinomial si una permutación separable dada es un patrón en una permutación mayor, en contraste con el mismo problema para permutaciones no separables, que es NP-completo .

El problema de encontrar el patrón separable más largo que sea común a un conjunto de permutaciones de entrada puede resolverse en tiempo polinomial para un número fijo de permutaciones de entrada, pero es NP-difícil cuando el número de permutaciones de entrada puede ser variable, y sigue siendo NP-difícil incluso cuando las entradas son todas separables. ^{[ 5 ]}

Las permutaciones separables surgieron por primera vez en el trabajo de Avis y Newborn (1981) , quienes demostraron que son precisamente las permutaciones que pueden ordenarse mediante un número arbitrario de pilas de extracción en serie, donde una pila de extracción es una forma restringida de pila en la que cualquier operación de extracción extrae todos los elementos a la vez.

Shapiro y Stephens (1991) retomaron el estudio de las permutaciones separables en su análisis de la percolación bootstrap , un proceso en el que una matriz de permutación inicial se modifica cambiando repetidamente a uno cualquier coeficiente de la matriz que tenga dos o más vecinos ortogonales iguales a uno. Como demuestran, la clase de permutaciones que se transforman mediante este proceso en una matriz con todos los coeficientes iguales a uno es precisamente la clase de permutaciones separables.

El término "permutación separable" fue introducido posteriormente por Bose, Buss y Lubiw (1998) , quienes las consideraron por sus propiedades algorítmicas.

Cada permutación puede usarse para definir un grafo de permutación , un grafo cuyos vértices son los elementos de la permutación y cuyas aristas son las inversiones de la permutación. En el caso de una permutación separable, la estructura de este grafo se puede leer a partir del árbol de separación de la permutación: dos vértices del grafo son adyacentes si y solo si su ancestro común más bajo en el árbol de separación es negativo. Los grafos que se pueden formar a partir de árboles de esta manera se llaman cografos (abreviatura de grafos reducibles por complemento) y los árboles a partir de los cuales se forman se llaman coárboles. Por lo tanto, las permutaciones separables son precisamente las permutaciones cuyos grafos de permutación son cografos. ^{[ 6 ]} La caracterización de grafo prohibido de los cografos (son los grafos sin camino inducido de cuatro vértices ) corresponde a los dos patrones prohibidos de cuatro elementos de las permutaciones separables.

Las permutaciones separables también están estrechamente relacionadas con los órdenes parciales en serie-paralelo , los conjuntos parcialmente ordenados cuyos grafos de comparabilidad son los cografos. Al igual que los cografos y las permutaciones separables, los órdenes parciales en serie-paralelo también pueden caracterizarse por subórdenes prohibidos de cuatro elementos. Toda permutación define un orden parcial cuya dimensión de orden es dos, en el que los elementos a ordenar son los elementos de la permutación, y en el que x  ≤ y siempre que x tenga un valor numérico menor que y y esté a su izquierda en la permutación. Las permutaciones para las que este orden parcial es en serie-paralelo son precisamente las permutaciones separables. 

Las permutaciones separables también pueden usarse para describir particiones jerárquicas de rectángulos en rectángulos más pequeños (los llamados "planos de segmentación", utilizados, por ejemplo, en el diseño de circuitos integrados ) mediante el uso de los signos positivos y negativos del árbol de separación para describir cortes horizontales y verticales de un rectángulo en rectángulos más pequeños. ^{[ 7 ]}

Las permutaciones separables incluyen como caso especial las permutaciones ordenables por pila , que evitan el patrón 231.

• Ackerman, Eyal; Barequet, Gill; Pinter, Ron Y. (2006), "Una biyección entre permutaciones y planos de planta, y sus aplicaciones", Discrete Applied Mathematics , 154 (12): 1674– 1684, doi : 10.1016/j.dam.2006.03.018 , MR 2233287 
• Avis, David ; Newborn, Monroe (1981), "Sobre pilas de pop en series", Utilitas Mathematica , 19 : 129–140 , MR 0624050 .
• Bouvel, Mathilde; Rossin, Dominique; Vialette, Stéphane (2007), "Patrón separable común más largo entre permutaciones", Combinatorial Pattern Matching (CPM 2007) , Lecture Notes in Computer Science, vol.  4580, Springer, pp. 316–327 , doi : 10.1007/978-3-540-73437-6_32 , ISBN  978-3-540-73436-9.
• Bose, Prosenjit ; Buss, Jonathan; Lubiw, Anna (1998), "Pattern matching for permutations", Information Processing Letters , 65 (5): 277–283 , doi : 10.1016/S0020-0190(97)00209-3 , MR 1620935 .
• Ghys, Étienne (2017), Un paseo matemático singular , Lyon: ENS Éditions, arXiv : 1612.06373 , ISBN 978-2-84788-939-0, MR 3702027 
• Kitaev, Sergey (2011), "2.2.5 Permutaciones separables", Patrones en permutaciones y palabras , Monografías en Ciencias de la Computación Teórica. Una serie EATCS, Berlín: Springer-Verlag , pp. 57–66 , doi : 10.1007/978-3-642-17333-2 , ISBN  978-3-642-17332-5, Zbl 1257.68007 .
• Shapiro, Louis; Stephens, Arthur B. (1991), "Percolación bootstrap, los números de Schröder y el problema de los N -reyes", SIAM Journal on Discrete Mathematics , 4 (2): 275–280 , doi : 10.1137/0404025 , MR 1093199 .
• Szepieniec, AA; Otten, RHJM (1980), "El enfoque genealógico del problema de la maquetación", 17.ª Conferencia sobre Automatización del Diseño (DAC 1980) , págs. 535–542 , doi : 10.1145/800139.804582 , ISBN  0-89791-020-6, S2CID 2031785 .
• West, Julian (1995), "Generación de árboles y los números de Catalan y Schröder", Matemáticas Discretas , 146 ( 1–3 ): 247–262 , doi : 10.1016/0012-365X(94)00067-1 , MR 1360119 .