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

ципиально. Пусть для определенности »(£>®+ 3 ) = 3. Рассмотрим диаграмму L = L\ и . a) Пусть I cfkdL п о )| = 2 1н>|. Тогда i(Dp+] ) = 2. Предположим противное, пусть i(Dp+i) = 3. Тогда, рассуждая как и выше получим, что i(Dp+2) = 4. Из строения слоя Ка<) следует, что для некоторого j в L2: 3 < j < р-r существуя область D ,+j с i(D ,+j ) = 2. Пусть это наименьшее j с таким условием. Тогда, если наклеить £| на 1 2>то, во избежание возможных противоречий, получим, что в L\ должна быть область с четырьмя внутренними ребрами, причем в но­ вой диаграмме АТона должна располагаться строго над областью D°+y, то есть в L\ это будет область />у _2 • Но тогда по структуре слоя получаем, что между областями £>у -2 и D ®+2 должна быть область с двумя внутренними ребрами, то есть существует такое h >j , что г( D%) = 2 , тогда в ей соответствует об­ ласть Dr+f ,+2 с четырьмя внутренними ребрами. Опять из строения слоя сле­ дует, что между областями Z )®+/,+2 и Dp+2 должна быть область с двумя внут­ ренними ребрами. Очевидно, что этот процесс «чередования» будет продол­ жаться до бесконечности, чего быть не может в силу ограниченности длины слова w. Итак, i(Dp+ 1 ) = 2. Применяя рассуждения, проведенные в п. 1.1.1.1. полу­ чим, что слой Ка периодический с периодом из р областей и s = пр. Будем го­ ворить, что у нас слой типа b) I qidL п а ) I>2 |и>|. Если i(Dp ) = 3 и при этом :'(D®+| ) = 3 или 2 (i(Dp) = 2, i(D °p+\ ) = 3), то, наклеив копию области Д° к областям D°p и 0 ° и , получим противоречие либо с условием Т(4), либо слова из R сократимы. Если i(Dp) = 3 и i(D °p+i) = 4, то приходим к противоречиям, как в а). Пусть, наконец, i{Dp ) = 2, но i(Dp+\) = 4. Наклеим области £>®, Dr°+• к областям Dp , D p+(. Тогда, поскольку в силу особенностей строения слоя Ка(] область О® может иметь не более трех внутренних ребер, то в новой диаграм­ ме вершина А = 8 0 ^ п 8Dp будет либо внутренней степени 3, либо слова из R сократимы. 2 . I U||>|w|. 2.1. Пусть /(D®) = 3 и ср (3D® n o ) = га, \г\ + |а| = к. 2.1.1. г(£>®+ 1 ) = 2 или 3. Наклеим область D,° на Dr°uD ,°+| по границе а. Тогда либо А - внутренняя вершина степени 3, либо слова из R сократимы. 124