Secuencia de Davenport-Schinzel

En combinatoria , una secuencia de Davenport-Schinzel es una secuencia de símbolos en la que el número de veces que dos símbolos cualesquiera pueden aparecer en alternancia es limitado. La longitud máxima posible de una secuencia de Davenport-Schinzel está limitada por el número de sus símbolos distintos multiplicado por un factor pequeño pero no constante que depende del número de alternancias permitidas. Las secuencias de Davenport-Schinzel fueron definidas por primera vez en 1965 por Harold Davenport y Andrzej Schinzel para analizar ecuaciones diferenciales lineales . Siguiendo a Atallah (1985), estas secuencias y sus límites de longitud también se han convertido en una herramienta estándar en geometría discreta y en el análisis de algoritmos geométricos . ^[1]

Definición

Se dice que una secuencia finita U = u ₁ , u ₂ , u _{3 , es una secuencia de Davenport–Schinzel de orden} s si satisface las dos propiedades siguientes:

1. No hay dos valores consecutivos en la secuencia que sean iguales entre sí.
2. Si x e y son dos valores distintos que aparecen en la secuencia, entonces la secuencia no contiene una subsecuencia... x , ... y , ..., x , ..., y , ... que consta de s  + 2 valores alternados entre 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 subsecuencias alternas de longitud cuatro, como ...1, ... 2, ... 1, ... 2, ... (que aparece de cuatro maneras diferentes como una subsecuencia de toda la secuencia) pero no contiene ninguna subsecuencia alterna de longitud cinco.

Si una secuencia de Davenport–Schinzel de orden s incluye n valores distintos, se denomina secuencia de Davenport–Schinzel ( n , s ) o secuencia DS ( n , s ). ^[2]

Límites de longitud

La complejidad de la secuencia DS ( n , s ) se ha analizado asintóticamente en el límite a medida que n tiende a infinito, con el supuesto de que s es una constante fija y se conocen límites casi estrictos para todos los s . Sea λ _s ( n ) la longitud de la secuencia DS ( n , s ) más larga. Los mejores límites conocidos en λ _s involucran la función inversa de Ackermann

α( norte ) = mínimo { metro | A ( metro , metro ) ≥ norte },

donde A es la función de Ackermann. Debido al crecimiento muy rápido de la función de Ackermann, su inversa α crece muy lentamente y es como máximo cuatro para problemas de cualquier tamaño práctico. ^[3]

Utilizando la notación O grande y Θ grande , se conocen los siguientes límites:

• ${\displaystyle \lambda _{0}(n)=1}$.
• ${\displaystyle \lambda _{1}(n)=n}$. ^[4]
• ${\displaystyle \lambda _{2}(n)=2n-1}$. ^[4]
• ${\displaystyle \lambda _{3}(n)=2n\alpha (n)+O(n)}$. ^[5] Este límite de complejidad se puede realizar dentro de un factor de 2 mediante segmentos de línea: existen disposiciones de n segmentos de línea en el plano cuyas envolventes inferiores tienen complejidad Ω( n  α( n )). ^[6]
• ${\displaystyle \lambda _{4}(n)=\Theta (n2^{\alpha (n)})}$. ^[7]
• ${\displaystyle \lambda _{5}(n)=\Theta (n\alpha (n)2^{\alpha (n)})}$. ^[8]
• Para valores pares e impares de s ≥ 6,

${\displaystyle \lambda _{s}(n)=n\cdot 2^{{\frac {1}{t!}}\alpha (n)^{t}+O(\alpha (n)^{t-1})}}$, donde . ^[9] ${\displaystyle t=\left\lfloor {\frac {s-2}{2}}\right\rfloor }$

El valor de λ _s ( n ) también se conoce cuando s es variable pero n es una constante pequeña: ^[10]

${\displaystyle \lambda _{s}(1)=1\,}$

${\displaystyle \lambda _{s}(2)=s+1\,}$

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

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

Cuando s es una función de n, los límites superior e inferior de las secuencias de Davenport-Schinzel no son estrictos.

• Cuando , y . ^[11] ${\displaystyle s>n^{1/t}(t-1)!}$ ${\displaystyle \lambda _{s}(n)=\Omega (n^{2}s/(t-1)!)}$ ${\displaystyle \lambda _{s}(n)=O(n^{2}s)}$
• Cuando , . ^[12] ${\displaystyle \log \log n<s=n^{o(1)}}$ ${\displaystyle \lambda _{s}(n)=\Omega \left(n\left({\frac {s}{2\log \log _{s}n}}\right)^{\log \log _{s}n}\right)}$
• Cuando , . ^[13] ${\displaystyle s\leq \log \log n}$ ${\displaystyle \lambda _{s}(n)=\Omega (n2^{s})}$

Aplicación para bajar sobres

Una secuencia de Davenport-Schinzel de orden 3 formada por la envolvente inferior de segmentos de línea.

La envolvente inferior de un conjunto de funciones ƒ _i ( x ) de una variable real x es la función dada por su mínimo puntual:

ƒ( x ) = min _i ƒ _i ( x ).

Supongamos que estas funciones se comportan particularmente bien: todas son continuas y dos de ellas son iguales en, como máximo, s valores. Con estos supuestos, la línea real se puede dividir en un número finito de intervalos dentro de los cuales una función tiene valores menores que todas las demás funciones. La secuencia de estos intervalos, etiquetada por la función minimizadora 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 de este orden también limita el número de intervalos en esta representación de la envolvente inferior.

En la aplicación original de Davenport y Schinzel, las funciones en consideración eran un conjunto de soluciones diferentes para la misma ecuación diferencial lineal homogénea de orden s . Cualquier par de soluciones distintas pueden tener como máximo s valores en común, por lo que la envolvente inferior de un conjunto de n soluciones distintas forma una DS ( n , s )-secuencia.

El mismo concepto de envolvente inferior se puede aplicar también a funciones que son continuas solo por partes o que están definidas solo sobre intervalos de la línea real; sin embargo, en este caso, los puntos de discontinuidad de las funciones y los puntos finales del intervalo dentro del cual se define cada función se suman al orden de la secuencia. Por ejemplo, un segmento de línea no vertical en el plano se puede interpretar como el gráfico de una función que asigna un intervalo de valores x a sus valores y correspondientes , y la envolvente inferior de una colección de segmentos de línea forma una secuencia de Davenport-Schinzel de orden tres porque dos segmentos de línea cualesquiera pueden formar una subsucesión alternada con una longitud de cuatro como máximo.

Véase también

• Palabra cuadrada libre

Notas

1. Sharir y Agarwal (1995), págs. x y 2.
2. Véase Sharir y Agarwal (1995), pág. 1, para esta notación.
3. Sharir y Agarwal (1995), pág. 14.
4. Sharir y Agarwal (1995), pág. 6.
5. Sharir y Agarwal (1995), capítulo 2, págs. 12–42; Hart y Sharir (1986); Komjath (1988); Klázar (1999); Nivasch (2009); Pettie (2015).
6. Sharir y Agarwal (1995), capítulo 4, págs. 86-114; Wiernik y Sharir (1988).
7. Sharir y Agarwal (1995), capítulo 3, págs. 43–85; Agarwal, Sharir y Shor (1989); Nivasch (2009); Pettie (2015).
8. Pettie (2015).
9. Sharir y Agarwal (1995), capítulo 3, págs. 43–85; Agarwal, Sharir y Shor (1989); Nivasch (2009); Pettie (2015).
10. Roselle y Stanton (1971).
11. Roselle y Stanton (1971); Wellman y Pettie (2016).
12. Wellman y Pettie (2016).
13. Wellman y Pettie (2016).

Referencias

• Agarwal, PK ; Sharir, Micha ; Shor, P. (1989), "Límites superiores e inferiores precisos en la longitud de secuencias generales de Davenport–Schinzel", Journal of Combinatorial Theory, Serie A , 52 (2): 228–274, doi : 10.1016/0097-3165(89)90032-0 , MR  1022320.
• Atallah, Mikhail J. (1985), "Algunos problemas de geometría computacional dinámica", Computers and Mathematics with Applications , 11 (12): 1171–1181, doi :10.1016/0898-1221(85)90105-1, MR  0822083.
• Davenport, H. ; Schinzel, Andrzej (1965), "Un problema combinatorio relacionado con ecuaciones diferenciales", American Journal of Mathematics , 87 (3), The Johns Hopkins University Press: 684–694, doi :10.2307/2373068, JSTOR  2373068, MR  0190010.
• Hart, S.; Sharir, Micha (1986), "No linealidad de las secuencias de Davenport–Schinzel y de los esquemas generalizados de compresión de trayectorias", Combinatorica , 6 (2): 151–177, CiteSeerX  10.1.1.295.885 , doi :10.1007/BF02579170, MR  0875839, S2CID  18864716.
• Klazar, M. (1999), "Sobre las longitudes máximas de las secuencias de Davenport–Schinzel", Contemporary Trends in Discrete Mathematics , DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 49, American Mathematical Society, págs. 169–178.
• Komjáth, Péter (1988), "Una construcción simplificada de secuencias no lineales de Davenport-Schinzel", Journal of Combinatorial Theory, Serie A , 49 (2): 262–267, doi :10.1016/0097-3165(88)90055-6, MR  0964387.
• Mullin, RC; Stanton, RG (1972), "Un enfoque de teoría de mapas para las secuencias de Davenport-Schinzel". Pacific Journal of Mathematics , 40 : 167–172, doi : 10.2140/pjm.1972.40.167 , MR  0302601.
• Nivasch, Gabriel (2009), "Límites mejorados y nuevas técnicas para secuencias Davenport-Schinzel y sus generalizaciones", Límites mejorados y nuevas técnicas para secuencias Davenport--Schinzel y sus generalizaciones (PDF) , vol. 57, págs. 1–10, arXiv : 0807.0484 , Bibcode :2008arXiv0807.0484N, doi :10.1145/1706591.1706597, S2CID  3175575, archivado desde el original (PDF) el 2012-10-18 , consultado el 2009-01-08.
• Roselle, DP ; Stanton, RG (1971), "Algunas propiedades de las secuencias de Davenport-Schinzel", Acta Arithmetica , 17 (4): 355–362, doi : 10.4064/aa-17-4-355-362 , MR  0284414.
• Sharir, Micha ; Agarwal, Pankaj K. (1995), Secuencias de Davenport–Schinzel y sus aplicaciones geométricas , Cambridge University Press, ISBN 0-521-47025-0.
• Stanton, RG; Dirksen, PH (1976), "Secuencias de Davenport-Schinzel", Ars Combinatoria , 1 (1): 43–51, MR  0409347.
• Stanton, RG; Roselle, DP (1970), "Un resultado sobre secuencias de Davenport-Schinzel", Teoría combinatoria y sus aplicaciones, III (Proc. Colloq., Balatonfüred, 1969) , Ámsterdam: Holanda Septentrional, págs. 1023-1027, MR  0304189.
• Wiernik, Ady; Sharir, Micha (1988), "Realizaciones planares de secuencias no lineales de Davenport–Schinzel por segmentos", Geometría discreta y computacional , 3 (1): 15–47, doi : 10.1007/BF02187894 , MR  0918177.
• Pettie, Seth (2015), "Límites precisos en secuencias de Davenport-Schinzel de cada orden", J. ACM , 62 (5): 1–40, arXiv : 1204.1086 , doi :10.1145/2794075, S2CID  6880266.
• Wellman, Julian; Pettie, Seth (2016), Límites inferiores en secuencias de Davenport-Schinzel a través de matrices rectangulares de Zarankiewicz , arXiv : 1610.09774 , Bibcode :2016arXiv161009774W.

Enlaces externos

• Secuencia de Davenport-Schinzel, de MathWorld .
• Secuencias de Davenport-Schinzel Archivado el 13 de enero de 2020 en Wayback Machine , una sección del libro Motion Planning , de Steven M. LaValle.