Графы Кэли групп Zd и пределы конечных вершинно-примитивных графов

• Автор: Костоусов, Кирилл Викторович
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Екатеринбург
• Количество страниц: 122 с.

Введение. Формулировки основных результатов

1 Графы Кэли групп ЪА и конечные группы целочисленных матриц

1.1 Критерий изоморфности графов Кэли групп доказательство теоремы

1.2 Связь графов Кэли групп Ъ с конечными группами целочисленных матриц: доказательство теоремы

1.3 О пределах вершинно-примитивных графов НА-типа

2 Реберно-транзитивные графы Кэли групп ІА и пределы графов, допускающих реберно-транзитивную вершинно-примитивную группу автоморфизмов ЯА-типа
2.1 Реберно-транзитивные графы Кэли группы Ъ и \т{Т'Ре^апз)4. доказательство теоремы

2.2 Реберно-транзитивные графы Кэли групп іА, с? > 2, и

1іт(ЯЯд^гашї): доказательство теоремы

3 Минимальные графы Кэли групп Ъл и пределы графов минимальной валентности для вершинно-примитивных групп НА-типа
3.1 Графы Кэли групп іА наименьшей валентности как пределы минимальных вершинно-примитивных графов НА-типа
3.2 Минимальные графы Кэли группы НА и Нт(.ЯР^): доказательство теоремы
3.3 Минимальные графы Кэли группы 1} и Нт(^7'Рял): доказательство теоремы
3.4 Графы Кэли группы 1А, соответствующие орбитам конечной группы целочисленных матриц
3.5 Алгоритмы, позволяющие находить минимальные графы Кэли групп Z
3.6 Схема нахождения минимальных графов Кэли группы ТА при d > 4
4 Минимальные графы Кэли группы Z4 и пределы графов минимальной валентности для вершинно-примитивных групп НА-типа
4.1 Подгруппы бесконечного орбитного типа в GL^Z): доказательство теоремы 7
4.2 Минимальные графы Кэли группы Z4 и Ит^Рц-д): доказательство теоремы 8
4.3 Приложение к главе
4.3.1 Построение множества групп Q
4.3.2 Группы из Q со своими порождающими
4.3.3 Свойства групп из Q
4.3.4 Дополнительные свойства групп из Q[
5 Минимальные графы Кэли группы Z5 и пределы графов минимальной валентности для вершинно-примитивных групп НА-типа
5.1 Доказательство теоремы
5.2 Приложение к главе 5: построение множества групп
6 Минимальные графы Кэли группы Z6 и пределы графов минимальной валентности для вершинно-примитивных групп НА-типа
6.1 Доказательство теоремы
6.2 Приложение к главе
6.2.1 Построение множества групп Q'6
6.2.2 Группы из Qg со своими порождающими
6.2.3 Свойства групп из Q'g
6.2.4 Дополнительные свойства групп из Q'6
Литература
Используемые обозначения

Введение. Формулировки основных результатов
Всюду ниже под графом понимается неориентированный граф без петель и кратных ребер. Множество вершин графа Г обозначается через У (Г), а множество ребер — через Е(Г). Под автоморфизмами графа Г понимаются подстановки на множестве У(Г), сохраняющие отношение смежности.
Граф называется вершинно-примитивным, если он допускает группу автоморфизмов, действующую примитивно на множестве его вершин. Класс конечных связных вершинно-примитивных графов будем обозначать через ТТ (здесь и всюду ниже под классом некоторых графов понимается множество изоморфных типов этих графов). Важный в комбинаторике и алгебре подкласс класса РТ составляют графы, допускающие вершинно-примитивную реберно-транзитивную группу автоморфизмов. Этот класс обозначается через Т'ре~^апв' Класс рре-капв^ в свою очередь, имеет важный подкласс ТТтгп, состоящий из графов минимальной валентности для конечных вершиннопримитивных групп. Связный граф Г называется графом минимальной валентности для вершинно-примитивной группы автоморфизмов (7, если Г имеет наименьшую валентность среди всех связных графов А, таких что У (А) = У(Г) и б < АиДД). Каждая примитивная группа подстановок может быть реализована как группа автоморфизмов некоторого связного вершиннопримитивного графа. При этом вершинно-примитивные графы минимальной валентности для заданной примитивной группы доставляют наиболее естественные ее реализации в качестве группы автоморфизмов графа.
Для изучения класса РТ в [5] и [8] был предложен подход, связанный с изучением предельных графов для класса ТТ. Если С — произвольный класс конечных связных вершинно-примитивных графов, то предельными для С называются бесконечные связные графы, у которых каждый шар изоморфен шару некоторого графа из С. Класс предельных для С графов обозначается через Нт(С'). Описание Ит(С') доставляет описание типичного локального строения графов из С. Вопрос о строении графов из Ипф.РР) был поставлен В.И. Трофимовым в [2, вопрос 12.89]. В силу сказанного выше, также представляет интерес изучение строения графов из Ит(Т7>е~1гаш) и Хга(Т'Ртт). Заметим, что, как

4.3.3 Свойства групп из Q
Следующие свойства групп из (Д, приведенных в предыдущем разделе, частью проверены при помощи GAP и Maple, частью же (оценка m(G) < тДС)) следуют из таблицы 1 в §4.3.1. Эти свойства применяются в §4.1 и §4.2 для доказательства теорем 7 и 8.
Свойство I4.
Ga, 154 > С4Д66;
^(^4,154) < 24.
Свойство 2л.
Свойство З4.
^4,156 > GaAдб6, где а4д
т(^4Д5б) < 24.
6*4,163 > 6*4,166!
^(Сддбз) < 24.
/ 0 1 2 1
1 -2 2 2
3 1 1 0
1 -1 -1 1
Свойство 4д.
где 64д
Свойство 64. Свойство 64.
Для {x,X2,xz,xa) 6 Q4 {0} справедливо
eiGr4,165^4,l = (®1, Х2,Х$, £4)6*4,165,
/ £l £2 £3 £4
-£2 £l + £2 £4 Ха ~ £3
£4 - £3 £2 - £4 £1 + £2 + £3 “ х4 х2
Х2 ~ £4 £3 - х4 -£2 £1 + £3 - £4 )
el6*4,165 = е1б?4дб6е2, е3, в4 Е &1G4
166а4)2
GJ& = ^2, где
/О 1 -1 о 10-11 -12 11 V 1 -1
, G2 — группа из теоремы 7.