قضیه رمزی

با نظریه رمزی اشتباه نشود.

در علم ترکیبیات قضیهٔ رمزی بیان می‌کند که در رنگ آمیزی یال‌های هر گراف کامل (گراف ساده‌ای که در آن هر رأس به تمامی رئوس دیگر به وسیلهٔ یک یال متصل است) به اندازهٔ کافی بزرگی می‌توان زیر گراف‌های کامل تک رنگ یافت. در رنگ آمیزی با دو رنگ قضیهٔ رمزی بیان می‌کند که برای هر جفت از اعداد صحیح و مثبت ${\displaystyle (r,s)}$ کوچکترین عدد مثبت ${\displaystyle R(r,s)}$ وجود دارد به گونه‌ای که برای هر گراف کامل با ${\displaystyle R(r,s)}$ راس که یال‌های آن با دو رنگ قرمز و آبی رنگ آمیزی شده باشند، زیرگراف کاملی با ${\displaystyle r}$ راس وجود دارد که کاملاً آبی شده باشد یا زیر گراف کاملی با ${\displaystyle s}$ راس وجود دارد که کاملاً قرمز شده باشد. در این جا ${\displaystyle R(r,s)}$ به عدد صحیحی دلالت می‌کند که به ${\displaystyle r}$ و ${\displaystyle s}$ وابسته‌است.

قضیهٔ رمزی یک دست‌آورد بنیادین در علم ترکیبیات است. F. P. Ramsey اولین نسخهٔ این دست‌آورد را به اثبات رساند. این مسئله قضیهٔ ترکیبیاتی را بنیان نهاد که امروزه آن را قضیهٔ رمزی می‌نامند. در این کاربرد سؤال این است که آیا زیرمجموعه‌های تک رنگی یافت می‌شوند که در این زیرمجموعه‌ها تمام یال‌های متصل به هم از یک رنگ باشند.

بسطی از این قضیه برای هر تعداد رنگ متناهی به جای دو رنگ به کار می‌رود. به‌طور دقیق تر این قضیه بیان می‌کند که برای هر تعداد رنگ داده شدهٔ c وهر مجموعه از اعداد صحیح داده شدهٔ ${\displaystyle n_{1},n_{2},...,n_{c}}$ عدد ${\displaystyle R\left(n_{1},n_{2},...,n_{c}\right)}$ به گونه‌ای وجود دارد که اگر یال‌های گراف کاملی از مرتبه ${\displaystyle R\left(n_{1},n_{2},...,n_{c}\right)}$ با c رنگ متفاوت، رنگ آمیزی شود آن گاه برای مقادیری از i بین ۱ تا c گراف مورد نظر باید شامل زیرگراف کاملی از مرتبه${\displaystyle n_{i}}$باشد که تمام یال‌های آن به رنگ i هستند. مورد خاصی که در بالا به آن اشاره شد برای c=۲ اتفاق می‌افتد. (${\displaystyle n_{2}=s}$، ${\displaystyle n_{1}=r}$)

مثال:R(۳٬۳)=۶

تصور کنید که یال‌های یک گراف کامل با ۶ راس با دو رنگ آبی و قرمز رنگ آمیزی شده باشد. حال یک راس مثلاً راس v را انتخاب کنید. ۵ یال به v متصل هستند و از این رو بنابر اصل لانه کبوتری حداقل ۳ تا از آن‌ها باید همرنگ باشند. بدون کاسته شدن از کلیت مسئله می‌توان فرض کرد که حداقل ۳ یال که از راس v به راس‌های r,s،t متصل اند آبی هستند (در غیر این صورت جای رنگ‌های قرمز و آبی عوض می‌شود) اگر هر یک از یال‌های (r, s), (r, t), (s, t) نیز آبی باشد آن گاه ما یک مثلث از یال‌های آبی داریم. در غیر این صورت یعنی اگر هیچ‌یک از یال‌های ذکر شده آبی نباشند هر سهٔ این یال‌ها قرمز خواهند بود و ما یک مثلث به رنگ قرمز خواهیم داشت.

از آن جایی که این استدلال را برای هر رنگ آمیزی می‌توان به کار برد، هر گراف کامل ${\displaystyle K_{6}}$ شامل یک ${\displaystyle K_{3}}$ تک رنگ است و از این رو R(۳٬۳) ≤ ۶. نسخهٔ عمومی این قضیه، قضیهٔ آشنایان وغریبه‌ها نامیده می‌شود.

یک اثبات جایگزین با استفاده از روش دوگونه شماری بدست می‌آید. این روش بدین صورت پیش می‌رود: تعداد سه تایی‌های مرتب از راس‌های x,y،z را که در آن یال (x,y) قرمز و (y,z) آبی هستند، بشمارید. اولاً هر راس داده شده در میان ۰×۵=۰ یا ۱×۴=۴ یا ۲ × ۳ = ۶ تا از سه تایی‌های مرتب خواهد بود؛ بنابراین حداکثر ۶×۶=۳۶ تا از این سه تایی‌ها وجود دارد. دوما برای هر مثلث (x,y،z) غیر تک رنگ دقیقاً ۲ تا از این سه تایی‌ها وجود دارد؛ بنابراین حداکثر ۱۸ تا مثلث غیر تک رنگ وجود دارد؛ بنابراین حداقل ۲ تا از ۲۰ مثلث موجود در ${\displaystyle K_{6}}$ تک رنگند.

برعکس، می‌توان یک ${\displaystyle K_{5}}$ را با دو رنگ، رنگ آمیزی کرد بدون این که هیچ ${\displaystyle K_{3}}$ تک رنگی ایجاد شود که نشان می‌دهد R(۳٬۳)> ۵.

اثبات قضیه

ابتدا قضیه را برای حالت رنگ آمیزی با دو رنگ با استفاده از استقرا روی r+s اثبات می‌کنیم. از روی تعریف واضح است که برای هر n ای R(n, ۱) = R(1, n) = ۱. این پایهٔ استقراست. ما اثبات خواهیم کرد که ${\displaystyle R\left(r,s\right)}$ وجود دارد و این کار را با یافتن یک محدودهٔ صریح برای آن انجام خواهیم داد. فرض استقرای ما این است که ${\displaystyle R\left(r-1,s\right)}$،${\displaystyle R\left(r,s-1\right)}$ وجود دارد.

ادعا: ${\displaystyle R(r,s)\leq R(r-1,s)+R(r,s-1)}$. یک گراف کامل با ${\displaystyle R\left(r-1,s\right)+R\left(r,s-1\right)}$ راس را در نظر بگیرید. راس v از گراف داده شده را انتخاب کنید و راس‌های باقی‌مانده را به دو مجموعهٔ M و N تفکیک کنید به گونه‌ای که هر راسی همانند w در مجموعهٔ M باشد اگر یال (v, w) آبی باشد و w در N باشد اگر که یال (v, w) قرمز باشد.

حال با استفاده از اصل لانه کبوتری داریم: ${\displaystyle \left|N\right|\geq R(r,s-1)}$ یا ${\displaystyle \left|M\right|\geq R(r-1,s)}$اگر M دارای زیرگراف کامل ${\displaystyle K_{s}}$ به رنگ قرمز باشد آن گاه گراف اولیه نیز شامل این بخش می‌شود و مسئله حل شده‌است. در غیر این صورت M دارای زیرگراف کامل ${\displaystyle K_{r-1}}$ است و بنابراین بنا بر تعریف M, M اجتماع {v} دارای زیرگراف کامل ${\displaystyle K_{r}}$ به رنگ آبی است. برای حالت دیگر نیز استدلال مشابه‌است.

پس ادعای ما درست است و ما اثبات را برای رنگ آمیزی با دو رنگ کامل کردیم. اکنون می‌خواهیم نتایج حالت کلی در رنگ آمیزی با c رنگ را به اثبات برسانیم. از استقرا استفاده می‌کنیم. ما نتایج مورد نظرمان را برای c=۱(بدیهی) و c=۲ (طبق مطالب گفته شده در بالا) داریم. حال c>۲ را در نظر می‌گیریم.

ادعا:${\displaystyle R(n_{1},...,n_{c})\leq R(n_{1},...,n_{c-2},R(n_{c-1},n_{c}))}$

توجه کنید که عبارت سمت راست تنها دارای عدد رمزی برای c-۱ رنگ و ۲ رنگ است و از این رو طبق فرض استقرا عددی متناهی مانند t وجود دارد. پس اثبات ادعایمان برای اثبات قضیه کافی است.

اثبات ادعا

گرافی با t راس را در نظر بگیرید و یال‌های آن را با c رنگ، رنگ آمیزی کنید. حال خود را به کور رنگی بزنید و وانمود کنید که رنگ c-1 و رنگ c رنگ‌های یکسانی هستند. پس در این وضعیت گراف با c-1 رنگ، رنگ آمیزی شده‌است. بنابر فرض استقرا این گراف شامل ${\displaystyle K_{ni}}$ تک رنگ است که رنگ i در بازهٔ ${\displaystyle 1\leq i\leq (c-2)}$ قرار دارد یا شامل یک ${\displaystyle K_{R\left(n_{c-1},n_{c}\right)}}$ رنگ شده با رنگ‌های تیره‌است. در حالت اول کار ما به پایان رسیده‌است. در حالت دوم دیدگاه خود را مورد بازبینی قرار می‌دهیم و می‌بینیم که بنا بر تعریف ${\displaystyle R\left(n_{c-1},n_{c}\right)}$ ما باید یا یک گراف ${\displaystyle K_{n_{c-1}}}$ که به تمامی با تک رنگ (c-1) رنگ شده داشته باشیم یا یک گراف ${\displaystyle K_{n_{c}}}$ که با تک رنگ c رنگ شده باشد. در هر دو حالت اثبات کامل است.

اعداد رمزی

اعداد ${\displaystyle R\left(r,s\right)}$ در قضیهٔ رمزی (و بسط یافتهٔ آن‌ها در موارد با بیش از دو رنگ) تحت عنوان اعداد رمزی شناخته می‌شوند. یک حد بالا برای ${\displaystyle R\left(r,s\right)}$ را، می‌توان از اثبات قضیه استخراج کرد و سایر استدلال‌ها نیز حد پایین برای آن ارائه می‌کنند. (نخستین حد پایین توسط Paul Erdős با استفاده از روش احتمالاتی به دست آمد) هر چند شکاف بزرگی میان مقادیر حد پایین و حد بالا وجود دارد. من تبع آن تعداد بسیار اندکی از r وsها هستند که ما برای آن‌ها مقدار دقیق ${\displaystyle R\left(r,s\right)}$ را می‌دانیم. محاسبهٔ حد پایین L برای ${\displaystyle R\left(r,s\right)}$ معمولاً نیازمند ارائهٔ یک رنگ آمیزی گراف ${\displaystyle K_{L-1}}$ با دو رنگ قرمز و آبی است به‌طوری‌که هیچ زیرگراف آبی ${\displaystyle K_{r}}$ و هیچ زیرگراف قرمز ${\displaystyle K_{s}}$ در آن یافت نشود. هر چند که بررسی حالت‌های مختلف رنگ آمیزی گراف ${\displaystyle K_{n}}$ با افزایش مقدار n از نظر محاسباتی بسیار پیچیده خواهد شد. تعداد حالت‌های رنگ آمیزی رشدی بالاتر از رشد نمایی(exponentially) دارد.

در حال حاضر حتی مقدار دقیق ${\displaystyle R\left(5,5\right)}$ شناخته شده‌است هر چند که از قبل می‌دانستیم که مقدار آن بین ۴۳(توسط Geoffrey Exoo) و 49 (Brendan McKay، وStanisław Radziszowski) قرار دارد. احتمال داده می‌شود که مقدار دقیق ${\displaystyle R\left(6,6\right)}$ برای همیشه مجهول بماند. Paul Erdős می‌گوید:

" بیگانگانی (نیروهای خارجی) را تصور کنید که بسیار نیرومندتر از ما بر روی زمین هستند و از ما خواسته‌اند که مقدار ${\displaystyle R\left(5,5\right)}$ را محاسبه کنیم و در غیر این صورت سیارهٔ ما را نابود خواهند کرد. در این حالت ما باید تمام کامپیوترها و ریاضی دان هایمان را به کار بگیریم و برای یافتن مقدار مورد نظر به شدت تلاش کنیم. حال به جای این تصور کنید که از ما خواسته شده تا مقدار ${\displaystyle R\left(6,6\right)}$ را محاسبه نماییم، در این وضعیت ما باید تمام تلاشمان را برای نابود کردن بیگانگان به کار ببریم!"

مقدار ${\displaystyle R\left(r,s\right)}$ برای مقادیر r و s تا ۱۰ در جدول زیر نشان داده شده‌است. از آن جایی که در بسیاری از موارد مقدار دقیق را نمی‌دانیم، بهترین حدود یافت شده در جدول به نماش گذاشته شده‌است. ${\displaystyle R\left(r,s\right)}$ برای مقادیر r و s کوچک‌تر از ۳ به صورت R(1,s) = ۱و R(2,s) = s برای تمام مقادیرs داده شده‌است.

r,s	۱	۲	۳	۴	۵	۶	۷	۸	۹	۱۰
۱	۱	۱	۱	۱	۱	۱	۱	۱	۱	۱
۲	۱	۲	۳	۴	۵	۶	۷	۸	۹	۱۰
۳	۱	۳	۶	۹	۱۴	۱۸	۲۳	۲۸	۳۶	۴۰–۴۲
۴	۱	۴	۹	۱۸	۲۵	۳۶–۴۱	۴۹–۶۱	۵۸–۸۴	۷۳–۱۱۵	۹۲–۱۴۹
۵	۱	۵	۱۴	۲۵	۴۳–۴۸	۵۸–۸۷	۸۰–۱۴۳	۱۰۱–۲۱۶	۱۲۶–۳۱۶	۱۴۴–۴۴۲
۶	۱	۶	۱۸	۳۶–۴۱	۵۸–۸۷	۱۰۲–۱۶۵	۱۱۳–۲۹۸	۱۳۲–۴۹۵	۱۶۹–۷۸۰	۱۷۹–۱۱۷۱
۷	۱	۷	۲۳	۴۹–۶۱	۸۰–۱۴۳	۱۱۳–۲۹۸	۲۰۵–۵۴۰	۲۱۷–۱۰۳۱	۲۴۱–۱۷۱۳	۲۸۹–۲۸۲۶
۸	۱	۸	۲۸	۵۸–۸۴	۱۰۱–۲۱۶	۱۳۲–۴۹۵	۲۱۷–۱۰۳۱	۲۸۲–۱۸۷۰	۳۱۷–۳۵۸۳	۶۰۹۰–۳۳۱
۹	۱	۹	۳۶	۷۳–۱۱۵	۱۲۶–۳۱۶	۱۶۹–۷۸۰	۲۴۱–۱۷۱۳	۳۱۷–۳۵۸۳	۵۶۵–۶۵۸۸	۵۸۱–۱۲۶۷۷
۱۰	۱	۱۰	۴۰–۴۲	۹۲–۱۴۹	۱۴۴–۴۴۲	۱۷۹–۱۱۷۱	۲۸۹–۲۸۲۶	۶۰۹۰–۳۳۱	۵۸۱–۱۲۶۷۷	۷۹۸–۲۳۵۵۶

در جدول یک تقارن ناچیز در میان قطر نیز وجود دارد. جدول فوق از جدول بزرگ‌تری که توسط Stanisław Radziszowski تألیف شده، اقتباس شده‌است. در سال ۲۰۱۲ قضیه ${\displaystyle R\left(4,6\right)>=36}$ را Geoffrey Exoo اثبات کرد.^[۱]

یک مثال از چندین رنگ: 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.

اگر شما هر رنگی از رنگ‌های تابیده یا ناتابیدهٔ گراف ${\displaystyle K_{16}}$ را انتخاب کنید و گرافی را در نظر بگیرید که یال‌هایش دقیقاً یال‌هایی با همان رنگ ویژه باشد آن گاه به گراف Clebsch دست خواهیم یافت.

دقیقاً دو روش برای رنگ آمیزی یال‌های گراف ${\displaystyle K_{15}}$ با سه رنگ وجود دارد به گونه‌ای که از ایجاد مثلث‌های تک رنگ پرهیز کنیم. این گراف را می‌توان با حذف کردن هر راس دلخواه از گراف تابیده یا ناتابیدهٔ K16 که به‌طور مطلوب رنگ آمیزی شده، به دست آورد.

علاوه بر این دقیقاً ۱۱۵ یال برای رنگ آمیزی ${\displaystyle K_{14}}$ با سه رنگ وجود دارد به گونه‌ای که در آن از ایجاد مثلث‌های تک رنگ جلوگیری شود.

پیوند به بیرون

• بررسی Radziszowski درباره اعداد رمزی کوچک
• بررسی اعداد رمزی در گراف‌های جهت دار

منابع

ویکی‌پدیای انگلیسی

• 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.

1. B. McKay, گرافهای رمزی