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

зательства леммы 6 следует, что СТ > К Т * - 2СС > . . . 2 : А,° а , 0 число К?'" К \ \ Итак, в диаграмме Af +1 все диски короткие, то есть в каждом из этих дисков на выходит менее чем р областей. Таких дисков, очевидно, менее + (f + 1)С] . Поэтому достаточно ограничить '‘'-Ч" -.2 * ■ i \i ЮиД \ I c S O lir ii О Ч - a J :i Cj , следовательно К*"* <рС\. Итак, *Г° < рС\ +(t+ 1)С,2 £ рС, + EWC\ . Лемма доказана. Следствие 8.1. Если в исходной диаграмме М0 все длинные диски, такие как в лемме выше, то числа п, т можно ограничить. Замечание. Точно также как это было сделано для слова w, определяется множество ]i (v), (v) и разбиение множества длинных дисков на два типа. а \ ri Замечание 2. Заметим, что если слой А, 0 - слой I типа, то слой А| 0 мо­ жет быть слоем 1 -го или И-го типа. Далее поступаем следующим образом: приведем нашу диаграмму М0 к (Г*- т такому виду, что слои А,- J длинных дисков А/ для некоторых i и слои А ,-1 бу­ дут одного типа, не обязательно одинаковыми. Для этого 1. Рассмотрим элемент из (w) с основанием как и в слое А, 0 диска А/. Рассмотрим кольцевую диаграмму A;: (pidNi) = wg и w", Склеим диаграммы М0 и Ni по границе с меткой Wg . Приведенную диаграмму, полученную из MflUAfy после удаления областей из дисков I-го типа, сокращающихся с облас­ тями из N; обозначим через N \. <p(dN\) = w" и v~2m. Диски второго типа стали в А] длиннее и толще, а диски I-го типа - короче и тоньше и, возможно, распа­ лись на более короткие диски первого типа. Далее наклеиваем на А( по границе с меткой w” кольцевую диаграмму А;, имеющую общее со слоем А ^1 основание и одну из граничных меток и’” . Удаляя из диаграммы Aj и Аг пары взаимно обратных областей, получим диа- • п 2 m грамму А 2 с граничными метками и >2 и v . Указанные преобразования продолжаем до тех пор, пока не получим диа­ грамму А; в которой длинные диски по границе а, одного - Н-го типа. .* I Вернемся к диаграмме М0. Точно так же, как А,- из Мо строится диаграм­ 135