| Функциональный анализ и его приложения |
|
|
|
|
|
Многочлен переплетений бинарных дельта-матроидов и инварианты зацеплений Надежда Коданева Национальный исследовательский университет "Высшая школа экономики", Москва, Россия
Английская версия:
Functional Analysis and Its Applications, 2025, Volume 59, Issue 1, Pages DOI: https://doi.org/10.1134/S1234567825010033 
Реферативные базы данных:
   § 1. ВведениеИнварианты узлов конечного порядка были введены В. Васильевым [15] в конце 1980-x гг. Они могут быть описаны с помощью весовых систем, т.е. функций на хордовых диаграммах, удовлетворяющих так называемым четырехчленным соотношениям. Каждой хордовой диаграмме может быть сопоставлен граф, называемый графом пересечений, и это соответствие позволяет ввести четырехчленные соотношения и для графов (см. [9]). Поэтому каждый инвариант графов, удовлетворяющий четырехчленному соотношению, определяет весовую систему. Хордовые диаграммы можно интерпретировать как вложенные графы с одной вершиной. Рассматривая вложенные графы с произвольным числом вершин, мы можем обобщить понятия весовых систем с узлов на зацепления. Произвольному вложенному графу нельзя сопоставить граф пересечений. Вместо этого вложенному графу можно сопоставить другую комбинаторную структуру, называемую дельта-матроидом [2], и этот дельта-матроид будет бинарным. Как было показано в [10], для бинарных дельта-матроидов можно определить четырехчленное соотношение, которое согласовано с соответствием между вложенными графами и их дельта-матроидами и с четырехчленным соотношением для вложенных графов. Этот результат ставит вопрос о том, удовлетворяют ли этому соотношению известные инварианты дельта-матроидов. В статье мы показываем, что для многочлена переплетений ответ на этот вопрос утвердительный. Для другого инварианта бинарных дельта-матроидов, называемого многочленом переходов, утвердительный ответ был дан в [4]. Бинарные дельта-матроиды порождают градуированную связную коммутативную кокоммутативную алгебру Хопфа. Ее факторалгебра по модулю четырехчленных соотношений наследует структуру алгебры Хопфа. Второй из наших основных результатов связан с изучением поведения многочлена переплетений на примитивных элементах этой факторалгебры. Мы показали, что размерность пространства значений этого многочлена на подпространстве примитивных элементов в пространстве дельта-матроидов из $n$ элементов равна $n$. Недавно весовые системы, соответствующие некоторым алгебрам Ли, были продолжены с хордовых диаграмм на перестановки [5], [16]. Этот результат приводит к вопросу о том, можно ли получить многочлен переплетений или какие-либо другие инварианты графов или хордовых диаграмм как специализации этих весовых систем, и таким образом получить естественное продолжение на перестановки1 и гиперкарты. Далее мы введем основные понятия нашего исследования и опишем результаты Н. Нетрусовой, связанные с многочленом переплетений графов. 1.1. Многочлен переплетений графовИсходно многочлен переплетений был введен как функция, определенная рекурсивно на ориентированных графах, в которых входящая и исходящая степени каждой вершины равны двум. Он возник в работе Р. Арратиа, Б. Боллобаша и Г. Соркина [1], связанной с секвенированием ДНК. Затем рекуррентное соотношение было обобщено до определения многочлена на произвольных графах. Здесь мы определим многочлен переплетений, следуя [12] (см. также [13]). Начнем с определения операции поворота. Пусть $G$ – некоторый граф (здесь и далее имеется в виду граф без петель и кратных ребер). Выберем произвольные вершины $a$ и $b$ графа $G$, соединенные ребром, и разобьем остальные вершины графа на четыре класса:
Тогда поворотом графа $G$ относительно ребра $ab$ называется граф $G^{ab}$, который является результатом стирания всех ребер графа $G$ между вершинами из двух различных из первых трех классов и добавления всех таких ребер, которых не было в $G$. Все остальные ребра (включая $ab$) остаются неизменными. Определение 1. Многочленом переплетений графа $G$ называется многочлен $q(G, x)$ от одной переменной $x$, определенный следующей рекуррентной формулой. Теорема из [1] утверждает, что многочлен переплетений корректно определен, т.е. он не зависит от порядка выбора ребер, к которым применяется рекуррентное соотношение. Замечание 1. Можно заметить, что определения поворота и многочлена переплетений не зависят от порядка вершин $a$ и $b$, т.е. $G^{ab}=G^{ba}$, а значит, мы также можем пользоваться рекуррентным соотношением 1.2. Дельта-матроидыВ этом пункте мы даем основные определения, связанные с дельта-матроидами, и показываем, как определение многочлена переплетений может быть обобщено на дельта-матроиды. Наше изложение следует [10]. Определение 2. Система множеств $(E, \Phi)$ – это пара, состоящая из конечного множества $E$ и $\Phi\subset 2^E$. Множество $E$ называется базовым множеством, а элементы множества $\Phi$ – допустимыми множествами. Система множеств называется собственной, если $\Phi$ непусто. В этой работе мы рассматриваем только собственные системы множеств. Определение 3. Дельта-матроид – это собственная система множеств, удовлетворяющая следующей аксиоме симметричного обмена: для любых двух множеств $X$, $Y \in \Phi$ если $x \in X \Delta Y$, то существует элемент $y \in X \Delta Y$ такой, что $ (X\Delta \{x, y\}) \in \Phi$. Здесь через $\Delta$ обозначена симметрическая разность множеств, т.е. $X\Delta Y=(X\setminus Y)\cup (Y\setminus X)$. Например, система множеств $(\{1, 2, 3\}, \{\varnothing, \{1\}, \{1, 2\}, \{2, 3\}, \{1, 2, 3\}\})$ является дельта-матроидом, а система множеств $(\{1, 2, 3\}, \{\varnothing, \{1, 2, 3\}\})$ не является: аксиома симметричного обмена нарушается для $X=\varnothing$, $Y=\{1,2,3\}$, $x=1$. Определение 4. Пусть $D=(E, \Phi)$ – система множеств. Для $X \subset E$ определим скручивание $D * X$ как систему множеств $(E, \Phi \Delta X)$, где $\Phi \Delta X = \{F \Delta X \mid F \in \Phi \}$. Согласно А. Буше [2] любое скручивание дельта-матроида является дельта-матроидом. Для графа $G$ мы можем определить его дельта-матроид $M_{G}$ следующим образом. Пусть $A_G$ – матрица смежности графа $G$ над полем $\mathbb{F}_2$. Мы говорим, что граф $G$ является невырожденным, если матрица $A_G$ невырожденная. Пустой граф является невырожденным по соглашению. Согласно определению базовое множество дельта-матроида $M_G$ – это множество вершин графа $V(G)$, а допустимые множества – это такие $X \subset V(G)$, что индуцированный подграф $G|_X$ невырожденный. Заметим, что дельта-матроид $M_{G^{ab}}$ поворота $G^{ab}$ графа $G$ является $\{a,b\}$-скручиванием дельта-матроида $M_G$ графа $G$, т.е. $M_{G^{ab}}=M_G*\{a,b\}$. Можно показать, что системы множеств, заданные таким образом, действительно являются дельта-матроидами. Более того, мы можем аналогичным образом определить систему множеств $M_{A}$ для произвольной симметричной матрицы $A$ над полем $\mathbb{F}_2$ (т.е. на главной диагонали можно писать не только нули, но и единицы). Такая система множеств также является дельта-матроидом, как показал А. Буше в [2]. Дельта-матроиды, которые могут быть получены из $M_A$ с помощью скручиваний, называются бинарными дельта-матроидами. Определение 5. Петлей называется элемент $e$ базового множества $E$ дельта-матроида ${D=(E, \Phi)}$, если он не входит ни в одно из допустимых множеств, и копетлей, если он входит во все допустимые множества. Для элемента $e$, не являющегося петлей, мы определяем “$D$ стянуть $e$” как систему множеств Для элемента $e$, не являющегося копетлей, мы определяем “$D$ удалить $e$” как систему множеств Если же $e$ является петлей, то мы полагаем $D/e=D\setminus e$, а если $e$ – копетля, то $D\setminus e=D/e.$ Эти операции определены корректно на дельта-матроидах, т.е. “$D$ удалить $e$” и “$D$ стянуть $e$” являются дельта-матроидами. Определение 6 (см. [3]). Расстоянием от системы множеств $D=(E, \Phi)$ до подмножества $X \subset E$ называется Многочлен переплетений системы множеств $D$ определяется равенством Многочлены переплетений дельта-матроидов, отвечающих графам, согласованы с многочленом переплетений графов. Следующий результат описывает связь между этими многочленами. Теорема 1 (см. [3]). Пусть $G$ – граф, а $M_{G}$ – его дельта-матроид. Тогда $q(G,x)=q_{\Delta}(M_{G}, x-1)$. Рекуррентное соотношение, определяющее многочлен переплетений графов, может быть распространено на случай дельта-матроидов. Теорема 2 (см. [3]). Пусть $D=(E, \Phi)$ – дельта-матроид, а элемент $e\in E$ не является ни копетлей, ни петлей. Тогда Если $\varnothing \in \Phi$, то для любого подмножества $X \subset E$ и любого элемента $e \in X$ справедливо равенство 1.3. Четырехчленное соотношение для графовСвязь между многочленом переплетений графов и теорией узлов изучала Н. Нетрусова в [14]. Она показала, что многочлен переплетений графов удовлетворяет четырехчленному соотношению, а значит, задает инвариант узлов. Определение 7. Алгебра $\mathcal{G}$ графов – это бесконечномерная коммутативная алгебра (над полем $\mathbb{C}$), свободно порожденная всеми графами, умножение в которой определено как несвязное объединение графов. Эта алгебра является градуированной, т.е. $\mathcal{G}=\mathcal{G}_0 \oplus \mathcal{G}_1 \oplus \dotsb$, где $\mathcal{G}_{k}$ – это подпространство алгебры, порожденное графами с $k$ вершинами. Используя эту конструкцию, мы можем определить многочлен переплетений как функцию на алгебре $\mathcal{G}$, продолженную на нее по линейности. Он будет определен корректно, поскольку многочлен переплетений произведения графов равен произведению многочленов множителей, как сформулировано в следующем утверждении. Предложение 1. Если граф $G$ представляет собой несвязное объединение двух графов $G_{1}$ и $G_{2}$, то $q(G, x)=q(G_{1}, x) \cdot q(G_{2}, x)$. Определение 8. Функция $f$, определенная на графах, называется $4$-инвариантом, если она удовлетворяет следующему условию для любого графа $G$ и любых двух различных вершин $a$, $b \in V(G)$: Теорема 3 (см. [14]). Многочлен переплетений графов является $4$-инвариантом. Этот результат подводит нас к вопросу о том, будет ли обобщение многочлена переплетений на бинарные дельта-матроиды обладать аналогичным свойством. § 2. Четырехчленное соотношение для многочлена переплетений дельта-матроидовВ этом параграфе мы опишем четырехчленное соотношение для бинарных дельта-матроидов, введенное в [10], и докажем, что многочлен переплетений дельта-матроидов ему удовлетворяет. 2.1. Четырехчленное соотношение для дельта-матроидовОпределение четырехчленного соотношения для дельта-матроидов мотивировано аналогичным соотношением для вложенных графов. А. Буше [2] следующим образом сопоставил связному вложенному графу $\Gamma$ его дельта-матроид $M_\Gamma$. Базовое множество дельта-матроида $M_\Gamma$ – это множество $E(\Gamma)$ ребер вложенного графа $\Gamma$, а допустимыми подмножествами являются такие $X\subset E(\Gamma)$, что остовный вложенный подграф $\Gamma|_X$ имеет связную границу (т.е. имеет единственную грань). Отметим, что в отличие от абстрактных графов вложенные графы могут иметь петли и кратные ребра. Замечание 2. В [6] введены четырехчленные соотношения для лагранжевых подпространств, которые можно рассматривать как комбинаторный аналог четырехчленных соотношений для вложенных графов. В. Жуков [17] доказал эквивалентность этого подхода тому, который применяется для бинарных дельта-матроидов. Чтобы описать четырехчленные соотношения для дельта-матроидов, сначала определим два движения Васильева. Второе движение Васильева (протягивание одной ручки вдоль другой) ввели и изучили Й. Моффатт и Е. Мфако-Банда в [11]. Первое движение Васильева (обмен концов ручек) было определено С. Ландо и В. Жуковым в [10]. Определение 9. Пусть $D=(E,\Phi)$ – система множеств, $a$ и $b$ – два различных элемента в $E$. Тогда результатом протягивания ручки $a$ вдоль ручки $b$ является система множеств $\widetilde{D_{ab}}=(E, \widetilde{\Phi_{ab}})$, где Предложение 2 (см. [11]). Множество бинарных дельта-матроидов замкнуто относительно операции протягивания ручки. Определение 10. Пусть $D=(E,\Phi)$ – система множеств, $a$ и $b$ – два различных элемента в $E$. Результатом обмена концов ручек $a$ и $b$ является система множеств $D'_{ab}= (E, \Phi'_{ab})$, где Предложение 3 (см. [10]). Множество бинарных дельта-матроидов замкнуто относительно операции обмена концов ручек. Операции протягивания ручки $\widetilde{D_{ab}}$ и обмена концов ручек $D'_{ab}$ коммутируют; обозначим их композицию через $\widetilde{D'_{ab}}$. Тогда про функцию $f$, определенную на бинарных дельта-матроидах, говорят, что она удовлетворяет четырехчленному соотношению, если равенство
$$
\begin{equation*}
f(D)-f(D'_{ab})= f(\widetilde{D_{ab}}) - f(\widetilde{D'_{ab}})
\end{equation*}
\notag
$$
выполняется для любого бинарного дельта-матроида $D=(E, \Phi)$ и любой пары $a,b \in E$, где $a \neq b$. 2.2. Многочлен переплетений и четырехчленное соотношениеПервый из наших основных результатов следующий. Теорема 4. Многочлен переплетений бинарных дельта-матроидов удовлетворяет четырехчленному соотношению. Доказательство. Пусть $D=(E,\Phi)$ – бинарный дельта-матроид. Мы утверждаем, что для каждого множества $\phi \subset E$ верно равенство
Это можно доказать, показав, что для любого множества $\phi$ выполняется хотя бы одно из двух следующих условий:
Возможны четыре случая:
Докажем, что остальные случаи невозможны. Пусть $\phi' \subset E \setminus \{a, b\}$. Тогда если $\phi=\phi'\sqcup \{a\}$, то $\phi$ может стать допустимым или перестать быть допустимым только при действии первого движения Васильева. Если $\phi=\phi'\sqcup \{a, b\}$, то $\phi$ может стать допустимым или перестать быть допустимым только при действии второго движения Васильева. Все остальные подмножества не могут стать допустимыми или перестать ими быть под действием движений Васильева, следовательно, они либо являются допустимыми во всех четырех дельта-матроидах, либо не являются ни в одном из них. Чтобы понять, могут ли множества вида ${\phi = \phi' \sqcup \{a\}}$ и ${\phi = \phi'\sqcup \{a, b\}}$ стать допустимыми или перестать быть допустимыми, необходимо проверить, являются ли ${\phi' \sqcup \{b\}}$ и $\phi'$ допустимыми. Такие множества либо являются допустимыми во всех четырех дельта-матроидах, либо не являются допустимыми ни в одном из них. Следовательно, условие того, чтобы $\phi$ стало допустимым или перестало им быть при движениях Васильева, выполняется либо в обоих дельта-матроидах, к которым оно применяется, либо не выполняется ни в одном из них. Теперь поочередно рассмотрим все возможные случаи. I. Все четыре расстояния равны $0$, значит, равенство (1) выполняется. II. Если $\phi$ допустимо в $D$ и не допустимо в $\widetilde{D}_{ab}$, то $\phi=\phi' \sqcup \{a\}$, $b\notin \phi$ и $\phi' \sqcup \{b\}$ допустимы во всех четырех дельта-матроидах. Расстояния от $\phi$ до $\widetilde{D}_{ab}$ и $\widetilde{D}'_{ab}$ не больше $2$, поскольку $|\phi \Delta (\phi' \sqcup \{b\})|=2$. Если одно из них равно $1$, то существует множество $\phi_{0}$, допустимое в $\widetilde{D}_{ab}$ или $\widetilde{D}'_{ab}$, такое, что $\phi \Delta \phi_{0} = c$, $c \in E$. Если оно допустимо в обоих этих дельта-матроидах, то (1) верно. Иначе $\phi_{0}=\phi'_{0} \sqcup \{a, b\}$ и $\phi'_{0}$ допустимо во всех четырех дельта-матроидах. Поскольку $b$ не принадлежит $\phi$, $c=b$ и $\phi'=\phi'_{0}$. Следовательно, $d_{\widetilde{D}_{ab}}(\phi)=d_{\widetilde{D}'_{ab}}(\phi)=|\phi \Delta \phi'|=1$. III. Если $\phi$ допустимо в $D$, но не в $D'_{ab}$, то $\phi=\phi' \sqcup \{a, b\}$ и $\phi'$ допустимо во всех четырех дельта-матроидах. Аналогично расстояния от $\phi$ до $D'_{ab}$ и $\widetilde{D}'_{ab}$ не больше $2$. Если одно из этих расстояний равно $1$, то для некоторого множества $\phi_0$, которое является допустимым в $D'_{ab}$ или $\widetilde{D}'_{ab}$, $\phi \Delta \phi_0 = c$, где $c$ – элемент допустимого множества. Если $\phi_0$ допустимо в обоих этих дельта-матроидах, то второе расстояние также равно $1$. В ином случае $\phi_0=\phi_0' \sqcup \{a\}$, $b\notin \phi_0$ и $\phi_0' \sqcup \{b\}$ допустимо в обоих этих дельта-матроидах. Кроме того, $b=c$, $\phi'=\phi_0'$. Тогда расстояние от $\phi$ до $\phi_0$ равно расстоянию от $\phi$ до $\phi_0' \sqcup \{b\}$, т.е. расстояния от $\phi$ до обоих дельта-матроидов равны $1$. IV. Без потери общности мы можем предположить, что расстояние от $\phi$ до $D$ не больше трех других расстояний. Пусть через $\phi_{0}$ обозначено допустимое множество из $\Phi$ такое, что $d_{D}(\phi)=|\phi \Delta \phi_{0}|$. Если не все четыре расстояния от $\phi$ до дельта-матроидов равны, то $\phi_{0}$ не является допустимым или в $D'_{ab}$, или в $\widetilde{D}_{ab}$. В первом случае $\phi_0=\phi'_0 \sqcup \{a, b\}$ и $\phi'_0$ допустимо во всех четырех дельта-матроидах. Если ровно один элемент из $\{a,b\}$ принадлежит $\phi$, то расстояния от $\phi$ до $\phi_0$ и $\phi'_0$ равны. Следовательно, все четыре расстояния от $\phi$ до дельта-матроидов равны $|\phi \Delta \phi'_0|$. Если ни $a$, ни $b$ не принадлежат множеству $\phi$, то $|\phi \Delta \phi'_0|<|\phi \Delta \phi_0|$, поэтому такой случай невозможен. Если оба элемента $a$ и $b$ принадлежат множеству $\phi$, то $|\phi \Delta \phi'_0|=|\phi \Delta \phi_0|+2$. Предположим, что хотя бы одно из расстояний от $\phi$ до $\widetilde{D}_{ab}$ и $\widetilde{D}'_{ab}$ меньше этого значения. Тогда это расстояние достигается для некоторого $\phi_1$ либо из $\widetilde{\Phi}_{ab}$, либо из $\widetilde{\Phi}'_{ab}$. Если множество $\phi_1$ допустимо в обоих этих дельта-матроидах, то равенство (1) выполняется. Иначе $\phi_1=\phi'_1 \sqcup \{a\}$, $b\notin \phi'_1$ и $\phi'_1 \sqcup \{b\}$ допустимо в обоих дельта-матроидах. По предположению $a, b \in \phi$, а значит, расстояния от $\phi$ до $\phi_1$ и $\phi'_1 \sqcup \{b\}$ равны. Во втором случае $\phi_0=\phi'_0 \sqcup \{a\}$ и $\phi'_0 \sqcup \{b\}$ допустимо во всех четырех дельта-матроидах. Если $a$ и $b$ одновременно принадлежат $\phi$ или одновременно не принадлежат $\phi$, получаем, что $|\phi \Delta \phi_0|=|\phi \Delta (\phi_0' \sqcup \{b\})|$. Поэтому расстояние от $\phi$ до $D$ равно трем другим расстояниям. Если $b$ принадлежит множеству $\phi$, а $a$ – нет, то $|\phi \Delta (\phi_0' \sqcup \{b\})|=|\phi \Delta \phi_0|-2$, что невозможно в рассматриваемом случае. В ином случае верно, что $\phi = \phi' \sqcup \{a\}$ и $b \notin \phi$. Тогда расстояния от $\phi$ до $D'_{ab}$ и $\widetilde{D}'_{ab}$ не больше $|\phi \Delta (\phi_0' \sqcup \{b\})|=|\phi \Delta \phi_0|+2$. Если одно из расстояний меньше этого значения, то оно достигается для некоторого допустимого множества $\phi_1$ и второе расстояние имеет то же значение. Действительно, либо $\phi_1$ допустимо во втором дельта-матроиде, либо $\phi_1=\phi_1' \sqcup \{a, b\}$, $\phi_1'$ также допустимо, и число элементов в $\phi \Delta \phi_1$ такое же, как в $\phi \Delta \phi_1'$. Таким образом, для любого множества $\phi$ мы доказали, что либо все четыре расстояния равны между собой, либо есть две пары равных расстояний. $\square$ В [10] показано, что любой инвариант бинарных дельта-матроидов, удовлетворяющий четырехчленному соотношению, определяет инвариант зацеплений конечного типа. А значит, мы получаем Следствие 1. Многочлен переплетений бинарных дельта-матроидов определяет инвариант зацеплений конечного типа в $3$-сфере. § 3. Многочлен переплетений примитивных элементов алгебры Хопфа дельта-матроидовВ этом параграфе мы изучаем различающую силу многочлена переплетений бинарных дельта-матроидов. Бинарные дельта-матроиды порождают коммутативную кокоммутативную алгебру Хопфа. Эта алгебра Хопфа является алгеброй многочленов от своих примитивных элементов, и имеет смысл рассматривать ограничение полиномиального инварианта на подпространство примитивных элементов (которое однозначно задает инвариант). В частности, различающая сила мультипликативного инварианта может быть измерена как размерность пространства его значений на подпространстве примитивных элементов степени $n$. Для многочлена переплетений графов Н. Нетрусова [14] доказала, что пространство значений многочлена переплетений на примитивных элементах, состоящих из графов с $n$ вершинами, имеет размерность $[{n}/2]$ (т.е. целая часть величины ${n}/2$) для $n\geqslant2$. Это утверждение можно сравнить с аналогичным для хроматического многочлена – для него такая размерность будет равна $1$ для всех $n=1,2,3,\dots$ . Наш основной результат в этом направлении состоит в следующем. Мы доказали, что размерность пространства значений многочлена переплетений бинарных дельта-матроидов размерности $n$ равна $n$ для всех целых неотрицательных $n$. 3.1. Алгебра Хопфа бинарных дельта-матроидовОпределим произведение и копроизведение бинарных дельта-матроидов в векторном пространстве $\mathcal{B}$, свободно порожденном всеми бинарными дельта-матроидами. Пространство $\mathcal{B}$ является градуированным, т.е. $\mathcal{B}=\mathcal{B}_{0} \oplus \mathcal{B}_{1} \oplus \mathcal{B}_{2} \oplus \dotsb$, где $\mathcal{B}_{k}$ – это подпространство, порожденное классами изоморфизма бинарных дельта-матроидов с $k$ элементами в базовом множестве. Произведение дельта-матроидов $D_{1}=(E_{1}, \Phi_{1})$ и $D_{2}=(E_2, \Phi_2)$ таких, что $E_1\cap E_2=\varnothing$, – это дельта-матроид $D=(E_1 \sqcup E_2, \Phi)$, где $\Phi = \{\phi_1 \sqcup \phi_2 \mid \phi_1 \in \Phi_1\text{ и }\phi_2 \in \Phi_2\}$. Это произведение, продолженное по линейности на пространство $\mathcal{B}$, делает его коммутативной алгеброй. Единицей в этой алгебре является дельта-матроид, базовое множество которого пустое. Алгебра является градуированной, поскольку произведение $m$ уважает градуировку:
$$
\begin{equation*}
m\colon \mathcal{B}_k \otimes \mathcal{B}_l \to \mathcal{B}_{k+l}.
\end{equation*}
\notag
$$
Копроизведение дельта-матроида $D=(E, \Phi)$ определяется равенством
$$
\begin{equation*}
\mu(D)=\sum_{E'\subset E} D_{E'} \otimes D_{E\setminus E'},
\end{equation*}
\notag
$$
где $D_{E'}=D\setminus(E\setminus E')$ – ограничение дельта-матроида $D$ на $E'$. Определение 11. Элемент $p$ биалгебры называется примитивным, если ${\mu(p)=1\otimes p+p\otimes 1}$. Примитивные элементы образуют векторное подпространство в $\mathcal{B}$. Для каждого $n$ подпространство $\mathcal{B}_n$ является прямой суммой подпространства примитивных элементов и подпространства разложимых элементов, которое порождено произведениями элементов меньшей размерности. Это разложение определяет проекцию пространства $\mathcal{B}_n$ на его подпространство примитивных элементов. Согласно [8] проекция дельта-матроида $D=(E, \Phi)$ на подпространство примитивных элементов задается формулой
$$
\begin{equation*}
\pi(D)=D-1!\times \sum_{E_1 \sqcup E_2 = E} D_{E_1} D_{E_2} +2!\times \sum_{E_1 \sqcup E_2 \sqcup E_3 = E} D_{E_1} D_{E_2} D_{E_3} - \dotsb.
\end{equation*}
\notag
$$
Здесь $k\textrm{-я}$ сумма берется по всем неупорядоченным разбиениям базового множества $E$ на $k$ непустых подмножеств $E_1, \dots,E_k$. 3.2. Многочлен переплетений примитивных элементовБудем говорить, что многочлен выделяет $k$ примитивных элементов в размерности $n$, если он имеет $k$ линейно независимых значений на подпространстве примитивных элементов, состоящих из дельта-матроидов с $n$ элементами в базовом множестве. Докажем несколько лемм, которые нам потребуются в дальнейшем. Лемма 1. Пусть $D=(E, \Phi)$ – дельта-матроид, соответствующий $(n\times n)$-матрице $A=((a_{ij}))_{i, j=1}^{n}$, а $A'$ – матрица размера $(n+1)\times(n+1)$, полученная добавлением $(n+1)$-й строки и $(n+1)$-го столбца в матрицу $A$ с $a_{1, n+1}=a_{n+1, 1}=1$ и $a_{i, n+1}=a_{n+1, i}=0$ для всех $i$ от $2$ до $n+1$. Пусть $D'$ – дельта-матроид, соответствующий матрице $A'$. Тогда Доказательство. Из теоремы 2 следует, что Поскольку $D'\setminus \{n+1\} = D$, остается проверить, что
Множество $\phi$ допустимо в $(D' * \{n+1\}) \setminus \{n+1\}$ тогда и только тогда, когда $\phi$ не содержит $n+1$ и $\phi \sqcup \{n+1\}$ допустимо в $D'$. Каждое такое множество содержит $1$, поскольку в квадратных подматрицах $A'$, включающих в себя последнюю строку и не включающих в себя первый столбец, последняя строка состоит только из нулей, а значит, подмножество, соответствующее такой матрице, не может быть допустимым. Кроме того, множество $\phi \sqcup \{1\}$ допустимо в $(D' * \{n+1\}) \setminus \{n+1\}$ тогда и только тогда, когда $\phi$ допустимо в $D\setminus 1$. Действительно,
$$
\begin{equation*}
\det \begin{pmatrix} a_{11} & \dots & 1\\ \dots & A[\phi] & 0\\ \dots & & \dots\\ 1 & 0\dots & 0\\ \end{pmatrix} = \det\begin{pmatrix} a_{11} \dots & 1\\ & 0\\ A[\phi] & \dots\\ & 0\\ \end{pmatrix} = \det (A[\phi]).
\end{equation*}
\notag
$$
Тогда
$$
\begin{equation*}
\begin{aligned} \, &q_{\Delta}((D' * \{n+1\}) \setminus \{n+1\}, x) =\sum_{X \subset E} x^{d_{(D' * \{n+1\}) \setminus \{n+1\}} (X)} \\ &\qquad =\sum_{X \subset E\setminus \{1\}} (x^{d_{(D' * \{n+1\}) \setminus \{n+1\}} (X)} + x^{d_{(D' * \{n+1\}) \setminus \{n+1\}} (X\sqcup \{1\})}) \\ &\qquad =\sum_{X \subset E\setminus \{1\}} (x^{d_{D \setminus \{1\}} (X)+1} + x^{d_{D \setminus \{1\}} (X)}) \\ &\qquad =\sum_{X \subset E\setminus \{1\}} x^{d_{D \setminus \{1\}} (X)} (x+1) =q_{\Delta}(D\setminus \{1\}, x) (x+1). \end{aligned}
\end{equation*}
\notag
$$
$\square$ Ниже мы будем обозначать $(D^{[k]})'$ через $D^{[k+1]}$, где $D^{[0]}=D$. Лемма 2. Пусть $D_{n}$ – дельта-матроид $(\{1, \dots, n\}; \{\varnothing, \{1\}, \dots, \{n\}\})$. Тогда при $n>1$ многочлен переплетений его проекции на подпространство примитивных элементов имеет ненулевой свободный член, который равен ${(-1)^{n-1} (n-1)!}$. Замечание 4. Я благодарна С. К. Ландо за помощь в доказательстве того, что сумма слагаемых в свободном члене действительно равна $(-1)^{n-1} (n-1)!$. Доказательство. Дельта-матроид $D_{n}$ соответствует матрице размера $n\times n$, каждый элемент которой равен $1$. Его проекция на подпространство примитивных элементов равна .
Каждый из дельта-матроидов $D_{E_i}$ также соответствует матрице, каждый элемент которой равен единице, это матрица $|E_i| \times |E_i|$. То есть $D_{E_i} = D_{|E_i|}$. Для произвольного $k$ от $1$ до $n$ в дельта-матроиде $D_k$ ровно $k+1$ допустимых множеств, а именно: $\varnothing$, $\{1\}, \dots,\{k\}$. Значит, свободный член многочлена $q_{\Delta}(D_k, x)$ равен $k+1$. Действительно, слагаемое в сумме $\sum_{X \subset \{1,\dots, k\}} x^{d_{D_{k}}(X)}$ равно $x^0=1$ тогда и только тогда, когда $X$ допустимо. Таким образом, свободный член многочлена $q_{\Delta}(\pi(D_n), x)$ равен
$$
\begin{equation*}
\begin{aligned} \, n+1 &-1!\times\sum_{\substack{E_1\sqcup E_2=E\\ E_1\ne\varnothing,\,E_2\ne\varnothing}} (|E_1|+1)(|E_2|+1) \\ &+2!\times\sum_{\substack{E_1\sqcup E_2\sqcup E_3=E\\ E_1\ne\varnothing,\,E_2\ne\varnothing,\,E_3\ne\varnothing}} (|E_1|+1)(|E_2|+1)(|E_3|+1)-\dotsb. \end{aligned}
\end{equation*}
\notag
$$
Докажем, что эта сумма равна $(-1)^{n-1}(n-1)!$ для $n\geqslant 2$. Рассмотрим подалгебру $\mathcal K$ алгебры Хопфа графов $\mathcal G$ над полем $\mathbb Q$, порожденную полными графами. Обозначим полный граф на $n$ вершинах через $K_n$, $n=0,1,2,\dots$, и рассмотрим экспоненциальную производящую функцию
$$
\begin{equation*}
\mathcal K(t)=\sum_{n=0}^\infty K_n\frac{t^n}{n!} =1+K_1\frac{t^1}{1!}+K_2\frac{t^2}{2!}+\dotsb
\end{equation*}
\notag
$$
(здесь мы пользуемся тем, что пустой граф $K_0$ является единицей в алгебре Хопфа графов).
Рассмотрев в алгебре Хопфа полных графов $\mathcal K$ проекцию $\pi\colon \mathcal K\to\mathcal P(\mathcal K)$ на подпространство примитивных элементов, ядро которой – это подпространство разложимых элементов, получим
$$
\begin{equation*}
\begin{aligned} \, \pi(\mathcal K(t)) &=\sum_{n=0}^\infty \pi(K_n)\frac{t^n}{n!} =\log\mathcal K \\ &=K_1\frac{t^1}{1!}+(K_2-K_1^2)\frac{t^2}{2!}+(K_3-3K_1K_2+2K_1^3)\frac{t^3}{3!}+\dotsb. \end{aligned}
\end{equation*}
\notag
$$
Здесь коэффициент перед $K_1^{m_1}K_2^{m_2}\dots$ по модулю равен числу разбиений множества $E$ на $m_1$ одноэлементных множеств, $m_2$ двухэлементных и так далее. И это именно те разбиения, которые возникают в проекции $\pi(D_n)$. Рассмотрим мультипликативное отображение $\varphi\colon \mathcal K\to\mathbb C$, значение которого на $K_n$ равно $n+1$. Для этого отображения имеем
$$
\begin{equation*}
\begin{aligned} \, \varphi\mathcal K(t) &=\sum_{n=0}^\infty\varphi(K_n)\frac{t^n}{n!} =1+\varphi(K_1)\frac{t^1}{1!}+\varphi(K_2)\frac{t^2}{2!}+\dotsb \\ &=1+2\cdot\frac{t^1}{1!}+3\cdot\frac{t^2}{2!}+4\cdot\frac{t^3}{3!}+\dotsb \\ &=\biggl(\frac{t^1}{0!}+\frac{t^2}{1!}+\frac{t^3}{2!}+\frac{t^4}{3!}+\dotsb\biggr)' =(te^t)'=(1+t)e^t. \end{aligned}
\end{equation*}
\notag
$$
Теперь запишем логарифм производящей функции $\varphi\mathcal K$:
$$
\begin{equation*}
\log\varphi\mathcal K(t)=\varphi\log\mathcal K(t) =\sum_{n=0}^\infty\varphi(\pi(K_n))\frac{t^n}{n!}
\end{equation*}
\notag
$$
(первое равенство верно, так как отображение $\varphi$ мультипликативно).
С другой стороны,
$$
\begin{equation*}
\begin{aligned} \, \log\varphi\mathcal K(t) &=\log((1+t)e^t)=t+\log(1+t)=t+\sum_{n=1}^\infty(-1)^{n-1}\frac{t^n}{n} \\ &=t+\sum_{n=1}^\infty(-1)^{n-1}(n-1)!\frac{t^n}{n!}. \end{aligned}
\end{equation*}
\notag
$$
Сравнивая эти две формулы логарифма производящей функции $\varphi\mathcal K$, мы можем сделать вывод, что доказываемое равенство верно, а значит, у $\pi(D_n)$ ненулевой свободный член. $\square$ Лемма 3. Если $D$ – дельта-матроид, соответствующий некоторой матрице, и $D'$ получен из $D$ как в лемме 1, то Замечание 5. Доказательство этой леммы аналогично доказательству похожей леммы для графов в [14]. Доказательство. Разбиения множества $E\sqcup \{n+1\}$ на непустые подмножества могут быть разделены на три типа: те, в которых $1$ и $n+1$ принадлежат одному подмножеству, те, в которых $n+1$ составляет отдельное подмножество, и те, в которых $1$ и $n+1$ принадлежат разным подмножествам, причем $n+1$ не составляет отдельное подмножество. Предположим, что $1$ принадлежит $E_1$.
В первом случае дельта-матроид, соответствующий разбиению $E_1\sqcup\dots \sqcup E_k$, – это $(D')_{E_1} (D')_{E_2} \dots (D')_{E_k}$. Он изоморфен дельта-матроиду $(D')_{E_1}D_{E_2}\dots D_{E_k}$, поскольку и $n+1$, и $1$ принадлежат $E_1$. Многочлен переплетений такого дельта-матроида равен
$$
\begin{equation*}
\begin{aligned} \, &q_{\Delta}((D')_{E_1}D_{E_2}\dots D_{E_k}, x) =q_{\Delta}((D')_{E_1}, x) \cdot q_{\Delta}(D_{E_2}, x) \dotsb q_{\Delta}(D_{E_k}, x) \\ &\qquad =(q_{\Delta}(D_{E_1}, x) + (x+1)q_{\Delta}(D_{E_1} \setminus 1, x)) \cdot q_{\Delta}(D_{E_2}, x) \dotsb q_{\Delta}(D_{E_k}, x) \\ &\qquad =q_{\Delta}(D_{E_1}\dots D_{E_k}, x) + (x+1) \cdot q_{\Delta}(D_{E_1 \setminus 1} D_{E_2} \dotsb D_{E_k}, x). \end{aligned}
\end{equation*}
\notag
$$
Теперь рассмотрим второй случай. Обозначим через $D_{\{n+1\}}$ ограничение дельта-матроида $D'$ на множество $\{n+1\}$, т.е. дельта-матроид ${(\{n+1\}; \{\varnothing\})}$. Для произвольного дельта-матроида $M$ с $n$ элементами в базовом множестве допустимыми множествами $MD_{\{n+1\}}$ являются исключительно допустимые множества $M$, так как единственным допустимым множеством $D_{\{n+1\}}$ является пустое множество. Значит, расстояние от некоторого множества до дельта-матроида $MD_{\{n+1\}}$ равно расстоянию до дельта-матроида $M$, если это множество не содержит $n+1$, или на $1$ больше расстояния до $M$, если множество содержит $n+1$. Поэтому
$$
\begin{equation*}
\begin{aligned} \, &q_{\Delta}(MD_{\{n+1\}}, x) =\!\sum_{X \subset \{1,\dots, n+1\}} x^{d_{MD_{\{n+1\}}}(X)} =\!\sum_{X \subset \{1,\dots, n\}} \bigl(x^{d_M(X)} + x^{d_M(X \sqcup \{n+1\})}\bigr) \\ &\qquad =\sum_{X \subset \{1,\dots, n\}} x^{d_M(X)}(1 + x) =(x+1)q_{\Delta}(M, x). \end{aligned}
\end{equation*}
\notag
$$
Наконец, если элемент $n+1$ попал в $i$-е множество, представим это множество в виде $E_i \sqcup \{n+1\}$, $i\neq1$, $E_i\neq \{n+1\}$. Тогда $D_{E_i \sqcup \{n+1\}}=D_{E_i} D_{\{n+1\}}$. Действительно, $n+1$ не является элементом ни одного из допустимых множеств в $D_{E_i \sqcup \{n+1\}}$, а единственное допустимое множество в $D_{\{n+1\}}$ – это пустое множество, значит, у произведения $D_{E_{i}}$ и $D_{\{n+1\}}$ такой же набор допустимых множеств, как у $D_{E_{i}}$ и $D_{E_{i} \sqcup \{n+1\}}$. Следовательно, количество слагаемых вида $D_{E_1} \dots D_{E_k} D_{\{n+1\}}$ в проекции дельта-матроида $D'$ на подпространство примитивных элементов равно $k-1$, поскольку $n+1$ можно добавить в каждое из подмножеств $E_2,E_3, \dots, E_k$. Теперь рассмотрим проекцию $\pi(D')$ и значение многочлена переплетений на ней:
$$
\begin{equation*}
\begin{aligned} \, &\pi (D') =D' - \sum_{E_1\sqcup E_2 = E} D'_{E_1} D_{E_2} +2!\times \sum_{E_1\sqcup E_2 \sqcup E_3= E} D'_{E_1} D_{E_2} D_{E_3} -\dotsb \\ &\qquad\qquad - D D_{\{n+1\}} + 2!\times \sum_{E_1 \sqcup E_2 =E} D_{E_1} D_{E_2} D_{\{n+1\}} - \dotsb \\ &\qquad\qquad - \sum_{E_1 \sqcup E_2 =E} D_{E_1} D_{E_2} D_{\{n+1\}} \\ &\qquad\qquad+ 2! \cdot 2\times \sum_{E_1\sqcup E_2 \sqcup E_3 =E} D_{E_1} D_{E_2} D_{E_3} D_{\{n+1\}} - \dotsb \end{aligned}
\end{equation*}
\notag
$$
и
$$
\begin{equation*}
\begin{aligned} \, &q_{\Delta}(\pi(D'), x) =q_{\Delta}\biggl(D - \sum_{E_1\sqcup E_2 = E} D_{E_1} D_{E_2} + \dotsb, x\biggr) \\ &\qquad\qquad +(x+1)q_{\Delta}\biggl(D\setminus 1 - \sum_{E_1\sqcup E_2 = E} D_{E_1 \setminus 1} D_{E_2} \dots, x\biggr) \\ &\qquad\qquad + (x+1)q_{\Delta}\biggl(-D+2!\times \sum_{E_1\sqcup E_2 = E} D_{E_1} D_{E_2} - \dotsb, x\biggr) \\ &\qquad\qquad + (x+1)q_{\Delta}\biggl(-\sum_{E_1\sqcup E_2 = E} D_{E_1} D_{E_2} \\ &\qquad\qquad\qquad+2! \cdot 2\times \sum_{E_1\sqcup E_2\sqcup E_3 = E} D_{E_1} D_{E_2} D_{E_3} - \dotsb, x\biggr) \\ &\qquad=q_{\Delta}(\pi(D), x)+(x+1)q_{\Delta}\biggl(D\setminus 1 - \sum_{E_1\sqcup E_2 = E} D_{E_1 \setminus 1} D_{E_2} \dots\biggr) \\ &\qquad\qquad +(x+1)q_{\Delta}\biggl(-D + (2!-1)\sum_{E_1\sqcup E_2 = E} D_{E_1} D_{E_2} \\ &\qquad\qquad\qquad -(3!-2\cdot 2!) \sum_{E_1\sqcup E_2\sqcup E_3 = E} D_{E_1} D_{E_2} D_{E_3} + \dotsb, x\biggr) \\ &\qquad=q_{\Delta}(\pi(D), x)+\biggl((x+1)q_{\Delta} \biggl(D\setminus 1 - \sum_{E_1\sqcup E_2 = E} D_{E_1 \setminus 1} D_{E_2} \dots, x\biggr) \\ &\qquad\qquad +(x+1)q_{\Delta}(-\pi(D), x). \end{aligned}
\end{equation*}
\notag
$$
Теперь остается доказать, что
$$
\begin{equation*}
D\setminus 1 - \sum_{E_1\sqcup E_2 = E} D_{E_1 \setminus 1} D_{E_2} + 2! \times\sum_{E_1\sqcup E_2\sqcup E_3 = E} D_{E_1 \setminus 1} D_{E_2} D_{E_3} \dotsc=0.
\end{equation*}
\notag
$$
Каждое слагаемое кроме первого и последнего включает разбиения двух типов. В некоторых из них в множестве $E_1$ есть хотя бы один элемент, отличный от $1$. В остальных $E_1 = \{1\}$. Первое слагаемое – элемент первого типа, а последнее – второго типа. Если удалить элемент $1$ из дельта-матроида $D_{\{1\} \sqcup E_2 \sqcup \dots \sqcup E_{k}}$, то получится дельта-матроид $D_{E_2 \sqcup \dots \sqcup E_{k}}$. В предыдущем слагаемом содержится ровно $k-1$ таких дельта-матроидов первого типа, так как можно добавить элемент $1$ к любому множеству из $E_2,\dots,E_k$, получив в результате разбиение множества $E$ на $k-1$ подмножеств и соответствующий ему дельта-матроид. В сумме первый дельта-матроид умножается на $(-1)^{k-1}(k-1)!$, а остальные умножаются на $(-1)^{k-2}(k-2)!$, а значит, их сумма равна нулю. Таким образом, вся сумма равна нулю и $q_{\Delta}(\pi (D'), x) = -x \cdot q_{\Delta}(\pi (D), x)$. $\square$ Лемма 4. Пусть $D_{K_n}$ – это дельта-матроид полного графа на $n$ вершинах. Степень многочлена $q_{\Delta}(\pi(D_{K_n}), x)$ равна $n$, а для любого $k$ от $0$ до $n-2$ степень многочлена $q_{\Delta}(\pi(D_{n-k}^{[k]}), x)$ меньше $n$. Доказательство. Многочлен переплетений произвольного дельта-матроида – это многочлен с неотрицательными коэффициентами. Его степень не превосходит $n$, поскольку количество элементов в симметрической разности двух подмножеств базового множества не может превышать $|E| = n$.
Заметим, что пустое множество является допустимым в каждом из этих дельта-матроидов, а значит, оно является допустимым в каждом слагаемом их проекций. Следовательно, расстояние от множества до дельта-матроида не больше количества элементов множества. Оно может быть равно $n$ только для множества с $n$ элементами, т.е. для базового множества, и только если дельта-матроид не имеет других допустимых множеств кроме пустого. Поскольку каждое множество из двух элементов является допустимым в $D_{K_n}$, единственное слагаемое в его проекции, удовлетворяющее этому условию, – это последнее слагаемое, соответствующее разбиению базового множества на $n$ непустых подмножеств. Следовательно, многочлен переплетений проекции $\pi(D_{K_n})$ – это многочлен степени $n$, а коэффициент при $x^n$ равен $(-1)^{n-1}(n-1)!$ . Кроме того, если в дельта-матроиде существует одноэлементное допустимое множество, то оно остается допустимым в каждом слагаемом проекции. Это означает, что ни для одного из дельта-матроидов $D_{n-k}^{[k]}$ многочлен переплетений не будет многочленом степени $n$ (множество $\{1\}$ допустимо в каждом из них). $\square$ Теорема 5. Многочлен переплетений дельта-матроидов выделяет ровно $n$ примитивных элементов в размерности $n$. Доказательство. Покажем, что проекции дельта-матроидов $D_{n},D_{n-1}^{[1]},\dots,D_{2}^{[n-2]}$ и $D_{K_n}$ имеют линейно независимые значения многочлена переплетений.
Докажем это индукцией по $n$. Предположим, что
$$
\begin{equation*}
q_{\Delta}(\pi(D_{n-1}), x), \quad \dots, \quad q_{\Delta}(\pi(D_{2}^{[n-3]}), x)
\end{equation*}
\notag
$$
линейно независимы. Тогда по лемме 3
$$
\begin{equation*}
\begin{gathered} \, q_{\Delta}(\pi(D_{n}), x) = -x \cdot q_{\Delta}(\pi(D_{n-1}), x), \qquad \dots, \\ q_{\Delta}(\pi(D_{2}^{[n-2]}), x) = -x \cdot q_{\Delta}(\pi(D_{2}^{[n-3]}), x) \end{gathered}
\end{equation*}
\notag
$$
также линейно независимы. Все эти многочлены делятся на $x$, следовательно, $q_{\Delta}(\pi(D_{n}), x)$ линейно независим с ними, поскольку имеет ненулевой свободный член по лемме 2.
Остается проверить, что многочлен $q_{\Delta}(\pi(D_{K_n}), x)$ линейно независим со всеми остальными многочленами. Как следует из леммы 4, степень многочлена $q_{\Delta}(\pi(D_{K_n}), x)$ равна $n$, а степени других многочленов меньше $n$. $\square$
Цитирование в формате AMSBIB
\RBibitem{Kod25} |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|