عدد رمزی چند رنگی (رنگارنگ)

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

کلیدواژه ها:

قضیه رمزی ، عدد رمزی رنگارنگی ، اصل لانه کبوتری ، رنگ آمیزی گراف