Содержание к диссертации
Введение
1 Хорошие пары в реберно регулярных графах 11
2 Об автоморфизмах сильно регулярных графов с Л = 0 и /^ = 2 37
2.1 Об автоморфизмах графа с параметрами (352,26,0,2) 42
2.2 Об автоморфизмах графа с параметрами (704,37,0,2) 49
3 Об автоморфизмах графа с параметрами (1600,205,0,30) 53
Литература
- Хорошие пары в реберно регулярных графах
- Об автоморфизмах графа с параметрами (352,26,0,2)
- Об автоморфизмах графа с параметрами (704,37,0,2)
Введение к работе
Мы рассматриваем неориентированные графы без петель и кратных ребер. Если а,Ь — вершины графа Г, то через d(o, 6) обозначим расстояние между а и 6, а через Ti(a) — подграф, индуцированный Г на множестве всех вершин графа Г, которые находятся на расстоянии і от вершины а. Подграф Г і (а) будем называть окрестностью вершины а и обозначать через [о]. Через а1 обозначим подграф, индуцированный {a} U [а].
Степенью вершины называется число вершин в ее окрестности. Граф Г называется регулярным степени к, если степень любой вершины а графа Г равна к. Число вершин в [а] П [6] обозначим через Л(а, Ъ) (/і(а,6)), если d[a,b) = 1 (d(a,b) = 2), а соответствующий подграф назовем (д-) А-подграфом. Граф Г назовем реберно регулярным с параметрами (г>, к, А), если он содержит v вершин, регулярен степени /с, и каждое его ребро аЪ лежит в А треугольниках. Граф Г — вполне регулярный граф с параметрами (v, к, A, fj), если он реберно регулярен с соответствующими параметрами и [а] П [6] содержит ц вершин для любых двух вершин а, &, находящихся на расстоянии 2 в Г. Вполне регулярный граф называется сильно регулярным графом, если он имеет диаметр 2.
Через і^тг,...,т„ обозначим полный 7г-дольный граф, с долями порядков ті, ..., тп. Если mj = .. . = тп = т, то соответствующий граф обозначается через Кпхт. Треугольным графом Т(т) называется граф с множеством неупорядоченных пар из X в качестве вершин, \Х\ — т и пары {а, &}, {с, d} смежны тогда и только тогда, когда они имеют общий элемент. Граф на множестве вершин X х У называется т X п решеткой^ если \Х\ = тп, \Y\ = п и вершины (жі,уі), (х2,У2) смежны тогда и только тогда, когда Xi — x
В связи с завершением классификации конечных простых групп возникла задача единого представления конечных простых групп. Перспективным направлением является поиск такого класса конечных геометрий, что каждая конечная простая группа действует флаг-транзитивно на некоторой геометрии и все геометрии этого класса допускают классификацию [15—18. 20, 31, 32]. Например, класс билдингов Титса характеризует группы Лиевского типа [36]. Позднее в этом направлении возникли задачи, не связанные с групповым действием, в частности, такой является задача классификации дистанционно регулярных графов [1,15].
Пусть G — транзитивная группа подстановок на множестве Q. Если подгруппа Gp группы G, состоящая из всех подстановок, фиксирующих точку р є П, имеет г орбит, то говорят, что G является группой ранга г. Пусть г — 3 и соответствующие 3 орбиты — это {р}у Д(р),Г(р). Тогда по группе G удается построить сильно регулярный граф Г, множество вершин которого — Г и две вершины р, q смежны в Г, если р Є A(q) [14].
Д.Хигмэн [24 — 30] развил теорию групп ранга 3. Эти группы являются группами автоморфизмов сильно регулярных графов, причем они действуют транзитивно как на множестве вершин и ребер, так и на множестве пар различных несмежных вершин. Такие графы являются дистанционно транзитивными графами диаметра 2.
Граф Г диаметра d называется дистанционно транзитивным, если для любого г Є {0,.-., d} и для любых вершин u,v,x,y, таких что d(u, v) = d{x, у) — ї, существует автоморфизм д графа Г : {u,v)9 = (х,у). Дистанционно транзитивные графы диаметра 2 (графы ранга 3) сыграли важную роль в классификации конечных простых групп. Около половины спорадических групп были построены как группы автоморфизмов графов ранга 3 [31].
Если вершины и, w находятся на расстоянии і в Г, то через 6j(u, w) (че- рєз Ci(u,w)) обозначим число вершин в пересечении Г(+і(п) (в пересечении Ґі-і('Ц)) с [«>]. Дистанционно регулярным графом называется граф, в котором параметры Ьі{щги) и Ci(u, w) не зависят от вершин к, w, а зависят только от расстояния на котором эти вершины находятся в графе Г.
Поскольку каждый дистанционно регулярный граф является вполне регулярным графом (в частности, реберно регулярным графом), то некоторые результаты об этих классах графов могут быть использованы в теории дистанционно регулярных графов.
В диссертации исследуются строение реберно регулярных графов с к > З&і — 1 и возможные автоморфизмы некоторых сильно регулярных графов.
Результаты работы докладывались на Международной алгебраической конференции, посвященной 70-летию А.И.Старостина и 80-летию Н.Ф.Сесекина, на Международной алгебраической конференции, посвященной 250-летию Московского госуниверситета, на 34-й и 36-й Региональных молодежных конференциях ИММ УрО РАН, на алгебраических семинарах Института математики и механики УрО РАН.
Диссертация состоит из введения, трех глав и списка литературы (43 наименования).
Во введении обсуждается история вопроса, даются определения и формулируются основные результаты работы. В главе 1 рассматриваются реберно регулярные графы. Пусть Г — реберно регулярный граф с параметрами (v, к, Л). Тогда (см. лемму 1.1.1) степень вершины в любом /х-подграфе из Г не больше к — 2Ь\. Поэтому для /і* = к — 2Ь\ + 1 и любых вершин и, w, находящихся на расстоянии 2, выполняется неравенство fj,(u,w) > /z*. Пару вершин, находящихся на расстоянии 2. [и, w) назовем хорошей, если ц(и, га) = ^».
В лемме 1.4.2 из [15] доказано, что если Г — неполный связный реберно регулярный граф с параметрами (v, fc, А) в котором А > 2к/3 — 1, (эквивалентно к > ЗЬі), то Г имеет диаметр 2, v < 2к — 2 и выполняется неравенство kbi> (v~k- l)(fc + 1 - 2bi) (*).
В работе [37] доказано, что если к > З&і — 1, либо для любой вершины и не более двух вершин из Г2(и) образуют хорошие пары с и, либо к = 3&i — 1 и Г является графом икосаэдра. Для числа веришн в реберно регулярном графе диаметра 2 с к > 361 — 1 существенно уточняется неравенство (*). Установлено, что реберно регулярный граф с параметрами треугольного графа Т(тг),п = 5,6, графа Клебша или графа Шлефли совпадает с соответствующим сильно регулярным графом.
В первой главе изучено расположение хороших пар в реберно регулярных графах при к > З&і — 1,
Следующий результат является основным в главе 1.
Теорема 1.1. Пусть Г связный реберно регулярный граф с параметрами (г>, к,Х) и и Є Г. Тогда выполняются следующие утверждения: если к > 4Ьі — 1, то Г не содержит хороших пар; если к > 3&1 — 1, то либо к = ЗЬх — 1, Г является многоугольником или графом икосаэдра и любые две вершины, находящиеся на расстоянии 2, образуют хорошие пары, либо р,(и, W{) — pi* для не более чем двух вершин wi из Г2(и)._
Во второй главе работы выясняются возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярных графов с (А, р) — (0,2). Подграфы неподвижных точек автоморфизмов сильно регулярного графа с малыми значениями параметров Аид имеют жестко заданное строение. Так подграф неподвижных точек автоморфизма графа Мура сам является графом Мура или звездой (см. лемму 1 [11]). Хорошо известно (предложение 1.1.2 [15]), что сильный граф с р > 2 сильно регулярен. Поэтому непустые подграфы неподвижных точек 2'-автоморфизмов сильно регулярного графа с max{A, fi} < 2 сильно регулярны с этими же параметрами или являются кликами.
Во введении главы 2 приведены вспомогательные леммы и изложен метод Г.Хигмэна работы с автоморфизмами сильно регулярных графов [21]. В первом параграфе теоретико-графовыми методами выясняются возможные порядки и строение подграфов неподвижных точек автоморфизмов графа с параметрами (352,26,0,2). Затем с помощью теории характеров конечных групп полученные результаты существенно уточняются. Автоморфизмы этого графа изучались в [40,41]. Во втором параграфе указанной главы с помощью теории характеров конечных групп выяснены возможные порядки и строение подграфов неподвижных точек автоморфизмов графа Г с параметрами (704,37,0,2). Автоморфизмы этого графа изучались в [43].
В третьей главе диссертации с применением аналогичных методов главы 2 выяснены возможные порядки и строение подграфов неподвижных точек автоморфизмов графа Крейна с параметрами (1600, 205,0,30). Автоморфизмы этого графа изучались в [42].
Доказательство теорем второй и третьей главы опирается на метод Г. Хиг-мэна работы с автоморфизмами сильно регулярного графа, изложенный в третьей главе монографии Камерона [21]. При этом сильно регулярный граф Г на v вершинах с собственными значениями к, г, s рассматривается как симметричная схема отношений (X, {Rq, Лі, -})} где X — множество вершин графа Г, Rq — отношение равенства на вершинах графа Г, Ri — отношение смежности в Г и J?2 — отношение смежности в дополнительном графе Г.
Если Р и Q — первая и вторая матрицы собственных значений схемы, то / 1 1 1 \
Р = к г s , ^v — к — 1 —г — 1 — s — 1 j и PQ — QP = vl. При этом кратности l,f,g собственных значений k,r,s графа Г образуют первый столбец матрицы Q.
Подстановочное представление группы G — Aut(r) на вершинах графа Г обычным образом дает матричное представление ф группы G в GL(v,G).
Пространство Cv является ортогональной прямой суммой собственных ^(G)-инвариантных подпространств Wq ф W\ ф W2 матрицы смежности графа Г. Пусть Xi — характер представления фцг Тогда для любого д Є G получим Xi{g) = v~l lLQvaj{9), 3=0 где ai(g) — число точек х из X таких, что (я, х9) Є Щ. Заметим, что значения характеров являются целыми алгебраическими числами, а правая часть данной формулы — число рациональное, поэтому Хг{д) является целым числом.
Основными результатами второй главы являются следующие 2 теоремы.
Теорема 2.3. Пусть Г является сильно регулярным графом с параметрами (352,26,0,2), G — Аи1(Г), д — элемент простого порядка р из G и Д — Fix(g), Тогда выполняется одно из следующих утверждений; р — 2 и либо А — пустой граф, 14-коклика или связный граф степени 6 на 32 вершинах, либо Д имеет четыре связные компоненты, являющиеся четырехугольниками; р = 5 и Д — двухвершинная клика; р = 11 и Д — пустой граф; р = 13 и Д является одновершинным графом.
Из теоремы 2.3 следует, что порядок группы автоморфизмов G графа Г с параметрами (352,26,0,2) делит 21 52 11 -13. В частности, G — разрешимая группа.
Теорема 2.4. Пусть Г — сильно регулярный граф с параметрами (704, 37, 0, 2), G = Aut(r), g — элемент простого порядка р из G и О, = Fix(g). Тогда выполняется одно из следующих утверждений: (1) р = 2 и Q — либо пустой граф, либо объединение 10 изолированных ребер, либо вполне регулярный граф степени 5 на 32 вершинах, либо вполне регулярный граф степени 7 па 44 вершинах; р — 5 или 7 и Q является четырехугольником; р = 11 иП — пустой граф; р = 37 u Q — одновершинный граф.
Из теоремы следует что порядок группы автоморфизмов G графа Г с параметрами (704, 37,0, 2) делит 2' 5- 7-11 37. В частности, G — разрешимая группа.
В третьей главе диссертации выясняются возможные порядки автоморфизмов сильно регулярного графа Крейна без треугольников с параметрами (1600,205,0,30).
Пусть сильно регулярный граф Г с параметрами (и, к, А, //) имеет собственные значения fc, г, s. Если графы Г и Г связны, то выполняются неравенства, называемые условиями Крейна: (г + 1)(А + г + 2rs) <{к + r)(s + I)2 и (5 + 1)(к + s + 2rs) <(к + s)(r 4- I)2.
Граф Г назовем графом Крейна, если для него достигается равенство в одном из условий Крейна (1) или (2). По теореме 8.15 [22] для любой вершины а графа Крейна Г подграфы [а] и Гг(а) сильно регулярны. Ввиду предложения 8.12 и теоремы 8.8 [22] граф Крейна без треугольников имеет параметры ((r2~t-3r)2,r3H-3r2+r, 0,r2+r) и неглавные собственные значения г, — (г2+2г). Граф с такими параметрами обозначим Кге{т). Пусть Г = Кге(г). Для любых смежных вершин а, 6 Є Г подграфы Г2(а) и Г2(а) П Г2(Ь) сильно регулярны с параметрами ((г2 + 2т — 1)(г2 + 3r + 1),J"3 + 2г2,0,г2) и ((г2 + 2г)(г2 + 2г — 1), г3 + г2 — г, 0,г2 — г) и имеют неглавные собственные значения г> ~[г2-\-г] и г, —г2 соответственно. Ввиду теоремы 8.8 [22] сильно регулярный граф без треугольников Г имеет параметры ((г2 + Зг)2, г3 + Зг2 + г, 0, г2 -+- г) для некоторого г > 2 тогда и только тогда, когда любая 3-коклика из Г попадает в окрестности одного и того же числа вершин (а именно, числа г).
Известно, что в случаях г = 1 и 2 существуют единственные графы с такими параметрами — граф Клебша и граф Хигмэна-Симса соответственно. Несуществование КУе(З) доказано в [4]. Вопрос о существовании ТОе(4) и Кте{Ъ) остается открытым.
Основным результатом главы 3 является:
Теорема 3.1. Пусть Г — граф Крейна Кте{Ъ), G — Aut(r). Если д — элемент нечетного простого порядка р из G, О, = Fix(g), то верно одно из утверждений: Q — пустой граф и р = 5; либо О, — одновершинный граф и р = 41, либо Q является 2-кликой и р = 17;
П является графом /Сд,8 с удаленным максимальным паро сочетанием и р = 3.
Хорошие пары в реберно регулярных графах
Доказательство. Пусть 7 = \[и] П [го] П[г]\ и p,q - различные вершины из [и] П [го] П [z]. Тогда [р] содержит Ъ\ — 2 вершин из ([z] П [го]) — [и], причем \([z] П [го]) [и}\ — А — 7- Отсюда [р] П [q] содержит u,w,z, у — 2 вершин из [и] П [го] П [г], по ji — 7 вершин из ([и] П [го]) — [г] и из {[и] Г) [z]) [го] и не менее 2{Ь\ — 2) - (А — 7) вершин из {[z] П [го]) — [и]. Поэтому \\р] П [д] 3+(7-2) + 2(р -7) + (2 - 4 - А + 7), т.е. 2р - 3 + 26х 2А. Противоречие с тем, что /і, = А + 2 — Ьі.
Лемма 1.1.3. Пусть Г -реберно регулярный граф с р(и, го) = р+, p(u, г) — /и + 1 для смежных вершин ш, z из Г2(и), 7 — \[и] П [to] П [z]. Тогда выполняются следующие утверждения: (1) 7 2; (2) еош 7 = 1, d Є [и] Л [го] П [z], то к ЗЬ\ — 1 и е случае равенства d не смежна с единственной вершиной из {[и] П [г]) — [го] и из [d\ — и1 С [го] П [г].
Доказательство. Пусть 7 = ІМ П [го] П [г]] и р,q - различные вершины из [и] П [го] П [г]. Если [р] содержит а вершин из [го] — ([и] U [г]), то по лемме 1.1.1 [р] содержит д — 7 + а вершин из ([г] П [и]) — [го] и &i — 2 — а вершин из ([z]П[го]) — [и], причем (ИП[го]) — [и]\ = А—7- Отсюда [р]Л[д] содержит и, го, г, /І — 2 вершин из [и]П[го]П[г], 2(р -7 2) — (р — 2 -7 + I + А — 7) вершин из (Mn[z]-[to])U(Hn[z]-[u]). Поэтому [р]Л[д] 3+( -2) + ( +26 5-А), т.е. 2ц — 4 + 2oi 2А. Так как р = А + 2 — &і, то нестрогое неравенство превращается в равенство, поэтому каждая вершина из [го] — [и] смежна не более чем с одной вершиной из [и] П [го] Л [г] и [го] Л [г] С [ж] U [у] для любых различных вершин х,у из [и] П [w] П [z].
Так как р не смежна по крайней мере с А — у b\ + 2 вершинами из [w] П [z], то ч(Л - 7 - Ьг + 2) А - 7- Отсюда 72 - 70 + 3 - h) + А 0. Заметим, что (А — b\ + З)2 - 2А (А + 4 - Ъ\)2 при 6i 4, и в этом случае 7 А — &1 + 3 — /л + 1, противоречие.
Пусть Ь\ = 3. Тогда 72-7Л + 0и = + 1 4. Так как 7 2, то 3 & —4 4ипо предложению 2 [6] граф Г сильно регулярен, противоречие.
Если Ьх = 2. Тогда 72 - т(Л + 1) + А 0 и А = 1. Отсюда к = 4 и /л = 1. противоречие. Наконец, если &i — 1, то Г - многоугольник или полный многодольный граф Ких2 и условия леммы нарушаются. Утверждение (1) доказано.
Пусть 7 = 1, d Є [и] П [w] П [z]. Тогда [d] содержит /u — 1 вершин из [и] П [ги] и либо /І — 1, либо /І вершин из [и] Г\[г]. В последнем случае А 2/І — 1 И к 3&1 — 2. Если fc = 3&1 — 1, то d не смежна с единственной вершиной из {[и] П [z]) — [w] и [d] — и1- С [ги] П [г]. Утверждение (2) доказано.
Сильно регулярные графы с собственным значением -2 были классифицированы Зейделем в [15]. Любой Зейделев граф — это либо полный много-дольный граф КГХ2, либо решетчатый или треугольный граф, либо один из графов Шрйкханде, Чанга, Петерсена, Клебша или Шлефли.
Лемма 1.1.4. Если Г - сильно регулярный граф, имеющий целочисленные собственные значения, Ь\ — к — А — 1. Тогда (1) если Ь\ - простое число, то Г является полным многодольным графом Кгх(Ьі+і) или зейделевым графом; (2) если Ь\ = 2р,р - простое число, то Г является полным многодолъ-ным графом, либо имеет собственные значения —2 или —3, либо является дополнительным к зейделеву графу; (3) если &i — 4, то Г является полным многодельным графом Kryi , 5x5-решеткой, треугольным графом Т(7) или дополнительным графом к 4 X А-решетке, треугольному графу Т(6) или графу Клебша (заметим, что в половинном случае параметры графа равны (17,8, 3,4) и он является графом Пэли).
Доказательство. Пусть — т - наименьшее собственное значение графа. Если m — 1, то Г состоит из изолированных клик. Но в этом случае Ь\ — 0. Пусть т - целое число, большее 1. Тогда по лемме 3.1 из [6] т — 1 делит Ь\.
Если bi - простое число, то либо т—\ = 1, либо т — 1 = Ьь Но в последнем случае Г является полным многодольным графом Кгх 1+1у Утверждение (1) доказано.
Пусть Ь\ = 2р,р - простое число и Г не является полным многодольным или зейделевым графом. Тогда либо т—1 = 2, либо т—\ = р. Но в последнем случае по лемме 1.4.3 из [15] п — т = 1 и Г является дополнительным к зейделеву графу. Утвержение (2) доказано.
Наконец, если Ь\ = 4, то ввиду утверждения (2) Г является полным многодольным графом /Сгх5, зейделевым графом или дополнительным кзейделеву графу. Среди зейделевых графов Ъ\ — 4 имеют только 5 х 5-решетка или треугольны граф Т{1). Аналогично, среди дополнительных к зейделевым графам Ь\ = 4 имеют дополнительны граф к 4 х 4-решетке, треугольному графу Т(6) или графу Клебша. Утверждение (3) доказано. Лемма 1,1.5. Если Г - реберно регулярный граф с к 4bj — 1, то Г не содержит хороших пар.
Доказательство. Пусть fi(u,w) = // , Х{ множество всех вершин из ([и] U [w]) — ([и] П [w]), смежных точно с і вершинами из [и] П [w], ХІ = \Х{\. Подсчитав число ребер между [и] Г) [w] и ([u] U [w]) ([и] П [w]), а также число треугольников с основанием в [и] П [w] и вершиной в ([и] U [w]) — {[и] П [и ]), получим равенства Еж = 4Ьі - 2, Ггж; = fi (2bi - 2) и Е (5) = ft )( 2) ОтсюдаО ЕХІ(І-/3)2 = р {ц -1)(Ьі 2)-{20-1) (21 -2) + ( -2)02. Поэтому (4Ьі - 2)/32 - 4jLi (6i - 1)/3 + (м (&1 -2)- /І«.ЬІ) 0, дискриминант
Об автоморфизмах графа с параметрами (352,26,0,2)
Пусть вершины го,,г не смежны. Тогда подграф [d\ П [г] содержит и, oi - 2 вершин из [и] и &i — 1 вершин из [го] П [z]. Далее, [d\ Г) [z] содержит единственную вершину t из [и] и точно Ь\ — 1 вершин из [го] П [г], поэтому (d, z) - хорошая пара. Симметрично, (і, го) - хорошая пара, в частности, о не смежна с вершинами из [d] П [w] П [z].
Так как (к, ж) - хорошая пара, то [ж ] не пересекает [и] П [ж], поэтому [я ] - ш-1- содержит 2, о и 6i — 2 вершин из [и] П [г]. Таким образом, [ж ] содержит ш, г, о, по Ъ\ — 2 вершин из [и] П [гу], [и] П [z] и &i вершин из [w] П [г].
Пусть а - отличная от ж вершина из [d]fl[iy] Л[г] и [а] содержит /3+2 вершин из [и] П [я]. Тогда [а] содержит по bi - /3 вершин из [и] П [гу], [м] П [z], поэтому [а] — жх содержит точно 2Ъ\ — 2/3 — 2 вершин из [и] и быть может вершину ж . По лемме 1.1.16 Ь\ нечетно, поэтому а смежна с ж и /3 = (b\ — 1)/2. Значит, [ж ] — о1- содержит гу, z и Ь\ — 2 вершин из [d] П [w] П [z]. Поэтому [о] — (х )х содержит и, Ь\ — 3 вершин из [гу] П [г] и 2 вершины из [и]. Итак, либо (о, ж) -хорошая пара, либо [о] П [и] содержит точно 2 вершины из [х]. Если (о, ж) -хорошая пара, то для вершины с из [гі]П[ж]П[о] подграф [c]n[d] содержит и, х, &1 — 2 вершин из [и] П [ж] и Ь\ — 2 вершин из [и] П [гу]. Но в этом случае [и] П [с] содержит 36i — 5 вершин и Ь\ — 3, противоречие. Пусть {р, д} = [и] П [ж] П [о]. Тогда [р] содержит по крайней мере Ъ\ — 2 вершин из [о] П [гу] П [z]. Поэтому подграф [р] П [d] содержит и, Ь\ — 2 вершин из [и] П [ж], не более 2 вершин из [го] П [z] и не менее 6i — 3 вершин из [it] П [w]. Но в этом случае [р] П [ ?] содержит я, ж и не менее ЗЬі — 7 вершин из [и]. Противоречие с тем, что тогда Зої — 5 2b\ — 2 и Ьі 3. Лемма доказана.
По лемме 1.1.19 подграф {ш, ж, z] является кликой. Для у Є {ш, ж, z] через у обозначим единственную вершину из Г2(г ), не смежную с у. Положим Д = Ti{u) - {w,w ,x,x ,z,z }. Лемма 1.1.20. Выполняются следующие утверждения: (1) &i = 7, к = 20, А = 12, v = 36, подграф {w , ж , г } является кликой и содержится в [р] П [q], р смежна с 4 вершинами из А; (2) [d] содержит гу, х и 5 вершин из A, [] П [d] содержит 4 вершины из А и число ребер между [и] П [ж] гі Д равно 32; (3) [гу ] содержит по 4 вершины из [и] Г) [ж], [и] П [г] «6 вершин из А, [w ] П [z ] содержит либо 3 вершины из [и] П [х] и 5 вершин из Д, либо по 4 вершины из [и] П [ж], Д.
Доказательство. Допустим, что вершина z не смежна с р. Тогда [z ] w1-содержит w , q и b\ — 2 вершин из ([и] П [ж]) — {d, г}. Симметрично, [гг ] — хЛ содержит х , g и &i — 2 вершин из ([и] П [ш]) — {d, г}. Если же z смежна с р, д, то [г 1] содержит не менее 2Ь\ — 3 вершин в каждом из подграфов [и] — [w], [и] — [х]. В любом случае р,(и, z ) 2fei 4. С другой стороны, /і(г, г ) &і+3, а по утверждению (4) леммы 1.1.1 д(и, г ) = /2(2, z ). Так как по лемме 1.1.16 Ъ\ 7, то Ь\ — 7, вышеуказанные нестрогие неравенства превращаются в равенства, z не смежна с d и выполняется утверждение (1).
Теперь подграф [d\ — х1- содержит и и Ь\ — 1 вершин из [и] П [ги], поэтому [d] — их содержит ш, г и 6i — 2 = 5 вершин из Д. Далее, [d] П [t] содержит и, г, х, bi — 2 вершин из [и] П [ж] и 6i — 3 = 4 вершин из Д.
Подграф [w ] содержит по 4 вершины из [и] П [ж], [w] П [г] и 6 вершин из Д. Если [го ] П [г ] содержит 6 вершин из [и], то одна вершина из [гі] П [х] — {t, d} смежна с 6 вершинами из Д, а каждая из четырех оставшихся - с 4. Если же [w ] П [г ] содержит 5 вершин из [и], то две вершины из [и] П [ж] — {, d} смежны с 5 вершинами из Д, а каждая из трех оставшихся - с 3. В любом случае число ребер между [и] П [ж] — {, d} и Д равно 22.
Лемма 1.1.21. Подграф Д содержит три вершины, смежные с d,t,r и по одной вершине, смежной с парами вершин из {d,t,r}.
Доказательство. Подграф Д содержит либо три вершины, смежные с d,t,r и но одной вершине, смежной с парами вершин из {d,t, г}, либо четыре вершины, смежные с d, t,r и по одной вершине, смежной с единственной вершиной из {d,t,r}.
Допустим, что выполняется последняя возможность. Тогда Д — До U {J\ff h} U {01,02}, где До С [d] П [t] П [г], а вершины f,g,h смежны с d,t,r соответственно. Подграф [d] П [z] содержит x,w,t,r и пять вершин из А, причем Ad,z — {p,q, z }. Так как вершина / не смежна с t,r, то степень / в графе [d\ П [z] равна б, [/] содержит AQ и не пересекает {р, q, z }. Симметрично, [д] содержит Д0 и не пересекает {р, q, ги }, [h] содержит До и не пересекает {р, q, ж }. Таким образом, {w,x,z,d,t,r, f,g,h} С ЛР;9, поэтому вершины р, q не смежны и р(р,я) 15. Заметим, что для любой вершины у из До подграф [у] — ([p]U[g]) содержит iv,x,z,d,t,r, f,g,h, поэтому р, q не смежны с у. Противоречие с тем, что \\р] П Д = 4. Лемма доказана.
Ввиду леммы 1.1.21 можно считать, что А = Д0 U {/, #, h} U {01,02,03}, где До С [d] П [t] С\[г], а вершины f,g и h смежны с парами d,t, d,r и , г соответственно. Лемма 1.1.22 Выполняются следующие утверждения: (1) \р] П [q] не пересекает AQ U {/, g: К}; (2) До С Ap,q.
Доказательство. Заметим, что [ 2] П [z] = {x,w,t,r, /, ?} U До и AJJZ = {г ,р, /}. Если / Є [р]П[ г], то степень / в графе [d]n[z] равна 8, противоречие с тем, что / не смежна с г. Значит, / смежна не более чем с одной вершиной из {z ,p,q}.
Пусть вершина у из До смежна с р, q. Тогда [d\ Л [z] С и вершины у, z не смежны. Симметрично, х ,и не смежны сі/, а [у] содержит f,g,h. Так как каждая из вершин /, g, h смежна не более чем с одной вершиной из {р, д}, то можно считать, что f,g не смежны с р. Противоречие с тем, что [у] — рх содержит 8 вершин w, х, z} d, t, г, f, д. Утверждение (1) доказано.
Об автоморфизмах графа с параметрами (704,37,0,2)
Пусть в данном параграфе Г — сильно регулярный граф с параметрами (704,37,0,2). Теорема 2.4. Пусть Г — сильно регулярный граф с параметрами (704, 37, 0, 2), G — Aut(r), д — элемент простого порядка р из G uQ, Fix(tr). Тогда выполняется одно из следующих утверждений: (1) р — 2 и Q — либо пустой граф, либо объединение 10 изолированных ребер, либо вполне регулярный граф степени 5 на 32 вершинах, либо вполне регулярный граф степени 7 на 44 вершинах; (2) р = 5 или 7 и Q, является четырехугольником; (3) р = 11 и Q — пустой граф; (4) р = 37 и ГЇ — одновершинный граф. Из теоремы следует что порядок группы автоморфизмов G графа Г с параметрами (704,37, 0,2) делит 21 5 7 11 37. В частности, G — разрешимая группа.
Пусть Г — сильно регулярный граф с параметрами (704, 37,0,2), имеющий собственные значения к — 37, г = 5, s = — 7, О, — регулярный подграф графа Г степени к на и вершинах. Тогда по лемме 2.1.1 получим 22АУ — 110 и 1бк + 112. Причем если в одном из этих нестрогих неравенств достигается равенство, то каждая вершина из Г — fi смежна точно с и(37 — А;7)/(704 — и) вершинами из П.
Если Г — граф с параметрами (704,37,0,2) и G Aut(r). Тогда первая и вторая матрицы собственных значений }
Поэтому значение характера, полученного при проектировании на подпространство размерности 296 равно 5а0{д) -ati{g) +32 хЛо) = Лемма 2.3.1 Пусть ХІ — Х;(Д), х\ 0 и хо ф 0. Тогда для любой вершины и Є XQ имеем \[и]пХ2\ = [Д.
Доказательство. Число 2-путей с началом -и, концом в Д и средней вершиной в Х2 равно 2Д. Так как вершина из [и] П Х2 лежит в двух таких путях, то [и] П Х2\ = 2Д/2 = Д. Предложение 2.5. Пусть Г — сильно регулярный граф с параметрами (704,37,0,2), имеющий инволютивпый автоморфизм t. Тогда для Д — Fix(f), Д ф 0, выполняется одно из следующих утвероюдений: (1) Д является графом степени 1 на 20 вершинах; (2) Д является графом степени 5 на 32 вершинах; (3) Д является графом степени 7 на 44 вершинах.
Доказательство. Ввиду леммы 2.1.2 Д является вполне регулярным графом с параметрами (5,/5,0,2), где 6 = JA). Так как А; = 37, то /5 нечетно. Число ребер между Д и Г — Д равно с5(37 — (3). По лемме 2.1.2, указанное число не больше 2(704 — 5).
Пусть ХІ — множество вершин из Г — Д, смежных точно с г вершинами из Д, хі — \ХІ\. Тогда хо + х\ + хч = 704 — 5 и хі + 2x2 — 5(37 — /3). По лемме 2.1.1 jS 7.
Если /9 = 1, то по лемме 2.1.2 граф Д является объединением 10 изолированных ребер. Тогда хі( ) = (132 — oti(t))/12, и ai(t) кратно 12. В этом случае Х2 360, х0 = 324, xi = 0. По лемме 2.3.1 имеем, что XQ — регулярный граф степени 17 на 324 вершинах. Х2 — регулярный граф степени 17 на 360 вершинах.
Если (3 = 3, то S — 24 и по предложению 1.13.1 [15], Д является объединением трех 3-кубов. В этом случае XQ = 272, х\ = 0, Х2 = 408. По лемме 2.3.1 имеем, что Хо — регулярный граф степени 13 на 272 вершинах. Противоречие с леммой 2.1.1.
Если /3 5, то «5 = 32 и Д является 5-кубом или объединением двух изолированных графов Клебша. Значение характера в этом случае равно Xi( ) = (192-ai(f))/12, иаі(() = 8(12). В этом случае х0 = 160, xl = 0,х2 = 512. По лемме 2.3.1 имеем, что XQ — регулярный граф степени 5 на 160 вершинах. Поэтому Хч — регулярный граф степени 25 на 512 вершинах.
Если /3 = 7, = 44 и Д — граф степени 7 на 44 вершинах. Тогда XQ — х\ 0, 2 = 660. Поэтому Хч — регулярный граф степени 35 на 660 вершинах. Далее, OL\{i) = 0, поэтому значение характера равно XitO — 252/12 = 21.
Предложение 2.6. Пусть Г — сильно регулярний граф с параметрами (704,37,0,2), д — элемент простого нечетного порядка р из Aut(r). Тогда для множества неподвижных точек Q, Fix(p) выполняется одно из следующих утверждений: (1) О, — пустой граф и р= 11; (2) Q — одновершинный граф и р = 37; (3) О, является четырехугольником и р — 5 или 7. Доказательство. Если О — пустой граф, то р = 11, так как v = 26 11.
Еслир = 11, то ао(д) 0 и Хі(я) = (32 — 0:1(5))/12, поэтому а\(д) — lltu. Отсюда w = 12х + 4. Пусть {х, х9} — ребро. Тогда (д)-орбита точки а является 11-угольником или графом степени 4. В последнем случае эта орбита является сильно регулярным графом с параметрами (11,4,0,2), противоречие. Следовательно (з)-орбиты длины 11 являются либо 11-угольниками, либо 11-кокликами. Если О = {а} является одновершинным графом, то д действует без непо движных точек на [а], причем \[а]\ — 37, и на Гз(а), причем Г2(а) = 37 18.
Поэтому р = 37 и 0:0(5) = 1- Число всех орбит длины 37 равно 19. Пусть {х,хв} — ребро. Так как значение характера в этом случае равно Хі(з) = (37 — скі( ?))/12 и Oii(g) = 37u , то w 1 или 13.
Если Q является двухвершинной кликой {а, &}, то [а] — {Ь} = 36, на множестве [а] — {Ь} действует автоморфизм порядка р и р — 3. Значение характера в этом случае равно xi{o) — (42 — aj(g))/l2. Но cvi(p) = 0, поэтому Xi(g) 42/12. Противоречие.
Если fi является четырехугольником {a,b;c,d}, то [z] — Q является 35-кокликой для z Є {a,b,c,d}. Поэтому a Qy) 140, ot\{g) 560 и р — 7 или 5. Если р — 7 или 5, то а$(д) — 4 и XiG?) — (52 — ai(#))/12. Если 0(1(5) = 7s, то s = 12гс 4- 4. Общее число 7-угольных орбит равно f=1 0:1(51) = 12 + 12 и указанное число не больше 72. Если а\(д) — 5гу, то ад = 12г/ + 8. Тогда общее число 5-угольных орбит равно Hf otiig1) = 12 + 16. Поэтому число 5-угольных орбит не больше 112.
Граф П не может быть графом Клебша, так как каждая вершина из Q смежна с 25 вершинами из Г — Г2 и р делит 32. Граф Q не может быть графом Гевиртца, так как в этом случае каждая вершина из Q смежна с 27 вершинами из Г — Q и каждая вершина из Г — Сі смежна не более чем с одной вершиной из Г, противоречие с тем, что тогда 56 - 27 704 — 56. Теорема доказана.
