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

Лемма 3.1. Граничные метки диаграммы М} либо циклически R, R - несо­ кратимы, либо становятся таковыми после выполнения п копий одного и того же сокращения. Причём, и при отсутствии сокращения, и после выполнения п копий сокращения на внутреннюю границу полученной кольцевой диаграммы нелыя наклеить слой из областей с двумя рёбрами на внутренней границе слоя. Доказательство. Достаточно доказать утверждение леммы для слова ф(т4). Покажем, что предположения о возможности приклеить на т 4 депов­ скую область или полосу приводят к одному из встречавшихся выше противо­ речий. Пусть в слове ф(т 4) есть R - сокращение. Наклеим на внутреннюю границу J .•i‘ • диаграммы М; деновскую область Д (рис. 1). Длинные вертикальные стрел­ ки на рисунке 1 отделяют друг от друга основания степени, написанной на гра­ нице <т0, а короткие стрелки указывают общие подслова в граничных метках различных областей. Деновская область Д имеет на границе т 4 не менее четырёх рёбер. Если эти рёбра принадлежат 1 раницам областей то, поскольку Sf,S^,S/t7 имеют по два ребра на т4, либо в области нарушается условие С( 6 ), либо области образуют сократимую пару, вследствие чего граничные метки областей свободно сократимы. Если рёбра области Д принадлежат об­ ластям ,Д , то имеют место те же противоречия. Если рёбра области Д принадлежат областям то возможны три случая. 67