Плоские графы Кэли тема диссертации и автореферата по ВАК РФ 01.01.06, кандидат физико-математических наук Беленкова, Жанна Тадеушевна

• Беленкова, Жанна Тадеушевна
• кандидат физико-математических наук
• 1998

Оглавление диссертации кандидат физико-математических наук Беленкова, Жанна Тадеушевна

Оглавление

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

44

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

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

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

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

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

Глава

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

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

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

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

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

Приложения

Литература

Введение диссертации (часть автореферата) на тему «Плоские графы Кэли»

Введение

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

Преобразованием множества 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].

Список литературы диссертационного исследования кандидат физико-математических наук Беленкова, Жанна Тадеушевна, 1998 год

Литература

1. Serre, J.-P. Arbes, amalgames et SL2. Asterisque No. 46. Societe Math, the France, 1977.

2. Serre, J.-P. Trees.Graduate Text in Math. Springer-Verlag, 1980.

3. Шафаревич И.Р. Основные понятия алгебры. (Итоги науки и техники. Современные проблемы математики. Фундаментальные направления.) Том 11. Москва: ВИНИТИ, 1986. 5-288.

4. Кроуэлл Р., Фокс. Введение в теорию узлов. Москва: Мир, 1967.

5. Масси У., Столлингс Дж. Алгебраическая топология. Введение. Москва: Мир, 1977.

6. Вейль Г. Симметрия. Москва, 1968.

7. Guggenheimer H.W. Plane Geometry and Its Groups. Holden-Day, 1967.

8. Федоров E.C. Симметрия на плоскости. Записки императорского Санкт-Петербургского минералогического общества. 1891, 28(2), 345390.

9. Gersten S.M. Dehn functions and /i-norms of finite presentation, Algorithms and Classification in Combinatorial Group Theory (G.Baumslag, C.F.Miller III, eds.), Springer-Verlag, New York - Berlin -Heidelberg, 1992.

10. Gersten S. Isoperimetric and isodiametric functions of finite presentations, preprint, University of Utah, 1991.

11. Цишанг X., Фогт Э., Колдевай Х.-Д. Поверхности и разрывные группы. Москва: Наука, 1988. 685с.

12. Беленкова Ж.Т., Романьков В.А. Регулярные графы Кэли. Сибирский мат. журнал, Депонирована в ВИНИТИ, 1997. № 802-В97, 37с. 54 рис.

13. Беленкова Ж.Т., Романьков В.А. Плоские графы Кэли конечных групп. Препринт ОмГУ, 1997. 8с

14. Беленкова Ж.Т. Все плоские графы Кэли группы 5V Препринт ОмГУ, 1997. 11с.

15.Коксетер Г.С.М., Мозер У.О.Дж. Порождающие элементы и определяющие соотношения дискретных групп. Пер. с англ./ Под ред. Мерзлякова Ю.И. - Москва: Наука. Главная редакция физико-математической литературы, 1980. 240с.

16. Зыков А.А. Теория конечных графов. Новосибирск: Наука, 1969. 543с.

17. Epstein D.B.A., Cannon J.W., Holt D.F., Levy S.V.F., Paterson M.S., Thurston W.P. Word processing in groups. Jones and Bartlett, BostonLondon, 1992.

18. Никулин В.В., Шафаревич И.Р. Геометрии и группы. Москва: Наука, 1983.239с.

19. Делоне Б.Н., Александров А.Д., Падуров H.H. Математические основы структурного анализа кристаллов. Ленинград, Москва.: ОНТИ, 1934.

20. Гильберт Д., Кон-Фоссен С. Наглядная геометрия. Москва: Гостехиздат, 1951.

21. Wieting T.W. The mathematical theory of chromatic plane ornaments. Dekker, 1982.

22. Линдон P., Шупп П. Комбинаторная теория групп, М.: Мир, 1980.

23. Магнус В., Каррас А., Солитер Д. Комбинаторная теория групп, Москва: Наука, 1974.

24. Узоры симметрии. Под редакцией Сенешаль М. и Флека Дж. Москва: Мир, 1980. 272с.