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

Следствие (из леммы 2.8). Пусть ЛГ,- диск из леммы 2.8. Тогда, если |х ^ ! = ЛГ„то N} - С ,4 S = !*,!£ С = 2С ,2 Доказательство. Пусть К° \ = NHl, i =0 - 1 . Тогда S = N, +... + >Ny+( n , - C,2) + ... + \ ( ' > N. - -1 c f ч [c ,2J > / (’ N. „2 -^ ( n Л 2 N. - — С 2 + С 2 Ч Ч У с 2 Ч*-! У , =c 2 2 Cf Первое неравенство обосновывается следующим образом. В сумме S ка­ ждое слагаемое больше последующего на величину, не превышающую С,2, по­ следнее слагаемое не превосходит С2. Эта сумма содержит не меньше слагае­ мых, чем вторая сумма, в которой, начиная с того же N ,, слагаемые убывают максимально быстро: последующее получается из предыдущего вычитанием С2, и последнее слагаемое больше, чем С2. Причем, слагаемые первой суммы не меньше слагаемых с теми же номерами из второй суммы. Следствие доказано. Предположим, что диаграмма М0 не определяет K(w). Тогда в ней нет диска Ку, определяющего A'(w). Значит, сняв менее, чем Е слоев с каждого из дисков К\ с М ,, получим поддиаграмму К\ с К„ содержащую только диски, слои которых содержат меньше, чем р областей каждый. Оценим сверху длину границы диска К \ . Лемма 2.9. Пусть диаграмма М0 не определяет множество A'(vv), и Кх- диск в М0. Тогда \ к ”‘"| <Ctp+ EC f. Доказательство. Пусть К° - К, 1 , К'{ =К, \ К?: .... К[ = К,м \ K .f , где t < E - 1. 54