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

Покажем, что U S (U ') 1.Цусть D 1 и и 2 ) * ' будут области из Д, такие, что ( f (Э ( А ) Л Э С А ' ) ) е ^ и l(?(3(t>k)П Э О > к ))5 а ' .Имея j f ( э О ) , ) П & ) s f t , }{д{Ц¥\Ч )гк , Ц (ъ{Т> 'к ) Л г ) а Я ,' ( (р (з(Т > ь )П 'г )З ъ f l / f положим, что метками областей £>*' , Z> *, Z), , 2 >/ являются слова , At# fit , fii^i и 1 , /fit a S', f соо тветствен ­ но. Пусть, для определённости, /4|>|и'| .Тогда из двух тождеств * fi< S i U. 1 и fit (L i ')"1 & f l e U S,' следует Ц'(£ U ^1 U.' , где U * U , , а также что слова ( S j.) * 'и Цj 1 имеют непустой общий конец, а сло ва и U, ишют непустое оборе начало, то есть слово Sk Sk свободно приводимо.Если же 1 U.I < |ц‘ | , то аналогично приходим к свободной приводимости слова S,‘ . Поэтов C » U p 1 ...C jt U .'1 Пусть D c есть области из 4 , U ( I f т а кие, что П (3 ) « fie и ЗЭ, содержит ребро с веткой С, . Пусть (jt есть ребро из области D , , общее с областью, граница которой пересекает т .Если if { a j a r C l для , то имеем, что Д & J J g * UC\ ... Qg LC* .Покажем, что <?«... C( « ( С « ...< \ ± ) ш , где d K e .l c ) . Пусть £ * k , то есть C>k .В е й л у ti= по усло­ вию c'(J/4), имвем, что Ok tiss Oj , Ckt2s Ct и так д а л е е , То есть P i® Cj , если 1*^' (и тЫ к ) .Если lexj, + р , где 0 * р е к , то C i .* Cj при i (tn o c fp ) .В конечном итоге имеем P is Cj при (m od сО . Таким образом, получаем, что A - U (61 цС* и С * IKC i Ц ' 1 , что противоречит условию ( 2 ) определения множества М , Следовательно, диаграмма А не может быть двухслойной. Покажем, что А не может быть однослойной диаграммой ни при <3"f l У * 0 , ни при , ( Есди С П Х = г 0 , т о , в силу условия Т (4 ), существую^ две области 3>i и Х>г из А таких, что Э ( 1 \ ) . е и &=• < р ( Эф , ) Пе з ) » ( f 1 , /Г < & 1 Р (Э й Х )П fit-) * ф ( Э ( о г) Л ей )'1, откуда, в силу условия (/(1/4), следует невозможное Ц )(е) * 1 . Предположим поэтому» что & л -г jg f .То гда Р с 1 , а следовательно, в силу условия ( 2 ) , f t i i и 6 ^ 1 . Покажем, что в этом случае г» = 4 . Предположим для этого противное, то е с т ь , что а > 4 ,в зедятим, что,в силу Д 6 р &Д , диаграмма А имеет по 47