Гипотеза Сидоренко из теории графов касается оценки числа гомоморфизмов некоторого (произвольного, но фиксируемого) графа в произвольный граф . Она утверждает, что при двудольном это число никогда не меньше, чем для случайного графа размера с той же ожидаемой плотностью рёбер, что и у .
Гипотезу выдвинул Александр Сидоренко в 1986 годуСм. упоминание об этом в перед гипотезой 1 (частный случай был доказан ещё раньше). Она разными методами доказана для некоторых классов графов , но далека от общего решения.
Формулировка
Пусть означает число гомоморфизмов из графа в граф . Пусть означает "плотность" таких гомоморфизмов среди всех отображений вершин в вершины . То есть, это вероятность, что случайное отображение из множества в множество будет гомоморфизмом. Пусть также значает граф из двух вершин и одного ребра.
Гипотеза Сидоренко
Если – двудольный граф из рёбер, то для всякого графа верно, что
Обычно гипотезу рассматривают как множество утверждений для различных и говорят о её решении именно при том или ином и произвольном .
Сидоренко изначально сформулировал утверждение в более общем виде, для меры на взвешенных континуальных графах (так называемых графонах).
Интерпретация через случайность
Для случайного графа в модели ожидаемое число рёбер и ожидаемое число вхождений графа , равное в точности соответствуют равенству в гипотезе Сидоренко.
На первый взгляд, суждение о том, что некоторая величина (здесь – число вхождений ) "никогда не меньше, чем в среднем" может показаться парадоксальным, ведь это означало бы, что все значения величины равны среднему. Это было бы так, если бы в интерпретации через случайность рассматривалась модель случайных графов Эрдёша-Реньи с фиксированным количеством рёбер, ведь оценка в гипотезе Сидоренко зависит от фактического числа рёбер в графе. А в модели лишь ожидаемое число рёбер будет равным ему. то есть усреднение делается далеко не только по графам того же размера, что и заданный, и в том числе по графам, для которых гипотеза Сидоренко даёт очень разные оценки на число вхождений .
Некоторые результаты
Гипотеза доказана для: путей, см. утверждение в начале с. 674 при ; циклов чётной длины, пример 1; деревьев, следствие 1; графов гиперкубов; полных двудольных графов, см. теорему 5 и замечание после неё; для двудольных графов с размером одной из долей не более 4, см. теорему 1 и замечание после неё; для графов, в которых есть хотя бы одна вершина, смежная всем вершинам противоположной доли, теорема 1.2.
Многие результаты были объединены в единой концепции доказательства с помощью использования свойств энтропии из теории информации.Entropy and Sidorenko's conjecture — after Szegedy , обзор в блоге Гауэрса
Также известны результаты о конструировании графов: для любого двудольного графа существует число такое, что если продублировать вершины одной из долей (вместе с исходящими рёбрами) раз, то получившийся граф будет удовлетворять гипотезе Сидоренко, следствие 1.2.
Тем не менее, гипотеза остаётся открытой для многих графов. Например, для (полного двудольного графа без гамильтонова цикла).
Примечания
Литература
Категория:Теория графов