اثبات ریاضی جدید یافت که بی‌نظمی در گراف‌های بزرگ‌تر ادامه دارد

منتشر‌شده در: مجلهquanta به تاریخ ۴ نوامبر ۲۰۲۰
لینک منبع: Disorder Persists in Larger Graphs, New Math Proof Finds

پس از بیش از ۷۰ سال ناسازگاری، یکی از سرسخت‌ترین اعداد در ریاضی در نهایت از بین رفت.

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

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

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

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

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

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

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

نسبت به تمام نتایج دیگری که از زمان مطالعه اعداد رمزی توسط پاول اردوس در دهه ۱۹۳۰ و ۱۹۴۰ به دست آمده‌اند، اثبات جدید در تعیین مقدار دقیق اعداد رمزی، مفیدتر است. کنلون، از موسسه فن‌آوری کالیفرنیا، و فربر، از دانشگاه کالیفرنیا، ایروین، یک «کران پایین» جدید برای اعداد رمزی چند رنگ یافتند که به صورت نمایی دقیق‌تر از بهترین تخمین قبلی است. نتیجه آن‌ها درک جدیدی از فعل و انفعال میان نظم و تصادفی بودن در گراف‌ها را برای ریاضی دانان فراهم می‌کند که از اهمیت اساسی در ریاضیات برخوردار است.

آکسنوویچ گفت: « این نتیجه فوق‌العاده‌ای است. من عاشق آن هستم.»

اتصالات رنگی

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

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

اعداد رمزی بسته به تعداد رنگ‌ها و اندازه دسته‌ای که به دنبالش هستید، متفاوت هستند. اما به طور کلی محاسبه دقیق آن‌ها دشوار است و ریاضی دانان تنها مقادیر دقیق برای تعداد کمی از موقعیت‌ها را می‌دانند. حتی برای دسته‌های کوچک با اندازه ۵ (و دو رنگ)، بهترین چیزی که آن‌ها می‌توانند بگویند این است که عدد رمزی بین ۴۳ تا ۴۸است.

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

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

آکسنوویچ گفت: « چیزهای زیادی هست که باید چک شوند.»

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

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

بهره‌برداری تصادفی بودن

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

در سال ۱۹۳۵، اردوس و جورج سزکرز اولین کران‌ها را ایجاد کردند. آن‌ها از یک اثبات کوتاه برای نشان دادن این که اعداد رمزی دو رنگ باید کوچک‌تر از حد بالایی ۴به توان t باشند استفاده کردند، که در آن t اندازه دسته تکی مورد نظر شما است. آن‌ها همچنین دریافتند که اعداد رمزی سه‌رنگ باید کوچک‌تر از ۲۷ به توان t باشند. یک دهه بعد، در سال ۱۹۴۷، اردوس اولین کران پایین این اعداد را محاسبه کرد: برای دو رنگ این عدد رادیکال ۲ به توان t و برای سه رنگ رادیکال ۳ به‌توان t راس است.

برای tهای بزرگ، تفاوت زیادی بین رادیکال ۲به توان t و ۴به توان t وجود خواهد داشت. این فاصله نشان‌دهنده درک نادقیق ریاضی دانان از اعداد رمزی است. اما شکل کران‌ها-روشی که اندازه گراف مورد نیاز بر حسب اندازه مجموعه مورد نظر بیان می‌شود-اشاره به چیزی دارد که ریاضی دانان می‌خواهند بدانند.

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

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

تصور کنید که یک گراف کامل با ۱۰راس و ۴۵ یال دارید. و تصور کنید می‌خواهید بدانید که آیا می‌توان سه رنگ را بدون ایجاد یک دسته تک‌رنگ با اندازه مشخص، مثلا پنج راس (متصل با ۱۰یال) به کار برد یا نه.

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

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

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

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

شکل ۵:

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

در طول ۷۰ سال بعد، ریاضی‌دانان در سال ۱۹۷۵ با پشتکار تدریجی توسط جوئل اسپنسر، کران پایین اردوس را تنها یک‌بار برای دو و سه رنگ بهبود بخشیدند. بسیاری از مردم روی این مساله کار کردند، اما هیچ یک از آن‌ها راهی بهتر از روش احتمالی برای محاسبه اعداد رمزی پیدا نکردند. کنلون گفت: «مشکل، تلاش برای شکست این [کران] ناشی از نمونه‌گیری تصادفی بوده‌است.»

و این کاری است که کنلون و فربر در نهایت در پاییز امسال انجام دادند.

ترتیب ادغامی

اثبات جدید کران پایین اعداد رمزی برای سه رنگ یا بیشتر را بهبود می‌دهد.

قبل از کار کنلون و فربر، کران پایین برای سه رنگ، رادیکال ۳ به توان t (یعنی حدود ۱.۷۳ به توان t) بود. آن‌ها این کران را به ۱.۸۳۴ به توان t رساندند. برای چهار رنگ، آن‌ها کران پایین را از ۲به توان t، تا ۲.۱۳۵به توان t بالا بردند. هر دو پیشرفت، جهش عظیمی هستند. با افزایش عدد پایه با توان t، کنلون و فربر ثابت کردند که گراف‌های سه و چهار رنگی بیشتری وجود دارند که فاقد دسته‌های تک‌رنگ لازم هستند. به عبارت دیگر، آن‌ها نشان دادند که بی‌نظمی می‌تواند در گراف‌های بزرگ‌تر از آنچه قبلا شناخته شده‌بود باقی بماند.

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

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

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

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

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

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

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

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

ویگدرسون گفت: « وضعیت دانش ما در زمان اردوس در دهه ۴۰ گیر افتاده‌است، بنابراین هر چیزی که رویکردی جدید به سوالات از این نوع ارائه دهد، هیجان‌انگیز است.»

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