Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء

6 اقتباسات (Scopus)

ملخص

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 (Equation Presented) where t = [(s - 2)/2], and α(n) denotes the inverse Ackermann function. The previous upper bounds, by Agarwal, Sharir, and Shor (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 based on some recurrences very similar to those used by the author, together with Alon, Kaplan, Sharir, and Smorodinsky (SODA 2008), for the problem of stabbing interval chains with j-tuples. With this new technique we: (1) re-derive the upper bound of λ3(n) ≤ 2nα(n) + O(η√α(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, Klazar, and Valtr (1992). Regarding lower bounds, we show that λ3(n) ≥ 2nα(n) - O(n) (the previous lower bound (Sharir and Agarwal, 1995) had a coefficient of 1/2), so the coefficient 2 is tight. We also present a simpler variant of the construction of Agarwal, Sharir, and Shor that achieves the known lower bounds of λs(n) ≥ n·2 (1/t!)α(n)t-O(α(n)t-1) for s ≥ 4 even.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفProceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms
ناشرAssociation for Computing Machinery (ACM)
الصفحات1-10
عدد الصفحات10
رقم المعيار الدولي للكتب (المطبوع)9780898716801
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2009
منشور خارجيًانعم
الحدث20th Annual ACM-SIAM Symposium on Discrete Algorithms - New York, NY, الولايات المتّحدة
المدة: ٤ يناير ٢٠٠٩٦ يناير ٢٠٠٩

سلسلة المنشورات

الاسمProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

!!Conference

!!Conference20th Annual ACM-SIAM Symposium on Discrete Algorithms
الدولة/الإقليمالولايات المتّحدة
المدينةNew York, NY
المدة٤/٠١/٠٩٦/٠١/٠٩

بصمة

أدرس بدقة موضوعات البحث “Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا