Меры и нормальные формы для фундаментальной группы конечного графа групп

• Автор: Аверина, Яна Сергеевна
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Омск
• Количество страниц: 67 с.

Глава 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. Произвольный конечный граф групп
Список литературы

Среди многих проблем, которыми занимается комбинаторная теория групп, важнейшими являются алгоритмические проблемы и изучение свойств свободных конструкции над группами. В последние годы бурно развивается и статистическая теория групп, предметом которой является определение различных мер на группах, вычисление роста групп, порождающих функций, функций Дэна и т.д. Исследования в данной диссертации проводятся в рамках этих двух направлений теории групп.
В 1920 году Э. Артин сформулировал понятие свободного произведения групп иа языке нормальных форм. Независимо от него в 1927 году О. Шрайср также ввел это понятие, используя язык представления групп с помощью порождающих и определяющих соотношений; и том же году он дал определение группы новой конструкции -свободного произведения с объединенной подгруппой - и описал нормальные формы элементов таких групп. А.Г. Курошем в 1934 году была доказана структурная теорема о подгруппах свободного произведения групп. В 1949 году в совместной работе Г. Хиг-мапа, Б. Неймана и X. Нейман было введено понятие еще одной свободной конструкции — НИХ-расширения групп.
В 19С8-1969 годах возникает теория Басса-Серра, объясняющая с геометрической точки зрения многие результаты, полученные для групп, являющихся свободными конструкциями. В то же время Ж.-П. Серром было дано определение фундаментальной группы графа групп, обобщающее понятия свободного произведения с объединением и НИХ-расшпрения (см. [1]).
В настоящее время свободные групповые конструкции широко используются в комбинаторной теории групп, в частности, при построении примеров, связанных со сложностью алгоритмических проблем (например, для доказательства неразрешимости классических алгоритмических проблем). При исследовании упомянутых проблем, как разрешимых, так и неразрешимых, плодотворной является идея стратификации входных данных по сложности рассматриваемых алгоритмических проблем. На этом пути определяется регулярная часть алгоритма, то есть множеств входных данных, на которых алгоритм работает быстро (например, в линейное или квадратичное время), а также дополнение к регулярной части - черная дыра алгоритма - множество элементов, про которые мы либо не знаем, как на нем работает алгоритм, либо знаем, что алгоритм на нем работает плохо.
Как правило, при решении алгоритмических проблем вычисления проводятся либо со словами свободной группы, либо со стандартными нормальными формами для
іі дальнейшем мы ограничимся рассмотрением лишь тех групп tti(G, Y), у которых все вершинные и реберные группы конечно порождены и свободны. Кроме того, будем полагать, что для различных вершинных групп G; ~ F(X) и Gj ~ F(Y) алфавиты Л' и Y не пересекаются. Рассмотрим некоторую вершинную группу G,- и одну нз ее реберных подгрупп А у Пусть щ — представитель из класса Ajg, полученный в результате обработки (г) Для данного слова дг є G; представитель р имеет минимальную длину в классе Ajij.
(И) Существует константа Мі такая, что для всякого гд Є G;, если дг = а ■ р, то |п| <
Ы + М{.
(Ш) Время, затрачиваемое па работу алгоритма AjP на входе гд, ограничено сверху величиной Ligi для некоторой константы Д.
Кроме CRSP, в процедуре I замаскирован переписывающий процесс Р, а именно: пусть Gi и Gi — вершинные группы, инцедентиые одному ребру (в пашем случае G; ~ F(X), Gi ~ F (Y), где X и Y — конечные алфавиты), Aj — реберная подгруппа, соответствующая одному из ребер е, соединяющих вершины для G,- и G;. В силу наличия изоморфных вложений Aj в Gi и G/, а также соотношений вида ae(Aj)a^'(Aj) или t~lac(Aj)ta^l(Aj)(в зависимости оттого, входит или пет ребро с в максимальное поддерево Т) произвольное слово w из Aj может быть записано в порождающих < u Uk >— Aj, где щ, і = 1,к слова в алфавите X, либо в порождающих < vi,... ,Vk >= Aj, где Vi — слова от Y. Если w записано в порождающих г,, і = 1 ,к, то есть w = w(vi,... ,?;*,•), его можно переписать как w — w{u,... ,Uk), выражая и,- через uj. II наоборот, если w = iv(ui,.. ■ ,щ), то можно получить его запись в порождающих ід. Для вершинных групп Gi и Gi и их реберной подгруппы Aj введем константу Xu, - шах{А,-у (u, v), Xuj (и, и)}, где
max{ui u*}
A uj{u,v) = р.
Таким образом, верни неравенства
w{ui,... ,ик) < XUjw{vi vk) j
|iu(ui w*)l < Aiy|w(ub ... ,ик)
Рассмотрим пседиппчный элемент g = gig-г, g і Є G;, Є G/. Для приведения g к канонической нормальной форме нужно воспользоваться ШАГОМ 2 процедуры I. Сначала