Гипотеза Сидоренко

Гипотеза Сидоренко из теории графов касается оценки числа гомоморфизмов некоторого (произвольного, но фиксируемого) графа $H$ в произвольный граф $G$. Она утверждает, что при двудольном $H$ это число никогда не меньше, чем для случайного графа размера $|G|$ с той же ожидаемой плотностью рёбер, что и у $G$.

Гипотезу выдвинул Александр Сидоренко в 1986 году (частный случай был доказан ещё раньшеШаблон:Sfn). Она разными методами доказана для некоторых классов графов $H$, но далека от общего решения.

Формулировка

Пусть $h_H(G)$ означает число гомоморфизмов из графа $H$ в граф $G$. Пусть $t_H(G)=\frac{h_H(G)}{|V(G){|}^{|V(H)|}}$ означает "плотность" таких гомоморфизмов среди всех отображений вершин $H$ в вершины $G$. То есть, $t_H(G)$ это вероятность, что случайное отображение из множества $V(H)$ в множество $V(G)$ будет гомоморфизмом. Пусть также $K_2$ значает граф из двух вершин и одного ребра.

Шаблон:Рамка Гипотеза Сидоренко

Если $H$ – двудольный граф из $m$ рёбер, то для всякого графа $G$ верно, что $t_H(G)\ge t_{K_2}(G{)}^m$ Шаблон:Конец рамки

Обычно гипотезу рассматривают как множество утверждений для различных $H$ и говорят о её решении именно при том или ином $H$ и произвольном $G$.

Сидоренко изначально сформулировал утверждение в более общем виде, для меры на взвешенных континуальных графах (так называемых Шаблон:Iw).Шаблон:Sfn

Интерпретация через случайность

Для случайного графа в модели $G(n,p)$ ожидаемое число рёбер $𝔼t_{K_2}(G)=np$ и ожидаемое число вхождений графа $H$, равное $𝔼t_H(G)=n^{|V(H)|}{p}^{|E(H)|}$ в точности соответствуют равенству в гипотезе Сидоренко.

На первый взгляд, суждение о том, что некоторая величина (здесь – число вхождений $H$) "никогда не меньше, чем в среднем" может показаться парадоксальным, ведь это означало бы, что все значения величины равны среднему. Это было бы так, если бы в интерпретации через случайность рассматривалась модель случайных графов Эрдёша-Реньи $G(n,m)$ с фиксированным количеством рёбер, ведь оценка в гипотезе Сидоренко зависит от фактического числа рёбер в графе. А в модели $G(n,p)$ лишь ожидаемое число рёбер будет равным ему. то есть усреднение делается далеко не только по графам того же размера, что и заданный, и в том числе по графам, для которых гипотеза Сидоренко даёт очень разные оценки на число вхождений $H$.

Некоторые результаты

Гипотеза доказана для:

• путей;
• циклов чётной длины;
• деревьев;
• графов гиперкубовШаблон:Sfn;
• полных двудольных графов;
• для двудольных графов с размером одной из долей не более 4;
• для графов, в которых есть хотя бы одна вершина, смежная всем вершинам противоположной доли.

Многие результаты были объединены в единой концепции доказательства с помощью использования свойств энтропии из теории информации.Шаблон:Sfn

Также известны результаты о конструировании графов: для любого двудольного графа существует число $p$ такое, что если продублировать вершины одной из долей (вместе с исходящими рёбрами) $p$ раз, то получившийся граф будет удовлетворять гипотезе Сидоренко.

Тем не менее, гипотеза остаётся открытой для многих графов. Например, для $K_{5,5}\setminus C_{10}$ (полного двудольного графа без гамильтонова цикла).

Литература

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья