Введение к работе
Актуальность темы. Для единого представления конечных простых групп перспективным направлением является поиск такого класса конечных геометрий, что каждая конечная простая группа действует флаг-транзитивно на некоторой геометрии и все геометрии этого класса допускают классификацию [4]. Например, класс билдингов Титса характеризует группы лиева типа [5]. Позднее в этом направлении возникли задачи, не связанные с групповым действием. В частности, такой является задача классификации дистанционно регулярных графов [12].
Пусть G — транзитивная группа подстановок на множестве Q. Если стабилизатор Ga точки а Є Г2, имеет г орбит на Г2, то говорят, что G имеет подстановочный ранг г. Пусть г = 3 и соответствующие три орбиты — это {а}, А(а), Г(а). Если |А(а)| ф |Г(а)|, то по группе G можно построить сильно регулярный граф Г, множество вершин которого Q и две вершины а, Ъ смежны в Г, если Ъ Є Г(а) [7]. Д. Хигман ([7]—[11]) развил теорию групп ранга 3. Такие графы являются дистанционно транзитивными графами диаметра 2.
В настоящее время при исследовании графов вовлекаются симметрии все более общего вида.
В работе рассматриваются неориентированные графы без петель и кратных ребер. Если а, Ъ - вершины графа Г, то через d(a, Ь) обозначается расстояние между а и 6, а через Г^(а) - подграф графа Г, индуцированный множеством вершин, которые находятся на расстоянии г в Г от вершины а. Подграф Т\(а) называется окрестностью вершины а и обозначается через [а]. Через а1- обозначается подграф, являющийся шаром радиуса 1 с центром а.
Граф Г называется регулярным графом степени к, если [а] содержит точно к вершин для любой вершины а из Г. Граф Г называется реберно регулярным графом с параметрами (г>, к, А), если Г содержит v вершин, является регулярным степени к: и каждое ребро графа Г лежит точно в А треугольниках. Граф Г называется вполне регулярным графом с параметрами (г>, к, А, /і), если Г реберно регулярен с соответствующими параметрами и подграф [а] П [Ь]
содержит /і вершин в случае d(a} Ъ) = 2. Сильно регулярным графом с параметрами (г>, к, А, /і) называется реберно регулярный граф с параметрами (-и, к, А), в котором любые две несмежные вершины и,и)ЄГ имеют ровно /і общих соседей.
Число вершин в [а] П [6] обозначим через Л(а, 6), если d(a^ Ь) = 1, а соответствующий подграф назовем Х-подграфом. Если rf(a, 6) = 2, то число вершин в [а] П [Ь] обозначим через /i(a, о), а соответствующий подграф назовем ц-подграфом.
Если вершины и, w находятся на расстоянии і в Г, то через bi(u, w) (через Ci(u,w)) обозначим число вершин в пересечении подграфа Гі_|_і(гі) (Гі_і(гі)) с T(w). Заметим, что в реберно регулярном графе число bi(u,w) не зависит от выбора смежных вершин u,w и рав-но Ъ\ = к — А — 1. Граф Г диаметра d называется дистанционно регулярным с массивом пересечений {&о, &ъ , о^-ъ Сі,..., q}, если значения bi(u,w) и q(it, if) не зависят от выбора вершин w,u> на расстоянии і в Г для любого і = 0,..., <і.
Пусть JF — некоторый класс графов. Граф Г назовем локально Т графом^ если [а] лежит в Т для любой вершины а графа Г. Если при этом класс Т состоит из графов, изоморфных некоторому графу А, то граф Г назовем локально А-графом.
Через і^тоь...,ТОп обозначим полный многодольный граф {Мі,..., Мп} с долями Мі порядка rri{. Если т\ = ... = тп = т, то указанный граф обозначается Кпхт.
Система инцидентности с множеством точек Р и множеством прямых С называется а-частичной геометрией порядка (s,t), если каждая прямая содержит ровно s + 1 точек, каждая точка лежит ровно на t + 1 прямой, любые две точки лежат не более чем на одной прямой и для любого антифлага (a, L) Є (Р, С) найдется точно а прямых, проходящих через а и пересекающих L (обозначение pGa(s,t) или pGa). В случае а = 1 геометрия называется обобщенным четырехугольником и обозначается GQ(s,t). Точечный граф геометрии определяется на множестве точек Р и две точки смежны, если они лежат на прямой. Точечный граф геометрии pGa(s, t) сильно регулярен с v = (s+ 1)(1+ st/a), k = s(t + l), Л = s — l + t(a — 1), /і = a(t + 1). Сильно регулярный граф с такими параметрами на-
зывается псевдогеометрическим графом для pGa(s,t) или псевдо pGa(s, )-графом.
А.А. Махневым предложена программа классификации связных вполне регулярных графов, в которых окрестности вершин изоморфны сильно регулярному графу А с собственным значением 2. Эта программа основана на получении границы для диаметра таких графов с помощью теоремы Смита (см. теорему 3.2.5 [12]).
Цель диссертации. Целью данной работы является решение следующих задач (в рамках указанной ппрограммы):
1. Провести редукцию классификации вполне регулярных гра
фов, у которых окрестности вершин — псевдогеометрические гра
фы для pGs-2(s}t) к локально псевдо GQ(3,3)- и псевдо GQ(3,5)-
графам.
Изучить вполне регулярные локально псевдо GQ(3,3)- и псевдо GQ(3, 5)-графы.
Найти возможные автоморфизмы сильно регулярного графа с параметрами (245,64,18,16).
Методы исследования. Основными методами исследования являются методы теории конечных групп, теоретико-графовые методы и методы локального анализа комбинаторно симметричных графов.
Научная новизна. Основные результаты, полученные в работе, являются новыми. Выделим из них следующие.
Доказано, что диаметр графа, в котором окрестности вершин — псевдогеометрические графы для pGs-2(s,t): не больше 4.
Определены возможные параметры вполне регулярных графов, в которых окрестности вершин — псевдогеометрические графы для pGs-2{s,t).
Найдены возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярного графа Г с параметрами (245,64, 18,16).
Теоретическая и практическая ценность. Работа носит теоретический характер. Результаты продолжают изучение реберно ре-
гулярных графов и их автоморфизмов. Результаты и методы диссертации могут быть использованы для изучения графов и конечных геометрий подобного типа.
Апробация работы. Основные результаты работы докладывались на: Международной алгебраической конференции, посвященной 80-летию со дня рождения А.И. Кострикина (Нальчик, 2009 г.), на международной конференции "Мальцевские чтения" (Новосибирск, 2010 г.), на VIII международной школе-конференции по теории групп (Нальчик, 2010 г.) и на 42-й Всероссийской молодежной конференции "Современные проблемы математики "(Екатеринбург, 2011 г.). Результаты работы докладывались и обсуждались на алгебраическом семинаре ИММ УрО РАН.
Публикации. Основные результаты диссертации опубликованы в работах [13] [20]. Статьи [14], [16], [19] опубликованы в журналах из списка ВАК. Работы [13] [19] выполнены в нераздельном соавторстве с А.А. Махневым.
Структура и объем работы. Работа состоит из введения, четырех глав и списка цитированной литературы, содержащего 29 наименований. Объем диссертации — 87 стр.
