| Успехи математических наук |
|
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье) Циклические накрытия графов. Перечисление отмеченных остовных лесов и деревьев, индекс Кирхгофа и якобианы А. Д. Медныхab, И. А. Медныхab a Институт математики им. С. Л. Соболева Сибирского отделения Российской академии наук b Новосибирский государственный университет
Англоязычная версия:
Russian Mathematical Surveys, 2023, Volume 78, Issue 3, Pages DOI: https://doi.org/10.4213/rm10098e 
Реферативные базы данных:
     1. ВведениеЦель настоящего обзора – изучение инвариантов циклических накрытий графов. При этом накрываемый граф предполагается фиксированным, а циклическая группа накрытия имеет сколь угодно большой порядок. Классическим примером таких накрытий являются циркулянтные графы. Они накрывают одновершинный граф с заданным числом петель. Более сложными представителями семейства циклических накрытий являются I-, Y-, H-графы, обобщенные графы Петерсена, сэндвич-графы, дискретные торы и многие другие. В обзоре приводятся аналитические формулы, позволяющие вычислять число отмеченных остовных лесов и деревьев в циклических накрытиях, найдена их асимптотика и изучены арифметические свойства этих чисел. Кроме того, для циркулянтных графов указаны точные формулы для вычисления индекса Кирхгофа и установлено, что, с точностью до экспоненциально малого остаточного члена, они задаются полиномами третьей степени. Все указанные инварианты являются спектральными – их значения определяются спектром матрицы Лапласа. Особое место отводится якобианам графов, которые, с нашей точки зрения, являются дискретными версиями якобианов римановых поверхностей. Якобиан графа можно определить как максимальную абелеву группу, порожденную потоками на графе, удовлетворяющими первому и второму законам Кирхгофа. По классической теореме Кирхгофа порядок этой группы совпадает с числом остовных деревьев в графе. Указанная группа, которую также называют песочной группой, группой Пикара, критической группой, долларовой группой или группой компонент, была независимо введена многими авторами. Важной особенностью якобиана графа является его неспектральный характер. Существуют графы с одинаковыми спектрами, но разными якобианами. В то же время существуют графы с одинаковыми якобианами, но разными спектрами. В обзоре приводятся структурные формулы для вычисления якобианов циркулянтных графов и их простейших аналогов. Основная техника вычисления всех указанных выше инвариантов базируется на использовании полиномов Чебышёва и их свойств. 2. Основные определенияДля удобства читателя в текущем разделе мы определим циклические накрытия графов и опишем их основные инварианты. Основное внимание будет уделено спектральным инвариантам графов, таким как число остовных деревьев, число отмеченных остовных лесов и индекс Кирхгофа. Кроме того, будут приведены структурные теоремы для вычисления якобиана графа, который, вообще говоря, не является спектральным инвариантом. 2.1. Базовое понятие графа. Остовные леса и деревьяВ рамках данного обзора графом G будем называть неориентированный конечный мультиграф с петлями. Для удобства будем считать, что каждое ребро, включая петли, ориентированo двумя возможными способами. Обозначим через V(G) и E(G) множество его вершин и множество его ребер соответственно. Деревом называется связный граф, не содержащий циклов. Несвязное объединение деревьев называется лесом. Отмеченным деревом назовем дерево с одной выделенной вершиной (корнем). Лес, состоящий из отмеченных деревьев, называется отмеченным лесом. Остовное дерево в связном графе G – это подграф G, который содержит все вершины графа G и является деревом. Oстовный лес в графе G – это подграф G, который содержит все вершины графа G и является лесом. 2.2. Матрица Лапласа для графа и его спектральные свойстваРассмотрим конечный граф G, допускающий кратные ребра, но не имеющий петель. Матрица A=A(G)=(au,v)u,v∈V(G), где au,v – число ребер между вершинами u и v, называется матрицей смежности графа G. Обозначим через d(v) степень вершины v∈V(G) и рассмотрим диагональную матрицу D=D(G) с элементами dv,v=d(v). Матрица L=L(G)=D(G)−A(G) называется матрицей Лапласа или лапласианом графа G. Отметим, что матрица Лапласа всегда вырождена и неотрицательно определена. Количество нулевых собственных значений этой матрицы равно числу компонент связности графа. В частности, матрица Лапласа связного графа имеет ровно одно нулевое собственное значение, а все остальные ее собственные значения – положительны [70]. Для более общих рассуждений нам потребуется расширить понятие лапласиана графа. Пусть X={xv,v∈V(G)} – набор независимых переменных, а D(X) – диагональная матрица, образованная элементами xv, v∈V(G). Определим обобщенный лапласиан графа G как L(G,X)=D(X)−A(G). 2.3. Теорема Кирхгофа о числе остовных деревьевОдним из основных инвариантов заданного графа является его сложность, определяемая как число его остовных деревьев. Если граф не связен, то его сложность равна нулю. Для связного графа сложность выражается по классической теореме Кирхгофа [45]. Она равна произведению всех ненулевых собственных значений матрицы Лапласа, поделенному на число вершин графа. Эту величину можно найти и как определитель произвольного главного минора матрицы Лапласа. Со времен Кирхгофа было опубликовано множество работ, посвященных изучению сложности различных семейств графов (см., например, [88], [77], [78], [36], [85], [11], [10]). 2.4. Теорема Кельманса–Челнокова и число отмеченных остовных лесовНаряду с подсчетом остовных деревьев также представляет интерес задача о числе отмеченных остовных лесов в заданном графе. Рассмотрим граф G на n вершинах. Пусть – характеристический полином его матрицы Лапласа L(G). Представим его в виде Согласно классическому результату [44] величина |ck| совпадает с числом отмеченных остовных лесов в графе G, состоящих из k деревьев. В силу неотрицательности собственных значений матрицы Лапласа L(G) последовательность коэффициентов c1,c2,…,cn−1,cn, где cn=1, знакопеременна. Поэтому справедлива следующая формула для подсчета числа отмеченных остовных лесов в графе G: Этот результат был независимо получен авторами работ [16], [47], [32] и др.В то же время об аналитических формулах для числа остовных лесов известно очень немного. В частности, П. Чеботарёв [14] перечислил отмеченные остовные леса в путевых и циклических графах, а О. Книл [47] доказал, что число отмеченных остовных лесов в полном графе Kn на n вершинах равно (n+1)n−1. Отмеченные остовные леса в полных двудольных графах были перечислены в [42]. Явные формулы для числа отмеченных остовных лесов для циклических, звездчатых и некоторых других графах даны в [47]. Что касается выражения для количества неотмеченных лесов, оно обычно имеет гораздо более сложную структуру [13], [53], [86]. 2.5. Индекс КирхгофаПусть G – связный конечный граф на n вершинах. Обозначим через L(G) матрицу Лапласа графа G. Известно [70], что если граф связен, то все собственные значения L(G), за исключением одного, равного нулю, положительны. Иными словами, спектр матрицы Лапласа графа G имеет вид 0=\lambda_{0}<\lambda_{1}\leqslant\cdots\leqslant\lambda_{n-1}. Первоначально индекс Кирхгофа графа G был определен Д. Клейном и М. Рандичем [46] как суммарное резистивное расстояние между его вершинами. Напомним соответствующее определение. Пронумеруем вершины графа G числами 1,2,\dots,n. Тогда резистивное расстояние между вершинами i и j, обозначаемое r_{i,j}=r_{i,j}(G), определяется как эффективное сопротивление между ними, если мы наделим каждое ребро G единичным сопротивлением. Следуя [46], определим индекс Кирхгофа графа G как величину
\begin{equation*}
\operatorname{Kf}(G)=\sum_{1\leqslant i<j\leqslant n}r_{i,j}.
\end{equation*}
\notag
Такое определение было мотивировано известным индексом Винера [89], определяемым как где d_{i,j} обозначает расстояние между вершинами i и j. Клейн и Рандич [46] показали, что \operatorname{Kf}(G)\leqslant W(G), где равенство достигается тогда и только тогда, когда граф G является деревом. Интересная связь между индексом Кирхгофа и спектром матрицы Лапласа была независимо найдена в работах [34] и [95]. Справедлива формула
\begin{equation}
\operatorname{Kf}(G)=n\sum_{j=1}^{n-1}\frac{1}{\lambda_j}\,.
\end{equation}
\tag{2}
Индексы Кирхгофа для различных семейств графов были изучены в работах [56], [73], [92], [91], [57], [19], [43], [5]. 2.6. Мера МалераВ последние десятилетия исследования асимптотического поведения сложности графов проводились с точки зрения изучения меры Малера [35], [80], [81]. Общие свойства меры Малера изложены в обзоре [82] и монографии [26]. Интересно отметить, что мера Малера тесно связана с ростом групп, значениями гипергеометрических функций и объемами гиперболических многообразий [12]. Приведем основные определения. Рассмотрим полином
\begin{equation*}
P(z)=a_{0}z^{s}+\cdots+a_{s-1}z+a_{s}= a_{0}\prod_{i=1}^{s}(z-\alpha_i),\qquad a_{0}\ne0,
\end{equation*}
\notag
с комплексными коэффициентами. Следуя [58], определим его меру Малера формулой
\begin{equation}
M(P)=\exp\biggl(\int_{0}^{1}\log|P(e^{2\pi\mathtt{i}t})|\,dt\biggr)
\end{equation}
\tag{3}
– среднее значение модуля |P(z)| по единичной окружности |z|=1. Отметим, что величина M(P) появилась ранее в работе Д. Лемера [52] в несколько иной форме Эквивалентность этих определений следует из формулы Йенсена [41]
\begin{equation*}
\int_{0}^{1}\log|e^{2\pi\mathtt{i}t}-\alpha|\,dt=\log_{+}|\alpha|,
\end{equation*}
\notag
где \log_{+}x обозначает \max(0,\log x). Иногда более удобной для исследований является малая мера Малера, определяемая как
\begin{equation*}
m(P):=\log M(P)=\int_{0}^{1}\log|P(e^{2\pi\mathtt{i}t})|\,dt.
\end{equation*}
\notag
Определение меры Малера может быть естественным образом расширенно на класс полиномов Лорана
\begin{equation*}
R(z)=a_{s}z^{p}+a_{s-1}z^{p+1}+\cdots+a_{1}z^{p+s-1}+a_{0}z^{p+s}= a_{0}z^{p}\prod_{i=1}^{s}(z-\alpha_i),
\end{equation*}
\notag
где a_{0},a_{s}\ne0 и p – произвольное целое число. 2.7. ЯкобианыРассмотренные выше инварианты графа (сложность, число отмеченных лесов, индекс Кирхгофа) являются спектральными инвариантами. Иначе говоря, они зависят от собственных значений матрицы Лапласа. Однако существуют инварианты, не зависящие от спектра матрицы Лапласа. Характерным примером такого инварианта является якобиан (группа якобиана) графа. Эта группа также известна как группа Пикара, критическая группа, долларовая группа (dollar group) или группа песочной кучи (sandpile group). Данное понятие было независимо введено многими авторами в последние десятилетия [24], [22], [6], [9], [4], [48]. Раньше всего оно появилось в статистической физике при исследовании модели песочной кучи [24]. В дальнейшем оно также было открыто как эффективный инструмент нахождения стабильного финансового положения в банковской системе [9]. Это понятие возникает и как дискретная версия якобиана из классической теории римановых поверхностей [6]. Теоретико-числовой подход к этому понятию реализован в работе [4]. Некоторые аспекты этой теории с точки зрения математической кристаллографии даются в [48]. Следуя [54], дадим определение якобиана \operatorname{Jac}(G) графа G. Рассмотрим лапласиан L(G) как гомоморфизм \mathbb{Z}^{|V|}\to\mathbb{Z}^{|V|}, где |V|=|V(G)| – число вершин в графе G. Его коядро
\begin{equation*}
\operatorname{coker}(L(G))=\mathbb{Z}^{|V|}/\operatorname{im}(L(G))
\end{equation*}
\notag
– некоторая абелева группа. Пусть
\begin{equation*}
\operatorname{coker}(L(G))\cong\mathbb{Z}_{d_{1}}\oplus\mathbb{Z}_{d_{2}} \oplus\cdots\oplus\mathbb{Z}_{d_{|V|}}
\end{equation*}
\notag
– ее нормальная форма Смита, однозначно определенная условиями d_i\mid d_{i+1}, 1\leqslant i\leqslant|V|-1. Если граф G связен, то группы {\mathbb Z}_{d_{1}},{\mathbb Z}_{d_{2}},\dots,{\mathbb Z}_{d_{|V|-1}} конечны, а \mathbb{Z}_{d_{|V|}}=\mathbb{Z}. Определим группу якобиана (или просто якобиан) графа G как подгруппу кручения коядра \operatorname{coker}(L(G)). Другими словами,
\begin{equation*}
\operatorname{Jac}(G)\cong\mathbb{Z}_{d_{1}}\oplus\mathbb{Z}_{d_{2}} \oplus\cdots\oplus\mathbb{Z}_{d_{|V|-1}}.
\end{equation*}
\notag
Группа якобиана – важный алгебраический инвариант конечного графа. В частности, ее порядок совпадает с числом остовных деревьев в графе. В то же время структура якобиана известна только в конкретных случаях [40], [22], [9], [54]. Структура якобиана для циркулянтных графов, I-графов и обобщенных графов Петерсена была изучена в работах [49], [60], [68]. Напомним, что класс вышеупомянутых графов достаточно широк и включает в себя циклические графы, полные графы, лестницу Мёбиуса, антипризму и другие графы. Для простейших бесконечных семейств графов группа якобина была описана явно, а в общем случае мы представляем более эффективный метод ее нахождения. Заметим, что число остовных деревьев для графов, а также структуру якобиана во многих случаях можно выразить в терминах полиномов Чебышёва. Есть очень важное наблюдение о структуре группы якобиана. Порядок якобиана как абелевой группы совпадает со сложностью графа. Иначе говоря, порядок якобиана – спектральная характеристика графа. В то же время существуют графы, которые имеют одинаковый спектр лапласиана, но неизоморфные якобианы [4]. 3. Циклические накрытия графов3.1. Общее определение циклического накрытия графаПусть даны два графа G=(V(G),E(G)) и H=(V(H),E(H)). Сюръективное отображение f\colon V(G)\to V(H) называется накрывающим отображением из G в H (или просто накрытием), если для каждого v\in V(G) сужение f на окрестность вершины v является биекцией в окрестность вершины f(v) в H. Напомним, что окрестностью вершины v графа G называется подграф, индуцированный вершиной v и всеми ее смежными вершинами в графе G (см. [27; п. 6.8]). Группа преобразований наложения (covering group) накрытия f состоит из всех автоморфизмов g графа G, сохраняющих проекцию, т. е. таких, что f\circ g=f. Накрытие называется циклическим, если группа преобразований наложения – циклическая и ее порядок совпадает с кратностью накрытия. Существует несколько подходов к описанию циклических накрытий графов: топологический – основанный на теории накрывающих пространств [59], геометрический – основанный на теории униформизации [7], и алгебраический – в его основе лежит теория напряжения графов (voltage assignment) [30]. В случае, когда граф G обладает циклической группой автоморфизмов \mathbb{Z}_n, действующей без неподвижных точек на множестве вершин и множестве ориентированных ребер графа, циклическое накрытие возникает как естественная проекция G\to G/\mathbb{Z}_n. 3.2. Циркулянтные графы и их спектрыПростейшими представителями циклических накрытий графов являются циркулянтные графы. Они представляют собой циклические накрытия над одновершинным графом с заданным числом петель. Также их можно определить как графы Кэли циклических групп [21]. Нам будет удобно пользоваться следующим эквивалентным определением. Пусть n>1 – целое положительное число. Рассмотрим конечный набор целых чисел s_1,s_2,\dots,s_k таких, что 1\leqslant s_1<s_2<\cdots<s_k\leqslant n/2. Определим циркулянтный граф G=C_{n}(s_1,s_2,\dots,s_k) как граф на n вершинах 0,1,2,\dots,{n-1}, в котором вершина i, 0\leqslant i\leqslant n-1, смежна с вершинами i\pm s_1,i\pm s_2,\dots,i\pm s_k (\bmod \ n). Величины s_1,s_2,\dots,s_k называются скачками графа G. В случае s_k<n/2 все вершины графа имеют степень 2k. Если же n четно и s_k=n/2, то все вершины графа имеют степень 2k- 1. Хорошо известно, что граф C_n(s_1,s_2,\dots,s_k) связен тогда и только тогда, когда \operatorname{gcd}(s_1,s_2,\dots,s_k,n)= 1. В общем случае число связных компонент графа C_n(s_1,s_2,\dots,s_k) равно d=\operatorname{gcd}(s_1,s_2,\dots,s_k,n). При этом вершины 0,1,\dots,d-1 лежат в разных компонентах связности и каждая компонента связности изоморфна графу C_{n/d}(s_1/d,s_2/d,\dots,s_k/d). Если d>1, то граф G не связен. Он не имеет остовных деревьев, но имеет остовные леса. В дальнейшем, если не оговорено обратное, все графы предполагаются связными. Два циркулянтных графа C_{n}(s_1,s_2,\dots,s_k) и C_{n}(\tilde{s}_1,\tilde{s}_2,\dots,\tilde{s}_k) называются сопряженными, если существует взаимно простое с n целое число r такое, что наборы чисел \{\tilde{s}_1,\tilde{s}_2,\dots,\tilde{s}_k\} и \{rs_1,rs_2,\dots,rs_k\} совпадают как подмножества циклической группы \mathbb{Z}_n. В данном случае умножение вершин на r (\bmod \ n) задает изоморфизм графов. В 1967 г. А. Адам предположил, что два циркулянтных графа изоморфны в том и только том случае, когда они сопряжены [3]. Целью этой гипотезы была классификация циркулянтных графов с точностью до изоморфизма. Однако оказалось, что гипотеза Адама не верна. В качестве контрпримера можно указать два графа C_{16}(1,2,7) и C_{16}(2,3,5). Они не сопряжены, но изоморфны [21]. Полное решение проблемы изоморфизма для циркулянтных графов дал М. Музычук [71]. С. А. Евдокимов и И. Н. Пономаренко [25] показали, что циркулянтные графы распознаются за полиномиальное время в множестве всех графов. Циркулянтной матрицей будем называть матрицу следующей структуры:
\begin{equation*}
\begin{pmatrix} a_0 & a_1 & a_2 & \dots & a_{n-1} \\ a_{n-1} & a_0 & a_1 & \dots & a_{n-2} \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ a_1 & a_2 & a_3 & \dots & a_0 \\ \end{pmatrix}.
\end{equation*}
\notag
Матрицу такого типа будем обозначать через \operatorname{circ}(a_0,a_1,\dots,a_{n-1}). Несложно заметить, что матрица смежности и матрица Лапласа циркулянтного графа циркулянтны. Верно и обратное: если матрица Лапласа некоторого графа циркулянтна (при подходящей нумерации вершин), то сам граф также циркулянтен. Напомним [23], что собственные значения матрицы C=\operatorname{circ}(a_0,a_1,\dots,a_{n-1}) задаются простыми формулами где p(z)=a_0+a_1 z+\cdots+a_{n-1}z^{n-1} и \varepsilon_n – первообразный корень степени n из единицы. Кроме того, рассмотренная циркулянтная матрица представима в виде где T=\operatorname{circ}(0,1,0,\dots,0) – матричное представление оператора циклического сдвига
\begin{equation*}
(x_0,x_1,\dots,x_{n-2},x_{n-1})\to(x_1,x_2,\dots,x_{n-1},x_0).
\end{equation*}
\notag
Это дает ключ к описанию лапласиана и его спектра для произвольного циркулянтного графа. А именно, вместе с каждым циркулянтным графом G=C_{n}(s_1,s_2,\dots,s_k) рассмотрим сопровождающий полином Лорана Тогда лапласиан графа G представляется в виде L(G)=P(T), а его спектр задается числами \lambda_j=P(\varepsilon^j_n), j=0,1,\dots,n-1.3.3. Циркулянтные расслоения графовПусть H – связный конечный граф с вершинами v_1,v_2,\dots,v_m, возможно с кратными ребрами, но без петель. Обозначим через a_{i,j} количество ребер между вершинами v_i и v_j. Так как H не имеет петель, то a_{i,i}=0. Для построения циркулянтного расслоения H_n=H_n(G_1,G_2,\dots,G_m) каждой вершине v_i припишем циркулянтный граф G_i=C_n(s_{i,1},s_{i,2},\dots,s_{i,k_i}). В случае, когда G_i=C_{n}(\varnothing) – пустой граф на n вершинах, полагаем k_{i}=1 и s_{i,1}=0. Циркулянтное расслоение над H со слоями G_1,G_2,\dots,G_m – это граф с множеством вершин При фиксированном k вершины (k,v_i) и (k,v_j) соединены a_{i,j} ребрами, а при фиксированном i вершины (k,v_i), k=1,2,\dots,n, образуют циркулянтный граф C_n(s_{i,1},s_{i,2},\dots,s_{i,k_i}), в котором вершина (k,v_i) смежна с вершинами
\begin{equation*}
(k\pm s_{i,1},v_i), \ (k\pm s_{i,2},v_i),\ \dots, \ (k\pm s_{i,k_i},v_i) \pmod{n}.
\end{equation*}
\notag
Далее по тексту будем называть H базовым графом или базой циркулянтного расслоения H_{n}. Важным аспектом такого определения является наличие слоев, образованных пустыми циркулянтными графами C_{n}(\varnothing), т. е. графами, состоящими из n изолированных вершин. Это значительно расширяет класс исследуемых объектов и, в частности, позволяет включить в него Y- и H-графы, а также их обобщения. Отметим некоторые свойства циркулянтных расслоений. Существует проекция \varphi\colon H_n\to H, переводящая вершины (k,v_i), k=1,\dots,n, и ребра между ними в вершины v_i, а ребра между вершинами (k,v_i) и (k,v_j), i\ne j, взаимно однозначно в ребра между вершинами v_i и v_j. При этом для каждой вершины v_i графа H имеем \varphi^{-1}(v_i)=G_i, i=1,2,\dots,m. Это отображение, удобное с топологической и комбинаторной точек зрения, вообще говоря, не является накрытием графов. Для построения накрытия рассмотрим действие циклической группы \mathbb{Z}_n на графе H_n, определенное правилом (k,v_{i})\to(k+1,v_{i}), k \!\pmod{n}. Тогда группа \mathbb{Z}_n действует без неподвижных точек на множестве вершин и ориентированных ребер графа, а факторграф H_{n}/\mathbb{Z}_{n} представляет собой оснащенный граф \widehat{H}, полученный из графа H присоединением k_i петель к каждой i-й вершине графа H. Таким образом, H_n является n-листным циклическим накрытием над оснащенным графом \widehat{H}. 3.4. Семейства циркулянтных расслоений: I-, Y-, H-графы и дискретные торыВ данном пункте приводится описание нескольких семейств циркулянтных расслоений, представляющих циклические накрытия над простейшими графами. Вначале мы рассмотрим сэндвич-граф \operatorname{SW}_n=H_n(G_1,G_2,\dots,G_m), составленный из циркулянтных графов G_i=C_n(s_{i,1},s_{i,2},\dots,s_{i,k_i}), i=1,2,\dots,m. Чтобы построить \operatorname{SW}_n, в качестве базового графа H выберем путевой граф (path graph) на m вершинах v_1,v_2,\dots,v_m с концами v_1 и v_m. Важным частным случаем такой конструкции является I-граф I(n,k,l), который возникает при m=2 и имеет два циклических слоя G_1=C_n(k) и G_2=C_n(l). Обобщенный граф Петерсена \operatorname{GP}(n,k) – это также I-граф с параметрами n,k и l=1 [83]. Сэндвич H_n(G_1,G_2) двух произвольных циркулянтных графов G_1 и G_2 рассматривался в работе [2]. Следующим примером может служить семейство обобщенных Y-графов Y_n=Y_n(G_1,G_2,G_3). Чтобы его построить, в качестве базы H рассмотрим Y-образный граф на четырех вершинах v_1, v_2, v_3, v_4 с тремя ребрами v_1v_4, v_2v_4, v_3v_4. Одновалентным вершинам графа H припишем циркулянтные графы G_1, G_2, G_3, а его центральной вершине – пустой циркулянтный граф G_4=C_n(\varnothing). Тогда, по определению циркулянтных расслоений, мы полагаем Y_n=H_n(G_1,G_2,G_3,G_4). В частности, при G_1=C_n(k), G_2=C_n(l) и G_3=C_n(m) возникает 3-регулярный Y-граф Y(n;k,l,m), определенный ранее в [8], [37]. Еще один пример – обобщенный H-граф H_n(G_1,G_2,G_3,G_4,G_5,G_6), где G_1, G_2, G_3 и G_4 – произвольные циркулянтные графы, а G_5=G_6=C_n(\varnothing) – пустые графы на n вершинах. В этом случае базовым графом служит граф H с вершинами v_1, v_2, v_3, v_4, v_5, v_6 и ребрами v_1v_5, v_5v_3, v_2v_6, v_6v_4, v_5v_6. В частном случае, когда G_1=C_n(i), G_2=C_n(j), G_3=C_n(k), G_4=C_n(l), имеем 3-регулярный граф H(n;i,j,k,l), исследованный в работе [37]. Для простоты мы будем использовать обозначение H_n(G_1,G_2,G_3,G_4), опуская символику для пустых графов. Дискретный тор – декартово произведение циклических графов C_n и C_m. Его можно рассматривать также как циркулянтное расслоение
\begin{equation*}
T_{n,m}=H_{n}(\,\underbrace{C_{n}(1),\dots,C_{n}(1)}_{m \text{ раз }}\,)
\end{equation*}
\notag
с базой H=C_{m}(1) и m одинаковыми слоями C_{n}(1),\dots,C_{n}(1). 3.5. Циклическое накрытие общего видаПусть H – конечный связный граф с вершинами v_1,v_2,\dots,v_r (возможно, с петлями и кратными ребрами). Для описания общей конструкции n-листного циклического накрытия графа H рассмотрим циклическую группу \Gamma=\langle\mathbb{Z}_n,+\rangle, состоящую из вычетов по модулю n. Для удобства будем считать, что все ребра H, включая петли, ориентированы двумя возможными способами. Для любого ориентированного ребра e графа H противоположно ориентированное ребро обозначим через \bar{e}. Используя метод напряжений (voltage assignment), разработанный в [30], припишем каждому ориентированному ребру e графа H напряжение \alpha(e), а именно некоторый элемент группы \Gamma. Следуем правилу, согласно которому сумма напряжений, приписанных двум противоположно ориентированным ребрам, равна нулю, т. е. \alpha(e)+\alpha(\bar{e})=0. Для любых i,j=1,\dots,r и любых k=1,\dots,a_{i,j} обозначим напряжение k-го ориентированного ребра от v_i до v_j через \alpha_k(i,j). Для различных i и j будем считать, что \alpha_k(j,i)=-\alpha_k(i,j). Поскольку каждая петля имеет две противоположные ориентации, можно взять напряжение \alpha_k(i,i) для одной из них (выбранной произвольно) и -\alpha_k(i,i) для другой. Рассмотрим n-листное циклическое накрытие H_n=H_{n}(\alpha) графа H, полученное при помощи задания напряжений \alpha=\{\alpha_k(i,j), i,j=1,\dots,r, k=1,\dots,a_{i,j}\}. Согласно общей теории [30] граф H_{n} имеет множество вершин u_{i,s}, i=\!1,2,\dots,r, s\kern-1pt=\!1,2,\dots,n, и множество ребeр v_{i,s}v_{j,s+\alpha_k(i,j)}, где i,j\kern-1pt=\kern-1pt 1,2,\dots,r, k=\!1,2,\dots,a_{i,j}, а вторые индексы берутся по модулю n. Отметим, что таким образом можно получить все циклические n-кратные накрытия графа H. Эта конструкция охватывает циркулянтные графы, графы Хаара, циркулянтные расслоения и многие другие семейства графов. 4. Циркулянтные графы с четным числом скачков4.1. Теорема о числе остовных деревьевВ этом пункте будут даны аналитические формулы для числа остовных деревьев в циркулянтных графах C_{n}(s_1,s_2,\dots,s_k) с четной степенью вершин. Приведенные ниже результаты принадлежат авторам настоящей статьи и опубликованы в работах [61] и [62]. Следует отметить, что близкие по духу результаты были получены ранее в работах [93], [18], [94]. Предложенный ниже подход представляется более простым и удобным. Он позволяет получить формулы для функции сложности в замкнутом виде и детально исследовать ее арифметические свойства. Кроме того, явный вид полученной формулы позволяет найти ее асимптотику через геометрические параметры графа и меру Малера его сопровождающего полинома. В случае, когда граф имеет четную степень вершин, справедлива следующая теорема [62; теорема 1, следствие 1]. Теорема 4.1. Число \tau(n) остовных деревьев циркулянтного графа
\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
дается формулой при этом q=s_1^2+s_2^2+\cdots+s_k^2 и w_p, p=1,2,\dots,s_k-1, – отличные от единицы корни алгебраического уравнения где Q(w)=\displaystyle\sum_{j=1}^k(T_{s_j}(w)-1), а T_k(w) – полином Чебышёва первого рода. 4.2. Асимптотика числа остовных деревьевРассмотрим бесконечное семейство графов G_n, n\in \mathbb{N}, и обозначим через \tau(n)=\tau(G_n) число остовных деревьев в графе \tau(G_n). Во многих случаях важно знать асимптотическое поведение функции \tau(n). Обозначим через v(G_n) число вершин графа G_n. Величина (если она существует) называется термодинамическим пределом (а также древесной энтропией или балком) семейства G_n. Изучению этой величины для различных семейств графов посвящено значительное количество работ по статистической физике (см., например, [87], [90], [79], [35], [55]).В этом пункте будут приведены асимптотические формулы для числа остовных деревьев циркулянтных графов, полученные в [61] и [62]. Интересно сопоставить эти результаты с результатами работ [93], [18], [94] и [55], где аналогичные асимптотики получены другими методами. Имеет место следующий результат [62; теорема 2]. Теорема 4.2. Число остовных деревьев циркулянтного графа
\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
имеет следующую асимптотику: где 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). Тогда – рациональная функция с целыми коэффициентами. Кроме того, F(z)=F(1/z).Заметим, что радиус сходимости ряда F(z) равен R=1/A, где A – мера Малера сопровождающего полинома Лорана графа C_{n}(s_1,s_2,\dots,s_k). Это непосредственно следует из теоремы 4.2 и формулы Коши–Адамара. 4.4. Арифметические свойства числа остовных деревьевВ серии работ [93], [18], [94] было замечено, что во многих важных случаях число остовных деревьев циркулянтного графа дается формулой \tau(n)=n\,a(n)^2, где a(n) – некоторая целочисленная последовательность. Однако это верно не всегда. Например, в случае графа C_n(1,3) и четного n мы имеем \tau(n)=2n\,a(n)^2 для некоторой целочисленной последовательности a(n). Цель настоящего пункта – объяснить этот феномен. Напомним, что каждое целое положительное число p однозначно представляется в виде p=q\,r^2, где p и q целые положительные числа, а q – свободно от квадратов. Мы будем называть q свободной от квадратов частью числа p. Справедлива следующая теорема [61], [62]. Теорема 4.4. Обозначим через \tau(n) число остовных деревьев в циркулянтном графе C_{n}(s_1,s_2,\dots,s_k ), где 1\leqslant s_1<s_2<\cdots<s_k<n/2. Пусть p – количество нечетных чисел в последовательности s_1,s_2,\dots,s_k и q – свободная от квадратов часть числа p. Тогда существует целочисленная последовательность a(n) такая, что (a) \tau(n)=n\,a(n)^2, если n нечетно; (b) \tau(n)=q \,n\,a(n)^2, если n четно. Сделаем следующее замечание. В теореме 4.4 величину p можно заменить на максимальное собственное значение матрицы Лапласа графа C_{n}(s_1,s_2,\dots,s_k). Как следует из результатов работы [62], оно равно Приведем несколько примеров, иллюстрирующих приведенные выше результаты. Пример 4.1 (граф C_n(1,2)). В этом случае \tau(n)=nF_n^2, где F_n – числа Фибоначчи, A=(3+\sqrt{5}\,)/2, q=5 и \tau(n)\sim(n/5)A^n, n\to\infty. Кроме того, Пример 4.2 (граф C_n(1,3)). Теорема 4.1 дает следующую формулу для числа остовных деревьев:
\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 где \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 – корень уравнения 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} – отличные от единицы корни полинома а 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.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-е число Фибоначчи. Заметим, что где \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, являются соответственно корнями алгебраических уравнений где 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]. Приведем родственный результат, разными методами установленный в работах [20] и [5]. Теорема 5.5. Индекс Кирхгофа призматического графа \operatorname{Pr}_n=C_n\times P_2 дается формулой 5.5. Производящая функция для числа остовных деревьевТеорема о рациональности производящей функции для числа остовных деревьев в графе C_{2n}(s_{1},s_{2},\dots,s_{k},n), аналогичная теореме 4.3, доказана в статье [65]. 5.6. ПримерыПриведем небольшую серию примеров, представляющих результаты, сформулированные в разделе 5. Пример 5.1 (лестница Мёбиуса C_{2n}(1,n)). Для данного семейства графов по теореме 5.1 имеем
\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, получим где 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) – полином Чебышёва первого рода и 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) – мера Малера полинома Лорана Приведем несколько примеров, иллюстрирующих приведенные выше результаты. Пример 6.1 (граф C''_{2n}(1,n) – лестница Мёбиуса с двойными ступенями). Применяя теорему 6.1, получим Интересно сравнить этот результат с аналогичным результатом, полученным в [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) удовлетворяет рекуррентному соотношению с начальными данными 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*}
G_i=C_n(s_{i,1},s_{i,2},\dots,s_{i,k_i}),\qquad i=1,2,\dots,m,
\end{equation*}
\notag
рассмотрим обобщенный лапласиан базового графа L(H,X). Мы определим X, полагая
\begin{equation*}
x_{i}=2k_{i}+d_i-\sum_{j=1}^{k_i}(z^{s_{i,j}}+z^{-s_{i,j}}),
\end{equation*}
\notag
где d_i – степень вершины v_i в H. По определению циркулянтного графа в случае G_{i}\ne C_{n}(\varnothing) имеем 1\leqslant s_{i,1}<s_{i,2}<\cdots<s_{i,k_{i}}. Тогда x_{i} – полином Лорана со старшим членом -z^{s_{i,k_{i}}}. Если G_{i}=C_{n}(\varnothing), то x_{i}=d_{i}. Положим P(z)=\det(L(H,\,X)). Заметим, что P(z) – целочисленный полином Лорана. Для дальнейших рассуждений нам необходимо исследовать структуру старшего члена полинома P(z). Этот член является произведением полиномов x_{i}=2k_{i}+d_{i}- \displaystyle\sum_{j=1}^{k_{i}}(z^{s_{i,j}}+z^{-{s_{i,j}}}) с s_{i,k_{i}}>0 и определителя матрицы, полученной из L(H,\,X) удалением всех строк и столбцов, соответствующих непустым циркулянтным слоям. Для явного вычисления старшего члена P(z) можно использовать следующую лемму. Лемма 7.1. Пусть V'=(v_1,v_2,\dots,v_{m'}) – подмножество (возможно, пустое) вершин базового графа H циркулянтного расслоения H_n(G_1,G_2,\dots,G_m) с пустыми циркулянтными слоями C_{n}(\varnothing). Определим H' как вершинно-индуцированный подграф графа H, образованный V'. Тогда старший член полинома P(z) задается формулой где \eta=\det(L(H',X')), s=\displaystyle\sum_{j=1}^{m}s_{j,k_{j}}, X'=(d_{1},d_{2},\dots,d_{m'}) и d_{j} – степень вершины v_j в графе H. Доказательство. По определению P(z)=\det(L(H,X)), где
\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
описывается формулой где 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, имеем Пример 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} имеет вид где 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) полином напряжений совпадает с сопровождающим полиномом Лорана В случае циркулянтных расслоений, рассмотренных в п. 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. Отметим также следующие полезное соотношение: 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, отметим, что в случае циркулянтных расслоений 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, задается формулой где w_{p},\,p=1,2,\dots,s_{k}, – все корни алгебраического уравнения а T_{s}(w) – полином Чебышёва первого рода степени s.Приведем принципиальную схему доказательства. Множество собственных значений матрицы I_n+L(G) имеет вид
\begin{equation*}
\mu_{j}=P(\varepsilon_{n}^{j})=2k+1- \sum_{i=1}^k(\varepsilon_{n}^{j s_i}+\varepsilon_{n}^{-j s_{i}}),\qquad j=0,\dots,n-1.
\end{equation*}
\notag
Число отмеченных остовных лесов может быть представлено формулой
\begin{equation*}
f_{G}(n)=\det(I_n+L(G))=\prod_{j=0}^{n-1}P(\varepsilon_{n}^{j}).
\end{equation*}
\notag
Поскольку P(z)=P(1/z), все корни P(z) распадаются на пары
\begin{equation*}
z_{1},\frac{1}{z_{1}}\,,\quad z_{2},\frac{1}{z_{2}}\,,\quad \dots,\quad z_{s_{k}},\frac{1}{z_{s_{k}}}\,.
\end{equation*}
\notag
Далее, используя положительность числа f_{G}(n) и основные свойства результантов [75; гл. 3], имеем
\begin{equation*}
\begin{aligned} \, \prod_{j=0}^{n-1}P(\varepsilon_{n}^{j})&= \operatorname{Res}(P(z),z^n-1)=|\operatorname{Res}(z^n-1,P(z))| \\ &=\biggl|\,\prod_{p=1}^{s_{k}}(z_{p}^{n}-1)(z_{p}^{-n}-1)\biggr|= \biggl|\,\prod_{p=1}^{s_{k}}(2T_{n}(w_{p})-2)\biggr|. \end{aligned}
\end{equation*}
\notag
Последнее равенство вытекает из следующего свойства полиномов Чебышёва:
\begin{equation*}
T_{n}\biggl(\frac{1}{2}(z+z^{-1})\biggr)=\frac{1}{2}(z^{n}+z^{-n}).
\end{equation*}
\notag
Кроме того, полагаем w_{p}=(z_{p}+1/z_{p})/2, p=1,\dots,s_{k}. Эти числа являются корнями уравнения \displaystyle\sum_{j=1}^{k}(2T_{j}(w)-2)=1. Следующая теорема позволяет перечислить остовные леса в циркулянтном графе с нечетной степенью вершин. Ее доказательство основано на тех же соображениях, что и доказательство теоремы 9.1. Мы по-прежнему не требуем связности графа. Теорема 9.2. Пусть C_{2n}(s_{1},s_{2},\dots,s_{k},n), 1\leqslant s_{1}<s_{2}<\cdots<s_{k}<n, – циркулянтный граф с нечетной степенью вершин. Тогда число f_{G}(n) отмеченных остовных лесов в графе G=C_{2n}(s_1,s_2,\dots,s_k,n) задается формулой где величины u_p и v_p, p=1,2,\dots,s_k, – корни алгебраических уравнений соответственно. При этом и T_s(w) – полином Чебышёва первого рода.9.2. Арифметические свойства числа отмеченных остовных лесовВ случае циркулянтных графов с четной степенью вершин имеет место следующий результат [33; теорема 7.1]. Теорема 9.3. Обозначим через f_{G}(n) число отмеченных остовных лесов в циркулянтном графе
\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} (если оно есть) равно где 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
определяется формулой где A=\exp\biggl(\displaystyle\int_0^1 \log(P(e^{2\pi\mathtt{i}t}))\,dt\biggr) – мера Малера сопровождающего полинома Лорана P(z)=2k+1-\displaystyle\sum_{i=1}^k(z^{s_i}+z^{-{s_i}}). Доказательство проводится по следующей схеме. По теореме 9.1 число f_{G}(n) остовных лесов определяется формулой f_{G}(n)=\displaystyle\prod_{s=1}^{s_k}|2\,T_n(w_s)-2|, где w_{s}=(z_{s}+z_{s}^{-1})/2. Имеем T_{n}(w_s)=(z_{s}^{n}+z_{s}^{-n})/2, где z_{s} и 1/z_{s}, s=1,\dots,s_{k}, – все корни полинома P(z). Если \varphi\in\mathbb{R}, то
\begin{equation*}
P(e^{\mathtt{i}\varphi})=2k+1-\sum_{j=1}^{k} (e^{s_{j} \mathtt{i}\varphi}+e^{-s_{j}\mathtt{i}\varphi})= 2k+1-2\sum_{j=1}^{k}\cos(s_{j}\varphi)\geqslant1.
\end{equation*}
\notag
Следовательно, полином P(z) не имеет корней, по модулю равных единице, и |z_{s}|\ne1 для всех s. Заменяя при необходимости z_s на 1/z_s, всегда можем считать, что |z_s|>1 для всех s. Тогда T_n(w_s)\sim z_s^n/2, n\to \infty. Поэтому |2T_n(w_s)-2|\sim|z_s|^n, n\to\infty. Отсюда следует, что
\begin{equation*}
\prod_{s=1}^{s_k}|2\,T_n(w_s)-2|\sim \prod_{s=1}^{s_k}|z_s|^n= \prod_{P(z)=0,\,|z|>1}|z|^n=A^n,
\end{equation*}
\notag
где A=\displaystyle\prod_{P(z)=0,\,|z|>1}|z| – мера Малера полинома P(z). B силу результатов, приведенных в п. 2.6, ее можно найти по формуле A=\exp\biggl(\displaystyle\int_0^1\log(P(e^{2\pi\mathtt{i}t}))\,dt\biggr).
Окончательно, Асимптотика числа отмеченных остовных лесов в циркулянтном графе с нечетной степенью вершин определяется следующей теоремой. Теорема 9.6. Число f_{G}(n) отмеченных остовных лесов в циркулянтном графе
\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
имеет следующую асимптотику: где 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
В данном случае где 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. Для изложения результатов данного раздела введем следующие вспомогательные полиномы. Положим где обобщенные лапласианы L(H,X) и L(H,W) те же, что и в разделе 7. Как и раньше, полиномы связаны соотношением P_{f}(z)=Q_{f}((z+1/z)/2). Обозначим через \zeta модуль старшего коэффициента полинома P_{f}(z).10.1. Число отмеченных остовных лесов в циркулянтном расслоенииСледующий результат установлен в [31; теорема 3.3]. Теорема 10.1. Число f(n) отмеченных остовных лесов в циркулянтном расслоении H_{n}(G_1,G_2,\dots,G_m) вычисляется по формуле где s=s_{1,k_1}+s_{2,k_2}+\cdots+s_{m,k_m} и w_p, p=1,2,\dots,s, – все корни уравнения Q_{f}(w)=0, а \zeta – модуль старшего коэффициента полинома P_{f}(z).10.2. Арифметические свойства числа отмеченных остовных лесов в циркулянтном расслоенииСледующий результат получен в [31; теорема 4.1]. Теорема 10.2. Пусть f(n) – число отмеченных остовных лесов в циркулянтном расслоении H_n, а f(H) – число отмеченных остовных лесов в базовом графе H. Обозначим через p свободную от квадратов часть числа Q_{f}(-1). Тогда существует целочисленная последовательность a(n) такая, что (a) f(n)=f(H)\,a(n)^{2}, если n нечетно; (b) f(n)=p\,f(H)\,a(n)^{2}, если n четно. 10.3. Асимптотика числа отмеченных остовных лесов в циркулянтном расслоенииПриведенный ниже результат доказан в [31; теорема 5.1]. Теорема 10.3. Число f(n) отмеченных остовных лесов в циркулянтном расслоении H_n имеет следующую асимптотику: где A=\exp\biggl(\displaystyle\int_{0}^{1}\log |P_{f}(e^{2\pi\mathtt{i}t})|\,dt\biggr) – мера Малера полинома P_{f}(z).10.4. ПримерыПример 10.1 (I-граф I(n,k,l) и обобщенный граф Петерсена \operatorname{GP}(n,k)). Рассмотрим граф H с двумя вершинами и соединяющим их ребром. Положим G_{1}=C_{n}(k) и G_{2}=C_{n}(l). Рассмотрим графы
\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) имеем и \zeta=4. При этом
\begin{equation*}
f(n)=4^n\biggl(2T_{n}\biggl(\frac{13}{8}\biggr)-2\biggr)(2T_{n}(2)-2)^2.
\end{equation*}
\notag
По теореме 10.2 существует целочисленная последовательность a(n) такая, что f(n)=f(1)a(n)^2, если n нечетно, и f(n)=21f(1)a(n)^2, если n – четно, при этом f(1)=20. Теорема 10.3 дает следующую асимптотику: Пример 10.3 (обобщенный H-граф). Рассмотрим обобщенный H-граф вида H_{n}(G_{1},G_{2},G_{3},G_{4}), где G_{i}, i=1,2,3,4, – заданные циркулянтные графы C_{n}(s_{ i,1},\,s_{i,2},\dots,s_{i,k_i}). Для данного графа имеем
\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) получим и \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-графе. Асимптотическое поведение описывается формулой 11. Группы якобиана циркулянтных графовПонятие группы якобиана графа, которую также называют группой Пикара, критической группой, долларовой или песочной группой, было независимо введено многими авторами [22], [6], [9], [4]. Это понятие возникает как дискретная версия якобиана в классической теории римановых поверхностей. Также оно допускает естественную интерпретацию в различных разделах физики, теории кодирования и финансовой математике. Группа якобиана является важным алгебраическим инвариантом конечного графа. В частности, ее порядок совпадает с числом остовных деревьев графа. Цель данного раздела – определить структуру якобиана для циркулянтных графов. Для простейших циркулянтных графов группа якобиана будет найдена в явном виде, в то время как в общем случае будет предложен удобный метод для ее вычисления. 11.1. Графы с четной степенью вершинВведем следующее определение. Пусть P(z) – полином Лорана вида где a_1,a_2,\dots,a_{s-1}, p, s – целые числа и s положительно. Сопровождающую матрицу \mathcal{A} полинома P(z) определим следующим равенством:
\begin{equation*}
\mathcal{A}=\biggl(\begin{array}{c}\begin{array}{c|c} {0} & I_{s-1}\end{array}\\\hline -1,-a_1,\dots,-a_{s-1}\\ \end{array}\biggr),
\end{equation*}
\notag
где I_{s-1} – единичная (s-1)\times(s-1)-матрица. Так как \det(\mathcal{A})=(-1)^{s}, то матрица \mathcal{A} обратима и обратная к ней матрица \mathcal{A}^{-1} также целочисленна. Сопровождающую матрицу полинома -P(z) также будем считать равной \mathcal{A}. Строение якобиана циркулянтного графа с четной степенью описывается следующим утверждением [60; теорема 2.1]. Теорема 11.1. Пусть G=C_{n}(s_{1},s_{2},\dots,s_{k}) – циркулянтный граф со скачками 1\leqslant s_{1}<s_{2}<\cdots<s_{k}< n/2. Тогда группа якобиана \operatorname{Jac}(G) изоморфна группе кручения коядра оператора \mathcal{A}^n-I, где \mathcal{A} – сопровождающая матрица полинома 2k-\displaystyle\sum_{l=1}^{k}(z^{s_{l}}+z^{-s_{l}}). В качестве применения теоремы 11.1 рассмотрим следующий результат, независимо полученный в работах [38] и [60]. Пример 11.1 (граф C_n(1,2)). Якобиан \operatorname{Jac}(C_n(1,2)) изоморфен \mathbb{Z}_{(n,F_n)}\oplus\mathbb{Z}_{F_n}\oplus\mathbb{Z}_{\{n,F_n\}}, где (a,b)=\operatorname{gcd}(a,b) и \{a,b\}=\operatorname{lcm}(a,b) – наибольший общий делитель и наименьшее общее кратное чисел a и b, а F_n – числа Фибоначчи. В качестве следующего примера выступает теорема 2.2 из работы [60]. Пример 11.2 (граф C_n(1,3)). Рассмотрим две периодические последовательности \mu(n) и \eta(n), определенные по формулам
\begin{equation*}
\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) задается формулой 11.2. Графы с нечетной степенью вершинСледующая теорема (в эквивалентной форме) приведена в работе [60]. Техника ее доказательства изложена в последующей работе [32].
\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
и где 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 с целыми коэффициентами такие, что Заметим, что лапласиан 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. Тогда 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}: Это означает, что множители \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 можно взять блочную матрицу где 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]. Напомним, что по теореме об универсальных коэффициентах Чтобы сформулировать аналогичное утверждение для графов, назовем приведенным якобианом \operatorname{Jac}_\mathbb{A}(G) графа G по абелевой группе \mathbb{A} группу, заданную тензорным произведением \operatorname{Jac}(G)\otimes\mathbb{A}. Представим конечную абелеву группу \mathbb{A} в виде суммы \mathbb{Z}_{q_1}\oplus\mathbb{Z}_{q_2}\oplus\cdots\oplus\mathbb{Z}_{q_k}, где q_1,q_2,\dots,q_k – подходящие степени простых чисел, и положим
\begin{equation*}
\operatorname{Jac}_{q}(G)=\operatorname{Jac}(G)\otimes \mathbb{Z}_q.
\end{equation*}
\notag
Тогда приведенный якобиан \operatorname{Jac}_\mathbb{A}(G) графа G по группе \mathbb{A} равен
\begin{equation*}
\operatorname{Jac}_{q_1}(G)\oplus\operatorname{Jac}_{q_2}(G) \oplus\cdots\oplus\operatorname{Jac}_{q_k}(G).
\end{equation*}
\notag
Отметим, что приведенные якобианы играют важную роль в дискретной теории динамических систем [39], [72]. Имеет место следующая теорема [66; теорема 2]. Теорема 12.2. Пусть G_n=C_{n}(s_{1},s_{2},\dots,s_{k}),\,n=1,2,\dots, – последовательность циркулянтных графов, а \widehat{G}_n – соответствующая ей последовательность конусов. Пусть \mathbb{A} – произвольная конечная абелева группа. Тогда последовательности приведенных по группе \mathbb{A} якобианов \operatorname{Jac}_\mathbb{A}(G_n) и \operatorname{Jac}_\mathbb{A}(\widehat{G}_n) периодичны. Чтобы проиллюстрировать теорему 12.2, заметим, что для семейства графов G_n=C_n(1,2) периоды приведенных якобианов \operatorname{Jac}_{\,\mathbb{Z}_6}(G_{n}) и \operatorname{Jac}_{\,\mathbb{Z}_6}(\widehat{G}_{n}) равны 12 и 5, а соответствующие периоды для \operatorname{Jac}_{\,\mathbb{Z}_7}(G_{n}) и \operatorname{Jac}_{\,\mathbb{Z}_7}(\widehat{G}_{n}) равны 56 и 12.
Цитирование в формате AMSBIB
\RBibitem{MedMed23}
Эта публикация цитируется в следующих 1 статьяx:
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Обратная связь:math-net2025_04@mi-ras.ru |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|