Введение к работе
В связи с завершением классификации конечных простых групп возникла задача единого представления конечных простых групп. Перспективным направлением является поиск такого класса конечных геометрий, что каждая конечная простая группа действует флаг-транзитивно на некоторой геометрии и все геометрии этого класса допускают классификацию (см. [4]-[8], [23], [22]). Например, класс билдингов Титса характеризует группы лиева типа [26]. Позднее в этом направлении возникли задачи, не связанные с групповым действием, в частности, такой является задача классификации дистанционно регулярных графов [4].
Пусть G — транзитивная группа подстановок на множестве Q. Если стабилизатор Gp в G точки р є Q имеет г орбит на Q, то говорят, что G имеет подстановочный ранг г (является группой подстановок ранга г). Пусть г = 3 и соответствующие три орбиты — это {р}, А(р) и Г(р). Тогда по группе G удается построить сильно регулярный граф Г с множеством вершин Q, и две вершины р, q смежны в Г, если q є Г(р) [12].
Д. Хигман ([12]—[18]) развил теорию групп ранга 3. Эти группы являются группами автоморфизмов сильно регулярных графов, причем они действуют транзитивно как на множествах вершин и ребер, так и на множестве пар различных несмежных вершин. Такие графы являются дистанционно транзитивными графами диаметра 2.
Граф Г диаметра d называется дистанционно транзитивным, если для любого г Є {0,...,d} и для любых его вершин u,v,x,y таких, что d(u,v) = d(x,y) = і, существует автоморфизм g графа Г такой, что (u,v)9 = (х,у). Дистанционно транзитивные графы диаметра 2 (графы ранга 3) сыграли важную роль в классификации конечных простых групп. Около половины спорадических групп были построены как группы автоморфизмов графов ранга 3 (см. [23]). В настоящее время при исследовании графов вовлекаются симметрии все более общего вида. Сначала это были условия дистанционной транзитивности и дистанционной регулярности графов, а затем и более общие условия комбинаторной симметричности.
Первые результаты о комбинаторно симметричных графах были получены в пятидесятых годах прошлого века. Пусть L(Kn) — реберный граф полного графа Кп на п вершинах, или в других обозначениях треугольный граф Т{п). Этот граф является сильно регулярным графом с параметрами ((), 2(п — 2), п — 2, 4J. В работах 1959-60 годов Л. Чанг [11] и А. Хоффман ([19], [20]) независимо показали, что треугольный граф Т(п) определяется однозначно своими параметрами для всех п, за исключением п = 8. Для случая п = 8 было показано, что, кроме треугольного графа Т(8), такие же параметры имеют только три графа, которые были найдены Л. Чангом в 1949 году [10].
Через Kmit_>mn обозначим полный гг-дольный граф с долями порядков гаї, ...,mn. Если гаї = ... = mn = га, то соответствующий граф обозначается через Кпхт. Если га > 2, то граф К\т называется т-лапой. Реберный граф L(Kmn) полного многодольного графа Кт>п является кореберно регулярным графом с параметрами (тп,т + п — 2, 2). Реберный граф для Кт>п называют га х п- решеткой. Известно, что пх п- решетка является сильно регулярным графом с параметрами (п2,2п — 2,п — 2,2). С. Шрикханде в [25] показал, что сильно регулярный граф, имеющий параметры п х п- решетки является либо п х п-решеткой, либо графом Шрикханде при п = 4.
Результаты Л. Чанга , С. Шрикханде и А. Хоффмана [21] были объединены Дж. Зей-делем [24], который определил все сильно регулярные графы с наименьшим собственным значением —2. Дж. Зейдель показал, что, кроме треугольных графов Т{п) и ггхгг-решеток, сильно регулярными графами с наименьшим собственным значением —2, являются только графы КпХ2, графы Петерсена, Шрикханде, Клебша, Шлефли и три графа Чанга.
Основные определения. В работе рассматриваются неориентированные графы без петель и кратных ребер. Если а, Ъ - вершины графа Г, то через d(a, Ъ) обозначается расстояние между а и 6, а через ГДа) - подграф графа Г, индуцированный множеством вершин, которые находятся на расстоянии г в Г от вершины а.
Подграф Гі(а) называется окрестностью вершины а и обозначается через [а]. Через а1- обозначается подграф, являющийся шаром радиуса 1 с центром а.
Граф Г называется регулярным графом степени к, если [а] содержит точно к вершин для любой вершины а из Г.
Граф Г называется реберно регулярным графом с параметрами (v, к, Л), если Г содер-
жит v вершин, является регулярным степени к и каждое ребро из Г лежит в Л треугольниках.
Граф Г называется вполне регулярным графом с параметрами (v,k,X,/j,), если Г реберно регулярен с соответствующими параметрами и подграф [а] П [Ь] содержит ц вершин в случае d(a, b) = 2. Вполне регулярный граф диаметра 2 называется сильно регулярным графом.
Если d(a,b) = 1, то число вершин в [а] П [Ь] обозначим через Х(а,Ь), а подграф [а] П [Ь] назовем Х-подграфом. Если d(a,b) = 2, то число вершин в [а] П [Ь] обозначим через /j,(a,b), а соответствующий подграф назовем ц-подграфом.
Если вершины u,w находятся на расстоянии г в Г, то через bi(u,w) (соотв. d(u,w)) обозначим число вершин в пересечении Гі+і(и) (соотв. Гг_і(и)) с Г(и>). Заметим, что в реберно регулярном графе число b\(u,w) не зависит от выбора смежных вершин u,w и обозначается через Ъ\.
Частичной геометрией pGa(s,t) называется система инцидентности, состоящая из точек и прямых, в которой каждая прямая содержит s + 1 точку, каждая точка лежит на t + 1 прямой (две прямые пересекаются не более, чем по одной точке) и для любой точки а, не лежащей на прямой L, найдется точно а прямых, проходящих через а и пересекающих L. Если а = 1, то геометрия pGa(s,t) называется обобщенным четырехугольником и обозначается GQ(s,t).
Точечным графом частичной геометрии называется граф, вершинами которого являются точки геометрии, и две различные вершины смежны, если они лежат на одной прямой. Точечный граф частичной геометрии pGa(s,t) сильно регулярен с параметрами v = (s + 1)(1 + st/a), k = s(t +1), X = (s — 1) +(a — l)i, /j, = a(t+l). Любой сильно регулярный граф с такими параметрами для некоторых a, s,t называется псевдогеометрическим графом для pGa(s, t).
Цель диссертации. Целью данной работы является решение следующих задач:
изучить связные реберно регулярные графы с параметрами (v, к, X) и к > ЗЬ\ — 1;
найти возможные автоморфизмы сильно регулярного графа, являющегося псевдогеометрическим для pG2(4,9);
3) найти возможные автоморфизмы сильно регулярного графа, в котором окрестности вершин являются точечными графами частичной геометрии рб?2(4,9).
Методы исследования. Основными методами исследования являются теоретико-графовые методы, методы локального анализа комбинаторно симметричных графов и методы теории конечных групп, в частности, метод Хигмена приложения теории характеров к выяснению порядков автоморфизмов дистанционно регулярных графов и подграфов неподвижных точек этих автоморфизмов.
Научная новизна. Основные результаты, полученные в работе, являются новыми.
Выделим из них следующие.
Исследованы связные реберно регулярные графы с параметрами (v, к, А) и к > ЗЬі — 1.
Найдены возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярных графов с параметрами (210, 95, 40, 45) и (95, 40,12, 20).
Найдены возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярного графа, в котором окрестности вершин являются точечными графами частичной геометрии рСг(4,9).
Теоретическая и практическая ценность. Работа носит теоретический характер. Результаты продолжют изучение комбинаторно симметричных графов и их автоморфизмов. Результаты и методы диссертации могут быть использованы для изучения алгебраических структур подобного типа.
Апробация работы. Основные результаты работы докладывались на международном российско-китайском семинаре ( Иркутск, 2007), VII Международной школе конференции по теории групп (Челябинск, 2008) и на 39-й и 40-й Всероссийских молодежных конференциях ИММ УрО РАН (Екатеринбург, 2008-2009 гг.).
Результаты работы также докладывались и обсуждались на алгебраическом семинаре ИММ УрО РАН.
Публикации. Основные результаты диссертации опубликованы в работах [27]-[33]. Работы [27]-[32] выполнены в нераздельном соавторстве с А.А. Махневым.
Структура и объем работы. Работа состоит из введения, трех глав и списка цитированной литературы, содержащего 42 наименования.
