Локальное строение и автоморфизмы реберно регулярных графов

Мы рассматриваем неориентированные графы без петель и кратных ребер. Если а, Ъ — вершины графа Г, то через с?(а, 6) обозначим расстояние между, а и Ь, а через Г^(а) — подграф, индуцированный Г на множестве всех вершин графа Г, которые находятся на расстоянии г от вершины а. Подграф Гх (а) будем называть окрестностью вершины, а и обозначать через [а]. Через а1 обозначим подграф, индуцированный {a} U [а].

Степенью вершины называется число вершин в ее окрестности. Граф Г называется регулярным степени к, если степень любой вершины, а графа Г равна к. Число вершин в [а] П [Ь] обозначим через А (а, Ь) (д (а, Ь)), если d (a, b) = 1 (с?(а, Ь) = 2), а соответствующий подграф назовем (fi-) А-подграфом. Граф Г назовем реберно регулярным с параметрами (и, к, А), если он содержит v вершин, регулярен степени к, и каждое его ребро ab лежит в, А треугольниках. Граф Г — вполне регулярный граф с параметрами (v, к, А, /л), если он реберно регулярен с соответствующими параметрами и [а] П [6] содержит /I вершин для любых двух вершин а, 6, находящихся на расстоянии 2 в Г. Вполне регулярный граф называется сильно регулярным графом, если он имеет диаметр 2.

Через Кти., 5ТПп обозначим полный n-дольный граф, с долями порядков mi, ., тп. Если т =. = mn = т, то соответствующий граф обозначается через Кпхт. Треугольным графом Т{т) называется граф с множеством неупорядоченных пар из X в качестве вершин, Х = т и пары {а, 6}, {с, d} смежны тогда и только тогда, когда они имеют общий элемент. Граф на множестве вершин X х Y называется m х п решеткой, если Х = т, |У| = п и вершины (xi, yi), (2:2, У2) смежны тогда и только тогда, когда Xi = Х2 или у = у2. Если вершины u, w находятся на расстоянии г в Г, то через bi (u, w) (чрез Ci (u, w)) обозначим число вершин в пересечении Гi+i (u) (в пересечении rji (tt)) с [w]. Заметим, что в реберно регулярном графе с параметрами г>, к, А) значение bi (и, и-) не зависит от выбора ребра {и, w} и равно Лг — Л — 1.

В связи с завершением классификации конечных простых групп возникла задача единого представления конечных простых групп. Перспективным направлением является поиск такого класса конечных геометрий, что каждая конечная простая группа действует флаг-транзитивно на некоторой геометрии и все геометрии этого класса допускают классификацию [15—18, 20, 31, 32]. Например, класс билдингов Титса характеризует группы Лиевского типа [36]. Позднее в этом направлении возникли задачи, не связанные с групповым действием, в частности, такой является задача классификации дистанционно регулярных графов [1,15].

Пусть G — транзитивная группа подстановок на множестве П. Если подгруппа Gp группы G, состоящая из всех подстановок, фиксирующих точку р? Q, имеет г орбит, то говорят, что G является группой ранга г. Пусть г — 3 и соответствующие 3 орбиты — это {р}, А (р), Г (р). Тогда по группе G удается построить сильно регулярный граф Г, множество вершин которого — fz и две вершины р, q смежны в Г, если р € Д (<?) [14].

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

Граф Г диаметра d называется дистанционно транзитивным, если для любого г Е {0,., d} и для любых вершин и, v, х, у, таких что d (u, v) = d (x, у) = г, существует автоморфизм д графа Г: (u, v)9 = (х, у). Дистанционно транзитивные графы диаметра 2 (графы ранга 3) сыграли важную роль в классификации конечных простых групп. Около половины спорадических групп были построены как группы автоморфизмов графов ранга 3 [31].

Если вершины u, w находятся на расстоянии г в Г, то через bi (u, w) (через c-(u, w)) обозначим число вершин в пересечении Гг+1(и) (в пересечении Гг-1(^)) с [w]. Дистанционно регулярным графом называется граф, в котором параметры w) и c-(u, w) не зависят от вершин u, w, а зависят только от расстояния на котором эти вершины находятся в графе Г.

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

В диссертации исследуются строение реберно регулярных графов с к > 3&i — 1 и возможные автоморфизмы некоторых сильно регулярных графов.

Результаты работы докладывались на Международной алгебраической конференции, посвященной 70-летию А. И. Старостина и 80-летию Н. Ф. Сесекина, на Международной алгебраической конференции, посвященной 250-летию Московского госуниверситета, на 34-й и 36-й Региональных молодежных конференциях ИММ УрО РАН, на алгебраических семинарах Института математики и механики УрО РАН.

Диссертация состоит из введения, трех глав и списка литературы (43 наименования).

1. Баннаи Э., Ито. Т. Алгебраическая комбинаторика. Схемы отношений: Пер. с англ.-М.: Мир, 1987.-375 е., ил.

2. Браувер А. Е. Ван Линт Дж. Сильно регулярные графы.//Кибернетический сборник: Вып. 23. Сборник статей: Пер. с англ. -М.: Мир, 1987. С. 160−186.

3. Донских Е. Н., Махнев А. А. О реберно регулярных графах с bi = 4 // Проблемы теор. и приклад, матем. Труды регион, молод, конф. Екатеринбург 2002, 18−19.

4. Зрипов С. Р., Махнев А. А., Яблонко И. П. О сильно регулярных графах без треугольников // Алгебра и линейная оптимизация. Труды межд. семинара, Екатеринбург, УрО РАН 2002, 117−121.

5. Махнев А. А. О сильной регулярности некоторых реберно регулярных графов // Известия РАН, сер. матем. 2004, т. 68, С. 159−172.

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

7. Махнев А. А. Реберно регулярные графы, в которых каждое ребро лежит в большом числе треугольников // Дискр. анализ и исслед. операций 1995, т. 2, № 4, 42−53.

8. Махнев А. А., Белоусов И. Н., Гурский Е. И., Дергач А. С. О почти хороших парах в реберно регулярных графах // Проблемы теор. и приклад, матем. Труды регион, молод, конф. Екатеринбург 2004, 25−26.

9. Махнев А. А., Дрожевский А. В., Ищенко П. В., Паметов П. Ю. О почти хороших парах вершин в реберно регулярных графах // Проблемы теор. и приклад, матем. Труды регион, молод, конф. Екатеринбург 2003, 25−26.

10. Махнев А. А., Минакова И. М. Об одном классе реберно регулярных графов // Известия Гомельского госуниверситета, Вопросы алгебры 2000, т. 3 (16), 145−154.

11. Махнев А. А., Падучих Д. В. Об автоморфизмах графа Ашбахера //Алгебра и логика 2001, т. 40, № 2, 125−134.

12. Хестенс М. Д., Хигмэн Д. Г. Группы ранга 3 и сильно регулярные графы.// Кибернетический сборник: Новая серия, вып. 23. Сборник статей: Пер с англ.-М.: Мир, 1986. С.131−152.

13. Холл. М. Комбинаторика. М:-Изд-во" Мир", 1970, 424 с.

14. Юбо К. Сильно регулярные графы.//Кибернетический сборник: Вып. 24. Сборник статей: М.: Мир, 1987. С. 160−186.

15. Brouwer А.Е., Cohen A.M., Neumaier A. Distance-regular graphs // Berlin etc: Springer-Verlag 1989.

16. Brouwer A. E., Willbrink H. A. Block designs. //Handbook of incidence geometry: buildings and foundations/F. Buekenhout.—Elsever Science, Amsterdam, 1995, P. 349−383.

17. Brouwer A.E., Haemers W.H. The Gewirtz graph: an exercize in the theory of graph spectra // Europ. J. Comb. 1993, v. 14, 397−407.

18. Buekenhout F. Foundations of incidence geometry.//Handbook of incidence geometry: buildings and foundations/F. Buekenhout.— Elsever Science, Amsterdam, 1995, P. 63 107.

19. Buekenhout F, Cameron P. Projective and affine geometry over division rings.//Handbook of incidence geometry: buildings and foundations/F. Buekenhout. Elsever Science, Amsterdam, 1995, P. 27 — 63.

20. Buekenhout F, Pasini P. Finite diagram geometries extending buildings.// Handbook of incidence geometry: buildings and foundations/F. Buekenhout.— Elsever Science, Amsterdam, 1995, P. 1143 — 1255.

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

22. Cameron P., Van Lint J. Designs, Graphs, Codes and their Links. London Math. Soc. Student Texts 22, 1981. Cambr. Univ. Press. 240 pp.

23. Cohen A.M. Point line spaces related to buildings.//Handbook of incidencegeometry: buildings and foundations/F. Buekenhout.— Elsever Science, Amsterdam, 1995, P. 647−739.

24. Higman D. G. Finite permutation groups of rank 3. — Math. Z., 1964, v. 86, p. 145 156.

25. Higman D. G. Primitive rank 3 groups with a prime subdegree. — Math. Z., 1966, v. 91, p. 70 86.

26. Higman D. G. Intersection matricies for finite permutation groups.— J. Algebra, 1967, v. 6, p. 22 42.

27. Higman D. G. On finite affine planes of rank 3. — Math. Z., 1968, v. 104, p. 147 149.

28. Higman D. G. A survey of some questions and resalts about rank 3 permutation groups.— Actes, Cjngres Int. Math. Rome, 1970, v. 1, p. 361 — 365.

29. Higman D. G. Characterization of families of rank 3 permutation groups by the subdegrees I, II, — Arth. Math., 1970, v. 21, p. 151 156- 353 — 361.

30. Higman D. G. Coherent configurations. — Rend. Sem. Mat. Univ. Padova, 1970, v. 44, p. 1 26.

31. Prager С. E., Soicher L. H. Low rank representations and graphs for sporadic groups. Lecture series 8. Cambridge, University press, 1997.

32. Numata M. On a characterization of a class of regular graphs // Osaka J. Math. 1974, v. 11, 389−400.

33. Nakagawa N. On strongly regular graphs with parameters (к, 0, 2) and their antipodal double cover // Hokkaido Math. Soc. 2001, v. 30, 431−450.

34. Thas J. A. Generalized polygons.//Handbook of incidence geometry: buildings and foundations/F. Buekenhout.— Elsever Science, Amsterdam, 1995, P. 383— 433.

35. Thas J. A. Projective geometry over a finite field.//Handbook of incidence geometry: buildings and foundations/F. Buekenhout.— Elsever Science, Amsterdam, 1995, P. 295−349.

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

37. Willbrink H. A., Brouwer A. E. A (57, 14, 1) strongly regular graph does not exist// Proc. Kon. Nederl. Akad. Ser. A, 1983. Vol. 45, N 1. P. 117−121.РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ.

38. Махнев А. А., Веденев А. А. Кузнецов А.Н., Носов В. В. О хороших парах в реберно регулярных графах // Дискрет, матем. 2003, т. 15, 77−97.

39. Махнев А. А., Веденев А. А. Кузнецов А.Н., Носов В. В. О хороших парах в реберно регулярных графах // Тез. докладов международного семинара по теории групп по-священного 70-летию А. И. Старостина и 80-летию Н. Ф. Сесекина, Екатеринбург, 2001. С. 139−140.

40. Махнев А. А., Носов В. В. Об автоморфизмах графов с Л = 0, д = 2.//Математический сборник. Том 195, № 3, 2004, С. 47−68.

41. Махнев А. А., Носов В. В. Об автоморфизмах графов с, А = 0, д = 2.// Проблемы теоретической и прикладной математики: труды 34-й Региональной молодежной конференции. Екатеринбург: УрО РАН, 2003. С. 41−44.

42. Махнев А. А., Носов В. В. Об автоморфизмах графов Крейна без треугольников. // Международная алгебраическая конференция, посвященная 250-летию Московского университета. Тезисы докладов. М.:Изд.-во механико-математической литературы. МГУ, 2004 г.С.89−91.

43. Носов В. В. Об автоморфизмах графа с параметрами (704, 37,0,2) //Проблемы теоретической и прикладной математики: Труды 36-й Регион, молод, конф. Екатеринбург: УрО РАН, 2005. С 55−60.