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

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

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

ФормулировкаПравить

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ПримечанияПравить

↑ См. упоминание об этом в Sidorenko, 1993 перед гипотезой 1
↑ Mulholland, Smith, 1959.
↑ Sidorenko, 1993.
↑ Mulholland, Smith, 1959, см. утверждение в начале с. 674 при $\text{[math]}$ $\text{[math]}$ $v=(1,\dots ,1)$
↑ Сидоренко, 1991, пример 1
↑ Сидоренко, 1991, следствие 1
↑ Hatami, 2010.
↑ Сидоренко, 1991, см. теорему 5 и замечание после неё
↑ Сидоренко, 1991, см. теорему 1 и замечание после неё
↑ Conlon, Sudakov, Fox, 2010, теорема 1.2
↑ Szegedy, 2015.
↑ Entropy and Sidorenko's conjecture — after Szegedy Архивная копия от 26 сентября 2020 на Wayback Machine, обзор в блоге Гауэрса
↑ 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.

[1] См. упоминание об этом в Sidorenko, 1993 перед гипотезой 1

[_1497b1a8b8e963cc-2] Mulholland, Smith, 1959.

[_ea41871fdd59911d-3] Sidorenko, 1993.

[4] Mulholland, Smith, 1959, см. утверждение в начале с. 674 при $\text{[math]}$ $\text{[math]}$ $v=(1,\dots ,1)$

[5] Сидоренко, 1991, пример 1

[6] Сидоренко, 1991, следствие 1

[_1ac1a692db2286c6-7] Hatami, 2010.

[8] Сидоренко, 1991, см. теорему 5 и замечание после неё

[9] Сидоренко, 1991, см. теорему 1 и замечание после неё

[10] Conlon, Sudakov, Fox, 2010, теорема 1.2

[_30bea5262774156c-11] Szegedy, 2015.

[12] Entropy and Sidorenko's conjecture — after Szegedy Архивная копия от 26 сентября 2020 на Wayback Machine, обзор в блоге Гауэрса

[13] Conlon, Lee, 2018, следствие 1.2

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]