Содержание к диссертации
Введение
1 О локально GQ(s,t) графах с сильно регулярными подграфами 15
1.1 Предварительные результаты 15
1.2 Случай графов Мура 17
1.3 Случай графов Клебша и Гевиртца 20
1.4 А - граф с ц > 2 24
2 О реберно регулярных графах с t>i = 5 26
2.1 Предварительные результаты 26
2.2 Реберно регулярные графы больших степеней с bi = 5 29
2.3 Графы с bi = 5 степени 14 41
3 Об автоморфизмах графа с (364,33,2,3) 48
3.1 Предварительные результаты 48
3.2 Характеры групп и автоморфизмы графов 49
3.3 Ишюлютивпыс автоморфизмы графа с параметрами (364,33,2,3) 56
3.4 Автоморфизмы частичного четырехугольника PQ(3,10,3) . 63
4 Об автоморфизмах графа с (676,45,2,3) 72
4.1 Предварительные результаты 72
4.2 Характеры групп и автоморфизмы графов 74
4.3 Ишюлютивпыс автоморфизмы графа с параметрами (676,45,2,3) 82
4.4 Автоморфизмы частичного четырехугольника PQ(3,14,3) 88
Список литературы
- Случай графов Мура
- Реберно регулярные графы больших степеней с bi = 5
- Характеры групп и автоморфизмы графов
- Ишюлютивпыс автоморфизмы графа с параметрами (676,45,2,3)
Введение к работе
В связи с завершением классификации конечных простых групп возникла задача единого представления конечных простых групп. Перспективным направлением является поиск такого класса конечных геометрий, что каждая конечная простая группа действует флаг-транзитивио на некоторой геометрии и все геометрии этого класса допускают классификацию ([11]-[15], [32], [34]). Например, класс билдингов Титса характеризует группы лиева типа [37]. Позднее в этом направлении возникли задачи, не связанные с групповым действием, в частности, такой является задача классификации дистанционно регулярных графов [11].
Пусть G — транзитивная группа подстановок на множестве Q. Если стабилизатор Gp точки /; Є О, имеет г орбит на Q, то говорят, что G имеет подстановочный ранг г (является группой подстановок ранга г). Пусть г = 3 и соответствующие три орбиты — это {р}, А(р), Г(р). Тогда но группе G удается построить сильно регулярный граф Г, множество вершин которого — Q и две вершины р, q смежны в Г, если q Є Г(р) [22].
Д. Хигмаи ([22]-[28]) развил теорию групп ранга 3. Эти группы являются группами автоморфизмов сильно регулярных графов, причем они действуют транзитивно как на множествах вершин и ребер, так и на множестве пар различных несмежных вершин. Такие графы являются дистанционно транзитивными графами диаметра 2.
В настоящее время при исследовании графов вовлекаются симметрии все более общего вида. Сначала это были условия дистанционной транзитивности и дистанционной регулярности графов, а затем и более общие условия комбинаторной симметричности. Оказалось, что в некоторых случаях комбинаторная симметрия графа влечет его дистанционную транзитивность.
Первые результаты о комбинаторно симметричных графах были получены в пятидесятых годах. Пусть L(Kn) — реберный граф полного графа Кп на п вершинах или в других обозначениях треугольный граф Т(п). Этот граф является сильно регулярным графом с параметрами (Q),2(n — 2),п — 2,4). В работах 1959-60 годов Л. Чанг [19] и А. Хоффман ([29], [30]) независимо показали, что треугольный граф Т{п) определяется однозначно своими параметрами для всех п, за исключением п = 8. Для случая п — 8 было показано, что кроме треугольного графа Т(8), такие же параметры имеют только три графа, которые были найдены Л. Чаигом в 1949 году [18].
Реберный граф L{Km n) полного многодельного графа Кт п является ко-реберио регулярным графом с параметрами (тп,т + п — 2,2). Граф Кт,п называют га X п решеткой. При га = п решетчатый граф является сильно регулярным графом с параметрами (п2,2п — 2,п — 2,2). С. Шрикхаиде в [ЗС] показал, что граф, имеющий параметры пхп решетки является либо решеткой, либо графом Шрикхаиде (n = 4).
Результаты Л. Чанга, С. Шрикхаиде и А. Хоффмана [31] были объединены Дж. Зейделем [35], который определил все сильно регулярные графы с наименьшим собственным значением —2. Дж. Зейдель показал, что кроме треугольных графов Т(п) и решетчатых п х n-графов, сильно регулярными графами, которые имеют наименьшее собственное значение —2, являются только графы КпХ2, графы Петерссна, Шрикхаиде, Клебша, Шлефли и три графа Чанга.
В работе рассматриваются неориентированные графы без петель и кратных ребер. Если а, Ъ - вершины графа Г, то через d(a, b) обозначается расстояние меж/гу а и Ь, а через Г;(а) - подграф графа Г, индуцированный множеством вершин, которые находятся на расстоянии г в Г от вершины а.
Подграф Гі(а) называется окрестностью вершины а и обозначается через [а]. Через а1 обозначается подграф, являющийся шаром радиуса 1 с центром а.
Граф Г называется регулярным графом степени к, если [а] содержит точно к вершин для любой вершины а из Г.
Граф Г называется реберно регулярным графом с параметрами (v,k,X), если Г содержит v вершин, является регулярным степени к, и каждое ребро из Г лежит в Л треугольниках. Положим Ь\ = к — Л — 1.
Граф Г называется вполне регулярным графом с параметрами (v, к, А, //), если Г реберно регулярен с соответствующими параметрами и подграф [а]П[6] содержит /х вершин в случае d(a, b) = 2. Вполне регулярный граф диаметра 2 называется сильно регулярным граф ом.
Сильно регулярный граф с параметрами (4/л + 1,2//,/х — 1,//) называется графом в половинном случае.
Графом Поли называется грае}), вершинами которого являются элементы конечного ноля Fq, где q сравнимо с 1 по модулю 4, и две вершины смежны, если разность соответствующих элементов ноля Fq является ненулевым квадратом.
Граф Г называется сильным с параметрами (Л,//), если каждое ребро из Г лежит точно в Л треугольниках и подграф [а] П [Ь] содержит /І вершин в случае d(a, b) = 2.
Число вершин в [а] П [6] обозначим через Л(а, 6), если d(a,b) = 1, а соответствующий подграф назовем Х-подграфом.
Если d(a,b) — 2, то число вершин в [а] П [6] обозначим через fi(a,b), а соответствующий подграф назовем ц-подграфом.
Пусть Т — некоторый класс графов. Граф Г назовем локально Т графом, если [а] лежит в Т для любой вершины а графа Г. Если при этом класс Т состоит из графов, изоморфных некоторому графу А, то граф Г назовем локально А графом.
Точечным графом системы инцидентности, состоящей из точек и прямых, называется граф, вершинами которого являются точки этой системы и две вершины смежны, если соответствующие точки лежат на одной прямой.
Частичным четырехугольником PQ(s, t, /х) называется система инцидентности, состоящая из точек и прямых, в которой каждая прямая содержит s + 1 точку, каждая точка лежит на t + 1 прямой (две прямые пересекаются не более, чем по одной точке), для любых двух несмежных вершин точечного графа пересечение их окрестностей содержит точно /і вершин и для любой точки а, не лежащей на прямой L, найдется не более одной прямой, проходящей через а и пересекающей L.
Множество вершин графа MZ(n), отвечающего аффинной плоскости 7Г = (X, С) порядка п, совпадает с объединением множества точек X и множества прямых С, причем подграф X является кокликой, две прямые смежны, если они параллельны, и точка смежна с прямой, только если она принадлежит этой прямой. Граф MZ(n) имеет п(2п + 1) вершин, является кореберно регулярным с fi = 1, А(а, Ь) — О, если одна из вершин а,Ь — точка, а другая — содержащая эту точку прямая, А(а, Ь) = п — 2, если о и Ъ — параллельные прямые.
Цель диссертации. Целью дайной работы является решение следующих задач:
1) Исследовать вполне регулярные локально GQ(s,t) графы с сильно регулярными //-подграфами.
2) Изучить связные реберно регулярные графы с параметрами (v, к, А) и h = 5.
3) Рассмотреть возможные автоморфизмы сильно регулярных графов с малыми параметрами А и /І.
Методы исследования. Основными методами исследования являются методы теории конечных групп, теоретико-графовые методы и методы локального анализа комбинаторно симметричных графов.
Научная новизна. Основные результаты, полученные в работе, являют ся новыми. Выделим из них следущие.
1. Исследованы вполне регулярные локально GQ(s,t) графы, в которых каждый /1-иодграф изоморфен известному сильно регулярному графу А.
2. Классифицированы связные реберно регулярные графов с b\ = 5 с одним из дополнительных условий: граф сильно регулярен или к 14.
3. Найдены возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярных графов с параметрами (364,33,2,3) и (676,45,2,3)
Теоретическая и практическая ценность. Работа носит теоретический характер. Результаты позволяют продолжить изучение комбинаторно симметричных графов и их автоморфизмов. Результаты и методы диссертации могут быть использованы для изучения алгебраических структур подобного типа.
Апробация работы. Основные результаты работы докладывались на:
Между народной конференции, посвященной 75-летию со дня рождения проф. А.И. Кокорина (Иркутск, 2004 г.);
VI Международной конференции, посвященной 100-летию Н.Г. Чудакова (Саратов, 2004 г.);
Международной алгебраической конференции, посвященной 100-летию со дня рождения П.Г. Канторовича и 70-летию Л.Н. Шеврина (Екатеринбург, 2005 г.);
36-й и 37-й Региональных молодежных конференциях ИММ УрО РАН (Екатеринбург, 2005-2006 гг.);
Результаты работы доклады вал и с ь и обсуждались на алгебраическом семинаре ИММ УрО РАН.
Публикации. Основные результаты диссертации опубликованы в работах [38-[45]. Работы [38]-[43] выполнены в нераздельном соавторстве с А.А. Мах-невым.
Структура и объем работы. Работа состоит из введения, четырех глав и списка цитированной литературы, содержащего 45 наименований.
Результаты диссертации.
Во введении обсуждается история вопроса, даются определения и формулируются основные результаты работы. В главе I рассматриваются связные локально GQ(s, і) графы, в которых /i-подграфы являются известными сильно регулярными графами.
Если регулярный грае}) степени к диаметра d имеет v вершин, то выполняется неравенство: v 1+к+к(к—1)+.. .+к(к—1)е1 1. Графы, для которых это нестрогое неравенство превращается в равенство, называются графами Мура. Простейший пример графа Мура представляет (2d + 1)-угольник. Р. Даме-релл [20] доказал, что граф Мура степени к 3 имеет диаметр 2. В этом случае v = к2 + 1, граф сильно регулярен с А = 0 и /І = 1, а степень к равна 3 (граф Петерсена), 7 (граф Хоффмана-Синглтона) или 57. Существование графа Мура степени к — 57 неизвестно.
Граф Клебша определен на множестве векторов 4-мерного линейного пространства V над полем из двух элементов, причем два вектора смежны, если расстояние Хеммиига между ними равно 1 или 4. Это единственный сильно регулярный граф с параметрами (16,5,0,2). Графы Гевиртца, Хигмаиа-Симса и Маклафлина — это графы ранга 3 групп з(4), Хигмана-Симса и Маклафлииа па 5G, 100 и 275 вершинах соответственно.
Пусті» Л — класс графов, элементами которого являются Кщп, графы Мура, графы с параметрами (100,22,0,6), (77,16,0,4), (16,5,0,2), (56,10,0,2). Известные в настоящее время сильно регулярные графы с Л = 0 принадлежат Л.
Заметим, что вполне регулярные локально GQ(4,2) графы классифицированы в [8. В работе [1] описаны связные локально GQ(3,t) графы.
Следующий результат является основным в главе I.
Теорема 1 Пусть Г — (толпе регулярный локально GQ(s,t) граф, в кото ролі каоїсдий fi-подграф изоморфен известному сильно регулярному графу А Є Л. Тогда выполняется одно из следующих утвероісдеиий:
(1) A = Kt+i,t+i nt + 1 делит s2(s2 — 1);
(2) А — граф Петерсеиа и Г — единственный локально GQ(2, 2) граф с параметрами (28,15,6,10);
(3) А — граф Хофмаиа-Синглтона, t = 6 и s = 9,14,15, 24,29 или 30;
(4) А — граф Клебша, 1 = 4 и s = 2,4,6,8,11,12 или 16;
(5) А — граф Гевиртца, t = 9 и s = 3, 7,27,31 і/ш 63;
(6) А — граф) с паралістраліи (77,16,0,4), t = 15 и s = 21,41,55, 153 или 195;
(7) А — граф Хигмаиа-Симса, t = 21 us = 19,24,34,35,39,45,49, 69,84,89,99,105,115,119,144,159,175,189,199,210,214,259,294,309, 339,364,375,399,419 или 420.
Следствие 1 Пусть Г — сильно регулярный локально GQ(s, t) граф), в котором каоїсдий ц-подграф изоморфен известному сильно регулярному графу А. Тогда выполняется одно из следующих утвероіедепий:
(1) А = Kt+ij+i и либо s = 1 и Г = /Сзх( +1) либо s = 4,t = 1 гі Г — частное графа Доісонсона J(10,5), либо s = t = 1,2,3,8 или 13;
(2) А — граф Петерсеиа и Г является единственным локально GQ(2,2) графом с параметрами (28,15, 6,10);
(3) А — граф Гевиртца и Г — граф Маклафлииа.
Известно существование и единственность сильно регулярных локально GQ(t,t) графов с fi-подграфалш, изоморфными Kt+ij+i для t = 1 (Г — частное графа Доісоиеона 1(10,5)), t = 2 (Г — единственный локально GQ(2,2) граф с параметрами (28,15,6,10)) и t = 3 (Г- — граф ранга 3 для группы ІІ4(2) с параметрами (176,40,12,8)). Во второй главе работы рассматривается реберно регулярный граф с параметрами (v, к, А). В монографии А. Броувсра, А. Коэна и А. Ноймайера [11] доказано, что связный реберно регулярный граф с b\ = 1 является многоугольником или полным многодольным с долями порядка 2. А.А. Махне-вым в [6] получено описание реберно регулярных графов с 6і 3, а также Ь\ = 4, к 10. В данной главе классифицированы связные реберно регулярные графы с &і = 5 с одним из дополнительных условий: граф сильно регулярен или к 14.
Через Ф обозначим граф, множество вершин которого разбивается тремя //-замкнутыми К\Х2 подграфами Фі, Фг и Фз, у которого смежные вершины с, d из Фз смежны с вершинами а\,..., а\ из Фі и с вершинами 6і,..., 64 из Ф2, а смежные вершины е, / из Фз — {с, d, с , d } смежны с вершинами а\, а,2, а%, а\ и с вершинами 61,62,63,64, ГДС для х Є Фг- вершина х является антииодом х в Ф можно считать, что а\ смежна с 61,63,62,64, аг смежна с 62,64,6 ,63, аз смежна с 6і, &2,63,64, а\ смежна с 6, 62,63,64.
Если О, — граф диаметра, большего 2, то 0,2 граф па множестве вершин графа О, в котором две вершины смежны тогда и только тогда, когда они находятся на расстоянии 2 в О.
Основным результатом второй главы является
Теорема 2 Пусть Г — связный реберно регулярный граф с параметрами (у, к, А) и b\ = 5. Тогда выполняются следующие утвероісдения:
(1) если Г сильно регулярен, то он является одним из следующих графов: полный миогодольиый граф) Кгхв(г 2), 6 X б решетка, граф Шлефыи, треугольный граф Т(8) или один из трех графов Чанга;
(2) если к 14, то либо Г сильно регулярен, либо верно одно из утвер-оісдений:
(і) граф) Г изоморфен граф)у Ф;
(гі) Г является граф)ом 0,2, где О — граф Клейна (единственный ди стаициоиио регулярный локально семиугольный граф диаметра 3 па 24 вершинах, являющийся 3-пакрытисм 8-клики).
В третьей главе работы выясняются возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярных графов с (Л, /І) = (2,3). Если Г — граф в половинном случае, то он имеет параметры (13,6,2,3) и Г является графом Пэли. Используя равенство (Л — /І)2 + A(k — fi) = п2 при Л = 2, получим п2 = Ак + /І2 — 8/х + 4. Если /І четно, то /i = 2t и п2 = А(к + t2 — At + 1). Если же // нечетно, то fi2 и п2 сравнимы с 1 по модулю 8, поэтому к нечетно. В случае \i = 3 имеем, что п2 = 4Л; — 11, поэтому п = 2и + 1, А; = и2 -\- и + 3 и неглавные собственные значения графа Г равны и и — (и + 1). Кратность собственного значения и равна / = ик(к + и + 1)/(пц) — и(и2 + и + 3)(w2 + 2и + 4)/(6u + 3), следовательно, 2и + 1 делит 11 • 13 и и = 5,6 или 71. Соответственно, & = 33,45 или 5187. Случай к = 33 рассмотрен в третьей главе, /г = 45 — в четвертой. Хорошо известно (предложение 1.1.2 из [11]), что сильный граф с ц 2 регулярен. Поэтому связные компоненты непустых подграфов неподвижных точек автоморфизмов нечетного порядка сильно регулярного графа с тах{Л,//} 2 либо являются кликами, либо сильно регулярны с этими же параметрами. Автоморфизмы графов Мура, т.е. сильно регулярных графов с параметрами (v, к, 0,1), изучались в [9]. Автоморфизмы сильно регулярных графов с /л = 2 и Л Є {0,1} рассматривались в [7], [5]. В первом параграфе третьей главы приведены вспомогательные леммы,, во втором — изложен метод Г.Хигмана работы с автоморфизмами сильно регулярных графов [14].
Через F ix(g) обозначим подграф индуцированный на множестве вершин графа Г, неподвижных относительно автоморфизма д.
В третьем параграфе теоретико-графовыми методами выясняются возможные порядки и строение подграфов неподвижных точек автоморфизмов графа с параметрами (364,33,2,3). Затем, с помощью теории характеров коночных групп полученные результаты существенно уточняются. Автоморфизмы этого графа изучались в [43].
Основными результатами третьей главы являются следующие теорема и следствие.
Теорема 3 Пусть Г — сильно регулярный граф с параметрами
(364,33,2,3), д — элемент простого порядкар из Aut(r) uQ = Fix(g). Тогда
выполняется одно из следующих утверждений:
(1) р = 7 или 13 и Q — пустой граф;
(2) р = 11 и Q является 1-кликой или р = Ъ uQ, является 4-кликой;
(3) р = 3 и либо Q является графом Поли с параметрами (13,6,2,3), либо Q является объединением ip изолированных вершин и ф 3 изолированных А-клик, число (р -\-ф сравнимо с 1 по модулю 3 и не превосходит 22;
(4) р = 2 и либо Q(a) П 0(6) = 3 для некоторых несмеоюных вершин a, b Є О, ./шбо Г2 является одним из графов:
(г) 2-клика, (ії) граф) Петерсеиа,
{Иг) Q С aL для некоторой вершины a, Q{a) является объединением /3 изолированных вершин и 7 треугольников, где {3 + 7 четно.
Из теоремы 3 следует, что для группы G автоморфизмов графа Г множество 7r{G) всех простых делителей G содержится в {2,3,5,7,11,13}.
Следствие 2 Пусть Г — точечный граф) частичного четырехугольника PQ(3,10,3), g — элемент простого порядка р из Aut(r) и Q = Fix{g). Тогда выполняется одно из следующих утвероісдсний:
(1) р = 7 или 13 и О, — пустой граф;
(2) р = 11 и Q является 1-кликой или р = 5 и Q является 4-кликой;
(3) р = 3 и Q является объединением ср изолированных вершин и ф изолированных 4-клик, причем {(р, ф) = (1,3), (2,2), (0,1), (3,1), (6,1), (10,0) или (7,0);
(4) p = 2 и либо \Q(a)r\Q(b)\ = 3 для некоторых иесмеоісиьіх вершин а,Ь Є Q, либо Q С aL, для некоторой вершины a, Q{a) является объединением /5 изолированных вершин и 7 треугольников, где (j3,j) = (0,11),(3,6),(0,3) или (11,0).
В четвертой главе с помощью теории характеров конечных групп выяснены возможные порядки и строение подграфов неподвижных точек автоморфизмов графа Г с параметрами (676,45,2,3). Автоморфизмы этого графа изучались в [44].
Основными результатами четвертой главы являются следующие теорема и следствие.
Теорема 4 Пусть Г — сильно регулярный граф с параметрами (676,45,2,3), g — элемент простого порядка р из Aut(r) и A = Fix{g). Тогда выполняется одно из следующих утвероіедсиий:
(1) А — пустой граф, р — 2 или 13, в случае р = 2 граф V, вершинами которого являются g-допустимые 4-клики из Г, причем вершины X, Y смеоюпы в V, если некоторая вершина из X смеоіспа с вершиной из Y, является сильно регулярным с параметрами (169,42,5,12);
(2) А является либо 1-кликой и р = 5, либо 4-кликой и р = 7;
(3) р = 13 и А — граф Поли с параметрами (13,6,2,3);
(4) р = 3, А является объединением а. изолированных вершин, /3 изолированных 4-клик и 7 графов Пэли с параметрами (13,6,2,3), число А сравнимо с 1 по модулю 3 и верно одно из утвероіедений:
(і) 7 = a = 2,/3 = 0,
(іг) 7 — 1? а + 4(3 делится на 3 и не превосходит 18,
{гіг) 7 = 0, а + 4/3 делится на 3 и не превосходит 21;
(5) р = 2 и А(а) П А(Ь) = 3 для некоторых иссмеоіспьіх вершин а, Ъ Є А, либо А является одним из граф)ов: (г) граф Петерсена,
(г г) ДСа1 для некоторой вершины а, А (а) содероісит (р изолированных вершин и ф треугольников,
{Иг) А является графом MZ{4).
Из теоремы 4 следует, что для группы G автоморфизмов графа Г множество 7r{G) содержится в {2,3,5, 7,13}.
Следствие 3 Пусть Г — точечный граф) частичного четырехугольника PQ{3,14,3), g — элемент простого порядка р из Aut(r) и 2 = Fix{g). Тогда выполняется одно из следующих утвероіедеиий:
(1) р = 2 и либо
(г) А — пустой граф, либо
(г г) А(а) П А(6) = 3 для некоторых несмеоісньїх вершин a, b Є А, либо (ш) А С а1 для некоторой вершины а, А (а) является объединением ср изолированных вершин и ф треугольников, {(р,ф) = (4,3) или (13,0);
(2) р = 3, А является объединением а изолированных вершин и (3 изолированных 4-клик, где а + 4/? 19 и в случае равенства имеем fi = 0;
(3) р — 5 и А является 1-кликой;
(4) р = 7 и А является 4-кликой;
(5) р = 13 и А — пустой граф.
Случай графов Мура
Пусть до конца главы Г является вполне регулярным локально GQ(s, t) графом, в котором каждый //-подграф изоморфен известному сильно регулярному графу А. Тогда к = (s + l)(st + 1), A = s(t + 1). Пусть А = [а] П [Ь]. Заметим, что каждая прямая L обобщенного четырехугольника [а] пересекает А по 0 или 2 точкам. Действительно, если с Є ЬГ)А, то М = (L\j{a}) — {с} является прямой из [с] и по определению обобщенного четырехугольника [о] содержит единственную точку d из М. Таким образом, {с, d} = L П А.
В этом параграфе будут рассмотрены случаи, когда А — полный двудольный граф или граф Мура. Лемма 6 Если A = Kt+i,t+i, то t-\-l делит s2(s2 — 1). Доказательство. Из прямоугольного соотношения к (к — А — 1) = fo/z, где / = Гг(сі) для любой вершины а, заключаем, что 2{t + 1) делит (s + l){st + l)sH. Так как t + 1 взаимно просто с t, (t + 1, st + 1) = (t + 1, s — 1), то t + 1 делит s2(s2 — 1). Лемма доказана. Лемма 7 Если A = iff+i, +i и Г сильно регулярен, то либо 5=1, либо 5 = 4, = 1, л?/б"о s = t = 2,3,8 или 13. Доказательство. По теореме 3.1 из [21]выиолняется заключение леммы или 5 = t = 4. Но в последнем случае по [33] таких графов нет.
Следует заметить, что локально GQ(l,t) граф совпадает с Кзх( +1)- Пусть s 1. Для небольших значений і известна дополнительная информация. Если t = 1, то окрестности вершин в Г являются (5 + 1) х (s + 1) решетками и по [10] Г является графом Джонсона или его частным. Если t = 2, то s = 2 или 4. В случае 5 = 2 грае]) Г является единственным локально GQ(2, 2) графом с параметрами (3G,15,G,G). Если же s = 4, то но [8] Г является единственным дистанционно регулярным локально (2ф(4,2)-графом на 378 вершинах с массивом пересечений (45,32,12,1; 1,6,32,45). Если t — 3, то s = 3, 5 или 9. Если 5 = 3, то по [1] Г — единственный локально GQ(3,3) граф с параметрами (176,40,12,8). Если t = 4, то 5 делит s2(s2 — 1), поэтому s = 4,6,11 или 16. В случае s = 4 граф Г является сильно регулярным и по теореме из [33] не существует.
Пусть А является графом Мура. Если А — пятиугольник, то t = 1 и Г является локально (s + 1) X (s + 1) решеткой. Противоречие с тем, что тогда связные компоненты //-подграфов являются циклами четной длины.
Лемма 8 Если А — граф Петсрсепа, то Г является едипствсппым сильно регулярным локально GQ{2,2) графом с параметрами (28,15,6,8).
Доказательство. Если А — граф Петсрсепа, то t = 2 и s = 1,2 или 4. Но в случае s = 1 получим /І = 6, противоречие. Если s = 2, то выполняется заключение леммы (см., например [17]).
Пусть s = 4. Тогда но [8] вполне регулярный локально GQ(A, 2) граф имеет ц, равное 6 или 18. Лемма доказана.
Пусті) до конца параграфа А — граф Хофмаиа-Сииглтона. Тогда t = 6. По условию целочисленное s+б делит 42s(s + l) и s = 3,4,6,8,9,12,14,15, 22,24,29,30 или 36. Так как ц = 50 делит 6s2(s+l)(6s+l), то s = 4,9,14,15,24,29 или 30.
Лемма 9 Пусть а,Ь — вершины из Г с d(a, b) = 2, и А = [а] П [Ь] — граф Хофмаиа-Сииглтоиа. Тогда для Х{ = ЛГг(А) П [6] выполняются следующие угпвсроісдеиия: (1) xi = 0 для нечетных і и для г 8; (2) ЕХІ = (s + l)(6s+ 1)-50, Zixi = 50(7s-7). Доказательство. Если першина с из [Ь] — [а] смежна с вершиной из А, то [с]ПА состоит из изолированных ребер. Заметим, что для ребра {«, w} графа А подграф А — ([и] U [w]) состоит из трех изолированных ребер. Поэтому Х{ = 0 для нечетных і и для і 8. Утверждение (1) доказано. Далее, [Ь] — А содержит (s + l)(6s + 1)-50 вершин и каждая вершина из А смежна с 7s — 7 вершинами из Г — А. Отсюда следует утверждение (2). Лемма 10 Параметр s не равен 4. Доказательство. Если 5 = 4, то fi = 2(st + 1) = 50 и ввиду леммы 1.1.2 граф Г сильно регулярен с параметрами (366,125,28,50). Далее, п2 = (Л — ц)2 + 4(к — ц) = 282 и неглавные собственные значения графа равны п — т = 3, — т = —25. По условию целочисленпости nfi = 28-50 делит (т — 1)к(к + т) = 24 125 150, противоречие.
Реберно регулярные графы больших степеней с bi = 5
Лемма 23 Пусть Г — сильно регулярный граф, имеющий целочисленные собственные значения, uh\ = к — А — 1. Тогда (1) если Ъ\ — простое число, то Г является полным миогодольным гра-ф)ом KrxQ,l+i) или Зейделевым графом; (2) если Ь\ = 2р, р — простое число, то Г либо является полным многодельным графом, либо имеет собственное значение —2 или —3, либо является дополнительным к Зейдслеву граф)у; (3) если Ь\ = 4, то Г является полным многодельным графом Кгх , 5x5 решеткой, треугольным графюм Т(7) или дополнительным граф)ом к 4 X 4 решетке, треугольному графу Т(б) или граф у Клебша (Следует заметить, что в половинном случае параметры графа равны (17,8,3,4) и он является графом Пэли).
Доказательство. См. лемму 7 из [3]. Лемма 24 Пусть Г — связный реберно регулярный граф с параметрами (v, к, Л). Если А к + 1/2 — \/2к + 2 (равносильно к {Ъ\ + 3&i)/2 + 1), то Г - дополнительный граф) для сильно регулярного графа Д и либо /І(А) 1, либо Л(А) = 0« и(А) = 2. Доказательство. Это уточнение теоремы 1.4.3 из [11], следующее из ее доказательства. Лемма 25 Пусть Г — реберно регулярный граф диаметра 2 с параметрами (v,к,А). Тогда для p, = v-2k + \ = (v-k — 1) — Ь\ и X = min{t — {и1 U wL\ d(u,w) = 2} выполняется неравенство kji (Ьі + Д)(Ьі + Д-1-А).
Доказательство. По условию граф Г является кореберно регулярным с вышеуказанным р.. По предложению 1.4.1 [11], примененному к Г, имеем v — k—1 к(к — 1 — Х)//і. Так как к = &І + /І, то кц (&І + /І)(&І + /І —1 —А).
Лемма 26 Пусть Г — сильно регулярный граф с параметрами (г , /г, А,/І), Л — индуцированный подграф с N вершинами, М ребрами и степенями вершин di,..., с?АГ м г число вершин из Г —А, смеэ/сиых точно с г вершинами из А. Тогда (1) (V-N)- (kN - Ш) + ХМ + /І(() - М) - Е ( = о + Е f ; и (2) если х\,...,хт — естественные числа, то (Ег #г)2 ЕЯгЕг2#ь гари-ч(сл« равенство достигается, только если х\ = 0 для любого і, отличного от г0 = Zixi/Yxi.
Доказательство. Подсчитав число вершин в Г —А, число ребер между А и Г —А и число 2-путей с концами в А и средней вершиной в Г —А, получим равенства v - N = Еж,-, kN - 2М = Ег я; и ХМ + /І(( ) - М) - E-Ii ( = Е ( J2 Вычитая второе равенство из суммы первого и третьего, получим утверждение (1). Так как квадратный трехчлен Е(г — Х)2ХІ = Т,І2ХІ — 2хТ,іхі + х2Т,Х( неотрицателен, то его дискриминант (Ег з;г-)2 — E#;Ez2 i неположителен. В случае равенства (jZixi)2 = Е#І Ег2жг квадратный трехчлен Е(г—Х)2ХІ имеет единственный корень х = Ег г/Е г (кратности 2), поэтому Х( = О для г ф Е ІХІ/ Е хі. Лемма доказана.
В этом параграфе предполагется, что Г — реберно регулярный граф с b\ = 5. Следует заметить, что А = к — 6, поэтому к четно. Если к не делится на 3, то v делится на 3. Лемма 27 Если Г — сильно регулярный граф с b\ = 5, то Г является одним из следующих графов: (1) полный многодельный граф КГХ6, (2) 6 х 6 решетка; (3) треугольный граф) Т(8) или один из трех графов Чанга; (4) граф) Шлефли с параметрами (27,16,10,8). Доказательство. Ввиду леммы 23, Г — граф в половинном случае, полный многодольный граф Кгхо или граф Зейделя. Если параметры графа равны (4// + 1,2//,// — 1,//), то // = 5 и v = 21 не является суммой двух квадратов целых чисел. Поэтому половинный случай невозможен.
Пусть Г — граф Зейделя. Если Г = КГХ2, то Ь\ = 1. Если Г имеет параметры п х п решетки (п2,2п — 2, п — 2,2), то Ь\ = п — 1 и п = 6. Если Г имеет параметры треугольного графа Т(п), то Ь\ = п — 3 и п = 8. Поэтому Г является треугольным графом Т(8) или одним из трех графов Чанга. Граф Петерсеиа имеет Ь\ = 2. Граф Клебша с параметрами (16,10,6,6) имеет &1 = 3. Наконец, граф Шлефли имеет параметры (27,16,10,8) и Ь\ = 5. Лемма 28 Если к 22, то Г — сильно регулярный граф. Доказательство. Если к 22, то по лемме 24 граф Г сильно регулярен. Лемма доказана. До конца параграфа будем предполагать, что Г не является сильно регулярным графом. Напомним, что если к ЗЬі — 2, то по следствию из [6] либо Ь\ 3, либо диаметр графа не больше 2.
Характеры групп и автоморфизмы графов
Доказательство теоремы опирается на метод Хигмеиа работы с автоморфизмами сильно регулярного графа, представленный в третьей главе монографии Камерона [1G]. При этом граф Г рассматривается как симметричная схема отношений (X, ТІ) с двумя классами, где X — множество вершин графа, RQ — отношение равенства, R\ — отношение смежности в Г, . — отношение смежности в дополнительном графе Г. Если Р и Q — первая и вторая матрицы собственных значений схемы, то /1 1 1 N к г s v — к — 1 —г — 1 — s — 1 PQ = QP = г;/. Здесь v — число вершин, k,r,s — собственные значения графа Г кратностей 1,/, # соответственно (указанные кратности образуют первый столбец матрицы Q).
Подстановочное представление группы G = Aut(T) на вершинах графа Г обычным образом дает матричное представление ф группы G в GL(v,C). Пространство Си является ортогональной прямой суммой собственных G-инвариантных подпространств Wo ф W\ ф W2 матрицы смежности графа Г. Пусть Xi характер представления ф\уг Тогда для любого д Є G получим ХМ = у 1 Qn xj(g), где ctj(g) — число точек х из X таких, что (х,х9) Є Rj. Заметим, что значения характеров являются целыми алгебраическими числами, правая часть равенства для Xi{o) число рациональное, поэтому Хі(з) должно быть целым.
До конца работы будем предполагать, что Г — сильно регулярный граф с параметрами (364,33,2,3) и G = Aut(r). Тогда Г имеет собственные значения 33, 5, -С кратностей 1, 195, 168 и / 1 1 / 1 33 -6 5 330 5 -6 Р = , Q = 168 -336/11 28/11 195 325/11 -39/11 ) Поэтому значение характера, полученного при проектировании на подпространство размерности 168 равно Xi(g) = (168а0Ы - (336с і(0) - 28а2(0))/П)/364. Подставляя в эту формулу значение а Ы = v — ао(д) — сц{д), получим Xi(0) = (5aoG/) -aife) + 28)/11.
Выберем подгруппу X из G порядка, взаимно простого с 6. Пусть Q = FixpQ — множество вершин графа Г, неподвижных относительно X. Если a, b — две вершины из fi, то [а] П [6] — подграф, допустимый относительно X, поэтому [а] Г) [6] С fi. Значит Г2 — либо пустой граф, либо сильно регулярный граф с А = 2, /І = 3, либо является кликой с числом вершин, не большим 4. Пусть д — элемент простого порядка р из G, A = Fix(#), c i( 7) = pw. Лемма 43 Выполняются следующие утвероіедения: (1) если А — пустой граф, то р = 7 или 13; (2) если А является /3-кликой, то либо /3 = 1 и р = 3 ИЛЇ/ 11; лг о /3 = 2 и р = 2; либо /3 = 4 и р = 3 или 5; (3) если А является сильно регулярным графом диаметра 2, то либо А — граф Поли с параметрами (13, б, 2,3) и р = 3, либо А — граф Петерсеиа и р = 2. Доказательство. Напомним, что хі(о) = (5ао(о) ai(o) + 28)/11. Если А — пустой граф, то р делит 3G4, поэтому р = 2, 7 или 13. В случае р = 13 на множестве вершин графа Г имеется 28 (д)-орбит и 2w + 5 делится на 11. В случае р = 7 на множестве вершин графа Г имеется 52 (д)-орбиты и к; — 4 делится на 11. В случае р — 2 каждая (д)-орбита Ф является 2-кликой, иначе для несмежных вершин я, х3 подграф [х] П [х9] содержит 3 вершины, и по крайней мере одна из них попадает в Д. Поэтому ot\{g) = 364, противоречие с тем, что cv\(g) — 28 делится на 11. Если А является /3-кликой, то р делит 364 —/3 и 34 — /3, поэтому либо /3 = 1 и р = 3 или 11, либо /3 = 2 и р = 2, либо /3 = 4ир = 2,3 или 5. Если /3 = 1 и р = 3, то ai(g) делится на 33.
Ишюлютивпыс автоморфизмы графа с параметрами (676,45,2,3)
Лемма 55 Пусть Г — сильно регулярный граф с параметрами (676,45,2,3) и неглавными собственными значениями 6, — 7, А — индуцированный регулярный подграф из Г, Х{ — миооїсество вершин из Г—А, смежных точно с г вершинами из А, и Х{ = г- Тогда выполняются следующие утвсроісдепия: (1) если А подграф) из Г на w вершинах, то о7о — w причем одно из равенств достигается тогда и только тогда, когда каоїсдая вершина из Г — А смео/сиа точно с w(45 — d)/(676 — w) вершинами из А; (2) если А является объединением /3 изолированных 4-клик и Xi = 0 для г 4, то /3 8, причем в случае (3 = 8 каоїсдая вершина из Г — А смсоїсна с 0 или 3 вершинами из А; (3) если А является объединением у изолированных графов Поли с параметрами (13,6,2,3) и Х{ = 0 для і 4, то 7 3, причем в случае 7 = 3 каоїсдая вершина из Г — А смсоїсна с 0 или 3 вершинами из Д.
Доказательство. Первое утверждение леммы следует из леммы 39 предыдущей главы. Пусть А является объединением восьми изолированных 4-клик. Допустим, что ХІ = 0 для г 4. Тогда Е г = 644, хі+2х2+3хз = 1344 и х2+3х3 = 1344. Отсюда жз = 488, х\ = хч — 0 и XQ = 156. Легко понять, что Д не содержит девять изолированных 4-клик. Утверждение (2) доказано.
Пусть А является объединением трех изолированных графов Пэли с параметрами (13,6, 2,3) и ХІ = 0 для і 4. Тогда гсг- = 637, х\ +2#2 + 3#з = 1521 и х2+3х = 1521. Отсюда х = 507, х\ = х2 = 0 и XQ = 130. Легко понять, что А не содержит четыре изолированных 4-клики. Утверждение (3) доказано. Лемма доказана. Лемма 56 Вполне регулярный граф с параметрами (52,9,2,3) не существует. Доказательство. Пусть Д является вполне регулярным графом с параметрами (52,9,2,3). Заметим, что окрестность любой вершины в Д является объединением трех треугольников, девятиугольником или объединением т-и п-уголышков, т + п = 9.
Пусть а Є Д, d Є Дз(а), h — Ді(а), c3(a,d) = t и {eb...,e } = [d] П Дг(а) Тогда k\ = 9,/ = 18 и Еі з г = 24. По предложению 1.9.1 из [11] имеем С{(а,и) /І — 2 + г, в частности, t 4. Положим A(a,d) = ([а] П Дг( і)) U ([d] П Д2(а)). Если t = 4, то Д(а, d) является полным двудолыи ш графом 7 4,4 с удаленным максимальным паросочетанием. В этом случае для различных i,j подграф [ег] П [е/] содержит d и 2 вершины из Д(а). Поэтому {ei,..., Є4} является такой кокликой из A(d), что [ег]П[е_/] не пересекает A(d). Противоречие со ст{)оением Д( ). Итак, t 5.
Если диаметр Д не меньше 5, то Д 1 + 9 + 18 + 18 + 9 + 1, противоречие. Заметим, что 62(0, е) 5 для любой вершины е из Д2(о). В противном случае д-иодграф [а] П [е] является треугольником и для двух вершин и, w из [а] П [е] подграф [и] П [w] содержит е,а и вершину из [а] Г) [е], противоречие. Так как число ребер между Дг(а) и Дз(а) не больше 90, а каждая вершина из Дз(а) смежна по крайней мере с 5 вершинами из Дг(о), то Дз(а) 18 и А4(а) 6. Положим Q = Дз(а) U Д4(а). Тогда \Q\ = кз + кЛ = 24, каждая вершина из Д4(а) имеет степень 9 в Г2, а каждая вершина из Дз(а) имеет в Q степень, не большую 4.
Заметим, что Д4(а) — [rf] 2 для любой вершины d из Дз(а). В случае А4(а) — [d]\ 3 для вершин щ,..., щ из A4(a) — [d] подграф [d]n[wz] содержит вершины из fi, \l(d)\ = 4ищ несмежна с единственной вершиной Wi из Q(d) для г — 1,..., 3. Тогда вершина w из Q(d) — {wi,W2, w } смежна с щ,іі2, щ и с двумя вершинами из {ei, ...,es}. Так как к 6, то {wi, ...,w3} — подграф из А (а), являющийся 3-кликой. Противоречие с тем, что [w\] Г) [У ] содержит d,w3,u3.
Таким образом, к = 6 и каждая вершина из Дз(а) смежна точно с 4 вершинами из А а). Противоречие с том, что число ребер между Аз(а) и Д4(а) равно 18 4, но не больше б 9. Лемма доказана.
Пусть Г — сильно регулярный граф с параметрами (676,45,2,3), G = Aut(r) и д Є G. Тогда Г имеет собственные значения 45, 6, -7 кратностей 1, 360, 315 и
Поэтому значение характера, полученного при проектировании на подпространство размерности 360 равно Х\{о) — (360ао( 7) + 48ai(g) — 4((#))/676. Подставляя в эту формулу значение 0 2(9) v — ао(д) — ai(g), получим Xi(0) = (7aoM + ai(0))/13-4.
Выберем подгруппу X из G порядка, взаимно простого с 6. Пусть Q = Fix(X) — множество вершин графа Г, неподвижных относительно каждого элемента из X. Если а,Ь — две вершины из Q, то [а] П [Ь] — подграф, допустимый относительно X, поэтому [а]Г)[&] С Q. Значит Г2 — либо пустой граф, либо сильно регулярный граф с А = 2,/І = 3, либо является кликой с числом вершин, не большим 4.
