達文波特-欣策爾序列

在组合数学中，達文波特–欣策爾序列是指对任意两个符号交替出现的次数作出限制的序列。達文波特–欣策爾序列其最大长度的界等于序列中不同符号的数目乘以一个渐近意义上很小但并非常数的因子，该因子取决于前述的交替次数上限。達文波特–欣策爾序列最早是由哈罗德·达文波特和安杰伊·欣策尔于 1965 年为研究线性微分方程而定义的。该序列及其长度的渐近界继 Atallah (1985) 一文之后成为了离散几何与几何算法分析领域的标准工具。

定义

有限序列 U = u₁, u₂, u₃, ... 满足下列条件时被称作是 s 阶 達文波特–欣策爾序列：

1. 任意两个相邻的元素不相等。
2. 若 x 和 y 是序列中不同的两个元素，那么该序列中不包含 x 和 y 交替出现，共有 s + 2 个数值的子序列 ... x, ... y, ..., x, ..., y, ...。

例如，序列

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

是一个 3 阶 達文波特-欣策爾序列：它包含了长度为 4 的交替序列，如 ...1, ... 2, ... 1, ... 2, ... （作为子序列在整个序列中出现了 4 次），但它并不包含任何长度为 5 的交替序列。

如果一个 s 阶 達文波特-欣策爾序列包含了 n 个不同的值，就称其为 (n,s) 達文波特-欣策爾序列，或称 DS(n,s) 序列。

长度的界

相关文献已经研究了 DS(n,s) 序列在渐近意义上的复杂度：对于 n 趋于无穷，假设 s 是固定的常数，已经得出了对于所有 s 的近乎紧确的界。令 λ_s(n) 表示最长的 DS(n,s) 序列的长度。目前已知的 λ_s 的最佳的界可用反阿克曼函数

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

来描述。其中 A 是阿克曼函数。由于阿克曼函数增长得很快，其反函数的增长就非常慢，以至于在所有的实际规模的问题中，该函数的值都不会超过常数 4。

用大O符号和大Θ符号可以表述下面这些已知的渐近界：

• λ₁(n) = n.
• λ₂(n) = 2n − 1.
• $2n\alpha (n)-O(n)\leq \lambda _{3}(n)\leq 2n\alpha (n)+O(n{\sqrt {\alpha (n)}})$. 这个界可以在常数因子的误差范围内达到：对于平面上的 n 条线段，存在一种摆放它们的方式，使得它们的下包络线（英語：lower envelope）的线段条数的复杂度达到 Ω(n α(n))。
• 对于 s ≥ 4 且 s 为偶数，

$\lambda _{s}(n)=n\cdot 2^{{\frac {1}{t!}}\alpha (n)^{t}(1+o(1))}$, 其中 t = (s − 2)/2.

• 对于 s ≥ 5 且 s 为奇数，目前已知的最佳的界是

$\lambda _{s}(n)<n\cdot 2^{{\frac {1}{t!}}\alpha (n)^{t}\log \alpha (n)(1+o(1))}$, 其中 t = (s − 3)/2.

然而这个界并未被确认是紧确的。

当 s 是变量而 n 是一个很小的常数时，λ_s(n) 的值目前也已知道：

$\lambda _{s}(2)=s+1\,$

$\lambda _{s}(3)=3s-2+(s\,{\bmod {\,}}2)$

$\lambda _{s}(4)=6s-2+(s\,{\bmod {\,}}2).$

在下包络线中的应用

由一组线段的下包络线形成的一个 3 阶 達文波特-欣策爾序列

以实数 x 为变量的函数族 ƒ_i(x) 的下包络线（英語：lower envelope）可用这族函数逐点取的最小值

ƒ(x) = min_iƒ_i(x)

来描述。 我们假定这族函数都非常理想化：它们都是连续的，而且它们之中任意两个函数都只能在最多 s 个自变量取值处相等。有了这些假设，我们就可以把实数轴划分为有限个区间，使得在每一个这样的区间当中，都存在一个函数，其值比其他任何函数的值都要小。用某个区间上值最小的函数为该区间标上号，这些区间所形成的序列就是一个 s 阶 達文波特-欣策爾序列。因此，s 阶 達文波特-欣策爾序列长度的上界也就是下包络线在这种表示方法中区间数目的上界。

在达文波特和欣策尔最初提出的应用当中，上述函数族就是某个 s 阶齐次线性微分方程的不同的解之集合。任意两个不同的解最多只能有 s 个相同的值，所以 n 个两两不同的解的下包络线就可形成一个 DS(n,s) 序列。

下包络线的概念也可以应用于分段连续或仅在实数轴的某些区间上才有定义的函数族；但在这些情况下，计算達文波特-欣策爾序列的阶时，不仅要算不同的函数其图像最多能在几个点处相交，函数中不连续点的个数和函数定义区间的端点个数也要算。例如，平面上一条非竖直的线段可看作是把某个区间上的 x 值映射到相应的 y 值的函数图形，而一族这样的线段的下包络线形成的是3 阶的達文波特-欣策爾序列，因为任何两条线段可以形成长度最大为 4 的交替子序列。

另见

• 无平方字

参考文献

• Agarwal, P. K.; Sharir, Micha; Shor, P., Sharp upper and lower bounds on the length of general Davenport–Schinzel sequences, Journal of Combinatorial Theory, Series A, 1989, 52 (2): 228–274, MR 1022320, doi:10.1016/0097-3165(89)90032-0 .
• Atallah, Mikhail J., Some dynamic computational geometry problems, Computers and Mathematics with Applications, 1985, 11: 1171–1181, MR 0822083, doi:10.1016/0898-1221(85)90105-1 .
• Davenport, H.; Schinzel, Andrzej, A combinatorial problem connected with differential equations, American Journal of Mathematics (The Johns Hopkins University Press), 1965, 87 (3): 684–694, JSTOR 2373068, MR 0190010, doi:10.2307/2373068 .
• Hart, S.; Sharir, Micha, Nonlinearity of Davenport–Schinzel sequences and of generalized path compression schemes, Combinatorica, 1986, 6 (2): 151–177, MR 0875839, doi:10.1007/BF02579170 .
• Klazar, M., On the maximum lengths of Davenport–Schinzel sequences, Contemporary Trends in Discrete Mathematics, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 49, American Mathematical Society: 169–178, 1999 .
• Komjáth, Péter, A simplified construction of nonlinear Davenport–Schinzel sequences, Journal of Combinatorial Theory, Series A, 1988, 49 (2): 262–267, MR 0964387, doi:10.1016/0097-3165(88)90055-6 .
• Mullin, R. C.; Stanton, R. G., A map-theoretic approach to Davenport-Schinzel sequences., Pacific Journal of Mathematics, 1972, 40: 167–172, MR 0302601, doi:10.2140/pjm.1972.40.167 .
• Nivasch, Gabriel, Improved bounds and new techniques for Davenport–Schinzel sequences and their generalizations, Proc. 20th ACM-SIAM Symp. Discrete Algorithms (PDF): 1–10, 2009 [2014-07-09], arXiv:0807.0484 , （原始内容 (PDF)存档于2012-10-18） .
• Roselle, D. P.; Stanton, R. G., Some properties of Davenport-Schinzel sequences, Acta Arithmetica, 1970/71, 17: 355–362, MR 0284414  .
• Sharir, Micha; Agarwal, Pankaj K., Davenport–Schinzel Sequences and Their Geometric Applications, Cambridge University Press, 1995, ISBN 0-521-47025-0 .
• Stanton, R. G.; Dirksen, P. H., Davenport-Schinzel sequences., Ars Combinatoria, 1976, 1 (1): 43–51, MR 0409347 .
• Stanton, R. G.; Roselle, D. P., A result on Davenport-Schinzel sequences, Combinatorial theory and its applications, III (Proc. Colloq., Balatonfüred, 1969), Amsterdam: North-Holland: 1023–1027, 1970, MR 0304189 .
• Wiernik, Ady; Sharir, Micha, Planar realizations of nonlinear Davenport–Schinzel sequences by segments, Discrete & Computational Geometry, 1988, 3 (1): 15–47, MR 0918177, doi:10.1007/BF02187894 .

外部链接

• Davenport-Schinzel Sequence （页面存档备份，存于互联网档案馆）（MathWorld 上的页面）
• Davenport-Schinzel Sequences （页面存档备份，存于互联网档案馆），Motion Planning 一书中的一节，作者是 Steven M. LaValle。