Конечные геометрии, графы, их расширения и автоморфизмы тема автореферата и диссертации по математике, 01.01.04 ВАК РФ
|
Нирова, Марина Сефовна
АВТОР
|
||||
|
доктора физико-математических наук
УЧЕНАЯ СТЕПЕНЬ
|
||||
|
Екатеринбург
МЕСТО ЗАЩИТЫ
|
||||
|
2014
ГОД ЗАЩИТЫ
|
|
01.01.04
КОД ВАК РФ
|
||
|
|
||||
На правах рукописи
НИРОВА Марина Сефовна
Конечные геометрии, графы, их расширения и автоморфизмы
01.01.04 — геометрия и топология, 01.01.06 — математическая логика, алгебра и теория чисел
АВТОРЕФЕРАТ
диссертации на соискание ученой степени доктора физико-математических наук
Екатеринбург - 2014
Работа выполнена в отделе алгебры и топологии ИММ УрО РАН
Научный консультант:
доктор физ.-мат. наук, член-корр. РАН МАХНЕВ A.A. заведующий отделом алгебры и топологии ИММ УрО РАН
Официальные оппоненты:
доктор физ.-мат. наук, профессор АНТОНОВ В.А. Южно-Уральский госуниверситет, профессор
доктор физ.-мат. наук, профессор КАЗАРИН Л.С. Ярославский государственный университет, заведующий кафедрой
доктор физ.-мат. наук ПОНОМАРЕНКО И.Н. Санкт-Петербургский филиал Института математики РАН, ведущий научный сотрудник
Ведущая организация:
Уральский федеральный университет
Защита состоится 24 февраля 2015 г. в 14 ч. 00 м. на заседании диссертационного совета Д 004.006.03 по защите диссертаций на соискание ученой степени доктора наук при ИММ УрО РАН по адресу: 620990, Екатеринбург, ул. Софьи Ковалевской, д. 16.
С диссертацией можно ознакомиться в научной библиотеке ИММ УрО РАН, а также на сайте Института http://imm.uran.ru.
Автореферат разослан f^jянваря 2015 г.
Ученый секретарь
диссертационного совета кандидат физ.-мат. наук
Белоусов И.Н.
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы. В связи с завершением классификации конечных простых групп возникла задача единого представления конечных простых групп автоморфизмами конечных геометрий. Перспективным направлением является поиск такого класса конечных геометрий, что каждая конечная простая группа действует флаг-транэитивяо на некоторой геометрии и все геометрии этого класса допускают классификацию. Например, класс билдпнгов Титса характеризует группы лиева типа [1]. Позднее в этом направлении возникли задачи, не связанные с групповым действием, в частности, такой является задача классификации различных классов дистанционно регулярных графов [2].
Пусть в — транзитивная группа подстановок на множестве П. Если подгруппа группы б, состоящая из всех подстановок, фиксирующих точку р е П, имеет г орбит, то говорят, что (7 является группой ранга т. Пусть г = 3 и соответствующие три орбиты — это {р}, Д, Е. Если Д п Е содержат разное число элементов, то на множестве П можно построить сильно регулярный граф Г. Для этого положим Г(р) = Д, и для каждого } 6 С окрестность вершины р9 совпадает с Д3. Если вместо Д здесь взять Е, то мы получим дополнительный сильно регулярный граф.
Д. Хигмен (см. [3], [4]) развил теорию групп ранга 3. Эти группы являются группами автоморфизмов сильно регулярных графов, причем они действуют транэитивно как на множестве вершин и ребер, так и на множестве пар различных несмежных вершин. Такие графы являются дистанционно транзитивными графами диаметра 2.
В диссертации рассматриваются неориентированные графы без петель и кратных ребер.
Граф Г диаметра с! называется дистанционно транзитивным, если для любого г 6 {О, ...,4} и для любых вершин и, ь,х,у, таких что <1(и, V) = ё(х,у) = г, существует автоморфизм д графа Г такой, что (и,ь)я = {х,у). Дистанционно транзитивные графы диаметра 2 (графы ранга 3) сыграли важную роль в классификации конечных простых групп. Около половины спорадических групп было построены как группы автоморфизмов графов ранга 3(5].
Если вершины и,ю находятся на расстоянии г в Г, то через ¿¡(и,и>) (через с^и, -ш)) обозначим число вершин в пересечении Г<+1(и) (в пересечении Г(_1(и)) с [ш]. Дистанционно регулярным графом называется граф, в котором параметры b¿(г¿, ги) и сДи,и>) не зависят от вершин и, т, а зависят только от расстояния на котором эти вершины находятся в графе Г.
Поскольку каждый дистанционно регулярный граф является вполне регулярным графом (в частности, реберно регулярным графом), то некоторые результаты об этих классах графов могут быть использованы в теории дистанционно регулярных графов.
Система инцидентности, состоящая из точек и прямых, называется а-частичной геометрией порядка (в, £), если каждая прямая содержит ровно я + 1 точку, каждая точка лежит ровно на < + 1 прямой (прямые пересекаются не более, чем по одной точке) и для любой точки о, не лежащей на прямой Ь, найдется точно а прямых, проходящих через а и пересекающих Ь (обозначение рОа(з, <)). Если а = 1, то геометрия называется обобщенным четырехугольником и обозначается Сф(в,(). Точечным графом частичной геометрии называется граф, вершинами которого являются точки геометрии, и две различные
верпзиаы смежны, если они лежат на общей прямой (коллинеарны). Легко понять, что точечный граф (граф коллинеарности) частичной геометрии pGa(s, t) сильно регулярен с параметрами: »/ = («+ 1)(1 -+ sí/a), к = s(t + 1), Л = (s - 1) + (о - ])t, ц = o(t + 1). Сильно регулярный граф с такими параметрами для некоторых натуральных чисел о, s, t называется псевдогеометрическим графом для pGa(s, t).
Цель работы. В диссертации изучаются некоторые классы геометрий (графов), их расширения и автоморфизмы. В частности, завершены программы исследования
- дистанционно регулярных локально GQ(4, ^-графов,
- примитивных дистанционно регулярных реберно симметричных локально циклических графов с числом вершин, не большим 1000,
- дистанционно регулярных расширений сильно регулярных графов с собственным значением 2,
- реберно симметричных сильно регулярных графов с числом вершин, не большим 100.
Методы исследований. Основными методами исследования являются теоретико-графовые методы и методы теории конечных групп, в частности метод Хигмена приложения теории характеров к выяснению порядков автоморфизмов дистанционно регулярных графов.
Научная новизна. Все основные результаты диссертации являются новыми:
- найдены параметры сильно (s — 2)-однородных расширений частичных геометрий pGa(s, t)\
- классифицированы дистанционно регулярные локально GQ(4, ¿)-графы;
- изучены вполне регулярные графы с í>i = 6 и сильно регулярные графы с 6i < 24;
- найдены автоморфизмы примитивных дистанционно регулярных локально циклических графов с числом вершин, не большим 1000;
- найдены автоморфизмы графа А с параметрами антиокрестности вершины в 4-изорегулярном графе fzo(3), доказано, что граф Д не является реберно симметричным;
- завершена программа изучения вполне регулярных графов, в которых окрестности вершин сильно регулярны с собственным значением 2;
- доказано, что новых реберно симметричных сильно регулярных графов с числом вершин, не большим 100, нет,
- найдены допустимые массивы пересечений дистанционно регулярных графов с А = 2, ииеющих не более 4096 вершин.
Теоретическая и практическая ценность. Работа носит теоретический характер. Ее результаты могут быть использованы в геометрии и теории графов.
Апробация работы. Основные результаты диссертации неоднократно докладывались и обсуждались на алгебраическом семинаре отдела алгебры и топологии ИММ УрО РАН, а также были представлены на следующих конференциях: VII-X Международные школы-конференции по теории групп (2008 г. Челябинск, 2010 г. Нальчик, 2012 г. Владикавказ, 2014 г. Нальчик); Международная алгебраическая конференция, посвященная 80-летию со дня рождения А.И. Кострикина (2009 г., Нальчик); Международная конференция «Группы и геометрии», посвященная 80-летию со дня рождения А.И. Старостина (2011 г., Ека-
теринбург); Международная конференция «Алгебра и линейная оптимизация», посвященная 100-летию со дня рождевия С.Н. Черникова (2012 г., Екатеринбург); Международная конференция "Алгебра и комбинаторика посвященная 60-летию A.A. Махнева (2013 г., Екатеринбург).
Публикации. Материал диссертации был опубликован в цикле работ, состоящем из 14 статей [43-56] (13 из них опубликованы в журналах из списка ВАК), и 8 тезисов докладов. Из 14 статей 5 написаны без соавторов, 3 - тремя авторами (Ефимов К.С., Махнев A.A., Нирова М.С.; Журтов А.Х., Махнев A.A., Нирова М.С.; Белоусов И.Н., Махнев A.A., Ни-рова М.С.), остальные 6 в соавторстве с Махневым A.A. Все совместные работы написаны в нераздельном соавторстве.
Структура и объем работы. Диссертация состоит из введения, 5 глав и списка литературы, содержащего 82 названия. Общий объем диссертации составляет 157 страниц.
КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении даны основные определения и обозначения, используемые в диссертации, обсуждается общая мотивировка решаемых задач, сформулированы основные результаты. В плаве 1 получено описание параметров сильно (в—2)-однородных расширений частичных геометрий рСа(в,() и классифицированы дистанционно регулярные локально графы. В главе 2 изучены вполне регулярные графы с 61 =6, сильно регулярные графы с &1 < 24 и примитивные дистанционно регулярные графы с А = 2 и числом вершин, не большим 1000. В главе 3 изучаются 4-изорегулярные графы, их сильно регулярные подграфы и автоморфизмы. В главе 4 представлена программа изучения вполне регулярных графов, в которых окрестности вершин сильно регулярны с собственным значением 2. Приведены результаты, завершающие указанную программу. Кроме того, доказано, что новых реберно симметричных сильно регулярных графов с числом вершин, не большим 100, нет. В главе 5 найдены массивы пересечений дистанционно регулярных графов с А = 2 и числом вершин, не большим 4096.
Мы рассматриваем неориентированные графы без петель и кратных ребер. Если а,Ь — вершины графа Г, то через ¿(а, 6) обозначается расстояние между а п Ь, а через Г,(а) — подграф графа Г, индуцированный множеством вершин, которые находятся в Г на расстояний г от вершины а. Подграф Г] (а) называется окрестностью вершины а и обозначается через [а]. Через а1 обозначается подграф, являющийся шаром радиуса 1 с центром о.
Регулярным графом степени к называется граф Г, таков что для любой вершины и £ Г выполняется равенство |Г(и)| = к. Реберно регулярным графом с параметрами (и, к, А) называется регулярный граф степени к на и вершинах, любое ребро которого лежит точно в А треугольниках. Вполне регулярным графом с параметрами (ь,к,\,11) называется реберно регулярный граф с параметрами (г), к, А), в котором любые две вершины и, и) 6 Г на расстоянии 2 имеют ровно ц общих соседей. Сильно регулярным графом с параметрами
называется реберно регулярный граф с параметрами (V, к, А), в котором любые две несмежные вершины и, и> € Г имеют ровно ц общих соседей.
Заметим, что сильно регулярный граф с /I > 0 является дистанционно регулярным графом диаметра 2, а дистанционно регулярный граф с Л > 2 — вполне регулярным графом с к = Ьо, \ = к — Ь^ — I а /I = с?.
Пусть задан класс графов Т. Мы скажем, что граф Г является локально Т-графом, если для любой вершины а € Г имеем Г(а) а Т. Можно поставить задачу описания локально ^"-графов. Если граф Г вершинно транзитивен, то окрестности всех его вершин изоморфны, и граф Г является локально ^"-графом, где ^состоит из графов, изоморфных некоторому графу Д. В этом случае назовем Г локально А-графом. В более общем случае Т может быть классом графов, удовлетворяющих некоторым условиям. Например, класс связных, реберно регулярных графов — это в точности класс связных, локально регулярных графов.
Определим несколько сильно регулярных графов, которые будут фигурировать в диссертации, а также являются примерами локально Д-графов.
Через А"т11,..,тп обозначим полный п-Эольный граф, с долями порядков т1,...,тпп. Если т 1 = ... = тПп = тп, то соответствующий граф обозначается через Кпхт. Граф АТ1т называется т-лапой. Графом Тэйлора называется дистанционно регулярный граф с массивом пересечений {к,ц, 1; 1,р,к}.
Пусть М и N—конечные множества порядка шип, соответственно. Два элемента из М х N будем считать смежными, если они различаются точно в одной координате. Полученный граф называется тп х п-решетксгй; при т = п он сильно регулярен с параметрами (п2,2(п — 1), п — 2,2).
Треугольным графом Т(п) называется граф 2-подмножеств множества порядка п, в котором две вершины смежны тогда и только тогда, когда они пересекаются в точности по одной точке. Граф Т(п) сильно регулярен и имеет параметры (п(п —1)/2,2(п - 2), п — 2,4). Окрестность каждой вершины в Т(п) изоморфна 2х(п- 2)-решетке, т.е. Т(п) — локально 2 х (л — 2)-решетка.
Единственный сильно регулярный графе параметрами (27,16,10,8) называется графом Шлефли. Единственный сильно регулярный граф с параметрами (16,10,6,6) называется графом Клебша. Граф Шлефли является локально графом Клебша.
Изучение автоморфизмов дистанционно регулярных графов опирается на метод Хиг-мена приложения теории характеров конечных групп, представленный в третьей главе монографии Камерона [6|. При этом граф Г рассматривается как симметричная схема отношений (Х,И) с <1 классами, где X — множество вершин графа, Но — отношение равенства на Л" и для г > 1 класс Я, состоит из пар (и, и') таких, что (¿(и, и>) = г. Для и Е Г положим ki = |Г|(и)|, v = |Г|. Классу Я, отвечает граф Г, на множестве вершин x, в котором вершины и, к/ смежны, если (и,ю) 6 Я^ Пусть А{ — матрица смежности графа Г^ для г >0чАо = ! — единичная матрица. Тогда А,А3 = А7151 подходящих
неотрицательных целых р^, называемых числами пересечений графа Г.
Пусть Р, — матрица, в которой на месте {], I) стоит р\у Тогда собственные значения р ((О), ...,рх(<1) матрицы Р\ являются собственными значениями графа Г кратностей тп о = 1 Матрицы Р и ф, у которых на месте (¿,_/) стоят стоят р^(г) и <^(г) = тп}р,(з)/к,
соответственно, называются первой и второй матрицей собственных значений схемы и связаны равенством РС} = С}Р = у1.
Пусть щ н ■ш^ — левый и правый собственные векторы матрицы Р^, отвечающие собственному значению р] (.}) и имеющие первую координату 1. Тогда кратность т} собственного значения Р1(з)равна (здесь — скалярное произведение в Евклидовом пространстве К"). Фактически, являются столбцами матрицы Р и тп3и3 являются строками матрицы (¡¿.
Подстановочное представление группы й = Аи1;(Г) на вершинах графа Г обычным образом дает матричное представление ф группы С? в С). Пространство С" является
ортогональной прямой суммой собственных (З-инвариантных подпространств И-о, ■. •, И^ матрицы смежности А = А\ графа Г. Для любого д & С матрица Ф(д) перестановочна с А, поэтому подпространство \У, является ^(С)-инвариантным. Пусть — характер представления . Тогда для д € О получим
л
где с*}(д) — число точек х из X таких, что (х, х9) <Е Л3. Заметим, что значения характеров являются целыми алгебраическими числами, и если правая часть выражения для — число рациональное, то х>(9) — целое число.
В главе 1 получено описание параметров сильно (я — 2)-однородных расширений частичных геометрий р<За(5, () и классифицированы дистанционно регулярные локально Сд(4,0-графы.
В кандидатской диссертации М.С. Нировой классифицированы з-однородные и сильно (я — 1)-однородные расширения частичных геометрий рва(я,4) (см. [7]).
Пара (а, Ь) частичной геометрии (Р, С) называется флагом, если точка а принадлежит прямой Ь, и антифлагом в противном случае. Если (а,Ь) является антифлагом, то через /(о, Ь) обозначим число точек в Ь, коллинеарных а. Геометрия называется (^-однородной, если для любого антифлага (о, Ь) число /(а, Ь) равно 0 или и сильно (^однородной, если это число всегда равно у. Геометрия рС<(я, £) является сетью, а рС,+ 1(я,4) является 2-схемой с Л = 1. Если 5 — частичная геометрия р(За(я, 4), то двойственная геометрия (С, Р), в которой каждая точка отождествляется с пучком проходящих через нее прямых, является частичной геометрией р£7а(4, в).
Теорема 1.1 ([46]). Пусть 3 — сильно (я — 2)-однородная геометрия ЕрСа{$Л), Г = Г(5). Тогда либо геометрия Б является расширением двойственной 2-схемы рС(+1(24 + 2,1), Г — псевдогеометрический граф для сети рСъ(21 + 3,24) и дополнительный граф к блочному графу является псевдогеометрическим графом для р<31+2(24 + 3, 42 -I- 24), либо выполняется одно из следующих утверждений:
(1) а = 1, Г — псевдогеометрический граф длярСв(9,8), рСг(5,8), р<34(7,24), рС?а(9,32) илирв 10(13,120) и геометрия 5 - это £<3(3(8,1), £<3(3(4,2), £6^(6,4), £С<2(8,4) или ЕО(3(12,10) соответственно;
(2) 4 = а > 1, Г является псевдогеометрическим графам для рС6(9,8) и геометрия 5 — это ЕрО^, 4) для некоторого 4 6 {2,..., 5}-
(3) Г — псевдогеометрический граф для рв3(6,20), р<34(7,3), ;Х34(7,4), р<34(7,8) или рв4(7,20) ив - это Ер02(5,8), Ерв2{6,1), ЕрЬ3(6,2), £р£3(6,4) или ЕрСъ(6,10) соответственно;
(4) Г является псевдогеометрическим графом для pG^(8,140), pGe(9,56), pGe(9,8r) (г 6 {2,4}), pGe(9,2t) (t e {3,7,13}), pGe(9,32), pG„(ll,40), pGe(ll,95) или pGg(ll,2u) (u € {4,16}) u геометрия S - это EpG4(7,80), EpG2{8,14), EpG3(8,3r), EpG^SJ), EpGb(8,20), EpGi(W, 12), £,pG4(10,38) или £pG5( 10,u) соответственно;
(5) 10 < s < 20, Г — псевдогеометрический граф для одной из геометрий pGB(l2,99), pG12( 15,56), pG12(15,16), pG12(15,26), pGl5(18,170), pGie(19,56), pG17(20,323), pG18(21,150) или pGje(21,24) и S - это EpGa(ll, 9a) (а e {3,4,6}), EpGa(14,4a) (a e {2,3,5,9}), EpG7( 14,8), £pG7(14,13), EpGa(n, 10a) (а 6 {2,3,8}), EpGg( 18,28), EpGa(\9,17a), a € {3,10,13}, FpGe^O, 45) или £pG1B(20, 18) соответственно;
(6) 20 < s < 40, Г — псевдогеометрический граф для одной из геометрийpGj2(35,136), pGзг(35,136), pG32(35,136) или 104) и S — это одна из геометрий EpGn(M,44), £pG2e(34,112), £pG7(34,28) или £pGi7(34,52) соответственно,-
(7) 40 < s, Г является псевдогеометрическим графом длярйц(51,880) илирС48(51,200) и S — одна из геометрий EpG^(bO,264) или EpGa(50,4а) (а € {3,8,23,33}) соответственно.
В работе Ф.Бюкенхаута и К.Юбо |8] рассматривается задача классификации локально полярных пространств, в частности, локально GQ(s, ^-графов. Там же получено решение этой задачи в случае s = 2.
В случае s = 3 описание локально GQ(s, £)-графов завершено в работе A.A. Махнева
[9].
В случае s = 4 известны вполне регулярные локально GQ(4, t)-графы для t € {2,4,6,8, 11,16} (см. [10-15|). Кроме того, известны сильно регулярные локально GQ(4, t)-графы [16].
В диссертации нэучены вполне регулярные локально G<2(4,£)-графы, t £ {1,12}. Тем самым завершена классификация дистанционно регулярных локально GQ(4, ¿)-графов.
Теорема 1.2 ([54]). Пусть Г — связный вполне регулярный локально GQ(4,12)-граф с параметрами (v,k, А, р). Тогда диаметр Г равен 3 u р € {56,60,64,70,80,84}.
Следствие 1.1. Пусть Г — дистанционно регулярный локально ССЦ4,Ь)-граф с параметрами (v,k,X,p). Тогда выполняется одно из утверждений:
(1) t = 1, либо р = 4 и Г — граф Джонсона .7(10,5) или его стандартное частное, либо р = 8 и Г имеет массив пересечений {25,16,1; 1,8,25},-
(2) t = 2, Г — граф с параметрами (126,45,12,18) на множестве векторов нормы J в 6-мерном ортогональном пространстве типа "- " над GF(3) или Г — единственный локально С(^(4,2)-граф с массивом пересечений {45,32,12,1; 1,6,32,45};
(3) t = 6, Г имеет параметры (726,125,28,20) или Г — граф с массивом пересечений {125,96,1;1,48,125}.
Для реберно регулярного графа с параметрами (v,k, А) параметр bi равен к — А — 1. Глава 2 посвящена изучению графов с малыми значениями Ь\ и локально циклических дистанционно регулярных графов с числом вершин, не большим 1000.
Хорошо известно, что связный граф с b\ = 1 является многоугольником или полным многодольным графом с долями порядка 2. Вполне регулярные графы с 2 < bt <5 изучены в [17-19]. Если 61 = 6, то наиболее сложный случай возникает при к = 10, А = 3. Этот случай изучается в параграфе 2.1.
Пусть Г — связный граф, в котором окрестности вершин изоморфны графу Петер-сена. Тогда [2, теорема 1.16.5] Г является дистанционно регулярным графом с массивом пересечений {10,6; 1,6} (граф Т(7)), {10,6,4,1; 1,2,6,10} (граф Конвея-Смита) или {10,6,4; 1,2,5} (граф Доро). Ректаграфом называется вполне регулярный граф с Л = 0 и (1 = 2.
Теорема 2.1 ([43]). Пусть Г — связный вполне регулярный граф с параметрами (v, 10,3,/í). Тогда выполняется одно из следующих утверждений:
(1) диаметр Г равен 2 и Г является дополнительным графом к треугольному графу Т(7) или одним из десяти графов с параметрами (28,10,3,4);
(2) ц = 3, диаметр Г равен 3 и 34 < v < 37;
(3) ft = 2 и Г является графом Конвея-Смита или графом Доро.
Из теоремы 2.1 и результатов [20] вытекает классификация вполне регулярных графов с 6j = 6.
Следствие 2.1. Пусть Г — связный вполне регулярный граф с = 6. Тогда Г является одним из следующих графов:
(1) полный многодольный граф КТХ7, граф с параметрами (25,12,5,6), 7 х 7-решетка, треугольный графТ(9), дополнительный граф к5 х 5-решетке или к треугольному графу Т(7), граф Хофмана-Синглтона или его дополнение, граф с параметрами (26,10,3,4) или его дополнение;
(2) полный двудольный граф Л"в.8 с удаленным максимальным паросочетанием, граф Тэйлора с параметрами (28,13,6,6), в котором окрестности вершин изоморфны графу Пэли Р(13) или граф Тэйлора с параметрами (32,15,8, 6), в котором окрестности вершин изоморфны треугольному графу Т(6);
(3) (i = 1, окрестность каждой вершины является 7-кокликой, или объединением изолированных п-клик для п = 2,3 или 6;
(4) /1 = 2 ü либо
(i) Г является ректаграфом с v < 27 и диаметра, не большего 7 (в случае v = 27 или d(Г) =7 граф Г является 1 -кубом), либо
(п) окрестность каждой вершины в Г является объединением четырех изолированных ребер, либо
(Ш) Г — дистанционно регулярный граф с массивом пересечений {9,6,1; 1,2,9}, гриф Конвея-Смита или граф Доро;
(5) ц = 3 и либо
(г) Г — дистанционно регулярный граф с массивом пересечений {8,6,1; 1,3,8}, либо (и) Г — локально девятиугольный граф диаметра 3, каждый ¡i-подграф является 3-кокликой или объединением изолированной вершины и ребра, Ьг(и, х) < 3 для любых вершин и,х с d(u, т) = 2 и |Г3(и)| < 10, либо
(ш) к = 10, диаметр Г равен 3 и 34 < v < 37, либо
(iv) к = 11, диаметр Г равен 3, v = 36 и Гэ(и) является 2-кликой для некоторой вершины и;
(6) /4 = 4 и Г - граф Джонсона J(7,3).
Хотя вполне регулярные графы с малыми значениями параметра b¡ удалось классифицировать только для bi < 6, но сильно регулярные графы удалось изучить до bt < 23.
В параграфе 2.2 изучаются сильно регулярные графы с Ь] < 24.
Графом Джонсона J(n, тп) называется граф, вершинами которого являются т-элемент-ные подмножества данного п-элементного множества, причем две вершины а, b смежны, только если |а П Ь| — тп — 1. Графом Хемминга Н(п,т) называется граф, вершинами которого являются элементы из X", где \Х\ = т и две вершины смежны, только если расстояние Хемминга между ними равно 1. Граф Пэли Р(д) в качестве вершин имеет элементы поля Fq, <7 = 1 (mod 4), и две вершины а, Ь смежны, только если b — а является ненулевым квадратом в Fq. Граф Петерсена — это дополнительный граф для треугольного графа Т(Ъ) (он имеет параметры (10,3,0,1)). Граф Шрикханде — это единственный сильно регулярный локально шестиугольный граф с параметрами (16,6,2,2). Имеется точно 3 сильно регулярных графа, имеющих параметры графа Т(8), но не пзоморфных Т(8). Эти графы называются графами Чанга.
Сильно регулярные графы с собственным значением —2 были классифицированы Зей-делем [2, теорема 3.12.4]. Любой зейделев граф — это либо полный многодольный граф А*гх2, либо решетчатый или треугольный граф, либо один из графов Шрикханде, Чанга, Петерсена, Клебша или Шлефли.
Теорема 2.2 ((49]). Пусть Г является сильно регулярным графом с 0 < bj < 24. Тогда Г — граф из следующего списка:
(1) граф с параметрами (4bt + l,2bi,6i — l,bi), bi ^ {5,8,14,17,19,23} или полный многодольный граф Kr%(bt+1>;
(2) зейделев граф или его дополнение;
(3) псевдогеометрический граф для GQ(s,t), {s,t} е {{2,2},{2,4},{3,3},{3,5},{4,4}, {6,3}} или его дополнение;
(4) псевдогеометрический граф для сети pGt(s, t), где либо t = 2,s=3,4,5,...,12, либо t = 3, s = 4,5, ...,9, либо t = 4, s = 6,7,8, либо t = 5, s = 8, либо t = s - 2, s = 7,8,9;
(5) псевдогеометрический граф для pG2(4, t) (t = 3,7), pG2(5,5), pG3(s, 2) (s = 5,6,8,9, 12;, pG3(5,7), pG„(7,2), pG4(7,3), pG4(8,3), pGE(9,3), pG6(14,2), pGe(8,5), pGe(15,2), pGg(15,2), pGg( 18,2), pG9(15,3), pG10(15,3), pG14(20,3), pG,e(24,2), pG16(19,3) или рС2о(24,3);
(6) дополнительный граф либо к графу из пункта (5), либо к псевдогеометрическому графу для GQ(4,6);
(7) граф с параметрами (50,7,0,1), (56.10,0,2), (77,16,0,4), (81,20,1,6), (82,36,15,16), (85,30,11,10), (85,14,3,2), (99,14,1,2), (100,33,14,9), (100,22,0,6), (126,25,8,4), (136,30, 8,6), (162,23,4,3), (243,22,1,2), (300,26,4,2), или (400,21,2,1);
(8) дополнительный граф для графа из пункта (7).
В.П. Буриченко и A.A. Махнев [21] нашли массивы пересечений дистанционно регулярных локально циклических графов с числом вершин не большим 1000. В [22] найдены возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярных локально циклических графов с числом вершин не большим 1000.
Предложение 2.1. Пусть Г является дистанционно регулярным графом диаметра, большего 2, на v < 1000 вершинах. Если А = 2 и ц > 1, то либо Г имеет массив пересечений графа Хэмминга Н(п,3), п = 3,4, либо верно одно из утверждений:
(1) Г — примитивный граф с массивам пересечений {15,12,6; 1,2,10}, {19,16,8; 1,2,8}, {24,21,3; 1,3,18}, {35,32,8; 1,2,28}, {51,48,8; 1,4,36};
(2) Г — антиподалъный граф с ß — 1 и массивом пересечений {2г +1,2г — 2,1; 1,2,2г + 1}, г £ {3,4,...,21} - {10,16} uv = 2r(г + 1);
(3) Г — антиподалъный граф с ц > 3 и массивом пересечений
{15,12,1; 1,4,15}, {18,15,1; 1,5,18}, {27,24,1; 1,8, 27}, {35,32,1;1,4,35}, {45,42,1; 1,6,45}, {42,39,1;1,3,42}, {75,72,1; 1,12,75}.
В [23-26] найдены возможные простые порядки автоморфизмов графов с 4 первыми массивами пересечений из пункта (1) заключения предложения. В параграфе 2.3 изучаются автоморфизмы гипотетического дистанционно регулярного графа с массивом пересечений {51,48,8; 1,4,36}. Тем самым завершается описание автоморфизмов графов из пункта (1) заключения предложения. Ни один из этих графов не является реберно симметричным.
Граф с массивом пересечений {51,48,6; 1,4,36} имеет v = 1 + 51 + 612 + 136 = 800 вершин и спектр511, II102,3425, -Ö272, причем Г2 — сильно регулярный графе параметрами (800,612,468,468) и неглавными собственными значениями 12, —12.
Теорема 2.3 ([55]). Пусть Г — дистанционно регулярный граф, имеющий массив пересечений {51,48,8; 1,4,36}, G = Aut(r), g — элемент из G простого порядка р и fi = Fix(g). Тогда n(G) С {2,3,5,17} и выполняются следующие утверждения:
(1) ß — пустой граф и либо
(г) р = 5, ах(д) = 400 + 100i - 60s, а2(д) = 120s и а3(д) = 400 - 100i - 60s, либо
(гг) р = 2, üj(д) = 400 + 40т - 24i, а2{д) = 48£ и а3(д) = 400 - 40r - 24t;
(2) р = 17, |П| = 1, а2(д) = 204 и либо аj(p) = 595,а3(д) = 0, либо at(g) = 255 и а3(д) = 340;
(3) р = 3, либо
(г) 2 < |П| < 14 и Я состоит из вершин попарно находящихся на расстоянии 3,
либо
(гг) 14 < |П| < 62, либо
(ггг) а3(д) = 0, а^) = 120r+40-5o0(p), а2(д) = 760 + 4a0(ff) - 120г и 65 < |П| < 98;
(4) р = 2, |f2| четно и либо
(г) ai(g) = а(д) = 0 и П е {32,80}, либо
(и) 4 < |П| < 62, либо
(т) а3(д) =0, at(g) =80г-5а0(д) ф 0, а2(д) = 20оо(д) + 800 - 80r и 64 < |П| < 106.
Следствие 2.2. Граф с массивом пересечений {51,48,8; 1,4,36} не является реберно с имме тричным.
Заметим, что В.П. Буриченко и A.A. Махнев не рассматривали случай /1 = 1. A.A. Махнев поставил задачу нахождения массивов пересечений антиподальных дистанционно регулярных графов диаметра ЗсА = 2, /I = 1 л числом вершин, не большим 1000. В параграфе 2.4 решена более общая задача. Найдены массивы пересечений антиподальных дистанционно регулярных графов диаметра ЗсА<2и/1 = 1. Далее, найдены возможные порядки и подграфы неподвижных точек автоморфизмов дистанционно регулярного графа с массивом пересечений {42,39,1; 1,1,42}.
Предложение 2.2 ([52]). Пусть Г является антиподалъным дистанционно регулярным графом диаметра 3eA<2u/i = l. Тогда выполняется одно из следующих утверждений:
(1) А = 0 и к е {2,6,56};
(2) Л = 1 и Г — дистанционно транзитивный граф с массивом пересечений {2е,2* — 2,1; 1,1,2е};
(3) А = 2, Г имеет массив пересечений {42,39,1; 1,1,42} и спектр 421,6™, -I30, -5903.
Существование графа в пункте (1) предложения равносильно существованию сильно регулярного графа с параметрами ((k + I)2 + 1,к + 1,0,1) (графа Мура).
Теорема 2.4 ([62]). Пусть Г — дистанционно регулярный граф, имеющий массив пересечений {42,39,1; 1,1,42}, G = Aut(F), g — элемент из G простого порядка р и П = Fix(i). Тогда выполняются следующие утверждения:
(1)0 — пустой граф и либо
(i) р = 43, а3(д) = 0, a^s) = 430г и г € {0,1,2,3}, либо
(гг) р = 5, а3(д) = 200s + 120, at(g) = 50t + 40 и 5t + 20s < 155, либо
(ж) р = 2, а3(д) = 80s + 40, ац(д) = 801 и 1 + s <21;
(2) П лежит в антиподальном классе графа Г и либо (г) р = 7, |П| = 26 и |a2(ff)| > 42 • 26, либо
(гг) р = 3, [П| 6 {1,4, ...,40} и |oi(i)| < 42|fi|, либо (да) р = 2, |П| 6 {2,4, ...,38} и |а2(р)| > 42|П|;
(3) р = 13 и fî является 4-кликой;
(4) р = 2 и П — шестиугольник или вторая окрестность вершины в графе Хофмана-Синглтона.
Следствие 2.3. Группа автоморфизмов дистанционно регулярного графа с массивом пересечений {42,39,1; 1,1,42} действует интранзитивно на множестве вершин.
В главе 3 изучаются 4-изорегулярные графы, их сильно регулярные подграфы и автоморфизмы. Для подмножества вершин S графа Г через Г(5) обозначим naes([a] — S).
Граф Г называется ^изорегулярным, если для любого г < t и любого г-вершинного подмножества S число |Г(5)| зависит только от изоморфного типа подграфа, индуцированного S. Заметим, что класс 2-изорегулярных графов совпадает с классом сильно регулярных графов. Граф Г на » вершинах называется абсолютно изорегулярным, если он является (и — 1)-изорегулярным. Далее, t-изорегулярный граф называется точно t-изорегулярным, если он не является (t + 1)-иэорегулярным.
Камерон [27, теорема 8.21] доказал, что каждый 5-иэорегулярный граф Г является абсолютно изорегулярным и, с точностью до перехода к дополнительному графу, является полным многодольным графом Ктх„, пятиугольником или 3 х 3-решеткой. Далее, каждый точно 4-изорегулярный граф, с точностью до перехода к дополнительному графу, является псевдогеометрическим графом для pGr(2г,2т3 + Зг2 - 1). Через Fzo(r) будем обозначать такой граф. При г = 1 получим точечный граф единственного обобщенного четырехугольника порядка (2,4), а при г = 2 — граф Маклафлина.
Существование плотной сферической 5-схемы в S"'1 (см. [28]) равносильно существовав нию графа Izo(r), где п = (2г+1 )2 —2. В [28, следствие 4.7] доказано несуществование плотных 5-схем для бесконечного набора значений параметра г: 3,4,6,10,12,22,28,30,34,42,46,
В параграфе 3.1 найдены параметры 6 сильно регулярных подграфов из Г = 1го{г): Е = [о], Д = Г2(а) для вершины а £ Г; Е(6), Е2(*Ь) для вершины Ь е Е; Д(с), Д2(с) для вершины се Д.
Предложение 3.1. Пусть Г — псевдогеометрический граф для р(Зг(2г, 2г3 -ьЗг2 - 1). Тогда он имеет v = 8г4 + 16г3 + 6г2 — 2г — 1 вершин и собственные значения к — 4г4 + 6г3,г, -(2г3 + Зг2) кратностей 1,/ = 8г4 + 16г3 + 2г2 - 6г,р = 4г2 + 4г-2 соответственно. Далее, для любой вершины а
(1) подграф Е = [а] является псевдогеометрическим графом для рС,-\(1т - 1,г3 +г2 — г - 1), имеет = 4г4 + 6г3 вершин и собственные значения к\ = 2г4 + г3 - Зг2 + г, г, = г, = —(г3 + г2 - г) кратностей 1, Д = 4г4 + 6г3 - 4г2 - 4г + 2,51 = 4г2 + 4г - 3 соответственно;
(2) подграф Д = Г2(а) сильно регулярен, имеет у? = 4г4 + 10т3 + 6г2 - 2г — 2 вершин и собственные значения к? = 2г4 + Зг3,г2 = г, = —(г3 + 2г2) кратностей 1,/2 = 4г4 + 1 Ог3 + 2г2 - 6г, рз = 4г2 + 4г - 3 соответственно.
Предложение 3.2. Пусть Е — псевдогеометрический граф для рСг-\(2т — 1, г3 + г2 — г — 1). Тогда он имеет v = 4г4 + 6г3 вершин и собственные значения к = 2г4 + г3 — Зг2 + г,г,—(г3+г2 — г) кратностей 1,/ = 4г4 + 6г3 — 4г2 — 4г + 2, д = 4г2+4г —3 соответственно. Далее, для любой вершины Ь 6 Е
(1) подграф Е(Ь) является псевдогеометрическим графом для рСг_2(2г — 2, (г3 — Зг — 2)/2), имеет ь^ = 2г4 + г3 — Зг2+г вершин и собственные значения т4-г3—3г2+3г, г, —(г3 — Зг)/2 кратностей 1, /1 = 2г4 + г3 - 7г2 - Зг + 3,5] = 4г2 + 4г - 4 соответственно;
(2) подграф Е2(&) сильно регулярен с параметрами (2г4+5г3+Зг2—г —1, г4 + г3 —г2, (г4 — г3 - Зг2 + Зг)/2, (г4 - гг)/2) и собственными значениями г4 + г3 - г2, г, -(г3 + 2г2 - г)/2 кратностей 1, 2г4 + 5г3 — г2 — 5г + 2,4г2 + 4г — 4 соответственно.
Предложение 3.3. Пусть Д является сильно регулярным графом с параметрами (4г4 + 10г3 + 6г2 — 2г — 2,2г4 4- Зг3, г4 - 2г2 + г, г4 + г3) и собственными значениями к = 2г4+Зг3,г,-(г3 + 2г2) кратностей 1,4г4+ 10г3 + 2г2-6г,4гг + 4г-3 соответственно. Если г > 2, то для любой вершины с 6 Д
(1) подграф Д(с) является сильно регулярным графом с параметрами (2г4 + Зг3,г4 — 2г2 + г, (г4 - 2г3 - Зг2 + 6г)/2, (г4 - г3 - 2г2 + 2г) /2) и собственными значениями г4 - 2г2 + г, г, -(г3 + г2 - 2г)/2 кратностей 1,2г4 + Зг3 - 4г2 - 4г + 3,4г2 + 4г - 4 соответственно;
(2) подграф Д2(с) сильно регулярен с параметрами (2г4 + 7г3 + 6г2-2г-3,г4-|-2г3,(г4-Зг2 2г)/2, (г4 -1- г3)/2), собственными значениями т4 + 2г3,г, -(г3 + Зг2)/2 кратностей 1,2г4 + 7г3 + 2г2 - 6г, 4г2 + 4г — 4 соответственно.
Далее, с помощью метода Хигмена для автоморфизма д графа /го(г) найдена формула для значения характера, полученного при проектировании на подпространство размерности 4г2 + 4г - 2
Х2(д) = Ыя) - 01(р)/г)/((г + 1)(2г + 1)) + (2г2 + 2г - 1)/(г + 1).
Найдены возможные простые порядки автоморфизмов д графа /го(г) таких, что подграф П = Р'1х(р) является пустым, кликой или кокликой.
Теорема 3.1 (|44]). (1) Если П - пустой граф, то (г) р делит (2г + 1)(4г3 + 6г2 - 1), в частности, рф 2,
(гг) если р = 3, то г = 1 (mod 3), Qj (g) = wt(2t + 1) и u> + 1 делится наг + 1.
(2) Если Л является п-кликой, то п = 1 и либо р = 37, г = 37и + 17, либо р = 2.
(3) Если ÍÍ является т-кокликой, тп > 2, тоЗ < т < 4т2 + 4г - 2, р делит г и т + 1.
A.A. Махнев [29] доказал, что псевдогеометрический граф для pG2(5,32) не существует. Так как окрестность вершины в графе Izo(3) является псевдогеометрическим графом дпя рСг(5,32), то и граф Izo(3) не существует. Однако вопрос о существовании сильно регулярного графа с параметрами (640,243,66,108) (это параметры второй окрестности вершины в графе Izo(3)) остается открытым.
Пусть Г является сильно регулярным графом с параметрами (640,243,66,108), а — вершина графа Г. Тогда Г имеет собственные значения к = 243,г = 3, s = —45 и достигается равенство во втором условии Крейна (s -+■ l)(fc -+- s + 2rs) < (к + s)(r + l)2. Поэтому [о] является сильно регулярным графом с параметрами (243,66,9,21) и Г2(а) является сильно регулярным графом с параметрами (396,135,30,54). В работах [30, 31] найдены возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярных графов с параметрами (243,66,9,21) и (396,135,30,54). С помощью этих результатов найдены возможные порядки и подграфы неподвижных точек автоморфизмов сольно регулярного графа с параметрамп (640,243,66,108). При этом решалась задача восстановления автоморфизма графа по его действию на окрестности и на антиокрестности неподвижной точки.
Теорема 3.2 ([45]). Пусть Г является сильно регулярным графом с параметрами (640,243,66,108), G = Aut(r), g — элемент простого порядка р из G, П = Fix(<j). Тогда выполняется одно из следующих утверждений:
(1) fi - пустой граф, либо р = 5 и at(g) 6 {240,480}, либо р = 2 и a^g) е {96,192, 288,384,480,592};
(2) П является 1 -кликой, р = 3 и оц(д) = 99;
(3) П является т-кокликой, т > 2, р = 3 и (|П|, at(g)) е {(4,204), (13,87), (13,519), (22, 402),(31,285),(37,351),(40,168)};
(4) р = 3, П является регулярным графом степени 3Í, 0 < í < 24, a¡(g) = 54r + 9t + 135g + 6s, s ± 0 и 28 < |П| = 1 + 3t + 3s < 100;
(5) p = 2, П содержит вершину степени 2í + 1, ai(g) = 36г + 61 + 45g + 12s + 12, q четно, -2 < q < 6, s 0 и 16 < |fi| = 2t + 2 + 6s < 154.
Следствие 3.1. Сильно регулярный граф с параметрами (640,243,66,108) не является реберно симметричным.
В главе 4 изучаются вполне регулярные графы, в которых окрестности вершин сильно регулярны с собственным значением 2, небольшие сильно регулярные графы и их автоморфизмы.
А.Л. Гаврилюком и A.A. Махневым предложена программа изучения вполне регулярных графов, в которых окрестности вершин — сильно регулярные графы с данными параметрами и собственным значением 2.
В работе [32] получено описания класса Q сильно регулярных графов с собственным значением 2. Там же классифицированы графы, в которых окрестности вершин — графы из Q с параметром А' = 1. В работах [33-36] получено описание графов, в которых окрестности вершин — графы из Q с параметром А' = 0.
Предложение 4.1. Если Г е Q, то выполняется одно из следующих утверждений:
(1) Г — объединение изолированных треугольников, четырехугольник или пятиугольник;
(2) Г — псевдогеометрический граф для pG(2l_6y3(7sß,s - 3), s делится на 3, или псевдогеометрический граф для s — 2);
(3) Г иммет параметры v = (2s2 -I- 5s + 3)/3, k = (2s2 - 4s)/3, Л = (2s2 - 13s + 24)/3, fi = (2s2 - 10s + 12)/3, usE-1 (mod 3);
(4) Г — псевдогеометрический граф для pG,_2(s, t), где (s,t) принадлежит либо (г) {(3,3), (3,5), (3,9)}, либо
(И) {(4,1),(4,7),(4,9),(4,12),(4,17),(4,27)}, либо (Ш) {(5,1),(5,7),(5,9),(5,12),(5,17),(5,27)}, либо (w) {(6,18),(7,25),(8,3),(8,5),(8,15),(8,21),(9,42)}, либо (») {(14,2),(14,4),(14,32), (32,5)};
(5) Г имеет параметры либо
(г) (26,15,8,9), (36,14,4,6), (45,32,22,24), (50,7,0,1), (56,10,0,2), (76,30,8,14), (77,16,0,4), либо
(«) (81,20,1,6), (99,56,28,36), (100,22,0,6), (105,52,21,30), (105,32,4,12), (120,42,8,18), (126,100,80,84), либо
(Иг) (126,50,13,24), (154,72,26,40), (162,56,10,24), (162,92,46,60), (176,70,18,34), (225,128,64,84), (232,154,96,114), (243,110,37,60), либо
(iv) (253,112,36,60), (300,182,100,126), (351,210,113,144), (375,272,190,216), (441, 352,276,300), (476,342,236,270), (540,392,274,312), (703,520,372,420), (1344,221,88,26), (1911,270,105,27).
В работе [37] приведено описание вполне регулярных графов, в которых окрестности вершин либо являются псевдогеометрическими графами для pG,_t), либо сильно регулярны с параметрамп v = (2s2 + 5s 3)/3, k = (2s2 - 4s)/3, Л = (2s2 - 13s + 24)/3, ß = (2s2 — 10s + 12)/3, и s = —1 (mod 3). Следующий результат является первоначальной редукцией графов, в которых окрестности вершин сильно регулярны с параметрами пункта (5) заключения предложения.
Теорема 4.1 ([48]). Пусть Г — связный вполне регулярный граф, в котором окрестности вершин сильно регулярны с параметрами (t>', k',X',fi') из пункта (5) заключения предложения 4.1. Если А' > 2, то верно одно из следующих утверждений:
(1) Г — сильно регулярный граф с параметрами (100,36,14,12), в котором окрестности вершин имеют параметры (36,14,4,6);
(2) «¿(Г) = 3 и либо
(г) ß е {18,24,36} и окрестности вершин имеют параметры (105,32,4,12), либо (ii) fi = 35 и окрестности вершин имеют параметры (162,56,10,24), либо (ш) ц = 66 и окрестности вершин имеют параметры (243,110,37,60), либо (iv) ß = 70 и окрестности вершин имеют параметры (253,112,36,60).
Эта теорема существенно уточняется в статье И.Н. Белоусова, A.A. Махнева и М.С. Нировой [50], завершающей реализацию вышеуказанной программы.
Теорема 4.2. Пусть Г — связный вполне регулярный граф, удовлетворяющий условиям теоремы 4.1. Тогда d(Г) = 2.
Теорема 4.3. Пусть Г — сильно регулярный граф с параметрами (100,36,14,12), G = АиЦГ), д — элемент простого порядка р из G и Í2 = Fix(g). Тогда выполняется одно из следующих утверждений:
(1) П - пустой граф, либор = 5 uüi(j) е {0,100}, либор = 2 и at(g) е- {0,20,40,.... 100},-
(2) Q является п-кликой, либо р = 7 и п = 2, ац(д) = 42 или п = 9 и Qi(s) 6 {14,84}, либо р = 3, п е {1,4,7,10} и a¡ (g) + Ап делится на 10;
(3) П является 1-кокликой, 2 < Í < 10, то либо р = 3, Qt(g) = 10г -41 и I € {4,7,10}, либо р = 2, ai (g) = 20s — 41, каждая вершина из Г — Í2 смежна с четным числом вершин изП ule {4,6,8,10};
(4) р = 3, |П| =3t+ 1, 4 < t < 9 и 12£ + 4 + сц(д) € {70,100,130,160};
(5) р = 2, |П| = 2з, 2 < s < 25 и 8s + а,(д) делится на 20.
Следствие 4.1. Пусть Г — реберно симметричный сильно регулярный граф с параметрами (100,36,14,12), в котором котором окрестности вершин сильно регулярны с параметрами (36,14,4,6). Тогда Г — граф ранга 3 и группа Aut(r) изоморфна Aut(Jj).
Из этого следствия и результатов [32-37] получаем
Следствие 4.2. Пусть Г — дистанционно регулярный граф, в котором окрестности вершин — графы из Q. Тогда либо окрестности вершин в Г — объединения изолированных треугольников, либо Г — сильно регулярный граф с параметрами (6,4,2,4), (27,16,10,8), (35,16,6,8), (100,36,14,12), (162,56,10,24), (176,40,12,8), (210,95,40,45), (245,64,18,16), (275,112,30,56), (372,56,10,8) или (486,100,22,20), либо диаметр Г больше 2 и выполняется одно из следующих утверждений:
(1) Г является локально псевдо pG2(4,t)-графам Тэйлора;
(2) Г — граф икосаэдра или граф Джонсона 7(8,4);
(3) Г — граф Тервиллигера с массивом пересечений {50,42,1; 1,2,50} или {50,42,9; 1,2, 42};
(4) Г — антиподальное 3-накрытие сильно регулярного графа с параметрами (162,56, 10,24), имеющее массив пересечений {56,45,16,1; 1,8,45,56};
(5) Г имеет массив пересечений {81,60,1; 1,20,81}.
В параграфе 4.2 изучаются сильно регулярные графы с числом вершин, не большим 100, и их автоморфизмы.
Хорошо известно, что имеются 30 наборов параметров неизвестных сильно регулярных графов с числом вершин, не большим 100. Из результатов Бехбахани и Лама [38] следует, что только 11 из них могут отвечать реберно симметричным графам.
Предложение 4.2. Пусть Г — неизвестный реберно симметричный сильно регулярный граф с числом вершин, не большим 100, и G = Aut(r). Тогда выполняется одно из следующих утверждений:
(1) Г имеет параметры (85,30,11,10) и n(G) = {2,3,5,17};
(2) Г имеет параметры (85,54,33,36) и v(G) = {2,3,5,17};
(3) Г имеет параметры (88,27,6,9) и {2,3,11} С tt(G) С {2,3,5,11};
(4) Г имеет параметры (88,60,41,40) и tt(G) = {2,3,5,11};
(5) Г имеет параметры (96,45,24,18) и n(G) = {2,3,5};
(6) Г и.иеет параметры (96,50,22,30) и п(G) = {2,3,5};
(7) Г имеет параметры (96,60,38,36) и 7Г(G) = {2,3,5};
(8) Г имеет параметры (99,42,21,15) и {2,3,7,11} С тг(G) С {2,3,5,7.11};
(9) Г имеет параметры (99,56,28,36) и {2,3,7,11} С jt(G) С {2,3,5,7,11};
(10) Г имеет параметры (100,33,8,12) ип(G) = {2,3,5,11};
(11) Г имеет параметры (100,66,44,42) и n(G) - {2,3,5,11}.
A.A. Махневым в М.С. Нировой предложена программа класификации реберно симметричных сильно регулярных графов с параметрами из заключения предложения 4.2 и вделан первый шаг на пути реализации этой программы.
Теорема 4.4 ([47]). Пусть Г — сильно регулярный граф с параметрами (85,30,11,10), д — элемент простого порядка р из Aut(r) и Д = Fix(j). Тогда выполняется одно из следующих утверждений:
(1) Д — пустой граф и либо р = 5, Qi(ff) £ {25,70}, либо р = 17 u Qi(ff) = 34;
(2) А является ß-кликой, и либо
(г) р = 2 и ß = 3, ai(g) е {4,22,40,58,76} или ß = 5, cti(s) € {14,32,50,68} или /0 = 7, at(g) € {6,24,42,58,76}, либо
(й) р = 3 и ß = 1, cti(g) € {12,39,66} или /3 = 4, a^g) € {0,27,54} или /3 = 7, tti(i) 6 {15,42,69};
(3) р = 5, Д является у-кокликой и 7 = 5, Qi(g) 6 {5,50} или 7 = 10, Qi(g) е {30,75};
(4) р = 3, |Д| = 3t + 1, 2 < t < 7 и (121 - 30 + сц(д))/9 сравнимо с 1 по модулю 3;
(5) р = 2, |Д| = 2s + 1, 2 < s < 13 и 8я - 30 + ai($) делится на 18.
Следствие 4.3. Сильно регулярный граф с параметрами (85,30,11,10) не является вершинно симметричным.
В работах [39-42] доказано несуществование реберно симметричных сильно регулярных графов с параметрами (88,27,6,9), (88,60,41,40), (96,45,24,18), (96,50,22,30), (96,60,38, 36), (99,42,21,15) и (99,56,28,36). Завершает вышеуказанную программу
Теорема 4.5 ([53]). Пусть Г — сильно регулярный граф с параметрами (100,33,8,12), g — элемент простого порядка р из Aut(r) и Д = Fix(fl). Тогда выполняется одно из следующих утверждений:
(1) Д — пустой граф, р = 2 и а^д) = 201. или р = 5 и cti(g) = 0,50,100;
(2) Д является А-кликой, р = 2 и at(g) - 12 делится на 20, или р = 3 и 0:1(5) — 12 делится на 30;
(3) Д является у-кокликой, либо
(г) 7 = 1, р= 3 и и Qi(<?) = 3,33,63,93 или р = 11 и at(g) = 33, либо (И) р = 3, 7 = 4,7,..., 16 и cti(g) — З7 делится на 30;
(4) Д является объединением п > 2 изолированных тгц-хлик, р = 2, m, G {2,4} и |Д| < 20;
(5) Д содержит геодезический 2-путь и либо (i)p = Z, | Д| = 3t + 1, 3 < t < 8, либо
(И) р = 2, \ Д| = 2s, 3 < s < 25.
Следствие 4.4. Сильно регулярные графы с параметрами (100,33,8,12) и (100,66,44, 42) не являются реберно симметричными.
Из этого следствия и результатов [39-42,47] получаем
Следствие 4.5. Сильно регулярные графы с параметрами из заключения предложения 4.2 не являются реберно симметричными.
В.П. Буриченко в A.A. Махнев [21] нашли массивы пересечений дистанционно регулярных графов с А = 2, /I > 1 и числом вершин не большим 1000. Отметим, что в [21] пропущены массивы {9,6,3; 1,2,3} графа Хемминга #(3,4) с v = 64, {12,9,6,3; 1,2,3,4} графа Хемминга #(4,4) с v = 256 и массив {33,30,15; 1,2,15}, зато имеется лишний массив {13,10,7; 1, 2,7} (граф с таким массивом пересечений не существует).
Теорема 5.1 ([56]). Пусть Г — дистанционно регулярный граф с А = 2, р. = 1, имеющий не более 4096 вершин. Тогда Г имеет один из следующих массивов пересечений:
(1) {21,18; 1,1} (v = 400);
(2) {6,3,3,3; 1,1,1,2} (Г — обобщенный восьмиугольник порядка (3,1), г> = 160), {6,3,3; 1,1,2} (Г — обобщенный шестиугольник порядка (3,1), v = 52), {12,9,9; 1,1,4} (Г — обобщенный шестиугольник порядка (3,3), v = 364), {6,3,3,3,3,3; 1,1,1,1,1,2} (Г — обобщенный двенадцатиугольник порядка (3,1), v = 1456);
(3) {18,15,9; 1,1,10} (v = 1 + 18 + 270 + 243 = 532, Г3 - сильно регулярный граф); {33,30,8; 1,1,30}, {39,36,4; 1,1,36}, {21,18,12,4; 1,1,6,21}
(ti = 1 + 21 + 378 + 756 + 144 = 1300, = 0).
Завершает классификацию дистанционно регулярных графов с А = 2 и не более 4096 вершинами
Следствие 5.1 ([56]). Пусть Г — дистанционно регулярный граф диаметра, большего 2, с А = 2, имеющий не более 4096 вершин. Тогда выполняется одно из утверждений:
(1) Г — примитивный граф с массивом пересечений {6,3,3; 1,1,2}, {9,6,3; 1,2,3}, {12,9,9; 1,1,4}, {15,12,6; 1,2,10}, {18,15,9; 1,1,10}, {19,16,8; 1,2,8}, {24,21,3; 1,3,18}, {30,27,24; 1,2,10}, {33,30,8; 1,1,30}, {33,30,15; 1,2,15}, {35,32,8:1,2,28}, {35,32,28; 1,4, 8}, {39,36,4; 1,1,36}, {39,36,20; 1,2,20}, {39,36,22; 1,2,18}, {39,36,27; 1,4,13}, {42,39,24; 1,2,12}, {48,45,9; 1,1,40}, {51,48,8; 1,4,36}, {51,48,24; 1,2,24}, {55,52,34; 1,2,22}, {58,55, 8; 1,2,44}, {60,57,16; 1,4,30}, {60,57,32; 1,4,18}, {63,60,10; 1,2,54}, {63,60,49; 1,4,15}, {68,65,32; 1,4,40}, {75,72,8; 1,2,60}, {75,72,42; 1,4,50}, {75,72,31; 1,8,45}, {80,77,61; 1,7, 20}, {90,87,60; 1,15,18}, {99,96,12; 1,4,88}, {99,96,20; 1,4, 72}, {99,96,6; 1,6,88}, {120,117, 5; 1,5,108}, {143,140,34; 1,7,110}, {147,144,39; 1,12,117}, {224,221,32; 1,16,208};
(2) Г — антиподальный граф с р = 2 и массивом пересечений {2т +1,2г — 2,1; 1,2,2г + 1}, г е {3,4,...,44} - {10,16,28,34,38} uv = 2г(г + 1);
(3) Г — антиподальный граф с р > 3 и массивом пересечений {15,12,1; 1,4,15}, {18,15,1; 1,5,18}, {27,24,1; 1,8,27}, {35,32,1; 1,4,35}, {45,42,1; 1,6,45}, {42,39,1; 1,3,42}, {63,60,1; 1,4,63}, {75,72,1; 1,12,75}, {99,96,1; 1,4,99}, {108,105,1; 1,5,108}, {147,144,1; 1,16,147}, {171,168,1; 1,12,171}, {243,240,1; 1,20,243};
(4) Г — примитивный граф с массивом пересечений {6,3,3,3; 1,1,1,2}, {12,9,6,3; 1,2,3, 4}, {21,18,12,4; 1,1,6,21}, {15,12,9,6,3; 1,2,3,4,5}, {6,3,3,3,3,3; 1,1,1,1,1,2}, {18,15,12, 9,6,3; 1,2,3,4,5,6}.
Отметим, что к списку Буриченко-Махнева добавились только массивы некоторых обобщенных многоугольников, графов Хемминга Н(п,4), двух графов с р = 1, массив {33,30,15; 1,2,15} п массивы графов диаметра 3 с числом вершин, большим 1000.
ЛИТЕРАТУРА
1. Tits J. Buildings of Spherical Type and finite BN-pairs, Springer Lecture Notes in Mathematics, v. 386, 1974.
2. Brouwer A.E., Cohen A.M., Neumaier A. Distance-regular graphs // Berlin etc: SpringerVerlag - 1989.
3. Higman D.G. Finite permutation groups of rank 3 // Math. Z. 1964, v. 86, 145-156.
4. Higman D.G. Primitive rank 3 groups with a prime subdegree /,/ Math. Z. 1966, v. 91, 70-86.
5. Prager C.E., Soicher L.H. Low rank representations and graphs for sporadic groups. Lecture series 8. Cambridge, University press, 1997.
6. Cameron P.J. Permutation Groups. London Math. Soc. Student Texts №45. Cambridge: Cambridge Univ. Press. 1999.
7. Махнев A.A., Нирова M.С. Об однородных расширениях частичных геометрий // Труды Института математики и механики УрО РАН 2007, т. 13, N 1, 148-157.
8. Buekenhout F., Hubaut X. Locally polar spaces and related rank 3 groups // J. Algebra 1977, v. 45, 391-434.
9. Махнев A.A. Локально GQ(3,5)-rpacJ>bi и геометрии с короткими прямыми //Дискр. матем. 1998, т. 10, 72-86.
10. Махнев А. А., Падучих Д. В. Расширения GQ(4,2), вполне регулярный случай // Дискретная математика 2001, т. 13, N 3, 91-109.
11. Махнев A.A., Падучих Д.В., Хамгокова М.М. О вполне регулярных локально GQ(4,4)-графах // Доклады академии наук 2010, т. 434, N 5, 583-586.
12. Махнев A.A., Падучих Д.В., Хамгокова М.М. О вполне регулярных локально GQ(4,6)-графах // Доклады академии наук 2011, т. 439, N 2, 146-149.
13. Махнев A.A., Падучих ДВ. О вполне регулярных локально С<2(4,8)-графах // Доклады академии наук 2012, т. 443, N 1, 583-586.
14. Махнев A.A., Падучих Д.В. Обобщенный четырехугольник GQ(4,16) и его расширения // XI Белорусская математическая конф. Тез. докл. Минск: Институт математики HAH Беларуси, 2012. С. 39-40.
15. Кагазежева A.M. О локально GQ(4,11)-графах // Математический форум (Итоги науки. Юг России), т. 6 Группы и графы, Владикавказ 2012, 28-39.
16. Махнев A.A., Падучих Д.В. О сильно регулярных локально GQ(4,t)-графах // Сибирский матем. журнал 2008, т. 49, N 1, 161-182.
17. Махнев A.A. О сильной регулярности некоторых реберно регулярных графов // Известия РАН, сер. матем. 2004, т. 68, 159-172.
18. Васильев С.А., Махнев A.A. О вполне регулярных графах с i>i = 4 // Известия Гомельского госуниверситета. Гомель 2006, 101-108.
19. Казарина В.И., Махнев A.A. О реберно регулярных графах с bj = 5 // Владикавказский матем. журнал 2009, т. 11, N 1, 29-42.
20. Ефимов К.С. Классификация вполне регулярных графов с b¡ =6, Труды Института математики и механики 2012, т. 18, N 3, 5-7.
21. Буриченко В.П., Махнев A.A. О вполне регулярных локально циклических графах // Современные проблемы математики. Тезисы 42 Всероссийской молодежной конференции. ИММ УрО РАН, Екатеринбург 2011, 11-14.
22. Буриченко В.П., Махнев A.A. Об автоморфизмах сильно регулярных локально циклических графов // Доклады академии наук 2011, т. 441, N 2, 151-155.
23. Буриченко В.П., Махнев A.A. Об автоморфизмах дистанционно регулярного графа с массивом пересечений {15,12,6; 1,2,10} // Доклады академии наук 2012, т. 444, № 3, 305-309
24. Белоусов И.Н. Об автоморфизмах дистанционно регулярного графа с массивом пересечений {19,16,8; 1,2,8} // Доклады академии наук 2012, т. 443, № 3, 305-309
25. Махнев A.A., Падучих Д.В. Об автоморфизмах дистанционно регулярного графа с массивом пересечений {24,21,3; 1,3,18} // Алгебра и логика 2012,
26. Махнев A.A., Циовкина Л.Ю. Об автоморфизмах дистанционно регулярного графа с массивом пересечений {35,32,8; 1,2,28} // Труды Института математики и механики 2012, т. 18, N 1, 235-241.
27. Cameron P., Van Lint J. Designs, Graphs, Codes and their Links, London Math. Soc. Student Texts 22 1981. Cambr. Univ. Press.
28. Nebe G., Venkov B. On tight spherical designs // Алгебра и анализ 2012, т. 24, N 3, 163-171.
29. Махнев A.A. О несуществовании сильно регулярных графов с параметрами (486, 165,36,66) // Украинский матем. журнал 2002, т. 54, N 7, 941-949.
30. Махнев A.A., Токбаева A.A. Об автоморфизмах сильно регулярного графа с параметрами (243,66,9,21) // Владикавказский матем. журнал 2010. Т. 12, N 4, 35-45.
31. Исакова М.М., Махнев A.A. Об автоморфизмах сильно регулярного графа с параг метрами (396,135,30,54) // Владикавказский матем. журнал 2010. Т. 12, N 3, 32-42.
32. Кабанов В.В., Махнев A.A., Падучих Д.В. О сильно регулярных графах с собственным значением 2 и их расширениях // Труды Института математики и механики УрО РАН 2010. Т. 16, N 3. С. 105-116.
33. Гаврилюк А.Л., Махнев A.A. Дистанционно регулярные графы, в которых окрестности вершин изоморфны графу ХофманагСинглтона // Доклады академии наук 2009, т. 428, N 2, 157-160.
34. Гаврилюк А.Л., Махнев A.A., Падучих Д.В. О графах, в которых окрестности вершин изоморфны графу Гевиртца // Труды Института математики и механики УрО РАН 2010, т. 16, N 2, 35-47.
35. Махнев A.A., Падучих Д.В. Вполне регулярные графы, в которых окрестности вершин изоморфны графу ХигменатСимса // Труды Института математики и механики УрО РАН 2011, т. 17, N 4, 189-198.
36. Махнев A.A., Падучих Д.В. Вполне регулярные графы, в которых окрестности вершин изоморфны графу Матье // Труды Института математики и механики УрО РАН 2012 т. 18, N 3, 189-198.
37. Зюляркина Н.Д., Махнев A.A. О расширениях сильно регулярных графов с собственным значением 2 // Доклады академии наук 2012, т. 442, N 1, 7-10.
38. Behbahani М., Lam С. Strongly regular graphs with non-trivial automorphisms // Discrete Math. 2011, v. 311, N 2-3, 132-144.
39. Ефимов К.С., Махнев A.A. Об автоморфизмах сильно регулярного графа с параметрами (88,27,6,9) // Доклады академии наук 2012, т. 445, N 3, 247-250.
40. Журтов А.Х., Махнев A.A., Кагаэежева A.M. Об автоморфизмах сильно регулярного графа с параметрами (96,45,24,18) // Доклады академии наук 2012, т. 445, N 3, 247-250.
41. Белоусов И.Н., Махнев A.A. Об автоморфизмах сильно регулярного графа с параметрами (96,60,38,36) // Доклады академии наук 2013, т. 451, N 3, 247-250.
42. Ефимов К.С., Махнев A.A. Об автоморфизмах сильно регулярных графов с параметрами (99,42,21,15) и (99,56,44,42) // Доклады академии наук 2013, т. 449, N 3, 247-250.
Работы автора по теме диссертации
43. Ефимов К.С., Махнев A.A., Нирова М.С. О вполне регулярных графах с fe = 10, А = 3 // Труды Института математики и механики УрО РАН 2010, т. 16, N 2, 75-90.
44. Журтов А.Х., Махнев A.A., Нирова М.С. Об автоморфизмах 4-изорегулярных графов // Труды Института математики п механики УрО РАН 2010, т. 16, N 3, 93-104.
45. Махнев A.A., Нирова М.С. Об автоморфизмах сильно регулярного графа с параметрами (640,243,66,108) // Доклады академии наук 2011, т. 440, N 6, 743-746.
46. Нирова М.С. Сильно (s— 2)-однородные расширения частичных геометрий pGa(s, t) // Труды Института математики и механики УрО РАН 2011, т. 17, N 4, 244-257.
47. Махнев A.A., Нирова М.С. О небольших симметричных сильно регулярных графах // Доклады академии наук 2012, т. 444, N 1, 23-27.
48. Махнев A.A., Нирова М.С. О графах, в которых окрестности вершин сильно регулярны с собственным значением 2 // Доклады академии наук 2012. т. 444, N 3, 258-261.
49. Нирова М.С. О сильно регулярных графах с b¡ <24 // Труды Института математики и механики УрО РАН 2012, т. 18, N 3, 187-194.
50. Белоусов И.Н., Махнев A.A., Нирова М.С. Дистанционно регулярные графы, в которых окрестности вершин сильно регулярны с собственным значением 2 // Доклады академии наук 2012, т. 447, N 5, 475-478.
51. Махнев A.A., Нирова М.С. Об автоморфизмах дистанционно регулярного графа с массивом пересечений {51,48,8; 1,4,36} // Математический форум (Итоги науки. Юг России). Т. 6 Группы и графы. Владикавказ: ЮМИ ВНЦ РАН и РСО-А 2012, 129-141.
52. Нирова М.С. Об антиподальных дистанционно регулярных графах с ft = 1 // Доклады академии наук 2013, т. 448, N 4, 392-395.
53. Нирова М.С. Реберно симметричные сильно регулярные графы с числом вершин, не большим 100 // Сибирские электронные математические известия 2013, т. 10. 22-30.
54. Нирова М.С. Дистанционно регулярные локально GQ(4,12)-графы // Сибирские электронные математические известия 2012, т. 9, 653-659.
55. Махнев A.A., Нирова М.С. Об автоморфизмах дистанционно регулярного графа с массивом пересечений {51,48,8; 1,4,36} // Доклады академии наук 2013, т. 449, N 3, 258-261.
56. Makhnev A.A., Nirova M.S. On distance-regular graphs with A = 2 // Jornal of Siberian Federal Univ. 2014, т. 7, N 2, 188-194.
57. Ефимов К.С., Махнев A.A., Нирова М.С. О вполне регулярных графах с fe = 10, А = 3 // Алгебра и ее приложения. Труды межд. конф., посвященной 80-летию со дня рождения А.И. Кос-трикина, Нальчик 2009, 44-48.
58. Журтов А.Х., Махнев A.A., Нирова М.С. Об автоморфизмах 4-изорегулярных графов // Теория групп и ее приложения. Труды VIII Международной школы-конференции по теории групп. Нальчик 2010, 100-107.
59. Белоусов И.Н., Махнев A.A., Нирова М.С. О расширениях сильно регулярных графов с собственным значением 2 // Алгебра и линейная оптимизация. Тез. докл. Международной конф. Екатеринбург 2012, 25-27.
60. Махнев A.A., Нирова М.С. О небольших симметричных сильно регулярных графах // Алгебра и линейная оптимизация. Тез. докл. Международной конф. Екатеринбург 2012, 124-125.
61. Нирова М.С. Об антиподальных дистанционно регулярных графах с ц = 1 // Теория групп и ее приложения. Тез. докл. Международной школы-конференции. Владикавказ 2012, 94-96.
62. Нирова М.С. О локально GQ(4,12)-графах // Современные проблемы математики. Тез. докл. 44 Международной молодежной школы-конференции. Екатеринбург 2013, 8587.
63. Нирова М.С. О реберно симметричных сильно регулярных графах с числом вершин, не большим 100 // Алгебра и комбинаторика. Тез. докл. межд. конф., посвященной 60-летию A.A. Махнева, Екатеринбург 2013, 120-122.
64. Махнев A.A., Нирова М.С. О дистанционно регулярных графах с Л = 2 // Теория групп и ее приложения. Труды Международной школы-конф. по теории групп, Нальчик 2014, 41-42.
15--2511
2014270370
2014270370
