Авторефераты по всем темам >>
Авторефераты по разным специальностям
Уральское отделение Российской академии наукФедеральное государственное бюджетное учреждение науки Институт математики и механики имени Н.Н. Красовского
На правах рукописи
УДК 519.17+512.54 ЦИОВКИНА
юдмила Юрьевна СИММЕТРИЧНЫЕ ДИСТАНЦИОННО РЕГУЛЯРНЫЕ ГРАФЫ И ИХ АВТОМОРФИЗМЫ
01.01.06 математическая логика, алгебра и теория чисел
Автореферат диссертации на соискание ученой степени кандидата физико-математических наук Екатеринбург - 2012
Работа выполнена в отделе алгебры и топологии Федерального государственного бюджетного учреждения науки Института математики и механики Уральского отделения Российской академии наук.
Научный консультант: доктор физико-математических наук, профеcсор, чл.-корр. РАН МАХНЕВ А.А.
Официальные оппоненты: доктор физико-математических наук, профеcсор АЛЕЕВ Р.Ж.
кандидат физико-математических наук ЕФИМОВ К.С.
Ведущая организация: ФГАОУ ВПО УрФУ имени первого Президента России Б.Н.Ельцина
Защита состоится 27 ноября 2012 г. в 15 ч. 30 м. на заседании диссертационного совета Д 004.006.03 по защите диссертаций в Институте математики и механики Уральского отделения РАН по адресу: 620219, г. Екатеринбург, ул. Софьи Ковалевской, д. 16.
С диссертацией можно ознакомиться в научной библиотеке Института математики и механики УрО РАН (г. Екатеринбург, ул. С. Ковалевской, д. 16).
Автореферат разослан 2012 г.
Ученый секретарь диссертационного совета, кандидат физ.-мат. наук БЕЛОУСОВ И.Н.
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы. Одной из центральных проблем в теории конечных групп является поиск единого представления конечных простых групп. В связи с этим, актуальной стала задача классификации дистанционно регулярных графов на основе свойств транзитивности их групп автоморфизмов, которой и посвящена настоящая диссертационная работа. В работе исследуются дистанционно регулярные графы диаметра 3 с некоторыми условиями их комбинаторной и групповой симметричности, и их автоморфизмы.
Класс K графов (под графом здесь и далее будем понимать неориентированный граф без петель и кратных ребер) назовем универсальным, если каждая конечная группа представима группой автоморфизмов некоторого конечного графа из K. Известный результат Р. Фрухта [14] послужил выделению ряда универсальных подклассов графов, в числе которых оказались следующие: регулярные графы степени k для произвольного фиксированного k > 2, двудольные графы, гамильтоновы графы, t-хроматические графы для t > 1, сильно регулярные графы (регулярные графы, у которых число вершин в пересечении окрестностей любой пары различных вершин зависит только от того, смежны эти вершины или нет)([23],[20]).
В [9] Ф. Бюкенхаутом была предложена идея построения единой геометрической теории, согласно которой каждая конечная простая группа была бы представима группой автоморфизмов некоторой геометрической структуры из определенного класса конечных геометрий.
Отметим, что спорадические простые группы Фишера, Судзуки, Маклафлина, Холла-Янко, Рудвалиса и Хигмена-Симса были впервые построены именно как группы автоморфизмов сильно регулярных графов.
Например, Б. Фишер исследовал почти простые группы, порожденные классом 3-транспозиций (сопряженным классом инволюций группы, в котором произведение любых двух элементов имеет порядок 3), и доказал, что все они являются группами ранга 3 на ассоциированных графах, вершинами которых являются элементы класса 3-транспозиций и две вершины смежны, если соответствующие инволюции коммутируют. Среди таких групп оказались все симметрические группы, некоторые классические (симплектические, ортогональные, унитарные) группы, и три спорадические группы, обнаруженные Фишером в процессе исследования, две из которых (F i22, F i23) являются простыми, а F i24 содержит простую группу индекса 2.
Известно, что если G транзитивная группа подстановок ранга 3 на множестве X и имеет четный порядок, то можно построить граф ранга 3 c V () = X, группа автоморфизмов которого допускает G в качестве подгруппы; к тому же, каждый граф ранга 3 является сильно регулярным графом. Таким образом, внутренняя геометрия целого ряда групп, как показал Фишер, выразима с помощью сильно регулярных графов. Свое развитие теория групп подстановок ранга 3 получила в работах Д.Г. Хигмена ([17]Ц[19]).
Важным комбинаторным обобщением понятия сильно регулярного графа является понятие дистанционно регулярного графа. Для вершины a графа через i(a) обозначим подграф, индуцированный на множестве всех вершин, находящихся на расстоянии i от a. Граф диаметра d называется дистанционно регулярным с массивом пересечений {b0, b1,..., bd-1; c1,..., cd}, если значения bi(u, w) = |i+1(u) (w)| и ci(u, w) = |i-1(u) (w)| не зависят от выбора вершин u, w, находящихся на расстоянии i в для любого i = 0,..., d. Положим ai = b0-bi-ci, = c2, = a1. Заметим, что для дистанционно регулярного графа b0 это степень графа, c1 = 1. Дистанционно регулярный граф диаметра 2 это в точности то же, что и связный сильно регулярный граф (случай несвязного сильно регулярного графа не представляет особого интереса, так как несвязный сильно регулярный граф является объединением изолированных равномощных клик). Введем еще некоторые необходимые определения. Если граф диаметра d, то через i, где i {1,..., d}, обозначается граф с тем же множеством вершин, что и , в котором две вершины смежны тогда и только тогда, когда они находятся на расстоянии i в . Граф диаметра d называется примитивным, если граф i связен для любого i {1,..., d}, в противном случае граф называется импримитивным. Граф диаметра d > 1 называется антиподальным, если соответствующий граф d является объединением изолированных клик. Согласно основной теореме Д. Смита, каждый импримитивный дистанционно регулярный граф является двудольным или антиподальным.
В диссертационной работе исследуются реберно симметричные дистанционно регулярные графы. Граф назовем реберно симметричным, если его группа автоморфизмов действует транзитивно на множестве его дуг (упорядоченных ребер). Более высокой степенью симметрии обладают дистанционно транзитивные графы. Граф диаметра d называется дистанционно транзитивным, если для любого i {1,..., d} группа Aut() действует транзитивно на множестве дуг графа i (в частности, каждый граф i является реберно симметричным). Легко понять, что каждый дистанционно транзитивный граф является дистанционно регулярным графом.
При этом, дистанционно транзитивные графы диаметра 2 суть в точности связные графы ранга 3. Группами автоморфизмов дистанционно транзитивных графов представимы многие конечные простые группы. Необходимо отметить также, что дистанционно регулярные графы и реберно симметричные графы используются в различных приложениях, в том числе, в алгебраической теории кодирования и при моделировании сетей. В связи с этим представляют интерес задача полного описания класса дистанционно транзитивных графов, и связанная с ней задача описания более широкого класса - класса реберно симметричных дистанционно регулярных графов.
Изучение реберно симметричных графов началось с двух важных работ У. Татта 1947 и 1959 годов о конечных кубических графах. Татт рассмотрел класс графов, группы автоморфизмов которых действуют транзитивно на s-дугах графа, то есть графов с вершинно транзитивной группой автоморфизмов и стабилизатором вершины, действующем транзитивно на множестве исходящих из нее s-дуг (s-дугой называется путь (v0,..., vs), в котором vi-1 = vi+1 для любого i {1,..., s - 1}). Как оказалось, для регулярных графов степени 3 с транзитивной на s-дугах группой автоморфизмов, число s не превосходит 5 и граница достигается на графе Татта-Кокстера.
Впоследствии Р. Вейсс обобщил результат Татта, доказав, что для регулярных графов произвольной степени k 3 с транзитивной на s-дугах группой автоморфизмов, число s не превосходит 7 и граница достигается на 12-клетке Татта[25].
Г. Сабидусси в работе [24] предложил следующий метод построения всех реберно симметричных графов на основе сравнительно небольшой информации об их группах автоморфизмов, который, в частности, оказался полезным в классификации дистанционно транзитивных графов. Пусть даны неинвариантная подгруппа H группы G и элемент g G. Через = (G, H, HgH) обозначим граф с множеством вершин V (G, H) = {Hx | x G} и ребрами {Hx, Hy} такими, что xy-1 HgH. Тогда (см.
[24] или [15]) (1) если G действует точно на V (G, H), g2 H и G = H, g, то связный граф, G Aut() и G действует точно и транзитивно на вершинах и на дугах графа ; (2) если G действует транзитивно на дугах связного графа , H стабилизатор вершины e , g является 2-элементом и вершины e, eg смежны в , то (G, H, HgH), g2 H и G = H, g.
Большое количество исследований было посвящено примитивным дистанционно транзитивным графам, однако, в общем случае описание дистанционно транзитивных графов не завершено. Вместе с тем, задача классификации реберно симметричных дистанционно регулярных графов требует дальнейшего изучения.
Кроме того, проблемой общего характера в теории графов является вопрос существования графов с заданным набором свойств, в частности, в теории дистанционно регулярных графов актуален вопрос о реализуемости массива пересечений, то есть существования графов с заданным массивом пересечений.
Пусть F некоторый класс графов. Граф назовем локально F графом, если (a) лежит в F для любой вершины a графа . Если при этом класс F состоит из графов, изоморфных некоторому графу , то граф назовем локально -графом.
Пусть - реберно симметричный граф без изолированных вершин и G = Aut() - его группа автоморфизмов. Ясно, что группа G действует транзитивно на вершинах графа , поэтому - локально -граф. Более того, для каждой вершины a графа ее стабилизатор Ga действует транзитивно на окрестности (a), поэтому (a) является локально (a)-графом.
Таким образом, свойство реберной симметричности можно рассматривать как локальное свойство графа.
окальные комбинаторные и теоретико-групповые свойства в некоторых случаях могут влиять на глобальную структуру графа (яркими примерами тому являются вышеупомянутые теоремы Татта и Вейсса), но степень этого влияния не всегда поддается полному анализу. При этом, для дистанционно регулярных графов удается найти простые делители порядков их групп автоморфизмов и подграфы неподвижных точек для автоморфизмов простых порядков с помощью теории характеров конечных групп (с применением метода Гр. Хигмена), что может быть полезным при построении графов с помощью компьютера или в доказательствах несуществования дистанционно регулярных графов с заданными локальными свойствами.
Граф назовем локально циклическим, если окрестность каждой его вершины является объединением изолированных циклов. Например, граф Шрикханде это единственный сильно регулярный локально C6-граф на 16 вершинах с = = 2. Граф Шрикханде является реберно симметричным тороидальным графом; к тому же, это граф наименьшего порядка, который является дистанционно регулярным, но не дистанционно транзитивным [8].
Одним из вопросов, рассматриваемых в диссертации, является вопрос существования реберно симметричных дистанционно регулярных локально циклических графов.
В работе используется следующий важный результат А.А. Махнева и В.П. Буриченко о дистанционно регулярных локально циклических графах.
Предложение 1 ([1], теорема 2). Пусть является дистанционно регулярным графом диаметра, большего 2, на v 1000 вершинах. Если = 2 и > 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) антиподальный граф с = 2 и массивом пересечений {2r + 1, 2r - 2, 1; 1, 2, 2r + 1}, r {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, получаемых с помощью конструкции Мэтона, если 2r + 1 степень простого числа [8]. В частности, в случае r = 3 получается граф Клейна, единственный дистанционно регулярный локально C7-граф диаметра 3 на 24 вершинах, являющийся 3накрытием 8-клики. Граф Клейна является реберно симметричным, но не дистанционно транзитивным [8].
Исследования, проводимые в диссертации, направлены на решение вопроса о существовании реберно симметричных дистанционно регулярных локально циклических графов для массивов из пунктов (1)Ц(3) предложения 1.
Другая часть работы посвящена изучению реберно симметричных антиподальных дистанционно регулярных графов.
В [15] К. Годсил, Р. Либлер и Ч. Прэгер получили описание антиподальных дистанционно транзитивных графов диаметра 3. Более общей является задача описания реберно симметричных антиподальных дистанционно регулярных графов диаметра 3. Антиподальный дистанционно регулярный граф диаметра 3 имеет (см. [8]) массив пересечений {k, (r - 1), 1; 1, , k}, является r-накрытием (k + 1)-клики и для параметров r, , , k справедливо тождество k -1-r = -. Положим = -.
В [16] доказано, что для фиксированных r, имеется лишь конечное число допустимых массивов, кроме случаев {-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 г.). Результаты работы докладывались и обсуждались на алгебраических семинарах Института математики и механики УрО РАН.
Публикации. Основные результаты диссертации опубликованы в работах [26]Ц[33]. Работы [26]Ц[29] выполнены в нераздельном соавторстве с А.А. Махневым. Работы [32]Ц[33] выполнены в нераздельном соавторстве с А.А. Махневым и Д.В. Падучих.
Структура и объем работы. Работа состоит из введения, трех глав и списка цитированной литературы, содержащего 33 наименования.
КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении обсуждается история и актуальность вопроса, даются определения и формулируются основные результаты работы. Первая глава имеет вспомогательный характер. В ней подробно излагается метод Хигмена изучения автоморфизмов дистанционно регулярных графов и доказывается ряд вспомогательных утверждений, используемых в доказательствах теорем.
Вторая глава посвящена изучению автоморфизмов дистанционно регулярных локально циклических графов для следующих массивов пересечений из пунктов (1)Ц(3) предложения 1: {42, 39, 1; 1, 3, 42}, {35, 32, 1; 1, 2, 28}, {35, 32, 1; 1, 2, 35}. В ней определяются возможные порядки и подграфы неподвижных точек автоморфизмов дистанционно регулярных графов с этими массивами пересечений. Исследуются реберно симметричные дистанционно регулярные графы с вышеперечисленными массивами пересечений.
Пусть для произвольного автоморфизма g графа число точек x из таких, что d(x, xg) = j обозначается через j(g). Основными результатами второй главы являются следующие теоремы и следствия.
Теорема 1. Пусть дистанционно регулярный граф, имеющий массив пересечений {42, 39, 1; 1, 3, 42}, G = Aut(), g элемент из G простого порядка p и = Fix(g). Тогда выполняется одно из следующих утверждений:
(1) пустой граф и либо (i) p = 43, 1(g) = 43, 2(g) = 559;
(ii) p = 7, 3(g) = 98s + 14, 1(g) = 91l + 42s + 49 и 13l + 20s 77;
(iii) p = 2, 3(g) = 28s + 14, 1(g) = 26l + 12s + 62 и 13l + 20s 263;
(2) p = 13, является 4-кликой, 3(g) = 52, 1(g) = 169l + 65 и l {0, 1, 2};
(3) p = 7, лежит в антиподальном классе и либо (i) || = 7, 1(g) = 91l - 7t и 3(g) = 7 + 14t, либо (ii) || = 14, 1(g) = 91l - 7t + 49 и 3(g) = 14t ;
(4) p = 3, содержит t антиподальных классов, пересекающих по s вершинам, 3(g) = 14 - s и либо (i) t = 1, s {2, 5, 8, 11, 14} и 1(g) = 39l + 6s - 3, либо (ii) t = 4, является объединением s изолированных 4-клик, s {2, 5, 8} и 1(g) = 39l - 15s + 15;
(5) p = 2, содержит t антиподальных классов, пересекающих по s вершинам, 3(g) = t(14 - s) + 14t и либо (i) t = 1, || = s, s {2, 4, 6, 8, 10, 12, 14} и 1(g) = 26l +6s+6t +10, либо (ii) t = 3, шестиугольник и 1(g) = 26l + 6t + 6, либо (iii) t = 5, является графом K5,5 с удаленным максимальным паросочетанием и 1(g) = 26l + 6t - 2.
Следствие. Дистанционно регулярный граф с массивом пересечений {42, 39, 1; 1, 3, 42} не является реберно симметричным.
Теорема 2. Пусть дистанционно регулярный граф, имеющий массив пересечений {35, 32, 8; 1, 2, 28}, G = Aut(), g элемент из G простого порядка p и = Fix(g). Тогда (G) {2, 3, 5, 7} и выполняется одно из следующих утверждений:
(1) пустой граф и либо (i) p = 7, 3(g) = 168s, 1(g) = 98l+42s-42 и 2(g) = 798-98l-210s;
(ii) p = 3, 3(g) = 72s, 1(g) = 42l + 18s и 2(g) = 756 - 42l - 90s;
(iii) p = 2, 3(g) = 48s, 1(g) = 28l + 12s и 2(g) = 756 - 28l - 60s;
(2) состоит из вершин, попарно находящихся на расстоянии 3 в и либо (i) p = 5, || = 1, 3(g) = 120s + 40 и 1(g) = 70l + 30s + 5, либо (ii) p = 7, || = 7r, 3(g) = 168s + 112/r и 1(g) = 98l + 42s - 49r, s 2/r, r {1, 2} или || = 21, 3(g) = 0 и 1(g) = 98l + 49, l 6;
(3) p = 2, || = 2t, 3(g) = 48l - 16t, 1(g) = 28s + 12l - 14t и либо (i) для любой вершины a из подграф 3(a) не пересекает и || 36, либо (ii) содержит вершину степени 1 и || 50, либо (iii) степень любой вершины в не меньше 3 и не больше 19, а || 82.
Следствие. Дистанционно регулярный граф с массивом пересечений {35, 32, 8; 1, 2, 28} не является реберно симметричным.
Теорема 3. Пусть дистанционно регулярный граф, имеющий массив пересечений {35, 32, 1; 1, 2, 35}, G = Aut(), g элемент из G простого порядка p и = Fix(g). Тогда (G) {2, 3, 5, 7, 17} и выполняется одно из следующих утверждений:
(1) пустой граф и либо (i) p = 17, 1(g) = 3(g) = 34 и 2(g) = 544 или 3(g) = 612, либо (ii) p {2, 3}, 3(g) = 0, 2(g) = 576 и 1(g) = 36;
(2) лежит в антиподальном классе и либо (i) p = 7, || = 3, 17, либо (ii) p = 5, || = 7, 17;
(3) p = 3, 5 и граф икосаэдра;
(4) p = 2, объединение двух антиподальных классов, 3(g) = 0 и 1(g) = 34.
Следствие. Дистанционно регулярный граф с массивом пересечений {35, 32, 1; 1, 2, 35} не является реберно симметричным.
В третьей главе диссертации изучаются реберно симметричные антиподальные дистанционно регулярные графы диаметра 3. Как было указано выше, массивы пересечений таких графов полностью определяются параметрами r, , k. Перечислим далее известные бесконечные классы антиподальных дистанционно регулярных графов диаметра 3.
А. Конструкция Мэтона, k = r+1 степень простого числа p ( четно или p = 2).
Б. Конструкция Камерона, k = q3, = (q2 - 1)(q + 1)/r, q степень простого числа p, r делит (q + 1)/(2, p + 1).
В. Конструкция Бонди, k = r+1, = 1, r нечетно, существует дезаргова проективная плоскость порядка k.
Г. Конструкция Броувера, k = st, r = s+1, = t-1, существует псевдогеометрический граф для GQ(s, t), имеющий спред (разбиение множества вершин (s + 1)-кликами).
Д. Конструкция Годсила-Хензеля, k = p2i - 1, r = pi-l, = pi+l, p простое число, 0 l < i.
Е. Конструкция де Каена-фон дер Флаасса, k = ql+1 - 1, r = ql, = q, q = 2t.
Введем ниже новые бесконечные серии антиподальных дистанционно регулярных графов диаметра 3. Отметим сразу, что вопрос реализуемости соответствующих массивов пересечений остается открытым в общем случае.
1. Серия Судзуки. Граф Suz(q) имеет массив пересечений {q2, q2 - q 2, 1; 1, q + 1, q2}, q = 22e+1 8, r = q - 1, G = Aut(Suz(q)) = Aut(Sz(q)) и Ga расширение силовской 2-подгруппы P порядка q2 с помощью циклической группы порядка 2e + 1.
Имеется простая конструкция графа Suz(q). Вершинами графа являются инволюции группы Sz(q), и две инволюции смежны, если порядок их произведения равен 5. Поэтому окрестность вершины в графе Suz(q) имеет разбиение 4-кликами.
Для любого делителя s числа q - 1, 1 < s q - 1 существует граф Suz(q, s) с массивом пересечений {q2, (s - 1)(q2 - 1)/s, 1; 1, (q2 - 1)/s, q2}, q = 22e+1 8, G = Aut(Suz(q, s)) = Aut(Sz(q)) и Ga расширение силовской 2-подгруппы P порядка q2 с помощью абелевой группы порядка (q - 1)(2e + 1)/s.
2. Серия Ри. Граф Ree(q) имеет массив пересечений {q3, q3 - 2q2 - 2q 3, 1; 1, 2(q2 + q + 1), q3}, q = 32e+1 > 3, r = (q - 1)/2, G = Aut(Ree(q)) = Aut(2G2(q)) и Ga расширение силовской 3-подгруппы P (цоколя группы) порядка q3 с помощью циклической группы порядка 4e + 2.
Для любого делителя s числа (q - 1)/2, 1 < s (q - 1)/2 существует граф Ree(q, s) с массивом пересечений {q2, (s - 1)(q3 - 1)/s, 1; 1, (q3 1)/s, q2}, q = 32e+1 > 3, G = Aut(Ree(q, s)) = Aut(2G2(q)) и Ga расширение силовской 3-подгруппы (цоколя группы) P порядка q3 с помощью группы порядка (q - 1)(2e + 1)/s.
3. Унитарная серия. Граф U3(q) имеет массив пересечений {q3, (r 1)(q3 - 1)/r, 1; 1, (q3 - 1)/r, q3}, q = pe > 3, r 2 -часть числа (q - 1), G = Aut(U3(q)) = Aut(U3(q)) и Ga расширение силовской p-подгруппы P (цоколя группы) порядка q3 с помощью абелевой группы порядка (q2 - 1)e/r.
Для любого неединичного делителя s 2 -части числа (q - 1) существует граф U3(q, s) с массивом пересечений {q3, (s - 1)(q3 - 1)/s, 1; 1, (q3 1)/s, q3}, q = pe > 3, G = Aut(U3(q, s)) = Aut(U3(q)) и Ga расширение силовской p-подгруппы P (цоколя группы) порядка q3 с помощью абелевой группы порядка (q2 - 1)e/s.
Следующая теорема уточняет некоторые утверждения основной теоремы Годсила, Либлера и Прэгер из [15].
Теорема 4. Пусть реберно симметричный дистанционно регулярный граф с массивом пересечений {k, (r - 1), 1; 1, , k} и G = Aut().
Тогда выполняются следующие утверждения:
(1) если двудольный граф, то получается удалением из Kk+1,k+максимального паросочетания, G 2 Sk+1;
(2) если r = k, то либо k = 2 и шестиугольник, либо k = 6, вторая окрестность вершины в графе Хофмана-Синглтона и G S7;
(3) если r = 2, то либо (i) k + 1 = 22m-1 2m-1, G 2 Sp2m(2), m 3, либо (ii) k = q3, G 2 P U3(q), q > 3 или G 2 Aut(2G2(q)), q = 32e+1, e 1, либо (iii) k = q, G 2 P L2(q), q 1 (mod 4), либо (iv) k = 175, G = 2 HiS или k = 275, G = 2 Co3, либо (v) k = 22t - 1, G = 2 ASp2t(2).
В случае (ii) граф имеет параметры v = 2(q3 + 1), k = q3, = (q -1)(q2 +1)/2, = (q +1)(q2 -1)/2. В этом случае для группы Ри G2(q) в основной теореме из [15] допущена опечатка: вместо n = 32e+1+1 должно быть n = 36e+3 + 1. Отметим, что в случае, когда r = 2 (утверждения (1), (3)) соответствующие графы являются дистанционно транзитивными.
Основным результатом третьей главы диссертации является следующая теорема.
Теорема 5. Пусть реберно симметричный дистанционно регулярный граф с массивом пересечений {r + 1, (r - 1), 1; 1, , r + 1} и G = Aut(). Если r > 2, то выполняется одно из следующих утверждений:
(1) k = q степень простого числа, r делит q - 1, имеет массив пересечений {q, (r -1)(q -1)/r, 1; 1, (q -1)/r, q} и L2(q) G или SL2(q) G;
(2) {Suz(q, s), Ree(q, s), U3(q, s)}.
Автор искренне благодарит своего научного руководителя профессора Александра Алексеевича Махнева за постановку задач, внимание, поддержку и ценные замечания.
Автор также выражает признательность всем участникам семинара отдела алгебры и топологии ИММ УрО РАН за полезные замечания и обсуждение результатов диссертации.
Список литературы [1] Буриченко В. П., Махнев А. А. О вполне регулярных локально циклических графах // Соврем. проблемы математики: тез. Междунар. 42-й Всерос. мол. шк.-конф.- Изд-во ИММ УрО РАН. Екатеринбург, 2011.С.181-183.
[2] Буриченко В.П., Махнев А.А. Об автоморфизмах дистанционно регулярного графа с массивом пересечений {15, 12, 1; 1, 2, 15} // Доклады академии наук.-2012.-Т. 445, № 4. C. 375Ц379.
[3] Гаврилюк А.Л., Махнев А.А. Об автоморфизмах дистанционно регулярного графа с массивом пересечений {56, 45, 1; 1, 9, 56} // Доклады академии наук.-2010.-Т. 432, № 5. C. 583Ц587.
[4] Мазуров В.Д. Минимальные подстановочные представления конечных простых классических групп. Cпециальные линейные, симплектические и унитарные группы // Алгебра и логика.-1993.-Т. 32, № 3. C. 267287.
[5] Махнев А.А., Падучих Д.В. О группе автоморфизмов графа Ашбахера // Доклады академии наук.-2009.-Т. 426, № 3. C. 310-313.
[6] Махнев А.А., Падучих Д.В. Об автоморфизмах дистанционно регулярного графа с массивом пересечений {24, 21, 3; 1, 3, 18} // Доклады академии наук.-2011.-Т. 441, № 1. С. 14-18.
[7] Махнев А. А., Падучих Д. В. Об автоморфизмах дистанционно регулярного графа с массивом пересечений {81, 60, 1; 1, 20, 81} // Доклады академии наук.-2010.-Т. 435, № 3. С. 305-309.
[8] Brouwer A.E., Cohen A.M., Neumaier A. Distance-Regular Graphs. Berlin etc: Springer-Verlag. 1989.
[9] Buekenhout F. Diagrams for geometries and groups// J. Combin. Theory.
Ser. A. 1979. Vol. 27. P.121Ц151.
[10] Cameron P.J. Permutation Groups. London Math. Soc. Student Texts №45. Cambridge: Cambridge Univ. Press. 1999.
[11] Cameron P.J., van Lint J.H. Graphs, Codes and Designs. London Math.
Soc. Student Texts №22. Cambridge: Cambridge Univ. Press. 1991.
[12] Conway J., Curtis R., Norton S., Parker R., Wilson R. Atlas of finite groups. Oxford: Clarendon Press, 1985.
[13] Dixon J.D., Mortimer, B. Permutation Groups. Graduate Texts in Mathematics.- Vol.163. Berlin etc: Springer-Verlag. 1996.
[14] Frucht, R. Herstellung von Graphen mit vorgegebener abstrakter Gruppe// Compositio Math. 1938. Vol. 6. P.239Ц250.
[15] Godsil C.D., Liebler R.A., Praeger C.E. Antipodal distance transitive covers of complete graphs // Europ. J. Comb. 1998. Vol. 19, № 4. P. 455478.
[16] Godsil C.D., Hensel A.D. Distance regular covers of the complete graphs // J. Comb. Theory Ser. B. 1992. Vol. 56, P. 205-238.
[17] Higman D.G. Finite permutation groups of rank 3// Math. Z. 1964. Vol.86.
P.145Ц156.
[18] Higman D.G. Primitive rank 3 groups with a prime subdegree// Math. Z.
1966. Vol.91. P.70Ц86.
[19] Higman D.G. Characterization of families of rank 3 permutation groups by the subdegrees I, II// Arch. Math. Basel. 1970. Vol.21.- P.151Ц156;
353Ц361.
[20] Mendelsohn, E. Every (finite) group is the group of automorphisms of a (finite) strongly regular graph// Ars. Combinatoria. 1978. Vol. 6. P.75Ц86.
[21] Neukirch J. Algebraic Number Theory// Grundlehren der mathematischen Wissenschaften. Vol.322. Berlin etc: Springer-Verlag. 1999.
[22] Praeger C.E., Soicher L.H. Low rank representations and graphs for sporadic groups// Lecture series 8. Cambridge: Cambridge Univ. Press.
1997.
[23] Sabidussi G. Graphs with given automorphism group and given graph theoretical properties// Canad. J. Math. 1957. Vol.9. P. 515-525.
[24] Sabidussi G. Vertex-transitive graphs// Monatsh. Math. 1964. Vol.68.
P. 426-438.
[25] Weiss R.M. The nonexistence of 8-transitive graphs// Combinatorica.
1981. Vol.1. P. 309Ц311.
Работы автора по теме диссертации [26] Циовкина Л. Ю. Об автоморфизмах дистанционно регулярного графа с массивом пересечений {42, 39, 1; 1, 3, 42}/ А. А. Махнев, Л. Ю. Циовкина// Алгебра и геометрия: тр. Междунар. конф., посвящ. 80-летию со дня рождения А.И. Старостина.- Изд-во УМЦ-УПИ. Екатеринбург, 2011.- С.112-115.
[27] Циовкина Л. Ю. Об автоморфизмах дистанционно регулярного графа с массивом пересечений {42, 39, 1; 1, 3, 42}/ А. А. Махнев, Л. Ю.
Циовкина// Доклады Академии Наук.- 2011.- Т. 441, №3. С. 305-309.
[28] Циовкина Л. Ю. Об автоморфизмах дистанционно регулярного графа с массивом пересечений {35, 32, 8; 1, 2, 28}/ А. А. Махнев, Л. Ю. Циовкина// Соврем. проблемы математики: тез. Междунар. 43-й Всерос.
мол. шк.-конф.- Изд-во ИММ УрО РАН. Екатеринбург, 2012.- С.69-71.
[29] Циовкина Л. Ю. Об автоморфизмах дистанционно регулярного графа с массивом пересечений {35, 32, 8; 1, 2, 28}/ А. А. Махнев, Л. Ю. Циовкина// Труды Института математики и механики УрО РАН.- 2012.Т. 18, №1. С. 235Ц241.
[30] Циовкина Л. Ю. Об автоморфизмах дистанционно регулярного графа с массивом пересечений {35, 32, 1; 1, 2, 35} / Л.Ю. Циовкина // Алгебра и линейная оптимизация: тез. Междунар. конф., посвящ. 100-летию со дня рождения С.Н. Черникова.- Изд-во УМЦ-УПИ. Екатеринбург, 2012.- С.172-174.
[31] Циовкина Л. Ю. Об автоморфизмах графа с массивом пересечений {35, 32, 1; 1, 2, 35} // Сиб. электрон. матем. изв.- 2012.- Т. 9. С. 285Ц293.
[32] Циовкина Л. Ю. Реберно симметричные дистанционно регулярные накрытия клик с = / А.А. Махнев, Д.В. Падучих, Л.Ю. Циовкина //Теория групп и ее прил.: тез. 9-й Междунар. шк.-конф., посвящ.
90-летию со дня рождения проф. З.И. Боревича.- Изд-во СОГУ. Владикавказ, 2012.- С.86-88.
[33] Циовкина Л. Ю. Реберно симметричные дистанционно регулярные накрытия клик с a1 = c2 / А.А. Махнев, Д.В. Падучих, Л.Ю. Циовкина // Доклады Академии Наук.- 2012.- Т. ???, №?. С. ??-??.
Подписано в печать 24.09.12 Формат 60х84 1/16 Бумага писчая Плоская печать Тираж 100 экз. Заказ Ризография научно-исследовательской части ГОУ ВПО УГТУ-УПИ 620002, г. Екатеринбург, ул. Мира
Авторефераты по всем темам >>
Авторефераты по разным специальностям