Базисные вложения графов и метод трехстраничных вложений И. А. Дынникова

Настоящая диссертация представляет собой исследование по современной геометрической топологии. В первой главе изучаются базисные вложения графов. Во второй главе вводится взаимно однозначное кодирование для всех изотопических классов заузленных графов в R3. Результаты обеих глав основаны на геометрических методах построения вложений графов в книжку со страницами. Во введении даются мотивировки исследований, вводятся ключевые понятия, формулируются известные результаты и теоремы автора.

1. Базисные вложения графов.

Первый параграф введения относится к главе 1. В пункте 1.1 обсуждаются вопросы, которые привели к понятию базисного вложения. В пункте 1.2 даются необходимые определения и формулируется критерий базисной вложимости графов в книжку со страницами (теорема 1.1). Пункт 1.3 посвящен следствиям этого критерия о запрещенных и универсальных семействах графов.

1.1. Истоки базисных вложений графов.

Под топологическим вложением понимается гомеоморфизм на образ. Свойство базисности усиливает понятие топологического вложения. Это свойство связано с вопросом представления непрерывных функций многих переменных на компактах в виде суперпозиции непрерывных функций меньшего числа переменных. Базисные вложения стали изучаться в работах, мотивированных решением А. Н. Колмогорова и В. И. Арнольда 13-й проблемы Д. Гильберта. Д. Гильберт сформулировал свою знаменитую 13-ю проблему так: «доказать, что уравнение 7-й степени х7 + ах3 + Ьх2 + сх + 1 = 0 имеет решения (непрерывно зависящие от параметров а, Ь, с), которые не выражаются в виде суперпозиции непрерывных функций только двух аргументов». А. Н. Колмогоров каждую непрерывную функцию многих переменных сумел представить в виде суперпозиции непрерывных функций только трех переменных [6]. В. И. Арнольд случай трех переменных свел к случаю двух[1], см. также [2]. После этого А. Н. Колмогоров доказал, что каждая функция, непрерывная на n-мерном кубе 1п, представляется в виде суммы (2п + 1)-ой непрерывной функции одного переменного [7]. Ниже формулируется только ослабленная версия этой теоремы. Через С (Х, Y) обозначается пространство непрерывных функций X —> У.

Теорема 1А (А. Н. Колмогоров [7]). При п > 2 существует такое семейство функций {(Pi}f=tl с C (In-, R), что любая функция / € С (/" -Е) представляется в виде f{x) = х = (хи. •, хп) е /", д{ € C (RR).

Теорема А. Н. Колмогорова не только опровергла гипотезу Д. Гильберта, но и поставила много новых вопросов. Обсуждение некоторых из них см. в [38, введение]. Здесь будет затронуто только одно направление, которое привело к понятию базисного вложения. В теореме 1А ключевую роль играет фиксированное семейство непрерывных функций {v?,}^1. Из этой теоремы следует, что непрерывное отображение ip = (</?i,., </>2n+i): In —> R2n+1 разделяет точки куба /", т. е. является топологическим вложением. Я. Штернфельд переформулировал функциональную теорему А. Н. Колмогорова на топологическом языке, введя понятие базисного вложения [38, стр. 4].

Определение 1.1 (базисное вложение). Пусть X и Xi (1 < i < к) — компактные метрические пространства, а р>г: X —> Xi — непрерывные функции. Семейство называется базисным, если каждая функция / € CpijM) представляется в виде f (x) = ^(^¿-(^О) — гДе х? X, gi € C (X?-R), 1 < i < к. Вопрос существования базисного семейства для пространств X, Xi,.Xk является топологическим, т. е. ответ на него зависит только от топологии пространств X и Xi (1 < i < к). Кроме того, базисное семейство задает вложение <�р = (ipi,., tpk) '¦ X С которое наивывается базисным и обозначается X Сь nt=i XiДанное определение можно короче сформулировать следующим образом [38, предложение 8. (i) на стр. 5]. Вложение X С Пг=1 Xi называется базисным, если любая функция / е С (Х-Е) представляется в виде fix) = EI=1 9i{xi), где gi G C (X?-R), x = (жь., хк) e X, хг e Хг.

Таким образом, свойство базисности усиливает понятие топологического вложения. В пункте 1.1.1 первой главы диссертации рассматриваются примеры базисных и небазисных вложений в R х К. Из теоремы А. Н. Колмогорова следует, что n-мерный куб /п базисно вкладывается в R2n+1. Здесь и далее под Rm понимается прямое произведение т экземпляров прямой R. П. Остранд обобщил теорему 1А на произвольные компакты. Ниже формулируется только частный случай теоремы П. Остранда в терминах базисных вложений.

Теорема 1 В (П. Остранд [33]). Любое n-мерное компактное метрическое пространство базисно вкладывается в R2n+1.

Оказалось, что число 2nf 1 в теоремах 1А и 1 В нельзя уменьшить.

Теорема 1С (Я. Штернфельд [38, теорема 1.12]). При п >2 любое п-мерное компактное метрическое пространство не вкладывается базисно в R2″ .

Итак, согласно теоремам 1 В и 1С произвольное компактное метрическое пространство X базисно вкладывается в Rm (т > 3) тогда и только тогда, когда dimX < Последнее утверждение усиливает известную теорему.

Небелинга-Менгера о том, что любое n-мерное компактное метрическое пространство X топологически вкладывается в R2″ +1. Заметим, что в отличие от топологического вложения, понятие базисного вложения позволяет охарактеризовать размерность компакта в терминах непрерывных функций на нем. При т — 1 понятия топологического и базисного вложения совпадают, но случай плоскости т — 2 еще до конца не разобран. Известно только описание линейно связных 1-мерных компактов, базисно вложимых вЕх! [36, теорема 3]. Недавно появилось простое доказательство критерия Я. Штернфельда базисного вложения в плоскость ЕхК [31]. Также было доказано, что для конечных графов базисная вложимость вЕхКв непрерывном смысле эквивалентна базисной вложимости в гладком смысле1 [14]. Если прямую К заменить на 1-мерный компакт, то размерность 2п + 1 в теоремах 1А и 1 В можно уменьшить.

Теорема (Я. Штернфельд [38, замечание о теореме 4.6 на стр. 29]). Пусть п > 1 и X — произвольное п-мерное компактное метрическое пространство. Тогда компакт X базисно вкладывается в Мх П" -1 гДе — некоторые 1-мерные компакты (1 < г < п).

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

Задача 1а. Для данного 1-мерного компакта У (например, У — букет нескольких отрезков и окружностей) описать все 1-мерные компакты X, базисно вложимые в произведение2 Е х У.

Задача 16. Для данного 1-мерного компакта X (например, X — конечный граф) найти такой минимальный (по вложению) 1-мерный компакт У, что компакт X базисно вкладывается в произведение К х У.

В обзоре по открытым проблемам геометрической топологии [18] задача 1а была сформулирована в случае, когда X — конечный граф, а У — букет нескольких отрезков. В такой постановке задача 1а эквивалентна проблеме ха-рактеризации конечных графов X, базисно вложимых в книжку со страницами ЕхУ. Задача 16 является частным случаем вопроса, который изучался Я. Штернфельдом [39]. В качестве следствия Я. Штернфельд охарактеризовал размерность произвольного дендрита (линейно связного компакта, не содержащего гомеоморфного образа окружности) в терминах нульмерных отображений (прообразы всех точек которых нульмерны) в другие дендриты.

В диссертации дается решение задачи 1а в случае, когда X — произвольный конечный граф, а У — букет отрезков и окружностей (теорема 1.1). Задача 16 решается для любого конечного графа X (следствие 1.2).

1.2. Критерий базисной вложимости графов.

Опишем класс графов, базисные вложения которых будут рассматриваться. Под конечным графом С? понимается произвольный 1-мерный клеточный комплекс с конечным числом клеток. Его 0-мерные клетки называются вершинами, а 1-мерные — ребрами. Ребро I примыкает к вершине V, если точка V содержится в замыкании клетки I. Степень с^г? вершины V е С равна числу ребер графа (7, примыкающих к ней. Вершины степени 0 называются изолированными. Граф может быть несвязным, но изолированные вершины не рассматриваются. Мулъти-ребро — это набор ребер, примыкающих к одной паре вершин, а петля — ребро, примыкающее ровно к одной вершине. Все графы считаются.

Определение гладкого базисного вложения получается из последнего предложения определения 1.1 заменой в двух местах непрерывных функций на гладкие.

2Поскольку рассматриваются вложения компактов, произведение К х У можно заменить на [0,1] х V. неориентированными, допускаются мульти-ребра и петли. Графы изучаются с точностью до произвольного гомеоморфизма3. Для формулировки основного результата введем дополнительные понятия.

Определение 1.2 (склеенная книжка ШхТп, т, ось ШхО). Для целых чисел п, т > 0 (п + 2 т > 2) возьмем п отрезков, в каждом из которых выделен один конец, и т окружностей, в каждой из которых выделено по точке. Через Тп т обозначим букет всех этих отрезков и окружностей, в котором все выделенные точки склеиваются в одну: Tn? m = Sj. Точка склейки в букете Tn? m будет считаться центром букета и обозначать через О. Произведение Rx Тп т назовем склеенной книжкой. Она состоит из п полуплоскостей и т цилиндров, склеенных вместе вдоль оси Ж х О.

Через обозначим количество связных компонент конечного графа G. По определению первое число Бетти b (G) графа G равно — x (G), где x{G) — эйлерова характеристика графа G. Цикл S С G — это подграф, гомеоморфный окружности. Например, дерево — это связный граф G без циклов (с первым числом Бетти b (G) = 0).

Определение 1.3 (сложные вершины и дефект S (G)). Ребро, примыкающее к вершине степени 1, будет называться висячим. Вершина v € G считается неразветвленной, если к ней примыкает висячее ребро, и разветвленной в противном случае. Вершина v € G называется сложной, если либо ее степень degv > 5, либо deg-u = 4 и она является разветвленной. Дефект S (G) графа G — это сумма ~ 2) по всем сложным вершинам v графа G. V.

В пункте 1.1.2 первой главы диссертации дефект вычисляется для нескольких серий известных графов. Следующая теорема 1.1 решает задачу 1а (см. пункт 1.1) для случая, когда X — произвольный конечный граф, a Y = Tn? rn.

Теорема 1.1. Фиксируем целые числа п, т > 0 (п + 2 т > 2). Конечный граф G базисно вкладывается в книжку К х Tn? m тогда и только тогда, когда его первое число Бетти b (G) < т и либо дефект S (G) < п+2т, либо 5{G) — п+2т и одна из сложных вершин графа G является неразветвленной.

Теорема 1.1 для случая плоскости R х R (п = 2, т — 0) дает такой критерий: «конечный граф G базисно вкладывается в R х R тогда и только тогда, когда b (G) = 0 (т.е. G не имеет циклов) и ?(G) = 0 (т.е. G не содержит сложных вершин)». Этот результат эквивалентен характеризации (данной А. Б. Скопен-ковым в терминах запрещеных подграфов) конечных графов, которые базисно вкладываются в Е х М [36, теорема 1]. Другие частные случаи теоремы 1.1 подробно разбираются в пункте 1.1.3 первой главы.

Самая существенная часть теоремы 1.1 (при т = 0) доказана в [28]. На произвольное т > 0 результаты обобщены в [11, 29]. Теорема 1.1 дает эффективный критерий базисной вложимости конечных графов в книжку К х Тп гп.

3Всюду в диссертации гомеоморфизм обозначается через и.

Следствие 1.1. Фиксируем целые числа п, т > 0 (п + 2 т > 2). Существует алгоритм, который по любому конечному графу С проверяет базисную вложи-мостъ графа (7 в книжку М х Тп<�т. Этот алгоритм является квадратичным по количеству вершин графа О.

Следующее следствие решает задачу 16 (см. пункт 1.1 введения) для произвольного конечного графа X.

Следствие 1.2. Для любых конечных графов X, У существует конечный граф, который нельзя базисно вложить в произведение ХхУ. С другой стороны, для каждого конечного графа С существует такой минимальный (по вложению) букет Тп>т, что граф С базисно вкладывается в книжку К х Тп<�т. При этом т = и если все сложные вершины графа О являются разветвленными, то п = тах{0,6(С) — 2Ь{0) + 1}, иначе п = тах{0,5(С) — 2&(??)}.

Следствие 1.2 означает, что не существует одного универсального произведения X х У, в которое можно базисно вложить все конечные графы. Зато семейство произведений {1х Тп, т п, т > 0, п + 2 т > 2} является универсальным, в том смысле, что для каждого конечного графа О найдется свое произведение К х Тп, т, куда граф б вкладывается базисно.

1.3. Запрещенное и универсальное семейства графов.

Многие теоремы геометрической топологии сформулированы в терминах запрещенных графов. Среди них — известная теорема Куратовского [27] о характеризации планарных графов. Для базисных вложений в книжку К х ТП) ТО также можно указать конечное запрещенное семейство.

Определение 1.4 (запрещенное семейство). Семейство графов {Рг (Гп т)} называется запрещенным (для базисных вложений в книжку К х ТП) ГП), если.

1) все графы Рг (Тп>т) базисно невложимы в книжку М х ГП-ГП, и.

2) любой граф, базисно невложимый в книжку 1х ТП]Т71, содержит подграф, гомеоморфный некоторому графу из семейства {^?(Тп>то)}.

Следствие 1.3. При фиксированных п, т > 0 (п + 2 т >2) существует конечное запрещенное семейство графов для базисных вложений е Е х ТП) ГП.

Следствия 1.2 и 1.3 получены в [11, 29]. Следствие 1.3 допускает уточнения в некоторых частных случаях. А именно, запрещенные семейства будут найдены в явном виде для пар (п, т) = (0,1), (3,0), (1,1) в следствиях 1.4, 1.5 и 1.6 соответственно. Например, для базисных вложений в цилиндр К х 51 есть ровно 6 запрещенных графов, для книжки с тремя страницами К х Т3-о — 8 запрещенных графов, а для цилиндра с приклеенной полуплоскостью К х Гхд — 16 запрещенных подграфов.

Определение 1.5 (универсальное семейство). Семейство графов {[/?(Т"1т)} называется универсальным (для базисных вложений в книжку М х Тп т), если.

1) все графы ^?(Тп>т) базисно вкладываются в книжку М х Тп>т, и.

2) любой граф, базисно вложимый в книжку Е х Тп>тп, содержится в некотором графе из семейства {^¿-(Тп т)}.

Через Т^ I обозначим граф, получающийся из букета разветвлением к висячих ребер (т.е. приклейкой к каждой висячей вершине двух висячих ребер, см. графы То 2, Т5,0, Т-о и Т'2д на рисунке4 1.1). Следующие три следствия описывают запрещенные и универсальные семейства графов в случаях (п, т) = (0,1), (3,0), (1,1). Значок и используется для несвязного объединения графов, а символ и — для склеек графов, показанных на рисунках ниже.

Следствие 1.4. Конечный граф (5 базисно вкладывается в К х 51 тогда и только тогда, когда выполнено одно из следующих эквивалентных условий: (1−4а) граф С не содержит запрещенные подграфы с рисунка 1.1- (1−4-6) граф С содержится в некотором универсальном графе {/?(51) (где г> 1), см. рисунок 1.2 при г = 1,2,3. оо со е ^ ьВИ.

Рисунок 1.2. Универсальные графы для цилиндра М х 51.

Чтобы определить универсальные графы (б*1) для всех к? М, введем понятие универсального листа 14(К).

Определение 1.6 (универсальный лист ?4 (К), корень). Пусть Ь — Тз0 — триод, одна из висячих вершин которого считается корнем, а две другие — крайними. Тогда при к > 1 дерево Ьк+1 получается из Ьк приклейкой двух висячих ребер5 в каждой крайней вершине. Крайними вершинами нового дерева.

4На рисунках 1.1−1.6 жирные точки обозначают сложные вершины, а толстыми линиями выделены сети графов, см. определение 1.25 в пункте 1.6.2.

5Висячее ребро всегда приклеивается по одному из своих концов.

Т'.

2,1.

Ь}~+ будут висячие вершины всех новых приклеенных ребер. Затем в каждой невисячей вершине дерева приклеим одно висячее ребро. Построенное дерево 1/к (Ш) называется универсальным листом с корнем г? С £4(К) (см. рисунок 1.8 в пункте 1.4.2).

По определению лист Щ (М) — отрезок (висячее ребро) и С/1 (К.) «Т^оВ пункте 1.5.1 будет доказано, что все универсальные лисья {^(М)} образуют семейство универсальных графов для базисных вложений в плоскость I х Е (случай п = 2, ш = 0). Универсальный граф £//г (51) получается приклейкой к окружности ровно в к точках по одному висячему ребру и одному универсальному листу6 Универсальный граф С4(Т3-о) получается склейкой по корням четырех универсальных листьев С4х (М) и одного висячего ребра.

Следствие 1.5. Конечный граф С базисно вкладывается в Е х Х^о тогда и только тогда, когда выполнено одно из следующих эквивалентных условий:

1.5а) граф С? не содержит запрещенные подграфы с рисунка 1.3;

1.56) граф С содержится в некотором универсальном графе С/ДТз, 0) (где г>1), см. рисунок 1−4 при г = 1,2,3,4.

XX Хт.

-^5,0 и Т^О У.

5,0 и 7*0 к.

4,0 и ^4,0.

5,0 и Г5>о.

Рисунок 1.3. Запрещенные графы для книжки К х Т3]0.

Т" м Т" 4,0 и 1 4,0 и2(Ъ, о).

Д (Т3, о).

Рисунок 1.4. Универсальные графы для книжки Е х.

Универсальный лист всегда приклеивается по своему корню.

Универсальный граф ?/2*4−1 (Ты) получается приклейкой к окружности в одной точке двух универсальных листьев (К) и одного висячего ребра, а еще в других к — 1 точках — по одному листу ?4 1 (К) и висячему ребру. Универсальный граф ?/2А-(Ты) получается приклейкой к окружности в одной точке универсального графа [//ДТ^о) (по крайней вершине одного из листьев ?41 (К) С ?4(Тз, о)) и одного висячего ребра, а еще в других /с — 1 точках — по одному листу 11к-2(К) и висячему ребру.

Следствие 1.6. Конечный граф С базисно вкладывается в К х 7д тогда и только тогда, когда выполнено одно из следующих эквивалентных условий:

1.6а) граф С не содержит запрещенные подграфы с рисунка 1.5- (1.66) граф С содержится в некотором универсальном графе £/*(Тхд) (где г > 1), см. рисунок 1.6 при г = 1, 2, 3, 4, 5, 6.

51 и 51.

2~5,о и ^5,0.

Тг.

0,2.

5;

3,3 т5, о и Т1 (ьч нн.

4,0 ^ ^4,0.

2,1 ^ Т^о.

Тб.О и 0.

4,0 и ^4,0.

Рисунок 1.5. Запрещенные графы для книжки К х Тд.

ЕМТ,.

Гхд б (Тхд).

Рисунок 1.6. Универсальные графы для книжки М х Тд.

2. Метод трехстраничных вложений И. А. Дынникова.

Во второй главе вложения конечных графов в книжку со страницами применяются к задаче взаимно однозначного кодирования изотопических классов заузленных графов в I3. В пункте 2.1 обсуждаются связи заузленных графов с теорией узлов и смежными областями. В пункте 2.2 вводятся необходимые определения, формулируются результаты И. А. Дынникова о кодировании неориентированных зацеплений и теоремы 2.1−2.2 автора. Пункт 2.3 посвящен алгебраическим и геометрическим следствиям теорем 2.1².2.

2.1. Заузленные графы в трехмерной топологии.

Заузленные графы — это подмножества С С К3, гомеоморфные конечным графам и рассматриваемые с точностью до объемлющей изотопии. Заузленные графы стали интенсивно изучаться на рубеже 90-х годов прошлого века в работах ведущих специалистов по теории узлов [23, 24, 25]. В этих исследованиях заузленные графы появились как естественные обобщения узлов. Сразу же бьы получен аналог теоремы Райдемайстера, описывающий заузленные графы в терминах плоских диаграмм, а также построены аналоги полиномиальных инвариантов узлов. В дальнейшем обнаружились важные связи заузленных графов как с самой теорией узлов, так и со смежными областями.

Например, категории тензорных представлений алгебр Хопфа (которые дают полиномиальные инварианты узлов в терминах квантовых групп) были расширены на все заузленные графы [34]. Японские топологи вслед за Таниямой [40] стали изучать заузленные графы, гомеоморфные фиксированному графу С, с точностью до таких известных в алгебраической топологии эквивалентно-стей, как кобордизмы, гомотопии и гомологии. В этом направлении, например, была получена гомологическая классификация заузленных графов [41] и классификация с точностью до пальцевых движений [42]. Благодаря открытым в 1990 году инвариантам Васильева [43] возрос интерес к сингулярным узлам. По определению сингулярные узлы — это заузленные 4-валентные графы, рассматриваемые с точностью до изотопии, в течение которой окрестность каждой вершины графа лежит в некоторой (непостоянной) плоской площадке. Выяснилось, что конструкция Васильева инвариантов конечного типа применима к любым заузленным графам [37]. Несмотря на значительный интерес к заузлен-ным графам, пока нет серьезных продвижений в следующей задаче.

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

Почти единственным общим результатом по этой теме является характе-ризация заузленных графов С С К3, которые изотопны графам, вложенным в плоскость [35]. А именно, заузленный граф б С I3 можно изотопно переместить в плоскость тогда и только тогда, когда абстрактный граф С является планарным и для любого подграфа С С фундаментальная группа дополнения 7Г1 (Е3 — С) свободна. Важным частным случаем задачи 2 является следующая проблема: для любого заузленного графа С С К3 определить, изотопен ли он своему зеркальному образу. По этому вопросу известно, что планарный 3-связный граф, не имеющий автоморфизмов порядка 2, нельзя вложить в М3 так, чтобы полученный заузленный граф был изотопен своему зеркальному образу [21]. К данному моменту теория заузленных графов уже стала известной темой современной трехмерной топологии. Например, в последний обзор открытых проблем топологии малых размерностей [26] были включены несколько задач (5.15−5.18) по заузленным графам. Среди них — вопрос ха-рактеризации абстрактных самозаузленных графов, любые вложения которых в К3 обязательно содержат нетривиальный узел.

Одним из существенных результатов в теории узлов за последние 5−10 лет является трехстраничный подход И. А. Дынникова к изотопической классификации неориентированных зацеплений в К3 [4, 19]. Метод И. А. Дынникова заключается в изотопном перемещении зацепления в книжку? = ЕхТ3 о с тремя страницами и последующем кодировании полученного вложения. Подобные вложения в книжку с конечным числом страниц, возможно, впервые рассматривались Брюнном в 1898 году [15]. Брюнн доказал, что любой узел изотопен узлу, проекция которого на плоскость К2 имеет ровно одну особую точку. Позднее такие вложения привели к новому инварианту узлов — дуговому индексу [17]. Расширяя свой подход на книжку с произвольным числом страниц, И. А. Дын-ников уменьшил число соотношений в своей кодирующей полугруппе [5]. Недавно И. А. Дынников описал алгоритм, распознающий тривиальный узел монотононным образом с помощью прямоугольных диаграмм, которые тесно связаны с вложениями в книжку со страницами [20].

В настоящей диссертации подход И. А. Дынникова обобщается на произвольные заузленные графы. А именно, задача 2 сводится к алгебраической проблеме равенства центральных элементов в двух сериях конечно определенных полугрупп (теоремы 2.1 и 2.2). Кроме того, вопрос об изотопности заузленно-го графа своему зеркальному образу тоже сведен к проблеме равенства слов в конечно определенных полугруппах (следствие 2.1).

2.2. Взаимно однозначное кодирование заузленных графов.

Введем необходимые определения. Будем рассматривать только неориентированные конечные графы без изолированных вершин с точностью до гомеоморфизма. Поскольку висячие ребра нельзя заузлить, они исключаются. Графы могут быть несвязными, также допускаются петли и мульти-ребра (точные определения этих терминов см. в пункте 1.2 введения).

Определение 2.1 (/с-вершины, п-графы, 7-графы). Если вершина, А графа С имеет степень к, то она кратко называется к-вершиной. Фиксируем целое п > 2. Если граф (7 имеет вершины степени только от 2 до п, то назовем его п-графом. Пусть 3 = О’ъ • • ¦, — произвольное множество целых чисел ^ > 3. Если граф содержит А—вершины только при к = 2 или к € 3, то <7 будет считаться 3-графом.

Например, любой 2-граф состоит из нескольких окружностей, а каждый {4}-граф является по определению 4-валентным графом. Все рассуждения будут вестись в кусочно-линейной категории, т. е. ребра графа при вложении в К3 считаются конечными ломаными.

Определение 2.2 (заузленный граф, жесткая и нежесткая изотопии).

Заузленный п-граф С С К3 — это подмножество пространства К3, гомеоморф-ное произвольному п-графу (7. (См. примеры на левых картинках рисунков 2.11 и 2.12 в параграфе 2.2). Заузленные графы будут изучаться с точностью до двух отношений эквивалентности — жесткой и нежесткой объемлющих изо-топий. Нежесткая объемлющая изотопия между двумя заузленными графами С С I3 и Я С I3 — это такое непрерывное семейство гомеоморфизмов <�рг: М3 —" К3,? € [0,1], что (р0 = гй и = Н. Если потребовать, чтобы в любой момент t € [0,1] объемлющей изотопии окрестность каждой вершины графа <�л (Сг) С М3 лежала в некоторой (непостоянной) плоской площадке, то получится жесткая объемлющая изотопия.

Из определения 2.2 следует, что изотопные графы гомеоморфны, но среди гомеоморфных заузленных графов есть неизотопные друг другу. Например, известно много неизотопных замкнутых кривых в К3, каждая из которых гомеоморфна окружности. Заметим, что введенные выше два понятия объемлющей изотопии совпадают для заузленных 3-графов. Действительно, любую изотопию между заузленными 3-графами можно сделать жесткой. Для этого достаточно держать в некоторой (непостоянной) плоской площадке три дуги, выходящие из каждой вершины. Любой заузленный 2-граф по определению является неориентированным зацеплением. Сингулярные узлы — это заузленные 7-графы при ,/ = {4}, рассматриваемые с точностью до жесткой изотопии. Следующая обобщенная теорема Райдемайстера была первым результатом в теории заузленных графов, перенесенным из классической теории узлов.

Теорема 2А (Джониш-Миллет [23]). Заузленные графы жестко (соответственно, нежестко) изотопны тогда и только тогда, когда их плоские диаграммы можно совместить плоскими изотопиями и движениями Райдемайстера Ш — Я5 (соответственно, Ш — Д4, Д5') с рисунка 2.1.

Я1.

Я2.

ЯЗ т ¦¦¦/ т х.

Рисунок 2.1. Движения Райдемайстера для заузленных графов в Е3.

На рисунке 2.1 многоточие между двумя ребрами обозначает последовательность нескольких ребер. Таким образом, движения Райдемайстера для заузлен-ных графов являются локальными, но двумерными. В параграфе 2.1 вводится линейное кодирование заузленных графов и конечное число локальных движений, порождающих любую объемлющую изотопию между графами в К3.

Определение 2.3 (кодирующий алфавит А&bdquo-). Для каждого п > 2 рассмотрим следующий кодирующий алфавит:

А&bdquo- = { ai, bi, Ci, di, xmji | i e Z3, 3 < m < n}.

Всюду считается, что индекс г принадлежит группе Z3 = {0,1,2}. Например, при п — 2 получается алфавит И. А. Дынникова из [4]:

А2 = { а0, аи а2, Ь0, Ьь Ь2, с0, сь с2, d0, du d2 }.

Общее количество букв алфавита А&bdquoравно д (п) = 3(п + 2). Геометрическая интерпретация букв алфавита A" будет дана в пункте 2.1.1.

Определение 2.4 (универсальные полугруппы7 RSGn и NSGn). Пусть RSGn — полугруппа, заданная образующими из алфавита А&bdquoи определяющими соотношениями (1)—(10). Предполагается, что целочисленные параметры m, p, q удовлетворяют неравенствам 3 < m < п, 2 < р < и 2 < q <

1) d0dxd2 = 1;

2) bidi = dibi = 1;

3) ai — ai+idi-i: bj = Oj-iCj+i, Ci = bjiCj+i, d" = 1>

4) с) C 15 x2q, i-l — dj1 (bi+iX2qjdi+i)bJl ;

5) X2p-i, id% = ai (x2P-ijd = ^(Щ x2p-i, ibi) cj;

6) diX2q, id4~l = ai (diX2qiidqi~1)ci, bqflx2qiibi = сц{Щ~1×2ч^Ьг)сй.

7) (dlci)w = w (diCi), где ги € {сг+ь bidi+1di, xmti+1};

8) uv = vu, где и G {a^, б^с^-Д, х2р-, А, diX2qiibi}, v € {ui+ii ^t+i> ci+i) bidi+di, xmi+i}-,.

9) {x2p-ijbi)DPti = ?VmO^-u&i). где Dk) i = dfd^d^^k > 1);

10) {diX2qibi)Dqi = D^ildiX^ibi).

Заменим соотношения (9)-(10) на (9') x^ib^dfdf^d,^^ — хт, ФгЧерез NSGn обозначим полугруппу, порожденную образующими из А&bdquoи соотношениями (1) — (8), (9'). Для множества J = {ji,., j/J целых чисел ji > 3 введем полугруппу RSGj, порожденную буквами {ai, bi: Ci, di, xm>i | г G Z3, m G J} и соотношениями (1)—(10), содержащими только эти буквы. Пусть полугруппа NSGj задается теми же буквами из А&bdquoи соотношениями (1)—(8), (9') при m G J.

Все полугруппы RSGn, NSGn имеют единичный элемент — пустое слово, т. е. являются моноидами. Одно из соотношений (2) избыточно: его можно получить из равенства (1) и остальных соотношений (2). Тогда общее количество.

7RSG = rigig spatial graphs, NSG = non-rigid spatial graphs. соотношений (1)—(10) равно r (n) = 3(п2+7п—2). Полугруппа NSGn имеет то же количество образующих и определяющих соотношений, что и RSGn. Если множество J содержит |J| элементов, то полугруппы RSGj и NSGj порождаются 3(4 + | J) буквами и 3(16 + 11| J + J2) соотношениями. Например, полугруппа8 И. А. Дынникова DS = RSG2 = NSG2 задается 12 образующими из А2 и 48 соотношеними (1)—(10), не содержащими букв xm>i. Первоначально в работе [4] полугруппа DS порождалась 54 соотношениями, но впоследствии 6 соотношений оказались лишними. Полугруппы RSG3 = NSGj, и RSG{4} задаются 15 образующими и 84 соотношениями, а полугруппы RSG4 Щ NSG4 — 18 образующими и 126 соотношениями. Элемент полугруппы называется центральным, если он коммутирует со всеми остальными элементами этой полугруппы.

Теорема 2 В (И. А. Дынников [4]). Каждое неориентированное зацепление L С R3 кодируется некоторым элементом wi полугруппы DS.

Теорема 2С (И. А. Дынников [4]). Два неориентированных зацепления К, L С R3 изотопны тогда и только тогда, когда в полугруппе DS имеем wk = wl.

Теорема 2D (И. А. Дынников [4]). Элемент w € DS кодирует некоторое неориентированное зацепление в R3 тогда и только тогда, когда w — центральный элемент полугруппы DS.

Коротко главный результат И. А. Дынникова формулируется так: «центр полугруппы DS взаимно однозначно кодирует (с точностью до объемлющей изотопии) все неориентированные зацепления в R3». И. А. Дынников описал группу DG обратимых элементов в своей полугруппе DS.

Теорема 2Е (И. А. Дынников [4]). Группа DG имеет следующее задание:

DG = {х, у [[х, у], х2ух~2} = [[х, у], у2ху'2} = [[х, у], [ж-1, у'1] = 1), [х, у] = хух~1у.

Коммутант [DG, DG] изоморфен группе кос Воо из бесконечного числа нитей.

Теоремы 2B-2D являются частными случаями (при п = 2) теоремы 2.1, которую также удобно разбить на три части.

Теорема 2.1а. Каждый заузленный n-граф G С R3 кодируется некоторым элементом wq полугруппы RSGn.

Теорема 2.16. Любые два заузленных n-графа G, Н С R3 жестко изотопны тогда и только тогда, когда в полугруппе RSGn имеем wq = wh.

Теорема 2.1 В. Элемент w G RSGn кодирует некоторый заузленный п-граф в R3 тогда и только тогда, когда w — центральный элемент полугруппы RSGn. Алгоритм, определяющий, является ли данный элемент w G RSGn центральным, имеет линейную сложность по длине слова w.

Коротко теорему 2.1 можно сформулировать так: «центр полугруппы RSGn взаимно однозначно кодирует с точностью до жесткой объемлющей изотопии все заузленные n-графы в R3». Например, центр полугруппы RSG3 = NSG3 взаимно однозначно кодирует все заузленные трехвалентные графы. Полугруппа Stg с таким же свойством была построена в работе [10], она порождается.

8Всюду в диссертации изоморфизм полугрупп и групп обозначается через й.

24 образующими и 90 соотношениями. В примере 2.2 (пункт 2.1.2) демонстрируется связь между полугруппами ЯЬд и = N303. А центр полугруппы взаимно однозначно кодирует (с точностью до жесткой изотопии) все заузленные графы с вершинами степени только 3 и 4. В параграфе 2.1 дается геометрическая интерпретация полугруппы Я, ЗОп. Там же описывается план доказательства теоремы 2.1. Самая существенная часть теоремы 2.1 (при п = 3) доказана в [10], общий случай — в [11].

Фактически, теорема 2.1 сводит топологическую задачу жесткой изотопической классификации заузленных графов к алгебраической проблеме равенства центральных элементов в конечно определенных полугруппах Дб’Сп. В некоторых частных случаях эту проблему удается решить в явном виде. Например, в параграфе 2.6 настоящей диссертации получена классификация бесконечного семейства сингулярных узлов, имеющих простые трехстраничные вложения (предложения 2.4 и 2.5). Там же исследован подход к проблеме равенства слов с помощью теории представлений групп. Оказалось, что при гомоморфизме полугрупп в ассоциированные группы теряется большая часть информации о заузленных графах (предложение 2.8). Этот отрицательный результат подчеркивает сложность задачи полной классификации заузленных графов. Результаты параграфа 2.6 не относятся к основным, они только демонстрируют возможные подходы к эффективной классификации заузленных графов.

Теорема 2.2. Центр полугруппы взаимно однозначно кодирует с точностью до нежесткой объемлющей изотопии все заузленные п-графы в К3. Алгоритм, определяющий, является ли данный элемент V € NSGn центральным, имеет линейную сложность по длине слова V.

Как и в случае жесткой изотопии при п = 2 полугруппа Л^Сг совпадает с полугруппой И. А. Дынникова 05 Для п — 3 оба понятия изотопии на заузленных графах одинаковы, поэтому = 3. Но при п > 3 эти две серии полугрупп расходятся: «Щ NSGn, см. пример 2.2 в пункте 2.1.2.

2.3. Алгебраические и геометрические следствия.

В этом пункте формулируются следствия теорем 2.1−2.2.

Определение 2.5 (антиавтоморфизмы рп,?п, зеркальный образ). Рассмотрим следующее преобразование9 слов в алфавите Ап:

Г Рп{аг) = Сг-, Рп (Ьг) = ¿-г, рп (Сг) = аг, /9"(с/г) = Рп{х2р-1,г) = Рп{х2д, г) = ж2д, г.

Отображение рп по формуле рп (иу) = рп{и)рп (и) продолжается до инволютив-ных антиавтоморфизмов рп: ЯЗОп —>¦ В, ЗОп и еп: АгЗОп —> МЗСп. Аналогично определяются антиавтоморфизмы р]: RSGJ —"¦ J я? J: N30J —> NSGJ. Зеркальный образ графа С С К3 — это граф С С Е3, который получается из С отражением относительно некоторой двумерной плоскости в К3.

При помощи антиавтоморфизмов рп, еп вопрос об изотопности заузленного графа своему зеркальному образу также сводится к проблеме равенства слов.

9Как обычно, считается i е Ъз, 2 < р < 2 < д < число п фиксировано.

Следствие 2.1. а) Пусть заузленный n-граф С? С К3 кодируется некоторым центральным элементом wg? RSGn (см. теорему 2.1а). Заузленный граф G жестко изотопен своему зеркальному образу тогда и только тогда, когда в полугруппе RSGn имеем wq = pn{wG)б) Пусть заузленный n-граф G С К3 кодируется некоторым центральным элементом vg? NSGn (см. теорему 2.2). Заузленный граф G нежестко изотопен своему зеркальному образу тогда и только тогда, когда в полугруппе NSGn имеем vq = ?n{vG)¦

Следствие 2.2. а) При любых п > m > 2 естественное отображение RSGm —> RSGn является мономорфизмом полугрупп. Группа всех обратимых элементов полугруппы RSGn изоморфна группе И. А. Дынникова DG. б) При любых п > m > 2 естественное отображение NSGm —>¦ NSGn является мономорфизмом полугрупп. Группа всех обратимых элементов полугруппы NSGn изоморфна группе DG.

Метод трехстраничных вложений И. А. Дынникова можно применить также и к произвольным заузленным J-графам.

Следствие 2.3. а) Центр полугруппы RSGj (соответственно, NSGj) взаимно однозначно кодирует с точностью до жесткой (соответственно, нежесткой) объемлющей изотопии все заузленные J-графы в R3. Алгоритм, определяющий, является ли элемент w? RSG j (соответственно, v? NSG j) центральным, имеет линейную сложность по его длине. б) Пусть заузленный ./-граф G С К3 кодируется некоторым центральным элементом wg? RSGj (соответственно, vg? NSGj). Заузленный граф G жестко (соответственно, нежестко) изотопен своему зеркальному образу тогда и только тогда, когда в полугруппе RSGj имеем wg = Pj{wg) (соответственно, в полугруппе NSGj имеем vG = £j (vg))в) Для любого подмножества К С J естественные отображения RSGk —> RSGj и NSG к —> NSGj являются мономорфизмами полугрупп. Группы всех обратимых элементов полугрупп RSG j и NSG j изоморфны группе DG.

Например, центр полугруппы RSG{4} = S К из [3] взаимно однозначно кодирует все неориентированные сингулярные узлы в R3. А центр полугруппы NSG{4} взаимно однозначно кодирует (с точностью до нежесткой изотопии) все заузленные 4-валентные графы. Следующее следствие является обобщением (при J = 0) теоремы Брюнна [15], где впервые фигурируют вложения узлов в книжку со страницами.

Следствие 2.4. Любой заузленный /-граф G С К3, рассматриваемый с точностью до нежесткой изотопии, можно спроектировать на плоскость М2 с единственной особой точкой.

В первой главе диссертации рассматриваются базисные вложения графов в книжку со страницами M х T"jm. А что можно сказать о топологических вложениях конечных графов в те же книжки? Оказывается, решение этой задачи вытекает из доказательства теоремы 2.1а. В следующем утверждении конечный граф G может иметь и висячие вершины.

Следствие 2.5. Любой конечный граф G топологически вкладывается в книжку R х Т3о всего с тремя страницами (а значит, и в любую книжку Кх при п + 2 т > 3).

Все утверждения в диссертации имеют двойную нумерацию. Первое число (1 или 2) обозначает номер главы, а второе — номер соответствующего утверждения внутри главы. Главные результаты диссертации — это теоремы 1.1 и 2.1−2.2. К основным выводам также относятся следствия 1.1−1.3 и 2.1. Промежуточные результаты названы предложениями, леммами и утверждениями (по убыванию важности). Диссертация содержит 15 предложений, 18 лемм и 20 утверждений. Благодаря такому разбиению вывод каждого вспомогательного результата занимает не более полутора страниц. Кроме того, для удобства читателя текст снабжен 45 примерами и 25 рисунками.

Список литературы

содержит 43 наименования, общий объем текста 105 страниц.

Благодарности. Автор признателен своим научным руководителям Виктору Матвеевичу Бухштаберу и Аркадию Борисовичу Скопенкову за постановку задач и внимание к исследованиям. Автор благодарен Ивану Алексеевичу Дын-никову и Владимиру Валентиновичу Вершинину за многократные обсуждения результатов и ряд ценных замечаний. Диссертант благодарит РФФИ и фонд ИНТАС за частичную финансовую поддержку во время написания диссертации. Автор выражает свою признательность за гостеприимство университетам Монпелье, Ливерпуля, Дижона, Тулузы и Парижа, а также лично — Владимиру Вершинину, Хью Мортону, Луису Пари, Степану Оревкову и Пьеру Вожелю, работавшим вместе с диссертантом в рамках гранта ИНТАС YS 2001/2−30.

1. В. И. Арнольд, О функциях от трех аргументов, Доклады АН СССР, 1957, том 114, стр. 679−681.

2. В. И. Арнольд, Представление непрерывных функций трех переменных в виде суперпозиции непрерывных функций двух переменных, Математический сборник, 1962, том 56, стр. 3−92.

3. В. В. Вершинин, В. А. Курлин. Трехстраничные вложения сингулярных узлов. Функциональный анализ и его приложения, 2003, том 37, вып. 4.

4. И. А. Дынников, Трехстраничный подход в теории узлов, Функциональный анализ и его приложения, 1999, том 33, вып. 4, стр. 25−37 и 2000, том 34, вып. 1, стр. 29−40.

5. И. А. Дынников, Конечно определенные группы и полугруппы в теории узлов, Труды Математического института им. В. А. Стеклова, 2000, том 231, Динамические системы, автоморфизмы и бесконечные группы, стр. 231−248.

6. А. Н. Колмогоров, О представлении непрерывных функций нескольких переменных в виде суперпозиции непрерывных функций меньшего числа переменных, Доклады АН СССР, 1956, том 108, стр. 179−182.

7. А. Н. Колмогоров, О представлении непрерывных функций многих переменных в виде суперпозиции непрерывных функций одного переменного и сложения, Доклады АН СССР, 1957, том 114, вып. 5, стр. 953−956.

8. Р. Кроуэлл, Р. Фокс, Введение в теорию узлов, М., Мир, 1967.

9. В. А. Курлин. Редукция оснащенных зацеплений к обычным, Успехи математических наук, 1999, том 54, вып. 4, стр. 177−178.

10. В. А. Курлин. Трехстраничные диаграммы Дынникова заузленных трехвалентных графов, Функциональный анализ и его приложения, 2001, том 35, вып. 3, стр. 84−88.

11. A. Baran, D. Repovs, Zeljko, On basic embeddings into the plane (preprint), University of Ljubljana, 2003.

12. H. Brunn, Uber verknotete Kurven, Verhandlungen des ersten Internationalen Mathematiker-Kongresses (Zurich 1897), Leipzig, 1898, p. 256−259.

13. G. Burde, H. Zieschang. Knots, de Gruyter Studies in Mathematics, v. 5, Berlin, 1985.

14. P. R. Cromwell, I. J. Nutt, Embedding knots and links in an open book II, Bounds on arc index. Math. Proc. Cambridge Philos. Soc., 1996, v. 119, no. 2, 309−319.

15. A. Cavicchioli, D. Repovs, A. B. Skopenkov, Open problems on graphs, arising from geometric topology, Topology and its Applications, 1998, v. 84, p. 207 226.

16. I. A. Dynnikov, A new way to represent links. One-dimensional formalism and untangling technology, Acta Appl. Math., 2001, v. 69, p. 243−283.

17. I. A. Dynnikov, Arc presentation of links. Monotonie simplification (preprint), available at http://front.math.ucdavis.edu/math.GT/208 153.

18. E. Flapan, Rigity of graph symmetries in the 3-sphere, J. Knot Theory Ramif., 1995, v. 4, p. 373−388.

19. B. Gemein. Representations of the singular braid monoid and group invariants of singular knots, Topology and Its Applications, 2001, v. 114, no. 1, 117−140.

20. D. Jonish, К. C. Millett, Isotopy invariants of graphs. Trans. Amer. Math. Soc., 1991, v. 327, no. 2, p. 655−702.

21. L. Kauffman, Invariants of graphs in three-space. Trans. Amer. Math. Soc., 1989, v. 311, no. 2, p. 697−710.

22. L. Kauffman, P. Vogel, Link polynomials and a graphical calculus, J. Knot Theory Ramifications, 1992, v. 1, no. 1, p. 59−104.

23. R. Kirby, Problems in low-dimensional topology, edited by Rob Kirby, AMS/IP Stud. Adv. Math., 2.2, Geometric topology (Athens, GA, 1993), 35−473, Amer. Math. Soc., Providence, RI, 1997.

24. K. Kuratowski, Sur les problemes des courbes gauches en topologie, Fund. Math., 1930.

25. V. A. Kurlin, Basic embeddings into a product of graphs, Topology and Its Applications, 2000, v. 102, no. 2, p. 113−137.

26. V. A. Kurlin, Kolmogorov-Arnold's solution of Hilbert’s 13th problem and basic embeddings of graphs, Abstracts of the International conference «Kol-mogorov and contemporary mathematics» (Moscow, June 2003), p. 822.

27. H. R. Morton, E. Beltrami, Arc index and the Kauffman polynomial, Math. Proc. Cambridge Philos. Soc., 1998, v. 123, p. 41−48.

28. N. Mramor-Kosta, E. Trenklerova, On basic embeddings of compacta into the plane (preprint), University of Ljubljana, 2003.

29. L. Neuuiirth, Star projections of knots, In Algebraic and Differential Topology — Global Differential Geometry, p. 198−205, Teubner texts, v. 70, 1984.

30. P. Ostrand, Dimension of metric spaces and Hilbert’s problem 13, Bull. AMS, 1965, v. 7, p. 619−622.

31. N. Yu. Reshitikhin, V. G. Turaev, Ribbon graphs and their invariants derived from quantum groups, Comm. Math. Physics, 1990, v. 127, p. 1−26.

32. M. Scharlemann, A. Thompson, Detecting unknoted graphs in 3-space, J. Differential Geometry, 1991, v. 34, no. 2, p. 539−560.

33. A. B. Skopenkov, A description of continua basically embeddable in R2, Topology Appl., 1995, v. 65, no. 1, p. 29−48.

34. T. Stenford, Finite-type invariants of knots, links, and graphs, Topology, 1996, v. 35, no. 4, p. 1027−1050.

35. Y. Sternfeld, Hilbert’s 13th problem and dimension, Lecture Notes in Math., v. 1376 (Springer, 1989), p. 1−49.

36. Y. Sternfeld, Mappings in dendrites and dimension, Houston J. Math., 1993, v. 19, no. 3, p. 483−497.

37. K. Taniayma, Cobordism, homotopy and homology of graphs in R3, Topology, 1994, v. 33, no. 3, p. 509−523.

38. K. Taniayma, Homology classification of spatial embeddings of a graph, Topology Appl., 1995, v. 65, p. 205−228.

39. K. Taniyama, A. Yasuhara, Clasp-pass moves on knots, links and spatial graphs, Topology Appl., 2002, v. 122, p. 501−529.

40. V. A. Vassiliev, Cohomology of knot spaces, in Theory of singularities and its applications, Advances in Soviet Mathematics, 1990, v. 1, p. 23−70.