Содержание
Введение 3
1 О графах, в которых окрестности вершин являются псевдо-геометрическими графами для рС$-2(я, і) 12
1.1 Предварительные результаты...................................12
1.2 Сильно регулярный случай.....................................15
1.3 Графы диаметра 3, в которых окрестности вершин изоморфны
р£*-2($,£)...................................................22
2 Графы, в которых окрестности вершин — нсевдогеометриче-ские графы для (7ф(3,3) 25
2.1 Предварительные результаты...................................25
2.2 Локально псевдо (ЭД(3,3)-графы...............................28
3 Графы, в которых окрестности вершин — псевдогеометрические графы для СС}(3,5) 38
3.1 Предварительные результаты...................................38
3.2 Локально псевдо С5(3,5)-графы................................43
3.3 Случай /і = 20...............................................47
3.4 Случай [і = 18...............................................52
4 Автоморфизмы графа с параметрами (245,64,18,16) 59
4.1 Предварительные результаты...................................60
4.2 Автоморфизмы графа с параметрами (245.64,18,16)............. 64
4.3 Автоморфизмы малых порядков...................................79
2
Введение
Для единого представления конечных простых групп перспективным направлением является поиск такого класса конечных геометрий, что каждая конечная простая группа действует флаг-транзитивло па некоторой геометрии и все геометрии этого класса допускают классификацию [1|. Например, класс билдингов Титса характеризует группы лиева типа [15|. Позднее в этом направлении возникли задачи, не связанные с групповым действием. В частности, такой является задача классификации дистанционно регулярных графов [16].
Пусть G — транзитивная группа подстановок на множестве П. Если стабилизатор Gp точки р € Р., имеет г орбит на Q, то говорят, что G имеет подстановочный ранг г. Пусть г = 3 и соответствующие три орбиты — это {р}, Д(р), Г(р). Тогда по группе G удастся построить сильно регулярный граф Г. множество вершин которого П и две вершины р, q смежны в Г, если Ч е Г(р) [17].
Д. Хигмеи ([17]-|21]) развил теорию групп ранга 3. Эти группы являются группами автоморфизмов сильно регулярных графов, причем они действуют транзитивно как на множествах вершин и ребер, так и на множестве пар различных несмежных вершин. Такие графы являются дистанционно транзитивными графами диаметра 2.
В настоящее время при исследовании графов вовлекаются симметрии все болсс общего вида.
В работе рассматриваются неориентированные графы без нетель и кратных ребер. Если а, Ь - вершины графа Г, то через d(a, b) обозначается рас-
3
I
стояние между а и Ь, а через Г*(а) - подграф графа Г, индуцированный множеством вершин, которые находятся на расстоянии і в Г от вершины а.
Подграф Гі(а) называется окрестностью вершины а и обозначается через [а]. Через а1 обозначается подграф, являющийся шаром радиуса 1 с центром а.
Граф Г называется регулярным графом степени к, если [а] содержит точно к вершин для любой вершины а из Г.
Граф Г называется реберно регулярным графом с параметрами (щ к, А), если Г содержит г? вершин, является регулярным степени к, и каждое ребро из Г лежит в Л треугольниках.
Граф Г называется вполне регулярным, графом с параметрами (и, к, Л,/і), если Г реберно регулярен с соответствующими параметрами и подграф [а] П [Ь] содержит р вершин в случае <і(а, 6) = 2. Сильно регулярным графом с иараметралш (•?;, к, А, р) называется реберно регулярный граф с параметрами (щ/с, Л), в котором любые две несмежные вершины и, ю € Г имеют ровно /2 общих соседей.
Число вершин в [а] П [Ь] обозначим через А(а, 6), если <і(а, 6) = 1, а соответствующий подграф назовем X-подграфом.
Если д.(а,Ь) = 2, то число вершин в [а] П [Ь] обозначим через д(а, 6), а соответствующий подграф назовем р-подграфюм.
Если вершины и, їй находятся на расстоянии г в Г, то через 6;(?х, ш) (через а(и,и))) обозначим число вершин в пересечении Гі+і(гх)
(Г,_і(гх)) с Г(чл). Заметим, что в реберно регулярном графе число Ь\(ирш) не зависит от выбора смежных вершин и, ги и обозначается через бі.Граф Г диаметра сі называется дистанционно регулярным с массивом пересечений {6о, Ьи ...,Ь&-1;Сі,, ел}, если значения Ьфи, ш) и сфирш) не зависят от
4
выбора вершин u,w на расстоянии г в Г для любою г = 0,
Пусть Т — некоторый класс графов. Граф Г назовем локально J7 графом, если [а] лежит в Т для любой вершины а графа Г. Если при этом класс Т состоит из графов, изоморфных некоторому графу А, то граф Г назовем локально А-графом.
Через Kmumjmn обозначим полный многодельный граф {М1}..., Мп} с долями Mi порядка rrii. Если гп\ — ... = mn = т, то указанный граф обозначается Кпхт.
Система инцидентности с множеством точек Р и множеством прямых С называется а-частичпой геометрией порядка («,£), если каждая прямая содержит ровно 3 + 1 точек, каждая точка лежит ровно на t+ 1 прямой, любые две точки лежат не более чем на одной прямой и для любого антифлага (a, L) G (Р, £) найдется точно а прямых, проходящих через а и пересекающих L (обозначение pGa(5, t) или pGa). В случае а = 1 геометрия называется обобщенным четырехугольником и обозначается GQ(s, t). Точечный граф геометрии определяется на множестве точек Р и две точки смежны, если они лежат на прямой. Точечный граф геометрии pGn{s,t.) сильно регулярен с V = (з+ 1)(1 + st/or), k = s(t 4-1), À = s — 1 +t(cx — 1), /х = a(t + 1). Сильно регулярный граф с такими параметрами называется псевдогеометрпческим графюм для pG0(s,t) или псевдо pGa($> £)-графом.
A.A. Махневым предложена программа классификации связных вполне регулярных графов, в которых окрестности вершин изоморфны сильно регулярному графу Л с собственным значением 2. Эта программа основана ira получении границы для диаметра таких графов с помощью теоремы Смита (см. теорему 3.2.5 |16|).
Цель диссертации. Целыо данной работы является решение следующих
задач:
1. Провести редукцию классификации вполне регулярных графов, у которых окрестности вершин - ПСОВДОГСОМетрИЧССКИС графы ДЛЯ 2(5, <) к
локально псевдо G(Э(3,3)- и ОС?(3,5)-графам.
2. Изучить вполне регулярные локально псевдо ОС?(3,3) и 0(2(3,5)-графы.
3. Найти возможные автоморфизмы сильно регулярного графа с параметрами (245,64,18,16).
Методы исследования. Основными методами исследования являются методы теории конечных групп, теоретико-графовые методы и методы локальною анализа комбинаторно симметричных графов.
Научная новизна. Основные результаты, полученные в работе, являются новыми. Выделим из них следующие.
1. Получена граница для диаметра графов, у которых окрестности вершин - псевдо геометрические графы для рС?5_ 2($,£).
2. Получены возможные параметры вполне регулярных графов, у которых окрестности вершин - псевдогеометрические графы для рС?.ч_2(5, £), в случаях, когда диаметр графа равен 2,3 или 4.
3. Найдены возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярного графа Г с параметрами (245,64,18,16).
Теоретическая и практическая ценность. Работа носит теоретический характер. Результаты продолжают изучение роберно регулярных графов и их автоморфизмов. Результаты и методы диссертации могут быть использованы для изучения графов и конечных геометрий подобного типа.
Апробация работы. Основные результаты работы докладывались:
на Международной алгебраической конференции, посвященной 80-летию
0
- Київ+380960830922