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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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