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

• Гаврилюк, Александр Львович
• кандидат физико-математических наук
• 2008

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

Введение

Вполне регулярные графы и блок-схемы

Автоморфизмы дистанционно регулярного графа с массивом пересечений {60,45, 8,1,12, 50}

Графы Крейна без треугольников

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

В комбинаторном анализе проблемой общего характера является задача размещения элементов в заданном числе множеств таким образом, чтобы г-ый элемент появлялся Т{ раз во всей совокупности этих множеств, чтобы 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 наименований.

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

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.- С. 159172.

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.