مقدمه
در سال ۲۰۰۴، دو ریاضیدان نوع قدرتمندی از ساندویچ را فرضیهگذاری کردند.
آنها در حال مطالعه گرافها بودند؛ مجموعههایی از نقاط (که رأس نامیده میشوند) و خطوط (که یال نامیده میشوند). گرافها ممکن است نماینده هر چیزی باشند، از گروههای اجتماعی گرفته تا اینترنت و نورونهای مغز. ریاضیدانان امیدوار بودند با قرار دادن یکی از انواع گراف — نوعی که در ریاضیات و علوم کامپیوتر فراگیر است اما تحلیل آن دشوار است — به شکلی ریاضیاتی دقیق بین دو گراف سادهتر، ویژگیهای آن را درک کنند.
اگر پژوهشگران میتوانستند وجود چنین ساندویچی را اثبات کنند، نه تنها نشان میدادند که گراف میانی دارای یک ویژگی مورد علاقه است، بلکه ثابت میکردند که تمام ویژگیهای مهم دیگر را نیز داراست. با این کار، آنها همچنین نشان میدادند که دو فرآیند تصادفی بسیار متفاوت که ریاضیدانان دوست دارند مطالعه کنند، به شیوهای عمیقتر و زیباتر از آنچه تصور میکردند، به هم مرتبط هستند.
«این مفهوم بسیار زیباست»، گفت پو گائو (در تب جدید باز میشود)، ریاضیدان دانشگاه واترلو در کانادا که روی این مسئله کار کرده است. «آنچه مرا بیش از همه جذب میکند، در واقع زیبایی آن است.»
در دو دهه گذشته، ریاضیدانان در زمینه «حدس ساندویچ» پیشرفتهایی داشتند؛ حدسی که میگوید تا زمانی که گراف مورد علاقه شما به اندازه کافی بزرگ باشد، همیشه میتوانید ساندویچ مورد نیاز را ایجاد کنید. اما هیچکس نتوانست آن را به طور کامل اثبات کند. سپس در سال ۲۰۲۵، سه ریاضیدان راهی یافتند تا تکنیکهای حوزه خود را تا حد ممکن به چالش بکشند و این جستجو را به پایان رساندند.
گرافهای با طعمهای مختلف
در اواخر دهه ۱۹۵۰، ادگار گیلبرت، ریاضیدان آمریکایی، در آزمایشگاه بل در حال مطالعه شبکههای تلفنی بود. برای درک بهتر این شبکهها، او مدلی ساده از یک گراف «تصادفی» ارائه داد که در آن رأسها به صورت تصادفی به سایر رأسها متصل میشوند. (ریاضیدانان پل اردوش و آلفرد رینی به طور مستقل و تقریباً در همان زمان مدل مشابهی را ارائه کردند.)
برای ساخت یکی از این گرافها، با مجموعهای از رأسها شروع کنید. هر جفت رأس دلخواه را در مجموعه انتخاب کنید، سپس یک سکه (احتمالاً سوگیریدار) را پرتاب کنید. اگر سر آمد، بین آنها یک یال رسم کنید؛ در غیر این صورت، به سراغ بعدی بروید. این مرحله را برای هر جفت رأس در گراف تکرار کنید.
این گرافها که به عنوان گرافهای دوجملهای تصادفی شناخته میشوند، راهی مفید — اگرچه ناکامل — برای نمایش شبکهها ارائه دادند. آنها نسبتاً آسان بودند و ریاضیدانان چیزهای جالب زیادی درباره آنها اثبات کردند. به عنوان مثال، تا دهه ۱۹۷۰، آنها کشف کردند که تحت چه شرایطی یک گراف دوجملهای تصادفی شامل یک دور همیلتونی خواهد بود؛ مسیری که از هر رأس دقیقاً یک بار بازدید میکند.
اما این تنها نوع گراف تصادفی نیست. ریاضیدانان همچنین درباره گرافهای تصادفی کنجکاو بودند که در آنها تمام رأسها تعداد یالهای یکسانی دارند. این گرافهای موسوم به منظم، درک بهتری از ساختار تصادفی نسبت به گرافهای دوجملهای ارائه میدهند. و اغلب در مدلسازی شبکههای دنیای واقعی بسیار دقیقتر هستند.
اما چون یالهای آنها الگوهای مقیدتر و وابستهتری تشکیل میدهند، تحلیل آنها نیز بسیار دشوارتر است. پس از پاسخ به سوال درباره دورهای همیلتونی برای گرافهای دوجملهای، ۲۰ سال کار اضافی طول کشید تا ریاضیدانان بتوانند همین کار را برای گرافهای منظم انجام دهند.
اما اگر بتوانید گرافهای منظم تصادفی را با گرافهای دوجملهای تصادفی تقریب بزنید چه؟ اگر این امکانپذیر باشد، ریاضیدانان میتوانند بسیاری از ویژگیهای اثباتناپذیر یک گراف منظم را از گراف دوجملهای متناظر — رایگان — به دست آورند.
در اوایل دهه ۲۰۰۰، جونگ هان کیم (در تب جدید باز میشود)، که آن زمان در مرکز تحقیقات مایکروسافت بود، و وان ها وو (در تب جدید باز میشود)، که آن زمان در دانشگاه کالیفرنیا، سن دیگو بود، نشان دادند چگونه میتوان این کار را با ساختن یک ساندویچ گرافی (در تب جدید باز میشود) انجام داد.
ایده، به زبانی ساده، پیدا کردن یک دستور واحد — یک فرآیند تصادفی — برای ساخت همزمان یک گراف دوجملهای و یک گراف منظم بود. نه تنها این دستور باید نوع صحیح گرافها را تولید کند، بلکه این گرافها باید به شکل درست نیز با هم جور شوند. اگر بتوانید این کار را انجام دهید، هنگامی که نتایجی را درباره گراف دوجملهای که تحلیلش نسبتاً آسان است اثبات میکنید، آن نتایج برای گراف منظم نیز معتبر خواهند بود.
در تشبیه ساندویچ، مانند این است که چیزهایی را درباره یکی از برشهای نان اثبات کنید و بدانید که آن نتایج برای پنیر وسط نیز صادق خواهد بود.
اما دقیقاً چگونه این گرافها باید با هم جور شوند؟ شما باید دستوری تهیه کنید که پنیر را به صورت جداگانه روی هر برش نان لایهلایه کند.
اولاً، به دستوری نیاز دارید که یک گراف منظم به شما بدهد که شامل یک گراف دوجملهای باشد. یعنی یالهای گراف دوجملهای زیرمجموعهای از یالهای تشکیلدهنده گراف منظم باشند. اگر آن گراف دوجملهای هر ویژگیای داشته باشد که احتمال ظهور آن هنگام افزودن یالها بیشتر میشود، گراف منظم شما نیز آن ویژگی را خواهد داشت. این نیمه پایینی ساندویچ کیم و وو است.
به طور مشابه، به دستوری نیاز دارید که یک گراف منظم به شما بدهد که در داخل یک گراف دوجملهای قرار گرفته باشد. اگر این گراف دوجملهای بزرگتر ویژگیهایی داشته باشد که احتمال ظهور آنها هنگام حذف یالها بیشتر میشود، گراف منظم شما نیز باید این ویژگیها را داشته باشد. این نیمه بالایی ساندویچ شماست.
کیم و وو حدس زدند که تا زمانی که گراف منظم شما تعداد معقولی یال داشته باشد، تقریباً همیشه میتوانید این ساندویچ را بسازید (در تب جدید باز میشود).
با توجه به اینکه دستور شما باید گرافهای دوجملهای و منظم را همزمان ایجاد کند، حتی اگر معمولاً با استفاده از فرآیندهای تصادفی کاملاً متفاوت ساخته میشوند، این کار آسان نیست. در طول سالها، ریاضیدانان اثبات کردند که نیمه پایینی ساندویچ کیم و وو وجود دارد و نیمه بالایی را در برخی موارد اثبات کردند. «این دنبالهای از ایدهها بود که بر پایه یکدیگر بنا شده بودند»، گفت مایکل کریوویلویچ (در تب جدید باز میشود)، ریاضیدان دانشگاه تلآویو که روی این مسئله کار کرده است. هر مرحله «نیازمند تکنیک بسیار خوبی است. نیازمند نبوغ است.»
اما ساندویچ هنوز کامل نشده بود.
دستور پخت کامل
اثبات حدس نیازمند راهی برای اتصال نزدیک نان و پنیر هر ساندویچی بود.
به طور خاص، لایهها باید به صورت همزمان ساخته میشدند تا تضمین شود که همیشه با هم جور خواهند شد.
در سال ۲۰۲۳، سه ریاضیدان — ریچارد مونتگومری (در تب جدید باز میشود) از دانشگاه وارویک؛ ناتالی بگه (در تب جدید باز میشود)، پژوهشگر پسادکتری او در آن زمان؛ و دنیل ایلکوویچ (در تب جدید باز میشود)، دانشجوی دکتری او — شروع به فکر کردن درباره روشهایی برای ساخت گراف منظم تصادفی و گراف دوجملهای تصادفی یالبهیال کردند، به گونهای که در هر مرحله تضمین شود گراف منظم شامل گراف دوجملهای است. این کمی شبیه ساخت ساندویچ از تکههای ریز پنیر رندهشده است که یکییکی روی نان قرار میگیرند، به جای اینکه یک برش کامل را یکجا بگذارید.
برای دنبال کردن دستور آنها (که به گفته ریاضیدانان، به شدت از نتیجهای در سال ۲۰۱۹ (در تب جدید باز میشود) توسط گائو و دو همکارش اقتباس شده است)، با دو مجموعه از رأسها بدون یال شروع کنید. یکی از مجموعهها در نهایت به گراف دوجملهای شما تبدیل میشود و دیگری به گراف منظم.
اکنون گراف دوجملهای خود را به روش معمول بسازید. یعنی یک جفت رأس را انتخاب کنید و یک سکه وزندار را پرتاب کنید. اگر سکه سر آمد، یک یال به گراف دوجملهای اضافه کنید. یکی نیز به گراف منظم اضافه کنید.
اگر سکه پشت آمد، یال را در گراف دوجملهای اضافه نکنید. اما ممکن است لازم باشد یا نباشد که یک یال به گراف منظم اضافه کنید. در نهایت، یک گراف منظم با این ویژگی تعریف میشود که هر رأس تعداد یالهای یکسانی دارد. شما باید مطمئن شوید که تمام یالهای مورد نیاز وجود دارند.
بنابراین وقتی سکه شما پشت میآید، گراف دوجملهای را نادیده بگیرید، اما یک سکه دوم وزندار را پرتاب کنید تا تصمیم بگیرید آیا یالی به گراف منظم اضافه شود یا خیر. وزن این سکه دوم با پیشرفت در ساخت گراف تغییر خواهد کرد. بگه، ایلکوویچ و مونتگومری راه هوشمندانهای برای تخمین وزن سکه هنگام افزودن یالهای بیشتر به گرافها پیدا کردند تا تضمین شود که یک گراف واقعاً منظم به دست میآورید. علاوه بر این، شما همچنین تضمین میکنید که گراف منظم شامل گراف دوجملهای است و بخش پایینی ساندویچ را به شما میدهد.
برای ساخت بخش بالایی، ریاضیدانان سپس کل فرآیند خود را معکوس کردند. آنها با دو گرافی شروع کردند که تمام یالهای ممکن را شامل میشدند. سپس یالها را یکییکی حذف کردند تا به گراف منظم و گراف دوجملهایای رسیدند که شامل آن بود.
آنها ساندویچ خود را تمام کرده بودند. «حدس به نوعی بسیار طبیعی است. نبودِ اثبات آن تا حالا کمی آزاردهنده بود»، کریوویلویچ گفت. هنگامی که نتیجه جدید این سه نفر را دید، احساس «نوعی آرامش» کرد.
عوارض رایگان
با حل حدس ساندویچ، ریاضیدانان دیگر نیازی ندارند هر ویژگی گرافهای منظم تصادفی را از صفر اثبات کنند. آنها اکنون میتوانند از ادبیات گستردهای که درباره گرافهای دوجملهای تصادفی نوشته شده است بهره ببرند و به طور خودکار انواع ویژگیها را به دست آورند.
این بدان معناست که آنها میتوانند دهها نتیجه درباره گرافهای منظم را در یک اثبات یکپارچه و روان بازنویسی کنند. و نتایج جدیدی در حال حاضر شروع به ظاهر شدن کردهاند (در تب جدید باز میشود).
علاوه بر این، اثبات این «متا-قضیه»، همانطور که گیل کالایی (در تب جدید باز میشود) از دانشگاه عبری اورشلیم بیان کرد، مجموعهای از روشها را ارائه میدهد که «جعبهابزار ما را غنیتر میکند» و «دندانهای فنی ما را تیزتر میکند». آن روشها ممکن است به ریاضیدانان اجازه دهند حتی بیشتر از آنچه در ابتدا قصد داشتند، درباره ساختار شبکهها درک کنند.
در همین حال، پژوهشگران امیدوارند ساندویچهای پیچیدهتری بسازند، پر از لایههای متناوب گرافهای دوجملهای و منظم، یا با مواد اولیه دیگر. با این کار، آنها همچنان به کاوش در چگونگی شباهت فرآیندهای تصادفی ظاهراً متفاوت — یکی بسیار مقید و دیگری نه — ادامه میدهند. «آن نوع ارتباط عمیق بین این دو»، بگه گفت، «تقریباً بیش از حد خوب به نظر میرسد تا واقعی باشد.» و با این حال، واقعی است.