Secuencia de Davenport-Schinzel

En combinatoria , una secuencia de Davenport-Schinzel es una secuencia de caracteres en la que dos caracteres cualesquiera pueden aparecer en orden alterno un número limitado de veces. La longitud máxima posible de una secuencia de Davenport-Schinzel está limitada por el número de caracteres multiplicado por un pequeño factor constante que depende del número de entrelazados permitidos. Las secuencias de Davenport-Schinzel fueron definidas por primera vez en 1965 por Harold Davenport y Andrzej Schinzel para el análisis de ecuaciones diferenciales lineales . Siguiendo a Atalla [1] , estas secuencias y límites en sus longitudes se han convertido en una herramienta estándar en geometría combinatoria y en el análisis de algoritmos geométricos [2] .

Definición

Una sucesión finita U = u 1 , u 2 , u 3 se dice que es una sucesión Davenport-Schinzel de orden s si satisface las siguientes dos propiedades:

No hay dos valores consecutivos en una secuencia que sean iguales entre sí.
Si x e y son dos valores distintos que aparecen en una secuencia, entonces la secuencia no contiene una subsecuencia... x ,... y ,..., x ,..., y ,... que consta de s + 2 valores alternos de x e y .

Por ejemplo, la secuencia

1, 2, 1, 3, 1, 3, 2, 4, 5, 4, 5, 2, 3

es una secuencia de Davenport-Schinzel de orden 3 - contiene una secuencia alterna de cuatro longitudes, como ...1, ...2, ...1, ...2, ... (aparece de cuatro maneras diferentes como una secuencia de la secuencia completa), pero no contiene una subsecuencia de longitud cinco.

Si una secuencia de Davenport-Schinzel de orden s contiene n valores distintos, se denomina ( n , s ) secuencia de Davenport-Schinzel o secuencia DS ( n , s ) [3] .

Límites de longitud

La complejidad de una secuencia DS ( n , s ) se analiza asintóticamente cuando n tiende al infinito, suponiendo que s es una constante y se conocen límites casi exactos para todos los s . Sea λ s ( n ) la longitud de la secuencia DS ( n , s ) más larga. Los límites de λs más conocidos utilizan la función inversa de Ackermann

α( norte )=min { metro |A( metro , metro ) ≥ norte } ,

donde A es la función de Ackermann. Debido al muy rápido crecimiento de la función de Ackermann, su inversa crece muy lentamente y no excede de 4 para la mayoría de los problemas de cualquier tamaño práctico [4] .

Si usa la notación "O" grande , se conocen los siguientes límites:

${\ estilo de visualización \ lambda _ {0} (n) = 1}$ .
${\ estilo de visualización \ lambda _ {1} (n) = n}$ [5]
${\ estilo de visualización \ lambda _ {2} (n) = 2n-1}$ [5] .

${\ estilo de visualización \ lambda _ {3} (n) = 2n \ alfa (n) + O (n)}$ [6] [7] [8] [9] [10] [11] [12] . Este límite de complejidad se puede realizar hasta una constante por segmentos: existe tal disposición de n segmentos en el plano, cuya envolvente inferior tiene una complejidad Ω( n α( n )) [13] [8] .

${\ estilo de visualización \ lambda _ {4} (n) = \ Theta (n2 ^ {\ alfa (n)})}$ [14] [15] [12] .
$\lambda _{5}(n)=\Theta (n\alpha (n)2^{\alpha (n)})$ [12] .

Para valores pares e impares s ≥ 6

\lambda _{s}(n)=n\cdot 2^{{\frac {1}{t!)}}\alpha (n)^{t}+O(\alpha (n)^{ t-uno})}

, donde [14] [15] [12] .

t=\left\lpiso {\frac {s-2}{2}}\right\rpiso

El valor de λ s ( n ) también se conoce si s es variable y n es una pequeña constante [16] :

{\ estilo de visualización \ lambda _ {s} (1) = 1 \,}

{\ estilo de visualización \ lambda _ {s} (2) = s + 1 \,}

\lambda _{s}(3)=3s-2+(s\,{\bmod {\,}}2)

\lambda _{s}(4)=6s-2+(s\,{\bmod {\,}}2).

Si s es una función de n , los límites superior e inferior de la sucesión de Davenport-Schinzel no son exactos.

Si , y [16] [17] . $s>n^{1/t}(t-1)!$ $\lambda _{s}(n)=\Omega (n^{2}s/(t-1)!)$ ${\ estilo de visualización \ lambda _ {s} (n) = O (n ^ {2} s)}$
Si , [17] . ${\displaystyle \log \log n<s=n^{o(1)))$ $\lambda _{s}(n)=\Omega \left(n\left({\frac {s}{2\log \log _{s}n))\right)^{\log \log _ {s}n}\right)$
Si , [17] . $s\leq \log \log n$ $\lambda _{s}(n)=\Omega (n2^{s})$

Aplicación a sobres inferiores

La envolvente inferior del conjunto de funciones ƒ i ( x ) de la variable real x es la función dada por el mínimo puntual:

ƒ( x ) = min yo ƒ yo ( x ).

Supongamos que estas funciones tienen un comportamiento muy bueno: todas son continuas y dos de ellas son iguales como máximo en valores de s . Bajo estos supuestos, el eje real se puede dividir en un número finito de intervalos , dentro de cada uno de los cuales una función tiene valores menores que los valores de todas las demás funciones. Una secuencia de tales intervalos, etiquetada por la función mínima dentro de cada intervalo, forma una secuencia de Davenport-Schinzel de orden s . Por lo tanto, cualquier límite superior de la complejidad de una secuencia de Davenport-Schinzel con este orden también limita el número de intervalos en tal representación de la envolvente inferior.

La aplicación original de Davenport-Shinzel consideró funciones que son soluciones diferentes a la misma ecuación diferencial lineal homogénea de orden s . Dos soluciones diferentes cualesquiera tienen como máximo s valores comunes, por lo que la envolvente inferior del conjunto de n soluciones diferentes forma una secuencia DS ( n , s ).

El mismo concepto de la envolvente inferior se puede aplicar a funciones que solo son continuas por tramos o solo se definen en intervalos del eje real. Sin embargo, en este caso, se suman a la sucesión los puntos de discontinuidad de las funciones y los extremos de los intervalos en los que se da cada función. Por ejemplo, un segmento no vertical en el plano puede interpretarse como la gráfica de una función que asigna los puntos x del intervalo a los valores y correspondientes , y la envolvente inferior del conjunto de segmentos forma una secuencia de Davenport-Schinzel de orden tres, ya que dos segmentos cualquiera pueden formar una secuencia intercalada de longitud como máximo 4.

Véase también

Palabra sin cuadrados

Notas

↑ Atallah, 1985 .
↑ Sharir, Agarwal, 1995 , pág. = x y 2.
↑ Sharir, Agarwal, 1995 , pág. una.
↑ Sharir, Agarwal, 1995 , pág. catorce.
↑ 1 2 Sharir, Agarwal, 1995 , pág. 6.
↑ Sharir, Agarwal, 1995 , pág. 12-42 Capítulo 2.
↑ Hart, Sharir, 1986 .
↑ 1 2 Wiernik, Sharir, 1988 .
↑ Komjath, 1988 .
↑ Klazar, 1999 .
↑ Nivasch, 2009 .
↑ 1 2 3 4 Pettie, 2015 .
↑ Sharir, Agarwal, 1995 , pág. 86–114 Capítulo 4.
↑ 1 2 Sharir, Agarwal, 1995 , pág. 43-85 Capítulo 3.
↑ 1 2 Agarwal, Sharir, Shor, 1989 .
↑ 1 2 Roselle, Stanton, 1970/71 .
↑ 1 2 3 Wellman, Pettie, 2016 .

Literatura

Agarwal PK, Sharir M., Shor P. Límites superior e inferior definidos en la longitud de las secuencias generales de Davenport-Schinzel // Journal of Combinatorial Theory, Series A. - 1989. - Vol. 52 , no. 2 . — S. 228–274 . - doi : 10.1016/0097-3165(89)90032-0 . .
Atallah MJ Algunos problemas de geometría computacional dinámica // Computadoras y Matemáticas con Aplicaciones . - 1985. - T. 11 . - S. 1171-1181 . - doi : 10.1016/0898-1221(85)90105-1 . .
Davenport H., Schinzel A. Un problema combinatorio relacionado con ecuaciones diferenciales // American Journal of Mathematics. - The Johns Hopkins University Press, 1965. - V. 87 , no. 3 . — S. 684–694 . -doi : 10.2307/ 2373068 . — .
Hart S., Sharir M. No linealidad de las secuencias de Davenport-Schinzel y de los esquemas de compresión de rutas generalizadas // Combinatorica. - 1986. - T. 6 , núm. 2 . — S. 151–177 . -doi : 10.1007/ BF02579170 .
Klazar M. Sobre las longitudes máximas de las secuencias de Davenport-Schinzel // Tendencias contemporáneas en matemáticas discretas. - Sociedad Matemática Americana, 1999. - V. 49. - S. 169-178. — (Serie DIMACS en Matemática Discreta e Informática Teórica).
Peter Komjath. Una construcción simplificada de secuencias de Davenport-Schinzel no lineales // Journal of Combinatorial Theory, Series A. - 1988. - V. 49 , no. 2 . — S. 262–267 . - doi : 10.1016/0097-3165(88)90055-6 .
Mullin RC, Stanton RG Un enfoque teórico de mapas para las secuencias de Davenport-Schinzel. // Pacific Journal of Mathematics. - 1972. - T. 40 . — S. 167–172 . -doi : 10.2140 / pjm.1972.40.167 . (enlace no disponible)
Gabriel Nivasch. Límites mejorados y nuevas técnicas para las secuencias de Davenport-Schinzel y sus generalizaciones // Proc. 20º Simposio ACM-SIAM. Algoritmos discretos . - 2009. - S. 1–10. Archivado el 18 de octubre de 2012 en Wayback Machine .
Roselle DP, Stanton RG Algunas propiedades de las secuencias de Davenport-Schinzel // Acta Arithmetica. — 1970/71. - T. 17 . — S. 355–362 .
Micha Sharir, Pankaj K. Agarwal. Secuencias de Davenport-Schinzel y sus aplicaciones geométricas . - Prensa de la Universidad de Cambridge, 1995. - ISBN 0-521-47025-0 .
Stanton RG, Dirksen PH Secuencias de Davenport-Schinzel. // Ars combinatoria. - 1976. - Vol. 1 , número. 1 . — págs. 43–51 .
Stanton RG, Roselle DP Un resultado sobre secuencias de Davenport-Schinzel // Teoría combinatoria y sus aplicaciones, III (Proc. Colloq., Balatonfüred, 1969). - Holanda Septentrional, 1970. - S. 1023-1027.
Ady Wiernik, Micha Sharir. Realizaciones planares de secuencias no lineales de Davenport-Schinzel por segmentos // Geometría discreta y computacional. - 1988. - Vol. 3 , número. 1 . — P. 15–47 . -doi : 10.1007/ BF02187894 .
Seth Petty. Límites definidos en secuencias de Davenport-Schinzel de cada orden // J. ACM. - 2015. - T. 62 , núm. 5 . -doi : 10.1145/ 2794075 .
Julian Wellman, Seth Pettie. Límites inferiores de las secuencias de Davenport-Schinzel a través de matrices rectangulares de Zarankiewicz . - 2016. - arXiv : 1610.09774 .

Enlaces

Secuencia de Davenport-Schinzel , de MathWorld .
Davenport-Schinzel Sequences , una sección del libro Motion Planning , de Steven M. LaValle.