Содержание
Введение 3
1 Вполне регулярные графы с //< < к — 2Ь\ + 3 16
1.1 Предварительные результаты.....................................16
1.2 Доказа гельство теоремы 1......................................19
1.3 Доказательство предложения.....................................20
1.4 Доказательство теоремы 2 и следствия ..........................26
2 Вполне регулярные графы с Ь\ — 6 32
2.1 Предварительные результаты.....................................32
2.2 Реберно регулярные графы больших степеней с Ьі = б.............36
2.3 Графы с Ьі = 6. /і-подграфы большие или коклпковые.............39
2.4 Графы с Ьі — 6, р-подграфы малые, по пс все коклпковые ... 50
2.5 Вполне регулярные графы с к = 10, Л — 3........................56
3 Автоморфизмы сильно регулярного графа с параметрами (75,32,10,16)
3.1 Предварительные результаты.....................................63
3.2 Автоморфизмы графа с параметрами (75,32,10,16) 67
3.3 Автоморфизмы точечного графа частичной геометрии рС2(4, 7) 76
2
Введение
В связи с завершенном классификации конечных простых групп возникла задача единого представления конечных простых групп. Перспективным направлением является поиск такого класса конечных геометрий, что каждая конечная простая группа действует флаг-транзитивно на некоторой геометрии и вес геометрии этого класса допускают классификацию (|10|-|13|, [29|, |2S|). Например, класс билдпнгов Титеа характеризует группы лиева типа (см. |32]). Позднее в этом направлении возникли задачи, не связанные е групповым действием, в частности, такой является задача классификации дистанционно регулярных графов (см. (10))-
Пусть G — транзитивная группа подстановок на множестве Q. Если стабилизатор Gj, точки р є £2, имеет г орбит на S2, то говорят, что G имеет подстановочный ранг г (является группой подстановок ранга г). Пусть г = 3 и соответствующие три орбиты — это {р}, Д(р), Г(р). Тогда но группе G удастся построить сильно регулярный граф Г, множество вершин которого Q и две вершины р, q смежны в Г, если q Є l’(p) (см- [17|V
Д. Хигман (|17|-|23|) развил теорию групп ранга 3. Эти группы являются группами автоморфизмов сильно регулярных графов, причем они действуют транзитивно как на множествах вершин и ребер, так п на множестве нар различных несмежных вершин. Такие графы являются дистанционно транзитивными графами диаметра 2.
В настоящее время при исследовании графов вовлекаются симметрии вес более общего вида. Сначала это были условия дистанционной транзитивности и дистанционной регулярности графов, а. затем и более общие условия комбинаторной симметричности. Оказалось, что в некоторых случаях комбинаторная симметричность графа влечет его дистанционную транзитивность. Первые результаты о комбинаторно симметричных графах были получе-
3
иы в пятидесятых годах. Пусть Ь(Кп) — реберный граф полного графа Кп на и вершинах пли в других обозначениях треугольный граф Т(п). Этот граф является сильно регулярным графом с параметрами (("),2(п — 2),п — 2,4).
В работах 1959-60 годов Л. Чанг (|16|) и А. Хоффман ([24|, |25|) независимо показали, что треугольный граф Т(п) определяется однозначно своими параметрами для всех п, за исключением п — 8. Для случая п. = 8 было показано, что кроме треугольного графа. Т(8). такие же параметры имеют только три графа, которые были найдены Л. Чангом в 1949 году (см.|15|).
Реберный граф Т;(К1ПуП) полного многодольного графа Кт>п является ко-реберно реіулярнмм графом с параметрами (гпп. т -г п - 2,2). Граф 1\тчп называют гп х п решеткой. При т = п решетчатый граф является сильно регулярным графом с параметрами (/г,2п — 2, п — 2.2). С. Шрикхаиде в [311 показал, что граф, имеющий параметры п х п решетки является либо решеткой, либо графом Шрикхаиде (п = 4).
Результаты Л. Чанга и С. Шрикхаиде были объединены Дж. Зейделем (|30|), который определил все сильно регулярные графы с наименьшим собственным значением —2. Дж. Зейдель показал, что кроме треугольных графов Т(п) и решетчатых п х п-графов, сильно регулярными графами, которые имеют наименьшее собственное значение —2. являются только графы Кпх2> графы Петерсена, Шрикхаиде, Клсбша, Шлефли и три графа Чанга.
Для изучения ребс])но регулярных графов полезным оказался метод хороших пар и его обобщения.
Рассматриваются неориентированные графы без петель и кратных ребер. Если а, Ь - вершины графа Г, то через д.(а, Ь) обозначается расстояние между а и 6, а через Г,(а) - подграф графа Г, индуцированный множеством вершин, которые находятся на расстоянии г в Г от вершины а.
Подграф Г] (а) называется окрестностью вершины, а н обозначается через [а]. Окрестность вершины называется ..шкальным подграфом. Через а1
4
обозначается подграф, являющийся шаром радиуса 1 с центром а.
Граф Iі называется регулярны и графом степени к. если [а] содержит ючно к вершин для любой вершины а из Г.
Граф Г называется реберно регулярным графом с параметрами (у, к, А), если Г содержит у вершин, является регулярным степени к. и каждое ребро из Г лежит в Л треугольниках.
Граф 1 называется вполне регулярным графом с параметрами (г, к. А, /і), если Г реберно регулярен с соответствующими параметрами и подграф [«]П[6] содержит (і вершин в случае сі(а,Ь) — 2. Вполне регулярный граф диаметра 2 называется сильно регулярным графом.
Число вершин в [а] П [Ь] обозначим через Л(а, Ь), если б{а,Ь) = 1, а соответствующий подграф назовем X-подграфа и.
Если д(а.Ь) = 2, то число вершин в [а] П [Ь] обозначим через /і(а,Ь), а соответствующий подграф назовем р-подграфом.
Если вершины и, ю находятся на расстоянии г в Г, то через Ь,(и, го) (через Сі(и,го)) обозначим число вершин в пересечении 1'1+1(м)
(Г;_!(г/)) с Г(ш). Заметим, что в реберно регулярном графе число Ьі(и,и>) не зависит от выбора смежных вершин н.ьи и обозначается через /ц.Граф Г диаметра (і называется дистанционно регулярны м с массивом пересечений {Ьо, &ь • • • 5 сі, с(і}, если значения Ьфи. га) и о (и, ги) по завися г от
выбора вершин и,гг на расстоянии і в Г для любого і = 0,
Пусть Т — некоторый класс графов. Граф Г назовем локально Т графом, если [а] лежит в Т для любой вершины а графа Г. Если при этом класс Т состоит из графов, изоморфных некоторому графу Д, то граф Г назовем локально А-графом.
Пусть Г - реберно регулярный граф с параметрами (г\ /с, Л) и Ь\ = к—Л—1. Пара вершин и, ш называется (почти) хорошей, если <1(и,т) = 2 и ц(щю) равно к — 2Ь] 4- 1 (равно к — 2Ь\ + 2). Тройка вершин (м, ш, с) называется
5
(почти) хорошей, если ш. г € Г2(1*) и /і(гг. го) + //(?/, 2) не больше 2к — 4Ь\ Ч 3 (равно 2к — 46| Ч- 4).
Если fi(u,iL1) — к — 2Ь\ Ч- 1, то подграф [и] П [ге] является клнкоП и [d] С гг U wA для любой вершимы d Є [гг] П [гу].
Если Г содержит хорошую тройку то подграф [г/,] П [?/;] П [г] со-
держит не более одной вершины.
Аналогичный результат для почти хороших троек был получен A.A. Мах-новым и его учениками:
Пусть Г — связный реберно регулярный граф с параметрами (v. к. А), к = 3&14-7 и 7 > —2. Если (гг, н», z) — почти хорошая тройка и А = [г*]П[ггг]П[г] — непустой граф, то вершины w. z смежны н выполняется одно из следующих утверждений:
(1) |Д|<2і.7<-1;
(2) подграф А является 3-кликой. Ь\ — б, к = 10 и г; = 31;
(3) подграф А является 3-кликой, Ь\ = 3 и Г — граф Клсбша;
(4) подграф А является 4-клнкой, /д = 5 и Г - граф Шлсфлн.
С помощью этого результата были получены новые верхние границы для числа вершин графов с к > 3Ь\ — 2. Теория хороших пар используется в диссертации при изучении графов с // < к — 2Ь\ + 3 и графов с Ь\ — 6.
Целью диссертации является решение следующих задач:
1) изучить вполне регулярные графы с /г < к — 2Ь[ Ч- 3;
2) изучить вполне регулярные графы с Ь\ = 0;
3) найти возможные автоморфизмы сильно регулярного графа с параметрами (75,32,10,16).
Основными методами исследования являются методы теории конечных групп, теоретико-графовые методы и методы локального анализа комбинаторно симметричных графов.
G
- Київ+380960830922