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

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

توضیح

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

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

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

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

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

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

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

References

↑ Kahn, J.; van den Berg, J. (2001-02-01). "A correlation inequality for connection events in percolation". The Annals of Probability. 29 (1). doi:10.1214/aop/1008956324. ISSN 0091-1798.
↑ ^۲٫۰ ^۲٫۱ Gladkov, Nikita; Pak, Igor (2024-02-01). "Positive dependence for colored percolation". Physical Review E. 109 (2). doi:10.1103/physreve.109.l022101. ISSN 2470-0045.
↑ HÄGGSTRÖM, OLLE (1998-12-01). "On a Conjecture of Bollobás and Brightwell Concerning Random Walks on Product Graphs". Combinatorics, Probability and Computing. 7 (4): 397–401. doi:10.1017/s0963548398003605. ISSN 0963-5483.
↑ Häggström, Olle (2016-07-01). "Markov random fields and percolation on general graphs". Advances in Applied Probability. 32 (1): 39–66. doi:10.1239/aap/1013540021. ISSN 0001-8678.
↑ Sonesson, Anders; Henriksson, Ann-Sofie (2013-06-10). "Högre utbildnings första temanummer: Självständiga arbeten". Högre utbildning. 3 (2): 83–86. doi:10.23865/hu.v3.807. ISSN 2000-7558.
↑ van Hintum, Peter; Lammers, Piet (2019-02-01). "The bunkbed conjecture on the complete graph". European Journal of Combinatorics. 76: 175–177. doi:10.1016/j.ejc.2018.10.002. ISSN 0195-6698.
↑ Zelinka, Bohdan (1983). "Homomorphisms of infinite bipartite graphs onto complete bipartite graphs". Czechoslovak Mathematical Journal. 33 (4): 545–547. doi:10.21136/cmj.1983.101911. ISSN 0011-4642.
↑ ^۸٫۰ ^۸٫۱ Hollom, Lawrence (2024-01-01). "A new proof of the bunkbed conjecture in the p↑1 limit". Discrete Mathematics. 347 (1): 113711. doi:10.1016/j.disc.2023.113711. ISSN 0012-365X.

[1] Kahn, J.; van den Berg, J. (2001-02-01). "A correlation inequality for connection events in percolation". The Annals of Probability. 29 (1). doi:10.1214/aop/1008956324. ISSN 0091-1798.

[:0-2] ۲٫۰ ^۲٫۱ Gladkov, Nikita; Pak, Igor (2024-02-01). "Positive dependence for colored percolation". Physical Review E. 109 (2). doi:10.1103/physreve.109.l022101. ISSN 2470-0045.

[3] HÄGGSTRÖM, OLLE (1998-12-01). "On a Conjecture of Bollobás and Brightwell Concerning Random Walks on Product Graphs". Combinatorics, Probability and Computing. 7 (4): 397–401. doi:10.1017/s0963548398003605. ISSN 0963-5483.

[4] Häggström, Olle (2016-07-01). "Markov random fields and percolation on general graphs". Advances in Applied Probability. 32 (1): 39–66. doi:10.1239/aap/1013540021. ISSN 0001-8678.

[5] Sonesson, Anders; Henriksson, Ann-Sofie (2013-06-10). "Högre utbildnings första temanummer: Självständiga arbeten". Högre utbildning. 3 (2): 83–86. doi:10.23865/hu.v3.807. ISSN 2000-7558.

[6] van Hintum, Peter; Lammers, Piet (2019-02-01). "The bunkbed conjecture on the complete graph". European Journal of Combinatorics. 76: 175–177. doi:10.1016/j.ejc.2018.10.002. ISSN 0195-6698.

[7] Zelinka, Bohdan (1983). "Homomorphisms of infinite bipartite graphs onto complete bipartite graphs". Czechoslovak Mathematical Journal. 33 (4): 545–547. doi:10.21136/cmj.1983.101911. ISSN 0011-4642.

[:1-8] ۸٫۰ ^۸٫۱ Hollom, Lawrence (2024-01-01). "A new proof of the bunkbed conjecture in the p↑1 limit". Discrete Mathematics. 347 (1): 113711. doi:10.1016/j.disc.2023.113711. ISSN 0012-365X.

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]

[۷]

[۸]