Введение к работе
Актуальность темы. Для единого представления конечных простых групп перспективным направлением является поиск такого класса конечных геометрий, что каждая конечная простая группа действует флаг-транзитивно на некоторой геометрии и все геометрии этого класса допускают классификацию [8]. Например, класс билдингов Титса характеризует группы лиева типа [15]. Позднее в этом направлении возникли задачи, не связанные с групповым действием. В частности, такой является задача классификации дистанционно регулярных графов [7].
Пусть G — транзитивная группа подстановок на множестве Q. Если стабилизатор Gp точки р Є Г2, имеет г орбит на Г2, то говорят, что G имеет подстановочный ранг г. Пусть г = 3 и соответствующие три орбиты — это {р}7 А(р): Т(р). Тогда по группе G удается построить сильно регулярный граф Г, множество вершин которого Q и две вершины р, q смежны в Г, если q Є Г(_р) [10].
Д. Хигман ([10] [14]) развил теорию групп ранга 3. Эти группы являются группами автоморфизмов сильно регулярных графов, причем они действуют транзитивно как на множествах вершин и ребер, так и на множестве пар различных несмежных вершин. Такие графы являются дистанционно транзитивными графами диаметра 2.
В настоящее время при исследовании графов вовлекаются симметрии все более общего вида.
В работе рассматриваются неориентированные графы без петель и кратных ребер. Если а, Ъ - вершины графа Г, то через d(a, Ь) обозначается расстояние между а и 6, а через Ti(a) - подграф графа Г, индуцированный множеством вершин, которые находятся на расстоянии г в Г от вершины а.
Подграф Ті (а) называется окрестностью вершины а и обозначается через [а]. Через а1- обозначается подграф, являющийся шаром радиуса 1 с центром а.
Граф Г называется регулярным графом степени к, если [а] содержит точно к вершин для любой вершины а из Г.
Граф Г называется реберно регулярным графом с параметрами (v,k,X): если Г содержит v вершин, является регулярным степени к: и каждое ребро из Г лежит в Л треугольниках.
Граф Г называется вполне регулярным графом с параметрами (г>, к, А, /і), если Г реберно регулярен с соответствующими параметрами и подграф [а] П [Ь] содержит /і вершин в случае d(a,b) = 2. Вполне регулярный граф диаметра 2 называется сильно регулярным графом.
Пусть Т — некоторый класс графов. Граф Г назовем локально Т графом, если [а] лежит в Т для любой вершины а графа Г. Если при этом класс Т состоит из графов, изоморфных некоторому графу А, то граф Г назовем локально А-графом.
Пусть Г — реберно регулярный граф с параметрами (v,k,\) и Ъ\ = к — А — 1. Пара вершин и, w называется (почти) хорошей, если d(u,w) = 2 и fi(u,w) равно к — 2Ъ\ + 1 (равно к — 2Ъ\ + 2). Тройка вершин (u,w,z) называется (почти) хорошей, если w,z Є Г^іі) и fi(u, w) + fi(u, z) не больше 2k — 4&i + 3 (равно 2k — 4&i + 4). А.А. Махнев [1] получил следующее свойство хороших троек: Пусть Г — реберно регулярный граф, содержащий хорошую тройку (u,w,z) и 5 = \[и] П [w] П [z}\. Тогда выполняются следующие утверждения:
если /і(іі, w) = /і(м, z) = к — 2b\ + 1, то 5 = 0 в случае, когда вершины w,z не смежны и 6 < 1 в случае, когда вершины w,z смежны;
если ц(и, w) + fi(u, z) = 2к — 4&i + 3, то 5 < 1.
С помощью этих результатов получается новое доказательство классификации графов Тервиллигера без 3-лап. Получение аналогичных оценок для почти хороших троек потребовало значительных усилий. В [2] была доказана
Теорема А. Пусть Г — связный реберно регулярный граф с параметрами (г>, к, X), к = 3&1 +7 «7^ —2. Если (u}w} z) — почти хорошая тройка и А = [и] П [w] П [z] — непустой граф, то вершины w} z смежны и выполняется одно из следующих утверждений:
(1) |А| < 2 «7 < -1;
подграф А является 3-кликой, Ъ\ = б, к = 16 и v = 31;
подграф А является 3-кликой, Ъ\ = 3 и Г — градб Клебша;
подграф А является 4-кликой, Ъ\ = 5 и Г — градб Шлефли.
С помощью теоремы А были найдены новые верхние границы для числа вершин реберно регулярных графов с к > З&і — 2.
Цель диссертации. Целью данной работы является решение следующих задач:
Найти новые верхние границы для числа вершин реберно регулярных графов с к > ЗЬ\.
Найти возможные порядки и подграфы неподвижных точек сильно регулярного графа с параметрами (64,35,18,20).
Найти возможные автоморфизмы сильно регулярного графа с параметрами (396,135,30,54) и уточнить результаты в случае, когда граф является точечным для частичной геометрии pG2(5,26).
Методы исследования. Основными методами исследования являются методы теории конечных групп, теории характеров, теоретико-графовые методы и методы локального анализа комбинаторно симметричных графов.
Научная новизна. Основные результаты, полученные в работе, являются новыми. Выделим из них следущие:
Найдены новые верхние оценки для числа вершин реберно регулярных графов с к > ЗЬ\.
Определены возможные порядки элементов группы G автоморфизмов сильно регулярного графа с параметрами (64,35,18,20), в частности, установлено, что tt(G) С {2,3,5,7}.
Найдены возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярного графа Г с параметрами (396,135, 30,54). Результаты существенно уточнены в случае, когда Г — точечный граф частичной геометрии pG2(5, 26).
Теоретическая и практическая ценность. Работа носит теоретический характер. Результаты продолжают изучение реберно регулярных графов и их автоморфизмов. Результаты и методы диссертации могут быть использованы для изучения графов и конечных
геометрий подобного типа.
Апробация работы. Основные результаты работы докладывались на:
Международной алгебраической конференции, посвященной 80-летию со дня рождения А.И. Кострикина (Нальчик, 2009 г.), на 40-й и 41-й Региональных молодежных конференциях ИММ УрО РАН (Екатеринбург, 2009-2010 гг.) и на Международной школе-конференции по теории групп, посвященной 75-летию со дня рождения В.А. Белоногова (Нальчик, 2010 г.).
Результаты работы докладывались и обсуждались на алгебраических семинарах ИММ УрО РАН и Кабардино-Балкарского госуниверситета.
Публикации. Основные результаты диссертации опубликованы в работах [16]—[22]. Работы [16] [21] выполнены в нераздельном соавторстве с А.А. Махневым.
Структура и объем работы. Работа состоит из введения, трех глав и списка цитированной литературы, содержащего 47 наименований. Объем работы — 70 стр.
