نظریه رمزی
قضیه رمزی (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) = ۱۷.
منابع
- استراتژی‌های حل مسئله/آرتور انگل/مترجمان آرش امینی… /نشر مبتکران/۱۳۸۲
- نظریه گراف و کاربردهای آن/باندی و مورتی/ترجمه دارا معظمی/ویرایش علی عمیدی/مرکز نشر دانشگاهی/۱۳۸۴ چاپ ۳
- ریاضیات انتخاب یا چگونه بدون شمارش بشماریم/ایوان نیون/مترجمان علی عمیدی و بتول جذبی/مرکز نشر پیش دانشگاهی/۱۳۸۶.