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

РОССИЙСКАЯ АКАДЕМИЯ НАУК УРАЛЬСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ И МЕХАНИКИ

На правах рукописи ГАВРИЛЮК Александр Львович

БЛОК-СХЕМЫ, КОМБИНАТОРНО СИММЕТРИЧНЫЕ ГРАФЫ И ИХ АВТОМОРФИЗМЫ

01 01 06 — математическая логика, алгебра и теория чисел

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

00316Э970

Екатеринбург — 2008

003169970

Работа выполнена в отделе алгебры и топотогии Института математики и механики УрО РАН

Научный руководитель:

доктор фичико-ма1ема1иче(ких наук,

профессор, чп-корр РАН МАХНЕВ Александр Алексеевич

Официальные оппоненты

доктор физико-математических паук, профессор БАРАНСКИЙ Виталий Анатольевич

кандидат физико-математических наук КАЗАРИНА Вероника Игоревна

Ведущая организация. Инс 1шу1 маи'матки СО РАН

Защита состоится 17 июня 2008 года в 15 30 часов на заседании специализированного совета Д 004 006 03 в Институте математики и механики УрО РАН по адресу 620219, г Екатеринбург, ул С Ковалевской, 16

С диссертацией можно ознакомиться в научной библиотеке Института математики и механики УрО РАН (г Екатеринбург, ул С Ковалевской, 16)

Автореферат разослан /С мая 2008 года

Ученый секретарь диссертационного совета, докт ор физ -мат наук

В В Кабанов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ.

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

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

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

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

Использование более сильных условий регулярности для графа позволяет ввести понятие сильно регулярного графа с параметрами (ь,к,\,ц), который определяется как граф на V вершинах, регу-

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

Вместе с тем, к понятию сильно регулярного графа можно прий г и и другим путем, рассматривая действие некоторой группы перестановок С на конечном множестве V Будем юворить, что О имеет подстановочный ранг 3, если О транзитивно действует на V и имеет точно 3 орбиты на У X У диагональ {(р,р)| р € V} и еще две другие орбиты 0,0' Если группа ранга 3 имеет четный порядок, то она содержит инволюцию, переставляющую, скажем, точки р и д Таким образом, орбита, содержащая р и симметрична Образуем граф Г, вершинами которого являются элементы V, а ребрами — неупорядоченные пары, соответствующие упорядоченным парам из О Тогда группа б вкладывается в группу автоморфизмов графа Г, а граф Г является сильно регулярным Теория групп ранга 3 была развита в работах Д Хигмана ([17]—[23])

В дальнейшем, для вершины а графа Г через Г,(а) будем обо ¡начать подграф, индуцированный на множестве вершин, находящихся в Г на расстоянии г от вершины а Для вершин а, Ь £ Г через ¿(а, Ь) будем обозначать расстояние между а и 6 в Г Кроме того, всюду далее под подграфом будем ионимать только индуцированный подграф Подграф Г] (а) называется окрестностью вершины а и обозначается через [а] Через а-1- обозначается подграф, являющийся

шаром радиуса 1 с центром а В соответствии с приведенным выше определением, граф Г называется регулярным графом степени к, если [а] (одержит точно к поршни для любой вершины а ич Г

Очевидно, что графами, построенными но группам ранга 3, теория сильно регулярных графов не исчерпывается Дальнейшим обобщением таких графов являются дистанционно транзитивные графы диаметра <1 = ¿(Г), группы автоморфизмов которых действуют гранзигивно на множествах {(и,и;)| 6 Г,с1г{и,ии) — г} дЛя любого г б {0, , (I) Комбинаторным обобщением сильно регулярных графов являются дистанционно регулярные графы, для которых существуют такие натуральные числа р^, г,з,к 6 {0, ,е(} что |Г,(и) П ГДг/;)| = для любых вершин и,ги, находящихся на расстоянии к в Г (см [9])

Отметим, в частности, что изучение дистанционно транзитивных графов связано с поиском единого представления конечных простых групп — задачей, которая стала актуальной после завершения классификации конечных простых групп ([9]-[12], [27], [29], [32])

Первые результаты о комбинаторно симметричных графах были получены в пятидесятых годах прошлого века Пусть Ь{Кп) — реберный грае}) полного графа Кп на п вершинах или в других обозначениях треугольный граф Т(п) (или, что тоже самое, блок-граф полной 2-схемы) Этот граф является сильно регулярным графом с параметрами 2(п — 2), п - 2,4) В работах 1959-60 годов Л Чанг [16] и А Хоффман ([24], [25]) независимо показали, чго треугольный граф Т(п) определяется однозначно своими параметрами для всех п, за исключением п = 8 Для случая п = 8 было показано, чго, кроме треугольного графа Т(8), такие же параметры имеют только три графа, которые были найдены Л Чангом в 1949 году [15]

Реберный граф Ь(Кт<п) полного двудольного графа Ктп с долями порядков тип является кореберно регулярным графом (см [9]) с параметрами (тп,т + п — 2,2) Граф Ь(Кт,п) называют т х п решеткои При то = п ->та решетка является сильно регулярным графом с параметрами (п2,2п—2, п—2,2) С Шрикханде в [31] показал, что граф, имеющий параметры п х п решетки является решеткой

при п ф 4 При п = 4 существует еще один сильно регулярный граф с параметрами решетки, но не изомофрный ей, названный графом Шрикханде

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

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

Введем еще несколько определений и обозначений Граф Г называется вполне регулярным графом с параметрами (у, к, А, /х), если Г содержит V вершин, регулярен степени к, каждое ребро из Г лежит точно в А треугольниках, и подграф [а] П [Ь] содержит точно ¡л вершин для любой пары вершин о, Ь, находящихся на расстоянии 2 в Г Очевидно, что вполне регулярный граф диаметра 2 является сильно регулярным графом

Подграф [а] П [Ь] будем называть \-подграфом, если ¿(а, Ъ) = 1 Если же с1(а,Ь) = 2, то соответствующий подграф назовем р,-подграфом

Если вершины и, ш находятся на расстоянии г в Г, то через Ьг(и, к;) (соответственно сДи, гу)) обозначим число вершин в пересечении Г(г<;) с Г,+г(и) (соответственно Г,_1(и)) Граф Г диаметра (I называется

дистанционно регулярным с массивом пересечений {fc>o, , b,i~\. ci,

,c(i}, если значения b¡ = Ьг(и,и)) и с, = c¡(u,w) не зависят от выбора вершин и, w па расстоянии г в Г для любого г = 0, , d Можно показать, что это определение дистанционно регулярного графа равносильно приведенному выше (см [9])

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

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

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

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

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

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

1 Исследованы вполне регулярные графы Г диаметра d > 3, в которых для некоторой вершины а € Г napa (Г^(а), r<í_i(o)) является 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+3г)2, г3+ 3г2 + г, 0, г2 + г) при г — 4 Доказано, что группа автоморфизмов такого графа не квазипримитивна

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

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

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

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

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

Результаты диссертации.

Во введении обсуждается история вопроса, даются определения и формулируются основные результаты

В главе I рассматриваются вполне регулярные графы Г диаметра с1, в которых для некоторой вершины а € Г пара (Г,;(а), Г^- 1.(а)) является 2-схемой (блок-схемой) относительно отношения инцидентности, индуцированного смежностью в графе

Блок-схемы естественно возникают внутри сильно регулярных графов Например, если для клики или коклики X графа Г достигается равенство в границе Хоффмана (см. [9]), то пара (X, Г — X) является 2-схемой В монографии Камерона и ван Линта [14, § 8] рас-

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

Следующие результаты являются основными в главе I

Предложение 1. Пусть Г — связный вполне регулярный граф диаметра й с параметрами (ь,к,\,ц), в котором для некоторой вершины а пара (Г,](а), Г^^а)) является 2-(У, В, Я, К, Л) схемой Тогда Я = са(а,х) для х £ ГДа), К = для у £ Г<г_1(а) и

подграф Г^(а) является кликой, кокликой или сильно регулярным графом с параметрами (г/ = V, к' = к — Я, А' = Л — Л, р! = р, — Л)

Класс дистанционно регулярных графов Г, в которых для неко-юрой вершины а подграф Га(о) является кокликой, содержит ап-типодальные и двудольные графы, для этих графов А равно 0 (и 2-схема вырождена) и ¡л соответственно

Пример 1 Следующие дистанционно регулярные графы диаметра (I > 3 являются двудольными, но не антиподальными

(1) обобщенные п-уголышки порядка (1, д) для п = 6,8,12,

(2) удвоения графов Грассмана,

(3) графы типов (В0-В7) и типа (В14) [9, таблица 6 9]

Графы типа (ВО) — это графы инцидентности симметричных 2-схем, графы типа (В1) возникают из кодов Казами, графы типов (В2-В7) — это графы инцидентности частичных /¿-геометрий (см

[9, §1 7])

Дистанционно регулярный граф Г, в котором для некоторой вершины а подграф Г,¡(а) — клика, оказывается половинным графом дистанционно регулярного графа нечетного диаметра 2(1 Ч- 1, являющегося антиподальным 2-накрытием

Пример 2 Следующие дистанционно регулярные графы диаметра 2с/ + 1 > 7 являются двудольными и антиподальными 2-

накрытиями

(1) удвоения нечетных графов на 2(1 + 1 точках (половинные графы являются графами Джонсона Л^2в.-\-1,(2)),

(2) (2<* + 1)-куб,

(3) графы диаметра 7 на 2048 вершинах (удвоение графа смежных классов усеченного бинарного кода Голея) и на 4096 вершинах (удвоение графа смежных классов бинарного кода Голея)

Примеры сильно регулярных графов Г, в которых для некоторой вершины а пара (Гг(а), [а]) является 2-схемой, приведены в [14] Пример дистанционно регулярного графа Г диаметра, большего 2, в котором для некоторой вершины а подграф Г,г(а) является сильно регулярным графом, обеспечивает граф Джонсона J(2d + 2, й) Для этого графа получим А = 2(1, ц = 4, для любой вершины а имеем Га(а) = Т(й+2) — сильно регулярный граф с А' = ¿, р! = 4 Но для этого графа не выпочняется равенство А — А' = /1 — //

Теорема 1. Пусть Г — вполне регулярный граф диаметра 3, имеющий параметры (и, к, А, ¡г) Тогда следующие утверждения равносильны

(1) Г является дистанционно регулярным графом, в котором для каждой вершины а подграф Гз(а) является кликой, кокликой или сильно регулярным графом с параметрами (у1, к', А', ц'), где А — А' = А» — ц',

(2) для любой вершины а пара (Гз(а), Гг(а)) является 2-с/хемой

Автору не известны примеры дистанционно регулярных графой диаметра ¿>3 с параметрами (у, к, X, ¡г), в которых для некоторой вершины а подграф Г Да) был бы сильно регулярным диаметра 2 с параметрами (и1, к1, А', ц') и Х - X' = ц — ц'

Для некоторых сильно регулярных графов Е найдены возможные параметры вполне регулярных графов Г диаметра 3, в которых найдется такая вершина а, что Гз(а) = Е и пара (Гз(а), Гг(а)) является 2-схемой

Теорема 2. Пусть Е — сильно регулярный граф, Г — вполне регулярный граф диаметра 3, имеющий параметры (г>, к, А, /х) и

вершит/ а такую, что Г3(а) = £ и пара (Гз(а), Гг(а)) является 2-схемой Тогда выполняются следующие утверждения.

(1) если схема (£, Г2(а)) симметрична, то Г семиугольник,

(2) £ является п х п решеткой, схема (£, Г2(а)) имеет параметры (п2,4п2,2(п + 1), (п + 1)/2,1), п нечетно, и граф Г имеет параметры (5п2 + Ап + 1,4п, п — 1,3),

(3) если £ полный многодольный граф КТХ2, ¿Р&Ф Мура, Клеб-ша, Шрикханде, Шлефли, один из графов Чаша, пхп решетка при п < 50, или треугольный граф Т(п) при п < 50, то полный список допустимых параметров графов, не вошедших в указанную в (2) бесконечную серию, содержится в таблице 1

Таблица 1.

N граф точек схемы параметры схемы параметры графа

1 граф Петерсена (10,30,12,4,4) (56,15,4,5)

2 граф Хофмана-Спнглтона (50,1050,168,8,24) (1276,175,24,25)

3 граф Шрикханде (16,360,90,4,18) (473,96,20,20)

4 решетка па 9 вершинах (9,24,8,3,2) (46,12,3,4)

5 решетка на 16 вершинах (16,360,90,4,18) (473,96,20,20)

6 решетка на 36 вершинах (36,225,50,8,10) (322,60,14,12)

7 решетка на 100 вершинах (100,825,132,16,20) (1076,150,28,22)

8 решетка на 441 вершинах (441,2940,80,12,2) (3502,120,21,4)

9 Т(9) (36,84,14,6,2) (149,28,9,6)

10 Т(11) (55,264,48,10,8) (386,66,17,12)

11 Т(14) (91,195,15,7,1) (336,39,13,5)

12 Т(14) (91,546,60,10,6) (722,84,18,10)

13 Т(15) (105,910,104,12,11) (1146,130,24,15)

14 Т(15) (105,520,104,21,20) (756,130,33,24)

15 Т(17) (136,8568,378,6,14) (9113,408,29,18)

16 Т(20) (190,513,135,50,35) (875,171,53,39)

17 Т(25) (300,4600,414,27,36) (5361,460,59,40)

18 Т(35) (595,22440,1056,28,48) (24158,1122,81,52)

Для дистанционно регулярных графов диаметра > 3, в которых для любой вершины а пара (Гц(а), Г^_1(а)) является 2-схемой,

результаты первой главы диссертации позволяют выдвинуть следующее предположение

Гипотеза Если Г — дистанционно регулярный граф диаметра d > 3, в котором для любой вершины а пара (Г,/(а), является 2-схемой, то подграф Е — Г<г(а) является кликой или коклихой

Указанная гипотеза подтверждается тем, что среди допустимых массивов пересечений дистанционно регулярных графов, приведенных в [9], лишь два массива {60,45,8,1,12,50} и {49,36,8,1,6,42} отвечают графам, для которых могут быть выполнены условия нашей гипотезы

Для первого массива Гз(а) является 6x6 решеткой, а для второго — объединением семи изолированных 8-клик Однако, в лемме 14 4 первой главы диссертации доказано, что в дистанционно регулярном графе с массивом пересечений {60,45,8,1,12,50} найдется вершина, третья окрестность которой не является 6x6 решеткой Для второго массива пара (Гз(а), Гг(а)) является (V, В, R, К, А)-схемой, где Г = 56, В = 294, Д = 42, К = & н К = R(K - 1)/(V - 1) = 42 7/55 (дробность числа А показывает наличие вершин в Гз(а), находящихся на расстоянии 3, что противоречит предположению, что пара (Гз(а), Гг(а)) является 2-схемой в указанном смысле) Таким образом, не известны массивы пересечений, которым бы отвечали дистанционно регулярные графы, третья окрестность каждой вершины которых является сильно регулярным графом, а пара (Г^(а),Г,2_1(а)) является 2-схемой

Во второй главе изучаются автоморфизмы гипотетического дистанционно регулярного графа с массивом пересечений {60,45,8,1, 12,50} Этот граф имеет спектр {601,1445,0207, -1069}, является Q-полиномиальным, граф Г2 (в котором вершины смежны тогда и только тогда, когда они находятся на расстоянии 2 в Г) сильно регулярен с параметрами (322,225,160,150) и является псевдогеометрическим для частичной геометрии pG2(6,15)

Введем следующее обозначение Пусть Г — граф, тогда для элемента g группы G = Aut,(r) через Fix(g) обозначим подграф вершин

графа Г, фиксируемых автоморфизмом д

Следующие теорема и следствие являются основными во второй главе

Теорема 3. Пусть Г — дистанционно регулярный граф, имеющий массив пересечений {60,45,8; 1,12,50}, (3 = Аи^Г), д - элемент из С простого порядка р > 5 и О = Г1х(д) Тогда верно одно из утверждений

(1) р = 7 или 23 и О, — пустой граф,

(2) р = 5 и либо

(г) £2 состоит из двух вершин, находящихся на расстоянии 3 в Г, либо

(гг) )£2| = 7 и Г3(а) П Г2 является 6-кликой для некоторой вершины а £ О.

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

Для изучения возможных порядков и подграфов неподвижных точек автоморфизмов дистанционно регулярных графов Г Хигмен предложил оригинальный метод, использующий теорию характеров конечных групп Этот метод изложен в монографии П Камерона [13], причем ранее он применялся только к изучению инво-лютивных автоморфизмов сильно регулярного графа с параметрами (3250,57,0,1) Позднее, в работах [1]-[3] изучались автоморфизмы сильно регулярных графов с малыми числами пересечений В диссертации это г метод применяется для изучения автоморфизмов гипотетического дистанционно регулярного графа < массивом пересечений {60,45,8,1,12,50}

В третьей главе доказывается несуществование сильно регулярного графа с параметрами ((г2 + Зг)2, г3 + Зг2 + г, 0, г2 + г) для г = 3 и изучаются автоморфизмы графов из этой серии для г = 4

Введем далее некоторые определения. Полный п-дольный граф с долями порядков тщ, , ш„ обозначим через К,„и )7„п Граф называется т-лапой Граф с п долями порядка 1 называется

п-короной (короной, если п = 2) Кликовым расширением графа Г

называется граф, полученный заменой каждой вершины а на клику (а), причем различные клики попарно не пересекаются, и вершина из (а) смежна со всеми вершинами из (6) тогда и только тогда, когда a, b смежны в Г Граф Г называется редуцированным, если для любой вершины а € Г множество {х £ Г| х1 — а1} состоит только из вершины а

Хорошо известно, что на строение графа сильное влияние оказывают его /¿-подграфы Так, например, в работе [28] М Нумата получил классификацию графов без корон, в которых /¿-подграфы являются изоморфными реберно регулярными графами диаметра 2 (естественно, не имеющими 3-лап)

В работе [5] исследовались связные редуцированные регулярные графы без корон, в которых каждый /¿-подграф реберно регулярен с заданными параметрами (v', к', А'), к' > О

По следствию 2 теоремы 2 из [5] связный редуцированный регулярный граф Г без корон, в котором каждый /¿-подграф реберно регулярен с заданными параметрами (v',k',\')t к' > 0 и имеет диаметр не более 2, является одним из следующих графов

(1) Г не содержит 3-коклик и либо является октаэдром или треугольным графом Т{5), либо граф Г сильно регулярен и имеет параметры ((г2 + 3г)2, г3 + Зг2 + г, 0, г2 + г) для некоторого г > 1, либо нетривиальным кликовым расширением пятиугольника,

(2) Г содержит 3-коклику, не содержит 3-лап и является кликовым расширением графа икосаэдра, треугольным графом Т(т) при тп > 6 или графом Шлефли,

(3) Г содержит 3-лапу и является графом Грассмана, графом Джонсона или его частным, локально треугольным графом или графом Госсета

Напомним [14], что сильно регулярный граф Г с параметрами {v,k, A,/i) имеет точно 3 различных собственных значения k,r,s Если графы Г и Г связны, то выполняются неравенства, называемые условиями Крейна

(1) (г + l)(fc + г + 2rs) <(k + r)(s + l)2 и

(2) (s + 1 )(k + s + 2rs) < (k + s)(r + l)2

Граф Г назовем графом Крейна, если для него достигается равенство в одном из условий Крейна (1) или (2) По теореме 8 15 из [14] для любой вершины а графа Крейна Г иодфафы [а] и Гг(а) сильно регулярны Пусть Г является графом Крейна без треугольников Ввиду предложения 8 12 и теорем 8 7 и 8 8 из [14] сильно регулярный граф Г без треугольников с 2 < /л < к имеет параметры ((г2 + Зг)2,г3 + Зг2 + г, 0, г2 + г) тогда и только Ю1да, когда любая 3-коклика из Г попадает в окрестность ровно г вершин Такой граф обозначим через Кге(г) Далее, для любых смежных вершин а, 6 € Г подграфы Г2(а) и Гг(а) П Гг(Ь) сильно регулярны с параметрами ((г2 + 2г — 1)(г2 + Зг + 1),г3 + 2г2,0, г2) и ((г2+ 2г)(г2+ 2г — 1),г3 + г2 — г, 0, г2 — г) соответственно Известно, что в случаях г — 1 и 2 существуют единственные графы Кге{г) — граф дополнительный к графу Клебша и граф Хигмепа-Симса соответственно Последний граф построен в 19С8 г вместе со спорадической простой группой Хигмена-Симса

Существование графов Кге(г) при г > 3 в общем случае остается неизвестным В соответствии с чтим в работе [5] была поставлена

Проблема 1 Существует ли сильно регулярный граф с параметрами ((г2 + Зг)2, г3 + Зг2 + г, 0, г2 + г) в случае г > 3?

Отметим, что вопрос о существовании графа Кге(3) непосредственно связан с еще одной известной проблемой из теории схем Пусть Г = Кге(г) Рассмотрим схему V — ([а],Г2(а)), где точка b £ [а] инцидентна блоку В G Г2(а) тогда и только тогда, когда b и В смежны в Г Тогда 3-схема V является расширением симметричной 2-схсмы Т>' — ([а] — {6}, [6] — {а}) Проблема существовани расширений схем является одной из нерешенных и наиболее важных задач в теории схем (см [14])

В частности, если г — 3, то схема V является 2 - (56,11, 2) схемой Но вопрос о существовании расширения схемы 2 — (56,11,2) более 30 лет оставался открытым Ранее, Багчи, изучая самоортогональный код над F3, отвечающий строкам матрицы инцидентности гипотетической 3-(57,12,2) схемы, доказал несуществование таких 3-схем (см [7]) Однако в его работе была допущена ошибка (см

[10]) В теореме 1 из работы [4] утверждалось, что граф Кге(г) не содержит Кг^т подграфов, в частности, граф Кге(3) не существует Однако в лемме 3 из [4] была допущена арифметическая ошибка

Один из основных результатов третьей главы диссертации заключается в следующих теореме и следствии из нее

Теорема 4. Не существуют сильно регулярные графы с параметрами ((г2 + 3г)2, г3 + 3г2 + г, 0, г2 + г) для г = 3

Следствие 2. Симметричные 2-(56,11,2) схемы перасширяс-мы

В заключение третьей главы изучается группа автоморфизмов гипотетического сильно регулярного графа Кге(4)

Отметим, что для изучения возможных порядков и подграфов неподвижных точек автоморфизмов графа Кге(4) используется метод Хигмена Автоморфизмы графа Кге{5) изучались в [1]

Пусть (7 — транзитивная группа подстановок па множестве X Группа в называется квазипримитивной на X, если любая пееди-ничная нормальная подгруппа из (? действует транзитивно на X

Теорема 5. Пусть Г — граф Крейна Кге(4), (3 = А1й,(Г) Если д — элемент простого порядка р из С?, О, — Г1х(д), то р € {2,7}, причем в случае р = 7 автоморфизм д действует без неподвиоюпых точек

Следствие 3. Действие группы С7 на вершинах графа Г не ква-зипримитивио

Автор выражает признательность своему научному руководи гелю профессору А А Махневу за постановку задачи, внимание и поддержку, а также всем участникам семинара отдела алгебры и ю-пологии ИММ УрО РАН за критические замечания и обсуждение результатов диссертации

Список литературы

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

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

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

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

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

[6] Холл, М Комбинаторика/М Холл//М Издательство "Мир" -1970 - 424 с

[7] Bagchi В No extendable biplane of order 9/B Bagchi// J Comb Theory (A) 1988 V 49 P 1-12 (Corrigendum 1991 V 57 P 162)

[8] Bous R С Strongly regular giaph, partial geomerties, and partially balanced designs/R С Bous//Pacific J Math, 1963 V 13 P 389419

[9] Biouwer, AE Distance-iegular graphs/ AE Biouwei, AM Cohen, A Neumaier// Berlin etc Springer-Verlag - 1989- 495 с

|10] Biouwei, AE Block designs/ AE Biouwei, HA Willbnnk// Handbook of liicidcncc geometry buildings and foundations/ F Buekenhout - Elsevei Science Amsterdam - 1995 - P 349-383

[11] Buekenhout, F Foundations of incidence geometry / F Buekenhout// Handbook of incidcncc gcomctiy buildings and foundations/F Buekerihouf, - ELsever Science Amsterdam - 1995 -P 63-107

[12] Buekenhout, F Finite diagram geometries extending buildings/ F Buekenhout, P Pasmi// Handbook of incidence geometry buildings and foundations/F Buekenhout — Elsever Science Amsterdam -1995- P1143-1255

[13] Cameron, P Peimutation Gioups/ P Cameron- London Math Soc Student Texts 45 Cambridge Univ Pi ess, 1999

[14] Carneion, P J Giaphs, Codes and Designs / Cameion P J , van Lint. J -London Math Soc, Student Texts №22, Cambudge Cambridge Univ Press, 1991

[15] Chang, L C The uniqueness and nonuniqueness of tuangulai association schemes/ LC Chang// Sci Recoid- 1949- Vol 3-P 604-613

[16] Chang, L C Association schemes of partially balanced block designs with parameters v = 28, nj = 12, no = 15 and p2 = 4/ LC Chang// Sci Recoid - 1950 - Vol 4 - P.12-18

[17] Higman, D G Finite permutation gioups of rank 3/ D G Higman// Math Z - 1964 - Vol 86 - P 145-156

]18] Higman, D G Pnmitive iank 3 groups with a prune subdegiec/ D G Higman// Math Z - 1966 - Vol.91 - P 70-86

]19] Higman, D G Intersection matricies tor finite peimutation gioups/ D G Higman// J Algebia - 1967 - Vol 6 - P 22-42

[20] Higman, D G On finite affine planes of rank 3/ D G Higman// Math Z - 1968 - Vol 104 - P147-149

[21] Higman, D G A suivey of some questions and resalts about iank 3 peirnutation gioups/ D G Higman// Actcs, Cjngies Int Math Rome - 1970 - Vol 1 - P 361-365

Higman, D G Characterization of families of rank 3 permutation gioups by the subdegiees I, II/ D G Higman// Aith Math - 1970 -Vol 21 - P 151-156, 353-361

Higman, D G Coheient configurations/ D G Higman//Rend Sem Mat Uiuv Padova - 1970 - Vol 44 - P 1-26

Hoffman, A J On the uniqueness of the tnangulai association scheme/ A J Hoffman// Ann Math Stat - 1960 - Vol 31 - P492-497

Hoffman, A J On the exceptional case in a characterization of the aics of complete graphs/A J Hoffman// IBM J Res Develop-1960- Vol 4- P 487-496

Hoffman, A J On the lme-giaphs of the complete bipaitite giaph/ A J Hoffman// Ann Math Stat - 1964 - Vol 35 - P 883-885

Numata, M On a characterization of a class of regular giaphs/ M Numata// Osaka J A-lath - 1974 - Vol 11 - P 389-400

Numata M , A charactenzation of Grassman arid Johnson giaphs/ M Numata //J Comb Theoiy (B) 1990 V 48 P 178-190

Piaegei, CE Low rank representations and giaphs for sporadic gioups/ CE Piagei, LH Soicher- Lecture series 8- Cambndge University press - 1997

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

Shnckhande, S S The uniqueness of the association scheme/ S S Shnckhande// Aim Math Stat - 1959 - Vol 30 - P 781-798

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

Работы автора по теме диссертации

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

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

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

(36J Гаврилюк АЛО графах Крейна без треугольников /АЛ Гаврилюк, А А Махнев // Доклады РАН, матем 2005, т 403, N 6, С 727-730

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

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

[39] Gavulyuk A L On distancc-regulai graphs and then automoiphi-sms / Beloubov I N , Gavrilyuk A L , Makhnev A A // Algcbiaic Combinatorics, Intern conf m honor Enchi Bannai's 60th birthday, Tohoku Umv 2006, P 54-55

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

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

Подписано в печать 14 05 2008 Формат 60x84/16 Объем 1,3 уел -печ л Тираж 100 экз Заказ № 163 Размножено с готового оригинал-макета в типографии AHO "Уральский центр академического обслуживания" 620219, г Екатеринбург, ул Первомайская, 91

Введение

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

Автоморфизмы дистанционно регулярного графа с массивом пересечений {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 наименований.

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.