Алгебра флагов

Алгебры флагов являются важным вычислительным инструментом в области теории графов , который имеет широкий спектр приложений для изучения плотности гомоморфизма и смежных тем. Грубо говоря, они формализуют понятие сложения и умножения плотностей гомоморфизма и создают основу для решения неравенств гомоморфизма графов с помощью компьютеров, сводя их к полуопределенным задачам программирования. Первоначально представлено Александром Разборовым в статье 2007 года. С тех пор этот метод позволил решить множество сложных, ранее нерешенных вопросов теории графов. К ним относятся $D_{2,3}$ вопрос относительно области допустимой плотности ребер, пар плотности треугольников и максимального количества пятиугольников в графах без треугольников.

Мотивация

Мотивация теории алгебр флагов приписывается Джону Адриану Бонди и его работе над гипотезой Качетта-Хаггквиста приправленного гомоморфизмом графов , где он проиллюстрировал свои основные идеи с помощью доказательства теоремы Мантеля, . Это доказательство представляет собой адаптацию традиционного доказательства Мантеля посредством двойного счета , за исключением того, что оно сформулировано в терминах плотностей гомоморфизма графов и показывает, какой объем информации можно закодировать с помощью только отношений плотности.

Теорема (Мантела): Плотность ребер в графе без треугольников. $G$ самое большее ${\frac {1}{2}}$. Другими словами, $\mathrm {ex} (K_{2},\{K_{3}\})\leq {\frac {1}{2}}.$

Поскольку в графе нет треугольников, среди трех вершин в $G$, они могут либо образовывать независимый набор , либо одно индуцированное ребро ${\tilde {P_{3}}}$, или путь длины 2 $P_{3}$. Обозначая $d(H,G)$ как индуцированная плотность подграфа $H$ в $G$, двойной счет дает:

${\binom {n}{3}}\left(d({\tilde {P_{3}}},G)+2d(P_{3},G)\right)={\binom {n}{2}}(n-2)d(K_{2},G)\implies d({\tilde {P_{3}}},G)+2d(P_{3},G)=3d(K_{2},G).$

Интуитивно, $d(P_{3},G)\approx 3d(K_{2},G)^{2}$ с тех пор как $P_{3}$ состоит всего из двух $K_{2}$s соединены вместе, и существует три способа пометить общую вершину среди набора из трех точек. Фактически, это можно строго доказать, дважды подсчитав количество индуцированных $P_{3}$с. Сдача в аренду $|G|$ обозначаем количество вершин $G$, у нас есть:

$d(P_{3},G)={\binom {|G|}{3}}^{-1}\sum _{v\in V(G)}{\binom {d(v)}{2}}={\binom {|G|}{3}}^{-1}{\binom {|G|-1}{2}}\sum _{v\in V(G)}d(P_{3}^{b},G^{v})={\frac {3}{|G|}}\sum _{v\in V(G)}d(P_{3}^{b},G^{v}),$

где $P_{3}^{b}$ - путь длины 2 с помеченной средней вершиной, и $d(P_{3}^{b},G^{v})$ представляет собой плотность $P_{3}^{b}$s подчиняется ограничению, согласно которому используется помеченная вершина, и что $P_{3}^{b}$ считается правильным индуцированным подграфом только тогда, когда его помеченная вершина совпадает с $v$. Теперь обратите внимание, что $d(P_{3}^{b},G^{v})\approx d(K_{2}^{b},G^{v})^{2}$ поскольку вероятность выбора двух $K_{2}^{b}$s, где непомеченные вершины совпадают, мала (если быть строгим, предел как $|G|\to \infty$ надо брать, так $d(H,G)$ действует как предельная функция на последовательности все больших и больших графов $G$. Эта идея будет важна для фактического определения алгебр флагов.)В завершение примените неравенство Коши – Шварца, чтобы получить

$\sum _{v\in V(G)}d(P_{3}^{b},G^{v})\approx \sum _{v\in V(G)}d(K_{2}^{b},G^{v})^{2}\geq {\frac {1}{|G|}}\left(\sum _{v\in V(G)}d(K_{2}^{b},G^{v})\right)^{2}={\frac {1}{|G|}}\left({\frac {1}{|G|-1}}{\binom {|G|}{2}}2d(K_{2},G)\right)^{2}=|G|d(K_{2},G)^{2}.$

Если подключить это обратно к нашему исходному соотношению, это докажет то, что было высказано интуитивно. Наконец, обратите внимание, что $d({\tilde {P_{3}}},G)\geq 0$ так

$6d(K_{2},G)^{2}\leq 2d(P_{3},G)\leq 3d(K_{2},G)\implies d(K_{2},G)\leq {\frac {1}{2}}.$

Важными идеями этого доказательства, которые будут обобщены в теории алгебр флагов, являются такие замены, как $d(P_{3},G)\to 3d(K_{2},G)^{2}$, использование помеченных плотностей графов, рассмотрение только «предельного случая» плотностей и применение Коши в конце для получения значимого результата.

Определение

Исправить коллекцию запрещенных подграфов ${\mathcal {H}}$ и рассмотрим набор графов ${\mathcal {G}}$ из ${\mathcal {H}}$-бесплатные графики. Теперь определите тип размера $k$ быть графиком $\sigma \in {\mathcal {G}}$ с помеченными вершинами $V(\sigma )=[k]$. Тип размера 0 обычно обозначается как $\varnothing$.

Сначала мы определяем $\sigma$-flag, частично размеченный граф, который будет иметь решающее значение для теории алгебр флагов:

Определение: А $\sigma$-флаг - пара $(F,\theta )$ где $F\in {\mathcal {G}}$ является основным, немаркированным, ${\mathcal {H}}$-свободный граф, в то время как $\theta :[k]\to V(F)$ определяет вложение помеченного графа $\sigma$ на вершины $F$.

Обозначим множество $\sigma$-флаги быть ${\mathcal {F}}^{\sigma }$ и набор $\sigma$-флаги размера $n$ быть ${\mathcal {F}}_{n}^{\sigma }$. В качестве примера: $P_{3}^{b}$ из доказательства теоремы Мантеля, приведенного выше, является $\sigma$-флаг где $\sigma$ — это тип размера 1, соответствующий одной вершине.

Для $\sigma$-флаги $F_{1},F_{2},\ldots ,F_{t},(G,\theta )$ удовлетворяющий $|G|-|\sigma |\geq \sum _{i=1}^{t}|F_{i}|-|\sigma |$, мы можем определить плотность $\sigma$-флаги на базовый график $G$ следующим образом:

Определение: Плотность $p(F_{1},F_{2},\ldots ,F_{t};G)$ принадлежащий $\sigma$-флаги $F_{1},\ldots ,F_{t}$ в $G$ определяется как вероятность успешного случайного внедрения $F_{1},\ldots ,F_{t}$ в $V(G)$ такие, что они не пересекаются на $V(G)\setminus \mathrm {im} (\theta )$ и все помечены точно так же, как $G$ на $\mathrm {im} (\theta )$. Точнее, выберите попарно непересекающиеся $U_{1},U_{2},\ldots ,U_{t}\subseteq V(G)\setminus \mathrm {im} (\theta )$ наугад и определить $p(F_{1},\ldots ,F_{t};G)$ быть вероятностью того, что $\sigma$-флаг $(G[U_{i}\cup \mathrm {im} (\theta )],\theta )$ изоморфен $F_{i}$ для всех $i\in [t]$.

Обратите внимание, что при встраивании $F$ в $G$, где $F,G$ являются $\sigma$-flags, это можно сделать путем первого встраивания $F$ в $\sigma$-флаг $F'$ размера $n\in [|F|,|G|]$ а затем встраивание $F'$ в $G$, что дает формулу: $p(F;G)=\sum _{F'\in {\mathcal {F}}_{n}^{\sigma }}p(F;F')p(F';G)$. Распространив это на наборы $\sigma$-flags дает правило цепочки:

Теорема (цепное правило): Если $F_{1},F_{2},\ldots ,F_{t},G$ являются $\sigma$-флаги, $s,n$ являются естественными такими, что $F_{1},\ldots ,F_{t}$ вписаться $G$, $F_{1},\ldots ,F_{s}$ вписаться в $\sigma$-флаг размера $n$и $\sigma$-флаг размера $n$ в сочетании с $F_{s+1},\ldots ,F_{t}$ вписаться $G$, затем

$p(F_{1},F_{2},\ldots ,F_{t};G)=\sum _{F\in {\mathcal {F}}_{n}^{\sigma }}p(F_{1},\ldots ,F_{s};F)p(F,F_{s+1},\ldots ,F_{t};G)$.

Напомним, что предыдущее доказательство Мантеля включало линейные комбинации членов вида $d(H,G)$. Соответствующие идеи были немного неточными, позволяя $|G|$ стремятся к бесконечности, но явно существует последовательность $G_{1},G_{2},\ldots$ такой, что $d(H,G_{i})$ сходится к некоторым $\phi (H)$ для всех $H$, где $\phi$ называется предельным функционалом. Таким образом, все ссылки на $d(H,G)$ на самом деле относятся к предельному функционалу. Теперь неравенства гомоморфизма графов можно записать в виде линейных комбинаций $\phi$ с разными $H$s, но было бы удобно выразить их одним термином. Это мотивирует определить $\mathbb {R} {\mathcal {F}}^{\sigma }$, множество формальных линейных комбинаций $\sigma$-флаги над $\mathbb {R}$, и теперь $\phi$ можно расширить до линейной функции по $\mathbb {R} {\mathcal {F}}^{\sigma }$.

Однако, используя все пространство $\mathbb {R} {\mathcal {F}}^{\sigma }$ расточительно при исследовании только предельных функционалов, поскольку существуют нетривиальные соотношения между плотностями некоторых $\sigma$-флаги. В частности, правило цепочки показывает, что

$\phi (F)=\phi \left(\sum _{F'\in {\mathcal {F}}_{n}^{\sigma }}p(F;F')F'\right)\implies F-\sum _{F'\in {\mathcal {F}}_{n}^{\sigma }}p(F;F')F'\in \ker \phi$

всегда верно. Вместо того, чтобы иметь дело со всеми этими элементами ядра , пусть набор выражений приведенной выше формы (т. е. полученных из цепного правила с одним $\sigma$-флаг) как ${\mathcal {K}}^{\sigma }$ и факторизируем их в нашем окончательном анализе. Эти идеи в совокупности образуют определение алгебры флагов:

Определение (алгебры флагов). Алгебра флагов определяется в пространстве линейных комбинаций $\sigma$-флаги ${\mathcal {A}}^{\sigma }=\mathbb {R} {\mathcal {F}}^{\sigma }/{\mathcal {K}}^{\sigma }$ оснащен билинейным оператором

$F\cdot G=\sum _{H\in {\mathcal {F}}_{n}^{\sigma }}p(F,G;H)H$

для $F,G\in {\mathcal {F}}^{\sigma }$ и любые натуральные $n$ такой, что $F,G$ вписаться в $\sigma$-флаг размера $n$, линейно расширяя оператор до $\mathbb {R} {\mathcal {F}}^{\sigma }$.

Осталось проверить, что выбор $n$ не имеет значения для пары $F,G$ при условии, что оно достаточно велико (это можно доказать с помощью правила цепочки), а также если $f\in {\mathcal {K}}^{\sigma }$ затем $f\cdot g\in {\mathcal {K}}^{\sigma }$, что означает, что оператор учитывает фактор и, таким образом, образует четко определенную алгебру в желаемом пространстве.

Одним из важных результатов этого определения для оператора является то, что умножение соблюдается для предельных функционалов. В частности, для предельного функционала $\phi$, личность $\phi (f\cdot g)=\phi (f)\cdot \phi (g)$ соответствует действительности. Например, было показано, что $\phi (P_{3}^{b})=\phi (K_{2}^{b})^{2}$ в нашем доказательстве Мантеля, и этот результат является лишь следствием этого утверждения. В более общем плане тот факт, что $\phi$ мультипликативен, означает, что все предельные функционалы являются гомоморфизмами алгебр между ${\mathcal {A}}^{\sigma }$ и $\mathbb {R}$.

Нисходящий оператор

Приведенное выше определение обеспечивает основу для решения $\sigma$-флаги, которые частично помечены графами. Однако в большинстве случаев немаркированные графики или $\varnothing$-флаги представляют наибольший интерес. Чтобы перейти от первого ко второму, определите нисходящий оператор.

Оператор вниз определяется наиболее естественным образом: учитывая $\sigma$-флаг $F$, позволять $\downarrow \!\!F$ быть $\varnothing$-флаг, возникающий в результате забывания меток, назначенных $\sigma$. Теперь, чтобы определить естественное отображение между $\sigma$-флаги и неразмеченные графы, пусть $q_{\sigma }(F)$ — вероятность того, что инъективное отображение $\theta :[k]\to V(F)$ взятое наугад, имеет изображение, изоморфное $\sigma$и определить $[\![F]\!]_{\sigma }=q_{\sigma }(F)\downarrow \!\!F$. Расширение $[\![\cdot ]\!]$ линейно к $\mathbb {R} {\mathcal {F}}^{\sigma }$ дает действительную линейную карту, которая отправляет комбинации $\sigma$-флажки к комбинациям немаркированных.

Самый важный результат относительно $[\![\cdot ]\!]$ это его усредняющие свойства. В частности, исправить $\sigma$-флаг $F$ и неразмеченный график $G$ с $|G|\geq |F|$, затем выбираем вложение $\theta$ из $\sigma$ на $G$ случайным образом определяет случайную величину $p(F;(G,\theta ))$. Можно показать, что

$\mathbb {E} [p(F;(G,\theta )]={\frac {q_{\sigma }(F)p(\downarrow \!\!F;G)}{q_{\sigma }(\sigma )p(\downarrow \!\!\sigma ;G)}}.$

Оптимизация с помощью алгебр флагов

Все линейные функционалы, $\phi$ являются гомоморфизмами алгебр $\phi :{\mathcal {A}}^{\sigma }\to \mathbb {R}$. Более того, по определению $\phi (F)\geq 0$ для любого $\sigma$-флаг $F$ с $\phi$ представляет собой предел плотности. Итак, скажем, что гомоморфизм $\psi \in \operatorname {Hom} ({\mathcal {A}}^{\sigma },\mathbb {R} )$ положительно тогда и только тогда, когда $\psi (F)\geq 0\forall F\in {\mathcal {F}}^{\sigma }$, и пусть $\operatorname {Hom} ^{+}(A^{\sigma },\mathbb {R} )$ — множество положительных гомоморфизмов. Можно показать, что множество предельных функционалов $\Phi$ есть в точности множество положительных гомоморфизмов $\operatorname {Hom} ^{+}(A^{\sigma },\mathbb {R} )$, поэтому достаточно понять последнее определение множества.

Чтобы получить линейную комбинацию $f\in {\mathcal {A}}^{\sigma }$ Чтобы получить действительное неравенство гомоморфизма графов, оно должно быть неотрицательным для всех возможных линейных функционалов, что тогда будет означать, что оно верно для всех графов. Учитывая это, определим семантический конус типа $\sigma$, набор ${\mathcal {S}}^{\sigma }\subset {\mathcal {A}}^{\sigma }$ такой, что

${\mathcal {S}}^{\sigma }=\{f\in {\mathcal {A}}^{\sigma }\mid \phi (f)\geq 0\,\,\,\forall \phi \in \operatorname {Hom} ^{+}({\mathcal {A}}^{\sigma },\mathbb {R} )\}.$

Снова, $\sigma =\varnothing$ представляет наибольший интерес и соответствует случаю неразмеченных графов. Однако нисходящий оператор обладает свойством отображать ${\mathcal {S}}^{\sigma }$ к ${\mathcal {S}}^{\varnothing }$, и можно показать, что образ ${\mathcal {S}}^{\sigma }$ под $[\![\cdot ]\!]_{\sigma }$ является подмножеством ${\mathcal {S}}^{\varnothing }$, что означает, что любые результаты по типу $\sigma$ семантический конус легко обобщается и на неразмеченные графы.

Просто наивно манипулируя элементами ${\mathcal {A}}^{\sigma }$, многочисленные элементы смыслового конуса ${\mathcal {S}}^{\sigma }$ может быть сгенерирован. Например, поскольку элементы $\operatorname {Hom} ^{+}({\mathcal {A}}^{\sigma },\mathbb {R} )$ неотрицательны для $\sigma$-флаги, любая коническая комбинация элементов ${\mathcal {F}}^{\sigma }$ даст элемент ${\mathcal {S}}^{\sigma }$. Возможно, более нетривиально, любая коническая комбинация квадратов элементов $A^{\sigma }$ также даст элемент семантического конуса.

Хотя квадраты флагов, которые в сумме дают нетривиальные результаты, можно найти вручную, зачастую проще автоматизировать процесс. В частности, можно адаптировать идеи оптимизации суммы квадратов для многочленов к алгебрам флагов. Определить степень вектора $f\in \mathbb {R} {\mathcal {F}}^{\sigma }$ быть самым большим флагом с ненулевым коэффициентом в разложении $f$, и пусть степень $f^{*}\in {\mathcal {A}}^{\sigma }$ быть минимальной степенью вектора среди всех вариантов выбора в $f^{*}+{\mathcal {K}}^{\sigma }$. Также определите $v_{\sigma ,n}={\mathcal {F}}_{n}^{\sigma }\to {\mathcal {A}}^{\sigma }$ как каноническая вставка отправки $F$ себе за все $F\in {\mathcal {F}}_{n}^{\sigma }$. Эти определения приводят к следующему аналогу алгебры флагов:

Теорема: Учитывая $f\in {\mathcal {A}}^{\sigma }$, $n\geq |\sigma |$, то существуют $g_{1},\ldots ,g_{t}\in {\mathcal {A}}^{\sigma }$ для некоторых $t\geq 1$ тогда и только тогда, когда существует положительная полуопределенная матрица $Q:{\mathcal {F}}_{n}^{\sigma }\times {\mathcal {F}}_{n}^{\sigma }\to \mathbb {R}$ такой, что $f=v_{\sigma ,n}^{\intercal }Qv_{\sigma ,n}$.

Благодаря этой теореме проблемы гомоморфизма графов теперь можно свести к задачам полуопределенного программирования, которые можно решить с помощью компьютера. Например, теорему Мантеля можно перефразировать как поиск наименьшего $\lambda \in \mathbb {R}$ такой, что $\lambda \varnothing -K_{2}\in S^{\varnothing }$. Как $S^{\varnothing }$ плохо изучен, в такой форме трудно продвинуться в вопросе, но заметим, что конические комбинации $\varnothing$-флаги и квадраты векторов лежат в $S^{\varnothing }$, поэтому вместо этого возьмите полуопределенное расслабление. В частности, минимизировать $\lambda$ при условии, что $\lambda \varnothing -K_{2}=r+[\![v_{1,2}^{\intercal }Qv_{1,2}]\!]$ где $r$ представляет собой коническую комбинацию $\varnothing$-флаги и $Q$ является положительно полуопределенным. Эту новую задачу оптимизации можно преобразовать в задачу полуопределенного программирования, которую затем можно решить с помощью стандартных алгоритмов.

Обобщения

Метод алгебр флагов легко обобщается на многочисленные графоподобные конструкции. Как писал Разборов в своей оригинальной статье, вместо этого флаги можно описывать с помощью теории конечных моделей . Вместо графов — модели некоторой невырожденной универсальной теории первого порядка. $T$ с равенством в конечной реляционной сигнатуре $L$ можно использовать только предикатные символы. Модель $M$, который заменяет наше предыдущее понятие графа, имеет базовый набор $V(M)$, элементы которого называются вершинами.

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