Плоские графы Кэли тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

i

,-J

7 .'/ :

v, '

омский государственный университет

На правах рукописи

Беленкова Жанна Тадеушевна

ПЛОСКИЕ ГРАФЫ КЭЛИ

01.01.06 — математическая логика, алгебра и теория чисел

диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель: доктор физико-математических наук, профессор В.А. Романьков

омск 1998

Оглавление

Введение 4 Глава 1.

замощение гшоскосш правильными треугольниками

1. Группы с тремя порождающими 10

1.1. Первый способ распределения 10

1.2. Второй способ распределения 11

1.3. Третий способ распределения 11

1.4. Четвертый способ распределения 12

1.5. Пятый способ распределения 12

2. Группы с четырьмя порождающими 13

2.1. Первый способ распределения 13

2.2. Второй способ распределения 14

2.3. Третий способ распределения 14

2.4. Четвертый способ распределения 15

2.5. Пятый способ распределения 15

2.6. Шестой способ распределения 16

2.7. Седьмой способ распределения 16

2.8. Восьмой способ распределения 16

2.9. Девятый способ распределения 17

3. Группы с пятью порождающими 18 3.1 .Первый способ распределения 18 3.2.Второй способ распределения 18 3.3 .Третий способ распределения 19

4. Группы с шестью порождающими 19

ЗАМОЩЕНИЕ ПЛОСКОСТИ КВАДРАТАМИ

1. Группы с двумя порождающими 21

1.1. а и ал лежат рядом 21

1.2. а и Ь лежат рядом 24

2. Группы с тремя порождающими 27

2.1. Ребра с и с1 лежат под прямым углом друг к другу 27

2.2. с и с'1 — параллельные ребра 29

3. Группы с четырьмя порождающими 32

ЗАМОЩЕНИЕ ПЛОСКОСТИ ШЕСТИУГОЛЬНИКАМИ

1. Группа с двумя порождающими 40

2. Группа с тремя порождающими

44

СРАВНЕНИЕ С КРИСТАЛЛОГРАФИЧЕСКИМИ ГРУППАМИ 48 Глава 2

ПЛОСКИЕ ГРАФЫ КЭЛИ КОНЕЧНЫХ ГРУПП

1. Подготовительные леммы 50

2. Основные результаты 52

3. Примеры и приложения 55

Глава 3

ВСЕ ПЛОСКИЕ ГРАФЫ КЭЛИ ГРУППЫ £4

1. 2-порожденный случай 58

2. 3-порожденый случай 63

3. Все минимальные порождающие множества 66

4. Плоские графы группы 84 в случае четырех и более порождающих 68

Приложения 70

Литература 100

Введение

Понятие группы впервые возникло в форме группы преобразований и в этой же форме чаще всего встречается в математике или математической физике.

Преобразованием множества X называется взаимно-однозначное отображение /• Х—>Х этого множества на себя. Совокупность 8утт(Х) всех преобразований множества X совместно с операцией композиции образует полную группу преобразований множества X или группу подстановок на множестве X. Любая подгруппа (7 группы Бутт(Х) называется группой преобразований множества X.

Если на множестве X определена геометрическая, топологическая или какая-либо иная структура, то выделяют группу преобразований X, сохраняющих эту структуру. Например, преобразования, сохраняющие расстояние р(х,у) между точками евклидова пространства, то есть такие преобразования /, что р([(х),/(у))= р(х,у), образуют группу движений. Если все они фиксируют одну выделенную точку, то мы имеем дело с группой ортогональных преобразований.

Группа тех или иных преобразований, сохраняющих некоторый объект, интерпретируется, как совокупность его симметрий и называется группой симметрий. Например, группа симметрий плоского узора состоит из всех движений плоскости, переводящих его в себя; группа симметрий геометрической фигуры состоит из всех движений пространства, переводящих эту фигуру на себя и т.п.

Большой степенью симметрии обладают кристаллы, и поэтому группа симметрий кристалла является его важной характеристикой. Здесь под симметрией понимается перемещение пространства, сохраняющее расположение атомов кристалла и все связи между ними, перемещая каждый атом в атом того же элемента.

В настоящее время выделилось целое направление исследований, известное как геометрическая теория групп. Оно включает изучение групп, связанных с геометрическими и топологическими объектами (фундаментальных, групп классов преобразований и т.п.), а также изучение абстрактных групп геометрическими методами. Важное значение, например, имеют группы, действующие на деревьях. Смотри по этому поводу [1], [2], [3], [4], [5].

Естественным объектом, связанным с группой, который можно наделить структурой метрического пространства, является ее граф Кэли. Мы рассматриваем случай, когда группа конечно порождена.

Пусть О — группа с заданным конечным множеством порождающих элементов X. Через Г=Г(0,Х) обозначим граф Кэли группы О относительно X. Граф Г состоит из множества вершин (? и имеет одно геометрическое ребро для каждой тройки где ^'еС,

хеХ, g-gx. Таким образом, из каждой вершины графа выходит одинаковое количество ребер, равное числу элементов множества порождающих и обратных к ним.

Граф Г является связным метрическим пространством, в котором каждое ребро считается изометричным единичному отрезку, а расстояние между точками определяется как длина геодезической между ними. Метрика на вершинах графа Г соответствует словарной метрике группы Сг в алфавите X, расстояние между элементами g, / определяется, как длина кратчайшей записи элемента ^ л как группового слова в алфавите X.

Говорим, что группа (? допускает плоский граф Кэли, если для некоторого множествах Г=Г(С,Х) топологически вложим в плоскость. Граф Г в этом случае назовем плоским. Заметим, что данное свойство не является инвариантом группы С, а существенно зависит от выбора X

В данной работе всюду предполагается и поэтому специально не оговаривается, что множества порождающих элементов не содержат 1 и состоят из различных элементов. Если элемент л: еХ имеет порядок два, то между вершинами g, gx проводится одно геометрическое ребро, а не два, что не меняет плоскостности графа.

Группа О действует на графе Кэли Г изометриями по следующему правилу: элементу /еС соответствует преобразование, переводящее произвольную вершину geG в вершину соответственно, ребро

(§>х>§) переходит в ребро Говорят, что О действует на Г

левыми сдвигами. Данное действие транзитивно на вершинах: вершина g переходит в вершину к при действии элемента к^1. Однако не любая изометрия графа Г является левым сдвигом. Чтобы пояснить это, введем понятие раскрашенного графа. Граф называется раскрашенным, если любому его ребру сопоставлен определенный цвет. Например, граф Кэли естественно раскрашен, роль цвета в данном случае играет соответствующий ребру элемент порождающего множества. Для раскрашенного графа допускаются только те изометрии, которые переводят ребра в ребра того же цвета. Более точно следует считать, что каждое раскрашенное ребро имеет начальную и конечную вершины, которые при преобразованиях также должны сохраняться. В этом смысле левый сдвиг является преобразованием нужного вида.

Зададимся вопросом: что необходимо для того, чтобы раскрашенный граф можно было представить как граф Кэли некоторой группы.

Ясно, что граф должен быть связен. Каждая из его вершин должна быть начальной (соответственно, конечной) вершиной в точности одного ребра любого из цветов. В частности, каждая вершина должна быть смежной с одним и тем же числом ребер, скажем, п ребер.

Любому пути Р на графе соответствует окраска о(Р)=К1<1)К2{2\..Кпф), где </)=±1, £(г)=1, если путь Р проходит по ребру с окраской К[ от начальной вершины к конечной; £{})--1, если, наоборот. Если путь Р замкнут, то есть его начальная вершина (начальная вершина первого ребра в Р) совпадает с его конечной вершиной (конечной вершиной последнего ребра в Р), и q некоторый другой путь с той же окраской, то д также должен быть замкнут.

Все перечисленные условия, очевидно, необходимы для того, чтобы граф являлся графом Кэли некоторой группы. Они также достаточны для этого.

Действительно, сопоставим каждому цвету К^ порождающий элемент некоторой группы. Если К^(У)К2г(1)...Кпф) цвет замкнутого пути Р, то запишем соотношение к1&(1)к2г(2:>...кпЕ(п)=1. Группу О определим, как порожденную всеми элементами ки связанными соотношениями указанного вида. Если для такой группы построить граф Кэли, то он совпадет с данным раскрашенным графом. Действительно, достаточно показать, что элемент кх^к^... равен 1 тогда и только тогда, когда соответствующую окраску К\К2...К^ имеет замкнутый путь в графе. Равенство к^Ч^™ означает, что к^1)к2(2\..кпгИ

принадлежит нормальному замыканию соотношений группы (/ в свободной группе ^ с соответствующим базисом:

..с^А'^ где с, произвольные элементы гх — левые части соотношений. Сопоставим правой части выписанного равенства соответствующую окраску, которую прослеживаем, начиная из произвольной точки графа, которую можно объявить 1. Очевидно, что эта окраска соответствует замкнутому пути, тогда окраска Кх^К^—К^ соответствует замкнутому пути, значит, равенство &1Е(1)&28(2)...&п8(и):=1 записано в соотношениях.

Особенно важную роль группы симметрий и классификация при помощи этих групп имеют в кристаллографии — разделе физики, изучающем свойства кристаллических веществ (см.[6], [3], [7], [8]).

Мы отвлечемся от физики и запишем свойства группы симметрий С кристаллического вещества в пространстве X абстрактным образом (см. [6]).

1) Для всякой точки л; пространства X найдется такое число <3(х)>0, зависящее от точки х, что для всякого движения / из О, для которого /(х)^х, выполнено неравенство р(х,/(х))>с1(х).

2) Существует такой шар Б в X, что для всякой точки л; еХ найдется движение/еС, для которой /(х) &5>.

Учитывая, что группы О движений пространства, удовлетворяющие свойствам 1) и 2), впервые появились в кристаллографии как группы симметрий кристаллических веществ, их называют кристаллографическими группами.

В случае если X плоскость, мы приходим к понятию плоских кристаллографических групп. Их можно использовать при классификации повторяющихся узоров на плоскости, называемых орнаментами. Поэтому эти группы важны не только в науке, но и в искусстве (см.[3])

Всего же существует 17 различных типов плоских кристаллографических групп. Они впервые были описаны Федоровым еще в 19 веке, а ранее (в 18 веке) все 17 орнаментов были собраны в одном месте арабами в виде настенных украшений и росписей собора Альгамбры в Гренаде (Испания).

Заполнение плоскости равными между собой правильными многоугольниками, не пересекающимися друг с другом во внутренних точках, называется регулярным замощением плоскости.

С регулярным замощением связывается граф, вершины которого — вершины замощения, а ребра — ребра замощения. Такой граф назовем регулярным графом. Их может быть всего три вида: граф, состоящий из правильных треугольников, из квадратов и из шестиугольников. В силу того, что любая группа в действует на своем графе Кэли Г(0,Х) левыми умножениями, что в рассматриваемом случае приводит к изометриям плоскости, любая такая группа оказывается изоморфной некоторой плоской кристаллографической группе.

Поскольку граф Кэли определяется по группе неоднозначно: его строение зависит от выбора порождающих, большое внимание в геометрической теории групп уделяется тем свойствам графа Кэли, которые не зависят от выбора системы порождающих элементов. В связи с этим вводится понятие изопериметрической эквивалентности графов Кэли (см. [9], [10]).

Графы Кэли одной и той же группы эквивалентны в этом смысле. К сожалению, известно совсем немного свойств, сохраняющихся при изопериметрической эквивалентности графов Кэли. Отметим среди них почти абелевость и почти свободу [9], [10]. Значительная часть диссертации связана с рассмотрением более жесткого условия одинаковости графов Кэли, рассматриваемых как обычные ненаправленные графы.

Диссертация посвящена изучению свойств плоских графов Кэли. В ней описываются все возможные варианты выбора групп и их порождающих множеств, приводящие к регулярным замощениям как графам Кэли. А также приведены некоторые общие свойства плоских графов Кэли конечных групп, и как пример описаны все плоские графы Кэли группы Б4.

Диссертация состоит из введения и трех глав.

В первой главе изучаются бесконечные группы, графы Кэли которых являются регулярными замощениями плоскости.

В результате подробных рассмотрений получаем 6 групп с графом Кэли, составленным из треугольников, 16 групп с графом, составленным из квадратов, и 6 групп с графом из шестиугольников. Отметим, что в нашем описании встречаются некоторые группы, изоморфные одной и той же кристаллографической группе, взятой с разными порождающими множествами. В то же время, с точностью до изоморфизма, полученные графы исчерпывают всего 14 кристаллографических групп.

Вторая глава диссертации посвящена изучению конечных групп и таких порождающих множеств, что граф Кэли оказывается плоским. В принципе, конечные группы, допускающие плоские графы Кэли, известны (см.[11]). Однако их перечисление не дает полного описания. Одна и та же группа может обладать неизоморфными плоскими графами Кэли, неизоморфные группы, наоборот, могут допускать изоморфные плоские графы Кэли.

Основные результаты второй главы можно сформулировать в следующем виде.

Теорема 1. Граф Кэли Г=Г(А.Х) нециклической абелевой группы А относительно Х=& 2<^\<Щ=к, к>3, вложим в плоскость тогда и только тогда, когда |#|=2.

Теорема 2. Пусть в группа с множеством порождающих /},

3<<[/|=А:. Причем два к-цикла не соединены более чем одним ребром. Тогда граф Г-Г(А.Х) не вложим в плоскость.

В третьей главе описываются все плоские графы Кэли группы 34. При этом также изучается вопрос о других группах, допускающих указанные графы.

Основные Результаты опубликованы в работах [12], [13], [14].

Глава 1

ЗАМОЩЕНИЕ ПЛОСКОСТИ ПРАВИЛЬНЫМИ ТРЕУГОЛЬНИКАМИ

Каждая вершина в таком графе имеет кратность 6, то есть группы с таким графом Кэли могут иметь 3,4,5 или 6 порождающих элементов.

1. Группы с тремя порождающими

Обозначим порождающие элементы через а, Ь, с. Возможны пять способов распределения порождающих элементов по ребрам, выходящим из 1, при обходе по

часовой стрелке: .-1 Z. L-1

-1,

1) a,a'1,b,Ь'1,с,с'1; 2) a,b,b~l,а~1 ,с,с

3) a,b,а'1,Ь'1,с,с'1;

4) a,b,c,al,b'l,c'l\ 5) a,b,с,b~l,al,с~1

1.1. Первый способ распределения

Ребро, соединяющее а и а1 (рис. 1.1), не может быть Ъ, с, Ь'1 или с"1, потому что, иначе в первом случае из а в Ь'1 должно быть ребро а, во втором — из с в а должен быть путь а, в третьем — из Ъ'1 в а1 должен быть путь а, в четвертом случае из а в с должно быть ребро а, но это противоречит структуре графа. Значит, это ребро а. Проведя аналогичные рассуждения, приходим к

-1

Ь, а с и с'1 —

с.

выводу, что ребро, соединяющее bub

Теперь рассмотрим ребро, соединяющее а"1 и Ь. Это может быть либо с, либо с'1. Но с быть не может, так как в противном случае из а в с должно быть ребро Ъ. Значит, это ребро с'1. Получили четыре выражения:

а3 = 1, Ь3 = 1, с3 = 1, аЬс-1.

Используя их, можно построить весь граф (Приложение. Рис.1). Этот граф принадлежит группе

031 - < а, Ъ, с | а =1, Ъ =1, с =1, аЬс= 1 >.

1.2. Второй способ распределения

Рассмотрим ребро, соединяющее а и Ь (рис. 1.2). Это может быть а, Ь'1, с или с'1. Однако, а быть не может, так как иначе из а в а1 должно быть ребро Ь'1, а это невозможно. Невозможно с и с'1, так как иначе в первом случае из Ь'1 в с должно быть ребро а, а во втором случае из Ь'1 в с'1 должно быть ребро а, что противоречит структуре графа. Осталось проверить б"1.

В этом случае получаем выражение Ъ =а. По этому выражению можно построить следующие два по часовой стрелке цикла. Рассмотрим ребро, соединяющее а и с"1. Оно не может быть ни а, ни Ь, так как иначе в первом случае из а в а'1 должно быть ребро с, а во втором случае из Ъ в ал должно быть ребро с. Значит, это с. И новое выражение: с а= 1. Остальные циклы можно построить, воспользовавшись последним выражением. Найденных выражений хватает, чтобы построить весь граф (Приложение. Рис.2).

Этот граф принадлежит группе

2 2

^32 ~ < а, Ъ, с \ Ъ =а, с а= 1 >.

1.3. Третий способ распределения

Рассмотрим ребро, соединяющее а и Ъ ъ (рис.1.3.). Оно не может быть а, иначе из а в а1 должно быть ребро Ь'1. Но и Ъл также невозможно, иначе из Ь'1 в Ъ должен быть путь а1 а. Невозможны также ребра с и с'1, так как в первом случае из Ъл в с"1 должно быть ребро

Рис. 1.3

а

-1

а, а во втором, из а в с противоречит структуре графа.

Переходим к следующему случаю.

должно быть ребро Ь, что

1.4. Четвертый способ распределения

Начнем рассмотрение с ребра, соединяющего вершины а а и Ъ (рис. 1.4). Это не может быть а, так как

иначе из а'1 в а должно быть ребро Ъ. Это и не ¿Г1, так как тогда бы из Ъл в Ъ должно быть ребро а, но это невозможно. Значит, это либо с, либо с'1. Но с'1 опять невозможно, так как тогда из а'1 в с'1 должно быть ребро Ъ. Значит, это ребро с. Получили выражение

ас = Ъ.

Теперь рассмотрим ребро, соединяющее а и с"1. Это, как и выше не может быть а или с. Но Ь тоже быть не может, так как тогда из а'1 в Ъ должно быть ребро с'1. Значит, это ребро Ь'1. Ещё одно выражение:

са = Ъ.

Эти два выражения позволяют построить весь граф (Приложение. Рис.3).

Этот граф принадлежит группе

С33 = < а, Ь, с | ас—Ъ, са=Ь >

1.5. Пятый способ распределения

Определим, какое ребро соединяет а и Ъ (рис. 1.5). Это не может быть а, так как иначе из \ а'1 в а должно быть ребро Ь, а это невозможно.