Комбинаторная теория групп - Линдон Р.
Скачать (прямая ссылка):
6. Проблема равенства слов
347
С этого момента действие будет развиваться по двум в равной мере интересным, но независимым направлениям. Следующие три раздела посвящены более детальному изучению геометрии (q, р)-карт, решению проблем равенства слов и сопряженности в случае, когда F — свободная группа, а конечное множество R удовлетворяет неметрическим условиям С(р) и T(q), и приложениям к группам узлов.
Вторая возможность — переход к изучению алгебраических приложений теории малых сокращений. Эти приложения используют теорию малых сокращений над свободными произведениями, свободными произведениями с объединенной подгруппой и HNN-расширениями. Читатель, интересующийся только алгебраическими приложениями, может перейти к разд. 9.
6. Проблема равенства слов
В этом разделе мы продолжим изучение свойств односвязных [р, <7І-карт и разрешимость проблемы равенства слов при наложении неметрических условий С(р) и T(q). Полученные здесь результаты принадлежат Линдону [1966]. Нашим основным результатом будет теорема о площади. С комбинаторной точки зрения разумно определить площадь карты M или как число VM вершин этой карты, или как число FM областей этой карты. Если читатель нарисует несколько [р, <7]-карт, то он увидит, что они «растут по направлению к границе», т. е. увеличение размера карты отражается на ее границе. Мы покажем, что площадь односвязной [р, <?]-карты ограничена некоторой функцией, зависящей только от границы. Из этого факта легко получается решение проблемы равенства слов.
Лемма 6.1. Если М — [р, q]-Kapma, такая, что каждая ее компонента является либо односвязной, либо кольцевой, то
(6.1) Ем<1?и[р-а(о)] и
(6.2) V*<f?M[P-d(»)]. ? Перепишем формулу (3.1) в виде
'''Ek = f E'[P-d(V)] + 3- ?°[р-d(V)] + Ya[q-d(D)]-q(Q-h).
Поскольку M является [р, <7]-картой и h, то только первый член может быть положительным. Следовательно,
348 Гл. V. Теория малых сокращений
Пусть M1- подкарта карты М, получающаяся вычеркиванием всех изолированных вершин. Из Vm1 Em1 с помощью леммы 3.2
получаем VMl^^YaMi[p-d{v)].
Если изолированных точек нет, то заключение леммы доказано. Если изолированные вершины имеются, то обозначим через Q0 их число, а через M0-подкарту карты М, состоящую из этих вершин. Тогда
J Hm0 [P -d И = <7Qo > Qo = Vm0. Поскольку Vm=Vm1 +Vm,, лемма доказана. ?
Определение. Пусть M — произвольная карта. Граничный слой карты M состоит из всех граничных вершин, ребер, содержащих граничные вершины, и граничных областей карты М.
Если M — некоторая [р, д]-карта, введем обозначение
о (M) = 2м [р -a (V)].
Теорема 6.2. (Теорема о площади.) Пусть M1-односвязная [р, а]-карта. Тогда
VM<lo(M)\
Двойственным образом пусть M — односвязная (q, р)-карта. Тогд Рм<р(1м[р-НО)])У
? Докажем вначале, что если M есть [р, д]-карта, содержаща некоторую внутреннюю вершину, a M1 получается удалением гра ничного слоя карты М, то
о (M)—a (M1)^p.
Перейдем сначала от M к M', удаляя по одной граничные вершины степени 1 и изолированные вершины. Если граничные вершины степени 1 имеются, рассмотрим одну из них, скажем v. Пусть M'" получается из M удалением вершины v и ребра е, содержащего v. Вершина V дает вклад р—1 в о (M). Поскольку р>2, р—1>1. Пусть V2 — другая концевая точка ребра е. В карте M'" степень d(v2) уменьшилась на 1, откуда a (M)—а(М"') = [(р—1)—1]>0 и а (M)^o (M'"). Будем удалять граничные вершины по одной, пока они все не будут удалены. Обозначим через М" конечный результат этого процесса. Тогда о (M)^o (M"). В результате удаляются все компоненты карты М, являющиеся деревьями, а также всё шипы*: прикрепленные к М.
Пусть M' получается из M" вычеркиванием всех изолированных* вершин. Если их число равно Q0, то их вклад в о (M") равен Q0p. Следовательно, о (ЛГ)>а (M').
6. Проблема равенства слов
349
Теперь мы в состоянии показать, что a (M')—а(М1).>2р. Мы можем предполагать, что M не содержит изолированных вершин, а также граничных вершин степени один, и не будем вводить M'.
(1) Пусть п = 2„[P-Cl(V)].
(2) Пусть U1 == [P — di (v)], где dt — функция степени для Af1. Пусть I —множество ребер с концами на дМ.
(3) Пусть e1 — число ребер в точности с одним концом на дМ.
(4) Пусть e2-число ребер с двумя концами на дМ.
(5) Пусть s = ]?Md(v). Тогда
(6) 5 = 8^28,.
(7) Пусть /(v) = U(V)-U1(V). Тогда /(и) —число ребер, содержащих V и лежащих в \.
Если V^dM1, TOV — внутренняя вершина карты Af и d(v)^p. Следовательно, используя (7), получаем
(в) «і=2м, [р - di W < 2«, P W - di И=23м, / (")•
(9) 23«,/» = «і-
(10) Можно записать л = 2м р — 2м ^ (u)= P^ м — s. Отсюда, используя (6), (8) и (9), выводим
(11) п—H1 = pVM-S-Ii1 ^рУ'м — s-e1 = рУм — 2s + 2e2. Поскольку в Af нет изолированных вершин или граничных
вершин степени 1, имеем
(12) VM^e2. Поэтому
(13) n-n1^pVM-2s + 2VM = 2[(p/2 + \)VM-s] или, используя (5) и переписывая,
(14) п - H1 > 2 Ум [(р/2 +1) -d (V)] = 2 2« [(р/<7) + 2 - d («)]. По следствию ЗІ5 эта последняя сумма не меньше 2р. Значит,
(15) о (Af)-a (Af0>2Я.
Теперь нам нужно доказать, что VM^ (q/p2)o (Af)2= (q/p2)n2.
