Secvența Davenport-Schinzel

În combinatorică , o secvență Davenport-Schinzel este o secvență de caractere în care oricare două caractere pot apărea în ordine alternantă de un număr limitat de ori. Lungimea maximă posibilă a unei secvențe Davenport-Schinzel este limitată de numărul de caractere înmulțit cu un mic factor constant care depinde de numărul de intercalări permise. Secvențele Davenport-Schinzel au fost definite pentru prima dată în 1965 de Harold Davenport și Andrzej Schinzel pentru analiza ecuațiilor diferențiale liniare . În urma lui Atalla [1] , aceste secvențe și limite pe lungimile lor au devenit un instrument standard în geometria combinatorie și în analiza algoritmilor geometrici [2] .

Definiție

Se spune că o secvență finită U = u 1 , u 2 , u 3 este o secvență Davenport-Schinzel de ordinul s dacă îndeplinește următoarele două proprietăți:

Nu există două valori consecutive dintr-o secvență egale între ele.
Dacă x și y sunt două valori distincte care apar într-o secvență, atunci secvența nu conține o subsecvență … x , … y , …, x , …, y , … constând din s + 2 alte valori x și y .

De exemplu, secvența

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

este o secvență Davenport-Schinzel de ordinul 3 - conține o secvență alternativă de lungime patru, cum ar fi ...1, ...2, ...1, ...2, ... (apare în patru moduri diferite ca o secvență a secvenței complete), dar nu conține o subsecvență de lungime cinci.

Dacă o secvență Davenport-Schinzel de ordin s conține n valori distincte, se numește ( n , s ) o secvență Davenport-Schinzel sau o secvență DS ( n , s ) [3] .

Limite de lungime

Complexitatea unei secvențe DS ( n , s ) este analizată asimptotic pe măsură ce n merge la infinit, presupunând că s este o constantă și se cunosc limite aproape exacte pentru toți s . Fie λ s ( n ) să desemneze lungimea celei mai lungi secvențe DS ( n , s ). Cele mai cunoscute limite λs folosesc funcția Ackermann inversă

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

unde A este funcția Ackermann. Datorită creșterii foarte rapide a funcției Ackermann, inversul acesteia crește foarte lent și nu depășește 4 pentru majoritatea problemelor de orice dimensiune practică [4] .

Dacă utilizați notația „O” mare , se cunosc următoarele limite:

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

$\lambda _{3}(n)=2n\alpha (n)+O(n)$ [6] [7] [8] [9] [10] [11] [12] . Această complexitate legată poate fi realizată până la o constantă prin segmente — există un astfel de aranjament de n segmente pe plan, a cărui anvelopă inferioară are complexitatea Ω( n α( n )) [13] [8] .

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

Pentru valorile pare și impare s ≥ 6

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

, unde [14] [15] [12] .

t=\left\lfloor {\frac {s-2}{2}}\right\rfloor

Valoarea lui λ s ( n ) este cunoscută și dacă s este variabilă și n este o constantă mică [16] :

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

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

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

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

Dacă s este o funcție a lui n , limitele superioare și inferioare ale secvenței Davenport-Schinzel nu sunt exacte.

Dacă , și [16] [17] . $s>n^{1/t}(t-1)!$ $\lambda _{s}(n)=\Omega (n^{2}s/(t-1)!)$ $\lambda _{s}(n)=O(n^{2}s)$
Dacă , [17] . $\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}\dreapta)$
Dacă , [17] . $s\leq \log \log n$ $\lambda _{s}(n)=\Omega (n2^{s})$

Aplicație pentru a coborî plicurile

Anvelopa inferioară a mulțimii de funcții ƒ i ( x ) a variabilei reale x este funcția dată de minimul punctual:

ƒ( x ) = min i ƒ i ( x ).

Să presupunem că aceste funcții au un comportament foarte bun - toate sunt continue și oricare două dintre ele sunt cel mult egale în s valori. Conform acestor ipoteze, axa reală poate fi împărțită într-un număr finit de intervale , în cadrul fiecăruia dintre acestea o funcție are valori mai mici decât valorile tuturor celorlalte funcții. O secvență de astfel de intervale, etichetată de funcția minimă în fiecare interval, formează o secvență Davenport-Schinzel de ordinul s . Astfel, orice limită superioară a complexității unei secvențe Davenport-Schinzel cu această ordine limitează, de asemenea, numărul de intervale într-o astfel de reprezentare a anvelopei inferioare.

Aplicația originală Davenport-Shinzel a luat în considerare funcții care sunt soluții diferite pentru aceeași ecuație diferențială liniară omogenă de ordinul s . Orice două soluții diferite au cel mult s valori comune, astfel încât anvelopa inferioară a mulțimii de n soluții diferite formează o secvență DS ( n , s ).

Același concept al anvelopei inferioare poate fi aplicat funcțiilor care sunt numai continue pe bucăți sau definite doar pe intervale ale axei reale. Totuși, în acest caz, punctele de discontinuitate ale funcțiilor și capetele intervalelor în care este dată fiecare funcție se adaugă secvenței. De exemplu, un segment non-vertical din plan poate fi interpretat ca un grafic al unei funcții care mapează punctele x ale intervalului la valorile y corespunzătoare , iar anvelopa inferioară a setului de segmente formează o secvență Davenport-Schinzel de ordinul trei, deoarece oricare două segmente pot forma o secvență intercalată cu lungimea de cel mult 4.

Vezi și

Cuvânt fără pătrat

Note

↑ Atallah, 1985 .
↑ Sharir, Agarwal, 1995 , p. =x și 2.
↑ Sharir, Agarwal, 1995 , p. unu.
↑ Sharir, Agarwal, 1995 , p. paisprezece.
↑ 1 2 Sharir, Agarwal, 1995 , p. 6.
↑ Sharir, Agarwal, 1995 , p. 12-42 Capitolul 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. 86–114 Capitolul 4.
↑ 1 2 Sharir, Agarwal, 1995 , p. 43-85 Capitolul 3.
↑ 1 2 Agarwal, Sharir, Shor, 1989 .
↑ 1 2 Roselle, Stanton, 1970/71 .
↑ 1 2 3 Wellman, Pettie, 2016 .

Literatură

Agarwal PK, Sharir M., Shor P. Limitele superioare și inferioare ascuțite ale lungimii secvențelor generale Davenport–Schinzel // Journal of Combinatorial Theory, Series A. - 1989. - Vol. 52 , nr. 2 . — S. 228–274 . - doi : 10.1016/0097-3165(89)90032-0 . .
Atallah MJ Câteva probleme de geometrie computațională dinamică // Calculatoare și matematică cu aplicații . - 1985. - T. 11 . - S. 1171-1181 . - doi : 10.1016/0898-1221(85)90105-1 . .
Davenport H., Schinzel A. O problemă combinatorie legată de ecuații diferențiale // American Journal of Mathematics. - The Johns Hopkins University Press, 1965. - V. 87 , nr. 3 . — S. 684–694 . - doi : 10.2307/2373068 . — .
Hart S., Sharir M. Nonlinearity of Davenport–Schinzel sequences and of generalized path compression schemes // Combinatorica. - 1986. - T. 6 , nr. 2 . — S. 151–177 . - doi : 10.1007/BF02579170 .
Klazar M. Despre lungimile maxime ale secvenţelor Davenport–Schinzel // Tendinţe contemporane în matematică discretă. - Societatea Americană de Matematică, 1999. - V. 49. - S. 169-178. — (Seria DIMACS în matematică discretă și informatică teoretică).
Peter Komjath. O construcție simplificată a secvențelor neliniare Davenport–Schinzel // Journal of Combinatorial Theory, Series A. - 1988. - V. 49 , nr. 2 . — S. 262–267 . - doi : 10.1016/0097-3165(88)90055-6 .
Mullin RC, Stanton RG O abordare teoretică a hărților a secvențelor Davenport-Schinzel. // Pacific Journal of Mathematics. - 1972. - T. 40 . — S. 167–172 . - doi : 10.2140/pjm.1972.40.167 . (link indisponibil)
Gabriel Nivasch. Limite îmbunătățite și tehnici noi pentru secvențele Davenport–Schinzel și generalizările lor // Proc. 20-a ACM-SIAM Symp. Algoritmi discreti . - 2009. - S. 1–10. Arhivat pe 18 octombrie 2012 la Wayback Machine
Roselle DP, Stanton RG Unele proprietăți ale secvențelor Davenport-Schinzel // Acta Arithmetica. — 1970/71. - T. 17 . — S. 355–362 .
Micha Sharir, Pankaj K. Agarwal. Secvențele Davenport–Schinzel și aplicațiile lor geometrice . - Cambridge University Press, 1995. - ISBN 0-521-47025-0 .
Stanton RG, Dirksen PH Davenport-Schinzel secvențe. // Ars Combinatoria. - 1976. - Vol. 1 , număr. 1 . — p. 43–51 .
Stanton RG, Roselle DP Un rezultat asupra secvențelor Davenport-Schinzel // Teoria combinatorie și aplicațiile sale, III (Proc. Colloq., Balatonfüred, 1969). - Olanda de Nord, 1970. - S. 1023-1027.
Ady Wiernik, Micha Sharir. Realizări plane ale secvențelor Davenport–Schinzel neliniare pe segmente // Geometrie discretă și computațională. - 1988. - Vol. 3 , numărul. 1 . — S. 15–47 . - doi : 10.1007/BF02187894 .
Seth Petty. Limite clare pe secvențele Davenport-Schinzel de fiecare ordin // J. ACM. - 2015. - T. 62 , nr. 5 . - doi : 10.1145/2794075 .
Julian Wellman, Seth Pettie. Limitele inferioare ale secvențelor Davenport-Schinzel prin matrice rectangulară Zarankiewicz . - 2016. - arXiv : 1610.09774 .

Link -uri

Secvența Davenport-Schinzel , de la MathWorld .
Davenport-Schinzel Sequences , o secțiune din cartea Motion Planning , de Steven M. LaValle.