Плотность гомоморфизма

В математической области экстремальной теории графов плотность гомоморфизма относительно графа $H$ это параметр $t(H,-)$ который связан с каждым графиком $G$ следующим образом:

$t(H,G):={\frac {\left|\operatorname {hom} (H,G)\right|}{|V(G)|^{|V(H)|}}}$.

Выше, $\operatorname {hom} (H,G)$ — это набор гомоморфизмов графов или карт, сохраняющих смежность, из $H$ к $G$. Плотность также можно интерпретировать как вероятность того, что карта вершин $H$ к вершинам $G$ случайно выбранный равномерно, является гомоморфизмом графа. Существует связь между плотностями гомоморфизма и плотностью подграфов, которая подробно описана ниже.

Примеры

• Плотность ребер графа $G$ дается $t(K_{2},G)$.
• Количество прогулок с $k-1$ шаги задаются $\operatorname {hom} (P_{k},G)$.
• $\operatorname {hom} (C_{k},G)=\operatorname {Tr} (A^{k})$ где $A$ является матрицей смежности $G$.
• Пропорция используемых красителей $k$ подходящие цвета определяются выражением $t(G,K_{k})$.

Другие важные свойства, такие как количество стабильных множеств или максимальный разрез, можно выразить или оценить через числа или плотности гомоморфизма.

Плотность подграфов

Мы определяем (помеченную) плотность подграфа $H$ в $G$ быть

$d(H,G):={\frac {\#{\text{ labeled copies of }}H{\text{ in }}G}{|V(G)|^{|V(H)|}}}$.

Обратите внимание, что было бы немного сомнительно называть это плотностью, поскольку мы не совсем делим на общее количество помеченных подграфов на $|V(H)|$ вершины $G$, но наше определение асимптотически эквивалентно и его проще анализировать для наших целей. Обратите внимание, что любая помеченная копия $H$ в $G$ соответствует гомоморфизму $H$ в $G$. Однако не каждый гомоморфизм соответствует помеченной копии — существуют вырожденные случаи, когда несколько вершин $H$ направляются в одну и ту же вершину $G$. При этом число таких вырожденных гомоморфизмов составляет всего лишь $O(n^{|V(H)|-1})$, поэтому у нас есть $t(H,G)=d(H,G)+O(1/n)$. Например, мы видим, что для графов с постоянной плотностью гомоморфизма плотность помеченного подграфа и плотность гомоморфизма асимптотически эквивалентны. Для $H$ являющийся полным графом $K_{m}$, плотность гомоморфизма и плотность подграфа фактически равны (при $G$ без петель), так как края $K_{m}$ заставить все изображения при гомоморфизме графа быть различными.

Обобщение на графоны

Понятие плотности гомоморфизма можно обобщить на случай, когда вместо графа $G$, у нас есть графон $W$,

$t(H,W)=\int _{[0,1]^{|V(H)|}}\prod _{ij\in E(H)}W(x_{i},x_{j})\prod _{i\in V(H)}dx_{i}$

Обратите внимание, что подынтегральная функция — это произведение, которое пробегает ребра в подграфе. $H$, тогда как дифференциал представляет собой произведение, пробегающее вершины в $H$. Интуитивно каждая вершина $i$ в $H$ представлена ​​переменной $x_{i}.$Например, плотность треугольников в графоне определяется выражением

$t(K_{3},W)=\int \limits _{[0,1]^{3}}W(x,y)W(y,z)W(z,x)dxdydz$.

Это определение плотности гомоморфизма действительно является обобщением, поскольку для любого графа $G$ и связанный с ним ступенчатый графон $W_{G}$, $t(H,G)=t(H,W_{G})$.

Определение можно распространить на все симметричные измеримые функции. $W$. Следующий пример демонстрирует преимущества этого дальнейшего обобщения. Относительно функции $W(x,y)=2\cos(2\pi (x-y))$, плотность $H$ в $W$ количество эйлеровых циклов в $H$.

Это понятие полезно для понимания асимптотического поведения плотностей гомоморфизма графов, удовлетворяющих определенному свойству, поскольку графон является пределом последовательности графов.

Неравенства

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

Теорема Турана

Классическим примером является теорема Турана , которая утверждает, что если $t(K_{r},W)=0$, затем $t(K_{2},W)\leq \left(1-{\frac {1}{r-1}}\right)$. Частным случаем этого является теорема Мантеля , которая утверждает, что если $t(K_{3},W)=0$, затем $t(K_{2},W)\leq 1/2$.

Теорема Гудмана

Расширение теоремы Мантеля дает явную нижнюю оценку плотности треугольников через плотности ребер.

Теорема (Гудмана). $t(K_{3},G)\geq t(K_{2},G)(2t(K_{2},G)-1).$

Теорема Краскала-Катона

Неравенство, обратное теореме Гудмана, является частным случаем теоремы Краскала-Катона , которая утверждает, что $t(K_{3},G)\leq t(K_{2},G)^{3/2}$. Оказывается, что оба эти неравенства являются точными для определенных плотностей ребер.

Доказательство. Это неравенство достаточно доказать для любого графа $G$. Сказать $G$ это график на $n$ вершины и $\{\lambda _{i}\}_{i=1}^{n}$ являются собственными значениями его матрицы смежности $A_{G}$. Из теории спектральных графов мы знаем

$\operatorname {hom} (K_{2},G)=t(K_{2},G)|V(G)|^{2}=\sum _{i=1}^{n}\lambda _{i}^{2}$, и $\operatorname {hom} (K_{3},G)=t(K_{3},G)|V(G)|^{3}=\sum _{i=1}^{n}\lambda _{i}^{3}$.

Вывод тогда следует из следующего неравенства:

$\operatorname {hom} (K_{3},G)=\sum _{i=1}^{n}\lambda _{i}^{3}\leq \left(\sum _{i=1}^{n}\lambda _{i}^{2}\right)^{3/2}=\operatorname {hom} (K_{2},G)^{3/2}$.

Описание треугольника и плотности ребер

Более полное описание взаимоотношений между $t(K_{3},G)$ и $t(K_{2},G)$ было доказано Разборовым . Его работа 2008 года завершает понимание проблемы неравенства гомоморфизма, описание $D_{2,3}$, которая является областью допустимой плотности ребер, пар плотности треугольников в графоне.

$D_{2,3}=\{(t(K_{2},W),t(K_{3},W))\;:\;W{\text{ is a graphon}}\}\subseteq [0,1]^{2}$.

Верхняя граница области точная и определяется теоремой Краскала-Катона. Нижняя граница является основным результатом работы Разборова по обеспечению полного описания.

Полезные инструменты

Коши-Шварц

Одним из особенно полезных неравенств для анализа плотностей гомоморфизма является неравенство Коши – Шварца . Эффект применения неравенства Коши-Шварца заключается в «складывании» графика по линии симметрии, чтобы связать его с меньшим графом. Это позволяет уменьшить плотность больших, но симметричных графов до плотности меньших графов. В качестве примера докажем, что цикл длины 4 — Сидоренко . Если вершины помечены цифрами 1,2,3,4 именно в таком порядке, диагональ, проходящая через вершины 1 и 3, является линией симметрии. Сгибание этой линии относится $C_{4}$ к полному двудольному графу $K_{1,2}$. Математически это формализуется как

${\begin{aligned}t(C_{4},G)&=\int _{1,2,3,4}W(1,2)W(2,3)W(3,4)W(1,4)=\int _{1,3}\left(\int _{2}W(1,2)W(2,3)\right)\left(\int _{4}W(1,4)W(4,3)\right)=\int _{1,3}\left(\int _{2}W(1,2)W(2,3)\right)^{2}\\&\geq \left(\int _{1,2,3}W(1,2)W(2,3)\right)^{2}=t(K_{1,2},G)^{2}\end{aligned}}$

где мы применили Коши-Шварца, чтобы «сложить» вершину 2 на вершину 4. Тот же метод можно использовать, чтобы показать $t(K_{1,2},G)\geq t(K_{2},G)^{2}$, что в сочетании с вышеизложенным подтверждает, что $C_{4}$ является графом Сидоренко.

Обобщенное неравенство Гёльдера также можно использовать аналогичным образом для многократного сворачивания графов за один шаг. Также возможно применить более общую форму Коши-Шварца к графам складки в случае, когда определенные ребра лежат на линии симметрии.

лагранжиан

Лагранжиан может быть полезен при анализе экстремальных задач. Количество определяется как

$L(H)=\max _{\begin{matrix}x_{1},\ldots ,x_{n}\geq 0\\x_{1}+\cdots x_{n}=1\end{matrix}}\sum _{e\in E(H)}\prod _{v\in e}x_{v}$.

Одним из полезных фактов является то, что максимизирующий вектор $x$ одинаково опирается на вершины клики в $H$. Ниже приводится применение анализа этой величины.

По мнению Хамеда Хатами и Сергея Норине, любое алгебраическое неравенство между плотностями гомоморфизма можно преобразовать в линейное неравенство. В некоторых ситуациях решение о том, верно или нет такое неравенство, можно упростить, как это происходит в следующей теореме.

Теорема ( Боллобас ). Позволять $a_{1},\cdots ,a_{n}$ быть действительными константами. Тогда неравенство

$\sum _{i=1}^{n}a_{i}t(K_{i},G)\geq 0$

справедливо для каждого графа $G$ тогда и только тогда, когда это справедливо для любого полного графа $K_{m}$.

Однако мы получаем гораздо более сложную проблему, фактически неразрешимую , когда у нас есть неравенства гомоморфизма на более общем множестве графов $H_{i}$:

Теорема (Хатами, Норине). Позволять $a_{1},\cdots ,a_{n}$ быть действительными константами, и $\{H_{i}\}_{i=1}^{n}$ графики. Тогда неразрешимой задачей является определить, выполняется ли неравенство плотности гомоморфизма

$\sum _{i=1}^{n}a_{r}t(H_{i},G)\geq 0$

справедливо для каждого графа $G$.

Недавнее наблюдение доказывает, что любое неравенство плотности линейного гомоморфизма является следствием положительной полуопределенности некоторой бесконечной матрицы или положительности квантового графа ; другими словами, любое такое неравенство будет следовать из применения неравенства Коши-Шварца.

См. также

• Общий график
• Гипотеза Сидоренко