Superpatrón

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 números del 1 al n en algún orden, y s  = s ₁ , s ₂ , ..., 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 forma 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, ya que cualesquiera dos subsecuencias que forman los 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 ² (dado por el orden lexicográfico en los vectores de coordenadas de los puntos en una cuadrícula cuadrada) y también observó que, para un superpatrón de longitud n , debe ser cierto que tiene al menos tantas subsecuencias como patrones. Es decir, debe ser cierto que ${\displaystyle {\tbinom {n}{k}}\geq k!}$, de donde se deduce por la aproximación de Stirling que n  ≥ k ² / e ² , 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 ² / e ² , ^{[ 3 ]} refutando la conjetura de Arratia de que el límite inferior k ² / e ² era ajustado. ^{[ 2 ]}    

La cota superior de k ² en la longitud del superpatrón demostrada por Arratia no es ajustada. Después de mejoras intermedias, ^{[ 4 ]} Miller ( 2009 ) demostró que hay un k -superpatrón de longitud como máximo k ( k + 1)/2 para cada k . ^{[ 5 ]} Esta cota fue mejorada posteriormente por Engen y Vatter ( 2021 ) , quienes la redujeron a ⌈( k ² + 1)/2⌉. ^{[ 6 ]}      

Eriksson et al. conjeturaron que la longitud real del k -superpatrón más corto es asintótica a k ² /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) aproximadamente 2√ n , se deduce que una permutación aleatoria debe tener una longitud de al menos k ² /4 para tener una alta probabilidad de ser un k -superpatrón: las permutaciones más cortas que esta 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 ² /(4 − ε) serán k -superpatrones.

• Superpermutación