. متن داده‌شده را خلاصه کن

متن: تصور کنید که یال‌های یک گراف کامل با ۶ راس با دو رنگ آبی و قرمز رنگ‌آمیزی شده باشد. حال یک راس مثلا راس v را انتخاب کنید. ۵ یال به v متصل هستند و از این رو بنابر اصل لانه کبوتری حداقل ۳ تا از آن‌ها باید همرنگ باشند. بدون کاسته شدن از کلیت مسئله می‌توان فرض کرد که حداقل ۳ یال که از راس v به راس‌های r,s، t متصل اند آبی هستند (در غیر این صورت جای رنگ‌های قرمز و آبی عوض می‌شود) اگر هر یک از یال‌های (r, s) , (r, t) , (s, t) نیز آبی باشد آن گاه ما یک مثلث از یال‌های آبی داریم. در غیر این صورت یعنی اگر هیچ‌یک از یال‌های ذکر شده آبی نباشند هر سه این یال‌ها قرمز خواهند بود و ما یک مثلث به رنگ قرمز خواهیم داشت. از آن جایی که این استدلال را برای هر رنگ‌آمیزی می‌توان به کار برد، هر گراف کامل شامل یک تک رنگ است و از این رو r (۳ ٬ ۳) ≤ ۶. نسخه عمومی این قضیه، قضیه آشنایان وغریبه‌ها نامیده می‌شود. یک اثبات جایگزین با استفاده از روش دوگونه شماری بدست می‌آید. این روش بدین صورت پیش می‌رود: تعداد سه تایی‌های مرتب از راس‌های x,y، z را که در آن یال (x,y) قرمز و (y,z) آبی هستند، بشمارید. اولا هر راس داده‌شده در میان ۰ × ۵ = ۰ یا ۱ × ۴ = ۴ یا ۲ × ۳ = ۶ تا از سه تایی‌های مرتب خواهد بود؛ بنابراین حداکثر ۶ × ۶ = ۳۶ تا از این سه تایی‌ها وجود دارد. دوما برای هر مثلث (x,y، z) غیر تک رنگ دقیقا ۲ تا از این سه تایی‌ها وجود دارد؛ بنابراین حداکثر ۱۸ تا مثلث غیر تک رنگ وجود دارد؛ بنابراین حداقل ۲ تا از ۲۰ مثلث موجود در تک رنگند. برعکس، می‌توان یک را با دو رنگ، رنگ‌آمیزی کرد بدون این‌که هیچ تک رنگی ایجاد شود که نشان می‌دهد r (۳ ٬ ۳) > ۵. ابتدا قضیه را برای حالت رنگ‌آمیزی با دو رنگ با استفاده از استقرا روی r+s اثبات می‌کنیم. از روی تعریف واضح است که برای هر n ای r (n, ۱) = r (۱ , n) = ۱. این پایه استقراست. ما اثبات خواهیم کرد که وجود دارد و این کار را با یافتن یک محدوده صریح برای آن انجام خواهیم داد. فرض استقرای ما این است که، وجود دارد. ادعا:. یک گراف کامل با راس را در نظر بگیرید. راس v از گراف داده‌شده را انتخاب کنید و راس‌های باقی‌مانده را به دو مجموعه m و n تفکیک کنید به گونه‌ای که هر راسی همانند w در مجموعه m باشد اگر یال (v, w) آبی باشد و w در n باشد اگر که یال (v, w) قرمز باشد. برای حالت دیگر نیز استدلال مشابه‌است. از …
خلاصه:
در علم ترکیبیات قضیهٔ رمزی بیان می‌کند که در رنگ آمیزی یال‌های هر گراف کامل (گراف ساده‌ای که در آن هر رأس به تمامی رئوس دیگر به وسیلهٔ یک یال متصل است) به اندازهٔ کافی بزرگی می‌توان زیر گراف‌های کامل تک رنگ یافت . در رنگ آمیزی با دو رنگ قضیهٔ رمزی بیان می‌کند که برای هر جفت از اعداد صحیح و مثبت کوچکترین عدد مثبت وجود دارد به گونه‌ای که برای هر گراف کامل با راس که یال‌های آن با دو رنگ قرمز و آبی رنگ آمیزی شده باشند ، زیرگراف کاملی با راس وجود دارد که کاملا آبی شده باشد یا زیر گراف کاملی با راس وجود دارد که کاملا قرمز شده باشد . در این جا به عدد صحیحی دلالت می‌کند که به و وابسته‌است .