Теоретико-групповые методы исследования плоских деревьев тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М.В. ЛОМОНОСОВА

МЕХАНИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

На правах рукописи УДК 512.542

Суворов Антон Дмитриевич

ТЕОРЕТИКО-ГРУППОВЫЕ МЕТОДЫ ИССЛЕДОВАНИЯ ПЛОСКИХ ДЕРЕВЬЕВ

01.01.06 — математическая логика, алгебра и теория чисел

Автореферат

диссертации на соискание учёной степени кандидата физико-математических наук

Москва 1998

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

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

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

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

профессор В. С. Куликов; доктор физико-математических наук профессор С. П. Струнков.

Ведущая организация — Санкт-Петербургский государственный

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

Защита диссертации состоится " ^_" Я^&^рЧ_ 1998 г. в

16 ч. 15 мин. на заседании диссертационного совета Д.053.05.05 при Московском государственном университете им. М.В. Ломоносова по адресу: 119899, ГСП, Москва, Воробьёвы горы, МГУ, механико-математический факультет, аудитория 14-08.

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

Автореферат разослан " & " Н-ОЗ^/?5) 1993 г.

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

профессор В. Н. Чубариков.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Традиционно теоретико-групповые методы применяются для изучения комбинаторных объектов — здесь уместно упомянуть теорию графов, комбинаторную топологию. Обширные исследования связаны с различными классами графов на поверхностях, часто называемых картами, эскизами или детскими рисунками. В настоящей работе развивается теоретико-групповой подход к изучению плоских деревьев — частного случая детских рисунков.

В работе Александра Гротендика "Esquisse d'un programme", написанной в 1984 г. (опубликованной лишь в 1997г. в 2\ указано вытекающее из теоремы Г.В. Белого соответствие между комбинаторными объектами — детскими рисунками — и арифметико-алгебраическими — парами Белого (X,ß), где X — алгебраическая кривая над Q, ß — непостоянная рациональная функция на ней с не более чем 3 критическими значениями. Идеи Гротендика, высказанные в "Esquise d'un programme", положили начало новому направлению исследований, иногда называемому "программой Гротендика". С современным состоянием предмета можно ознакомиться по сборникам и 2'.

В настоящей диссертации рассматриваются некоторые аспекты вышеупомянутого соответсвия Гротендика, а именно сопоставление связного одноклеточного детского рисунка на С (плоского дерева) и полинома Ша-бата — многочлена из C[z] с не более чем двумя критическими значениями.

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

en ~ z * z.

Изучается круг вопросов, связанный с группой вращений ребер плоских деревьев. С одной стороны, группа вращений ребер представляет самостоятельный интерес: например, получены реализации групп Матье

'The Grothendieck Theory of Dessins d'Enfants (ed. L.Schneps) // London Math. Soc. Lecture Notes Series, 200 (1994).

2Geometric Galois Action IJI(eds. L.Schneps, P.LochaJt) // London Math. Soc. Lecture Notes Scries, 242, 243 (1997).

Мц,М23 как групп вращений ребер. С другой, группа вращений ребер играет вспомогательную роль в геометрической теории Галуа, поскольку она является одним из инвариантом действия группы Галуа на детских рисунках (в частности, плоских деревьях).

В ряде случаев именно группа вращений ребер позволяет разделять орбиты Галуа. Так, для выделенных четырех деревьев с группой вращения ребер, изоморфной группе Матье М23, Ю. В. Матиясевич вычислил полиномы Шабата, определенные над биквадратичным расширением

Цель работы:

• Изучить соответствие Гротендика между одноклеточными детскими рисунками на сфере - плоскими деревьями и полиномами Шабата.

• Исследовать группы вращений ребер плоских деревьев, в частности, импримитивные группы вращений ребер, группы вращений ребер композиции плоских деревьев.

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

Научная новизна. Основные результаты работы являются новыми. Среди них:

• Построение трех эквивалентных категорий плоских деревьев. (Теоерема 1.37 стр. 22)

• Построение деревьев с группой вращений ребер М2з и РЭЬ5(2). (Теорема 2.16 стр. 31)

• Результаты о группе вращений ребер плоских двукрашенных деревьев с нетривиальной группой автоморфизмов.

(Теорема и следствия 3.29 -3.33 стр. 48-52)

• Применение классических результатов Ритта о разложимых полиномах к задаче определения порядка группы вращений ребер композиции плоских двукрашенных деревьев.

(Теорема 3.43 стр.60)

Практическая и теоретическая ценность. Работа носит теоретический характер. Полученные в ней результаты могут быть использованы в некоторых задачах теории графов и геометрической теории Галуа.

Апробация результатов. Результаты диссертации докладывались на семинаре Г.Б.Шабата "Графы на поверхностях и кривые над числовыми полями", на семинаре кафедры Высшей алгебры механико-математического факультета МГУ.

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

Структура диссертации. Диссертация состоит из введения, трех глав, разбитых на параграфы, приложения и списка литературы. Основные результаты опубликованы в четырех работах. Полный объем диссертации — 76 страниц, библиография включает 41 наименование.

Краткое содержание работы.

В главе 1 вводятся плоские двукрашенные деревья — основной объект рассмотрения в диссертации. Последовательно определяются вложенные плоские двукрашенные деревья — связные ацикличные 1-комплексы, вложенные в ориентированную плоскость С; абстрактные плоские двукрашенные деревья, являющиеся абстрактными двукрашенными деревьями с заданным циклическим порядком ребер в вершинах, и многочлены Ша-бата — многочлены из С[г] \ С с не более чем двумя критическими значениями.

Доказывается эквивалентность категорий абстрактных плоских дву-крашенных деревьев с двумя отмеченными вершинами АВТТг, вложенных плоских двукрашенных деревьев с двумя отмеченными вершинами £ВТТ2 и многочленов Шабата с критическими значениями —1,1 и инвариантным множеством {—1,1} — БР-ц. (Теорема 1.37).

Эквивалентность осуществляется функторами ^ : ЕВРТг —> ЛВРТ2 (сопоставление вложенному дереву его комбинаторной структуры) и (? : БР-г^ —> ЕВРТг (сопоставление полиному Р дерева в истинной форме Р-1[—1,1], прообраза отрезка, соединяющего критические значения; черные и белые вершины соответствуют Р_1( —1) и Р_1(1)).

В главе 2 определяется действие универсальной группы врагцений ребер £1Z — свободной группы Z * Z с двумя образующими а.,а0 — на множестве ребер произвольного абстрактного плоского двукрашенного дерева Т — (Е,а.,а0) (здесь Е — множество ребер дерева Т, а,,а0 — перестановки из S{E), задающие циклический порядок ребер в вершинах):

S(E(T)), тгг(а.) = а.,тгг(а0) = а0

Группа вращений ребер ER(T) плоского двукрашенного дерева Т, являющаяся подгруппой симметрической группы перестановок ребер дерева, определяется как тгт{£71) =< а,,а0 >.

Категория плоских двукрашенных деревьев являетчся полной подкатегорией конечных £7£-множеств.

Указывается соответствие между группами вращений ребер деревьев и группами монодромии полиномов Шабата.

Определяются деревья двух специальных типов, "ежики" Нп и "цепочки" Сп:

Нп = ({1,... , п], а, = id,a0 - (1,2,... ,п))

Сп = ({1,... ,n},a. = (1,2)...(п-2,п- 1),о0 = (2,3)... (п - 1,п)), если число ребер п нечетно и

Сп = {{1,... ,п},а. = (1,2)... (п — 1, п), а0 = (2,3)... (п — 2, п — 1)), если п четно.

Группа вращений ребер ежика ER(Hn) — циклическая группа Zn, группа вращений ребер цепочки ER(Cn) — диэдральная группа Dn (при п > 3).

Приводится классификация плоских двукрашенных деревьев, основанная на свойствах групп вращений ребер деревьев.

Группа вращений ребер "наугад взятого" двукрашенного дерева является симметрической группой S„ или знакопеременной группой Л„ в зависимости от четности образующих о.,а0: падение порядка ER(T) объясняется либо принадлежностью дерева к конечному списку исключительных деревьев (см. ниже), либо принадлежностью к классу ежиков или цепочек, либо приводимостью дерева Т (см. ниже).

Определяется класс исключительных плоских двукрашенных деревьев — деревьев с примитивной группой вращений ребер, отличной от 5„, Д, или Ъп. Приводится полный список исключительных деревьев (Теорема 2.16), возникший в результате исследований нескольких авторов (Адрианов, Звонкин, Кочетков, Суворов, Шабат) и опубликованный в работе [2]. Полнота списка доказана Н.М. Адриановым (см. 3'). Автором найдены все исключительные деревья с числом ребер 23 и 31. (см. [1]- й).

На рисунке 0 представлены деревья, группа вращений ребер которых изоморфна группе Матье Л/23.

Рис. 0: е = 23, ER(T) = М23

Вводится понятие приводимости плоских двукрашенных деревьев, наиболее наглядно определяемое в категории полиномов Шабата: приводимость дерева означает композиционную разложимость соответствующего полинома.

В главе 3 определяется композиция плоских двукрашенных деревьев с двумя отмеченными вершинами согласно работе Н.М. Адрианова и А.К. Звонкина 4'. Результаты главы существенно дополняют опубликованные в этой работе сведения о композиции (серия результатов о порядке группы вращений композиции).

Понятие композиции плоских деревьев определяется на языке трех категорий — абстрактных плоских двукрашенных деревьев, вложенных

3Н. М. Адрианов, Классификация примитивных групп врау{ечий ребер плоских деревьев, Фундаментальная и прикладная математика, т.З, №4, 1075-1089, 1997.

* N. M. Adrianov, А. К. Zvonkin, Composition of plane trees, Acta Applicandae Mathematicae, 1998, №1-3 ,p. 239-245.

о

о

о

о

о

О

о

о

о

о

о

о

о

о

о

о

плоских двукрашенных деревьев и многочленов Шабата. Возможное благодаря установленной в первой главе эквивалентности указанных категорий, такое параллельное использование трех языков чрезвычайно удобно: на языке многочленов понятия определяются наиболее лаконично, техника вложенных плоских деревьев позволяет дать определяемому понятию наглядную геометрическую интерпретацию, а определение в категории абстрактных плоских деревьев дает инструментарий для изучения теоретико-групповых свойств объекта.

Если Р^Рг 6 то полином Рз = о Р2 также принадлежит

57?_1.1. Полином Рз задает плоское двукрашенное дерево Тр3, называемое композицией плоских двукрашенных деревьев Тр1 и Тр}.

В категории вложенных плоских двукрашенных деревьев композиция определяется следующим образом: пусть Т\ = (Е.1, Е01, Г2,5ц, в^), Т2 = (£.2, £о2, 0.52Ъ 52г) € ЕВТТъ- Дерево т3 = Ту о т2 получается, если каждое ребро дерева т2 заменить копией дерева т\ таким образом, что омеченные вершины яц, вклеиваются на место черной и белой вершин ребра.

Соответствующее определение композиции в категории абстрактных плоских двукрашенных деревьев существенно длиннее и приводится лишь в основном тексте диссертации.

Понятие композиции плоских деревьев напоминает понятие композиции графов (прямое соответствие отсутствует). Аналогично результату Сабидуси о том, что при определенных условиях группа автоморфизмов композиции графов С\ и является сплетением групп автоморфизмов этих графов 5', установлено что группа вращений ребер композиции плоских двукрашенных деревьев гомоморфно вкладывается в сплетение групп вращений ребер этих деревьев. Точнее, имеет место следующая коммутативная диаграмма:

1

4

1

(0 1-» К (и) 1 —► ЕЯ{Т2)е™

ЯЯ(Г, о Т2) 4- ¿2

А ЕЯ(Г^ —► 1

II

^ ЕЯ{Т,) —> 1

5ЗаЫ(1икз1 в. СгарЛ тиШрЧсаЧоп МаНи Ъ„ 1960, Вс1.72, N5, р.440-457

В ряде случаев удается определить индекс вложения кс ~ [Е11{Т{) \ : ЕЯ{ТХ о Т2)] = [ЕЯ{Т2)е™ : К]. В наиболее

общей постановке вопрос является сложным, но в случае, когда дерево Т обладает нетривиальной группой автоморфизмов, удалось найти критерий сюръективности вложения ЕБ.{Т\ 0Т2) в ЕК{Т{) \ Е11{Т2).

Плоские деревья Т с АЫ(Т) ф {1} описываются следующим образом: группа автоморфизмов плоского двукрашенного дерева Т нетривиальна тогда и только тогда когда дерево Т является композицией некоторого дерева Т\ и ежика Яр, где р — простое число, Т = Т\ о Нр. В случае Т — Т\ о Нр и Аи1{Т\) = {1} группа автоморфизмов дерева Т изоморфна

ъг

В случае Т2 = Яр изучение действия группы ЕЯ(Тх) в векторном пространстве Е11(Тг)ЕХр, где — множество ребер дерева Т, п = фЕ{Т\), позволяет доказать следующую теорему.

Теорема 3.29 Пусть Т2 = Нр. ЕЯ{Т\ о Т2) ф ЕЩТх) I Е11{Т2) (т.е. кс ф 1) тогда и только тогда, когда линейное действие Ь группы ЕЕ.(Тх) на некотором нетривиальном факторпредставлении 5 представления продолжается до нетривиального аффинного действия А по формулам

Aa.lV = Ьа.,(и-/д) Аа^у =

Здесь /д —■ фиксированный элемент группы Е1{{Тг)Е^т^.

Из теоремы вытекает ряд интересных следствий, в том числе

Следствие 3.32 Пусть Т2 - Нр, ЕК{ТХ) = или Ап. Тогда при подходящем выборе отмеченной вершины ид дерева Т\ могут иметь место следующие нетривиальные значения индекса

2, если р = 2, ЕЕ(Тх) = 5„, обрадующаяа.1 нечетна, — \ а01 четна р"-1 иначе

Интересная серия примеров с нетривиальным индексом вложения группы вращений ребер композиции деревьев ЕЩТ1 о Т2) в сплетение групп ЕЯ{Тх) ? ЕЯ(Т2) получена двумя принципиально разными путями.

С одной стороны, с использованием теоремы 3.29 и ее следствий доказывается следующее утверждение:

Утверждение 3.33 Пусть Т2 = Нр, все черные вершины дерева Т\ кроме va имеют валентности, кратные р. Тогда для композиции Тз = Ti о Т2 имеем ке = рп~1.

С другой стороны, этот же класс деревьев (с дополнительным требованием неприводимости) возникает с применением классических результатов Ритта (см. б') о разложимых полиномах:

Теорема 3.43 Пусть Т = (Е, а., а0) — такое плоское двукрашенное дерево степени приводимости 2, что существуют два морфизма ipi :Т —> Т\ и </ъ : Т —> Тг дерева Т на неизоморфные неприводимые деревья Ti и Т2, причем #Е(Т{) > 1 ,#£,(Т2) > 1. Тогда имеет место один из следующих двух случаев:

i) Т,,Т2 - цепочки с ni и «2 ребрами (ni и тг2 - простые числа); Т -цепочка с тг = nin2 ребрами.

В этом случае Т = Ti о Т2 = Т2 о Ti (у деревьев Ti, Т2 отмеченные вершины uq, ид — концевые); ER(T) ~ Dn.

ii) Т2 - ежик с простым числом ребер р (для определенности — с центральной вершиной белого цвета), Т\ - дерево, у которого набор валентностей вершин одного из цветов (для определенности черного) имеет вид (pcu...,pck-i,ck),ci е N, НОД(рс1,..., pck-i, с/.) = 1.

В данном случае Т = Т\ оТ2, где у дерева Ti отмеченная вершина «д — черная вершина валентности ск (uq — любая другая вершина). Порядок группы вращений ребер #ER{T) = #ER(Ti)#ER{T2).

Степенью приводимости плоского дерева Т называется число неразложимых полиномов в композиционном разложении полинома Шабата, соответствующего дереву Т.

В приложении А приведен полный список исключительных плоских двукрашенных деревьев, опубликованный в работе [2].

В процессе работы над диссертацией автором был проведен значительный объём компьютерных экспериментов. Использовались как оригинальные программы, написанные на языке Паскаль с использованием алгоритма сильных систем образующих групп перестановок Симса, так и компьютерные пакеты Maple и GAP.

eJ. F. Ritt, Prime and Composite Polynomials, Trans. Amer. Math. Soc., v.23, 1922, p. 51-66.

Автор рад случаю выразить искреннюю признательность своим научным руководителям, А.В. Михалеву и Г.Б. Шабату, за постоянное внимание к работе, теплую поддержку и ценные замечания.

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

[1] Н. М. Адрианов, 10. Ю. Кочетков, А. Д. Суворов, Г. Б. Шабат, Группы Матье и плоские деревья, Фундаментальная и прикладная математика, т.1, №2, 377-384, 1995.

[2] Н. М. Адрианов, Ю. Ю. Кочетков, А. Д. Суворов, Плоские деревья с исключительными примитивными группами вращений ребер, Фундаментальная и прикладная математика, т.З, №4, 1091-1098, 1997.

[3] А. Д. Суворов, О приводимых деревьях, Kurosh Algebraic Conference^, Москва, 1998, 214-215.

[4] А. Д. Суворов, Группа вращений ребер композиции плоских деревьев и сплетение групп, Успехи Матем. Наук.

В работах [1] и [2] автором построены все исключительные деревья с числом ребер 23 и 31.

//

Московский Государственный Университет им. М. В. Ломоносова Механико-математический факультет

ТЕОРЕТИКО-ГРУППОВЫЕ МЕТОДЫ ИССЛЕДОВАНИЯ ПЛОСКИХ ДЕРЕВЬЕВ

01.01.06 - математическая логика, алгебра и теория чисел

диссертация на соискание ученой степени кандидата физико-математических наук

Научные руководители : д. ф.-м.н.,профессор A.B. Михалев

к.ф.-м.н., доцент Г.Б. Шабат

На правах рукописи УДК 512.542

Суворов Антон Дмитриевич

Москва 1998

! '< *

L' / /:

О [

Оглавление

Введение 3

1 Плоские двукрашенные деревья. Эквивалентные категории 13

1.1 Вложенные плоские двукрашенные деревья .... 13

1.2 Абстрактные плоские двукрашенные деревья ... 15

1.3 Многочлены Шабата и плоские деревья ............19

1.4 Три эквивалентные категории........................21

2 Группа вращений ребер плоских деревьев 26

2.1 Определение группы вращений ребер................26

2.2 Классификация деревьев с точки зрения групп вращений ребер....................28

2.3 Исключительные плоские двукрашенные деревья . 30

3 Композиция плоских двукрашенных деревьев 35

3.1 Три эквивалентных конструкции композиции ... 35

3.2 Группа вращений ребер плоских деревьев с нетривиальной группой автоморфизмов..........42

3.3 Плоские деревья и неоднозначная разложимость полиномов........................58

Приложение А. Список исключительных простых

деревьев 64

Литература 72

Введение

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

В работе Александра Гротендика "Esquisse d'un programme" [28], написанной в 1984 г., указано вытекающее из теоремы Г.В. Белого [4] соответствие между комбинаторными объектами — детскими рисунками — и алгебраическими кривыми над числоыми полями с заданной рациональной функцией. Идеи Гротендика, высказанные в "Esquise d'un programme", положили начало новому направлению исследований, иногда называемому "программой Гротендика". Среди основных работ, посвященных данной тематике, можно назвать сборники [29],[26],[27], статьи [40],[41],[39].

Целью настоящей диссертации является рассматрение некоторых аспектов вышеупомянутого соответсвия Гротендика, а именно сопоставления связного одноклеточного детского рисунка на € (плоского дерева) и полинома Шабата — многочлена из С[z] с не более чем двумя критическими значениями.

Один из способов описать детский рисунок — задать на нем действие картографической группы. В настоящей работе такой подход применяется к плоским деревьям — они рассматриваются как конечные множества (ребер) с заданным действием универсальной группы вращений ребер £1Z ~ Z * Z.

Изучается круг вопросов, связанный с группой вращений

ребер плоских деревьев (см. [Щ3],[2],[8], [9]). Группа вращений ребер представляет особый интерес, поскольку она инвариантна относительно действия группы Галуа на множестве плоских двукрашенных деревьев (см. [31]).

В ряде случаев группа вращений ребер позволяет разделять орбиты Галуа. Так, для выделенных четырех деревьев с группой вращения ребер, изоморфной группе Матье М23, Ю. В. Ма-тиясевич вычислил полиномы Шабата, определенные над биква-дратичным расширением <0>.

Сейчас уже известны все деревья с примитивной группой вращений ребер (см. [3]). Естественно встает вопрос об им-примитивных группах вращений ребер, соответствующих приводимым деревьям. Работа является продвижением в этом направлении. Исследуются различные аспекты приводимости деревьев, в частности, операция композиции деревьев.

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

Основные результаты работы:

1)Построение трех эквивалентных категорий плоских деревьев.

2)Построение деревьев с группой вращений ребер М23 и РВЬ5(2).

3)Теоремы о группе вращений ребер плоских двукрашенных деревьев с нетривиальной группой автоморфизмов.

4) Применение классических результатов Ритта о разложимых полиномах к задаче определения порядка группы вращений ребер композиции плоских двукрашенных деревьев.

Диссертация состоит из введения, трех глав, разбитых на па-

раграфы, приложения и списка литературы. Основные результаты опубликованы в трех работах. Полный объем диссертации — 76 страниц, библиография включает 41 наименование.

В главе 1 вводятся плоские двукрашенные деревья — основной объект рассмотрения в диссертации. Последовательно определяются вложенные плоские двукрашенные деревья — связные ацикличные 1-комплексы, вложенные в ориентированную плоскость С; абстрактные плоские двукрашенные деревья, являющиеся абстрактными двукрашенными деревьями с заданным циклическим порядком ребер в вершинах, и, наконец, многочлены Шабата — многочлены из С[<г] с не более чем двумя критическими значениями.

Доказывается эквивалентность категорий абстрактных плоских двукрашенных деревьев с двумя отмеченными вершинами ÄBVT2, вложенных плоских двукрашенных деревьев с двумя отмеченными вершинами 6BVT2 и многочленов Шабата с критическими значениями —1,1 и инвариантным множеством {—1,1} — SV-хд.

Эквивалентность осуществляется функторами

F : BBVT2 ABVT2 (сопоставление вложенному дереву его комбинаторной структуры) и G : SV- 1д BBVT2 (сопоставление полиному Р дерева в истинной форме P~l[— 1,1], прообраза отрезка, соединяющего критические значения; черные и белые вершины соответствуют Р~г(—1) и Р_1(1)).

В главе 2 определяется действие универсальной группы вращений ребер £71 — свободной группы Z * Z с двумя образующими а,,а0 — на множестве ребер произвольного абстрактного плоского двукрашенного дерева Т = (Е, а,, а0) (здесь Е — множество ребер дерева Т, а„а0 — перестановки из S(E), за-

дающие циклический порядок ребер в вершинах):

7гт : €11 3(Е(Т))) тгг(а.) = а.,тгг(а0) = а0 Группа вращений ребер ЕК(Т) плоского двукрашенного дерева

ТО V

, являющаяся подгруппой симметрическом группы перестановок ребер дерева, определяется как жт(Е71) —< а,,а0 >.

Категория плоских двукрашенных деревьев являетчся полной подкатегорией конечных £7£-множеств.

Указывается соответствие между группами вращений ребер деревьев и группами монодромии полиномов Шабата.

Определяются деревья двух специальных типов, "ежики" Нп и "цепочки" Сп:

Нп = ({1,... , п}, а. = М, а0 = (1,2,... , п))

Сп = ({1,... , п}, а. = (1,2)... (п—2, п-1), а0 = (2,3)... (п-1, п)), если число ребер п нечетно и

Сп = ({1,... , п}, а. = (1,2)... (п-1, п), а0 = (2,3)... (п-2, п-1)), если п четно.

Группа вращений ребер ежика ЕЩНп) — циклическая группа ЪП) группа вращений ребер цепочки ЕИ(Сп) — ди-эдральная группа Вп (при п> 3).

Приводится классификация плоских двукрашенных деревьев, основанная на свойствах групп вращений ребер деревьев.

Группа вращений ребер "наугад взятого" двукрашенного дерева является симметрическои группой Ьп или знакопеременной группой Ап в зависимости от четности образующих а#, ас: падение порядка ЕН(Т) объясняется либо принадлежностью дерева к конечному списку исключительных деревьев (см. ниже), либо

принадлежностью к классу ежиков или цепочек, либо приводимостью дерева Т (см. ниже).

Определяется класс исключительных плоских двукрашенных деревьев — деревьев с примитивном группой вращении ребер, отличной от Яп,Ап, Оп или Ъп. Приводится полный список исключительных деревьев, возникший в результате исследований нескольких авторов (Адрианов, Звонкин, Кочетков, Суворов, Шабат) и опубликованный в работе [3]. Полнота списка вытекает из теорем 2.15, 2.16 доказательство которых получено Н.М. Адриановым (см. [1]»[2],[3]). Автором найдены все исключительные деревья с числом ребер 23 и 31 (см. [1], [3]).

На рисунке 0 представлены деревья, группа вращений ребер которых изоморфна группе Матье М23.

Рис. 0: е = 23, ЕЩТ) = М23

Вводится понятие приводимости плоских двукрашенных деревьев, наиболее наглядно определяемое в категории полиномов Шабата: приводимость дерева означает композиционную разложимость соответствующего полинома.

В главе 3 определяется композиция плоских двукрашенных

деревьев с двумя отмеченными вершинами согласно работе Н.М. Адрианова и А.К. Звонкина [20]. Результаты главы существенно дополняют опубликованные в работе [20] сведения о композиции (серия результатов о порядке группы вращений композиции).

Понятие композиции плоских деревьев определяется на языке трех категорий — абстрактных плоских двукрашенных деревьев, вложенных плоских двукрашенных деревьев и многочленов Шабата. Возможное благодаря установленной в первой главе эквивалентности указанных категорий, такое параллельное использование трех языков чрезвычайно удобно: на языке многочленов понятия определяются наиболее лаконично, техника вложенных плоских деревьев позволяет дать определяемому понятию наглядную геометрическую интерпретацию, а определение в категории абстрактных плоских деревьев дает инструментарий для изучения теоретико-групповых свойств объекта.

Если Р\,Р% £ то полином Рз = о Р2 также принад-

лежит <SP._i.i- Полином Рз задает плоское двукрашенное дерево Тр3, называемое композицией плоских двукрашенных деревьев Трг и Тр2.

В категории вложенных плоских двукрашенных деревьев композиция определяется следующим образом: пусть П - (£.ъ Ео1, 512)> = (2.2, £о2, 52Ъ «22) € ЖРТ2. Дерево гз = п о 7*2 получается, если каждое ребро дерева 7*2 заменить копией дерева п таким образом, что омеченные вершины вклеиваются на место черной и белой вершин ребра.

Соответствующее определение композиции в категории абстрактных плоских двукрашенных деревьев существенно длин-

нее и приводится лишь в основном тексте диссертации.

Понятие композиции плоских деревьев напоминает понятие композиции графов [17] (прямое соответствие отсутствует). Аналогично результату Сабидуси о том, что при определенных условиях группа автоморфизмов композиции графов (?1 и С?2 является сплетением групп автоморфизмов этих графов [36],[37],[38],[17] установлено что группа вращений ребер композиции плоских двукрашенных деревьев гомоморфно вкладывается в сплетение групп вращений ребер этих деревьев. Имеет место следующая коммутативная диаграмма:

(1) 1 (И) 1

1 1

К -А ЕН(Тг о Гг) А ЯВД) —» 1

IЧ 1г2 II

ЕК{Т2)Е{Тг) ЕП{ТХ)\ЕП{Т2) ЕЩП) —» 1

В ряде случаев удается определить индекс вложения кс := [ЯВД) ? ЕЩТ2) : ЕЩТ! о Т2)} = [ЕК(Т2)е^ : К]. В наиболее общей постановке вопрос является сложным, но в случае, когда дерево Т обладает нетривиальной группой авто-

1 и и

морфизмов, удалось наити критерии сюръективности вложения ЯВД о Т2) в ЕК{ТХ) I ЕШРг).

Плоские деревья Т с АЫ(Т) ф {1} описываются следующим образом: группа автоморфизмов плоского двукрашенного дерева Т нетривиальна тогда и только тогда когда дерево Т является композицией некоторого дерева Т\ и ежика Нр, где р — простое число, Т — Т\ о Нр. В случае Т = Т\ о Нр и АЫ(Тх) = {1} группа автоморфизмов дерева Т изоморфна Ъг

В случае Т2 = Нр изучение действия группы ЕК(Тх) в векторном пространстве ЕК{Т2)е^ ~ где -Б(Тх) — множество ребер дерева Т, п — позволяет доказать следующую

теорему.

Теорема 3.29. Пусть Т2 = Нр. ЕК{ТгоТ2) ф ЕЩТ^ЕЩП) (т.е. кс ф 1) тогда и только тогда, когда линейное действие Ь группы ЕЩТх) на некотором нетривиальном факторпредста-влении 5 представления ЕИ(Т2)е^ продолжается до нетривиального аффинного действия А по формулам

А= Ьа#1(г;-/д)

Аао1у = Ьао1у Здесь /д — фиксированный элемент группы ЕЯ(Т2)е^ .

Из теоремы вытекает ряд интересных следствий, в том числе

Следствие 3.32. Пусть Т2 = Нр, £Д(ТХ) = 8п или Ап. Тогда при подходящем выборе отмеченной вершины «д дерева 71 могут иметь место следующие нетривиальные значения индекса

г

2, если р = 2, ЕЩТг) = 5П, образующая«^ нечетна,

кс = \ а01 четна иначе

Интересная серия примеров с нетривиальным индексом вложения группы вращений ребер композиции деревьев ЕИ(Т1оТ2) в сплетение групп ЕЛ{Т\) I ЕИ(Т2) получена двумя принципиально разными путями.

С одной стороны, с использованием теоремы 3.29 и ее следствий доказывается следующее утверждение:

Утверждение 3.33.

Пусть Т2 = Яр, все черные вершины дерева Т\ кроме ид имеют валентности, кратные р. Тогда для композиции Т3 = Т\ о Т2 имеем кс = рте-1.

С другой стороны, этот же класс деревьев (с дополнительным требованием неприводимости) возникает с применением классических результатов Ритта (см. [34]) о разложимых полиномах:

Теорема 3.43.Пусть Т = (Е, а,, а0) — такое плоское двукра-шенное дерево степени приводимости 2, что существуют два морфизма (р1 : Т -»■ Т\ и <р2 > Т -> Т2 дерева Т на неизоморфные неприводимые деревья и У2, причем фЕ(Т\) > 1, #Е(Т2) > 1. Тогда имеет место один из следующих двух случаев:

1) 1!, Т2 ~ цепочки с щ и п2 ребрами (щ и гг2 - простые числа); Г - цепочка с п = П1П2 ребрами.

В этом случае Т — Т\ о Г2 = Т2 о Тх (у деревьев 71, Т2 отмеченные вершины г>п, г;д — концевые); ЕН(Т) ~ 1)п.

¡1) Т2 - ежик с простым числом ребер р (для определенности — с центральной вершиной белого цвета), Т\ - дерево, у которого набор валентностей вершин одного из цветов (для определенности черного) имеет вид (рс\,... 1, с&), с; €

Л7", НОД(рсь... ,рск-ъ Ск) - 1.

В данном случае Т = Т\ о Т2, где у дерева Тх отмеченная вершина г?д — черная вершина валентности Ск (!>□ — любая другая вершина). Порядок группы вращений ребер фЕ11(Т) = ЯЕЩТ^фЕЩП).

Степенью приводимости плоского дерева Т называется число неразложимых полиномов в композиционном разложении полинома Шабата, соответствующего дереву Т.

В приложении А приведен полный список исключительных плоских двукрашенных деревьев, опубликованный в работе [3].

В процессе работы над диссертацией автором был проведен значительный объем компьютерных экспериментов. Использовались как оригинальные программы, написанные на языке Паскаль с использованием алгоритма сильных систем образующих групп перестановок [6], так и компьютерные пакеты Maple и GAP.

Автор рад случаю выразить искреннюю признательность своим научным руководителям, Г.Б. Шабату и A.B. Михалеву, за постоянное внимание к работе, теплую поддержку и ценные замечания.

1 Плоские двукрашенные деревья. Эквивалентные категории

1.1 Вложенные плоские двукрашенные деревья

Определение 1.1 Вложенным плоским деревом т = (Е,0) будем называть пару подмножеств комплексной плоскости

ЕсОсС

в которой £ — непустое конечное множество, О, — компактно, дополнение П \ Е гомеоморфно непустому несвязному объединению конечного числа непустых интервалов, а дополнение С\П гомеоморфно проколотому диску.

Определение 1.2 Накрытием вложенных плоских деревьев (3 : т т', т = (т' = (Е',£У) назовем сохраняющее ориентацию разветвленное накрытие /?:€->€, такое что = Е, (3~1(0! \ £') = О \ Е (множество точек ветвления этого накрытия содержится в Е).

Накрытия вложенных плоских деревьев на-

зываются эквивалентными, если существует гомотопия 3 : С х / С (здесь I = [0,1]), такая что 50 = 5(-, 0) : € С совпадает с (3, ¿>1 = 5(-, 1) : С С совпадает с ¡3, причем St является накрытием деревьев гиг' для любого Ь £ I.

Определение 1.3 Морфизмом вложенных плоских деревьев (р : г —> г' называется класс эквивалентности [¡3] накрытий вложенных плоских деревьев (3 : т т'.

Замечание 1.4 Вложенные плоские деревья г = (Е, О) и т' — (Е', изоморфны (изотопны), если существует такой сохраняющий ориентацию открытый гомеоморфизм ц>: С —)• С, что (р(Е) = Е' и (р(П) = П'.

Определение 1.5 Пусть т = (2,£2) - вложенное плоское дерево. Тогда элементы множества £ называются вершинами этого дерева, а связные компоненты дополнения П \ £ - его ребрами.

Определение 1.6 Ребра, в замыкании которых лежит данная вершина, называются инцидентными этой вершине.

Определение 1.7 Назовем 2-раскраской вложенного плоского дерева г — (£,0) такое разбиение множества £ на два непересекающихся подмножества

£ — £. П £0

(которые будут называться множествами вершин черного и белого цветов), что любые две вершины, инцидентные одному и тому же ребру, имеют разные цвета.

Замечание 1.8 Любое вложенное плоское дерево допускает ровно две 2-раскраски (выбор цвета одной вершины определяет цвета всех остальных).

Определение 1.9 Вложенное плоское дерево, в котором выбрана одна из двух 2-раскрасок, будет называться вложенным плоским двукрашенным деревом и обозначаться т = (£,, £0, £2).

Определение 1.10 Естественно модифицируется определение морфизма: морфизмом вложенных плоских двукрашен-ных деревьев <р : т = (£#, £0,0) —> т' = (£'в, £[,, П') будем называть класс эквивалентности такого накрытия вложенных плоских деревьев : С С, что г11(Е1) = £., /Ир'о) = Г \ (К П £'о)) = П \ (£# П £0).

Замечание 1.11 Дальше мы будем рассматривать вложенные плоские двукрашенные деревья с двумя отмеченными вершинами «1, «2 ^ ^ = Е# IIЕ0. Будем называть морфизмом вложен- г^ ¡^^ ных плоских двукрашенных деревьев с двумя отмеченными вер- с ^ шинами т = (£,, £0, П, 8\, §2) и т' — Е'0,0!, з'2) класс экви- 1 валентности накрытия /3, если, в дополнение к требованиям у определения 1.10, = 8'ъ /?(вг) = 4-

Пример 1.12 В некотором смысле простейшими вложенными двукрашенными плоск�