Блок-схемы, комбинаторно симметричные графы и их автоморфизмы

В комбинаторном анализе проблемой общего характера является задача размещения элементов в заданном числе множеств таким образом, чтобы г-ый элемент появлялся Т{ раз во всей совокупности этих множеств, чтобы j-oe множество содержало точно kj элементов и, наконец, чтобы пары, тройки и тому подобные наборы элементов появлялись определенное число раз. Такое размещение может быть названо системой инцидентности. В частности, в прикладной математике (статистика, теория планирования экспериментов) чаще используется понятие уравновешенной неполной блок-схемы, в которой всякий набор элементов (блок) состоит точно из к элементов (точек), каждая точка принадлежит точно г блокам, и каждая пара различных точек появляется вместе точно в Л блоках [8].

Блок-схема является частным случаем t-схем (с параметрами (v, k, Л)), которые определяются как пара (X, В), где X — множество точек, В — множество блоков, каждый из которых содержит точно к точек, и любые t точек принадлежат вместе точно Л блокам. Таким образом, блок-схема является 2-схемой с подходящими параметрами.

Взаимосвязь блок-схем с другими объектами комбинаторного анализа — кодами, исправляющими ошибки, графами, хорошо известна и исследовалась ранее (см. [19]).

Далее мы рассматриваем неориентированные графы без петель и кратных ребер. В таком случае граф можно определить как пару, состоящую из множества вершин и множества ребер, то есть неупорядоченных двухэлементных подмножеств множества вершин. Заметим, что любой регулярный граф (то есть граф, в котором каждая вершина смежна с одним и тем же числом вершин) является 1-схемой, а полный граф (клика) является 2-схемой (схемой нар или полной схемой).

Использование более сильных условий регулярности для графа позволяет ввести понятие сильно регулярного графа с параметрами (v, к, Л, //), который определяется как граф на v вершинах, регулярный степени к, в котором пересечение окрестностей любой пары различных вершин содержит точно Л или /л вершин в зависимости от того, смежны эти вершины или нет. Впервые понятие сильно регулярного графа было введено Боузом [12] при изучении частичных геометрий и уравновешенных неполных блок-схем. Так, например, хорошо известно [12], что блок-граф 2 — (v, к, 1) схемы, в котором два блока смежны тогда и только тогда, когда они имеют непустое пересечение, является сильно регулярным графом. Этот факт был обобщен Боузом, Геталсом и Зейделем для блок-графов квазисимметричных схем [19]. Таким образом, блок-схемы позволяют получить примеры сильно регулярных графов. Однако изучение этих графов не дает дополнительной информации о схемах. Напротив, изучение схем, возникающих в сильно регулярных графах, позволяет в ряде случаев установить некоторые структурные особенности графа, в том числе, доказать его несуществование.

Вместе с тем, к понятию сильно регулярного графа можно прийти и другим путем, рассматривая действие некоторой группы перестановок G на конечном множестве V. Будем говорить, что G имеет подстановочный ранг 3, если G транзитивно действует на V и имеет точно 3 орбиты на V х V: диагональ {(р, р)| P~?~V} и еще-две" другие орбиты-070-.-Если группа ранга 3-имеет четный порядок, то она содержит инволюцию, переставляющую, скажем, точки р и q. Таким образом, орбита, содержащая р и q, симметрична. Образуем граф Г, вершинами которого являются элементы V, а ребрами — неупорядоченные пары, соответствующие упорядоченным парам из 0. Тогда группа G вкладывается в группу автоморфизмов графа Г, а граф Г является сильно регулярным. Теория групп ранга 3 была развита в работах Д. Хигмана ([24]—[30]).

В дальнейшем, для вершииы, а графа Г через Гг (а) будем обозначать подграф, индуцированный на множестве вершин, находящихся в Г на расстоянии i от вершины а. Для вершин a, b G Г через d (a, Ъ) будем обозначать расстояние между, а и 6 в Г. Кроме того, всюду далее под подграфом будем понимать только индуцированный подграф. Подграф Г]. (а) называется окрестностью вершины, а и обозначается через [а]. Через aL обозначается подграф, являющийся шаром радиуса 1 с центром а. В соответствии с приведенным выше определением, граф Г называется регулярным графом степени к, если [а] содержит точно к вершин для любой вершины, а из Г.

Очевидно, что графами, построенными по группам ранга 3, теория сильно регулярных графов не исчерпывается. Дальнейшим обобщением таких графов являются дистанционно транзитивные графы диаметра d = с?(Г), группы автоморфизмов которых действуют транзитивно на множествах {(w, w) и, w Е V, dr (u, w) = г} для любого i? {0, Комбинаторным обобщением сильно регулярных графов являются дистанционно регулярные графы, для которых существуют такие натуральные числа р^-, к Е {0,., с?} что |Гг-(г?) ПГ^(гу)| = рдля любых вершин u, w, находящихся па расстоянии к в Г (см. [13]).

Отметим, в частности, что изучение дистанционно транзитивных графов связано с поиском единого представления конечных простых групп — задачей, которая стала актуальной после «завершения» классификации конечных простых групп ([13]-[17], [34], [36], [39]).

Первые результаты о комбинаторно симметричных графах были получены в пятидесятых годах прошлого века. Пусть L (Kn) — реберный граф полного графа Кп на п вершинах или в других обозначениях треугольный граф Т (п) (или, что тоже самое, блок-граф полной 2-схемы). Этот граф является сильно регулярным графом с параметрами (Q), 2(п — 2), п — 2,4). В работах 1959;60 годов JL Чанг [21] и А. Хоффман ([31], [32]) независимо показали, что треугольный граф T (ri) определяется однозначно своими параметрами для всех п, за исключением п = 8. Для случая п = 8 было показано, что, кроме треугольного графа Т (8), такие же параметры имеют только три графа, которые были найдены J1. Чангом в 1949 году [20].

Реберный граф Ь{Кт<�п) полного двудольного графа Кт<�п с долями порядков тип является кореберно регулярным графом (см. [13]) с параметрами (mn, т—п—2, 2). Граф L (KmjJl) называют тхп решеткой. При то = п эта решетка является сильно регулярным графом с параметрами (п2, 2п—2, п—2, 2). С. Шрикханде в [38] показал, что граф, имеющий параметры п х п решетки является решеткой при п / 4. При п = 4 существует еще один сильно регулярный граф с параметрами решетки, но не изомофрный ей, названный графом Шрикханде.

Дж. Зейдель [37] показал, что кроме треугольных графов Т (п) и п х п-решетки, сильно регулярными графами, которые имеют наименьшее собственное значение —2, являются только графы Кпх2, графы Петерсена, Шрикханде, Клебша, Шлефли и три графа Чанга.

Одной из нерешенных проблем в теории комбинаторно симметричных графов остается задача о существовании графа с заданным условиями комбинаторной симметрии, например, существование сильно регулярного графа с заданными параметрами. Если эту задачу решить для конкретного графа не «удается, может оказаться «полезной» «информация «о свойствах группы авто-* морфизмов (например, информация о простых делителях порядка группы и подграфах неподвижных точек автоморфизмов простого порядка) этого гипотетического графа, в частности, при попытке построения графа с помощью компьютера. Для дистанционно регулярных графов оказывается возможным получение такой информации с помощью теории характеров конечных групп [18]. Кроме того, эта информация может быть существенно уточнена, если известно, что гипотетический граф связан с некоторой схемой.

Введем еще несколько определений и обозначений. Граф Г называется вполне регулярным графом с параметрами (v, k, fz), если Г содержит v вершин, регулярен степени к, каждое ребро из Г лежит точно в Л треугольниках, и подграф [а] П [b] содержит точно /л вершин для любой пары вершин а, 6, находящихся на расстоянии 2 в Г. Очевидно, что вполне регулярный граф диаметра 2 является сильно регулярным графом.

Подграф [а] П [b] будем называть Х-подграфом, если d (a, b) = 1. Если же d (a, 6) = 2, то соответствующий подграф назовем ц-подграфом.

Если вершины и, w находятся на расстоянии г в Г, то через b{(u, w) (соответственно Ci (u, w)) обозначим число вершин в пересечении Г (ад) с Г{+1(и) (соответственно rji (w)). Граф Г диаметра d называется дистанционно регулярным с массивом пересечений {&-о> • • • > bd-1- ci,., с^}', если значения 6г- = bi (u, w) и сг- = Ci (u, w) не зависят от выбора вершин и, w на расстоянии г в Г для любого г — 0,., d. Можно показать, что это определение дистанционно регулярного графа равносильно приведенному выше (см. [13]).

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

1) Изучить вполне регулярные графы Г диаметра d > 3, в которых для некоторой вершины a G Г пара (Гй (о), Г^-1(а)) является 2-схемой относительно отношения инцидентности, индуцированного смежностью в графе.

2) Изучить возможные автоморфизмы гипотетических дистанционно регулярных графов с массивом пересечений {60,45, 8- 1,12, 50}.

3) Изучить вопрос о существовании сильно регулярных графов с параметрами ((г2 + Зг)2,г3 + Зг2 + г, 0, г2 + г) при г > 3, изучить возможные автоморфизмы графов из этой серии.

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

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

1. Исследованы вполне регулярные графы Г диаметра d > 3, в которых для некоторой вершины, а 6 Г пара (Г^(а), rr/i (a)) является 2-схемой относительно отношения инцидентности, индуцированного смежностью в графе. Определены возможные параметры графов при d = 3 в случаях, когда Гз (а) является графом Зейделя или когда указанная 2-схема является симметричной.

2. Найдены возможные порядки и подграфы неподвижных точек автоморфизмов простых порядков дистанционно регулярных графов с массивом пересечений {60,45,8- 1,12, 50}.

3. Доказано несуществование сильно регулярного графа с параметрами ((r2 + 3r)2,r3 + 3r2 + r, 0, г2 + г) при г = 3 и, как следствие, нерасширяемость симметричной 2 — (56,11,2) схемы до 3-схемы.

4. Найдены возможные простые делители порядка группы автоморфизмов сильно регулярных графов с параметрами ((г2 + Зг)2, г3 + Зг2 + г, 0, г2 + г) при г — 4. Доказано, что группа автоморфизмов такого графа не квазипри-митивна.

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

Апробация работы. Основные результаты диссертации докладывались на Международной школе-конференции по теории групп, посвященной 75-летию со дня рождения А. И. Старостина (Нальчик, 2006 г.) и 35-й, 36-ой и 37-й Региональных молодежных конференциях ИММ УрО РАН (Екатеринбург, 2004;2006 гг.).

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

Публикации. Основные результаты диссертации опубликованы в работах [40]—[48]. Работы [40]—[47] выполнены в нераздельном соавторстве с А.А. Мах-певым.

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

1. Махнев, А. А. Об автоморфизмах сильно регулярных графов Крейна без треугольников/ А. А. Махнев, В.В. Носов// Алгебра и логика 2005, Т. 44, N 3, 335−354.

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

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

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

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

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

7. Кабанов, В.В. О графах без корон с регулярными /i-подграфами, II/ В. В. Кабанов, Махнев А. А., Падучих Д.В.// Математические заметки 2003, № 3. Т. 74. С. 396−406.

8. Холл, М. Комбинаторика/ М. Холл// М.: Издательство «Мир» , — 1970.424 с.

9. Aschbacher, M. The nonexistence of rank three permutation groups of degree 3250 and subdegrec 57 / M. Aschbacher // J. Algebra.- 1971. V. 19, № 3,-P.538−540.

10. Bagchi B. No extendable biplane of order 9/ B. Bagchi// J. Comb. Theory (A). 1988. V. 49. P. 1−12 (Corrigendum: 1991. V. 57. P. 162).

11. Bous R.C. A generalization of Moore graphs of diameter 2/ R.C. Bous, T.A. Dowling// J. Comb. Theory (B) 1971. V. 11. P. 213−226.

12. Bous R.C. Strongly regular graph, partial geomerties, and partially balanced designs/ R.C. Bous// Pacific J. Math, 1963. V. 13. P. 389−419.

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

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

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

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

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

18. Cameron, P. Permutation Groups/ P. Cameron.- London Math. Soc. Student Texts 45.: Cambridge Univ. Press, 1999.

19. Cameron, P. J. Graphs, Codes and Designs. / Cameron P. J., van Lint J. London Math. Soc., Student Texts № 22, Cambridge: Cambridge Univ. Press, 1991.

20. Chang, L.C. The uniqueness and nonuniqueness of triangular association schemes/ L.C. Chang// Sci. Record.- 1949. Vol.3. P.604−613.

21. Chang, L.C. Association schemes of partially balanced block designs with parameters v = 28, щ = 12, no = 15 and p2 = 4/ L.C. Chang// Sci. Record.-1950. Vol.4. P.12−18.

22. Damerell, R.M. On Moore graphs/ Damerell R.M.// Math. Proc. Cambr. Phil. Soc.- 1973. Vol.74. P.227−236.23. van Dam, E. Graphs with constant p, and Д/ van Dam E., Haemers W.H.// Discrete Math.- 1998. V. 162. P.293−307. Vol.74.-P.227−236.

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

24. Higman, D.G. Primitive rank 3 groups with a prime subdegree/ D.G. Higman// Math. Z.- 1966, — Vol.91. P.70−86.

25. Higman, D.G. Intersection matricies for finite permutation groups/ D.G. Higman// J. Algebra.- 1967. Vol.6. P.22−42.

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

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

28. Higman, D.G. Characterization of families of rank 3 permutation groups by the subdegrees I, II/ D.G. Higman// Arth. Math.- 1970, — Vol.21. P.151−156- 353−361.

29. Higman, D.G. Coherent configurations/ D.G. Higman// Rend. Sem. Mat.Univ. Padova.- 1970. Vol.44. P. 1−26.

30. Hoffman, A.J. On the uniqueness of the triangular association scheme/ A.J. Hoffman// Ann. Math. Stat.- I960. Vol.31. P.492−497.

31. Hoffman, A.J. On the exceptioal case in a characterization of the arcs of complete graphs/ A.J. Hoffman// IBM J. Res. Develop.-1960, — Vol.4. P.487−496.

32. Hoffman, A.J. On the line-graphs of the complete bipartite graph/ A.J. Hoffman// Ann. Math. Stat.- 1964. Vol.35. P.883−885.

33. Numata, M. On a characterization of a class of regular graphs/ M. Numata// Osaka J. Math.- 1974, — Vol.11. P.389−400.

34. Numata M., A characterization of Grassman and Johnson graphs/ M. Numata // J. Comb. Theory (B). 1990. V. 48. P. 178−190.

35. Praeger, C.E. Low rank representations and graphs for sporadic groups/ C.E. Prager, L.H. Soicher.- Lecture series 8. Cambridge: — University-press.- -1997.

36. Seidel, J.J. Strongly regular graphs with (-1,1,0) adjacency matrix having eigenvalue 3/ J.J. Seidel// Linear Algebra and Appl.- 1968. Vol.1. P.281−298.

37. Shrickhande, S.S. The uniqueness of the association scheme/ S.S. Shrickhande// Ann. Math. Stat.- 1959. Vol.30. P.781−798.

38. Tits, J. Buildings of Spherical Type and finite BN-pairs/ J. Tits// Springer Lecture Notes in Mathematics.- Vol.386.Работы автора по теме диссертации.

39. Гаврилюк A.JI. Вполне регулярные графы и блок-схемы / A. J1. Гаври-люк, А. А. Махнев // Проблемы теор. и приклад, матем. Труды 36-ой молодежной школы-конфер. Изд-во ИММ УрО РАН, Екатеринбург, 2004. С. 20−22.

40. Гаврилюк A. J1. О графах Крейна без треугольников / A.JI. Гаврилюк, А. А. Махнев // Проблемы теор. и приклад, матем. Труды 37-ой молодежной коифер. Изд-во ИММ УрО РАН, Екатеринбург, 2005. С. 18−20.

41. Гаврилюк A.JI. Об автоморфизмах дистанционно регулярного графа с массивом пересечений {60,45, 8- 1,12, 50} / A.JI. Гаврилюк, А. А. Махнев // Межд. алгебр, конф. Тез.докл. Гомель, изд-во Гомел. ун-та, 2005. С. 56−58.

42. Гаврилюк A.JI. О графах Крейна без треугольников / A.JI. Гаврилюк, А. А. Махнев // Доклады РАН, матем. 2005, т. 403, N 6, С. 727−730.

43. Гаврилюк A.JI. Двудольные подграфы в графах Крейна без треугольников / A.JI. Гаврилюк, А. А. Махнев // Проблемы теор. и приклад, матем. Труды 38-й Регион, молод, конф. Изд-во ИММ УрО РАН, Екатеринбург, 2006. С. 10−11.

44. Гаврилюк A.JI. Вполне регулярные графы и блок-схемы / A.JI. Гаврилюк, А. А. Махнев // Сиб. матем. журнал, 2006, т. 47, N 4, С. 753−768.

45. Gavrilyuk A.L. On distance-regular graphs and their automorphisms / Belousov I.N., Gavrilyuk A.L., Makhnev A.A. // Algebraic Combinatorics, Intern, conf. in honor Eiichi Bannai’s 60th birthday, Tohoku Univ. 2006, P. 54−55.

46. Гаврилюк A.JI. Об автоморфизмах дистанционно регулярного графа с массивом пересечений {60,45, 8- 1,12, 50} / A.JI. Гаврилюк, А. А. Махнев // Труды Института математики и механики УрО РАН 2007, т. 13, N 2, С. 41−53.

47. Гаврилюк А. Л. Об автоморфизмах сильно регулярного графа с параметрами (784,116,0, 20) / А. Л. Гаврилюк // Сибирские электронные математические известия, 2008, т. 5, С. 80−87.