نظریه رمزی

قضیه رمزی(ramsey)

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

مثال

برای مثال

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

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

تاریخچه

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

قضیه کران بالا

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

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

برهان:

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

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

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

بیان مساله به صورت دیگر(حالت کلی)

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

برای مثال r(3,3,3) = 17.

منابع

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