حدس تخت دوطبقه

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

مثالی از یک گراف تخت دوطبقه

توضیح

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

ابتدا به هر یال در هر گراف یک احتمال اختصاص داده می‌شود، به گونه‌ای که یال‌های تخت بالایی و یال‌های متناظرشان در تخت پایینی احتمال یکسانی دارند. احتمال‌های اختصاص‌یافته به یال‌های پایه می تواند دلخواه باشد. سپس، با حذف مستقل هر یال براساس احتمال اختصاص‌داده‌شده، یک زیر-گراف تصادفی از گراف تخت دو طبقه تشکیل می‌شود. مثلاً می‌توان فرض کرد که تمام یال‌ها با احتمال یکسانی، $0<p<1$ حذف می‌شوند.       

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

اهمیت حدس تخت دوطبقه

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

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

در اکتبر ۲۰۲۴، مثال نقضی برای این حدس پیشنهاد شده است که یک گراف مسطح با ۷۲۲۲ رأس دارد که با الهام از ابرگراف پیشنهادی در مثال نقض تعمیم یافته این حدس در پژوهش هالوم مطرح شده است.