En matemática combinatoria , una permutación separable es una permutación que puede obtenerse 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] son también las permutaciones cuyas gráficas de permutación son cografías y las permutaciones que realizan los órdenes parciales serie-paralelos . Es posible probar en tiempo polinomial si una permutación separable dada es un patrón en una permutación mayor, o para encontrar el subpatrón común más largo de dos permutaciones separables.
Definición y caracterización
Bose, Buss y Lubiw (1998) definen una permutación separable como una permutación que tiene un árbol separador : un árbol binario enraizado en el que los elementos de la permutación aparecen (en orden de permutación) en las hojas del árbol, y en el que el 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 más pequeños 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 determinada permutación: si dos nodos adyacentes en el mismo árbol tienen el mismo signo, entonces pueden ser reemplazados por un par de nodos diferente usando una operación de rotación de árbol .
Cada subárbol de un árbol de separación puede interpretarse como si representara una permutación separable más pequeña, cuyos valores de elemento están determinados por la forma y el patrón de signo 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 permutaciones dadas por sus dos subárboles secundarios, y un árbol cuyo nodo raíz es negativo representa la suma sesgada de las permutaciones dadas por sus dos subárboles secundarios. subárboles. De esta forma, un árbol separador equivale a una construcción de la permutación por sumas directas y sesgadas, partiendo de la permutación trivial.
Como prueban 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 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 cada permutación separable puede realizarse de esta manera. [3]
Enumeración combinatoria
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 la longitud uno) es
Este resultado fue probado para una clase de matrices de permutación equivalente a las permutaciones separables de 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 nodo mismo y luego aplicando la teoría de las funciones generadoras a estos árboles. West (1995) dio otra prueba que se aplica más directamente a las permutaciones separables . [4]
Algoritmos
Bose, Buss & Lubiw (1998) demostraron que es posible determinar en tiempo polinómico 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 es 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 permanece NP- difícil incluso cuando las entradas son todas separables. [5]
Historia
Las permutaciones separables surgieron por primera vez en el trabajo de Avis y Newborn (1981) , quienes demostraron que son precisamente las permutaciones que se pueden clasificar por un número arbitrario de pop-stacks en serie, donde un pop-stack es una forma restringida de pila en que cualquier operación emergente hace estallar todos los elementos a la vez.
Shapiro y Stephens (1991) volvieron a considerar las permutaciones separables en su estudio 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 matriz que tenga dos o más vecinos ortogonales iguales a uno. Como muestran, la clase de permutaciones que se transforman mediante este proceso en la matriz todo-uno es exactamente la clase de permutaciones separables.
El término "permutación separable" fue introducido más tarde por Bose, Buss & Lubiw (1998) , quienes los consideraron por sus propiedades algorítmicas.
Estructuras relacionadas
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 cuyos bordes son las inversiones de la permutación. En el caso de una permutación separable, la estructura de este gráfico se puede leer en el árbol de separación de la permutación: dos vértices del gráfico son adyacentes si y solo si su ancestro común más bajo en el árbol de separación es negativo. Los gráficos que se pueden formar a partir de árboles de esta manera se denominan cografías (abreviatura de gráficos reducibles por complemento) y los árboles a partir de los cuales se forman se denominan cotrees. Por tanto, las permutaciones separables son exactamente las permutaciones cuyas gráficas de permutación son cografías. [6] La caracterización gráfica prohibida de las cografías (son las gráficas sin trayectoria inducida por 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 serie-paralelos , los conjuntos parcialmente ordenados cuyas gráficas de comparabilidad son las cografías. Al igual que con las cografías y las permutaciones separables, los órdenes parciales serie-paralelos 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 se quede de él en la permutación. Las permutaciones para las que este orden parcial es serie-paralelo son exactamente las permutaciones separables.
Las permutaciones separables también se pueden utilizar para describir particiones jerárquicas de rectángulos en rectángulos más pequeños (los denominados "planos de planta en rodajas", que se utilizan, 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 horizontal y vertical. rebanadas de un rectángulo en rectángulos más pequeños. [7]
Las permutaciones separables incluyen como un caso especial las permutaciones ordenables en pila , que evitan el patrón 231.
Notas
- ^ Kitaev (2011) , p. 57.
- ^ a b Bose, Buss y Lubiw (1998) ; Kitaev (2011) , Teorema 2.2.36, pág. p.58.
- ↑ Ghys (2016) , pág. 15.
- ^ Véase Kitaev (2011) , Teorema 2.2.45, p. 60.
- ^ Bouvel, Rossin y Vialette (2007) .
- ^ Bose, Buss y Lubiw (1998) .
- ^ Szepieniec y Otten (1980) ; Ackerman, Barequet y Pinter (2006)
Referencias
- Ackerman, Eyal; Barequet, Gill; Pinter, Ron Y. (2006), "A bijection between permutations and floorplans, and its applications", Discrete Applied Mathematics , 154 (12): 1674-1684, doi : 10.1016 / j.dam.2006.03.018 , MR 2233287
- Avis, David ; Newborn, Monroe (1981), "On pop-stacks in 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", Coincidencia de patrones combinatorios (CPM 2007) , Lecture Notes in Computer Science, 4580 , Springer, págs. 316–327, doi : 10.1007 / 978-3-540- 73437-6_32 , ISBN 978-3-540-73436-9.
- Bose, Prosenjit ; Buss, Jonathan; Lubiw, Anna (1998), " Coincidencia de patrones para permutaciones", Cartas de procesamiento de información , 65 (5): 277–283, CiteSeerX 10.1.1.39.3641 , doi : 10.1016 / S0020-0190 (97) 00209-3 , MR 1620935.
- Ghys, Étienne (2016), A Singular Mathematical Promenade , arXiv : 1612.06373 , Bibcode : 2016arXiv161206373G.
- Kitaev, Sergey (2011), "2.2.5 Permutaciones separables", Patrones en permutaciones y palabras , Monografías en Informática Teórica. An EATCS Series, Berlín: Springer-Verlag , págs. 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), "Bootstrap percolation, the Schröder numbers, and the N- kings problem", 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 del diseño", 17ª Conf. on Design Automation (DAC 1980) , págs. 535–542, doi : 10.1109 / DAC.1980.1585298 (inactivo el 31 de mayo de 2021)Mantenimiento de CS1: DOI inactivo a partir de mayo de 2021 ( enlace ).
- West, Julian (1995), "Generando árboles y los números de Catalán y Schröder", Matemáticas discretas , 146 (1-3): 247-262, doi : 10.1016 / 0012-365X (94) 00067-1 , MR 1360119.