Симметричные дистанционно регулярные графы и их автоморфизмы тема диссертации и автореферата по ВАК РФ 01.01.06, кандидат физико-математических наук Циовкина, Людмила Юрьевна

• Циовкина, Людмила Юрьевна
• кандидат физико-математических наук
• 2012

Оглавление диссертации кандидат физико-математических наук Циовкина, Людмила Юрьевна

Введение

1 Определения, обозначения и вспомогательные результаты

1.1 Метод Хигмена и вспомогательные результаты.

1.2 Вспомогательные результаты для случая антиподальных дистанционно регулярных графов диаметра 3.

2 Об автоморфизмах дистанционно регулярных локально циклических графов

2.1 Об автоморфизмах дистанционно регулярного графа с массивом пересечений {42,39,1; 1,3,42}.

2.1.1 Вспомогательные результаты.

2.1.2 Автоморфизмы графа с массивом пересечений

42,39,1; 1,3,42}.

2.1.3 Граф с массивом пересечений {42,39,1; 1,3,42} не является реберно симметричным.

2.2 Об автоморфизмах дистанционно регулярного графа с массивом пересечений {35,32,8; 1,2, 28}.

2.2.1 Вспомогательные результаты.

2.2.2 Автоморфизмы графа с массивом пересечений

35,32,8; 1,2,28}.

2.2.3 Граф с массивом пересечений {35,32,8; 1,2,28} не является реберно симметричным.

2.3 Об автоморфизмах дистанционно регулярного графа с массивом пересечений {35,32,1; 1,2,35}.

2.3.1 Вспомогательные результаты.

2.3.2 Автоморфизмы графа с массивом пересечений

35,32,1; 1,2,35}.

2.3.3 Граф с массивом пересечений {35,32,1; 1,2,35} не является реберно симметричным.

3 Реберно симметричные дистанционно регулярные накрытия клик с Л = д

3.1 Автоморфизмы графа с массивом пересечений г}1 + 1, (г - 1)11,1; 1,}1,г/1+ 1}.

3.2 Случай точного действия Аи^Г) : Е.

3.3 Случай неточного действия Аи1(Г) : Е.

Введение диссертации (часть автореферата) на тему «Симметричные дистанционно регулярные графы и их автоморфизмы»

Одной из центральных проблем в теории конечных групп является поиск единого представления конечных простых групп. В связи с этим, приобрела актуальность задача классификации дистанционно регулярных графов на основе свойств транзитивности их групп автоморфизмов, которой и посвящена настоящая диссертационная работа. В работе исследуются дистанционно регулярные графы диаметра 3 с некоторыми условиями их комбинаторной и групповой симметричности, и их автоморфизмы.

Класс /С графов (под графом здесь и далее будем понимать неориентированный граф без петель и кратных ребер) назовем универсальным, если каждая конечная группа представима группой автоморфизмов некоторого конечного графа из /С. Известный результат Р. Фрухта [14] послужил выделению ряда универсальных подклассов графов, в числе которых оказались следующие: регулярные графы степени к для произвольного фиксированного к > 2, двудольные графы, гамильтоновы графы, ¿-хроматические графы для £ > 1, сильно регулярные графы (регулярные графы, у которых число вершин в пересечении окрестностей любой пары различных вершин зависит только от того, смежны эти вершины или нет)([23],[20]). В [9] Ф. Бюкенхаутом была предложена идея построения единой геометрической теории, согласно которой каждая конечная простая группа была бы представима группой автоморфизмов некоторой геометрической структуры из определенного, поддающегося описанию, класса конечных геометрий. Отметим, что спорадические простые группы Фишера, Судзуки, Маклафлина, Холла-Янко, Рудвалиса и Хигмена-Симса были впервые построены как группы автоморфизмов сильно регулярных графов. Например, Б. Фишер исследовал почти простые группы, порожденные классом 3-транспозиций (сопряженным классом инволюций группы, в котором произведение любых двух элементов имеет порядок < 3), и доказал, что все они являются группами ранга 3 на ассоциированных графах, вершинами которых являются элементы класса 3-транспозиций и две вершины смежны, если соответствующие инволюции коммутируют. Среди таких групп оказались все симметрические группы, некоторые классические (симплектические, ортогональные, унитарные) группы, и три спорадические группы, обнаруженные Фишером в процессе исследования, две из которых (.Рггг, -^23) являются простыми, а -/Р?24 содержит простую группу индекса 2.

Известно, что если С — транзитивная группа подстановок ранга 3 на множестве X и имеет четный порядок, то можно построить граф Г ранга 3 с У"(Г) = X, группа автоморфизмов которого допускает С в качестве подгруппы; к тому же, каждый граф ранга 3 является сильно регулярным графом. Таким образом, внутренняя геометрия целого ряда групп, как показал Фишер, выразима с помощью сильно регулярных графов. Свое развитие теория групп подстановок ранга 3 получила в работах Д. Г. Хигмена ([17]-[19]).

Важным комбинаторным обобщением понятия сильно регулярного графа является понятие дистанционно регулярного графа. Для вершины а графа Г через Г ¿(а) обозначим подграф, индуцированный Г на множестве всех вершин, находящихся на расстоянии г от а. Граф Г диаметра (I называется дистанционно регулярным с массивом пересечений {&о, &ъ • ■ •, Ьсг-ъ сг,., са}, если значения Ъ{(и, ио) = |Гг+1(г/) Г) Г(ги)| и Сг(и, гю) — |Гг1 (гг) П Г(гу)| не зависят от выбора вершин и, т, находящихся на расстоянии г в Г для любого г £ {0,., <!}. Положим аг= Ьо—6«—с^, р, = С2, Л = <21. Заметим, что для дистанционно регулярного графа &о — это степень графа, с\ = 1. Дистанционно регулярный граф диаметра 2 это в точности то же, что и связный сильно регулярный граф (случай несвязного сильно регулярного графа не представляет особого интереса, так как несвязный сильно регулярный граф является объединением изолированных равномощных клик). Введем еще некоторые необходимые определения. Если Г — граф диаметра с1, то через Гг-, где г € {1,., с?}, обозначается граф с тем же множеством вершин, что и Г, в котором две вершины смежны тогда и только тогда, когда они находятся на расстоянии г в Г. Граф Г диаметра (I называется примитивным, если граф Г; связен для любого % е {1,., в противном случае граф Г называется импримитивным. Граф Г диаметра с1 > 1 называется антиподальным, если соответствующий граф Г^ является объединением изолированных клик. Согласно основной теореме Д. Смита, каждый импримитивный дистанционно регулярный граф является двудольным или антиподальным[8].

В диссертационной работе исследуются реберно симметричные дистанционно регулярные графы. Граф назовем реберно симметричным, если его группа автоморфизмов действует транзитивно на множестве его дуг (упорядоченных ребер). Более симметричными объектами (обладающими большими группами автоморфизмов) являются дистанционно транзитивные графы. Граф Г диаметра d называется дистанционно транзитивным, если для любого i 6 {1,., d} группа Aut(r) действует транзитивно на множестве дуг графа (в частности, каждый граф r¿ является реберно симметричным). Легко понять, что каждый дистанционно транзитивный граф является дистанционно регулярным графом. При этом, дистанционно транзитивные графы диаметра 2 суть в точности связные графы ранга 3. Группами автоморфизмов дистанционно транзитивных графов предста-вимы многие конечные простые группы. Необходимо отметить также, что дистанционно регулярные графы и реберно симметричные графы используются в различных приложениях, в том числе, в алгебраической теории кодирования и при моделировании сетей. В связи с этим представляют интерес задача полного описания класса дистанционно транзитивных графов, и связанная с ней задача описания более широкого класса - класса реберно i симметричных дистанционно регулярных графов.

Изучение реберно симметричных графов началось с двух важных работ У. Татта 1947 и 1959 годов о конечных кубических графах. Татт рассмотрел класс графов, группы автоморфизмов которых действуют транзитивно на s-дугах графа, то есть графов с вершинно транзитивной группой автоморфизмов и стабилизатором вершины, действующем транзитивно на множестве исходящих из нее s-дуг (s-дугой называется путь (vq, vs)1 в котором Vi-1 ф Vi+i для любого i € {1,., s — 1}). Как оказалось, для регулярных графов степени 3 с транзитивной на s-дугах группой автоморфизмов, число s не превосходит 5 и граница достигается на графе Татта-Кокстера. Впоследствии Р. Вейсс обобщил результат Татта, доказав, что для регулярных графов произвольной степени к > 3 с транзитивной на й-дугах группой автоморфизмов, число 5 не превосходит 7 и граница достигается на 12-клетке Татта[25].

Г. Сабидусси в работе [24] предложил следующий метод построения всех реберно симметричных графов на основе сравнительно небольшой информации об их группах автоморфизмов, который, в частности, оказался полезным в классификации дистанционно транзитивных графов. Пусть даны неинвариантная подгруппа Н группы б? и элемент д € <7. Через Г = Г (С, Я, НдН) обозначим граф с множеством вершин Я) = {Нх | х е <3} и ребрами {Нх, Ну} такими, что ху~1 € ЯдЯ. Тогда (см. [24] или [15]) (1) если (7 действует точно на Я), Е Н и С = (Я, то Г — связный граф, <7 < Аи1;(Г) и С действует точно и транзитивно на вершинах и на дугах графа Г; (2) если С действует транзитивно на дугах связного графа Е, Н — стабилизатор вершины е б Е, д является 2-элементом и вершины е, е9 смежны в Е, то Е ~ Г(£, Н, НдН), д2 е Я и (7 = (Я, 5).

Большое количество исследований было проведено для класса примитивных дистанционно транзитивных графов, однако, в общем случае описание дистанционно транзитивных графов не завершено. Вместе с тем, задача классификации реберно симметричных дистанционно регулярных графов требует дальнейшего изучения.

Кроме того, проблемой общего характера в теории графов является вопрос существования графов с заданным набором свойств, в частности, в теории дистанционно регулярных графов актуален вопрос о реализуемости массива пересечений, то есть существования графов с заданным массивом пересечений.

Пусть Т — некоторый класс графов. Граф Г назовем локально Т графом, если Г (а) лежит в Т для любой вершины а графа Г. Если при этом класс Т состоит из графов, изоморфных некоторому графу А, то граф Г назовем локально А-графом.

Пусть Г - реберно симметричный граф без изолированных вершин и <2 = АцЦГ) - его группа автоморфизмов. Ясно, что группа (7 действует транзитивно на вершинах графа Г, поэтому Г - локально А-граф. Более того, для каждой вершины а графа Г ее стабилизатор (?а действует транзитивно на окрестности Г (а), поэтому Г (а) является локально Аг(а)-графом. Таким образом, свойство реберной симметричности можно рассматривать как локальное свойство графа.

Локальные комбинаторные и теоретико-групповые свойства в некоторых случаях влияют на глобальную структуру графа (яркими примерами тому являются вышеупомянутые теоремы Татта и Вейсса), но степень этого влияния не всегда поддается полному анализу. При этом, для дистанционно регулярных графов удается найти простые делители порядков их групп автоморфизмов и подграфы неподвижных точек для автоморфизмов простых порядков с помощью теории характеров конечных групп (с применением метода Гр. Хигмена), что может быть полезным при построении или в доказательствах несуществования дистанционно регулярных графов с заданными локальными свойствами.

Граф назовем локально циклическим, если окрестность каждой его вершины является объединением изолированных циклов. Например, граф

Шрикханде это единственный сильно регулярный локально Сб-граф на 16 вершинах с Л = ß = 2. Граф Шрикханде является реберно симметричным графом, к тому же, это граф наименьшего порядка, который является дистанционно регулярным, но не дистанционно транзитивным [8].

Одним из вопросов, рассматриваемых в диссертации, является вопрос существования реберно симметричных дистанционно регулярных локально циклических графов.

В работе используется следующий важный результат A.A. Махнева и В.П. Буриченко о дистанционно регулярных локально циклических графах.

Предложение 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) Г — антиподальный граф с ¡1 — 2 и массивом пересечений

2 г + 1,2 г- 2,1; 1,2,2 г + 1}, г € {3,4,., 21} - {10,16} и v = 2 г (г + 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, А;}, является г-накрытием (А;+1)-клики и для параметров г, Л, к справедливо тождество к — 1 — г/2 = Х — {I. Положим 5 = \ — ц. В [16] доказано, что для фиксированных г, 5 имеется лишь конечное число допустимых массивов, кроме случаев 5 € {—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 тезисы - тремя авторами (Махнев A.A., Падучих Д.В., Циовкина Л.Ю.), остальные - в соавторстве с Махневым A.A. Все совместные работы написаны в нераздельном соавторстве.

Структура и объем работы. Работа состоит из введения, трех глав и списка цитированной литературы, содержащего 33 наименования. Общий объем диссертации составляет 80 страниц.

Список литературы диссертационного исследования кандидат физико-математических наук Циовкина, Людмила Юрьевна, 2012 год

1. Буриченко В. П., Махнев A.A. О вполне регулярных локально циклических графах // Соврем, проблемы математики: тез. Междунар. 42-й Всерос. мол. шк.-конф.- Изд-во ИММ УрО РАН. Екатеринбург, 2011.-С.181-183.

2. Буриченко В.П., Махнев A.A. Об автоморфизмах дистанционно регулярного графа с массивом пересечений {15,12,1; 1,2,15} // Доклады академии наук.-2012.-Т. 445, № 4. С. 375-379.

3. Гаврилюк A.J1., Махнев A.A. Об автоморфизмах дистанционно регулярного графа с массивом пересечений {56,45,1; 1,9,56} // Доклады академии наук.-2010.-Т. 432, № 5. С. 583-587.

4. Мазуров В.Д. Минимальные подстановочные представления конечных простых классических групп. Специальные линейные, симплектиче-ские и унитарные группы // Алгебра и логика.-1993.-Т. 32, № 3. С. 267287.

5. Махнев A.A., Падучих Д.В. О группе автоморфизмов графа Ашбахера // Доклады академии наук.-2009.-Т. 426, № 3. С. 310-313.

6. Махнев A.A., Падучих Д.В. Об автоморфизмах дистанционно регулярного графа с массивом пересечений {24,21,3; 1,3,18} // Доклады академии наук.-2011.-Т. 441, № 1. С. 14-18.

7. Махнев A.A., Падучих Д.В. Об автоморфизмах дистанционно регулярного графа с массивом пересечений {81,60,1; 1,20,81} // Доклады академии наук.-2010.-Т. 435, № 3. С. 305-309.

8. Brouwer А.Е., 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; 353361.

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}/ А. А. Махнев, JI. Ю. Циовкина// Доклады Академии Наук.- 2011.- Т. 441, №3. С. 305-309.

27. Циовкина J1. Ю. Об автоморфизмах дистанционно регулярного графа с массивом пересечений {35,32,8; 1,2,28}/ А. А. Махнев, JI. Ю. Циовкина// Труды Института математики и механики УрО РАН,- 2012 Т. 18, №1. С. 235-241.

28. Циовкина JI. Ю. Об автоморфизмах графа с массивом пересечений {35,32,1; 1,2,35} // Сиб. электрон, матем. изв.- 2012,- Т. 9. С. 285-293.

29. Циовкина Л. Ю. Реберно симметричные дистанционно регулярные накрытия клик с А = /2 / A.A. Махнев, Д.В. Падучих, Л.Ю. Циовкина // Доклады Академии Наук,- 2012,- С. .