Доклады Российской академии наук. Математика, информатика, процессы управления, 2021, T. 498, № 1, стр. 51-54

1. ТЕОРЕМА ПЛАНСА ДЛЯ ЦИРКУЛЯНТНЫХ ГРАФОВ

Наиболее просто теорема Планса для графов формулируется в случае, когда $G$ – граф с одной вершиной и $k$ петлями. В этом случае ${{G}_{n}}$ – циркулярный граф вида ${{C}_{n}}({{s}_{1}},{{s}_{2}}, \ldots ,{{s}_{k}}),$ а ${{\hat {G}}_{n}}$ – конус над ним.

Tеорема 1. Пусть ${{G}_{n}} = {{C}_{n}}({{s}_{1}},{{s}_{2}}, \ldots ,{{s}_{k}})$ – циркулярный граф на $n$ вершинах, а ${{\hat {G}}_{n}}$ – конус над ним. Тогда для любого нечетного n группа $Jac({{\hat {G}}_{n}})$ является прямой суммой двух экземпляров конечной абелевой группы. Если n – четно, то группа $Jac({{\hat {G}}_{2}})$ естественным образом вкладывается в группу $Jac({{\hat {G}}_{n}})$, а фактор группа $Jac({{\hat {G}}_{n}}){\text{/}}Jac({{\hat {G}}_{2}})$ представляется в виде прямой суммы двух экземпляров конечной абелевой группы.

Доказательство основано на следующих соображениях. Рассмотрим ассоциированный с графом G_n полином Лорана L(z) = 2k – $\sum\limits_{j = 1}^k {({{z}^{{{{s}_{j}}}}} + {{z}^{{ - {{s}_{j}}}}})} $. Воспользуемся тем, что абелева группа $Jac({{\hat {G}}_{n}})$ представима невырожденной матрицей ${\text{I}} + {\text{L}}({{G}_{n}}).$ Напомним [3], что лапласиан циркулянтного графа ${{G}_{n}}$ имеет вид ${\text{L}}({{G}_{n}}) = L({{{\text{T}}}_{n}}),$ где ${{{\text{T}}}_{n}}$ – циркулярная n × n матрица вида ${{{\text{T}}}_{n}} = circ(0,1,0, \ldots ,0).$ Отсюда ${\text{I}} + {\text{L}}({{G}_{n}}) = A({{{\text{T}}}_{n}}),$ где $A(z) = 1 + L(z).$ Отметим, что $A(z)$ – полином Лорана с целочисленными коэффициентами, удовлетворяющий условиям $A(z) = A\left( {\tfrac{1}{z}} \right)$ и $A(1) = 1.$ Следовательно [4], $A(z)$ является полиномом Александера некоторого узла K. Пусть M_n – семейство циклических накрытий сферы ${{\mathbb{S}}^{3}}$, разветвленных над узлом K. Согласно [4], группа гомологий ${{H}_{1}}({{M}_{n}},\mathbb{Z})$ вычисляется как $\mathbb{Z}[t,{{t}^{{ - 1}}}]{\text{/}}\langle A(t),{{t}^{n}} - 1\rangle $, где $\mathbb{Z}[t,{{t}^{{ - 1}}}]$ – кольцо лорановских полиномов от t с целочисленными коэффициентами. Поэтому (см., например [5, лемма 3.2]), ${{H}_{1}}({{M}_{n}},\mathbb{Z})$ как абелева группа задается матрицей $A({{{\text{T}}}_{n}}).$ Отсюда группы $Jac({{\hat {G}}_{n}})$ и ${{H}_{1}}({{M}_{n}},\mathbb{Z})$ изоморфны. Следовательно, утверждения теоремы 1 о разложении якобиана в прямую сумму двух экземпляров абелевой группы следуют из теоремы Планса [6], современное доказательство которой можно найти в [7] и [8].

Заметим, что $det(A({{{\text{T}}}_{n}}))$ совпадает с числом отмеченных остовных лесов в графе ${{G}_{n}}$ и, следовательно, всегда отличен от нуля. Это означает, что $Jac({{\hat {G}}_{n}})$ – конечная абелева группа, как и прямые сомножители, на которые она раскладывается.

Важно отметить, что в случае произвольного узла K группа ${{H}_{1}}({{M}_{n}},\mathbb{Z})$ не обязательно конечна [7].

Теорема 1 и ее доказательство без существенных изменений могут быть перенесены на обобщенные графы Петерсена, I-графы, сэндвичи циркулянтных графов и другие классы полициркулянтных графов.

2. ТЕОРЕМЫ ПЕРИОДИЧНОСТИ ДЛЯ ГОМОЛОГИЙ И ЯКОБИАНОВ

В текущем разделе приводятся известные результаты о периодичности групп гомологий с коэффициентами в ${{\mathbb{Z}}_{m}}$ или, более обще, в произвольной конечной абелевой группе $\mathbb{A}$, и устанавливаются их аналоги для якобианов графов.

Известно, что группы гомологий n-листных разветвленных накрытий над узлом, вычисленные с коэффициентами в заданной циклической группе ${{\mathbb{Z}}_{m}}$, образуют периодическую последовательность. Следуя [8], представим это утверждение в более общей форме. Пусть M_n – последовательность n-листных циклических накрытий, разветвленных над заданным узлом, и $\mathbb{A}$ – конечная абелева группа. Тогда последовательность групп гомологий ${{H}_{1}}({{M}_{n}},\mathbb{A})$ с коэффициентами в группе $\mathbb{A}$ – периодична. Аналогичная теорема имеет место и для неразветвленных накрытий дополнения узла до гомологической сферы [9]. Напомним, что по универсальной теореме о коэффициентах ${{H}_{1}}({{M}_{n}},\mathbb{A}) = {{H}_{1}}({{M}_{n}},\mathbb{Z}) \otimes \mathbb{A}.$

Для формулировки аналогичного утверждения для графов назовем приведенным якобианом $Ja{{c}_{\mathbb{A}}}(G)$ графа $G$ по абелевой группе $\mathbb{A}$ группу, заданную тензорным произведением $Jac(G) \otimes \mathbb{A}$.

Представим конечную абелеву группу $\mathbb{A}$ в виде примарного произведения ${{\mathbb{Z}}_{{{{q}_{1}}}}} \oplus {{\mathbb{Z}}_{{{{q}_{2}}}}} \ldots \oplus {{\mathbb{Z}}_{{{{q}_{k}}}}}$, где ${{q}_{1}},{{q}_{2}}, \ldots ,{{q}_{k}}$ – подходящие степени простых чисел, и положим $Ja{{c}_{q}}(G) = Jac(G) \otimes {{\mathbb{Z}}_{q}}$. Тогда приведенный якобиан $Ja{{c}_{\mathbb{A}}}(G)$ графа $G$ по группе $\mathbb{A}$ равен $Ja{{c}_{{{{q}_{1}}}}}(G) \oplus Ja{{c}_{{{{q}_{2}}}}}(G) \oplus \ldots \oplus Ja{{c}_{{{{q}_{k}}}}}(G).$

Отметим, что приведенные якобианы играют важную роль в дискретной теории динамических систем [10].

Имеет место следующая теорема. Приведенное ниже доказательство достаточно элементарно и не опирается на теорию гомологий. Однако использованные в нем идеи, несомненно, могут быть применены и для доказательства периодичности групп гомологий.

Tеорема 2. Пусть ${{G}_{n}} = {{C}_{n}}({{s}_{1}},{{s}_{2}}, \ldots ,{{s}_{k}})$, n = 1, 2, ..., – последовательность циркулянтных графов, а $\mathop {\hat {G}}\nolimits_n $ – соответствующая ей последовательность конусов. Предположим, что $1 \leqslant {{s}_{1}} \leqslant \ldots \leqslant {{s}_{{k - 1}}} < {{s}_{k}}.$

Пусть $\mathbb{A}$ – произвольная конечная абелева группа. Тогда последовательности приведенных по группе $\mathbb{A}$ якобианов $Ja{{c}_{\mathbb{A}}}({{G}_{n}})$ и $Ja{{c}_{\mathbb{A}}}({{\hat {G}}_{n}})$ – периодичны.

Доказательство теоремы 2 проводится по следующей схеме. Поскольку группа $\mathbb{A}$ разлагается в конечную прямую сумму примарных циклических групп, первое утверждение теоремы достаточно доказать для случая $\mathbb{A} = Ja{{c}_{q}}({{G}_{n}}),$ где $q = {{p}^{k}}$ – положительная степень простого числа $p.$ Рассмотрим полином Лорана L(z) = 2k – $\sum\limits_{j = 1}^k ({{z}^{{{{s}_{j}}}}} + {{z}^{{ - {{s}_{j}}}}}),$ ассоциированный с графом ${{G}_{n}}.$ Пусть $\mathcal{A}$ – его сопровождающая матрица вида $\left( {\frac{{0|{{I}_{{2{{s}_{k}} - 1}}}}}{\ell }} \right),$ где строка $\ell $ имеет вид $({{\varepsilon }_{{{{s}_{k}}}}},{{\varepsilon }_{{{{s}_{k}} - 1}}}, \ldots ,{{\varepsilon }_{1}},{{\varepsilon }_{0}},{{\varepsilon }_{1}},{{\varepsilon }_{2}}, \ldots ,{{\varepsilon }_{{{{s}_{k}} - 1}}}),$ где ${{\varepsilon }_{i}}$ равен коэффициенту полинома $L(z)$ при zⁱ.

Тогда по теореме 2.1 из [3] якобиан графа ${{C}_{n}}({{s}_{1}},{{s}_{2}}, \ldots ,{{s}_{k}})$ изоморфен группе кручения коядра оператора ${{\mathcal{A}}^{n}} - {{I}_{s}}{\kern 1pt} :\;{{\mathbb{Z}}^{s}} \to {{\mathbb{Z}}^{s}}$, где $s = 2{{s}_{k}}.$ Указанное коядро – это абелева группа, представимая матрицей ${{\mathcal{A}}^{n}} - {{I}_{s}} = {{\{ {{a}_{{i,j}}}(n)\} }_{{i,j = 1, \ldots ,s}}}$. Отметим, что обе матрицы $\mathcal{A}$ и ${{I}_{s}}$ удовлетворяют уравнению $P(z) = 0,$ где

есть полином Лорана с целыми коэффициентами и старшим коэффициентом, равным единице. Отсюда непосредственно следует, что матрица ${{\mathcal{A}}^{n}} - {{I}_{s}}$ и каждый из ее коэффициентов ${{a}_{{i,j}}}(n)$ удовлетворяют разностному уравнению

Таким образом, при фиксированных i и j коэффициенты ${{a}_{{i,j}}}(n)$ образуют линейную рекуррентную последовательность. Хорошо известно [11], что линейная рекуррентная последовательность, взятая по любому модулю $m$, – периодична. При этом [12] ее период эффективно выражается через число m и коэффициенты полинома $P(z).$ Воспользуемся равенством ${\text{coker}}({{\mathcal{A}}^{n}} - {{I}_{s}})$ = = $Jac({{G}_{n}}) \oplus \mathbb{Z}$ и заметим, что абелева группа ${\text{coker}}({{\mathcal{A}}^{n}} - {{I}_{s}}) \oplus {{\mathbb{Z}}_{q}} = Ja{{c}_{q}}({{G}_{n}}) \oplus {{\mathbb{Z}}_{q}}$ задается матрицей ${{{\text{\{ }}({{a}_{{i,j}}}(n),q){\text{\} }}}_{{i,j = 1, \ldots ,s}}},$ где $({{a}_{{i,j}}}(n),q)$ – наибольший общий делитель ${{a}_{{i,j}}}(n)$ и q. Тогда ee периодичность, равно как и периодичность группы $Ja{{c}_{q}}({{G}_{n}}),$ обеспечиваются следующей леммой.

Лемма 1. Пусть q – целое положительное число, а $u(n)$ – линейная рекурсивная последовательность, удовлетворяющая уравнению (1). Тогда последовательность $(u(n),q)$ периодична по $n.$

Для доказательства леммы воспользуемся периодичностью последовательности $u(n)$ по модулю q. Тогда найдется период m такой, что для всех натуральных n имеет место сравнение u(n + + $m) \equiv u(n)modq.$ Отсюда для некоторых целых d(n) справедливы равенства $u(n + m) = u(n)$ + + d(n)q. Следовательно, (u(n + m), q) = = $(u(n) + d(n)q,q)$ = (u(n), q), т.е. последовательность $(u(n),q)$ периодична с периодом m.

Второе утверждение теоремы доказывается по той же схеме с заменой лорановского полинома $L(z)$ на $1 + L(z).$

Теорема 2 и идея ее доказательства могут быть перенесены на широкий класс полициркулянтных графов, включающих в себя обобщенные графы Петерсена, I-, Y-, H-графы и, более обще, на дискретные расслоения Зейферта, рассмотренные в работе [13].

3. ПРИМЕРЫ

1. Циклический граф ${{G}_{n}} = {{C}_{n}}.$ В этом случае якобиан конуса ${{\hat {G}}_{n}}$ имеет вид $Jac({{\hat {G}}_{n}})$ = = ${{\mathbb{Z}}_{{{{L}_{m}}}}} \oplus {{\mathbb{Z}}_{{{{L}_{m}}}}}$, если $n = 2m + 1$ нечетно, и $Jac({{\hat {G}}_{n}})$ = = ${{\mathbb{Z}}_{{{{F}_{m}}}}} \oplus {{\mathbb{Z}}_{{5{{F}_{m}}}}}$, если $n = 2m$ четно. Здесь ${{L}_{m}}$ и ${{F}_{m}}$ – это числа Люка и Фибоначчи соответственно. Заметим, что сопровождающий полином графа $\mathop {\hat {G}}\nolimits_n $ равен $ - {{z}^{{ - 1}}} + 3 - z$ и совпадает с полиномом Александера узла “восьмерка’’. Хорошо известно [14, 15], что группа гомологий n-листного циклического накрытия трехмерной сферы ${{\mathbb{S}}^{3}}$, разветвленного над узлом “восьмерка’’, совпадает с указанной выше абелевой группой.

2. Граф ${{G}_{n}} = {{C}_{n}}(1,2).$ Напомним, что [3] якобианы данного семейства графов заданы формулой $Jac({{C}_{n}}(1,2)) = {{\mathbb{Z}}_{{{\text{НОД}}(n,{{F}_{n}})}}} \oplus {{\mathbb{Z}}_{{{{F}_{n}}}}} \oplus {{\mathbb{Z}}_{{{\text{НОК}}(n,{{F}_{n}})}}}$, где ${{F}_{n}}$ – это числа Фибоначчи. Для нахождения якобиана конуса $Jac({{\hat {G}}_{n}})$ введем в рассмотрение две последовательности $s(n)$ и $t(n),$ удовлетворяющие единому рекуррентному соотношению

и начальным данным, приведенным в табл. 1.

Тогда теорема 1 позволяет установить, что группа $Jac({{\hat {G}}_{n}})$ в случае нечетного $n$ и фактор-группа $Jac({{\hat {G}}_{n}}){\text{/}}Jac({{\hat {G}}_{2}})$ в случае четного $n$ разлагаются в прямую сумму абелевых групп ${{H}_{n}} \oplus {{H}_{n}},$ где ${{H}_{n}} \cong {{\mathbb{Z}}_{{\alpha (n)}}} \oplus {{\mathbb{Z}}_{{\beta (n)}}},$ $\alpha (n) = {\text{НОД}}\left( {t(n),\tfrac{{s(n) + t(n)}}{2}} \right)$, $\beta (n) = \tfrac{{s{{{(n)}}^{2}} - 29t{{{(n)}}^{2}}}}{{4\alpha (n)}}$ и $Jac({{\hat {G}}_{2}}) \cong {{\mathbb{Z}}_{5}}$.

В качестве иллюстрации теоремы 2 заметим, что периоды последовательностей приведенных якобианов $Jac({{G}_{n}}) \otimes {{\mathbb{Z}}_{6}}$ и $Jac({{\hat {G}}_{n}}) \otimes {{\mathbb{Z}}_{6}}$ равны 12 и 5, а периоды последовательностей $Jac({{G}_{n}}) \otimes {{\mathbb{Z}}_{7}}$ и $Jac({{\hat {G}}_{n}}) \otimes {{\mathbb{Z}}_{7}}$ равны 56 и 12.