یک جهش بسیار کوچک به جلو در نظریه گراف

در 15 مارس، اعلانات جذاب سمینار، غوغاهایی را در زمینه ترکیب شناسی، مطالعه ریاضی شمارش، منتشر کرد. سه نفر از همکاران برنامه ریزی کردند تا در روز بعد گفتگوهای هماهنگ انجام دهند. جولیان ساهاسرابوده در حالی که ریاضیدانان در کمبریج انگلستان را مورد خطاب قرار می دهد سایمون گریفیث اخبار را در ریودوژانیرو به اشتراک می گذاشت و مارسلو کامپوس در سائوپائولو هر سه گفتگو عناوین یکسان و چکیده‌های رمزآلود و دو جمله‌ای داشتند که به «پیشرفت اخیر در مورد مشکل قدیمی Erdős» اشاره می‌کردند. در حالی که پل اردوس، ریاضیدان مجارستانی که در سال 1996 درگذشت، ژست گرفت. صدها مشکل در طول دوران حرفه‌ای او، ترکیب‌گرایان به سرعت موضوع خاصی را که این سه نفر قصد داشتند درباره آن صحبت کنند، تشخیص دادند. شایعات در مورد چیزی به نام عدد رمزی، یکی از دشوارترین مقادیر برای محاسبه در تمام ریاضیات، به گوش می رسید.

اعداد رمزی یک رشته کامل به نام نظریه رمزی را ایجاد کرده است که به دنبال الگوهای اجتناب ناپذیر در طیف وسیعی از سیستم ها می گردد.

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

عدد رمزی نشان می‌دهد که یک مثال پارادایماتیک باید چقدر بزرگ باشد قبل از اینکه الگوهای خاص به طور اجتناب‌ناپذیری به وجود بیایند. اما علیرغم مرکزیت آن، هیچ کس نتوانسته است عدد رمزی را برای همه محاسبه کند، به جز این ساده ترین نمونه ها. بهترین کاری که آنها توانسته‌اند انجام دهند این است که محدودیت‌ها (یا حد و مرزها) را در مورد آنچه ممکن است انجام دهند، بیابند. حتی در آن زمان، حد بالایی که برای اولین بار توسط Erdős و یکی از همکارانش نزدیک به یک قرن پیش ایجاد شد، به سختی تکان خورده بود.

سپس، در سمینارهای 15 مارس، و در مقاله ای که بعد از ظهر همان شب منتشر شد، محققان اعلام کردند که کران بالایی عدد رمزی را به میزان نمایی بهبود بخشیده اند.

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

خطوط حزب

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

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

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

اما تعیین اندازه عدد رمزی سخت است. در سال 1935، پنج سال پس از اینکه رمزی نشان داد وجود دارد، Erdős و George Szekeres حد بالایی جدید و محکم‌تر در مورد اینکه عدد رمزی برای دسته‌ای با اندازه معین چقدر است، ارائه کردند. اما از آن زمان به بعد، ریاضیدانان به سختی توانسته اند در محاسبات Erdős و Szekeres پیشرفت کنند.

برای دریافت شهود بهتر از معنای این، یک مثال کلاسیک را در نظر بگیرید، که در آن گره‌ها نماینده مهمانان در یک مهمانی هستند. لبه بین هر دو میهمان را اگر قبلاً ملاقات کرده‌اند قرمز و اگر ملاقات نکرده‌اند آبی کنید. می‌توانید هر اندازه دسته‌ای را که دوست دارید انتخاب کنید — افراد کافی را به مهمانی دعوت کنید، و نمی‌توانید از دعوت گروهی از افرادی که همگی یکدیگر را می‌شناسند (یک دسته به چند معنا از کلمه) یا دعوت از گروهی از افرادی که همگی یکدیگر را می‌شناسند اجتناب کنید. قبلا هرگز ملاقات نکرده اند

گفت: "ساده ترین چیزی که می توانید در یک نمودار داشته باشید، یک دسته تک رنگ است." ماریا چادنوفسکی، ریاضیدان دانشگاه پرینستون. این یک نوع شگفت انگیز است که در هر نمودار بزرگ می توانید یک نمودار بزرگ از آن ها را پیدا کنید. کاملاً مشخص نیست.»

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

نشان دادن اینکه عدد رمزی برای دسته‌ای با اندازه 3 یا R(3) 6 است چندان سخت نیست (نمودار را ببینید). اما تا سال 1955 بود که R(4) روی 18 سنجاق شد. R(5) ناشناخته باقی می ماند - حداقل 43 است و از 48 بزرگتر نیست. اگرچه این اعداد کوچک هستند، غربال کردن تمام رنگ های ممکن وجود ندارد. دیوید کانلون از موسسه فناوری کالیفرنیا در مورد این سوال گفت. تعداد رنگ‌ها را روی یک نمودار کامل با 43 گره در نظر بگیرید. شما 903 لبه دارید. هر کدام از آن ها را می توان به دو صورت رنگ آمیزی کرد. بنابراین شما 2 می گیرید⁹⁰³، که فقط از نظر نجومی بزرگ است."

با افزایش اندازه دسته، کار تعیین عدد رمزی دشوارتر می شود. Erdős با کنایه گفت که جنگ همه جانبه با بیگانگانی که از نظر ریاضی نیاز دارند آسان تر از تلاش برای R(6) را پیدا کنید، که چیزی بین 102 و 165 است. دامنه عدم قطعیت به سرعت رشد می کند: با توجه به برآوردهای گردآوری شده توسط استانیسلاو رادزیزوفسکی، R(10) می تواند به کوچکی 798 و به بزرگی 23,556 باشد. اما اهداف ریاضیدانان بسیار فراتر از عدد رمزی 10 است. آنها فرمولی می خواهند که تخمین خوبی از R(k، حتی - یا به خصوص - زمانی که k فوق العاده بزرگ است

ویگدرسون گفت: "من فردی را در علم ترکیبی نمی شناسم که حداقل کمی به این مشکل فکر نکرده باشد." "به نظر من این مشکل واقعاً خاص است."

دستور در دادگاه

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

پنج سال بعد، Erdős و Szekeres نشان دادند که عدد رمزی از k کمتر از 4 است^k. و 12 سال بعد از آن، Erdős نشان داد که از حدود $latex sqrt{2}^k$ بزرگتر است. برای انجام این کار، او شانس این را محاسبه کرد که یک نمودار با لبه های رنگی تصادفی حاوی یک دسته تک رنگ باشد. این تکنیک "احتمالی" به شدت در نظریه گراف تأثیرگذار شد. R(k) بین دو پست هدف که به طور تصاعدی در حال رشد هستند: $latex sqrt{2}^k$ و $latex 4^k$.

با گذشت دهه ها، ریاضیدانان زیادی تلاش کردند تا شکاف بین مقادیر ممکن عدد رمزی را کاهش دهند. برخی موفق شدند: در سال 1975، جوئل اسپنسر حد پایین را دو برابر کرد. و یک سری مقالات توسط کنلون, اندرو توماسون و اشوین سه حد بالایی را پایین آورد با ضریب حدود $latex 4^{log(k)^2}$ تا سال 2020. اما در مقایسه با اندازه کرانهای عدد رمزی، این تنظیمات کوچک بودند. در مقابل، هر کاهش به 4 در فرمول Erdős و Szekeres R(k) < 4^k یک پیشرفت تصاعدی خواهد بود که به سرعت در حال رشد است k بزرگتر می شود

گفت: "به نظر می رسد فقط یک سوال کوچک زیبا باشد." راب موریس، یک ریاضیدان در IMPA، موسسه ریاضیات محض و کاربردی برزیل، در ریودوژانیرو، که نتیجه جدید را با Campos، Griffiths و Sahasrabudhe نویسند. قدردانی کمی ظریف است. اما مردم واقعاً به آن اهمیت می دهند.» این احتمالاً دست کم گرفتن است. اگر آنها آن را در سال 1936 ثابت می کردند، مردم می گفتند، خوب، پس مشکل بزرگ چیست؟ بلا بولوباس که مشاور دکترای موریس و ساهاسرابوده در دانشگاه ممفیس بود، گفت. از آن زمان، ثابت شده است که این یک مشکل بسیار بزرگ است، زیرا در طول سال ها، چندین هزار مقاله در مورد انواع مختلف مشکل رمزی نوشته شده است. مانند لیانا یپرمیانیک ریاضیدان در دانشگاه اموری گفت: "اعداد رمزی پلی بین ترکیبات و احتمال و هندسه ایجاد می کنند."

نظریه بازی

 در آگوست 2018، ساهاسرابوده در دوره فوق دکتری زیر نظر موریس در IMPA بود. آن دو امیدوار بودند که پروژه جدیدی را با گریفیث، که در دانشگاه کاتولیک پاپی در همان نزدیکی تدریس می کند، آغاز کنند. مقاله ای از کانلون توجه آنها را جلب کرد. این مقاله یک استراتژی احتمالی برای دستیابی به بهبود تصاعدی در عدد رمزی را تشریح کرد. گریفیث، موریس و ساهاسرابوده شروع به بازی با این ایده کردند.

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

طرح آنها این بود که بر اساس ایده‌های مورد استفاده در اثبات اصلی Erdős و Szekeres مبنی بر اینکه $latex R(k) < 4^k$ استفاده شده است. برای اثبات اینکه عدد رمزی حداکثر $latex 4^k$ است، تصور کنید که یک بازی را روی یک نمودار کامل با گره‌های $latex 4^k$ انجام دهید. بازی دارای دو بازیکن است. ابتدا، حریف شما هر لبه را قرمز یا آبی رنگ می کند، به این امید که لبه ها را به گونه ای رنگ آمیزی کند که از ایجاد یک دسته تک رنگ جلوگیری کند. k گره ها

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

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

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

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

وقتی کارتان تمام شد، داخل سطل ها را نگاه کنید. از آنجایی که یک گره تنها پس از حذف همسایه های آبی آن وارد سطل قرمز می شود، تمام گره های سطل قرمز با لبه های قرمز به هم متصل می شوند - آنها یک دسته قرمز را تشکیل می دهند. به همین ترتیب، سطل آبی یک دسته آبی را تشکیل می دهد. اگر نمودار اصلی شما دارای حداقل گره $latex 4^k$ باشد، می توان ثابت کرد که یکی از این سطل ها باید حداقل شامل k گره ها، یک دسته تک رنگ را در نمودار اصلی تضمین می کنند.

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

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

یک امتحان کتاب باز

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

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

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

کامپوس که در سال 2021 به این پروژه ملحق شد، گفت: "ما برای مدت طولانی گیر کرده بودیم."

در ژانویه امسال، چهار ریاضیدان توافق کردند که به نسخه دیگری از این مسئله روی آورند. آن نسخه پیچیده تر به نظر می رسد، اما معلوم شد که ساده تر است.

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

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

سپس چهار ریاضیدان از کران جدید روی عدد رمزی خارج از مورب استفاده کردند تا راه را برای نتیجه مورب باز کنند. در آغاز فوریه، آنها نهایتاً محدودیت عدد رمزی را با یک عامل نمایی کاهش دادند، دستاوردی که ریاضیدانان نزدیک به یک قرن به دنبال آن بودند. و آنها این کار را با مدرن کردن همان خط استدلالی انجام دادند که Erdős و Szekeres در سال 1935 مطرح کردند.

اپسیلون، اپسیلون

پس از مذاکرات در 16 مارس، حاضران شروع به تایید شایعات کردند. عکس‌های سخنرانی Sahasrabudhe از طریق تماس‌های تلفنی و پیام‌های خصوصی - حتی در یک پست مبهم اما پیشنهادی در وبلاگ گیل کالای ریاضیدان. Campos، Griffiths، Sahasrabudhe و Morris ادعا کردند که نشان داده اند که $لاتکس R(k) < 3.993^k$ است. آن شب، چهار نویسنده مقاله خود را به صورت آنلاین منتشر کردند، به ریاضیدانان اجازه می دهد تا اثبات جدید را خودشان ببینند.

گفت: "من فکر می کنم بسیاری از ما اساساً انتظار نداشتیم که چنین پیشرفتی را در طول زندگی خود ببینیم." ماتیا بوچیچ، ریاضیدان دانشگاه پرینستون و موسسه مطالعات پیشرفته. "من فکر می کنم این یک نتیجه کاملا شگفت انگیز است."

بسیاری از کارشناسان امیدوارند که با برداشته شدن مانع نمایی، پیشرفت بیشتری به سرعت در پی خواهد داشت. نویسندگان مقاله جدید به عمد روش خود را به حد نهایی رسانده اند تا از مبهم کردن استدلال خود با جزئیات غیر ضروری جلوگیری کنند. کامپوس گفت: "من بسیار علاقه مند هستم که این روش واقعاً تا کجا می تواند پیش رود، زیرا هیچ ایده ای ندارم."

«این یک مدرک کاملاً مبتکرانه، کاملاً شگفت‌انگیز و یک پیشرفت واقعی است. بنابراین اکنون من انتظار دارم که دریچه های سیل باز شوند. من متقاعد شده‌ام که طی سه سال آینده، بحث در مورد بهبودهای احتمالی خواهد بود. آیا می توانیم 3.993 را به 3.9 ارتقا دهیم؟ شاید به 3.4؟ و در مورد 3 چطور؟"

اثبات جدید در 56 صفحه ارائه می‌شود و هفته‌ها طول می‌کشد تا تمام جزئیات توسط انجمن ترکیب‌شناسی تأیید شود. اما همکاران خوشبین هستند. "این گروه از نویسندگان، آنها افراد بسیار جدی هستند. و آنها افرادی هستند که واقعاً در موارد بسیار فنی خوب هستند.» ویگدرسون گفت.

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