Граф-зацепления: нереализуемость, ориентация и полином Джонса

Аннотация

Данная работа посвящена граф-зацеплениям с многими компонентами и состоит из двух частей. В первой части работы мы классифицируем вершины меченого графа по их принадлежности компонентам граф-зацепления. На основе этой классификации мы строим инвариант графзацеплений. Этот инвариант показывает, что меченый второй граф Буше порождает нереализуемое граф-зацепление. Во второй части работы мы вводим понятие ориентированного граф-зацепления. Для ориентированного граф-зацепления мы определяем число закрученности и, нормируя с его помощью скобку Кауфмана, получаем инвариант ориентированных граф-зацеплений - полином Джонса.

Полный текст

1. ВВЕДЕНИЕ Рассмотрим сначала следующий вопрос. Пусть дана диаграмма виртуального узла, т. е. погруженный в плоскость (погружение фиксировано) 4-валентный граф, каждая вершина которого снабжена крестовой структурой и структурой прохода-перехода. Вопрос состоит в следующем: Как много информации мы должны знать об этой диаграмме, чтобы определить для нее скобку Кауфмана или полином Джонса? Оказывается, что вышеназванные полиномы можно получить, лишь зная граф пересечений гауссовой диаграммы (все определения см. ниже) и число закрученности каждого классического перекрестка. Таким образом, информацию о право-лево, которая задается с помощью стрелок на гауссовой диаграмме, оказывается лишней при определении скобки Кауфмана и полинома Джонса. Отметим, что если мы забудем о числе закрученности и будем иметь только крестовую структуру (структуру противоположности ребер), мы получим нетривиальные объекты (с точностью до движений Рейдемейстера) (см. [21]). Вероятно, самый легкий и наглядный пример, показывающий, как получить информацию об узле из его графа пересечений, - это формула, позволяющая найти количество окружностей в состояниях скобки Кауфмана из графа пересечений, а точнее, из его матрицы смежности [7, 11, 23, 26, 29] (количество окружностей равно корангу матрицы смежности плюс один, см. рис. 1). В частности, это означает, что мы можем обобщить скобку Кауфмана на все графы, не обязательно соответствующие узлам (такие графы называются нереализуемыми, см. примеры ниже), причем обобщение совпадает с обычной скобкой Кауфмана в случае, если граф реализуем хордовой диаграммой. Это было отправной точкой исследования у Л. Тральди и Л. Зулли [30] (петлевые графы): они построили независимо теорию «нереализуемых графов», обладающую многими интересными свойствами теории узлов. Объекты этой теории - это классы эквивалентности (меченых) графов по «движениям Рейдемейстера» (переведенным на язык графов пересечений). Существенный недостаток такого подхода состоит в том, что он может быть применен только к узлам, а не к зацеплениям: для кодирования зацепления нужно использовать более сложные объекты, чем гауссовы диаграммы, - гауссовы диаграммы на многих окружностях. Этот подход получил дальнейшее развитие в работах Тральди [27, 28], и он позволяет кодировать не только узлы, но и зацепления с любым конечным количеством компонент с помощью меченых графов. В работах [2, 14] был предложен другой подход к обобщению узлов и зацеплений: в то время как гауссовы диаграммы соответствуют трансверсальному проходу каждого перекрестка, мы можем рассмотреть поворачивающие обходы [1, 3, 4, 13, 19]. Кроме того, мы можем закодировать тип прохода вершины (A-разведение или B-разведение), см. рис. 2. Заметим, что здесь каждая вершина еще будет иметь метку, зависящую от ориентации противоположных ребер (оснащение 0 Qc 2013 РУДН 33 34 Д. П. ИЛЬЮТКО, В. С. САФИНА 1 3 РИС. 1. Сглаживание вдоль двух хорд дает одну или три окружности. 1 5 4 12 6 3 7 13 11 2 10 8 1 14 7 3 6 4 5 9 2 8 9 14 10 13 11 12 :2-8,3-14,4-6,7-10, 11-13 :1-12,5-9 РИС. 2. Поворачивающий обход изображен тонкой линией; Хордовая диаграмма. РИС. 3. Граф, который неоднозначно представим хордовыми диаграммами. или оснащение 1). Поступая аналогично, как с гауссовыми диаграммами, мы можем определить движения на графах пересечений, соответствующие движениям на хордовых диаграммах, и затем продолжить их на все простые графы. В результате, мы получим новый объект - граф-зацепление Таким образом, имеется аналогия: переход от реализуемых гауссовых диаграмм (классических узлов) к произвольным хордовым диаграммам приводит к концепции виртуального узла, а переход от реализуемых (посредством хордовых диаграмм) графов к произвольным графам - к концепции граф-зацепления. Отметим, что при переходе от узлов к графам пересечений мы теряем некоторую информацию об узле, например, иногда гауссовы диаграммы могут быть получены из графа пересечений многими способами, см. рис. 3. Оказывается, что много информации об узле и его инвариантах можно получить из граф-зацепления. Например, можно определить число компонент граф-зацепления, которое совпадает с настоящим числом компонент зацепления в реализуемом случае, т. е. в случае, когда граф-зацепление можно реализовать некоторым зацеплением, построить аналог скобки Кауфмана. Определив число компонент граф-зацепления, мы можем выделить класс граф-зацеплений, имеющих одну компоненту, - граф-узлы. Граф-узлы в некотором смысле являются аналогом узлов в множестве зацеплений. Для граф-узла было построено число закрученности, с помощью которого был построен полный инвариант граф-узлов - полином Джонса [14]. Один из простейших инвариантов, позволяющий в некоторых случаях показать, что виртуальное зацепление не эквивалентно классическому зацеплению, - это коэффициент, аналогичный ГРАФ-ЗАЦЕПЛЕНИЯ: НЕРЕАЛИЗУЕМОСТЬ, ОРИЕНТАЦИЯ И ПОЛИНОМ ДЖОНСА 35 РИС. 4. Второй граф Буше BW3. РИС. 5. Первый граф Буше W5. коэффициенту зацепления для классических зацеплений, см. [6, 19]. Если дано виртуальное зацепление, то для каждой пары компонент мы можем найти четность числа классических перекрестков, принадлежащих обеим компонентам. Если окажется, что для некоторой пары компонент это число нечетно, то данное виртуальное зацепление не эквивалентно классическому зацеплению. В первой части работы мы переписываем условие принадлежности вершины одной или разным компонентам зацепления на языке матриц смежности графов пересечений. Оказывается, что эти условия инвариантны относительно граф-преобразований. Таким образом, мы можем классифицировать вершины граф-зацепления по принадлежности их одной или разным компонентам граф-зацепления. Далее мы классифицируем вершины, принадлежащие разным компонентам. А именно, каждый класс состоит из тех и только тех вершин, которые принадлежат разным компонентам и в которых пересекаются одни и те же две компоненты. Оказывается, что четность числа классов, состоящих из нечетного числа вершин, является инвариантом. С помощью этого инварианта мы показываем, что граф-зацепление, порожденное вторым графом Буше BW3 (см. риc. 4 и [14]), каждая вершина которого имеет оснащение 0, является нереализуемым, т. е. каждый граф данного класса не реализуем никакой хордовой диаграммой. Отметим, что нереализуемость граф-зацепления, порожденного первым графом Буше (W5, см. рис. 5 и [13]), каждая вершина которого имеет оснащение 0, была доказана с помощью четности (см. [5, 20, 21]). Вторая часть работы посвящена полиному Джонса для зацеплений со многими компонентами. Известно, что в случае узлов полином Джонса не зависит от ориентации узла, а в случае зацеплений полином Джонса строится для ориентированных зацеплений. В [14] полином Джонса был построен для граф-узлов. Для того чтобы построить полином Джонса для граф-зацеплений, мы должны сначала ввести понятие ориентированного граф-зацепления. Во второй части статьи мы сначала определяем ориентированное граф-зацепление, потом для него строим число закрученности, которое обобщает число закрученности зацепления. С помощью этого числа мы определяем полином, который является аналогом полинома Джонса. Последний полином является полным инвариантом ориентированного граф-зацепления. Благодарности. Авторы выражают благодарность В. О. Мантурову, И. М. Никонову, А. Т. Фоменко и В. В. Чернову за полезные советы и постоянное внимание к работе. Работа первого автора выполнена при частичной финансовой поддержке гранта Правительства РФ по постановлению № 220, договор 11.G34.31.0053, РФФИ (гранты № 13-01-00664а и № 12-01-31432-мол-а), программы поддержки ведущих научных школ РФ (грант № НШ1410.2012.1), программы «Научные и научно-педагогические кадры инновационной России» (госконтракт 14.740.11.0794). 36 Д. П. ИЛЬЮТКО, В. С. САФИНА Второй автор частично поддержан программой поддержки ведущих научных школ РФ (грант № НШ-1410.2012.1) и программой «Научные и научно-педагогические кадры инновационной России» (госконтракт 14.740.11.0794). 2. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ И ПОНЯТИЯ: ГРАФ-ЗАЦЕПЛЕНИЕ 1. Классические и виртуальные узлы. (Классический) узел или зацепление представляет собой образ гладкого вложения одной окружности S1 или несвязного объединения нескольких окружностей S1 ∗ ... ∗ S1 в трехмерную сферу S3 (в случае зацепления образ каждой окружности - узел - называется компонентой зацепления). Узлом (зацеплением) также называют само вложение. Основная задача теории узлов - это классификация классов изотопии узлов (зацеплений), где два узла f1, f2 : S1 → S3 (зацепления f1, f2 : S1 ∗.. .∗S1 → S3) называются изотопными, если существует изотопия Ft : S3 → S3, t ∈ [0, 1], такая, что F0 = id (тождественное отображение) и F1(f1(S1)) = f2(S1) (F1(f1(S1 ∗ ... ∗ S1)) = f2(S1 ∗ ... ∗ S1)). Отметим, что классификация узлов в S3 эквивалента классификации узлов в трехмерном евклидовом пространстве R3. В случае, если фиксирована ориентация окружности, говорят об ориентированном узле (соответственно в случае ориентированного зацепления требуется ориентация окружностей - прообразов компонент зацепления); в случае изотопии ориентированных зацеплений требуется, чтобы диффеоморфизм объемлющего пространства сохранял как ориентацию сферы, так и ориентации всех компонент. Обычно узлы (зацепления) кодируются следующим образом. Фиксируем узел (зацепление) и рассмотрим некоторую плоскость и проекцию узла (зацепления) на нее. Без ограничения общности можно считать, что проекция узла (зацепления) на плоскость представляет собой вложенный конечный четырехвалентный граф, являющийся образом гладкого погружения окружности (несвязного объединения окружностей) в плоскость. Каждая вершина графа проекции, называемая перекрестком диаграммы зацепления, снабжена структурой прохода-перехода, см. рис. 6 (ветвь, проходящая сверху, образует переход, ветвь снизу образует проход). Ребра переходов изображаются сплошными линиями, в то время как проход изображается линией, имеющей разрыв в перекрестке. Такое изображение узла (зацепления) на плоскости называется плоской диаграммой узла (зацепления). ❅ переход ❅ ❅ проход ❅ РИС. 6. Локальная структура перекрестка. Рейдемейстер [25] доказал, что любые две плоские диаграммы задают одно и то же зацепление тогда и только тогда, когда они могут быть получены друг из друга конечной последовательностью движений (впоследствии названных движениями Рейдемейстера), см. рис. 7, а также плоской изотопии. Это позволяет рассматривать изотопические классы узлов как комбинаторные объекты: они представляют собой классы эквивалентности плоских диаграмм по движениям Рейдемейстера. С другой стороны, каждую плоскую диаграмму узла можно задать в виде гауссовой диаграммы. Напомним, что гауссовой диаграммой, соответствующей плоской диаграмме, называется диаграмма, состоящая из ориентированной окружности (с фиксированной точкой, не являющейся прообразом перекрестка), на которой прообразы прохода и перехода для каждого перекрестка соединены стрелкой, направленной от прообраза перехода к прообразу прохода. Каждая стрелка снабжена знаком, который совпадает со знаком перекрестка, т. е. равен единице для перекрестка вида и минус единице для . Так, для классического правого трилистника гауссова диаграмма выглядит следующим образом: см. рис. 8. Не каждая окружность с хордами (хордовая диаграмма) может рассматриваться как гауссова диаграмма некоторого классического узла. По аналогии с движениями Рейдемейстера на плоских диаграммах мы можем определить движения на гауссовых диаграммах. Продолжим эти новые движения на все хордовые диаграммы ГРАФ-ЗАЦЕПЛЕНИЯ: НЕРЕАЛИЗУЕМОСТЬ, ОРИЕНТАЦИЯ И ПОЛИНОМ ДЖОНСА 37 1 2 3 РИС. 7. Движения Рейдемейстера Ω1, Ω2, Ω3. 2 3 + 1 2 1 + 1 + 3 2 3 РИС. 8. Гауссова диаграмма правого трилистника. (хорды ориентированы и снабжены знаком) и рассмотрим классы эквивалентности хордовых диаграмм по движениям. Точный список движений Рейдемейстера для гауссовых диаграмм можно найти в [10]. В результате мы получим новую теорию - теорию виртуальных узлов [12, 17]. Отметим, что вся информация об узле и его инвариантах может быть прочитана из любой гауссовой диаграммы, кодирующей этот узел [18]. Поскольку гауссовы диаграммы (на одной окружности) кодируют лишь диаграммы узлов, то с помощью гауссовых диаграмм мы можем определить только виртуальный узел, но не зацепление. Дадим другое определение виртуального зацепления. Пусть G - произвольный граф с множеством вершин V (G) и множеством ребер E(G). Под ребром мы будем понимать класс эквивалентности двух полуребер, которые его составляют. Вершина v ∈ V (G) имеет степень, равную k, если v инцидентна k полуребрам. Граф, все вершины которого имеют степень k, называется k-валентным или просто k-графом. Для любого k свободная петля, т. е. граф без вершин с одним циклическим ребром, рассматривается как k-граф. Определение 2.1. 4-Граф называется оснащенным или графом с крестовой структурой, если в каждой вершине графа четыре исходящих из нее полуребра разбиты на два семейства полуребер, т. е. задана структура противоположных ребер. Полуребра из одного семейства называются (формально) противоположными. 38 Д. П. ИЛЬЮТКО, В. С. САФИНА РИС. 9. Объезд. Определение 2.2. Под изоморфизмом 4-графов с крестовой структурой мы всегда будем понимать изоморфизм, сохраняющий структуру (оснащение). Обозначим через G0 4-граф, представляющий собой одну окружность. При изображении 4-графов с крестовой структурой на плоскости мы всегда предполагаем, что структура противоположных полуребер в вершинах наследуется из плоскости R2. Определение 2.3. Виртуальной диаграммой (или диаграммой виртуального зацепления) называется погружение (также и образ погружения) общего положения 4-графа с крестовой структурой в R2, у которого образ каждой вершины снабжен еще структурой классического перекрестка, т. е. указано, какая ветвь (пара противоположных ребер) проходит выше, а какая - ниже; при изображении на плоскости точки пересечения образов различных ребер оснащенного 4-графа называются виртуальными перекрестками и обозначаются кружочком. Виртуальная диаграмма называется связной, если связен соответствующий 4-граф. Виртуальное зацепление - это класс эквивалентности виртуальных диаграмм по виртуальным движениям Рейдемейстера, которые включают в себя обычные движения Рейдемейстера и движение объезда (см. рис. 9). То есть фактически для задания виртуального узла нам нужно лишь знать, как расположены классические перекрестки и как они между собой соединяются, при этом нам не важно, как расположены пути, идущие между классическими перекрестками, пересекаются ли они и имеют ли точки самопересечения. Замечание 2.1. Отметим, что такой подход - стандартные движения внутри локальной евклидовой области и движения типа объезда - был использован Н. Камадой и С. Камадой [16] для построения формальных теорий многомерных «виртуальных узлов» и их инвариантов. Подобно классическому зацеплению, виртуальное зацепление обладает некоторым количеством компонент (уникурсальных компонент). Компоненты виртуального зацепления можно описать комбинаторно, исходя из виртуальной диаграммы. Под уникурсальной компонентой диаграммы виртуального зацепления понимается следующее. Рассмотрим виртуальную диаграмму K как одномерный комплекс на плоскости. Часть связных компонент этого комплекса представляет собой окружности; каждую такую компоненту назовем (уникурсальной) компонентой зацепления. Оставшаяся часть представляет собой четырехвалентный граф Γ с вершинами в классических и виртуальных перекрестках. Уникурсальными компонентами диаграммы назовем также (помимо компонент-окружностей) классы эквивалентности на множестве ребер графа: два ребра e, e× считаются эквивалентными, если существует набор ребер e = e1,..., ek = e× и набор вершин v1,..., vk-1 (некоторые из которых, быть может, совпадают) графа K такие, что ребра ei, ei+1 подходят к вершине vi с противоположных сторон. Легко видеть, что количество компонент диаграммы зацепления является инвариантным при обобщенных движениях Рейдемейстера. В классическом случае это определение компонент зацепления согласуется с приведенным ранее. Виртуальный узел - это виртуальное зацепление с одной уникурсальной компонентой. Числом закрученности w(K) виртуальной диаграммы K называется количество положительных перекрестков минус количество отрицательных перекрестков . 2. Граф-зацепление. Любые две эквивалентные (в классе всех виртуальных диаграмм) связные (см. определение 2.3) виртуальные диаграммы являются эквивалентными в классе связных ГРАФ-ЗАЦЕПЛЕНИЯ: НЕРЕАЛИЗУЕМОСТЬ, ОРИЕНТАЦИЯ И ПОЛИНОМ ДЖОНСА 39 РИС. 10. Виртуализация. виртуальных диаграмм [14]. Поэтому, без ограничения общности, мы считаем, что все рассматриваемые виртуальные диаграммы связны и содержат по крайней мере один классический перекресток [2, 14]. Мы будем строить хордовые диаграммы не только для узлов, но и для зацеплений. Поэтому подход с помощью гауссовых диаграмм не годится. Вместо них мы будем рассматривать хордовые диаграммы, соответствующие поворачивающим обходам, причем в каждом (классическом) перекрестке мы поворачиваем с ребра на соседнее ребро. В дальнейшем, если не указано противное, все хордовые диаграммы соответствуют поворачивающим обходам. Определение 2.4. Хордовая диаграмма - это 3-граф, состоящий из выбранного неориентированного гамильтонового цикла (окружности) и неориентированных ребер (хорд), соединяющих точки на окружности, причем разные хорды не имеют общих точек на окружности. Мы назовем две хорды зацепленными, если концы одной хорды лежат в разных связных компонентах множества, полученного из S1 удалением концов другой хорды. В противном случае хорды называются незацепленными. Замечание 2.2. Хордовые диаграммы, как правило, изображаются в виде стандартной евклидовой окружности с конечным множеством ее хорд (точки пересечения хорд вершинами, конечно, не являются). Определение 2.5. Хордовая диаграмма называется меченой, если каждая хорда снабжена меткой (a, α), где a ∈ {0, 1} - оснащение хорды и α ∈ {±} - знак хорды. Если метки не указаны, то мы считаем, что все они равны (0, +). Хордовая диаграмма называется оснащенной, если каждая хорда снабжена только оснащением, т. е. 0 или 1. Пусть D - меченая хордовая диаграмма. Мы можем построить такую виртуальную диаграмму K(D) (с точностью до виртуализации, см. рис. 10), что диаграмма D совпадает с хордовой диаграммой некоторого поворачивающего обхода на K(D). Мы погружаем диаграмму D в R2, вкладывая окружность диаграммы в плоскость и размещая некоторые хорды внутри окружности, а остальные - вне. После этого мы удаляем окрестности каждого из концов всех хорд и заменяем каждую хорду парой хорд, соединяющих четыре точки на окружности, которые образовались в результате удаления двух окрестностей. При этом новые две хорды образуют только классический перекресток, если оснащение хорды равно 0, и образуют классический и виртуальный перекрестки, если оснащение хорды равно 1, см. рис. 11 (пересечения хорд из разных пар образуют всегда виртуальные перекрестки). Еще мы требуем, чтобы первоначальные части окружности соответствовали A-разведению, A : → , если хорда положительна, и B-разведению, B : → , если хорда отрицательна. Обратно, имея связную виртуальную диаграмму K, мы можем построить меченую хордовую диаграмму DC (K). Мы рассматриваем поворачивающий обход C на K (виртуальные перекрестки проходятся трансверсально) и строим оснащенную хордовую диаграмму. Знак хорды равен + (соответственно, -), если обход локально согласуется с A-разведением (соответственно, с Bразведением). Оснащение хорды зависит от ориентации противоположных полуребер при движении вдоль C (см. рис. 12). Нетрудно проверить, что эта операция обратна операции построения виртуальной диаграммы из меченой хордовой диаграммы: если мы рассмотрим хордовую диаграмму D и построим виртуальную диаграмму K(D) из нее, тогда для некоторого поворачивающего 40 Д. П. ИЛЬЮТКО, В. С. САФИНА (0,+) (0,-) (1,+) (1,-) РИС. 11. Замена хорды парой линий. (0,++)) (1,++)) (0,--)) (1,--)) РИС. 12. Замена классического перекрестка меченой хордой. обхода C меченая хордовая диаграмма DC (K(D)) будет совпадать с D. Это доказывает следующую теорему. Теорема 2.1 (см. [4]). Для любой связной виртуальной диаграммы L существует меченая хордовая диаграмма D такая, что L = K(D). Опишем движения на графах, которые получаются из движений Рейдемейстера на виртуальных диаграммах, используя поворачивающий обход [2, 14]. Эти движения соответствуют «настоящим» движениям Рейдемейстера, когда они применяются к графам, реализуемым хордовыми диаграммами. Затем мы обобщим эти движения на все графы (не только реализуемые диаграммами). В результате мы получим новый объект - граф-зацепление. Определение 2.6. Граф пересечений (см. [9]) G(D) хордовой диаграммы D - это простой граф (без петель и кратных ребер), вершины которого находятся в однозначном соответствии с хордами диаграммы D, причем две вершины соединены ребром в том и только в том случае, если соответствующие им хорды зацеплены. Назовем граф меченым, если каждая его вершина v снабжена меткой (a, α), где a ∈ {0, 1} - это оснащение вершины v, а α ∈ {±} - знак вершины v. Пусть D - меченая хордовая диаграмма. Меченый граф пересечений, ср. [9, 24], G(D) диаграммы D - это граф пересечений, каждая вершина которого снабжена соответствующей меткой. Простой граф H называется реализуемым, если существует такая хордовая диаграмма D, что H = G(D). В противном случае граф называется нереализуемым. Замечание 2.3. Мы будем еще рассматривать простые графы, каждая вершина которых имеет одну метку - 0 или 1. Назовем такие графы оснащенными. Таким образом, мы имеем два типа оснащенных графов: 4-валентные графы и простые графы. В первом случае мы будем часто говорить «граф с крестовой структурой». В реализуемом случае оснащенные графы - это графы пересечений оснащенных хордовых диаграмм. Следующая лемма очевидна. Лемма 2.1. Простой граф реализуем, если и только если каждая его компонента связности реализуема. Определение 2.7. Пусть G - произвольный граф и v ∈ V (G). Множество всех вершин графа G, смежных с v, называется окрестностью вершины v и обозначается N (v). ГРАФ-ЗАЦЕПЛЕНИЯ: НЕРЕАЛИЗУЕМОСТЬ, ОРИЕНТАЦИЯ И ПОЛИНОМ ДЖОНСА 41 u v u v u v LC(G;u) G P(G;u,v) РИС. 13. Локальное дополнение и шарнирное преобразование. Определим две операции на простых немеченых графах. Определение 2.8 (Локальное дополнение). Пусть G - произвольный граф. Локальное дополнение графа G в вершине v ∈ V (G) - это операция, которая меняет смежности только между вершинами a, b ∈ N (v) и a ±= b (остальные смежности остаются без изменений). Обозначим граф, полученный из G с помощью операции локального дополнения в вершине v, через LC(G; v). Определение 2.9 (Шарнирное преобразование). Пусть G - произвольный граф с двумя различными вершинами u и v. Шарнирное преобразование графа G в вершинах u и v - это операция, которая меняет смежности только между такими вершинами x, y, что x, y ∈/ {u, v}, x ∈ N (u), y ∈ N (v) и либо x ∈/ N (v), либо y ∈/ N (u) (остальные смежности остаются без изменений). Обозначим граф, полученный из G с помощью шарнирного преобразования в вершинах u и v, через piv(G; u, v). Пример 2.1. На рис. 13 изображены графы G, LC(G; u) и piv(G; u, v). Легко доказать следующую лемму. Лемма 2.2. Если вершины u и v смежны, то существует изоморфизм piv(G; u, v) ∼= LC(LC(LC(G; u); v); u). Определим граф-преобразования, т. е. преобразования меченых графов. Мы рассматриваем меченые хордовые диаграммы, построенные посредством поворачивающих обходов, и движения на них, которые получаются из «настоящих» движений Рейдемейстера виртуальных диаграмм. Затем мы переносим эти движения на произвольные меченые графы, используя графы пересечений хордовых диаграмм. В результате мы получим новый объект - класс эквивалентности меченых графов по формальным движениям [2, 14]. Определение 2.10. Ωg 1. Первое граф-преобразование состоит в добавлении/удалении изолированной вершины с меткой (0, α), α ∈ {±}. Ωg 2. Второе граф-преобразование состоит в добавлении/удалении двух несмежных (соответственно смежных) вершин с метками (0, ±α) (соответственно (1, ±α)), и имеющих одинаковые смежности с остальными вершинами. Ωg 3. Третье граф-преобразование определяется следующим образом. Пусть u, v, w - произвольные три вершины графа G, все имеющие метки (0, -), причем вершина u смежна только с вершинами v и w в G, а вершины v и w не смежны друг с другом. Тогда мы изменяем только смежности вершины u с вершинами v, w и t ∈ (N (v) \ N (w)) l(N (w) \ N (v)). Кроме того, мы еще меняем знаки вершин v и w на +. Обратная операция также называется третьим граф-преобразованием. Ωg 4. Четвертое граф-преобразование для графа G определяется следующим образом. Мы берем две смежные вершины u и v с метками (0, α) и (0, β) соответственно. Заменяем граф G на piv(G; u, v) и, кроме того, меняем знаки вершин u и v на -β и -α соответственно. Ωg 4×. В этом четвертом граф-преобразовании мы берем одну вершину v с меткой (1, α). Заменяем G на LC(G; v) и, кроме того, меняем знак вершины v и оснащение каждой вершины u ∈ N (v). 42 Д. П. ИЛЬЮТКО, В. С. САФИНА Замечание 2.4. Четвертые граф-преобразования Ωg 4 и Ωg 4× в реализуемом случае соответствуют замене поворачивающего обхода диаграммы зацепления другим поворачивающим обходом. Замечание 2.5. Если меченый граф G2 получен из меченого графа G1 применением одного граф-преобразования, то между вершинами графов, не «принимающих» участие в преобразовании, имеется взаимно однозначное соответствие. В случае третьего граф-преобразования мы всегда условимся считать, что вершина u графа G1 соответствует вершине u графа G2, а вершина v (соответственно w) графа G1 соответствует вершине w (соответственно v) графа G2. В случае четвертого граф-преобразования Ωg 4 мы всегда условимся считать, что вершина u графа G1 соответствует вершине v графа G2, а вершина v - вершине u графа G2. Всегда, если не оговорено противное, вершины графов Gi будем нумеровать следующим образом: вершины, не «принимающие» участие в преобразованиях, имеют одинаковые номера; добавляемые вершины при первых двух граф-преобразованиях имеют последние номера, вершины u, v, w для третьего граф-преобразования имеют номера 1, 2, 3 для G1 и соответственно 1, 3, 2 для G2, вершины u, v (соответственно вершина u) для четвертого граф-преобразования Ωg 4 (соответственно Ωg 4×) имеют номера 1, 2 (соответственно номер 1) для G1 и 2, 1 (соответственно номер 1) для G2 (т. е. соответствующие при преобразовании вершины имеют одинаковые номера). Замечание 2.6. Мы определили граф-преобразования для меченых графов. Если мы рассматриваем оснащенные графы, то для них граф-преобразования получаются из граф-преобразований Ωg 1-Ωg 4× забыванием знака, т. е. второй компоненты метки. В этом случае мы будем использовать те же самые обозначения. Сопоставление граф-преобразований с движениями Рейдемейстера приводит к следующей теореме. Теорема 2.2. Пусть G1 и G2 - два меченых графа пересечений виртуальных диаграмм K1 и K2 соответственно. Если K1 и K2 эквивалентны в классе связных диаграмм, тогда G1 и G2 получаются друг из друга последовательностью граф-преобразований Ωg 1-Ωg 4×. Определение 2.11. Граф-зацепление {G} - это класс эквивалентности меченого графа G относительно преобразований Ωg 1-Ωg 4×. Граф из {G} назовем представителем для {G}. Определение 2.12. Матрица смежности A(G) меченого графа G - это матрица (aij ) над Z2, для которой aii равно оснащению вершины vi, aij = 1, i ±= j, если и только если вершины vi и vj смежны, и aij = 0 в противном случае. Отметим, что corank (A(G1) + E) = corank (A(G2) + E), где G1, G2 ∈ {G} (см. [14]), где через corank A мы обозначаем коранг матрицы A, т. е. разность между размерностью матрицы и ее рангом (ранг считается над Z2). Определим число компонент граф-зацепления {G} как corank (A(G) + E) + 1, где E - единичная матрица. Граф-узел - это граф-зацепление с одной компонентой. Граф-зацепление называется нереализуемым, если каждый его представитель не является реализуемым графом. Отметим, что в реализуемом случае число компонент граф-зацепления совпадает с числом компонент соответствующего зацепления. 3. ПЕРЕСЕЧЕНИЕ РАЗНЫХ КОМПОНЕНТ Пусть G - меченый граф с множеством вершин V (G) = {v1,..., vn} и B(G) = A(G) + E, Bi(G) = A(G) + E + Eii, где Eii - n×n-матрица с одним ненулевым элементом, равным 1 и стоящим на пересечении i-го столбца и i-ой строки. 1. Вспомогательные результаты. Докажем некоторые леммы, которые нам понадобятся позже. Лемма 3.1. Равенство corank ( a b∗ b C \ = corank C, ГРАФ-ЗАЦЕПЛЕНИЯ: НЕРЕАЛИЗУЕМОСТЬ, ОРИЕНТАЦИЯ И ПОЛИНОМ ДЖОНСА 43 где C - симметрическая матрица, выполняется тогда и только тогда, когда вектор ( a +1 \ b линейно выражается через столбцы матрицы ( b∗ C \ ( a , а вектор b \ - нет (линейные комбинации рассматриваются над Z2, и возможен случай, когда в линейной комбина- ( a +1 \ ции участвует пустое множество столбцов, т. е. вектор b является нулевым). Замечание 3.1. Жирными буквами здесь и далее мы обозначаем векторы-столбцы. Доказательство. Импликация ⇐= очевидна. Рассмотрим импликацию =⇒ . Имеем rank ( a b∗ b C \ = rank C + 1. Если вектор b не выражается через столбцы матрицы C, то ( ) ( a b∗ rank b C = rank C +1 и rank b C \ = rank C + 2, получили противоречие. Следовательно, один из двух векторов ( a +1 \ b ( a или b \ линейно выражается через столбцы матрицы ( b∗ C \ . Но во втором случае получим, что corank ( a b∗ b C \ = corank ( 0 0∗ 0 C \ = corank C + 1, здесь и далее 0 - это вектор-столбец, состоящий из нулей. Обозначим через G \ {vi} меченый граф, полученный из G удалением вершины vi и всех ребер, инцидентных ей (метки всех остальных вершин сохраняются). Следствие 3.1. Если corank Bi(G) = corank B(G \ {vi}), то corank Bi(G) = corank B(G) - 1. Следствие 3.2. Если corank Bi(G) ±= corank B(G \ {vi}), то либо corank B(G) = corank B(G \ {vi}) = corank Bi(G) - 1, либо corank B(G) = corank Bi(G) = corank B(G \ {vi}) - 1. Доказательство. Без ограничения общности считаем, что i = 1 и ( a b∗ \ Тогда B(G) = b C . ( a +1 b∗ \ B1(G) = b C По лемме 3.1 мы имеем два случая: ( a +1 \ и B(G \ {v1}) = C. ( b∗ \ 1. Вектор b линейно выражается через столбцы матрицы C . Тогда corank B(G) = corank B(G \ {vi}) = corank Bi(G) - 1. 2. Вектор b линейно не выражается через столбцы матрицы C. Тогда corank B(G) = corank Bi(G) = corank B(G \ {vi}) - 1. 44 Д. П. ИЛЬЮТКО, В. С. САФИНА v (a,α) v K G K 1 G {v} v (a+1,α) v K2 G’ РИС. 14. Перекресток зацепления. 2. Вершины и компоненты граф-зацеплений. В данном пункте сначала мы переписываем условие принадлежности классического перекрестка зацепления одной компоненте зацепления на язык графов пересечений, а точнее, на язык матриц смежности графов пересечений, и используем новое условие для введения понятия принадлежности вершины графа одной компоненте. Затем мы проделываем то же самое для пары перекрестков, каждый из которых принадлежит разным компонентам, но при этом они оба принадлежат всего двум компонентам. Пусть v - классический перекресток виртуальной диаграммы K. Рассмотрим произвольный поворачивающий обход на диаграмме K и построим меченую хордовую диаграмму и соответствующий ей граф пересечений G, см. рис. 14 (верхний рисунок). Очевидно, что перекресток v принадлежит одной и той же компоненте тогда и только тогда, когда виртуальные диаграммы K1 и K2 (см. средний и нижний рис. 14) имеют разное число компонент. Легко видеть, что число компонент диаграммы K1 можно сосчитать по формуле corank B(G \ {v}) + 1, а K2 - по corank B(G×)+1 = corank Bi(G)+ 1, где i - номер вершины v. Используя эти числа, дадим следующее определение. Пусть дан меченый граф G с множеством вершин V (G) = {v1,..., vn}. Определение 3.1. Будем говорить, что вершина vi принадлежит одной компоненте меченого графа G, если corank Bi(G) ±= corank B(G\{vi}). В противном случае будем говорить, что вершина принадлежит разным компонентам графа G. Посмотрим, что происходит с вершинами меченого графа при применении к нему графпреобразований. Лемма 3.2. Пусть меченый граф G2 получен из меченого графа G1 применением первого граф-преобразования, при котором добавляется вершина с меткой (0, α). Тогда: 1. вершина, участвующая в преобразовании, принадлежит одной компоненте графа G2; 2. вершина графа G1 принадлежит одной компоненте тогда и только тогда, когда соответствующая ей вершина в G2 принадлежит одной компоненте. ГРАФ-ЗАЦЕПЛЕНИЯ: НЕРЕАЛИЗУЕМОСТЬ, ОРИЕНТАЦИЯ И ПОЛИНОМ ДЖОНСА 45 Доказательство. Пусть V (G1) = {v1,..., vn} и V (G2) = {v× ,..., v× }, и 1 n+1 A(G2) = ( A(G1) 0 \ 0∗ 0 , B(G2) = ( B(G1) 0 \ . 0∗ 1 1. Из определения сразу получаем n+1 corank Bn+1(G2) ±= corank B(G2 \ {v× }). Отсюда следует справедливость первого утверждения. 2. Легко видеть, что при i < n +1 два равенства corank Bi(G1) = corank B(G1 \ {vi}), i corank Bi(G2) = corank B(G2 \ {v×}) выполняются или не выполняются одновременно. Отсюда следует справедливость второго пункта утверждения. Лемма 3.3. Пусть меченый граф G2 получен из меченого графа G1 применением второго граф-преобразования, при котором добавляются две вершины. Тогда: 3. вершины графа G2, добавленные к графу G1, одновременно принадлежат либо одной компоненте, либо разным компонентам графа G2; 4. вершина графа G1 принадлежит одной компоненте тогда и только тогда, когда соответствующая ей вершина в G2 принадлежит одной компоненте. Доказательство. Пусть V (G1) = {v1,..., vn} и V (G2) = {v× ,..., v× }. Тогда 1 n+2 ⎛ A(G1) c c ⎞ ⎛ B(G1) c c ⎞ A(G2) = ⎝ c∗ a a ⎠ , B(G2) = ⎝ c∗ a a c∗ a +1 a ⎠ . c∗ a a +1 Первое утверждение очевидно. Рассмотрим теперь второе. Используя элементарные преобразования (см. также лемму 5.1 из [14]), мы получаем ⎛ B(G1) c c ⎞ ⎛ B(G1) c c ⎞ B(G2) = ⎝ c∗ a +1 a c∗ a a +1 ⎠ ⎝ c∗ a +1 a ⎠ 0∗ 1 1 ⎛ B(G1) 0 0 ⎞ ⎛ B(G1) 0 0 ⎞ ⎛ B(G1) 0 0 ⎞ ⎝ c∗ a +1 a 0∗ 1 1 ⎠ ⎝ c∗ 1 a 0∗ 0 1 ⎠ ⎝ 0∗ 1 0 ⎠ . 0∗ 0 1 Следовательно, при i < n +1 равенства corank Bi(G1) = corank B(G1 \ {vi}) и i corank Bi(G2) = corank B(G2 \ {v× }) выполняются или не выполняются одновременно. Лемма 3.4. Пусть меченый граф G2 получен из меченого графа G1 применением третьего граф-преобразования. Тогда вершина графа G1 принадлежит одной компоненте тогда и только тогда, когда соответствующая ей вершина в G2 принадлежит одной компоненте. Доказательство. Имеем ⎛ ⎜ B(G1) = ⎜ ⎝ 1 1 1 0∗ 1 1 0 a 1 0 1 b 0 a b C ∗ ∗ ⎞ ⎛ ⎟ ⎜ ⎟ , B(G2) = ⎜ ⎠ ⎝ 1 0 0 (a + b)∗ ⎞ 0 1 0 b 0 a + b 0 b 1 a a C ∗ ⎟ . ∗ ⎟ ⎠ Поскольку для любых a, b, C существует цепочка элементарных преобразований, переводящая матрицу B(G2) в матрицу B(G1) (см. доказательство леммы 5.1 из [14]), мы получаем справедливость утверждения для всех вершин с номерами i > 3. 46 Д. П. ИЛЬЮТКО, В. С. САФИНА Рассмотрим оставшиеся три вершины. Для первой вершины имеем ⎛ ⎜ B1(G2) = ⎜ 0 0 0 (a + b)∗ ⎞ 0 1 0 b∗ ⎟ ⎟ ⎛ 0 1 1 0∗ ⎜ 1 1 0 a∗ ⎜ ⎞ ⎟ ⎟ = B (G ), ⎝ 0 0 1 a∗ ⎠ ⎝ 1 0 1 b∗ ⎠ 1 1 a + b b a C т. е. corank B1(G1) = corank B1(G2). 0 a b C 1 1 Далее, матрицы B(G1\{v1}) и B(G2\{v× }) равны с точностью до перестановки строк и столбцов, т. е. corank B(G1 \ {v1}) = corank B(G2 \ {v× }). Отсюда следует справедливость утверждения для первой вершины. Для второй вершины имеем ⎛ 1 1 1 0∗ ⎞ ⎛ 1 0 0 0∗ ⎞ ⎜ B2(G1) = ⎜ ⎝ ⎟ 1 0 0 a 1 0 1 b 0 a b C 0 1 1 a 0 1 0 b 0 a b C ∗ ⎟ ⎜ ∗ ⎟ , ∗ ⎟ ⎜ ∗ ⎠ ⎝ ⎠ ⎛ ⎜ B2(G2) = ⎜ ⎝ 1 0 0 (a + b)∗ ⎞ 0 0 0 b 0 0 1 a ∗ ⎟ ∗ ⎟ ⎠ a + b b a C ⎛ 0 0 1 0∗ ⎞ 0 0 0 b 1 0 1 a ⎜ ∗ ⎟ ⎜ ∗ ⎟ ⎝ ⎠ 0 b a C ⎛ 0 0 1 0∗ ⎞ ⎛ 1 0 0 0∗ ⎞ ⎜ 0 0 0 b∗ ⎟ ⎜ 0 1 0 0∗ ⎟ , т. е. ⎝ ⎠ ⎝ ⎜ 1 0 0 0∗ ⎟ 0 b 0 C ⎠ ⎜ 0 0 0 b∗ ⎟ 0 0 b C Далее, ⎛ corank B2(G1) = corank ⎝ 1 1 a∗ 1 0 b∗ a b C ⎞ ⎠ , corank B2(G2) = corank ( 0 b∗ \ b C . ⎛ 1 1 0∗ ⎞ ⎛ 1 0 0∗ ⎞ B(G1 \ {v2}) = ⎝ 1 1 b∗ 0 b C ⎠ ⎝ 0 0 b∗ ⎠ , 0 b C ⎛ 1 0 (a + b)∗ ⎞ ⎛ 1 1 a∗ ⎞ т. е. 2 B(G2 \ {v× }) = ⎝ 0 1 a∗ a + b a C ⎠ ⎝ 1 0 b∗ ⎠ . a b C 2 corank B2(G1) = corank B(G2 \ {v× }), corank B2(G2) = corank B(G1 \ {v2}). Отсюда следует справедливость утверждения для второй вершины. Третья вершина рассматривается аналогично второй вершине. Лемма 3.5. Пусть меченый граф G2 получен из меченого графа G1 применением четвертого граф-преобразования. Тогда вершина графа G1 принадлежит одной компоненте тогда и только тогда, когда соответствующая ей вершина в G2 принадлежит одной компоненте. Доказательство. 1. Рассмотрим преобразование Ωg 4. Имеем ⎛ 1 1 0∗ 1∗ 0∗ 1∗ ⎞ ⎜ 1 1 0∗ 0∗ 1∗ 1∗ ⎟ ⎜ 1 ⎜ , ⎟ ⎟ B(G ) = ⎜ 0 0 B0 A1 A2 A3 ⎟ 1 ⎜ 1 0 A∗ ⎜ B4 A5 A6 ⎟ A ⎟ 2 5 ⎝ 0 1 A∗ ∗ B7 A8 ⎠ 3 A A 6 8 1 1 A∗ ∗ ∗ B9 ГРАФ-ЗАЦЕПЛЕНИЯ: НЕРЕАЛИЗУЕМОСТЬ, ОРИЕНТАЦИЯ И ПОЛИНОМ ДЖОНСА 47 ⎛ 1 1 0∗ 0∗ 1∗ 1∗ ⎞ ⎜ 1 1 0∗ 1∗ 0∗ 1∗ ⎟ 2 ⎜ , ⎟ B(G ) = ⎜ 0 0 B0 A1 A2 A3 ⎟ ⎜ 1 ⎟ B4 A5 + (1) A6 + (1) A∗ + (1) 5 B7 A8 + (1) ⎜ 0 1 A∗ ⎟ ⎜ ⎟ 1 0 A∗ ⎝ 2 ⎠ 1 1 A3 A6 + (1) A8 + (1) B9 ∗ ∗ ∗ где через (1) обозначена матрица соответствующего размера, состоящая из единиц. Поскольку существует цепочка элементарных преобразований, переводящая матрицу B(G2) в матрицу B(G1) (см. лемму 5.1 из [14]), мы получаем справедливость утверждения для всех вершин с номерами i > 2. Рассмотрим оставшиеся две вершины. Мы рассмотрим только первую (вторая рассматривается аналогично). Имеем ⎛ 0 1 0∗ 1∗ 0∗ 1∗ ⎞ 1 0∗ 0∗ 1∗ 1∗ ⎟ ⎜ 1 1 0∗ 1∗ 0∗ 1∗ 0 B0 A1 A2 A3 ⎟ ⎜ 0 0 B0 A1 A2 A3 ⎜ 1 ⎛ 0 1 0∗ 0∗ 0∗ 0∗ ⎞ ⎟ ⎜ 0 B1(G1) = ⎜ ⎟ ⎟ ⎜ ⎟ , ⎜ 1 0 A∗ ⎜ 1 1 A∗ ⎟ ⎟ ⎜ 1 B4 A5 A6 ⎟ ⎜ 1 A ⎜ ⎟ ⎜ B4 A5 + (1) A6 + (1) ⎟ A ⎟ 2 2 5 ⎝ 0 1 A∗ ∗ B7 A8 ⎠ ⎝ 0 0 A∗ 5 ∗ + (1) B7 A8 + (1) ⎠ 1 1 A∗ A∗ A∗ B9 1 1 A∗ A∗ + (1) A∗ + (1) B9 3 6 8 3 6 8 ⎛ 0 1 0∗ 0∗ 1∗ 1∗ 1 0∗ 1∗ 0∗ 1∗ ⎟ ⎜ 1 1 0∗ 0∗ 1∗ 1∗ 0 B0 A1 A2 A3 ⎟ ⎜ 0 0 B0 A1 A2 A3 ⎜ 1 ⎞ ⎛ 0 1 0∗ 0∗ 0∗ 0∗ ⎞ ⎟ ⎜ 0 B1(G2) = ⎜ ⎟ ⎟ ⎜ ⎟ , ⎜ 0 1 A∗ ⎟ ⎜ 0 1 A∗ ⎟ ⎜ 1 B4 A5 + (1) A6 + (1) ⎟ ⎜ ⎟ ⎜ 1 B4 A5 A6 ⎟ A ⎜ ⎟ 2 5 ⎝ 1 0 A∗ A∗ + (1) B7 A8 + (1) ⎠ 2 5 ⎝ 1 0 A∗ ∗ B7 A8 ⎠ 1 1 A3 A6 + (1) A8 + (1) B9 1 1 A3 A6 A8 B9 ∗ ∗ ∗ ⎛ 1 0∗ 0∗ 1∗ 1∗ ⎞ ∗ ∗ ∗ ⎜ 0 B0 A1 A2 A3 ⎟ B(G1 \ {v1}) = ⎜ 0 A∗ B4 A5 A6 ⎟ , ⎜ 1 ⎟ A ⎜ ⎟ 2 5 ⎝ 1 A∗ ∗ B7 A8 ⎠ 1 A3 A6 A8 B9 ∗ ∗ ∗ ⎛ 1 0∗ 1∗ 0∗ 1∗ ⎞ ⎜ 0 B0 A1 A2 A3 ⎟ B(G2 \ {v× }) = ⎜ 1 A∗ B4 A5 + (1) A6 + (1) ⎟ , 1 ⎜ 1 ⎟ ⎜ ⎟ 2 5 ⎝ 0 A∗ A∗ + (1) B7 A8 + (1) ⎠ т. е. 3 1 A∗ A 8 6 ∗ + (1) A∗ + (1) B9 1 corank B1(G1) = corank B(G2 \ {v× }), corank B1(G2) = corank B(G1 \ {v1}). Отсюда следует справедливость утверждения для первой вершины. 2. Рассмотрим преобразование Ωg 4×. Имеем ⎛ 0 0∗ 1∗ ⎞ ⎛ 0 0∗ 1∗ ⎞ B(G1) = ⎝ 0 A0 A1 ⎠ , B(G2) = ⎝ 0 A0 A1 ⎠ . 1 1 A∗ A2 1 1 A∗ A2 + (1) Справедливость утверждения для вершин с номерами i > 1 очевидна. Рассмотрим только первую вершину. Имеем ⎛ 1 0∗ 1∗ ⎞ ⎛ 1 0∗ 0∗ ⎞ B1(G1) = ⎝ 0 A0 A1 ⎠ ⎝ 0 A0 A1 ⎠ , 1 1 A∗ A2 1 1 A∗ A2 + (1) ⎛ 1 0∗ 1∗ ⎞ ⎛ 1 0∗ 0∗ ⎞ B1(G2) = ⎝ 0 A0 A1 ⎠ ⎝ 0 A0 A1 ⎠ , 1 1 A∗ A2 + (1) 1 1 A∗ A2 48 Д. П. ИЛЬЮТКО, В. С. САФИНА ( A0 A1 \ ( A0 A1 \ т. е. B(G1 \ {v1}) = A∗ 1 A2 1 , B(G2 \ {v× }) = A 1 ∗ A2 + (1) , 1 corank B1(G1) = corank B(G2 \ {v× }), corank B1(G2) = corank B(G1 \ {v1}). Отсюда следует справедливость утверждения для первой вершины. Рассмотрим теперь взаимное расположение двух вершин меченого графа. Определение 3.2. Рассмотрим две вершины vi и vj меченого графа G, принадлежащие разным компонентам. Будем говорить, что в этих вершинах пересекаются две компоненты (или эти вершины лежат на одних и тех же компонентах), если либо vi = vj, либо vi принадлежит одной компоненте графа G \ {vj }, т. е. corank Bi(G \ {vj }) ±= corank B(G \ {vj, vi}) при i < j или corank Bi-1(G \ {vj }) ±= corank B(G \ {vj, vi}) при i > j. В противном случае будем говорить, что в вершинах пересекаются разные компоненты. Обозначим через C i,j,...,k (соответственно, C i,j,...,k ) матрицу, полученную из матрицы C удалением столбцов (соответственно, строк) с номерами i, j,..., k. Вместо B-(G) будем писать B (G). Лемма 3.6. Пусть B(G) = ( b1 b2 C ) . В вершинах v1 и v2 пересекаются разные компоненты тогда и только тогда, когда векторы b1 и b2 линейно выражаются через столбцы матрицы C. Доказательство. Пусть ⎛ B(G) = ⎝ 5. b d∗ ⎞ 6. c e∗ ⎠ , d e F ⎛ a ⎞ и вершины v1 и v2 принадлежат разным компонентам, т. е., используя лемму 3.1, вектор ⎝ b ⎠ d ⎛ b d∗ ⎞ ⎛ a +1 ⎞ линейно выражается через столбцы матрицы ⎝ c e∗ ⎠ , а вектор ⎝ ⎛ b ⎞ e F ⎛ a d∗ ⎞ b ⎠ - нет, и вектор d ⎛ b ⎞ ⎝ c ⎠ линейно выражается через столбцы матрицы ⎝ e b e∗ d F ⎠ , а вектор ⎝ c +1 ⎠ - нет (все e вычисления производятся над Z2). (=⇒) Пусть в вершинах v1 и v2 пересекаются разные компоненты. Тогда corank B1(G \ {v2}) = corank B(G \ {v1, v2}), ( a и по лемме 3.1 вектор d \ линейно выражается через столбцы матрицы ( d∗ F \ . Тогда век- ( b \ ( d∗ \ ⎛ b ⎞ тор e линейно выражается через столбцы матрицы F . Поскольку вектор ⎝ c +1 ⎠ e ⎛ d∗ ⎞ линейно не выражается через столбцы матрицы ⎝ e∗ F (⇐=) Сразу следует из леммы 3.1. ⎠ , то мы получаем требуемое. Лемма 3.7. Пусть в вершинах vi и vj, i < j, пересекаются две компоненты. Тогда corank Bj-1(G \ {vi}) = corank Bi(G \ {vj }). Доказательство. Без ограничения общности будем считать, что i = 1 и j = 2. Имеем ⎛ B(G) = ⎝ 7. b d∗ ⎞ 8. c e∗ ⎠ . d e F ГРАФ-ЗАЦЕПЛЕНИЯ: НЕРЕАЛИЗУЕМОСТЬ, ОРИЕНТАЦИЯ И ПОЛИНОМ ДЖОНСА 49 По леммам 3.1 и 3.6, сумма векторов ⎛ a ⎞ ⎝ b ⎠ и d ⎛ b ⎞ ⎝ c ⎠ линейно выражается через столбцы e ⎛ d∗ ⎞ матрицы ⎝ e∗ F ⎠ . Совершая элементарные преобразования, получаем corank Bj-1(G \ {vi}) = corank ( c +1 e∗ e F ( a +1 d∗ \ = corank \ ( b +1 e∗ \ d F = = corank d F = corank Bi(G \ {vj }). Лемма 3.8. Отношение, порожденное «пересечением двух компонент», является отношением эквивалентности. Доказательство. 1. Рефлексивность, т. е. то, что отношение имеет место, когда две вершины совпадают, очевидна. 9. Симметричность (если в вершинах vi и vj пересекаются две компоненты, то и в вершинах vj и vi пересекаются две компоненты) сразу следует из леммы 3.7. 10. Транзитивность. Покажем, что, если vi и vj лежат на одних и тех же компонентах, vj и vk лежат на одних и тех же компонентах, то vi и vk лежат на одних и тех же компонентах. Без ограничения общности будем считать, что (i, j, k) = (1, 2, 3). Пусть ⎛ ⎜ B(G) = ⎜ ⎝ a b c b d e c k e l f m k∗ ⎞ ⎟ l∗ ⎟ = ( p p m∗ ⎠ 1 2 Q p3 Q ) . Поскольку вершины vs, s = 1, 2, 3, лежат на разных компонентах, то векторы ps линейно выражаются через столбцы матрицы B s(G). Пусть в вершинах v1 и v3 пересекаются разные компоненты. Тогда по лемме 3.6 векторы p1 и p3 линейно выражаются через столбцы матрицы B 1,3(G). Если вектор p1 (соответственно вектор p3) линейно выражается через столбцы матрицы B 1,2,3(G), то вектор p2 линейно выражается через столбцы матрицы B 1,2(G) (соответственно матрицы B 2,3(G)). Таким образом, в вершинах v1 и v2 (соответственно в вершинах v2 и v3) пересекаются разные компоненты. Получили противоречие с тем, что в вершинах v1 и v2 (соответственно в вершинах v2 и v3) пересекаются две компоненты. Пусть векторы p1 и p3 линейно не выражаются через столбцы матрицы B 1,2,3(G). Тогда вектор p1 + p3 линейно выражается через столбцы матрицы B 1,2,3(G) (линейные комбинации берутся над Z2), а вектор p2 линейно выражается через столбцы матрицы B 1,2(G) или B 2,3(G), но не выражается через столбцы матрицы B 1,2,3(G). В первом случае, т. е. когда вектор p2 линейно выражается через столбцы матрицы B 1,2(G), получим, что в вершинах v1 и v2 пересекаются разные компоненты, а во втором случае - что в вершинах v2 и v3 пересекаются разные компоненты. Посмотрим как граф-преобразования влияют на пары вершин. Лемма 3.9. Пусть меченый граф G2 получен из меченого графа G1 применением первого граф-преобразования, при котором добавляется вершина с меткой (0, α). Тогда в двух вершинах графа G1, принадлежащих разным компонентам, пересекаются две компоненты тогда и только тогда, когда в соответствующих двух вершинах графа G2 пересекаются две компоненты. Доказательство. Мы знаем (см. лемму 3.2), что при первом граф-преобразовании в добавляемой вершине пересекается одна компонента, и соответствующие при этом преобразовании вершины графов G1 и G2 одновременно принадлежат одной или разным компонентам. 50 Д. П. ИЛЬЮТКО, В. С. САФИНА Пусть V (G1) = {v1,..., vn}, V (G2) = {v× ,..., v× } и A(G2) = 1 ( A(G1) 0 \ 0∗ 0 n+1 , B(G2) = ( B(G1) 0 \ . 0∗ 1 Предположим, что вершины vi, vj, i > j, принадлежат разным компонентам. Тогда очевидно, что равенство corank Bj (G1 \ {vi}) = corank B(G1 \ {vi, vj }) равносильно равенству corank Bj (G2 \ {v× }) = corank B(G2 \ {v×, v× }). Отсюда получаем утверждение леммы. i i j Лемма 3.10. Пусть меченый граф G2 получен из меченого графа G1 применением второго граф-преобразования, при котором добавляются две вершины. Тогда в двух вершинах графа G1, принадлежащих разным компонентам, пересекаются две компоненты тогда и только тогда, когда в соответствующих двух вершинах графа G2 пересекаются две компоненты. Кроме того, если две добавляемые вершины в графе G2, принадлежат разным компонентам, то в них пересекаются две компоненты. Доказательство. Пусть V (G1) = {v1,..., vn} и V (G2) = {v× ,..., v× }. Тогда 1 n+2 ⎛ A(G1) c c ⎞ ⎛ B(G1) c c ⎞ A(G2) = ⎝ c∗ a a ⎠ , B(G2) = ⎝ c∗ a a c∗ a +1 a ⎠ . c∗ a a +1 Мы знаем (см. лемму 3.3), что добавляемые при втором граф-преобразовании вершины одновременно либо принадлежат одной компоненте, либо разным, и соответствующие при этом преобразовании вершины графов G1 и G2 также одновременно принадлежат одной или двум компонентам. Справедливость первого утверждения, т. е. равносильность равенств corank Bj (G1 \ {vi}) = corank B(G1 \ {vi, vj }), corank Bj (G2 \ {v×}) = corank B(G2 \ {v×, v× }), i i j где vi, vj, i < j < n + 1, принадлежат разным компонентам, легко следует из преобразований, приведенных в лемме 3.3. Докажем второе утверждение (про добавляемые вершины). Имеем n+1 corank Bn+1(G2) = corank B(G2 \ {v× n+2 }) ⇐⇒ corank Bn+2(G2) = corank B(G2 \ {v× }) ⇐⇒ ⎛ B(G1) c c ⎞ ( B(G ) c \ ⇐⇒ corank ⎝ c∗ a +1 a ⎠ = corank c∗ a a 1 , c∗ a +1 n+1 так как вершины v× , v × n+2 принадлежат разным компонентам. Поскольку ⎛ B(G1) c c ⎞ ⎛ B(G1) 0 c ⎞ ⎝ c∗ a +1 a ⎠ ⎝ c∗ a a то 0∗ 1 0 ⎠ , c∗ 0 a corank ( B(G1) c c∗ a \ = corank ( B(G1) c \ . c∗ a +1 Отсюда следует, что вектор-столбец c линейно не выражается через столбцы матрицы B(G1). Если бы он выражался, то первая матрица была бы эквивалентна матрице ( B(G1) 0 \ , 0∗ d а вторая - ( B(G1) 0 \ . 0∗ d +1 Получаем противоречие. Следовательно, поскольку матрицы у нас симметрические, ранг матрицы ( B(G1) c \ c∗ a ГРАФ-ЗАЦЕПЛЕНИЯ: НЕРЕАЛИЗУЕМОСТЬ, ОРИЕНТАЦИЯ И ПОЛИНОМ ДЖОНСА 51 больше ранга матрицы B(G1) как минимум на два, т. е. corank ( B(G1) c c∗ a \ ±= corank B(G1) ⇐⇒ n+2 ⇐⇒ corank Bn+1(G2 \ {v× n+1 }) ±= corank B(G2 \ {v× , v × n+2 }). Лемма 3.11. Пусть меченый граф G2 получен из меченого графа G1 применением третьего граф-преобразования. Тогда в двух вершинах графа G1, принадлежащих разным компонентам, пересекаются две компоненты тогда и только тогда, когда в соответствующих двух вершинах графа G2 пересекаются две компоненты. Доказательство. Пусть V (G1) = {v1,..., vn} и V (G2) = {v× ,..., v× }. Имеем 1 n ⎛ ⎜ B(G1) = ⎜ ⎝ 1 1 1 0∗ 1 1 0 a 1 0 1 b 0 a b C ∗ ∗ ⎞ ⎛ ⎟ ⎜ ⎟ , B(G2) = ⎜ ⎠ ⎝ 1 0 0 (a + b)∗ ⎞ 0 1 0 b 0 a + b 0 b 1 a a C ∗ ⎟ . ∗ ⎟ ⎠ Используя лемму 3.8, утверждение леммы для пар вершин (v1, vi), (v2, vi), (v3, vi), (vi, vj ) при i, j > 3, доказываем аналогично лемме 3.4. Рассмотрим оставшиеся случаи. Из-за симметрии достаточно рассмотреть следующие две пары: (v1, v2), (v2, v3). Мы рассмотрим только одну пару, вторая рассматривается аналогично. Рассмотрим пару (v1, v2). Надо показать, что равенства (надо следить за нумерацией вершин в новом графе) corank B1(G1 \ {v1}) = corank B(G1 \ {v1, v2}) и corank B1(G2 \ {v× }) = corank B(G2 \ {v× , v× }) выполняются или не выполняются одновременно. 1 1 2 ⎛ 1 ⎞ По лемме 3.6 первое равенство выполняется тогда и только тогда, когда векторы и ⎜ 1 ⎟ ⎜ ⎟ 1 ⎝ ⎠ 0 ⎛ 1 ⎞ ⎛ 1 0∗ ⎞ ⎜ 1 ⎟ линейно выражаются через столбцы матрицы ⎜ 0 a∗ ⎟ . Прибавляя вторую и третью ⎜ ⎟ ⎜ 0 ⎝ ⎠ ⎝ a ⎠ 1 b∗ ⎟ b C ⎛ 1 ⎞ ⎛ 0 ⎞ строку к первой строке, мы получим, что векторы ⎜ 1 ⎟ и ⎜ 1 ⎟ линейно выражаются через ⎜ ⎟ ⎜ ⎟ 1 0 ⎝ ⎠ ⎝ ⎠ 0 a ⎛ 0 (a + b)∗ ⎞ ⎛ 1 ⎞ ⎛ 0 ⎞ ⎛ 0 ⎞ столбцы матрицы ⎜ 0 a∗ ⎟ . Прибавляя к вектору ⎜ 1 ⎟ векторы ⎜ 1 ⎟ и ⎜ 0 ⎟ и ⎝ ⎠ ⎜ 1 b∗ ⎟ b C ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ 1 0 1 ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ 0 a b меняя местами вторую и третью строки, получим, что векторы ⎛ 1 ⎞ и ⎜ 0 ⎟ ⎜ ⎟ 0 ⎝ ⎠ a + b ⎛ 0 ⎞ ⎜ 0 ⎟ ⎜ ⎟ 1 ⎝ ⎠ a линейно ⎛ ⎜ выражаются через столбцы матрицы ⎜ ⎝ 0 (a + b)∗ 1 b∗ 0 a∗ b C ⎞ ⎟ ⎟ . Последнее условие по лемме 3.6 равно- ⎠ сильно второму равенству. Поскольку везде были совершены равносильные переходы, мы получаем справедливость утверждения. 52 Д. П. ИЛЬЮТКО, В. С. САФИНА Лемма 3.12. Пусть меченый граф G2 получен из меченого графа G1 применением четвертого граф-преобразования. Тогда в двух вершинах графа G1, принадлежащих разным компонентам, пересекаются две компоненты тогда и только тогда, когда в соответствующих двух вершинах графа G2 пересекаются две компоненты. Доказательство. Пусть V (G1) = {v1,..., vn} и V (G2) = {v× ,..., v× }. 1 n 11. Рассмотрим преобразование Ωg 4. Имеем ⎛ 1 1 0∗ 1∗ 0∗ 1∗ ⎞ ⎜ 1 1 0∗ 0∗ 1∗ 1∗ ⎟ ⎜ 1 ⎜ B(G ) = ⎜ 0 0 B0 A1 A2 A3 ⎟ ⎟ ⎟ = ( b1 b2 C ) , 1 ⎜ 1 0 A∗ ⎜ B4 A5 A6 ⎟ A ⎟ 2 5 ⎝ 0 1 A∗ ∗ B7 A8 ⎠ 3 A A 6 8 1 1 A∗ ∗ ∗ B9 ⎛ 1 1 0∗ 0∗ 1∗ 1∗ ⎞ ⎜ 1 1 0∗ 1∗ 0∗ 1∗ ⎟ ⎜ 2 ⎜ A B(G ) = ⎜ 0 0 B0 A1 A2 A3 ⎟ ⎟ ⎟ = ( b2 b1 C ) , ∗ 0 1 1 0 1 1 ⎜ 1 B4 A5 + (1) A6 + (1) ⎟ A A ⎜ ⎟ ∗ ∗ ⎝ 2 5 + (1) B7 A8 + (1) ⎠ A∗ A∗ + (1) A∗ + (1) B9 3 6 8 здесь и далее 1 - это вектор-столбец, состоящий из единиц. Справедливость утверждения для пар вершин (v1, vi), (v2, vi), (vi, vj ), i, j > 3, доказывается аналогично лемме 3.5 (мы пользуемся тем фактом, что отношение, порожденное «пересечением двух компонент», является отношением эквивалентности, см. лемму 3.8). Осталось рассмотреть пару (v1, v2). Пусть вершины v1 и v2 лежат на разных компонентах. Используя лемму 3.1 и элементарные преобразования над строками, легко показать, что вектор b1 линейно выражается через столбцы матрицы C тогда и только тогда, когда вектор b2 линейно выражается через столбцы матрицы C . 12. Рассмотрим преобразование Ωg 4×. Доказательство этого пункта полностью аналогично доказательству пункта 2 леммы 3.5. 3. Инвариант и графы Буше. Пусть G - меченый граф. На множестве вершин, принадлежащих разным компонентам, рассмотрим отношение эквивалентности, порожденное «пересечением двух компонент». Обозначим через ϑ(G) число классов эквивалентности, имеющих нечетное число элементов. Из лемм 3.9, 3.10, 3.11 и 3.12 следует следующая теорема. Теорема 3.1. Число ϑ(G) инвариантно при граф-преобразованиях, т. е. является инвариантом граф-зацеплений. Пример 3.1. Рассмотрим второй граф Буше BW3 (см. рис. 4) и снабдим каждую вершину оснащением 0 (знаки вершин нас не интересуют). Рассмотрим граф-зацепление, порожденное этим графом. Легко показать, что данное граф-зацепление содержит четыре компоненты и ϑ(BW3) = 7. Легко видеть, что для любого виртуального зацепления с числом компонент, равным 4, инвариант ϑ строго меньше семи. Таким образом, мы получаем, что данное граф-зацепление нереализуемо. Замечание 3.2. Отметим, что нереализуемость граф-зацепления, порожденного третьим графом Буше W7 (см. рис. 15), у которого все вершины, кроме центральной, имеют оснащение 0, доказывается с помощью четности [5, 20, 21] и эквивалентности из [13]. 4. ОРИЕНТАЦИЯ НА ГРАФ-ЗАЦЕПЛЕНИЯХ И ПОЛИНОМ ДЖОНСА В данном разделе мы определяем ориентированное граф-зацепление. Для ориентированных граф-зацеплений мы строим число закрученности, которое в реализуемом случае совпадает с настоящим числом закрученности зацепления. С помощью этого числа мы подправляем скобку Кауфмана (см. [2, 14]) и получаем полином Джонса. ГРАФ-ЗАЦЕПЛЕНИЯ: НЕРЕАЛИЗУЕМОСТЬ, ОРИЕНТАЦИЯ И ПОЛИНОМ ДЖОНСА 53 РИС. 15. Третий граф Буше W7. 1. Удаление вершин из графа. Сформулируем леммы, показывающие, как меняются ранги и коранги матриц смежности при удалении вершин из графа. В дальнейшем эти леммы помогут нам корректно определить число закрученности для граф-зацепления. Пусть G - меченый граф с множеством вершин V (G) = {v1,..., vn}. Лемма 4.1. Пусть вершина vi графа G принадлежит разным компонентам. Тогда существует граф Gcs(vi) ∈ {G}, полученный из графа G четвертыми граф-преобразованиями, i такой, что вершина v× графа Gcs(vi), соответствующая вершине vi, имеет знак, протиi воположный знаку sgn(vi) вершины vi. Кроме того, если вершина vi принадлежит разным компонентам, то и вершина v× принадлежит разным компонентам. Доказательство. Если вершина принадлежит разным компонентам, то по лемме 3.2 к ней нельзя применить первое граф-преобразование. Рассмотрим четыре случая. i 1. Пусть оснащение вершины vi равно 1. Тогда мы применяем к этой вершине четвертое графпреобразование Ωg 4× и сразу получаем вершину v× . 2. Пусть оснащение вершины vi равно 0 и есть смежная с ней вершина, имеющая оснащение 0. i Тогда мы применяем четвертое граф-преобразование Ωg 4 и сразу получаем вершину v×. 3. Пусть оснащение вершины vi равно 0 и есть смежная с ней вершина vj, имеющая оснащение 1. Тогда мы применяем сначала четвертое граф-преобразование Ωg 4× к вершине vj, i а потом это же преобразование к вершине, соответствующей вершине vi, чтобы получить вершину v× . 4. Пусть vi - изолированная вершина с оснащением 0. В этом случае вершина vi принадлежит одной компоненте, и мы получаем противоречие с условием леммы. Второе утверждение леммы сразу следует из леммы 3.5. Лемма 4.2. Пусть вершина vk ∈ V (G) принадлежит разным компонентам. 1. Если в двух вершинах vi и vj, i, j ±= k, пересекаются две компоненты графа G, то в графе G \ {vk } вершины, соответствующие вершинам vi и vj, либо принадлежат одной компоненте, либо в них опять пересекаются две компоненты. 2. Пусть вершина vi, i < k, принадлежит одной компоненте графа G. Тогда вершина графа G \ {vk }, соответствующая вершине vi, также принадлежит одной компоненте графа G\{vk } и, кроме того, corank Bi(G)-corank B(G) = corank Bi(G\{vk })-corank B(G\{vk }). Доказательство. 1. Первое утверждение следует из леммы 3.6. Докажем только второе утверждение. 2. Пусть i = n - 1, k = n и V (G \ {vn}) = {v1,..., vn-1}. Имеем ⎛ F d e ⎞ ( F d \ B(G) = ⎝ d∗ a c e∗ c b и ⎠ , B(G \ {vn}) = d∗ a corank Bn(G) = corank B(G \ {vn}), corank Bn-1(G) ±= corank B(G \ {vn-1}). 54 Д. П. ИЛЬЮТКО, В. С. САФИНА ⎛ e ⎞ ⎛ d ⎞ По лемме 3.1 вектор ⎝ c ⎠ линейно выражается через вектор ⎝ a b c ⎠ и столбцы матрицы ⎛ F ⎞ ⎛ d ⎞ ⎛ e ⎞ ⎝ d∗ e∗ ⎠ , а вектор ⎝ a ⎠ линейно не выражается через вектор c ⎝ c ⎠ и столбцы матрицы b ⎛ F ⎞ ⎛ e ⎞ ⎛ F ⎞ ⎝ d∗ e∗ ⎠ . Следовательно, вектор ⎝ c b ⎠ линейно выражается через столбцы матрицы ⎝ d∗ ⎠ . e∗ Получаем ⎛ F d e ⎞ ⎛ F d 0 ⎞ corank Bn-1(G) = corank ⎝ d∗ a +1 c e∗ c b ⎠ = corank ⎝ d∗ a +1 0 ⎠ = 0∗ 0 0 = corank ( F d d∗ a +1 ( F e \ \ + 1 = corank Bn-1(G \ {vn})+ 1, ( F 0 \ corank B(G \ {vn-1}) = corank e∗ b = corank 0∗ 0 = = corank F + 1 = corank B(G \ {vn-1, vn})+ 1. Используя следствие 3.1 и последние равенства, мы получаем справедливость второго утверждения леммы. Лемма 4.3. Пусть вершина vi принадлежит одной компоненте графа G. Тогда число wi = sgn(vi)(-1)corank Bi(G)-corank B(G) инвариантно при четвертых граф-преобразованиях. Доказательство. 1. Пусть граф G с множеством вершин V (G ) = {v× ,..., v× } получен из графа 1 n G четвертым граф-преобразованием Ωg 4× в вершине vj. Возможны два случая: i = j и i ±= j. Рассмотрим первый случай. Будем считать, что i = j = 1. Имеем ⎛ 0 0∗ 1∗ ⎞ ⎛ 0 0∗ 1∗ ⎞ B(G) = ⎝ 0 A0 A1 ⎠ , B(G ) = ⎝ 0 A0 A1 ⎠ . 1 1 A∗ A2 1 1 A∗ A2 + (1) i Тогда sgn(vi) = -sgn(v×), corank B(G) = corank B(G ) и ⎛ 1 0∗ 1∗ ⎞ ⎛ 1 0∗ 0∗ ⎞ corank Bi(G ) = corank ⎝ 0 A0 A1 ⎠ = corank ⎝ 0 A0 A1 ⎠ = corank B(G \ {vi}). 1 1 A∗ A2 + (1) 1 0 A∗ A2 i Поскольку corank Bi(G) ±= corank B(G \ {vi}), получаем corank Bi(G ) = corank Bi(G)± 1 и wi = w× . Рассмотрим второй случай. Будем считать, что j = 1 и i = 2. Имеем ⎛ 0 a 0∗ 1∗ ⎞ ⎛ 0 a 0∗ 1∗ ⎞ B(G) = ⎜ a b c∗ d∗ ⎟ , B(G) = ⎜ a b + a c∗ d∗ + (a)∗ ⎟ . ⎝ ⎝ ⎠ ⎜ 0 c A0 A1 ⎟ ⎠ ⎜ 0 c A0 A1 ⎟ 1 1 d A∗ A2 1 1 d + (a) A∗ A2 + (1) Тогда sgn(vi) = sgn(v×), corank B(G) = corank B(G ) и corank Bi(G ) = corank Bi(G), т. е. wi = w× . i i 2. Пусть граф G с множеством вершин V (G ) = {v× ,..., v× } получен из графа G четвертым 1 n граф-преобразованием Ωg 4 в вершинах vj и vk. Возможны два случая: i ∈ {j, k} и i ∈/ {j, k}. Рассмотрим первый случай. Будем считать, что i = j = 1 и k = 2. Имеем ⎛ 1 1 0∗ 1∗ 0∗ 1∗ ⎞ ⎜ 1 1 0∗ 0∗ 1∗ 1∗ ⎟ ⎜ ⎟ B(G) = 0 0 B0 A1 A2 A3 ⎜ ⎟ , ⎜ ⎟ 1 ⎜ 1 0 A∗ ⎜ B4 A5 A6 ⎟ A ⎟ 2 5 ⎝ 0 1 A∗ ∗ B7 A8 ⎠ 3 A A 6 8 1 1 A∗ ∗ ∗ B9 ГРАФ-ЗАЦЕПЛЕНИЯ: НЕРЕАЛИЗУЕМОСТЬ, ОРИЕНТАЦИЯ И ПОЛИНОМ ДЖОНСА 55 ⎛ 1 1 0∗ 0∗ 1∗ 1∗ ⎞ ⎜ 1 1 0∗ 1∗ 0∗ 1∗ ⎟ ⎜ . ⎟ B(G) = ⎜ 0 0 B0 A1 A2 A3 ⎟ ⎜ 1 ⎟ B4 A5 + (1) A6 + (1) A∗ + (1) 5 B7 A8 + (1) ⎜ 0 1 A∗ ⎟ ⎜ ⎟ 1 0 A∗ ⎝ 2 ⎠ 1 1 A3 A6 + (1) A8 + (1) B9 ∗ ∗ ∗ i Тогда sgn(vi) = -sgn(v×), corank B(G) = corank B(G ) и ⎜ 0 1 A∗ corank Bi(G ) = corank ⎜ 1 ⎝ 1 0 A∗ ⎜ 2 B4 A5 + (1) A6 + (1) ⎟ ⎛ 0 1 0∗ 0∗ 1∗ 1∗ ⎞ ⎜ 1 1 0∗ 1∗ 0∗ 1∗ ⎟ ⎜ ⎜ 0 0 B0 A1 A2 A3 ⎟ ⎟ = ⎟ 5 ⎠ A∗ + (1) B7 A8 + (1) ⎟ 1 1 A3 A6 + (1) A8 + (1) B9 ∗ ∗ ∗ ⎛ 0 1 0∗ 0∗ 0∗ 0∗ ⎞ ⎜ 1 1 0∗ 0∗ 1∗ 1∗ ⎟ ⎜ ⎟ = corank 0 0 B0 A1 A2 A3 ⎟ ⎜ ⎜ ⎟ = corank B(G \ {vi}). 1 ⎜ 0 1 A∗ ⎜ B4 A5 A6 ⎟ A ⎟ 2 5 ⎝ 1 0 A∗ ∗ B7 A8 ⎠ 3 A A 6 8 1 1 A∗ ∗ ∗ B9 i Поскольку corank Bi(G) ±= corank B(G \ {vi}), получаем corank Bi(G ) = corank Bi(G)± 1 и wi = w× . Рассмотрим второй случай. Будем считать, что j = 1, k = 2 и i = 3. Имеем ⎛ 1 1 a 0∗ 1∗ 0∗ 1∗ ⎞ ⎜ 1 1 h 0∗ 0∗ 1∗ 1∗ ⎟ ⎜ ⎟ ⎜ a h b c∗ d∗ e∗ f ∗ ⎟ ⎜ , ⎟ B(G) = ⎜ 0 0 c B0 A1 A2 A3 ⎟ ⎜ ⎟ 1 ⎜ 1 0 d A∗ ⎜ B4 A5 A6 ⎟ A ⎟ 2 5 ⎝ 0 1 e A∗ ∗ B7 A8 ⎠ 1 1 f A3 A6 A8 B9 ∗ ∗ ∗ ⎛ 1 1 h 0∗ 0∗ 1∗ 1∗ ⎞ ⎜ 1 1 a 0∗ 1∗ 0∗ 1∗ ⎟ ⎜ ⎟ ⎜ h a b c∗ d∗ + (h)∗ e∗ + (a)∗ f ∗ + (a + h)∗ ⎟ ⎜ . ⎟ B(G ) = ⎜ 0 0 c B0 A1 A2 A3 ⎟ ⎜ ⎟ 1 ⎜ 0 1 d + (h) A∗ ⎜ 1 0 e + (a) A∗ B4 A5 + (1) A6 + (1) ⎟ A∗ + (1) B7 A8 + (1) ⎟ ⎝ 2 1 1 f + (a + h) A∗ 5 ⎠ A∗ + (1) A∗ + (1) B9 3 6 8 Тогда sgn(vi) = sgn(v×), corank B(G) = corank B(G ) и corank Bi(G ) = corank Bi(G), т. е. wi = w× . i i Лемма 4.4. Пусть в вершинах vi и vj, i < j, пересекаются две компоненты. Тогда ∗ sgn(vi) sgn(vj ) (-1)corank Bj-1(G\{vi}) = sgn(v×) sgn(v× ) (-1)corank Bj-1(Gcs(vi)\{vi}), i j где V (Gcs(vi)) = {v× ,..., v× }, и соответствующие вершины графов G и G имеют одинако- 1 n вые номера. cs(vi) Доказательство. Без ограничения общности считаем, что i = 1, j = 2. Из определения 3.2 и из леммы 3.7 следует, что corank Bj-1(G \ {vi}) = corank Bi(G \ {vj }) ±= corank B(G \ {vi, vj }). Согласно лемме 4.3 и доказательству леммы 4.1, достаточно рассмотреть три случая. 56 Д. П. ИЛЬЮТКО, В. С. САФИНА 3. Пусть оснащение вершины v1 равно 1, и к ней применяется граф-преобразование Ωg 4×. Имеем ⎛ B(G) = ⎜ 0 a 0∗ 1∗ a b c∗ d∗ ⎞ ⎟ , B(G ⎛ ) = ⎜ 0 a 0∗ 1∗ ⎞ a b + a c∗ d∗ + (a)∗ ⎟ , ⎝ ⎠ ⎜ 0 c A0 A1 ⎟ ⎝ cs(vi) ⎠ ⎜ 0 c A0 A1 ⎟ 1 1 d A∗ A2 1 1 d + (a) A∗ A2 + (1) где (a) - это вектор, состоящий из a ∈ {0, 1}. Применяя лемму 3.7 и элементарные преобразования, получаем ⎛ 1 0∗ 1∗ ⎞ ⎛ 1 0∗ 0∗ ⎞ i corank Bj-1(Gcs(vi) \ {v×}) = corank ⎝ 0 A0 A1 ⎠ = corank ⎝ 0 A0 A1 ⎠ = ∗ 1 A1 ∗ A2 + (1) 0 A1 A2 т. е. = corank B(G \ {vi, vj }), i corank Bj-1(Gcs(vi) \ {v×}) = corank Bj-1(G \ {vi}) ± 1. Учитывая равенства sgn(vi) = -sgn(v×) и sgn(vj ) = sgn(v× ), получаем требуемое утверждение. i j 4. Пусть оснащение вершины v1 равно 0 и существует вершина vk , смежная с вершиной v1 и имеющая оснащение 0. В этом случае мы применяем к ним четвертое граф-преобразование Ωg 4. Возможны два случая: vk = v2 и vk ±= v2. В первом случае имеем ⎛ 1 1 0∗ 1∗ 0∗ 1∗ ⎞ ⎜ 1 1 0∗ 0∗ 1∗ 1∗ ⎟ ⎜ ) = ⎜ , ⎟ ⎟ B(G ⎜ 0 0 B0 A1 A2 A3 ⎟ 1 ⎜ 1 0 A∗ ⎜ B4 A5 A6 ⎟ A ⎟ 2 5 ⎝ 0 1 A∗ ∗ B7 A8 ⎠ 3 A A 6 8 1 1 A∗ ∗ ∗ B9 B(Gcs(vi)) ⎛ 1 1 0∗ 0∗ 1∗ 1∗ ⎞ ⎜ 1 1 0∗ 1∗ 0∗ 1∗ ⎜ 0 0 B0 A1 A2 A3 = ⎜ ∗ ⎜ ⎜ 0 1 A1 B4 ⎜ ⎝ 1 0 A∗ A∗ + (1) 2 5 A5 + (1) B7 A6 + (1) A8 + (1) ⎟ ⎟ ⎟ . ⎟ ⎟ ⎟ ⎠ 1 1 A3 A6 + (1) A8 + (1) B9 ∗ ∗ ∗ Применяя элементарные преобразования, получаем ⎛ 0 0∗ 0∗ 1∗ 1∗ ⎞ ⎜ 0 B0 A1 A2 A3 ⎟ corank Bj-1(Gcs(vi) \ {v×}) = corank ⎜ 0 A∗ B4 A5 + (1) A6 + (1) ⎟ = i ⎜ 1 ⎟ ⎜ ⎟ 2 5 ⎝ 1 A∗ A∗ + (1) B7 A8 + (1) ⎠ 1 A3 A6 + (1) A8 + (1) B9 ∗ ∗ ∗ ⎛ 0 0∗ 0∗ 1∗ 1∗ ⎞ ⎜ 0 B0 A1 A2 A3 ⎟ = corank ⎜ 0 A∗ B4 A5 A6 ⎟ = corank Bj-1(G \ {vi}). ⎜ 1 ⎟ A ⎜ ⎟ 2 5 ⎝ 1 A∗ ∗ B7 A8 ⎠ 3 A A 6 8 1 A∗ ∗ ∗ B9 Учитывая равенства sgn(vi) = -sgn(v×) и sgn(vj ) = -sgn(v× ), получаем требуемое утверждение. i j Во втором случаем (пусть k = 3) имеем ⎛ 1 a 1 0∗ 1∗ 0∗ 1∗ ⎞ ⎜ a b h c∗ d∗ e∗ f ∗ ⎟ ⎜ ⎟ ⎜ 1 h 1 0∗ 0∗ 1∗ 1∗ ⎟ ⎜ , ⎟ B(G) = ⎜ 0 c 0 B0 A1 A2 A3 ⎟ ⎜ ⎟ 1 ⎜ 1 d 0 A∗ ⎜ B4 A5 A6 ⎟ A ⎟ 2 5 ⎝ 0 e 1 A∗ ∗ B7 A8 ⎠ 3 A A 6 8 1 f 1 A∗ ∗ ∗ B9 ГРАФ-ЗАЦЕПЛЕНИЯ: НЕРЕАЛИЗУЕМОСТЬ, ОРИЕНТАЦИЯ И ПОЛИНОМ ДЖОНСА 57 ⎛ 1 h 1 0∗ 0∗ 1∗ 1∗ ⎞ ⎜ h b a c∗ d∗ + (h)∗ e∗ + (a)∗ f ∗ + (a + h)∗ ⎟ ⎜ ⎟ ⎜ 1 a 1 0∗ 1∗ 0∗ 1∗ ⎟ ⎜ . ⎟ B(Gcs(vi)) = ⎜ 0 c 0 B0 A1 A2 A3 ⎟ ⎜ ⎟ 1 ⎜ 0 d + (h) 1 A∗ ⎝ 1 e + (a) 0 A∗ ⎜ 2 B4 A5 + (1) A6 + (1) ⎟ A 5 ⎠ ∗ + (1) B7 A8 + (1) ⎟ 3 1 f + (a + h) 1 A∗ A 8 6 ∗ + (1) A∗ + (1) B9 Применяя лемму 3.7 и элементарные преобразования, получаем ⎜ 1 1 0∗ 1∗ 0∗ 1∗ ⎜ ⎜ ⎜ ⎜ 0 0 0 1 B0 A∗ 1 A1 B4 A2 A5 + (1) A3 A6 + (1) ⎛ i corank Bj-1(Gcs(vi) \ {v×}) = corank ⎜ 0 1 0∗ 0∗ 1∗ 1∗ ⎞ ⎟ ⎟ ⎟ = ⎟ ⎟ A ⎟ 2 5 ⎝ 1 0 A∗ ∗ + (1) B7 A8 + (1) ⎠ ∗ 1 1 A3 A ∗ 6 ∗ + (1) A8 + (1) B9 ⎛ 0 1 0∗ 0∗ 0∗ 0∗ ⎞ ⎜ 1 1 0∗ 0∗ 1∗ 1∗ ⎟ ⎛ 1 0 0∗ 0∗ 0∗ 0∗ ⎞ ⎜ 0 1 0∗ 0∗ 1∗ 1∗ ⎟ ⎜ 0 0 B0 A1 A2 A3 ⎟ ⎜ 0 0 B0 A1 A2 A3 ⎟ = corank ⎜ ⎟ = corank ⎜ ⎟ = ⎜ 0 1 A∗ ⎜ 0 0 A∗ ⎟ ⎟ ⎜ 1 B4 A5 A6 ⎟ A ⎜ ⎟ ⎜ 1 B4 A5 A6 ⎟ A ⎜ ⎟ 2 5 ⎝ 1 0 A∗ ∗ B7 A8 ⎠ 2 5 ⎝ 0 1 A∗ ∗ B7 A8 ⎠ 3 A A 6 8 1 1 A∗ ∗ ∗ B9 3 A A 6 8 0 1 A∗ ∗ ∗ B9 т. е. = corank B(G \ {vi, vj }), i corank Bj-1(Gcs(vi) \ {v×}) = corank Bj-1(G \ {vi}) ± 1. Учитывая равенства sgn(vi) = -sgn(v×) и sgn(vj ) = sgn(v× ), получаем требуемое утверждение. i j 5. Пусть оснащение вершины v1 равно 0 и существует вершина vk , смежная с вершиной v1 и имеющая оснащение 1. В этом случае мы применяем четвертое граф-преобразование Ωg 4× к vk, а потом это же преобразование - к вершине, соответствующей вершине v1 в полученном графе. Возможны два случая: vk = v2 и vk ±= v2. В первом случае имеем ⎛ 1 1 0∗ 1∗ 0∗ 1∗ ⎞ ⎜ 1 0 0∗ 0∗ 1∗ 1∗ ⎟ ⎜ ) = ⎜ , ⎟ ⎟ B(G ⎜ 0 0 B0 A1 A2 A3 ⎟ 1 ⎜ 1 0 A∗ ⎜ B4 A5 A6 ⎟ A ⎟ 2 5 ⎝ 0 1 A∗ ∗ B7 A8 ⎠ 3 A A 6 8 1 1 A∗ ∗ ∗ B9 B(Gcs(vi)) ⎛ 0 1 0∗ 1∗ 1∗ 0∗ ⎞ ⎜ 1 1 0∗ 1∗ 0∗ 1∗ ⎜ 0 0 B0 A1 A2 A3 = ⎜ ∗ ⎜ ⎜ 1 1 A1 B4 + (1) ⎜ ⎝ 1 0 A∗ A∗ + (1) 2 5 A5 + (1) B7 A6 A8 + (1) ⎟ ⎟ ⎟ . ⎟ ⎟ ⎟ ⎠ 3 A 0 1 A∗ 8 6 ∗ A∗ + (1) B9 + (1) Применяя элементарные преобразования, получаем ⎛ 0 0∗ 1∗ 0∗ 1∗ ⎞ ⎜ 0 B0 A1 A2 A3 ⎟ corank Bj-1(Gcs(vi) \ {v×}) = corank ⎜ 1 A∗ B4 + (1) A5 + (1) A6 ⎟ = i ⎜ 1 ⎟ ⎜ ⎟ 2 5 ⎝ 0 A∗ A∗ + (1) B7 A8 + (1) ⎠ 3 1 A∗ A 8 6 ∗ A∗ + (1) B9 + (1) 58 Д. П. ИЛЬЮТКО, В. С. САФИНА ⎛ 0 0∗ 1∗ 0∗ 1∗ ⎞ ⎜ 0 B0 A1 A2 A3 ⎟ = corank ⎜ 1 A∗ B4 A5 A6 ⎟ = corank Bi(G \ {vj }). ⎜ 1 ⎟ A ⎜ ⎟ 2 5 ⎝ 0 A∗ ∗ B7 A8 ⎠ 3 A A 1 A B9 ∗ ∗ ∗ 6 8 Учитывая равенства sgn(vi) = -sgn(v×) и sgn(vj ) = -sgn(v× ), получаем требуемое утверждение. Во втором случаем (пусть i j k = 3) имеем ⎛ 1 a 1 0∗ 1∗ 0∗ 1∗ ⎞ ⎜ a b h c∗ d∗ e∗ f ∗ ⎟ ⎜ ⎟ ⎜ 1 h 0 0∗ 0∗ 1∗ 1∗ ⎟ ⎜ , ⎟ B(G) = ⎜ 0 c 0 B0 A1 A2 A3 ⎟ ⎜ ⎟ 1 ⎜ 1 d 0 A∗ ⎜ B4 A5 A6 ⎟ A ⎟ 2 5 ⎝ 0 e 1 A∗ ∗ B7 A8 ⎠ 1 f 1 A3 A6 A8 B9 ∗ ∗ ∗ ⎛ 0 a + h 1 0∗ 1∗ 1∗ 0∗ ⎞ ⎜ a + h b a c∗ d∗ + (a + h)∗ e∗ + (a)∗ f ∗ + (h)∗ ⎟ ⎜ ⎟ ⎜ ⎜ B(Gcs(vi)) = ⎜ ⎜ 1 a 1 0∗ 1∗ 0∗ 1∗ ⎟ . ⎟ 0 c 0 B0 A1 A2 A3 ⎟ ⎟ 1 ⎜ 1 d + (a + h) 1 A∗ ⎜ B4 + (1) A5 + (1) A6 ⎟ A ⎟ 2 ⎝ 1 e + (a) 0 A∗ 5 ∗ + (1) B7 A8 + (1) ⎠ 3 A 6 0 f + (h) 1 A∗ ∗ 8 A∗ + (1) B9 + (1) Применяя лемму 3.7 и элементарные преобразования, получаем ⎛ 1 1 0∗ 1∗ 1∗ 0∗ ⎜ 1 1 0∗ 1∗ 0∗ 1∗ ⎜ 0 0 B0 A1 A2 A3 i ⎜ ⎜ 1 1 A∗ B4 + (1) 1 A5 + (1) A6 ⎜ ⎝ 1 0 A∗ A∗ + (1) 2 5 B7 A8 + (1) 0 1 A3 ∗ A6 ∗ A8 + (1) ∗ B9 + (1) 0∗ 0∗ 0∗ 0∗ ⎞ ⎛ 1 0 0∗ 0∗ 0∗ 0∗ 1∗ 1∗ ⎟ ⎜ 0 0 0∗ 0∗ ⎞ ⎟ ⎟ = ⎟ corank Bj-1(Gcs(vi) \ {v×}) = corank ⎜ ⎟ ⎟ ⎟ ⎠ ⎛ 1 1 ⎜ 1 1 0∗ 0∗ ⎞ 1∗ 1∗ ⎟ ⎜ 0 0 B0 A1 A2 A3 ⎟ ⎜ 0 0 B0 A1 A2 A3 ⎟ = corank ⎜ ⎟ = corank ⎜ ⎟ = ⎜ 1 1 A∗ ⎜ 0 0 A∗ ⎟ ⎟ ⎜ 1 B4 A5 A6 ⎟ A ⎜ ⎟ ⎜ 1 B4 A5 A6 ⎟ A ⎜ ⎟ 2 5 ⎝ 1 0 A∗ ∗ B7 + (1) A8 + (1) ⎠ 2 5 ⎝ 0 1 A∗ ∗ B7 A8 ⎠ 3 A 0 1 A∗ 8 6 ∗ A∗ + (1) B9 + (1) 3 A A 6 8 0 1 A∗ ∗ ∗ B9 т. е. = corank B(G \ {vi, vj }), i corank Bj-1(Gcs(vi) \ {v×}) = corank Bj-1(G \ {vi}) ± 1. Учитывая равенства sgn(vi) = -sgn(v×) и sgn(vj ) = sgn(v× ), получаем требуемое утверждение. i j 2. Ориентированные граф-зацепления и полином Джонса. Пусть G - меченый граф с k компонентами и V (G) = {v1,..., vn}. Поскольку при удалении вершины, принадлежащей разным компонентам, число компонент граф-зацепления уменьшается на единицу (см. следствие 3.1), то существует последовательность (vi1 ,..., vik -1 ), состоящая из k - 1 вершины vi1 ,..., vi k-1 , такая, что граф (... ((G \ {vi1 }) \ {vi2 }) ... ) \ {vik-1 }, полученный последовательным удалением вершин последовательности, имеет одну компоненту. Лемма 4.5. Для любой последовательности (αi1 ,..., αik - 1 ) знаков αij ∈ {±} найдется такой меченый граф G(vi1 ,..., vik 1 ), полученный из G четвертыми граф-преобразованиями, что - меченый граф G× = G(vi1 ,..., vik -1 ) \ {vi1 ,..., vi k-1 } имеет одну компоненту и знаки вершин графа G(vi1 ,..., vik с αij . -1 ), соответствующих вершинам vij , j = 1,...,k - 1, графа G, совпадают ГРАФ-ЗАЦЕПЛЕНИЯ: НЕРЕАЛИЗУЕМОСТЬ, ОРИЕНТАЦИЯ И ПОЛИНОМ ДЖОНСА 59 Доказательство. Заметим, что четвертые граф-преобразования меняют знаки только тех вершин, к которым они применяются. Далее, поскольку удаление вершины из графа не влияет на знаки и попарную смежность оставшихся вершин, то утверждение леммы легко доказывается по индукции с использованием леммы 4.1. Поскольку граф G× имеет одну компоненту, то мы можем определить число закрученности wi каждой его вершины v×, положив wi = (-1)corankBi(G∗)sgn(v×), и число закрученности его самого: i i n-k+1 w(G×) = ), i=1 wi. Определение 4.1. Число закрученности wi(G) графа G в вершине vi ∈ V (G) по отношению к последовательности вершин (vi1 ,..., vik - 1 ) со знаками (αi1 ,..., αi k-1 ) - это число закрученности вершины графа G×, соответствующей вершине vi, если i ±= ij, и wij (G) = αij иначе. Число закрученности графа G по отношению к последовательности вершин (vi1 ,..., vik 1 ) со знаками - (αi1 ,..., αik 1 ) - это - n w(G) = \ wi(G). i=1 Замечание 4.1. Из лемм 4.3 и 4.4 следует корректность определения числа закрученности, т. е. зависимость его не от выбора графа G(vi1 ,..., vik 1 ), а только от знаков удаляемых вершин. Дей- - ствительно, из этих лемм следует, что вершина, принадлежащая одной компоненте, всегда имеет одно и то же число закрученности, и для каждого класса эквивалентности вершин, порожденного отношением «пересечение двух компонент», число закрученности каждой вершины этого класса однозначно определяется числом закрученности произвольной вершины из этого класса. Определение 4.2. Пусть даны две последовательности вершин (vi1 ,..., vik - 1 ) и (vj1 ,..., vj k-1 ) со знаками (αi1 ,..., αik - 1 ) и (αj1 ,..., αj k-1 ) соответственно, удаление которых из соответствующих графов G(vi1 ,..., vik - 1 ) и G(vj1 ,..., vj k-1 ) приводит к графам с одной компонентой. Мы скажем, что эти последовательности эквиваленты, если числа закрученности в вершинах vip (соответственно vjp ), p = 1,...,k - 1, по отношению к двум последовательностям совпадают. Определение 4.3. Будем говорить, что на меченом графе G задана ориентация, если задан класс эквивалентности последовательностей вершин со знаками, дающих граф с одной компонентой. Лемма 4.6. Пусть меченый граф G имеет две компоненты. Предположим, что вершины vi и vj, i ±= j, принадлежат разным компонентам и к ним можно применить второе уменьшающее граф-преобразование. Тогда существует вершина vk, k ±= i, j, которая тоже принадлежит разным компонентам. Доказательство. Пусть i = 1 и j = 2. Тогда ⎛ a +1 a b∗ ⎞ B(G) = ⎝ a a +1 b∗ ⎠ b b C и det B(G) = 0. Поскольку первый и второй столбцы матрицы B(G) не являются нулевыми и не пропорциональны друг другу, то найдется номер k такой, что k-й столбец линейно выражается через остальные столбцы матрицы B(G). Следовательно, вершина vk принадлежит разным компонентам. Пусть на графе G задана ориентация, т. е. задана последовательность вершин (vi1 ,..., vik 1 ) со - знаками (αi1 ,..., αik -1 ). Определим ориентацию любого графа G , полученного из G применением одного граф-преобразования. Если мы применяем первое, третье, второе увеличивающее или четвертое граф-преобразование, то ориентация на G будет порождаться последовательностью вершин, соответствующей последовательности (vi1 ,..., vik 1 ), с теми же самыми знаками. Если мы приме- - няем второе уменьшающее граф-преобразование, то мы сначала, используя лемму 4.6, выбираем последовательность вершин (vj1 ,..., vjk - 1 ) со знаками (αj1 ,..., αj k-1 ), эквивалентную последовательности (vi1 ,..., vik - 1 ) со знаками (αi1 ,..., αi k-1 ), такую, что вершины vjp не участвуют в 60 Д. П. ИЛЬЮТКО, В. С. САФИНА нашем втором граф-преобразовании, и тогда на графе G задается ориентация с помощью последовательности, соответствующей последовательности (vj1 ,..., vjk - 1 ) со знаками (αj1 ,..., αj k-1 ). В этом случае мы скажем, что графы G и G имеют одинаковую ориентацию. Лемма 4.7. Пусть вершина vi меченого графа G принадлежит разным компонентам. Тогда существует граф G , полученный из G вторым увеличивающим граф-преобразованием, в котором в добавленных вершинах и в вершине, соответствующей вершине vi, пересекаются две компоненты. Доказательство. В качестве графа G можно взять граф, полученный из G добавлением двух вершин с оснащением 0, которые смежны только вершине vi. Лемма 4.8. Число закрученности ориентированного меченого графа изменяется на (±1) при граф-преобразовании Ωg 1. Более точно, оно изменяется на -1 при добавлении вершины со знаком «+» и на +1 при добавлении вершины со знаком «-». Число закрученности инвариантно при граф-преобразованиях Ωg 2-Ωg 4×. Доказательство. 1. Изменение на ±1 при первом граф-преобразовании была доказана в [14], а инвариантность при четвертых граф-преобразованиях следует из лемм 4.3 и 4.4. 1. Инвариантность при втором граф-преобразовании следует из возможности выбрать такую последовательность вершин, дающую ориентацию, что каждая ее вершина не участвует в нашем втором граф-преобразовании, а также из лемм 4.2 и 4.3 и инвариантности для меченых графов с одной компонентой, см. [14, лемма 5.4]. 2. Рассмотрим третье граф-преобразование. Используя лемму 4.7 и инвариантность относительно второго граф-преобразования, мы можем считать, что ориентация на графе задана с помощью последовательности вершин, не принимающих участие в нашем граф-преобразовании. Справедливость утверждения в этом случае следует из лемм 4.2 и 4.3 и инвариантности для меченых графов с одной компонентой, см. [14, лемма 5.4]. Определение 4.4 (см. [2, 14]). Мы назовем подмножество из V (G) состоянием для графа G. Скобка Кауфмана меченого графа G - это полином (Лорана) ⊗G)(a) = \ aα(s)-β(s)(-a2 - a-2)corank A(G(s)), s где сумма берется по всем состояниям s графа G, α(s) равно количеству вершин с метками (a, -) из s и вершин с метками (b, +) из V (G) \ s, β(s) = |V (G)|- α(s). Теорема 4.1 (см. [2, 14]). Скобка Кауфмана меченого графа инвариантна при Ωg 2-Ωg 4× граф-преобразованиях и умножается на (-a±3) при Ωg 1 граф-преобразовании. Определение 4.5. Граф-зацепление называется ориентированным, если на каждом его представителе задана ориентация, и для любых двух представителей G× и G×× существует такая последовательность меченых графов G1 = G×, G2,..., Gs = G××, что графы Gp и Gp+1 имеют одинаковую ориентацию. Замечание 4.2. Легко видеть, что для задания ориентации на граф-зацеплении достаточно задать ориентацию лишь на одном его представителе. Определение 4.6. Пусть F - ориентированное граф-зацепление. Определим его полином Джонса как X(G) = (-a)-3w(G)⊗G), где G - произвольный представитель граф-зацепления F. Замечание 4.3. По правде говоря, чтобы получить «настоящий» полином Джонса, нужно изменить переменную полинома X(G), положив a = q-1/4, но это, в сущности, - лишь изменение обозначений. Из леммы 4.8 и теоремы 4.1 сразу следует следующая теорема. Теорема 4.2. Полином Джонса является инвариантом ориентированных граф-зацеплений. ГРАФ-ЗАЦЕПЛЕНИЯ: НЕРЕАЛИЗУЕМОСТЬ, ОРИЕНТАЦИЯ И ПОЛИНОМ ДЖОНСА 61 v1 (0,-) v1 v2 (0,+) v2 РИС. 16. Граф-зацепление и зацепление Хопфа (пунктирная линия - это поворачивающий обход). v2 (0,+) v1 v2 v2 РИС. 17. Ориентация на зацеплении Хопфа. 3. Примеры. 1. Самое простое нетривиальное граф-зацепление, имеющее две компоненты, - это граф-зацепление, порожденное меченым графом G, состоящим из одной изолированной вершины v с оснащением 1 (знак вершины не важен, поскольку меченые графы с разными знаками эквивалентны). Для графа G имеем два состояния s1 = ∅ и s2 = {v}. Пусть для определенности знак вершины v равен +. Тогда α(s1) = 1, β(s1) = 0, corank A(G(s1)) = 0 и α(s2) = 0, β(s2) = 1, corank A(G(s2)) = corank (1) = 0. Получаем скобку Кауфмана ⊗G)(a) = a + a-1. На этом граф-зацеплении можно выбрать две ориентации: в первом случае число закрученности, например, будет равно +1, а во втором случае -1. Получаем два полинома Джонса: -a-2 - a-4 и -a4 - a2. 1. Рассмотрим граф-зацепление, порожденное меченым графом G, изображенным на рис. 16 слева. Этот граф получается из зацепления Хопфа (см. рис. 16 справа). Для графа G имеем четыре состояния s1 = ∅, s2 = {v1}, s3 = {v2}, s4 = {v1, v2}. Тогда α(s1) = 1, β(s1) = 1, corank A(G(s1)) = 0; α(s2) = 2, β(s2) = 0, corank A(G(s2)) = corank (0) = 1; α(s3) = 0, β(s3) = 2, ( 0 1 \ corank A(G(s2)) = corank (0) = 1; α(s4) = 1, β(s4) = 1, corank A(G(s2)) = corank 1 0 = 0. Получаем скобку Кауфмана ⊗G)(a) = -a4 - a-4. На этом граф-зацеплении можно выбрать две ориентации. Рассмотрим одну из них, которая задается последовательностью (v1) со знаком «-» (см. рис. 17). Тогда граф G \ {v1} состоит из одной вершины v2 с меткой (0, +), и число закрученности этого графа равно -1. Таким образом, число закрученности ориентированного меченого графа G равно -2, и полином Джонса равен -a10 - a2. 2. Рассмотрим граф-зацепление, порожденное вторым графом Буше BW3 с метками, изображенными на рис. 18. Мы знаем (см. пример 3.1), что это граф-зацепление содержит четыре компоненты и является нереализуемым. Скобка Кауфмана равна a-15 - 3a-11 + 6a-7 - 3a-3 + 7a - 3a5 + 4a9 - a13. Зададим ориентацию на графе с помощью последовательности вершин (v7, v2, v3) со знаками (-, +, -). Заметим, что ориентированный меченый граф BW3 \ {v7} может быть реализован ориентированными кольцами Борромео (см. рис. 19). Тогда число закрученности меченого графа BW3 равно -1. В результате получаем полином Джонса -a-12 + 3a-8 - 6a-4 +3 - 7a4 + 3a8 - 4a12 + a16. 3. Рассмотрим граф-зацепление, порожденное первым графом Буше W5 с метками, изображенными на рис. 20 (петлевой граф, соответствующий этому меченому графу, см. [13], был сообщен авторам Л. Зулли). Легко проверить, что это граф-зацепление содержит одну компоненту, т. е. является граф-узлом. 62 Д. П. ИЛЬЮТКО, В. С. САФИНА v2 (0,+) v3 (0,-) v1(0,-) v7 (0,-) v4(0,+) v6 (0,+) v5 (0,-) РИС. 18. Меченый второй граф Буше. (0,-) v5 (0,+) v4 v3 (0,-) v6 v2 (0,+) (0,+) v1 (0,-) РИС. 19. Кольца Борромео (пунктирная линия - это поворачивающий обход). (1,+) (0,+) (1,-) (0,+) (0,+) (0,+) РИС. 20. Граф-зацепление с тривиальным полиномом Джонса. Используя четность и эквивалентность между множеством граф-узлов и множеством гомотопических классов петлевых графов (см. [13, 15, 20, 22]), легко показать, что данный граф-узел является нереализуемым, а следовательно, и нетривиальным. Оказывается, что его скобка Кауфмана равна 1, а число закрученности - 0. Таким образом, мы имеем пример нетривиального граф-узла, имеющего тривиальный полином Джонса.