Davenport-Schinzel sorozat

A kombinatorikában a Davenport-Schinzel sorozat olyan karaktersorozat , amelyben bármely két karakter felváltva jelenhet meg korlátozott számú alkalommal. A Davenport-Schinzel sorozat maximális lehetséges hosszát korlátozza a karakterek száma, szorozva egy kis állandó tényezővel, amely a megengedett sorváltások számától függ. A Davenport–Schinzel szekvenciákat először 1965-ben Harold Davenport és Andrzej Schinzel határozta meg lineáris differenciálegyenletek elemzésére . Atalla [1] nyomán ezek a sorozatok és hosszukra vonatkozó korlátok standard eszközzé váltak a kombinatorikus geometriában és a geometriai algoritmusok elemzésében [2] .

Definíció

Az U = u 1 , u 2 , u 3 véges sorozatot s rendű Davenport-Schinzel sorozatnak nevezzük, ha kielégíti a következő két tulajdonságot:

Egy sorozatban nincs két egymást követő érték egyenlő egymással.
Ha x és y két különböző érték, amelyek egy sorozatban jelennek meg, akkor a sorozat nem tartalmaz … x , … y , …, x , …, y , … részsorozatot, amely s + 2 váltakozó x és y értékből áll .

Például a sorozat

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

egy 3-as rendű Davenport-Schinzel sorozat - egy négyes hosszúságú váltakozó sorozatot tartalmaz, például ...1, ...2, ...1, ...2, ... (négy különböző módon jelenik meg a teljes sorozat sorozataként), de nem tartalmaz öt hosszúságú részsorozatot.

Ha egy s rendű Davenport-Schinzel sorozat n különböző értéket tartalmaz , akkor azt ( n , s ) Davenport-Schinzel sorozatnak vagy DS ( n , s ) sorozatnak nevezzük [3] .

Hosszhatárok

A DS ( n , s )-sorozat összetettségét aszimptotikusan elemezzük , miközben n a végtelenbe megy, feltételezve, hogy s konstans, és szinte pontos határai minden s -re ismertek . Jelölje λ s ( n ) a leghosszabb DS ( n , s ) sorozat hosszát. A legismertebb λ-határok az inverz Ackermann-függvényt használják

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

ahol A az Ackermann-függvény. Az Ackermann-függvény nagyon gyors növekedése miatt az inverze nagyon lassan növekszik, és a legtöbb gyakorlati méretű probléma esetében nem haladja meg a 4-et [4] .

Ha az "O" nagy jelölést használja , a következő határok ismertek:

$\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] . Ez a komplexitási korlát szegmensenként egy állandóig megvalósítható – a síkon van egy olyan n szegmensből álló elrendezés, amelynek alsó burkológörbéje Ω( n α( n )) [13] [8] bonyolultságú .

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

Páros és páratlan értékek esetén s ≥ 6

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

, ahol [14] [15] [12] .

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

λ s ( n ) értéke akkor is ismert, ha s változó és n kis konstans [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).

Ha s n függvénye , a Davenport-Schinzel sorozat felső és alsó korlátja nem pontos.

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

Alkalmazás alsó borítékokra

x valós változó ƒ i ( x ) függvényhalmazának alsó burkológörbéje a pontonkénti minimum által adott függvény:

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

Tegyük fel, hogy ezek a függvények nagyon jó viselkedésűek – mind folytonosak , és bármelyik kettő legfeljebb s értékben egyenlő. Ezen feltételezések szerint a valós tengely véges számú intervallumra osztható , amelyek mindegyikén belül egy függvénynek kisebb az értéke, mint az összes többi függvény értékénél. Az ilyen intervallumok sorozata, amelyet az egyes intervallumokon belüli minimumfüggvény jelöl, egy s sorrendű Davenport-Schinzel sorozatot alkot . Így egy Davenport-Schinzel sorozat komplexitásának bármely felső korlátja ebben a sorrendben korlátozza az intervallumok számát is az alsó burkológörbe ilyen ábrázolásában.

Az eredeti Davenport-Shinzel alkalmazás olyan függvényeket vett figyelembe, amelyek különböző megoldásai ugyanannak az s sorrendű homogén lineáris differenciálegyenletnek . Bármely két különböző megoldásnak legfeljebb s közös értéke van, így az n különböző megoldásból álló halmaz alsó burkológörbéje DS ( n , s )-sorozatot alkot.

Az alsó burkológörbe ugyanaz a koncepciója alkalmazható azokra a függvényekre, amelyek csak darabonként folytonosak, vagy csak a valós tengely intervallumain definiálhatók. Ebben az esetben azonban a függvények megszakítási pontjai és azon intervallumok végei, amelyekben az egyes függvények adottak, hozzáadódnak a sorozathoz. Például egy nem függőleges szakasz a síkban értelmezhető egy függvény grafikonjaként, amely leképezi az intervallum x pontjait a megfelelő y értékekre , és a szegmensek halmazának alsó burkológörbéje egy Davenport-Schinzel sorozatot alkot. sorrendben hármat, mivel bármely két szegmens legfeljebb 4 hosszúságú interleaved sorozatot alkothat.

Lásd még

Négyzet nélküli szó

Jegyzetek

↑ Atallah, 1985 .
↑ Sharir, Agarwal, 1995 , p. =x és 2.
↑ Sharir, Agarwal, 1995 , p. egy.
↑ Sharir, Agarwal, 1995 , p. tizennégy.
↑ 1 2 Sharir, Agarwal, 1995 , p. 6.
↑ Sharir, Agarwal, 1995 , p. 12-42 2. fejezet.
↑ 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 4. fejezet.
↑ 1 2 Sharir, Agarwal, 1995 , p. 43-85 3. fejezet.
↑ 1 2 Agarwal, Sharir, Shor, 1989 .
↑ 1 2 Roselle, Stanton, 1970/71 .
↑ 1 2 3 Wellman, Pettie, 2016 .

Irodalom

Agarwal PK, Sharir M., Shor P. Éles felső és alsó határok az általános Davenport–Schinzel-szekvenciák hosszában // 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éhány dinamikus számítási geometriai probléma // Számítógépek és matematika alkalmazásokkal . - 1985. - T. 11 . - S. 1171-1181 . - doi : 10.1016/0898-1221(85)90105-1 . .
Davenport H., Schinzel A. A differenciálegyenletekkel kapcsolatos kombinatorikus probléma // 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. Davenport–Schinzel-szekvenciák és az általánosított útvonaltömörítési sémák nemlinearitása // Combinatorica. - 1986. - T. 6 , sz. 2 . – S. 151–177 . - doi : 10.1007/BF02579170 .
Klazar M. A Davenport–Schinzel sorozatok maximális hosszáról // Contemporary Trends in Discrete Mathematics. - American Mathematical Society, 1999. - V. 49. - S. 169-178. — (DIMACS-sorozat a diszkrét matematikában és az elméleti számítástechnikában).
Komjath Péter. Nemlineáris Davenport–Schinzel-szekvenciák egyszerűsített konstrukciója // 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 A Davenport-Schinzel szekvenciák térképelméleti megközelítése. // Pacific Journal of Mathematics. - 1972. - T. 40 . – S. 167–172 . - doi : 10.2140/pjm.1972.40.167 . (nem elérhető link)
Gabriel Nivasch. Javított határok és új technikák Davenport–Schinzel szekvenciákhoz és általánosításaikhoz // Proc. 20. ACM-SIAM Symp. Diszkrét algoritmusok . - 2009. - S. 1–10. Archiválva : 2012. október 18. a Wayback Machine -nál
Roselle DP, Stanton RG A Davenport-Schinzel szekvenciák néhány tulajdonsága // Acta Arithmetica. – 1970/71. - T. 17 . – S. 355–362 .
Micha Sharir, Pankaj K. Agarwal. Davenport–Schinzel szekvenciák és geometriai alkalmazásaik . - Cambridge University Press, 1995. - ISBN 0-521-47025-0 .
Stanton RG, Dirksen PH Davenport-Schinzel szekvenciák. // Ars Combinatoria. - 1976. - 1. évf. , szám. 1 . – 43–51 .
Stanton RG, Roselle DP Eredmény Davenport-Schinzel szekvenciákon // Kombinatorikus elmélet és alkalmazásai, III (Proc. Colloq., Balatonfüred, 1969). - Észak-Hollandia, 1970. - S. 1023-1027.
Ady Wiernik, Micha Sharir. Nemlineáris Davenport–Schinzel sorozatok síkbeli megvalósításai szegmensenként // Discrete & Computational Geometry. - 1988. - 3. évf. , szám. 1 . – S. 15–47 . - doi : 10.1007/BF02187894 .
Seth Petty. Éles határok minden rendű Davenport-Schinzel sorozaton // J. ACM. - 2015. - T. 62 , sz. 5 . - doi : 10.1145/2794075 .
Julian Wellman, Seth Pettie. Davenport-Schinzel szekvenciák alsó határai téglalap alakú Zarankiewicz-mátrixokon keresztül . - 2016. - arXiv : 1610.09774 .

Linkek

Davenport-Schinzel Sequence , a MathWorld -ből .
Davenport-Schinzel Sequences , Steven M. LaValle Motion Planning című könyvének egy része .