×

Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences. (English) Zbl 0697.05003

From the text: We obtain optimal bounds for the maximal length \(\lambda_4(n)\) of an \((n,4)\) Davenport-Schinzel sequence (a \(\mathrm{DS}(n,4)\) sequence in short), and then extend them to improve and almost tighten the lower and upper bounds for \(\lambda_s(n)\), \(s>4\).
We obtain sharp upper and lower bounds on the maximal length \(\lambda_s(n)\) of \((n, s)\)-Davenport-Schinzel sequences, i.e., sequences composed of \(n\) symbols, having no two adjacent equal elements and containing no alternating subsequence of length \(s+2\). We show that
(i) \(\lambda_4(n) = \Theta(n\cdot 2^{\alpha(n)})\);
(ii) for \(s > 4\), \[ \lambda_s(n) \le n\cdot 2^{(\alpha(n))^{(s-2)2} + 2 C_s(n)} \] if \(s\) is even and \[ \lambda_s(n) \le n\cdot 2^{(\alpha(n))^{(s-3)2}\log(\alpha(n)) + C_s(n)} \] if \(s\) is odd, where \(C_s(n)\) is a function of \(\alpha(n)\) and \(s\), asymptotically smaller than the main term; and finally
(iii) for even values of \(s > 4\), \[ \lambda_s(n) = \Omega(n\cdot 2^{K_s(\alpha(n))^{(s-2)2}+ Q_s(n)} \] where \(K_s = (((s - 2)/2)!)^{-1}\) and \(Q_s\) is a polynomial in \(\alpha(n)\) of degree at most \((s - 4)/2\).

MSC:

11B83 Special sequences and polynomials
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

Online Encyclopedia of Integer Sequences:

Davenport-Schinzel numbers of degree n on 3 symbols.

References:

[1] Atallah, M., Comput. Math. Appl., 11, 1171-1181 (1985) · Zbl 0586.68085
[2] Balstan, A.; Sharir, M., On shortest paths between two convex polyhedra, J. ACM, 35, 267-287 (1988) · Zbl 0652.68043
[3] Clarkson, K., Approximate algorithms for shortest path motion planning, (Proc. 19th Annual ACM Symposium on Theory of Computing (1987)), 56-65
[4] Cole, R.; Sharir, M., Visibility problems for polyhedral terrains, J. Symbolic Computation, 7, 11-30 (1989)
[5] Davenport, H.; Schinzel, A., A combinatorial problem connected with differential equations, Amer. J. Math., 87, 684-689 (1965) · Zbl 0132.00601
[6] Davenport, H., A combinatorial problem connected with differential equations II, Acta Arith., 17, 363-372 (1971) · Zbl 0216.30204
[7] H. Edelsbrunner and M. Sharir\(nn\)Discrete Comput. Geom.; H. Edelsbrunner and M. Sharir\(nn\)Discrete Comput. Geom. · Zbl 0712.52009
[8] H. Edelsbrunner, L. Guibas, and M. SharirDiscrete Comput. Geom.; H. Edelsbrunner, L. Guibas, and M. SharirDiscrete Comput. Geom. · Zbl 0691.68035
[9] Guibas, L.; Sharir, M.; Sifrony, S., On the general motion planning problem with two degrees of freedom, Discrete Comput. Geom., 4 (1989), in press · Zbl 0685.68049
[10] Hart, S.; Sharir, M., Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes, Combinatorica, 6, 151-177 (1986) · Zbl 0636.05003
[11] K. Kedem and M. SharirDiscrete Comput. Geom.; K. Kedem and M. SharirDiscrete Comput. Geom. · Zbl 0688.68039
[12] Leven, D.; Sharir, M., On the number of critical free contacts of a convex polygonal objects moving in \(2-D\) polygonal space, Discrete Comput. Geom., 2, 255-270 (1987) · Zbl 0616.52009
[13] Ó’Dúnlaing, C.; Sharir, M.; Yap, C., Generalized Voronoi diagrams for a ladder. II. Efficient construction of the diagram, Algorithmica, 2, 27-59 (1987) · Zbl 0631.68042
[14] Pach, J.; Sharir, M., The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates, Discrete Comput. Geom., 4 (1989) · Zbl 0734.05054
[15] Pollack, R.; Sharir, M.; Sifrony, S., Separating two simple polygons by a sequence of translations, Discrete Comput. Geom., 3, 123-136 (1988) · Zbl 0646.68052
[16] Roselle, D. P.; Stanton, R. G., Some properties of Davenport-Schinzel sequences, Acta Arith., 17, 355-362 (1971) · Zbl 0215.33203
[17] J. Schwartz and M. SharirJ. Symbolic Computation; J. Schwartz and M. SharirJ. Symbolic Computation · Zbl 0717.68050
[18] Sharir, M., Almost linear upper bounds on the length of general Davenport-Schinzel sequences, Combinatorica, 7, 131-143 (1987) · Zbl 0636.05004
[19] Sharir, M., Improved lower bounds on the length of Davenport-Schinzel sequences, Combinatorica, 8 (1988) · Zbl 0672.05015
[20] Szemerédi, E., On a problem by Davenport and Schinzel, Acta Arith., 25, 213-224 (1974) · Zbl 0291.05003
[21] Wiernik, A.; Sharir, M., Planar realizations of nonlinear Davenport-Schinzel sequences by segments, Discrete Comput. Geom., 3, 15-47 (1988) · Zbl 0636.68043
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.