En el estudio matemático de permutaciones y patrones de permutación , un superpatrón o permutación universal es una permutación que contiene todos los patrones de una longitud determinada. Más específicamente, un superpatrón k contiene todos los patrones posibles de longitud k . [1]
Definiciones y ejemplo
Si π es una permutación de longitud n , representada como una secuencia de números de 1 an 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 jel 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 de orden isomorfo a la subsecuencia. Por ejemplo, si π es la permutación 25314, entonces tiene diez subsecuencias de longitud tres, formando los siguientes patrones:
| Subsiguiente | Patrón |
|---|---|
| 253 | 132 |
| 251 | 231 |
| 254 | 132 |
| 231 | 231 |
| 234 | 123 |
| 214 | 213 |
| 531 | 321 |
| 534 | 312 |
| 514 | 312 |
| 314 | 213 |
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 superpatrón 3. Ningún superpatrón 3 puede ser más corto, porque dos subsecuencias cualesquiera que formen los dos patrones 123 y 321 solo pueden cruzarse en una sola posición, por lo que se requieren cinco símbolos solo para cubrir estos dos patrones.
Límites de longitud
Arratia ( 1999 ) introdujo el problema de determinar la longitud del superpatrón k más corto posible . [2] Observó que existe un superpatrón de longitud k 2 (dado por el ordenamiento lexicográfico sobre los vectores coordenados 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 tiene al menos tantas subsecuencias como patrones. Es decir, debe ser cierto que, de donde se sigue 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 posteriormente mejorado muy levemente por Chroman, Kwan y Singhal ( 2020 ), 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 estrecho. [2]
El límite superior de k 2 en la longitud del superpatrón probado por Arratia no es estrecho. Después de mejoras intermedias, [4] Miller ( 2009 ) demostró que hay un superpatrón k de longitud como máximo k ( k + 1) / 2 para cada k . [5] Este límite fue mejorado posteriormente por Engen y Vatter ( 2019 ), quienes lo redujeron a ⌈ ( k 2 + 1) / 2⌉. [6]
Eriksson y col. conjeturado que la verdadera longitud de la más corta k -superpattern 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 describen a continuación.
Superpatrones aleatorios
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 la más larga subsecuencia creciente de una permutación aleatoria tiene longitud (con una alta probabilidad) aproximadamente 2√ n , se sigue que una permutación aleatoria debe tener una longitud al menos k 2 /4 para tienen alta probabilidad de ser un k -superpatrón: las permutaciones más cortas que esto probablemente no contendrán el patrón de identidad. [2] Atribuye a Alon la conjetura de que, para cualquier ε> 0 , con alta probabilidad, permutaciones aleatorias de longitud k 2/ (4 - ε) serán k -superpatrones.
Ver también
Referencias
- ^ Bóna, Miklós (2012), Combinatoria de permutaciones , Matemáticas discretas y sus aplicaciones, 72 (2ª ed.), CRC Press, p. 227, ISBN 9781439850510.
- ^ a b c Arratia, Richard (1999), "Sobre la conjetura de Stanley-Wilf para el número de permutaciones que evitan un patrón dado" , Electronic Journal of Combinatorics , 6 : N1, doi : 10.37236 / 1477 , MR 1710623
- ^ Chroman, Zachary; Kwan, Matthew; Singhal, Mihir (2020), Límites inferiores para superpatrones y secuencias universales , arXiv : 2004.02375
- ^ a b Eriksson, Henrik; Eriksson, Kimmo; Linusson, Svante; Wästlund, Johan (2007), "Empaquetamiento denso de patrones en una permutación", Annals of Combinatorics , 11 (3–4): 459–470, doi : 10.1007 / s00026-007-0329-7 , MR 2376116
- ^ Miller, Alison (2009), "Límites asintóticos para permutaciones que contienen muchos patrones diferentes", Journal of Combinatorial Theory , Serie A, 116 (1): 92-108, doi : 10.1016 / j.jcta.2008.04.007
- ^ Engen, Michael; Vatter, Vincent (2021), "Containing all permutations", American Mathematical Monthly , 128 (1): 4–24, doi : 10.1080 / 00029890.2021.1835384
- ^ Godbole, Anant; Liendo, Martha (2013), Distribución del tiempo de espera para la aparición de superpatrones , arXiv : 1302.4668 , Bibcode : 2013arXiv1302.4668G.
