Русская Википедия:Гипотеза Сидоренко
Гипотеза Сидоренко из теории графов касается оценки числа гомоморфизмов некоторого (произвольного, но фиксируемого) графа <math>H</math> в произвольный граф <math>G</math>. Она утверждает, что при двудольном <math>H</math> это число никогда не меньше, чем для случайного графа размера <math>|G|</math> с той же ожидаемой плотностью рёбер, что и у <math>G</math>.
Гипотезу выдвинул Александр Сидоренко в 1986 году[1] (частный случай был доказан ещё раньшеШаблон:Sfn). Она разными методами доказана для некоторых классов графов <math>H</math>, но далека от общего решения.
Формулировка
Пусть <math>h_H(G)</math> означает число гомоморфизмов из графа <math>H</math> в граф <math>G</math>. В частности, <math>h_{K_2}(G)</math> пусть означает число рёбер в <math>G</math>. Пусть также <math>t_H(G) = \frac{h_H(G)}{|G|^{|V(H)|}}</math> означает "плотность" таких гомоморфизмов среди всех отображений вершин <math>H</math> в вершины <math>G</math>.
Шаблон:Рамка Гипотеза Сидоренко
Если <math>H</math> – двудольный граф из <math>m</math> рёбер, то для всякого графа <math>G</math> верно, что <math>t_H(G) \ge t_{K_2}(G)^m</math> Шаблон:Конец рамки
Обычно гипотезу рассматривают как множество утверждений для различных <math>H</math> и говорят о её решении именно при том или ином <math>H</math> и произвольном <math>G</math>.
Сидоренко изначально сформулировал утверждение в более общем виде, для меры на взвешенных континуальных графах (так называемых Шаблон:Iw).Шаблон:Sfn
Интерпретация через случайность
Для случайного графа в модели <math>G(n, p)</math> ожидаемое число рёбер <math>{\mathbb E}\ {t_{K_2}(G)} = np</math> и ожидаемое число вхождений графа <math>H</math>, равное <math>{\mathbb E}\ t_H(G) = n^{|V(H)|} p^{|E(H)|}</math> в точности соответствуют равенству в гипотезе Сидоренко.
На первый взгляд, суждение о том, что некоторая величина (здесь – число вхождений <math>H</math>) "никогда не меньше, чем в среднем" может показаться парадоксальным, ведь это означало бы, что все значения величины равны среднему. Это было бы так, если бы в интерпретации через случайность рассматривалась модель случайных графов Эрдёша-Реньи <math>G(n, m)</math> с фиксированным количеством рёбер, ведь оценка в гипотезе Сидоренко зависит от фактического числа рёбер в графе. А в модели <math>G(n, p)</math> лишь ожидаемое число рёбер будет равным ему. то есть усреднение делается далеко не только по графам того же размера, что и заданный, и в том числе по графам, для которых гипотеза Сидоренко даёт очень разные оценки на число вхождений <math>H</math>.
Некоторые результаты
Гипотеза доказана для:
- путей[2];
- циклов чётной длины[3];
- деревьев[4];
- графов гиперкубовШаблон:Sfn;
- полных двудольных графов[5];
- для двудольных графов с размером одной из долей не более 4[6];
- для графов, в которых есть хотя бы одна вершина, смежная всем вершинам противоположной доли[7].
Многие результаты были объединены в единой концепции доказательства с помощью использования свойств энтропии из теории информации.Шаблон:Sfn[8]
Также известны результаты о конструировании графов: для любого двудольного графа существует число <math>p</math> такое, что если продублировать вершины одной из долей (вместе с исходящими рёбрами) <math>p</math> раз, то получившийся граф будет удовлетворять гипотезе Сидоренко[9].
Тем не менее, гипотеза остаётся открытой для многих графов. Например, для <math>K_{5,5} \setminus C_{10}</math> (полного двудольного графа без гамильтонова цикла).
Примечания
Литература
- ↑ См. упоминание об этом в Шаблон:Sfn0 перед гипотезой 1
- ↑ Шаблон:Sfn0, см. утверждение в начале с. 674 при <math>v=(1,\dots,1)</math>
- ↑ Шаблон:Sfn0, пример 1
- ↑ Шаблон:Sfn0, следствие 1
- ↑ Шаблон:Sfn0, см. теорему 5 и замечание после неё
- ↑ Шаблон:Sfn0, см. теорему 1 и замечание после неё
- ↑ Шаблон:Sfn0, теорема 1.2
- ↑ Entropy and Sidorenko's conjecture — after Szegedy Шаблон:Wayback, обзор в блоге Гауэрса
- ↑ Шаблон:Sfn0, следствие 1.2
