La conjetura de Stanley-Wilf , formulada independientemente por Richard P. Stanley y Herbert Wilf a fines de la década de 1980, establece que la tasa de crecimiento de cada clase de permutación propiamente dicha es exponencial individualmente . Lo demostraron Adam Marcus y Gábor Tardos ( 2004 ) y ya no es una conjetura. Marcus y Tardos en realidad probaron una conjetura diferente, debido a Zoltán Füredi y Péter Hajnal ( 1992 ), que había demostrado implicar la conjetura de Stanley-Wilf por Klazar (2000) .
Declaración
La conjetura de Stanley-Wilf establece que para cada permutación β , hay una constante C tal que el número | S n ( β ) | de permutaciones de longitud n que evitan β como patrón de permutación es como máximo C n . Como observó Arratia (1999) , esto equivale a la convergencia del límite
El límite superior dado por Marcus y Tardos para C es exponencial en la longitud de β . Una conjetura más fuerte de Arratia (1999) había establecido que uno podría tomar C como ( k - 1) 2 , donde k denota la longitud de β , pero esta conjetura fue refutada por la permutación β = 4231 por Albert et al. (2006) . De hecho, Fox (2013) ha demostrado que C es, de hecho, exponencial en k para casi todas las permutaciones.
Tasas de crecimiento permitidas
La tasa de crecimiento (o límite de Stanley-Wilf) de una clase de permutación se define como
donde a n denota el número de permutaciones de longitud n en la clase. Claramente, no todos los números reales positivos pueden ser una tasa de crecimiento de una clase de permutación, independientemente de si están definidos por un único patrón prohibido o por un conjunto de patrones prohibidos. Por ejemplo, los números estrictamente entre 0 y 1 no pueden ser tasas de crecimiento de clases de permutación.
Kaiser y Klazar (2002) demostraron que si el número de permutaciones en una clase de longitud n es siempre menor que el n- ésimo número de Fibonacci , la enumeración de la clase es eventualmente polinomial. Por lo tanto, los números estrictamente entre 1 y la proporción áurea tampoco pueden ser tasas de crecimiento de clases de permutación. Kaiser y Klazar continuaron estableciendo todas las posibles constantes de crecimiento de una clase de permutación por debajo de 2; estas son las raíces reales más grandes de los polinomios
para un número entero k ≥ 2. Esto muestra que 2 es el menor punto de acumulación de tasas de crecimiento de las clases de permutación.
Vatter (2011) posteriormente amplió la caracterización de las tasas de crecimiento de las clases de permutación hasta un número algebraico específico κ≈2,20. De esta caracterización, se deduce que κ es el menor punto de acumulación de puntos de acumulación de tasas de crecimiento y que todas las tasas de crecimiento hasta κ son números algebraicos. Vatter (2019) estableció que existe un número algebraico ξ≈2.31 tal que hay incontables tasas de crecimiento en cada vecindario de ξ, pero solo contablemente muchas tasas de crecimiento por debajo de él. Pantone y Vatter (2020) caracterizaron las (contablemente muchas) tasas de crecimiento por debajo de ξ, todas las cuales también son números algebraicos. Sus resultados también implican que en el conjunto de todas las tasas de crecimiento de las clases de permutación, ξ es el menor punto de acumulación desde arriba.
En la otra dirección, Vatter (2010) demostró que cada número real de al menos 2,49 es la tasa de crecimiento de una clase de permutación. Ese resultado fue mejorado más tarde por Bevan (2014) , quien demostró que cada número real de al menos 2,36 es la tasa de crecimiento de una clase de permutación.
Ver también
- Enumeraciones de clases de permutación específicas para las tasas de crecimiento de clases de permutación específicas.
Notas
Referencias
- Albert, Michael H .; Anciano, Murray; Rechnitzer, Andrew; Westcott, P .; Zabrocki, Mike (2006), "En el límite de Stanley-Wilf de 4231-evitando permutaciones y una conjetura de Arratia", Advances in Applied Mathematics , 36 (2): 96-105, doi : 10.1016 / j.aam.2005.05. 007 , MR 2199982.
- 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, MR 1710623.
- Bevan, David (2014), Intervalos de tasas de crecimiento de clases de permutación , arXiv : 1410.3679 , Bibcode : 2014arXiv1410.3679B.
- Fox, Jacob (2013), los límites de Stanley-Wilf son típicamente exponenciales , arXiv : 1310.8378 , Bibcode : 2013arXiv1310.8378F.
- Füredi, Zoltán ; Hajnal, Péter (1992), "Teoría de matrices de Davenport-Schinzel", Matemáticas discretas , 103 (3): 233-251, doi : 10.1016 / 0012-365X (92) 90316-8 , MR 1171777.
- Kaiser, Tomáš; Klazar, Martin (marzo de 2002), "Sobre las tasas de crecimiento de las clases de permutación cerradas" , Electronic Journal of Combinatorics , 9 (2): artículo de investigación 10, 20, MR 2028280.
- Klazar, Martin (2000), "La conjetura de Füredi-Hajnal implica la conjetura de Stanley-Wilf", Serie de potencias formales y combinatoria algebraica (Moscú, 2000) , Springer, págs. 250-255, MR 1798218.
- Klazar, Martin (2010), "Algunos resultados generales en enumeración combinatoria", Patrones de permutación , London Math. Soc. Lecture Note Ser., 376 , Cambridge: Cambridge Univ. Prensa, págs. 3–40, doi : 10.1017 / CBO9780511902499.002 , MR 2732822.
- Marcus, Adam ; Tardos, Gábor (2004), "Matrices de permutación excluidas y la conjetura de Stanley-Wilf", Journal of Combinatorial Theory , Serie A, 107 (1): 153–160, doi : 10.1016 / j.jcta.2004.04.002 , MR 2063960.
- Pantone, Jay; Vatter, Vincent (2020), "Tasas de crecimiento de las clases de permutación: categorización hasta el umbral de incontables", Israel Journal of Mathematics , 236 (1): 1–43, arXiv : 1605.04289 , doi : 10.1007 / s11856-020-1964- 5 , MR 4093880.
- Vatter, Vincent (2019), "Tasas de crecimiento de las clases de permutación: de contables a incontables", Proc. London Math. Soc. , Serie 3, 119 (4): 960–997, arXiv : 1605.04297 , doi : 10.1112 / plms.12250 , MR 3964825.
- Vatter, Vincent (2010), "Clases de permutación de cada tasa de crecimiento por encima de 2.48188", Mathematika , 56 (1): 182–192, arXiv : 0807.2815 , doi : 10.1112 / S0025579309000503 , MR 2604993.
- Vatter, Vincent (2011), "Pequeñas clases de permutación", Proc. London Math. Soc. , Serie 3, 103 (5): 879–921, arXiv : 0712.4006 , doi : 10.1112 / plms / pdr017 , MR 2852292.
enlaces externos
- Cómo Adam Marcus y Gabor Tardos se dividieron y conquistaron la conjetura de Stanley-Wilf , por Doron Zeilberger .
- Weisstein, Eric W. "Conjetura de Stanley-Wilf" . MathWorld .