Suite de Davenport-Schinzel

Suite de Davenport-Schinzel

En combinatoire, une suite de Davenport-Schinzel est une suite de symboles dans laquelle le nombre de fois où deux symboles peuvent apparaître en alternance est limité. La longueur d'une suite de Davenport-Schinzel est limitée par le nombre de ses symboles distincts multiplié par un facteur petit mais non constant qui dépend du nombre d'alternances qui sont permises. Les suites de Davenport-Schinzel furent définies pour la première fois par Harold Davenport et Andrzej Schinzel afin d'analyser les équations différentielles linéaires. Ces séries et leurs limitations de longueur sont également devenues des outils standard en géométrie discrète et dans l'analyse des algorithmes géométriques[1].

Sommaire

Définition

Une suite finie de « symboles » U = u1, u2, u3, ... uN est dite suite de Davenport–Schinzel d'ordre s si elle satisfait aux deux propriétés suivantes :

  1. deux valeurs consécutives de la suite ne peuvent être égales.
  2. si x et y sont deux valeurs distinctes se produisant dans la suite, alors la suite ne contient pas de sous-suite ... x, ... y, ..., x, ..., y, ... consistant en s + 2 valeurs alternant entre x et y mais contient une sous-suite de longueur s + 1 avec deux symboles distincts.

Ainsi, la suite :

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

est une suite de Davenport–Schinzel d'ordre 3. Elle contient des sous-suites alternatives de longueur quatre, comme ...1, ... 2, ... 1, ... 2, ... (qui apparaît de quatre manières différentes comme une sous-suite dans la suite globale), mais ne contient aucune sous-suite alternative de longueur cinq.

Si une suite de Davenport–Schinzel d'ordre s comprend n valeurs distinctes, elle est appelée suite de Davenport–Schinzel (n,s), ou suite DS(n,s)[2].

Limites aux longueurs

La complexité des suites DS(n,s) a été analysée asymptotiquement lorsque n tend vers l'infini, en supposant que s est une constante fixe. Des bornes fortes presque optimales sont connues pour tout s.

Soit λs(n) la longueur de la suite DS(n,s) la plus longue. Les meilleurs limites connues sur λs utilisent la fonction d'Ackermann inverse.

α(n) = min { m | A(m,m) ≥ n },

A est la fonction d'Ackermann. En raison de la croissance très rapide de la fonction d'Ackermann, son inverse α croît très lentement, et est d'au plus quatre pour les problèmes de taille pratique[3].

Avec les notations de Landau (o et O), on connait les limites suivantes :

  • λ1(n) = n[4],
  • λ2(n) = 2n − 1[4].
  • \scriptstyle{2n\alpha(n)-O(n)\le\lambda_3(n)\le2n\alpha(n)+O(n\sqrt{\alpha(n)})}[5]. Cette borne de complexité peut être réalisée avec un facteur constant par des segments de droite : il existe des arrangement de n segments de droite dans le plan dont les enveloppes les plus basses ont la complexité Ω(n α(n))[6].
  • pour les valeurs paires de s≥ 4[7], \scriptstyle{\lambda_s(n)=n\cdot 2^{\frac{1}{t!}\alpha(n)^t(1+o(1))}}, où t = s/2 − 1.
  • pour les valeurs impaires de s≥ 5[7], \scriptstyle{\lambda_s(n)=n\cdot 2^{O(\alpha(n)^{\frac{s-3}{2}}\log\alpha(n))}.}.

La valeur de λs(n) est connue également lorsque s est variable et n une constante petite[8] :

\scriptstyle{\lambda_s(2)=s+1\,}
\scriptstyle{\lambda_s(3)=3s-2+(s\, \bmod \, 2)}
\scriptstyle{\lambda_s(4)=6s-2+(s\, \bmod\, 2)}

Application aux enveloppes basses

Une suite de Davenport-Schinzel formée par les enveloppes basses de segments de droite.

L'enveloppe basse d'un ensemble de fonctions ƒi(x) d'une variable réelle x est la fonction donnée par leurs minimums en chaque point :

ƒ(x) = mini ƒi(x).

On suppose que ces fonctions ont des comportements favorables : elles sont toutes continues, et chaque paire d'entre elles sont égales en au moins s valeurs. Avec ces hypothèses, la droite réelle peut être découpée en de nombreux intervalles finis dans lesquels une fonction à ses valeurs plus basses que celles de toutes les autres. La série de ces intervalles, désignée par la fonction de minimisation dans chacun des intervalles, forme une suite de Davenport–Schinzel d'ordre s. Donc, toute limite supérieure de la complexité d'une suite de Davenport–Schinzel de cet ordre limite aussi le nombre d'intervalles dans cette représentation de l'enveloppe basse.

Dans l'application originelle de Davenport et Schinzel, les fonctions considérées étaient un ensemble de solutions différentes à la même équation différentielle linéaire homogène d'ordre s. Toute paire de solutions distinctes peut avoir au plus s valeurs en commun, et donc l'enveloppe basse d'un ensemble de n solutions distinctes forme une suite DS(n,s).

Ce même concept d'enveloppe basse peut aussi être appliqué aux fonctions qui sont continues par morceaux ou définies seulement sur des intervalles de la droite réelle. Cependant, dans ce cas, les points de discontinuités des fonctions et des extrémités de l'intervalle dans lequel chaque fonnction est définie ajoute à l'ordre de la suite. Ainsi un segment de droite non vertical dans le plan peut être considéré comme le graphe d'une fonction liant un intervalle de x valeurs aux valeurs y correspondantes, et l'enveloppe basse d'un ensemble de segments de droite forme une suite de Davenport–Schinzel d'ordre trois car toute paire de segments de droite peut former une sous-suite alternative avec une longueur d'au plus quatre.

Notes et références

Notes

Références

  • (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Davenport–Schinzel sequence » (voir la liste des auteurs)
  • (en) Pankaj K. Agarwal (en), « Sharp upper and lower bounds on the length of general Davenport–Schinzel sequences », dans Journal of Combinatorial Theory, Series A, vol. 52, no 2, 1989, p. 228–274 [lien DOI] , MR1022320
  • (en) Mikhail J. Atallah, « Some dynamic computational geometry problems », dans Computers and Mathematics with Applications, vol. 11, 1985, p. 1171–1181 [lien DOI] , MR0822083
  • (en) H. Davenport, « A combinatorial problem connected with differential equations », dans American Journal of Mathematics, The Johns Hopkins University Press, vol. 87, no 3, 1965, p. 684–694 [texte intégral, lien DOI] , MR0190010
  • (en) S. Hart, « Nonlinearity of Davenport–Schinzel sequences and of generalized path compression schemes », dans Combinatorica, vol. 6, no 2, 1986, p. 151–177 [lien DOI] , MR0875839
  • (en) M. Klazar, « On the maximum lengths of Davenport–Schinzel sequences », dans Contemporary Trends in Discrete Mathematics, vol. 49, American Mathematical Society, coll. « DIMACS Series in Discrete Mathematics and Theoretical Computer Science », 1999, p. 169–178 
  • (en) Péter Komjáth, « A simplified construction of nonlinear Davenport–Schinzel sequences », dans Journal of Combinatorial Theory, Series A, vol. 49, no 2, 1988, p. 262–267 [lien DOI] , MR0964387
  • (en) R. C. Mullin, « A map-theoretic approach to Davenport-Schinzel sequences. », dans Pacific Journal of Mathematics, vol. 40, 1972, p. 167–172 [texte intégral] , MR0302601.
  • (en) Gabriel Nivasch, « Improved bounds and new techniques for Davenport–Schinzel sequences and their generalizations », dans Proc. 20th ACM-SIAM Symp. Discrete Algorithms, 2009 [lire en ligne], p. 1–10 , arXiv:0807.0484
  • (en) D. P. Roselle, « Some properties of Davenport-Schinzel sequences », dans Acta Arithmetica, vol. 17, 1970/71, p. 355–362 , MR0284414.
  • (en) Micha Sharir et Pankaj K. Agarwal, Davenport–Schinzel Sequences and Their Geometric Applications, New York, Cambridge University Press, 1995, 1re éd. (ISBN 978-0-521-47025-4) (LCCN 94030889) .
  • (en) R. G. Stanton, « Davenport-Schinzel sequences. », dans Ars Combinatoria, vol. 1, no 1, 1976, p. 43–51 , MR0409347.
  • (en) R.G. Stanton et D.P. Roselle, « A result on Davenport-Schinzel sequences », dans Combinatorial theory and its applications, III (Proc. Colloq., Balatonfüred, 1969), Amsterdam, North-Holland, 1970, p. 1023–1027 , MR0304189.
  • (en) Ady Wiernik, « Planar realizations of nonlinear Davenport–Schinzel sequences by segments », dans Discrete & Computational Geometry, vol. 3, no 1, 1988, p. 15–47 [lien DOI] , MR0918177

Voir aussi

Article connexe

Mot sans facteur carré

Liens externes


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Suite de Davenport-Schinzel de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать курсовую

Regardez d'autres dictionnaires:

  • Andrzej Schinzel — Andrezj Schinzel en 1974 (photo de MFO) Naissance 5 avril 1937 Sandomierz (Pologne) Domicile Pologne …   Wikipédia en Français

  • Harold Davenport — Pour les articles homonymes, voir Davenport. Harold Davenport Harold Davenport en 1968 Naissance 30  …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • DIOPHANTIENNES (ÉQUATIONS) — Diophante d’Alexandrie, vers les années 250 de notre ère, fut le premier à rechercher systématiquement les solutions en nombres entiers, ou rationnels, d’une équation ou d’un système d’équations polynomiales à coefficients entiers. Bien que ce ne …   Encyclopédie Universelle

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”