Davenport-Schinzelova sekvence

V kombinatorice je Davenport-Schinzelova sekvence posloupnost znaků , ve kterých se libovolné dva znaky mohou objevit ve střídavém pořadí omezený počet časů. Maximální možná délka Davenport-Schinzelovy sekvence je omezena počtem znaků vynásobeným malým konstantním faktorem, který závisí na počtu povolených prokládání. Davenport-Schinzelovy sekvence byly poprvé definovány v roce 1965 Haroldem Davenportem a Andrzejem Schinzelem pro analýzu lineárních diferenciálních rovnic . Po Atalle [1] se tyto posloupnosti a hranice jejich délek staly standardním nástrojem v kombinatorické geometrii a v analýze geometrických algoritmů [2] .

Definice

O konečné posloupnosti U = u 1 , u 2 , u 3 se říká, že je Davenport-Schinzelova posloupnost řádů s , pokud splňuje následující dvě vlastnosti:

Žádné dvě po sobě jdoucí hodnoty v sekvenci nejsou stejné.
Pokud jsou x a y dvě různé hodnoty objevující se v sekvenci, pak sekvence neobsahuje podsekvenci … x , … y , …, x , …, y , … sestávající ze s + 2 střídavých hodnot x a y .

Například sekvence

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

je Davenport-Schinzelova posloupnost řádu 3 – obsahuje střídající se posloupnost o délce čtyři, například ...1, ...2, ...1, ...2, ... (objevuje se čtyřmi různými způsoby jako posloupnost plné posloupnosti), ale neobsahuje podsekvenci o délce pět.

Pokud Davenport-Schinzelova sekvence řádu s obsahuje n různých hodnot, nazývá se ( n , s ) Davenport-Schinzelova sekvence nebo DS ( n , s )-sekvence [3] .

Omezení délky

Složitost DS ( n , s )-sekvence je analyzována asymptoticky , protože n jde do nekonečna, za předpokladu, že s je konstanta a jsou známy téměř přesné hranice pro všechna s . Označme λ s ( n ) délku nejdelší DS ( n , s )-posloupnosti. Nejznámější λovy meze používají inverzní Ackermannovu funkci

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

kde A je Ackermannova funkce. Vzhledem k velmi rychlému růstu Ackermannovy funkce roste její inverzní funkce velmi pomalu a u většiny problémů jakékoli praktické velikosti nepřesahuje 4 [4] .

Pokud použijete označení "O" velké , jsou známy následující hranice:

$\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] . Tato vazba složitosti může být realizována až do konstanty segmenty — v roviněje takové uspořádání n segmentů, jejichž spodní obálka má složitost Ω( 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] .

Pro sudé a liché hodnoty s ≥ 6

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

, kde [14] [15] [12] .

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

Hodnota λ s ( n ) je také známá, pokud s je proměnná a n je malá konstanta [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).

Pokud je s funkcí n , horní a dolní hranice Davenport-Schinzelovy posloupnosti nejsou přesné.

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

Aplikace na spodní obálky

Spodní obálka množiny funkcí ƒ i ( x ) reálné proměnné x je funkce daná bodovým minimem:

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

Předpokládejme, že tyto funkce mají velmi dobré chování – všechny jsou spojité a libovolné dvě z nich jsou stejné maximálně v hodnotách s . Za těchto předpokladů lze reálnou osu rozdělit do konečného počtu intervalů , v rámci kterých má jedna funkce hodnoty menší než hodnoty všech ostatních funkcí. Posloupnost takových intervalů, označená minimální funkcí v rámci každého intervalu, tvoří Davenport-Schinzelovu sekvenci řádů s . Jakákoli horní mez složitosti Davenport-Schinzelovy sekvence s tímto řádem tedy také omezuje počet intervalů v takové reprezentaci spodní obálky.

Původní Davenport-Shinzelova aplikace zvažovala funkce, které jsou různými řešeními stejné homogenní lineární diferenciální rovnice řádů s . Libovolná dvě různá řešení mají nanejvýš s společných hodnot, takže spodní obálka množiny n různých řešení tvoří DS ( n , s )-posloupnost.

Stejný koncept dolní obálky lze aplikovat na funkce, které jsou pouze po částech spojité nebo pouze definované na intervalech reálné osy. V tomto případě jsou však k posloupnosti přidány body nespojitosti funkcí a konce intervalů, ve kterých je každá funkce uvedena. Například nevertikální segment v rovině lze interpretovat jako graf funkce , která mapuje x bodů intervalu na odpovídající hodnoty y a spodní obálka sady segmentů tvoří Davenport-Schinzelovu sekvenci řádu tři, protože libovolné dva segmenty mohou tvořit prokládanou sekvenci o délce nejvýše 4.

Viz také

Slovo bez čtverce

Poznámky

↑ Atallah, 1985 .
↑ Sharir, Agarwal, 1995 , s. =x a 2.
↑ Sharir, Agarwal, 1995 , s. jeden.
↑ Sharir, Agarwal, 1995 , s. čtrnáct.
↑ 1 2 Sharir, Agarwal, 1995 , str. 6.
↑ Sharir, Agarwal, 1995 , s. 12-42 Kapitola 2.
↑ Hart, Sharir, 1986 .
↑ 1 2 Wiernik, Sharir, 1988 .
↑ Komjath, 1988 .
↑ Klazar, 1999 .
↑ Nivasch, 2009 .
↑ 1 2 3 4 Pettie, 2015 .
↑ Sharir, Agarwal, 1995 , s. 86–114 Kapitola 4.
↑ 1 2 Sharir, Agarwal, 1995 , str. 43-85 Kapitola 3.
↑ 1 2 Agarwal, Sharir, Shor, 1989 .
↑ 1 2 Roselle, Stanton, 1970/71 .
↑ 1 2 3 Wellman, Pettie, 2016 .

Literatura

Agarwal PK, Sharir M., Shor P. Ostré horní a dolní hranice délky obecných Davenport-Schinzelových sekvencí // Journal of Combinatorial Theory, Series A. - 1989. - Vol. 52 , no. 2 . — S. 228–274 . - doi : 10.1016/0097-3165(89)90032-0 . .
Atallah MJ Některé problémy s dynamickou výpočetní geometrií // Počítače a matematika s aplikacemi . - 1985. - T. 11 . - S. 1171-1181 . - doi : 10.1016/0898-1221(85)90105-1 . .
Davenport H., Schinzel A. Kombinatorický problém spojený s diferenciálními rovnicemi // American Journal of Mathematics. - The Johns Hopkins University Press, 1965. - V. 87 , no. 3 . — S. 684–694 . - doi : 10.2307/2373068 . — .
Hart S., Sharir M. Nelinearita Davenport–Schinzelových sekvencí a zobecněných schémat komprese cest // Combinatorica. - 1986. - T. 6 , no. 2 . — S. 151–177 . - doi : 10.1007/BF02579170 .
Klazar M. O maximálních délkách Davenport–Schinzelových sekvencí // Současné trendy v diskrétní matematice. - American Mathematical Society, 1999. - V. 49. - S. 169-178. — (Řada DIMACS v diskrétní matematice a teoretické informatice).
Petr Komjath. Zjednodušená konstrukce nelineárních Davenportových–Schinzelových sekvencí // Journal of Combinatorial Theory, Series A. - 1988. - V. 49 , no. 2 . — S. 262–267 . - doi : 10.1016/0097-3165(88)90055-6 .
Mullin RC, Stanton RG Mapově teoretický přístup k Davenport-Schinzelovým sekvencím. // Pacific Journal of Mathematics. - 1972. - T. 40 . — S. 167–172 . - doi : 10.2140/pjm.1972.40.167 . (nedostupný odkaz)
Gabriel Nivasch. Vylepšené meze a nové techniky pro Davenport–Schinzelovy sekvence a jejich zobecnění // Proc. 20. ACM-SIAM Symp. Diskrétní algoritmy . - 2009. - S. 1–10. Archivováno 18. října 2012 na Wayback Machine
Roselle DP, Stanton RG Některé vlastnosti Davenport-Schinzelových sekvencí // Acta Arithmetica. — 1970/71. - T. 17 . — S. 355–362 .
Micha Sharir, Pankaj K. Agarwal. Davenport-Schinzelovy sekvence a jejich geometrické aplikace . - Cambridge University Press, 1995. - ISBN 0-521-47025-0 .
Stanton RG, Dirksen PH Davenport-Schinzel sekvence. // Ars Combinatoria. - 1976. - svazek 1 , vydání. 1 . — s. 43–51 .
Stanton RG, Roselle DP Výsledek Davenport-Schinzelových sekvencí // Kombinatorická teorie a její aplikace, III (Proc. Colloq., Balatonfüred, 1969). - Severní Holandsko, 1970. - S. 1023-1027.
Ady Wiernik, Micha Sharir. Rovinné realizace nelineárních Davenportových–Schinzelových sekvencí po segmentech // Diskrétní a výpočetní geometrie. - 1988. - svazek 3 , vydání. 1 . — S. 15–47 . - doi : 10.1007/BF02187894 .
Seth Petty. Ostré hranice pro Davenport-Schinzelovy sekvence každého řádu // J. ACM. - 2015. - T. 62 , č.p. 5 . - doi : 10.1145/2794075 .
Julian Wellman, Seth Pettie. Dolní hranice Davenport-Schinzelových sekvencí prostřednictvím obdélníkových Zarankiewiczových matic . - 2016. - arXiv : 1610.09774 .

Odkazy

Davenport-Schinzel Sequence , z MathWorld .
Davenport-Schinzel Sequences , část v knize Motion Planning , Steven M. LaValle.