Гипотеза Сидоренко - Sidorenkos conjecture - Wikipedia

Гипотеза Сидоренко это важный догадка в области теория графов, поставленный Александр Сидоренко в 1986 году. Грубо говоря, гипотеза утверждает, что для любого двудольный граф ${ displaystyle H}$ и график ${ displaystyle G}$ на ${ displaystyle n}$ вершины со средней степенью ${ displaystyle pn}$, есть как минимум ${ Displaystyle p ^ {| E (H) |} n ^ {| V (H) |}}$ помеченные копии ${ displaystyle H}$ в ${ displaystyle G}$, с точностью до небольшой погрешности. Формально это дает интуитивное неравенство относительно гомоморфизм графов плотности в графоны. Предполагаемое неравенство можно интерпретировать как утверждение, что плотность копий ${ displaystyle H}$ в графе асимптотически минимизируется случайным графом, как и следовало ожидать ${ displaystyle p ^ {| E (H) |}}$ доля возможных подграфов, которые должны быть копией ${ displaystyle H}$ если каждое ребро существует с вероятностью ${ displaystyle p}$.

Заявление

Позволять ${ displaystyle H}$ быть графом. потом ${ displaystyle H}$ говорят, что имеет Сидоренко собственность если для всех графоны ${ displaystyle W}$, неравенство

${ Displaystyle т (ЧАС, W) geq t (K_ {2}, W) ^ {| E (H) |}}$

верно, где ${ displaystyle t (H, W)}$ это плотность гомоморфизма из ${ displaystyle H}$ в ${ displaystyle W}$.

Гипотеза Сидоренко (1986) утверждает, что каждый двудольный граф обладает свойством Сидоренко.^[1]

Если ${ displaystyle W}$ это график ${ displaystyle G}$, это означает, что вероятность равномерного случайного отображения из ${ Displaystyle V (H)}$ к ${ Displaystyle V (G)}$ гомоморфизм - это по крайней мере произведение по каждому ребру в ${ displaystyle H}$ вероятности того, что это ребро будет отображено на ребро в ${ displaystyle G}$. Это примерно означает, что случайно выбранный граф с фиксированным числом вершин и средней степенью имеет минимальное количество помеченных копий ${ displaystyle H}$. Это не удивительная гипотеза, потому что правая часть неравенства - это вероятность того, что отображение является гомоморфизмом, если каждое отображение ребер является независимым. Таким образом, следует ожидать, что обе стороны будут по крайней мере одного порядка. Естественное расширение на графоны вытекало бы из того факта, что каждый графон является предельная точка некоторой последовательности графов.

Требование, чтобы ${ displaystyle H}$ является двухсторонним иметь имущество Сидоренко необходимо - если ${ displaystyle W}$ двудольный граф, то ${ displaystyle t (K_ {3}, W) = 0}$ поскольку ${ displaystyle W}$ без треугольников. Но ${ displaystyle t (K_ {2}, W)}$ в два раза больше количества ребер в ${ displaystyle W}$, поэтому собственность Сидоренко не сохраняется на ${ displaystyle K_ {3}}$. Аналогичное рассуждение показывает, что ни один граф с нечетным циклом не обладает свойством Сидоренко. Так как граф является двудольным тогда и только тогда, когда он не имеет нечетных циклов, это означает, что единственные возможные графы, которые могут обладать свойством Сидоренко, являются двудольными графами.

Эквивалентная формулировка

Свойство Сидоренко эквивалентно следующей переформулировке:

Для всех графиков ${ displaystyle G}$, если ${ displaystyle G}$ имеет ${ displaystyle n}$ вершины и средняя степень ${ displaystyle pn}$, тогда ${ Displaystyle т (H, G) geq p ^ {| E (H) |}}$.

Это эквивалентно, потому что количество гомоморфизмов из ${ displaystyle K_ {2}}$ к ${ displaystyle G}$ в два раза больше количества ребер в ${ displaystyle G}$, а неравенство нужно проверять только тогда, когда ${ displaystyle W}$ это график, как упоминалось ранее.

В этой формулировке, поскольку количество неинъективных гомоморфизмов из ${ displaystyle H}$ к ${ displaystyle G}$ самое большее постоянное время ${ Displaystyle п ^ {| V (H) | -1}}$, Собственность Сидоренко означала бы наличие как минимум ${ displaystyle (p ^ {| E (H) |} -o (1)) n ^ {| V (H) |}}$ помеченные копии ${ displaystyle H}$ в ${ displaystyle G}$.

Примеры

Как отмечалось ранее, для доказательства свойства Сидоренко достаточно продемонстрировать неравенство для всех графов ${ displaystyle G}$. В этом разделе ${ displaystyle G}$ это график на ${ displaystyle n}$ вершины со средней степенью ${ displaystyle pn}$. Количество ${ displaystyle operatorname {hom} (H, G)}$ относится к числу гомоморфизмов из ${ displaystyle H}$ к ${ displaystyle G}$. Это количество такое же, как ${ Displaystyle п ^ {| V (H) |} t (H, G)}$.

Элементарные доказательства свойства Сидоренко для некоторых графов следуют из Неравенство Коши – Шварца или же Неравенство Гёльдера. Остальные можно сделать с помощью спектральная теория графов, особенно отмечая наблюдение, что количество замкнутых путей длиной ${ displaystyle ell}$ из вершины ${ displaystyle i}$ к вершине ${ displaystyle j}$ в ${ displaystyle G}$ компонент в ${ displaystyle i}$й ряд и ${ displaystyle j}$-й столбец матрицы ${ displaystyle A ^ { ell}}$, куда ${ displaystyle A}$ это матрица смежности из ${ displaystyle G}$.

Коши-Шварц: 4-цикл C₄

Зафиксировав две вершины ${ displaystyle u}$ и ${ displaystyle v}$ из ${ displaystyle G}$, каждая копия ${ displaystyle C_ {4}}$ который имеет ${ displaystyle u}$ и ${ displaystyle v}$ на противоположных концах могут быть идентифицированы путем выбора двух (не обязательно различных) общих соседей ${ displaystyle u}$ и ${ displaystyle v}$. Сдача ${ displaystyle operatorname {codeg} (u, v)}$ обозначить кодегри из ${ displaystyle u}$ и ${ displaystyle v}$ (т. е. количество общих соседей), это означает

${ displaystyle operatorname {hom} (C_ {4}, G) = sum _ {u, v in V (G)} operatorname {codeg} (u, v) ^ {2} geq { frac {1} {n ^ {2}}} left ( sum _ {u, v in V (G)} operatorname {codeg} (u, v) right) ^ {2}}$

по неравенству Коши – Шварца. Сумма теперь стала подсчетом всех пар вершин и их общих соседей, что совпадает с подсчетом всех вершин и пар их соседей. Так

${ displaystyle operatorname {hom} (C_ {4}, G) geq { frac {1} {n ^ {2}}} left ( sum _ {x in V (G)} deg ( x) ^ {2} right) ^ {2} geq { frac {1} {n ^ {2}}} left ({ frac {1} {n}} left ( sum _ {x in V (G)} deg (x) right) ^ {2} right) ^ {2} = { frac {1} {n ^ {2}}} left ({ frac {1} {n}} (n cdot pn) ^ {2} right) ^ {2} = p ^ {4} n ^ {4}}$

снова Коши – Шварца. Так

${ displaystyle t (C_ {4}, G) = { frac { operatorname {hom} (C_ {4}, G)} {n ^ {4}}} geq p ^ {4}}$

по желанию.

Теория спектральных графов: 2k-цикл C_2k

Хотя подход Коши – Шварца для ${ displaystyle C_ {4}}$ элегантен и элементарен, он не обобщается сразу на все четные циклы. Однако можно применить спектральную теорию графов, чтобы доказать, что все четные циклы обладают свойством Сидоренко. Обратите внимание, что нечетные циклы не учитываются в гипотезе Сидоренко, поскольку они не являются двудольными.

Используя наблюдение о замкнутых путях, следует, что ${ displaystyle operatorname {hom} (C_ {2k}, G)}$ это сумма диагональных элементов в ${ displaystyle A ^ {2k}}$. Это равно след из ${ displaystyle A ^ {2k}}$, который, в свою очередь, равен сумме ${ displaystyle 2k}$й полномочия собственные значения из ${ displaystyle A}$. Если ${ displaystyle lambda _ {1} geq lambda _ {2} geq dots geq lambda _ {n}}$ являются собственными значениями ${ displaystyle A}$, то теорема мин-макс подразумевает, что

${ displaystyle lambda _ {1} geq { frac { mathbf {1} ^ { intercal} A mathbf {1}} { mathbf {1} ^ { intercal} mathbf {1}}} = { frac {1} {n}} sum _ {x in V (G)} deg (x) = pn,}$

куда ${ displaystyle mathbf {1}}$ вектор с ${ displaystyle n}$ компоненты, все из которых ${ displaystyle 1}$. Но потом

${ displaystyle operatorname {hom} (C_ {2k}, G) = sum _ {i = 1} ^ {n} lambda _ {i} ^ {2k} geq lambda _ {1} ^ {2k } geq p ^ {2k} n ^ {2k}}$

потому что собственные значения a вещественная симметричная матрица настоящие. Так

${ Displaystyle т (C_ {2k}, G) = { frac { operatorname {hom} (C_ {2k}, G)} {n ^ {2k}}} geq p ^ {2k}}$

по желанию.

Энтропия: Пути длины 3

J.L. Сян Ли и Балаж Сегеди (2011) представили идею использования энтропия для доказательства некоторых случаев гипотезы Сидоренко. Позднее Сегеди (2015) применил эти идеи, чтобы доказать, что еще более широкий класс двудольных графов обладает свойством Сидоренко.^[2] Хотя доказательство Сегеди оказалось абстрактным и техническим, Тим Гауэрс и Джейсон Лонг сократил аргумент до более простого для конкретных случаев, таких как пути длины ${ displaystyle 3}$.^[3] По сути, доказательство выбирает красивый распределение вероятностей выбора вершин на пути и применяет Неравенство Дженсена (т.е. выпуклость), чтобы вывести неравенство.

Частичные результаты

Вот список некоторых двудольных графов ${ displaystyle H}$ которые оказались в собственности Сидоренко. Позволять ${ displaystyle H}$ иметь двудольную ${ Displaystyle A sqcup B}$.

• Пути обладают свойством Сидоренко, как показали Малхолланд и Смит в 1959 году (до того, как Сидоренко сформулировал гипотезу).^[4]
• Деревья обладают свойством Сидоренко, обобщающими путями. Это было показано Сидоренко в статье 1991 года.^[5]
• Циклы одинаковой длины имеют собственность Сидоренко, как показано ранее. Сидоренко также продемонстрировал это в своей статье 1991 года.
• Полные двудольные графы есть в собственности Сидоренко. Это также было показано в статье Сидоренко 1991 года.
• Двудольные графы с ${ Displaystyle мин {| А |, | В | } leq 4}$ есть в собственности Сидоренко. Это также было показано в статье Сидоренко 1991 года.
• Графы гиперкуба (обобщения ${ displaystyle Q_ {3}}$) имеют собственность Сидоренко, как показала Хатами в 2008 году.^[6]
  • В более общем смысле, нормирующие графы (введенные Хатами) обладают свойством Сидоренко.
• Если есть вершина в ${ displaystyle A}$ который является соседом с каждой вершиной в ${ displaystyle B}$ (или наоборот), то ${ displaystyle H}$ имеет собственность Сидоренко, как показали Конлон, Фокс и Судаков в 2010 году.^[7] Это доказательство использовало зависимый случайный выбор метод.
• Для всех двудольных графов ${ displaystyle H}$, есть некоторое положительное целое число ${ displaystyle p}$ так что ${ displaystyle p}$-Взрывать из ${ displaystyle B}$ имеет в собственности Сидоренко. Здесь ${ displaystyle p}$-разрыв ${ displaystyle H}$ образуется заменой каждой вершины в ${ displaystyle B}$ с ${ displaystyle p}$ копии самого себя, каждая из которых связана со своими первоначальными соседями в ${ displaystyle A}$. Это показали Конлон и Ли в 2018 году.^[8]
• Были предприняты попытки некоторых рекурсивных подходов, которые берут набор графов, обладающих свойством Сидоренко, для создания нового графа, обладающего свойством Сидоренко. Главный прогресс в этом направлении был достигнут Сидоренко в его статье 1991 года Ли и Сегеди в 2011 году.^[9], а также Ким, Ли и Ли в 2013 году^[10].
  • В статье Ли и Сегеди также использовались энтропийные методы для доказательства этого свойства для класса графов, называемого «деревьями отражения».
  • В статье Кима, Ли и Ли эта идея была распространена на класс графов с древовидной структурой, называемой «древовидно упорядочиваемыми графами».

Однако есть графы, для которых гипотеза Сидоренко остается открытой. Примером может служить граф «лента Мёбиуса». ${ displaystyle K_ {5,5} setminus C_ {10}}$, образованный удалением ${ displaystyle 10}$-цикл из полного двудольного графа с частями размера ${ displaystyle 5}$.

Ласло Ловас доказал локальный вариант гипотезы Сидоренко, т.е. для графов, «близких» к случайным графам в смысле срезанной нормы.^[11]

Наводя догадки

Последовательность графиков ${ displaystyle {G_ {n} } _ {n = 1} ^ { infty}}$ называется квазислучайный с плотностью ${ displaystyle p}$ для некоторой плотности ${ displaystyle 0$

если для каждого графика ${ displaystyle H}$,

${ displaystyle t (H, G_ {n}) = (1 + o (1)) p ^ {| E (H) |}.}$

Таким образом, последовательность графов будет иметь свойства Случайный граф Эрдеша – Реньи ${ Displaystyle G (п, р)}$.

Если плотность края ${ displaystyle t (K_ {2}, G_ {n})}$ фиксируется на ${ displaystyle (1 + o (1)) p}$, то из условия следует, что последовательность графов близка к случаю равенства в свойстве Сидоренко для каждого графа ${ displaystyle H}$.

Из статьи Чанга, Грэма и Уилсона 1989 г. о квазислучайных графах достаточно для ${ displaystyle C_ {4}}$ подсчитать, чтобы соответствовать тому, что можно было бы ожидать от случайного графа (т.е. условие выполняется для ${ displaystyle H = C_ {4}}$).^[12] В статье также спрашивается, какие графики ${ displaystyle H}$ иметь это свойство кроме ${ displaystyle C_ {4}}$. Такие графы называются форсирование графиков поскольку их количество контролирует квазислучайность последовательности графов.

Гипотеза о насилии утверждает следующее:

График ${ displaystyle H}$ принудительно тогда и только тогда, когда оно двудольное, а не дерево.

Несложно увидеть, что если ${ displaystyle H}$ насильно, значит, это двудольное, а не дерево. Некоторыми примерами графов принуждения являются четные циклы (показанные Чангом, Грэхемом и Уилсоном). Скокан и Тома показали, что все полные двудольные графы, не являющиеся деревьями, являются принудительными.^[13]

Гипотеза Сидоренко следует из вынуждающей гипотезы. Более того, принудительная гипотеза показала бы, что графы, близкие к равенству по свойству Сидоренко, должны удовлетворять условиям квазислучайности.^[14]

Рекомендации