En el estudio matemático de las permutaciones y los patrones de permutación , un superpatrón o permutación universal es una permutación que contiene todos los patrones de una longitud dada. Más específicamente, un k -superpatrón contiene todos los patrones posibles de longitud k . [1]
Si π es una permutación de longitud n , representada como una secuencia de los números del 1 al n en algún orden, y s = s 1 , s 2 , ..., s k es una subsecuencia de π de longitud k , entonces s corresponde a un patrón único , una permutación de longitud k cuyos elementos están en el mismo orden que s . Es decir, para cada par i y j de índices, el i -ésimo elemento del patrón para s debe ser menor que el j -ésimo elemento si y solo si el i -ésimo elemento de s es menor que el j -ésimo elemento. De manera equivalente, el patrón es isomorfo en orden a la subsecuencia. Por ejemplo, si π es la permutación 25314, entonces tiene diez subsecuencias de longitud tres, que forman los siguientes patrones:
Una permutación π se denomina k -superpatrón si sus patrones de longitud k incluyen todas las permutaciones de longitud k . Por ejemplo, los patrones de longitud 3 de 25314 incluyen las seis permutaciones de longitud 3, por lo que 25314 es un 3-superpatrón. Ningún 3-superpatrón puede ser más corto, porque dos subsecuencias cualesquiera que formen los dos patrones 123 y 321 solo pueden intersecarse en una única posición, por lo que se requieren cinco símbolos solo para cubrir estos dos patrones.
Arratia (1999) introdujo el problema de determinar la longitud del k -superpatrón más corto posible . [2] Observó que existe un superpatrón de longitud k 2 (dado por el ordenamiento lexicográfico en los vectores de coordenadas de puntos en una cuadrícula cuadrada) y también observó que, para un superpatrón de longitud n , debe darse el caso de que tenga al menos tantas subsecuencias como patrones. Es decir, debe ser cierto que , de lo que se deduce por la aproximación de Stirling que n ≥ k 2 / e 2 , donde e ≈ 2,71828 es el número de Euler . Este límite inferior fue mejorado posteriormente muy ligeramente por Chroman, Kwan y Singhal (2021), quienes lo aumentaron a 1,000076 k 2 / e 2 , [3] refutando la conjetura de Arratia de que el límite inferior k 2 / e 2 era estricto. [2]
El límite superior de k 2 para la longitud del superpatrón probado por Arratia no es estricto. Después de mejoras intermedias, [4] Miller (2009) demostró que existe un k -superpatrón de longitud como máximo k ( k + 1)/2 para cada k . [5] Este límite fue mejorado posteriormente por Engen y Vatter (2021), quienes lo redujeron a ⌈( k 2 + 1)/2⌉. [6]
Eriksson et al. conjeturaron que la longitud real del k -superpatrón más corto es asintótica a k 2 /2. [4] Sin embargo, esto está en contradicción con una conjetura de Alon sobre superpatrones aleatorios que se describe a continuación.
Los investigadores también han estudiado la longitud necesaria para que una secuencia generada por un proceso aleatorio se convierta en un superpatrón. [7] Arratia (1999) observa que, debido a que la subsecuencia creciente más larga de una permutación aleatoria tiene una longitud (con alta probabilidad) de aproximadamente 2√ n , se deduce que una permutación aleatoria debe tener una longitud de al menos k 2 /4 para tener una alta probabilidad de ser un k -superpatrón: las permutaciones más cortas que esto probablemente no contendrán el patrón identidad. [2] Él atribuye a Alon la conjetura de que, para cualquier ε > 0 , con alta probabilidad, las permutaciones aleatorias de longitud k 2 /(4 − ε) serán k -superpatrones.
