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

Пример графа двухъярусной кровати

Гипотеза о двухъярусной кровати — это утверждение в теории перколяции, разделе математики, изучающем поведение связанных кластеров в случайном графе. Гипотеза названа так, потому что структура участвующего в ней графа похожа на двухъярусную кровать. Впервые гипотеза была высказана Шаблон:Нп5 в 1985 году. В 2024 году российский и американский математик Игорь Пак с коллегами нашли контрпример — граф относительно несложной конструкции, содержащий более 7000 вершин.

Описание

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

В самой общей формулировке рёбра случайно и независимо сохраняются (остаются открытыми) с вероятностью $p_i$, и теряются (перекрываются) с вероятностью $1-p_i$. На обоих ярусах вероятности равны, вероятности для столбиков произвольные. При этом может случиться, что на верхнем ярусе ребро осталось, а на нижнем — перекрылось, и наоборот.

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

Гипотеза о двухъярусной кровати утверждает: когда у горизонтальных рёбер вероятность остаться $p$ одна и та же, а столбики всегда открыты, скорее между двумя вершинами из одного яруса сохранится путь, чем между теми же вершинами с разных ярусов. Формально:

Пусть $x$ и $y$ — вершины из одного яруса, $y^{\prime }$ — изоморфная копия $y$ из второго яруса. Тогда

$p\{x\leftrightsquigarrow y\}⩾p\{x\leftrightsquigarrow y^{\prime }\}$

Интерпретация и значимость

Когда между Шаблон:Math и Шаблон:Math есть неисчезающий столбик, то, очевидно, $x\leftrightsquigarrow y\iff x\leftrightsquigarrow y^{\prime }$. Таким образом, чтобы гипотеза имела смысл, нужно, чтобы столбики были не везде.

Гипотеза основывается на интуиции, что при исчезновении прямого пути от Шаблон:Math до Шаблон:Math найдётся резервный на другом ярусе. Потерять путь от Шаблон:Math до Шаблон:Math должно быть проще — меньше кандидатов в резервные пути. Аналогичные вопросы для случайных блужданий и модели Изинга были разрешены положительно. Первоначальной мотивировкой для этой гипотезы была более слабая гипотеза о том что при перколяции на бесконечной квадратной решётке вероятность вершины $(0,0)$ быть связанной с $(x,y)$ при $x,y⩾0$ больше, чем вероятность $(0,0)$ быть связанной с вершиной $(x+1,y)$.

Из-за интуитивности гипотезы двухъярусной кровати её доказательство было активной областью исследований в теории перколяции. Гипотеза была доказана для определённых типов графов, таких как колёса, полные графы, полные двудольные графы и графы с локальной симметрией. Гипотеза также была доказана в пределе $p\to 1$ для любого графа.

Авторы взяли более ранний контрпример Холлома для гиперграфов с разными вероятностями полностью потерять 3-гиперребро, оторвать от него «главную» вершину, и оторвать одну из двух второстепенных (столбики — обычные 2-рёбра), и сумели сымитировать каждое гиперребро большим количеством (более 2000) обычных равновероятных 2-рёбер. Полученный граф содержит 7222 вершины, Шаблон:Число ребра и всего три столбика, вероятность сохранения ребра $p=0,5$, при этом разница незначительна, около 10⁻⁶⁵⁰⁰.

Для данного графа из-за относительной простоты удалось вручную оценить разницу вероятностей. Меньшие графы и бо́льшие разницы не получается найти из-за случайной природы алгоритмов: даже если уровень значимости будет Шаблон:Math (шесть девяток), ни один журнал не примет этого результата.