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 pueden aparecer alternativamente es limitado. La longitud máxima posible de una secuencia de Davenport-Schinzel está limitada por el número de sus distintos símbolos 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]
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:
es una secuencia de Davenport-Schinzel de orden 3: contiene subsecuencias alternas de longitud cuatro, como ... 1, ... 2, ... 1, ... 2, ... (que aparece en cuatro formas diferentes como una subsecuencia de la secuencia completa) pero no contiene ninguna subsecuencia alterna de longitud cinco.
Si una secuencia Davenport-Schinzel de orden s incluye n valores distintos, se denomina secuencia Davenport-Schinzel ( n , s ) o secuencia DS ( n , s ). [2]
La complejidad de la secuencia DS ( n , s ) se ha analizado asintóticamente en el límite cuando n tiende al infinito, con la suposición de que s es una constante fija y se conocen límites casi estrechos para todo s . Sea λ s ( n ) la longitud de la secuencia DS ( n , s ) más larga. Los mejores límites conocidos en λ s implican la función inversa de Ackermann
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]
