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

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

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

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

Пусть $h_{H}(G)$ означает число гомоморфизмов из графа $H$ в граф $G$. В частности, $h_{K_{2}}(G)$ пусть означает число рёбер в $G$. Пусть также $t_{H}(G)={\frac {h_{H}(G)}{|G|^{|V(H)|}}}$ означает "плотность" таких гомоморфизмов среди всех отображений вершин $H$ в вершины $G$.

Гипотеза Сидоренко Если $H$ – двудольный граф из $m$ рёбер, то для всякого графа $G$ верно, что $t_{H}(G)\geq t_{K_{2}}(G)^{m}$

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

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

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

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

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

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

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

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

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

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

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

Литература

• H. P. Mulholland, C. A. B. Smith. An Inequality Arising in Genetical Theory (англ.) // The American Mathematical Monthly. — 1959. — Vol. 66, iss. 8. — P. 673–683.

• A. Sidorenko. A correlation inequality for bipartite graphs (англ.) // Graphs and Combinatorics. — 1993. — Vol. 9. — P. 201–204.

• А. Ф. Сидоренко. Неравенства для функционалов, порождаемых двудольными графами (рус.) // Дискретная математика. — 1991. — Т. 3, вып. 3. — С. 50–65.

• H. Hatami. Graph norms and Sidorenko’s conjecture (англ.) // Israel Journal of Mathematics. — 2010. — Vol. 175. — P. 125–150. — arXiv:0806.0047.

• D. Conlon, J. Fox, B. Sudakov. An Approximate Version of Sidorenko’s Conjecture (англ.) // Geometric and Functional Analysis. — 2010. — Vol. 20. — P. 1354–1366. — arXiv:1004.4236.

• D. Conlon, J. Lee. Sidorenko's conjecture for blow-ups (англ.). — 2018. — arXiv:1809.01259.

• B. Szegedy. An information theoretic approach to Sidorenko's conjecture (англ.). — 2015. — arXiv:1406.6738v3.