ダヴェンポート・シンツェル列

組合せ論において、ダヴェンポート・シンツェル列（ダヴェンポート・シンツェルれつ、Davenport–Schinzel sequence）は、任意の2つの記号が交互に現れる回数が一定以下であるという条件を満たす列である。ダーベンポート‐チンゼル列とも。最長のダヴェンポート・シンツェル列の長さは、列中の記号の種類数に対してほとんど線形 (しかし正確に線形ではない) で上から抑えられる。ダヴェンポート・シンツェル列は、線型微分方程式を解析するために、ハロルド・ダヴェンポートとアンドルゼイ・チンゼルとも。によって1965年に初めて定義された。以降、これらの列とその長さの評価は、離散幾何学および計算幾何学アルゴリズムの解析における標準的な道具にもなっている。, pp. x and 2.

定義列が、次の2つの性質を満たすとき、次数（order）のダヴェンポート・シンツェル列であるという。列の中で隣り合う2つの値は異なる列に現れる相異なる2つの値とに対して、列は個の値からなる、の形の交互部分列を含まない。

例えば、列 1, 2, 1, 3, 1, 3, 2, 4, 5, 4, 5, 2, 3 は次数3のダヴェンポート・シンツェル列である。この列は、...1, ... 2, ... 1, ... 2, ... のような長さ4の交互部分列を含むが、長さ5の交互部分列は含まない。

種類の記号からなる次数のダヴェンポート・シンツェル列は、ダヴェンポート・シンツェル列、または -列と呼ばれる。この記法については , p. 1 を参照。

長さの評価 -列の長さの最大値は、を定数としを無限大にしたときの極限で漸近的な解析がなされている。すべてのについてほぼタイトな評価が知られている。最長の -列の長さをとする。に関して知られている最良の評価は、以下で定義される逆アッカーマン関数を含む。。ここではアッカーマン関数である。アッカーマン関数は非常に速く増加するため、その逆関数の増加は極めて遅く、実用上あり得る規模の問題ではその値は高々4である。, p. 14.

ビッグO記法およびビッグΘ記法を用いると、次の評価が知られている。。。, p. 6. 。。, Chapter 2, pp. 12–42; ; ; ; ; . この長さは、係数2を無視すれば、線分の下包絡線によって達成できる。すなわち、平面上に本の線分を配置して、その下包絡線の複雑度をとすることができる。, Chapter 4, pp. 86–114; . 。, Chapter 3, pp. 43–85; ; ; . 。。ならば。ここでである。, Chapter 3, pp. 43–85; ; ; .

が変数でが小さい定数の場合、の値も知られている。。

。

がの関数である場合、ダヴェンポート・シンツェル列に対する既知の上界と下界はタイトではない。のとき、かつである。; 。のとき、である。。のとき、である。。

下包絡線への応用

実変数の関数の集合に対する下包絡線とは、各点での最小値によって定まる関数である。。これらの関数が特に性質の良いもの、たとえばすべてが連続で、任意の2つが高々個の値でのみ等しいものだとする。この仮定のもとでは、数直線を有限個の区間に分割し、各区間内ではある関数が他のすべての関数より小さくなるようにできる。これらの区間を、それぞれの区間でどの関数が最小値を与えるかによってラベル付けして得られる列は、次数のダヴェンポート・シンツェル列を形成する。したがって、次数のダヴェンポート・シンツェル列の長さに対する上界は、下包絡線のこの表現に含まれる区間数の上界にもなる。

ダヴェンポートとシンツェルの元々の応用では、考察対象の関数は、次数の斉次線型微分方程式に対する相異なる解の集合であった。相異なる2つの解は高々個の値で共通の値をとるため、個の解の下包絡線は -列を形成する。

下包絡線の概念は、区分的に連続な関数や、実数直線上のある区間でのみ定義された関数にも適用できる。ただしこの場合、関数の不連続点や、各関数が定義される区間の端点が列の次数に加算される。例えば、平面上の鉛直でない線分は、の値の区間を対応するの値へ写す関数のグラフと解釈できる。線分の集合の下包絡線は次数3のダヴェンポート・シンツェル列を形成する。これは、任意の2本の線分が長さ高々4の交互部分列しか形成できないためである。

ダヴェンポート・シンツェル列

Źródło i licencja