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

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

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

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

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

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

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

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

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

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

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

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

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

• путей^[4];
• циклов чётной длины^[5];
• деревьев^[6];
• графов гиперкубов^[7];
• полных двудольных графов^[8];
• для двудольных графов с размером одной из долей не более 4^[9];
• для графов, в которых есть хотя бы одна вершина, смежная всем вершинам противоположной доли^[10].

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

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

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

Примечания

1. См. упоминание об этом в Sidorenko, 1993 перед гипотезой 1
2. Mulholland, Smith, 1959.
3. Sidorenko, 1993.
4. Mulholland, Smith, 1959, см. утверждение в начале с. 674 при ${\displaystyle v=(1,\dots ,1)}$
5. Сидоренко, 1991, пример 1
6. Сидоренко, 1991, следствие 1
7. Hatami, 2010.
8. Сидоренко, 1991, см. теорему 5 и замечание после неё
9. Сидоренко, 1991, см. теорему 1 и замечание после неё
10. Conlon, Sudakov, Fox, 2010, теорема 1.2
11. Szegedy, 2015.
12. Entropy and Sidorenko's conjecture — after Szegedy Архивная копия от 26 сентября 2020 на Wayback Machine, обзор в блоге Гауэрса
13. Conlon, Lee, 2018, следствие 1.2

Литература

• 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.