نظریه رمزی

قضیه رمزی (ramsey) دربارهٔ رنگ‌آمیزی گراف هاست که در اینجا به حالت خاصی از آن اشاره می‌کنیم.

برای عددهای صحیح و دلخواه k و l کوچک‌ترین عدد صحیح (r(k,l وجود دارد به‌طوری‌که هر گراف با این تعداد گره دارای خوشه‌ای k گرهی یا شامل مجموعه مستقل l گرهی است.

 نمونه 
برای نمونه
(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) = ۱۷.

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

رده:نظریه رمزی
رده:نظریه گراف