| Успехи математических наук |
|
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье) Циклические накрытия графов. Перечисление отмеченных остовных лесов и деревьев, индекс Кирхгофа и якобианы А. Д. Медныхab, И. А. Медныхab a Институт математики им. С. Л. Соболева Сибирского отделения Российской академии наук b Новосибирский государственный университет
Англоязычная версия:
Russian Mathematical Surveys, 2023, Volume 78, Issue 3, Pages DOI: https://doi.org/10.4213/rm10098e 
Реферативные базы данных:
    1. ВведениеЦель настоящего обзора – изучение инвариантов циклических накрытий графов. При этом накрываемый граф предполагается фиксированным, а циклическая группа накрытия имеет сколь угодно большой порядок. Классическим примером таких накрытий являются циркулянтные графы. Они накрывают одновершинный граф с заданным числом петель. Более сложными представителями семейства циклических накрытий являются $I$-, $Y$-, $H$-графы, обобщенные графы Петерсена, сэндвич-графы, дискретные торы и многие другие. В обзоре приводятся аналитические формулы, позволяющие вычислять число отмеченных остовных лесов и деревьев в циклических накрытиях, найдена их асимптотика и изучены арифметические свойства этих чисел. Кроме того, для циркулянтных графов указаны точные формулы для вычисления индекса Кирхгофа и установлено, что, с точностью до экспоненциально малого остаточного члена, они задаются полиномами третьей степени. Все указанные инварианты являются спектральными – их значения определяются спектром матрицы Лапласа. Особое место отводится якобианам графов, которые, с нашей точки зрения, являются дискретными версиями якобианов римановых поверхностей. Якобиан графа можно определить как максимальную абелеву группу, порожденную потоками на графе, удовлетворяющими первому и второму законам Кирхгофа. По классической теореме Кирхгофа порядок этой группы совпадает с числом остовных деревьев в графе. Указанная группа, которую также называют песочной группой, группой Пикара, критической группой, долларовой группой или группой компонент, была независимо введена многими авторами. Важной особенностью якобиана графа является его неспектральный характер. Существуют графы с одинаковыми спектрами, но разными якобианами. В то же время существуют графы с одинаковыми якобианами, но разными спектрами. В обзоре приводятся структурные формулы для вычисления якобианов циркулянтных графов и их простейших аналогов. Основная техника вычисления всех указанных выше инвариантов базируется на использовании полиномов Чебышёва и их свойств. 2. Основные определенияДля удобства читателя в текущем разделе мы определим циклические накрытия графов и опишем их основные инварианты. Основное внимание будет уделено спектральным инвариантам графов, таким как число остовных деревьев, число отмеченных остовных лесов и индекс Кирхгофа. Кроме того, будут приведены структурные теоремы для вычисления якобиана графа, который, вообще говоря, не является спектральным инвариантом. 2.1. Базовое понятие графа. Остовные леса и деревьяВ рамках данного обзора графом $G$ будем называть неориентированный конечный мультиграф с петлями. Для удобства будем считать, что каждое ребро, включая петли, ориентированo двумя возможными способами. Обозначим через $V(G)$ и $E(G)$ множество его вершин и множество его ребер соответственно. Деревом называется связный граф, не содержащий циклов. Несвязное объединение деревьев называется лесом. Отмеченным деревом назовем дерево с одной выделенной вершиной (корнем). Лес, состоящий из отмеченных деревьев, называется отмеченным лесом. Остовное дерево в связном графе $G$ – это подграф $G$, который содержит все вершины графа $G$ и является деревом. Oстовный лес в графе $G$ – это подграф $G$, который содержит все вершины графа $G$ и является лесом. 2.2. Матрица Лапласа для графа и его спектральные свойстваРассмотрим конечный граф $G$, допускающий кратные ребра, но не имеющий петель. Матрица $A=A(G)=(a_{u,v})_{u,v\in V(G)}$, где $a_{u,v}$ – число ребер между вершинами $u$ и $v$, называется матрицей смежности графа $G$. Обозначим через $d(v)$ степень вершины $v\in V(G)$ и рассмотрим диагональную матрицу $D=D(G)$ с элементами $d_{v,v}=d(v)$. Матрица $L=L(G)=D(G)-A(G)$ называется матрицей Лапласа или лапласианом графа $G$. Отметим, что матрица Лапласа всегда вырождена и неотрицательно определена. Количество нулевых собственных значений этой матрицы равно числу компонент связности графа. В частности, матрица Лапласа связного графа имеет ровно одно нулевое собственное значение, а все остальные ее собственные значения – положительны [70]. Для более общих рассуждений нам потребуется расширить понятие лапласиана графа. Пусть $X=\{x_v,v\in V(G)\}$ – набор независимых переменных, а $D(X)$ – диагональная матрица, образованная элементами $x_v$, $v\in V(G)$. Определим обобщенный лапласиан графа $G$ как $L(G,X)=D(X)-A(G)$. 2.3. Теорема Кирхгофа о числе остовных деревьевОдним из основных инвариантов заданного графа является его сложность, определяемая как число его остовных деревьев. Если граф не связен, то его сложность равна нулю. Для связного графа сложность выражается по классической теореме Кирхгофа [45]. Она равна произведению всех ненулевых собственных значений матрицы Лапласа, поделенному на число вершин графа. Эту величину можно найти и как определитель произвольного главного минора матрицы Лапласа. Со времен Кирхгофа было опубликовано множество работ, посвященных изучению сложности различных семейств графов (см., например, [88], [77], [78], [36], [85], [11], [10]). 2.4. Теорема Кельманса–Челнокова и число отмеченных остовных лесовНаряду с подсчетом остовных деревьев также представляет интерес задача о числе отмеченных остовных лесов в заданном графе. Рассмотрим граф $G$ на $n$ вершинах. Пусть – характеристический полином его матрицы Лапласа $L(G)$. Представим его в виде
$$
\begin{equation*}
\chi_{G}(\lambda)=\lambda^n+c_{n-1}\lambda^{n-1}+\cdots+c_1\lambda.
\end{equation*}
\notag
$$
Согласно классическому результату [44] величина $|c_k|$ совпадает с числом отмеченных остовных лесов в графе $G$, состоящих из $k$ деревьев. В силу неотрицательности собственных значений матрицы Лапласа $L(G)$ последовательность коэффициентов $c_1,c_2,\dots,c_{n-1},c_{n}$, где $c_{n}=1$, знакопеременна. Поэтому справедлива следующая формула для подсчета числа отмеченных остовных лесов в графе $G$:
$$
\begin{equation}
\begin{aligned} \, f(G)&=f_{1}+f_{2}+f_{3}+\cdots+f_{n}= |c_{1}-c_{2}+c_{3}-\cdots+(-1)^{n-1}c_{n}| \notag \\ &=(-1)^{n}\chi_{G}(-1)=\det(I_{n}+L(G)). \end{aligned}
\end{equation}
\tag{1}
$$
Этот результат был независимо получен авторами работ [16], [47], [32] и др. В то же время об аналитических формулах для числа остовных лесов известно очень немного. В частности, П. Чеботарёв [14] перечислил отмеченные остовные леса в путевых и циклических графах, а О. Книл [47] доказал, что число отмеченных остовных лесов в полном графе $K_n$ на $n$ вершинах равно $(n+1)^{n-1}$. Отмеченные остовные леса в полных двудольных графах были перечислены в [42]. Явные формулы для числа отмеченных остовных лесов для циклических, звездчатых и некоторых других графах даны в [47]. Что касается выражения для количества неотмеченных лесов, оно обычно имеет гораздо более сложную структуру [13], [53], [86]. 2.5. Индекс КирхгофаПусть $G$ – связный конечный граф на $n$ вершинах. Обозначим через $L(G)$ матрицу Лапласа графа $G$. Известно [70], что если граф связен, то все собственные значения $L(G)$, за исключением одного, равного нулю, положительны. Иными словами, спектр матрицы Лапласа графа $G$ имеет вид $0=\lambda_{0}<\lambda_{1}\leqslant\cdots\leqslant\lambda_{n-1}$. Первоначально индекс Кирхгофа графа $G$ был определен Д. Клейном и М. Рандичем [46] как суммарное резистивное расстояние между его вершинами. Напомним соответствующее определение. Пронумеруем вершины графа $G$ числами $1,2,\dots,n$. Тогда резистивное расстояние между вершинами $i$ и $j$, обозначаемое $r_{i,j}=r_{i,j}(G)$, определяется как эффективное сопротивление между ними, если мы наделим каждое ребро $G$ единичным сопротивлением. Следуя [46], определим индекс Кирхгофа графа $G$ как величину
$$
\begin{equation*}
\operatorname{Kf}(G)=\sum_{1\leqslant i<j\leqslant n}r_{i,j}.
\end{equation*}
\notag
$$
Такое определение было мотивировано известным индексом Винера [89], определяемым как где $d_{i,j}$ обозначает расстояние между вершинами $i$ и $j$. Клейн и Рандич [46] показали, что $\operatorname{Kf}(G)\leqslant W(G)$, где равенство достигается тогда и только тогда, когда граф $G$ является деревом. Интересная связь между индексом Кирхгофа и спектром матрицы Лапласа была независимо найдена в работах [34] и [95]. Справедлива формула
$$
\begin{equation}
\operatorname{Kf}(G)=n\sum_{j=1}^{n-1}\frac{1}{\lambda_j}\,.
\end{equation}
\tag{2}
$$
Индексы Кирхгофа для различных семейств графов были изучены в работах [56], [73], [92], [91], [57], [19], [43], [5]. 2.6. Мера МалераВ последние десятилетия исследования асимптотического поведения сложности графов проводились с точки зрения изучения меры Малера [35], [80], [81]. Общие свойства меры Малера изложены в обзоре [82] и монографии [26]. Интересно отметить, что мера Малера тесно связана с ростом групп, значениями гипергеометрических функций и объемами гиперболических многообразий [12]. Приведем основные определения. Рассмотрим полином
$$
\begin{equation*}
P(z)=a_{0}z^{s}+\cdots+a_{s-1}z+a_{s}= a_{0}\prod_{i=1}^{s}(z-\alpha_i),\qquad a_{0}\ne0,
\end{equation*}
\notag
$$
с комплексными коэффициентами. Следуя [58], определим его меру Малера формулой
$$
\begin{equation}
M(P)=\exp\biggl(\int_{0}^{1}\log|P(e^{2\pi\mathtt{i}t})|\,dt\biggr)
\end{equation}
\tag{3}
$$
– среднее значение модуля $|P(z)|$ по единичной окружности $|z|=1$. Отметим, что величина $M(P)$ появилась ранее в работе Д. Лемера [52] в несколько иной форме Эквивалентность этих определений следует из формулы Йенсена [41]
$$
\begin{equation*}
\int_{0}^{1}\log|e^{2\pi\mathtt{i}t}-\alpha|\,dt=\log_{+}|\alpha|,
\end{equation*}
\notag
$$
где $\log_{+}x$ обозначает $\max(0,\log x)$. Иногда более удобной для исследований является малая мера Малера, определяемая как
$$
\begin{equation*}
m(P):=\log M(P)=\int_{0}^{1}\log|P(e^{2\pi\mathtt{i}t})|\,dt.
\end{equation*}
\notag
$$
Определение меры Малера может быть естественным образом расширенно на класс полиномов Лорана
$$
\begin{equation*}
R(z)=a_{s}z^{p}+a_{s-1}z^{p+1}+\cdots+a_{1}z^{p+s-1}+a_{0}z^{p+s}= a_{0}z^{p}\prod_{i=1}^{s}(z-\alpha_i),
\end{equation*}
\notag
$$
где $a_{0},a_{s}\ne0$ и $p$ – произвольное целое число. 2.7. ЯкобианыРассмотренные выше инварианты графа (сложность, число отмеченных лесов, индекс Кирхгофа) являются спектральными инвариантами. Иначе говоря, они зависят от собственных значений матрицы Лапласа. Однако существуют инварианты, не зависящие от спектра матрицы Лапласа. Характерным примером такого инварианта является якобиан (группа якобиана) графа. Эта группа также известна как группа Пикара, критическая группа, долларовая группа (dollar group) или группа песочной кучи (sandpile group). Данное понятие было независимо введено многими авторами в последние десятилетия [24], [22], [6], [9], [4], [48]. Раньше всего оно появилось в статистической физике при исследовании модели песочной кучи [24]. В дальнейшем оно также было открыто как эффективный инструмент нахождения стабильного финансового положения в банковской системе [9]. Это понятие возникает и как дискретная версия якобиана из классической теории римановых поверхностей [6]. Теоретико-числовой подход к этому понятию реализован в работе [4]. Некоторые аспекты этой теории с точки зрения математической кристаллографии даются в [48]. Следуя [54], дадим определение якобиана $\operatorname{Jac}(G)$ графа $G$. Рассмотрим лапласиан $L(G)$ как гомоморфизм $\mathbb{Z}^{|V|}\to\mathbb{Z}^{|V|}$, где $|V|=|V(G)|$ – число вершин в графе $G$. Его коядро
$$
\begin{equation*}
\operatorname{coker}(L(G))=\mathbb{Z}^{|V|}/\operatorname{im}(L(G))
\end{equation*}
\notag
$$
– некоторая абелева группа. Пусть
$$
\begin{equation*}
\operatorname{coker}(L(G))\cong\mathbb{Z}_{d_{1}}\oplus\mathbb{Z}_{d_{2}} \oplus\cdots\oplus\mathbb{Z}_{d_{|V|}}
\end{equation*}
\notag
$$
– ее нормальная форма Смита, однозначно определенная условиями $d_i\mid d_{i+1}$, $1\leqslant i\leqslant|V|-1$. Если граф $G$ связен, то группы ${\mathbb Z}_{d_{1}},{\mathbb Z}_{d_{2}},\dots,{\mathbb Z}_{d_{|V|-1}}$ конечны, а $\mathbb{Z}_{d_{|V|}}=\mathbb{Z}$. Определим группу якобиана (или просто якобиан) графа $G$ как подгруппу кручения коядра $\operatorname{coker}(L(G))$. Другими словами,
$$
\begin{equation*}
\operatorname{Jac}(G)\cong\mathbb{Z}_{d_{1}}\oplus\mathbb{Z}_{d_{2}} \oplus\cdots\oplus\mathbb{Z}_{d_{|V|-1}}.
\end{equation*}
\notag
$$
Группа якобиана – важный алгебраический инвариант конечного графа. В частности, ее порядок совпадает с числом остовных деревьев в графе. В то же время структура якобиана известна только в конкретных случаях [40], [22], [9], [54]. Структура якобиана для циркулянтных графов, $I$-графов и обобщенных графов Петерсена была изучена в работах [49], [60], [68]. Напомним, что класс вышеупомянутых графов достаточно широк и включает в себя циклические графы, полные графы, лестницу Мёбиуса, антипризму и другие графы. Для простейших бесконечных семейств графов группа якобина была описана явно, а в общем случае мы представляем более эффективный метод ее нахождения. Заметим, что число остовных деревьев для графов, а также структуру якобиана во многих случаях можно выразить в терминах полиномов Чебышёва. Есть очень важное наблюдение о структуре группы якобиана. Порядок якобиана как абелевой группы совпадает со сложностью графа. Иначе говоря, порядок якобиана – спектральная характеристика графа. В то же время существуют графы, которые имеют одинаковый спектр лапласиана, но неизоморфные якобианы [4]. 3. Циклические накрытия графов3.1. Общее определение циклического накрытия графаПусть даны два графа $G=(V(G),E(G))$ и $H=(V(H),E(H))$. Сюръективное отображение $f\colon V(G)\to V(H)$ называется накрывающим отображением из $G$ в $H$ (или просто накрытием), если для каждого $v\in V(G)$ сужение $f$ на окрестность вершины $v$ является биекцией в окрестность вершины $f(v)$ в $H$. Напомним, что окрестностью вершины $v$ графа $G$ называется подграф, индуцированный вершиной $v$ и всеми ее смежными вершинами в графе $G$ (см. [27; п. 6.8]). Группа преобразований наложения (covering group) накрытия $f$ состоит из всех автоморфизмов $g$ графа $G$, сохраняющих проекцию, т. е. таких, что $f\circ g=f$. Накрытие называется циклическим, если группа преобразований наложения – циклическая и ее порядок совпадает с кратностью накрытия. Существует несколько подходов к описанию циклических накрытий графов: топологический – основанный на теории накрывающих пространств [59], геометрический – основанный на теории униформизации [7], и алгебраический – в его основе лежит теория напряжения графов (voltage assignment) [30]. В случае, когда граф $G$ обладает циклической группой автоморфизмов $\mathbb{Z}_n$, действующей без неподвижных точек на множестве вершин и множестве ориентированных ребер графа, циклическое накрытие возникает как естественная проекция $G\to G/\mathbb{Z}_n$. 3.2. Циркулянтные графы и их спектрыПростейшими представителями циклических накрытий графов являются циркулянтные графы. Они представляют собой циклические накрытия над одновершинным графом с заданным числом петель. Также их можно определить как графы Кэли циклических групп [21]. Нам будет удобно пользоваться следующим эквивалентным определением. Пусть $n>1$ – целое положительное число. Рассмотрим конечный набор целых чисел $s_1,s_2,\dots,s_k$ таких, что $1\leqslant s_1<s_2<\cdots<s_k\leqslant n/2$. Определим циркулянтный граф $G=C_{n}(s_1,s_2,\dots,s_k)$ как граф на $n$ вершинах $0,1,2,\dots,{n-1}$, в котором вершина $i$, $0\leqslant i\leqslant n-1$, смежна с вершинами $i\pm s_1,i\pm s_2,\dots,i\pm s_k$ $(\bmod \ n)$. Величины $s_1,s_2,\dots,s_k$ называются скачками графа $G$. В случае $s_k<n/2$ все вершины графа имеют степень $2k$. Если же $n$ четно и $s_k=n/2$, то все вершины графа имеют степень $2k- 1$. Хорошо известно, что граф $C_n(s_1,s_2,\dots,s_k)$ связен тогда и только тогда, когда $\operatorname{gcd}(s_1,s_2,\dots,s_k,n)= 1$. В общем случае число связных компонент графа $C_n(s_1,s_2,\dots,s_k)$ равно $d=\operatorname{gcd}(s_1,s_2,\dots,s_k,n)$. При этом вершины $0,1,\dots,d-1$ лежат в разных компонентах связности и каждая компонента связности изоморфна графу $C_{n/d}(s_1/d,s_2/d,\dots,s_k/d)$. Если $d>1$, то граф $G$ не связен. Он не имеет остовных деревьев, но имеет остовные леса. В дальнейшем, если не оговорено обратное, все графы предполагаются связными. Два циркулянтных графа $C_{n}(s_1,s_2,\dots,s_k)$ и $C_{n}(\tilde{s}_1,\tilde{s}_2,\dots,\tilde{s}_k)$ называются сопряженными, если существует взаимно простое с $n$ целое число $r$ такое, что наборы чисел $\{\tilde{s}_1,\tilde{s}_2,\dots,\tilde{s}_k\}$ и $\{rs_1,rs_2,\dots,rs_k\}$ совпадают как подмножества циклической группы $\mathbb{Z}_n$. В данном случае умножение вершин на $r$ $(\bmod \ n)$ задает изоморфизм графов. В 1967 г. А. Адам предположил, что два циркулянтных графа изоморфны в том и только том случае, когда они сопряжены [3]. Целью этой гипотезы была классификация циркулянтных графов с точностью до изоморфизма. Однако оказалось, что гипотеза Адама не верна. В качестве контрпримера можно указать два графа $C_{16}(1,2,7)$ и $C_{16}(2,3,5)$. Они не сопряжены, но изоморфны [21]. Полное решение проблемы изоморфизма для циркулянтных графов дал М. Музычук [71]. С. А. Евдокимов и И. Н. Пономаренко [25] показали, что циркулянтные графы распознаются за полиномиальное время в множестве всех графов. Циркулянтной матрицей будем называть матрицу следующей структуры:
$$
\begin{equation*}
\begin{pmatrix} a_0 & a_1 & a_2 & \dots & a_{n-1} \\ a_{n-1} & a_0 & a_1 & \dots & a_{n-2} \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ a_1 & a_2 & a_3 & \dots & a_0 \\ \end{pmatrix}.
\end{equation*}
\notag
$$
Матрицу такого типа будем обозначать через $\operatorname{circ}(a_0,a_1,\dots,a_{n-1})$. Несложно заметить, что матрица смежности и матрица Лапласа циркулянтного графа циркулянтны. Верно и обратное: если матрица Лапласа некоторого графа циркулянтна (при подходящей нумерации вершин), то сам граф также циркулянтен. Напомним [23], что собственные значения матрицы $C=\operatorname{circ}(a_0,a_1,\dots,a_{n-1})$ задаются простыми формулами где $p(z)=a_0+a_1 z+\cdots+a_{n-1}z^{n-1}$ и $\varepsilon_n$ – первообразный корень степени $n$ из единицы. Кроме того, рассмотренная циркулянтная матрица представима в виде где $T=\operatorname{circ}(0,1,0,\dots,0)$ – матричное представление оператора циклического сдвига
$$
\begin{equation*}
(x_0,x_1,\dots,x_{n-2},x_{n-1})\to(x_1,x_2,\dots,x_{n-1},x_0).
\end{equation*}
\notag
$$
Это дает ключ к описанию лапласиана и его спектра для произвольного циркулянтного графа. А именно, вместе с каждым циркулянтным графом $G=C_{n}(s_1,s_2,\dots,s_k)$ рассмотрим сопровождающий полином Лорана Тогда лапласиан графа $G$ представляется в виде $L(G)=P(T)$, а его спектр задается числами $\lambda_j=P(\varepsilon^j_n)$, $j=0,1,\dots,n-1$.3.3. Циркулянтные расслоения графовПусть $H$ – связный конечный граф с вершинами $v_1,v_2,\dots,v_m$, возможно с кратными ребрами, но без петель. Обозначим через $a_{i,j}$ количество ребер между вершинами $v_i$ и $v_j$. Так как $H$ не имеет петель, то $a_{i,i}=0$. Для построения циркулянтного расслоения $H_n=H_n(G_1,G_2,\dots,G_m)$ каждой вершине $v_i$ припишем циркулянтный граф $G_i=C_n(s_{i,1},s_{i,2},\dots,s_{i,k_i})$. В случае, когда $G_i=C_{n}(\varnothing)$ – пустой граф на $n$ вершинах, полагаем $k_{i}=1$ и $s_{i,1}=0$. Циркулянтное расслоение над $H$ со слоями $G_1,G_2,\dots,G_m$ – это граф с множеством вершин
$$
\begin{equation*}
V(H_n)=\{(k,v_i), \ k=1,2,\dots,n, \ i=1,2,\dots,m\}.
\end{equation*}
\notag
$$
При фиксированном $k$ вершины $(k,v_i)$ и $(k,v_j)$ соединены $a_{i,j}$ ребрами, а при фиксированном $i$ вершины $(k,v_i)$, $k=1,2,\dots,n$, образуют циркулянтный граф $C_n(s_{i,1},s_{i,2},\dots,s_{i,k_i})$, в котором вершина $(k,v_i)$ смежна с вершинами
$$
\begin{equation*}
(k\pm s_{i,1},v_i), \ (k\pm s_{i,2},v_i),\ \dots, \ (k\pm s_{i,k_i},v_i) \pmod{n}.
\end{equation*}
\notag
$$
Далее по тексту будем называть $H$ базовым графом или базой циркулянтного расслоения $H_{n}$. Важным аспектом такого определения является наличие слоев, образованных пустыми циркулянтными графами $C_{n}(\varnothing)$, т. е. графами, состоящими из $n$ изолированных вершин. Это значительно расширяет класс исследуемых объектов и, в частности, позволяет включить в него $Y$- и $H$-графы, а также их обобщения. Отметим некоторые свойства циркулянтных расслоений. Существует проекция $\varphi\colon H_n\to H$, переводящая вершины $(k,v_i)$, $k=1,\dots,n$, и ребра между ними в вершины $v_i$, а ребра между вершинами $(k,v_i)$ и $(k,v_j)$, $i\ne j$, взаимно однозначно в ребра между вершинами $v_i$ и $v_j$. При этом для каждой вершины $v_i$ графа $H$ имеем $\varphi^{-1}(v_i)=G_i$, $i=1,2,\dots,m$. Это отображение, удобное с топологической и комбинаторной точек зрения, вообще говоря, не является накрытием графов. Для построения накрытия рассмотрим действие циклической группы $\mathbb{Z}_n$ на графе $H_n$, определенное правилом $(k,v_{i})\to(k+1,v_{i})$, $k \!\pmod{n}$. Тогда группа $\mathbb{Z}_n$ действует без неподвижных точек на множестве вершин и ориентированных ребер графа, а факторграф $H_{n}/\mathbb{Z}_{n}$ представляет собой оснащенный граф $\widehat{H}$, полученный из графа $H$ присоединением $k_i$ петель к каждой $i$-й вершине графа $H$. Таким образом, $H_n$ является $n$-листным циклическим накрытием над оснащенным графом $\widehat{H}$. 3.4. Семейства циркулянтных расслоений: $I$-, $Y$-, $H$-графы и дискретные торыВ данном пункте приводится описание нескольких семейств циркулянтных расслоений, представляющих циклические накрытия над простейшими графами. Вначале мы рассмотрим сэндвич-граф $\operatorname{SW}_n=H_n(G_1,G_2,\dots,G_m)$, составленный из циркулянтных графов $G_i=C_n(s_{i,1},s_{i,2},\dots,s_{i,k_i})$, $i=1,2,\dots,m$. Чтобы построить $\operatorname{SW}_n$, в качестве базового графа $H$ выберем путевой граф (path graph) на $m$ вершинах $v_1,v_2,\dots,v_m$ с концами $v_1$ и $v_m$. Важным частным случаем такой конструкции является $I$-граф $I(n,k,l)$, который возникает при $m=2$ и имеет два циклических слоя $G_1=C_n(k)$ и $G_2=C_n(l)$. Обобщенный граф Петерсена $\operatorname{GP}(n,k)$ – это также $I$-граф с параметрами $n,k$ и $l=1$ [83]. Сэндвич $H_n(G_1,G_2)$ двух произвольных циркулянтных графов $G_1$ и $G_2$ рассматривался в работе [2]. Следующим примером может служить семейство обобщенных $Y$-графов $Y_n=Y_n(G_1,G_2,G_3)$. Чтобы его построить, в качестве базы $H$ рассмотрим $Y$-образный граф на четырех вершинах $v_1$, $v_2$, $v_3$, $v_4$ с тремя ребрами $v_1v_4$, $v_2v_4$, $v_3v_4$. Одновалентным вершинам графа $H$ припишем циркулянтные графы $G_1$, $G_2$, $G_3$, а его центральной вершине – пустой циркулянтный граф $G_4=C_n(\varnothing)$. Тогда, по определению циркулянтных расслоений, мы полагаем $Y_n=H_n(G_1,G_2,G_3,G_4)$. В частности, при $G_1=C_n(k)$, $G_2=C_n(l)$ и $G_3=C_n(m)$ возникает $3$-регулярный $Y$-граф $Y(n;k,l,m)$, определенный ранее в [8], [37]. Еще один пример – обобщенный $H$-граф $H_n(G_1,G_2,G_3,G_4,G_5,G_6)$, где $G_1$, $G_2$, $G_3$ и $G_4$ – произвольные циркулянтные графы, а $G_5=G_6=C_n(\varnothing)$ – пустые графы на $n$ вершинах. В этом случае базовым графом служит граф $H$ с вершинами $v_1$, $v_2$, $v_3$, $v_4$, $v_5$, $v_6$ и ребрами $v_1v_5$, $v_5v_3$, $v_2v_6$, $v_6v_4$, $v_5v_6$. В частном случае, когда $G_1=C_n(i)$, $G_2=C_n(j)$, $G_3=C_n(k)$, $G_4=C_n(l)$, имеем $3$-регулярный граф $H(n;i,j,k,l)$, исследованный в работе [37]. Для простоты мы будем использовать обозначение $H_n(G_1,G_2,G_3,G_4)$, опуская символику для пустых графов. Дискретный тор – декартово произведение циклических графов $C_n$ и $C_m$. Его можно рассматривать также как циркулянтное расслоение
$$
\begin{equation*}
T_{n,m}=H_{n}(\,\underbrace{C_{n}(1),\dots,C_{n}(1)}_{m \text{ раз }}\,)
\end{equation*}
\notag
$$
с базой $H=C_{m}(1)$ и $m$ одинаковыми слоями $C_{n}(1),\dots,C_{n}(1)$. 3.5. Циклическое накрытие общего видаПусть $H$ – конечный связный граф с вершинами $v_1,v_2,\dots,v_r$ (возможно, с петлями и кратными ребрами). Для описания общей конструкции $n$-листного циклического накрытия графа $H$ рассмотрим циклическую группу $\Gamma=\langle\mathbb{Z}_n,+\rangle$, состоящую из вычетов по модулю $n$. Для удобства будем считать, что все ребра $H$, включая петли, ориентированы двумя возможными способами. Для любого ориентированного ребра $e$ графа $H$ противоположно ориентированное ребро обозначим через $\bar{e}$. Используя метод напряжений (voltage assignment), разработанный в [30], припишем каждому ориентированному ребру $e$ графа $H$ напряжение $\alpha(e)$, а именно некоторый элемент группы $\Gamma$. Следуем правилу, согласно которому сумма напряжений, приписанных двум противоположно ориентированным ребрам, равна нулю, т. е. $\alpha(e)+\alpha(\bar{e})=0$. Для любых $i,j=1,\dots,r$ и любых $k=1,\dots,a_{i,j}$ обозначим напряжение $k$-го ориентированного ребра от $v_i$ до $v_j$ через $\alpha_k(i,j)$. Для различных $i$ и $j$ будем считать, что $\alpha_k(j,i)=-\alpha_k(i,j)$. Поскольку каждая петля имеет две противоположные ориентации, можно взять напряжение $\alpha_k(i,i)$ для одной из них (выбранной произвольно) и $-\alpha_k(i,i)$ для другой. Рассмотрим $n$-листное циклическое накрытие $H_n=H_{n}(\alpha)$ графа $H$, полученное при помощи задания напряжений $\alpha=\{\alpha_k(i,j)$, $i,j=1,\dots,r$, $k=1,\dots,a_{i,j}\}$. Согласно общей теории [30] граф $H_{n}$ имеет множество вершин $u_{i,s}$, $i=\!1,2,\dots,r$, $s\kern-1pt=\!1,2,\dots,n$, и множество ребeр $v_{i,s}v_{j,s+\alpha_k(i,j)}$, где $i,j\kern-1pt=\kern-1pt 1,2,\dots,r$, $k=\!1,2,\dots,a_{i,j}$, а вторые индексы берутся по модулю $n$. Отметим, что таким образом можно получить все циклические $n$-кратные накрытия графа $H$. Эта конструкция охватывает циркулянтные графы, графы Хаара, циркулянтные расслоения и многие другие семейства графов. 4. Циркулянтные графы с четным числом скачков4.1. Теорема о числе остовных деревьевВ этом пункте будут даны аналитические формулы для числа остовных деревьев в циркулянтных графах $C_{n}(s_1,s_2,\dots,s_k)$ с четной степенью вершин. Приведенные ниже результаты принадлежат авторам настоящей статьи и опубликованы в работах [61] и [62]. Следует отметить, что близкие по духу результаты были получены ранее в работах [93], [18], [94]. Предложенный ниже подход представляется более простым и удобным. Он позволяет получить формулы для функции сложности в замкнутом виде и детально исследовать ее арифметические свойства. Кроме того, явный вид полученной формулы позволяет найти ее асимптотику через геометрические параметры графа и меру Малера его сопровождающего полинома. В случае, когда граф имеет четную степень вершин, справедлива следующая теорема [62; теорема 1, следствие 1]. Теорема 4.1. Число $\tau(n)$ остовных деревьев циркулянтного графа дается формулой при этом $q=s_1^2+s_2^2+\cdots+s_k^2$ и $w_p$, $p=1,2,\dots,s_k-1$, – отличные от единицы корни алгебраического уравнения где $Q(w)=\displaystyle\sum_{j=1}^k(T_{s_j}(w)-1)$, а $T_k(w)$ – полином Чебышёва первого рода. 4.2. Асимптотика числа остовных деревьевРассмотрим бесконечное семейство графов $G_n$, $n\in \mathbb{N}$, и обозначим через $\tau(n)=\tau(G_n)$ число остовных деревьев в графе $\tau(G_n)$. Во многих случаях важно знать асимптотическое поведение функции $\tau(n)$. Обозначим через $v(G_n)$ число вершин графа $G_n$. Величина (если она существует) называется термодинамическим пределом (а также древесной энтропией или балком) семейства $G_n$. Изучению этой величины для различных семейств графов посвящено значительное количество работ по статистической физике (см., например, [87], [90], [79], [35], [55]).В этом пункте будут приведены асимптотические формулы для числа остовных деревьев циркулянтных графов, полученные в [61] и [62]. Интересно сопоставить эти результаты с результатами работ [93], [18], [94] и [55], где аналогичные асимптотики получены другими методами. Имеет место следующий результат [62; теорема 2]. Теорема 4.2. Число остовных деревьев циркулянтного графа имеет следующую асимптотику: где $A=\exp\biggl(\displaystyle\int_{0}^{1} \log|P(e^{2\pi\mathrm{i}t})|\,dt\biggr)$ – мера Малера сопровождающего полинома Лорана $P(z)=2k-\displaystyle\sum_{i=1}^k(z^{s_i}+z^{-s_i})$, а $q=s_1^2+s_2^2+\cdots+s_k^2$. Непосредственно из теоремы 4.2 вытекает следующий результат, ранее полученный в работах [93], [94]. Следствие 4.1. Термодинамический предел последовательности циркулянтных графов $C_{n}(s_1,s_2,\dots,s_k)$ равен малой мере Малера сопровождающего полинома Лорана $P(z)$. Другими словами, где $m(P)=\displaystyle\int_0^1\log|P(e^{2\pi\mathrm{i}t})|\,dt$ и $P(z)=2k-\displaystyle\sum_{i=1}^k(z^{s_i}+z^{-s_i})$. 4.3. Рациональность производящей функции для числа остовных деревьевСледующая теорема, доказанная в [65], дает положительный ответ на вопрос С. К. Ландо о рациональности производящей функции для числа остовных деревьев в циркулянтном графе. Теорема 4.3. Пусть $\tau(n)$ – число остовных деревьев в циркулянтном графе $C_{n}(s_1,s_2,\dots,s_k)$. Тогда – рациональная функция с целыми коэффициентами. Кроме того, $F(z)=F(1/z)$. Заметим, что радиус сходимости ряда $F(z)$ равен $R=1/A$, где $A$ – мера Малера сопровождающего полинома Лорана графа $C_{n}(s_1,s_2,\dots,s_k)$. Это непосредственно следует из теоремы 4.2 и формулы Коши–Адамара. 4.4. Арифметические свойства числа остовных деревьевВ серии работ [93], [18], [94] было замечено, что во многих важных случаях число остовных деревьев циркулянтного графа дается формулой $\tau(n)=n\,a(n)^2$, где $a(n)$ – некоторая целочисленная последовательность. Однако это верно не всегда. Например, в случае графа $C_n(1,3)$ и четного $n$ мы имеем $\tau(n)=2n\,a(n)^2$ для некоторой целочисленной последовательности $a(n)$. Цель настоящего пункта – объяснить этот феномен. Напомним, что каждое целое положительное число $p$ однозначно представляется в виде $p=q\,r^2$, где $p$ и $q$ целые положительные числа, а $q$ – свободно от квадратов. Мы будем называть $q$ свободной от квадратов частью числа $p$. Справедлива следующая теорема [61], [62]. Теорема 4.4. Обозначим через $\tau(n)$ число остовных деревьев в циркулянтном графе $C_{n}(s_1,s_2,\dots,s_k )$, где $1\leqslant s_1<s_2<\cdots<s_k<n/2$. Пусть $p$ – количество нечетных чисел в последовательности $s_1,s_2,\dots,s_k$ и $q$ – свободная от квадратов часть числа $p$. Тогда существует целочисленная последовательность $a(n)$ такая, что (a) $\tau(n)=n\,a(n)^2$, если $n$ нечетно; (b) $\tau(n)=q \,n\,a(n)^2$, если $n$ четно. Сделаем следующее замечание. В теореме 4.4 величину $p$ можно заменить на максимальное собственное значение матрицы Лапласа графа $C_{n}(s_1,s_2,\dots,s_k)$. Как следует из результатов работы [62], оно равно Приведем несколько примеров, иллюстрирующих приведенные выше результаты. Пример 4.1 (граф $C_n(1,2)$). В этом случае $\tau(n)=nF_n^2$, где $F_n$ – числа Фибоначчи, $A=(3+\sqrt{5}\,)/2$, $q=5$ и $\tau(n)\sim(n/5)A^n$, $n\to\infty$. Кроме того, Пример 4.2 (граф $C_n(1,3)$). Теорема 4.1 дает следующую формулу для числа остовных деревьев: Далее, где $w$ – то же, что и в предыдущем примере. Пример 4.3 (граф $C_n(2,3)$). По теореме 4.1 4.5. Индекс Кирхгофа и его асимптотикаЦель настоящего пункта – привести полученную в [64] явную аналитическую формулу для индекса Кирхгофа циркулянтного графа $C_{n}(s_{1},s_{2},\dots,s_{k})$, а также изучить ее асимптотическое поведение при $n$, стремящемся к бесконечности. Указанные формулы представлены в виде конечного, не зависящего от $n$ числа слагаемых, каждое из которых представляет собой рациональную функцию, вычисленную в корнях некоторого заданного полинома. Теорема 4.5. Индекс Кирхгофа циркулянтного графа $G_{n}=C_{n}(s_{1},s_{2},\dots,s_{k})$ вычисляется по формуле где $w_{p}$ – отличные от единицы корни полинома а $T_{n}(w)$ и $U_{n-1}(w)$ – полиномы Чебышёва первого и второго рода соответственно. Как следствие, мы получим приводимую ниже асимптотическую формулу поведения индекса Кирхгофа для циркулянтных графов $G_{n}=C_{n}(s_{1},s_{2},\dots,s_{k})$ при $n$, стремящемся к бесконечности [64; следствие 1]. Следствие 4.2. Имеет место асимптотическая формула где $P(z)=2k-\displaystyle\sum_{j=1}^{k}(z^{s_{j}}+z^{-s_{j}})$, а $A=\min\{|z|\colon P(z)=0,|z|>1\}$ – константа, зависящая только от $s_1,s_2,\dots,s_k$. Заметим, что главный член асимптотики представляет собой кубический полином от $n$ со свободным членом, равным нулю. Рассмотрим несколько примеров, иллюстрирующих приведенные выше результаты. Пример 4.5 (граф $C_{n}(1,2)$). Для данного семейства графов индекс Кирхгофа может быть вычислен по формуле где $F_{n}$ – $n$-е число Фибоначчи. Заметим, что где $\phi=(1+\sqrt{5}\,)/2$ – золотое сечение. Пример 4.6 (граф $C_{n}(1,3)$). Индекс Кирхгофа семейства циркулянтных графов $C_n(1,3)$ имеет следующее асимптотическое поведение: где $A=\sqrt{(1+\sqrt{5}+\sqrt{2(1+\sqrt{5}\,)}\,)/2}\simeq 1.700015\dots$ . 5. Циркулянтные графы с нечетной степенью вершин5.1. Число остовных деревьев в графах с нечетной степеньюВ случае циркулянтных графов нечетной валентности число остовных дервьев находится следующим образом [62; теорема 2]. Теорема 5.1. Пусть $C_{2n}(s_1,s_2,\dots,s_k,n)$, где $1\leqslant s_1<s_2<\cdots<s_k< n$, – циркулянтный граф нечетной валентности. Тогда число остовных деревьев $\tau(n)$ графа $C_{2n}(s_1,s_2,\dots,s_k,n)$ дается формулой где $q=s_1^2+s_2^2+\cdots+s_k^2$, числа $u_p$, $p=1,2,\dots,s_k-1$, и $v_p$, $p=1,2,\dots,s_k$, являются соответственно корнями алгебраических уравнений где $Q(w)=2k+1-2\displaystyle\sum_{i=1}^{k}T_{s_i}(w)$, а $T_k(w)$ – полином Чебышёва первого рода. 5.2. Асимптотика числа остовных деревьев в графах с нечетной степеньюСледующие два результата получены в работе [62]. Теорема 5.2. Рассмотрим циркулянтный граф $G_n=C_{2n}(s_1,s_2,\dots,s_k,n)$, $1\leqslant s_1 < s_2 < \cdots < s_k < n$. Положим $\operatorname{gcd}(s_1,s_2,\dots,s_k)=d$. Тогда число остовных деревьев в графе $G_n$ имеет следующее асимптотическое поведение: Здесь $q=s_1^2+s_2^2+\cdots+s_k^2$ и – мера Малера полинома Лорана $P(z)(P(z)+2)$, где $P(z)=2k-\displaystyle\sum_{j=1}^{k}(z^{s_{j}}+z^{-s_{j}})$. Следствие 5.1. Термодинамический предел последовательности циркулянтных графов $C_{2n}(s_1,s_2,\dots,s_k,n)$ равен малой мере Малера сопровождающего полинома Лорана $R(z)=P(z)(P(z)+2)$, где $P(z)=2k-\displaystyle\sum_{j=1}^{k}(z^{s_{j}}+z^{-s_{j}})$. Другими словами, где $m(R)=\displaystyle\int_0^1\log|R(e^{2\pi\mathrm{i}t})|\,dt$. 5.3. Арифметические свойства графов с нечетной степенью вершинСледующая теорема описывает арифметические свойства числа остовных деревьев в циркулянтных графах с нечетной степенью вершин [62; теорема 3]. Теорема 5.3. Обозначим через $\tau(n)$ число остовных деревьев циркулянтного графа $C_{2n}(s_1,s_2,\dots,s_k,n)$, где $1\leqslant s_1< s_2<\cdots< s_k< n/2$. Пусть $p$ – количество нечетных чисел в последовательности $s_1,s_2,\dots,s_k$. Пусть $q$ – свободная от квадратов часть числа $2p$, а $r$ – свободная от квадратов часть числа $2p+1$. Тогда существует целочисленная последовательность $a(n)$ такая, что (a) $\tau(n)=r\,n\,a(n)^2$, если $n$ нечетно; (b) $\tau(n)=q\,n\,a(n)^2$, если $n$ четно. Как следует из доказательства теоремы 4 в [62], максимальное собственное значение $\lambda_{\max}$ матрицы Лапласа графа $C_{2n}(s_1,s_2,\dots,s_k,n)$ равно $4p+2$, если $n$ нечетно, и $4p$, если $n$ четно. Это позволяет в формулировке теоремы 5.3 заменить обе величины $r$ и $q$ на $\lambda_{\max}/2$. 5.4. Индекс Кирхгофа для графов с нечетной степенью вершинЯвные аналитические формулы для индекса Кирхгофа циркулянтных графов вида $C_{2n}(s_{1},s_{2},\dots,s_{k},n)$, а также их асимптотикa при $n$, стремящемся к бесконечности, приведены в [64]. Эти формулы представляют собой рациональные выражения от полиномов Чебышёва и их производных. Мы ограничимся лишь частным случаем этого результата, независимо полученным в работах [19] и [5]. Приведем родственный результат, разными методами установленный в работах [20] и [5]. Теорема 5.5. Индекс Кирхгофа призматического графа $\operatorname{Pr}_n=C_n\times P_2$ дается формулой 5.5. Производящая функция для числа остовных деревьевТеорема о рациональности производящей функции для числа остовных деревьев в графе $C_{2n}(s_{1},s_{2},\dots,s_{k},n)$, аналогичная теореме 4.3, доказана в статье [65]. 5.6. ПримерыПриведем небольшую серию примеров, представляющих результаты, сформулированные в разделе 5. Пример 5.1 (лестница Мёбиуса $C_{2n}(1,n)$). Для данного семейства графов по теореме 5.1 имеем Пример 5.2 (графы $C_{2n}(1,2,n)$). Применяя теорему 5.2, получим где $K_{1,2}=(3+\sqrt{5})(4+\sqrt{3}+\sqrt{15+8\sqrt{3}}\,)/4\approx 14.54\dots$ . Также, в силу теоремы 5.3, существует целочисленная последовательность $a(n)$ такая, что $\tau(n)=2n\,a(n)^2$, если $n$ четно, и $\tau(n)=3n\,a(n)^2$, если $n$ нечетно. 6. Циркулянтные графы с неограниченными скачкамиВ этом разделе мы рассматриваем особый класс циркулянтных графов, а именно циркулянтные графы с неограниченными скачками. Они определяются так же, как раньше, но со специальными ограничениями на количество вершин и структуру скачков. Точнее, мы будем иметь дело с циркулянтными графами
$$
\begin{equation*}
G_n=C_{\beta n}(s_1,s_2,\dots,s_k, \alpha_1n,\alpha_2n,\dots,\alpha_{\ell}n),
\end{equation*}
\notag
$$
определенными на $\beta\,n$ вершинах, со скачками $s_1,s_2,\dots,s_k$, $\alpha_{1}n,\alpha_{2}n,\dots,\alpha_{\ell}n$, удовлетворяющими неравенствам
$$
\begin{equation*}
1\leqslant s_1<s_2<\cdots<s_k<\biggl[\frac{\beta n}{2}\biggr],\qquad 1\leqslant\alpha_1<\alpha_2<\cdots<\alpha_{\ell}\leqslant \biggl[\frac{\beta}{2}\biggr].
\end{equation*}
\notag
$$
Нас интересует исследование таких графов при достаточно больших $n$. В дальнейшем $s_1,s_2,\dots,s_k$, $\alpha_1,\alpha_2,\dots,\alpha_{\ell}$, $\beta$ предполагаются фиксированными целыми положительными числами. В частности, граф $G_n$ не имеет кратных ребер, если $\alpha_{\ell}<\beta/2$. Если $\alpha_{\ell}=\beta/2$, то граф имеет ровно два ребра между вершинами $v_i$ и $v_{i+\beta\,n/2}$, где индексы берутся по модулю $\beta\,n$. В указанном случае $\beta$ – заведомо четное число. Типичным примером является граф $C_{2n}(1,n)$, который, в соответствии с приведенным выше соглашением, представляет собой лестницa Мëбиуса на $2n$ вершинах с двойными ступенями. Замечание 6.1. В разделе 5 и в серии статей [93], [18], [61], [62], посвященных циркулянтным графам с нечетной степенью вершин, символ $C_{2n}(1,n)$ используется для обозначения лестницы Мëбиуса с одинарными ступенями. Степень вершин такого графа нечетна и равна 3. Чтобы избежать разночтения, лестницу Мëбиуса с двойными ступенями будем обозначать через $C''_{2n}(1,n)$. 6.1. Остовные деревья в циркулянтных графах с неограниченными скачкамиСледующий результат получен в работе [67]. Теорема 6.1. Число остовных деревьев в циркулянтном графе с неограниченными скачками В качестве следствия из теоремы 6.1 получается результат Ж. Луис, установленный в работе [55] в несколько иной форме. Следствие 6.1. Число остовных деревьев в циркулянтном графе с неограниченными скачками задается формулой где $T_n(w)$ – полином Чебышёва первого рода. Отметим еще одно следствие из теоремы 6.1. Следствие 6.2. Число остовных деревьев в циркулянтном графе с неограниченными скачками 6.2. Арифметические свойства числа остовных деревьев в циркулянтных графах с неограниченными скачкамиАрифметические свойства числа остовных деревьев в циркулянтных графах с неограниченными скачками представлены в следующей теореме [67; теорема 5.1]. Теорема 6.2. Обозначим через $\tau(n)$ число остовных деревьев в циркулянтном графе где $1\leqslant s_1<s_2<\cdots<s_k<[\beta n/2]$ и $1\leqslant\alpha_1<\alpha_2<\cdots<\alpha_\ell\leqslant [\beta/2]$. Пусть $p$ и $q$ соответствуют количествам нечетных элементов в последовательностях $s_1,s_2,\dots,s_k$ и $\alpha_1,\alpha_2,\dots,\alpha_\ell$. Положим $r$ равным свободной от квадратов части числа $p$, а $s$ равным свободной от квадратов части числа $p+q$. Тогда существует целочисленная последовательность $a(n)$ такая, что (a) $\tau(n)=\beta\,n\,a(n)^2$, если $\beta\,n$ нечетно; (b) $\tau(n)=\beta\,r\,n\,a(n)^2$, если $n$ четно; (c) $\tau(n)=\beta\,s\,n\,a(n)^2$, если $n$ нечетно, а $\beta$ четно. 6.3. Асимптотика числа остовных деревьев в циркулянтных графах с неограниченными скачкамиСправедлива следующая теорема, описывающая асимптотику числа остовных деревьев [67]. Теорема 6.3. Пусть $\operatorname{gcd}(s_1,s_2,\dots,s_k)=d$ и $\operatorname{gcd}(\alpha_1,\alpha_2,\dots,\alpha_\ell,\beta)=1$. Тогда число остовных деревьев в циркулянтном графе с неограниченными скачками Приведем несколько примеров, иллюстрирующих приведенные выше результаты. Пример 6.1 (граф $C''_{2n}(1,n)$ – лестница Мёбиуса с двойными ступенями). Применяя теорему 6.1, получим Интересно сравнить этот результат с аналогичным результатом, полученным в [94; теорема 4]. Напомним [11], что число остовных деревьев в лестнице Мёбиуса с одинарными ступенями равно $n(T_n(2)+1)$. Пример 6.2 (граф $C_{2n}(1,2,n)$). В данном примере имеем Пример 6.3 (граф $C_{2n}(1,2,3,n)$). Для этого семейства графов число остовных деревьев задается формулой где а $\omega_1$, $\omega_2$, $\omega_3$ – корни кубического уравнения $2w^3+w^2-w-3=0$. Также имеем следующие арифметические свойства: $\tau(n)=6n\,a(n)^2$, если $n$ нечетно, и $\tau(n)=4n\,a(n)^2$, если $n$ четно. Кроме того, $\tau(n)\sim(n/28)A^{n}$, $n\to\infty$, где $A\approx42.4038$. Пример 6.4 (граф $C_{3n}(1,n)$). В этом случае имеем Пример 6.5 (граф $C_{3n}(1,2,n)$). Вследствие теоремы 6.1 получим Пример 6.6 (граф $C_{6n}(1,n,3n)$). В рассматриваемом случае справедлива формула Для подходящей целочисленной последовательности $a(n)$ имеем $\tau(n)=6n\,a(n)^2$, если $n$ четно, и $\tau(n)=18n\,a(n)^2$, если $n$ нечетно. Пример 6.7 (граф $C_{12n}(1,3n,4n)$). В этом случае 7. Циркулянтные расслоения графов7.1. Число остовных деревьев в циркулянтных расслоенияхДля произвольного циркулянтного расслоения где
$$
\begin{equation*}
G_i=C_n(s_{i,1},s_{i,2},\dots,s_{i,k_i}),\qquad i=1,2,\dots,m,
\end{equation*}
\notag
$$
рассмотрим обобщенный лапласиан базового графа $L(H,X)$. Мы определим $X$, полагая
$$
\begin{equation*}
x_{i}=2k_{i}+d_i-\sum_{j=1}^{k_i}(z^{s_{i,j}}+z^{-s_{i,j}}),
\end{equation*}
\notag
$$
где $d_i$ – степень вершины $v_i$ в $H$. По определению циркулянтного графа в случае $G_{i}\ne C_{n}(\varnothing)$ имеем $1\leqslant s_{i,1}<s_{i,2}<\cdots<s_{i,k_{i}}$. Тогда $x_{i}$ – полином Лорана со старшим членом $-z^{s_{i,k_{i}}}$. Если $G_{i}=C_{n}(\varnothing)$, то $x_{i}=d_{i}$. Положим $P(z)=\det(L(H,\,X))$. Заметим, что $P(z)$ – целочисленный полином Лорана. Для дальнейших рассуждений нам необходимо исследовать структуру старшего члена полинома $P(z)$. Этот член является произведением полиномов $x_{i}=2k_{i}+d_{i}- \displaystyle\sum_{j=1}^{k_{i}}(z^{s_{i,j}}+z^{-{s_{i,j}}})$ с $s_{i,k_{i}}>0$ и определителя матрицы, полученной из $L(H,\,X)$ удалением всех строк и столбцов, соответствующих непустым циркулянтным слоям. Для явного вычисления старшего члена $P(z)$ можно использовать следующую лемму. Лемма 7.1. Пусть $V'=(v_1,v_2,\dots,v_{m'})$ – подмножество (возможно, пустое) вершин базового графа $H$ циркулянтного расслоения $H_n(G_1,G_2,\dots,G_m)$ с пустыми циркулянтными слоями $C_{n}(\varnothing)$. Определим $H'$ как вершинно-индуцированный подграф графа $H$, образованный $V'$. Тогда старший член полинома $P(z)$ задается формулой где $\eta=\det(L(H',X'))$, $s=\displaystyle\sum_{j=1}^{m}s_{j,k_{j}}$, $X'=(d_{1},d_{2},\dots,d_{m'})$ и $d_{j}$ – степень вершины $v_j$ в графе $H$. Доказательство. По определению $P(z)=\det(L(H,X))$, где Для $j=1,2,\dots,m'$ имеем $x_{j}=d_{j}$, поскольку $k_j=1$, $s_{j,1}=0$. Если $j=m'+1,\dots,m$, то старший член полинома $x_j$ по переменной $z$ равен $-z^{s_{j,k_{j}}}$. Поскольку все остальные элементы матрицы $L(H,X)$ являются целочисленными константами, то, используя основные свойства определителей, получаем утверждение леммы. Отметим, что $L(H',X')$ – симметричная матрица со строгим диагональным преобладанием [50; лемма 5.1]. Следовательно, $\eta>0$. В случае $m'=0$ полагаем $\eta=1$. Рассмотрим еще одну спецификацию $L(H,W)$ для обобщенного лапласиана $H$ с множеством $W=(w_1,w_2,\dots,w_m)$, где $w_{i}=2k_{i}+d_i-\displaystyle\sum_{j=1}^{k_i}2\,T_{s_{i,j}}(w)$, $T_l(w)=\cos(l\arccos w)$ – полином Чебышёва первого рода. Положим $Q(w)=\det(L(H,\,W))$. Тогда $Q(w)$ – целочисленный полином степени $s=s_{1,k_1}+s_{2,k_2}+\cdots+s_{m,k_m}$. Так как $(z^n+z^{-n})/2=T_n((z+z^{-1})/2)$, имеем $P(z)=Q(w)$, где $w=(z+z^{-1})/2$. Замечание 7.1. В обозначениях леммы 7.1 старший член полинома $Q(w)$ равен $(-1)^{m-m'}2^{s}\eta\,w^{s}$. Величина $\bar{m}=m-m'$ совпадает с числом невырожденных слоев расслоения $H_n$. Основной результат текущего пункта составляет следующая теорема. Она представляет собой исправленную версию теоремы 4.2 из [51], в формулировку которой вкралась опечатка. Теорема 7.1. Число $\tau(n)$ остовных деревьев в циркулянтном расслоении $H_{n}(G_1,\dots,G_m)$ задается формулой Доказательство. Для удобства читателя приведем схему доказательства теоремы 7.1. Используя аргументы из доказательства теоремы 4.2 работы [51], имеем
$$
\begin{equation}
\tau(n)=(-1)^{(\bar{m}+s)(n-1)}n\,\eta^{n-1}\tau(H) \prod_{j=1}^{s-1}\frac{T_{n}(w_{j})-1}{w_{j}-1}\,,
\end{equation}
\tag{5}
$$
где $\bar{m}$ – число невырожденных слоев в дискретном расслоении Зейферта. Заметим, что правая часть равенства (5) положительна.
Следовательно,
$$
\begin{equation*}
\tau(n)=n\,\eta^{n-1}\tau(H)\prod_{j=1}^{s-1}|T_{n}(w_{j})-1| \Bigm/\prod_{j=1}^{s-1}|w_{j}-1|.
\end{equation*}
\notag
$$
По лемме 7.1 полином $Q(w)$ имеет старший коэффициент $a_{0}$, по модулю равный $2^{s}\eta$.
Кроме того, по лемме 4.1 из [51] имеем $Q(1)=0,\,Q'(1)=-2q\tau(H)$. Отсюда следует, что
$$
\begin{equation*}
\prod_{j=1}^{s-1}|w_{j}-1|=\frac{|Q'(1)|}{|a_{0}|}= \frac{q\,\tau(H)}{2^{s-1}\eta}\,.
\end{equation*}
\notag
$$
Используя полученные равенства, завершаем доказательство. 7.2. Арифметические свойства числа остовных деревьев в циркулянтных расслоенияхСледующий результат получен в теореме 5.1 из [51]. Теорема 7.2. Пусть $\tau(n)$ – число остовных деревьев в циркулянтном расслоении $H_n$. Обозначим через $p$ свободную от квадратов часть числа $Q(-1)$. Тогда существует целочисленная последовательность $a(n)$ такая, что (a) $\tau(n)= n\,\tau(H)\,a(n)^{2}$, если $n$ нечетно; (b) $\tau(n)=p\,n\,\tau(H)\,a(n)^{2}$, если $n$ четно. Из теоремы 7.2 вытекает следующее утверждение. Следствие 7.1. Число остовных деревьев в циркулянтном расслоении $H_n$ делится нацело на $n\,\tau(H)$, где $\tau(H)$ – число остовных деревьев в базовом графе $H$. 7.3. Асимптотика числа остовных деревьев циркулянтного расслоенияОсновным результатом данного пункта является следующая теорема, доказанная в [51] (см. [51; теорема 6.1]) в предположении, что модуль старшего коэффициента $\eta$ полинома $P(z)$ равен единице. Однако, как показано в работе [50], доказательство остается в силе и для произвольного значения $\eta$. Теорема 7.3. Асимптотическое поведение числа $\tau(n)$ остовных деревьев циркулянтного расслоения $H_n$ при условии описывается формулой где $q=\displaystyle\sum_{i=1}^{m}\,\sum_{j=1}^{k_i}s_{i,j}^2$, а $A=\exp\biggl(\displaystyle\int_{0}^{1} \log|P(e^{2 \pi \mathtt{i} t})|\,\textrm{d}t\biggr)$ – мера Малера полинома $P(z)$. 7.4. Примеры Пример 7.1 (циркулянтный граф $C_{n}(s_{1},s_{2},\dots,s_{k})$). Будем рассматривать граф $C_{n}(s_{1},s_{2},\dots,s_{k})$ как циркулянтное расслоение $H_{n}(G_{1})$ над одновершинным графом $H=\{v_{1}\}$ со слоем $G_{1}=C_{n}(s_{1},s_{2},\dots,s_{k})$. В этом случае $d_{1}=0$, $L(H,X)=(x_{1})$ и Пример 7.2 ($I$-граф $I(n,k,l)$ и обобщенный граф Петерсена $\operatorname{GP}(n,k)$). В качестве базы рассмотрим граф $H$, состоящий из двух вершин, соединенных ребром. Пусть $G_{1}=C_{n}(k)$ и $G_{2}=C_{n}(l)$. Тогда Пример 7.3 (сэндвич из $m$ циркулянтных графов). Рассмотрим путевой граф $H$ на $m$ вершинах. Назовем граф $H_{n}(G_{1},G_{2},\dots,G_{m})$ сэндвичем из циркулянтных графов $G_{1},G_{2},\dots,G_{m}$. В этом случае $d_{1}=d_{m}=1$ и $d_{i}=2$, $i=2,\dots,m-1$. Положим Пример 7.4 (обобщенный $Y$-граф). Рассмотрим обобщенный $Y$-граф В этом случае где $A_{i}(w)=2k_{i}+1-\displaystyle\sum_{j=1}^{k_{i}}2T_{s_{i,j}}(w)$. Пример 7.5 (обобщенный $H$-граф). Следуя работе [51], определим $H$-граф $H_{n}(G_{1},G_{2},G_{3},G_{4})$. Здесь каждый $G_{i}$ – это граф $C_{n}(s_{i,1},\,s_{i,2},\dots,s_{i,k_i}),\,i=1,2,3,4$. В этом случае где $A_{i}(w)$ имеют такой же вид, как и в предыдущем примере. Пример 7.6 (дискретный тор $T_{n,m}=C_n\times C_m$). Дискретный тор определим как Пример 7.7 (прямое произведение $C_n\times H$, где $H$ – регулярный граф). Пусть $H$ – связный $d$-регулярный граф. Отождествим прямое произведение $C_n\times H$ и Пусть $X=(x,\dots,x)$ ($m$ раз), тогда $L(H,X)=x I_{m}-A(H)$. Отсюда следует, что $\det(L(H,X))$ совпадает с характеристическим полиномом $\chi_{H}(x)$ графа $H$. Имеем $Q(w)=\chi_{H}(2+d-2w)$. Тогда $Q(-1)=\chi_{H}(4+d)$. 8. Общие циклические накрытия графовВ этом разделе мы используем общую конструкцию циклических накрытий графов и приводим основные результаты о подсчете остовных деревьев в таких накрытиях. Пусть $H$ – конечный связный граф с вершинами $v_1, v_2,\dots,v_r$, возможно с петлями и кратными ребрами. Матрица смежности графа $H$ имеет вид
$$
\begin{equation*}
A(H)=\begin{pmatrix} a_{1,1} & a_{1,2} & \dots & a_{1,r} \\ a_{2,1} & a_ {2,2} & \dots & a_{2,r} \\ \vdots & \vdots & \ddots & \vdots \\ a_{r, 1} & a_{r, 2} & \dots & a_{r,r} \\ \end{pmatrix},
\end{equation*}
\notag
$$
где $a_{i,j}$ – число ребер между $v_i$ и $v_j$, если $i\ne j$, и удвоенное число петель в вершине $v_i$, если $i=j$. Рассмотрим циклическое накрытие $H_n=H_{n}(\alpha)$ графа $H$, полученное при помощи задания напряжений $\alpha=\{\alpha_k(i,j),\,i, j=1,\dots,r,\,k=1,\dots,a_{i,j}\}$. Согласно общей конструкции, описанной в п. 3.5, граф $H_{n}$ имеет множество вершин $u_{i,s}$, $i=1,2,\dots,r$, $s=1,2,\dots,n$, и множество ребeр $v_{i,s}v_{j,s+\alpha_k(i,j)}$, где $i,j=1,2,\dots,r$, $k=1,2,\dots,a_{i,j}$, а вторые индексы берутся по модулю $n$. Матрица смежности $A(H_{n})$ графа $H_{n}$ представляет собой блочную матрицу
$$
\begin{equation*}
A(H_{n})=\begin{pmatrix} B_{1,1} & B_{1,2} & \dots & B_{1,r} \\ B_{2,1} & B_{2,2} & \dots & B_{2,r} \\ \vdots & \vdots & \ddots & \vdots \\ B_{r,1} & B_{r,2} & \dots & B_{r,r}\\ \end{pmatrix},
\end{equation*}
\notag
$$
где $(i,j)$-й блок $B_{i,j}=B_{i,j}(n)$, $i,j=1,2,\dots,r$, задается формулами
$$
\begin{equation}
B_{i,j}=\sum_{k=1}^{a_{i,j}}T_{n}^{\alpha_k(i,j)},\quad i\ne j, \quad\text{и}\quad B_{i,i}=\sum_{k=1}^{a_{i,i}}(T_{n}^{\alpha_k(i,i)}+ T_{n}^{-\alpha_k(i,i)}).
\end{equation}
\tag{6}
$$
Здесь $B_{i,j}$ – это $(n\times n)$-матрица, у которой $(s,s')$-й элемент равен числу ребер между вершинами $v_{i,s}$ и $v_{j,s'}$. Напомним, что лапласиан графа $H_{n}$ имеет вид где $D(H_{n})$ – диагональная матрица, составленная из степеней его вершин. Обозначим через $d(v_i)$ степень вершины $v_i$ в графе $H$ (она совпадает с числом ориентированных ребер, выходящих из вершины).Для более удобного описания блочной структуры лапласиана рассмотрим следующие вспомогательные полиномы:
$$
\begin{equation*}
p_{i,i}(z)=d(v_i)-\sum_{k=1}^{a_{i,i}}(z^{\alpha_{k}(i,i)} z^{-\alpha_{k}(i,i)})\quad\text{и}\quad p_{i,j}(z)=-\sum_{k=1}^{a_{i,j}}z^{\alpha_k(i,j)},\ \ i\ne j.
\end{equation*}
\notag
$$
Заметим, что $(i,j)$-й блок блочной матрицы $L(H_{n})=(L_{i,j})_{i,j=1,2,\dots,r}$ представим в виде $L_{i,j}=p_{i,j}(T_n)$, где $T_n=\operatorname{circ}(0,1,0,\dots,0)$ – циркулянтная $(n\times n)$-матрица. Также рассмотрим полином
$$
\begin{equation}
P(z)=\det\begin{pmatrix} p_{1,1}(z) & p_{1,2}(z) & \dots & p_{1,r}(z) \\ p_{2,1}(z) & p_{2,2}(z) & \dots & p_{2,r}(z) \\ \vdots & \vdots & \ddots & \vdots \\ p_{r,1}(z) & p_{r,2}(z) & \dots & p_{r,r}(z)\\ \end{pmatrix}.
\end{equation}
\tag{7}
$$
В дальнейшем будем называть $P(z)$ полиномом напряжений циклического накрытия $H_n$. Замечание 8.1. Для циркулянтного графа $C_n(s_1,s_2,\dots,s_k)$ полином напряжений совпадает с сопровождающим полиномом Лорана Отметим следующие важные свойства полинома напряжений $P(z)$ (см. [50; лемма 5.2]). Лемма 8.1. Имеем $P(z)=P(1/z)$, $P(1)=0$ и $P'(1)=0$, $P''(1)< 0^{}$. В частности, $P(z)$ имеет корень $z=1$ кратности $2$. Для удобства формулировки основных результатов этого раздела нам понадобится еще один вспомогательный полином. Поскольку полином напряжений удовлетворяет равенству $P(z)=P(1/z)$, его можно записать в виде
$$
\begin{equation*}
P(z)=a_0\biggl(z^s+\frac{1}{z^s}\biggr)+a_{1}\biggl(z^{s-1}+ \frac{1}{z^{s-1}}\biggr)+\cdots+a_{s-1}\biggl(z+\frac{1}{z}\biggr)+a_s.
\end{equation*}
\notag
$$
Используя соотношение $\dfrac{1}{2}\biggl(z^n+\dfrac{1}{z^n}\biggr)= T_n\biggl(\dfrac{1}{2}\biggl(z+\dfrac{1}{z}\biggr)\biggr)$, получим
$$
\begin{equation*}
P(z)=Q\biggl(\frac{1}{2}\biggl(z+\frac{1}{z}\biggr)\biggr),
\end{equation*}
\notag
$$
где
$$
\begin{equation*}
Q(w)=2a_0T_s(w)+2a_1T_{s-1}(w)+\cdots+2a_{s-1}T_{1}(w)+a_s.
\end{equation*}
\notag
$$
Мы будем называть $Q(w)$ преобразованием Чебышёва полинома $P(z)$. Заметим, что $Q(w)$ – полином степени $s$ со старшим коэффициентом $\widetilde{a}_0=2^sa_0$. Отметим также следующие полезное соотношение: 8.1. Теорема о числе остовных деревьев в циклическом накрытииНезначительная переформулировка теоремы 6.2 из работы [50] дает следующий результат. Теорема 8.1. Рассмотрим циклическое накрытие $H_n$. Пусть $P(z)$ – его полином напряжений, а $Q(w)$ – преобразование Чебышёва полинома $P(z)$. Тогда число $\tau(n)$ остовных деревьев в $H_{n}$ может быть вычислено по формуле где произведение берется по всем отличным от единицы корням полинома $Q(w)$, а $\eta$ – модуль старшего коэффициента полинома $P(z)$. Замечание 8.2. Сравнивая этот результат с теоремой 7.1, отметим, что в случае циркулянтных расслоений 8.2. Асимптотика числа остовных деревьев в циклическом накрытииВ данном пункте приводится формула, описывающая асимптотику числа $\tau(H_n)$ при $n\to\infty$. Основной результат составляет следующая теорема, доказанная в [50] (см. [50; теорема 8.1]). Теорема 8.2. Асимптотическое поведение числа остовных деревьев в циклическом накрытии $H_n$ описывается формулой где $A=\exp\biggl(\displaystyle\int_{0}^{1}\log |P(e^{2 \pi \mathtt{i} t})|\,dt\biggr)$ – мера Малера полинома напряжений $P(z)$. 9. Отмеченные остовные леса в циркулянтных графах9.1. Перечисление отмеченных остовных лесов в циркулянтных графахПрежде всего рассмотрим случай циркулянтных графов с четной степенью вершин. В этом случае справедливы следующие две теоремы, доказанные в работе [33]. В формулировках этих теорем граф не предполагается связным. Теорема 9.1. Число $f_{G}(n)$ отмеченных остовных лесов в циркулянтном графе $G=C_{n}(s_1,s_2,\dots,s_k)$, $1\leqslant s_1< s_2<\cdots< s_k< n/2$, задается формулой где $w_{p},\,p=1,2,\dots,s_{k}$, – все корни алгебраического уравнения а $T_{s}(w)$ – полином Чебышёва первого рода степени $s$. Приведем принципиальную схему доказательства. Множество собственных значений матрицы $I_n+L(G)$ имеет вид
$$
\begin{equation*}
\mu_{j}=P(\varepsilon_{n}^{j})=2k+1- \sum_{i=1}^k(\varepsilon_{n}^{j s_i}+\varepsilon_{n}^{-j s_{i}}),\qquad j=0,\dots,n-1.
\end{equation*}
\notag
$$
Число отмеченных остовных лесов может быть представлено формулой
$$
\begin{equation*}
f_{G}(n)=\det(I_n+L(G))=\prod_{j=0}^{n-1}P(\varepsilon_{n}^{j}).
\end{equation*}
\notag
$$
Поскольку $P(z)=P(1/z)$, все корни $P(z)$ распадаются на пары
$$
\begin{equation*}
z_{1},\frac{1}{z_{1}}\,,\quad z_{2},\frac{1}{z_{2}}\,,\quad \dots,\quad z_{s_{k}},\frac{1}{z_{s_{k}}}\,.
\end{equation*}
\notag
$$
Далее, используя положительность числа $f_{G}(n)$ и основные свойства результантов [75; гл. 3], имеем
$$
\begin{equation*}
\begin{aligned} \, \prod_{j=0}^{n-1}P(\varepsilon_{n}^{j})&= \operatorname{Res}(P(z),z^n-1)=|\operatorname{Res}(z^n-1,P(z))| \\ &=\biggl|\,\prod_{p=1}^{s_{k}}(z_{p}^{n}-1)(z_{p}^{-n}-1)\biggr|= \biggl|\,\prod_{p=1}^{s_{k}}(2T_{n}(w_{p})-2)\biggr|. \end{aligned}
\end{equation*}
\notag
$$
Последнее равенство вытекает из следующего свойства полиномов Чебышёва:
$$
\begin{equation*}
T_{n}\biggl(\frac{1}{2}(z+z^{-1})\biggr)=\frac{1}{2}(z^{n}+z^{-n}).
\end{equation*}
\notag
$$
Кроме того, полагаем $w_{p}=(z_{p}+1/z_{p})/2$, $p=1,\dots,s_{k}$. Эти числа являются корнями уравнения $\displaystyle\sum_{j=1}^{k}(2T_{j}(w)-2)=1$. Следующая теорема позволяет перечислить остовные леса в циркулянтном графе с нечетной степенью вершин. Ее доказательство основано на тех же соображениях, что и доказательство теоремы 9.1. Мы по-прежнему не требуем связности графа. Теорема 9.2. Пусть $C_{2n}(s_{1},s_{2},\dots,s_{k},n)$, $1\leqslant s_{1}<s_{2}<\cdots<s_{k}<n$, – циркулянтный граф с нечетной степенью вершин. Тогда число $f_{G}(n)$ отмеченных остовных лесов в графе $G=C_{2n}(s_1,s_2,\dots,s_k,n)$ задается формулой где величины $u_p$ и $v_p$, $p=1,2,\dots,s_k$, – корни алгебраических уравнений соответственно. При этом и $T_s(w)$ – полином Чебышёва первого рода. 9.2. Арифметические свойства числа отмеченных остовных лесовВ случае циркулянтных графов с четной степенью вершин имеет место следующий результат [33; теорема 7.1]. Теорема 9.3. Обозначим через $f_{G}(n)$ число отмеченных остовных лесов в циркулянтном графе Пусть $p$ – число нечетных элементов в последовательности $s_1,s_2,\dots,s_k$, а $q$ – свободная от квадратов часть числа $p$. Тогда существует целочисленная последовательность $a(n)$ такая, что (a) $f_{G}(n)=a(n)^2$, если $n$ нечетно; (b) $f_{G}(n)=q\,a(n)^2$, если $n$ четно. Доказательство основано на следующих соображениях. Поскольку то все собственные значения матрицы $I_n+L(G)$ повторяются дважды (возможно, за исключением среднего члена последовательности $\mu_{j}$). Следовательно, $f_{G}(n)=\displaystyle\prod_{j=0}^{n-1}\mu_j$ равно $\biggl(\,\displaystyle\prod_{j=0}^{(n-1)/2}\mu_j\biggr)^2$, если $n$ нечетно, и $\mu_{n/2}\biggl(\,\displaystyle\prod_{j=0}^{n/2-1}\mu_j\biggr)^2$, если $n$ четно. Заметим, что все числа $\mu_{j}$ – алгебраические, так как являются корнями полинома с целыми коэффициентами. Произведение алгебраического числа со всеми его сопряженными по Галуа называется нормой и всегда является целым числом. Каждое число $\mu_{j}$ входит в произведения $\displaystyle\prod_{j=0}^{(n-1)/2}\mu_j$ и $\displaystyle\prod_{j=0}^{n/2-1}\mu_j$ вместе с его сопряженными по Галуа. Отсюда следует, что указанные произведения – целые числа. Для завершения доказательства заметим, что среднее собственное число $\mu_{n/2}$ (если оно есть) равно
$$
\begin{equation*}
P(-1)=2k+1-\sum_{p=1}^{k}((-1)^{s_p}+(-1)^{-s_p})=4p+1,
\end{equation*}
\notag
$$
где $p$ – число нечетных элементов последовательности $s_1,s_2,\dots,s_k$. Следующая теорема описывает арифметические свойства числа отмеченных остовных лесов в циркулянтных графах с нечетной степенью вершин [33; теорема 5.2]. Теорема 9.4. Пусть $f_{G}(n)$ – число отмеченных остовных лесов в циркулянтном графе и $p$ – количество нечетных элементов последовательности $s_1,s_2,\dots,s_k$. Положим $q$ и $r$ равными свободным от квадратов частям чисел $4p+1$ и $4p+3$ соответственно. Тогда существует целочисленная последовательность $a(n)$ такая, что (a) $f_{G}(n)=q\,a(n)^2$, если $n$ четно; (b) $f_{G}(n)=r\,a(n)^2$, если $n$ нечетно. 9.3. Асимптотика числа отмеченных остовных лесовВ циркулянтном графе с четной степенью вершин имеем следующие результаты, полученные в работе [33]. Теорема 9.5. Асимптотическое поведение числа отмеченных остовных лесов в циркулянтном графе определяется формулой где $A=\exp\biggl(\displaystyle\int_0^1 \log(P(e^{2\pi\mathtt{i}t}))\,dt\biggr)$ – мера Малера сопровождающего полинома Лорана $P(z)=2k+1-\displaystyle\sum_{i=1}^k(z^{s_i}+z^{-{s_i}})$. Доказательство проводится по следующей схеме. По теореме 9.1 число $f_{G}(n)$ остовных лесов определяется формулой $f_{G}(n)=\displaystyle\prod_{s=1}^{s_k}|2\,T_n(w_s)-2|$, где $w_{s}=(z_{s}+z_{s}^{-1})/2$. Имеем $T_{n}(w_s)=(z_{s}^{n}+z_{s}^{-n})/2$, где $z_{s}$ и $1/z_{s}$, $s=1,\dots,s_{k}$, – все корни полинома $P(z)$. Если $\varphi\in\mathbb{R}$, то
$$
\begin{equation*}
P(e^{\mathtt{i}\varphi})=2k+1-\sum_{j=1}^{k} (e^{s_{j} \mathtt{i}\varphi}+e^{-s_{j}\mathtt{i}\varphi})= 2k+1-2\sum_{j=1}^{k}\cos(s_{j}\varphi)\geqslant1.
\end{equation*}
\notag
$$
Следовательно, полином $P(z)$ не имеет корней, по модулю равных единице, и $|z_{s}|\ne1$ для всех $s$. Заменяя при необходимости $z_s$ на $1/z_s$, всегда можем считать, что $|z_s|>1$ для всех $s$. Тогда $T_n(w_s)\sim z_s^n/2$, $n\to \infty$. Поэтому $|2T_n(w_s)-2|\sim|z_s|^n$, $n\to\infty$. Отсюда следует, что
$$
\begin{equation*}
\prod_{s=1}^{s_k}|2\,T_n(w_s)-2|\sim \prod_{s=1}^{s_k}|z_s|^n= \prod_{P(z)=0,\,|z|>1}|z|^n=A^n,
\end{equation*}
\notag
$$
где $A=\displaystyle\prod_{P(z)=0,\,|z|>1}|z|$ – мера Малера полинома $P(z)$. B силу результатов, приведенных в п. 2.6, ее можно найти по формуле $A=\exp\biggl(\displaystyle\int_0^1\log(P(e^{2\pi\mathtt{i}t}))\,dt\biggr)$.
Окончательно, Асимптотика числа отмеченных остовных лесов в циркулянтном графе с нечетной степенью вершин определяется следующей теоремой. Теорема 9.6. Число $f_{G}(n)$ отмеченных остовных лесов в циркулянтном графе имеет следующую асимптотику: где $K=\exp\biggl(\displaystyle\int_0^1\log |P(e^{2\pi\mathtt{i}t})^{2}-1|\,dt\biggr)$ – мера Малера полинома Лорана $P(z)^2-1$, а $P(z)=2k+2-\displaystyle\sum_{i=1}^k(z^{s_i}+z^{-s_i})$. 9.4. ПримерыПриведем серию примеров, иллюстрирующих результаты текущего раздела. Пример 9.1 (циклический граф $C_n=C_n(1)$). По теореме 9.1 для нахождения числа отмеченных остовных лесов в данном случае надо найти все корни уравнения $1+2-2T_{1}(w)=0$. Это число $w$ равно $3/2$. Поэтому $f_{G}(n)=2T_{n}(3/2)-2$. Далее, по теореме 9.5 заключаем, что Пример 9.2 (циркулянтный граф $C_{n}(1,2)$). Следуя теореме 9.1 для циркулянтного графа с двумя скачками $1$ и $2$, приходим к необходимости решить уравнение $1+4-2T_{1}(w)-2T_{2}(w)=0$. Его корнями являются величины Отсюда заключаем, что где $A=(7+\sqrt{5}+\sqrt{38+14\sqrt{5}}\,)/4\simeq 4.3902568\dots$ . По теореме 9.3 найдется последовательность целых чисел $a(n)$ такая, что $f_{G}(n)=5a(n)^2$, если $n$ четно, и $f_{G}(n)=a(n)^2$, если $n$ нечетно. Пример 9.3 (циркулянтный граф $C_{n}(1,3)$). Пусть $w_{1}$, $w_{2}$ и $w_{3}$ – корни кубического уравнения $1+4-2T_{1}(w)-2T_{3}(w)=0$. Тогда Пример 9.4 (лестница Мёбиуса $C_{2n}(1,n)$). По теореме 9.2 надо решить два алгебраических уравнения: $3-2T_{1}(w)=0$ и $5-2T_{1}(w)=0$. Соответствующие корни: $u_{1}=3/2$ и $v_{1}=5/2$. Отсюда следует, что 10. Циркулянтные расслоения графовПусть $H_n=H(G_{1},\,G_{1},\dots,\,G_{m})$ – циркулянтное расслоение, рассмотренное в разделе 7. Для изложения результатов данного раздела введем следующие вспомогательные полиномы. Положим
$$
\begin{equation*}
P_{f}(z)=\det(I+L(H,X)),\qquad Q_{f}(w)=\det(I+L(H,W)),
\end{equation*}
\notag
$$
где обобщенные лапласианы $L(H,X)$ и $L(H,W)$ те же, что и в разделе 7. Как и раньше, полиномы связаны соотношением $P_{f}(z)=Q_{f}((z+1/z)/2)$. Обозначим через $\zeta$ модуль старшего коэффициента полинома $P_{f}(z)$. 10.1. Число отмеченных остовных лесов в циркулянтном расслоенииСледующий результат установлен в [31; теорема 3.3]. Теорема 10.1. Число $f(n)$ отмеченных остовных лесов в циркулянтном расслоении $H_{n}(G_1,G_2,\dots,G_m)$ вычисляется по формуле где $s=s_{1,k_1}+s_{2,k_2}+\cdots+s_{m,k_m}$ и $w_p$, $p=1,2,\dots,s$, – все корни уравнения $Q_{f}(w)=0$, а $\zeta$ – модуль старшего коэффициента полинома $P_{f}(z)$. 10.2. Арифметические свойства числа отмеченных остовных лесов в циркулянтном расслоенииСледующий результат получен в [31; теорема 4.1]. Теорема 10.2. Пусть $f(n)$ – число отмеченных остовных лесов в циркулянтном расслоении $H_n$, а $f(H)$ – число отмеченных остовных лесов в базовом графе $H$. Обозначим через $p$ свободную от квадратов часть числа $Q_{f}(-1)$. Тогда существует целочисленная последовательность $a(n)$ такая, что (a) $f(n)=f(H)\,a(n)^{2}$, если $n$ нечетно; (b) $f(n)=p\,f(H)\,a(n)^{2}$, если $n$ четно. 10.3. Асимптотика числа отмеченных остовных лесов в циркулянтном расслоенииПриведенный ниже результат доказан в [31; теорема 5.1]. Теорема 10.3. Число $f(n)$ отмеченных остовных лесов в циркулянтном расслоении $H_n$ имеет следующую асимптотику: где $A=\exp\biggl(\displaystyle\int_{0}^{1}\log |P_{f}(e^{2\pi\mathtt{i}t})|\,dt\biggr)$ – мера Малера полинома $P_{f}(z)$. 10.4. Примеры Пример 10.1 ($I$-граф $I(n,k,l)$ и обобщенный граф Петерсена $\operatorname{GP}(n,k)$). Рассмотрим граф $H$ с двумя вершинами и соединяющим их ребром. Положим $G_{1}=C_{n}(k)$ и $G_{2}=C_{n}(l)$. Рассмотрим графы Пример 10.2 (обобщенный $Y$-граф). Рассмотрим обобщенный $Y$-граф Тогда где $A_{i}(w)=2k_{i}+2-\displaystyle\sum_{j=1}^{k_{i}}2T_{s_{i,j}}(w)$. В частном случае $G_{1}=G_{2}=G_{3}=C_{n}(1)$ имеем и $\zeta=4$. При этом
$$
\begin{equation*}
f(n)=4^n\biggl(2T_{n}\biggl(\frac{13}{8}\biggr)-2\biggr)(2T_{n}(2)-2)^2.
\end{equation*}
\notag
$$
По теореме 10.2 существует целочисленная последовательность $a(n)$ такая, что $f(n)=f(1)a(n)^2$, если $n$ нечетно, и $f(n)=21f(1)a(n)^2$, если $n$ – четно, при этом $f(1)=20$. Теорема 10.3 дает следующую асимптотику: Пример 10.3 (обобщенный $H$-граф). Рассмотрим обобщенный $H$-граф вида $H_{n}(G_{1},G_{2},G_{3},G_{4})$, где $G_{i}$, $i=1,2,3,4$, – заданные циркулянтные графы $C_{n}(s_{ i,1},\,s_{i,2},\dots,s_{i,k_i})$. Для данного графа имеем 11. Группы якобиана циркулянтных графовПонятие группы якобиана графа, которую также называют группой Пикара, критической группой, долларовой или песочной группой, было независимо введено многими авторами [22], [6], [9], [4]. Это понятие возникает как дискретная версия якобиана в классической теории римановых поверхностей. Также оно допускает естественную интерпретацию в различных разделах физики, теории кодирования и финансовой математике. Группа якобиана является важным алгебраическим инвариантом конечного графа. В частности, ее порядок совпадает с числом остовных деревьев графа. Цель данного раздела – определить структуру якобиана для циркулянтных графов. Для простейших циркулянтных графов группа якобиана будет найдена в явном виде, в то время как в общем случае будет предложен удобный метод для ее вычисления. 11.1. Графы с четной степенью вершинВведем следующее определение. Пусть $P(z)$ – полином Лорана вида где $a_1,a_2,\dots,a_{s-1}$, $p$, $s$ – целые числа и $s$ положительно. Сопровождающую матрицу $\mathcal{A}$ полинома $P(z)$ определим следующим равенством:
$$
\begin{equation*}
\mathcal{A}=\biggl(\begin{array}{c}\begin{array}{c|c} {0} & I_{s-1}\end{array}\\\hline -1,-a_1,\dots,-a_{s-1}\\ \end{array}\biggr),
\end{equation*}
\notag
$$
где $I_{s-1}$ – единичная $(s-1)\times(s-1)$-матрица. Так как $\det(\mathcal{A})=(-1)^{s}$, то матрица $\mathcal{A}$ обратима и обратная к ней матрица $\mathcal{A}^{-1}$ также целочисленна. Сопровождающую матрицу полинома $-P(z)$ также будем считать равной $\mathcal{A}$. Строение якобиана циркулянтного графа с четной степенью описывается следующим утверждением [60; теорема 2.1]. Теорема 11.1. Пусть $G=C_{n}(s_{1},s_{2},\dots,s_{k})$ – циркулянтный граф со скачками $1\leqslant s_{1}<s_{2}<\cdots<s_{k}< n/2$. Тогда группа якобиана $\operatorname{Jac}(G)$ изоморфна группе кручения коядра оператора $\mathcal{A}^n-I$, где $\mathcal{A}$ – сопровождающая матрица полинома $2k-\displaystyle\sum_{l=1}^{k}(z^{s_{l}}+z^{-s_{l}})$. В качестве применения теоремы 11.1 рассмотрим следующий результат, независимо полученный в работах [38] и [60]. Пример 11.1 (граф $C_n(1,2)$). Якобиан $\operatorname{Jac}(C_n(1,2))$ изоморфен $\mathbb{Z}_{(n,F_n)}\oplus\mathbb{Z}_{F_n}\oplus\mathbb{Z}_{\{n,F_n\}}$, где $(a,b)=\operatorname{gcd}(a,b)$ и $\{a,b\}=\operatorname{lcm}(a,b)$ – наибольший общий делитель и наименьшее общее кратное чисел $a$ и $b$, а $F_n$ – числа Фибоначчи. В качестве следующего примера выступает теорема 2.2 из работы [60]. Пример 11.2 (граф $C_n(1,3)$). Рассмотрим две периодические последовательности $\mu(n)$ и $\eta(n)$, определенные по формулам Положим
$$
\begin{equation*}
\begin{gathered} \, \Delta_1=\operatorname{gcd}(n,s,t,u,v),\quad \Delta_2=\operatorname{gcd}(s,t,nu,nv), \\ \Delta_3=\operatorname{gcd}(ns,nt,su+tv,sv-tu),\quad \Delta_4=\operatorname{gcd}(s^2+t^2,n(su+tv),n(sv-tu)), \\ \Delta_5=\frac{n}{10}(s^2+t^2). \end{gathered}
\end{equation*}
\notag
$$
Тогда якобиан $\operatorname{Jac}(C_n(1,3))$ изоморфен группе $\mathbb{Z}_{d_1}\oplus\mathbb{Z}_{d_2}\oplus\mathbb{Z}_{d_3}\oplus \mathbb{Z}_{d_4}\oplus\mathbb{Z}_{d_5}$, где Кроме того, число остовных деревьев в графе $C_n(1,3)$ задается формулой11.2. Графы с нечетной степенью вершинСледующая теорема (в эквивалентной форме) приведена в работе [60]. Техника ее доказательства изложена в последующей работе [32]. Теорема 11.2. Пусть – циркулянтный граф с нечетной степенью вершин. Тогда его якобиан $\operatorname{Jac}(G)$ изоморфен группе кручения коядра оператора $\mathcal{A}^n-(2k+1)I+\displaystyle\sum_{j=1}^{k}(\mathcal{A}^{s_{j}}+ \mathcal{A}^{-s_{j}})$, где $\mathcal{A}$ – сопровождающая матрица полинома $\biggl(2k+1-\displaystyle\sum_{j=1}^{k}(z^{s_{j}}+z^{-s_{j}})\biggr)^2-1$. В качестве примера приведем следующий результат, полученный различными методами в работах [17], [69] и [60]. Пример 11.3 (лестница Мёбиуса $M(n)=C_{2n}(1,n)$). Положим и где $T_m=T_m(2)$ и $U_{m-1}=U_{m-1}(2) $ – полиномы Чебышёва первого и второго рода соответственно. Тогда якобиан $\operatorname{Jac}(M(n))$ лестницы Мёбиуса $M(n)$ изоморфен группе $\mathbb{Z}_{(n,H_m)}\oplus\mathbb{Z}_{H_m}\oplus\mathbb{Z}_{3\{n,H_m\}}$, если $n=2m+1$ нечетно, группе $\mathbb{Z}_{(n,T_m)}\oplus\mathbb{Z}_{T_m}\oplus\mathbb{Z}_{2\{n,T_m\}}$, если $n=2m$ и $m$ четно, и группе $\mathbb{Z}_{(n,T_m)/2}\oplus \mathbb{Z}_{2T_m}\oplus\mathbb{Z}_{2\{n,T_m\}}$, если $n=2m$ и $m$ нечетно. 11.3. Графы с неограниченными скачкамиЦель данного пункта – описать критическую группу циркулянтного графа вида $G=C_{\beta n}(s_1,s_2,\dots,s_k,\alpha_1n,\alpha_2n,\dots,\alpha_\ell n)$, имеющего $\beta n$ вершин и $k+\ell$ скачков, первые $k$ из которых постоянны, а остальные $\ell$ линейным образом зависят от величины $n$. Частный случай $\beta=1$ и $\ell=0$ (циркулянтный граф с постоянными скачками) рассмотрен в предыдущих пунктах. Рассмотрим целочисленную $(m\times n)$-матрицу $M$ как линейное отображение из $\mathbb{Z}^{m}$ в $\mathbb{Z}^{n}$. Тогда $M$ имеет образ $\operatorname{im}M=M^{t}\mathbb{Z}^{m}$ и коядро $\operatorname{coker}M=\mathbb{Z}^{n}/\operatorname{im}M$. Напомним, что якобиан $\operatorname{Jac}(G)$ графа $G$ изоморфен группе кручения коядра его матрицы Лапласа $L(G)$. Основной результат текущего пункта составляет следующая теорема, доказанная в [63]. Теорема 11.3. Пусть $G=C_{\beta n}(s_1,s_2,\dots,s_k,\alpha_1n, \alpha_2n,\dots,\alpha_\ell n)$ – связный циркулянтный граф, где $1\leqslant s_1<s_2<\cdots<s_k<[\beta n/2]$, $1\leqslant \alpha_1<\alpha_2<\cdots<\alpha_\ell\leqslant [\beta/2]$ – целые числа. Пусть Обозначим через $\mathcal{A}$ сопровождающую матрицу полинома Лорана Тогда группа якобиана $\operatorname{Jac}(G)$ изоморфна группе кручения коядра целочисленной $(2\beta s_k\times 4\beta s_k)$-матрицы $(P(\mathcal{A})+l(\mathcal{A}^n),\mathcal{A}^{\beta\,n}-I_{2\beta s_k})$. Более того, ранг абелевой группы $\operatorname{Jac}(G)$ всегда не менее $2$ и не более $2\beta s_k-1$. Обе оценки являются точными. Набросок доказательства. Прежде всего заметим, что $R_\beta(z)$ является результантом лорановских полиномов $P(z)+l(x)$ и $x^\beta-1$ по переменной $x$. Отсюда следует, что $R_\beta(z)$ – полином с целыми коэффициентами и старшим коэффициентом, равным единице. Повторяя доказательство теоремы Безу для результантов [75; теорема 3.2], найдем полиномы Лорана $p(x,z)$ и $q(x,z)$ от $x$ и $z$ с целыми коэффициентами такие, что Заметим, что лапласиан $L(G)$ графа $G$ задается матрицей $-P(T_{\beta n})-l(T_{\beta n}^n)$, где $T_{\beta n}=\operatorname{circ}(0,1,0,\dots,0)$ – циркулянтная $(\beta\, n \times \beta\, n)$-матрица сдвига. Пусть $\mathbb{A}$ – бесконечно порожденная абелева группа, свободно порожденная элементами $x_i$, $i\in\mathbb{Z}$. Рассмотрим эндоморфизм $T$, действующий на группе $\mathbb{A}$ по правилу $T\colon x_i\to x_{i+1}$. Пользуясь техникой обозначений из работы [49], представим коядро $L(G)$ как абелеву группу, имеющую следующее копредставление:
$$
\begin{equation*}
\begin{aligned} \, \operatorname{coker}(L(G))&=\langle x_i,\,i\in\mathbb{Z}\colon (P(T)+l(T^n))x_j=0,(T^{\beta\,n}-1)x_j=0,\,j\in\mathbb{Z}\rangle \\ &=\langle x_i,\,i\in\mathbb{Z}\colon (P(T)+l(T^n))x_j=0,(T^{\beta\,n}-1)x_j=0, \\ &\qquad p(T^n,T)(P(T)+l(T^n))x_j+q(T^n,T)(T^{\beta\,n}-1)x_j=0,\, j\in\mathbb{Z}\rangle \\ &=\langle x_i,\,i\in\mathbb{Z}\colon (P(T)+l(T^n))x_j=0,(T^{\beta\,n}-1)x_j=0,R_{\beta}(T)x_j=0\rangle. \end{aligned}
\end{equation*}
\notag
$$
Положим $A=P(T)+l(T^n)$, $B=T^{\beta\,n}-1$ и $C=R_{\beta}(T)$. Старший коэффициент полинома $R_{\beta}(z)$ равен единице, поэтому $\mathbb{Z}$-модуль $\operatorname{coker} C=\mathbb{A}/\operatorname{im}C$ свободно порожден элементами $u_1,u_2,\dots,u_s$, где $s=2\beta s_k$ – степень $R_{\beta}(z)$, а $u_i=[x_i]$ – образ $x_i$ при каноническом отображении $\mathbb{A}\to\mathbb{A}/\operatorname{im}C$. Действие оператора $T\big|_{\operatorname{coker}C}$ в базисе $u_1,u_2,\dots,u_s$ задается сопровождающей матрицей $\mathcal{A}$ полинома $R_\beta(z)$. Отсюда следует, что действия эндоморфизмов $A\big|_{\operatorname{coker}C}$ и $B\big|_{\operatorname{coker}C}$ на $\operatorname{coker}C$ представляются $(s\times s)$-матрицами $P(\mathcal{A})+l(\mathcal{A}^n)$ и $\mathcal{A}^{\beta\,n}-I_{2\beta s_k}$ соответственно. Применение леммы 1 из [49] завершает доказательство теоремы. Простейшим циркулянтным графом с непостоянными скачками является лестница Мёбиуса с двойными ступенями $C''_{2n}(1,n)$. Проиллюстрируем предыдущую теорему следующим примером. Пример 11.4 (граф $C''_{2n}(1,n)$ – лестница Мёбиуса с двойными ступенями). Группа якобиана лестницы Мёбиуса с двойными ступенями изоморфна $\mathbb{Z}_{(n,a(n))}\oplus\mathbb{Z}_{a(n)}\oplus \mathbb{Z}_{4\{n,a(n)\}/(2,n)}$, где $(l,m)=\operatorname{gcd}(l,m)$, $\{l,m\}=\operatorname{lcm}(l,m)$, а $a(n)$ – последовательность $A079496$ в онлайн-энциклопедии целочисленных последовательностей (OEIS). При этом $a(n)=T_m(3)$, если $n=2m$, и $a(n)=2U_{m-1}(3)+T_m(3)$, если $n=2m+1$, где $T_m(x)$ и $U_{m-1}(x) $ – полиномы Чебышёва первого и второго рода соответственно. 11.4. Якобианы конусов над графамиСоединением двух графов $G$ и $H$ называется граф $G*H$, полученный из дизъюнктного объединения графов $G$ и $H$ добавлением ребер, соединяющих каждую вершину $G$ с каждой вершиной $H$. Если $H=K_{1}$ – граф, состоящий из одной вершины, то соединение $\widehat{G}=G*K_{1}$ называется конусом над графом $G$. Приведем следующий любопытный результат из теории графов, в разное время полученный разными авторами (см., например, работу [15] и цитируемую там литературу). Теорема 11.4. Число остовных деревьев в конусе $\widehat{G}$ над графом $G$ равно числу отмеченных остовных лесов в графе $G$. Отметим, что существует естественное взаимно однозначное соответствие между множеством остовных деревьев в конусе $\widehat{G}$ и множеством отмеченных остовных лесов в графе $G$. Действительно, рассмотрим $\widehat{G}$ как соединение графа $G$ с одновершинным графом $\{v_0\}$. Тогда каждое остовное дерево $t$ в конусе $\widehat{G}$ содержит вершину $v_0$. Пусть $v_0v_j$, $j=1,2,\dots,k$, – все ребра графа $t$, инцидентные вершине $v_0$. При этом $f=t\cap G$ – остовной лес в графе $G$, состоящий из $k$ деревьев $t_1,t_2,\dots,t_k$, где $v_j$ – вершина дерева $t_j$. Таким образом, пары $(t_j,v_j)$, $j=1,2,\dots,k$, образуют отмеченный остовной лес в графе $G$. Обратно, если $(t_j,v_j)$, $j=1,2,\dots,k$, – отмеченный остовной лес в графе $G$, то граф $t$, полученный объединением вершины $v_0$, ребер $v_0v_j$ и деревьев $t_j$, $j=1,2,\dots,k$, является остовным деревом в конусе $\widehat{G}$. Следующая теорема была независимо доказана в работах разных авторов (см., например, [28; замечание 3] и [32; теорема 2]). Теорема 11.5. Рассмотрим граф $G$ на $n$ вершинах. Тогда группа якобиана конуса над графом $G$ изоморфна группе кручения коядра линейного оператора $I_n+L(G)$, где $L(G)$ – матрица Лапласа графа $G$, а $I_n$ – единичная матрица порядка $n$. Заметим, что $\operatorname{coker}(I_{n}+L(G))$ является конечной абелевой группой порядка $\det(I_{n}+L(G))$. Согласно формуле (1) это число совпадает с количеством отмеченных остовных лесов в графе $G$. Следуя работе [32], будем называть $\operatorname{coker}(I_{n}+L(G))$ лесной группой (forest group) графа $G$ и обозначать ее через $F(G)$. Тогда утверждение теоремы 11.5 может быть сформулировано следующим образом: Группа якобиана $\operatorname{Jac}(\widehat{G})$ конуса $\widehat{G}$ над графом $G$ изоморфна лесной группе $F(G)$. 11.5. Лесная группа циркулянтного графаДля циркулянтного графа с четной степенью вершин справедлива следующая теорема [32; теорема 3]. Теорема 11.6. Рассмотрим конус $\widehat{G}$ над циркулянтным графом Тогда группа якобиана $\operatorname{Jac}({\widehat{G}})$ изоморфна группе $\operatorname{coker}(\mathcal{A}^n-I)$, где $\mathcal{A}$ – сопровождающая матрица полинома Лорана $2k+1-\displaystyle\sum_{l=1}^{k}(z^{s_{l}}+z^{-s_{l}})$. Рассмотрим $(2k+1)$-валентный циркулянтный граф
$$
\begin{equation*}
G=C_{2n}(s_{1},s_{2},\dots,s_{k},n),\qquad 1\leqslant s_{1}<s_{2}<\cdots<s_{k}<n.
\end{equation*}
\notag
$$
В этом случае верна следующая теорема, установленная в [32; теорема 4]. Теорема 11.7. Пусть $\widehat{G}$ – конус над циркулянтным графом $G$. Тогда группа $\operatorname{Jac}({\widehat{G}})$ изоморфна $\operatorname{coker}\biggl(\mathcal{A}^n-(2k+2)I+\displaystyle\sum_{j=1}^{k} (\mathcal{A}^{s_{j}}+\mathcal{A}^{-s_{j}})\biggr)$, где $\mathcal{A}$ – сопровождающая матрица полинома Лорана $\biggl(2k+2-\displaystyle\sum_{j=1}^{k}(z^{s_{j}}+z^{-s_{j}})\biggr)^2-1$. Для иллюстрации приведенной теоремы рассмотрим следующий пример. Пример 11.5 (лесная группа лестницы Мёбиуса). Пусть $\widehat{G}$ – конус над лестницей Мёбиуса $G=C_{2n}(1,n)$. Предположим, что $n=2m+1$ – нечетное число. Определим полином Чебышёва четвертого рода как 12. Теорема Планса и периодичность приведенных якобиановТеорема Планса [74] утверждает, что первая группа гомологий $n$-листного циклического накрытия трехмерной сферы, разветвленного над заданным узлом, является прямой суммой двух экземпляров абелевой группы, если $n$ нечетно. Этот же результат верен для гомологий четнолистных накрытий, профакторизованных по приведенной группе гомологий двулистного накрытия. (Современное доказательство теоремы имеется в работах [29] и [84].) Цель данного раздела – установить аналогичные результаты для якобиaнов (критических групп) циркулянтных графов. Будет установлено также, что якобианы циркулянтных графов на $n$ вершинах, приведенные по заданной конечной абелевой группе, являются периодическими функциями от $n$. В работе [66] отмечена параллель между результатами, описывающими гомологии разветвленных циклических накрытий над узлами, и теорией циклических накрытий над графами. Приведем следующий глоссарий, позволяющий устанавливать соответствие между объектами из теории узлов и их аналогами в теории графов: – узел $K$ в сфере $\mathbb{S}^3$ соответствует вершине $v$ конуса $\widehat{G}=\{v\}\star G$; – полином Александера узла $K$ соответствует ассоциированному полиному Лорана графа $G$; – дополнение узла $\mathbb{S}^3\setminus K$ соответствует графу $G$; – циклическое накрытие над $\mathbb{S}^3\setminus K$ соответствует циклическому накрытию над графом $G$; – циклическое накрытие $M_n$ сферы $\mathbb{S}^3$, разветвленное над $K$, соответствует циклическому накрытию $\widehat{G}_n$ конуса $\widehat{G}=\{v\}\star G$, разветвленному над $v$; – группа гомологий $H_1(M_n,\mathbb{Z})$ соответствует якобиану $\operatorname{Jac}(\widehat{G}_n)$. 12.1. Теорема Планса для циркулянтных графовНаиболее просто теорема Планса для графов формулируется в случае, когда $G$ – граф с одной вершиной и $k$ петлями [66]. В этом случае $G_n$ – циркулянтный граф вида $C_{n}(s_{1},s_{2},\dots,s_{k})$, а $\widehat{G}_n$ – конус над ним. Теорема 12.1. Пусть $G_n=C_{n}(s_{1},s_{2},\dots,s_{k})$ – циркулянтный граф на $n$ вершинах, а $\widehat{G}_n$ – конус над ним. Тогда для любого нечетного $n$ группа $\operatorname{Jac}(\widehat{G}_n)$ является прямой суммой двух экземпляров конечной абелевой группы. Если $n$ четно, то группа $\operatorname{Jac}(\widehat{G}_2)$ естественным образом вкладывается в группу $\operatorname{Jac}(\widehat{G}_n)$, а факторгруппа $\operatorname{Jac}(\widehat{G}_n)/\operatorname{Jac}(\widehat{G}_2)$ представляется в виде прямой суммы двух экземпляров конечной абелевой группы. Набросок доказательства. Предположим вначале, что $n=2m+1$ – нечетное число. Согласно теореме 11.6 группа якобиана $\operatorname{Jac}({\widehat{G}})$ изоморфна группе $\operatorname{coker}(\mathcal{A}^n-I)$, где $\mathcal{A}$ – сопровождающая матрица полинома Лорана $2k+1-\displaystyle\sum_{l=1}^{k}(z^{s_{l}}+z^{-s_{l}})$. Воспользуемся элементарным тождеством Лемма 12.1. Существует целочисленная унимодулярная матрица $U$ такая, что произведение $U(\mathcal{A}+\mathcal{A}^{-1})U^{-1}$ – блочная матрица вида $\begin{pmatrix} G & 0 \\ 0 & J\,G\,J\end{pmatrix}$, где $G$ – некоторая целочисленная $(s_{k}\times s_{k})$-матрица, а $J$ – антидиагональная матрица, составленная из единиц. Доказательство леммы. В качестве $U$ можно взять блочную матрицу где $C=\biggl(\begin{array}{c}\begin{array}{c|c}0 & I_{s_k-1}\end{array} \\ \hline 0\,\dots\,0\end{array}\biggr)$ – сопровождающая матрица полинома $z^{s_k}$. Несложно проверить, что $\det(U)=1$.
Дальнейшее доказательство теоремы использует тот факт, что умножение на целочисленную унимодулярную матрицу не меняет коядра линейного оператора. Имеем следующую последовательность элементарно эквивалентных матриц:
$$
\begin{equation*}
\begin{aligned} \, \mathcal{A}^{2m+1}-I&\sim p(\mathcal{A}+\mathcal{A}^{-1})\sim U\,p(\mathcal{A}+\mathcal{A}^{-1})\,U^{-1}\sim p(U\,(\mathcal{A}+\mathcal{A}^{-1})\,U^{-1}) \\ & \sim p\biggl(\begin{pmatrix} G & 0 \\ 0 & J\,G\,J \end{pmatrix}\biggr)\sim \begin{pmatrix} p(G) & 0 \\ 0 & p(J\,G\,J)\end{pmatrix}\sim \begin{pmatrix} p(G) & 0 \\ 0 & p(G)\end{pmatrix}. \end{aligned}
\end{equation*}
\notag
$$
Отсюда следует, что
$$
\begin{equation*}
\operatorname{coker}(\mathcal{A}^{2m+1}-I)=\operatorname{coker}(p(G)) \oplus\operatorname{coker}(p(G)).
\end{equation*}
\notag
$$
Доказательство для случая нечетного $n$ завершено.
Доказательство в четном случае $n=2m$ основано на тождестве и замечании, что факторгруппа $\operatorname{Jac}(\widehat{G}_{2m})/\operatorname{Jac}(\widehat{G}_2)$ изоморфна коядру матрицы $(\mathcal{A}^{2m}-1)(\mathcal{A}^2-1)^{-1}$.12.2. Приведенные якобианы и их периодичностьИзвестно, что группы гомологий $n$-листных разветвленных накрытий над узлом, вычисленные с коэффициентами в заданной циклической группе $\mathbb{Z}_m$, образуют периодическую последовательность. Следуя [84], представим это утверждение в более общей форме. Пусть $M_n$ – последовательность $n$-листных циклических накрытий, разветвленных над заданным узлом, и $\mathbb{A}$ – конечная абелева группа. Тогда последовательность групп гомологий $H_1(M_n,\mathbb{A})$ с коэффициентами в группе $\mathbb{A}$ периодична. Аналогичная теорема имеет место и для неразветвленных накрытий дополнения узла до гомологической сферы [76]. Напомним, что по теореме об универсальных коэффициентах
$$
\begin{equation*}
H_1(M_n,\mathbb{A})=H_1(M_n,\mathbb{Z})\otimes\mathbb{A}.
\end{equation*}
\notag
$$
Чтобы сформулировать аналогичное утверждение для графов, назовем приведенным якобианом $\operatorname{Jac}_\mathbb{A}(G)$ графа $G$ по абелевой группе $\mathbb{A}$ группу, заданную тензорным произведением $\operatorname{Jac}(G)\otimes\mathbb{A}$. Представим конечную абелеву группу $\mathbb{A}$ в виде суммы $\mathbb{Z}_{q_1}\oplus\mathbb{Z}_{q_2}\oplus\cdots\oplus\mathbb{Z}_{q_k}$, где $q_1,q_2,\dots,q_k$ – подходящие степени простых чисел, и положим
$$
\begin{equation*}
\operatorname{Jac}_{q}(G)=\operatorname{Jac}(G)\otimes \mathbb{Z}_q.
\end{equation*}
\notag
$$
Тогда приведенный якобиан $\operatorname{Jac}_\mathbb{A}(G)$ графа $G$ по группе $\mathbb{A}$ равен
$$
\begin{equation*}
\operatorname{Jac}_{q_1}(G)\oplus\operatorname{Jac}_{q_2}(G) \oplus\cdots\oplus\operatorname{Jac}_{q_k}(G).
\end{equation*}
\notag
$$
Отметим, что приведенные якобианы играют важную роль в дискретной теории динамических систем [39], [72]. Имеет место следующая теорема [66; теорема 2]. Теорема 12.2. Пусть $G_n=C_{n}(s_{1},s_{2},\dots,s_{k}),\,n=1,2,\dots$, – последовательность циркулянтных графов, а $\widehat{G}_n$ – соответствующая ей последовательность конусов. Пусть $\mathbb{A}$ – произвольная конечная абелева группа. Тогда последовательности приведенных по группе $\mathbb{A}$ якобианов $\operatorname{Jac}_\mathbb{A}(G_n)$ и $\operatorname{Jac}_\mathbb{A}(\widehat{G}_n)$ периодичны. Чтобы проиллюстрировать теорему 12.2, заметим, что для семейства графов $G_n=C_n(1,2)$ периоды приведенных якобианов $\operatorname{Jac}_{\,\mathbb{Z}_6}(G_{n})$ и $\operatorname{Jac}_{\,\mathbb{Z}_6}(\widehat{G}_{n})$ равны 12 и 5, а соответствующие периоды для $\operatorname{Jac}_{\,\mathbb{Z}_7}(G_{n})$ и $\operatorname{Jac}_{\,\mathbb{Z}_7}(\widehat{G}_{n})$ равны 56 и 12.
Цитирование в формате AMSBIB
\RBibitem{MedMed23} |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|