Введение к работе
Актуальность темы. Одной из центральных проблем в теории конечных групп является поиск единого представления конечных простых групп. В связи с этим, приобрела актуальность задача классификации дистанционно регулярных графов на основе свойств транзитивности их групп автоморфизмов, которой и посвящена настоящая диссертационная работа. В работе исследуются дистанционно регулярные графы диаметра 3 с некоторыми условиями их комбинаторной и групповой симметричности, и их автоморфизмы.
Класс /С графов (под графом здесь и далее будем понимать неориентированный граф без петель и кратных ребер) назовем универсальным, если каждая конечная группа представима группой автоморфизмов некоторого конечного графа из К. Известный результат Р. Фрухта [14] послужил выделению ряда универсальных подклассов графов, в числе которых оказались следующие: регулярные графы степени к для произвольного фиксированного к > 2, двудольные графы, гамильтоновы графы, ^-хроматические графы для t > 1, сильно регулярные графы (регулярные графы, у которых число вершин в пересечении окрестностей любой пары различных вершин зависит только от того, смежны эти вершины или нет)([23],[20]). В [9] Ф. Бюкенхаутом была предложена идея построения единой геометрической теории, согласно которой каждая конечная простая группа была бы представима группой автоморфизмов некоторой геометрической структуры из определенного, поддающегося описанию, класса конечных геометрий. Отметим, что спорадические простые группы Фишера, Судзуки, Маклафлина, Холла-Янко, Рудвалиса и Хигмена-Симса были впервые построены как группы автоморфизмов сильно регулярных графов. Например, Б. Фишер исследовал почти простые группы, порож-
денные классом 3-транспозиций (сопряженным классом инволюций группы, в котором произведение любых двух элементов имеет порядок < 3), и доказал, что все они являются группами ранга 3 на ассоциированных графах, вершинами которых являются элементы класса 3-транспозиций и две вершины смежны, если соответствующие инволюции коммутируют. Среди таких групп оказались все симметрические группы, некоторые классические (симплектические, ортогональные, унитарные) группы, и три спорадические группы, обнаруженные Фишером в процессе исследования, две из которых (Fi22> Fi2s) являются простыми, a Fi24 содержит простую группу индекса 2.
Известно, что если G — транзитивная группа подстановок ранга 3 на множестве X и имеет четный порядок, то можно построить граф Г ранга 3 с У (Г) = X, группа автоморфизмов которого допускает G в качестве подгруппы; к тому же, каждый граф ранга 3 является сильно регулярным графом. Таким образом, внутренняя геометрия целого ряда групп, как показал Фишер, выразима с помощью сильно регулярных графов. Свое развитие теория групп подстановок ранга 3 получила в работах Д.Г. Хигмена ([17Ц19]).
Важным комбинаторным обобщением понятия сильно регулярного графа является понятие дистанционно регулярного графа. Для вершины а графа Г через Г^а) обозначим подграф, индуцированный Г на множестве всех вершин, находящихся на расстоянии і от а. Граф Г диаметра d называется дистанционно регулярным с массивом пересечений {b0,bi,... ,bd-i\ci,... , q}, если значения bi{u,w) = |Гі+і(гі) П Г(го)| и Ci(u, w) = |IVi(u) ПГ(ш)| не зависят от выбора вершин и, w, находящихся на расстоянии г в Г для любого і Є {0,..., d}. Положим Oj = 60 — Ь; — с*, /і = С2, А = <ц. Заметим, что для дистанционно регулярного графа bo — это степень графа, ci = 1. Дистанционно регулярный граф диаметра 2 это
б точности то же, что и связный сильно регулярный граф (случай несвязного сильно регулярного графа не представляет особого интереса, так как несвязный сильно регулярный граф является объединением изолированных равномощных клик).
В диссертационной работе исследуются реберно симметричные дистанционно регулярные графы. Граф назовем реберно симметричным, если его группа автоморфизмов действует транзитивно на множестве его дуг (упорядоченных ребер). Каждый реберно симметричный граф может быть построен на основе сравнительно небольшой информации о своей группе автоморфизмов следующим образом. Пусть даны неинвариантпая подгруппа Н группы G и элемент д Є G. Через Г = T(G, Н, НдН) обозначим граф с множеством вершин V(G, Н) — {Нх | х Є G] и ребрами {Нх, Ну} такими, что ху-1 Є НдН. Тогда (см. [24] или [15]) (1) если G действует точно на V(G, Н), д2 є Я и G = (Н, д), то Г - связный граф, G < Aut(r) и G действует точно и транзитивно на вершинах и на дугах графа Г; (2) если G действует транзитивно на дугах связного графа Е, Н — стабилизатор вершины є Є Е, д является 2-элементом и вершины е, е9 смежны в Е, то Е ~ T(G,H,HgH), д2 Є Н и G = (Н,д). Более симметричными объектами (обладающими большими группами автоморфизмов) являются дистанционно транзитивные графы. Если Г — граф диаметра d, то через Г,-, где ie{l,...,(f}, обозначается граф с тем же множеством вершин, что и Г, в котором две вершины смежны тогда и только тогда, когда они находятся на расстоянии г в Г. Граф Г диаметра d называется дистанционно транзитивным, если для любого г Є {1,...,d} группа Aut(r) действует транзитивно на множестве дуг графа Г^ (в частности, каждый граф Г* является реберно симметричным). Легко попять, что каждый дистанционно транзитивный граф является дистанционно регулярным графом. При этом, дистанционно транзитивные графы диаметра 2 суть в точности связ-
ные графы ранга 3. Группами автоморфизмов дистанционно транзитивных графов представимы многие конечные простые группы. Необходимо отметить также, что дистанционно регулярные графы и реберно симметричные графы используются в различных приложениях, в том числе, в алгебраической теории кодирования и при моделировании сетей. В связи с этим представляют интерес задача полного описания класса дистанционно транзитивных графов, и связанная с ней задача описания более широкого класса - класса реберно симметричных дистанционно регулярных графов.
Большое количество исследований было проведено для класса примитивных дистанционно транзитивных графов, однако, в общем случае описание дистанционно транзитивных графов не завершено. Вместе с тем, задача классификации реберно симметричных дистанционно регулярных графов требует дальнейшего изучения.
Кроме того, проблемой общего характера в теории графов является вопрос существования графов с заданным набором свойств, в частности, в теории дистанционно регулярных графов актуален вопрос о реализуемости массива пересечений, то есть существования графов с заданным массивом пересечений.
Пусть J- — некоторый класс графов. Граф Г назовем локально Т графом, если Г(а) лежит в Т для любой вершины а графа Г. Если при этом класс Т состоит из графов, изоморфных некоторому графу А, то граф Г назовем локально А-графом.
Пусть Г - реберно симметричный граф без изолированных вершин и G = Aut(r) - его группа автоморфизмов. Ясно, что группа G действует транзитивно на вершинах графа Г, поэтому Г — локально А-граф. Более того, для каждой вершины а графа Г ее стабилизатор Ga действует транзитивно на окрестности Г(а), поэтому Г(а) является локально Дг(а)-графом. Таким образом, свойство реберной симметричности можно рассматривать
как локальное свойство графа.
Локальные комбинаторные и теоретико-групповые свойства могут влиять на глобальную структуру графа (яркими примерами тому являются известные теоремы Татта и Вейсса о специальном подклассе реберно симметричных графов с транзитивными на s-дугах группами автоморфизмов), но степень этого влияния не всегда поддается полному анализу. При этом, для дистанционно регулярных графов удается найти простые делители порядков их групп автоморфизмов и подграфы неподвижных точек для автоморфизмов простых порядков с помощью теории характеров конечных групп (с применением метода Гр. Хигмена), что может быть полезным при построении или в доказательствах несуществования дистанционно регулярных графов с заданными локальными свойствами.
Граф назовем локально циклическим, если окрестность каждой его вершины является объединением изолированных циклов. Например, граф Шрикханде это единственный сильно регулярный локально Сб-граф на 16 вершинах с A = /j, = 2. Граф Шрикханде является реберно симметричным, к тому же, это граф наименьшего порядка, который является дистанционно регулярным, но не дистанционно транзитивным [8].
Одним из вопросов, рассматриваемых в диссертации, является вопрос существования реберно симметричных дистанционно регулярных локально циклических графов.
В работе используется следующий важный результат А.А. Махнева и В.П. Буриченко о дистанционно регулярных локально циклических графах.
Предложение 1 ([1], теорема 2). Пусть Г является дистанционно регулярным графом диаметра, большего 2, на v < 1000 вершинах. Если А = 2 u /j > 1, то верно одно из утверждений:
(1) Г — примитивный граф с массивом пересечений
{15,12,6; 1,2,10}, {19,16,8; 1,2,8}, {24,21,3; 1,3,18}, {35,32,8; 1,2,28} или {51,48,8; 1,4,36};
(2) Г — антиподальный граф с fj, = 2 и массивом пересечений
{2г + 1,2г - 2,1; 1, 2,2г + 1}, г {3,4,..., 21} - {10,16} и v = 2r(r + 1)/
(3) Г — антиподальный граф с ц> 3 и массивом пересечений
{15,12,1; 1,4,15}, {18,15,1; 1,5,18}, {27,24,1; 1,8,27}, {35,32,1; 1,4,35}, {45,42,1; 1,6,45}, {42,39,1; 1,3,42} или {75,72,1; 1,12,75}.
Известно существование реберно симметричных дистанционно регулярных графов из пункта (2) предложения 1, получаемых с помощью конструкции Мэтона, если 2г + 1 — степень простого числа [8]. В частности, в случае г = 3 получается граф Клейна, единственный дистанционно регулярный локально С7-граф диаметра 3 на 24 вершинах, являющийся 3-накрытием 8-клики. Граф Клейна является реберно симметричным, но не дистанционно транзитивным [8].
Исследования, проводимые в диссертации, направлены на решение вопроса о существовании реберно симметричных дистанционно регулярных локально циклических графов для массивов из пунктов (1)-(3) предложения 1.
Другая часть работы посвящена изучению реберно симметричных ан-типодальных дистанционно регулярных графов.
В [15] К. Годсил, Р. Либлер и Ч. Прэгер получили описание анти-подальных дистанционно транзитивных графов диаметра 3. Более общей является задача описания реберно симметричных антиподальных дистанционно регулярных графов диаметра 3. Антиподальный дистанционно регулярный граф диаметра 3 имеет (см. [8]) массив пересечений {к, /*(г — 1), 1; 1, /і, к}, является r-накрытием (к + 1)-клики и для параметров г,\,ц,к справедливо тождество к — 1 — r^ = X — fi. Положим 5 = Л — \i.
В работе [16] доказано, что для фиксированных г, 5 имеется лишь конечное число допустимых массивов, кроме случаев 6 Є {—2,0,2}. В диссертации исследуются реберно симметричные антиподальные дистанционно регулярные графы диаметра 3 в случае А — ц.
Цель диссертации. Целью данной работы является решение следующих задач:
1)Изучить возможные автоморфизмы гипотетических дистанционно регулярных графов с массивами пересечений {42,39,1; 1,3,42}, {35,32,1; 1,2,28}, {35,32,1; 1,2,35} и исследовать реберно симметричные дистанционно регулярные графы с этими массивами пересечений.
2) Исследовать реберно симметричные антиподальные дистанционно регулярные графы диаметра 3 в случае Л = [і.
Методы исследования. Основными методами исследования являются методы теории конечных групп, теоретико-графовые методы и методы локального анализа комбинаторно симметричных графов.
Научная новизна. Все основные результаты диссертации являются новыми.
Теоретическая и практическая ценность. Работа носит теоретический характер. Результаты работы продолжают исследование дистанционно регулярных графов и их автоморфизмов. Результаты и методы диссертации могут быть использованы для изучения алгебраических структур подобного типа.
Апробация работы. Основные результаты работы докладывались на Международной конференции по алгебре и геометрии, посвященной 80-летию со дня рождения А.И. Старостина (Екатеринбург, 2011 г.), на Международной (43-й Всероссийской) молодежной школе-конференции ИММ
УрО РАН (Екатеринбург, 2012 г.), на Международной конференции "Алгебра и линейная оптимизация", посвященной 100-летию со дня рождения проф. С.Н. Черникова (Екатеринбург, 2012 г.), на Международной школе-конференции по теории групп, посвященной 90-летию со дня рождения проф. З.И.Боревича (Владикавказ, 2012 г.). Результаты работы неоднократно докладывались и обсуждались на алгебраическом семинаре Института математики и механики УрО РАН.
Публикации. Результаты диссертации были опубликованы в 4 статьях (три статьи опубликованы в журналах из списка ВАК) и 4 тезисах докладов. Из них 1 статья и 1 тезисы написаны без соавторов, 1 статья и 1 тезисы - тремя авторами (Махнев А.А., Падучих Д.В., Циовкина Л.Ю.), остальные — в соавторстве с Махневым А.А. Все совместные работы написаны в нераздельном соавторстве.
Структура и объем работы. Работа состоит из введения, трех глав и списка цитированной литературы, содержащего 33 наименования. Общий объем диссертации составляет 80 страниц.
