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

ше. Поэтому считаем далее, что tM (D) > 1. Применим к диаграмме А /0 формулу кривизны: — /(Z>)] S 4(*■) [3]. Область D дает вклад в эту сумму самое DaM большее 1 , а значит в диаграмме М0 по лемме 2 можно выделить не менее двух полос. Хотя бы одна из них должна быть расположена на участке границы дМ\Г\у, что противоречит R - несократимости слова <Ду). Лемма доказана. Определение 16. Граничная область D в кольцевой диаграмме М называ­ ется правильной , если dDndM - связное множество. В противном случае об­ ласть D называется неправильной. Лемма 13. Пусть М - диаграмма из теоремы 3 и в М больше двух областей и нет неправильных областей. Тогда существуют области Д* и De с М такие, что 1) dDAndM и dDsT\dM - связные множества, {А, В) = у nS; 2) дйАпуФ 0 , ЗД| r\S* 0 , dDBn y * 0,dDer\S* 0 и все четыре множества содержат ребра. Доказательство. От противного. Предположим, что 1. Ни при А, ни при В нет областей указанного типа. Значит, существуют области D', D", П , О", где D' и £>'содержат точку A, D" и D" содержат точку 8 ; все четыре области имеют ребра на дМ\ dD 'r\ dD и д D ”n dD" - ребро. Докажем последнее утверждение. Допустим, что области D' иD ', D" и D” имеют только общие вершины А и В соответственно. Это означает, что сущест­ вуют области D 0 и D0 : /(Do) > 4, /(D 0 )> 4 и dD0 n dD' и 3D 0 n dD '- ребра и __ __ _ $+1 /+1 3D 0 n dD " и 3D 0 ndD " - ребра Пусть Kr= (JD /, K g- ( J Dj - области из M, 1 =1 J =I граничащие с у и S соответственно. Области пронумерованы по ходу следова­ ния от Л к В вдоль/ h « D , = D ' , D | = D’, DJ+, = D", D/+] = D". Замечание. Для любой области D 6 Кг или Kg i(D) е {2,3,4} и любые две области с двумя внутренними ребрами разделены областью с четырьмя внут­ ренними ребрами (не считая областей с тремя внутренними ребрами). Применим формулу кривизны к диаграмме М: i [ 3 - / ( D ) ) = i ( 3 - / ( D ) ] + i[ 3 - i(D ) ] + [ 3 - /(D 0)] + [3 -/(D ^ )] 0=М DaKr DcKg В силу сказанного только что замечания I и II - ое слагаемые дают макси­ мальный вклад в эту сумму не более 2. Вклад III и IV слагаемых по -1, т.е. • _ _ £ [3 - /(D)] < 0 - противоречие. Итак, dD 'n dD и d D " n dD " - ребро. DeM Далее рассматриваем всевозможные ситуации, когда /(D), /(D'), /(D'), /(D") е {2, 3}. И во всех получающихся диаграммах, рассуждал как и выше, 115