در علم ترکیبیات قضیهٔ رمزی بیان می کند که در رنگ آمیزی یال های هر گراف کامل ( گراف ساده ای که در آن هر رأس به تمامی رئوس دیگر به وسیلهٔ یک یال متصل است ) به اندازهٔ کافی بزرگی می توان زیر گراف های کامل تک رنگ یافت. در رنگ آمیزی با دو رنگ قضیهٔ رمزی بیان می کند که برای هر جفت از اعداد صحیح و مثبت ( r , s ) کوچکترین عدد مثبت R ( r , s ) وجود دارد به گونه ای که برای هر گراف کامل با R ( r , s ) راس که یال های آن با دو رنگ قرمز و آبی رنگ آمیزی شده باشند، زیرگراف کاملی با r راس وجود دارد که کاملاً آبی شده باشد یا زیر گراف کاملی با s راس وجود دارد که کاملاً قرمز شده باشد. در این جا R ( r , s ) به عدد صحیحی دلالت می کند که به r و s وابسته است.
قضیهٔ رمزی یک دست آورد بنیادین در علم ترکیبیات است. F. P. Ramsey اولین نسخهٔ این دست آورد را به اثبات رساند. این مسئله قضیهٔ ترکیبیاتی را بنیان نهاد که امروزه آن را قضیهٔ رمزی می نامند. در این کاربرد سؤال این است که آیا زیرمجموعه های تک رنگی یافت می شوند که در این زیرمجموعه ها تمام یال های متصل به هم از یک رنگ باشند.
بسطی از این قضیه برای هر تعداد رنگ متناهی به جای دو رنگ به کار می رود. به طور دقیق تر این قضیه بیان می کند که برای هر تعداد رنگ داده شدهٔ c وهر مجموعه از اعداد صحیح داده شدهٔ n 1 , n 2 , . . . , n c عدد R ( n 1 , n 2 , . . . , n c ) به گونه ای وجود دارد که اگر یال های گراف کاملی از مرتبه R ( n 1 , n 2 , . . . , n c ) با c رنگ متفاوت، رنگ آمیزی شود آن گاه برای مقادیری از i بین ۱ تا c گراف مورد نظر باید شامل زیرگراف کاملی از مرتبه n i باشد که تمام یال های آن به رنگ i هستند. مورد خاصی که در بالا به آن اشاره شد برای c=۲ اتفاق می افتد. ( n 2 = s ، n 1 = r )
تصور کنید که یال های یک گراف کامل با ۶ راس با دو رنگ آبی و قرمز رنگ آمیزی شده باشد. حال یک راس مثلاً راس v را انتخاب کنید. ۵ یال به v متصل هستند و از این رو بنابر اصل لانه کبوتری حداقل ۳ تا از آن ها باید همرنگ باشند. بدون کاسته شدن از کلیت مسئله می توان فرض کرد که حداقل ۳ یال که از راس v به راس های r, s، t متصل اند آبی هستند ( در غیر این صورت جای رنگ های قرمز و آبی عوض می شود ) اگر هر یک از یال های ( r, s ) , ( r, t ) , ( s, t ) نیز آبی باشد آن گاه ما یک مثلث از یال های آبی داریم. در غیر این صورت یعنی اگر هیچ یک از یال های ذکر شده آبی نباشند هر سهٔ این یال ها قرمز خواهند بود و ما یک مثلث به رنگ قرمز خواهیم داشت.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفقضیهٔ رمزی یک دست آورد بنیادین در علم ترکیبیات است. F. P. Ramsey اولین نسخهٔ این دست آورد را به اثبات رساند. این مسئله قضیهٔ ترکیبیاتی را بنیان نهاد که امروزه آن را قضیهٔ رمزی می نامند. در این کاربرد سؤال این است که آیا زیرمجموعه های تک رنگی یافت می شوند که در این زیرمجموعه ها تمام یال های متصل به هم از یک رنگ باشند.
بسطی از این قضیه برای هر تعداد رنگ متناهی به جای دو رنگ به کار می رود. به طور دقیق تر این قضیه بیان می کند که برای هر تعداد رنگ داده شدهٔ c وهر مجموعه از اعداد صحیح داده شدهٔ n 1 , n 2 , . . . , n c عدد R ( n 1 , n 2 , . . . , n c ) به گونه ای وجود دارد که اگر یال های گراف کاملی از مرتبه R ( n 1 , n 2 , . . . , n c ) با c رنگ متفاوت، رنگ آمیزی شود آن گاه برای مقادیری از i بین ۱ تا c گراف مورد نظر باید شامل زیرگراف کاملی از مرتبه n i باشد که تمام یال های آن به رنگ i هستند. مورد خاصی که در بالا به آن اشاره شد برای c=۲ اتفاق می افتد. ( n 2 = s ، n 1 = r )
تصور کنید که یال های یک گراف کامل با ۶ راس با دو رنگ آبی و قرمز رنگ آمیزی شده باشد. حال یک راس مثلاً راس v را انتخاب کنید. ۵ یال به v متصل هستند و از این رو بنابر اصل لانه کبوتری حداقل ۳ تا از آن ها باید همرنگ باشند. بدون کاسته شدن از کلیت مسئله می توان فرض کرد که حداقل ۳ یال که از راس v به راس های r, s، t متصل اند آبی هستند ( در غیر این صورت جای رنگ های قرمز و آبی عوض می شود ) اگر هر یک از یال های ( r, s ) , ( r, t ) , ( s, t ) نیز آبی باشد آن گاه ما یک مثلث از یال های آبی داریم. در غیر این صورت یعنی اگر هیچ یک از یال های ذکر شده آبی نباشند هر سهٔ این یال ها قرمز خواهند بود و ما یک مثلث به رنگ قرمز خواهیم داشت.
wiki: قضیه رمزی