اثبات رنگین‌کمانی نشان می‌دهد که گراف‌ها اجزای یکنواختی دارند

در ۸ ژانویه، سه ریاضی‌دان یک اثبات از یک مساله نزدیک به ۶۰ ساله در ترکیبات خطی به نام حدس رینگل منتشر کردند. به طور کلی، پیش‌بینی می‌کند که گراف‌ها - ساختارهای تینکرتوی نقاط و خطوط - می‌توانند کاملا از قطعات کوچک‌تر یک‌سان ساخته شوند.

ریاضی دانان هیجان‌زده هستند که دلیل جدید آن را درست می‌داند

گیل کالای، ریاضی دان در دانشگاه عبری اورشلیم که در این پروژه نبوده است، می‌گوید: «یک دلیل بزرگ برای شادی این است که این مساله یک حدس قدیمی را حل می‌کند که مردم نمی‌توانند با روش‌های دیگر حل کنند.»

حدس ریگل پیش‌بینی می‌کند که انواع خاصی از گراف‌های پیچیده - فکر کنید طرح‌های تینکرتوی با تریلیون‌ها قطعه یا بیشتر - می‌توانند «کاشی شده» یا به طور کامل توسط هر نسخه تکی از گراف‌های کوچک‌تر خاص پوشش داده شوند. از نظر مفهومی، این جمله مانند نگاه کردن به آشپزخانه و پرسیدن این است: آیا می‌توانم کف را به طور کامل با کپی‌های یک‌سان از هر نوع کاشی در فروشگاه بپوشانم؟ در زندگی واقعی، بیشتر کاشی‌ها برای آشپزخانه خاص شما کار نمی‌کنند - شما باید اشکال مختلف را با هم ترکیب کنید تا کل کف را بپوشاند. اما در دنیای نظریه گراف، این حدس پیش‌بینی می‌کند که کاشی کاری همیشه جواب می‌دهد.

با کف آشپزخانه، مثل گراف‌ها، جایی که شما اولین کاشی را قرار می‌دهید. کار جدید به این سوال مهم در مورد قراردادن به شکلی که هم شگفت‌انگیز و هم به طرز شگفت آوری شهودی باشد، می‌پردازد.

جنگل و درختان

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

جیکوب فاکس از دانشگاه استنفورد گفت: «شما تکه‌های پازل دارید و مطمئن نیستید که آیا می‌توانید پازل را از روی قطعات کنار هم قرار دهید یا خیر.»

در سال ۱۹۶۳ یک ریاضیدان آلمانی به نام گرهارد رینگول یک سوال ساده اما گسترده از این نوع مطرح کرد. او گفت: اول، با هر عدد فرد از رئوس بزرگ‌تر از ۳ شروع کنید (عدد باید برای حدس عجیب باشد، همانطور که در یک لحظه خواهیم دید). لبه‌های بین آن‌ها را رسم کنید تا هر راس به هر راس دیگری متصل شود. این یک شی را ایجاد می‌کند که گراف کامل نامیده می‌شود.

سپس، در مورد نوع دیگری از نمودار فکر کنید. این می‌تواند یک مسیر ساده متصل به یک خط باشد. یا می‌تواند یک مسیر با لبه‌های دیگری باشد که از آن منشعب می‌شوند. شما می‌توانید شاخه‌ها را به شاخه‌ها اضافه کنید. شما می‌توانید گراف را تا جایی که می‌خواهید پیچیده کنید، تا زمانی که شامل هیچ حلقه بسته‌ای نباشد. این نوع گراف‌ها درخت نامیده می‌شوند.

سوال ریگل در مورد رابطه بین گراف‌های کامل و درختان بود. او گفت: اول یک گراف کامل حاوی 2n+1 راس را تصور کنید (یعنی یک عدد فرد). سپس در مورد هر درخت ممکن که می‌توانید از n + 1 راس استفاده کنید فکر کنید - که به طور بالقوه تعداد زیادی درخت مختلف است.

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

رینگل پیش‌بینی کرد که اگر شما به حرکات ادامه دهید، با فرض اینکه شما کار را در جای مناسب شروع کنید، قادر خواهید بود که گراف کامل را به طور کامل کاشی کنید. این بدان معنی است که هر یال در گراف کامل توسط یک یال در درخت پوشش داده می‌شود و هیچ کپی از درخت با هم همپوشانی ندارد.

«من می‌توانم از درخت کپی بگیرم. من یک کپی از آن را روی نمودار کامل گذاشتم. بعضی از لبه‌ها را می‌پوشاند.» این را بنی ساداکوف از موسسه فدرال فن‌آوری زوریخ، یکی از نویسندگان اثبات جدید با ریچارد مونتگومری از دانشگاه بیرمنگام و الکسی پوکروسکی از کالج بیرکبک، دانشگاه لندن، می‌گوید. و ادامه می‌دهد: «من به انجام این کار ادامه می‌دهم و حدس می‌زنم که شما می‌توانید همه چیز را کاشی کنید.»

سرانجام، رینگل پیش‌بینی کرد که کاشی کاری بدون توجه به این که از کدام یک از درختان ممکن مختلف برای انجام آن استفاده می‌کنید، کار می‌کند. این ممکن است بسیار وسیع به نظر برسد. حدس رینگل به طور مساوی برای تکمیل گراف‌های با ۱۱ راس و گراف‌های کامل با ۱۱ تریلیون و ۱ راس به کار می‌رود. و همانطور که گراف‌های کامل بزرگ‌تر می‌شوند، تعداد درخت‌های ممکن را می‌توانید با استفاده از n + 1 راس نیز به آسمان بکشید. چگونه هر یک از این درختان می‌توانند به طور کامل یک نمودار کامل را تشکیل دهند؟

اما دلایلی وجود داشت که فکر کنم حدس و گمان ریگل درست باشد. نزدیک‌ترین آن‌ها این بود که حساب ترکیبی ساده حدس را رد نکرد: تعداد یال‌ها در یک گراف کامل با 2n+1 راس همیشه می‌تواند توسط تعداد یال‌ها در یک درخت با n + 1 راس به طور مساوی تقسیم شود.

مونتگومری گفت: «مهم است که تعداد یال‌ها در درخت تعداد یال‌ها را در گراف کامل تقسیم کند.»

ریاضی‌دانان به سرعت شواهد دیگری را شناسایی کردند که نشان می‌داد این حدس حداقل عملی است، و زنجیره‌ای از اکتشافات را به حرکت در آورد که سرانجام به اثبات رسید.

جانشانی و چرخش

یکی از ساده‌ترین درختان یک ستاره است: یک راس مرکزی با یال‌های درخشان از آن. اما با تصویر معمول یک ستاره متفاوت است، چون لبه‌ها نباید به طور یکنواخت در اطراف راس مرتب شوند. آن‌ها فقط باید از یک مکان گسترش یابند، و نمی‌توانند یکدیگر را در هر جایی به جز راس مرکزی قطع کنند. اگر بخواهید حدس (رینگل) را بررسی کنید، درختی که شبیه یک ستاره است، مکان طبیعی برای شروع خواهد بود.

و در واقع ریاضی دانان به سرعت مشاهده کردند که ستاره با n + 1 راس همیشه می‌تواند یک گراف کامل با 2n+1 راس را به طور کامل کاشی کند. این واقعیت به تنهایی جالب است، اما راهی که برای اثبات آن وجود دارد، این است که واقعا ریاضی دانان فکر می‌کنند.

یک مثال ساده را در نظر بگیرید. با ۱۱ راس شروع کنید. این رئوس را در یک دایره مرتب کنید و سپس هر راس را با هر راس دیگر متصل کنید تا یک گراف کامل را تشکیل دهید.

حالا ستاره متناظر را در نظر بگیرید: یک نقطه مرکزی با پنج یال که از آن خارج شده‌اند.

سپس ستاره را طوری قرار دهید که راس مرکزی با یکی از ریوس گراف کامل موازی شود. بعضی از آن‌ها را اما نه همه آن‌ها را. حالا ستاره را یک راس در سمت چپ قرار دهید، انگار که می‌خواهید صورت یک قطب‌نما را بچرخانید. شما یک کپی جدید از ستاره خود خواهید داشت که بر روی یک مجموعه کاملا متمایز از یال‌ها در گراف کامل قرار دارد.

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

ساداکوف گفت: «ما می‌دانیم که اگر درخت یک ستاره باشد، این حدس کاملا ساختگی نیست. علاوه بر این، ما می‌توانیم آن را به این شکل زیبا نشان دهیم: نمودار را روی یک دایره قرار دهید، ستاره را عوض کنید، کپی‌های جدید بگیرید، و به این ترتیب کاشی کاری انجام خواهد شد.»

مدت کوتاهی پس از این که ریگل حدس خود را منتشر کرد، یک ریاضیدان اسلواک - کانادایی به نام آنتون کوتزیگ از این مثال برای پیش‌بینی حتی شجاع‌تر از ریگل استفاده کرد. در حالی که ریگل گفت که هر گراف کامل با 2n+1 راس می‌تواند توسط هر درختی با n + 1 راس کاشی کاری شود، کوتزیگ حدس زد که کاشی کاری همیشه می‌تواند دقیقا همان کاری که با ستاره انجام می‌شود انجام شود: با قرار دادن درخت در گراف کامل و سپس چرخش ساده آن.

مثل یک ایده خیالی به نظر می‌رسید. ستاره متقارن است و در نتیجه مهم نیست چطور آن را قرار دهید. با این حال، بیشتر درختان به شکل گنگی هستند. آن‌ها باید دقیقا مناسب روش چرخشی کار قرار گیرند.

پوکروسکی گفت: «ستاره این ساختار ساده را دارد که به شما اجازه می‌دهد آن را با دست قرار دهید، اما اگر یک درخت وحشی با شاخه‌های مختلف داشته باشید، سخت است تصور کنید که چطور یک محل دقیق برای آن پیدا کنید.»

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

رنگ‌آمیزی رنگین‌کمان

کدگذاری رنگی اغلب زندگی را آسان‌تر می‌کند. این می‌تواند به شما کمک کند تقویم خود را سازمان دهی کنید و یا به سرعت بین جعبه‌های غذا در یک خانواده بزرگ تمایز قائل شوید. معلوم می‌شود که این یک راه موثر برای فهمیدن این است که چگونه اولین درخت را درون یک گراف کامل قرار دهید.

دوباره در مورد گراف کامل با ۱۱ راس که دور یک دایره ردیف شده‌اند فکر کنید. شما می‌خواهید لبه‌های آن را با توجه به یک قانون ساده، که مربوط به فاصله بین دو راس متصل به یک یال است، رنگ کنید.

این فاصله به صورت تعداد فضاهای اطراف دایره تعریف می‌شود که باید از یک راس به راس دیگر بروید. (بدون میان‌بر در داخل دایره) البته شما همیشه می‌توانید یکی از دو راه را در اطراف یک دایره بروید، بنابراین فاصله را به عنوان مسیر کوتاه‌تر بین دو راس در نظر بگیرید. اگر راس‌های مجاور هم باشند فاصله بین آن‌ها ۱ است نه ۱۰. اگر دو راس توسط یک راس دیگر جدا شوند فاصله بین آن‌ها ۲ است.

حالا لبه‌های گراف را براساس فاصله رنگ کنید. تمام لبه‌هایی که راس‌های یک واحدی را به هم متصل می‌کنند، رنگ یک‌سان، مثلا آبی را دریافت می‌کنند. همه یالی که راس‌های دو واحدی را به هم متصل می‌کنند، رنگ یکسانی را دریافت می‌کنند.

این کار را ادامه دهید تا لبه‌هایی که راس‌های یک فاصله را به هم متصل می‌کنند همگی رنگ یکسانی دریافت کنند. همچنین باید از یک رنگ متفاوت برای هر فاصله استفاده کنید. در یک گراف کامل با 2n+1 راس، شما برای اجرای طرح به n رنگ مختلف نیاز دارید. در پایان یک طرح زیبا - و یک طرح مفید - خواهید داشت.

کمی پس از اینکه رینگل و کوتزیگ فرضیات خود را مطرح کردند، کوتزیگ دریافت که این رنگ‌آمیزی کامل گراف می‌تواند به عنوان راهنمایی برای چگونگی قرار دادن یک درخت بر روی آن عمل کند. ایده این بود که درخت را طوری قرار دهید که یک لبه از هر رنگ را پوشش دهد و دو بار هیچ رنگی را نپوشاند. ریاضی دانان این محل را یک کپی رنگین‌کمانی از درخت می‌نامند. از آنجا که رنگ‌آمیزی به n رنگ نیاز دارد، و درخت با n+1 راس n یال دارد، بلافاصله می‌دانیم که حداقل ممکن است که همیشه یک کپی رنگین‌کمان وجود داشته باشد.

تا اواخر دهه ۱۹۶۰، ریاضی دانان فهمیدند که کپی رنگین کمانی درخت یک ویژگی بسیار خاص دارد: این دقیقا نقطه شروع درست برای چرخش درخت به منظور کاشی کردن گراف.

پوکروسکی گفت: «اگر شما یک کپی رنگین‌کمان بگیرید، کاشی کاری همیشه جواب می‌دهد.»

حالا ریاضی دانان می‌دانستند که می‌توانند حدس ریگل را با اثبات اینکه هر گراف کامل با 2n+1 راس شامل یک کپی رنگین‌کمان از هر درخت با n + ۱ راس است، ثابت کنند. اگر کپی رنگین‌کمان همیشه وجود داشته باشد، کاشی کاری همیشه جواب می‌دهد.

اما اثبات وجود چیزی همیشه دشوار است. برای انجام این کار، ریاضی دانان باید ثابت کنند که گراف‌های کامل نمی‌توانند کمکی بکنند بلکه حاوی کپی‌های رنگین کمانی از درختان هستند. بیش از ۴۰ سال طول کشید، اما این دقیقا همان کاری است که سودکوف و همکارانش در اثبات جدید خود انجام دادند.

پر کردن کامل

تصور کنید که یک گراف کامل با ۱۱ راس و یک درخت با ۶ راس به شما داده می‌شود. نمودار کامل با پنج رنگ مختلف رنگ‌آمیزی شده‌است. درخت پنج یال دارد. وظیفه شما پیدا کردن یک کپی رنگین کمانی از درخت در داخل گراف کامل است.

شما می‌توانید به سادگی لبه‌های درخت را در یک زمان روی گراف قرار دهید. قرار دادن لبه اول آسان است: می‌تواند بر روی هر لبه از هر رنگ دیگری قرار گیرد. لبه دوم کمی سخت‌تر است. می‌تواند تقریبا به هر جایی برود، نه بر روی یک یال کامل گراف که همان رنگی است که قبلا پوشش داده‌اید. اما همانطور که به قرار دادن لبه‌های درخت خود ادامه می‌دهید، کار قرار دادن درخت بعدی سخت‌تر می‌شود. زمانی که به آخرین لبه درخت می‌رسید، دیگر انتخابی برای این که کدام رنگ را پوشش دهد ندارید - تنها یک رنگ باقی مانده‌است. بهتر است امیدوار باشید که از قبل برنامه‌ریزی شغلی خوبی انجام داده باشید!

این ایده که کار پیدا کردن یک کپی رنگین کمانی از یک درخت با قرار دادن لبه‌های بیشتر آن سخت‌تر می‌شود، در مرکز توجه سه ریاضی‌دان قرار داشت. آن‌ها به دنبال راه‌هایی بودند تا در پایان این فرآیند بیش‌ترین انعطاف‌پذیری را داشته باشند.

آن‌ها از همان ابتدا می‌دانستند که پیدا کردن نسخه‌های رنگین کمانی از درختان بسیار ساده آسان است - درختان به شکل یک مسیر طولانی، یا یک مسیر طولانی با چند شاخه کوتاه. سخت‌ترین درختان برای قرار دادن صحیح آن‌هایی بودند که لبه‌های زیادی دارند و در یک راس همگرا می‌شوند، مانند ستاره‌ها، اما با شکل غیر یکنواخت و نامنظم. قرار دادن آن‌ها مثل این است که سعی کنید یک کالسکه را وقتی نیمه‌پر است در صندوق عقب اتومبیل قرار دهید.

پوکروسکی گفت: «مشکل زمانی پیش می‌آید که شما سعی دارید نمودار کامل را با چیزهای انعطاف‌ناپذیر که شبیه ستاره هستند، بسته‌بندی کنید»

همان طور که هر کس که چمدان را بسته‌بندی می‌کند می‌داند، شما باید با دشوارترین اشیا شروع کنید: بزرگ‌ترین چمدان و اشیا بزرگ و غیرقابل‌انعطاف مانند دوچرخه. در آخر کار همیشه می‌توانید کت و شلوار بپوشید. ریاضی دانان نیز این فلسفه را پذیرفته‌اند.

درختی را با ۱۱ یال تصور کنید. شش‌تایشان در یک راس مرکزی گرد هم می‌آیند. بقیه یک شکل واحد دارند که از آن خارج می‌شود، مثل یک تنگه.

سخت‌ترین بخش درخت برای قرار دادن راس با شش یال است. بنابراین ریاضی دانان آن را از بقیه درخت جدا کردند و اول آن را قرار دادند تا در نهایت قسمت دیگر را دوباره وصل کنند، درست همان طور که شما می‌توانید یک تخت‌خواب را از هم جدا کنید تا آن را به طبقه بالا ببرید و بعد وقتی آن را در اتاق خود دارید آن را کنار هم قرار دهید. در واقع، آن‌ها فقط بخش ستاره را یک‌بار قرار ندادند - آن‌ها مکان‌های مختلفی را برای کپی کردن ستاره در داخل گراف کامل پیدا کردند. سپس به طور تصادفی یکی از آن‌ها را انتخاب کردند.

با انجام این کار، آن‌ها اطمینان حاصل کردند که فضای باقی مانده در گراف کامل نیز تصادفی است - به این معنی که دارای توزیع تقریبا برابر لبه‌های رنگ‌های مختلف است. این فضایی بود که باید بقیه درخت را در آن قرار می‌دادند - راهی که کنار گذاشته بودند.

آن‌ها با محدودیت‌هایی در نحوه قرار دادن آن مواجه شدند. این مسیر باید با بخش ستاره‌ای که قبلا قرار داده بودند ارتباط برقرار می‌کرد، و همچنین باید رنگ‌هایی را که قبلا توسط ستاره‌ای که به آن متصل بود پوشیده نشده بود، بپوشاند.

اما ریاضی دانان به خودشان گزینه‌هایی داده بودند. آن‌ها می‌توانستند مسیر را به تقریبا هر یک از نسخه‌های مختلف ستاره متصل کنند.

حتی بهتر از آن، چون فضای اطراف ستاره تصادفی بود، ریاضی دانان گزینه‌هایی داشتند که در مورد آن رنگ‌های باقیمانده درخت را پوشش می‌دادند.

مونتگومری گفت: «در پایان تعبیه، وقتی همه چیز دشوار می‌شود، به جای داشتن یک رنگ که باید از آن استفاده کنم، من انتخاب کمی دارم.»

سه ریاضی‌دان اثبات خود را با یک بحث احتمالاتی به پایان رساندند. آن‌ها نشان دادند که زمانی که سخت‌ترین بخش‌های یک درخت را در خود جای می‌دادند، اگر فضای باقی مانده در گراف کامل اساسا تصادفی بود، همیشه راهی وجود داشت که آن‌ها می‌توانستند باقی مانده درخت را برای گرفتن یک کپی رنگین کمانی تعبیه کنند.

نوگا الون از دانشگاه پرینستون گفت: «شما می‌توانید از آنچه که در ابتدا باقی مانده استفاده کنید تا چیزی را که از درخت باقی مانده جذب کنید تا یک رنگ کلی رنگین‌کمان ایجاد کنید.»

ریاضی دانان راه دقیقی برای پیدا کردن یک کپی رنگین‌کمان از هر درخت با n + 1 راس در هر گراف کامل با 2n+1 راس پیدا نکردند. اما آن‌ها ثابت کردند که یک کپی رنگین‌کمان باید وجود داشته باشد.

و اگر کپی رنگین‌کمان همیشه وجود داشته باشد، پس همیشه امکان دارد که دقیقا همان کاری را انجام دهیم که رینگل پیش‌بینی کرده بود. حدس درست بود.

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

فاکس گفت: «این نشان می‌دهد که روش‌هایی که مردم برای مدتی در مورد آن‌ها فکر کرده‌اند در واقع بسیار قدرتمند هستند. زمانی که آن‌ها را به درستی تطبیق می‌دهید، می‌توانید این پرسش‌ها را حل کنید که به نظر می‌رسید دور از دسترس هستند.»

چاپ‌شده در: مجله Quanta به تاریخ ۱۹ فوریه ۲۰۲۰
نویسنده: Kevin Hartnett
لینک مقاله اصلی:https://www.quantamagazine.org/mathematicians-prove-ringels-graph-theory-conjecture-20200219/

این مقاله توسط ربات هوشمند ترجمه انگلیسی به فارسی متن تخصصی و به صورت خودکار ترجمه شده و می‌تواند به صورت محدود دارای اشکالات ترجمه باشد.