Плотность гомоморфизма - Homomorphism density - Wikipedia

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

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

Над, ${\displaystyle hom(H,G)}$ это набор гомоморфизмы графов, или карты с сохранением смежности, из ${\displaystyle H}$ к ${\displaystyle G}$. Плотность также можно интерпретировать как вероятность того, что карта из вершин ${\displaystyle H}$ в вершины ${\displaystyle G}$ равномерно случайным образом выбирается гомоморфизм графов.^[1] Существует связь между плотностями гомоморфизмов и плотностями подграфов, которая подробно рассматривается ниже. ^[2]

Примеры

• Плотность ребер графа ${\displaystyle G}$ дан кем-то ${\displaystyle t(K_{2},G)}$.
• На графике с ${\displaystyle n}$ вершины, где средняя степень больше или равна ${\displaystyle pn}$, плотность края не менее ${\displaystyle p}$.
• Плотность треугольников на графике ${\displaystyle G}$ дан кем-то ${\displaystyle t(K_{3},G)}$.
• Плотность 4-х циклов на графике ${\displaystyle G}$ дан кем-то ${\displaystyle t(C_{4},G)}$.

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

Определим (помеченную) плотность подграфа графа ${\displaystyle H}$ в ${\displaystyle G}$ быть

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

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

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

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

${\displaystyle 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}}$

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

Например, плотность треугольника в графоне определяется как

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

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

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

Важные результаты: неравенство

Многие результаты в экстремальная теория графов могут быть описаны неравенствами, включающими плотности гомоморфизмов, ассоциированные с графом. Например, Теорема Мантеля заявляет, в контексте графоны, что если ${\displaystyle t(K_{3},W)=0}$, тогда ${\displaystyle t(K_{2},W)\leq 1/2}$. Другой пример Теорема Турана, который гласит, что если ${\displaystyle t(K_{r},W)=0}$, тогда ${\displaystyle t(K_{2},W)\leq (r-2/r-1)}$.

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

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

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

выполняется для каждого графа ${\displaystyle G}$ тогда и только тогда, когда это верно для каждого полного графа ${\displaystyle K_{m}}$.^[3]

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

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

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

выполняется для каждого графа ${\displaystyle G}$. ^[2]

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

Описание ${\displaystyle D_{2,3}}$

Еще одно недавнее достижение состоит в завершении понимания проблемы неравенства гомоморфизма, описании ${\displaystyle D_{2,3}}$, которая является областью допустимой плотности ребер, пары плотности треугольников в графоне:

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

Наблюдение 1. Эта область замкнута, поскольку предел последовательности графов - графон. ^[1]

Замечание 2. Для каждого ${\displaystyle 0\leq r\leq 1}$, набор ${\displaystyle D_{2,3}\cap [0,1]\times \{r\}}$ представляет собой вертикальный отрезок без пробелов.

Доказательство: Рассмотрим два графона ${\displaystyle W_{0}}$, ${\displaystyle W_{1}}$ с одинаковой плотностью кромки; тогда семейство графонов следующего вида: ${\displaystyle t}$ варьируется от 0 до 1

${\displaystyle W_{t}=(1-t)W_{0}+tW_{1}}$

достигает всевозможной плотности треугольника между значениями ${\displaystyle t(K_{3},W_{0})}$ и ${\displaystyle t(K_{3},W_{1})}$, по непрерывности этой карты.

Замечание 3. Для каждого, графон ${\displaystyle W:[0,1]^{2}\rightarrow [0,1]}$, имеем оценку сверху ${\displaystyle t(K_{3},W)\leq t(K_{2},W)^{3/2}}$

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

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

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

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

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

Замечание 3. Экстремальные точки выпуклой оболочки

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

даны ${\displaystyle W=K_{m}}$ для каждого ${\displaystyle m}$ положительное число. В частности, экстремумы ${\displaystyle D_{2,3}}$ задаются следующим дискретным набором точек на кривой ${\displaystyle y=x(2x-1)}$:

${\displaystyle p_{m}=\left({\frac {m-1}{m}},{\frac {(m-1)(m-2)}{m^{2}}}\right)}$

Замечание 3. Это теорема, вытекающая из Разборов,^[5] который утверждает, что для данной плотности краев ${\displaystyle r=t(K_{2},W)}$, если

${\displaystyle {\frac {k-1}{k}}<r<{\frac {k}{k+1}}}$,

для некоторого положительного целого числа ${\displaystyle k}$, то минимально допустимая плотность треугольников достигается единственной ступенчатой ​​функцией graphon ${\displaystyle W}$ с весами узлов ${\displaystyle a_{1},\cdots a_{k}}$ с суммой равной 1 и такой, что ${\displaystyle a_{1}=\cdots =a_{k-1}\geq a_{k}}$. Более точно, минимально возможный ${\displaystyle t(K_{3},W)}$ является

${\displaystyle {\frac {(k-1)\left(k-2{\sqrt {k(k-r(k+1))}}\right)\left(k+{\sqrt {k(k-r(k+1))}}\right)^{2}}{k^{2}(k+1)^{2}}}}$.

Смотрите также

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

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

1. Боргс, К., Чайес, Дж. Т., Ловас, Л., Сос, В. Т., Вестергомби, К. (2008). «Сходящиеся последовательности плотных графов. I. Частоты подграфов, метрические свойства и тестирование». Успехи в математике. 219, № 6: 1805, 1811 - через ELSEVIER Science Project.
2. Хатами, Х., Норин, С. (2011). «Неразрешимость линейных неравенств в плотностях гомоморфизмов графов» (PDF). Журнал Американского математического общества. 24, № 2: 553 - через MathSciNet.
3. Боллобаш, Бела (1986). Комбинаторика: системы множеств, гиперграфы, семейства векторов и комбинаторная вероятность. Кембридж: Издательство Кембриджского университета. стр.79-84. ISBN  0-521-33059-9.
4. Фридман, М., Ловас, Л., Шрайвер, А. (2007). «Позитивность отражения, ранговая связность и гомоморфизм графов» (PDF). Журнал Американского математического общества. 20, № 1: 1.
5. Разборов, Александр (2008). «О минимальной плотности треугольников в графах» (PDF). Комбинаторика, теория вероятностей и вычисления. 17, № 4: 1 - через MathSciNet (AMS).