Научная литература
booksshare.net -> Добавить материал -> Математика -> Линдон Р. -> "Комбинаторная теория групп" -> 154

Комбинаторная теория групп - Линдон Р.

Линдон Р., Шупп П. Комбинаторная теория групп. Под редакцией Ремесленникова В.Н. — М.: Мир, 1980. — 447 c.
Скачать (прямая ссылка): kombinatornteor1980.djvu
Предыдущая << 1 .. 148 149 150 151 152 153 < 154 > 155 156 157 158 159 160 .. 202 >> Следующая

Заметим, что это следует из леммы 6.1, если граничный слой для M состоит из всей карты Af. Действительно, в этом случае
= ^m < (<7/7?) 2-м [P — d(v)] и 2^ [Р — d (V)]^t р для всех непустых карт. Будем вести доказательство индукцией по числу вершин в Af. Сделанное замечание позволяет нам считать, что Af содержит некоторую внутреннюю вершину.
Далее, VM равно Vn плюс число вершин в граничном слое, т. е. VM = VMi-\-V'M- По предположению индукции и лемме 6.1 имеем
VM<lAn-2pr + j;n =
- J ["2 - 4/>» + 4/>г + пр] < f2 [п2 - 2пр + 4р*].
Заметим, что если п<.2р, граничный слой должен состоять из всех вершин карты Af, так как в противном случае мы получим противоречие с формулой (15). Это позволяет предположить, что п^2р,
350 Гл. V. Теория малых сокращений
2ргС^4р2. Поэтому
VM<f^2 = ^a(M)K
Вторая часть теоремы непосредственно получается из первой переходом к дуальным картам. ?
Теперь мы можем быстро доказать разрешимость проблемы равенства слов для конечных множеств R, удовлетворяющих нашим предположениям.
Теорема 6.3. Пусть F — конечно порожденная свободная группа, R — конечное симметризованное множество элементов группы F и N — нормальное замыкание множества R. Если R удовлетворяет условию С (6) или условиям С (4) и T (4), или С(3) и T (6), то проблема равенства слов в группе FlN алгоритмически разрешима 1).
? Пусть до — произвольное слово из F. Если до Є N, то рассмотрим диаграмму M минимальной ^-последовательности для до. Тогда M является (q, р)-картой, где (q, р) — это (3,6), (4,4) или (6,3) в зависимости от случая.
По теореме о площади число областей в M не превосходит величины (q/p2)(^M\p—і (D)])2. Для области карты M неравенство р—i(D)>0 выполняется только в том случае, когда dD содержит некоторое граничное ребро. Поскольку не более |ш| областей карты M могут содержать граничное ребро, получаем
0<2м [p-HD)]<P\*»\-
Если d = (qlp2) (р21 w |а) = о | до |а, число областей карты M не| превосходит d. Положим L = тахЛ/6A | г,-1.
По лемме 1.2 .W = (u[r[u[~x) ... (и'тг'и'тХ), где m^.d, ни одно! Iи'{\ не превосходит d(L +1доI) и все г\ лежат в R. Так как! каждое такое произведение лежит в N, остается сделать вывод,! что w?N тогда и только тогда, когда w-= (и'гу^'"1). ..(итг'ти'щ1),\ где m<d и I и,-К с/(L-f-1 до I).
Имеется лишь конечное число таких произведений, и можно проверить, равно какое-нибудь из них слову до или нет. Таким! образом, проблема равенства слов в GIN алгоритмически разрешима. ?
*) Как уже отмечалось, при A.<1 /5 из условия C(K) следует условие С(6) и по| приведенной теореме в группе FlR проблема равенства слов разрешима. Замени* в условии C(K) строгое неравенство на нестрогое и обозначим полученное условие через С"(<Я). В работе А. И. Гольберга [1978*] указан несложный процесс пе<1 реписки, переводящий конечное представление в ему эквивалентное, но уже удов-1 летворяющее условию С'(<1/5), что говорит о невозможности усиления резуль-| тата Линдона в данных терминах.— Прим, ред,
7. Проблема сопряженности
351
7. Проблема сопряженности
В этом разделе мы докажем некоторые результаты, необходимые для работы с кольцевыми (q, р)-картами и для решения проблемы сопряженности. Для иллюстрации несправедливости теоремы о площади для кольцевых карт возьмем, например, прямоугольник, разделенный на тп квадратов, и изогнем его так, чтобы получилось кольцо, причем отождествляться будут стороны, разделенные на п отрезков. В результате имеем покрытие кольца картой типа [4, 4]. Длина границы равна 2т, а число областей равно тп, причем п произвольно. Таким образом, не может быть такой функции от числа граничных вершин, которая ограничивала бы число областей в кольцевой (q, р)-карте.
Однако, если читатель попытается построить кольцевые (q, р)-карты с несколькими слоями, он увидит, что число областей в слое обязано оставаться неизменным или возрастать по направлению к одной или обеим границам. Пусть M — кольцевая (q, р)-карта; рассмотрим последовательность карт M=M0, M1, ..., Mk, где Mi+i получается из M1 удалением граничного слоя карты Mt. Нами будет доказано существование функции от границы карты М, ограничивающей число граничных областей в каждой из карт Mt. Именно это свойство позволит нам положительно решить проблему сопряженности. Результаты этого раздела взяты из статьи Шуппа [1968].
Лемма 7.1. Пусть M есть [р, q]-mpma, такая, что каждая ее компонента либо односвязна, либо является кольцевой. Тогда
? Доказательство аналогично выводу следствия 3.3 из основных формул теоремы 3.1. ?
Свяжем теперь дуальные карты с операцией удаления граничного слоя.
Лемма 7.2. Если M — некоторая карта, М* — дуальная к ней карта и M1 получается из M удалением граничного слоя, то M1 дуальна к карте М*.
? Поскольку М* дуальна к карте М, внутренние вершины v из M находятся во взаимно однозначном соответствии с областями D* карты M*, причем vQD*. Более того, каждое внутреннее ребро е из M пересекает в точности одно ребро е* из М*. Поэтому необходимо показать, что ребра карты M1 — это в точности ребра карты М, пересекающие внутренние ребра карты М*. Это эквивалентно тому, что ребро карты М* является граничным в этой карте в том итолькотом случае, когда оно пересекает некоторое ребро карты М,
Предыдущая << 1 .. 148 149 150 151 152 153 < 154 > 155 156 157 158 159 160 .. 202 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed