En combinatoria, una sucesión de Davenport-Schinzel es una secuencia de símbolos en la que el número de veces que dos símbolos cualesquiera pueden aparecer alternadamente está limitado. La longitud máxima posible de una sucesión 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 sucesiones de Davenport-Schinzel fueron definidas por primera vez en 1965 por Harold Davenport y Andrzej Schinzel para analizar ecuaciones diferenciales lineales. Siguiendo a , estas sucesiones 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., pp. x and 2.
Definición Una sucesión finita U = u1, u2, u3, se denomina sucesión de Davenport-Schinzel de orden s si satisface las dos propiedades siguientes:
No hay dos valores consecutivos iguales entre sí en la sucesión. Si x e y son dos valores distintos que aparecen en la sucesión, entonces la sucesión no contiene una subsucesión ... x, ... y, ... x, ... y, ... que consista en s + 2 valores que se alternan entre x e y.
Por ejemplo, la sucesión:
1, 2, 1, 3, 1, 3, 2, 4, 5, 4, 5, 2, 3
es una sucesión de Davenport-Schinzel de orden 3: contiene subsecuencias alternas de longitud cuatro elementos, como ... 1, ... 2, ... 1, ... 2, ..., que aparecen de cuatro maneras diferentes como subsecuencias de la sucesión completa:
1, 2, 1, 3, 1, 3, 2, 4, 5, 4, 5, 2, 3 1, 2, 1, 3, 1, 3, 2, 4, 5, 4, 5, 2, 3 1, 2, 1, 3, 1, 3, 2, 4, 5, 4, 5, 2, 3 1, 2, 1, 3, 1, 3, 2, 4, 5, 4, 5, 2, 3
pero no contiene subsecuencias alternas de longitud cinco elementos (por eso es de orden 3).
Si una sucesión de Davenport-Schinzel de orden s incluye n valores distintos, se denomina sucesión de Davenport-Schinzel (n,s) o sucesión DS(n,s).Véase , p. 1, para esta notación.
Límites de longitud La complejidad de la sucesión DS(n,s) se ha analizado asintóticamente en el límite cuando n tiende a infinito, suponiendo que s es una constante fija, y se conocen cotas casi exactas para todos los s. Sea λs(n) la longitud de la sucesión DS(n,s) más larga. Las mejores cotas conocidas para λs involucran la función de Ackermann inversa:
α(n) = min m | A(m,m) ≥ n,
donde A es la función de Ackermann. Debido al rápido crecimiento 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., p. 14.
Usando las notaciones O grande y Θ grande, se conocen las siguientes cotas:
. ., p. 6. . ., Chapter 2, pp. 12–42; ; ; ; ; . Este límite de complejidad se puede alcanzar con un factor de 2 mediante segmentos rectilíneos: existen n configuraciones de segmentos rectilíneos en el plano cuya envolvente inferior tiene complejidad O(n a(n))., Chapter 4, pp. 86–114; . ., Chapter 3, pp. 43–85; ; ; . .. Para valores pares e impares de s ≥ 6, , donde .
El valor de λs(n) también se conoce cuando s es variable pero n es una constante pequeña:.
Cuando s es una función de n, las elemento mayorante y minorante en sucesiones de Davenport-Schinzel no son ajustadas.
Cuando , y .; . Cuando , .. Cuando , .
Aplicación a envolventes inferiores
La envolvente inferior de un conjunto de funciones ƒ i(x) de variable real x es la función dada por su mínimo puntual:
ƒ(x) = mini ƒi(x).
Supóngase que estas funciones se comportan particularmente bien: todas son continuoas, y cualesquiera dos de ellas son iguales en como máximo s valores. Con estas suposiciones, la recta real puede dividirse en un número finito de intervalos dentro de los cuales una función tiene valores menores que todas las demás. La sucesión de estos intervalos, etiquetados por la función minimizadora dentro de cada intervalo, forma una sucesión de Davenport-Schinzel de orden s. Por lo tanto, cualquier límite superior para la complejidad de una sucesión 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 consideradas eran un conjunto de diferentes soluciones 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).
El mismo concepto de envolvente inferior también puede aplicarse a funciones que solo son continuas a trozos o que se definen únicamente sobre intervalos de la recta real. Sin embargo, en este caso, los puntos de discontinuidad de las funciones y los extremos del intervalo dentro del cual se define cada función se suman al orden de la sucesión. Por ejemplo, un segmento rectilíneo no vertical en el plano puede interpretarse como la gráfica de una función que aplica un intervalo de valores x a sus correspondientes valores y, y la envolvente inferior de un conjunto de segmentos de recta forma una sucesión de Davenport-Schinzel de orden tres, ya que cualesquiera dos segmentos de recta pueden formar una subsecuencia alternada de longitud como máximo cuatro.
Referencias
Bibliografía .
. .
.
.
.
.
.
.
.
.
.
.
.
.
Enlaces externos Sucesión de Davenport-Schinzel, de MathWorld. Sucesiones de Davenport-Schinzel , una sección del libro «Planificación de movimiento», de Steven M. LaValle.
Categoría:Sucesiones Categoría:Geometría discreta