Введение к работе
Актуальность темы. Для единого представления конечных простых групп перспективным направлением является поиск такого класса конечных геометрий, что каждая конечная простая группа действует флаг-транзитивно на некоторой геометрии и все геометрии этого класса допускают классификацию [12]. Например, класс билдингов Титса характеризует группы лиева типа [22]. Позднее в этом направлении возникли задачи, не связанные с групповым действием. В частности, такой является задача классификации дистанционно регулярных графов [11].
Первые результаты о комбинаторно симметричных графах были получены в пятидесятых годах XX века. Пусть L(Kn) — реберный граф полного графа Кп на п вершинах или в других обозначениях треугольный граф Т{п). Этот граф является сильно регулярным графом с параметрами (n(n —1)/2, 2(п —2),п —2, 4). В работах 1959-60 годов Л. Чанг [15] и А. Хоффман ([17], [18]) независимо показали, что треугольный граф Т{п) определяется однозначно своими параметрами для всех п, за исключением п = 8. Для случая п = 8 было показано, что кроме треугольного графа Т(8), такие же параметры имеют только три графа, которые были найдены Л. Чангом в 1949 году [14].
Реберный граф L(Km^n) полного многодольного графа КШіП является кореберно регулярным графом с параметрами (mn,m + п — 2,2). Граф L(Km^n) называют m х n-решеткой. При m = п решетчатый граф является сильно регулярным графом с параметрами (п2, 2п — 2, п — 2, 2). С. Шрикханде в [21] показал, что граф, имеющий параметры пхп решетки является либо решеткой, либо графом Шрикханде (n = 4).
Результаты Л. Чанга, С. Шрикханде и А. Хоффмана [19] были объединены Дж. Зейделем [20], который определил все сильно регулярные графы с наименьшим собственным значением —2. Дж. Зей-дель показал, что кроме треугольных графов Т{п) и решетчатых п х n-графов, сильно регулярными графами, которые имеют наименьшее собственное значение —2, являются только графы КпХ27
графы Петерсена, Шрикханде, Клебша, Шлефли и три графа Чан-га.
В работе рассматриваются неориентированные графы без петель и кратных ребер. Если а, Ъ - вершины графа Г, то через d(a, Ь) обозначается расстояние между а и 6, а через 1\(а) - подграф графа Г, индуцированный множеством вершин, которые находятся на расстоянии г в Г от вершины а.
Подграф Ті (а) называется окрестностью вершины а и обозначается через [а]. Через а1- обозначается подграф, являющийся шаром радиуса 1 с центром а.
Граф Г называется регулярным графом степени к, если [а] содержит точно к вершин для любой вершины а из Г.
Граф Г называется реберно регулярным графом с параметрами (v,k,X): если Г содержит v вершин, является регулярным степени к: и каждое ребро из Г лежит в А треугольниках.
Граф Г называется вполне регулярным графом с параметрами (г>, к, А, /і), если Г реберно регулярен с соответствующими параметрами и подграф [а] П [Ь] содержит /і вершин в случае d(a,b) = 2. Вполне регулярный граф диаметра 2 называется сильно регулярным графом.
Пусть Т — некоторый класс графов. Граф Г назовем локально Т графом, если [а] лежит в Т для любой вершины а графа Г. Если при этом класс Т состоит из графов, изоморфных некоторому графу А, то граф Г назовем локально А-графом.
Пусть Г — реберно регулярный граф с параметрами (v,k,\) и &i = к — А — 1. Пара вершин и, w называется (почти) хорошей, если d(u,w) = 2 и fi(u,w) равно к — 2bi + 1 (равно к — 2bi + 2). Тройка вершин (u,w,z) называется (почти) хорошей, если w}z Є ^(w) и fi(u, w) + fi(u, z) не больше 2k — 4&i + 3 (равно 2k — 4&i + 4).
Основанием для развития метода хороших пар стало следующее наблюдение. Пусть Г — реберно регулярный граф с параметрами (v,k,X) и &i = к — Х — 1. Если вершины u,w находятся на расстоянии 2 в Г, то выполняются следующие утверждения:
(1) степень любой вершины в /і-подграфе из Г не меньше к — 2bi\
вершина d имеет степень а в графе [и] П [w]: тогда и только тогда, когда [d] содержит точно а — (к — 2Ь\) вершин вне и1- U w^;
если /i(u,w) = k — 2b\ + l} то подграф [ii]n[it>] является кликой и [d] C^U w1- для любой вершины d Є [и] П [w];
если Г — (и1- U w^) содержит единственную вершину z, то ц(и, z) = fi(w, z).
А.А. Махнев [1] получил следующее свойство хороших троек: Пусть Г — реберно регулярный граф, содержащий хорошую тройку (u,w,z) и 5 = \[и] П [w] П [z}\. Тогда выполняются следующие утверждения:
если /і(іі, w) = /і(м, z) = к — 2b\ + 1, то 5 = 0 в случае, когда вершины w,z не смежны и 6 < 1 в случае, когда вершины w,z смежны;
если ц(и, w) + /і(м, z) = 2к — 4&i + 3, то ^ < 1.
С помощью этих результатов получается новое доказательство классификации графов Тервиллигера без 3-лап. Получение аналогичных оценок для почти хороших троек потребовало значительных усилий (см. [2] - [5]). В [6] была доказана
Теорема А. Пусть Г — связный реберно регулярный граф с параметрами (г>, к, X), к = 3&1 +7 «7^ —2. Если (u}w} z) — почти хорошая тройка и А = [и] П [w] П [z] — непустой граф, то вершины w} z смежны и выполняется одно из следующих утверждений:
|А| < 2 «7 < -1;
подграф А является 3-кликой, Ъ\ = б, к = 16 и v = 31;
подграф А является 3-кликой, Ъ\ = 3 и Г — градб Клебша;
подграф А является А-кликой, Ъ\ = 5 и Г — градб Шлефли.
С помощью теоремы А были найдены новые верхние границы для числа вершин реберно регулярных графов (в случае к > З&і Исаковой М.М., в случае & = З&і — 1 Чуксиной Н.В. и в случае ft = 3&1 — 2 Токбаевой А.А.).
Цель диссертации. Целью данной работы является решение следующих задач:
1. Найти новые верхние границы для числа вершин реберно регулярных графов с к = 3&1 — 2.
Найти возможные порядки и подграфы неподвижных точек сильно регулярного графа с параметрами (76,35,18,14).
Найти возможные автоморфизмы сильно регулярного графа с параметрами (243,66,9,21).
Методы исследования. Основными методами исследования являются методы теории конечных групп, теории характеров, теоретико-графовые методы и методы локального анализа комбинаторно симметричных графов.
Научная новизна. Основные результаты, полученные в работе, являются новыми. Выделим из них следущие.
Найдены новые верхние оценки для числа вершин реберно регулярных графов с к = 3&1 — 2.
Найдены возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярного графа с параметрами (76,35,18,14)
Определены возможные порядки элементов группы G автоморфизмов сильно регулярного графа с параметрами (243,66,9,21), в частности, установлено, что tt(G) С {2,3,5,7,11}. Доказано, что граф Г не является реберно симметричным.
Теоретическая и практическая ценность. Работа носит теоретический характер. Результаты продолжают изучение реберно регулярных графов и их автоморфизмов. Результаты и методы диссертации могут быть использованы для изучения графов и конечных геометрий подобного типа.
Апробация работы. Основные результаты работы докладывались на:
Международной алгебраической конференции, посвященной 80-летию со дня рождения А.И. Кострикина (Нальчик, 2009 г.), на 40-й и 41-й Региональных молодежных конференциях ИММ УрО РАН (Екатеринбург, 2009-2010 гг.) и на Международной школе-конференции по теории групп, посвященной 75-летию со дня рождения В.А. Белоногова (Нальчик, 2010 г.).
Результаты работы докладывались и обсуждались на алгебраических семинарах ИММ УрО РАН и Кабардино-Балкарского госуниверситета.
Публикации. Основные результаты диссертации опубликованы в работах [23]-[29]. Работы [23]-[28] выполнены в нераздельном соавторстве с А.А. Махневым.
Структура и объем работы. Работа состоит из введения, трех глав и списка цитированной литературы, содержащего 47 наименований. Объем диссертации — 91 стр.
