Комбинаторно симметричные графы и их автоморфизмы

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

1 О локально (в,і) графах с сильно регулярными

д-подграфами

* 1.1 Предварительные результаты

1.2 Случай графов Мура

1.3 Случай графов Клсбша и Гевиртца

1.4 Д — граф с /х >

2 О реберно регулярных графах с Ь>і = 5

2.1 Предварительные результаты

^ 2.2 Реберно регулярные графы больших степеней с Ьі = 5

2.3 Графы с Ьі = 5 степени

* 3 Об автоморфизмах графа с (364,33,2,3)

3.1 Предварительные результаты
3.2 Характеры групп и автоморфизмы графов
3.3 Инволютивныс автоморфизмы графа с параметрами (364,33,2,3)
3.4 Автоморфизмы частичного четырехугольника Р(^(3,10,3)
4 Об автоморфизмах графа с (676,45,2,3)
9 4.1 Предварительные результаты
4.2 Характеры групп и автоморфизмы графов
** 4.3 Инволютивныс автоморфизмы графа с параметрами (676,45, 2,3)
4.4 Автоморфизмы частичного четырехугольника РС^(3,14,3)
Список литературы

В связи с завершением классификации конечных простых групп возникла задача единого представления конечных простых групп. Перспективным направлением является поиск такого класса конечных геометрий, что каждая конечная простая группа действует флаг-транзитивпо на некоторой геометрии и все геометрии этого класса допускают классификацию ([11]-[15], [32], [34]). Например, класс билдингов Титса характеризует группы лиева типа [37]. Позднее в этом направлении возникли задачи, не связанные с групповым действием, в частности, такой является задача классификации дистанционно регулярных графов [11].
Пусть С — транзитивная группа подстановок на множестве П. Если стабилизатор Ор точки р Е Г2, имеет г орбит на О., то говорят, что С имеет подстановочный ранг г (является группой подстановок ранга г). Пусть г = 3 и соответствующие три орбиты — это {р}, Д(р), Г(р). Тогда но группе С удается построить сильно регулярный граф Г, множество вершин которого — и две вершины р,д смежны в Г, если д Е Г(р) [22].
Д. Хигмап ([22]—[28]) развил теорию групп ранга 3. Эти группы являются группами автоморфизмов сильно регулярных графов, причем они действуют транзитивно как на множествах вершин и ребер, так и на множестве пар различных несмежных вершин. Такие графы являются дистанционно транзитивными графами диаметра 2.
В настоящее время при исследовании графов вовлекаются симметрии все более общего вида. Сначала это были условия дистанционной транзитивности и дистанционной регулярности графов, а затем и более общие условия комбинаторной симметричности. Оказалось, что в некоторых случаях комбинаторная симметрия графа влечет его дистанционную транзитивность.
Первые результаты о комбинаторно симметричных графах были получены п пятидесятых годах. Пусть Ь{Кп) — реберный граф полного графа Кп на п вершинах или н других обозначениях треугольный граф Т(п). Этот граф является сильно регулярным графом с параметрами ((2); 2(п — 2),п — 2,4). В работах 1959-60 годов Л. Чанг [19] и А. Хоффман ([29], [30]) независимо ^ показали, что треугольный граф Т{п) определяется однозначно своими нара-
♦ метрами для всех п, за исключением п = 8. Для случая п — 8 было показано,
что кроме треугольного графа Т(8), такие же параметры имеют только три графа, которые были найдены Л. Чангом в 1949 году [18].
Реберный граф Ь(К1п>п) полного многодольного графа Кт<п является ко-реберно регулярным графом с параметрами (тп,т + п — 2,2). Граф КтіП называют т х п решеткой. При т = п решетчатый граф является сильно регулярным графом с параметрами (п2,2п — 2,п — 2,2). С. Шрикхаиде ф її [ЗС] показал, что граф, имеющий параметры п х п решетки является либо
решеткой, либо графом Шрикхаиде (п = 4).
„ Результаты Л. Чанга, С. Шрикхаиде и А. Хоффмана [31] были объединены Дж. Зейделем [35], который определил все сильно регулярные графы с наименьшим собственным значением —2. Дж. Зейдель показал, что кроме треугольных графов Т(п) и решетчатых п X п-графов, сильно регулярными графами, которые имеют наименьшее собственное значение —2, являются только графы Кпх2, графы Петерсена, Шрикхаиде, Клебша, Шлсфли и три графа Чанга.
® В работе рассматриваются неориентированные графы без петель и кратных ребер. Если а, Ь - вершины графа Г, то через с1(а, Ъ) обозначается рас-ь стояние между а и Ь, а через Гг(а) - подграф графа Г, индуцированный
множеством вершин, которые находятся на расстоянии г в Г от вершины а.
Подграф Г і (а) называется окрестностью вершины а и обозначается через [а]. Через а-1 обозначается подграф, являющийся шаром радиуса 1 с центром а.

7?о — отношение равенства, Я — отношение смежности и Г, Я? — отношение смежности и дополнительном графе Г. Если Р и — первая и вторая матрицы собственных значений схемы, то
/ 1 1 1 '
к Г
V — к — 1 —г — 1 —я
= С}Р = и/. Здесь V — число вершин, А;, г, я — собственные значения графа Г кратностей 1 ,/,д соответственно (указанные кратности образуют первый столбец матрицы <3).
Подстановочное представление группы С = АиЬ{Г) на вершинах графа Г обычным образом дает матричное представление ф группы С в GL(г;, С). Пространство С1’ является ортогональной прямой суммой собственных С-инвариаптных подпространств Иф ® матрицы смежности графа Г.
Пусть Хг ~ характер представления фщ. Тогда для любого д £ С получим
Хі(д) = V 1Ё <3ім(д), і=о
где аДд) — число точек х из X таких, что (х,хп) Є Я3-. Заметим, что значения характеров являются целыми алгебраическими числами, правая часть равенства для Хі(о) ~ число рациональное, поэтому Хг(д) должно быть целым.
До конца работы будем предполагать, что Г — сильно регулярный граф с параметрами (364,33,2,3) и Є = АиЦГ). Тогда Г имеет собственные значения 33, 5, -6 кратностей 1, 195, 168 и

33 -6 5 330 5

168 -336/11 28/11
195 325/11 -39/11
Поэтому значение характера, полученного при проектировании на подпространство размерности 168 равно
Хі(д) = (тао(д) - (336аг{д) - 28а2(