Содержание к диссертации
Введение
1 Реберно регулярные графы с к > 3t>i — 3 14
1.1 Предварительные результаты 14
1.2 Доказательство теоремы 21
1.3 Вполне регулярные графы с \i = к — 2Ь\ + 2 2G
1.4 Редукция к графам диаметра 29
1.5 Графы диаметра 3 31
2 О сильно регулярных графах с /І = 1 и их автоморфизмах 62
2.1 Предварительные результаты G2
2.2 Автоморфизмы графов с параметрами (v,k,3,l) G4
2.3 Автоморфизмы графа с параметрами (3905,04,3,1) 69
2.4 Группа автоморфизмов графа с параметрами (3905,04,3,1) . 71
2.5 Автоморфизмы графа с параметрами (9701,100,3,1) 77
2.0 Группа автоморфизмов графа с параметрами (9701,100,3,1)... 80
3 Об автоморфизмах дистанционно регулярного графа с мас сивом пересечений {8,7,5; 1,1,4} 86
3.1 Предварительные результаты 80
3.2 Характеры конечных групп и автоморфизмы дистанционно регулярных графов 88
3.3 Ипволютивиые автоморфизмы графа с массивом пересечений {8,7,5;1,1,4} 94
3.4 Граф с массивом пересечений {8,7,5; 1,1,4} не является вершинно транзитивным 105
Литература
- Доказательство теоремы
- Редукция к графам диаметра
- Автоморфизмы графа с параметрами (3905,04,3,1)
- Характеры конечных групп и автоморфизмы дистанционно регулярных графов
Введение к работе
В связи с завершением классификации конечных простых групп возникла задача единого представления конечных простых групп. Перспективным направлением является поиск такого класса конечных геометрий, что каждая конечная простая группа действует флаг-трапзитивпо на некоторой геометрии и все геометрии этого класса допускают классификацию ([15]-[19], [37], [36]). Например, класс билдингов Титса характеризует группы лиева типа [40]. Позднее в этом направлении возникли задачи, не связанные с групповым действием, в частности, такой является задача классификации дистанционно регулярных графов [15].
Пусть G — транзитивная группа подстановок на множестве Q. Если стабилизатор Gp точки р Є ІЇ, имеет г орбит на О,, то говорят, что G имеет подстановочный ранг г (является группой подстановок ранга г). Пусть г = 3 и соответствующие три орбиты — это {р}, Д(р), Г(р). Тогда по группе G удается построить сильно регулярный граф Г, множество вершин которого Q и две вершины p,q смежны в Г, если q Є Г(р) [2G].
Д. Хигман ([26]-[32]) развил теорию групп ранга 3. Эти группы являются группами автоморфизмов сильно регулярных графов, причем они действуют транзитивно как на множествах вершин и ребер, так и на множестве пар различных несмежных вершин. Такие графы являются дистанционно транзитивными графами диаметра 2.
В настоящее время при исследовании графов вовлекаются симметрии все более общего вида. Сначала это были условия дистанционной транзитивности и дистанционной регулярности графов, а затем и более общие условия комбинаторной симметричности. Оказалось, что в некоторых случаях комбинаторная симметрия графа влечет его дистанционную транзитивность.
Первые результаты о комбинаторно симметричных графах были получе-
ны в пятидесятых годах. Пусть L(Kn) — реберный грае]) полного графа Кп на п вершинах или в других обозначениях треугольный граф Т(п). Этот граф является сильно регулярным графом с параметрами ((), 2(п — 2), п — 2,4). В работах 1959-60 годов Л. Чанг [23] и А. Хоффман ([33], [34]) независимо показали, что треугольный граф Т(п) определяется однозначно своими параметрами для всех п, за исключением п = 8. Для случая п = 8 было показано, что кроме треугольного графа Т(8), такие же параметры имеют только три графа, которые были найдены Л. Чаигом в 1949 году [22].
Реберный граф L(K„hn) полного многодолыюго графа К7П,п является ко-реберио регулярным графом с параметрами (mn,m + п — 2,2). Граф КШ)П называют га х п решеткой. При m = п решетчатый граф является сильно регулярным графом с параметрами (п2,2п — 2,п — 2,2). С. Шрикханде в [39] показал, что граф, имеющий параметры n х п решетки является либо решеткой, либо графом Шрикханде (п = 4).
Результаты Л. Чанга, С. Шрикханде и А. Хоффмана [35] были объединены Дж. Зейделем [38], который определил все сильно регулярные графы с наименьшим собственным значением —2. Дж. Зейдель показал, что кроме треугольных графов Т(п) и решетчатых п X п-графов, сильно регулярными графами, которые имеют наименьшее собственное значение —2, являются только графы КпХ2, графы Петсрсена, Шрикханде, Клебша, Шлефли и три графа Чанга.
В работе рассматриваются неориентированные графы без петель и кратных ребер. Если а, Ъ - вершины графа Г, то через d(a, Ь) обозначается расстояние между а и Ь, а через Г;(а) - подграф графа Г, индуцированный множеством вершин, которые находятся на расстоянии г в Г от вершины а.
Подграф Гі(а) называется окрестностью вершины а и обозначается через [а]. Через а1 обозначается подграф, являющийся шаром радиуса 1 с центром а.
Граф Г называется регулярным графом степени к, если [а] содержит точно к вершин для любой вершины а из Г.
Граф Г называется реберно регулярным графом с параметрами (г;,/с, Л), если Г содержит v вершин, является регулярным степени к, и каждое ребро из Г лежит в Л треугольниках.
Граф Г называется вполне регулярным графом с параметрами (v, к, А,/і), если Г реберно регулярен с соответствующими параметрами и подграф [а]П[Ь] содержит ц вершин в случае d(a,b) — 2. Вполне регулярный граф диаметра 2 называется сильно 'регулярным графом.
Число вершин в [а] П [6] обозначим через Л(а, 6), если d(a,b) = 1, а соответствующий подграф назовем Х-подграфом.
Если d(a,b) = 2, то число вершин в [а] П [Ь] обозначим через ц(а,Ь), а соответствующий подграф назовем /л-подграфом.
Если вершины и, w находятся на расстоянии і в Г, то через bi(u,w) (через Ci(u,w)) обозначим число вершин в пересечении Гі+і(и) (Г,-_і(и)) с Г(гу). Заметим, что в реберно регулярном графе число bi(u,w) не зависит от выбора смежных вершин u,w и обозначается через бі.Граф Г диаметра d называется дистанционно регулярным с массивом пересечений {&о, h,..-.., bd-ї, сі,..., о/}, если значения 6,-(u, w) и c,-(w, ги) не зависят от выбора вершин u,w на расстоянии г в Г для любого і = 0, ...,d.
Пусть Т — некоторый класс графов. Граф Г назовем локально Т графом, если [а] лежит в Т для любой вершины а графа Г. Если при этом класс Т состоит из графов, изоморфных некоторому графу А, то грае}) Г назовем локально А-графом.
Цель диссертации. Целью данной работы является решение следующих задач:
1) Изучить связные реберно регулярные графы с параметрами (v, к, X) и к > ЪЬх - 3.
Найти возможные автоморфизмы сильно регулярных графов с малыми параметрами А и \i.
Найти возможные автоморфизмы дистанционно регулярных графов диаметра 3 с малым числом вершин.
Методы исследования. Основными методами исследования являются методы теории конечных групп, теоретико-графовые методы и методы локального анализа комбинаторно симметричных графов.
Научная новизна. Основные результаты, полученные в работе, являются новыми. Выделим из них следущие.
Исследованы связные реберно регулярные графы с параметрами (v, к, А) и к > ЗЬі — 3.
Найдены возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярных графов с параметрами (v, к, 3,1) и изучены группы автоморфизмов графов с параметрами (3905,64,
3,1) и (9705,100,3,1).
3. Найдены возможные порядки и подграфы неподвижных точек автомор
физмов дистанционно регулярных графов с массивом пересечений {8,7,5; 1,
1,4}.
Теоретическая и практическая ценность. Работа носит теоретический характер. Результаты продолжют изучение комбинаторно симметричных графов и их автоморфизмов. Результаты и методы диссертации могут быть использованы для изучения алгебраических структур подобного типа.
Апробация работы. Основные результаты работы докладывались па: Международной школ е-конференции но теории групп, посвященной 75-летию со дня рождения А.И.Старостина (Нальчик, 200G г.) и на 37-й и 38-й Региональных молодежных конференциях ИММ УрО РАН (Екатеринбург, 2006-2007 гг.);
Результаты работы докладывались и обсуждались на алгебраических семинарах ИММ УрО РАН.
Публикации. Основные результаты диссертации опубликованы в работах [42]-[47]. Работы [42]—[4G] выполнены в нераздельном соавторстве с А.А. Михневым.
Структура и объем работы. Работа состоит из введения, трех глав и списка цитированной литературы, содержащего 47 наименований.
Результаты диссертации.
Во введении обсуждается история вопроса, даются определения и формулируются основные результаты работы. В главе I рассматриваются связные реберно регулярные графы с параметрами (v, к, А) и к > З&і — 3.
При изучении реберно регулярных графов с к > f(b{) для некоторых функций / удается установить оценку v < д(к) (или получить описание графов, для которых не выполняется оценка v < д{к)). Так, в [15, лемма 1.4.2] доказано, что если Г — связный неполный реберно регулярный граф с параметрами (v,k,X), в котором & > 3&1, то диаметр Г равен 2 и v < 2к — 2. Фактически доказано, что v < к — 2 + 3&i + 3/(&i + 1), и уточнение границы для числа вершин потребует описания графов с малыми значениями &i и графов, насыщенных хорошими парами вершин. В следствии из [1] доказано, что если Г — связный реберно регулярный грае]) с параметрами (v, А;, А), в котором ЗА > 2к — 5 (равносильно, к > З&і —2), то либо Г — многоугольник или граф икосаэдра, либо к = 4 и каждое ребро графа Г лежит в единственном треугольнике, либо Г — граф диаметра 2 с не более чем 2к вершинами, пятиугольник, 3x3 решетка или треугольный граф Т(7). Через Т(к) обозначим класс регулярных графов степени к без треугольников, а через 8(к) — класс реберных графов для графов из Т(к). Пусть расстояние между вершинами u,w в реберно регулярном графе Г равно 2. Пару (u,w) назовем хорошей, если fi(u,w) = к — 2bi + l, назовем почти хорошей, если fi(u,w) = к — 26i -f-2.
Граф -Р(га) с v = Ьт , к.— Am — 2 и &i = 2т — 1 получается заменой вершин пятиугольника на попарно непересекающиеся m х т решетки. Следующие результаты является основными в главе I.
Теорема 1 Пусть Г — связный реберно регулярный граф с параметрами (г», Аг, Л) и Ь\ = к — А — 1. Если и Є Г, w, z — две несмежные вершины из Г2(и) и ц(и,ш) = ц(и,г) = к—2Ь\-\-2, то для^у = \[u]n[w]n[z]\ выполняются следующие утвероіедепия:
к < 6і(3 — (27 — 6)/(72 -37 + 2)) + 7-6, причем в случае равенства li{w, z) = 26i — 2 + 7 и каяедая вершина из ([и] — [w] U [z]) U ([ш] П [z]) — [и]) смеоісна с одной или с двумя вершинами из [и] Г) [w] П [z\;
к < 2&i + 7 — 6 + 4&i/(7 + 1), причем в случае равенства fi(w,z) = 26i — 2 + 7 м каоїсдая вершина из ([и] — [w] U [z]) U ([гу] C\[z]) — [и]) смеоісна с (7 — 1)/2 вершинами из [и] П [ги] П [г];
если j > I, то к < 36i — 4, причем в случае к = 3bi — 4 получим 7 = 2.
Хорошо известно, что если любая пара вершин связного реберно регулярного графа, находящихся на расстоянии 2, является хорошей, то граф оказывается пятиугольником или графом икосаэдра. С помощью теоремы 1 получено описание связных реберно регулярных графов, в которых любая пара вершин, находящихся на расстоянии 2, является почти хорошей.
Следствие 1 Пусть Г — вполне регулярный граф с параметрами (f, к, Л, /z) и /і = к — 2&i + 2. Тогда Г — либо граф Зейдсля, либо тривалентний граф) без треугольников диаметра, большего 2, с \і = 1.
Теорема 2 Пусть Г — связный реберно регулярный граф с параметрами (v, k,X) и k > З&1 — 3. Тогда выполняется одно из следующих утверждений: (1) диаметр Г не больше 2 и либо число вершин v не превосходит 2& + 4, либо граф Г совпадает с графом Р(2) или локально шестиугольным графом на 17 или 19 вершинах;
диаметр Г не меньше 3 и Г является тривалентним графом без треугольников, реберным графом четырехвалентного графа без треугольников или локально шестиугольным графом;
Г — граф диаметра 3 с |Гз(и)| < 1 для любой вершины и.
Следствие 2 Пусть Г — связный вполне регулярный граф) диаметра, большего 2, с параметрами (г;, /j, Л, д) и к > ЗЬ\ — 3. Тогда выполняется одно из следующих утвероіедений:
Г Є (4) и /х = Ьі - 2 = 1;
Г Є Т(3) U (3) иц = Ьі-1 = 1;
/z = b\ иТ является п-у гольником, п > 6, полным двудольным графом 7^4,4 с удаленным максимальным паросочетанием, графом икосаэдра, графом Дэюонсопа J(6,3), локально Т(6)-графом Тэйлора на 32 вершинах или локально Шлефли-графом Тэйлора на 56 вершинах.
Во второй главе работы выясняются возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярных графов с (Л,/х) = (3,1).
Автоморфизмы сильно регулярных графов с (і = 1 рассматривались в [4, 13] для графов Мура и в [5] для графов с Л = 2 (хорошо известно, что сильно регулярные графы с A = fi — 1 не существуют).
Известно (предложение 1.1.2 [15]), что сильный граф с ц > 2 регулярен. Поэтому непустые подграфы неподвижных точек 2'-автоморфизмов сильно регулярного графа с тах{А,//} < 2 либо являются кликами, либо сильно регулярны с этими же параметрами.
Пусть Г — сильно регулярный граф с параметрами (v, к, 3,1), G = Aut(r). Тогда п2 = (А — /і)2 + 4(& — ц) = 4к, причем окрестность любой вершины является объединением изолированных 4-клик. Поэтому к = 4и2,п = 4и и Г имеет неглавные собственные значения п — m = 2и + 1 и — m — 1 — 2и. Далее, v = 1 + 4и2 + 16и2(и2 — 1), условие целочисленности выполнено, и так как число 5-клик в Г равно vk/20, то и2 сравнимо с 0 или 1 по модулю 5.
Для д Є G через а\{д) обозначим число пар вершин (и,ия) таких, что и,и9 смежны.
Через Fix(g) обозначим подграф индуцированный на множестве вершин графа Г, неподвижных относительно автоморфизма д.
Мельницей называется граф Г, совпадающий с а1 для некоторой вершины а, в котором [а] является объединением изолированных клик одинаковых порядков.
Графом Грюиберга-Кегеля (графом простых чисел) конечной группы G называется граф, вершинами которого являются простые делители \G\ и два делителя р, г смежны в этом графе, если G содержит элемент порядка рг.
Основным результатом второй главы являются
Теорема 3 Пусть Г — сильно регулярный граф с параметрами (v,k, 3,1), д — элемент простого порядка р из Aut(r) и О, — Fix(#). Тогда v = 16u4 — 12и2-\-1, k = 4u2 для некоторого натурального числа и такого, что и2 сравнимо с 0 или 1 по модулю 5 и либо р = 2, каоїсдая вершина из Г — О, смсоїспа с единственной вершиной из О, и выполняется одно из утверждений:
(1) О, — сильно регулярный граф с А = 3, ц = 1 степени 4w2 ии = 2ш2 — 1
делит а.\{д)/4 + w2;
Q — or для некоторой вершины а Є Г и 4и делит а\(д); либо р = 3 и выполняется одно из утверждений:
О, — одновершинный граф, 3 делит и и Аи делит cxi(g);
Q является подграфом из а1, причем Q,(a) содержит х изолированных вершин и у клик порядка 4, 3 делит (и2 — 1, х-\-у — 1) и 2и делит их-\-2у — х;
О, — граф Петерсена и и = 6;
О, — граф Хоффмана-Синглїпона и и = 9 или 21;
О, — граф Ашбахсра и и= 10601;
О, — является сильно регулярным графом с Л = 3, \і — 1 степени 4w2, число и2 — w2 делится наЗ и и делит 4w4 — Зш2;
либо р>5 и выполняется одно из утвсроісдений:
(9) fi — пустой граф, р делит l+4u2+16u2(w2—1) и 4и делит а\(д)+2и+1;
Q — одновершинный граф, р делит и2 и Аи делит cv\(g);
Q является Ъ-кликой, р делит и2 — 1 и Аи делит cvi(g) — А;
Q является мельницей на Ах+1 вершинах из а1, р делит (и2—1, х—1) и Аи делит Ах — ct\{g);
П — сильно регулярный граф) степени Aw2 с А = 3, /і = 1; число р делит и2 — w2 и и делит Aw4 — 3w2 — a\{g)/A.
Теорема 4 Пусть Г — сильно регулярный граф) с параметрами (3905,64,3, 1), g — элемент простого порядка р из Aut(r) и Q, = Fix(g). Тогда выполняется одно из следующих утвероіедсний:
р > 3, Q — либо пустой граф, р = 5,11 или 71 и 16 делит a\(g) + 9, либо является Ъ-кликой, р — 5 и ct\{g) — 5(16s + 4), либо является мельницей на Ах + 1 вершинах из а1 для некоторой вершины а, р = 5, х = 6 или 11, cvi(g) = 5(16g + 8) или 5(16r + 12) соответственно;
р = 3 и fi является подграфюм из а1, содероісащим х изолированных вершин и у клик порядка А, где (х,у) Є {(0,4), (0,16), (2,5), (4,6),(6,7),(8,8),(16,0))/
р = 2 и О, = ах для некоторой вершины а.
Следствие 3 Сильно регулярный граф) с параметрами (3905,64,3,1) не является вершинно транзитивным.
Теорема 5 Пусть Г — сильно регулярный граф) с парамстралш (9701,100,3, 1)? 9 ~ элемент простого порядка р из Aut(r) и Q = Fix(g). Тогда выполняется одно из следующих утверждений:
р = 89 или 109, О, — либо пустой граф и 20 делит ai(g) + 11;
р = Ъ,0. является одновершинным графом, и сх\{д) делится па 20;
p — З, О, — подграф из а1, и Q(a) является объединением х изолированных вершин и у клик порядка 4, 3 делит х + у — 1 и 5 делит 2х + у;
р = 2 и О, = а1 для некоторой вершины а.
Следствие 4 Порядок группы автоморфизмов сильно регулярного графа Г с параметрами (9701,100,3,1) делит 2гЗ-5289-109 и Г не является вершинно транзитивным графом.
В третьей главе работы выясняются возможные порядки и подграфы неподвижных точек автоморфизмов дистанционно регулярных графов с массивом пересечений {8,7,5; 1,1,4}.
Для изучения возможных порядков и подграфов неподвижных точек автоморфизмов дистанционно регулярных графов Г. Хигмеп предложил оригинальный метод, использующий теорию характеров конечных групп. Этот метод изложен в монографии П. Камерона [20], причем он применялся только к изучению инволютивиых автоморфизмов сильно регулярного графа с параметрами (3250,57,0,1). Позднее, в работах [2]-[4] изучались автоморфизмы сильно регулярных графов с малыми числами пересечений. В данной работе этот метод применяется для изучения автоморфизмов гипотетического дистанционно регулярного графа с массивом пересечений {8,7,5; 1,1,4} па 135 вершинах.
Основными результатами третьей главы являются следующие теорема и следствие.
Теорема 6 Пусть Г — дистанционно регулярный граф), имеющий массив пересечений {8,7,5; 1,1,4}; G = Aut(r), g — элемент из G простого порядка р uQ = Fix(g). Тогда верно одно из утверждений:
р = 3 или 5 и Q — пустой граф;
р = 7 и Q является двухвершинной кликой;
(3) p = 2, Q состоит вершин, попарно находящихся на расстоянии 3 в Y, и \Q\ = 3,5,7,9 или 11.
Следствие 5 Дистанционно регулярный граф, имеющий массив пересечений {8,7,5; 1,1,4}, не является вершинно трапзитивнъш.
Доказательство теоремы
Лемма 1.1.11 Если Г является реберно регулярным графом с Ь\ 3, к 3&1 — 1, то Г — либо многоугольник или граф икосаэдра, либо полный много-дольный граф) A rx(b!+i); треугольный граф Т(п), n = 5,6 или граф) Клебша.
Доказательство. Если Ь\ = 1, то Г - многоугольник или полный многодольный граф КГх2 Если Г - сильно регулярный граф, то лемма следует из леммы 1.1.10. Допустим, что Г - не сильно регулярный граф. Пусть &i = 2. Ввиду леммы 1.1.8 имеем А l/2-\-k — y/2k + 2, т.е. 2к + 2 (&i + 3/2)2 и к (&i + ЗЬі)/2. Отсюда А; = 5, А = 2 и Г является графом икосаэдра.
Пусть Ь\ г= 3. Снова ввиду леммы 1.1.8 получим к {Ь\ + ЪЬ\)/2. Отсюда к = 8, А = 4 и по следствию из [lj диаметр Г равен 2, а число вершин в Г не больше 16. Так как vkX делится на G, то v = 15. Для любой вершины и число ребер между [и] и Гг(и) равно 24.
Так как Г - не сильно регулярный граф, то fi(u,w) = 3 для некоторых несмежных вершин и, w Є Г. В этом случае число треугольников с основанием в [и] П [w] и вершиной в ([и] — [w]) U ([w] — [и]) равно 3. Заметим, что вершина из [и] - [w] не может быть смежна с 3 вершинами из [и] П [w], иначе каждая вершина из [w] — [и] смежна с единственной вершиной из [и] П [w] и [гу] — [и]\ 6, противоречие. Поэтому можно считать, что [w] — [и] содержит не менее двух вершин Zi, смежных с ребрами из [и] П [w]. Тогда [и] — [х]
содержит единственную вершину, смежную с ребром из [и] П [го], и 4 вершины, каждая из-которых смежна с единственной вершиной из [и] П [ги]. Ввиду леммы 1.1.5 fi(u,Zi) 5, поэтому [го] — [и] содержит еіце одну вершину X с ц{и,х) — 3. Отсюда [и] - ([го] U [х]) = {г/і,гу2}. Как и выше, [и] — [х] содержит единственную вершину, смежную с ребром из [к]П[ш], поэтому вершины 2/1,2/2 смежны. Далее, каждая вершина d из [и] Г) [го] смежна с единственной вершиной из Мп[ж] и из {уиУ2}- Поэтому [у] и [z] содержат непересекающиеся тройки вершин из [и] П ([го] U [х]). Отсюда [у] П [z] содержит 3 вершины из [х] П [го], каждая из которых смежна с единственной вершиной из [и] Г) [го]. Противоречие с тем, что [х]П[го] состоит из 4 вершин, две из которых смежны с ребрами из [и] П [го].
Лемма 1.1.12 Если Г — реберно регулярный граф с к 4&і — 2 и Г со ?ер-э/сигд хорошую пару, то к = 4&i — 2 и Г является пятиугольником.
Доказательство. Пусть fi(u, го) = fc—2&i+1, Х - множество всех вершин из ([и] U [го]) — ([г/] Г) [го]), смежных точно с і вершинами из.[и] П [го], xi = \Х{\. Подсчитав число ребер между [и] П [го] и ([и] U [го]) - ([и] Г) [го]), а также число треугольников с основанием в [и] П [го] и вершиной в ([и] U [го]) — ([и] П [го]), получим равенства ХІ = 4&i — 2, гх; = (А; — 2&і + 1)(2&і — 2) и Q)XJ = ( "2J1+1)(&i-2). Отсюда г 2аг,- = (А; —2Ьі + 1)(А;Ьі —2А:—2bf+6&i —2). Положим x = (fc - 2&! + l)(26i - 2)/(46i - 2).
Тогда0 Жі(г-х)2 = г2ж-жгх, и (А;-26х + l)(fc&i- 2А; -2 + 6оі -2)(46і-2) (А;-26і + 1)2(26і-2)2. Отсюда ((k-2bl+l)(bl 2)+bl)(2bi-l) (k - 26i + 1)(2 - 4&i + 2) и A; 462 - 2.
Если A; = 4&i — 2, то x,- = 0 для іфхи каждая вершина из ([м]и[го]) — {[и]П [го]) смежна точно с Ь\ — 1 вершинами из [и] ҐІ [го]. Таким образом, каждая вершина с? из [и] — [го]) смежна точно с &і вершинами из [го] — [и] и /і(гх, d) = 2bі — 1. Отсюда Г является сильно регулярным графом Тервиллигера без 3-лап, поэтому Г — пятиугольник.
Пусть Г является реберно регулярным графом с параметрами (v, к, А). Если Г содероісит две несмежные вершины u,w с fi(u, w) = к—1, {u j- = [w\—uL, {ги } = [и] —w1, то выполняются следующие утверждения: (1) [и ] П [и] П [w] = [w ] П [и] П [w]; (2) если к 2bi, то вершины и , w несмежны и //(w , w ) = к — 1.
Доказательство. Пусть вершина d из [и] П [ги] имеет степень а в графе [и] П [ги]. Если d смежна сад , то А = а + 1 и вершина d смежна с и . Если же d несмежна с ги , то Л = а и вершина с? несмежна с и . Утверждение (1) доказано. Пусть а Є [и ] — (и1 Uw;1). Если а несмежна с w , то [а] П [ги] = ([а] П [и]) U {и }, причем для с/ Є [а]П[м] имеем [d] —(a1U«-L) = [ i] — (ах иго ). Ввиду леммы 1.1.1 степень d в графе [а] П [и] равна степени d и графе [а] П [ги]. Если к 2&i, то и смежна с некоторой вершиной d из [а]П[гх], противоречие. Итак, каждая вершина из [и ] — (и1 U ги1) смежна с ги . Отсюда fi(u ,w ) = к — 1 и вершины гх ,ги неемжны. Лемма доказана.
В этом параграфе Г — реберно регулярный граф, имеющий параметры (v, к, А) Пусть и Є Г, w,z — несмежные вершины из Г2(и), ц(и,ги) = n(u,z) = к — 2&i + 2 (т.е. (и,ги) и (u, z) — почти хорошие пары) и 7 = [и] П [ги] Г\[г]\. Положим /І = до(ги, z).
Выполняются следующие утвероіедения: (1) для любой вершины d Є [и]П [ги] Г) [z] подграф dL содероісит [и] Г) [ги], [w]n[z]; 3&i+7—4—А: вершин из [и] — {[w]\J[z]) ubi—2 вершин из [w]r\[z] — [u]; (2) для различных вершин d,e 6 [м] П [ги] П [z] подграф) [d] Л [є] содероісит u,w,z, 7 2 вершин из [u]n[w]n[z] и по к — 2oi+2 — 7 вершин из [u]D[w) — [z] и из [и] Л [г] — [ги].
Редукция к графам диаметра
Доказательство. Пусть fi(u, х) = Ь\. Тогда xLCid1 = х1 — [и] для любой вершины d Є [#]n[z]. Если d, у — различные вершины из [ж]П[г], то с Пт/1 = A U ([х] П [z]), противоречие с тем, что вершина z смежна с d,y. Отсюда [i(x, z) = 1 и Ь\ 3, противоречие.
Пусть fJ,(u,x) = /J.{x,z) = Ь\ — 1. Тогда Д = &i и для любой вершины w Є Мп[ж] найдется единственная вершина из ([и]Г)[ж])иД, не попадающая в w1. Число ребер между Д-{ж} и ([и]П[яг])и([а;]П[-г]) не меньше 2(&і-1)(&і-2). Поэтому каждая вершина из Д — {х} смежна точно с 26і — 4 вершинами из ([и] П [х]) U ([х] П [z]) и подграф Д(ж) является (&і — 1)-кокликой. Далее, вышеуказанное число ребер равно 2(6i — l)(h — 2) и подграфы [и]П[ж], [ж]П[,г] являются кликами. Теперь для любых двух вершин w, w Є [и] П [х] подграф [w] П [w1] содержит и, Ъ\ — 3 вершин из [и] П [х] и точно Ь\ - 2 вершин из Д. Пусть d — отличная от х вершина из [и;]П[т/]. Так как Мп[а;]П[ ] = Ь]_ — 2, и каждая вершина из [it] П [х] П [d] смежна с &i — 2 вершинами из Д — {х}, то //(w,d) = fi(d,z) = &i — 1. Так как w смежна с единственной вершиной из Гг(м) — Д, то &i = 4 и [d] П [ж] содержит не менее двух вершин из [и]. Симметрично, [d] П [х] содержит не менее двух вершин из [z], противоречие с леммой 1.1.6. Лемма 1.4.2 Верны равенства li(u,x) = fi(x,z) = Ь\ — 2. Доказательство. Предположим, что р(щх) = Ь\ — 2 и n(x,z) = Ь\ — 1. Тогда Д = &i + 1 и для любой вершины w Є [и] П [ж] найдется единственная вершина из Д, не попадающая в [w]. Отсюда Д — {х} содержит две вершины d, е, смежные со всеми вершинами из [и] П [х]. Ив леммы 1.1.4 следует, что fj,(u,d),/2(u,e) Ъ\. Ввиду леммы 1.4.1 имеем с?, є Є z{z). Теперь для любой вершины у Є [х] Ґ1 [z] подграф [х] П [у] содержит по &i — 2 вершин из [х] П [z] и из Д. Поэтому [х] П [z] является кликой, и для различных у, у Є [х] П [z] подграф [у] П [у1] содержит z, 61 — 3 вершин из [я] П [г] и Ьі — 1 вершин из Д, противоречие. Лемма доказана.
Завершим доказательство предложения 1. Из лемм 1.1.1,1.4.2 следует, что Mu»d) = fi(d, z) = b\ — 2 для любой вершины d из [w] Г) [у], в частности, [w] — и1 и [у] — г1 содержатся в d1. Далее, Д = &i + 2 и число ребер между ([и] П [х]) U (И И) и Д - {х} равно 2(6i — 2)(6i - 1)- С другой стороны, ввиду леммы 1.1.4 каждая вершина из Д — {х} смежна не более чем с двумя вершинами из ([и] П [ж]) U ([ж] П И). Поэтому 2(&i - 2)(6i - 1) 2(6i + 1) и &і З, противоречие. Предложение 1 доказано.
Пусть граф Г имеет диаметр 3 и является контрпримером к теореме. Тогда k = 3&i — 3 и Л = 26i — 4. По лемме 1.1.1 степень любой вершины в /І-иодграфе из Г не меньше Ь\ — 3. Если Ь\ = 2, то ввиду леммы 1.1.2 Г Є Т(3). Если Ь\ = 3, то ввиду леммы 1.1.3 окрестности вершин в Г либо состоят из двух изолированных треугольников, либо являются шестиугольниками. В любом случае получим противоречие с выбором Г. Значит, Ь\ 4.
Предложение 3 Пусть Г — связный реберно регулярный граф диаметра 3 с параметрами (v,k,X). Если к = З&і — 3, hi 4, то Гз(и) 1 для любой вершины и.
Пусть выполнены условия предложения 2. Зафиксируем геодезический 3-путь uwxy. В леммах 1.5.1-1.5.11 доказывается, что Ь- и х) = 1. Имеем [у] П Гз(и ) С Гг(и) (леммы 1.5.2-1.5.4). Для а Є 2{и) и А(а) = [а]ПГз(и) подграф Л(а) является кликой из Гг(іу) (лемма 1.5.5). Допустим, что [х] содержит две вершины y,z из Гз(и). Тогда ц(и,х) &i (лемма 1.5.1), [у] — zL С (и) (лемма 1.5.G) и каждая вершина d из [и]ПГ2(у) смежна с вершиной из [г/]П[г] (лемма 1.5.7). Наконец, каждая вершина из [и] П Гг(?/) смежна не более чем с одной вершиной из [у] — z1 (леммы 1.5.8-1.5.10).
Лемма 1.5.1 Если [х] содержит вершину z из Гз(и) — {у], то ц(и,х) Ь\. Доказательство. Допустим, что [х] содержит вершину z из Гз(«) — {у} и [i(u,x) = &i. Докажем
(1) х1 П yL = х1 П г1 = у1 П z1. Заметим, что [х] П [it] содержит 6і вершин вне у1 Uz1. Поэтому х1 Пу1 — x1f\z1, вершины у, z смежны и х1Пу1 = y1r\z1. Утверждение (1) доказано. Докажем
(2) если а Є [w] П [у] — {х} и fi(u,a) = &і, то вершины x,z несмежны с а. Пусть а Є [w] П [у] - {x} и /i(u,a) = 61. Если a смежна с z, то по утверждению (1) получим а1 П у1 = а1 П z1 = у1 П г1, противоречие с тем, что тогда а смежна с х. Значит, вершины х, z несмежны с а. Утверждение (2) доказано. Докажем
(3) если d — смежная с х вершина из [w] П [у], то {w} = [и] П [d] П [ж]. Пусть d — смежная с х вершина из [w] Г) [у]. Если fi(u,d) = Ь\ — 2, то тройка it, ж, d является почти хорошей. Так как [d] Г) [х] содержит вершины у, z, несмежные ни с одной вершиной из [и] Л [х] П [d], то ввиду леммы 1.1.6 получим {ги} = [и] П [с/] П [ж].
Пусть fi(u, d) = b\ — 1. Тогда [d] — у1 содержит b\ — 1 вершин из [и] и единственную вершину сине [и]. Симметрично, [с/]—г1 содержит Ь\—1 вершин из [и] и единственную вершину е вне [и]. Если е = с, то с?1 П yL = d1 П z1 = у1 П -г1, противоречие с тем, что ги Є [G( Г) [ж]. Значит, е / с и і/1 П z1 содержит Л + 1 вершин из d1. Поэтому ж1 П d1 содержит А + 1 вершин вне [и] и единственную вершину w из [и]. Утверждение (3) доказано. Докажем (4) подграф [и] П [х] является кликой. Пусть степень w в графе [it] П [х] равна &i — 3. Тогда [w] — и1 С х1 и ввиду утверждения (1) имеем [ги] П [?/] = [ги] П [л] = [ги] — и1.
Допустим:, что подграф [ги] П [у] содержит две несмежные вершины d, d . Положим 5 = \[и]Г) [d]П [d ]\. Тогда /i(it, d) = //(it, d ) = b\ — l и no лемме 1.1.G получим 5 2. Если J = 1, то [г/] Г) [ги] содержит по &i — 2 вершин в каждом из подграфов [с/], [с? ] и но утверждению (3) не пересекает [х]. Противоречие с тем, что тогда Ъ\ 3. Если же 6 = 2, то [и] П [w] содержит вершину из [d] П [d1], по Ъ\ — 3 вершин в каждом из подграфов [d] — [d1], [d \ — [d] и из [х]. Отсюда &i = 4. Противоречие с тем, что [ги] П [г//] содержит u,d,d и по вершине из [и] П [d], [w] П [d1]. Значит, подграф [ги] П [у] является &і-кликой.
Автоморфизмы графа с параметрами (3905,04,3,1)
Наименьшая степень сильно регулярного графа с А = 3,// = 1 достигается при и = А. Такой граф Г имеет параметры (3905,04,3,1) и собственные значения 9 и —7. Пусть G = Aut(T). Тогда , \ 9 / ч аМ . 55 = 16 )- 6-+16 для любого д Є G. В частности, 16 делит 9(ао(д) — 1) — ot\(g). Лемма 2.3.1 Пусть д — элемент простого порядка р из G и Q = Fix(g). Если р 3, то выполняется одно из утиероіедеиий: (1) Q — пустой граф, р = 5,11 или 71, и 16 делит oti(g) + 9; (2) П является Ь-кликой, р = 5 и ai(g) = 5(16s + 4); (3) Q является мельницей на Ах +1 вершинах из а1, р = 5, х = 6,11 или 16, аі( 7) = 5(16(7 + 8), 5(16г + 12) или 0 соответственно.
Доказательство. Возможности для Q. выяснены в лемме 2.2.1. Если Q — пустой граф, то р делит 3905 = 5 11 71 и 16 делит a\{g) + 9. Напомним, что ввиду леммы 2.1.2 каждая (д)-орбита является кликой, кокликой или многоугольником. В случаер = 71 получим а\(д) = 71(16х+1). Если о.\{дг) = 17-71 для некоторого і 6 {0,..., 34}, то a\(gj) = 71 для j Є {0,..., 34} —{г} и на Г имеется 51 многоугольная и 4 кокликовых (#)-орбиты. Если же a\{gl) = 71 для любого г Є {0,..., 34}, то на Г имеется 35 многоугольных и 20 кокликовых (д)-орбит. В случае р = 11 получим а.\{д) — 11(16?/ + 5). Если же р = 5, то а\{д) = 5(16z + 11) (заметим, что только в этом случае возможны кликовые орбиты). Если Q — одновершинный граф {а}, то р делит и2, противоречие с тем, что и = 4. Если Q является 5-кликой, то р = 5, 16 делит ai(g) — 4 и а\(д) = 5(16s + 4) для некоторого целого числа s.
Если Q является мельницей на 4х + 1 вершинах из а1, то р делит (16 — х115). Поэтому р = 5 и х — 6,11 или 16. Соответственно, число ai(g) равно 5(16?+ 8), 5(16г+12)или0. По выбору и граф Q. не может быть сильно регулярным графом с А = 3,/1 = 1. Лемма 2.3.2 Пусть f — элемент порядка 3 из G, S = Fix(/). Тогда является подграфом из а1 для некоторой вершины, а, Е(а) содер жит х изолированных вершин и у клик порядка 4, и (х, у) Є {(0,4), (0,16), (2,5), (4,6), (6,7),(8,8),(16,0)}. Доказательство. Ввиду леммы 2.2.2 граф S С а1 и (а) состоит из х изолированных вершин и у клик порядка 4. Далее, 3 делит х + у — 1 и 8 делит Ъх + 2у, в частности, х четно. Если х = О, то 3 делит у — 1, 4 делит у и у = 4 или 16. Если ж = 2, то 3 делит у + 1, 4 делит 3 + у и у = 5. Если ж = 4, то 3 делит у, 4 делит 2 + Зу и / = 6. Если ж = 6, то 3 делит у — 1, 4 делит у + 1 и у = 7. Если а; = 8, то 3 делит у + 1, 4 делит у и у = 8. Если х — 10, то 3 делит у, 4 делит у — 1 и у = 9, противоречие с тем, что х + у 16. Если ж = 12, то 3 делит у — 1, 4 делит у + 2, противоречие. Если х = 14, то 3 делит у + 1, 4 делит у + 1, противоречие. Если х = 16, то у = 0. Лемма доказана. Из леммы 2.2.3 следует, что для любой инволюции s Є G подграф Fix(s) совпадает с а1 для подходящей вершины а. Теорема 4 доказана.
Пусть сильно регулярный граф Г имеет параметры (3905,64,3,1), G = Aut(r), /С — множество 5-клик графа Г. Так как каждая вершина из Г лежит в шестнадцати 5-кликах, то /С = 16 11 71. Пусть R — силовская 5-подгруина из G. Тогда R фиксирует некоторую 5-клику К. Через Я обозначим поточечный стабилизатор К в группе G и положим Р = ППН. Тогда индекс Р в R не больше 5. Напомним, что по лемме 2.3.1 для любого элемента д порядка 5 подграф Q, = Fix(#) является пустым, 5-кликой или мельницей на 4х + 1 вершинах из а1, х = 6,11 или 16. Лемма 2.4.1 Выполняются следующие утверждения: (1) для а Є К при действии на [а] каждый элемент g порядка 5 из Р имеет один из типов: (i) g фиксирует единственную 4-клику из [а], (ii) Fix(g) — подграф из а1 для некоторой вершины, а Є К, содержащий шесть 5-клик, (Hi) Fix(g) — подграф из а1 для некоторой вершины а Є К, содероіса-щий одиннадцать 5-клик (iv) Fix(g) = а1 для некоторой вершины а Є К; (2) элемент любого из типов (И — ги) относительно а является элементом типа (г) относительно любой вершины Ь из К — {а}; (3) Н не содероісит элементов порядка 25. Доказательство. Утверждения (1) и (2) следуют из леммы 2.3.1.
Пусть / — элемент порядка 25 из Н, g = f. Если g типа (г), то для а Є К элемент / действует без неподвижных точек на множестве из 15 клик в [а], отличных от К — {а}, противоречие. Если g типа (гг), то / действует на множестве из двух #-орбит длины 5 па .15 максимальных кликах в [а], противоречие. Если g типа (г г г), то / действует на g-орбите длимы 5 на 15 максимальных кликах в [а], противоречие. Если g типа (iv), то / действует на пятнадцати 5-кликах из [Ь] — К для b Є К—{а}. Поэтому / фиксирует некоторую 5-клику из [Ь]—К, противоречие с тем, что Fix(g) = а1. Утверждение (3) доказано.
Характеры конечных групп и автоморфизмы дистанционно регулярных графов
Доказательство теоремы G опирается на метод Хигмепа. При этом графу Г отвечает симметричная схема отношений (Х,Т1) с d классами, где X — множество вершин графа, RQ отношение равенства на X и для г 1 класс Щ состоит из пар (u,w) таких, что d(u,w) = і. Для мЄГ положим кі = ГІ(И), v = Г. Классу Щ отвечает граф Г,- на множестве вершин X, в котором вершины u,w смежны, если (u,w) Є Ri- Пусть А{ — матрица смежности графа ТІ для і ОиАо = І — единичная матрица. Тогда A(Aj = T.p\jAi для подходящих неотрицательных целых p[j.
Пусть Pi — матрица, в которой на месте (j,l) стоит р\.у Тогда собственные значения pi(0), ...,pi(d) матрицы Pi являются собственными значениями графа Г кратностей mo = 1, ...,m /. Заметим, что матрица Pj является значением некоторого рационального многочлена от Pi, поэтому упорядочение собственных значений матрицы Pi задает порядок па множестве собственных значений матрицы Pj. Матрицы Р и Q, у которых на месте (г, j) стоят стоят Pj(i) и qj(i) = rnjPi{j)/rii соответственно, называются первой и второй матрицей собственных значений схемы и связаны равенством PQ = QP = \Х\1, где I — единичная матрица порядка t/+ 1.
Предложение 4 Пусть щ и Wj — левый и правый собственные векторы, матрицы Pi, отвечающие собственному значениюpi(j) и имеюш/ас первую координату 1. Тогда кратность щ собственного значенияpi(j) равна n/(Uj,Wj). Доказательство. См. теорему 17.12 из [21].
Фактически, из доказательства теоремы 17.12 следует, что Wj являются столбцами матрицы Р и nrtjUj являются строками матрицы Q.
Подстановочное представление группы G = Аиі(Г) на вершинах графа Г обычным образом дает матричное представление ф группы G в GL(n, С). Пространство С" является ортогональной прямой суммой собственных G-инвариантных подпространств И Ф-.-ФИ матрицы смежности А\ графа Г. Для любого д Є G матрица ф(д) перестановочна с А\, поэтому подпространство Wi является (С)-иивариаитиым. Пусть Хг характер представления ф\уг Тогда (см. 3.7 (20]) для д Є G получим Xi{g) = n lT.j=oQijaj(9) гДе aj(g) — число точек х из X таких, что (x,x J) Є Щ. Заметим, что значения характеров являются целыми алгебраическими числами, и если правая часть выражения для Хі{о) число рациональное, то XiWl " целое число.
Поэтому Х2(д) = 1/ЩЬ0а0{д)-2Баі(д)/4-25а2(д)/4+5аі{д)) и Х2(д) = (40а0(#) - Ьаі(д) - Ъа2(д) + 4a3(tf))/108. Подставляя а\(д) + а2{д) = 135 -«оМ - «зЫ, получим хгЫ = {Ьа0(д) + а3(д))/12 - 25/4.
Далее, хз{д) = 1/135(30а0( 7) - 15аі(д) + 30а2(д)/7-15а3(д)/7). Подставляя ац(д) = 135 - а0(д) - а2{д) - а3( 7), получим х3( 7) = (7ао( г) + За2(#) + 2a3b))/21 - 15.
Лемма 3.2.3 Пусть д — автоморфизм простого порядка р графа Г, Fix(g) — пустой граф) и j — число (д)-орбит, являющихся кликами в графе Гз. Тогда выполняется одно из утверждений: (1) р = 5 и либо (г) 7 = 3, Г имеет 24 пятиугольные (д)-орбиты, и число орбит, в которых вершина смеоіспа с се образом под действием д, равно 17,12 или 7, либо (и) Г имеет 17 пятиугольных (д) -орбит и число орбит, в которых вершина смеоіспа с ее образом под действием д, равно 12 или Ъ, либо (НІ) Г имеет 10 пятиугольных (д)-орбит и число орбит, в которых вершина смеоіспа с ее образом иод действием д, равно Ъ, либо (iv) Г имеет 9 пятиугольных (д)-орбит и число орбит, в гсоторых вершина смеоісиа с се образом под действием д, равно 8 или 1, либо (v) Г имеет 2 пятиугольные {д)-орбиты и число орбит, в которых вершина смеоіспа с се образом под действием д, равно 1; (2) р = 3, (а2(д), а3(д)) = (24,111) или (108,27).
Доказательство. Так как 135 = 5-27, тор = 3 или 5. Из целочислениости Хі(д) следует, что аз{д)/3 — 1 делится па 4 и &з(д) = 12s + 3 для некоторого неотрицательного целого числа s. Из целочислениости Хз(#) следует, что &2{д) + 2аз(#)/3 делится на 7.
Пусть р = 5. Тогда az(g) = 15 или 75. Если а (д) = 15, то одЫ + Ю делится на 7 и 0:2((7) = 25,60 или 95. Если а (д) = 75, тогда 0.2(g) + 50 делиться на 7 и 01.2(g) = 20 или 55. Теперь тройка (оц(д), 0.2(g), 02(g)) совпадает с (95,25,15), (60,60,15), (25,95,15), (40,20,75) или (5,55,75).
Если вершина и смежна с и9, то v№ — пятиугольник и d(u, u!J ) = 2. Если d(u, и9) = 3, то в графе Гз орбита и является пятиугольником или кликой. Пусть 7 — число кликовых (р)-орбит в графе Гз- Тогда а2(д2)—о\(д)—(о3(д)— 7) — число (д)-орбит, в которых вершины попарно находятся на расстоянии 2 в графе Г. Ясно, что указанное число совпадает с «2 (д) — щ (д2) — (о (д2)—7)
Если о\(д) = 95, то агО?2) = 95, 7 — 3 и Г имеет 24 пятиугольные (д)-орбиты. Если cvi(g) = 60, то 02(д2) = 60 или 95. В первом случае у = 3 и Г имеет 24 пятиугольные (д)-орбиты. Во втором случае Г имеет 17 пятиугольных (д)-орбит.
