Симметричные графы и их автоморфизмы тема диссертации и автореферата по ВАК РФ 01.01.06, кандидат физико-математических наук Гутнова, Алина Казбековна

• Гутнова, Алина Казбековна
• кандидат физико-математических наук
• 2011

Оглавление диссертации кандидат физико-математических наук Гутнова, Алина Казбековна

Введение

1 О графах, в которых окрестности вершин являются псевдогеометрическими графами для рС«,-2(3, £)

1.1 Предварительные результаты.

1.2 Сильно регулярный случай.

1.3 Графы диаметра 3, в которых окрестности вершин изоморфны

2 Графы, в которых окрестности вершин — псевдогеометрические графы для 3,3)

2.1 Предварительные результаты.

2.2 Локально псевдо С<5(3,3)-графы.

3 Графы, в которых окрестности вершин — псевдогеометрические графы для 3, 5)

3.1 Предварительные результаты.

3.2 Локально псевдо 3, 5)-графы.

3.3 Случай ¡1 =

3.4 Случай /х =

4 Автоморфизмы графа с параметрами (245,64,18,16)

4.1 Предварительные результаты.

4.2 Автоморфизмы графа с параметрами (245, 64,18,16)

4.3 Автоморфизмы малых порядков.

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

Для единого представления конечных простых групп перспективным направлением является поиск такого класса конечных геометрий, что каждая конечная простая группа действует флаг-транзитивно на некоторой геометрии и все геометрии этого класса допускают классификацию [1]. Например, класс билдингов Титса характеризует группы лиева типа [15]. Позднее в этом направлении возникли задачи, не связанные с групповым действием. В частности, такой является задача классификации дистанционно регулярных графов [16].

Пусть С — транзитивная группа подстановок на множестве Если стабилизатор точки р £ П, имеет г орбит на П, то говорят, что С имеет подстановочный ранг г. Пусть г = 3 и соответствующие три орбиты — это {р}, А(р), Г(р). Тогда по группе С удастся построить сильно регулярный граф Г, множество вершин которого О и две вершины р, д смежны в Г, если <7 е г(р) [17].

Д. Хигмеи ([17]-[21]) развил теорию групп ранга 3. Эти группы являются группами автоморфизмов сильно регулярных графов, причем они действуют транзитивно как на множествах вершин и ребер, так и на множестве пар различных несмежных вершин. Такие графы являются дистанционно транзитивными графами диаметра 2.

В настоящее время при исследовании графов вовлекаются симметрии все более общего вида.

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

Подграф 1\(а) называется окрестностью вершины а и обозначается через [а]. Через а-1 обозначается подграф, являющийся шаром радиуса 1 с центром а.

Граф Г называется регулярным графом степени к, если [а] содержит точно к вершин для любой вершины а из Г.

Граф Г называется реберно регулярным графом с параметрами (у,к,\), если Г содержит у вершин, является регулярным степени /г, и каждое ребро из Г лежит в Л треугольниках.

Граф Г называется вполне регулярным графом с параметрами (у, к, А,/и), если Г реберно регулярен с соответствующими параметрами и подграф [а] П [Ь] содержит 11 вершин в случае й{а, Ъ) = 2. Сильно регулярным графом с параметрами (у, к, А, ц) называется реберно регулярный граф с параметрами (у, к, Л), в котором любые две несмежные вершины и,и) Е Г имеют ровно ¡1 общих соседей.

Число вершин в [а] П [Ъ] обозначим через А(а, Ь), если й(а,Ъ) — 1, а соответствующий подграф назовем \-подграфом.

Если (1(а,Ь) = 2, то число вершин в [а] П [6] обозначим через ¿¿(а, Ь), а соответствующий подграф назовем ¡1- подграфом.

Если вершины и, и) находятся на расстоянии г в Г, то через ¿»¿(гл, т) (через Сг(и, и))) обозначим число вершин в пересечении Гг+1(и) (Гг1(^)) с Г(ги). Заметим, что в реберно регулярном графе число Ъ\{и,и)) не зависит от выбора смежных вершин и, У) и обозначается через б^Граф Г диаметра 6, называется дистанционно регулярным с массивом пересечений {&о, 2>1,., Ьс1-и С1,., Ог}, если значения Ь((и, ги) и сг-(п, гу) не зависят от выбора вершин и, w на расстоянии г в Г для любого г — 0,., d.

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

Через -Кть.,тп обозначим полный многодольный граф {Mi,., Мп} с долями Mi порядка rrii. Если mi = . - - = тпп = тп, то указанный граф обозначается Кп ХШ'

Система инцидентности с множеством точек Р и множеством прямых С называется а-частичной геометрией порядка (s,t), если каждая прямая содержит ровно s +1 точек, каждая точка лежит ровно на t + 1 прямой, любые две точки лежат не более чем на одной прямой и для любого антифлага (а, L) G (Р, С) найдется точно а прямых, проходящих через а и пересекающих L (обозначение pGa(s,t) или pGa). В случае а = 1 геометрия называется обобщенным четырехугольником и обозначается GQ(s,t). Точечный граф геометрии определяется на множестве точек Р и две точки смежны, если они лежат на прямой. Точечный граф геометрии pGa(s,t) сильно регулярен с v = (s + 1)(14-st/а), k — s(t+ 1), Л = s — 1 -\-t(a — a(t + 1). Сильно регулярный граф с такими параметрами называется псевдогеометрическим графюлi для pGa(s,t) или псевдо pGa(s, ¿)-графом.

A.A. Махневым предложена программа классификации связных вполне регулярных графов, в которых окрестности вершин изоморфны сильно регулярному графу А с собственным значением 2. Эта программа основана на получении границы для диаметра таких графов с помощью теоремы Смита (см. теорему 3.2.5 [16]).

Цель диссертации. Целью данной работы является решение следующих задач:

1. Провести редукцию классификации вполне регулярных графов, у которых окрестности вершин - псевдогеометрические графы для к локально псевдо (7(2(3, 3)- и С(5(3, 5)-графам.

2. Изучить вполне регулярные локально псевдо (?<3(3, 3) и 5)-графы.

3. Найти возможные автоморфизмы сильно регулярного графа с параметрами (245,64,18,16).

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

Научная новизна. Основные результаты, полученные в работе, являются новыми. Выделим из них следующие.

1. Получена граница для диаметра графов, у которых окрестности вершин - псевдо геометрические графы для рС8-2(3^).

2. Получены возможные параметры вполне регулярных графов, у которых окрестности вершин - псевдогеометрические графы для 2(5, в случаях, когда диаметр графа равен 2, 3 или 4.

3. Найдены возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярного графа Г с параметрами (245,64,18,16).

Теоретическая и практическая ценность. Работа носит теоретический характер. Результаты продолжают изучение реберно регулярных графов и их автоморфизмов. Результаты и методы диссертации могут быть использованы для изучения графов и конечных геометрий подобного типа.

Апробация работы. Основные результаты работы докладывались: на Международной алгебраической конференции, посвященной 80-летию со дня рождения А.И. Кострикина (Нальчик, 2009 г.), на международной конференции "Мальцевские чтения"(Новосибирск, 2010 г.), на VIII международной школе-конференции по теории групп (Нальчик, 2010 г.) и на 42-й Всероссийской молодежной конференции "Современные проблемы математики" (Екатеринбург, 2011 г.).

Результаты работы докладывались и обсуждались на алгебраических семинарах ИММ УрО РАН.

Публикации. Основные результаты диссертации опубликованы в работах [23]—[30]. Работы [23]—[29] выполнены в нераздельном соавторстве с A.A. Мах-невым.

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

Список литературы диссертационного исследования кандидат физико-математических наук Гутнова, Алина Казбековна, 2011 год

1. Buekenhout, F. Locally polar spaccs and related rank 3 groups /' F. Buekenhout, X. Hubaut// J. Algebra 1977, v. 45. P.391-434.

2. Cameron, P. Extended generalized quadrangles/ P.J. Cameron, D.R. Hughes, A. Pasini// Geom. Dedic. 1990, v. 35, P.193-228.

3. Cameron, P.J. Permutation Groups/ P.J. Cameron// London Math. Soc. Student Texts 45, Cambridge Univ. Press. 1999.

4. Hobart, S.A. EpGs with minimal II/ S.A. Hobart, D.R. Hughes// Geom. Dedic. 1992, v. 42, P.129-138.

5. Hobart, S.A. Extended partial geometries: nets and dual nets/ S.A. Hobart, D.R. Hughes// Europ. J. Comb. 1990, v. 11, P.357-372.

6. Махнев, А.А. О графах, в которых окрестности вершин являются графами, дополнительными к графу Зейделя/ M.JI. Карданова, А.А. Махнев// Дискр. матем. 2009, т. 3, N 3, С.71-83.

7. Neumaier, A. Strongly regular graphs with smallest eigenvalue — m/ A. Neumaier// Arch. Math. 1979, v. 33, P.392-400.

8. Махнев, A.A. О расширениях частичных геометрий, содержащих малые ¡л-подграфы/ А.А. Махнев// Дискр. анализ и исслед. операций 1996, т. 3, N 3, С.71-83.

9. Махнев, А.А. Об автоморфизмах дистанционно регулярного графа с массивом пересечений {56,45,1; 1, 9, 56}/ А.Л. Гаврилюк, А.А. Махиев// Доклады Академии наук 2010, т.432, N 5, С.512-515.

10. Brouwer, A.E. Distance-Regular Graphs/ A.E. Brouwer, A.M. Cohen, A. Neumaier// Berlin etc: Springer-Verlag 1989, 495 p.

11. Haemers, W. The pseudo-geometric graphs for generalized quadrangles of order (3,t)/ W. Haemers, E. Spence// Eur. J. Comb. 2001, v. 22, N 6, P.839-845.

12. Behbahani, M. Strongly regular graphs with nontrivial automorphisms/ M. Behbahani, C. Lam// Discrete Math. 2011, v. 311, P.132-144.

13. Tits, J. Buildings of Spherical Type and finite BN-pairs/ J. Tits// Springer Lecture Notes in Mathematics.- Vol.386.

14. Brouwer, A.E. Distance-regular graphs/ A.E. Brouwer, A.M. Cohen, A. Neumaier// Berlin etc: Springer-Verlag.- 1989,- 495 c.

15. Higman, D.G. Finite permutation groups of rank 3/ D.G. Higman// Math. Z.- 1964.- Vol.86.- P.145-156.

16. Higman, D.G. Primitive rank 3 groups with a prime subdegrce/ D.G. Higman/'/ Math. Z.- 1966.- Vol.91.- P.70-86.

17. Higman, D.G. Intersection matrices for finite permutation groups/' D.G. Higman// J. Algebra.- 1967.- Vol.6.- P.22-42.

18. Higman, D.G. On finite affine planes of rank 3/ D.G. Higman// Math. Z-1968,- Vol.104.- P. 147-149.

19. Higman, D.G. A survey of some questions and results about rank 3 permutation groups/ D.G. Higman// Actes, Cjngres Int. Math. Rome 1970.-Vol.l.- P.361-365.

20. Кабанов, B.B. О сильно регулярных графах с собственным значением 2 и их расширениях/ В.В. Кабанов, A.A. Махнев, Д.В. Падучих// Доклады Академии наук 2010.- Т.431. - N5, апрель. С.583-586.Работы автора по теме диссертации

21. Гутнова, А.К. О графах, в которых окрестности вершин являются псевдогеометрическими графами для pGs-2(s, t) / А.К. Гутнова, A.A. Махнев // Доклады Академии наук 2010, т. 431, N 3, С.300-304.

22. Гутнова, А.К. Графы, в которых окрестности вершин — псевдогеометрические графы для GQ(3,3) / А.К. Гутнова, A.A. Махнев // Тезисы международной конференции "Мальцевские чтения", посвященной 70-летию академика Ю.Л.Ершова, Новосибирск 2010, С.72.

23. Гутнова, A.K. Графы, в которых окрестности вершин — псевдогеометрические графы для GQ{3, 3) / A.K. Гутнова, A.A. Махнев // Доклады Академии наук 2010, т. 433, N 6, С.727-730.

24. Гутнова, А.К. Об автоморфизмах сильно регулярного графа с параметрами (245,64,18,16) / А.К. Гутнова, А.А.Махнев // Труды 42-й Всероссийской молодежной конференции "Современные проблемы математики". Екатеринбург 2011, С.195-197.

25. Гутнова, А.К. Графы, в которых окрестности вершин — псевдогеометрические графы для GQ(3,5) / А.К. Гутнова, A.A. Махнев // Доклады Академии наук 2011, т. 438, N 5, С.595-598.

26. Гутнова А.К. Об автоморфизмах сильно регулярного графа с параметрами (245,64,18,16) / А.К. Гутнова // Сибирские электронные матем. известия,- 2011.- Т. 8.- С.4-18.