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

Перейти к навигацииПерейти к поиску

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

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

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

Пусть означает число гомоморфизмов из графа в граф . Пусть означает "плотность" таких гомоморфизмов среди всех отображений вершин в вершины . То есть, это вероятность, что случайное отображение из множества в множество будет гомоморфизмом. Пусть также значает граф из двух вершин и одного ребра.

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

Если двудольный граф из рёбер, то для всякого графа верно, что

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

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

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

Для случайного графа в модели ожидаемое число рёбер и ожидаемое число вхождений графа , равное в точности соответствуют равенству в гипотезе Сидоренко.

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

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

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

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

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

Тем не менее, гипотеза остаётся открытой для многих графов. Например, для (полного двудольного графа без гамильтонова цикла).

Примечания

  1. См. упоминание об этом в Sidorenko, 1993 перед гипотезой 1
  2. Mulholland, Smith, 1959.
  3. Sidorenko, 1993.
  4. Mulholland, Smith, 1959, см. утверждение в начале с. 674 при
  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

Литература

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