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

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

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

Введение

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

1.1. Вычисление мер подгрупп.

1.2. Мультипликативность меры

Глава 2. Разреженные и строго разреженные подмножества свободной группы.

2.1. Регулярные подмножества свободной группы.

2.2. Определение и простейшие свойства строго разреженных множеств.

2.3. Критерий строгой разреженности регулярных подмножеств свободной группы.

2.4. Конструкции над строго разреженными множествами.

2.5. Разреженность двойного класса смежности по подгруппам бесконечного индекса.

Глава 3. Алгоритмы приведения элементов фундаментальных групп конечных графов групп к нормальной форме.

3.1. Основные определения.

3.2. Случай линейного графа.;.

3.3. «Чупа-чупс».

3.4. Треугольник.

3.5. Произвольный конечный граф.;.

3.6. Единственность ^-нормальной формы элементов фундаментальной группы конечного графа групп.

3.6.1. Граф У-дерево

3.6.2. Граф Уне является деревом

3.7. Оценка процедуры I .'.

Глава 4. Критерий сопряженности для элементов фундаментальной группы конечного графа групп.

4.1. Обозначения и основные определения.

4.2. Ассоциированный граф является деревом.

4.3. Произвольный конечный граф групп.

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

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

В 192G году Э. Артин сформулировал понятие свободного произведения групп на языке нормальных форм. Независимо от него в 1927 году О. Шрайср также ввел это понятие, используя язык представления групп с помощью порождающих и определяющих соотношений; в том же году он дал определение группы повой конструкции -свободного произведения с объединенной подгруппой - и описал нормальные формы элементов таких групп. А.Г. Курошем в 1934 год}' была доказана структурная теорема о подгруппах свободного произведения групп. В 1949 году в совместной работе Г. Хиг-мапа, Б. Неймана и X. Неймаи было введено понятие еще одной свободной конструкции — HNN-расширепия групп.

В 19С8-1969 годах возникает теория Басса-Серра, объясняющая с геометрической точки зрения многие результаты, полученные для групп, являющихся свободными конструкциями. В то же время Ж.-П. Серром было дано определение фундаментальной группы графа групп, обобщающее понятия свободного произведения с объединением и HNN-расширения (см. [1]).

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

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

Вероятностные меры на свободных группах были введены в работе А. В. Боровика, А. Г. Мяснпкова и В. Н. Ремссленникова [5]. В работе [9] эти вероятностные меры были распространены па свободные групповые конструкции и применены для исследования генерической сложности проблемы равенства слов и проблемы сопряженности.

По этим направлениям проводятся исследования в диссертации.

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

1. Serre J.-P. Trees 1. Berlin-Heidelberg-New York: Springer-Verlag, 1980.

2. В.Магнус, A.Kappac, Д.Солитэр Комбинаторная теория групп // М.: Наука, 1974.

3. Липдои Р., Шупп П. Комбинаторная теория групп // М.: Мир, 1980.

4. Богопольский О.В. Введение в теорию групп И М.: Современная математика, 2002.

5. A.V. Borovik, A. G. Myasnikov, V. N. Remeslennikov Multiplicative measures on free groups II International Jornal of Algebra and Computations 13 (2003), P. 705-731.

6. I. Kapovich, A. Myasnikov, P. Schupp, V. Shpilrain Generic-Case Complexity Decision Problems in Group Theory and Random Walks // Jornal of Algebra 264 (2003), no 2, P. 665-694.

7. David B.A. Epstein and others, Word Processing in Groups II Jones and Bartlett Publishers, 1992.

8. Каргаполов М.И., Мерзляков IO.И. Основы теории групп IIМ.: Наука, 1977.

9. A.V. Borovik, A. G. Myasnikov, V. N. Remeslennikov The Conjugacy Problem in Amalgamated Products I: Regular Elements and Black Holes II to appear: International Jornal of Algebra and Computations.

10. Kapovich I., Myasnikov A. Stallings Foldings and Subgroups of Free Groups, Jornal of Algebra 248 (2002), no 2, P. 608 668.

11. Gregory Quenell Combinatorics on free product graphs Geometry of the spectrum II (Seattle, WA, 1993), Amer. Math. Soc., Providence, RI, 1994, pp. 257-281.

12. Laurent Bartholdi Counting Paths in Graphs II arxiv:math.co/0012161 vl 18 Dec 2000.

13. E.C. Есып, В.H.Ремесленников Уравнения от одной переменной над свободными произведениями циклических групп II Препринт ном. 31. Омск: ОмГАУ, 2000.

14. Гэри М., Джонсон Д. Вычислительные машины и труднореишемые задачи II М.: Мир, 1982.

15. Я.С. Аверина, Е.В. Френкель Полиномиальный алгоритм приведения элементов некоторых групп Баумслага-Солитера к нормальной форме II Вестник Омского университета, 2004, выпуск 2(32), с. 16- 18.

16. Я.С. Аверина, Е.В. Френкель Разреэюенность классов смеэ/сности по подгруппам свободной группы II Вестник Омского университета, 2004, выпуск 4 (34), с. 25 27.

17. Я.С. Аверина, Е.В. Френкель Вычисление меры подгрупп свободного произведения циклических групп!/ Вестник Омского университета, 2002, выпуск 3(25), с. 13 15.

18. Я.С. Аверина, Е.В. Френкель Разреженность классов смеэ/сности по подгруппам свободной группы!/ Препринт№00-01, Омск: Омск. Госуниверситет, 2004 14с.

19. Я.С. Аверина, Е.В. Френкель Алгоритм приведения к канонической нормальной форме элементов фундаментальных групп графов групп/! Преприпт№00-02, Омск: Изд-во ОмГУ, 2005-20с.

20. Я.С. Аверина, Е.В. Френкель О строго разреэюенных подмножествах свободной группы!7 Сибирские электронные математические известия, ISSN 1813-3304, ТОМ 2 (2005), с.1-13, http://semr.matli.nsc.ru.

21. Я.С. Аверина Критерий сопряженности для элементов фундаментальной группы конечного графа групп!! Препринт№00-03, Омск: Отдел оперативной полиграфии фирмы «Банковский сервис», 2006 1 б с.