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

• Суворов, Антон Дмитриевич
• кандидат физико-математических наук
• 1998

Оглавление диссертации кандидат физико-математических наук Суворов, Антон Дмитриевич

Оглавление

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

деревьев

Литература

Введение диссертации (часть автореферата) на тему «Теоретико-групповые методы исследования плоских деревьев»

Введение

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

В работе Александра Гротендика "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] установлено что группа вращений ребер композиции плоских двукрашенных деревьев гомоморфно вкладывается в сплетение групп вращений ребер этих деревьев. Имеет место следующая коммутативная диаграмма:

Список литературы диссертационного исследования кандидат физико-математических наук Суворов, Антон Дмитриевич, 1998 год

Литература

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

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

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

[4] Г. В. Белый, О расширениях Галуа максимального кругового поля, Изв. Акад. Наук СССР, 43 (1979), 269-276.

[5] К. С. Браун, "Когомологии групп", М., "Наука", 1987

[6] В.Н. Земляченко, Н.М. Корниенко, Р.И. Тышкевич. Проблема изоморфизма графов Записки научных семинаров ЛОМИ, Вып. 118, 1982, "Теория сложности вычислений I", стр. 83-159

[7] Каргаполов М.И., Мерзляков Ю.И. Основы теории групп М, Наука, 1982

[8] Ю. Ю. Кочетков, Картографические группы и обобщенные полиномы Чебышева, Успехи Матем. Наук, т.49, №6, 1994, с.203-204.

[9] Ю. Ю. Кочетков, Плоские деревья и их группы монодро-мии, Успехи Матем. Наук, т.50, №6, 1995, с. 163-164.

[10] "Лекции по теории графов", М., "Наука", 1990.

[11] С. Маклейн, "Гомология", М., "Мир", 1966.

[12] Ю. В. Матиясевич, Вычисление обобщенных многочленов Чебышева на компьютере, Вестник Московского Ун-та, 6 (1996), 59-61.

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

[14] С. А. Степанов, "Арифметика алгебраических кривых", М., Наука, 1991.

[15] О. Форстер, "Римановы поверхности", М., Мир, 1980.

[16] Ф. Харари, Э. Палмер "Перечисление графов", М., Мир, 1977.

[17] Ф. Харари Теория графов, М, Мир, 1973

[18] N. М. Adrianov, G. В. Shabat, Plane trees and classical math, Contemporary Mathematics and its Applications, v.21, Algebra-3, (ed. R.V.Gamkrelidze), Moscow, 1995, 8-16.

[19] N. M. Adrianov, G. B. Shabat, Unicellular cartography and Galois orbits of plane trees, "Geometric Galois Action II", eds. L.Schneps and P. Lochak, London Mathematical Society Lecture Notes Series 243 , 13-24.

[21

[22

[23

[24

[25

[26

[27

[28

[29

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

J. Bétréma, D. Péré, A. Zvonkin, "Plane trees and their Sha-bat polynomials. Catalog." Rapport interne de LaBRI, no. 92-75, Bordeaux, 1992, 119 pp.

J. H. Conway, et.al. An ATLAS of finite groups, Oxford University Press, London, 1985.

F. Dorey, G. Whaples Prime and Composite Polynomials, J.Algebra, v.28 (1972), 88-101.

H. T. Engstrom Polynomial substitutions, Amer.J.Math, v.63 (1941), 249-255.

D. Gorenstein, "Finite groups", 2nd éd., Chelsea Publishing Company, New York, 1980.

"Geometric Galois Action I", eds. L.Schneps and P. Lochak, London Mathematical Society Lecture Notes Series 242.

"Geometric Galois Action II", eds. L.Schneps and P. Lochak, London Mathematical Society Lecture Notes Series 243.

A. Grothendieck, Esquisse d'un programme, "Geometric Galois Action I", eds. L.Schneps and P. Lochak, London Mathematical Society Lecture Notes Series 242.

"The Grothendieck Theory of Dessins d'Enfants", ed. L.Schneps, London Math. Soc. Lecture Notes Series 200, Cambridge University Press, 1994.

G. A. Jones, D. Singerman, Theory of maps on orientable surfaces, Proc. London Math. Soc. (3) v.37(1978), 273-307.

[31] G. A. Jones, M, Streit, Galois groups, monodromy groups and cartographic groups, in "Geometric Galois Action II", eds. L.Schneps and P. Lochak, London Mathematical Society Lecture Notes Series 243, 25-66.

[32] P. Miiller, Primitive monodromy groups of polynomials, in "Recent developments in the inverse Galois problem" (M.Fried, ed.), Contemporary Mathematics, vol. 186, 1995, 385-401.

[33] R. Ree, A theorem on permutations, J. Combinatorial Theory, Ser. A, v.10, 1971, p. 174-175.

[34] J. F. Ritt, Prime and Composite Polynomials, Trans. Amer. Math. Soc., v.23, 1922, p. 51-66.

[35] J. F. Ritt, On algebraic functions which can be expressed in terms of radicals, Trans. Amer. Math. Soc., v.24, no.l, 1922, p. 21-30.

[36] Sabidussi G. The composition of graphs Duke Math. J., 1959, v.26, N4, p.693-696

[37] Sabidussi G. Graph multiplication Math. Z., 1960, Bd.72, N5, p.446-457

[38] Sabidussi G. The lexicographic product of graphs Duke Math. J., 1961, v.28, N4, p.573-578

[39] G. B. Shabat, V. A. Voevodsky, Drawing curves over number fields, in "Grothendieck Festschrift III", Progress in Math. 88, Birkhauser, Basel, 1990, 199-227.

[40] G. Shabat, A. Zvonkin, Plane trees and algebraic numbers, in "Jerusalem Combinatorics 93" (H.Barcelo, G.Kalai, eds.), Contemporary Mathematics, vol. 178, 1994, 233-275.

[41] L. Schneps, Dessins d'enfants on the Riemann sphere, in "The Grothendieck Theory of Dessins d'Enfants", ed. L.Schneps, London Math. Soc. Lecture Notes Series 200, Cambridge University Press, 1994 , 47-78.