ملخص: We present several new results regarding ?s (n), the maximum length of a Davenport-Schinzel sequence of order s on n distinct symbols. First, we prove that ?s (n) = n · 2(1/t!)a(n)t+O(a(n)t-1) for s = 4 even, and ?s (n) = n · 2(1/t!)a(n)t log2 a(n)+O(a(n)t ) for s = 3 odd, where t = (s - 2)/2, and a(n) denotes the inverse Ackermann function. The previous upper bounds, by Agarwal et al. [1989], had a leading coefficient of 1 instead of 1/t! in the exponent. The bounds for even s are now tight up to lower-order terms in the exponent. These new bounds result from a small improvement on the technique of Agarwal et al. More importantly, we also present a new technique for deriving upper bounds for ?s (n). This new technique is very similar to the one we applied to the problem of stabbing interval chains [Alon et al. 2008]. With this new technique we: (1) re-derive the upper bound of ?3(n) = 2na(n) + O(nva(n)) (first shown by Klazar [1999]); (2) re-derive our own new upper bounds for general s; and (3) obtain improved upper bounds for the generalized Davenport-Schinzel sequences considered by Adamec et al. [1992].Regarding lower bounds, we show that ?3(n) = 2na(n)- O(n) (the previous lower bound (Sharir and Agarwal, 1995) had a coefficient of 12 ), so the coefficient 2 is tight. We also present a simpler variant of the construction of Agarwal et al. [1989] that achieves the known lower bounds of ?s (n) = n · 2(1/t!)a(n)t-O(a(n)t-1) for s = 4 even. Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems-Geometrical problems and computations; G.2.1 [Discrete Mathematics]: Combinatorics

لغة: إنجليزية