کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10118856 | 1633558 | 2005 | 16 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Upper and lower Ramsey bounds in bounded arithmetic
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
منطق ریاضی
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Pudlák shows that bounded arithmetic (Buss' S2) proves an upper bound on the Ramsey number Rr(k) (the r refers to the number of colors, assigned to edges; the k refers to the size of the monochromatic set). We will strengthen this result by improving the bound. We also investigate lower bounds, obtaining a non-constructive lower bound for the special case of 2 colors (i.e. r=2), by formalizing a use of the probabilistic method. A constructive lower bound is worked out for the case when the monochromatic set size is fixed to 3 (i.e. k=3). The constructive lower bound is used to prove two “reversals”. To explain this idea we note that the Ramsey upper bound proof for k=3 (when the upper bound is explicitly mentioned) uses the weak pigeonhole principle (WPHP) in a significant way. The Ramsey upper bound proof for the case in which the upper bound is not explicitly mentioned, uses the totality of the exponentiation function (Exp) in a significant way. It turns out that the Ramsey upper bounds actually imply the respective principles (WPHP and Exp) used to prove them, indicating that these principles were in some sense necessary.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Annals of Pure and Applied Logic - Volume 135, Issues 1â3, September 2005, Pages 135-150
Journal: Annals of Pure and Applied Logic - Volume 135, Issues 1â3, September 2005, Pages 135-150
نویسندگان
Kerry Ojakian,