| Успехи математических наук |
|
|
|
|
|
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях) Весовые системы и инварианты графов и вложенных графов М. Э. Казарянab, С. К. Ландоab a Национальный исследовательский университет "Высшая школа экономики" b Сколковский институт науки и технологий
Англоязычная версия:
Russian Mathematical Surveys, 2022, Volume 77, Issue 5, Pages DOI: https://doi.org/10.4213/rm10054e 
Реферативные базы данных:
    ВведениеСформировавшаяся в основном в 1990-х годах теория инвариантов узлов и зацеплений конечного порядка, основы которой заложены в работе [61], породила необходимость изучения весовых систем. Весовая система – это функция на хордовых диаграммах, удовлетворяющая так называемым $4$-членным соотношениям Васильева. Обычно рассматриваются весовые системы, принимающие значения в некотором коммутативном кольце. В свою очередь, хордовая диаграмма – это комбинаторный объект, граф специального вида. Можно считать, что это $3$-регулярный граф с выделенным ориентированным гамильтоновым циклом. Такие графы считаются изоморфными, если существует изоморфизм, переводящий гамильтонов цикл в первом графе в гамильтонов цикл во втором с сохранением ориентации. $4$-членные соотношения строятся по хордовой диаграмме и паре соседних вершин на гамильтоновом цикле и представляют собой линейные соотношения на значениях функции на четверке хордовых диаграмм с одним и тем же количеством вершин. Поскольку эти соотношения линейны, поиск всех весовых систем сводится к решению систем линейных уравнений. Однако и количество переменных (хордовых диаграмм), и количество уравнений ($4$-членных соотношений) очень быстро растет с ростом числа вершин в диаграмме (так, имеется более 600 тыс. диаграмм с $2\cdot 9=18$ вершинами, а количество соотношений превышает $5\cdot10^6$). В то же время ранг матрицы уравнений – размерность пространства хордовых диаграмм по модулю $4$-членных соотношений – растет гораздо медленнее и в случае 9 хорд равен $104$. Универсальные методы вычисления этих размерностей отсутствуют, и имеются лишь довольно грубые верхние и нижние оценки. Наряду с изучением пространств всех весовых систем, важную роль играют процедуры построения конкретных весовых систем и их семейств. Эти конструкции используются, в частности, для получения нижних оценок на размерности. Двумя основными источниками конструкций являются инварианты графов пересечений хордовых диаграмм, удовлетворяющие $4$-членным соотношениям для графов [43], и метризованные алгебры Ли [39], [5]. Между этими двумя конструкциями имеются существенные отличия. Инварианты графов, как правило, несложно вычислить, однако соответствующие им весовые системы имеют не очень высокую различающую способность. Напротив, весовые системы, отвечающие алгебрам Ли, оказываются довольно мощными, но до недавнего времени не было известно эффективных подходов к их вычислению. В настоящей статье мы описываем оба упомянутых выше подхода к конструированию весовых систем, концентрируясь на недавних результатах. Задача вычисления значений весовых систем, отвечающих метризованным алгебрам Ли, на хордовых диаграммах является сложной из-за того, что вычисления приходится проводить в некоммутативной алгебре – универсальной обертывающей алгебре алгебры Ли. Для простейшего нетривиального случая алгебры Ли $\mathfrak{sl}(2)$ вычисления упрощаются благодаря наличию рекуррентных соотношений Чмутова–Варченко [20], однако и их использование не всегда приводит к желаемому результату. Так, до самого последнего времени не были известны значения $\mathfrak{sl}(2)$-весовой системы на хордовых диаграммах, любые две хорды в которых пересекают друг друга (т. е. диаграммах с полным графом пересечений). Окончательный ответ дала П. Закорко [65], доказав гипотезу С. К. Ландо 2015 г. о производящей функции для этих значений. Еще одно недавнее достижение – построение рекуррентных соотношений для вычисления значений $\mathfrak{gl}(N)$-весовой системы [63]. Эти соотношения основываются на предложении М. Э. Казаряна о продолжении $\mathfrak{gl}(N)$-весовой системы на произвольные перестановки (в то время как хордовые диаграммы интерпретируются как перестановки специального вида). Один из ключевых вопросов в исследовании инвариантов графов состоит в том, как распространять такие инварианты на вложенные графы, т. е. графы на поверхностях. Этому вопросу посвящено большое количество статей последнего времени. В большинстве статей инвариант вложенных графов определяется как инвариант подлежащего абстрактного графа, расширенный за счет добавления в него информации о вложении. Нас, однако, в первую очередь интересует возможность продолжения весовых систем, отвечающих инвариантам конечного порядка узлов, до весовых систем, отвечающих инвариантам конечного порядка зацеплений (зацепление, в отличие от узла, может иметь несколько компонент связности). Хордовую диаграмму можно интерпретировать как вложенный граф с одной вершиной на ориентированной поверхности, а зацеплениям отвечают обобщенные хордовые диаграммы – вложенные графы с числом вершин, равным количеству компонент зацепления, на ориентированных поверхностях. В недавних работах [50], [24] предложен подход к продолжению весовых систем и инвариантов графов на произвольные вложенные графы, основанный на анализе структур соответствующих алгебр Хопфа. Алгебры Хопфа естественно возникают при решении комбинаторных задач различной природы (см., например, [13]). Пространство графов и пространство хордовых диаграмм по модулю $4$-членных соотношений наделены естественными структурами связных градуированных алгебр Хопфа. На пространстве, порожденном вложенными графами, такая структура нам неизвестна. Однако она есть на пространстве бинарных дельта-матроидов [45] – комбинаторных объектов, аккумулирующих в себе важную информацию как о структуре графа или хордовой диаграммы, так и о структуре вложенного графа. В то же время вопрос о том, как определять весовые системы, ассоциированные с метризованными алгебрами Ли, на дельта-матроидах, остается открытым. Статья имеет следующую структуру. В разделе 1 мы напоминаем основные определения, связанные с хордовыми диаграммами, их графами пересечений, $4$-членными соотношениями для хордовых диаграмм и графов. Мы приводим несколько ключевых примеров инвариантов графов, удовлетворяющих $4$-членным соотношениям и задающих тем самым весовые системы. В разделе 2 описана структура алгебры Хопфа на пространстве графов и поведение приведенных ранее примеров инвариантов графов относительно этой структуры. Здесь также приведены недавние результаты [18] о связи между структурой алгебры Хопфа и свойством интегрируемости инвариантов графов. Раздел 3 посвящен весовым системам, отвечающим алгебрам Ли. Наряду с известными определениями и результатами об $\mathfrak{sl}(2)$-весовой системе здесь описаны недавние результаты П. Зиновой и М. Казаряна о ее значениях на хордовых диаграммах, граф пересечения которых – полный двудольный, а также гипотеза С. Ландо (теорема П. Закорко) о ее значениях на хордовых диаграммах с полным графом пересечения. В этом же разделе описано продолжение $\mathfrak{gl}(N)$-весовой системы на произвольные перестановки и приведены рекуррентные соотношения для ее вычисления. Раздел 4 посвящен построению продолжений весовых систем с хордовых диаграмм на произвольные вложенные графы. Здесь вводятся дельта-матроиды и описывается структура алгебры Хопфа на пространстве четных бинарных дельта-матроидов. Все определения и классические результаты о весовых системах можно найти в [17], [46]. Мы приводим лишь те определения и утверждения, которые необходимы для формулировки недавних результатов. Обозначения
1. $4$-членные соотношенияВ 1990 г. В. А. Васильев [61] ввел понятие инварианта узлов конечного порядка и поставил в соответствие всякому инварианту узлов порядка не выше $n$ функцию на хордовых диаграммах с $n$ хордами. Он показал, что всякая такая функция удовлетворяет $4$-членным соотношениям. В 1993 г. М. Концевич [39] доказал обратное утверждение: если функция на хордовых диаграммах с $n$ хордами со значениями в поле характеристики $0$ удовлетворяет $4$-членным соотношениям, то она получается конструкцией Васильева из некоторого инварианта узлов порядка не выше $n$. (Как в теореме Васильева, так и в теореме Концевича на функцию накладывается еще одно требование – она должна удовлетворять так называемому одночленному соотношению; однако это требование устраняется переходом к инвариантам оснащенных узлов и практически не влияет на построение теории, поэтому мы не будем упоминать о нем далее.) Функции на хордовых диаграммах, удовлетворяющие $4$-членным соотношениям, называются весовыми системами. Построенный Концевичем универсальный инвариант узлов конечного порядка (интеграл Концевича) позволяет в принципе восстановить инвариант конечного порядка по соответствующей ему весовой системе. Поэтому изучение весовых систем играет ключевую роль в понимании природы инвариантов узлов конечного порядка. Заметим, однако, что явное вычисление интеграла Концевича – трудная задача, еще не имеющая удовлетворительного решения. 1.1. Хордовые диаграммы и $4$-членные соотношенияХордовая диаграмма порядка $n$ – это ориентированная окружность, на которой зафиксировано $2n$ попарно различных точек, разбитых на $n$ пар, рассматриваемая с точностью до сохраняющих ориентацию диффеоморфизмов окружности. Окружность, на которой задана диаграмма, будем также называть петлей Вильсона диаграммы. На приводимых ниже рисунках мы всегда предполагаем, что окружность ориентирована против часовой стрелки. Точки окружности, входящие в одну пару, соединены отрезком прямой или дугой. $4$-членное соотношение определяется хордовой диаграммой и парой хорд с соседними концами в ней. Мы говорим, что функция $f$ на хордовых диаграммах удовлетворяет $4$-членным соотношениям Васильева, если для любой хордовой диаграммы $C$ и любой пары хорд $a$, $b$ с соседними концами в ней выполняется равенство, приведенное на рис. 1. Изображенное на рисунке соотношение означает следующее. Все четыре входящие в него хордовые диаграммы могут иметь дополнительный набор хорд, концы которых расположены на пунктирных дугах окружностей, который одинаков во всех четырех диаграммах. Из четырех концов двух выделенных хорд $a$, $b$ оба конца хорды $b$ и один из концов хорды $a$ фиксированы во всех четырех диаграммах, а второй конец хорды $a$ поочередно занимает все четыре возможных положения рядом с концами хорды $b$; положение второго конца хорды $a$ определяет соответствующую диаграмму в соотношении. Отметим, что нам не важно, предполагать или нет, что хорды $a$ и $b$ пересекаются, – для того чтобы свести случай пересекающихся хорд к случаю непересекающихся, достаточно умножить соотношение с рис. 1 на $-1$. Мы будем записывать $4$-членное соотношение в виде
$$
\begin{equation}
f(C)-f(C'_{ab})=f(\widetilde{C}_{ab})-f(\widetilde{C}'_{ab})
\end{equation}
\tag{1}
$$
и говорить, что хордовая диаграмма $C'_{ab}$ получается из диаграммы $C$ первым движением Васильева на паре хорд $a$, $b$ с соседними концами, диаграмма $\widetilde{C}_{ab}$ – вторым движением Васильева, а диаграмма $\widetilde{C}'_{ab}$ – композицией первого и второго движений; отметим, что первое и второе движение, выполненные на одной и той же паре хорд, коммутируют и порядок, в котором они выполняются, не играет роли. В определение $4$-членного соотношения входит операция вычитания, а в дальнейшем мы планируем умножать хордовые диаграммы. Поэтому чаще всего мы будем рассматривать весовые системы со значениями в некотором коммутативном кольце, специфицируя его в конкретных примерах. 1.2. Графы пересеченийИнварианты графов пересечений хордовых диаграмм служат одним из богатых источников весовых систем. Графом пересечения $g(C)$ хордовой диаграммы $C$ называется простой граф, множество вершин которого взаимно однозначно соответствует множеству хорд диаграммы $C$, и две вершины соединены ребром тогда и только тогда, когда соответствующие им хорды пересекаются. (Две хорды в хордовой диаграмме пересекаются, если их концы перемежаются вдоль окружности; изображаемая на рисунках точка пересечения хорд не является вершиной хордовой диаграммы.) На рис. 2 приведен пример $4$-членного соотношения для хордовой диаграммы и ее графа пересечений. На рисунке изображены лишь сами хордовые диаграммы и графы, указание на значение функции опущено. Всякий граф с не более чем $5$ вершинами является графом пересечений некоторой хордовой диаграммы. Среди графов с 6 вершинами есть два, которые не являются графами пересечений, они изображены на рис. 3. С ростом $n$ доля графов пересечений среди всех простых графов на $n$ вершинах быстро падает. Известны различные полные наборы препятствий к тому, чтобы граф был графом пересечений (см., например, [10]). С другой стороны, некоторые графы пересечений реализуются как графы пересечения нескольких неизоморфных между собой хордовых диаграмм. Рассмотрим, например, граф-цепочку на $n$ вершинах (см. рис. 4). Для $n=5$ имеется три хордовых диаграммы с таким графом пересечения (см. рис. 5). 1.3. $4$-членные соотношения для графов$4$-членные соотношения для графов были введены в [43]. Мы говорим, что инвариант графов $f$ удовлетворяет $4$-членному соотношению, если для любого графа $G$ и любой пары $a$, $b$ его вершин выполняется соотношение
$$
\begin{equation}
f(G)-f(G'_{ab})=f(\widetilde{G}_{ab})-f(\widetilde{G}'_{ab});
\end{equation}
\tag{2}
$$
здесь граф $G'_{ab}$ получается из графа $G$ изменением смежности вершин $a$ и $b$ на противоположную, граф $\widetilde{G}_{ab}$ получается из $G$ заменой примыкания к $a$ всех вершин в $G$, смежных с $b$, на противоположное, а граф $\widetilde{G}'_{ab}$— композицией этих операций (они коммутируют). Замечание. Преобразование $G\mapsto G'_{ab}$ симметрично по $a$ и $b$: $G'_{ab}=G'_{ba}$. В свою очередь, второе движение Васильева для графов, $G\mapsto \widetilde{G}_{ab}$, не симметрично, и граф $\widetilde{G}_{ba}$, как правило, не изоморфен графу $\widetilde{G}_{ba}$. Инварианты графов, удовлетворяющие $4$-членным соотношениям, называются $4$-инвариантами. Как и в случае весовых систем, мы будем предполагать, что $4$-инварианты принимают значения в некотором коммутативном кольце. Простой анализ изменения графа пересечения хордовой диаграммы при применении к ней движений Васильева доказывает следующее утверждение. Теорема 1.1 [43]. Если $f$ – $4$-инвариант графов, то $f\circ g$ – весовая система на хордовых диаграммах. Пример $4$-членного соотношения приведен на рис. 2. Отметим, однако, что, даже если граф $G$ является графом пересечений, это не обязательно выполняется для остальных входящих в соотношение графов. Таким образом, всякий $4$-инвариант определяет весовую систему, а значит, по теореме Концевича, и инвариант узлов. Ниже мы приводим ряд примеров $4$-инвариантов. Следующий поставленный С. К. Ландо вопрос остается открытым уже в течение двух десятилетий: верно ли, что по модулю $4$-членных соотношений для графов любой граф является линейной комбинацией графов пересечений? Компьютерные вычисления (И. А. Дынников, частное сообщение) показывают, что это так для всех графов с не более чем $8$ вершинами. 1.3.1. Хроматический многочленОдним из исторически первых примеров $4$-инварианта простых графов является хроматический многочлен. Пусть $G$ – граф, $V(G)$ – множество его вершин. Хроматическим многочленом $\chi_G(c)$ графа $G$ называется число правильных раскрасок множества вершин $V(G)$ в $c$ цветов, т. е. число отображений $V(G)\to\{1,2,\dots,c\}$ таких, что для любых двух соседних (соединенных ребром) вершин значения отображения на них различны. Как хорошо известно, хроматический многочлен удовлетворяет соотношению удаления-стягивания: для любого графа $G$ и любого ребра $e$ в нем; здесь граф $G'_e$ получается из $G$ удалением ребра $e$, а граф $G''_e$ – стягиванием этого ребра. При стягивании ребра $e$ оно удаляется, его концы становятся одной новой вершиной графа, и если при этом в графе возникают кратные ребра, то они заменяются одним ребром.Доказать соотношение удаления-стягивания для хроматического многочлена несложно: оно соответствует разбиению множества всех правильных раскрасок вершин графа $G'_e$ в $c$ цветов на два непересекающихся подмножества – тех раскрасок, в которых концы ребра $e$ покрашены в различные цвета (это все правильные раскраски вершин графа $G$), и тех, в которых эти концы покрашены в один цвет (они соответствуют правильным раскраскам вершин графа $G''_e$). Поскольку хроматический многочлен дискретного (не имеющего ребер) графа на $n$ вершинах равен $c^n$, соотношение удаления-стягивания доказывает, что для графа $G$ на $n$ вершинах $\chi_G(c)$ действительно является многочленом, степень которого равна $n$, а старший коэффициент равен $1$. Теорема 1.2 [16]. Хроматический многочлен является $4$-инвариантом графов. Действительно, применив соотношение удаления-стягивания для графа $G$ и ребра $e$ с концами $a$, $b$ в нем, мы заключаем, что В свою очередь,
$$
\begin{equation*}
\chi_{\widetilde{G}_{ab}}(c)-\chi_{\widetilde{G}'_{ab}}(c)= -\chi_{\widetilde{G}''_{ab}}(c).
\end{equation*}
\notag
$$
Для завершения доказательства осталось проверить, что естественное отождествление множеств вершин графов $G''_{ab}$ и $\widetilde{G}''_{ab}$ устанавливает изоморфизм этих графов. 1.3.2. Взвешенный хроматический многочлен (симметризованный хроматический многочлен Стенли)Хроматический многочлен – важный инвариант графов, однако его различающая сила не очень велика. Например, хроматический многочлен любого дерева на $n$ вершинах равен $c(c-1)^{n-1}$, тогда как число попарно неизоморфных деревьев на $n$ вершинах очень быстро растет с ростом $n$. Гораздо более тонким инвариантом является взвешенный хроматический многочлен, более известный под названием симметризованного хроматического многочлена Стенли. Для определения взвешенного хроматического многочлена нам потребуется понятие взвешенного графа. Определение 1.3. Взвешенным графом называется простой граф $G$, каждой вершине которого приписано натуральное число – ее вес. Весом взвешенного графа называется сумма весов его вершин. Определение 1.4 [16]. Взвешенным хроматическим многочленом называется инвариант $G\mapsto W_G(q_1,q_2,\dots)$ взвешенных графов, принимающий значения в кольце многочленов от бесконечного набора переменных $q_1,q_2,\dots$ и обладающий следующими свойствами: Теорема 1.5 [16]. Существует единственный инвариант взвешенных графов, обладающий перечисленными выше свойствами. Взвешенный хроматический многочлен $W_G$ взвешенного графа $G$ веса $n$ является квазиоднородным многочленом от переменных $q_1,q_2,\dots$ степени $n$, если считать вес переменной $q_k$ равным $k$ для $k=1,2,\dots$ . Каждый простой граф можно считать взвешенным графом, если положить вес каждой его вершины равным $1$. Таким образом, любой инвариант взвешенных графов задает и инвариант простых графов. Как и при доказательстве теоремы для хроматического многочлена, мы замечаем, что естественное отождествление множеств вершин графов $G''_{ab}$ и $\widetilde{G}''_{ab}$ устанавливает изоморфизм этих графов как взвешенных графов. В 1995 г. Р. Стенли ввел понятие симметризованного хроматического многочлена. Определение 1.7 [60]. Пусть $G$ – простой граф. Назовем раскраской множества вершин $V(G)$ графа $G$ в бесконечный набор цветов отображение Каждой раскраске $\beta$ можно поставить в соответствие моном $x_\beta$ степени $n=|V(G)|$ от переменных $x_1,x_2,\dots$, равный произведению всех значений отображения $\beta$ на вершинах графа $G$. Симметризованным хроматическим многочленом графа $G$ называется бесконечная сумма где раскраска $\beta$ называется правильной, если она переводит любые две соседние вершины в различные элементы множества $X$. По очевидным соображениям симметризованный хроматический многочлен является симметрической функцией от переменных $X$. Гипотеза Стенли утверждает, что симметризованный хроматический многочлен различает все деревья. Она подтверждена для деревьев с количеством вершин вплоть до 29 (см. [32]), что указывает на то, что симметризованный хроматический многочлен $S_G$ является гораздо более тонким инвариантом графов, чем обычный хроматический многочлен $\chi_G$. Будучи симметрическим многочленом от переменных $X$, всякий симметризованный хроматический многочлен может быть выражен как многочлен от любого базиса в пространстве симметрических многочленов. В частности, в качестве такого базиса можно выбрать степенные суммы Выраженный в таком виде симметризованный хроматический многочлен $S_G$ становится конечным квазиоднородным многочленом степени $n=|V(G)|$ от переменных $p_1,p_2,\dots$, если степень переменной $p_k$ положить равной $k$ для $k=1,2,\dots$ . Следующее утверждение устанавливает связь между симметризованным хроматическим многочленом Стенли и взвешенным хроматическим многочленом.Теорема 1.8 [52]. Симметризованный хроматический многочлен Стенли, выраженный через степенные суммы, при подстановке $p_k=(-1)^{n-k}q_k$, $k=1,2,\dots$ , переходит во взвешенный хроматический многочлен; здесь $n=|V(G)|$. Как следствие, симметризованный хроматический многочлен Стенли является $4$-инвариантом графов. В свою очередь, обычный хроматический многочлен является специализацией симметризованного многочлена Стенли – последний переходит в хроматический многочлен при подстановке $p_i=c$ для $i=1,2,3,\dots$ . 1.3.3. Многочлен переплетенийИсходно многочлен переплетений определялся как функция на ориентированных графах, в каждую вершину которых входят и из каждой вершины которых выходят два ребра. Определение появилось в статье [4], посвященной секвенированию ДНК. Впоследствии определение было распространено на произвольные простые графы. Начнем с определения операции поворота. Пусть $G$ – простой граф. Для любой пары смежных вершин $a$, $b$ графа $G$ остальные его вершины разбиваются на четыре класса:
Поворот $G^{ab}$ графа $G$ по ребру $ab$ – это граф, полученный изменением смежности между вершинами первых трех классов в том и только том случае, если они принадлежат разным классам. Многочлен переплетений $L_G(x)$ определяется рекуррентно следующими условиями:
В [4] доказано, что многочлен переплетений корректно определен – результат его вычисления не зависит от порядка, в котором применяются повороты. Непосредственно из определения вытекает, что $L_G(x)$ – многочлен от $x$, степень которого равна $n=|V(G)|$. Эта теорема доказана в [51] и – другим способом – в [38]. 1.3.4. Многочлен переходовМногочлен переходов для $4$-регулярных графов с выделенным ориентированным эйлеровым циклом был введен в [34]. Стянув каждую хорду хордовой диаграммы $C$ в точку, мы превращаем ее в $4$-регулярный граф, в котором петля Вильсона диаграммы задает ориентированный эйлеров цикл. Многочлен перехода такого графа задает тем самым отображение из множества хордовых диаграмм в пространство многочленов. Наоборот, $4$-регулярному графу с выделенным ориентированным эйлеровым циклом однозначно сопоставляется хордовая диаграмма, число хорд в которой равно числу вершин в графе. Эйлеров цикл становится петлей Вильсона хордовой диаграммы, а вершины – хордами в ней. Мы определим многочлен переходов для хордовой диаграммы. Для определения многочлена переходов нам понадобится понятие перехода. Пусть $C$ – хордовая диаграмма. Каждую хорду диаграммы можно заменить ленточкой одним из трех описанных ниже способов. Поставим в соответствие каждому из этих способов одну из греческих букв $\chi$, $\phi$ или $\psi$:
Зафиксируем функцию веса $w\colon\{\phi,\chi,\psi\}\to K$, которая каждой из греческих букв ставит в соответствие элемент коммутативного кольца $K$. Взвешенным многочленом переходов хордовой диаграммы $C$ называется многочлен
$$
\begin{equation*}
T_C(x)=\sum_{s\colon V(C)\to\{\phi,\chi,\psi\}}\, \prod_{v\in V(C)} w(s(v))x^{c(s)-1},
\end{equation*}
\notag
$$
где суммирование ведется по всем состояниям хордовой диаграммы $C$ и через $c(s)$ обозначено количество компонент связности у границы поверхности, полученной из $C$ подклейкой диска к петле Вильсона с приклеенными ленточками. Теорема 1.10 [25]. Выбрав в качестве функции веса функцию $w(\chi)=t$, $w(\phi)=-t$, $w(\psi)=s$, мы превращаем взвешенный многочлен переходов в весовую систему со значениями в кольце многочленов $\mathbb{C}[t,s,x]$. 1.3.5. Косохарактеристический многочленПусть $G$ – простой граф с $n=|V(G)|$ вершинами. Занумеруем вершины графа числами от $1$ до $n$ произвольным образом и поставим в соответствие этой нумерации матрицу смежности графа $G$. Матрица смежности $A(G)$ представляет собой $(n\times n)$-матрицу над полем $\mathbb{F}_2$ из двух элементов, в клетке $(i,j)$ которой стоит $1$, если вершины с номерами $i$ и $j$ соединены ребром, и $0$ в противном случае. В частности, матрица $A(G)$ симметрична, а на ее диагонали стоят нули. Класс изоморфизма графа $G$ однозначно восстанавливается по его матрице смежности. Различные характеристики матрицы смежности – например, ее характеристический многочлен – играют ключевую роль при изучении графов. Определение 1.11. Граф $G$ называется невырожденным (соответственно вырожденным), если его матрица смежности $A(G)$ невырождена (соответственно вырождена) над $\mathbb{F}_2$. Невырожденностью графа называется инвариант графов, принимающий значения в поле $\mathbb{C}$ и равный $1$ для невырожденного графа и $0$ для вырожденного. Матрица смежности любого графа на нечетном числе вершин вырождена, поскольку над полем $\mathbb{F}_2$ она является кососимметрической; таким образом, невырожденность любого графа на нечетном числе вершин равна $0$. Граф на четном числе вершин может быть как вырожденным, так и невырожденным. Мы будем обозначать невырожденность графа $G$ через $\nu(G)$. Действительно, пусть $G$ – граф и $a$, $b$ – его вершины. Занумеруем вершины графа $G$ так, чтобы вершины $a$ и $b$ получили номера 1 и 2 соответственно. Тогда матрица смежности $A(\widetilde{G}_{ab})$ графа $\widetilde{G}_{ab}$ имеет вид где $I_{12}$ – это квадратная $(|V(G)|\times |V(G)|)$-матрица над полем $\mathbb{F}_2$, совпадающая с единичной всюду за исключением клетки $(1,2)$, в которой стоит $1$, а $I_{12}^\top$ – транспонированная к ней. Утверждение леммы следует из того, что матрицы $I_{12}$ и $I_{12}^\top$ невырождены.Определение 1.13 [24]. Косохарактеристическим многочленом графа $G$ называется многочлен где суммирование идет по всем подмножествам $U$ множества $V(G)$ вершин графа, а через $G\big|_U$ обозначен подграф в $G$, индуцированный множеством $U$ его вершин. Косохарактеристический многочлен графа с четным (соответственно нечетным) числом вершин является четной (соответственно нечетной) функцией своего аргумента. Из леммы 1.12 вытекает следующее утверждение. Объясним, почему косохарактеристический многочлен так называют. Пусть $C$ – хордовая диаграмма, $g(C)$ – ее граф пересечения. Ориентируем этот граф следующим образом. Выбрав точку $\alpha$ на окружности диаграммы, не являющуюся концом ни одной из хорд, разрежем окружность в этой точке и развернем ее в прямую, ориентация которой индуцирована ориентацией окружности. Хорды при этом превратятся в полуокружности – дуги, причем две вершины в графе $g(C)$ соединены ребром, если соответствующие им дуги пересекаются. Ориентируем ребро в графе $g(C)$ от той вершины, левый конец соответствующей дуги которой лежит левее левого конца дуги, соответствующей второму концу ребра. Если занумеровать вершины графа в той последовательности, в которой левые концы соответствующих им хорд идут вдоль прямой, то каждое ребро оказывается ориентированным от вершины с меньшим номером к вершине с б\’ольшим номером. Выбранная таким образом ориентация графа пересечения зависит от выбора точки разреза окружности $\alpha$; обозначим соответствующий ориентированный граф через $\vec{g}_\alpha(C)$. Матрица смежности ориентированного графа с $n$ занумерованными вершинами – это целозначная $(n\times n)$-матрица, в клетке $(i,j)$ которой стоит: $0$, если вершины $i$ и $j$ не соединены между собой; $1$, если они соединены стрелкой, ведущей из $i$ в $j$; и $-1$, если имеется стрелка, ведущая из $j$ в $i$. Матрица смежности ориентированного графа является кососимметрической. Предложение 1.15 [24]. Характеристический многочлен матрицы смежности ориентированного графа $\vec{g}_\alpha(C)$ не зависит от выбора точки разреза $\alpha$. Теорема 1.16 [24]. Характеристический многочлен матрицы смежности ориентированного графа пересечений хордовой диаграммы $C$ совпадает с косохарактеристическим многочленом $Q_{g(C)}$ ее графа пересечений. Таким образом, для графа пересечений его косохарактеристический многочлен является характеристическим многочленом ориентированного графа, полученного ориентацией его ребер из некоторого класса возможных ориентаций. Этим и объясняется выбор названия инварианта. Для графа, не являющегося графом пересечений, такой ориентации может не существовать. 2. Алгебра Хопфа графовМногие естественные инварианты графов являются мультипликативными. Значение такого инварианта на графе $G_1\sqcup G_2$, представляющем собой несвязное объединение двух графов, $G_1$ и $G_2$, является произведением его значений на графах $G_1$ и $G_2$. В частности, мультипликативными являются все инварианты, определенные в п. 1.3. Мультипликативность инварианта означает, что для вычисления его значения на данном графе достаточно знать его значения на всех компонентах связности этого графа. В этом разделе мы показываем, что не менее принципиальную роль в изучении структуры инвариантов графов играет их поведение относительно коумножения. Вместе с умножением графов коумножение задает структуру алгебры Хопфа на градуированном пространстве, порожденном простыми графами. На важность этой структуры впервые обратили внимание авторы статьи [35]. Алгебра Хопфа графов является алгеброй многочленов от своих примитивных элементов. Эти примитивные элементы являются линейными комбинациями графов, и для многих мультипликативных инвариантов их значения на примитивных элементах оказываются существенно проще, чем значения на самих графах. Так, значение хроматического многочлена на любом примитивном элементе – это линейный многочлен, тогда как хроматический многочлен простого графа на $n$ вершинах – это многочлен степени $n$. Следуя [18], мы называем полиномиальные инварианты графов, значения которых на примитивных элементах являются линейными многочленами, теневыми инвариантами. Эта терминология связана с тем, что предметом изучения теневого исчисления в комбинаторике являются гомоморфизмы алгебры Хопфа графов в другие алгебры Хопфа [55]. Свойства интегрируемости теневых инвариантов графов описаны в п 2.4. 2.1. Умножение и коумножение графовОбозначим через $\mathcal{G}_n$ векторное пространство над полем $\mathbb{C}$, порожденное всеми графами на $n$ вершинах, $n=0,1,2,\dots$, и пусть
$$
\begin{equation*}
\mathcal{G}=\mathcal{G}_0\oplus\mathcal{G}_1\oplus\mathcal{G}_2\oplus\cdots
\end{equation*}
\notag
$$
– прямая сумма этих пространств. Отметим, что пространство $\mathcal{G}_0$ одномерно и порождено пустым графом. Введем на $\mathcal{G}$ умножение $m\colon\mathcal{G}\otimes\mathcal{G}\to\mathcal{G}$, задав его на образующих формулой и продолжив на линейные комбинации графов по линейности. Это умножение очевидным образом коммутативно и согласовано с градуировкой:
$$
\begin{equation*}
m\colon\mathcal{G}_k\otimes \mathcal{G}_n\to \mathcal{G}_{k+n}
\end{equation*}
\notag
$$
для всех $k$ и $n$. Единицей $e\in\mathcal{G}_0$ этого умножения является пустой граф. Действие коумножения $\mu\colon\mathcal{G}\to\mathcal{G}\otimes\mathcal{G}$ на графе $G$ имеет вид1
$$
\begin{equation*}
\mu\colon G\mapsto \sum_{V(G)=U\sqcup W}G\big|_U\otimes G\big|_W,
\end{equation*}
\notag
$$
где суммирование в правой части идет по всем упорядоченным разбиениям множества вершин $V(G)$ графа $G$ на два непересекающихся подмножества, а через $G\big|_U$ обозначен подграф в $G$, индуцированный подмножеством вершин $U$. Коумножение продолжается на линейные комбинации графов по линейности. Относительно введенного коумножения векторное пространство $\mathcal{G}$ является коалгеброй. Коединицей относительно коумножения $\mu$ является линейное отображение $\epsilon\colon\mathbb{C}\to\mathcal{G}_0$, переводящее $1$ в $e$. 2.2. Примитивные элементы, теорема Милнора–Мура и структура алгебры ХопфаЭлемент $p$ коалгебры с коумножением $\mu$ называется примитивным, если В коалгебре $\mathcal{G}$ граф $K_1\in\mathcal{G}_1$, состоящий из единственной вершины, является примитивным. Никакой другой граф примитивным не является, однако некоторые линейные комбинации графов, в которых участвует более одного графа, примитивны. Так, нетрудно проверить, что примитивным элементом является разность графов $K_2-K_1^2$. Здесь и далее мы обозначаем через $K_n$ полный граф на $n$ вершинах.Всякая алгебра многочленов $\mathbb{C}[y_1,y_2,\dots]$ от конечного или бесконечного числа переменных наделяется структурой коалгебры, если мы будем считать элементы $y_i$ примитивными, $\mu(y_1)=1\otimes y_i+y_i\otimes1$. Коумножение продолжается на мономы и их линейные комбинации (многочлены) таким образом, чтобы оно было кольцевым гомоморфизмом, т. е.
$$
\begin{equation*}
\mu\biggl(\,\prod_{k=1}^n y_{i_k}\biggr)= \prod_{k=1}^n(1\otimes y_{i_k}+y_{i_k}\otimes1).
\end{equation*}
\notag
$$
Определение 2.1. Набор данных $(H,m,\mu,e,\epsilon,S)$, в котором называется алгеброй Хопфа, если Отображение $S$ в алгебре Хопфа называется антиподом. Коумножение $\mu$ называется кокоммутативным, если образ копроизведения $\mu(a)$ для любого элемента $a\in H$ симметричен относительно перестановки тензорных сомножителей в $H\otimes H$. Все рассматриваемые в настоящей статье алгебры Хопфа кокоммутативны. Алгебра многочленов $\mathbb{C}[y_1,y_2,\dots]$ превращается в алгебру Хопфа, если мы определим антипод $S$ как отображение $S\colon y_i\mapsto -y_i$ для всех $i=1,2,\dots$, продолженное на все пространство $H$ как гомоморфизм алгебр. Алгебра Хопфа $H$ может быть градуированной. В этом случае она представляется как прямая сумма конечномерных подпространств: причем умножение и коумножение должны быть согласованы с градуировкой, т. е.
$$
\begin{equation*}
m\colon H_i\otimes H_j\to H_{i+j},\qquad \mu\colon H_n\to\bigoplus_{i+j=n} H_i\otimes H_j.
\end{equation*}
\notag
$$
Градуированная алгебра Хопфа $H$ называется связной, если пространство $H_0$ одномерно. Если задана градуировка (вес) $w(y_i)\in \mathbb{N}$ каждой переменной $y_i$ в алгебре Хопфа многочленов, причем для каждого $n=1,2,3,\dots$ имеется лишь конечное число переменных, вес которых не превосходит $n$, то алгебра Хопфа многочленов $\mathbb{C}[y_1,y_2,\dots]$ становится градуированной. Подпространство градуировки $n$ в ней порождено мономами веса $n$, где вес монома определяется как сумма весов входящих в него переменных. Следующая теорема Милнора–Мура описывает структуру градуированных коммутативных кокоммутативных алгебр Хопфа. Теорема 2.2 [47]. Всякая связная градуированная коммутативная кокоммутативная алгебра Хопфа является полиномиальной алгеброй Хопфа от своих примитивных элементов. Эта теорема означает, что, выбрав базис в каждом подпространстве примитивных элементов $P(H_n)\subset H_n\subset H$ градуировки $n$, мы можем отождествить $H$ с градуированной алгеброй Хопфа многочленов от элементов этих базисов, если положить вес каждого элемента базиса равным его градуировке. Замечание. Теорема Милнора–Мура справедлива и в том случае, если предположить лишь кокоммутативность алгебры Хопфа. Однако мы собираемся использовать ее только в коммутативном случае, в котором предложенная выше формулировка достаточна. Всякому многочлену в алгебре Хопфа многочленов естественным образом ставится в соответствие примитивный элемент – линейная часть этого многочлена. Это отображение из векторного пространства многочленов в векторное пространство их линейных частей является проекцией, т. е. его квадрат совпадает с ним самим. Из теоремы Милнора–Мура 2.2 вытекает, что проекция на подпространство примитивных элементов естественно определена в любой связной градуированной коммутативной кокоммутативной алгебре Хопфа $H$. Мы будем обозначать эту проекцию символом $\pi$: Каждое однородное подпространство $H_n\subset H$ раскладывается в прямую сумму $H_n=P(H_n)\oplus D(H_n)$ подпространства примитивных элементов $P(H_n)$ и ядра $D(H_n)$ проекции $\pi$. Ядро $D(H_n)$ состоит из разложимых элементов, т. е. многочленов от примитивных элементов градуировки, меньшей $n$. Проекцию $\pi$ можно задать следующей формулой. Пусть $\phi,\psi\colon H\to H$ – линейные отображения. Определим произведение свертки $\phi *\psi\colon H\to H$ как линейное отображение, заданное равенством для всех $a\in H$. В градуированных алгебрах Хопфа с помощью произведения свертки можно определять другие операции над линейными отображениями, представимые в виде степенных рядов. Так, если $\phi\colon H\to H$ – линейное отображение алгебры Хопфа $H$ в себя, сохраняющее градуировку, причем $\phi(1)=1$, то определен логарифм отображения $\phi$:
$$
\begin{equation*}
\log\phi=\phi_0-\frac{1}{2}\phi_0*\phi_0+ \frac{1}{3}\phi_0*\phi_0*\phi_0-\cdots,
\end{equation*}
\notag
$$
где $\phi_0\colon H\to H$ – линейное отображение, $\phi_0\colon 1\mapsto0$ и $\phi_0$ совпадает с $\phi$ на всех однородных подпространствах $H_k$ положительной градуировки, $k>0$. Для доказательства этого утверждения достаточно проверить, что для любого примитивного элемента $p$ и для любого монома от примитивных элементов степени выше $1$.В частности, в алгебре Хопфа графов $\mathcal{G}$ проекция $\pi$ на подпространство примитивных элементов, ядром которой является подпространство разложимых элементов, задается следующим равенством [42]:
$$
\begin{equation}
\pi(G)=G-1!\sum_{U_1\sqcup U_2=V(G)}G\big|_{U_1}G\big|_{U_2}+ 2!\sum_{U_1\sqcup U_2\sqcup U_3=V(G)} G\big|_{U_1}G\big|_{U_2}G\big|_{U_3}-\cdots,
\end{equation}
\tag{6}
$$
где суммы берутся по всем неупорядоченным разбиениям множества $V(G)$ вершин графа $G$ на два, три, четыре и т. д. непустых непересекающихся подмножества. Например, $\pi(K_3)=K_3-3K_1K_2+2K_1^3$. Нетрудно проверить, что линейная комбинация $\pi(K_3)$ графов в правой части равенства действительно является примитивным элементом. Проекция $\pi\colon\mathcal{G}\to\mathcal{G}$ переводит несвязные графы в $0$, поскольку они являются разложимыми элементами алгебры Хопфа $\mathcal{G}$. В свою очередь, проекции связных графов с $n$ вершинами образуют базис в пространстве $P(\mathcal{G}_n)$ примитивных элементов градуировки $n$. Тождественное отображение $\operatorname{Id}\colon\mathcal{G}\to \mathcal{G}$ сохраняет $4$-членные соотношения, поэтому то же самое справедливо и для его логарифма $\log \operatorname{Id}=\pi$. Как следствие, формула для проекции работает и в факторалгебре Хопфа $\mathcal{F}$ алгебры $\mathcal{G}$ по идеалу, порожденному $4$-членными соотношениями. Формула для проекции на примитивные элементы в алгебре Хопфа хордовых диаграмм $\mathcal{C}$ выглядит аналогичным образом, только множество вершин $V(G)$ графа $G$ заменяется в ней на множество хорд $V(C)$ хордовой диаграммы $C$. Замечание. Имеется другой – возможно, выглядящий более просто – способ поставить в соответствие графу примитивный элемент в алгебре Хопфа графов (см., например, [3]). А именно, он задается соответствием 2.3. Инварианты графов и структура алгебры ХопфаПоведение многих инвариантов графов, как и инвариантов весовых систем, тесно связано со структурой соответствующей алгебры Хопфа. Типичный пример такого поведения дает хроматический многочлен. Продолжим хроматический многочлен графа до отображения $\chi\colon\mathcal{G}\to\mathbb{C}[c]$ всего пространства $\mathcal{G}$ в пространство многочленов от одной переменной по линейности. Теорема 2.4. Значение хроматического многочлена на любом примитивном элементе алгебры Хопфа $\mathcal{G}$ является линейным многочленом, т. е. мономом степени $1$. В действительности это свойство представляет собой не что иное, как хорошо известное биномиальное свойство хроматического многочлена, которое говорит о том, что отображение $\chi$ является гомоморфизмом алгебр Хопфа. Теорема 2.5. Хроматический многочлен графа $G$ удовлетворяет соотношению где суммирование в правой части идет по всем упорядоченным разложениям множества вершин $V(G)$ графа $G$ на два непересекающихся непустых подмножества. О градуированных гомоморфизмах алгебры Хопфа графов $\mathcal{G}$ в алгебру Хопфа многочленов $\mathbb{C}[p_1,p_2,\dots]$ мы более подробно пишем ниже (см. п. 2.4). Теорема 2.4 означает, в частности, что значение хроматического многочлена на проекции $\pi(G)$ любого графа $G$ на подпространство примитивных является линейным многочленом. В силу формулы (6) и того факта, что свободный член хроматического многочлена любого (непустого) графа равен $0$, мы заключаем, что многочлен $\chi_{\pi(G)}(c)$ совпадает с линейным членом многочлена $\chi_G(c)$ для любого графа $G$. Аналогичным образом ведут себя другие инварианты графов. Теорема 2.6 [24], [38]. Косохарактеристический многочлен графа на всяком примитивном элементе является константой. 2.4. Алгебра Хопфа графов и интегрируемостьВ этом пункте мы описываем связь между инвариантами графов и теорией интегрируемых систем математической физики. Каждому инварианту графов можно поставить в соответствие его усреднение – результат суммирования значений инварианта по всем графам с весом, обратно пропорциональным порядку группы автоморфизмов графа. Если инвариант принимает значения в кольце многочленов от бесконечного числа переменных, то результат его усреднения – формальный ряд от этих переменных. Для графов на поверхностях (вложенных графов) подобные конструкции, как хорошо известно, приводят к решениям интегрируемых иерархий. Однако для абстрактных графов подобное утверждение было доказано лишь недавно ([18], см. также [14]). Оно состоит в том, что результат усреднения по графам теневых инвариантов становится – после подходящей ренормализации переменных – решением иерархии Кадомцева–Петвиашвили. Перечислительные задачи, приводящие к другим решениям этой иерархии, подробно описаны в [37]. 2.4.1. Интегрируемая иерархия КПИнтегрируемая иерархия Кадомцева– Петвиашвили (иерархия КП), история которой восходит к работе [36], представляет собой бесконечную систему нелинейных уравнений в частных производных на неизвестную функцию $F(p_1,p_2,\dots)$ от бесконечного набора переменных. Уравнения иерархии индексируются разбиениями целых чисел $n$, $n\geqslant4$, на две части, ни одна из которых не равна $1$. Первые два уравнения, отвечающие разбиениям числа $4$ и числа $5$ соответственно, имеют вид
$$
\begin{equation*}
\begin{aligned} \, \frac{\partial^2F}{\partial p_2^2}&= \frac{\partial^2F}{\partial p_1\,\partial p_3}- \frac{1}{2}\biggl(\frac{\partial^2F}{\partial p_1^2}\biggr)^2- \frac{1}{12}\,\frac{\partial^4F}{\partial p_1^4}\,, \\ \frac{\partial^2F}{\partial p_2\,\partial p_3}&= \frac{\partial^2F}{\partial p_1\partial p_4}- \frac{\partial^2F}{\partial p_1^2}\, \frac{\partial^2F}{\partial p_1\,\partial p_2}- \frac{1}{6}\,\frac{\partial^4F}{\partial p_1^3\,\partial p_2}\,. \end{aligned}
\end{equation*}
\notag
$$
Левая часть каждого из уравнений соответствует разбиению числа $n$ на две части, ни одна из которых не равна единице, тогда как члены в правой части соответствуют разбиениям того же числа $n$, в которые, однако, единица уже входит. Для $n=6$ имеются два уравнения: они соответствуют разбиениям $2+4=6$ и $3+3=6$, и т. д. Экспоненты решений иерархии КП называются ее $\tau$-функциями. 2.4.2. Теневые инварианты графовОпределение 2.7. Инвариант графов со значениями в кольце многочленов $\mathbb{C}[q_1,q_2,\dots]$ от бесконечного числа переменных называется теневым, если его продолжение по линейности до отображения $\mathcal{G}\to\mathbb{C}[q_1,q_2,\dots]$ является градуированным гомоморфизмом алгебр Хопфа; градуировка в кольце многочленов здесь определяется весом переменных $w(q_i)=i$ для $i=1,2,3,\dots$ . Из определения непосредственно вытекает, что инвариант графов является теневым тогда и только тогда, когда его значение на всяком примитивном элементе порядка $n$ имеет вид $cq_n$ для некоторой константы $c$. Пример 2.8. Примером теневого инварианта является симметризованный хроматический многочлен Стенли. Действительно, согласно теореме 1.5 алгебра Хопфа взвешенных графов по модулю соотношения удаления-стягивания градуированно изоморфна алгебре Хопфа многочленов. Среди других теневых инвариантов и их специализаций, получаемых присвоением переменным $q_i$ конкретных значений, множество хорошо известных инвариантов графов. Пример 2.9. В работе [18] введены многочлены Абеля графов. Всякому остовному лесу в графе $G$ поставим в соответствие моном от переменных $q_i$, равный произведению $iq_i$ по всем деревьям в лесе, где через $i$ обозначено количестве вершин в дереве. Здесь умножение на $i$ отвечает выбору корня в дереве, т. е. такой моном кодирует количество корневых лесов, соответствующих выбранному остовному лесу. Многочлен Абеля $A_G(q_1,q_2,\dots)$ равен сумме таких мономов по всем остовным лесам в $G$. Если $G$ – граф с $n$ вершинами, то $A_G$ – квазиоднородный многочлен степени $n$. Коэффициент при $q_n$ в нем равен сложности графа $G$, умноженной на $n$. (Напомним, что сложностью графа называется количество остовных деревьев в нем.) Если в многочлен Абеля $A_{K_n}$ полного графа на $n$ вершинах подставить $q_i=x$ для всех $i=1,2,\dots,n$, то он превратится в обычный многочлен Абеля [1] $A_n(x)=x(x+n)^{n-1}$. Многочлены $A_n$, $n=0,1,2,\dots$, образуют универсальную биномиальную последовательность многочленов [56]. Теорема 2.10 [18]. Многочлен Абеля является теневым инвариантом графов, т. е. его продолжение по линейности на алгебру Хопфа графов $\mathcal{G}$ является градуированным гомоморфизмом алгебр Хопфа. 2.4.3. Интегрируемость теневых инвариантовТеорема 2.11. Пусть $I$ – теневой инвариант графов со значениями в кольце многочленов от бесконечного набора переменных $q_1,q_2,\dots$ . Определим производящую функцию где суммирование производится по всем классам изоморфизма графов, а через $\operatorname{|Aut(G)|}$ обозначен порядок группы автоморфизма графа $G$. Определим константы $i_n$ как сумму всех коэффициентов при мономе $q_n$:
$$
\begin{equation*}
i_n=n!\sum_{G\text{ связный}} \frac{[q_n]I_G(q_1,q_2,\dots)}{\operatorname{|Aut(G)|}}\,.
\end{equation*}
\notag
$$
Предположим, что постоянная $i_n$ отлична от нуля для всех $n=1,2,\dots$ . Тогда после перешкалирования переменных производящая функция $\mathcal{I}^\circ$ становится следующей линейной комбинацией одночастичных многочленов Шура:Подчеркнем, что после указанного в формулировке теоремы перешкалирования всякий теневой инвариант графов $I$ превращается в одну и ту же производящую функцию. В формуле для $i_n$ суммирование по связным графам можно заменить суммированием по всем графам, поскольку коэффициент при мономе $q_n$ в многочлене $I_G(q_1,q_2,\dots)$ для любого несвязного графа $G$ равен $0$. Поскольку любая линейная комбинация одночастичных многочленов Шура является $\tau$-функцией иерархии КП, справедливо следующее утверждение. Следствие 2.12. Производящая функция $\mathcal{I}$ после перешкалирования переменных, указанного в теореме 2.11, становится $\tau$-функцией иерархии КП. 3. Алгебра Хопфа хордовых диаграмм и весовые системы, отвечающие алгебрам ЛиПространство хордовых диаграмм, как и пространство графов, наделено естественной структурой алгебры Хопфа. В этом разделе мы описываем взаимодействие с этой структурой весовых систем, строящихся по алгебрам Ли. Это большой и очень важный класс весовых систем, связанный с квантовыми инвариантами узлов. Однако, ввиду необходимости проводить вычисления в некоммутативной алгебре, нахождение их значений является вычислительно сложной задачей. Мы напоминаем известные результаты и описываем недавние, позволяющие преодолеть эти сложности и получить явные ответы в случае алгебр Ли $\mathfrak{sl}(2)$ и $\mathfrak{gl}(N)$. 3.1. Структура алгебры Хопфа хордовых диаграммКак и графы, хордовые диаграммы порождают алгебру Хопфа. Существенное отличие этой алгебры Хопфа от алгебры Хопфа графов состоит в том, что она корректно определена только в том случае, если мы рассматриваем пространство хордовых диаграмм, профакторизованное по подпространству, натянутому на $4$-членные соотношения. Без такой факторизации не удается корректно определить произведение хордовых диаграмм (тогда как коумножение определяется естественным образом). Определим произведение $C_1C_2$ хордовых диаграмм $C_1$, $C_2$ как хордовую диаграмму, полученную склейкой их петель Вильсона, разрезанных каждая в произвольной точке, отличной от концов хорд, с сохранением ориентации этих петель (см. рис. 6). Это произведение корректно определено по модулю $4$-членных соотношений. Коумножение переводит хордовую диаграмму $C$ в сумму тензорных произведений хордовых диаграмм, получаемых разбиением множества хорд диаграммы $C$ на два непересекающихся подмножества:
$$
\begin{equation*}
\mu\colon C\mapsto \sum_{I\sqcup J=V(C)}C\big|_I\otimes C\big|_J.
\end{equation*}
\notag
$$
Эти операции превращают векторное пространство
$$
\begin{equation*}
\mathcal{C}=\mathcal{C}_0\oplus\mathcal{C}_1\oplus\mathcal{C}_2\oplus\cdots,
\end{equation*}
\notag
$$
где $\mathcal{C}_n$ – это векторное пространство, порожденное хордовыми диаграммами с $n$ хордами и профакторизованное по $4$-членным соотношениям, в градуированную коммутативную кокоммутативную связную алгебру Хопфа [39]. Отображение, переводящее хордовую диаграмму в ее граф пересечений, продолжается по линейности до гомоморфизма алгебры Хопфа хордовых диаграмм в алгебру Хопфа графов, профакторизованных по $4$-членным соотношениям. Алгебра Хопфа хордовых диаграмм естественно изоморфна алгебре Хопфа диаграмм Якоби. Диаграмма Якоби представляет собой вложенный $3$-регулярный граф с выделенным ориентированным циклом – петлей Вильсона. Градуировка такой диаграммы равна половине числа ее вершин (как нетрудно видеть, количество вершин в $3$-регулярном графе четно). Обозначим через $\mathcal{J}_n$ векторное пространство, порожденное диаграммами Якоби градуировки $n$, профакторизованное по соотношениям Соотношение антисимметрии состоит в том, что изменение ориентации в одной вершине диаграммы переводит ее в ту же диаграмму, но со знаком минус; STU-соотношение изображено на рис. 7. STU-соотношение позволяет представить любую диаграмму Якоби в виде линейной комбинации хордовых диаграмм; это представление и осуществляет изоморфизм между $\mathcal{J}$ и $\mathcal{D}$ [5].Как и в случае хордовых диаграмм, произведение двух диаграмм Якоби задается склейкой с сохранением ориентации их петель Вильсона, разрезанных в произвольных точках, не являющихся вершинами диаграмм-сомножителей. При стирании петли Вильсона в диаграмме Якоби она распадается на компоненты связности (в хордовой диаграмме компоненты связности – это ее хорды). Коумножение переводит диаграмму Якоби в сумму тензорных произведений ее поддиаграмм, получающихся всеми возможными разбиениями множества компонент связности диаграммы на два непересекающихся подмножества (см. рис. 8). В частности, связные диаграммы Якоби являются примитивными элементами в алгебре Хопфа $\mathcal{J}$. Эти примитивные элементы порождают каждое из однородных пространств примитивных элементов $P(\mathcal{J}_n)$ (но, как правило, между ними имеются линейные зависимости). Как следствие, на каждом пространстве $P(\mathcal{J}_n)$, а значит, и на естественно изоморфном ему пространстве $P(\mathcal{C}_n)$ имеется фильтрация
$$
\begin{equation*}
\{0\}\subset P^{(1)}(\mathcal{J}_n)\subset P^{(2)}(\mathcal{J}_n) \subset\dots \subset P^{(n+1)}(\mathcal{J}_n)=P(\mathcal{J}_n),
\end{equation*}
\notag
$$
где подпространство $P^{(k)}(\mathcal{J}_n)$ порождено связными диаграммами Якоби с не более чем $k$ вершинами на петле Вильсона. В [63] высказана гипотеза, согласно которой проекция $\pi(C)$ хордовой диаграммы $C$ с $n$ хордами на подпространство примитивных элементов лежит в подпространстве $P^{(k+1)}(\mathcal{J}_n)$, где $k$ – половина окружения графа пересечения $g(C)$. (Окружением простого графа называется длина наибольшего простого цикла в нем.) Приведенные ниже результаты о значениях весовых систем, отвечающих алгебрам Ли, на проекциях хордовых диаграмм на примитивные подтверждают эту гипотезу. 3.2. Универсальная весовая система, строящаяся по алгебре ЛиКаждой метризованной алгебре Ли ставится в соответствие весовая система, которая принимает значения в центре универсальной обертывающей алгебры этой алгебры Ли. В типичной ситуации этот центр является алгеброй многочленов от нескольких переменных – элементов Казимира алгебры Ли. Ниже мы описываем эту конструкцию и применяем ее к построению эффективных алгоритмов вычисления весовых систем и получению явных формул. 3.2.1. Определение весовой системыУниверсальная конструкция, ставящая в соответствие всякой метризованной алгеброй Ли весовую систему, состоит в следующем. Пусть задана алгебра Ли $\mathfrak{g}$, $[\,\cdot\,{,}\,\cdot\,]$, снабженная $\operatorname{ad}$-инвариантным скалярным произведением (невырожденной симметричной билинейной формой) $\langle\,\cdot\,{,}\,\cdot\,\rangle$; $\operatorname{ad}$-инвариантность означает, что $\langle [a,b],c\rangle=\langle a,[b,c]\rangle$ для любой тройки элементов $a,b,c\in{\mathfrak{g}}$. Выберем произвольный базис $e_1,\dots,e_d$ в ${\mathfrak{g}}$, $d=\dim{\mathfrak{g}}$, и обозначим через $e_1^*,\dots,e_d^*$ элементы двойственного базиса, $\langle e_i,e_j^*\rangle=\delta_{ij}$ для всех $i,j=1,\dots,d$. Пусть теперь задана хордовая диаграмма $C$ с $n$ хордами. Выберем на окружности произвольную точку, отличную от концов хорд. Назовем ее точкой разреза. Далее выберем для каждой хорды $a$ индекс $i_a$ из диапазона $1,\dots,d$ и поставим в соответствие одному концу хорды базисный элемент $e_{i_a}$, а другому – элемент $e_{i_a}^*$ двойственного базиса. Перемножим получившиеся $2n$ элементов алгебры Ли в порядке следования концов хорд по петле Вильсона, начиная от точки разреза. Полученный моном является элементом универсальной обертывающей алгебры $U{\mathfrak{g}}$ данной алгебры Ли. Просуммируем получившиеся мономы по всем $d^n$ возможным способам расстановки индексов на хордах; результат суммирования обозначим через $w_{\mathfrak{g}}(C)\in U{\mathfrak{g}}$. Например, для изображенной на рис. 9 дуговой диаграммы, полученной разрезанием хордовой диаграммы, соответствующий элемент универсальной обертывающей алгебры равен Теорема 3.1 [39]. 1. Элемент $w_{\mathfrak{g}}(C)$ не зависит от выбора базиса $e_1,\dots,e_d$ в алгебре Ли. 2. Элемент $w_{\mathfrak{g}}(C)$ не зависит от выбора точки разреза хордовой диаграммы. 3. Элемент $w_{\mathfrak{g}}(C)$ лежит в центре $ZU{\mathfrak{g}}$ алгебры $U{\mathfrak{g}}$. 4. Инвариант $w_{\mathfrak{g}}$ удовлетворяет $4$-членным соотношениям, т. е. является весовой системой. 5. Построенная весовая система со значениями в коммутативном кольце $ZU{\mathfrak{g}}$ является мультипликативной: $w_{\mathfrak{g}}(C_1C_2)=w_{\mathfrak{g}}(C_1)w_{\mathfrak{g}}(C_2)$ для произвольной пары хордовых диаграмм $C_1$ и $C_2$. 3.2.2. Диаграммы Якоби и значения весовой системы на примитивных элементахОпределение весовой системы, связанной с алгеброй Ли, имеет удобную переформулировку в терминах диаграмм Якоби. На алгебре Ли ${\mathfrak{g}}$ рассмотрим $3$-линейную форму $\omega(a,b,c)=\langle[a,b],c\rangle$, представляющую собой элемент третьей тензорной степени ${\mathfrak{g}}^*\otimes{\mathfrak{g}}^*\otimes{\mathfrak{g}}^*$. Обозначим через $\omega^*\in{\mathfrak{g}}\otimes{\mathfrak{g}}\otimes{\mathfrak{g}}$ соответствующий двойственный тензор, полученный отождествлением ${\mathfrak{g}}$ с двойственным пространством ${\mathfrak{g}}^*$ при помощи скалярного произведения $\langle\,\cdot\,{,}\,\cdot\,\rangle$. Заметим, что тензор $\omega^*$ инвариантен относительно циклических перестановок сомножителей тензорного произведения и меняет знак при перестановке любых двух сомножителей. Пусть теперь дана диаграмма Якоби. С каждой внутренней вершиной диаграммы свяжем тензор $\omega^*$, тензорные сомножители в котором соответствуют выходящим из этой вершины ребрам. Со всяким внутренним ребром диаграммы, т. е. ребром, соединяющим две внутренние вершины, свяжем свертку тензоров, соответствующих концам ребра, при помощи скалярного произведения. В результате такой свертки мы получаем элемент из тензорной степени алгебры Ли ${\mathfrak{g}}$, сомножители в котором нумеруются вершинами диаграммы, лежащими на петле Вильсона. Наконец, применим к полученному тензору гомоморфизм в универсальную обертывающую алгебру $U{\mathfrak{g}}$, переводящий тензорное произведение элементов алгебры Ли в их произведение в алгебре $U{\mathfrak{g}}$ в том порядке, в каком соответствующие вершины идут на окружности при ее обходе против часовой стрелки, начиная от точки разреза. Полученный элемент из $U{\mathfrak{g}}$ есть не что иное, как значение весовой системы $w_{\mathfrak{g}}$ на данной диаграмме Якоби. Приведенное выше определение полезно применять для эффективного вычисления значений весовой системы $w_{\mathfrak{g}}$ на примитивных элементах – связных диаграммах Якоби. Универсальная обертывающая алгебра $U{\mathfrak{g}}$ алгебры Ли ${\mathfrak{g}}$ допускает фильтрацию векторными подпространствами:
$$
\begin{equation*}
U^{(0)}{\mathfrak{g}}\subset U^{(1)}{\mathfrak{g}}\subset U^{(2)}\subset\dots\subset U{\mathfrak{g}},\qquad U^{(0)}{\mathfrak{g}}\cup U^{(1)}{\mathfrak{g}}\cup U^{(2)}{\mathfrak{g}}\cup\dots=U{\mathfrak{g}},
\end{equation*}
\notag
$$
в которой подпространство $U^{(k)}{\mathfrak{g}}$ порождено мономами степени не выше $k$ от элементов алгебры Ли $\mathfrak{g}$. Эта фильтрация, в свою очередь, индуцирует фильтрацию на центре $ZU{\mathfrak{g}}$ универсальной обертывающей алгебры. Как показано в [20], значение весовой системы, отвечающей данной метризованной алгебре Ли ${\mathfrak{g}}$, на примитивном элементе, лежащем в члене фильтрации $P^{(k)}$, введенной в п. 3.1, лежит в $ZU^{(k)}$. 3.3. $\mathfrak{sl}(2)$-весовая системаАлгебра Ли $\mathfrak{sl}(2)$ является простейшей некоммутативной алгеброй Ли с невырожденным $\operatorname{ad}$-инвариантным скалярным произведением. В отличие от более сложных алгебр Ли, для $\mathfrak{sl}(2)$-весовой системы имеется рекуррентное соотношение Чмутова–Варченко, существенно облегчающее ее вычисление. Однако даже с использованием этого соотношения процесс вычисления остается трудоемким и позволяет получить явные ответы лишь в ограниченном количестве ситуаций. В частности, до последнего времени не была известна явная формула для значений $w_{\mathfrak{sl}(2)}$ на хордовых диаграммах, в которых все хорды попарно пересекаются. Мы описываем соответствующий результат П. Закорко, а также результаты П. Зиновой и М. Казаряна о значениях $w_{\mathfrak{sl}(2)}$ на хордовых диаграммах, граф пересечения которых – полный двудольный. Значения весовой системы $w_{\mathfrak{sl}(3)}$ на некоторых хордовых диаграммах с полным двудольным графом пересечений посчитаны в [62]. 3.3.1. Рекуррентное соотношение Чмутова–ВарченкоВесовая система $w_{\mathfrak{g}}$, связанная с данной алгеброй Ли ${\mathfrak{g}}$, принимает значения в коммутативном кольце $ZU{\mathfrak{g}}$, однако отдельные слагаемые выражения для $w_{\mathfrak{g}}(C)$ из определения этой весовой системы лежат в сложной некоммутативной алгебре $U{\mathfrak{g}}$. Поэтому непосредственное применение на практике формулы из определения не слишком эффективно, и для более эффективного вычисления таких весовых систем требуется искать методы, в которых на всех шагах вычислений приходилось бы иметь дело с коммутативным кольцом (скажем, многочленов от некоторого числа переменных). Простейшей некоммутативной алгеброй Ли является алгебра $\mathfrak{sl}(2)$. Эффективный алгоритм вычисления весовой системы для этой алгебры предложили С. В. Чмутов и А. Н. Варченко [20]. Центр универсальной обертывающей алгебры $U\mathfrak{sl}(2)$ является кольцом многочленов от одной образующей – элемента Казимира, которую мы обозначим через $c$. Таким образом, весовая система $w_{\mathfrak{sl}(2)}$ принимает значения в алгебре многочленов от переменной $c$. Значение $w_{\mathfrak{sl}(2)}(C)$ на хордовой диаграмме $C$ с $n$ хордами является многочленом от $c$ степени $n$ со старшим коэффициентом $1$ и нулевым (при $n>0$) свободным членом. Теорема 3.2. Весовая система $w_{\mathfrak{sl}(2)}$, связанная с алгеброй Ли $\mathfrak{sl}(2)$, удовлетворяет следующим соотношениям. Как обычно, в приведенных соотношениях предполагается, что помимо хорд, изображенных на рисунке, во всех диаграммах соотношения присутствуют некоторые дополнительные хорды, одни и те же для всех шести диаграмм. Соотношений Чмутова–Варченко достаточно, чтобы вычислить значение весовой системы на произвольной хордовой диаграмме. Действительно, если к данной диаграмме неприменимы соотношения 1–3, то в ней обязательно найдется хорда, к которой применимо соотношение 4. Все последующие диаграммы являются более простыми, чем первая, в следующем смысле: две диаграммы из правой части имеют меньшее число хорд, чем у диаграмм левой части соотношений; в левой части соотношений у всех четырех диаграмм одинаковое количество хорд, но у последних трех меньше число пар пересекающихся хорд, чем у первой. Из этого следует, что значение весовой системы на любой диаграмме вычисляется однозначно путем последовательного применения соотношений, при этом за конечное число шагов. Соотношения Чмутова–Варченко можно также использовать в качестве аксиоматического определения весовой системы $w_{\mathfrak{sl}(2)}$. В этом подходе равенства теоремы превращаются в определение, а содержательным утверждением становится корректность такого определения, т. е. утверждение о том, что результат вычисления весовой системы не зависит от того порядка, в котором применяются соотношения Чмутова–Варченко. $4$-членные соотношения для построенной функции являются следствием соотношений Чмутова–Варченко, т. е. построенная функция действительно является весовой системой. 3.3.2. $\mathfrak{sl}(2)$-весовая система для графовСледующий результат Чмутова и Ландо является специфическим для алгебры Ли $\mathfrak{sl}(2)$ и связанной с ней весовой системы. Его аналог неверен, скажем, уже для алгебры Ли $\mathfrak{sl}(3)$. Теорема 3.3 [19]. Значение весовой системы $w_{\mathfrak{sl}(2)}$ на всякой хордовой диаграмме однозначно определяется графом пересечений этой диаграммы. Из этой теоремы вытекает, что весовая система $w_{\mathfrak{sl}(2)}$ задает функцию на графах, являющихся графами пересечений. Эта функция обращается в нуль на тех комбинациях графов пересечений, которые входят в $4$-членные соотношения для хордовых диаграмм. Гипотеза 3.4 (С. К. Ландо). Весовая система $w_{\mathfrak{sl}(2)}$ продолжается до функции на графах, удовлетворяющей $4$-членному соотношению для графов. Это продолжение единственно. Существование продолжения означает, что $w_{\mathfrak{sl}(2)}$ обращается в нуль на всякой линейной комбинации графов пересечений, являющейся следствием $4$-членных соотношений для графов (такая линейная комбинация не обязательно является следствием $4$-членных соотношений хордовых диаграмм). Единственность возможного продолжения не является специфической для $w_{\mathfrak{sl}(2)}$. Она связана с вопросом о том, является ли отображение, ставящее в соответствие хордовой диаграмме ее граф пересечений, эпиморфизмом (см. п. 1.3). Справедливость гипотезы 3.4 проверена при помощи компьютера для графов с не более чем $8$ вершинами (Е. Красильников [40]). Отметим, что в построенном Красильниковым продолжении коэффициенты значений $w_{\mathfrak{sl}(2)}$ на некоторых графах с $8$ вершинами, не являющихся графами пересечений, оказываются нецелыми (тогда как соотношения Чмутова–Варченко гарантируют, что на графах пересечений значения весовой системы являются многочленами с целыми коэффициентами). Имеются и другие существенные подтверждения гипотезы 3.4. Например, искомое продолжение известно для старшего коэффициента значения $w_{\mathfrak{sl}(2)}$ в проекции хордовой диаграммы на пространство примитивных. Значение $w_{\mathfrak{sl}(2)}(\pi(C))$ весовой системы $w_{\mathfrak{sl}(2)}$ на проекции хордовой диаграммы $C$ с $2n$ хордами на подпространство примитивных является многочленом степени не выше $n$. Теорема 3.5 [41], [6]. Коэффициент при $c^n$ в значении $w_{\mathfrak{sl}(2)}(\pi(C))$ весовой системы $w_{\mathfrak{sl}(2)}$ на проекции хордовой диаграммы $C$ с $2n$ хордами на подпространство примитивных совпадает со значением $2\log \nu(g(C))$ удвоенного логарифма невырожденности графа пересечений диаграммы (логарифм понимается в смысле операции свертки в алгебре Хопфа). Поскольку невырожденность графов является $4$-инвариантом, мы получаем подтверждение гипотезы. Один из возможных подходов к доказательству гипотезы 3.4 состоит в попытке построить $4$-инвариант графов со значениями в кольце многочленов от одной переменной, значения которого на всех графах пересечений совпадают со значениями $w_{\mathfrak{sl}(2)}$. Для построения такого инварианта очень важно иметь большой набор явных значений $w_{\mathfrak{sl}(2)}$ на графах – эти значения могут показать, какие структурные характеристики графа отражаются в $w_{\mathfrak{sl}(2)}$. Вычисления, результаты которых приводятся ниже, были во многом мотивированы этой задачей. В некоторых отношениях весовая система $w_{\mathfrak{sl}(2)}$ очень похожа на хроматический многочлен графа:
Поэтому было бы интересно узнать, справедлив ли для нее аналог теоремы Ху [33], доказанной им для хроматического многочлена. Задача. Верно ли, что последовательность абсолютных величин коэффициентов значения весовой системы $w_{\mathfrak{sl}(2)}$ на произвольной хордовой диаграмме логарифмически вогнута? В частности, верно ли, что эта последовательность унимодальна, т. е. абсолютные величины коэффициентов сначала возрастают, а потом убывают? Доказательство Ху связывает хроматический многочлен с геометрией алгебраических многообразий, и было бы интересно найти подобную связь для $\mathfrak{sl}(2)$-весовой системы. 3.3.3. Значения $\mathfrak{sl}(2)$-весовой системы на полных графахСоотношения Чмутова–Варченко позволяют не только вычислять значения весовой системы $w_{\mathfrak{sl}(2)}$ на конкретных хордовых диаграммах, но и получать замкнутые формулы для некоторых бесконечных серий хордовых диаграмм. Рассмотрим, в частности, диаграмму $K_n$, образованную $n$ попарно пересекающимися хордами. Граф пересечений такой диаграммы – полный граф на $n$ вершинах. Обычно вычисление значений того или иного инварианта графов на полных графах, благодаря высокой степени симметричности, не представляет какой-либо сложности. Для случая весовой системы $w_{\mathfrak{sl}(2)}$ эта задача оказалась сложной, а ответ в ней – неожиданным. Следующее утверждение было высказано в качестве гипотезы С. К. Ландо около 2015 г. Оно было частично доказано (для линейных членов многочлена) в работе [7]. Теорема 3.6 [65]. Производящий ряд для значений весовой системы алгебры Ли $\mathfrak{sl}(2)$ на полных графах допускает следующее разложение в бесконечную цепную дробь: где Это разложение полезно сравнить с разложением в цепную дробь для производящей функции хроматических многочленов полных графов:
$$
\begin{equation*}
\begin{aligned} \, \sum_{n=0}^\infty \chi_{K_n}(c)t^n&=1+ct+c(c-1)t^2+c(c-1)(c-2)t^3 \\ &\qquad+c(c-1)(c-2)(c-3)t^4+\cdots \\ &=\frac1{1+a_0t+\dfrac{b_1t^2}{1+a_1t+\dfrac{b_2t^2}{1+a_2t+\cdots}}}\,, \end{aligned}
\end{equation*}
\notag
$$
где Доказательство этой теоремы, приведенное в [65], содержит в качестве промежуточного результата также следующий эффективный способ вычисления значений весовой системы из теоремы. Определим линейный оператор $T$, действие которого в пространстве многочленов от переменной $x$ задается равенствами а также для произвольного многочлена $f$.Теорема 3.7 [65]. Значение весовой системы алгебры Ли $\mathfrak{sl}(2)$ на хордовой диаграмме с полным графом пересечений равно значению многочлена $T^n(1)$ в точке $x=c$: Знание значений весовой системы $w_{\mathfrak{sl}(2)}$ на полных графах позволяет легко найти ее значения на их проекциях на подпространство примитивных. Действительно, многочлены от полных графов образуют подалгебру Хопфа в алгебре Хопфа графов $\mathcal{G}$. Порядок группы автоморфизмов полного графа $K_n$ на $n$ вершинах равен $n!$, что позволяет представить экспоненциальную производящую функцию для проекций полных графов на подпространство примитивных как логарифм экспоненциальной производящей функции для полных графов:
$$
\begin{equation*}
\sum_{n=1}^\infty\pi(K_n)\,\frac{t^n}{n!}= \log \sum_{n=0}^\infty K_n\frac{t^n}{n!}\,.
\end{equation*}
\notag
$$
Применив $w_{\mathfrak{sl}(2)}$ к обеим частям равенства и подставив известные нам значения $w_{\mathfrak{sl}(2)}(K_n)$, мы получаем начальные члены разложения:
$$
\begin{equation*}
\begin{aligned} \, \sum_{n=1}^\infty w_{\mathfrak{sl}(2)}(\pi(K_n))\,\frac{t^n}{n!}&= c\,\frac{t}{1!}-c\,\frac{t^2}{2!}+2c\,\frac{t^3}{3!}+ (2c^2-7c)\frac{t^4}{4!}-(24c^2-38c)\frac{t^5}{5!} \\ &\qquad-(16c^3-284c^2+295c)\frac{t^6}{6!}+\cdots\,. \end{aligned}
\end{equation*}
\notag
$$
3.3.4. Алгебра долейОпределение 3.8. Долей с $n$ хордами называется упорядоченная пара ориентированных интервалов, на которых зафиксировано $2n$ попарно различных точек, разбитых на $n$ пар, рассматриваемая с точностью до сохраняющих ориентацию диффеоморфизмов каждого из интервалов. В качестве интервалов часто берутся две дуги петли Вильсона. Таким образом, доля – это часть хордовой диаграммы, образованная хордами, оба конца каждой из которых принадлежат данным двум дугам окружности. Если некоторая пара дуг хордовой диаграммы $C$ образует долю, то дополнение к ней также образует долю. Эту хордовую диаграмму мы будем называть джойном двух долей и обозначать через $S_1\mathbin{\#}S_2$ (см. рис. 11). В джойне конец первого интервала доли $S_1$ склеивается с началом первого интервала доли $S_2$, конец первого интервала доли $S_2$ – с началом второго интервала доли $S_1$, конец второго интервала доли $S_1$ – с началом второго интервала доли $S_2$ и конец второго интервала доли $S_2$ – с началом первого интервала доли $S_1$. Операция взятия джойна некоммутативна. Каждой доле $S$ можно поставить в соответствие хордовую диаграмму, соединив конец каждого из двух интервалов с началом второго интервала и объединив тем самым оба интервала в петлю Вильсона. Мы будем обозначать эту хордовую диаграмму через $\overline{S}$ и называть ее замыканием доли $S$. Граф пересечений $g(\overline{S})$ будем называть также графом пересечений доли $S$ и обозначать через $g(S)$. Две доли можно умножить, соединив их несущие интервалы с совпадающими номерами (см. рис. 12). Это умножение некоммутативно. Доли являются частным случаем диаграмм связок (см. [17; п. 5.10]). В работе [26] построены примеры долей с необратимой ориентацией. Для доказательства необратимости там используется универсальная весовая система, связанная с алгеброй Ли $\mathfrak{gl}(4)$. На пространстве, порожденном классами изоморфизмов долей, можно ввести соотношения, аналогичные соотношениям Чмутова–Варченко из теоремы 3.2. Действительно, в $6$-членном соотношении мы можем предполагать, что все участвующие в нем диаграммы являются долями. Есть, однако, небольшая тонкость в определении аналогов соотношений 2 и 3 из теоремы. А именно, предположим, что доля $S$ получена из доли $S'$ добавлением одной хорды, оба конца которой лежат на интервале с номером $i$, $i\in\{1,2\}$, и которая пересекается не более чем с одной из оставшихся хорд. Тогда соотношения для долей имеют вид в случае, когда данная хорда не пересекается ни с одной из оставшихся хорд или пересекается с единственной из оставшихся хорд соответственно. Элементы $c_1$, $c_2$ определены ниже в предложении 3.9.Обозначим через $\mathcal{S}$ факторпространство пространства, порожденного всевозможными долями, по подпространству, порожденному $6$-членными соотношениями и соотношениями (8). Это факторпространство наделено структурой алгебры, индуцированной операцией умножения долей. Отметим, что алгебра $\mathcal{S}$ лишь фильтрована, но не градуирована – $6$-членные соотношения неоднородны. Предложение 3.9. Алгебра $\mathcal{S}$ коммутативна и является алгеброй многочленов от трех образующих $c_1$, $c_2$, $x$, изображенных на рис. 13. Предложение утверждает, что при помощи $6$-членных соотношений и соотношений (8) всякую долю можно однозначно представить в виде линейной комбинации долей $1,x,x^2,x^3,\dots$, где доля $x^n$ образована $n$ параллельными хордами с концами на разных интервалах. Коэффициенты линейной комбинации – многочлены от $c_1$ и $c_2$. Одной из причин, по которой введение алгебры $\mathcal{S}$ оказывается полезным, является следующее наблюдение. Предложение 3.10. Предположим, что две доли (или две линейные комбинации долей) $S_1$ и $S_2$ представляют один и тот же элемент в алгебре $\mathcal{S}$. Тогда для произвольной дополнительной доли $R$ значения весовой системы алгебры Ли $\mathfrak{sl}(2)$ на хордовых диаграммах, полученных джойном долей $S_1$ и $S_2$ соответственно с $R$, совпадают: В качестве дополнительной доли $R$ можно взять, например, набор из $n$ параллельных хорд с концами на разных дугах или набор из $n$ попарно пересекающихся хорд с концами на разных дугах. 3.3.5. Значения $\mathfrak{sl}(2)$-весовой системы на полных двудольных графахЕще один обширный класс хордовых диаграмм, для значений $w_{\mathfrak{sl}(2)}$ на которых удается получить явные формулы, это хордовые диаграммы с полным двудольным графом пересечений. Обозначим через $K_{m,n}$ хордовую диаграмму, образованную $m$ параллельными горизонтальными хордами и $n$ параллельными вертикальными хордами. Граф пересечений такой диаграммы – это полный двудольный граф с $m$ вершинами в одной доле и $n$ вершинами в другой доле. Эквивалентным образом, $K_{m,n}$ является джойном двух долей, образованных соответственно $m$ и $n$ параллельными хордами с концами на разных дугах. Для каждого $m=0,1,2,3,\dots$ рассмотрим производящую функцию для значений весовой системы $w_{\mathfrak{sl}(2)}$ на диаграммах $K_{m,n}$:
$$
\begin{equation*}
G_m=G_m(c,t)=\sum_{n=0}^\infty w_{\mathfrak{sl}(2)}(K_{m,n})t^n.
\end{equation*}
\notag
$$
Теорема 3.11. Производящие функции $G_{m}$ удовлетворяют соотношению в котором коэффициенты $s_{i,m}$ задаются производящим рядом Заметим, что $G_m$ входит также и в правую часть соотношения теоремы, с коэффициентом $s_{m,m}=c-m(m-1)/2$. Перенеся соответствующее слагаемое в левую часть равенства теоремы, мы можем переписать его в виде более явного рекуррентного соотношения
$$
\begin{equation*}
G_m=\frac{1}{1-s_{m,m} t}\biggl(c^m+t\sum_{i=0}^{m-1}s_{i,m} G_i\biggr).
\end{equation*}
\notag
$$
Отсюда по индукции выводится следующее утверждение. Следствие 3.12. Производящий ряд $G_m$ представляется в виде конечной линейной комбинации геометрических прогрессий Коэффициенты этих геометрических прогрессий – многочлены от $c$. Так, при малых $m$ мы получаем
$$
\begin{equation*}
\begin{aligned} \, G_0&=\frac{1}{1-ct}\,, \\ G_1&=\frac{c}{1-(c-1)t}\,, \\ G_2&=\frac{c^2}{3 (1-ct)}+\frac{c}{2\,(1-(c-1)t)}+ \frac{c(4 c-3)}{6(1-(c-3)t)}\,, \\ G_3&=\frac{c^2}{6(1-ct)}+\frac{c(3c^2-2c+2)}{5(1-(c-1)t)}+ \frac{c(4 c-3)}{3(1-(c-3)t)}+\frac{c(c-2)(4 c-3)}{10(1-(c-6)t)}\,. \end{aligned}
\end{equation*}
\notag
$$
Это утверждение допускает следующее обобщение. Для произвольной доли $S$ обозначим через $(S,n)$ хордовую диаграмму, являющуюся джойном доли $S$ и доли $x^n$, состоящей из $n$ параллельных хорд. Введем производящую функцию
$$
\begin{equation*}
f_S=\sum_{n=0}^\infty w_{\mathfrak{sl}(2)}((S,n))t^n.
\end{equation*}
\notag
$$
Следствие 3.13. Производящая функция $f_S$ представляется в виде конечной линейной комбинации геометрических прогрессий вида где $m$ – количество тех хорд доли $S$, концы которых лежат на разных дугах. Коэффициенты этих геометрических прогрессий – многочлены от $c$. Действительно, если доля $S$ представляется по модулю $6$-членных соотношений и соотношений (8) в виде линейной комбинации базисных долей $x^k$, то ряд $f_S$ выражается в виде линейной комбинации с теми же коэффициентами рядов
$$
\begin{equation*}
\sum_{n=0}^\infty w_{\mathfrak{sl}(2)}((x^k,n))t^n= \sum_{n=0}^\infty w_{\mathfrak{sl}(2)}(K_{k,n})t^n=G_k,
\end{equation*}
\notag
$$
т. е. и мы можем применить предыдущее следствие. Как и в случае полных графов, многочлены от полных двудольных графов также образуют подалгебру Хопфа в $\mathcal{G}$. Для значений весовой системы $w_{\mathfrak{sl}(2)}$ на проекциях полных двудольных графов на подпространство примитивных имеются формулы, обобщающие формулу для логарифма экспоненциальной производящей функции для полных графов (см. подробности в [31]). 3.3.6. Значения $\mathfrak{sl}(2)$-весовой системы на графах, не являющихся графами пересеченийНе всякий граф является графом пересечений некоторой хордовой диаграммы, но при помощи $4$-членных соотношений для графов можно попытаться выразить данный граф через графы пересечений и продолжить тем самым на него значения весовой системы $w_{\mathfrak{sl}(2)}$. Формулы предыдущего пункта позволяют получить значения такого продолжения не только для отдельных графов, но и для бесконечных серий графов. Для произвольного графа $G$ обозначим через $(G,n)$ его связную сумму с $n$ изолированными вершинами, т. е. граф, полученный из $G$ добавлением $n$ вершин, а также всех ребер, соединяющих добавленные вершины с каждой из вершин исходного графа. Возьмем в качестве $G$ граф $C_5$, являющийся циклом на пяти вершинах. При $n\geqslant1$ граф $(C_5,n)$ не является графом пересечений. Предложение 3.14 [30]. Предположим, что гипотеза 3.4 о продолжимости весовой системы $w_{\mathfrak{sl}(2)}$ на пространство графов верна. Тогда значения продолженной весовой системы на графах $(C_5,n)$ задаются производящей функцией Для доказательства применим $4$-членное соотношение для графов (см. рис. 14): Каждый из трех графов в правой части является графом пересечений. Более того, каждый из них является графом пересечений хордовой диаграммы вида $(S,n)$ для некоторой доли $S$ – см. рис. 15.Применив рассуждения предыдущего пункта, мы можем выразить каждую из полученных долей через базисные $x^m$, $m=0,1,\dots,5$, и тем самым выразить производящую функцию для графов $(C_5,n)$ через соответствующие производящие функции для двудольных графов. 3.4. $\mathfrak{gl}(N)$-весовая системаДо недавнего времени рекурсии, аналогичной рекурсии Чмутова–Варченко, для алгебр Ли, отличных от $\mathfrak{sl}(2)$, не было известно, и единственным, по существу, способом вычисления значений весовой системы, связанной с той или иной алгеброй Ли, было прямолинейное применение определения, что чрезвычайно трудоемко. Здесь мы приводим результаты недавней работы [63], посвященной вычислению весовой системы для алгебр Ли $\mathfrak{gl}(N)$. В работе [64] эти результаты распространены на весовые системы, отвечающие супералгебрам Ли $\mathfrak{gl}(m|n)$. В качестве базиса в алгебре Ли $\mathfrak{gl}(N)$ можно взять матричные единицы $E_{ij}$, имеющие единицу на пересечении $i$-й строки и $j$-го столбца и нули в остальных клетках. Коммутатор двух матричных единиц имеет следующий вид: $[E_{ij},E_{kl}]=\delta_{jk}E_{il}-\delta_{il}E_{jk}$. Стандартное инвариантное скалярное произведение задается равенством $\langle x,y\rangle=\operatorname{Tr}(xy)$, и двойственный базис относительно этого скалярного произведения дается матрицами $E_{ij}^*=E_{ji}$. Центр $ZU \mathfrak{gl}(N)$ свободно порожден элементами Казимира $C_1,C_2,\dots,C_N$, где
$$
\begin{equation*}
C_{1}=\sum_{i=1}^NE_{ii},\qquad C_{2}=\sum_{i,j=1}^NE_{ij}E_{ji}
\end{equation*}
\notag
$$
и, более общим образом,
$$
\begin{equation*}
C_{k}=\sum_{i_1,i_2,\dots,i_k=1}^NE_{i_1i_2}E_{i_2i_3}\cdots E_{i_k i_1}.
\end{equation*}
\notag
$$
Так же определяются элементы Казимира с номерами большими, чем $N$. Они тоже лежат в центре, но выражаются полиномиально через элементы Казимира с номерами, не превышающими $N$. Таким образом, значение весовой системы, отвечающей алгебре Ли $\mathfrak{gl}(N)$, – многочлен от элементов Казимира. Например, нетрудно видеть, что для хордовой диаграммы $K_1$, состоящей из единственной хорды, мы имеем $w_{\mathfrak{gl}(N)}(K_1)=C_2$. Теорема 3.15 [63]. Имеется универсальная весовая система, обозначаемая через $w_{\mathfrak{gl}}$ и принимающая значения в кольце многочленов бесконечного числа образующих $N,C_1,C_2,\dots$, значение которой для всякого натурального $N$ совпадает со значением весовой системы алгебры Ли $\mathfrak{gl}(N)$. Нетрудно увидеть, что для всякой хордовой диаграммы $C$ с $n$ хордами значение весовой системы $w_{\mathfrak{gl}(N)}(C)$ при $N\geqslant n$ является многочленом от $C_1,\dots,C_{n}$. Теорема утверждает, что коэффициенты этого многочлена зависят от $N$ полиномиально. Более того, полученная универсальная формула для $w_{\mathfrak{gl}(N)}(C)$ справедлива и при $N< n$. Ниже мы определяем весовую систему $w_{\mathfrak{gl}}$ для произвольных перестановок и приводим рекуррентную формулу для ее вычисления. 3.4.1. $\mathfrak{gl}(N)$-весовая система на перестановках и рекуррентные соотношенияПусть $m$ – натуральное число и $S_m$ – группа перестановок элементов $\{1,2,\dots,m\}$; для произвольной перестановки $\sigma\in S_m$ положим
$$
\begin{equation*}
w_{\mathfrak{gl}(N)}(\sigma)=\sum_{i_1,\dots,i_m=1}^NE_{i_1i_{\sigma(1)}} E_{i_2i_{\sigma(2)}}\cdots E_{i_mi_{\sigma(m)}}\in U\mathfrak{gl}(N).
\end{equation*}
\notag
$$
Построенный элемент лежит, в действительности, в центре $ZU\mathfrak{gl}(N)$. Кроме того, он инвариантен относительно сопряжения стандартным длинным циклом,
$$
\begin{equation*}
w_{\mathfrak{gl}(N)}(\sigma)=\sum_{i_1,\dots,i_m=1}^N E_{i_2i_{\sigma(2)}} \cdots E_{i_mi_{\sigma(m)}}E_{i_1i_{\sigma(1)}}.
\end{equation*}
\notag
$$
Например, элемент Казимира $C_m$ соответствует циклической перестановке $1\mapsto2\mapsto\cdots\mapsto m\mapsto 1$. С другой стороны, всякая дуговая диаграмма с $n$ дугами может рассматриваться как инволюция без неподвижных точек на множестве из $m=2n$ элементов. Значение $w_{\mathfrak{gl}(N)}$ на перестановке, задаваемой этой инволюцией, равно значению $\mathfrak{gl}(N)$-весовой системы на соответствующей хордовой диаграмме. Например, для хордовой диаграммы $K_n$ мы имеем
$$
\begin{equation*}
w_{\mathfrak{gl}(N)}(K_n)= w_{\mathfrak{gl}(N)}((1\, n{+}1)(2\, n{+}2)\cdots(n\, 2n)).
\end{equation*}
\notag
$$
Всякая перестановка представляется ориентированным графом. Его вершины соответствуют переставляемым элементам. Они располагаются на ориентированной окружности и упорядочены циклически в порядке обхода окружности против часовой стрелки. Ориентированные ребра графа показывают действие перестановки (так что каждая вершина имеет одно входящее и одно выходящее ребро). Ориентированный граф $G(\sigma)$ состоит из этих $m$ вершин и $m$ ребер – см., например, рис. 16 (окружность, на которой расположены вершины графа, представлена на рисунке горизонтальной прямой). Теорема 3.17 [63]. Значение весовой системы $w_{\mathfrak{gl}(N)}$ на перестановке обладает следующими свойствами. (a)$w_{\mathfrak{gl}(N)}$ мультипликативна относительно связной суммы (конкатенации) перестановок. Отсюда следует, в частности, что для пустого графа (с нулевым количеством вершин) значение $w_{\mathfrak{gl}(N)}$ равно $1$. (b) Для стандартной циклической перестановки (с циклическим порядком на множестве переставляемых элементов, согласованным с перестановкой) значение $w_{\mathfrak{gl}(N)}$ равно соответствующему элементу Казимира:
$$
\begin{equation*}
w_{\mathfrak{gl}(N)}(1\mapsto2\mapsto\cdots\mapsto m\mapsto 1)=C_m.
\end{equation*}
\notag
$$
(c) Для графа произвольной перестановки $\sigma\in S_m$ и для любых двух соседних элементов $k$, $k+1$ из множества вершин $\{1,2,\dots,m\}$ инвариант $w_{\mathfrak{gl}(N)}$ удовлетворяет равенству, представленному на рис. 17. На графах левой части равенства изображены две соседние вершины и инцидентные им ребра. На графах в правой части эти две вершины заменены одной. Все остальные вершины и (полу)ребра одни и те же для всех четырех графов, участвующих в соотношении на рис. 17. В исключительном случае $\sigma(k+1)=k$ соотношение имеет вид, указанный на рис. 18. Применяя соотношения теоремы, всякий граф можно свести к моному от образующих $C_k$ (связной сумме независимых циклов) по модулю графов с меньшим числом вершин. Это приводит к индуктивному вычислению инварианта $w_{\mathfrak{gl}(N)}$. Следствие 3.18. Значение $w_{\mathfrak{gl}(N)}$ на всякой перестановке лежит в центре $ZU\mathfrak{gl}(N)$ универсальной обертывающей алгебры и является многочленом от $N,C_1,C_2,\dots$, причем этот многочлен универсален (один и тот же для всех $\mathfrak{gl}(N)$). Отображение, ставящее в соответствие перестановке этот универсальный многочлен, мы обозначим через $w_{\mathfrak{gl}}$. Теорема 3.15 является специализацией следствия 3.18 для случая, когда перестановка – инволюция без неподвижных точек. В качестве иллюстрации приведем значения весовой системы $w_{\mathfrak{gl}}$ на хордовых диаграммах $K_n$ для нескольких первых значений $n$:
$$
\begin{equation*}
\begin{aligned} \, w_{\mathfrak{gl}}(K_2)&=C_1^2+C_2^2-N\,C_2, \\ w_{\mathfrak{gl}}(K_3)&=C_2^3+3 C_1^2 C_2+2 C_2 N^2+(-2 C_1^2-3 C_2^2) N, \\ w_{\mathfrak{gl}}(K_4)&=3 C_1^4-4 C_1^3+6 C_2^2 C_1^2+2 C_1^2- 8 C_3 C_1+C_2^4+6 C_2^2 \\ &\qquad+(-6 C_2^3-14 C_1^2 C_2+6 C_1 C_2-2 C_2+2 C_4) N \\ &\qquad+(6 C_1^2+11 C_2^2-2 C_3) N^2-6 C_2 N^3, \\ w_{\mathfrak{gl}}(K_5)&=C_2^5+10 C_1^2 C_2^3+30 C_2^3+15 C_1^4 C_2- 20 C_1^3 C_2+10 C_1^2 C_2-40 C_1 C_3 C_2 \\ &\qquad+(-20 C_1^4+48 C_1^3-50 C_2^2 C_1^2-32 C_1^2 \\ &\qquad\qquad\qquad\;\;+30 C_2^2 C_1+96 C_3 C_1-10 C_2^4-82 C_2^2+ 10 C_2 C_4) N \\ &\qquad+(35 C_2^3+70 C_1^2 C_2-72 C_1 C_2-10 C_3 C_2+32 C_2-24 C_4) N^2 \\ &\qquad+(-24 C_1^2-50 C_2^2+24 C_3) N^3+24 C_2 N^4. \end{aligned}
\end{equation*}
\notag
$$
Как и в случае $\mathfrak{sl}(2)$, значения весовой системы $w_{\mathfrak{gl}(N)}$ на проекциях полных графов на подпространство примитивных вычисляются путем логарифмирования соответствующей экспоненциальной производящей функции. 3.4.2. Вычисление $\mathfrak{gl}(N)$-весовой системы с помощью изоморфизма Хариш– ЧандрыВ этом пункте мы приводим еще один способ, изложенный в [63], для вычисления весовой системы $\mathfrak{gl}(N)$. Алгебра $U\mathfrak{gl}(N)$ допускает разложение в прямую сумму:
$$
\begin{equation}
U\mathfrak{gl}(N)=(\mathfrak{n}_-\,U\mathfrak{gl}(N)+ U\mathfrak{gl}(N)\,\mathfrak{n}_+)\oplus U\mathfrak{h},
\end{equation}
\tag{9}
$$
где $\mathfrak{n}_-$, $\mathfrak{h}$ и $\mathfrak{n}_+$ – подалгебры нижнетреугольных, диагональных и верхнетреугольных матриц в $\mathfrak{gl}(N)$ соответственно. Определение 3.19. Проекцией Хариш–Чандры называется линейная проекция на второе слагаемое в (9): Теорема 3.20 (изоморфизм Хариш–Чандры [54]). Ограничение проекции Хариш-Чандры на центр $ZU\mathfrak{gl}(N)$ является инъективным гомоморфизмом коммутативных алгебр, и его изоморфный образ состоит из симметрических функций от сдвинутых матричных единиц $x_i=E_{ii}+N-i$, $i=1,\dots,N$. Кольцо сдвинутых симметрических функций подробно изучено в [53]. Изоморфизм теоремы позволяет отождествить область значений $\mathbb{C}[C_1,C_2,\dots,C_N]$ весовой системы $w_{\mathfrak{gl}(N)}$ с кольцом симметрических функций от образующих $x_1,\dots,x_N$. Явное выражение для образующих $C_k$ при этом изоморфизме определяется соотношением
$$
\begin{equation*}
1-Nu-\sum_{k=1}^\infty\phi(C_k)u^{k+1}= \prod_{i=1}^N\frac{1-(x_i+1)u}{1-x_iu}\,.
\end{equation*}
\notag
$$
Вычисление значения весовой системы $\mathfrak{gl}(N)$ на заданной хордовой диаграмме при помощи изоморфизма Хариш–Чандры состоит в том, чтобы применить проекцию $\phi$ к каждому моному, входящему в определение весовой системы, поочередно и получить тем самым индивидуальный вклад этого монома в значение весовой системы. Суммарный вклад мономов подсчитывается суммированием элементов коммутативного кольца. Это позволяет существенно сократить требуемый объем оперативной памяти компьютера для практических вычислений. Тем не менее временн\’ые затраты растут довольно быстро с ростом $N$, поскольку растет также количество мономов, входящих в определение весовой системы, равное $N^{2n}$ для хордовой диаграммы с $n$ хордами. Следует отметить, что проекция Хариш–Чандры применима для вычисления весовой системы $w_{\mathfrak{gl}(N)}$ при фиксированном $N$ и универсальная (полиномиальная) зависимость от $N$ для значений весовой системы из этого метода не видна. 3.5. $\mathfrak{sl}(N)$-весовая системаАлгебра Ли $\mathfrak{gl}(N)$ не является простой, она представляет собой прямую сумму простой алгебры Ли $\mathfrak{sl}(N)$ и одномерной абелевой. Соответственно, центр универсальной обертывающей алгебры Ли $\mathfrak{gl}(N)$ является тензорным произведением центров универсальных обертывающих алгебр Ли $\mathfrak{sl}(N)$ и $\mathbb{C}$, т. е. его можно отождествить с кольцом многочленов от $C_1$ с коэффициентами в $ZU\mathfrak{sl}(N)$. Поэтому значения весовой системы $w_{\mathfrak{sl}(N)}$ можно получить из значений $w_{\mathfrak{gl}(N)}$, положив $C_1=0$ и $C_k=\widetilde C_k$, $k\geqslant2$, где $\widetilde C_k$ – проекция соответствующего элемента Казимира из $ZU\mathfrak{gl}(N)$ в $ZU\mathfrak{sl}(N)$. Результат такой подстановки – многочлен от $\widetilde C_2,\widetilde C_3,\dots$ . Более явно, положим
$$
\begin{equation*}
\widetilde E_{ij}=E_{ij}-\delta_{ij}N^{-1}C_1\in \mathfrak{sl}(N)\subset\mathfrak{gl}(N).
\end{equation*}
\notag
$$
Тогда
$$
\begin{equation*}
\widetilde C_{k}=\sum_{i_1,i_2,\dots,i_k=1}^N\widetilde E_{i_1i_2} \widetilde E_{i_2i_3}\cdots \widetilde E_{i_k i_1}= \sum_{i=0}^k\begin{pmatrix} k \\ i\end{pmatrix}(-1)^iC_{k-i} \biggl(\frac{C_1}{N}\biggr)^i,
\end{equation*}
\notag
$$
где мы полагаем $C_0=N$, и
$$
\begin{equation*}
ZU\mathfrak{sl}(N)=\mathbb{C}[\widetilde C_2,\dots,\widetilde C_N]\subset ZU\mathfrak{gl}(N)=\mathbb{C}[C_1,\dots,C_N].
\end{equation*}
\notag
$$
Альтернативным образом, вычислять $w_{\mathfrak{sl}(N)}$ можно, продолжив этот инвариант на перестановки при помощи аналогичных случаю $\mathfrak{gl}(N)$ рекуррентных соотношений, заменив в них $w_{\mathfrak{gl}(N)}$ на $w_{\mathfrak{sl}(N)}$, $C_k$ на $\widetilde C_k$ и положив $\widetilde C_1=0$. Аналогично случаю весовой системы $w_{\mathfrak{gl}}$, результат представляется в виде универсального многочлена от $N$, $\widetilde C_2,\widetilde C_3,\dots$, который мы будем обозначать через $w_{\mathfrak{sl}}$. Поскольку мы имеем дело с меньшим числом образующих, вычисления для $w_{\mathfrak{sl}(N)}$ более эффективны, а ответ получается несколько более компактным. Например, для хордовых диаграмм $K_n$ мы получаем
$$
\begin{equation*}
\begin{aligned} \, w_{\mathfrak{sl}}(K_2)&=\widetilde C_2^2-\widetilde C_2 N, \\ w_{\mathfrak{sl}}(K_3)&=\widetilde C_2^3-3 \widetilde C_2^2 N+ 2 \widetilde C_2 N^2, \\ w_{\mathfrak{sl}}(K_4)&=\widetilde C_2^4+6 \widetilde C_2^2- 2 (3 \widetilde C_2^3+\widetilde C_2-\widetilde C_4) N+ (11 \widetilde C_2^2-2 \widetilde C_3) N^2-6 \widetilde C_2 N^3, \\ w_{\mathfrak{sl}}(K_5)&=\widetilde C_2^5+30 \widetilde C_2^3- 2 (5 \widetilde C_2^4+41 \widetilde C_2^2-5 \widetilde C_4 \widetilde C_2) N \\ &\qquad+(35 \widetilde C_2^3-10 \widetilde C_3 \widetilde C_2+ 32 \widetilde C_2-24 \widetilde C_4) N^2 \\ &\qquad-2 (25 \widetilde C_2^2-12 \widetilde C_3) N^3+24 \widetilde C_2 N^4, \\ w_{\mathfrak{sl}}(K_6)&=\widetilde C_2^6+90 \widetilde C_2^4+ 264 \widetilde C_2^2-240 \widetilde C_4 \widetilde C_2+ 160 \widetilde C_3^2 \\ &\qquad+(-15 \widetilde C_2^5-552 \widetilde C_2^3+ 30 \widetilde C_4 \widetilde C_2^2+64 \widetilde C_3 \widetilde C_2- 72 \widetilde C_2+88 \widetilde C_4-16 \widetilde C_6) N \\ &\qquad+(85 \widetilde C_2^4-30 \widetilde C_3 \widetilde C_2^2+ 1014 \widetilde C_2^2-174 \widetilde C_4 \widetilde C_2- 88 \widetilde C_3+32 \widetilde C_5) N^2 \\ &\qquad+(-225 \widetilde C_2^3+174 \widetilde C_3 \widetilde C_2- 416 \widetilde C_2+224 \widetilde C_4) N^3 \\ &\qquad+2 (137 \widetilde C_2^2-120 \widetilde C_3) N^4- 120 \widetilde C_2 N^5, \\ w_{\mathfrak{sl}}(K_7)&=\widetilde C_2^7+210 \widetilde C_2^5+ 3192 \widetilde C_2^3-1680 \widetilde C_4 \widetilde C_2^2+ 1120 \widetilde C_3^2 \widetilde C_2 \\ &\qquad+(-21 \widetilde C_2^6-2212 \widetilde C_2^4+ 70 \widetilde C_4 \widetilde C_2^3+448 \widetilde C_3 \widetilde C_2^2 \\ &\qquad\qquad\qquad\;\;-10680 \widetilde C_2^2+7432 \widetilde C_4 \widetilde C_2- 112 \widetilde C_6 \widetilde C_2-4096 \widetilde C_3^2) N \\ &\qquad+(175 \widetilde C_2^5-70 \widetilde C_3 \widetilde C_2^3+ 8358 \widetilde C_2^3-714 \widetilde C_4 \widetilde C_2^2 \\ &\qquad\qquad\qquad\;\;-2792 \widetilde C_3 \widetilde C_2+224 \widetilde C_5 \widetilde C_2+ 3456 \widetilde C_2-3392 \widetilde C_4+544 \widetilde C_6) N^2 \\ &\qquad+(-735 \widetilde C_2^4+714 \widetilde C_3 \widetilde C_2^2- 12892 \widetilde C_2^2 \\ &\qquad\qquad\qquad\;\;+2212 \widetilde C_4 \widetilde C_2+3392 \widetilde C_3- 1088 \widetilde C_5) N^3 \\ &\qquad+4 (406 \widetilde C_2^3-581 \widetilde C_3 \widetilde C_2+ 1316 \widetilde C_2-464 \widetilde C_4) N^4 \\ &\qquad-12 (147 \widetilde C_2^2-200 \widetilde C_3) N^5+ 720 \widetilde C_2 N^6. \end{aligned}
\end{equation*}
\notag
$$
Значения весовой системы $w_{\mathfrak{gl}}$ восстанавливаются по значениям весовой системы $w_{\mathfrak{sl}}$ при помощи структуры алгебры Хопфа на пространстве хордовых диаграмм. А именно, для всякого примитивного элемента $P$ степени больше $1$ в алгебре хордовых диаграмм имеем $w_{\mathfrak{gl}(N)}(P)=w_{\mathfrak{sl}(N)}(P)\in ZU\mathfrak{sl}(n)$, т. е. $w_{\mathfrak{gl}(N)}(P)$ выражается как многочлен от $\widetilde C_2,\widetilde C_3,\dots$ . В то же время в случае $P=K_1$ справедливо равенство
$$
\begin{equation*}
w_{\mathfrak{gl}(N)}(K_1)=C_2=\widetilde C_2+\frac{C_1^2}{N}= w_{\mathfrak{sl}(N)}(K_1)+\frac{C_1^2}{N}\,.
\end{equation*}
\notag
$$
Из этих соображений можно восстановить значения $w_{\mathfrak{gl}}$ по известным значениям $w_{\mathfrak{sl}}$, представив данную хордовую диаграмму как многочлен от примитивных элементов. Более явно, для произвольной хордовой диаграммы $C$
$$
\begin{equation*}
w_{\mathfrak{gl}}(C)=\sum_{I\sqcup J=V(C)} \biggl(\frac{C_1^2}{N}\biggr)^{|I|} w_{\mathfrak{sl}}(C|_J).
\end{equation*}
\notag
$$
В частности, экспоненциальные производящие функции для значений весовых систем $w_{\mathfrak{gl}}$ и $w_{\mathfrak{sl}}$ на хордовых диаграммах $K_n$ связаны соотношением
$$
\begin{equation*}
1+\sum_{n=1}^\infty w_{\mathfrak{gl}}(K_n)\frac{x^n}{n!}= e^{C_1^2/N}\biggl(1+\sum_{n=1}^\infty w_{\mathfrak{sl}}(K_n) \frac{x^n}{n!}\biggr).
\end{equation*}
\notag
$$
3.6. $\mathfrak{gl}(1|1)$-весовая системаПомимо метризованных алгебр Ли весовые системы можно строить и по метризованным супералгебрам Ли. Такая весовая система принимает значения в центре универсальной обертывающей алгебры соответствующей супералгебры Ли. Общая конструкция весовой системы очень похожа на конструкцию для алгебры Ли, и мы ее не приводим. Как и в случае алгебр Ли, значений этой весовой системы для сколько-нибудь сложной супералгебры Ли чрезвычайно трудоемко. В работе [29] эта конструкция реализована для простейшей супералгебры Ли $\mathfrak{gl}(1|1)$. Соответствующая весовая система $w_{\mathfrak{gl}(1|1)}$ принимает значения в кольце многочленов от двух переменных – подкольце в центре $ZU\mathfrak{gl}(1|1)$ универсальной обертывающей алгебры, порожденном элементами Казимира градуировки $1$ и $2$. В [29] выведены рекуррентные соотношения для вычисления значений этой весовой системы на хордовых диаграммах, аналогичные соотношениям Чмутова–Варченко для $w_{\mathfrak{sl}(2)}$. В [19] доказано, что ее значения определяются графом пересечений хордовой диаграммы. Косохарактеристический многочлен графа (см. п. 1.3.5) является не чем иным, как продолжением весовой системы $w_{\mathfrak{gl}(1|1)}$ до $4$-инварианта графов. В свою очередь, в [64] определена весовая система $w_{\mathfrak{gl}(m|n)}$ для перестановок (при произвольных $m$ и $n$) и выведены рекуррентные соотношения для вычисления ее значений. В частности, там доказано, что весовая система $w_{\mathfrak{gl}(m|n)}$ является специализацией универсальной весовой системы $w_\mathfrak{gl}$ относительно подстановки $N=m-n$ и замены элементов Казимира $C_1,C_2,\dots$ в $U\mathfrak{gl}(N)$ аналогичными элементами в $U\mathfrak{gl}(m|n)$. 4. Вложенные графы и дельта-матроидыХордовую диаграмму можно интерпретировать как вложенный граф с одной вершиной на ориентированной поверхности. Один из ключевых вопросов теории весовых систем состоит в том, как распространить весовую систему на вложенные графы с произвольным количеством вершин. Такие обобщенные весовые системы ставятся в соответствие инвариантам конечного порядка зацеплений – так же, как обычные весовые системы ставятся в соответствие инвариантам конечного порядка узлов. Существуют различные подходы к продолжению весовых систем и инвариантов графов на вложенные графы. Наиболее интенсивно разрабатывается подход, в котором вложенный граф интерпретируется как абстрактный граф, к которому добавляется информация о вложении (см., например, [27]). Таким образом были построены различные продолжения классического многочлена Татта [8], [28]. В этом разделе мы описываем другой подход к построению продолжений, разработка которого начата в последние годы. Этот подход основан на анализе и использовании структуры алгебры Хопфа на пространствах дельта-матроидов. Он приводит к инвариантам, удовлетворяющим $4$-членным соотношениям и представляющим поэтому обобщенные весовые системы. Дельта-матроиды (также называемые лагранжевыми матроидами) были введены А. Буше около 1990 г. [11], [9]. Эти комбинаторные структуры оказались одинаково хорошо приспособленными к выделению существенных характеристик как абстрактных, так и вложенных графов. Связь вложенных графов с дельта-матроидами подробно описана в [21], [22]. Структура алгебры Хопфа на различных пространствах дельта-матроидов и $4$-членные соотношения для них введены в [45]. 4.1. Вложенные графы и $4$-членные соотношенияВложенные графы, называемые также ленточными графами, являются предметом изучения топологической теории графов. Ориентируемый вложенный граф можно определить как абстрактный граф (имеющий, быть может, петли и кратные ребра), в каждой вершине которого задан циклический порядок на множестве инцидентных ей полуребер. В дальнейшем мы будем рассматривать только ориентируемые связные вложенные графы. Такой граф можно представлять себе как связную ориентируемую двумерную поверхность с краем, образованную дисками, отвечающими вершинам, и ленточками, отвечающими ребрам; каждая ленточка двумя короткими своими сторонами приклеена к границам одного или двух дисков (см. рис. 19). Каждой хордовой диаграмме можно поставить в соответствие вложенный граф с одной вершиной, превратив петлю Вильсона в вершину путем приклеивания к ней диска и заменив каждую хорду ленточкой, с сохранением ориентируемости поверхности. $4$-членные соотношения (1) можно интерпретировать как соотношения для произвольного вложенного графа, не обязательно одновершинного. При этом концы двух ребер, участвующих в соотношении, могут принадлежать границам различных вершин (двух или даже трех). Мы будем называть эти соотношения обобщенными $4$-членными соотношениями, а удовлетворяющие им инварианты вложенных графов – обобщенными весовыми системами. Первое движение Васильева для вложенных графов меняет местами два соседних конца двух лент, второе движение Васильева состоит в протягивании конца одной ленты (ручки) вдоль стороны другой. В дальнейшем нас будет в первую очередь интересовать вопрос, как продолжить весовую систему до обобщенной весовой системы. Мы будем строить весовые системы, отталкиваясь от структуры алгебры Хопфа на пространстве дельта-матроидов. 4.2. Дельта-матроиды графов и вложенных графов и $4$-членные соотношения для нихСистемой множеств называется пара $(E;S)$, состоящая из конечного множества $E$ и множества $S\subset 2^E$ его подмножеств. Система множеств $(E;S)$ называется собственной, если множество $S$ непусто; в дальнейшем мы будем рассматривать только собственные системы множеств. Определение 4.1. Собственная система множеств $(E;S)$ называется дельта-матроидом, если для нее выполняется следующая аксиома симметричного обмена: Здесь через $\Delta$ обозначена операция симметрической разности на множествах: $X\mathbin{\Delta} Y=(X\setminus Y)\cup(Y\setminus X)$. В аксиоме симметричного обмена элемент $b$ может как совпадать с элементом $a$, так и быть отличным от него. Элементы множества $S$ называются допустимыми подмножествами дельта-матроида $(E;S)$. Каждому простому графу $G$ и каждому вложенному графу $\Gamma$ можно поставить в соответствие дельта-матроид. Для графа конструкция выглядит следующим образом. Напомним, что граф $G$ называется невырожденным, если определитель его матрицы смежности $A(G)$ над полем $\mathbb{F}_2$ из двух элементов равен $1$. Дельта-матроидом $\delta(G)=(V(G);S(G))$ графа $G$ называется система множеств, состоящая из множества $V(G)$ вершин графа $G$ и множества $S(G)\subset 2^{V(G)}$ его подмножеств, причем подмножество $U\subset V(G)$ вершин графа является допустимым (т. е. $U\in S(G)$) тогда и только тогда, когда индуцированный им подграф $G\big|_U$ невырожден. В свою очередь, дельта-матроидом $\delta(\Gamma)=(E(\Gamma);S(\Gamma))$ вложенного графа $\Gamma$ называется система множеств, состоящая из множества $E(\Gamma)$ ребер вложенного графа $\Gamma$ и множества $S(\Gamma)\subset 2^{E(\Gamma)}$ его подмножеств, причем подмножество $U\subset E(\Gamma)$ ребер вложенного графа является допустимым (т. е. $U\in S(\Gamma)$) тогда и только тогда, когда остовный вложенный подграф $\Gamma\big|_U$ имеет связную границу. В случае если род вложенного графа $\Gamma$ равен нулю (т. е. это граф, вложенный в сферу), подмножество его ребер допустимо в том и только том случае, когда соответствующий остовный подграф $\Gamma\big|_U$ является деревом. В случае произвольного рода допустимые подмножества ребер дельта-матроида $\delta(\Gamma)$ называются также квазидеревьями (этот термин введен в [23]). А. Буше доказал, что системы множеств $\delta(G)$ и $\delta(\Gamma)$ действительно являются дельта-матроидами. Кроме того, если $\Gamma$ – вложенный граф с одной вершиной, т. е. хордовая диаграмма, то соответствующие определения согласованы. Теорема 4.2. Если $C$ – хордовая диаграмма, т. е. вложенный граф с одной вершиной, то дельта-матроид $\delta(C)$ естественно изоморфен дельта-матроиду $\delta(g(C))$ ее графа пересечений. Другими словами, граница хордовой диаграммы $C$ связна тогда и только тогда, когда ее граф пересечений $g(C)$ невырожден. Последнее утверждение неоднократно переоткрывалось (см., например, [59]). Дельта-матроид графа, как и дельта-матроид ориентированного вложенного графа, является четным. Дельта-матроид $(E;S)$ называется четным, если количество элементов во всех его допустимых множествах имеет одну и ту же четность: $|X|\equiv|Y|\!\!\mod 2$ для всех $X,Y\in S$. Поскольку нас в первую очередь интересуют вложенные графы на ориентируемых поверхностях, далее мы будем говорить только о четных дельта-матроидах, хотя большинство описываемых ниже конструкций распространяется и на дельта-матроиды, не являющиеся четными (см. п. 4.5). Определим операцию скручивания (или частичной двойственности) дельта-матроида следующим образом. Пусть $U\subset E$ – подмножество базового множества $E$ дельта-матроида $D=(E;S)$. Скручиванием $D*U$ дельта-матроида $D$ по подмножеству $U$ называется система множеств $D*U=(E;S*U)$, где $S*U=\{X\mathbin{\Delta} U\colon X\in S\}$. Для дельта-матроидов вложенных графов операция скручивания соответствует частичной двойственности, введенной в [15]. Скручивание дельта-матроида по произвольному подмножеству его базового множества является дельта-матроидом [11]. Определение 4.3. Дельта-матроид $\delta(G)$ графа $G$ называется графическим. Скручивание графического дельта-матроида по подмножеству его базового множества называется бинарным дельта-матроидом; бинарный дельта-матроид может не быть графическим. В частности, дельта-матроид $\delta(\Gamma)$ любого вложенного графа $\Gamma$ на ориентированной поверхности является четным бинарным. Для дельта-матроидов определено $4$-членное соотношение. Его определение требует определения двух операций над дельта-матроидами – первого и второго движений Васильева. Каждая из этих операций задается упорядоченной парой элементов дельта-матроида. Результат $\widetilde{D_{ab}}$ протягивания ручки $a$ вдоль ручки $b$ (см. [48]) в дельта-матроиде $D=(E;S)$, $a,b\in E$, задается равенством $\widetilde{D_{ab}}=(E;\widetilde{S_{ab}})$, где
$$
\begin{equation*}
\widetilde{S_{ab}}=S\mathbin{\Delta}\{X \sqcup a\colon X \sqcup b \in S \text{ и } X \subseteq E \setminus \{a,b\}\}.
\end{equation*}
\notag
$$
Результат ${D'_{ab}}$ обмена концов ручек $a$ и $b$ в дельта-матроиде $D=(E;S)$, $a,b\in E$, задается равенством ${D'_{ab}}=(E;{S'_{ab}})$, где
$$
\begin{equation*}
{S'_{ab}}=S\mathbin{\Delta}\{X \sqcup \{a,b\}\colon X \in S \text{ и } X \subseteq E \setminus \{a,b\}\}.
\end{equation*}
\notag
$$
Первое и второе движение Васильева переводят четный бинарный дельта-матроид в дельта-матроид того же вида. Функция $f$ на четных бинарных дельта-матроидах удовлетворяет $4$-членным соотношениям, если для любого такого дельта-матроида $D=(E;S)$ и любой пары $a,b\in E$ элементов его базового множества выполняется равенство
$$
\begin{equation*}
f(D)-f(D'_{ab})=f(\widetilde{D_{ab}})-f(\widetilde{D'_{ab}}).
\end{equation*}
\notag
$$
Если функция на четных бинарных дельта-матроидах удовлетворяет $4$-членным соотношениям, то ее ограничение на дельта-матроиды вложенных графов на ориентированных поверхностях удовлетворяет обобщенным $4$-членным соотношениям для них. 4.3. Алгебры Хопфа дельта-матроидовДве системы множеств $(E_1;S_1)$ и $(E_2;S_2)$ называются изоморфными, если существует взаимно однозначное отображение множества $E_1$ в множество $E_2$, переводящее систему подмножеств $S_1$ взаимно однозначно в систему подмножеств $S_2$. Обозначим через $\mathcal{B}^e_n$ векторное пространство, порожденное классами изоморфизма четных бинарных дельта-матроидов на $n$-элементных множествах, и положим
$$
\begin{equation*}
\mathcal{B}^e=\mathcal{B}^e_0\oplus\mathcal{B}^e_1\oplus \mathcal{B}^e_2\oplus\cdots\,.
\end{equation*}
\notag
$$
На пространстве $\mathcal{B}^e$ можно ввести естественную структуру градуированной коммутативной кокоммутативной алгебры Хопфа. Умножение в этой алгебре дается несвязным объединением, коумножение – расщеплением базового множества дельта-матроида на два непересекающихся подмножества всеми возможными способами. Дельта-матроид называется связным, если он не представляется в виде произведения дельта-матроидов с меньшими носителями. Результат факторизации пространства $\mathcal{B}^e$ по подпространству $4$-членных соотношений наследует структуру алгебры Хопфа. Мы не собираемся использовать эту алгебру Хопфа и поэтому не вводим специального обозначения для нее. Замечание. В отличие от графов и дельта-матроидов, вложенные графы, насколько нам известно, не порождают естественно определенную алгебру Хопфа. 4.4. Продолжение инвариантов графов на вложенные графы и дельта-матроидыВ этом пункте мы показываем, как распространять на вложенные графы $4$-инварианты графов, описанные в разделе 2. Построенные продолжения оказываются определенными для бинарных дельта-матроидов, и их определение использует структуру алгебры Хопфа на пространстве бинарных дельта-матроидов. 4.4.1. Многочлен переплетенийОпределенный выше для графов многочлен переплетений допускает естественное продолжение на бинарные дельта- матроиды. Определение 4.4. Расстоянием от системы множеств $D=(E;S)$ до подмножества $U\subset E$ называется величина Многочленом переплетений $L_D(x)$ дельта-матроида $D=(E;S)$ называется следующий многочлен (см. [49]): Теорема 4.5. Если $D=D(G)$ – дельта-матроид графа $G$, то многочлен переплетений $L_D$ дельта-матроида $D$ следующим образом связан с многочленом переплетений графа $G$: Теорема 4.6 [38]. Многочлен переплетений четных бинарных дельта-матроидов удовлетворяет $4$-членному соотношению для них. Теорема 4.7. Пространство значений многочлена переплетений на подпространстве примитивных элементов в $\mathcal{B}^e_n$ является $n$-мерным. Отсюда вытекает, что размерность подпространства примитивных элементов в $\mathcal{B}^e_n$ не меньше $n$. 4.4.2. Симметризованный многочлен СтенлиПонятие теневого инварианта графов естественным образом распространяется на инварианты дельта-матроидов. Чтобы определить такой инвариант, достаточно указать для каждого связного дельта-матроида $D=(E;S)$ коэффициент при $q_n$, где $n=|E|$, в значении теневого инварианта на нем. В [50] предложен способ продолжения теневых инвариантов графов до теневых инвариантов дельта-матроидов. Этот способ основан на использовании структуры комбинаторной алгебры Хопфа, введенной в [2]. Далее мы ограничимся коммутативными кокоммутативными комбинаторными алгебрами Хопфа. Комбинаторной алгеброй Хопфа называется пара $(\mathcal{H},\xi)$, состоящая из связной градуированной алгебры Хопфа $\mathcal{H}$ и характера (т. е. мультипликативного отображения) $\xi\colon\mathcal{H}\to\mathbb{C}$. Алгебра Хопфа многочленов $\mathbb{C}[q_1,q_2,\dots]$ становится комбинаторной алгеброй Хопфа, если снабдить ее каноническим характером $\zeta$, который каждую переменную $q_k$ переводит в $1$. Эта комбинаторная алгебра Хопфа является терминальным объектом в категории комбинаторных алгебр Хопфа, т. е. каждой комбинаторной алгебре Хопфа $(\mathcal{H},\xi)$ однозначно ставится в соответствие теневой инвариант – градуированный гомоморфизм алгебр Хопфа $\mathcal{H}\to\mathbb{C}[q_1,q_2,\dots]$, переводящий характер $\xi$ в $\zeta$. Как доказано в [2], симметризованный хроматический многочлен Стенли является градуированным гомоморфизмом алгебр Хопфа $\mathcal{G}\to\mathbb{C}[q_1,q_2,\dots]$, отвечающим характеру $\xi\colon\mathcal{G}\to\mathbb{C}$, который переводит граф с одной вершиной в $1$, а любой связный граф с $n\geqslant2$ вершинами в $0$. Эта структура позволила определить [50] симметризованный хроматический многочлен Стенли дельта-матроидов как градуированный гомоморфизм $W\colon\mathcal{B}^e\to\mathbb{C}[x;q_1,q_2,\dots]$ из алгебры Хопфа четных бинарных дельта-матроидов в алгебру Хопфа многочленов от переменных $q$ с коэффициентами в кольце многочленов от переменной $x$, отвечающий характеру, переводящему дельта-матроид $(\{1\};\{\varnothing\})$ в $1$, дельта-матроид $(\{1\};\{\{1\}\})$ в $x$, а любой связный дельта-матроид градуировки $n\geqslant2$ в $0$. Упомянутые два дельта-матроида порождают однородное подпространство $\mathcal{B}^e_1$. Теорема 4.8. Симметризованный хроматический многочлен Стенли дельта-матроидов удовлетворяет $4$-членным соотношениям для дельта-матроидов. 4.4.3. Многочлен переходовМногочлен переходов также допускает продолжение на дельта-матроиды, удовлетворяющее $4$-членным соотношениям для них. Для определения многочлена перехода нам понадобится несколько вспомогательных определений. Пусть $D=(E;S)$ – дельта-матроид и $U\subset E$ – подмножество его базового множества. Многочлен
$$
\begin{equation*}
Q_D(s,t,x)=\sum_{E=\Phi\sqcup X\sqcup\Psi} s^{|\Phi|}t^{|X|}x^{d_{D+\Phi*X\overline*\Psi}(\varnothing)}
\end{equation*}
\notag
$$
называется многочленом переходов дельта-матроида $D=(E;S)$. Здесь операция $+$ определяется для элемента $u\in E$ равенством
$$
\begin{equation*}
D+u=(E,S\mathbin{\Delta}\{F\cup\{u\}\colon F\in S,\, u\notin F\}).
\end{equation*}
\notag
$$
Операция $\overline*$ задается равенством Эти две операции продолжаются поэлементно на произвольное подмножество $A\subset E$. Это определение является специализацией определения взвешенного многочлена переходов дельта-матроидов из [12]. Теорема 4.9 [25]. Многочлен переходов четных бинарных дельта-матроидов удовлетворяет $4$-членному соотношению для них. 4.4.4. Косохарактеристический многочленПонятие невырожденности графа естественно продолжается на вложенные графы и дельта-матроиды. Дельта-матроид $(E;S)$ называется невырожденным, если $E\in S$, т. е. если все множество $E$ является допустимым. Для вложенных графов это означает, что вложенный граф невырожден, если его граница связна. Для хордовых диаграмм это определение согласовано с уже известным нам. Невырожденность $\nu(D)$ дельта-матроида равна $1$, если $D$ невырожден, и равна $0$ в противном случае. Мы можем определить косохарактеристический многочлен дельта-матроида $D=(E;S)$ равенством
$$
\begin{equation*}
Q_D(x)=\sum_{U\subset E} x^{|U|}\nu\bigl(D\big|_U\bigr).
\end{equation*}
\notag
$$
Теорема 4.10. Косохарактеристический многочлен для дельта-матроидов удовлетворяет $4$-членным соотношениям. Как и в случае графов, это утверждение вытекает из того, что невырожденность сохраняется при втором движении Васильева. 4.5. Включение неориентируемых поверхностей: оснащенные хордовые диаграммы, оснащенные графы и дельта-матроиды без требования четностиУ $4$-членных соотношений для хордовых диаграмм, графов, вложенных графов и дельта-матроидов есть неориентируемая версия, которую мы здесь коротко опишем. Ее не следует рассматривать отдельно от ориентированного варианта – все конструкции, в первую очередь структура алгебр Хопфа, требуют одновременного участия как ориентируемых, так и неориентируемых объектов. В то же время ориентируемые объекты порождают подалгебры Хопфа в алгебрах Хопфа объектов, ограничения на ориентируемость которых не накладываются. Оснащенной хордовой диаграммой называется пара $(C,\varphi)$, состоящая из хордовой диаграммы $C$ и оснащения $\varphi\colon V(C)\to\mathbb{F}_2$, ставящего в соответствие каждой хорде диаграммы $C$ элемент поля $\mathbb{F}_2$. Изоморфизм оснащенных хордовых диаграмм – это изоморфизм подлежащих хордовых диаграмм, переводящий оснащение первой из них в оснащение второй. Оснащенным графом называется пара $(G,\varphi)$, состоящая из простого графа $G$ и оснащения $\varphi\colon V(G)\to\mathbb{F}_2$, ставящего в соответствие каждой вершине графа $G$ элемент поля $\mathbb{F}_2$. Изоморфизм оснащенных графов – это изоморфизм подлежащих простых графов, переводящий оснащение первого графа в оснащение второго. Занумеровав вершины графа $G$ числами от $1$ до $n=|V(G)|$, мы можем поставить в соответствие оснащенному графу его матрицу смежности $A(G,\varphi)$. Вне диагонали эта матрица совпадает с матрицей смежности $A(G)$ простого графа $G$, а ее диагональные элементы совпадают с оснащениями соответствующих вершин. Классы изоморфизма оснащенных графов совпадают с симметричными матрицами над полем $\mathbb{F}_2$, рассматриваемыми с точностью до одновременной перенумерации столбцов и строк. Каждой оснащенной хордовой диаграмме естественным образом ставится в соответствие оснащенный граф – ее граф пересечения. Также каждую оснащенную хордовую диаграмму можно рассматривать как ленточный граф с одной вершиной; при этом хорде с оснащением $0$ ставится в соответствие обычная ленточка, а хорде с оснащением $1$ – ленточка с перекруткой вполоборота. Если хотя бы одна из хорд имеет оснащение $1$, то соответствующая хордовой диаграмме поверхность с краем становится неориентируемой. Оснащенные хордовые диаграммы, оснащенные графы и оснащенные весовые системы введены и изучены в [44]. Функция $f$ на оснащенных хордовых диаграммах со значениями в коммутативном кольце называется оснащенной весовой системой, если она удовлетворяет оснащенному $4$-членному соотношению. Инвариант $f$ оснащенных графов называется $4$-инвариантом, если для любой пары вершин $a,b\in V(G)$ он удовлетворяет $4$-членному соотношению
$$
\begin{equation*}
f((G,\varphi))-f((G'_{ab},\varphi))= f((\widetilde{G}_{ab},\widetilde{\varphi}_{ab}))- f((\widetilde{G}'_{ab},\widetilde{\varphi}_{ab})).
\end{equation*}
\notag
$$
Между множествами вершин всех четырех графов, участвующих в соотношении, имеется естественное взаимно однозначное соответствие, поэтому оснащения $\varphi$ и $\varphi_{ab}$ имеют общую область определения. Здесь через $\widetilde{\varphi}_{ab}$ обозначено оснащение графа $\widetilde{G}_{ab}$, которое совпадает с $\varphi$ на всех его вершинах, кроме $a$, в то время как $\widetilde{\varphi}_{ab}(a)=\varphi(a)+\varphi(b)$. Другими словами, матрица смежности $A(\widetilde{G}_{ab})$ оснащенного графа $\widetilde{G}_{ab}$ получается из матрицы смежности $A(G)$ графа $G$ тем же преобразованием (5), что и в неоснащенном случае. Так же, как для неоснащенных графов, для оснащенных определяется невырожденность и косохарактеристический многочлен. Невырожденность оснащенного графа сохраняется при втором движении Васильева. Отсюда вытекает, что косохарактеристический многочлен – $4$-инвариант оснащенных графов. В отличие от косохарактеристического многочлена простых графов, косохарактеристический многочлен оснащенных графов может не быть ни четным, ни нечетным. Всякий $4$-инвариант оснащенных графов задает оснащенную весовую систему, переводящую оснащенную хордовую диаграмму в значение инварианта на ее оснащенном графе пересечения. В частности, такие оснащенные весовые системы задаются невырожденностью и косохарактеристическим многочленом оснащенных графов. Дельта-матроид оснащенного графа и дельта-матроид произвольного вложенного графа, лежащего на (быть может, неориентируемой) поверхности, определяются так же, как в ориентируемом случае. Если среди вершин оснащенного графа есть вершина с оснащением $1$, то соответствующий дельта-матроид не будет четным – количество элементов в допустимых множествах будет как четным, так и нечетным. Также не будет четным и дельта-матроид вложенного в неориентируемую поверхность графа. Классы изоморфизма бинарных дельта-матроидов порождают алгебру Хопфа, содержащую подалгебру Хопфа $\mathcal{B}^e$.
Цитирование в формате AMSBIB
\RBibitem{KazLan22} |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|