اعداد رمزی¶

آشنایی¶

کران ها¶

به دست آوردن مقدار دقیق \(R(a,b)\) ممکن نیست اما می توان کران هایی برای آن ارائه داد.

در وهله اول باید ثابت کنیم \(R(a, b)\) وجود دارد.(ممکن است به ازای هیچ \(n\) ای ویژگی مطلوب برای \(K_n\) برقرار نباشد)

ایده حل این است که یک راس پیدا کنیم که به اندازه کافی مجاور آبی یا قرمز داشته باشد و سپس تنها مجاور های آن راس را در نظر بگیریم و در آنجا یک خوشه آبی یا قرمز با اندازه کوچکتر پیدا کنیم.

به صورت دقیق فرض کنید راسی مثل \(u\) وجود داشته باشد که حداقل \(R(a-1,b)\) مجاور آبی داشته باشد در اینصورت اگر مجاور های این راس را در نظر بگیرید دو حالت زیر پیش می آید‌ :

• در آن یک \(K_{a-1}\) آبی وجود دارد که در اینصورت می توانیم با اضافه کردن راس \(u\) به آن یک \(K_a\) آبی به دست بیاوریم.
• در آن یک \(K_b\) قرمز وجود دارد.

پس اگر راسی باشد که حداقل \(R(a-1,b)\) مجاور آبی وجود داشته باشد مسئله حل می شود. مشابها اگر راسی باشد که حداقل \(R(a, b-1)\) مجاور قرمز داشته باشد هم مسئله حل می شود.

پس نتیجه می گیریم که \(R(a,b) \leq R(a-1,b) + R(a,b-1)\) زیرا اگر گراف ما حداقل \(R(a-1,b) + R(a,b-1)\) راس داشته باشد هر راس دلخواهی را که در نظر بگیرید یا به اندازه کافی مجاور آبی خواهد داشت یا به اندازه کافی مجاور قرمز خواهد داشت.

نامساوی بالا ما را به یاد اتحاد پاسکال می اندازد. ( \(\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}\) )

همچنین می توان با استقرا ثابت کرد که \(R(a, b) \leq \binom{a+b}{a}\)

تعمیم به k بعد¶

تصور کنید که مجموعه ای \(n\) عضوی داریم و هر زیرمجموعه \(k\) تایی آن را با یکی از رنگ های آبی یا قرمز رنگ کرده ایم. حالا به یک زیرمجموعه مثل \(A\) خوشه \(k\) بعدی می گوییم اگر تمام زیر مجموعه های \(k\) تایی \(A\) همرنگ باشند. (اگر این رنگ آبی باشد خوشه آبی می گوییم و اگر این رنگ قرمز باشد خوشه قرمز می گوییم).

حالا \(R_k(a,b)\) را تعریف می کنیم مینیمم \(n\) که هر طور زیرمجموعه های \(k\) تایی آن را با آبی و قرمز رنگ کنیم یا یک خوشه آبی \(a\) تایی داشته باشیم یا یک خوشه قرمز \(b\) تایی.

ایده اثبات مشابه بالا است. فرض کنید \(n = R_k(a,b)\) یک عضو خاص مثل \(u\) از مجموعه \(n\) تایی \(A\) را در نظر بگیرید. فرض کنید \(B = A - \{u\}\). هر زیر مجموعه \(k-1\) تایی از \(B\) مثل \(S\) را به رنگی در می آوریم که زیرمجموعه \(k\) تایی \(S \cup \{u\}\) دارد. اگر تعداد اعضای \(B\) حداقل \(R_{k-1}( R_k(a-1,b), R_k(a,b-1) )\) باشد در اینصورت یکی از دو اتفاق زیر می افتد :

• در \(B\) یک خوشه \(k-1\) بعدی آبی مثل \(S\) به اندازه حداقل \(R_k(a-1,b)\) دارد. در اینصورت یا \(S\) یک خوشه \(k\) بعدی قرمز به اندازه \(b\) دارد (که مسئله حل است). یا \(S\) یک خوشه \(k\) بعدی آبی به اندازه \(a-1\) دارد. در اینصورت می توانیم \(u\) را به این مجموعه اضافه کنیم و یک خوشه \(k\) بعدی به اندازه \(a\) داریم.
• در \(B\) یک خوشه \(k-1\) بعدی قرمز مثل \(S\) به اندازه حداقل \(R_k(a,b-1)\) دارد. در اینصورت یا \(S\) یک خوشه \(k\) بعدی آبی به اندازه \(a\) دارد (که مسئله حل است). یا \(S\) یک خوشه \(k\) بعدی قرمز به اندازه \(b-1\) دارد. در اینصورت می توانیم \(u\) را به این مجموعه اضافه کنیم و یک خوشه \(k\) بعدی قرمز به اندازه \(b\) داریم.

طبق مطالب گفته شده می توان ثابت کرد که \(R_k(a,b) \leq R_{k-1}(R_k(a-1,b),R_k(a,b-1))\)

تعمیم به k بعد و c رنگ¶

به صورت مشابه می توانیم برای بیش از دو رنگ نیز مسئله را بیان و اثبات کنیم. پیدا کردن کران روی \(R_k(a_1,a_2,...,a_c)\) را به خواننده واگذار می کنیم.