Davenport-Schinzel-sekvens

Inom kombinatorik är en Davenport-Schinzel-sekvens en sekvens av tecken där vilka två tecken som helst kan förekomma i omväxlande ordning ett begränsat antal gånger. Den maximala möjliga längden på en Davenport-Schinzel-sekvens begränsas av antalet tecken multiplicerat med en liten konstant faktor som beror på antalet tillåtna sammanflätningar. Davenport-Schinzel-sekvenser definierades först 1965 av Harold Davenport och Andrzej Schinzel för analys av linjära differentialekvationer . Efter Atalla [1] har dessa sekvenser och gränser för deras längder blivit ett standardverktyg i kombinatorisk geometri och i analysen av geometriska algoritmer [2] .

Definition

En finit sekvens U = u 1 , u 2 , u 3 sägs vara en Davenport-Schinzel-sekvens av ordning s om den uppfyller följande två egenskaper:

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

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 en alternerande sekvens av längd fyra, såsom ...1, ...2, ...1, ...2, ... (uppträder på fyra olika sätt som en sekvens av den fullständiga sekvensen), men den innehåller inte en undersekvens av längden fem.

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

Längdgränser

Komplexiteten hos en DS ( n , s )-sekvens analyseras asymptotiskt när n går till oändligheten, förutsatt att s är en konstant och nästan exakta gränser för alla s är kända . Låt λ s ( n ) beteckna längden på den längsta DS ( n , s )-sekvensen. De mest kända λs-gränserna använder 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 invers mycket långsamt och överstiger inte 4 för de flesta problem av praktisk storlek [4] .

Om du använder notationen "O" big , är följande gränser kända:

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

$\lambda _{3}(n)=2n\alfa (n)+O(n)$ [6] [7] [8] [9] [10] [11] [12] . Denna komplexitetsbundna kan realiseras upp till en konstant av segment — det finns ett sådant arrangemang av n segment på planet, vars nedre envelopp har komplexiteten Ω( 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] .

För jämna och udda värden s ≥ 6

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

, där [14] [15] [12] .

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

Värdet på λ s ( n ) är också känt om s är variabel och n är en liten konstant [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).

Om s är en funktion av n är de övre och nedre gränserna för Davenport-Schinzel-sekvensen inte exakta.

Om , och [16] [17] . $s>n^{1/t}(t-1)!$ $\lambda _{s}(n)=\Omega (n^{2}s/(t-1)!)$ $\lambda _{s}(n)=O(n^{2}s)$
Om , [17] . ${\displaystyle \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}\höger)$
Om , [17] . $s\leq \log \log n$ $\lambda _{s}(n)=\Omega (n2^{s})$

Applikation för nedre kuvert

Den nedre enveloppen för uppsättningen funktioner ƒ i ( x ) för den reella variabeln x är funktionen som ges av det punktvisa minimumet:

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

Låt oss anta att dessa funktioner har mycket bra beteende - de är alla kontinuerliga och två av dem är högst lika i s -värden. Under dessa antaganden kan den reella axeln delas in i ett ändligt antal intervall , inom vart och ett av vilka en funktion har värden mindre än värdena för alla andra funktioner. En sekvens av sådana intervall, märkta med minimifunktionen inom varje intervall, bildar en Davenport-Schinzel-sekvens av ordning s . Således begränsar varje övre gräns för komplexiteten hos en Davenport-Schinzel-sekvens med denna ordning också antalet intervall i en sådan representation av det nedre höljet.

Den ursprungliga Davenport-Shinzel-applikationen ansåg funktioner som är olika lösningar på samma homogena linjära differentialekvation av ordningen s . Alla två olika lösningar har högst s gemensamma värden, så den nedre enveloppen av mängden av n olika lösningar bildar en DS ( n , s )-sekvens.

Samma koncept för det nedre höljet kan tillämpas på funktioner som endast är styckvis kontinuerliga eller endast definierade på intervaller av den reella axeln. Men i detta fall adderas diskontinuitetspunkterna för funktionerna och ändarna av intervallen i vilka varje funktion ges till sekvensen. Till exempel kan ett icke-vertikalt segment i planet tolkas som en graf av en funktion som mappar x -punkterna i intervallet till motsvarande y -värden , och den nedre enveloppen av uppsättningen av segment bildar en Davenport-Schinzel-sekvens av ordning tre, eftersom vilka två segment som helst kan bilda en sammanflätad sekvens av längd som högst 4.

Se även

Fyrkantlöst ord

Anteckningar

↑ Atallah, 1985 .
↑ Sharir, Agarwal, 1995 , sid. =x och 2.
↑ Sharir, Agarwal, 1995 , sid. ett.
↑ Sharir, Agarwal, 1995 , sid. fjorton.
↑ 1 2 Sharir, Agarwal, 1995 , sid. 6.
↑ Sharir, Agarwal, 1995 , sid. 12-42 2 kap.
↑ Hart, Sharir, 1986 .
↑ 1 2 Wiernik, Sharir, 1988 .
↑ Komjath, 1988 .
↑ Klazar, 1999 .
↑ Nivasch, 2009 .
↑ 1 2 3 4 Pettie, 2015 .
↑ Sharir, Agarwal, 1995 , sid. 86–114 4 kap.
↑ 1 2 Sharir, Agarwal, 1995 , sid. 43-85 3 kap.
↑ 1 2 Agarwal, Sharir, Shor, 1989 .
↑ 1 2 Roselle, Stanton, 1970/71 .
↑ 1 2 3 Wellman, Pettie, 2016 .

Litteratur

Agarwal PK, Sharir M., Shor P. Skarpa övre och nedre gränser på längden av allmänna Davenport–Schinzel-sekvenser // Journal of Combinatorial Theory, Series A. - 1989. - Vol. 52 , nr. 2 . — S. 228–274 . - doi : 10.1016/0097-3165(89)90032-0 . .
Atallah MJ Några problem med dynamisk beräkningsgeometri // Datorer och matematik med applikationer . - 1985. - T. 11 . - S. 1171-1181 . - doi : 10.1016/0898-1221(85)90105-1 . .
Davenport H., Schinzel A. Ett kombinatoriskt problem kopplat till differentialekvationer // 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. Icke-linjäritet av Davenport–Schinzel-sekvenser och generaliserade vägkomprimeringsscheman // Combinatorica. - 1986. - T. 6 , nr. 2 . — S. 151–177 . - doi : 10.1007/BF02579170 .
Klazar M. Om de maximala längderna av Davenport–Schinzel-sekvenser // Contemporary Trends in Discrete Mathematics. - American Mathematical Society, 1999. - V. 49. - S. 169-178. — (DIMACS-serien i diskret matematik och teoretisk datavetenskap).
Peter Komjath. En förenklad konstruktion av olinjära Davenport–Schinzel-sekvenser // 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 En kartteoretisk strategi för Davenport-Schinzel-sekvenser. // Pacific Journal of Mathematics. - 1972. - T. 40 . — S. 167–172 . - doi : 10.2140/pjm.1972.40.167 . (inte tillgänglig länk)
Gabriel Nivasch. Förbättrade gränser och nya tekniker för Davenport–Schinzel-sekvenser och deras generaliseringar // Proc. 20:e ACM-SIAM Symp. Diskreta algoritmer . - 2009. - S. 1–10. Arkiverad 18 oktober 2012 på Wayback Machine
Roselle DP, Stanton RG Vissa egenskaper hos Davenport-Schinzel-sekvenser // Acta Arithmetica. — 1970/71. - T. 17 . — S. 355–362 .
Micha Sharir, Pankaj K. Agarwal. Davenport–Schinzel-sekvenser och deras geometriska tillämpningar . - Cambridge University Press, 1995. - ISBN 0-521-47025-0 .
Stanton RG, Dirksen PH Davenport-Schinzel-sekvenser. // Ars Combinatoria. - 1976. - Vol. 1 , nummer. 1 . — s. 43–51 .
Stanton RG, Roselle DP Ett resultat av Davenport-Schinzel-sekvenser // Kombinatorisk teori och dess tillämpningar, III (Proc. Colloq., Balatonfüred, 1969). - Nord-Holland, 1970. - S. 1023-1027.
Ady Wiernik, Micha Sharir. Plana realiseringar av olinjära Davenport–Schinzel-sekvenser efter segment // Diskret och beräkningsgeometri. - 1988. - Vol. 3 , nummer. 1 . — S. 15–47 . - doi : 10.1007/BF02187894 .
Seth Petty. Skarpa gränser för Davenport-Schinzel-sekvenser av varje ordning // J. ACM. - 2015. - T. 62 , nr. 5 . - doi : 10.1145/2794075 .
Julian Wellman, Seth Pettie. Nedre gränser för Davenport-Schinzel-sekvenser via rektangulära Zarankiewicz-matriser . - 2016. - arXiv : 1610.09774 .

Länkar

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