دور کمر و رنگ آمیزی گراف ها و ربطش به چیزهای دیگر

من پنج شش سال پیش درس تئوری گراف را در دانشگاه گرفتم. خیلی از قضایای این درس با این که جالب بودند الان از یادم رفته اما یک قضیه نسبتا ساده اما فوق العاده زیبا و عمیق در مورد رنگ آمیزی گراف ها هست که هیچ وقت یادم نمی رود. احتمالا شمای خواننده از درس های دبیرستان یادت هست که جماعت ریاضی دان خیلی علاقه دارند ببینند برای رنگ آمیزی یک گراف به گونه ای که هیچ دو راس مجاوری از گراف رنگ مشابهی نداشته باشند چه تعداد رنگ لازم هست. کلا رنگ آمیزی گراف در حالت کلی مساله سختی است و برای مثال هیچ الگوریتم بهینه ای شناخته شده ای وجود ندارد که به ما بگوید آیا می شود یک گراف را با تعداد مشخصی رنگ داده شده رنگ کرد یا نه. یک سوال جالب دیگر این است که اگر یک گرافی تُنُک بود یعنی خیلی یال های زیادی بین راس های مختلف آن نبود آیا رنگ آمیزی آن آسان تر می شود یا نه. شهود به ما گوید احتمالا بله. برای مثال یک گراف به شکل یک حلقه را در نظر بگیرید. این گراف دو یا سه رنگ مختلف بیشتر برای رنگ آمیزی اش نیاز ندارد حالا هر تعداد راس در حلقه باشد. حالا یک معیار برای تنکی می تواند این باشد: اندازه کوچکترین دور (حلقه) در گراف. اگر این عدد بزرگ باشد معنی اش این راس های گراف خیلی به هم متصل نیستند چون اگر بودند می شد های حلقه های کوچک در گراف پیدا کرد. به این عدد دور کمر (ترجمه خوشحال من از girth) گراف می گویند. وقتی دور کمر یک گراف بالا است معنی اش این است حداقل به صورت محلی اگر یک بخش از آن گراف را در نظر بگیریم تعداد رنگ های زیادی برای رنگ آمیزی آن نیاز نداریم:

یک گراف با دور کمر 4 که تنها 2 رنگ برای رنگ آمیزی هر هم چهار راس مجاور آن کافی است اما برای رنگ آمیزی کل گراف به حداقل 4 رنگ نیاز است.

حالا سوال این است. تمامی گراف هایی را که دور کمرشان g است در نظر بگیرید. آیا تعداد به اندازه کافی بزرگی رنگ k وجود دارد که بشود با این تعداد تمامی این گراف ها را رنگ کرد؟ به عبارت دیگر آیا هر که گرافی به صورت محلی قابل رنگ آمیزی با تعداد کمی رنگ است در کل هم با تعداد کمی رنگ قابل رنگ آمیزی است؟
قضیه ساده و زیبایی که اشاره کردم که در سال 1959 ریاضیدان معروف و معتاد Paul Erdős آن را ثابت کرد می گوید که بر خلاف شهود اولیه ما لزوما نه: برای هر دور کمر g و تعداد رنگ ،k گراف هایی وجود دارند که  kرنگ برای رنگ آمیزی کل هر گراف کافی نباشد.

اگر می خواهید اثبات این قضیه را بخوانید که خیلی هم سخت نیست و به بیشتر از آمار و احتمال و ترکیبیات دوره کارشناسی نیازی ندارد اینجا را ببینید*.

ممکن است شما اینجا بپرسید چرا این قضیه از نظر من این قدر مهم است که بدون اثبات در موردش بنویسم؟
جوابش بر می گردد به سیستم های پیچیده و داستان emergence. همان طور که قبلا هم در در موردش نوشته بودم  emergence  به این معنا است در یک سیستم پیچیده ممکن است مجموعه‌ای از قوانین ساده در اجزا سیستم باعث ایجاد رفتاری غیرقابل انتظار و جدید در کل بشوند و این رفتار جدید به جای انکه در اجزا سیستم تعریف شده باشد نتیجه مستقیم ارتباط و اثر گذاری متقابل اجزای سیستم بر هم دیگر باشد (یک مثال از نتایج فلسفی emergence و چرا این پدیده مهم است).
 
این قضیه هم به نظر من یک مثال غیر منتظره از emergence یک رفتار جدید در کل یک سیستم است: گراف هایی وجود دارند که به صورت محلی با تعداد کمی رنگ قابل رنگ آمیزی اند اما نتیجه بر هم کنش اجزای گراف با یک دیگر در کل دیگر از قواعد محلی تبعیت نمی کند و در نتیجه این گراف ها با تعداد کمی رنگ در کل قابل رنگ آمیزی نیستند. به عبارت دیگر بر هر کنش اجزای گراف و نحوه ارتباط آنها با یکدیگر می تواند قوانین رنگ آمیزی را در سطح کل گراف تغییر دهد و هر تعداد رنگ هم داشته باشیم گرافی هست که ماحصل جمع اجزایش را نشود رنگ کرد و آسانی رنگ آمیزی اجزای آن گراف کمکی به ما نکند. از آن طرف هم در اکثر مثال هایemergence  رابطه اجزا با یک دیگر آنقدر پیچیده است که حل معادلات حاکم بر سیستم غیر ممکن است و نمی شود به صورت تحلیلی رفتار سیستم در کل را از قوانین محلی و نحوه ارتباط اجزا با هم استخراج کرد و تنها با شبیه سازی کامپیوتری - آن هم اگر با هزار قسم و آیه ممکن باشد - می شود دید که آیا رفتارجدیدی در سیستم در کل بر مبنای قوانین به وجود میاید یا نه. چیزی که این مثال بیش از پیش جالب و جذاب می کند و باعث می شود من هیچ وقت این قضیه را فراموش نکنم این است که در این مورد خاص نیازی به شبیه سازی کامپیوتری نیست و با ریاضیات نسبتا ساده اما خلاقانه ای می شود در مورد قوانین حاکم بر کل سیستم بر مبنای قوانین محلی اظهار نظر کرد.

* کلیت ایده این اثبات بر مبنای استفاده از گراف های تصادفی است. در یک گراف تصادفی هر یال به صورت تصادفی ممکن است رسم بشود و یا نشود. گراف های تصادفی موجودات جالبی هستند و خواص جالب زیاد دارند که شاید در موردشان نوشتم. در این اثبات خاص هم Erdős نشان داد که اگر برای هر گراف با دور کمر g و تعداد راس n اگر یال ها با یک تابع تصادفی به خصوص از g و n رسم شوند و بگذاریم اندازه این گراف یعنی n  به بی نهایت میل کند در نهایت یک گراف پیدا خواهیم کرد که با دور کمر g به حداقل تعداد مشخصی رنگ برای رنگ آمیزی کل آن نیاز باشد.