Sekvensen Davenport–Schinzel

I kombinatorik är en Davenport-Schinzel-sekvens en sekvens av symboler där antalet gånger två symboler kan visas omväxlande är begränsat. Den maximala möjliga längden på en Davenport–Schinzel-sekvens begränsas av antalet distinkta symboler multiplicerat med en liten men icke-konstant faktor som beror på antalet tillåtna alternationer. Davenport-Schinzel-sekvenser definierades först 1965 av Harold Davenport och Andrzej Schinzel för att analysera linjära differentialekvationer . Efter Atallah (1985) har dessa sekvenser och deras längdgränser också blivit ett standardverktyg inom diskret geometri och i analysen av geometriska algoritmer .

Definition

En finit sekvens U = u ₁ , u ₂ , u ₃ sägs vara en Davenport–Schinzel-sekvens av ordning s om den uppfyller följande två egenskaper:

1. Inga två på varandra följande värden i sekvensen är lika med varandra.
2. Om x och y är två distinkta värden som förekommer i sekvensen, så innehåller sekvensen inte en undersekvens ... x , ... y , ..., x , ..., y , ... bestående av s + 2 värden alternerande mellan x och y .

Till exempel sekvensen

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

är en Davenport–Schinzel-sekvens av ordning 3: den innehåller alternerande undersekvenser av längd fyra, såsom ...1, ... 2, ... 1, ... 2, ... (som visas på fyra olika sätt som en undersekvens av hela sekvensen) men den innehåller inte några alternerande undersekvenser av längd fem.

Om en Davenport–Schinzel-sekvens av ordning s innehåller n distinkta värden, kallas den en ( n , s ) Davenport–Schinzel-sekvens, eller en DS ( n , s )-sekvens.

Längdgränser

Komplexiteten hos DS ( n , s )-sekvensen har analyserats asymptotiskt i gränsen när n går till oändlighet, med antagandet att s är en fast konstant, och nästan snäva gränser är kända för alla s . Låt λ _s ( n ) beteckna längden på den längsta DS ( n , s )-sekvensen. De bästa gränserna som är kända för λ _s involverar den omvända Ackermann-funktionen

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

där A är Ackermann-funktionen. På grund av den mycket snabba tillväxten av Ackermann-funktionen, växer dess inversa α mycket långsamt och är som mest fyra för problem av vilken praktisk storlek som helst.

Genom att använda big O och big Θ notation är följande gränser kända:

• $\lambda _{0}(n)=1$ .
• $\lambda _{1}(n)=n$ .
• $\lambda _{2}(n)=2n-1$ .
• $\lambda _{3}(n)=2n\alfa (n)+O(n)$ . Denna komplexitetsgräns kan realiseras till inom en faktor 2 av linjesegment: det finns arrangemang av n linjesegment i planet vars lägre envelopper har komplexiteten Ω( n α( n )).
• $\lambda _{4}(n)=\Theta (n2^{\alpha (n)})$ .
• $\lambda _{5}(n)=\Theta (n\alpha (n)2^{\alpha (n)} )$ .
• För både jämna och udda värden på s ≥ 6,

$\lambda _{s}(n)=n\cdot 2^{{\frac {1}{t!}}\alpha (n )^{t}+O(\alpha (n)^{t-1})}$ , där $t=\left\lfloor {\frac {s-2}{ 2}}\höger\rgolv$ .

Värdet på λ _s ( n ) är också känt när s är variabel men n är en liten konstant:

$\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}}).$

När s är en funktion av n är de övre och nedre gränserna på Davenport-Schinzel-sekvenser inte snäva.

• När $s>n^{1/t}(t-1)!$ , $\lambda _{s}(n )=\Omega (n^{2}s/(t-1)!)$ och $\lambda _{s}(n)=O(n^ {2}s)$ .
• När $\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}\right)$ .
• När $s\leq \log \log n$ , $\lambda _{s}(n)=\Omega (n2 ^{s})$ .

Applicering på lägre kuvert

En Davenport–Schinzel-sekvens av ordning 3 bildad av den nedre enveloppen av linjesegment.

Den nedre enveloppen för en uppsättning funktioner ƒ _i ( x ) av en reell variabel x är funktionen som ges av deras punktvisa minimum:

ƒ( x ) = min _i ƒ _i ( x ).

Anta att dessa funktioner är särskilt väluppförda: de är alla kontinuerliga , och vilka två av dem är lika på högst s värden. Med dessa antaganden kan den reella linjen delas upp i ändligt många intervall inom vilka en funktion har värden som är mindre än alla de andra funktionerna. Sekvensen av dessa intervall, märkt av minimeringsfunktionen inom varje intervall, bildar en Davenport–Schinzel-sekvens av ordningsföljder . Således begränsar varje övre gräns för komplexiteten hos en Davenport-Schinzel-sekvens av denna ordning också antalet intervall i denna representation av det nedre höljet.

I den ursprungliga tillämpningen av Davenport och Schinzel var funktionerna som övervägdes en uppsättning olika lösningar på samma homogena linjära differentialekvation av ordningen s . Vilken som helst två distinkta lösningar kan ha högst s- värden gemensamma, så den nedre enveloppen av en uppsättning av n distinkta lösningar bildar en DS ( n , s )-sekvens.

Samma koncept med ett lägre envelopp kan också tillämpas på funktioner som endast är styckvis kontinuerliga eller som definieras endast över intervaller av den reella linjen; i det här fallet läggs emellertid diskontinuitetspunkterna för funktionerna och ändpunkterna för det intervall inom vilket varje funktion definieras till ordningen i sekvensen. Till exempel kan ett icke-vertikalt linjesegment i planet tolkas som grafen för en funktion som mappar ett intervall av x -värden till deras motsvarande y- värden, och den nedre enveloppen av en samling linjesegment bildar en Davenport–Schinzel-sekvens av ordning tre eftersom vilka två linjesegment som helst kan bilda en alternerande undersekvens med längd som högst fyra.

Se även

• Kvadratfritt ord

Anteckningar

•   Agarwal, PK ; Sharir, Micha ; Shor, P. (1989), "Sharp övre och nedre gränser på längden av allmänna Davenport–Schinzel-sekvenser", Journal of Combinatorial Theory, Series A , 52 ( 2): 228–274, doi : 10.1016/0097-3165( 89)90032-0 , MR 1022320 .
•   Atallah, Mikhail J. (1985), "Some dynamic computational geometry problems", Computers and Mathematics with Applications , 11 (12): 1171–1181, doi : 10.1016/0898-1221(85)90105-1 , MR 830 8 .
•   Davenport, H .; Schinzel, Andrzej ( 1965), "Ett kombinatoriskt problem kopplat till differentialekvationer", American Journal of Mathematics , The Johns Hopkins University Press, 87 (3): 684–694, doi : 10.2307/ 2373068 , JSTOR 23730601   .
•    Hart, S.; Sharir, Micha (1986), "Nonlinearity of Davenport–Schinzel sequences and of generalized path compression schemes", Combinatorica , 6 (2): 151–177, doi : 10.1007/BF02579170 , MR 0875839 , S864ID 1 , S864ID 1 .
• Klazar, M. (1999), "On the maximum lengths of Davenport–Schinzel-sekvenser", Contemporary Trends in Discrete Mathematics , DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 49, American Mathematical Society, s. 169–178 .
•   Komjáth, Péter (1988), "En förenklad konstruktion av icke-linjära Davenport–Schinzel-sekvenser", Journal of Combinatorial Theory, Series A , 49 ( 2): 262–267, doi : 10.1016/0097-3165(88)90055-6 , MR 0964387 .
•   Mullin, RC; Stanton, RG (1972), "En kartteoretisk strategi för Davenport-Schinzel-sekvenser." , Pacific Journal of Mathematics , 40 : 167–172, doi : 10.2140/pjm.1972.40.167 , MR 0302601 .
•   Nivasch, Gabriel (2009), "Förbättrade gränser och nya tekniker för Davenport–Schinzel-sekvenser och deras generaliseringar", Förbättrade gränser och nya tekniker för Davenport--Schinzel-sekvenser och deras generaliseringar (PDF) , vol. 57, s. 1–10, arXiv : 0807.0484 , Bibcode : 2008arXiv0807.0484N , doi : 10.1145/1706591.1706597 , S2CID 317557 från 1PD-arkivet 1F-1F5 från originalet 1PD -1F57-0 8 , hämtad 2009-01-08 .
•   Roselle, DP ; Stanton, RG (1971), "Some properties of Davenport-Schinzel sequences", Acta Arithmetica , 17 (4): 355-362, doi : 10.4064/aa-17-4-355-362 , MR 0284414 .
•   Sharir, Micha ; Agarwal, Pankaj K. (1995), Davenport–Schinzel Sequences and Their Geometric Applications , Cambridge University Press, ISBN 0-521-47025-0 .
•   Stanton, RG; Dirksen, PH (1976), "Davenport-Schinzel-sekvenser", Ars Combinatoria , 1 (1): 43-51, MR 0409347 .
•   Stanton, RG; Roselle, DP (1970), "A result on Davenport-Schinzel sequences", Combinatorial theory and its applications, III (Proc. Colloq., Balatonfüred, 1969) , Amsterdam: North-Holland, s. 1023–1027, MR 0304189 .
•   Wiernik, Ady; Sharir, Micha (1988), "Planar realizations of nonlinar Davenport–Schinzel sequences by segments", Discrete & Computational Geometry , 3 (1): 15–47, doi : 10.1007/BF02187894 , MR 0918177 .
• Pettie, Seth (2015), "Sharp bounds on Davenport-Schinzel sequences of every order", J. ACM , 62 (5): 1–40, arXiv : 1204.1086 , doi : 10.1145/2794075 .
• Wellman, Julian; Pettie, Seth (2016), Nedre gränser för Davenport-Schinzel-sekvenser via rektangulära Zarankiewicz-matriser , arXiv : 1610.09774 , Bibcode : 2016arXiv161009774W .

externa länkar

• Davenport-Schinzel Sequence , från MathWorld .
• Davenport-Schinzel Sequences , ett avsnitt i boken Motion Planning , av Steven M. LaValle.