Гипотеза о двухъярусной кровати

Гипотеза о двухъярусной кровати (также называемая «гипотеза о двухъярусной кровати ») — это утверждение теории перколяции , раздела математики, изучающего поведение связанных кластеров в случайном графе . Гипотеза названа в честь ее аналогии со структурой двухъярусной кровати . Впервые это было высказано Кастелейном . ^[1]

Описание

Гипотеза имеет множество эквивалентных формулировок. ^[2] В самой общей формулировке он включает в себя два одинаковых графа , называемых «верхней койкой» и «нижней койкой». Эти графы изоморфны , то есть имеют одинаковую структуру. Дополнительные ребра, называемые «стойками», добавляются для соединения каждой вершины верхней полки с соответствующей вершиной нижней полки.

Каждому ребру графа присвоена вероятность. Ребра на верхней койке и соответствующие им ребра на нижней койке имеют одинаковую вероятность. Вероятности, присвоенные постам, могут быть произвольными.

Затем формируется случайный подграф двухъярусного графа путем независимого удаления каждого ребра на основе присвоенной вероятности.

Формулировка гипотезы

Гипотеза о двухъярусной кровати утверждает, что в полученном случайном подграфе вероятность того, что вершина $x$ на верхней койке соединен с какой-то вершиной $y$ на верхней койке больше или равна вероятности того, что $x$ подключен к $z$ , изоморфная копия $y$ на нижней койке.

Интерпретация и значение

Гипотеза предполагает, что две вершины графа с большей вероятностью останутся соединенными после случайного удаления некоторых ребер, если расстояние между вершинами графа меньше. Это интуитивно понятно, но доказать эту гипотезу непросто и это активная область исследований в теории перколяции. ^[3] Недавно эта проблема была решена для определенных типов графов, таких как колеса , ^[4] полные графики, ^[5] полные двудольные графы и графы с локальной симметрией. ^[6] Это было доказано и в пределе $p\to 1$ для любого графика ^[7]

Ссылки

^ ван ден Берг, Джейкоб; Кан, Джефф (2001). «Корреляционное неравенство для событий связи при просачивании» . Анналы вероятности . 29 (1): 123–126. дои : 10.1214/aop/1008956324 . JSTOR 2652916 . Проверено 17 декабря 2023 г.
^ Рудзински, Джеймс; Смит, Клиффорд (2016). «Эквивалентные формулировки гипотезы о двухъярусной кровати» . Журнал математики и статистики Северной Каролины . 2 : 23–28 . Проверено 17 декабря 2023 г.
^ Гриметт, Джеффри Р. (2022). «Избранные задачи теории вероятностей». Европейский журнал комбинаторики . arXiv : 2205.07318 .
^ Леандер, Мадлен (2009). «О гипотезе о двухъярусной кровати» (PDF) . Самостоятельные работы по математике . Проверено 17 декабря 2023 г.
^ ван Хинтум, Питер; Ламмерс, Пит (2018). «Гипотеза о двухъярусной кровати о полном графе». Европейский журнал комбинаторики . 76 : 175–177. arXiv : 1803.07647 . дои : 10.1016/j.ejc.2018.10.002 .
^ Рихтхаммер, Томас (2022). «Гипотеза о двухъярусной кровати для полных двудольных графов и связанных с ними классов графов». arXiv : 2204.12931 [ мат.PR ].
^ Хатчкрофт, Том; Кент, Александр; Низич-Николац, Петар (2023). «Гипотеза о двухъярусной кровати верна в пределе» (PDF) . Комбинаторика, теория вероятностей и вычисления . 32 (3). Издательство Кембриджского университета: 363–369. дои : 10.1017/S096354832200027X . S2CID 263889353 .

[1] ван ден Берг, Джейкоб; Кан, Джефф (2001). «Корреляционное неравенство для событий связи при просачивании» . Анналы вероятности . 29 (1): 123–126. дои : 10.1214/aop/1008956324 . JSTOR 2652916 . Проверено 17 декабря 2023 г.

[2] Рудзински, Джеймс; Смит, Клиффорд (2016). «Эквивалентные формулировки гипотезы о двухъярусной кровати» . Журнал математики и статистики Северной Каролины . 2 : 23–28 . Проверено 17 декабря 2023 г.

[3] Гриметт, Джеффри Р. (2022). «Избранные задачи теории вероятностей». Европейский журнал комбинаторики . arXiv : 2205.07318 .

[4] Леандер, Мадлен (2009). «О гипотезе о двухъярусной кровати» (PDF) . Самостоятельные работы по математике . Проверено 17 декабря 2023 г.

[5] ван Хинтум, Питер; Ламмерс, Пит (2018). «Гипотеза о двухъярусной кровати о полном графе». Европейский журнал комбинаторики . 76 : 175–177. arXiv : 1803.07647 . дои : 10.1016/j.ejc.2018.10.002 .

[6] Рихтхаммер, Томас (2022). «Гипотеза о двухъярусной кровати для полных двудольных графов и связанных с ними классов графов». arXiv : 2204.12931 [ мат.PR ].

[7] Хатчкрофт, Том; Кент, Александр; Низич-Николац, Петар (2023). «Гипотеза о двухъярусной кровати верна в пределе» (PDF) . Комбинаторика, теория вероятностей и вычисления . 32 (3). Издательство Кембриджского университета: 363–369. дои : 10.1017/S096354832200027X . S2CID 263889353 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]