АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ ТЕОРИИ ГРУПП И ПОЛУГРУПП 2001 г.

Определим далее два множества. 1. Определим множество f(w ) как множество, состоящее из Е„ 1-слойны кольцевых диаграмм, имеющих такое же строение, как и слои диаграммы М . Т.е.. каждый элемент этого множества содержит п экземпляров каждого из ос­ нований ко, , *£■„-! • Элементы множества ) (w) будем обозначать через Ko(w) .......... Через °ь обозначим граничные циклы элемента K,(w), а через w" , w"+] (i = 0 , . . . , Ew -1) - граничные метки. Очевидно, что можно пронумеровать элементы множества (w) так, что если K,(w) и K/w) имеют общую граничную метку w ” , то I j-i )=1 (mod Ew). 2. Метками элементов из (и>) являются степени слов wh . . . В связи с этим понадобится рассмотреть множество (w) всех приведенных диаграмм сопряженности слов и>" со словом v2". Очевидно, Л/е (w). Из минимальности чисел п, т следует, что если A f e (и>) - диаграмма сопряженности слов w” и v , то из АР нельзя вырезать поддиаграмму М”, замкнув которую в кольцо, получим диаграмму сопряженности слов w "', v2m' при 1« |I< Ы , lm ,|< | т | . Действительно, предположим противное. Пусть у нас <р[дМ") - w"1 и V2m>. Наклеим на границу w”1 полученной диаграммы М" диа­ грамму, склеенную из менее чем Ew слоев множества (w). Получим диаграмму М ’"сопряженности слов w2n,= w j'и v2m| при |и )|< |л |, |/nil< |m |, что про­ тиворечит выбору чисел п, т. Пусть далее А/о - диаграмма из l/(w) с условием I М п 1= mmMe </АдМ0) = Wg и V2". Ясно, что диаграмма М 0 - простая: если она С-А-слойная при к > 0, то сняв с Мо ^-слойную поддиаграмму, получим диаграмму из i i(w), но с меньшим числом областей; если же у нас Л-слойная диаграмма, то получа­ ем, что либо степень слова w сопряжена со словом v, либо наоборот, а в этой ситуации показатель степени можно ограничить, как следует из [5]. Определение 5. Пусть К - приведенная односвязная диаграмма, дК = а и х , причём а п г= {А, В } - две вершины. Слова <р(а), <p(x)R,R- несо­ кратимы. Поддиаграмму диаграммы К, состоящую из областей D: dDncr * 0 (8Dn г ф 0 ) назовём Ка (К') - слоем диаграммы К (К - диск). Рассмотрим простую диаграмму М0 с граничными метками wq , v'2m, со­ стоящую из дисков К„ i > Ос границами о;, г,: аулт, = {А„ В,} и соединяющих р р их простых путей у, с концами В„ Ам : М а = ( U ^ l ) u (UP/)* в каждом из этих /=1 ;=1 дисков рассмотрим К ° ‘ - слой, i > 0. Лемма 5. Рассмотрим простую диаграмму М0, определенную выше. Для 129