کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4656740 1632978 2015 32 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the number of monotone sequences
ترجمه فارسی عنوان
در تعداد توالی های یکنواخت ؟؟
کلمات کلیدی
فوق، پسوند مونوتونی، زیکرس-پوشیده شده از درخت. پوشیده شده از درخت رادماکر
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

One of the most classical results in Ramsey theory is the theorem of Erdős and Szekeres from 1935, which says that every sequence of more than k2k2 numbers contains a monotone subsequence of length k+1k+1. We address the following natural question motivated by this result: Given integers k and n   with n⩾k2+1n⩾k2+1, how many monotone subsequences of length k+1k+1 must every sequence of n numbers contain? We answer this question precisely for all sufficiently large k   and n⩽k2+ck3/2/log⁡kn⩽k2+ck3/2/log⁡k, where c is some absolute positive constant.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 115, November 2015, Pages 132–163
نویسندگان
, ,