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

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

Линдон Р., Шупп П. Комбинаторная теория групп. Под редакцией Ремесленникова В.Н. — М.: Мир, 1980. — 447 c.
Скачать (прямая ссылка): kombinatornteor1980.djvu
Предыдущая << 1 .. 97 98 99 100 101 102 < 103 > 104 105 106 107 108 109 .. 202 >> Следующая

8*
228
Гл. III. Геометрические методы
число вершин. Следовательно, мы получаем, что т=щ—/+1, а это и требовалось. ?
Обрисуем связь между диаграммами Кэли и способом Тодда и Кокстера перечисления смежных классов. Диаграмма Кэли C = C(X; R) для симметризованного представления G = (X; R) может быть построена индуктивно^ как предел C00 последовательности диаграмм Са при отображениях уа^. Са—*Ср, а <?. Ограничимся случаем, когда представление конечно, a C00 есть предел последовательности C0, C1, C2, ... конечных диаграмм при отображениях ykl, определенных отображениями yk: Ск—>-Ск+1. Удобно считать, что множества X и R упорядочены, и на каждом шаге задавать порядок на вершинах диаграмм Ск.
Начнем, выбрав диаграмму C0, состоящую из единственной вершины v. Предположим теперь, что диаграмма Cft задана и построим Ck+i вместе с ук и порядком на вершинах диаграммы Ск+1. Возможны три случая.
Случай 1. В некоторой вершине v диаграммы Ch начинается путь р, не являющийся петлей, граничная метка г которого лежит в R. Выберем первую такую вершину, а для нее — единственный путь с наименьшим возможным г. Пусть р идет от и к у'. Определим отношение на вершинах из Cn, полагая и=«', если существуют пути q из V в и и q' из и' в и' с одинаковой меткой. Порождаемое отношение эквивалентности дает и эквивалентность на множестве ребер, которая сохраняет инцидентность и метки. В качестве Ск+1 возьмем фактор диаграммы Ся по этому отношению эквивалентности, причем ук— проекция. Упорядочим вершины из Ск+1 в соответствии с наименьшими их прообразами.
Случай 2. Такой ситуации, как в первом случае, нет, но для некоторой вершины V и некоторой буквы у=х±х (х? X) не существует ребра, выходящего из v, с меткой у. Выберем первую такую вершину V, а для нее — первый такой элемент х. Положим у=х, если нет ребра, выходящего из v с меткой х; в противном случае у=хх. Диаграмму Ск+1 получаем из Cn добавлением новой вершины и вместе с ребром из VBU, имеющим метку у. Отображение yh— это вложение. Вершины в Cft упорядочены, как и раньше, а новая вершина и следует за ними.
Случай 3. Ситуации, описанные в двух предыдущих случаях, отсутствуют. Определим тогда Ск+1=Ск с тождественным yh.
Если C00 есть предел диаграмм Ск при отображениях yh, то легко понять, что диаграмма C00 изоморфна диаграмме Кэли С. Очевидно, что если для Cft имеет место случай 3, то C00=Cj1, и поскольку диаграмма Кэли C00 для этого представления конечна, то группа G должна быть конечной. Немногим труднее сообразить,
12. Диаграммы смежных классов
229
что, наоборот, если группа G конечна, то для некоторого k диаграмма Си попадает в случай 3, а значит, C00=CV
Испытаем теперь метод перечисления смежных классов в частном случае смежных классов по тривиальной подгруппе H=I. Интересно для данного представления G= (X; R) выяснить, является ли группа G конечной, найти ее порядок и получить ее представление подстановками (на самом деле регулярное представление), если она конечна. Мы предполагаем, что каждый порождающий X из X встречается (как х или х-1) в некотором соотношении г из R, иначе, очевидно, группа G бесконечна. Мы не требуем, далее, чтобы множество R было симметризовано. Способ будет состоять в том, чтобы расположить некоторый вариант изложенной выше конструкции в табличной форме, пригодной для эффективных вычислений.
Интуитивно последовательные шаги в построении диаграммы состоят в составлении надлежащим образом списков наименований для вершин по порядку на каждой петле с меткой г, где г Z R- Для каждого г Z R образуем таблицу этих списков и на некоторых шагах (примерно соответствующих случаю 2 в приведенной выше конструкции) добавляем новые списки к этим таблицам. На других шагах (отвечающих случаю 1) мы устанавливаем некоторую эквивалентность между наименованиями в нашей таблице, означающую, что они являются названиями одной и той же вершины.
Пусть слово г ^Ry скажем r=y1... уп, приведенное, и все у і лежат в XUX'1. Составим для г таблицу, как показано ниже, помечая внутренние вертикальные разделительные линии буквами ух, ..., уп.
Уі
У п-і
Уп
Vi
V2
V3 ... ?»„_!
Строчка в этой таблице означает, как отмечалось, что vi% v2, .... vn, Vn+1 суть расположенные по очереди вершины на петле с меткой г, a un+1 есть та же самая вершина, что и u1.
В дополнение к этим таблицам удобно представлять себе отдельный список соотношений между вершинами vt, хотя вся информация и содержится на самом деле в таблицах. Особо для каждой строчки V1, v2, .. .Vn+1, как выше, мы выпишем соотношения
V1Vi = V2, V^y2 = V3, ...,Un-^n-J=Pn, vny„ = v„+1,
а также соотношение un+i = ^1. Кроме того, вместе с соотношением vtyj = vk мы фиксируем также соотношение vkyj1 = vl; далее, если дано равенство V1 = Vj, то вместе с vtyk = V1 запишем Vjyk = vt, вместе с vlyh=--vi запишем vty,, = Vj, а вместе с vt = vh запишем
230 Гл. ///. Геометрические методы
v. = vk. Практичнее заменить вхождения vt их индексами і = 2, ... .
Алгоритм начинается с записи первой строки 1, 2, . . ., п, в первую таблицу, где га — длина первого г QR. Вся извлекаема отсюда информация записана, как указано выше. С этого момент' происходит следующее. Допустим, что некоторый номер ki появля ется в таблицах, но не в каждой таблице начинает некоторую стр ку. Выберем первый такой номер ku и пусть r=yu . . . уп— первс такое слово г QR, что kx не начинает строки в таблице для г, равн как и любой k[, для которого записано равенство ki=k[. Стави на первое место в новой строке таблицы для г. Если уже записан равенство kxyi=ki для некоторого минимального k2, то ставим k на второе место в строке. Продолжая таким образом, мы, возможно закончим строку, поставив некоторый kn+1 на последнее место; этом случае запишем равенство ki=kn+1 вместе с его следствиями-как указано выше. В противном случае мы придем к некотором kh на /і-м месте, 1^/г^га, такому, что не зарегистрировано равен ства khyh=kj. Тогда завершим строчку, записав ее в виде It1, k2, . . . . ., kh, . . . т, ki, где /, /+1, . . ., т суть первые числа.
Предыдущая << 1 .. 97 98 99 100 101 102 < 103 > 104 105 106 107 108 109 .. 202 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed