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

• Нирова, Марина Сефовна
• кандидат физико-математических наук
• 2007

Оглавление диссертации кандидат физико-математических наук Нирова, Марина Сефовна

Введение.

Глава 1. Регулярные графы с малыми значениями

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

§ 1.2. Почти хорошие тройки в реберно регулярных графах.

§ 1.3. Сильно регулярные графы с b\ < 18.

§ 1.4. Вполне регулярные графы с Ъ\ < 5.

Глава 2. Узкие частичные четырехугольники и их автоморфизмы.

§ 2.1. Параметры узких частичных четырехугольников.

§ 2.2. Автоморфизмы сильно регулярного графа с (400,21,2,1).

Глава 3. Однородные расширения частичных геометрий.

§ 3.1. О s-однородных расширениях геометрий pGa(s,t).

§ 3.2. Сильно (s—1)-однородные расширения геометрийpGa(s,t). Литература

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

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

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

Через -K"mi,.,m„ обозначим полный n-дольный граф, с долями порядков mi, ., тп. Если mi = . = тп = ш, то соответствующий граф обозначается через Кпхт. Треугольным графом Т(т) называется граф с множеством неупорядоченных пар из X в качестве вершин, \Х\ = т и пары {a,b},{c,d} смежны тогда и только тогда, когда они имеют общий элемент. Граф на множестве вершин X х Y называется т х п решеткой, если |Х| = т, \Y\ = п и вершины (xi,yi), (£2,2/2) смежны тогда и только тогда, когда х\ = Х2 или yi = у2.

Графом Джонсона J(n,m) называется граф, вершинами которого являются m-элементные подмножества данного n-элементного множества, причем две вершины а, b смежны, только если \а П b\ = т — 1. Граф Пэ-ли P(q) в качестве вершин имеет элементы поля Fq, q = 1 (mod 4), и две вершины а, Ь смежны, только если Ъ — а является ненулевым квадратом в Fq. Граф Петерсена — это дополнительный граф для треугольного графа Т{5) (он имеет параметры (10,3,0,1)). Граф Клебша (Шлефли) — это единственный сильно регулярный граф с параметрами (16,10,6,6) (с параметрами (27,16,10,8)). Граф Шрикханде — это единственный сильно регулярный локально шестиугольный граф с параметрами (16,6,2,2). Имеется точно 3 сильно регулярных графа, имеющих параметры графа Т(8), но не изоморфных Т(8). Эти графы называются графами Чанга. Графом Хофмана-Синглтона называется единственный сильно регулярный граф с параметрами (50,7,0,1). Графом Хигмена-Симса называется единственный сильно регулярный граф с параметрами (100,22,0,6).

Частичной геометрией pGa(s,t) называется система инцидентности, состоящая из точек и прямых, в которой каждая прямая содержит s + 1 точку, каждая точка лежит на t + 1 прямой (две прямые пересекаются не более, чем по одной точке) и для любой точки а, не лежащей на прямой L, найдется точно а прямых, проходящих через а и пересекающих L. Если а = 1, то геометрия называется обобщенным четырехугольником и обозначается GQ(s,t). Если а = t, то геометрия называется сетью. Точечным графом частичной геометрии называется граф, вершинами которого являются точки геометрии, и две различные вершины смежны, если они лежат на одной прямой. Легко понять, что точечный граф частичной геометрии pGa(s,t) сильно регулярен с параметрами v = (s+l)(l-t-st/a), k = s(t+l), A = (s — 1) + (a — 1 )t, fi = a(t +1). Любой сильно регулярный граф с такими параметрами для некоторых a, s, t называется псевдогеометрическим графом для pGa(s,t).

Множество вершин графа MZ(n), отвечающего аффинной плоскости 7г = (X, С) порядка п, совпадает с X U С, причем подграф X является кокликой, точка смежна с прямой, только если она принадлежит этой прямой и две прямые смежны, если они не пересекаются. Граф MZ(n) имеет п(2п + 1) вершин, является кореберно регулярным с ц = 1, причем Х(а,Ь) = 0, если одна из этих вершин — точка, а другая — содержащая эту точку прямая, A (a, b) = п — 2, если а и Ъ — параллельные прямые.

Частичным четырехугольником PQ(s,t:/j,) называется система инцидентности, состоящая из точек и прямых, в которой каждая прямая содержит s + 1 точку, каждая точка лежит на t + 1 прямой (две прямые пересекаются не более, чем по одной точке) и для любых двух несмежных точек пересечение их окрестностей в точечном графе является //-кокликой. Точечный граф частичного четырехугольника PQ(s, t, ц) сильно регулярен с параметрами v = 1 + s(t + 1) + s2t{t + 1)//х, k = s(t + 1) и A = s — 1. Частичный четырехугольник назовем узким, если t < 6.

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

Если вершины и, w находятся на расстоянии i в Г, то через Ьг-(и, w) (через C{(u,w)) обозначим число вершин в пересечении ri+i(u) (в пересечении Гг1(и)) с [и;]. Дистанционно регулярным графом называется граф диаметра d, в котором для любого г 6 {0,1,d} параметры b{(u, w) и Ci(u, w) не зависят от выбора вершин и, w, а зависят только от расстояния между этими вершинами в графе Г.

Заметим, что в реберно регулярном графе с параметрами (v, к, А) значение b\(u, w) не зависит от выбора ребра {и, w} и равно к — А — 1.

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

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

Д.Хигмен [30-34] развил теорию групп ранга 3. Эти группы являются группами автоморфизмов сильно регулярных графов, т. е. дистанционно транзитивных графов диаметра 2.

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

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

В диссертации получено описание вполне регулярных графов с Ь\ < 5 и найдены параметры сильно регулярных графов с Ь\ < 18; изучены узкие частичные четырехугольники и доказано, что сильно регулярный граф с параметрами (400,21,2,1) не является вершинно транзитивным; классифицированы s-однородные и сильно (s — 1)-однородные расширения частичных геометрий pGa(s, t).

Результаты работы докладывались на Международной алгебраической конференции, посвященной 70-летию JT.H. Шеврина (Екатеринбург, 2005), на Международных конференциях "Мальцевские чтения" (Новосибирск, 2005 и 2006), на Международной школе-конференции по теории групп, посвященной 75-летию со дня рождения А.И. Старостина (Приэльбрусье, 2006), на 37-й и 38-й Региональных молодежных конференциях ИММ УрО РАН, на алгебраических семинарах Института математики и механики УрО РАН.

Основные результаты опубликованы в работах [13-19]. Работы [13-18] были написаны в нераздельном соавторстве с Махневым А.А.

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

Список литературы диссертационного исследования кандидат физико-математических наук Нирова, Марина Сефовна, 2007 год

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

2. Белоусов И.Н., Махнев А А. О почти хороших парах вершин в реберно регулярных графах // Известия Урал. гос. ун-та, Екатеринбург 2005, N 7, 35-48.

3. Васильев С.А., Махнев А.А. О вполне регулярных графах с Ъ\ = 4 // Известия Гомельского гос. ун-та, Гомель 2006, 101-108.

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

5. Зарипов С.Р., Махнев А.А., Яблонко И.П. Реберно регулярные графы диаметра 2сА > 2&/3 — 2 // Труды Украинского матем. конгресса, Киев 2001, секция 1: Алгебра и теория чисел, Институт математики НАН Украины, Киев 2003, 46-61.

6. Кабанов В.В., Махнев А.А. Об отделимых графах с некоторыми условиями регулярности // Матем. сборник 1996, т. 187, N 9, 495-503.

7. Казарина В.И., Махнев А.А. О реберно регулярных графах с Ь\ = 5 // Алгебра, логика и кибернетика. Тез. докл. Иркутск 2004, 159-161.

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

9. Махнев А.А. О псевдогеометрических графах некоторых частичных геометрий // Вопросы алгебры. Выпуск И. Гомель: Изд-во Гомельского ун-та 1997, 60-67.

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

11. Махнев А.А., Минакова И.М. Об одном классе реберно регулярных графов // Известия Гомельского ун-та 2000, 145-154.

12. Махнев А.А., Минакова И.М. Об автоморфизмах графов с А = 1, /х = 2 // Дискретная математика 2004, т. 16, N 1, 95-104.

13. Махнев А.А., Нирова М.С. Сильно регулярные графы с &i < 13 // Межд. алгебр, конф. Тез.докл. Екатеринбург, изд-во Урал, ун-та 2005, 184-186.

14. Махнев А.А., Нирова М.С. Узкие частичные четырехугольники и их автоморфизмы // Проблемы теор. и приклад, матем. Труды 37-й Регион, молод, конф. Изд-во ИММ УрО РАН, Екатеринбург 2006, 58-60.

15. Махнев А.А., Нирова М.С. Узкие частичные четырехугольники и их автоморфизмы // Алгебра и логика 2006, т. 45, N 6, 125-134.

16. Махнев А.А., Нирова М.С. Об однородных расширениях частичных геометрий // Проблемы теор. и приклад, матем. Труды 38-й Регион, молод, конф. Изд-во ИММ УрО РАН, Екатеринбург 2007, 46-49.

17. Махнев А.А., Нирова М.С. Сильно регулярные графы с Ь\ < 18 // Известия вузов, математика 2007.

18. Махнев А.А., Нирова М.С. Об однородных расширениях частичных геометрий // Труды ИММ УрО РАН, Екатеринбург 2007, т. 13.

19. Нирова М.С. О вполне регулярных графах с Ь\ < 5 // Сибирские электронные математические известия 2007, т. 4, 1-11.

20. Bous R.C., Dowling Т.A. A generalization of Moore graphs of diameter 2 // J. Comb. Theory (B) 1971, v. 11, 213-226.

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

22. Brouwer A. E., van Lint J. H. Strongly regular graphs and partial geometries // Enumeration к Designs / D. Jackson and S. Vanstone, eds.,Academic Press 1984, 85-122.

23. Brouwer A. E., Willbrink H. A. Block designs // Handbook of incidence geometry: buildings and foundations, ed. F. Buekenhout. Elsever Science, Amsterdam, 1995, 349-383.

24. Buekenhout F. Foundations of incidence geometry // Handbook of incidence geometry: buildings and foundations, ed. F. Buekenhout. Elsever Science, Amsterdam, 1995, 63-107.

25. Buekenhout F, Pasini P. Finite diagram geometries extending buildingsHandbook of incidence geometry: buildings and foundations, ed. F. Buekenhout. Elsever Science, Amsterdam, 1995, 1143-1255.

26. Cameron P. Partial quadrangles // Quart. J. Math. Oxford (2) 1975, v. 26, 61-73.

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

28. Cameron P., Fisher P. H. Small extended generalized quadrangles // Europ. J. Comb. 1990, v. 11, 403-413.

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

30. Higman D.G. Finite permutation groups of rank 3 // Math. Z. 1964, v. 86, 145-156.

31. Higman D.G. Primitive rank 3 groups with a prime subdegree // Math. Z. 1966, v. 91, 70-86.

32. Higman D.G. Intersection matricies for finite permutation groups // J. Algebra, 1967, v. 6, 22-42.

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

34. Higman D.G. Characterization of families of rank 3 permutation groupsby the subdegrees I, II // Arth. Math. 1970, v. 21, 151-156; 353-361.

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

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

37. Hughes D.R. Extended partial geometries: dual 2-designs, Europ. J. Comb. 1990, v. 11, 459-472.

38. Payne S., Thas J. Finite Generalized Quadrangles. Research Notes in Math. 1984, v. 110. Pitman: Boston.

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

40. Seidel J.J. Strongly regular graphs with (—1,1,0) adjacency matrix having eigenvalue — 3 // Linear Algebra & Appl. 1968, v. 1, 281-298.

41. Thas J.A. Some results on quadrics and new partial geometries // Simon Stevin 1981, v. 55, 129-139.

42. Tits J. Buildings of Spherical Type and finite BN-pairs, Springer Lecture Notes in Mathematics, v. 386 1968.

43. Wilbrink H.A., Brouwer A.E. (57,14,1) strongly regular graph does not exist // Proc. Kon. Nederl. Akad. Ser. A 1983, v. 45, 117-121.