نظریه رمزی

برای نمونه

(r(x,۲)=x r(۱,x)=۱ ۱=r(x,1

r(۴٬۵) = ۲۵ r(۵٬۳) = ۱۴ r(۴٬۴) = ۱۸ r(۳٬۴) = ۹ r(۳٬۳) = ۶ عدد رمزی آخر در سال ۱۹۹۳ با استفاده از کامپیوتر بدست آمده.

این عددهای را برای اولین بار رمزی نام‌گذاری کرد و بعدها دانشمندان بزرگی چون گلیسون و گرینوودو اردوش بر روی آن‌ها وقضایای مربوطه کار کرده‌اند این عددهای فعلاً تجربی اند و جز در موارد خاص فرمولی برای آن‌ها نداریم. برای آشنایی بیشتر به قضیه زیر توجه کنید.

در این جا می‌خواهیم کران بالایی برای عددهای رمزی (r(k,l بیان کنیم: اگر k>۱ , l>۱ آنگاه:

 (r(k,l) <= r(k,l-۱) + r(k-1,l

برهان:

فرض کنید g گرافی با (r(k,l-۱) + r(k-1,l گره باشد. گره v را در نظر بگیرید صبق اصل لانه کبوتری v یا به (r(k-1,l گره وصل است ویا به (r(k,l-۱ گره وصل نیست.

در صورتی که حالت اول بر قرار شود در این تعداد گره یا l گره مستقل اند ویا ۱-k گره خوشه‌اند و از آنجا که همه این رئوس به v وصل اند k-۱ گره به همراه k , v گره خوشه را تشکیل می‌دهند حکم مسئله ثابت می‌شود.

و اگر حالت دوم بر قرار شود یا k گره خوشه پیدا می‌شود یا l-۱ گره مستقل و از آنجا که v به این رئوس وصا نیست l-۱ گره و l,v گره مستقل را تشکیل می‌دهد؛ و حکم ثابت می‌شود.

اگر q1,q2,... ,qn عددهای صحیح بزرگتر از ۲ باشند آنگاه عددی مانند (r(q1,q2,... ,qn وجود دارد به‌طوری‌که اگر p بزرگتر از (r(q1,q2,... ,qn باشد و یال‌های گراف را با n رنگ (رنگ‌های ۱ تا n) رنگ کنیم، به ازای حداقل یک رنگ مانند i زیر گراف کامل qi گرهی وجود دارد که یال‌هایش هم رنگ رنگ i ام است.

برای نمونه r(3,3,3) = ۱۷.

• استراتژی‌های حل مسئله/آرتور انگل/مترجمان آرش امینی… /نشر مبتکران/۱۳۸۲
• نظریه گراف و کاربردهای آن/باندی و مورتی/ترجمه دارا معظمی/ویرایش علی عمیدی/مرکز نشر دانشگاهی/۱۳۸۴ چاپ ۳
• ریاضیات انتخاب یا چگونه بدون شمارش بشماریم/ایوان نیون/مترجمان علی عمیدی و بتول جذبی/مرکز نشر پیش دانشگاهی/۱۳۸۶.