Содержание
Введение 3
1 Реберно регулярные графы с к > 3Ь\ 15
1.1 Пі зедварительные результаты....................................16
1.2 Графы с хорошими парами.........................................18
1.3 Графы без хороших пар...........................................21
2 Автоморфизмы графа с параметрами (64,35,18,20) 24
2.1 Предварительные результаты......................................25
2.2 Автоморфизмы графа с параметрами (64,35,18,20)............ 29
3 Автоморфизмы графа с параметрами (396,135,30,54) 40
3.1 Предварительные результаты......................................42
3.2 Автоморфизмы графа с параметрами (396,135,30,54) 45
3.3 Автоморфизмы малых порядков.....................................55
3.4 Автоморфизмы мастичной геометрии 26).................59
2
Введение
Для единого представления конечных простых групп перспективным направлением является поиск такого класса конечных геометрий, что каждая конечная простая группа действует флаг-транзитивно на некоторой геометрии и все геометрии этого класса допускают классификацию ([20]-[24], [37], [21]). Например, класс билдингов Титса характеризует группы лиева типа [38]. Позднее в этом направлении возникли задачи, не связанные с групповым действием. В частности, такой является задача классификации дистанционно регулярных графов [20].
Пусть С — транзитивная группа подстановок па множестве П. Если стабилизатор Ср точки р 6 П, имеет г орбит на П, то говорят, что С имеет подстановочный ранг г. Пусть г = 3 и соответствующие три орбиты — это {р}, Д(р), Г(р). Тогда по группе С удается построить сильно регулярный граф Г, множество вершин которого П и две вершины р, д смежны в Г, если д в Г(р) [29].
Д. Хпгман ([29]—[35]) развил теорию групп ранга 3. Эти группы являются группами автоморфизмов сильно регулярных графов, причем они действуют транзи гивно как на множествах вершин и ребер, так и на множестве пар различных несмежных вершин. Такие графы являются дистанционно транзитивными графами диаметра 2.
В настоящее время при исследовании графов вовлекаются симметрии все более общего вида.
В работе рассматриваются неориентированные графы без петель и кратных ребер. Если а, Ь - вершины графа Г, то через с1(а, 6) обозначается рас-
3
стояние между а и Ь, а через Г,(а) - подграф графа Г, индуцированный множеством вершин, которые находятся на расстоянии г в Г от вершины а.
Подграф Г і (а) называется окрестностью вершины а и обозначается через [а]. Через а-1 обозначается подграф, являющийся шаром радиуса 1 с центром а.
Граф Г называется регулярным графом степени к, если [а] содержит точно к вершин для любой вершины а из Г.
Граф Г называется реберно регулярным графом с перам,стражи (у, к. А), если Г содержит и вершин, является регулярным степени к, и каждое ребро из Г лежит в Л треугольниках.
Граф Г называется вполне регулярным г]яифом с параметрами (?;. к. А. р.), если Г реберно регулярен с соответствующим и параметрами и подграф [а]П[6] содержит /і вершин в случае б(а. Ь) = 2. Вполне регулярный граф диаметра 2 называется сильно регулярным графом.
Число вершин в [а] П [Ь\ обозначим через Л(а, 6), если б(а,Ь) = 1, а соответствующий подграф назовем А-подграфом,
Если с/(а, 6) = 2, то число вершин в [а] П [Ь] обозначим через /х(а, 6), а соответствующий подграф назовем р-подграфом.
Если вершины и, и) находятся на расстоянии г в Г, то через Ьі(и.ги) (через гг)) обозначим число вершин в пересечении Г*+і(д)
(IV і (а)) с Г(іу). Заметим, что в реберно регулярном графе число Ь](ирш) не зависит от выбора смежных вершин и,ги и равно &і = к — А — І.Граф Г диаметра б называется дистанционно регулярным с массивом, пересечений {/?о,Ь[у..., Ь(і-і; сі,..., сг/}, если значения />,-(?д ш) и с,-(и, ю) не зависят от выбора вершин и, и) на расстоянии і в Г для любого г = 0, ...,б.
Пусть Т — некоторый класс графов. Граф Г назовем локально Т графом,
4
если [а] лежит в Т для любой вершины а графа Г. Если при этом класс Т состоит из графов, изоморфных некоторому графу Д, то граф Г назовем локалыю Д-графом.
Пусть Г — реберно регулярный граф с параметрами (v. к. А) и Ь\ = к—А—1. Пара вершин гг, ш называется (почти) хорошей, если <2(гг,г//) = 2 и /г(гг, w) равно к — 26] + 1 (равно /с — 26j -4- 2). Тройка вершин (гг, г/;, z) называется (почти) хорошей, если w,z Є Г2(гг) и /г (гг, ге) + р(гг, гг) не больше 2/с - 461 + 3 (равно 2А: — 4&і + 4).
Основанием для развития метода хороших нар стало следующее наблюдение. Пусть Г — реберно регулярный граф с параметрами (?;, /с, А) и 6і = к — А — 1. Если вершины гг, га находятся на расстоянии 2 в Г, то выполняются следующие утверждения:
(1) степень любой вершины в /г-подграфе из Г не меньше к — 2/ц;
(2) вершина d имеет степень а в графе [гг] П [г/;], тогда и только тогда, когда [d] содержит точно а — (к — 2Ь\) вершин вне uL U v)1 ;
(3) если p(u,w) = к — 2Ьі + 1, то подграф [гг] П [г/;] является кликой п [г/] С и1 U VIх для любой вершины d Є [гг] П [гг;];
(4) если Г — (гг1 Uw1) содержит единственную вершину гг, то p(u,z) = p(w, z).
A.A. Махнсв [1| получил следующее свойство хороших троек:
Пусть Г — регберно регулярный граф, содержащий хорошую тройку (гг, w, z) и 6 — |[гг] П [w] П [г]|. Тогда выполняются следующие утверждения:
(1) если p{u,w) = д(гг, z) = к — 2b\ 4- 1, то 5 = 0 в случае, когда вершины w, z не смежны и6<1 в случае, когда вершины гг, г: смежны;
(2) если p(u.w) -I- p(u.w) = 2/с — 4Ь\ + 3, то 6 < 1.
С помощью этих результатов получается новое доказательство классифи-
кации графов Тервиллигера без 3-лап. Получение аналогичных оценок для почти хороших троек потребовало значительных усилий (см. (2| - [5|). В [6]) была доказана
Теорема А. Пусть Г — связный реберно регулярный граф с параметрами (у,к,\), к — 361 + 7 и 7 > —2. Если (и, ги, г) — почти хорошая тройка и А = [и] П [и>] П [г] непустой граф, то вершины го, г смежны и выполняется одно из следующих утверждений:
(1) |Д| < 2 и 7 < — 1;
(2) подграф) А является 3-кликой, Ь\ = 0. к — 16 и V — 31;
(3) подграф А является 3-кликой, Ь\ = 3 и Г — граф Клебша;
(4) подграф А является 4-кликой, Ь\ = 5 и Г — граф Шлефли.
С помощью теоремы А были найдены новые верхние границы для числа
вершим реберно регулярных графов с к > 36] — 2.
Цель диссертации. Цслыо данной работы является решение следующих задач:
1. Найти новые верхние границы для числа вершин реберно регулярных графов с к > ЗЬ\.
2. Найти возможные порядки и подграфы неподвижных точек сильно регулярного графа с параметрами (64,35,18,20).
3. Найти возможные автоморфизмы сильно регулярного графа с пара,метрами (396,135,30,54) и уточнить результаты в случае, когда, граф является точечным для частичной геометрии рЄіі5,26).
Методы исследования. Основными методами исследования являются методы теории конечных групп, теории характеров, теоретике-графовые методы и методы локального анализа комбинаторно симметричных графов.
6
- Київ+380960830922