|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Циклические накрытия графов. Перечисление отмеченных остовных лесов и деревьев, индекс Кирхгофа и якобианы
А. Д. Медныхab, И. А. Медныхab a Институт математики им. С. Л. Соболева Сибирского отделения Российской академии наук
b Новосибирский государственный университет
Аннотация:
Цель настоящего обзора – изучение инвариантов циклических накрытий графов. При этом накрываемый граф предполагается фиксированным, а циклическая группа накрытия имеет сколь угодно большой порядок. Классическим примером такого накрытия является циркулянтный граф. Он накрывает одновершинный граф с заданным числом петель. Более сложными представителями семейства циклических накрытий являются $I$-, $Y$-, $H$-графы, обобщенные графы Петерсена, сэндвич-графы, дискретные торы и многие другие. В обзоре приведены аналитические формулы, позволяющие вычислять число отмеченных остовных лесов и деревьев в циклических накрытиях, найдена их асимптотика и изучены арифметические свойства этих чисел. Кроме того, для циркулянтных графов указаны точные формулы для вычисления индекса Кирхгофа и приведены структурные теоремы о строении якобианов таких графов.
Библиография: 95 названий.
Ключевые слова:
граф, якобиан, абелева группа, остовные деревья, отмеченные остовные леса, индекс Кирхгофа, числа Фибоначчи, полиномы Чебышёва.
Поступила в редакцию: 06.05.2022
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$ вершинах. Пусть
$$
\begin{equation*}
\chi_{G}(\lambda)=\det(\lambda\,I_{n}-L(G))
\end{equation*}
\notag
$$
– характеристический полином его матрицы Лапласа $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], определяемым как
$$
\begin{equation*}
W(G)=\sum_{1\leqslant i<j\leqslant n}d_{i,j},
\end{equation*}
\notag
$$
где $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] в несколько иной форме
$$
\begin{equation}
M(P)=|a_{0}|\prod_{|\alpha_{i}|>1}|\alpha_i|.
\end{equation}
\tag{4}
$$
Эквивалентность этих определений следует из формулы Йенсена [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})$ задаются простыми формулами
$$
\begin{equation*}
\lambda_j=p(\varepsilon^j_n),\qquad j=0,1,\dots,n-1,
\end{equation*}
\notag
$$
где $p(z)=a_0+a_1 z+\cdots+a_{n-1}z^{n-1}$ и $\varepsilon_n$ – первообразный корень степени $n$ из единицы. Кроме того, рассмотренная циркулянтная матрица представима в виде
$$
\begin{equation*}
C=p(T),
\end{equation*}
\notag
$$
где $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)$ рассмотрим сопровождающий полином Лорана
$$
\begin{equation*}
P(z)=2k-\sum_{i=1}^k(z^{s_i}+z^{-s_i}).
\end{equation*}
\notag
$$
Тогда лапласиан графа $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$. Циркулянтное расслоение
$$
\begin{equation*}
H_n=H_n(G_1,G_2,\dots,G_m)
\end{equation*}
\notag
$$
над $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)$, опуская символику для пустых графов. Дискретный тор
$$
\begin{equation*}
T_{n,m}=C_n\times C_m
\end{equation*}
\notag
$$
– декартово произведение циклических графов $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)$ остовных деревьев циркулянтного графа
$$
\begin{equation*}
C_{n}(s_1,s_2,\dots,s_k),\qquad 1\leqslant s_1< s_2<\cdots< s_k<\frac{n}{2}\,,
\end{equation*}
\notag
$$
дается формулой
$$
\begin{equation*}
\tau(n)=\frac{n}{q}\prod_{p=1}^{s_k-1}|2T_n(w_p)-2|,
\end{equation*}
\notag
$$
при этом $q=s_1^2+s_2^2+\cdots+s_k^2$ и $w_p$, $p=1,2,\dots,s_k-1$, – отличные от единицы корни алгебраического уравнения
$$
\begin{equation*}
Q(w)=0,
\end{equation*}
\notag
$$
где $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$. Величина
$$
\begin{equation*}
\lim_{n\to\infty}\frac{\log\tau(n)}{v(G_n)}
\end{equation*}
\notag
$$
(если она существует) называется термодинамическим пределом (а также древесной энтропией или балком) семейства $G_n$. Изучению этой величины для различных семейств графов посвящено значительное количество работ по статистической физике (см., например, [87], [90], [79], [35], [55]). В этом пункте будут приведены асимптотические формулы для числа остовных деревьев циркулянтных графов, полученные в [61] и [62]. Интересно сопоставить эти результаты с результатами работ [93], [18], [94] и [55], где аналогичные асимптотики получены другими методами. Имеет место следующий результат [62; теорема 2]. Теорема 4.2. Число остовных деревьев циркулянтного графа
$$
\begin{equation*}
C_{n}(s_1,s_2,\dots,s_k),\qquad 1\leqslant s_1<s_2<\cdots<s_k<\frac{n}{2}\,,
\end{equation*}
\notag
$$
имеет следующую асимптотику:
$$
\begin{equation*}
\tau(n)\sim\frac{n}{q}A^n,\qquad n\to\infty,
\end{equation*}
\notag
$$
где $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)$. Другими словами,
$$
\begin{equation*}
\lim_{n\to\infty}\frac{\log\tau(C_{n}(s_1,s_2,\dots,s_k))}{n}=m(P),
\end{equation*}
\notag
$$
где $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)$. Тогда
$$
\begin{equation*}
F(z)=\sum_{n=1}^\infty\tau(n)z^n
\end{equation*}
\notag
$$
– рациональная функция с целыми коэффициентами. Кроме того, $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], оно равно
$$
\begin{equation*}
\lambda_{n/2}=2\sum_{i=1}^{k}(1-(-1)^{s_i})=4p.
\end{equation*}
\notag
$$
Приведем несколько примеров, иллюстрирующих приведенные выше результаты. Пример 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$. Кроме того,
$$
\begin{equation*}
\sum_{n=1}^\infty\tau(n)z^n= \frac{1 - 2 w + 2 w^2}{(1 + w) (-3 + 2 w)^2}\,,\quad\text{где}\ \ w=\frac{1}{2}\biggl(z+\frac{1}{z}\biggr).
\end{equation*}
\notag
$$
Пример 4.2 (граф $C_n(1,3)$). Теорема 4.1 дает следующую формулу для числа остовных деревьев:
$$
\begin{equation*}
\tau(n)= \frac{2n}{5}\biggl(T_n\biggl(\frac{-1-i}{2}\biggr)-1\biggr) \biggl(T_n\biggl(\frac{-1+i}{2}\biggr)-1\biggr).
\end{equation*}
\notag
$$
По теореме 4.4 имеем $\tau(n)=n\,a(n)^2$, если $n$ нечетно, и $\tau(n)=2n\,a(n)^2$, если $n$ четно, где $a(n)$ – некоторая целочисленная последовательность. Здесь $A=(1+\sqrt{1-2i}\,)(1+\sqrt{1+2i}\,)/2\approx2.89$ и $\tau(n)\sim(n/10)A^n$, $n\to\infty$. Далее,
$$
\begin{equation*}
\sum_{n=1}^\infty\tau(n)z^n= \frac{(1+w)(1-w-2w^2+11w^3+8w^4-16w^5+4w^7)}{2(-1+w)(-1-3w-3w^2+2w^4)^2}\,,
\end{equation*}
\notag
$$
где $w$ – то же, что и в предыдущем примере. Пример 4.3 (граф $C_n(2,3)$). По теореме 4.1
$$
\begin{equation*}
\tau(n)=\frac{4n}{13}(T_n(\theta_1)-1)(T_n(\theta_2)-1),
\end{equation*}
\notag
$$
где $\theta_{1,2}=(-3 \pm i\sqrt{3}\,)/4$. По теореме 4.4 для некоторой целочисленной последовательности $a(n)$ имеем $\tau(n)=n\,a(n)^2$. Можно показать [93; теорема 9], что
$$
\begin{equation*}
\begin{gathered} \, a(n)=a(n-1)+a(n-2)+a(n-3)-a(n-4), \\ a(0)=0,\quad a(1)=1,\quad a(2)=1,\ \ a(3)=1. \end{gathered}
\end{equation*}
\notag
$$
При этом $\tau(n)\sim(n/13)A^n$, $n\to\infty$, где $A\approx2.96$ – корень уравнения
$$
\begin{equation*}
1-3z+z^2-3z^3+z^4=0.
\end{equation*}
\notag
$$
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})$ вычисляется по формуле
$$
\begin{equation*}
\operatorname{Kf}(G_n)=\frac{n}{12\sum_{j=1}^{k}s_{j}^{2}}\biggl(n^{2}- \frac{\sum_{j=1}^{k}s_{j}^{4}}{\sum_{j=1}^{k}s_{j}^{2}}\biggr)+ \sum_{p=2}^{s_{k}}\frac{n^{2}\,U_{n-1}(w_{p})} {(1-T_{n}(w_{p}))Q'(w_{p})}\,,
\end{equation*}
\notag
$$
где $w_{p}$ – отличные от единицы корни полинома
$$
\begin{equation*}
Q(w)=\sum_{j=1}^{k} (2-2T_{s_{j}}(w)),
\end{equation*}
\notag
$$
а $T_{n}(w)$ и $U_{n-1}(w)$ – полиномы Чебышёва первого и второго рода соответственно. Как следствие, мы получим приводимую ниже асимптотическую формулу поведения индекса Кирхгофа для циркулянтных графов $G_{n}=C_{n}(s_{1},s_{2},\dots,s_{k})$ при $n$, стремящемся к бесконечности [64; следствие 1]. Следствие 4.2. Имеет место асимптотическая формула
$$
\begin{equation*}
\operatorname{Kf}(G_{n})=\frac{n}{12\sum_{j=1}^{k} s_{j}^{2}}\biggl(n^{2}- \frac{\sum_{j=1}^{k} s_{j}^{4}}{\sum_{j=1}^{k} s_{j}^{2}}\biggr)- \sum_{\substack{z:P(z)=0\\|z|>1}} \frac{n^2}{zP'(z)}+ O\biggl(\frac{n^{2}}{A^{n}}\biggr),\qquad n\to\infty,
\end{equation*}
\notag
$$
где $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.4 (циклический граф $C_{n}$). Индекс Кирхгофа циклического графа равен
$$
\begin{equation*}
\operatorname{Kf}({C_{n}})=\frac{n^3-n}{12}\,.
\end{equation*}
\notag
$$
Пример 4.5 (граф $C_{n}(1,2)$). Для данного семейства графов индекс Кирхгофа может быть вычислен по формуле
$$
\begin{equation*}
\operatorname{Kf}({C_{n}(1,2)})=\frac{n}{300}(5n^{2}-17)+ \frac{n^{2}}{25}\,\frac{F_{2 n}}{F_{n}^{2}}\,,
\end{equation*}
\notag
$$
где $F_{n}$ – $n$-е число Фибоначчи. Заметим, что
$$
\begin{equation*}
\frac{F_{2n}}{F_{n}^{2}}=\sqrt{5}+O(\phi^{-2n}),
\end{equation*}
\notag
$$
где $\phi=(1+\sqrt{5}\,)/2$ – золотое сечение. Пример 4.6 (граф $C_{n}(1,3)$). Индекс Кирхгофа семейства циркулянтных графов $C_n(1,3)$ имеет следующее асимптотическое поведение:
$$
\begin{equation*}
\operatorname{Kf}({C_{n}(1,3)})= \frac{n}{600}\biggl(5n^{2}+6\sqrt{110+50\sqrt{5}}\,n-41\biggr)+ O\biggl(\frac{n^{2}}{A^{n}}\biggr),\qquad n\to\infty,
\end{equation*}
\notag
$$
где $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)$ дается формулой
$$
\begin{equation*}
\tau(n)=\frac{n}{2q}\prod_{p=1}^{s_k-1}(2T_n(u_p)-2) \prod_{p=1}^{s_k}(2T_n(v_p)+2),
\end{equation*}
\notag
$$
где $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$, являются соответственно корнями алгебраических уравнений
$$
\begin{equation*}
Q(u)-1=0,\quad u\ne1,\quad\textit{и}\quad Q(v)+1=0,
\end{equation*}
\notag
$$
где $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$ имеет следующее асимптотическое поведение:
$$
\begin{equation*}
\tau(n)\sim\frac{n\,d^2}{2q}K^n,\quad n\to\infty,\quad\textit{и}\quad \operatorname{gcd}(n,d)=1.
\end{equation*}
\notag
$$
Здесь $q=s_1^2+s_2^2+\cdots+s_k^2$ и
$$
\begin{equation*}
K=\exp\biggr(\int_{0}^{1}\log|P^2(e^{2\pi\mathrm{i}t})+ 2P(e^{2\pi\mathrm{i}t})|\,dt\biggr)
\end{equation*}
\notag
$$
– мера Малера полинома Лорана $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}})$. Другими словами,
$$
\begin{equation*}
\lim_{n\to\infty} \frac{\log\tau(C_{2n}(s_1,s_2,\dots,s_k,n))}{n}=m(R),
\end{equation*}
\notag
$$
где $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]. Теорема 5.4. Индекс Кирхгофа лестницы Мёбиуса $M_n=C_{2n}(1,n)$ дается формулой
$$
\begin{equation*}
\operatorname{Kf}(M_n)=\frac{n^3-n}{6}+ \frac{n^2 \operatorname{th} ((n/2)\operatorname{arch} 2)}{\sqrt{3}}\,.
\end{equation*}
\notag
$$
Приведем родственный результат, разными методами установленный в работах [20] и [5]. Теорема 5.5. Индекс Кирхгофа призматического графа $\operatorname{Pr}_n=C_n\times P_2$ дается формулой
$$
\begin{equation*}
\operatorname{Kf}(\operatorname{Pr}_n)=\frac{n^3-n}{6}+ \frac{n^2 \operatorname{cth} ((n/2)\operatorname{arch} 2)}{\sqrt{3}}\,.
\end{equation*}
\notag
$$
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 имеем
$$
\begin{equation*}
\tau(n)=n(T_{n}(2)+1)\sim\frac{n}{2}(2+\sqrt{3}\,)^{n},\qquad n\to\infty.
\end{equation*}
\notag
$$
Более того, по теореме 5.3 существует целочисленная последовательность $a(n)$ такая, что $\tau(n)=2n\,a(n)^2$, если $n$ четно, и $\tau(n)=3n\,a(n)^2$, если $n$ нечетно. Пример 5.2 (графы $C_{2n}(1,2,n)$). Применяя теорему 5.2, получим
$$
\begin{equation*}
\tau(n)\sim\frac{n}{10}K_{1,2}^n,\qquad n\to\infty,
\end{equation*}
\notag
$$
где $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. Число остовных деревьев в циркулянтном графе с неограниченными скачками
$$
\begin{equation*}
\begin{gathered} \, 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<\biggl[\frac{\beta n}{2}\biggr], \qquad 1\leqslant \alpha_1<\alpha_2<\cdots<\alpha_\ell\leqslant\biggl[\frac{\beta}{2}\biggr], \end{gathered}
\end{equation*}
\notag
$$
задается следующей формулой:
$$
\begin{equation*}
\tau(n)=\frac{n}{\beta\,q}\prod_{u=0}^{\beta-1}\, \prod_{\substack{1 \leqslant j \leqslant s_k \\ w_{j}(0)\ne1}} \biggl|2T_{n}(w_{j}(u))-2\cos\biggl(\frac{2\pi u}{\beta}\biggr)\biggr|,
\end{equation*}
\notag
$$
где для каждого целого числа $u=0,1,\dots,\beta-1$ определены величины $w_{j}(u)$, $j=1,2,\dots,s_{k}$, – полный набор корней уравнения
$$
\begin{equation*}
\sum_{i=1}^{k}T_{s_i}(w)=k+2\sum_{m=1}^{\ell}\sin^2 \biggl(\frac{\pi\,u\,\alpha_{m}}{\beta}\biggr).
\end{equation*}
\notag
$$
Здесь $T_{s}(w)$ – $s$-й полином Чебышёва первого типа и $q=s_{1}^{2}+s_{2}^{2}+\cdots+s_{k}^{2}$. В качестве следствия из теоремы 6.1 получается результат Ж. Луис, установленный в работе [55] в несколько иной форме. Следствие 6.1. Число остовных деревьев в циркулянтном графе с неограниченными скачками
$$
\begin{equation*}
C_{\beta n}(1,\alpha_1n,\alpha_2n,\dots,\alpha_\ell n),\qquad 1\leqslant \alpha_1<\alpha_2<\cdots<\alpha_\ell\leqslant \biggl[\frac{\beta}{2}\biggr],
\end{equation*}
\notag
$$
задается формулой
$$
\begin{equation*}
\tau(n)=\frac{n\,2^{\beta-1}}{\beta}\prod_{u=1}^{\beta-1} \biggl(T_n\biggl(1+2\sum_{m=1}^{\ell}\sin^2 \biggl(\frac{\pi\,u\,\alpha_{m}}{\beta}\biggr)\biggr)- \cos\biggl(\frac{2\pi\,u}{\beta}\biggr)\biggr),
\end{equation*}
\notag
$$
где $T_n(w)$ – полином Чебышёва первого рода. Отметим еще одно следствие из теоремы 6.1. Следствие 6.2. Число остовных деревьев в циркулянтном графе с неограниченными скачками
$$
\begin{equation*}
C_{\beta n}(1,2,\alpha_1n,\alpha_2n,\dots,\alpha_\ell n),\qquad 1\leqslant \alpha_1<\alpha_2<\cdots<\alpha_\ell\leqslant \biggl[\frac{\beta}{2}\biggr],
\end{equation*}
\notag
$$
задается формулой
$$
\begin{equation*}
\tau(n)=\frac{n\,F_n^2}{\beta}\,\prod_{u=1}^{\beta-1}\, \prod_{j=1}^2\biggl|2T_n(w_{j}(u))- 2\cos\biggl(\dfrac{2\pi\,u}{\beta}\biggr)\biggr|,
\end{equation*}
\notag
$$
где $F_n$ – $n$-е число Фибоначчи, а $T_n(w)$ – полином Чебышёва первого рода и
$$
\begin{equation*}
w_{1,2}(u)=\frac{1}{4}\biggl(-1\pm\sqrt{25+16\sum_{m=1}^{\ell} \sin^2\biggl(\dfrac{\pi\,u\,\alpha_{m}}{\beta}\biggr)}\,\biggr).
\end{equation*}
\notag
$$
6.2. Арифметические свойства числа остовных деревьев в циркулянтных графах с неограниченными скачками Арифметические свойства числа остовных деревьев в циркулянтных графах с неограниченными скачками представлены в следующей теореме [67; теорема 5.1]. Теорема 6.2. Обозначим через $\tau(n)$ число остовных деревьев в циркулянтном графе
$$
\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
$$
где $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$. Тогда число остовных деревьев в циркулянтном графе с неограниченными скачками
$$
\begin{equation*}
C_{\beta\,n}(s_1,s_2,\dots,s_k,\alpha_1n,\alpha_2n,\dots,\alpha_\ell n)
\end{equation*}
\notag
$$
имеет следующее асимптотическое поведение:
$$
\begin{equation*}
\tau(n)\sim\frac{n\,d^2}{\beta\,q}A^n,\quad n\to\infty,\quad\textit{и}\quad \operatorname{gcd}(n,d)=1,
\end{equation*}
\notag
$$
где
$$
\begin{equation*}
q=s_1^2+s_2^2+\cdots+s_k^2,\qquad A=\prod_{u=0}^{\beta-1}M(P_u)
\end{equation*}
\notag
$$
и $M(P_u)=\exp\biggl(\displaystyle\int_0^1 \log|P_u(e^{2\pi \mathrm{i} t})|\,dt\biggr)$ – мера Малера полинома Лорана
$$
\begin{equation*}
P_u(z)=2k-\sum_{i=1}^k(z^{s_i}+z^{-s_i})+ 4\sum_{m=1}^{\ell}\sin^2\biggl(\frac{\pi u \alpha_m }{\beta}\biggr).
\end{equation*}
\notag
$$
Приведем несколько примеров, иллюстрирующих приведенные выше результаты. Пример 6.1 (граф $C''_{2n}(1,n)$ – лестница Мёбиуса с двойными ступенями). Применяя теорему 6.1, получим
$$
\begin{equation*}
\tau(n)=\tau(C''_{2n}(1,n))=n\,(T_n(3)+1).
\end{equation*}
\notag
$$
Интересно сравнить этот результат с аналогичным результатом, полученным в [94; теорема 4]. Напомним [11], что число остовных деревьев в лестнице Мёбиуса с одинарными ступенями равно $n(T_n(2)+1)$. Пример 6.2 (граф $C_{2n}(1,2,n)$). В данном примере имеем
$$
\begin{equation*}
\tau(n)=2n F_n^2\biggl|T_n\biggl(\frac{-1-\sqrt{41}}4\biggr)-1\biggr|\, \biggl|T_n\biggl(\frac{-1+\sqrt{41}}4\biggr)-1\biggr|.
\end{equation*}
\notag
$$
Исходя из теоремы 6.2 существует целочисленная последовательность $a(n)$ такая, что $\tau(n)=2n\,a(n)^2$, если $n$ четно, и $\tau(n)=na(n)^2$, если $n$ нечетно. Пример 6.3 (граф $C_{2n}(1,2,3,n)$). Для этого семейства графов число остовных деревьев задается формулой
$$
\begin{equation*}
\tau(n)=\frac{8 n}{7}(T_n(\theta_1)-1)(T_n(\theta_2)-1) \prod_{p=1}^3(T_n(\omega_p)+1),
\end{equation*}
\notag
$$
где
$$
\begin{equation*}
\theta_{1}=\frac{-3+i\sqrt{7}}{4}\,,\qquad \theta_{2}=\frac{-3-i\sqrt{7}}{4}\,,
\end{equation*}
\notag
$$
а $\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)$). В этом случае имеем
$$
\begin{equation*}
\tau(n)=\frac{n}{3}\biggl(2T_n\biggl(\frac{5}{2}\biggr)+1\biggr)^2= \frac{n}{3}\biggl(\biggl(\frac{5+\sqrt{21}}{2}\biggr)^n+ \biggl(\frac{5-\sqrt{21}}{2}\biggr)^n+1\biggr)^2.
\end{equation*}
\notag
$$
См. также [94; теорема 5]. Заметим, что $\tau(n)=3n\,a(n)^2$, где $a(n)$ удовлетворяет рекуррентному соотношению
$$
\begin{equation*}
a(n)=6a(n-1)-6a(n-2)+a(n-3)
\end{equation*}
\notag
$$
с начальными данными $a(1)=2$, $a(2)=8$, $a(3)=37$. Пример 6.5 (граф $C_{3n}(1,2,n)$). Вследствие теоремы 6.1 получим
$$
\begin{equation*}
\tau(n)=\frac{n}{3}F_n^2(2T_n(\omega_1)+1)^2(2T_n(\omega_2)+1)^2,
\end{equation*}
\notag
$$
где $F_n$ – $n$-е число Фибоначчи и
$$
\begin{equation*}
\omega_{1}=\frac{-1+\sqrt{37}}{4}\,,\qquad \omega_{2}=\frac{-1-\sqrt{37}}{4}\,.
\end{equation*}
\notag
$$
По теореме 6.2 имеем: $\tau(n)=3n\,a(n)^2$ для некоторой целочисленной последовательности $a(n)$. Пример 6.6 (граф $C_{6n}(1,n,3n)$). В рассматриваемом случае справедлива формула
$$
\begin{equation*}
\tau(n)=\frac{n}{3}\biggl(2T_n\biggl(\frac{5}{2}\biggr)+ 1\biggr)^2\biggl(2T_n\biggl(\frac{7}2\biggr)-1\biggr)^2(T_n(5)+1).
\end{equation*}
\notag
$$
Для подходящей целочисленной последовательности $a(n)$ имеем $\tau(n)=6n\,a(n)^2$, если $n$ четно, и $\tau(n)=18n\,a(n)^2$, если $n$ нечетно. Пример 6.7 (граф $C_{12n}(1,3n,4n)$). В этом случае
$$
\begin{equation*}
\tau(n)=\frac{2 n}{3}T_n(2)^2\biggl(2T_n\biggl(\frac{5}2\biggr)+ 1\biggr)^2(T_n(3)+1)\biggl(4T_n\biggl(\frac{7}2\biggr)^2-3\biggr)^2 \biggl(2T_n\biggl(\frac{9}2\biggr)-1\biggr)^2.
\end{equation*}
\notag
$$
Исходя из теоремы 6.2, можно заключить, что $\tau(n)=3n\,a(n)^2$, если $n$ четно, и $\tau(n)=6n\,a(n)^2$, если $n$ нечетно, для некоторой последовательности $a(n)$ четных чисел.
7. Циркулянтные расслоения графов7.1. Число остовных деревьев в циркулянтных расслоениях Для произвольного циркулянтного расслоения
$$
\begin{equation*}
H_n=H_n(G_1,\,G_2,\dots,G_m),
\end{equation*}
\notag
$$
где
$$
\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)$ задается формулой
$$
\begin{equation*}
(-1)^{m-m'}\eta\,z^s,
\end{equation*}
\notag
$$
где $\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))$, где
$$
\begin{equation*}
X=(x_{1},x_{2},\dots,x_{m}),\qquad x_{j}=2k_{i}+d_{i}-\sum_{j=1}^{k_{i}}(z^{s_{i,j}}+z^{-s_{i,j}}).
\end{equation*}
\notag
$$
Для $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)$ задается формулой
$$
\begin{equation*}
\tau(n)=\frac{n\,\eta^{n}}{q}\,\prod_{p=1}^{s-1}|2T_n(w_p)-2|,
\end{equation*}
\notag
$$
где
$$
\begin{equation*}
s=\sum_{i=1}^{m}s_{i,k_i},\qquad q=\sum_{i=1}^{m}\,\sum_{j=1}^{k_{i}}s_{i,k_{j}}^{2},
\end{equation*}
\notag
$$
$w_p$, $p=1,2,\dots,s-1$, – все отличные от единицы корни уравнения $Q(w)=0$, а $\eta$ то же, что и в лемме 7.1. Доказательство. Для удобства читателя приведем схему доказательства теоремы 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$ при условии
$$
\begin{equation*}
\operatorname{gcd}(s_{i,p},\,i=1,2,\dots,m,\,p=1,2,\dots,k_i)=1
\end{equation*}
\notag
$$
описывается формулой
$$
\begin{equation*}
\tau(n)\sim\frac{n}{q}A^{n},\qquad n\to\infty,
\end{equation*}
\notag
$$
где $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})$ и
$$
\begin{equation*}
P(z)=2k-\sum_{p=1}^{k}(z^{s_p}+z^{-s_p}), \qquad Q(w)=2k-\sum_{p=1}^{k}2T_{s_p}(w).
\end{equation*}
\notag
$$
Различные аспекты сложности циркулянтных графов были изучены в разделе 4. Пример 7.2 ($I$-граф $I(n,k,l)$ и обобщенный граф Петерсена $\operatorname{GP}(n,k)$). В качестве базы рассмотрим граф $H$, состоящий из двух вершин, соединенных ребром. Пусть $G_{1}=C_{n}(k)$ и $G_{2}=C_{n}(l)$. Тогда
$$
\begin{equation*}
I(n,k,l)=H_{n}(G_{1},G_{2})\quad\text{и}\quad \operatorname{GP}(n,k)=I(n,k,1).
\end{equation*}
\notag
$$
Для данного циркулянтного расслоения имеем
$$
\begin{equation*}
\begin{aligned} \, P(z)&=(3-z ^{k}-z^{-k})(3-z^{l}-z^{-l})-1, \\ Q(w)&=(3-2T_{k}(w))( 3-2T_{l}(w))-1. \end{aligned}
\end{equation*}
\notag
$$
Арифметические и асимптотические свойства сложности $I$-графов изучались в работе [68]. Пример 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$. Положим
$$
\begin{equation*}
D(x_1,x_2,\dots,x_m)=\det\begin{pmatrix} \!\!\hphantom{-}x_1 & {-}1 & \hphantom{-}0 & \dots & \hphantom{-}0 & \hphantom{-}0& \hphantom{-}0 \\ -1 & \hphantom{-}x_2 & -1 & \dots & \hphantom{-}0 & \hphantom{-}0& \hphantom{-}0 \\ \ldots& \ldots & \hphantom{-}\ldots& \ldots&\hphantom{-} \ldots & \hphantom{-}\ldots & \hphantom{-}\ldots\\ \hphantom{-}0 & \hphantom{-}0 & \hphantom{-}0 & \dots & -1 & \hphantom{-}x_{m-1} & -1\\ \hphantom{-}0 & \hphantom{-}0 & \hphantom{-}0 & \dots & \hphantom{-}0 & -1 & \hphantom{-}x_m \end{pmatrix}.
\end{equation*}
\notag
$$
Прямым вычислением определителя получим
$$
\begin{equation*}
\begin{gathered} \, D(x_1,x_2,\dots,x_m)=x_1D(x_2,\dots,x_m)-D(x_3,\dots,x_m), \\ D(x_1)=x_1,\qquad D(x_1,x_2)=x_1x_2-1. \end{gathered}
\end{equation*}
\notag
$$
Соответственно,
$$
\begin{equation*}
Q(w)=D(w_1,w_2,\dots,w_m)\quad\text{и}\quad Q(-1)=D(d_1+4t_1,d_2+4t_2,\dots,d_m+4t_m),
\end{equation*}
\notag
$$
где $w_{i}=2k_{i}+d_i-\displaystyle\sum_{j=1}^{k_i}2\,T_{s_{i,j}}(w)$, а $t_i$ – число скачков нечетной длины в графе $G_{i}$. Заметим, что случай $m=1$ приводит к циркулянтному графу и уже рассмотрен выше. Случай $m=2$ исследован в работе [2]. Пример 7.4 (обобщенный $Y$-граф). Рассмотрим обобщенный $Y$-граф
$$
\begin{equation*}
Y_{n}(G_{1},G_{2},G_{3}),\qquad G_{i}=C_{n}(s_{i,1},s_{i,2},\dots,s_{i,k_i}), \quad i=1,2,3.
\end{equation*}
\notag
$$
В этом случае
$$
\begin{equation*}
Q(w)=3A_{1}(w)A_{2}(w)A_{3}(w)-A_{1}(w)A_{2}(w)-A_{1}(w)A_{3}(w)- A_{2}(w)A_{3}(w),
\end{equation*}
\notag
$$
где $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$. В этом случае
$$
\begin{equation*}
\begin{aligned} \, Q(w)&=A_{1}(w)A_{2}(w)A_{3}(w)A_{4}(w) \\ &\qquad\times\biggl(\biggl(3-\frac{1}{A_{1}(w)}- \frac{1}{A_{2}(w)}\biggr)\biggl(3-\frac{1}{A_{3}(w)}- \frac{1}{A_{4}(w)}\biggr)-1\biggr), \end{aligned}
\end{equation*}
\notag
$$
где $A_{i}(w)$ имеют такой же вид, как и в предыдущем примере. Пример 7.6 (дискретный тор $T_{n,m}=C_n\times 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$ вершинах. Обобщенный лапласиан с набором переменных $X=(x,\dots,x)$ ($m$ раз) является циркулянтной матрицей следующего вида:
$$
\begin{equation*}
L(H,X)=\begin{pmatrix} \hphantom{-}x & -1 & \hphantom{-}0 & \hphantom{-}\dots & \hphantom{-}0& -1 \\ -1 & \hphantom{-}x & -1 & \hphantom{-}\dots & \hphantom{-}0& \hphantom{-}0 \\ & \hphantom{-}\vdots & & \hphantom{-}\vdots & &\hphantom{-}\vdots \\ -1 & \hphantom{-}0 & \hphantom{-}0 & \hphantom{-}\dots & -1 & \hphantom{-}x\\ \end{pmatrix}.
\end{equation*}
\notag
$$
Здесь $L(H,X)$ – циркулянтная матрица порядка $m$ с собственными значениями
$$
\begin{equation*}
\mu_j=x-e^{2\pi \mathrm{i} j/m}-(e^{2\pi \mathrm{i} j/m})^{m-1}= x-2\cos\biggl(\frac{2\pi j}{m}\biggr),\qquad j=0,\dots,m-1.
\end{equation*}
\notag
$$
Следовательно,
$$
\begin{equation*}
\det(L(H,X))=\prod_{j=0}^{m-1}\mu_j=2 T_{m}\biggl(\frac{x}{2}\biggr)-2.
\end{equation*}
\notag
$$
Подставляя $x=4-z-z^{-1}$ и $w=(z+z^{-1})/2$, имеем
$$
\begin{equation*}
Q(w)=2 T_{m}(2-w)-2.
\end{equation*}
\notag
$$
Пример 7.7 (прямое произведение $C_n\times H$, где $H$ – регулярный граф). Пусть $H$ – связный $d$-регулярный граф. Отождествим прямое произведение $C_n\times H$ и
$$
\begin{equation*}
H_{n}=H_{n}(\underbrace{C_{n}(1),\dots,C_{n}(1)}_{m \text{ раз }}).
\end{equation*}
\notag
$$
Пусть $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}$ имеет вид
$$
\begin{equation*}
L(H_{n})=D(H_{n})-A(H_{n}),
\end{equation*}
\notag
$$
где $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)$ полином напряжений совпадает с сопровождающим полиномом Лорана
$$
\begin{equation*}
P(z)=2k-\displaystyle\sum_{p=1}^{k}(z^{s_p}+z^{-s_p}).
\end{equation*}
\notag
$$
В случае циркулянтных расслоений, рассмотренных в п. 7.1, полином $P(z)$ возникает как определитель обобщенного лапласиана $L(H,X)$. Отметим следующие важные свойства полинома напряжений $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$. Отметим также следующие полезное соотношение:
$$
\begin{equation*}
Q(w)=P(w+\sqrt{w^2-1}\,).
\end{equation*}
\notag
$$
8.1. Теорема о числе остовных деревьев в циклическом накрытии Незначительная переформулировка теоремы 6.2 из работы [50] дает следующий результат. Теорема 8.1. Рассмотрим циклическое накрытие $H_n$. Пусть $P(z)$ – его полином напряжений, а $Q(w)$ – преобразование Чебышёва полинома $P(z)$. Тогда число $\tau(n)$ остовных деревьев в $H_{n}$ может быть вычислено по формуле
$$
\begin{equation*}
\tau(n)=\frac{2 n\tau(H)\eta^{n}}{|P''(1)|}\, \prod_{p=1}^{s-1}|2T_n(w_p)-2|,
\end{equation*}
\notag
$$
где произведение берется по всем отличным от единицы корням полинома $Q(w)$, а $\eta$ – модуль старшего коэффициента полинома $P(z)$. Замечание 8.2. Сравнивая этот результат с теоремой 7.1, отметим, что в случае циркулянтных расслоений
$$
\begin{equation*}
|P''(1)|=2 q \tau(H),\quad\text{где}\quad q=\sum_{i=1}^{m}\,\sum_{j=1}^{k_{i}}s_{i,k_{j}}^{2}.
\end{equation*}
\notag
$$
8.2. Асимптотика числа остовных деревьев в циклическом накрытии В данном пункте приводится формула, описывающая асимптотику числа $\tau(H_n)$ при $n\to\infty$. Основной результат составляет следующая теорема, доказанная в [50] (см. [50; теорема 8.1]). Теорема 8.2. Асимптотическое поведение числа остовных деревьев в циклическом накрытии $H_n$ описывается формулой
$$
\begin{equation*}
\tau(H_n)\sim \frac{2n\,\tau(H)}{|P''(1)|}\,A^n,\qquad n\to\infty,
\end{equation*}
\notag
$$
где $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$, задается формулой
$$
\begin{equation*}
f_{G}(n)=\prod_{p=1}^{s_k}|2T_{n}(w_{p})-2|,
\end{equation*}
\notag
$$
где $w_{p},\,p=1,2,\dots,s_{k}$, – все корни алгебраического уравнения
$$
\begin{equation*}
\sum_{j=1}^{k}(2T_{s_{j}}(w)-2)=1,
\end{equation*}
\notag
$$
а $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)$ задается формулой
$$
\begin{equation*}
f_{G}(n)=\prod_{p=1}^{s_k}(2T_n(u_p)-2)(2T_n(v_p)+2),
\end{equation*}
\notag
$$
где величины $u_p$ и $v_p$, $p=1,2,\dots,s_k$, – корни алгебраических уравнений
$$
\begin{equation*}
Q(u)-1=0\quad\textit{и}\quad Q(v)+1=0
\end{equation*}
\notag
$$
соответственно. При этом
$$
\begin{equation*}
Q(w)=2k+2-2\sum_{i=1}^{k}T_{s_i}(w)
\end{equation*}
\notag
$$
и $T_s(w)$ – полином Чебышёва первого рода. 9.2. Арифметические свойства числа отмеченных остовных лесов В случае циркулянтных графов с четной степенью вершин имеет место следующий результат [33; теорема 7.1]. Теорема 9.3. Обозначим через $f_{G}(n)$ число отмеченных остовных лесов в циркулянтном графе
$$
\begin{equation*}
C_{n}(s_1,s_2,\dots,s_k),\qquad 1\leqslant s_1<s_2<\cdots<s_k<\frac{n}{2}\,.
\end{equation*}
\notag
$$
Пусть $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$ четно. Доказательство основано на следующих соображениях. Поскольку
$$
\begin{equation*}
\mu_{j}=P(\varepsilon_{n}^{j})=P(\varepsilon_{n}^{n-j})=\mu_{n-j},\qquad j=0,1,\dots,n-1,
\end{equation*}
\notag
$$
то все собственные значения матрицы $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)$ – число отмеченных остовных лесов в циркулянтном графе
$$
\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
$$
и $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. Асимптотическое поведение числа отмеченных остовных лесов в циркулянтном графе
$$
\begin{equation*}
G=C_{n}(s_1,s_2,\dots,s_k),\qquad 1\leqslant{s_1}<s_2<\cdots<s_k<\frac{n}{2}\,,
\end{equation*}
\notag
$$
определяется формулой
$$
\begin{equation*}
f_{G}(n)\sim A^n, \qquad n\to\infty,
\end{equation*}
\notag
$$
где $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)$.
Окончательно,
$$
\begin{equation*}
f_{G}(n)=\prod_{s=1}^{s_k}|2\,T_n(w_s)-2|\sim A^n,\qquad n\to\infty.
\end{equation*}
\notag
$$
Асимптотика числа отмеченных остовных лесов в циркулянтном графе с нечетной степенью вершин определяется следующей теоремой. Теорема 9.6. Число $f_{G}(n)$ отмеченных остовных лесов в циркулянтном графе
$$
\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
$$
имеет следующую асимптотику:
$$
\begin{equation*}
f_{G}(n)\sim K^{n},\qquad n\to\infty,
\end{equation*}
\notag
$$
где $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 заключаем, что
$$
\begin{equation*}
f_{G}(n) \sim\biggl(\frac{3+\sqrt{5}}{2}\biggr)^{n},\qquad n\to\infty.
\end{equation*}
\notag
$$
Исходя из формул, определяющих числа Фибоначчи $F_{n}$ и Люка $L_n$, можно заметить, что $f_{G}(n)=5F_{n}^{2}$, если $n$ четно, и $f_{G}(n)=L_{n}^{2}$, если $n$ нечетно. Последний результат был получен ранее в работе [14]. Пример 9.2 (циркулянтный граф $C_{n}(1,2)$). Следуя теореме 9.1 для циркулянтного графа с двумя скачками $1$ и $2$, приходим к необходимости решить уравнение $1+4-2T_{1}(w)-2T_{2}(w)=0$. Его корнями являются величины
$$
\begin{equation*}
w_{1}=\frac{1}{4}(-1+\sqrt{29}\,)\quad\text{и}\quad w_{2}=\frac{1}{4}(-1-\sqrt{29}\,).
\end{equation*}
\notag
$$
Отсюда заключаем, что
$$
\begin{equation*}
f_{G}(n)=|2T_{n}(w_{1})-2|\cdot |2T_{n}(w_{2})-2| \sim A^{n},\qquad n\to\infty,
\end{equation*}
\notag
$$
где $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$. Тогда
$$
\begin{equation*}
f_{G}(n)=(2T_{n}(w_{1})-2)(2T_{n}(w_{2})-2)(2T_{n}(w_{3})-2).
\end{equation*}
\notag
$$
В данном случае
$$
\begin{equation*}
f_{G}(n)\sim A_{1,3}^{n},\qquad n\to\infty,
\end{equation*}
\notag
$$
где $A_{1,3}\approx4.48461\dots$ – мера Малера полинома Лорана $5-z-z^{-1}-z^{3}-z^{-3}$. Можно показать, что $A_{1,3}$ будет корнем уравнения $1-x-2x^2-4x^3+x^4=0$. По теореме 9.3 имеем $f_{G}(n)=a(n)^2$ для подходящей целочисленной последовательности $a(n)$. Пример 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$. Отсюда следует, что
$$
\begin{equation*}
f_{G}(n)=\biggl(2T_{n}\biggl(\frac{3}{2}\biggr)-2\biggr) \biggl(2T_{n}\biggl(\frac{5}{2}\biggr)+2\biggr)\sim K^{n},
\end{equation*}
\notag
$$
где $K=(3+\sqrt{5}\,)(5+\sqrt{21}\,)/4\approx12.5438\dots$ . Из теоремы 9.4 заключаем, что $f_{G}(n)=5a(n)^2$ при четном $n$ и $f_{G}(n)=7a(n)^2$ при нечетном $n$. Здесь $a(n)$ – подходящая целочисленная последовательность.
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)$ вычисляется по формуле
$$
\begin{equation*}
f(n)=\zeta^{n}\prod_{p=1}^{s}|2T_n(w_p)-2|,
\end{equation*}
\notag
$$
где $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$ имеет следующую асимптотику:
$$
\begin{equation*}
f(n)\sim A^{n},\qquad n\to\infty,
\end{equation*}
\notag
$$
где $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)$. Рассмотрим графы
$$
\begin{equation*}
I(n,k,l)=H_{n}(G_{1},G_{2})\quad\text{и}\quad \operatorname{GP}(n,k)=I(n,k,1).
\end{equation*}
\notag
$$
Данный случай приводит к полиномам
$$
\begin{equation*}
\begin{aligned} \, P_{f}(z)&=(4-z^{k}-z^{-k})(4-z^{l}-z^{-l})-1, \\ Q_{f}(w)&=(4-2T_{k}(w))(4-2T_{l}(w))-1. \end{aligned}
\end{equation*}
\notag
$$
Арифметические и асимптотические свойства числа отмеченных остовных лесов в $I$-графах рассмотрены в [1]. Пример 10.2 (обобщенный $Y$-граф). Рассмотрим обобщенный $Y$-граф
$$
\begin{equation*}
Y_{n}(G_{1},G_{2},G_{3}), \quad\text{где}\quad G_{i}=C_{n}(s_{i,1},s_{i,2},\dots,s_{i,k_i}), \quad i=1,2,3.
\end{equation*}
\notag
$$
Тогда
$$
\begin{equation*}
Q_{f}(w)=4A_{1}(w)A_{2}(w)A_{3}(w)-A_{1}(w)A_{2}(w)-A_{1}(w)A_{3}(w)- A_{2}(w)A_{3}(w),
\end{equation*}
\notag
$$
где $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)$ имеем
$$
\begin{equation*}
Q_{f}(w)=208-336w+180w^2-32w^3
\end{equation*}
\notag
$$
и $\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 дает следующую асимптотику:
$$
\begin{equation*}
f(n) \sim A^{n},\quad n\to\infty, \quad\text{где}\quad A=\frac{1}{2}(7+4\sqrt{3}\,)(13+\sqrt{105}\,).
\end{equation*}
\notag
$$
Пример 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})$. Для данного графа имеем
$$
\begin{equation*}
\begin{aligned} \, Q_{f}(w)&=A_{1}(w)A_{2}(w)A_{3}(w)A_{4}(w) \\ &\quad\times \biggl(\biggl(4-\frac{1}{A_{1}(w)}-\frac{1}{A_{2}(w)}\biggr) \biggl(4-\frac{1}{A_{3}(w)}-\frac{1}{A_{4}(w)}\biggr)-1\biggr), \end{aligned}
\end{equation*}
\notag
$$
где $A_{i}(w)$ те же, что и выше. При $G_{1}=G_{2}=G_{3}=G_{4}=C_{n}(1)$ получим
$$
\begin{equation*}
Q_{f}(w)=16(-2+w)^{2}(-5+3w)(-9+5w)
\end{equation*}
\notag
$$
и $\zeta=15$. Тогда количество отмеченных остовных лесов в графе $H(n;1,1;1,1)$ определяется по формуле
$$
\begin{equation*}
f(n)=15^{n}\biggl(2T_{n}\biggl(\frac{5}{3}\biggr)-2\biggr) \biggl(2T_{n}\biggl(\frac{9}{5}\biggr)-2\biggr)(2T_{n}(2)-2)^2.
\end{equation*}
\notag
$$
Кроме того, для подходящей целочисленной последовательности $a(n)$ имеем $f(n)=f(1)a(n)^{2}$ в случае нечетных $n$ и $f(n)=7f(1)a(n)^2$ в случае четных $n$. Здесь $f(1)=128$ – количество отмеченных остовных лесов в базовом $H$-графе. Асимптотическое поведение описывается формулой
$$
\begin{equation*}
f(n) \sim A^{n},\quad n\to\infty,\quad\text{где}\quad A=9(7+4\sqrt{3}\,)(9+2\sqrt{14}\,).
\end{equation*}
\notag
$$
11. Группы якобиана циркулянтных графов Понятие группы якобиана графа, которую также называют группой Пикара, критической группой, долларовой или песочной группой, было независимо введено многими авторами [22], [6], [9], [4]. Это понятие возникает как дискретная версия якобиана в классической теории римановых поверхностей. Также оно допускает естественную интерпретацию в различных разделах физики, теории кодирования и финансовой математике. Группа якобиана является важным алгебраическим инвариантом конечного графа. В частности, ее порядок совпадает с числом остовных деревьев графа. Цель данного раздела – определить структуру якобиана для циркулянтных графов. Для простейших циркулянтных графов группа якобиана будет найдена в явном виде, в то время как в общем случае будет предложен удобный метод для ее вычисления. 11.1. Графы с четной степенью вершин Введем следующее определение. Пусть $P(z)$ – полином Лорана вида
$$
\begin{equation*}
P(z)=z^p+a_1z^{p+1}+\cdots+a_{s-1}z^{p+s-1}+z^{p+s},
\end{equation*}
\notag
$$
где $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*}
\mu(n)=\begin{cases} 4,&\text{если}\ n\equiv3\!\!\!\pmod6, \\ 2,&\text{если}\ n\equiv0\!\!\!\pmod6, \\ 1&\text{в остальных случаях}\ \end{cases}
\end{equation*}
\notag
$$
и
$$
\begin{equation*}
\eta(n)=\begin{cases} 2,&\text{если}\ n\equiv0\!\!\!\pmod6, \\ 1&\text{в остальных случаях}. \end{cases}
\end{equation*}
\notag
$$
Пусть также
$$
\begin{equation*}
2T_{n}\biggl(\frac{-1+\mathrm{i}}{2}\biggr)-2=s+\mathrm{i}\,t,\qquad U_{n-1}\biggl(\frac{-1+\mathrm{i}}{2}\biggr)=u+\mathrm{i}\,v.
\end{equation*}
\notag
$$
Заметим, что все числа $s$, $t$, $u$, $v$ – целые. Положим
$$
\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}$, где
$$
\begin{equation*}
d_1=\frac{\Delta_1}{\mu(n)}\,,\quad d_2=\frac{\eta(n)\Delta_2}{\Delta_1}\,,\quad d_3=\frac{\Delta_3}{\eta(n)\Delta_2}\,,\quad d_4=\frac{\Delta_4}{\Delta_3}\,,\quad d_5=\frac{\mu(n)\Delta_5}{\Delta_4}\,.
\end{equation*}
\notag
$$
Кроме того, число остовных деревьев в графе $C_n(1,3)$ задается формулой
$$
\begin{equation*}
\tau(n)=d_1d_2d_3d_4d_5=\Delta_5.
\end{equation*}
\notag
$$
11.2. Графы с нечетной степенью вершин Следующая теорема (в эквивалентной форме) приведена в работе [60]. Техника ее доказательства изложена в последующей работе [32]. Теорема 11.2. Пусть
$$
\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
$$
– циркулянтный граф с нечетной степенью вершин. Тогда его якобиан $\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)$). Положим
$$
\begin{equation*}
(l,m)=\operatorname{gcd}(l,m),\quad \{l,m\}=\operatorname{lcm}(l,m)
\end{equation*}
\notag
$$
и
$$
\begin{equation*}
H_m=T_m+U_{m-1},
\end{equation*}
\notag
$$
где $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]$ – целые числа. Пусть
$$
\begin{equation*}
P(z)=\sum_{j=1}^{k}(z^{s_j}+z^{-s_j}-2)\quad\textit{и}\quad l(z)=\sum_{j=1}^\ell(z^{\alpha_j}+z^{-\alpha_j}-2).
\end{equation*}
\notag
$$
Обозначим через $\mathcal{A}$ сопровождающую матрицу полинома Лорана
$$
\begin{equation*}
R_\beta(z)=\displaystyle\prod_{p=1}^{\beta}(P(z)+l(e^{2\pi {\rm i}p/\beta})).
\end{equation*}
\notag
$$
Тогда группа якобиана $\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$ с целыми коэффициентами такие, что
$$
\begin{equation*}
R_\beta(z)=p(z^n,z)(P(z)+l(z^n))+q(z^n,z)(z^{\beta\,n}-1).
\end{equation*}
\notag
$$
Заметим, что лапласиан $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}$ над циркулянтным графом
$$
\begin{equation*}
G=C_{n}(s_{1},s_{2},\dots,s_{k}),\qquad 1\leqslant s_{1}<s_{2}<\cdots<s_{k}<\frac{n}{2}.
\end{equation*}
\notag
$$
Тогда группа якобиана $\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$ – нечетное число. Определим полином Чебышёва четвертого рода как
$$
\begin{equation*}
W_m(z)=\frac{\sin((m+1/2)\theta)}{\sin(\theta/2)}\,,\quad\text{где}\ \ z=\cos\theta.
\end{equation*}
\notag
$$
Данный класс полиномов описывается рекуррентным образом:
$$
\begin{equation*}
W_0(z)=1,\quad W_1(z)=2z+1,\quad W_m(z)=2z W_{m-1}(z)-W_{m-2}(z).
\end{equation*}
\notag
$$
Положим $x=W_m(3/2)$ и $y=(W_m(-5/2)-W_m(3/2))/2$. Тогда
$$
\begin{equation*}
\operatorname{Jac}(\widehat{G})=\mathbb{Z}^2_{\operatorname{gcd}(x,y)} \oplus\mathbb{Z}_{(x^2+2x y)/\operatorname{gcd}(x,y)}\oplus \mathbb{Z}_{7(x^2+2x y)/\operatorname{gcd}(x,y)}.
\end{equation*}
\notag
$$
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}})$. Воспользуемся элементарным тождеством
$$
\begin{equation}
\frac{a^{2 m+1}-1}{a^m(a-1)}=a^m+a^{m-1}+\cdots+a^{-m+1}+a^{-m}.
\end{equation}
\tag{8}
$$
Перепишем правую часть равенства (8) в виде $p(a+a^{-1})$, где $p(z)$ – подходящий полином с целыми коэффициентами. Тогда имеет место равенство
$$
\begin{equation}
\mathcal{A}^{2 m+1}-1=\mathcal{A}^m (\mathcal{A}-I)p(\mathcal{A}+ \mathcal{A}^{-1}).
\end{equation}
\tag{9}
$$
Отметим следующую важную особенность сопровождающей матрицы $\mathcal{A}$:
$$
\begin{equation*}
\det(\mathcal{A})=\det(\mathcal{A}-I)=1.
\end{equation*}
\notag
$$
Это означает, что множители $\mathcal{A}^m$ и $\mathcal{A}-I$ не влияют на вычисление коядра матрицы в правой части равенства (9). Следовательно, коядро матрицы $\mathcal{A}^{2m+1}-1$ изоморфно коядру матрицы $p(\mathcal{A}+\mathcal{A}^{-1})$. Кроме того, справедлива следующая лемма. Лемма 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$ можно взять блочную матрицу
$$
\begin{equation*}
\begin{pmatrix} I & C\,J \\ J\,C & I\end{pmatrix},
\end{equation*}
\notag
$$
где $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$ основано на тождестве
$$
\begin{equation*}
\frac{a^{2m}-1}{a^2-1}=a^{m-1}(a^{m-1}+a^{m-3}+\cdots+a^{-m+3}+a^{-m+1})
\end{equation*}
\notag
$$
и замечании, что факторгруппа $\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.
|
|
|
Список литературы
|
|
|
1. |
N. V. Abrosimov, G. A. Baigonakova, L. A. Grunwald, I. A. Mednykh, “Counting rooted spanning forests in cobordism of two circulant graphs”, Сиб. электрон. матем. изв., 17 (2020), 814–823 |
2. |
N. V. Abrosimov, G. A. Baigonakova, I. A. Mednykh, “Counting spanning trees in cobordism of two circulant graphs”, Сиб. электрон. матем. изв., 15 (2018), 1145–1157 |
3. |
A. Ádám, “Research problem 2-10”, J. Combin. Theory, 2 (1967), 393 |
4. |
R. Bacher, P. de la Harpe, T. Nagnibeda, “The lattice of integral flows and the lattice of integral cuts on a finite graph”, Bull. Soc. Math. France, 125:2 (1997), 167–198 |
5. |
G. A. Baigonakova, A. D. Mednykh, “Elementary formulas for Kirchhoff index of Möbius ladder and prism graphs”, Сиб. электрон. матем. изв., 16 (2019), 1654–1661 |
6. |
M. Baker, S. Norine, “Harmonic morphisms and hyperelliptic graphs”, Int. Math. Res. Not. IMRN, 2009:15 (2009), 2914–2955 |
7. |
H. Bass, “Covering theory for graphs of groups”, J. Pure Appl. Algebra, 89:1-2 (1993), 3–47 |
8. |
N. Biggs, “Three remarkable graphs”, Canad. J. Math., 25:2 (1973), 397–411 |
9. |
N. L. Biggs, “Chip-firing and the critical group of a graph”, J. Algebraic Combin., 9:1 (1999), 25–45 |
10. |
F. T. Boesch, Z. R. Bogdanowicz, “The number of spanning tress in a prism”, Internat. J. Comput. Math., 21:3-4 (1987), 229–243 |
11. |
F. T. Boesch, H. Prodinger, “Spanning tree formulas and Chebyshev polynomials”, Graphs Combin., 2 (1986), 191–200 |
12. |
D. W. Boyd, “Mahler's measure and invariants of hyperbolic manifolds”, Number theory for the millennium (Urbana, IL, 2000), v. I, A K Peters, Natick, MA, 2002, 127–143 |
13. |
D. Calan, “A combinatorial derivation of the number of labeled forests”, J. Integer Seq., 6:4 (2003), 03.4.7, 9 pp. |
14. |
P. Chebotarev, “Spanning forests and the golden ratio”, Discrete Appl. Math., 156:5 (2008), 813–821 |
15. |
P. Chebotarev, R. Agaev, “Forest matrices around the Laplacian matrix”, Linear Algebra Appl., 356:1-3 (2002), 253–274 |
16. |
P. Chebotarev, E. Shamis, Matrix-forest theorems, 2006, 10 pp., arXiv: math/0602575 |
17. |
Pingge Chen, Yaoping Hou, Chingwah Woo, “On the critical group of the Möbius ladder graph”, Australas. J. Combin., 36 (2006), 133–142 |
18. |
Xiebin Chen, Qiuying Lin, Fuji Zhang, “The number of spanning trees in odd valent circulant graphs”, Discrete Math., 282:1-3 (2004), 69–79 |
19. |
Z. Cinkir, “Effective resistances and Kirchhoff index of ladder graphs”, J. Math. Chem., 54:4 (2016), 955–966 |
20. |
Z. Cinkir, Effective resistances and Kirchhoff index of prism graphs, 2017, 9 pp., arXiv: 1704.03429 |
21. |
M. Conder, R. Grande, “On embeddings of circulant graphs”, Electron. J. Combin., 22:2 (2015), P2.28, 27 pp. |
22. |
R. Cori, D. Rossin, “On the sandpile group of dual graphs”, European J. Combin., 21:4 (2000), 447–459 |
23. |
P. J. Davis, Circulant matrices, 2nd ed., AMS Chelsea Publishing, New York, NY, 1994 |
24. |
D. Dhar, P. Ruelle, S. Sen, D.-N. Verma, “Algebraic aspects of Abelian sandpile models”, J. Phys. A: Math. Gen., 28:4 (1995), 805–831 |
25. |
С. А. Евдокимов, И. Н. Пономаренко, “Распознавание и проверка изоморфизма циркулянтных графов за полиномиальное время”, Алгебра и анализ, 15:6 (2003), 1–34 ; англ. пер.: S. A. Evdokimov, I. N. Ponomarenko, “Circulant graphs: recognizing and isomorphism testing in polynomial time”, St. Petersburg Math. J., 15:6 (2004), 813–835 |
26. |
G. Everest, T. Ward, Heights of polynomials and entropy in algebraic dynamics, Universitext, Springer-Verlag London, Ltd., London, 2013, 212 pp. |
27. |
C. Godsil, G. Royle, Algebraic graph theory, Grad. Texts in Math., 207, Springer-Verlag, New York, 2001, xx+439 pp. |
28. |
G. Goel, D. Perkinson, “Critical groups of iterated cones”, Linear Algebra Appl., 567 (2019), 138–142 |
29. |
C. M. Gordon, “A short proof of a theorem of Plans on the homology of the branched cyclic coverings of a knot”, Bull. Amer. Math. Soc., 77 (1971), 85–87 |
30. |
J. L. Gross, T. W. Tucker, Topological graph theory, Wiley-Intersci. Ser. Discrete Math. Optim., John Wiley & Sons, Inc., New York, 1987, xvi+351 pp. |
31. |
L. A. Grunwald, Young Soo Kwon, I. A. Mednykh, “Counting rooted spanning forests for circulant foliation over a graph”, Tohoku Math. J. (2), 74:4 (2022), 535–548 |
32. |
L. A. Grunwald, I. A. Mednykh, “On the Jacobian group of a cone over a circulant graph”, Математические заметки СВФУ, 28:2 (2021), 88–101 |
33. |
L. A. Grunwald, I. A. Mednykh, “The number of rooted forests in circulant graphs”, Ars Math. Contemp., 22:4 (2022), 10, 12 pp. |
34. |
I. Gutman, B. Mohar, “The quasi-Wiener and the Kirchhoff indices coincide”, J. Chem. Inf. Comput. Sci., 36:5 (1996), 982–985 |
35. |
A. J. Guttmann, M. D. Rogers, “Spanning tree generating functions and Mahler measures”, J. Phys. A, 45:49 (2012), 494001, 24 pp. |
36. |
A. J. W. Hilton, “Spanning trees and Fibonacci and Lucas numbers”, Fibonacci Quart., 12 (1974), 259–262 |
37. |
J. D. Horton, I. Z. Bouwer, “Symmetric $Y$-graphs and $H$-graphs”, J. Combin. Theory Ser. B, 53:1 (1991), 114–129 |
38. |
Yaoping Hou, Chingwah Woo, Pingge Chen, “On the sandpile group of the square cycle $C_n^2$”, Linear Algebra Appl., 418:2-3 (2006), 457–467 |
39. |
Danrun Huang, “A cyclic six-term exact sequence for block matrices over a PID”, Linear Multilinear Algebra, 49:2 (2001), 91–114 |
40. |
B. Jacobson, A. Niedermaier, V. Reiner, “Critical groups for complete multipartite graphs and Cartesian products of complete graphs”, J. Graph Theory, 44:3 (2003), 231–250 |
41. |
J. L. V. W. Jensen, “Sur un nouvel et important théorème de la théorie des fonctions”, Acta Math., 22:1 (1899), 359–364 |
42. |
Yinglie Jin, Chunlin Lin, “Enumeration for spanning forests of complete bipartite graphs”, Ars Combin., 70 (2004), 135–138 |
43. |
M. Kagan, B. Mata, “A physics perspective on the resistance distance for graphs”, Math. Comput. Sci., 13:1-2 (2019), 105–115 |
44. |
A. K. Kelmans, V. M. Chelnokov, “A certain polynomial of a graph and graphs with an extremal number of trees”, J. Combin. Theory Ser. B, 16:3 (1974), 197–214 |
45. |
G. Kirchhoff, “Ueber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme geführt wird”, Ann. Phys. Chem., 72:12 (1847), 497–508 |
46. |
D. J. Klein, M. Randić, “Resistance distance”, J. Math. Chem., 12:1-4 (1993), 81–95 |
47. |
O. Knill, “Cauchy–Binet for pseudo-determinants”, Linear Algebra Appl., 459 (2014), 522–547 |
48. |
M. Kotani, T. Sunada, “Jacobian tori associated with a finite graph and its Abelian covering graphs”, Adv. in Appl. Math., 24:2 (2000), 89–110 |
49. |
Y. S. Kwon, A. D. Mednykh, I. A. Mednykh, “On Jacobian group and complexity of the generalized Petersen graph $GP(n,k)$ through Chebyshev polynomials”, Linear Algebra Appl., 529 (2017), 355–373 |
50. |
Y. S. Kwon, A. D. Mednykh, I. A. Mednykh, On complexity of cyclic coverings of graphs, 2018, 19 pp., arXiv: 1811.03801 |
51. |
Y. S. Kwon, A. D. Mednykh, I. A. Mednykh, “Complexity of the circulant foliation over a graph”, J. Algebraic Combin., 53:1 (2021), 115–129 |
52. |
D. H. Lehmer, “Factorization of certain cyclotomic functions”, Ann. of Math. (2), 34:3 (1933), 461–479 |
53. |
C. J. Liu, Yutze Chow, “Enumeration of forests in a graph”, Proc. Amer. Math. Soc., 83:3 (1981), 659–662 |
54. |
D. Lorenzini, “Smith normal form and Laplacians”, J. Combin. Theory Ser. B, 98:6 (2008), 1271–1300 |
55. |
J. Louis, “A formula for the number of spanning trees in circulant graphs with nonfixed generators and discrete tori”, Bull. Aust. Math. Soc., 92:3 (2015), 365–373 |
56. |
I. Lukovits, S. Nikolić, N. Trinajstić, “Resistance distance in regular graphs”, Int. J. Quantum Chem., 71:3 (1999), 217–225 |
57. |
Ye Luzhen, “On the Kirchhoff index of some toroidal lattices”, Linear Multilinear Algebra, 59:6 (2011), 645–650 |
58. |
K. Mahler, “On some inequalities for polynomials in several variables”, J. London Math. Soc., 37 (1962), 341–344 |
59. |
У. Масси, Дж. Столлингс, Алгебраическая топология. Введение, Мир, М., 1977, 344 с. ; пер. с англ.: W. S. Massey, Algebraic topology: an introduction, Harcourt, Brace & World, Inc., New York, 1967, xix+261 с. ; J. Stallings, Group theory and three-dimensional manifolds, Yale Math. Monogr., 4, Yale Univ. Press, New Haven, CT–London, 1971, v+65 pp. |
60. |
А. Д. Медных, И. А. Медных, “О строении группы якобиана циркулянтных графов”, Докл. РАН, 469:5 (2016), 539–543 ; англ. пер.: A. D. Mednykh, I. A. Mednykh, “On the structure of the Jacobian group for circulant graphs”, Dokl. Math., 94:1 (2016), 445–449 |
61. |
А. Д. Медных, И. А. Медных, “Об асимптотике и арифметических свойствах функции сложности циркулянтных графов”, Докл. РАН, 479:4 (2018), 363–367 ; англ. пер.: A. D. Mednykh, I. A. Mednykh, “Asymptotics and arithmetical properties of complexity for circulant graphs”, Dokl. Math., 97:2 (2018), 147–151 |
62. |
A. D. Mednykh, I. A. Mednykh, “The number of spanning trees in circulant graphs, its arithmetic properties and asymptotic”, Discrete Math., 342:6 (2019), 1772–1781 |
63. |
А. Д. Медных, И. А. Медных, “О строении критической группы циркулянтного графа с непостоянными скачками”, УМН, 75:1(451) (2020), 197–198 ; англ. пер.: A. D. Mednykh, I. A. Mednykh, “On the structure of the critical group of a circulant graph with non-constant jumps”, Russian Math. Surveys, 75:1 (2020), 190–192 |
64. |
А. Д. Медных, И. А. Медных, “Индекс Кирхгофа для циркулянтных графов и его асимптотика”, Докл. РАН. Матем., информ., проц. упр., 494 (2020), 43–47 ; англ. пер.: A. D. Mednykh, I. A. Mednykh, “Kirchhoff index for circulant graphs and its asymptotics”, Dokl. Math., 102:2 (2020), 392–395 |
65. |
A. D. Mednykh, I. A. Mednykh, “On rationality of generating function for the number of spanning trees in circulant graphs”, Algebra Colloq., 27:1 (2020), 87–94 |
66. |
А. Д. Медных, И. А. Медных, “О теореме Планса и периодичности якобианов циркулянтных графов”, Докл. РАН. Матем., информ., проц. упр., 498 (2021), 51–54 ; англ. пер.: A. D. Mednykh, I. A. Mednykh, “Plans' periodicity theorem for Jacobian of circulant graphs”, Dokl. Math., 103:3 (2021), 139–142 |
67. |
A. Mednykh, I. Mednykh, “Complexity of circulant graphs with non-fixed jumps, its arithmetic properties and asymptotics”, Ars Math. Contemp., 23:1 (2023), 8, 16 pp. |
68. |
I. A. Mednykh, “On Jacobian group and complexity of the $I$-graph $I(n,k,l)$ through Chebyshev polynomials”, Arc Math. Contemp., 15:2 (2018), 467–485 |
69. |
I. A. Mednykh, M. A. Zindinova, “On the structure of Picard group for Moebius ladder”, Сиб. электрон. матем. изв., 8 (2011), 54–61 |
70. |
B. Mohar, “The Laplacian spectrum of graphs”, Graph theory, combinatorics, and applications (Kalamazoo, MI, 1988), v. 2, Wiley-Intersci. Publ., John Wiley & Sons, Inc., New York, 1991, 871–898 |
71. |
M. Muzychuk, “A solution of the isomorphism problem for circulant graphs”, Proc. London Math. Soc. (3), 88:1 (2004), 1–41 |
72. |
N. Neumärker, The arithmetic structure of discrete dynamical systems on the torus, PhD thesis, Univ. Bielefeld, Bielefeld, 2012, 92 pp., pp. https://pub.uni-bielefeld.de/download/2508475/2508565/Diss_Neumaerker.pdf |
73. |
J. L. Palacios, “Closed-form formulas for Kirchhoff index”, Int. J. Quantum Chem., 81:2 (2001), 135–140 |
74. |
A. Plans, “Aportación al estudio de los grupos de homología de los recubrimientos cíclicos ramificados correspondientes a un nudo”, Rev. Acad. Ci. Madrid, 47 (1953), 161–193 |
75. |
В. В. Прасолов, Многочлены, 3-е изд., МЦНМО, М., 2003, 336 с.; англ. пер. 2-го изд.: V. V. Prasolov, Polynomials, Algorithms Comput. Math., 11, Springer-Verlag, Berlin, 2004, xiv+301 с. |
76. |
M. Sakuma, “Homology of Abelian coverings of links and spatial graphs”, Canad. J. Math., 47:1 (1995), 201–224 |
77. |
J. Sedláček, “On the number of spanning trees of finite graphs”, Časopis Pěst. Mat., 94:2 (1969), 217–221 |
78. |
J. Sedlácěk, “On the skeletons of a graph or digraph”, Combinatorial structures and their applications (Calgary, 1969), Gordon and Breach Sci. Publ., New York–London–Paris, 1970, 387–391 |
79. |
R. Shrock, F. Y. Wu, “Spanning trees on graphs and lattices in $d$ dimensions”, J. Phys. A, 33:21 (2000), 3881–3902 |
80. |
D. S. Silver, S. G. Williams, Spanning trees and Mahler measure, 2016, 12 pp., arXiv: 1602.02797 |
81. |
D. S. Silver, S. G. Williams, Graph complexity and Mahler measure, 2017, 16 pp., arXiv: 1701.06097 |
82. |
Ch. Smyth, “The Mahler measure of algebraic numbers: a survey”, Number theory and polynomials, London Math. Soc. Lecture Note Ser., 352, Cambridge Univ. Press, Cambridge, 2008, 322–349 |
83. |
A. Steimle, W. Staton, “The isomorphism classes of the generalized Petersen graphs”, Discrete Math., 309:1 (2009), 231–237 |
84. |
W. H. Stevens, On the homology of branched cyclic covers of knots, PhD thesis, Louisiana State Univ. and Agricultural & Mechanical College, 1996, 40 pp. |
85. |
Weigang Sun, Shuai Wang, Jingyuan Zhang, “Counting spanning trees in prism and anti-prism graphs”, J. Appl. Anal. Comput., 6:1 (2016), 65–75 |
86. |
L. Takács, “On the number of distinct forests”, SIAM J. Discrete Math., 3:4 (1990), 574–581 |
87. |
H. N. V. Templerley, M. E. Fisher, “Dimer problem in statistical mechanics – an exact result”, Philos. Mag. (8), 6:68 (1961), 1061–1063 |
88. |
L. Weinberg, “Number of trees in a graph”, Proc. IRE, 46:12 (1958), 1954–1955 |
89. |
H. Wiener, “Structural determination of paraffin boiling points”, J. Amer. Chem. Soc., 69:1 (1947), 17–20 |
90. |
F. Y. Wu, “Number of spanning trees on a lattice”, J. Phys. A, 10:6 (1977), L113–L115 |
91. |
Wenjun Xiao, I. Gutman, “Resistance distance and Laplacian spectrum”, Theor. Chem. Acc., 110 (2003), 284–289 |
92. |
Heping Zhang, Yujun Yang, “Resistance distance and Kirchhoff index in circulant graphs”, Int. J. Quantum Chem., 107:2 (2007), 330–339 |
93. |
Yuanping Zhang, Xuerong Yong, M. J. Golin, “The number of spanning trees in circulant graphs”, Discrete Math., 223:1-3 (2000), 337–350 |
94. |
Yuanping Zhang, Xuerong Yong, M. J. Golin, “Chebyshev polynomials and spanning tree formulas for circulant and related graphs”, Discrete Math., 298:1-3 (2005), 334–364 |
95. |
H.-Y. Zhu, D. J. Klein, I. Lukovits, “Extensions of the Wiener number”, J. Chem. Inf. Comput. Sci., 36:3 (1996), 420–428 |
Образец цитирования:
А. Д. Медных, И. А. Медных, “Циклические накрытия графов. Перечисление отмеченных остовных лесов и деревьев, индекс Кирхгофа и якобианы”, УМН, 78:3(471) (2023), 115–164; Russian Math. Surveys, 78:3 (2023), 501–548
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/rm10098https://doi.org/10.4213/rm10098 https://www.mathnet.ru/rus/rm/v78/i3/p115
|
Статистика просмотров: |
Страница аннотации: | 285 | PDF русской версии: | 30 | PDF английской версии: | 50 | HTML русской версии: | 136 | HTML английской версии: | 93 | Список литературы: | 39 | Первая страница: | 17 |
|