О комбинаторике разведений

Аннотация

Многие инварианты узлов строятся по разведениям узла в его перекрестках. Для их вычисления необходимо знать, на сколько компонент связности распадается диаграмма узла после разведения. В настоящей работе демонстрируется, как исследовать этот вопрос, используя модификацию теоремы Зулли вместе с модификацией спектральной теории графов.

Полный текст

1. ВВЕДЕНИЕ В работе [16] Зулли предложил прекрасный метод подсчета числа кривых в некотором состоянии. Под состоянием мы понимаем выбор ориентированного или неориентированного разведения в каждом перекрестке ориентированной диаграммы виртуального узла. Неориентированное: di = 1 Ориентированное: di = 0 Δ = diag(d1,..., dn) Используя это соглашение (которое отличается от принятого в [16]), принцип подсчета Зулли можно описать следующим образом. Пусть D - гауссова диаграмма виртуального узла K, а G - граф пересечений диаграммы D. Пусть A - матрица смежности графа пересечений (см. рис. 1). Занумеруем перекрестки произвольным образом номерами от 1 до n и положим di = 0, если i-й перекресток разведен ориентированно, и di = 1 в противном случае. Пусть Δ = diag(d1,..., dn) - диагональная матрица с этими значениями на диагонали. Для всякого состояния S обозначим число кривых в узле K после разведения через #D (S). Принцип подсчета петель Зулли (ПППЗ): число кривых в разведении S = (d1,..., dn) равно #D (S) = nullityZ2 (A + Δ)+ 1. В настоящей статье мы вводим уточненный принцип подсчета петель (УППП). Целью уточнения является упрощения процесса вычислений комбинаторных инвариантов узлов. Этот принцип особенно удобен для применения к бесконечным семействам узлов. Подобные семейства часто возникают в теории виртуальных узлов [5, 6]. Хотя принцип Зулли работает для всякого меченого графа пересечений, уточненный принцип подсчета петель требует введения линейно упорядоченных графов. Линейно упорядоченный граф - это простой граф, вершины которого пронумерованы числами от 1 до n, а на ребрах проставлены стрелки в направлении от вершины с меньшим номером к вершине с большим номером: u → v, если u< v. Поскольку гауссова диаграмма с отмеченной точкой дает канонический порядок стрелок, ее граф пересечения G превращается в линейно упорядоченный граф G относительно этого порядка. Обозначим через A G_ косую матрицу смежности графа G . В силу нашего принципа ориентации ребер графа элементы косой матрицы смежности, находящиеся над главной диагональю, неотрицательны, а находящиеся ниже диагонали - неположительны. На самой диагонали находятся только нули. Qc 2013 РУДН 87 88 М. В. КРИСМАН 3.+ 2. - 1. - 4. + ⎡ 0 1 1 0 ⎤ 2. 1. ⎢ 1 0 0 1 ⎥ ⎢ ⎣ 1 0 0 1 ⎥ ⎦ 0 1 1 0 4. 3. РИС. 1. Узел и его гауссова диаграмма, граф пересечений и матрица смежности. УППП применяется также к разведению в произвольном наборе перекрестков. Пусть So - множество ориентированных разведений, Su - множество неориентированных разведений, а S∅ - множество неразведенных перекрестков. Мы будем называть тройку S = (So, Su, S∅) частичным разведением виртуального узла. Если D - гауссова диаграмма диаграммы виртуального узла, обозначим через D∅ диаграмму, получающуюся из D удалением всех стрелок, соответствующих элементам множества S∅. Пусть O - разведение, соответствующее выбору ориентированного разведения для каждой стрелки гауссовой диаграммы. Для произвольной квадратной матрицы A обозначим через m0(A) кратность нуля как корня характеристического многочлена для A. Тогда уточненный принцип подсчета петель может быть сформулирован следующим образом: Уточненный принцип подсчета петель (УППП): Пусть S = (So, Su, S∅) - частичное состо- ∅ яние. Пусть G - линейно упорядоченный граф D∅. (A) Если Su = ∅, #D (S) = m0(A G_ )+ 1. (B) Если j ∈ Su I= ∅, то существуют гауссовы диаграммы Df (S) и Ds(S), называемые двулистными накрытиями D, такие что #Df (O) = 2#D j (S) = # s j (O) (см. раздел 2.4). j (S) Dj (S) (C) m0(A G_ ) может быть вычислена непосредственно через более простые линейно-упорядоченные графы с известными характеристическими полиномами. Часть (A) УППП доказывается аналогично ПППЗ. В данном случае основное различие состоит в вычислений гомологий над Q вместо Z2. Часть (B) УППП означает, что всякая задача подсчета числа петель может быть сведена к подсчету петель в полностью ориентированном состоянии. Для этого мы строим гауссову диаграмму по топологическому двулистному накрытию неориентируемой поверхности ΣD (S), ассоциированной с D и S (см. раздел 2.4). Часть (C) доказывается при помощи спектральной теории графов [7, 8], модифицированной для случая линейно упорядоченных графов. В самом деле, мы демонстрируем, как вычислять характеристические полиномы линейно упорядоченных графов, используя зеркальные образы, джойны, слияние и добавление ребер. Результаты несколько отличаются от стандартного симметричного случая. Хочется надеяться, что УППП будет рассматриваться и как интересное приложение спектральной теории графов, и как удобный инструмент для специалистов в комбинаторной теории узлов. Остановимся на этом месте и обсудим, почему УППП необходим. В [16] Зулли ввел ПППЗ для вычисления полинома Джонса узла. Помимо полинома Джонса существует множество инвариантов виртуальных узлов, вычисление которых требует подсчета числа петель. В работе [3] показано, что существует формула вычисления полинома Конвея через гауссовы диаграммы. Используемые в формуле диаграммы могут быть описаны следующим образом: это восходящие диаграммы (первое прохождение по всякой стрелке происходит в направлении стрелки), которые после применения О КОМБИНАТОРИКЕ РАЗВЕДЕНИЙ 89 ориентированного разведения для всех стрелок имеют одну компоненту. В работе [4] этот инвариант также распространяется на случай длинных виртуальных узлов. В работе [6] показано, что это расширение на класс длинных виртуальных узлов может быть использовано для определения бесконечного множества эквивалентных расширений полинома Конвея на длинные виртуальные узлы, удовлетворяющих одним и тем же скейн-соотношениям. Кроме этого, подсчет числа петель позволяет обобщить многие другие инварианты узлов (см. [1]). Таким образом, УППП полезен для упрощения вычисления этих новых инвариантов, особенно для бесконечных семейств узлов (таких как торические узлы, узлы на кренделе, скрученные последовательности, дробные скрученные последовательности и другие). Автор вдохновлялся впечатляющими результатами Зулли и Тралди [15], Тралди [14], Мантурова и Ильютко [9], а также Ильютко, Мантурова и Никонова [10]. В этих работах Z2-дефект матрицы смежности использован для распространения идей теории узлов на теорию графов. Зулли и Тралди предложили идею графов переплетения петель, в то время как Ильютко, Мантуров и Никонов развили понятие граф-зацеплений. Есть надежда, что представленные здесь приемы приведут к новым открытиям в области граф-зацеплений и графов переплетения петель. Работа имеет следующую структуру. В разделе 2 мы определим понятие линейно упорядоченных графов и установим справедливость частей (A) и (B) УППП. В разделе 3 мы разовьем вариант спектральной теории графов, применимый к линейно упорядоченным графам, и тем самым установим часть (C) УППП. В разделе 4 мы проиллюстрируем принцип подсчета петель вычислением однокомпонентных поддиаграмм узлов на кренделе для различных видов разведений. Мы заключим раздел 5 описанием некоторых открытых проблем и задач. Благодарности. Автор крайне благодарен анонимному рецензенту, нашедшему ошибку в утверждении теоремы 5. Автор также благодарен К. Фроману, А. Лоуренсу и М. Саито за интерес, проявленный к данной работе. 2. ПОДСЧЕТ ПЕТЕЛЬ ПО ГАУССОВОЙ ДИАГРАММЕ 1. Гауссовы диаграммы, графы пересечения и линейно упорядоченные графы. Мы предполагаем, что читатель знаком с понятием диаграммы виртуального узла (см., например, [11]). Всякую виртуальную диаграмму можно рассмотреть как иммерсию S1 → R2, где двойные точки представлены либо классическими перекрестками (с локальной ориентацией ⊕ или 8), либо виртуальными. Остальные точки являются регулярными точками иммерсии. Отметим некоторую регулярную точку и будем в дальнейшем полагать ее фиксированной; обозначим ее через ∗. Гауссова диаграмма задается соединением всех прообразов в S1 каждой классической двойной точки отрезком на плоскости R2. Эти отрезки ориентируются в направлении от дуги, образующей переход, к дуге, образующей проход. Каждую стрелку мы также снабдим меткой, отвечающей локальной ориентации перекрестка: ⊕ или 8. Прообраз отмеченной точки также будет обозначаться через ∗. Описанная конструкция проиллюстрирована рис. 2. 2. - 1. - 3.+ 4. + РИС. 2. Виртуальный узел с отмеченной точкой и его гауссова диаграмма. Для подсчета числа петель направление стрелок и знаки на них неважны; единственная информация, которую необходимо знать - характер каждого разведения: ориентированное или неориентированное. Таким образом, мы будем рассматривать только хордовую диаграмму, соответствующую данной гауссовой диаграмме. Обозначим через D(S1, ∗) набор хордовых диаграмм на S1 с отмеченной точкой ∗. 90 М. В. КРИСМАН Linearly Ordered Graphs : 2. 1. ⎡ 0 1 1 0 ⎤ 1 0 0 1 G = ⎢ ⎥ A G_ = ⎢ - ⎥ 4. 3. ⎣ -1 0 0 1 ⎦ 0 -1 -1 0 РИС. 3. Линейно упорядоченный граф и косая матрица смежности узла на рис. 1. Если D ∈ D(S1, ∗), то хорды D имеют канонический порядок. Хорда, конечная точка которой встречается первой при обходе окружности против часовой стрелки, начиная от отмеченной точки, получает номер 1. Удалим эту хорду из диаграммы. Теперь хорду, конец которой встретится первым при обходе полученной диаграммы, обозначим номером 2. Будем продолжать процесс до тех пор, пока каждая хорда не получит свой номер. Для всякой хорды D ∈ D(S1, ∗) определим граф пересечений GD следующим образом (см. [13]). Вершины GD находятся во взаимно-однозначном соответствии с хордами D. Две вершины u, v соединяются ребром, если соответствующие им хорды на гауссовой диаграмме пересекаются. Каждая вершина графа GD снабжается меткой, совпадающей с номером соответствующей хорды согласно каноническому порядку. Обозначим через l(v) метку в вершине v ∈ V (GD ). Пусть i -хорда в диаграмме D ∈ D(S1, ∗). Тогда назовем степенью i степень соответствующей вершины в GD. Граф пересечений может быть направлен в соответствии с каноническим порядком. Если u, v ∈ V (GD ) и u ∼ v, ребро получает направление к v, если l(u) < l(v), и к u в противном случае. Предполагается, что все графы пересечения GD диаграммы D ∈ D(S1, ∗) снабжены метками и направлены в соответствии с каноническим порядком. Иллюстрация для случая виртуального узла, изображенного на рис. 1, дана на рис. 3. Многие из полученных нами результатов справедливы не только для направленных графов пересечений хордовых диаграмм, но и для класса направленных графов, который мы будем называть классом линейно упорядоченных графов: пусть G - граф с n вершинами, помеченными числами 1,..., n. Если v - вершина графа G, обозначим через l(v) метку на ней. Нанесем на ребра графа G стрелки таким образом, что для пары вершин u, v u → v, если и только если l(u) < l(v). Граф с направленными таким образом ребрами будем называть линейно упорядоченным. Линейно упорядоченный граф будет обозначаться G . Косая матрица смежности графа G определяется как матрица смежности направленного графа G . В частности, столбцы матрицы упорядочены в соответствии с метками на вершинах. Элемент aij матрицы равен 1, если i ∼ j и l(i) < l(j), 0, если i j, и -1, если i ∼ j и l(i) > l(j). По построению все элементы косой матрицы смежности, лежащие над главной диагональю, неотрицательны, а все элементы под диагональю - неположительны (ср. с [8]). Косая матрица смежности будет обозначаться A G_ . Эта конструкция проиллюстрирована на рис. 3. Характеристический полином det(xI - A G_ ) матрицы A G_ G будет обозначаться через P _ (x). 2. Состояния, разведения и ленты. Частичное состояние S виртуального узла K - это выбор в каждом перекрестке ориентированного разведения, неориентированного или отсутствия разведения. Пусть So - множество перекрестков K, в которых выбрано ориентированное разведение, Su - множество перекрестков с неориентированными разведениями, а S∅ - множество перекрестков, в которых не выбрано разведение. Будем писать S = (So, Su, S∅). Будем через O обозначать такое частичное состояние, в котором во всех перекрестках выбрано ориентированное разведение. Под полуориентированным разведением будем понимать всякое частичное разведение с Su = ∅. Пусть теперь D ∈ D(S1, ∗). Частичное состояние S = (So, Su, S∅) - это разбиение хорд диаграммы D на три набора So, Su, S∅, среди которых не более двух пустых. Частичное разведение - это компактная поверхность ΣD (S), определяемая следующим образом. Прежде всего, цикл в D рассматривается как граница диска D2. Пусть D∅ - диаграмма, получаемая из D удалением всех хорд из множества S∅. Для каждой хорды i ∈ So приклеим незакрученную ленту к концам хорды i в D∅, как показано на левой части рис. 4. Для каждой хорды i ∈ Su приклеим ленту, закрученную на пол-оборота, как показано на правой части рис. 4. Полученная поверхность и будет обозначаться ΣD (S) (см. рис. 5). О КОМБИНАТОРИКЕ РАЗВЕДЕНИЙ 91 РИС. 4. Приклеивание незакрученной ленты (слева) и закрученной на пол-оборота ленты (справа). 2 3 1 S = ({3}, {1}, {2}) РИС. 5. Хордовая диаграмма D (слева) и частичное разведение ΣD (S) (справа). Определение 1. Число компонент границы поверхности ΣD (S) будет обозначаться через #D (S). Число замкнутых кривых в частичном разведении виртуального узла K будет обозначаться через #(K|S). Лемма 1. Пусть S - частичное состояние диаграммы виртуального узла K с отмеченной точкой. Пусть D - хордовая диаграмма гауссовой диаграммы узла K с каноническими метками (тем самым частичное разведение S порождает разбиение хорд D на множества). Тогда #(K|S) = #D (S). Доказательство. Заметим, что ориентированное разведение перекрестка порождает двухкомпонентное зацепление. Неориентированное разведение дает узел. Заметим также, что превращение классического перекрестка узла K в виртуальный эквивалентно удалению соответствующей хорды из диаграммы D. Процедура приклейки лент, описанная в определении поверхности ΣD (S), в точности моделирует этот процесс. Таким образом, число компонент границы ΣD (S) в точности совпадает с числом вложенных кривых в частичном состоянии. Для дальнейшего нам будет удобно присвоить обозначения концам каждой хорды и углам каждой ленты. Конец хорды i, встреченный первым при обходе против часовой стрелки, начиная с отмеченной точки, будет обозначаться ai. Другой конец той же хорды будет обозначаться bi. Два угла содержащей ai стороны i-й ленты получат обозначения a× и a××, где a× предшествует ai i i i i при обходе против часовой стрелки, а a×× - следует за ai. Аналогично, два угла противоположной стороны ленты получают обозначения b× и b××. Данная конструкция продемонстрирована на рис. 6. i i Заметим, что введенная система обозначений не зависит от выбора разведения. 3. Полуориентированные разведения: теорема Зулли над Q. В этом разделе мы докажем справедливость части (A) УППП. Сначала мы докажем, что число кривых в частичном состоянии может быть вычислено через рациональный дефект косой матрицы смежности. Затем мы покажем, что эта величина равна кратности нуля как корня характеристического многочлена косой матрицы смежности. Теорема 1 (Теорема Зулли над Q). Пусть D ∈ D(S1, ∗), и пусть S = (So, Su, S∅) - частичное состояние диаграммы D, причем Su = ∅. Пусть далее G ∅ - канонический линейно упорядоченный граф D∅. Тогда #D (S) = nullityQ(A _ t )+1 = nullity G∅ Q G (A _ ∅ ) = dim H1(∂ΣD (S), Q). 92 М. В. КРИСМАН ai a× a×× bi × b×× i i bi i РИС. 6. Обозначение концов хорды и углов соответствующей ленты. i* i’ i РИС. 7. 1-циклы i, i× и i∗. Доказательство. Пусть n - число хорд в диаграмме D∅. Определим j : (ΣD (S), ∅) → (ΣD (S), ∂ΣD (S)) G - вложение пар. Согласно [16] достаточно показать, что косая матрица смежности A _ ∅ ляет отображение j∗ : H1(ΣD (S); Q) → H1(ΣD (S), ∂ΣD (S); Q) ∼= ∼= H1(ΣD (S); Q) (двойственность Лефшеца) ∼= ∼= HomQ(H1(ΣD (S); Q), Q). представ- Рассмотрим ленту I × I, приклеенную вдоль дуг a× a×× и b× b××. Пусть ck - 1-симплекс на ленте с k k k k концами ak и bk, соответствующий средней дуге ленты. Центральная дуга ленты - гомеоморфный k образ {1/2}× [0, 1] в ΣD (S). Этот 1-симплекс ориентирован от bk к ak. Будем через c× обозначать 1-симплекс хорды с номером k. Ориентируем ck от ak к bk. Тогда сумма ck + ck - 1-цикл в Z(ΣD × × (S), Q) (см. рис. 7). Будем обозначать такой 1-цикл хорды k тем же символом. 1 Множество определенных таким образом 1-циклов k образует базис в H(ΣD (S), Q). Будем обозначать этот базис через B = {1, 2,..., n}. Выбор базиса в H∗(ΣD (S), Q) может быть сделан каноническим следующим образом. Начнем с отмеченной точки и будем двигаться согласно ориентации. Дуга, направленная от a× к a××, будет рассматриваться как 1-цикл в Z(ΣD (S), ∂ΣD (S); Q). i i Обозначим этот класс через i ∗ . Согласно доказательству двойственности Пуанкаре-Александера (см. [12, теорема 5.3.13]) упорядоченный набор {1∗,..., n∗} может быть взят в качестве упорядоченного базиса H1(ΣD (S), ∂ΣD (S); Q). Вслед за Зулли в [16] заменим класс i ∈B на гомологичный ему класс i×, такой что j∗(i) = j∗(i×) (изображен красным на рис. 7). Класс i× - это класс 1-симплекса от a×× до b× , объединенного с дуi i гой от b× до a×× вдоль границы i-й ленты. В таких обозначениях очевидно, что j∗(i) = j∗(i×). Более i i того, можно заметить, что j∗(i×) по модулю границы - это i-я строка косой матрицы смежности. В самом деле, если хорда с номером k пересекает хорду с номером i и i < k, то вклад в линейную комбинацию составит +1. С другой стороны, если k < i, то вклад составит -1. Поскольку поверхность ориентируема, остаток рассуждения из [16] может быть применен без изменений для доказательства того, что dimQ(ker(j∗)) + 1 = dimQ(H1(∂ΣD (S), Q)), что и завершает доказательство. Чтобы установить справедливость части (A) УППП, остается показать, что число петель в полностью ориентированном состоянии может быть вычислено непосредственно через характеристический многочлен. Прежде всего необходимо проидентифицировать собственные вектора в О КОМБИНАТОРИКЕ РАЗВЕДЕНИЙ 93 собственном подпространстве, отвечающем λ = 0. Будем пользоваться обозначениями из теоремы 1. Обозначим через E(0) собственное подпространство A G_ , отвечающее λ = 0. Порождающий ∅ набор собственных векторов для E(0) может быть построен следующим образом. Обозначим через (S)D множество компонент границы поверхности ΣD (S). Положим ı(C) равным множеству дуг ibi и ai bi на i-й ленте, содержащихся в компоненте C ∈ SD. Пусть c ∈ ı(C). Если c = aibi для a× ×× ×× × × ×× некоторого i, положим σ(c) = 1. Если же c = a××b× для некоторого i, положим σ(c) = -1. Для i i c ∈ ı(C), лежащего на i-й ленте, обозначим через ec вектор длины n (где n - количество хорд), i-я компонента которого равна 1, а остальные - 0. Следствие 1. В данных выше обозначениях справедливы следующие утверждения. 1. Для всех C ∈ SD элемент θC = ), c∈ı(C) ∅ σ(c)ec ∈ ker A G_ . 2. Набор векторов β(D) = {θC : C ∈ SD } порождает собственное подпространство соответствующее λ = 0, а потому линейно зависим. G A _ , ∅ 3. Если β(D) I= {0}, то существует элемент β(D), который может быть удален из этого набора для получения базиса E(0). 4. Размерность собственного подпространства, соответствующего λ = 0, равна алгебраической кратности 0 как корня характеристического многочлена. Доказательство. Для доказательства первого утверждения заметим, что благодаря нашему выбору знаков θC - это гомологический класс ±[C], записанный в терминах базиса B, определенного в доказательстве теоремы 1. Таким образом, θC лежит в ядре A G_ . Второе и третье утверждение сле- ∅ G дуют из теоремы 1. Для доказательства последнего утверждения заметим, что, поскольку A _ - ∅ кососимметрическая матрица над R, она диагонализуема над C. С другой стороны, из первых трех утверждений следует, что у E(0) имеется базис, состоящий из векторов над рациональными числами. Следовательно, размерность собственного подпространства над полем комплексных чисел совпадает с размерностью над полем рациональных чисел, что в точности равно алгебраической кратности. 4. Неориентированные разведения: двулистные накрытия ΣD (S). Теперь рассмотрим случай частичного разведения S, в котором хотя бы одна стрелка разведена неориентируемо. В таком случае ΣD (S) неориентируема. В силу этого доказательство теоремы 1 не может быть применено. Возникающая проблема может быть решена с использованием ориентированного двулистного накрытия ΣD (S) и рассмотрением его как хордовой диаграммы. Пусть S = (So, Su, S∅) - частичное состояние диаграммы D ∈ D(S1, ∗). Заметим, что если множество Su непусто, поверхность ΣD (S) неориентируема. D Мы построим ориентированное двулистное накрытие Σ2 (S) поверхности ΣD (S) следующим образом. Возьмем две копии ΣD (S) в R2 × R, одну из которых покрасим синим цветом, а другую - красным. Рассмотрим скрученную ленту B на синем экземпляре ΣD (S) и ее копию на B× на красном. Проведем горизонтальный разрез на B и аналогичный ему на B×. Таким образом, каждая из лент оказывается разделенной на две половины: B1, B2 и B× , B× соответственно. Пришьем 1 2 2 половину B1 к B× 1 и B2 к B× , сохраняя скручивание на пол-оборота. В результате получится двулистное ориентируемое накрытие для ΣD (S). Описанный процесс показан на рис. 8. Пусть S = (So, Su, S∅) - частичное состояние диаграммы D. Через A обозначим множество букв ai, bi, а через A¯ - множество букв вида a¯i, b¯i. Двигаясь против часовой стрелки, начиная с отмеченной точки ∗, выпишем D∅ в виде слова в этом алфавите: W1 W3 aj bj → W1aj W2bj W3, W2 где Wk - слово (возможно, пустое) в алфавите A \ {aj, bj }. Для каждого слова W в алфавите A обозначим через W¯ слово W, записанное в обратном порядке, причем всякая буква x из A 94 М. В. КРИСМАН → Неориентируемая поверхность ΣD (S) ΣD (S) и копия Разрезание и пришивание D РИС. 8. Построение ориентированного двулистного накрытия Σ2 (S). заменяется на букву x¯ ∈ A¯. Определим слова Wf (S) и Ws(S) следующим образом: j j Wf j (S) = W1W¯ 2a¯j W¯ 1W¯ 3W2bj W3, s Wj (S) = W1aj W2W¯ 1W¯ 3¯bj W¯ 2W3. j Пометим 4n - 2 точки на S1 против часовой стрелки в соответствии с порядком букв в Wf (S) или Ws f s j (S). Определим гауссову диаграмму двулистного накрытия Dj (S) или Dj (S) соответственно, проведя хорды по следующему правилу: 1. для всякого i I= j, если i ∈ So, aibi и a¯i¯bi -хорда, 2. для всякого i I= j, если i ∈ Su, a¯ibi и ai¯bi -хорда, 3. в Df (S) a¯j bj -хорда, в Ds(S) aj¯bj -хорда. j j Лемма 2. Пусть S = (So, Su, S∅) - разведение, причем |Su| 1. Если j ∈ Su, то #Ds j (S) (O) = 2#D Df (S) = # j (S) (O). Доказательство. Построим поверхность Σ× следующим образом. Возьмем копию ΣD (S) в R2 × R и линию l в R2, не пересекающую D. Обозначим через D× отражение D относительно l. Начиная с ∗, будем обозначать концы хорд D следующим образом. Если концы хорды и углы ленты обозначены, как обычно, ai, bi, a× , a××, b× , b××, соответствующие им точки при отражении относительно l i i i i получают обозначение a¯i, ¯bi, a¯× , a¯××, ¯b× , ¯b×× соответственно. Если хорда i не принадлежит Su, проведем i i i i неперекрученную ленту от ai к bi и от a¯i к ¯bi. Если хорда i принадлежит Su, проведем неперекрученную ленту от ai к ¯bi и от bi к a¯i. Описанная конструкция для примера, изображенного на рис. 8, показана на рис. 9. РИС. 9. Стягивание вдоль ребра для получения двулистного накрытия. D Нам требуется показать, что Σ× гомеоморфна Σ2 (S) и эта информация содержится в разведении O как Df (S), так и Ds(S). Заметим прежде всего, что для хорды j имеется две скрученные ленты. j j Первая (f ) из них идет от aj к ¯bj , а вторая (s) - от bj к a¯j . В первую очередь возьмем вторую ленту и обозначим ее через E. Лента - это прямоугольник I × I, одна сторона которого лежит на левой копии S1, а другая - на правой. Две другие стороны прямоугольника - дуги, идущие от одной копии S1 к другой. Представим теперь следующий путь: от отмеченной точки на первой О КОМБИНАТОРИКЕ РАЗВЕДЕНИЙ 95 копии к b× , затем по дуге b× a¯× ко второй копии S1. Будем двигаться против часовой стрелки j j j по D¯ , пока не достигнем дуги a¯××b××, затем вдоль этой дуги по D. Остановимся в отмеченной точке. j j Поскольку ленты соединены в точности как в Σ2 (S), мы можем заключить, что Σ× ≈ Σ2 (S). D D Деформируем вложение поверхности так, что E стянется в интервал и копии S1 окажутся склеенными по этому интервалу (см. правую часть рис. 9). Эта процедура также отождествляет конечные точки хорды в D и хорды в D¯ , создавая тем самым новую хорду (но уменьшая обj щее число хорд на единицу). Более того, возникает выделенная окружность S1. В самом деле, окружность - это путь, описанный в предыдущем абзаце. Получившаяся диаграмма - это Ds(S) D j (с точностью до эквивалентности хордовых диаграмм). Разведение O каждой из этих диаграмм - поверхность, гомеоморфная Σ2 (S). Аналогично, мы можем стянуть вдоль другой неперекрученной ленты j, чтобы получить Df (S). 3. ВЫЧИСЛЕНИЕ ХАРАКТЕРИСТИЧЕСКИХ МНОГОЧЛЕНОВ В предыдущих разделах мы свели задачу подсчета петель в частичных состояниях к поиску характеристических многочленов косых матриц смежности линейно упорядоченных графов. К счастью, эта задача частично решается в рамках существующих теорий. Ее решение является одним из главных достижений спектральной теории графов [7, 8]. К сожалению, теория симметрических матриц смежности должна быть полностью перестроена для случая линейно упорядоченных графов. Тем не менее многие из идей, возникающих в симметрическом случае, могут быть использованы в нашей ситуации. В общем случае мы будем накладывать более сильные условия для получения аналогичных результатов. Полученные формулы будут немного иными. 1. Зеркальные образы. В симметрическом случае свойства определителя гарантируют, что выбор порядка вершин не влияет на характеристический многочлен. В случае косой матрицы смежности это уже не так. Это, однако же, остается справедливым в случае зеркального образа. Теорема 2. Пусть D ∈ D(S1, ∗) и D¯ - ее зеркальный образ. Здесь D¯ оснащается каноническим порядком при движении против часовой стрелки, начиная от отмеченной точки. Пусть G - линейно упорядоченный граф пересечений D и G¯ - линейно упорядоченный граф пересечений D¯ . Тогда P _ G(x) = PG¯ (x). Доказательство. Пусть D имеет n хорд. Будем использовать формулу Лейбница для определителя матрицы. Для метки i в D обозначим через τ (i) каноническую маркировку зеркального образа хорды i в D¯ . Тогда τ ∈ Sn, симметрической группе n элементов. Пусть A - каноническая матрица смежности для D, а A¯ - каноническая матрица смежности для D¯ . В таком случае aij = a¯τ (j)τ (i). Положим A× = xI - A. Тогда в соответствии с формулой Лейбница для det(A×) n iσ(i) sign(σ) n a× = n iστ-1(i) sign(στ -1) n a× = n iτ-1σ(i) sign(τ -1σ) n a× = σ∈Sn i=1 στ-1∈(Sn)τ-1 i=1 n τ-1σ∈τ-1(Sn) i=1 n = τ-1σ∈τ-1(Sn) = σ(i)τ (i) sign(τ -1σ) n a¯× i=1 n sign(τσ-1) n a¯× = τ-1σ∈τ-1(Sn) = jτσ-1(j) sign(τ -1σ) n a¯× = j=1 n sign(τσ-1) n a¯× = τ-1σ∈τ-1(Sn) n j=1 jτσ-1(j) τσ-1∈τ (Sn)-1 j=1 jτσ-1(j) jγ(j) = sign(γ) n a¯× = det(xI - A¯), γ∈Sn что и завершает доказательство. j=1 96 М. В. КРИСМАН 2. Добавление ребра. Пусть G - линейно упорядоченный граф с n вершинами. Пусть u, v ∈ V (G ), причем l(v) = l(u) + 1 и u и v не являются смежными. Обозначим через G + uv линейно упорядоченный граф, полученный из G добавлением ориентированного ребра от u к v. Через G - u обозначим граф, получаемый из G удалением вершины u и перенумеровкой оставшихся естественным образом. Наконец, для всякой квадратной матрицы X через θuv (X) обозначим (u, v) элемент adj(X) - матрицы, присоединенной к X. Здесь мы используем обозначения, введенные в [7, 8]. Мы предлагаем читателю сравнить результаты, полученные в данном разделе, с аналогичными свойствами симметрических матриц смежности, представленными уравнениями (5.1.4) и (5.1.5) в [7]. Теорема 3. В описанных выше обозначениях характеристический многочлен косой матрицы смежности для G + uv задается следующей формулой: P _ G+uv (x) = PG_ -u-v (x)+ PG_ (x)+ θuv (xI - AG_ ) - θvu(xI - AG_ ). Доказательство. Утверждение доказывается в силу полилинейного разложения определителя. Пусть косая матрица смежности для G задается равенством A -a -b B at 0 0 -ct bt 0 0 -dt C c d D A× a b B× -at x 0 ct -bt 0 x dt C× -c -d D× ⎡ ⎤ ⎡ ⎤ A G_ = ⎢ ⎥ , xI - A_ = ⎢ ⎥ . ⎢ ⎥ ⎢ ⎥ G ⎣ ⎦ ⎣ ⎦ В таком случае полилинейное разложение |xI - A G_ +uv | дает: I I I A× a b B× -at x -1 ct -bt 1 x dt C× -c -d D× I I I I I I I I I A× 0 b B× -at 0 0 ct -bt 1 x dt C× 0 -d D× A× 0 0 B× -at 0 -1 ct -bt 1 0 dt C× 0 0 D× I I I I I I I I I I I I I I = I I + I I + I I I I I I I I I A× a b B× t -a x 0 ct -bt 0 x dt C× -c -d D× I I I + I I I I I I I I I I A× a 0 B× t -a x 1 ct -bt 0 0 dt C× -c 0 D× I I I I I I I I I I I I . I I - I I I I I I I I I I I I I I G-u-v Первый определитель в правой части - это θuv (xI - A G_ ). Второе выражение - P _ (x). Третье - P vecG(x). Последнее - θvu(xI - A G_ ). Таким образом, теорема доказана. Следствие 2. Пусть G - линейно упорядоченный граф с вершинами u, v, такой что l(v) = l(u) + 1, u v, и вершина в G Тогда является соседней с u, если и только если она соседняя с v. P _ G+uv (x) = PG_ -u-v (x)+ PG_ (x). Доказательство. Рассмотрим полилинейное разложение, данное в теореме 3. По условию a = b, c = d. Таким образом θuv (xI - A G_ ) = θvu(xI - A G_ ). 3. Джойны. Пусть G 1 и G 2 - линейно упорядоченные графы, число вершин которых равно n1 и n2 соответственно. Мы можем сконструировать линейно упорядоченный граф G 1 LJG 2 следующим образом. Графом будет несвязное объединение G 1 и G 2. Вершины, соответствующие G 1, промаркированы как в G 1. Вершина v в G 2 получит в G 1 LJ G 2 метку l(v)+ n1. Следующее утверждение в точности повторяет результат для симметрических матриц смежности [8]. Теорема 4. Характеристический многочлен для G 1 LJ G 2 задается равенством P _ _ G1 G2 (x) = PG_ 1 (x) · PG_ 2 (x). По данным линейно упорядоченным графам G 1 и G 2, число вершин которых равно n1 и n2 ∇ соответственно, мы можем построить джойн, обозначаемый G 1 G 2, взяв несвязное объединение G 1 и G 2, переобозначив каждую вершину v графа G 2 в l(v)+ n1 и соединив каждую вершину G 1 О КОМБИНАТОРИКЕ РАЗВЕДЕНИЙ 97 1’ 3’ 3 3 4(=1’) 6(=3’) 1 2 7(=4’) 5(=2’) 1 2 4’ 2’ G H ∇H G РИС. 10. Джойн G и H . с каждой вершиной G 2. Новые ребра будут направлены от u ∈ V (G 1) к v ∈ V (G 2). В таком случае косая матрица смежности задается выражением I A 1 J l , -Jt A 2 где J обозначает матрицу подходящего размера, состоящую из одних единиц. Пример построения джойна приведен на рис.10. Читателю стоит сравнить описанное понятие джойна с джойном, введенным в [8, теорема 2.1.5, следствие 2.1.6 и предложение 2.1.7]. ∇ Теорема 5. Характеристический многочлен косой матрицы смежности для G H удовлетворяет следующему равенству: P _ _ _ _ _ _ _ _ _ _ _ G∇H = PG(x)PH (x)+ (PK1∇G(x) - xPG(x))(PK1∇H (x) - xPH (x)). Доказательство. Положим |G | = n 1 и |H | = m 1. Обозначим N = n + m. Будем проводить доказательство индукцией по N. Если N = 2, то n = m = 1. В этом случае и правая, и левая часть равенства имеют вид x2 + 1. Пусть теперь утверждение теоремы верно вплоть до N - 1, причем N - 1 1, ∇ G H имеет N = n + m вершин. Прежде всего мы покажем, что производные левой и правой части совпадают. Затем мы покажем, что значения обеих частей в нуле совпадают. Заметим, что производная может быть выражена следующим образом: _ P × (x) = G P _ n G-j (c), j=1 где G - j обозначает линейно упорядоченный граф G, вершина j которого удалена, а оставшиеся перенумерованы соответствующим образом (из номеров всех вершин с номером большим, чем l(j) вычитается единица). Доказательство этого факта совпадает с доказательством [8, теорема 2.3.1] (на эту книгу мы будем давать ссылки и в дальнейшем). Мы можем заключить, что производная левой части имеет вид P × ∇H (x) = P _ _ _ (x) = P ∇H (x)+ P ∇(H-j)(x). G_ _ _ ∇ j∈V (G_ _ H_ ) (G ∇H)-j j∈V (G_ ) (G_ -j) _ _ j∈V (H_ ) G_ _ _ Применим предположение индукции к каждому слагаемому. Получаем P (x) = P _ (x)P _ (x)+ (P (x) - xP _ (x))(P (x) - xP _ (x)), ∇ (G_ -j) _ H_ G-j H ∇ K1 _ (G_ -j) G-j ∇ K1 _ H_ H P _ _ _ _ _ _ _ _ _ _ _ G∇(H-j)(x) = PG(x)PH-j (x)+ (PK1∇G(x) - xPG(x))(PK1 ∇(H-j)(x) - xPH-j (x)). 98 М. В. КРИСМАН Производная правой части записывается следующим образом: PH_ (x) PG_ j (x)+ P _ (x) P _ (x)+ (P (x) - xP _ (x))×(P _ _ (x) - xP _ (x)) + - j∈V (G_ ) G j∈V (H_ ) H-j ∇ K1 _ G_ G K1∇H H K1 + (P _ _ (x) - xP _ (x))(P _ _ (x) - xP _ (x))×. ∇G G K1∇H H Теперь возьмем производные членов в скобках. Для C = G или H получим: (P (x) - xP (x))× = P × (x) - xP × (x) - P _ (x) = ∇C K1 _ _ _ _ C_ K1∇C C_ (K1 _ _ = P C (x) - x P (x) - P (x) = ∇ j∈V (K1 _ C_ ) ∇C)-j j∈V (C_ ) C_ -j C_ P _ = K1 _ (x) - x P _ (x). j∈V (C_ ) ∇(C-j) j∈V (C_ ) C-j Сравнивая полученные выражения для производной левой и правой части, мы видим, что они совпадают. Для завершения доказательства нам требуется показать, что P _ _ _ _ _ _ _ _ _ G∇H (0) = PG(0)PH (0) + PK1∇G(0)PK1∇H (0). В конечном итоге для доказательства этого утверждения мы будем пользоваться формулой Лейбница. Обозначим через A косую матрицу смежности для G , а через B - косую матрицу ∇ смежности для H . Заметим, что определитель косой матрицы смежности для K1 G , где вершина, помеченная единицей, соответствует вершине, добавленной к G , равен jt adj(A) jn. Для K1 H n ∇ m определитель равен jt adj(B) jm, где jm - матрица размера m × 1, состоящая из одних единиц. ∇ Пусть M обозначает косую матрицу смежности для G H . Напомним формулу Лейбница для определителя матрицы: I I det (M ) = I I n+m = A J I I sign(σ) n miσ(i). I -Jt A 2 I σ∈Sn+m i=1 Пусть σ ∈ Sn+m, и пусть k - количество чисел i между 1 и n, таких что σ(i) > n. Пусть X = {i1,..., ik } - множество таких элементов. Докажем следующее утверждение: если k 2, то существует τ ∈ Sn+m, такое что n+m n+m sign(σ) n miσ(i) + sign(τ ) n miτ (i) = 0. i=1 i=1 Элементов j между n + 1 и m, таких что σ(j) < n + 1, должно быть ровно k. Обозначим их множество через Y = {j1,..., jk }. Заметим, что для i ∈ X, j ∈ Y miσ(i) = 1, mjσ(j) = -1. Таким образом, если мы возьмем произвольную перестановку σ(X) или σ(Y ) и ее композицию с σ, что даст нам новую перестановку γ ∈ Sn+m, то значение выражения n+m n miγ(i) i=1 останется неизменным. Поскольку k 2, число четных и нечетных перестановок совпадает. Таким образом, утверждение доказано. Далее, если k = 0, σ = τγ, где τ, γ не пересекаются, τ ∈ Sn, а γ - перестановка элементов {n + 1,..., m}. Мы можем заключить, что σ∈Sn+m,k=0 n+m sign(σ) n miσ(i) = det (A) det (B). i=1 Теперь пусть k = 1. В этом случае в n+m n i=1 входит n-1 элемент A, m-1 элемент B, 1 и -1. Единица определяет координату по строкам i, 1 i n, и координату по столбцам j, n +1 j m. -1 О КОМБИНАТОРИКЕ РАЗВЕДЕНИЙ 99 3 1’ 3’ 1 2 2’ 1 G H 3 4(=1’) 2(=2’) G · H 5=(3’) РИС. 11. Слияние по вершинам 2 графа G и 2× графа H . определяет координату по строкам i×, n + 1 i× m, и координату по столбцам j, 1 j× n. Вместе они тем самым определяют кофактор A (i, j×) и кофактор B (i×, j). Мы установим взаимно-однозначное соответствие с перестановками вида σ1σ2, где σ1 ∈ S(1,..., n), σ2 ∈ S(n + 1,..., m) и sign(σ)sign(σ1σ2) = -1. В самом деле, в данных выше обозначениях определим σ1 как σ|X и σ1(i) = j×. Определим σ2 как σ|Y и σ2(i×) = j. Теперь возьмем разложение σ1 и σ2 на несвязные циклы. Пусть τ1 - цикл σ1, содержащий i, а τ2 - цикл σ2, содержащий i×. Заметим, что τ1(ij)τ2 - перестановка, отправляющая i → j и i× → j×. Отсюда следует, что σ = σ1(ij)σ2 и sign(σ)sign(σ1σ2) = -1. Таким образом определено взаимно-однозначное соответствие между слагаемыми элементов det (M ) при k = 1 и произведением ( jt adj(A) jn)( jt adj(B) jm). n m Замечание: лишняя -1 компенсирует тот факт, что перестановка в M содержит дополнительную транспозицию (ij). Отсюда следует, что желаемая формула в нуле справедлива. Следовательно, наше рассуждение о производных доказывает, что формула верна для всех N. Индуктивное доказательство завершено. 4. Слияние. Пусть G и H - несвязные ненаправленные графы с вершинами u и v соответственно. Слияние G и H в вершинах u и v - это граф, полученный отождествлением вершин u и v. Обозначается слияние через G · H. Для линейно упорядоченных графов G , H с вершинами u, v соответственно слияние G · H определяется как слияние G · H, где все ребра G ориентированы, как в G , а каждая вершина w из H § v снабжена меткой l(w)+ n. Вершина u(= v) промаркирована u. Поскольку u меньше любой вершины из H § v, соседней с которой является, все ребра, соединяющие u и x ∈ V (H - v), направлены u → x. Эта конструкция изображена на рис. 11. Пусть G - линейно упорядоченный граф и u - его вершина. Определим продвижение u в G как линейно ориентированный граф, получаемый из G удалением вершины u, добавлением вершины v0 (с l(v0) = 1), у которой соседними будут те же вершины, что и у u, и перемаркировкой всякой вершины w с l(w) < l(u) на l(w)+ 1. Обозначим продвижение u в G через G ↔ u. Следующий результат показывает, что косой спектр слияния связан с косыми спектрами более простых линейно упорядоченных графов. Доказательство очень похоже на доказательство [8, теорема 2.2.3]. Теорема 6. Характеристический многочлен слияния линейно упорядоченных графов G в u и v задается выражением и H P _ _ _ _ _ _ _ _ G·H (x) = PG(x)PH-v (x)+ PG-u(x)PH↔v (x) - xPG-u(x)PH-v (x). Доказательство. Пусть косые матрицы смежности G и H имеют следующий вид: ⎡ A α B ⎤ ⎡ E γ F ⎤ ⎣ -αt 0 βt ⎦ , C -β D ⎣ -γt 0 δt ⎦ . C -β D 100 М. В. КРИСМАН Здесь «греческие столбцы» в матрицах представляют собой косые матрицы смежности для u и v соответственно. Пусть M является косой матрицей смежности линейно упорядоченного графа G · H . Тогда xI - M имеет вид ⎡ A× α B× 0 0 ⎤ ⎥ ⎢ αt x -βt -γt -δt ⎥ ⎢ , ⎢ C× β D× 0 ⎢ 0 ⎥ ⎥ ⎣ 0 γ 0 E× F × ⎦ 0 δ 0 G× H× где A×, B×, C×, D×, E×,F ×, G×,H× - матрицы, полученные из A, B, C, D, E, F, G, H вычитанием M из xI. Поскольку определитель полилинеен, det (xI - M ) может быть выражен следующим образом: I I A× 0 B × 0 I 0 I I I I A× -αt B× 0 0 I I I I A× 0 B× 0 0 I I I I αt x -βt -γt -δt I I I I αt x -βt -γt -δt I I I I αt x -βt -γt -δt I I C× I 0 D × 0 0 I + I C× β D× 0 0 I I I I C× × I I I - I 0 D 0 0 I . I I I 0 γ 0 E× I I 0 δ 0 G× I F × I I I I H× I I I I 0 0 0 E× F × 0 0 0 G× H× I I 0 0 0 E× I I I I 0 0 0 G× F × I I H× I Второе слагаемое - это P _ (x)P _ (x). Третье - xP _ (x)P _ (x). Первый определитель может G H-v G-u H-v _ быть преобразован, чтобы получить P G-u _ (x)P H↔v (x): I I A× 0 B × 0 I 0 I I I I A× B× 0 0 0 I I I I αt x -βt -γt -δt I I I I C× D× 0 0 0 I I C× × I I I I 0 D I 0 0 I = I I αt -βt x -γt -δt I . I I 0 γ 0 E× I I 0 δ 0 G× F × I I H× I I I 0 0 γ E× I I 0 0 δ G× F × I I H× I 5. Строительный кубик: линейно упорядоченные пути. Обозначим через Dn хордовую диаграмму с отмеченной точкой, причем последовательность концов маркированных хорд, начиная от отмеченной точки, задается кодом 12132435465 ... (n - 1)(n - 2)n(n - 1)n. Тогда граф пересечений Dn - это упорядоченный путь задается выражением P n. Косая матрица смежности для Dn ⎡ ⎢ ⎢ ⎢ A n = ⎢ ⎢ ⎢ ... ... ... . . . 0 1 0 ... 0 0 -1 0 1 ... 0 0 0 -1 0 ... 0 . 0 . ⎤ ⎥ ⎥ ⎥ . ⎥ ⎥ .. .. ⎥ ⎦ ⎣ ⎢ 0 0 0 ... 0 1 ⎥ 0 0 0 ... -1 0 Теорема 7. Пусть n ∈ N. Тогда для упорядоченного пути P n справедливы следующие утверждения: 1. рекурсивное соотношение P _ _ - Pn (z) = xPP_n (x)+ P 1 Pn-2 (x) с начальными условиями P _ (x) = x, P _ (x) = x2 + 1; P1 P2 2. решением этого рекурсивного соотношения является 1 If x \ ( n f x \ ( nl P _ Pn (x) = 2n+1 √ 1+ x2 +4 x + /x2 +4 2 + 1 - √ x +4 x - /x2 +4 ; О КОМБИНАТОРИКЕ РАЗВЕДЕНИЙ 101 3. решение может быть записано в виде суммы: 1 n/2 f n +1 \ Pn (x) = 2n P _ j=0 2j +1 xn-2j (x2 + 4)j . Доказательство. Для начала вычислим det (xI - A n): I I x -1 0 ... 0 0 I 1 x -1 ... 0 0 0 1 x ... 0 0 ... ... ... . . . ... ... I I I I I I I I I I I = xP I I I 1 -1 0 ... 0 0 I I I I 0 x -1 ... 0 0 I I I I 0 1 x ... 0 0 I (x)+ I I = . . I I P_n-1 I I I .. I ... ... . . . ... .. I I I 0 0 0 ... x -1 I I 0 0 0 ... x -1 I I I I I I 0 0 0 0 1 x I I I I I I I 0 0 0 0 1 x I I I 0 -1 0 ... 0 0 I I I I 0 x -1 ... 0 0 I I I I 0 1 x ... 0 0 I = xP _ (x)+ P _ (x)+ I . . . . . I = xP _ (x)+ P _ (x). Pn-1 . . Pn-2 I . . I . I .. . . . .. . I Pn-1 Pn-2 I 0 0 0 ... x -1 I I I I I I 0 0 0 0 1 x I Второе утверждение теоремы проверяется решением рекурсивного соотношения. Третье утверждение достигается применением биномиальной теоремы и формулы для треугольника Паскаля. 1. Строительный кубик: полные линейно упорядоченные графы. Обозначим через Dn хордовую диаграмму с отмеченной точкой, причем последовательность концов маркированных хорд, начиная от отмеченной точки, задается кодом 123 ... n123 ... n. Граф пересечений Dn - это полный граф на n вершинах. Мы будем обозначать этот граф (с каноническим порядком на нем) через K n. Обозначим через A n косую матрицу смежности для K n. Тогда ⎡ ⎢ A n = ⎢ ⎢ ⎣ ... ... . . . 0 1 1 ... 1 -1 0 1 ... . 1 . ⎤ ⎥ . ⎥ ⎦ .. .. ⎥ -1 -1 -1 ... 0 Лемма 3. Для косой матрицы смежности A n графа K n справедливы следующие утверждения: 1. для всякого n ∈ 2N A n обратима и det (A n) = 1; 2. если n ∈/ 2N, det (A n) = 0. Доказательство. Для начала предположим, что n ∈/ 2N. Достаточно показать, что существует ненулевой вектор в собственном пространстве, отвечающем λ = 0. В самом деле, если n нечетное, vn = [1 - 1 1 ··· - 1 1]t. Непосредственное вычисление показывает, что A n · vn = 0 для любого нечетного n. Таким образом, det (A n) = 0 для нечетных n. Пусть теперь n ∈ 2N. Легко проверить, что обратной к A n является матрица ⎡ 0 -1 -1 ... -1 ⎤ n A -1 ⎢ 1 0 -1 ... -1 ⎥ ⎢ . . = ⎢ .. ⎣ ... . . . ⎥ . . . . . ⎥ . ⎦ 1 1 1 ... 0 102 М. В. КРИСМАН n Поскольку A -1 - матрица над Z, det (A n) = ±1 (поскольку других единиц в Z нет). Вычислим определитель A n, пользуясь равенством n = A -1 1 det (A n) adj(A n) = ±adj(A n), где adj(B) обозначает матрицу, присоединенную к B. Доказательство проведем индукцией по n. I 0 1 l Для n = 2 A 2 = -1 0 , а потому det (A 2) = 1. Предположим, что наше утверждение верно для всех четных натуральных чисел, меньших n. Обозначим через Bˆj матрицу, полученную - ˆ из B удалением j того столбца. Для квадратной матрицы B обозначим через Bˆj матрицу, поi лученную удалением из B j-того столбца и i-той строки. Разложим определитель, заданный (1, 2)-кофактором A n: I I I -1 1 1 ... 1 I I I I I I I n-2 I -1 I n-2 I 1 I I -1 I I .. i I I .. i I I . I .. I A n-2 - I = det (A I I n-2)+ - I ( 1)i I I I . (A n-2 )ˆ I = -1+ I - ) ( 1)i+1 I I I . (A n-2 ˆ I = I I I I -1 I I n-2 n-2 i=1 I I -1 I I n-2 n-2 i=1 I 1 I I I = -1+ (-1)i+1 (-1)j-1 I (A n 2)ˆi I = -1+ (-1)i+j I (A n 2)ˆi I = i=1 j=1 I - I i=1 j=1 I - I n-2 n-2 = -1+ (-1)i+j (adj(A n i=1 j=1 -2))ij n-2 = -1+ (-1)j = -1. j=1 В третьей снизу строке мы используем индукционное предположение, что A -1 n-2 = adj(A n -2). n Таким образом, 1 является элементом (2, 1) матрицы adj(A n). Поскольку A -1 = ±adj(A n), элемент (2, 1) матрицы завершено. A -1 n также равен 1, а следовательно det (A n) = 1. Индуктивное доказательство Теорема 8. Для полных линейно упорядоченных графов K n верно следующее равенство: P _ 1 n Kn (x) = 2 ((-1+ x) + (1+ x)n). Доказательство. Мы вновь воспользуемся тем фактом, что n P × G_ (x) = j=1 PG_ -j (x). G_ Положим G = K n. Заметим, что для всех j = 1,...,n G - j ∼= K n-1. Отсюда следует, что P × (x) = _ nP Kn-1 _ (X). Сначала рассмотрим случай четного n. Имеем P (n-2)(x) = G n!(x2 + 1). Вспомним, что 2 P _ t Kt (0) = (-1) det (At) для всех t. В силу леммы 3 мы знаем, что PK_ t (0) = 1 для всех четных t и равно 0 для нечетных t. Отсюда мы можем заключить, что ⎧ n! четное k, P (k) K_ n (0) = ⎨(n - k)! , k n - 4, ⎩0, k n - 3, нечетное k. Согласно теореме Тейлора, P _ _ (0) n P (i) Kn i n! xn x n-2 n-4 2 n! 2j n/2 f n \ x2j = Kn (x) = i=0 1 x = ( + )+ i! 2 n!/2 (n - 2)! j=0 x (n - 2j)!(2j)! = 2j j=0 - = (( 1+ x)n + (1+ x)n). 2 О КОМБИНАТОРИКЕ РАЗВЕДЕНИЙ 103 σp σq σr p, q, r ∈ Z\{0} p, q, r нечетные p четное, q, r нечетные РИС. 12. Два случая узла на кренделе. Последнее равенство следует из биномиальной теоремы. Пусть теперь n нечетное. В этом случае P (n-1) _ (x) = n!x. Рассуждая аналогично случаю четного n, имеем, что G ⎧ n! нечетное k, P (k) K_ n (0) = ⎨(n - k)! , ⎩0, четное k. Из теоремы Тейлора и биномиальной теоремы следует, что P _ (n+1)/2 f n \ 2j-1 1 n n G(x) = j=1 x 2 2j - 1 = (-(1 - x) + (1+ x) ). 1. ПРИЛОЖЕНИЕ К УЗЛАМ НА КРЕНДЕЛЕ Пусть F - множество (не обязательно конечное) диаграмм виртуальных узлов (в частности, мы не рассматриваем их с точностью до рейдемейстеровской эквивалентности). Пусть m 1 - натуральное число. Пусть, далее, j - натуральное число между 1 и m. Вопрос (j, m): сколькими способами можно построить ориентированное разведение в m - j перекрестках и неориентированное разбиение в j перекрестках по данной диаграмме K ∈ F , так что в результате будет в точности одна связная компонента? Мы будем пользоваться следующим соглашением: если m больше общего числа перекрестков в K ∈ F , то ответом на вопрос (j, m) примем 0. В наших обозначениях вопрос (j, m) имеет эквивалентную формулировку: сколько существует частичных состояний S = (So, Su, S∅), таких что |Su| = j, |So| = m - j и #(K|S) = 1 для данной диаграммы K ∈ F? Пусть теперь F - множество диаграмм узлов на кренделе. Мы ответим на вопрос (0, m) и (1, m) для всех m. Пусть p, q, r ∈ Z \ {0}. Напомним, что зацепление на кренделе - это зацепление вида, продемонстрированного на рис. 12, причем внутри рамок у нас находятся 2-косы σp, σq, σr соответственно [2]. Легко проверить, что зацепление на кренделе L(p, q, r) является узлом на кренделе, если и только если среди чисел p, q, r не более одного четного. Когда все они нечетные, гауссова диаграмма соответствующего узла выглядит подобно изображенной в центре рис. 12. Здесь хорды обозначают p, q или r параллельно идущих хорд. Когда одно из них четное, например, p, гауссова диаграмма выглядит подобно правой части рис. 12. Хорда степени два обозначает p параллельных хорд. Хорды степени 1 обозначают q и r хорд, графами пересечений которых являются полные графы Kq и Kr соответственно. Мы докажем несколько утверждений, которые будут использованы для ответа на вопрос (0, m) и (1, m). Заметим, что мы не будем выписывать характеристические многочлены в явном виде, а лишь вычислим их значения в нуле и значения их производных в нуле. На диаграмме ниже области помеченные буквой α (или β) содержат хотя бы одну из конечных точек α (β) хорд, со свойством: каждая хорда в области пересекает все прочие хорды в этой области. 104 М. В. КРИСМАН Черные хорды, концы которых не лежат ни в α, ни в β области, обозначают одиночные хорды. Если черная хорда проходит через область, она пересекает все хорды, концы которых лежат в этой области. D4 = , D5 = , D6 = , D7 = РИС. 13. Диаграммы, рассматриваемые в леммах 4, 5, 6 и 7. Лемма 4. Пусть G 4 - линейно упорядоченный граф, связанный с диаграммой D4, изображенной на рис. 13. Тогда 1 P _ α+β G4 (0) = 2 (1 - (-1) ), P × 1 α α+β G_ 4 (0) = 4 (1 + (-1) + 2α + 2β + (-1) (1 + 2α + 2β)). Доказательство. Рассмотрим линейно упорядоченные графы K α+1 и K β+1. Образуем слияние этих графов по вершинам, помеченным 1 в каждом из них. Тогда G 4 есть K α+1 ·K β+1. По теореме 8 мы знаем многочлены K α+1(x) и K β+1(x). Заметим, что продвижение любой вершины j ∈ V (K β ) не меняет линейно упорядоченный граф: K β+1 совпадает с K β+1 ↔ j. Поэтому по теореме 6 мы можем вычислить P _ _ (x). Отсюда мы можем вычислить значение многочлена и его Kα+1·Kβ+1 производной в нуле (вычисления могут быть упрощены использованием пакета компьютерных вычислений Mathematica). Лемма 5. Пусть G 5 - линейно упорядоченный граф, связанный с диаграммой D5, изображенной на рис. 13. Тогда P _ 1 α G5 (0) = 8 (1 + (-1) )(1 + (-1)β )((1 + (-1) α+1 )(1 + (-1)β )+ (1 + (-1)α )(1 + (-1) β+1), P × 1 β 2α+β α G_ 5 (0) = 16 (8α(1 + (-1) )(1 + (-1) )+ (1 + (-1) ) × × ((1 + (-1)α)(1 + (-1)β )2 + 8β(1 + (-1)α+2β ))). Доказательство. Рассмотрим линейно упорядоченные графы K α+1 и K β+1. Образуем слияние этих графов по вершинам, помеченным 1: K α · K β. Новая вершина, помеченная 1, является соседней с экземпляром K α и с экземпляром K β. Теперь возьмем два экземпляра K α+1 · K β+1 и образуем слияние по вершинам, помеченным 1. Оказывается, G 5 задается (K α+1 · K β+1) · (K α+1 · K β+1). Поскольку мы всегда производим слияние по 1, продвижение не влияет на характеристический многочлен. Из предыдущей леммы мы знаем замкнутую формулу для P _ _ (x). С другой сто- Kα+1·Kβ+1 роны, удаление вершины 1 из (K α+1 · K β+1) дает несвязное объединение K α LJ K β. Следовательно, О КОМБИНАТОРИКЕ РАЗВЕДЕНИЙ 105 P _ G15 (x) может быть вычислен по теореме 6. Отсюда немедленно вытекает формула для многочлена и его производной в нуле. Лемма 6. Пусть G 6 - линейно упорядоченный граф, связанный с диаграммой D6, изображенной на рис. 13. Тогда P _ G6 (0) = 0, P × 3 G_ 6 (0) = 4 (-1+ (-1) α+β )2. Доказательство. Прежде всего рассмотрим H 1 = K 2 (K α LJK β ). По теореме 5 имеем, что P _ (x) зависит только от P _ (x), P _ (x), P _ _ _ _ (x) и ∇ P _ (x). Легко видеть, что H1 K 1 (K α LJ K β ) Kα Kβ K1∇(Kα Kβ ) K3 ∇ совпадает с K α+1 · K β+1, вычисленным в лемме 4. Обозначим через H 2 линейно упорядоченный граф, получаемый удалением синих и красных стрелок в правой части D6 и получающейся одиночной хорды внизу справа. Тогда H 2 содержит две последовательно идущие хорды с одними и теми же соседними. Поэтому H 2 может быть получен из H 1 удалением ребра, соединяющего вершины 1 и 2. Из следствия 2 мы можем заключить, что P _ H2 (x) = P_h1 (x) - PK_ α (x)PK_ β (x). Наконец, мы можем построить линейно упорядоченный граф для D6 как H 2 · H 2, причем слияние проводится по вершине 2 в первом графе и по вершине 1 во втором. Продвижение вновь не влияет на граф. Таким образом, следуют. P _ G (x) определяется по теореме 6. Многочлен и производная в нуле 6 Лемма 7. Пусть G 7 - линейно упорядоченный граф, связанный с диаграммой D7, изображенной на рис. 13. Тогда P _ G7 (0) = 0, P × 1 β α α+β 2α+β α+2β G_ 7 (0) = 4 (-1+ (-1) + (-1) + 2(-1) (-1) + (-1) + 8α + 8β. Доказательство. Начнем с H 1 = K α+1 · K β+1, где слияние проводится по вершине 1 в K β+1 и по вершине, отличной от 1, в K α+1. Затем возьмем два экземпляра H 1 и H 1 · H 1 по вершинам 1 в графах. Напомним, что H¯ обозначает граф пересечений зеркального образа диаграммы. Напомним далее, что по теореме 2 для графов, полученных таким образом, P ¯ (x) = P _ (x). Следовательно, H H P _ G7 (x) = PH_ 1·H_ 1 (x). Дважды применяя теорему 6, мы легко вычислим второй многочлен. Из этого вычисления вытекают требуемые нам факты. Теперь у нас есть все инструменты, чтобы дать ответ на вопрос (0, m) и (1, m). Пусть p, q, r ∈ Z \ {0} и P = |p|,Q = |q|,R = |r|. Пусть m ∈ N. Обозначим через N0(p, q, r, m) число вариантов выбора m перекрестков узла на кренделе L(p, q, r), так что ориентированное разведение в этих перекрестках дает одну компоненту. Обозначим через N1(p, q, r, m) число вариантов выбора m перекрестков узла на кренделе L(p, q, r), так что ровно в одном перекрестке разведение неориентируемо, в m-1 разведение ориентируемо и результат состоит ровно из одной компоненты. Иными словами, Nj - ответ на вопрос (j, m) для набора параметров p, q, r, m. Теорема 9. Пусть все числа p, q, r, m нечетные. Тогда I 0, m = 2, N0(p, q, r, m) = PQ + QR + RS, m = 2, ⎧0, m > 3, N (p, q, r, m ⎨P + Q + R, m = 1, ⎪⎪ 1 ) = ⎪⎪ 2(PQ + QR + RS), m = 2, ⎩3PQR + 2 P (Q + R)+ 2 Q (P + R)+ 2 R (P + Q), m = 3. 2 2 2 106 М. В. КРИСМАН Доказательство. Заметим, что если выбрана пара параллельных хорд и разведения у обеих ориентированные, то вне зависимости от дальнейшего выбора хорд и разведений количество компонент будет не меньше двух. Рассмотрим для начала формулу для N0. Если m = 1, ориентированные разведения дадут две компоненты. Если m > 3, то на диаграмме 12 должна быть выбрана хотя бы одна пара параллельных хорд. Следовательно, в этом случае N0 = 0. Аналогично, если m = 3 и выбраны две параллельные хорды, то N0 = 0. Если m = 3 и все хорды пересекаются, то можно проверить, что N0 = 0. Если m = 2, то число компонент будет равно единице, только если выбрана пара пересекающихся хорд. Таким образом, формула доказана. Теперь рассмотрим формулу для N1. Если m = 1, мы неориентированно разводим ровно один перекресток. Это даст нам одну компоненту. Если m = 2, число компонент будет равно единице, только если выбрана пара пересекающихся хорд. Одна из них будет разведена ориентированно, другая - неориентированно. Следовательно, искомое количество способов равно 2(PQ+QR +RS). Для m = 3 компонента будет одна, если (1) никакие из хорд не параллельны или (2) из двух параллельных хорд одна разводится неориентированно, а третья пересекает их. Вклад случая (1) составляет 2PQR. Вклад случая (2) составляет 2 P (Q + R)+ 2 Q (P + R)+ 2 R (P + Q). 2 2 2 Когда m > 3, мы вынуждены выбрать как минимум две параллельные хорды. Если ни одна из них не разведена неориентированно, мы получаем не меньше двух компонент. Следовательно, m 4. Предположим, m = 4. Единственная возможность состоит в том, что две хорды параллельны, а из двух хорд каждая пересекает все остальные. Более того, неориентированное разведение должно быть выбрано для одной из параллельных хорд. Непосредственная проверка показывает, что компонент будет две. Формула доказана. Теорема 10. Если одно из чисел p, q, r четное (для определенности предположим, что это p ), то: а). m = 1: б). m 2, четное: N0(p, q, r, 1) = 0, N1(p, q, r, 1) = P + Q + R; m/2 f Q \f R N0(p, q, r, 1) = \ f Q \f R + P \ f R \f Q \ + P , 2k k=0 m - 2k 2k m - 1 - 2k 2k m - 1 - 2k N1(p, q, r, 1) = P (m-2)/2 f Q \f R \ f Q + \f R \ + k=0 2k m - 1 - 2k m - 1 - 2k 2k m-1 + PQ (m-2)/2 fQ - 1\f R - \ 2 f R \f Q 1 \ + Q + k=0 k m - 2 - k m-1 2k k=0 m - 1 - 2k + PR m-2 fR - 1\f Q - \ 2 f Q \f R 1 \ + R ; в). m 3, нечетное: k=0 k m - 2 - k N0(p, q, r, m) = 0, 2k k=0 m - 1 - 2k N1(p, q, r, m) = P (m-1)/2 f Q \f R \ + k=0 2k m - 1 - 2k (m-3)/2 f Q \f R + P \ f Q + \f R \ + k=0 2k m - 2 - 2k m - 2 - 2k 2k О КОМБИНАТОРИКЕ РАЗВЕДЕНИЙ 107 + PQ m-2 fQ - 1\f R - \ (m-1)/2 f R \f Q 1 \ + Q + k k=0 m - 2 - k k=0 2k m - 1 - 2k + PR m-2 fR - 1\f Q - \ (m-1)/2 f Q \f R 1 \ + R . k k=0 m - 2 - k k=0 2k m - 1 - 2k Доказательство. Формула для N0 сразу следует из леммы 4. Пусть S = (So, Su, S∅) - частичное разведение, причем |Su| = 1. Для N1 выберем в первую очередь хорду a и разведем ее неориентированно. Тогда a должна быть среди p хорд, q хорд или r хорд. Предположим для начала, что a находится среди p параллельных хорд. Немедленно видим, что если из оставшихся p - 1 хорды выбрать более одной, компонент получится не менее двух. Следовательно, выбрать можно 0 или 1 хорду. D Теперь возьмем двулистное накрытие Σ2 (S), определенное в разделе 2.4, и стянем вдоль одной из лент, отвечающих a. Это даст нам гауссову диаграмму Df (S) (или DS (S)), как описывалось a a a a ранее. Вопрос о D превращается вопрос о неориентированном разведении Df (S) для данного выбора a и еще 2(m - 1) хорд, которое дает в точности две компоненты. Заметим, что, кроме a, хорды в Df (S) выбираются парами благодаря обратному образу двулистного накрытия. Обозначим через α число хорд, выбранных среди q хорд, и через β - число хорд, выбранных среди r хорд. a Предположим, что ни одна из параллельных a хорд не разведена ориентированно. Тогда Df (S) G15 совпадает с D5, изображенной на рис. 13. По лемме 5, P _ (0) = 0 для всех α, β 1, и P × G_ 15 (0) I= 0, если α, β не являются одновременно нечетными. Если α = β = 0, то m = 1 и ответом является a P + Q + R. Если α = 0,β I= 0 или α I= 0,β = 0, то по лемме 4, Df (S) имеет две компоненты. Следовательно, этот случай дает следующий вклад в формулу для N1: нечетное m: P (m-1)/2 f Q \f R \ , k=0 2k m - 1 - 2k четное m: P (m-2)/2 f Q \f R \ f Q + \f R \ . k=0 2k m - 1 - 2k m - 1 - 2k 2k a Пусть теперь одна из хорд, параллельных a, разведена ориентированно. Тогда Df (S) совпадает с D6, изображенной на рис. 13. В этом случае мы должны выбрать α, β так, что α + β = m - 2. G6 По лемме 6, P _ _ (0) = 0, если α 1,β 0 или β 1,α 0, и P × G6 (0) I= 0, если четность α и β различна. Если α = β = 0, то m = 2 и D6 состоит из четырех компонент. Следовательно, этот случай дает следующий вклад в формулу для N1: нечетное m: P (m-3)/2 f Q \f R \ f Q + \f R \ , четное m: 0. k=0 2k m - 1 - 2k m - 2 - 2k 2k a Теперь рассмотрим случай, когда неориентированное разведение выбрано среди q хорд. Если ориентированно разведено больше одной из p хорд, компонент заведомо больше двух. Значит, из p хорд может быть выбрано либо ни одной, либо одна хорда. Если выбрана одна хорда, то Df (S) G7 совпадает с D7, изображенной на рис. 13. Заметим, что α 1. По лемме 7, P _ (0) = 0 для всех α, β 1, и P × G_ 7 1. I= 0 для всех α, β 1. Если β = 0, то в силу леммы 4 для всякого выбора α компонент будет две. Следовательно, в данном случае вклад в N1 имеет вид PQ - m-2 fQ 1\f R \ . k k=0 m - 2 - k Далее рассмотрим случай, когда ни одна из p хорд не выбрана. Тогда α + β = m, причем α 1. Значит, передвигая при необходимости отмеченную точку (что не влияет на число компонент 108 М. В. КРИСМАН границы), мы можем добиться того, что косой характеристический многочлен линейно упорядоченного графа имеет вид (P _ (x))2 · P _ _ (x) для всех α 1,β 0. Мы получим ровно две Kβ Kα·Kα компоненты в точности, когда β является четным, а α 1. Таким образом, вклад в N1 имеет вид m-1 - 2 f R \f Q 1 \ Q . 2k k=0 m - 1 - 2k Аналогично, вклад в N1 в случае выбора неориентированного разведения среди r хорд имеет вид m-1 PR m-2 fR - 1\f Q - \ 2 f Q \f R 1 \ + R . k k=0 m - 2 - k 2k k=0 m - 1 - 2k Складывая эти вклады и учитывая четность m, получаем искомую формулу. Теорема доказана. 2. НЕКОТОРЫЕ ВОПРОСЫ И ЗАДАЧИ В заключение приведем список открытых вопросов о косых спектрах виртуальных узлов. Автор посвятил некоторое время их изучению, но не достиг существенных успехов. Автор выражает надежду, что данный список приведет к более глубокому изучению этих вопросов. 1. Верно ли, что для всякого частичного состояния S гауссовой диаграммы D его косой спектр определяется косым спектром вполне ориентированного состояния? 2. Верно ли, что для всякого частичного состояния S гауссовой диаграммы D, в котором есть хотя бы одно неориентированное разведение, линейно упорядоченный граф двулистного накрытия может быть восстановлен по операциям на линейно упорядоченном графе G D ? 3. Как соотношения возникают в косых спектрах линейно упорядоченных графов для гауссовых диаграмм, связанных с соотношениями теорий узлов (например, с движениями Рейдемейстера, шестичленными соотношениями, четырехчленными соотношениями)? 4. Каков ответ на вопрос (j, m) для других бесконечнопараметрических семейств виртуальных узлов? 5. Ответы на вопрос (j, m) будут представлять собой линейные комбинации обобщенных гипергеометрических функций; Мы также знаем, что связанные с узлами многочлены и инварианты конечного типа подсчитывают число определенных поддиаграмм гауссовых диаграмм. Существуют ли гипергеометрические равенства, которые могут быть извлечены из этих вычислительных принципов, рейдемейстеровской эквивалентности и мутаций? 6. (В. О. Мантуров) Какие комбинаторные формулы могут быть определены на графах пересечений (или на спектрах графов) для последующей интеграции до инвариантов конечного типа свободных узлов?