Симметричные графы и их автоморфизмы

Для единого представления конечных простых групп перспективным направлением является поиск такого класса конечных геометрий, что каждая конечная простая группа действует флаг-транзитивно на некоторой геометрии и все геометрии этого класса допускают классификацию [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 стр.

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.