Î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] .
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:
De exemplu, secvența
1, 2, 1, 3, 1, 3, 2, 4, 5, 4, 5, 2, 3este 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] .
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:
[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] .
Valoarea lui λ s ( n ) este cunoscută și dacă s este variabilă și n este o constantă mică [16] :
Dacă s este o funcție a lui n , limitele superioare și inferioare ale secvenței Davenport-Schinzel nu sunt exacte.
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.