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

Диаграмму A, \ K f обозначим через К0. Для получения оценки разности K f - А,”' рассмотрим диаграмму ( а ,0“) - представитель элемента из A(w), одна из граничных меток которого содержит метку ф(а|) в качестве подслова, а диаграмма К°' U ( а ““) , полученная склеиванием двух кольцевых диаграмм по границе с меткой Ф(ст!)> является приведенной, то есть номера оснований диа­ грамм А,0' и ( а "; ) ’ как представителей элементов из А(и-) отличаются на 1 . Наклеим ( а ,0") на диаграмму А 0 по границе ст]. Все области из слоя А"' сокращаются с областями из [К ,”' ) . В результате удаления всех пар взаимно обратных областей из диаграммы А„ U( a i<’‘ ) получается диаграмма А0, в ко- торой на тех местах, где в А 0 были простые пути у , , - диски из областей слоя ( а °“) , а диски из А0, возможно, распались на более мелкие диски, причем все указанные диски соединены в А 0 простыми путями у2. Заметим, что диаграмму А 0 можно получить, наклеив на диаграмму М0 по границе а 0слой с основанием, как в слое А,0”, а затем - слой с основанием, как в ( а ,"’ ) . Полученная после удаления всех сократимых пар областей коль­ цевая диаграмма принадлежит множеству М{м>). Поэтому в ней - не более С, дисков. Следовательно, в ее поддиаграмме А 0 - не более С, дисков. Итак, из вышесказанного выше следует, что в диаграмме А 0 \ K f - не бо­ лее С, дисков. Как и выше, получаем неравенства: >А°: - [ а ,”' j< С,2, K f’ > iA,"’i—С2. И так далее. По условию A“~i = 0 . Поэтому jA °'| < C,\ Cf > ( a ”*'1. - С ,2 , откуда име­ ем: ! a ; - !!< 2C f...,iK fi <i0C ?, что и требовалось. Лемма доказана. 53