Гипотеза о двухъярусной кровати — это утверждение в теории перколяции, разделе математики, изучающем поведение связанных кластеров в случайном графе. Гипотеза названа так, потому что структура участвующего в ней графа похожа на двухъярусную кровать. Впервые гипотеза была высказана в 1985 году. В 2024 году российский и американский математик Игорь Пак с коллегами нашли контрпример — граф относительно несложной конструкции, содержащий более 7000 вершин.
Описание У гипотезы есть много эквивалентных формулировок. Во всех формулировках строится так называемый граф двухъярусной кровати. Граф содержит два подграфа, называемых «верхним ярусом» и «нижним ярусом». Эти графы изоморфны, то есть имеют одинаковую структуру. Некоторые вершины верхнего яруса соединяется с соответствующей вершиной нижнего яруса дополнительным ребром, которые называются «столбиками».
В самой общей формулировке рёбра случайно и независимо сохраняются (остаются открытыми) с вероятностью , и теряются (перекрываются) с вероятностью . На обоих ярусах вероятности равны, вероятности для столбиков произвольные. При этом может случиться, что на верхнем ярусе ребро осталось, а на нижнем — перекрылось, и наоборот.
Формулировка гипотезы Гипотеза о двухъярусной кровати утверждает: когда у горизонтальных рёбер вероятность остаться одна и та же, а столбики всегда открыты, скорее между двумя вершинами из одного яруса сохранится путь, чем между теми же вершинами с разных ярусов. Формально:
Пусть и — вершины из одного яруса, — изоморфная копия из второго яруса. Тогда
Интерпретация и значимость Когда между и есть неисчезающий столбик, то, очевидно, . Таким образом, чтобы гипотеза имела смысл, нужно, чтобы столбики были не везде.
Гипотеза основывается на интуиции, что при исчезновении прямого пути от до найдётся резервный на другом ярусе. Потерять путь от до должно быть проще — меньше кандидатов в резервные пути. Аналогичные вопросы для случайных блужданий и модели Изинга были разрешены положительно. Первоначальной мотивировкой для этой гипотезы была более слабая гипотеза о том что при перколяции на бесконечной квадратной решётке вероятность вершины быть связанной с при больше, чем вероятность быть связанной с вершиной .
Из-за интуитивности гипотезы двухъярусной кровати её доказательство было активной областью исследований в теории перколяции. Гипотеза была доказана для определённых типов графов, таких как колёса, полные графы, полные двудольные графы и графы с локальной симметрией. Гипотеза также была доказана в пределе для любого графа.
Авторы взяли более ранний контрпример Холлома для гиперграфов с разными вероятностями полностью потерять 3-гиперребро, оторвать от него «главную» вершину, и оторвать одну из двух второстепенных (столбики — обычные 2-рёбра), и сумели сымитировать каждое гиперребро большим количеством (более 2000) обычных равновероятных 2-рёбер. Полученный граф содержит 7222 вершины, ребра и всего три столбика, вероятность сохранения ребра , при этом разница незначительна, около 10−6500.
Для данного графа из-за относительной простоты удалось вручную оценить разницу вероятностей. Меньшие графы и бо́льшие разницы не получается найти из-за случайной природы алгоритмов: даже если уровень значимости будет (шесть девяток), ни один журнал не примет этого результата.
Ссылки
Категория:Случайные графы