قضیه رمزی
در علم ترکیبیات قضیهٔ رمزی بیان میکند که در رنگ آمیزی یالهای هر گراف کامل (گراف سادهای که در آن هر رأس به تمامی رئوس دیگر به وسیلهٔ یک یال متصل است) به اندازهٔ کافی بزرگی میتوان زیر گرافهای کامل تک رنگ یافت. در رنگ آمیزی با دو رنگ قضیهٔ رمزی بیان میکند که برای هر جفت از اعداد صحیح و مثبت
قضیهٔ رمزی یک دستآورد بنیادین در علم ترکیبیات است. F. P. Ramsey اولین نسخهٔ این دستآورد را به اثبات رساند. این مسئله قضیهٔ ترکیبیاتی را بنیان نهاد که امروزه آن را قضیهٔ رمزی مینامند. در این کاربرد سؤال این است که آیا زیرمجموعههای تک رنگی یافت میشوند که در این زیرمجموعهها تمام یالهای متصل به هم از یک رنگ باشند.
بسطی از این قضیه برای هر تعداد رنگ متناهی به جای دو رنگ به کار میرود. بهطور دقیق تر این قضیه بیان میکند که برای هر تعداد رنگ داده شدهٔ c وهر مجموعه از اعداد صحیح داده شدهٔ
مثال:R(۳٬۳)=۶
تصور کنید که یالهای یک گراف کامل با ۶ راس با دو رنگ آبی و قرمز رنگ آمیزی شده باشد. حال یک راس مثلاً راس v را انتخاب کنید. ۵ یال به v متصل هستند و از این رو بنابر اصل لانه کبوتری حداقل ۳ تا از آنها باید همرنگ باشند. بدون کاسته شدن از کلیت مسئله میتوان فرض کرد که حداقل ۳ یال که از راس v به راسهای r,s،t متصل اند آبی هستند (در غیر این صورت جای رنگهای قرمز و آبی عوض میشود) اگر هر یک از یالهای (r, s), (r, t), (s, t) نیز آبی باشد آن گاه ما یک مثلث از یالهای آبی داریم. در غیر این صورت یعنی اگر هیچیک از یالهای ذکر شده آبی نباشند هر سهٔ این یالها قرمز خواهند بود و ما یک مثلث به رنگ قرمز خواهیم داشت.
از آن جایی که این استدلال را برای هر رنگ آمیزی میتوان به کار برد، هر گراف کامل
یک اثبات جایگزین با استفاده از روش دوگونه شماری بدست میآید. این روش بدین صورت پیش میرود: تعداد سه تاییهای مرتب از راسهای x,y،z را که در آن یال (x,y) قرمز و (y,z) آبی هستند، بشمارید. اولاً هر راس داده شده در میان ۰×۵=۰ یا ۱×۴=۴ یا ۲ × ۳ = ۶ تا از سه تاییهای مرتب خواهد بود؛ بنابراین حداکثر ۶×۶=۳۶ تا از این سه تاییها وجود دارد. دوما برای هر مثلث (x,y،z) غیر تک رنگ دقیقاً ۲ تا از این سه تاییها وجود دارد؛ بنابراین حداکثر ۱۸ تا مثلث غیر تک رنگ وجود دارد؛ بنابراین حداقل ۲ تا از ۲۰ مثلث موجود در
برعکس، میتوان یک
اثبات قضیه
ابتدا قضیه را برای حالت رنگ آمیزی با دو رنگ با استفاده از استقرا روی r+s اثبات میکنیم. از روی تعریف واضح است که برای هر n ای R(n, ۱) = R(1, n) = ۱. این پایهٔ استقراست. ما اثبات خواهیم کرد که
ادعا:
حال با استفاده از اصل لانه کبوتری داریم:
پس ادعای ما درست است و ما اثبات را برای رنگ آمیزی با دو رنگ کامل کردیم. اکنون میخواهیم نتایج حالت کلی در رنگ آمیزی با c رنگ را به اثبات برسانیم. از استقرا استفاده میکنیم. ما نتایج مورد نظرمان را برای c=۱(بدیهی) و c=۲ (طبق مطالب گفته شده در بالا) داریم. حال c>۲ را در نظر میگیریم.
ادعا:
توجه کنید که عبارت سمت راست تنها دارای عدد رمزی برای c-۱ رنگ و ۲ رنگ است و از این رو طبق فرض استقرا عددی متناهی مانند t وجود دارد. پس اثبات ادعایمان برای اثبات قضیه کافی است.
اثبات ادعا
گرافی با t راس را در نظر بگیرید و یالهای آن را با c رنگ، رنگ آمیزی کنید. حال خود را به کور رنگی بزنید و وانمود کنید که رنگ c-1 و رنگ c رنگهای یکسانی هستند. پس در این وضعیت گراف با c-1 رنگ، رنگ آمیزی شدهاست. بنابر فرض استقرا این گراف شامل
اعداد رمزی
اعداد
در حال حاضر حتی مقدار دقیق
" بیگانگانی (نیروهای خارجی) را تصور کنید که بسیار نیرومندتر از ما بر روی زمین هستند و از ما خواستهاند که مقدار
مقدار
r,s | ۱ | ۲ | ۳ | ۴ | ۵ | ۶ | ۷ | ۸ | ۹ | ۱۰ |
---|---|---|---|---|---|---|---|---|---|---|
۱ | ۱ | ۱ | ۱ | ۱ | ۱ | ۱ | ۱ | ۱ | ۱ | ۱ |
۲ | ۱ | ۲ | ۳ | ۴ | ۵ | ۶ | ۷ | ۸ | ۹ | ۱۰ |
۳ | ۱ | ۳ | ۶ | ۹ | ۱۴ | ۱۸ | ۲۳ | ۲۸ | ۳۶ | ۴۰–۴۲ |
۴ | ۱ | ۴ | ۹ | ۱۸ | ۲۵ | ۳۶–۴۱ | ۴۹–۶۱ | ۵۸–۸۴ | ۷۳–۱۱۵ | ۹۲–۱۴۹ |
۵ | ۱ | ۵ | ۱۴ | ۲۵ | ۴۳–۴۸ | ۵۸–۸۷ | ۸۰–۱۴۳ | ۱۰۱–۲۱۶ | ۱۲۶–۳۱۶ | ۱۴۴–۴۴۲ |
۶ | ۱ | ۶ | ۱۸ | ۳۶–۴۱ | ۵۸–۸۷ | ۱۰۲–۱۶۵ | ۱۱۳–۲۹۸ | ۱۳۲–۴۹۵ | ۱۶۹–۷۸۰ | ۱۷۹–۱۱۷۱ |
۷ | ۱ | ۷ | ۲۳ | ۴۹–۶۱ | ۸۰–۱۴۳ | ۱۱۳–۲۹۸ | ۲۰۵–۵۴۰ | ۲۱۷–۱۰۳۱ | ۲۴۱–۱۷۱۳ | ۲۸۹–۲۸۲۶ |
۸ | ۱ | ۸ | ۲۸ | ۵۸–۸۴ | ۱۰۱–۲۱۶ | ۱۳۲–۴۹۵ | ۲۱۷–۱۰۳۱ | ۲۸۲–۱۸۷۰ | ۳۱۷–۳۵۸۳ | ۶۰۹۰–۳۳۱ |
۹ | ۱ | ۹ | ۳۶ | ۷۳–۱۱۵ | ۱۲۶–۳۱۶ | ۱۶۹–۷۸۰ | ۲۴۱–۱۷۱۳ | ۳۱۷–۳۵۸۳ | ۵۶۵–۶۵۸۸ | ۵۸۱–۱۲۶۷۷ |
۱۰ | ۱ | ۱۰ | ۴۰–۴۲ | ۹۲–۱۴۹ | ۱۴۴–۴۴۲ | ۱۷۹–۱۱۷۱ | ۲۸۹–۲۸۲۶ | ۶۰۹۰–۳۳۱ | ۵۸۱–۱۲۶۷۷ | ۷۹۸–۲۳۵۵۶ |
در جدول یک تقارن ناچیز در میان قطر نیز وجود دارد.
جدول فوق از جدول بزرگتری که توسط Stanisław Radziszowski تألیف شده، اقتباس شدهاست.
در سال ۲۰۱۲ قضیه
یک مثال از چندین رنگ: R(3,3،3) = ۱۷
یک عدد رمزی رنگارنگ یک عدد رمزی است که در آن برای رنگ آمیزی از ۳ رنگ یا بیشتر استفاده میشود. فقط یک عدد رمزی رنگارنگ وجود دارد که مقدار دقیق آن شناخته شدهاست و آن R(3,3،3) = ۱۷ است.
برای اثبات این مسئله، یالی از یک گراف کامل را در نظر بگیرید که با ۳ رنگ قرمز، سبز و زرد رنگ آمیزی شدهاست. حال میخواهیم ببینیم این گراف باید حداقل چند راس داشته باشد که شرایط قضیهٔ رمزی برایش بر قرار باشند. پس معادلاً میتوانیم ببینیم حداکثر تعداد رئوس باید چند باشد که شرایط قضیهٔ رمزی بر قرار نشود. پس فرض کنید که یال مورد نظر هیچ مثلث هم رنگی را تشکیل نمیدهد. یک راس دلخواه v را انتخاب کنید. مجموعهٔ رئوسی که یک یال سبز به v دادهاند را در نظر بگیرید. این مجموعه همسایگی سبز راس v نامیده میشود. همسایگی سبز v نمیتواند شامل هیچ یال سبزی باشد، زیرا در غیر این صورت مثلث سبزی وجود خواهد داشت که متشکل از دو نقطهٔ انتهایی آن یال سبز و راس v خواهد بود. پس یالهای رنگ آمیزی شده در همسایگی سبز v تنها با دو رنگ قرمز و زرد رنگ آمیزی شدهاند. از آن جایی که R(3,3) = 6است همسایگی سبز v میتواند حداکثر شامل ۵ راس باشد. بهطور مشابه همسایگیهای قرمز و زرد v نیز هر کدام حداکثر میتوانند ۵ راس داشته باشند. از آن جایی که هر راس به جز خود v در یکی از همسایگیهای سبز، قرمز یا زرد v قرار گرفته، گراف کامل حداکثر میتواند ۱ + ۵ + ۵ + ۵ = ۱۶ راس داشته باشد. در نتیجه داریم: R(3,3،3) ≤ 17
برای این که ببینیم R(3,3،3) ≥ 17کافی است یالهای یک گراف کامل با ۱۶ راس را با سه رنگ متفاوت رنگ آمیزی کنیم و در عین حال از ایجاد مثلثهای تک رنگ بپرهیزیم. به این نتیجه خواهیم رسید که دقیقاً دو روش برای رنگ آمیزی K16 با این شرایط وجود دارد که آنها را رنگ آمیزی تابیده (معوج) و ناتابیده مینامیم. هر دو روش رنگ آمیزی در شکل سمت چپ در بالا نشان داده شدهاست. شکل بالایی رنگ آمیزی ناتابیده و شکل پایینی رنگ آمیزی تابیده را نشان میدهد. بدین ترتیب، مشخص میشود که گراف K16 را میتوان طوری با ۳ رنگ رنگ آمیزی کرد که هیچ k3 تک رنگی ایجاد نشود.
پس R(3,3،3)=17.
اگر شما هر رنگی از رنگهای تابیده یا ناتابیدهٔ گراف
دقیقاً دو روش برای رنگ آمیزی یالهای گراف
علاوه بر این دقیقاً ۱۱۵ یال برای رنگ آمیزی
پیوند به بیرون
منابع
ویکیپدیای انگلیسی
- http://en.wikipedia.org/wiki/Ramsey_number
- F. P. Ramsey: "On a problem of formal logic", Proc. London Math. Soc. series 2, vol. 30 (1930), pp. 264–286
- رونالد گراهام، B. Rothschild, J.H. Spencer, Ramsey Theory, John Wiley and Sons, NY (1990).
- G. Exoo, "A Lower Bound for R(5,5)", J. Graph Theory, 13 (1989), 97-98.
- ↑ B. McKay, گرافهای رمزی