Базисные вложения графов и метод трехстраничных вложений И. А. Дынникова тема автореферата и диссертации по математике, 01.01.04 ВАК РФ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М. В. Ломоносова

Механико-математический факультет

На нравах рукописи УДК 515.142 и 515.162

Курлин Виталий Александрович

БАЗИСНЫЕ ВЛОЖЕНИЯ ГРАФОВ И МЕТОД ТРЕХСТРАНИЧНЫХ ВЛОЖЕНИЙ И. А. ДЫННИКОВА

01.01.04 — геометрия и топология

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

лМ

Москва, 2003

Работа выполнена на кафедре высшей геометрии и топологии механико-математического факультета Московского государственного университета имени М. В. Ломоносова.

Научные руководители: доктор физико-математических наук,

профессор В. М. Бухштабер; доктор физико-математических наук, доцент А. Б. Скопенков.

Официальные оппоненты: доктор физико-математических наук,

профессор Е. В. Щепин; кандидат физико-математических наук, доцент А. Б. Сосинский.

Ведущая организация: Челябинский государственный

университет.

Защита состоится " 3» ошя5ря 2003 года в 16 часов 15 минут на заседании диссертационного совета Д.501.001.84 в Московском государственном университете имени М. В. Ломоносова по адресу 119992, ГСП-2, Москва, Ленинские Горы, Московский государственный университет имени М. В. Ломоносова, механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке механико-математического факультета МГУ (Главное здание, 14 этаж).

Автореферат разослан "2 "сентября 2003 г.

Ученый секретарь диссертационного совета Д.501.001.84 в МГУ, доктор физико-математических наук, профессор

В. Н. Чубариков

йосг-А

Общая характеристика работы

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

Д. Гильберт сформулировал свою знаменитую 13-ю проблему так: "доказать, что уравнение 7-й степени х7 + ах3 + Ьх2 + сх + 1 = 0 имеет решения (непрерывно зависящие от параметров а, Ь, с), которые не выражаются в виде суперпозиции непрерывных функций только двух аргументов". А. Н. Колмогоров1 каждую непрерывную функцию многих переменных сумел представить в виде суперпозиции непрерывных функций только трех переменных. Затем В. И. Арнольд2 случай трех переменных свел к случаю двух. После этого А. Н. Колмогоров3 обобщил эти результаты, представив каждую функцию, непрерывную на п-мерном кубе /", в виде суммы (2п+1)-ой непрерывной функции одного переменного. Эта теорема не только опровергла гипотезу Д. Гильберта, но и поставила много новых вопросов.

Рассмотрим только топологическое направление, развитое Я. Штер-нфельдом, который переформулировал теорему А. Н. Колмогорова на топологическом языке, введя понятие базисного вложения. Под топологическим вложением понимается гомеоморфизм на образ. Пусть X и (1 < г < к) — компактные метрические пространства. Вложение X С называется базисным, если каждая непрерывная функ-

ция / : X К представляется в виде /(я) = «/¿(а^), где функции : X —>■ К непрерывны, х = (хь.. . е X, ж,- б Х{. Таким образом, свойство базисности усиливает понятие топологического вложения. Ослабленная версия теоремы А. Н. Колмогорова утверждает, что п-мерный куб 1п базисно вкладывается в К2п+1. Здесь и далее через Кт обозначается прямое произведение ш > 2 экземпляров прямой К.

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

2В. И. Арнольд, О функциях от трех аргументов, Доклады АН СССР, 1957, том 114, стр. 679-681. ®А. Н. Колмогоров, О представлении непрерывных функций многих переменных в вяд/е суперпо-

зиции непрерывных функций одного переменного и сложения, том И4,

вып. 5, стр. 953-956. ' ? БлИОТЕКА 1

1 С. Петербург г-о Л ;

оэ 3009 ш*мп

П. Острандом и Я. Штернфельдом4 было доказано, что компактное метрическое пространство X базисно вкладывается в Rm (m > 3) тогда и только тогда, когда dim X < Последнее утверждение усиливает известную теорему Небелинга-Менгера о том, что любое п-мерное компактное метрическое пространство X топологически вкладывается в R2n+1. Заметим, что, в отличие от топологического вложения, понятие базисного вложения позволяет охарактеризовать размерность компакта в терминах непрерывных функций на нем. При т — 1 понятия топологического и базисного вложения совпадают, но случай плоскости m = 2 еще до конца не разобран. Известно только описание5 линейно-связных 1-мерных компактов, базисно вложимых в Мх R.

Недавно появилось простое доказательство6 критерия Я. Штерн-фельда базисного вложения в плоскость MxR. Также было проверено7, что для конечных графов базисная вложимость в плоскость RxR в непрерывном смысле эквивалентна базисной вложимости в гладком смысле. Хотя размерность 2тг+1 в теореме А. Н. Колмогорова уменьшить нельзя, Я. Штернфельд доказал, что каждый компакт X базисно вкладывается в произведение R х f|"=1 Х^ где Х( — некоторые 1-мерные компакты (1 < i < тг), тогда и только тогда, когда dimX < п. Последняя теорема тривиальна при п = 1. Однако, в этом случае можно рассмотреть следующие две открытые проблемы.

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

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

В обзоре по открытым проблемам геометрической топологии8 задача 1а была сформулирована в случае, когда X — конечный граф, а

Ostrand, Dimension of metric spaces and Hilbert's problem 13, Bull. AMS, 1969, v.7, p.619-622. Ya. Sternfeld, Hilbert's 13th problem and dimension, Lecture Notes in Math., 1989, v. 1376, p. 1-49.

®A. B. Skopenkov, A desription of continua basically embeddable in R2, Topology and Its Applications, 1995, v. 65, no 1, p. 29-48.

®N. Mramor-Kosta, E. Trenklerova, On basic embeddings of compact;» into the plane (preprint), University of Ljubljana, 2003.

^A. Bar an, D. RepovS, ¿eljko, On basic embeddings into the plane (preprint), Ljubljana, 2003.

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

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

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

Например, полиномиальные инварианты узлов, определенные в терминах линейных представлений квантовых групп, были расширены на произвольные заузленные графы11. А именно, был построен ковари-антный функтор из категории ленточных графов в категорию тензорных представлений любой квазитреугольной алгебры Хопфа. Японские топологи вслед за К. Таниямой12 стали изучать заузленные графы в С К3, гомеоморфные фиксированному конечному графу С7, с точностью до таких известных в алгебраической топологии эквивалентно-стей, как кобордизмы, гомотопии и гомологии. В этом направлении, например, была получена гомологическая классификация заузленных

9Ya. Sternfeld, Mappings in dendrites and dimension, Houston J. Math., 1993, v.19, no. 3, p.483-497.

h>l. h. Kauffman, Invariants of graphs in three-space, Trans. ams, 1989, v. 311, no. 2, p. 697710. D. Jonish, K. C. Millet, Isotopy invariants of graphs, Trans. ams, 1991, v. 327, no. 2, p. 655702. L. H. Kauifman, P. Vogel, Link polynomials and a graphical calculus, J. Knot Theory and Its Ramifications, 1992, v. 1, no. 1, p. 59-14. 11N

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

. Taniayma, Cobordism, homotopy and homology of graphs in R*, Topology, 1994, v. 33, no. 3, p. 509-523.

графов и классификация с точностью до пальцевых движений13. Благодаря открытым в 1990 году инвариантам В. А. Васильева14 возрос интерес к сингулярным узлам. По определению, сингулярные узлы — это заузленные 4-валентные графы, рассматриваемые с точностью до изотопии, в течение которой окрестность каждой вершины графа лежит в некоторой (непостоянной) плоской площадке. Выяснилось, что конструкция инвариантов В. А. Васильева применима к любым зауз-ленным графам15. Несмотря на значительный интерес к заузленным графам, пока нет серьезных продвижений в следующей задаче.

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

Почти единственным общим результатом по этой теме является ха-рактеризация заузленных графов Gel®, которые изотопны графам, вложенным в плоскость16. А именно, заузленный граф G С R3 можно изотопно переместить в плоскость тогда и только тогда, когда абстрактный граф G является планарным и для любого подграфа G' С G фундаментальная группа дополнения 7i"i (Ж3 — G') свободна. Важным частным случаем задачи 2 является следующая проблема: для любого заузленного графа GcR3 определить, изотопен ли он своему зеркальному образу. По этому вопросу известно, что планарный 3-связный граф, не имеющий автоморфизмов порядка 2, нельзя вложить в R3 так, чтобы полученный заузленный граф был изотопен своему зеркальному образу17. К данному моменту теория заузленных графов уже стала известной темой современной трехмерной топологии. Например, в последний обзор открытых проблем топологии малых размерностей18 были включены несколько задач (5.15-5.18) по заузленным графам. Среди них — вопрос характеризации самозаузленных графов, любые вложения которых в К3 обязательно содержат нетривиальный узел.

13к

. Taniayma, Homology classification of spatial embeddings of a graph, Topology and Its Applications, 1995, v. 65, p. 205-228. K. Taniyama, A. Yasuhara, Clasp-pass moves on knots, links and spatial graphs, Topology and Its Applications, 2002, v. 122, p. 501-529.

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

15T. Stenford, Finite-type invariants of knots, links, and graphs, Topology, 1996, v. 35, no. 4, p. 10271050.

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

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

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

Одним из существенных результатов теории узлов за последние 510 лет является трехстраничный подход И. А. Дынникова19 к изотопической классификации неориентированных зацеплений в R3. Недавно И. А. Дынников, развивая свой метод, построил алгоритм, распутывающий любой тривиальный узел монотонным образом20. Эти результат ты послужили отправной точкой для расширения метода трехстранич-ных вложений И. А. Дынникова на произвольные заузленные графы.

Цель работы. Цель настоящей диссертации — развить теорию базисных вложений и заузленных графов на основе современных достижений геометрической топологии. Центральными результатами работы являются:

( 1) эффективный алгоритмический критерий базисной вложимости

конечных графов в произведение К х Тп>т (теорема 1.1 и следствие 1.1); здесь букет Tnim получается такой склейкой п отрезков (в каждом из t которых выделен один конец) и m окружностей (в каждой из которых

выделено по точке), что все выделенные точки склеиваются в одну;

2) взаимно однозначное кодирование всех изотопических классов произвольных заузленных графов в К3 центральными элементами двух серий конечно определенных полугрупп (теоремы 2.1 и 2.2).

Методы исследования. В работе используются топологические и геометрические методы в теории базисных вложений графов, теория алгебраических полугрупп, комбинаторные методы трехмерной топологии и трехстраничный подход И. А. Дынникова. Например, введенное автором понятие дефекта позволило сформулировать главный результат первой главы — критерий базисной вложимости (теорема 1.1) — в доступной и понятной форме. Несмотря на простоту формулировки доказательство требует длительных построений с применением большого количества геометрических идей. При выводе основного результата второй главы — взаимно однозначного кодирования изотопических классов заузленных графов центральными элементами конечно определенных полугрупп RSGn и NSGn (теоремы 2.1 и 2.2) — детальный анализ геометрических конструкций позволил диссертанту

А. Дынников, Трехстраничный подход в теории узлов, Функциональный анализ и его приложения, 1999, том 33, вып. 4, стр. 25-37 и 2000, том 34, вып. 1, стр. 29-40. И. А. Дынников, Конечно определенные группы и полугруппы в теории узлов, Труды Математического института имени В. А. Стеклова, 2000, том 231, Динамические системы, автоморфизмы и бесконечные группы, стр. 231-248.1. A. Dynnikov, A new way to represent links. One-dimensional formalisai and untangling technology, Acta Appl. Math., 2001, v. 69, p. 243-283.

Щ. A. Dynnikov, Arc-presentations of links. Monotonie simplification (preprint), available at http://front-math.ucdavis.edu/math.GT/0208153.

минимизировать количество образующих и соотношений кодирующих полугрупп. В частности, оказалось, что полугруппа И. А. Дынникова (случай п — 2) задается не более чем 48 соотношениями, т.е. 6 соотношений в исходном задании И. А. Дынникова были лишними.

Научная новизна. Результаты диссертации являются новыми и состоят в следующем.

1) Получен эффективный алгоритмический критерий базисной вло-жимости конечных графов в произведение К х Тп,т (теорема 1.1 и следствие 1.1). Здесь букет Тп<т получается такой склейкой п отрезков (в каждом из которых выделен один конец) и т окружностей (в каждой из которых выделено по точке), что все выделенные точки < склеиваются в одну.

2) Доказано, что семейство {КхТп,т | п,т > 0,п+2т > 2} является универсальным в том смысле, что для каждого конечного графа б , найдется такой минимальный (по вложению) букет Тщт, что граф С? базисно вкладывается в произведение Ж х Тп,т (следствие 1.2).

3) Доказана конечность семейства запрещенных графов для базисных вложений в произведение Ж х Тп<т (следствие 1.3).

4) Для каждого п > 2 построены конечно определенные полугруппы ЯЯС?,, и Мввп, центры которых взаимно однозначно кодируют все изотопические классы заузленных графов в К3 (теоремы 2.1 и 2.2).

5) Построены такие инволютивные антиавтоморфизмы рп : —» Л5Стп и £п : п, что пересечения центров полугрупп Д5С!„ и Лг5(?п с множествами неподвижных точек морфизмов рп, еп взаимно однозначно кодируют все заузленные графы, изотопные своим зеркальным образам в К3 (следствие 2.1).

Теоретическая и практическая ценность. Работа носит теоретический характер. Результаты диссертации могут быть использованы в исследованиях по геометрической топологии и теории заузленных графов в Е3. Такие исследования проводятся в том числе в Московском государственном университете имени М. В. Ломоносова, Математическом институте Российской Академии Наук имени В. А. Стеклова, Санкт-Петербургском государственном университете и Челябинском государственном университете.

Апробация. Результаты диссертации докладывались на следующих семинарах и конференциях:

1) Семинар кафедры общей топологии и геометрии механико-математического факультета МГУ под руководством В. В. Федорчу-ка, Москва, октябрь 1996 и февраль 2003.

2) Семинар лаборатории общей топологии Математического института Российской Академии Наук имени В. А. Стеклова под руководством Е. В. Щепина, Москва, март 1997.

3) Конференция молодых ученых механико-математического факультета МГУ, Москва, апрель 1997 и апрель 2000.

4) Ежегодная конференция " Александровские Чтения", посвященная памяти П. С. Александрова, Москва, май 1997 и май 2000.

5) Семинар "Алгебраическая топология и вычислительная геометрия" кафедры высшей геометрии и топологии мех-мата МГУ под

* руководством В. М. Бухштабера, Москва, февраль 2000.

6) Международная конференция "Geometry and Applications", Новосибирск, март 2000.

. 7) Международная конференция "Combinatorics, Dynamics and Prob-

ability", Стокгольм (Швеция), октябрь 2000.

8) Международная конференция "Graphs and Patterns in Mathematics and Theoretical Physics", Стони Брук (США), июнь 2001.

9) Семинар по алгебре, геометрии и алгебраической топологии математического факультета университета Монпелье II, Монпелье (Франция), апрель 2002.

10) Международная конференция Лондонского математического общества "Knot theory, Algebraic Geometry and related topics", Ливерпуль (Велико британия), июнь 2002.

11) Коллоквиум кафедры чистой математики Ливерпульского университета под руководством Мэри Рис, Ливерпуль (Великобритания), октябрь 2002.

12) Геометрический семинар математического факультета Манчестерского университета под руководством Найджела Рэя и Федора Воронова, Манчестер (Великобритания), октябрь 2002.

13) Семинар по маломерной топологии математического факультета Дижонского университета под руководством Дэниэла Лайнса и Луиса Пари, Дижон (Франция), март 2003.

14) Семинар по топологии математического факультета Тулузского университета под руководством Томаса Фидлера, Тулуза (Франция), апрель 2003.

15) Семинар по топологии университета Париж-7 под руководством Пьера Вожеля, Париж (Франция), май 2003.

16) Международная конференция "Kolmogorov and contemporary mathematics", посвященная 100-летию A. H. Колмогорова, Москва, июнь 2003.

Публикации. Содержание диссертации опубликовано в четырех статьях, список которых приведен в конце автореферата.

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

Содержание диссертации

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

Первая глава посвящена доказательству критерия базисной вложи-мости конечных графов в книжку RxTn>m. Здесь букет ТП)ТП получается такой склейкой п отрезков (в каждом из которых выделен один конец) и т окружностей (в каждой из которых выделено по точке), что все выделенные точки склеиваются в одну. Пусть G,X,Y — произвольные конечные графы. Вложение G С X х У называется базисным, если для любой непрерывной функции / : G R существуют такие непрерывные функции д :Х h:Y Ж, что /(х, у) = д(х) 4- h(y) при всех (х,у) eGcXxY.

Опишем класс графов, базисные вложения которых будут рассматриваться. Под конечным графом G понимается произвольный 1-мерный клеточный комплекс с конечным числом клеток. Его 0-мерные клетки называются вершинами, а 1-мерные — ребрами. Ребро I примыкает к вершине v, если точка v содержится в замыкании клетки I. Степень deg v вершины v G G равна числу ребер графа

(2, примыкающих к ней. Вершины степени 0 называются изолированными. Граф может быть несвязным, но изолированные вершины не рассматриваются. Мулъти-ребро — это набор ребер, примыкающих к одной паре вершин, а петля — это ребро, примыкающее ровно к одной вершине. Все графы считаются неориентированными. Допускаются петли и мульти-ребра. Графы изучаются с точностью до произвольного гомеоморфизма.

Для формулировки основного результата введем дополнительные понятия. Пусть (? — произвольный конечный граф. Через #(? обозначим количество связных компонент графа (?. По определению, первое число Бетти 6(£7) графа б равно — где — эйлерова характеристика графа С. Например, дерево С — это связный граф с первым числом Бетти Ь(С?) = 0. Ребро, примыкающее к вершине степени 1, будет называться висячим. Вершина V 6 С? считается ке-разветпвленной, если к ней примыкает висячее ребро, и разветвленной в противном случае. Вершина и € (7 называется сложной, если либо ее степень > 5, либо <1е§и = 4 и она является разветвленной. Дефект 6(СИ) графа в — это сумма £(с1е§г; — 2) по всем сложным

V

вершинам и графа СУ. Следующая теорема 1.1 решает задачу 1а (см. актуальность темы) для случая, когда X — произвольный конечный граф иУ = Тщт.

Теорема 1.1. Фиксируем целые числа п,т > 0 (п + 2т > 2). Произвольный конечный граф СУ базисно вкладывается в произведение К х Тщт тогда и только тогда, когда первое число Бетти Ь(С) <т и либо дефект ¿(б) < п + 2т, либо 5(СУ) — п + 2т и одна из сложных вершин графа СУ является неразветвленной.

Из результатов второй главы (теорема 2.1а) следует, что любой конечный граф (3 топологически вкладывается в книжку К х Тз,о всего с 3 страницами. Теорема 1.1 дает эффективный критерий проверки базисной вложимости конечных графов в произведение К х Тп>т.

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

Теорема 1.1 для случая плоскости Кх1(п = 2,т = 0) дает такой критерий: "конечный граф СУ базисно вкладывается в К х К тогда и только тогда, когда Ь(СУ) = 0 (т.е. б не имеет циклов) и <$((7) = 0 (т.е. СУ не содержит сложных вершин)". Этот результат эквивалентен

характеризации (данной А. Б. Скопенковым в терминах запрещеных подграфов) конечных графов, которыебазисно вкладываютсявМхЕ (см. примечание 5). По сравнению с этим критерием А. Б. Скопен-кова при доказательстве теоремы 1.1 диссертантом были преодолены следующие трудности. Для численной характеризации препятствия к базисной вложимости было введено понятие дефекта графа. Именно в терминах дефекта критерий базисной вложимости удалось сформулировать в доступной и понятной форме. Ключевую роль в доказательстве необходимости условий критерия играют два утверждения (предложения 1.2 и 1.4 в параграфе 1.2). В первом утверждении произвольное базисное вложение графа редуцируется к такому, в котором все сложные вершины графа лежат на оси Кх О, где О — точка склейки букета Тп<т. Для доказательства второго ключевого утверждения вводится понятие отмеченной структуры на произведении К х ТПгГП. Такая структура позволяет провести индукцию по ее сложности и получить ограничение на дефект базисно вложенного графа.

Доказательство достаточности в теореме 1.1 проводится в три этапа. Сначала описывается семейство универсальных графов (параграф 1.3). Универсальные графы несут богатую дополнительную структуру в виде фильтрации деревьев, отмеченных точек и оснащений. Благодаря этой структуре произвольный универсальный граф можно базисно вложить в произведение Ж х Т„>т шар за шагом, от простых элементов к сложным (предложение 1.5 в параграфе 1.4). Построение искомого базисного вложения разбивается на семь шагов (леммы 1.6-1.12 в параграфе 1.4). Для обоснования свойства базисности вложений, построенных на отдельных шагах, вводятся два усиления понятия базисного вложения — совершенно базисное и сильно базисное вложения. На каждом шаге построения используется специальная геометрическая конструкция, которая позволяет продолжить вложение на больший граф с сохранением свойства базисности. Оказывается, что любой граф, базисно вложимый в произведение ® х Тп,т (при фиксированных п,т), является подграфом некоторого универсального графа (предложение 1.6 в параграфе 1.5). Этот последний этап доказательства достаточности в теореме 1.1 требует пяти последовательных шагов (пункты 1.5.2-1.5.6), в течение которых любой граф, удовлетворяющий условиям теоремы 1.1, достраивается до некоторого универсального графа.

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

Следствие 1.2. Для любых конечных графов X, У существует конечный граф, который нельзя баэисно вложить в произведение X х У. С другой стороны, для каждого конечного графа С? существует такой минимальный (по вложению) букет Тп>т, что граф (7 базисно вкладывается в произведение Ж х Тп>т. При этом т = 6(6), и если все сложные вершины графа (7 являются разветвленными, то п = тах{0,6(0) — 2Ъ{0) + 1}, иначе п = тах{0, ¿((7) - 26((7)}.

Следствие 1.2 означает, что не существует одного универсального произведения X х У, в которое можно базисно вложить все конечные графы. Зато семейство произведений {Е х Т„1т \ п, т > 0, п + 2т > 2} является универсальным в том смысле, что для каждого конечного графа С? найдется свое произведение Ж X Тп<т, куда граф СУ вкладывается базисно. Семейство графов {/¿(Тпт)} называется запрещенным (для базисных вложений в произведение Ж х Т„]Ш), если любой конечный граф С базисно вкладывается в Ж х Т„)т тогда и только тогда, когда граф С не содержит подграфов, гомеоморфных графам из {Р|(Т„>ТО)}. Многие теоремы геометрической топологии сформулированы в терминах запрещенных графов. Среди них — известная теорема Куратов-ского о характеризадии планарных графов21. Для базисных вложений в произведение Ж х Тп,т также можно указать конечное запрещенное семейство. Следующий результат вытекает из теоремы 1.1.

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

Семейство графов {[/,(!ГП1т)} называется универсальным (для базисных вложений в произведение Ж х Тп>т), если любой конечный граф С? базисно вкладывается в Ж X тогда и только тогда, когда он содержится в некотором графе из {[/¿(Т„1т)}. Следствие 1.3 допускает уточнения в случаях (п,т) = (0,1), (3,0), (1,1). А именно, при этих значениях параметров запрещенные и универсальные семейства графов описываются в явном виде (см. следствия 1.4,1.5 и 1.6 в пункте 1.3 введения). Например, для базисных вложений в цилиндр Е х 51 есть ровно 6 запрещенных графов, для книжки с тремя страницами Жх Тз,о — 8 запрещенных графов, а для цилиндра с приклеенной полуплоскостью Е х Тхд — 16 запрещенных графов.

Самые содержательные случаи теоремы 1.1 и следствий 1.1,1.3 (при т — 0) доказаны в [1, теорема 1.1 и следствие 1.3 соответственно].

2*К. Kuratowski, Sur les problèmes des courbes gauches en topologie, Fund. Math., 1930.

Там же описаны запрещенное и универсальное семейства графов для базисных вложений в К х Тз,о [1, следствие 1.2]. Обобщения на общий случай ш > 0 и следствие 1.2 получены в [3, 4].

Вторая глава посвящена взаимно однозначному кодированию изотопических классов произвольных заузленных графов в К?.

Фиксируем целое число п > 2. Здесь рассматриваются неориентированные конечные графы с вершинами степени от 2 до п. Поскольку висячие ребра нельзя заузлить, они исключаются. Графы могут быть несвязными, допускаются петли и мульти-ребра. Тогда заузленный граф б С К3 — это подмножество пространства К3, гомеоморфное данному конечному графу <3. В случае п = 2 любой заузленный граф по определению является неориентированным зацеплением. Заузленные графы будут изучаться с точностью до двух отношений эквивалентности — жесткой и нежесткой объемлющих изотопий.

Нежесткая объемлющая изотопия между двумя заузленными графами С? С К3 и Я С К3 — это такое непрерывное семейство гомеоморфизмов щ : К3 -> К3, < 6 [0,1], что щ = и ^(С?) = Я. Если потребовать, чтобы в любой момент £ € [0,1] объемлющей изотопии окрестность каждой вершины графа ^(С) с К3 лежала в некоторой (непостоянной) плоской площадке, то получится жесткая объемлющая изотопия. Из определения следует, что изотопные графы гомео-морфны, но среди гомеоморфных заузленных графов есть неизотопные друг другу. Например, известно много неизотопных замкнутых кривых в К3, каждая из которых гомеоморфна окружности. Заметим, что введенные выше два понятия объемлющей изотопии совпадают для заузленных графов с вершинами степени только 2 и 3.

Рассмотрим полугруппу с множеством образующих

К = { <4. Ьи Сг, сЦ, хт,{ I г е 2з, 3 < т < п}.

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

Аг = { ао, аь 02, 6о. Ьь &2> со. ¿1, Ф, ¿о, <¿1, ¿2 }•

Общее количество букв алфавита Ап равно д(п) = 3(п + 2). Пусть Д5(?п — полугруппа, заданная образующими из А„ и соотношениями (1)—(10). Предполагается, что целочисленные параметры т,р, д удовлетворяют неравенствам 3<т<п,2<р< и 2 < д <

(1) ¿0^2 = 1;

(2) Ы = (¿Д = 1;

(3) ^ = <4+1^-1, Ь{ = а<_1С<+1, ^ = <£{ = а;+1сц_1-,

(4) Х2р-1,1-1 = С1 (Х2р-и<Ъ+1), х2д,{-1 = (^+1Х29,¿^+1)6^1!

(5) = )с,-, х2р-\1А = а,(Ь?~ Х2Р_1,<6^с,-;

(6) <1{Х2д,х<Ц~1 = а^яг^сгГ1)«*, Ь1~1х2д,А = а^Ь^хц^а}

(7) (<£с,)гу = где ю £ {^+1, Ь{<и+хт,«-и};

(8) иь - уи, где и € {аД, Ь^сЦ^Ц-^, х2р-1,А, <кх2я,&}, V € {а»+1, £>¿+1, сй-Ь ЬД+Д) ^,¿+1};

(9) (г2р-1,А)£>р,< = Яр-мО^Д), где = ¿^¿^{к > 1);

(10) =

Одно из соотношений (2) избыточно: его можно получить из равенства (1) и остальных соотношений (2). Тогда общее количество соотношений (1)—(10) равно г(п) = 3(п2 + 7п — 2). Например, полугруппа И. А. Дынникова £>5 = ЯЗС2 задается 12 образующими из Аг и 48 соотношениями (1)—(10), не содержащими букв хт,{- Полугруппа В£Сз задается 15 образующими и 84 соотношениями, а полугруппа ИБОь — 18 образующими и 126 соотношениями. И. А. Дынников доказал (см. примечание 19), что центр полугруппы £>5 взаимно однозначно кодирует (с точностью до объемлющей изотопии) все неориентированные зацепления в М3. Главный результат второй главы — это теорема 2.1 о взаимно однозначном кодировании заузленных графов, рассматриваемых с точностью до жесткой изотопии, центральными элементами конечно определенных полугрупп Я5б?п. Удобно разбить теорему 2.1 на следующие три части.

Теорема 2.1а. Каждый заузленный граф б С К5, гомеоморфный любому конечному графу С с вершинами степени от 2 до п, кодируется некоторым центральным элементом та полугруппы Д5(3П.

Теорема 2.16. Два произвольных заузленных графа <3, Н С К3, го-меоморфные любому конечному графу с вершинами степени от 2 до п, жестко изотопны тогда и только тогда, когда в полугруппе имеем и>в = шя-

Теорема 2.1в. Элемент и) Е ЛЗС^п кодирует некоторый заузленный граф, гомеоморфный конечному графу (3 с вершинами степени от 2 до п, тогда и только тогда, когда го — центральный элемент полугруппы Д5С„. Алгоритм, определяющий, является ли данный элемент т € центральным, имеет линейную сложность по длине слова ги.

Коротко теорему 2.1 можно сформулировать так: "центры полугрупп Д5СП взаимно однозначно кодируют (с точностью до жесткой объемлющей изотопии) все заузленные графы в Ж3". Например, центр полугруппы ИБСз взаимно однозначно кодирует все заузленные трехвалентные графы, а центр полугруппы RSGi взаимно однозначно кодирует (с точностью до жесткой изотопии) все заузленные графы с вершинами степени только 3 и 4, в частности, все неориентированные сингулярные узлы. Таким образом, теорема 2.1 сводит топологическую задачу жесткой изотопической классификации заузленных графов к алгебраической проблеме равенства центральных элементов в конечно определенных полугруппах В некоторых частных слу-

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

теряется большая часть информации о заузленных графах (предложение 2.8). Этот отрицательный результат подчеркивает сложность задачи полной классификации заузленных графов. Результаты параграфа 2.6 не относятся к основным, они только демонстрируют возможные подходы к эффективной классификации заузленных графов.

При доказательстве теоремы 2.1 диссертантом были преодолены следующие трудности. Сначала каждый изотопический класс заузленно-го графа был представлен вложением графа в произведение Е х Тз,о (книжка с 3 страницами). По сравнению с конструкцией И. А. Дынни-кова для неориентированных зацеплений (случай п = 2) потребовался специальный выбор вложения окрестности каждой вершины графа. Такой экономный выбор позволил минимизировать число образующих и соотношений кодирующих полугрупп Й5С7„. Далее произвольная жесткая объемлющая изотопия заузленных графов была разложена в композицию соотношений полугруппы Д5(?п. Для этого помимо методов И. А. Дынникова понадобилось задать полугруппу графовых плетений образующими и соотношениями. А затем — редуцировать все соотношения между графовыми плетениями к соотношениям полугруппы Д5(?п. Детальный анализ показал, что достаточно 3(п + 2) образующих и 3(п2 + 7п — 2) определяющих соотношений. В частности, оказалось, что полугруппа И. А. Дынникова 2?5 = задается не

более чем 48 соотношениями, т.е. 6 соотношений в исходном задании полугруппы И. А. Дынникова были лишними.

Заменим соотношения (9)-(10) на (9') = Че-

рез обозначим полугруппу, заданную образующими из А„ и со-

отношениями (1) — (8), (9'). Новая полугруппа имеет то же количество образующих и определяющих соотношений, что и Лб'Сп.

Теорема 2.2. Центр полугруппы взаимно однозначно коди-

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

Как и в случае жесткой изотопии, при п = 2 полугруппа 2 совпадает с полугруппой И. А. Дынникова Для п = 3 два понятия объемлющей изотопии на заузленных графах одинаковы (любую изотопию между заузленными трехвалентными графами можно сделать жесткой), поэтому ИБС^ = КБОз- Но при п > 3 эти две серии полугрупп расходятся: ^ АГ5С?„.

Рассмотрим следующее преобразование букв из алфавита А„: Г Рп{сч) = (к, рп(Ь) = р„(а) = сц,

\ Рп(<к) = ¿4, рп(я2р-1,«) = Х2р-1 ¿Ь»с(, рп(= ж2д,»-

Отображение рп по правилу рп(т) = рп{у)рп(и) продолжается до ин-волютивных антиавтоморфизмов рп : ДЯСП —> и еп : ИвОп —>

ЛГ5(7П. Зеркальный образ заузленного графа б С К3 — это заузленный граф С С К3, который получается из графа С отражением относительно некоторой двумерной плоскости в К3. Вопрос об изотопности любого заузленного графа своему зеркальному образу также сводится к проблеме равенства слов.

Следствие 2.1а. Пусть заузленный граф в С М3, гомеоморфный произвольному конечному графу с вершинами степени от 2 до п, кодируется некоторым центральным элементом та £ ДЗСгц (см. теорему 2.1а). Заузленный граф СУ жестко изотопен своему зеркальному образу тогда и только тогда, когда в полугруппе Л5(?„ имеем ■шв = Рп{и>в)-

Следствие 2.16. Пусть заузленный граф G С R3, гомеоморфный произвольному конечному графу с вершинами степени от 2 до п, кодируется некоторым центральным элементом vg € NSGn (см. теорему 2.2). Заузленный граф G нежестко изотопен своему зеркальному образу тогда и только тогда, когда в полугруппе NSGn имеем vG = en{vG).

Самый содержательный случай теорем 2.1 и 2.2 (при п = 3) доказан в [2]. Случай произвольного п > 3 и следствие 2.1 получены в [3].

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

Публикации автора по теме диссертации

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

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

[3] В. А. Курлин, Базисные вложения графов и метод трехстраничных вложений Дынникова, Успехи математических наук, 2003, том 58, вып. 2, стр. 163-164.

[4] V. A. Kurlin, Kolmogorov-Arnold's solution of Hilbert's 13th problem and basic embeddings of graphs, Abstracts of the International conference "Kolmogorov and contemporary mathematics" (Moscow, June 2003), p. 822.

Издательство Центра прикладных исследований при механико-математическом факультете МГУ. Лицензия на издательскую деятельность ИД №04059 от 20.02.2001

Отпечатано с оригинал-макета на типографском оборудовании механико-математического факультета и Франко-русского центра им. A.M. Ляпунова.

2ooj~ A

* 134

с

Введение

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

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

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

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

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

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

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

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

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

1.1. Примеры и план доказательств.

1.1.1. Примеры на базисные вложения.

1.1.2. Вычисления дефекта графов.

1.1.3. Частные случаи теоремы 1.1.

1.1.4. План доказательства теоремы 1.1.

1.2. Необходимые условия базисной вложимости.

1.2.1. Геометрический критерий базисного вложения.

1.2.2. Ограничение на первое число Бетти графа.

1.2.3. Охлопывание базисного вложения.

1.2.4. Доказательство необходимости в теореме 1.1.

1.2.5. Грубое ограничение на дефект графа.

1.2.6. Тонкое ограничение на дефект графа.

1.3. Конструкция универсальных графов.

1.3.1. Универсальные листья и сердцевина.

1.3.2. Тонкая ветвь.

1.3.3. Толстая ветвь.

1.3.4. Универсальное дерево.

1.3.5. Универсальный граф.

1.4. Построение базисного вложения.

1.4.1. Сильно базисное и совершенно базисное вложения.

1.4.2. Совершенно базисное вложение универсального листа.

1.4.3. Совершенно базисное вложение сердцевины.

1.4.4. Совершенно базисное вложение тонкой ветви.

1.4.5. Совершенно базисное вложение толстой ветви.

1.4.6. Сильно базисное вложение универсального дерева.

1.4.7. Базисное вложение универсального графа.

1.5. Доказательство достаточности в теореме 1.1.

1.5.1. Случаи плоскости Ехйи цилиндра 1x5'.

1.5.2. Редукция к связному дереву.

1.5.3. Выделение удовлетворительных точек.

1.5.4. Выделение сердцевины.

1.5.5. Достраивание тонкой и толстой ветвей.

1.5.6. Окончание доказательства теоремы 1.1.

1.6. Доказательство следствий 1.1-1.6.

1.6.1. Доказательство следствий 1.1 и 1.2.

1.6.2. Доказательство следствия 1.3.

1.6.3. Доказательство следствий 1.4, 1.5 и 1.6.

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

2.1. Геометрический смысл полугрупп и МЗСп.

2.1.1. Геометрический смысл букв алфавита А„.

2.1.2. Локальные движения в трехстраничном подходе.

2.1.3. План доказательства теоремы 2.1.

2.2. Трехстраничные вложения заузленных графов.

2.2.1. Формальное определение трехстраничного вложения.

2.2.2. Построение трехстраничного вложения.

2.2.3. Доказательство теоремы 2.1а.

2.2.4. Сбалансированные слова в алфавите А„.

2.3. Графовые плетения и трехстраничные плетения.

2.3.1. Графовые плетения.

2.3.2. Полугруппа графовых плетений.

2.3.3. Трехстраничные плетения.

2.4. Доказательства основных результатов.

2.4.1. Полугруппа 11ВТп почти сбалансированных плетений.

2.4.2. Доказательство теоремы 2.16.

2.4.3. Доказательство теоремы 2.1в и следствий 2.1а, 2.2а.

2.4.4. Случай нежесткой изотопии и заузленных ,7-графов.

2.5. Доказательство леммы 2.3.

2.5.1. Новые эквивалентности слов в полугруппе ЯБОп.

2.5.2. Разложение г-сбалансированных слов.

2.5.3. Вывод соотношений 11) - </?(23) из (1)—(10).

Настоящая диссертация представляет собой исследование по современной геометрической топологии. В первой главе изучаются базисные вложения графов. Во второй главе вводится взаимно однозначное кодирование для всех изотопических классов заузленных графов в 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(R; R).

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

Определение 1.1 (базисное вложение). Пусть X и Xi (1 < i < к) — компактные метрические пространства, а р>г : X —> Xi — непрерывные функции. Семейство называется базисным, если каждая функция / € CpíjM) представляется в виде 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) = EÍ=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.

Оказалось, что число 2n -f 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.

51

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.

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 (кодирующий алфавит А„). Для каждого п > 2 рассмотрим следующий кодирующий алфавит:

А„ = { 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 }.

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

Определение 2.4 (универсальные полугруппы7 RSGn и NSGn). Пусть RSGn — полугруппа, заданная образующими из алфавита А„ и определяющими соотношениями (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 € {ûi+ii ^t+i> ci+i) bidi+\di, xmi+i}-,

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

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

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

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/0208153.

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 problèmes 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.