Содержание к диссертации
Введение
Глава 1. Локально GQ(A, 11)-графы
1.1. Вспомогательные результаты
1.2. Большие гиперовалы в GQ(A, 11)
1.3. Локально GQ(4,11)-графы
Глава 2. Автоморфизмы сильно регулярных графов с параметрами (96,45, 24,18) и (320,99,18,36)
2.1. Сильно регулярный граф с параметрами (96,45,24,18)
2.2. Графы с параметрами (96,45,24,18) и (96,50,22,30) не являются реберно симметричными
2.3. Сильно регулярный граф с параметрами (320,99,18,36)
Глава 3. Дистанционно регулярные графы, в которых окрестности вершин сильно регулярны со вторым собственным значением 3
3.1. Графы, в которых окрестности вершин сильно регулярны с параметрами (111,30, 5,9)
3.2. Графы, в которых окрестности вершин сильно регулярны с параметрами (169,42,5,12)
Глава 4. Автоморфизмы дистанционно регулярного графа с массивом пересечений {169,126,1; 1, 42,169}
4.1. Автоморфизмы графа с параметрами (169,42,5,12)
4.2. Автоморфизмы дистанционно регулярнго графа с массивом пересечений
4.3. Дистанционно регулярный граф с массивом пересечений {169,126,1; 1,42,169}, вершинно симметричный случай
Литература
- Большие гиперовалы в GQ(A, 11)
- Локально GQ(4,11)-графы
- Графы с параметрами (96,45,24,18) и (96,50,22,30) не являются реберно симметричными
- Графы, в которых окрестности вершин сильно регулярны с параметрами (169,42,5,12)
Введение к работе
Актуальность темы. В связи с завершением классификации конечных простых групп возникла задача единого представления конечных простых групп автоморфизмами конечных геометрий. Позднее в этом направлении возникли задачи, не связанные с групповым действием, в частности, такой является задача исследования дистанционно регулярных графов [1].
Система инцидентности, состоящая из точек и прямых, называется а-частичной геометрией порядка (s,t), если каждая прямая содержит ровно s + 1 точку, каждая точка лежит ровно на t + 1 прямой (прямые пересекаются не более, чем по одной точке) и для любой точки а, не лежащей на прямой L, найдется точно а прямых, проходящих через а и пересекающих L (обозначение pGa(s, )). Если а = 1, то геометрия называется обобщенным четырехугольником и обозначается GQ(s, t). Точечным графом частичной геометрии называется граф, вершинами которого являются точки геометрии, и две различные вершины смежны, если они лежат на общей прямой (коллинеарны). Легко понять, что точечный граф частичной геометрии pGa(s,t) сильно регулярен с параметрами: v = (s-\-l)(l-\-st/a), к = s(t-\-l), \ = (s — l) -\-(a — l)t, fi = a(t-\-l). Сильно регулярный граф с такими параметрами для некоторых натуральных чисел a,s,t называется псевдогеометрическим графом для pGa(s,t).
Дж. Кулен предложил задачу изучения дистанционно регулярных графов, в которых окрестности вершин — сильно регулярные графы со вторым собственным значением, не большим t для данного натурального числа t. Заметим, что сильно регулярный граф с нецелым собственным значением является графом в половинном случае, а вполне регулярный граф, в котором окрестности вершин — сильно регулярные графы в половинном случае, либо имеет диаметр 2, либо являеься графом Тэйлора. Таким образом, задача Кул єна может быть решена пошагово для t = 1, 2,....
Задача Кулена решена для t = 1 Кардановой М.Л. и Махневым А.А. в [2] и независимо Куленом. Случай t = 2 изучался более 10 лет и завершен в статье И.Н. Белоусова, А.А. Махнева и М.С. Нировой [3]. Рассмотрение случая t = 3 начато в статье А. А. Махнева [4] (теорема редукции) и А.А. Махнева и Д.В. Падучих [5] (список параметров исключительных графов).
В данной работе рассмотрены некоторые сильно регулярные графы со вторым собственным значением 3 и найдены их автоморфизмы. Кроме того, найдены массивы пересечений дистанционно регулярных графов, в которых окрестности вершин — подходящие сильно регулярные графы со вторым собственным значением 3. Определены возможные порядки и подграфы неподвижных точек автоморфизмов полученных дистанционно регулярных графов.
Граф Г диаметра d называется дистанционно транзитивным, если для любого г Є {0,...,d} и для любых вершин u,w,x,y, таких что d(u,w) = d(x,y) = і, существует автоморфизм g графа Г такой, что (u,w)g = (х,у). Дистанционно транзитивные графы диаметра 2 (графы ранга 3) сыграли важную роль в классификации конечных простых групп. Более половины спорадических групп могут быть представлены как группы автоморфизмов графов ранга 3 [6].
Если вершины u,w находятся на расстоянии г в Г, то через bi(u,w) (через Ci(u,w)) обозначим число вершин в пересечении Гі+1(м) (в пересечении Ті_і(и)) с [w]. Дистанционно регулярным графом с массивом пересечений {Ьо, b\,..., bd-\] С\,..., Са\ называется графдиаметра d, в котором параметры bi = bi(u,w) и q = Ci(u,w) не зависят от вершин u,w, а зависят только от расстояния, на котором эти вершины находятся в графе Г для і Є {0,1,..., d}.
Цель работы. Изучить локально GQ(4,11)-графы, найти автоморфизмы сильно регулярных графов с параметрами (96,45,24,18) и (320,99,18,36), перечислить массивы пересечений дистанционно регулярных графов, в которых окрестности вершин - сильно регулярные графы со вторым собственным значением 3 и параметрами (v', к', 5,//) и найти автоморфизмы возникших графов.
Методы исследований. Основными методами исследования являются теоретико-графовые методы и методы теории конечных групп, в частности, метод Г. Хигмена (см. [7]) приложения теории характеров к выяснению порядков автоморфизмов дистанционно регулярных графов.
Научная новизна. Все основные результаты диссертации являются новыми:
доказано, что сильно регулярный граф с параметрами (96,45,24,18) не является реберно симметричным,
найдены автоморфизмы сильно регулярного графа с параметрами (320,99,18,36),
получено описание вполне регулярных локально GQ(4,11)-графов,
перечислены массивы пересечений дистанционно регулярных графов, в которых окрестности вершин сильно регулярные графы со вторым собственным значением 3 и параметрами (v', A/, 5,//),
найдены автоморфизмы дистанционно регулярного графа с массивом пересечений {169,126,1; 1,42,169}.
Теоретическая и практическая ценность. Работа носит теоретический характер. Ее результаты могут быть использованы в геометрии и теории графов.
Апробация работы. Основные результаты диссертации неоднократно докладывались и обсуждались на алгебраическом семинаре отдела алгебры и топологии ИММ УрО РАН, а также были представлены на следующих конференциях: Теория групп и ее приложения, IX Международная школа-конференция по теории групп, Владикавказ 2012 г., Международная конференция по теории групп, посвященная 70-летию В.Д. Мазурова, Новосибирск 2013 г., Международная конференция "Группы и графы, алгоритмы и автоматы" , посвященная 80-летию В.А. Белоногова и 70-летию В.А. Баранского, Екатеинбург 2015 г.
Публикации. По теме диссертации имеется 8 публикаций [18-25] (четыре статьи опубликованы в журналах из списка ВАК). Из пяти статей две написаны без соавторов, одна - тремя авторами (Кагазежева A.M., Журтов А.Х., Махнев А.А.), две в соавторстве с Махневым А. А. В работе трех авторов Журтов А.Х. и Махнев А. А. улучшали некоторые моменты доказательства, предложенного Кагазежевой A.M. В статьях Кагазежевой A.M. и Махнева А.А. второму автору принадлежат постановки задач и идеи доказательств,
сами доказательства принадлежат Кагазежевой A.M.
Структура и объем работы. Диссертация состоит из введения, 4 глав и списка литературы, содержащего 37 наименований. Общий объем диссертации составляет 87 страниц.
Большие гиперовалы в GQ(A, 11)
Если z Є Xu, то число внешних прямых, проходящих через гине пересекающих XQ, равно 4, причем каждая такая прямая имеет тип (14,16,16,16,18). Итак, Г содержит 60 внешних прямых, 12 из которых имеют тип (0,14,22,22,22) и 48 — тип (14,16,16,16,18). Отсюда Х\д = 16, Х\6 = 36 и 3 = 36.
Пусть имеется г\ секущих типа (16,22,24), Г2 секущих типа (18,22,22) и гз секущих типа (14,24,24). Тогда Г\ = 8жів, Г2 = 9жі8- Число флагов, состоящих из секущей и лежащей на ней точки из Х22 равно ІІЖ22 = Ti+2r2 = 8жіб + 18жі8 = 8 36 + 18 16, противоречие.
Допустим, что XQ = 2 и XQ = {а, Ъ]. Если [a] U [Ь] содержит вершину с из Xis, то с лежит на внешней прямой L, не пересекающей XQ, И L имеет тип (14,16,16,16,18). Противоречие с тем, что Хи С [а] П [Ь]. Значит, [a] U [Ь] не пересекает Xig. Если z Є Хи, то [z] содержит точно 3 вершины из Xig. Каждая вершина из Xig лежит на трех прямых типа (14,16,16,16,18) и мы имеем Кз5 подграф {XU]XQ U Х\$}. ПОЛОЖИМ Хи = {z\, Z2,z%}, Х\$ = {di,d,2,ds}. Тогда на прямых, проходящих через di,Zj, содержатся по три точки из XIQ, всего 27 точек. Каждая из этих точек лежит на трех внешних прямых типа (16,16,16,16,16), причем любая такая прямая содержит не более
3 из указанных точек. Итак, имеется 60 внешних прямых, 24 из которых пересекают XQ, 9 имеют тип (14,16,16,16,18) и 27 — тип (16,16,16,16,16). Теперь каждая прямая типа (16,16,16,16,16) содержит две точки, несмежные с вершинами из Хи, каждая точка, несмежная с вершинами из Хи, лежит на
4 прямых типа (16,16,16,16,16) и число точек из XIQ, несмежных с вершинами из Х14, равно 27 2/4, противоречие. Значит, XQ 3. Допустим, что Ф является і 2,з-подграфом из Ф, содержащим XQ, Yi = ХІ(Ф), yi = \Yi\. По лемме 1.5 получим уо + 2/з = 49. Противо речие с тем, что Л содержит не менее 52 вершин из YQ. Итак, хи 1. Если w Є Х14, то XQ С [W] И ХО = 5. В противном случае w лежит на внешней прямой типа (14,16,16,16,18) и вершина с из Xig П L лежит на трех внешних для Л прямых, две из которых пересекают Хо. Противоречие с тем, что Хо С [w]. Теперь Г содержит 60 внешних прямых, каждая из которых пересекает Хо.
Пусть Zi = Xi(Xo), Zi = \Z{\. По лемме 4 получим 1 = 220, J2iZi = 240 и Е \О)%І = 120. Вычитая второе равенство из суммы первого и третьего, получим ZQ + Е Г 2 )zi = 100- Так как ад Є и о содержит 80 вершин из Л и 14 вершин из [w] П Х24, то ZQ = 94, 2 = Z4 = 0. Поэтому х\в = #18 = 0, противоречие с тем, что вершина из Х24 лежит на 11 секущих, не пересекающих Х14.
Значит, хи = 0. Допустим, что L — прямая типа (16,16,16,16,16). Тогда #18 = 0, Хо 4 и каждая вершина из Хо смежна с единственной точкой на прямой L. Если Г содержит прямую М типа (0,20,20,20,20), то каждая точка из Х20 П М смежна с точкой из Х\ П L и хо 5, противоречие. Итак, Г содержит 12жо прямых, пересекающих Хо, и 60 — 12жо прямых типа (16,16,16,16,16), х2о = 6ж0, х22 = 24ж0, жіб = (12ж0 + 5(60 - 12ж0))/4 = 75 — 12жо и 24 = 70 — 19жо- Отсюда жо = 3,3) = 18,3 = 72, х\6 = 39 и 24 = 13. Как и выше, получим равенства = 222, ЕЇ« = 144 и Е \О)%І = 36. Вычитая второе равенство из суммы первого и третьего, получим z0 + Е ( 1) = 114. Поэтому Xi6 П (Z0 U Z3) = 114 - (80 + 13) = 21. Так как GQ(4,11) не содержит іСз,9-подграфов, то \XIQ П Z%\ 8, поэтому
Допустим, что Хіб П Z% содержит 2 вершины р, д, и положим [/j = Х (Хо U {p,q}): Щ = \Ui\. По лемме 3 получим щ + щ = 49. Противоречие с тем, что Щ содержит не менее 48 вершин из Л и не менее 13 — 2-4 вершин из XIQ ([p] U [q] содержит не более 8 вершин из Хм). Значит, \Хм П Z%\ 1, поэтому \Хм П Zo\ 20. Число 2-путей с концами в XQ равно 36, 18 из этих путей содержат среднюю вершину в Х20 и 18 оставшихся путей содержат среднюю вершину в Хм-, поэтому либо \Хм П Z i\ = 16 и \Хм П Zo\ = 21, либо \Хм П Z3\ = 1, \Хм П Z2 = 13, \Хм П Zi = 5 и 1 П Z0\ = 20. Число флагов, состоящих из прямой типа (16,16,16,16,16) и точки на ней, равно 120. С другой стороны, указанное число флагов равно 4 21 + 2 16 в случае \Хм П Z0\ = 21 и равно 4 20 + 3-5 + 2- 13 + 1 в случае 1 П Z0\ = 20. В любом случае имеем противоречие.
Таким образом, хо = 5 и ZQ + Е ( 2 ) = 100. Если w Е Z% U Z4, то Zo содержит 80 вершин из Л и не менее 8 вершин из [w] П Х24, поэтому 2/3 + 3 /4 12 и Зжіб + #18 12. Так как окрестность вершины из Х24 содержит 12 вершин из Хм U - 18, то хм = 0, Жі8 = 12, противоречие с тем, ЧТО ZQ
Доказательство. Пусть GQ(4,11) содержит гиперовал с /І = 80. По лемме 1.11 имеем хо = 0. Пусть количество внешних прямых типов (14,16,16,16, 18), (16,16,16,16,16) равно 2/1,2/2 соответственно. Так как хо = 0, то 2/1+2/2 = 60. Подсчитаем количество флагов, состоящих из точки в ХІ И внешней прямой для і Є {14,16,18} двумя способами. Получим, соответственно, выражения
Доказательство. По лемме 2 имеем fi{u,w) 45 для любых вершин и,юєГс d(u,w) = 2. Пусть диаметр Г не меньше 4. Выберем геодезический 4-путь uwxyz в Г. Тогда обобщенный четырехугольник [х] содержит гиперовалы [и] П [х] и [х] П [z], между которыми нет ребер. Далее, \[и] Г\[х]\ 46 и \[х] Г\[г]\ 46, поэтому ввиду леммы 1.2 имеем 49 4б2 1792, противоречие. 550 и по лемме 1.2 граф [х] Г\Хо([и] П [ж]) является подграфом из 9-коклики. Допустим, что {у} z] — ребро из Гз(м). Тогда подграф [ ]fl[z] пересекает Гз(м) по коклике, и вершина у смежна с вершиной из [х] П [z] ПГ2(м), противоречие. Итак, ГЗ(ІІ) является кокликой. Отсюда число ребер между Т2(и) и Гз(м) не больше 550 9, но не меньше 225/сз, поэтому / 22.
Допустим, что вершины z, z находятся на расстоянии 3 в Гз(м), и положим А = (г ПГг ПГг ). Тогда А = 104-2 и любая вершина из А смежна с 72 вершинами из [и], [z], [z \. С другой стороны, вершина из Гз(м) — {z,z } смежна не более чем с 9 вершинами в каждом из подграфов Гз( ) — {u,z }: T (z ) —{и, z] и не менее чем с 63 вершинами из А. С другой стороны, вершина из А смежна с 216 вершинами из [и] U [z] U [z \ и не более чем с 9 вершинами из (Гз(гі) — {z,z }) U (T (z) — {u,z }) U (Гз(У) — {u,z}). Выберем вершину {s Є {и, z, z } так, что число ребер между А и Гз(й) — {и, z, z } равно не более 1/3 ребер между А и (ГзМ - {z,z }) U (Г3(;г) - {и, zf}) U (T3(z ) - {u,z}). Тогда 63(/ — 2) 3(104 — 2&з), поэтому / 6. В случае / = 6 вершина из Гз(м) — {z,zf} смежна не более чем с 4 вершинами в каждом из подграфов Гз( ) — {и, z }: Гз(У) — {и, z] и не менее чем с 73 вершинами из А, поэтому 73 4 3 92, противоречие.
Локально GQ(4,11)-графы
Псевдогеометрический граф для pG2(5,32) имеет сильно регулярные подграфы — окрестность вершины (псевдогеометрический граф для GQ(A, 8)) и вторую окрестность вершины (граф с параметрами (320,99,18,36)). В этом параграфе найдены возможные порядки и подграфы неподвижных точек ав томорфизмов сильно регулярного графа с параметрами (320,99,18,36) и спектром 99і, З275,-2144.
Лемма 2.15. Пусть Г является сильно регулярным графом с параметрами (320,99,18,36). Тогда выполняются следующие утверждения: (1) если Г содержит регулярный подграф А степени d на w вершинах, то —21 d — (99 — d)w/(320 — w) 3, причем в случае равенства каждая вершина из Г — А смежна точно с (99 — і)«;/(320 — w) вершинами из А; (2) порядок коклики вТ не больше 44 и порядок клики вТ не больше 4; (3) значение характера, полученного при проектировании мономиального представления на подпространство размерности 44, на элементе g Є Aut(r) равно X2(g) = (Зао(#) — ai (#))/24 + 4 и 44 — Х2(#) делится на р.
Доказательство. Ввиду границы Цветковича [3] порядок коклики в Г не больше 44. Ввиду границы Хофмана для клик порядок клики в Г не больше 5. Пусть L является 5-кликой из Г, ХІ - множество вершин из Г —L, смежных точно с і вершинами из L, Х{ = \Х{\. Тогда Еж,; = 315, J2iXi = 475, Е Q) = 150, поэтому XQ + Е Го )ж« = —10, противоречие. Если Г содержит регулярный подграф А степени d на w вершинах, то по лемме 2.1 имеем —21 d — (99 — d)w/(320 — w) 3.
Ввиду границы Цветковича порядок коклики в Г не больше 44. Ввиду границы Хофмана для клик порядок клики в Г не больше 5. Пусть L является 5-кликой из Г, ХІ - множество вершин из Г—L, смежных точно с і вершинами из L, ХІ = \ХІ\. Тогда J2Xi = 315, J2ixi = 475, Е ( )ХІ = 150, поэтому XQ + Е Го )xi = —10, противоречие. По [35, лемма 2.3] значение характера, полученного при проектировании мономиального представления на подпространство размерности 44, на элементе g Є Aut(r) равно X2Q?) = (Зао(#) — ai(#))/24 + 4. По лемме 2.3 число 44 — Xc2.{fj) делится на p.
Лемма 2.16. Пусть Г является сильно регулярным графом с параметрами (320,99,18,36), U — трехвершинный подграф из Г, Y{ — множество вершин из Г — U, смежных точно с і вершинами из U, у І = \Y{\. Тогда выполняются следующие утверждения: (1) для двух вершин u}w подграф Гг(гі) П (ги) содержит 156 вершин, если u}w не смежны, 140 вершин, если u}w смежны; (2) число уо + уз равно 128, если U является кокликой, равно 77, если U является кликой; (3) число уо + 2/з равно 95, если U является 2-путем, равно 112, если U — объединение изолированной вершины и ребра.
Доказательство. Для двух несмежных вершин и, w граф Г содержит 36 вершин из [и] П [w]: по 63 вершин из [и] — [w]: [w] — [и] и 156 вершин из Г2(ІІ) П Г2(и9). Для смежных вершин u,w граф Г содержит 18 вершин из [и] П [w], по 80 вершин из [и] — w , [w] — uL и 140 вершин из (и) П Т2{и9).
Если U является 3-кокликой, то Г содержит 3(36 —2/з) вершин из І2, 3(27+ 2/з) вершин из Y\ и 128 — 2/з вершин из Уо, поэтому 2/о + 2/з = 128. Аналогично доказывается, что 2/о + 2/з = 77, если U является кликой.
Если U является геодезическим 2-путем щщщ, то І2 содержит 35 — 2/3 вершин из [щ] П [ІІЗ], и по 18 — 2/з вершин из [iti] П [г ], [ г] П [мз], Уі содержит 61 + 2/3 вершин из [гіг], и по 45 + 2/з вершин из [iti], [мз], Уо содержит 95 — 2/з вершин, поэтому 2/0 + 2/з = 95.
Если [/ объединение изолированной вершины щ и ребра {М2, з}, то І2 содержит 18 — 2/3 вершин из [UQ\ П [Щ], и по 36 — 2/з вершин из [щ] П [гіг], [гіі] П [гіз], Y\ содержит 27 + 2/3 вершин из [гіі], и по 44 + г/з вершин из [гіг], [гіз], Уо содержит 112 — 2/3 вершин, поэтому 2/о + 2/з = 112. Лемма доказана. До конца главы будем предполагать, что Г является сильно регулярным графом с параметрами (320,99,18,36). Пусть д — автоморфизм простого порядка р графа Г и Q = Fix(g).
Лемма 2.17. Выполняются следующие утверждения: (1) если Q — пустой граф, то либо р = 5 и а\{д) Є {0,120}, либо р = 2 и ах(д) Є {0,48,96,144,192,240,288}; (2) если Q является п-кликой, то п = 1, р = 11 и а\(д) = 66; (3) если Q является т-кокликой, т 2, то р = 3; т = 3t + 2, 3 t 14 и а\(д) — 9т — 6 делится на 72; (4) если Q — объединение I 2 изолированных клик, но Q не является кокликой, то р = 2, Q является объединением изолированных ребер, I 29 и а\{д) — 6/ делится на 48.
Доказательство. Пусть Q — пустой граф. Тогдар Є {2, 5}. Еслир = 5, то по целочисленности Xzig) число ot\{g) делится на 24. Но в случае ot\{g) = 240 на Г возникает кликовая (д) орбита длины 5, противоречие с леммой 1.3.
Если р = 2, то число 44 — X2Q?) = 40 + а\(#)/24 четно, поэтому сх\{д) делится на 48. Утверждение (1) доказано. Пусть ХІ — множество вершин из Г — Г2, смежных точно с і вершинами из Q, ХІ = \ХІ\. Пусть Q является п-кликой. Тогда п 4. Если п = 1, то р делит 99 и 220, поэтому р = 11. По целочисленности Х2{д) число ai(g) — 3 делится на 24, поэтому ai(g) = 99.
Если п 2, то р делит 80 и 140, поэтому р Є {2,5}. Но в случае р = 5 число 18 — (п — 2) делится на 5, противоречие. Поэтому р = 2 и п Є {2, 4}. Так как каждая вершина из Г — Q смежна с четным числом вершин из Г2, то п = 4. Отсюда Ж0+Ж2+Ж4 = 316, 3 + 23 = 192 и Ж2+6Ж4 = 96, противоречие. Утверждение (2) доказано.
Пусть Q является т-кокликой, т 2. Тогда р делит 36 и 63, поэтому р = Зит = Зі + 2. По целочисленности Х2(#) число ot\{g) — 9т — б делится на 24, поэтому а.\(д) = 24г + 9т + б, X2Q?) = г + 4. По лемме 1.3 число 44 — Xzig) = г делится на 3. Утверждение (3) доказано.
Пусть Q содержит ребро и является объединением / изолированных клик, / 2. Тогда р делит 80 и 36, поэтому р = 2. Если Q содержит изолированную вершину, то р делит 99, противоречие. Пусть Q содержит изолированную 4-клику L7Yi множество вершин из Г—L, смежных точно с і вершинами из L, Уі = \Yi\. Тогдауо+2/2 = 316, 2у2 = 4-96 = 384, у2 = 6-16 = 96, противоречие. Итак, Q является объединением / изолированных ребер, и по лемме 2.15 имеем / 29. По целочисленности Х2(#) число ai(g) — 6/ делится на 24, поэтому сх\{д) = 24г + б/, X2Q?) = —т + 4. По лемме 2.15 число 44 — X2Q?) = 40 + г четно. Лемма доказана.
Графы с параметрами (96,45,24,18) и (96,50,22,30) не являются реберно симметричными
Лемма 3.7 Пусть Г является вполне регулярным графом, в котором окрестности вершин сильно регулярны с параметрами (169,42, 5,12). Тогда d(T) = 3«/iG {39,42,63}. Доказательство. Число /І делит 169 126 и 39 /І 71. Отсюда /І Є {39,42,63}. Пусть Г — сильно регулярный граф с наименьшим собственным значением —т. Тогда т — 1 делит 126, поэтому тройка (т}п}ц) совпадает с (10,23,39), (15,23,49), (19,25,55) плис (22,27,59). Отсюда /І = 39 и кратность собственного значения п — т = 13 равна 9 169 179/(23 39), противоречие.
Если d(T) 3 и и, w, ж, у, z - геодезический 4-путь в Г, то в графе [х] между [и] П [х] и [х] П [z] нет ребер и 7/i 169 —/І, поэтому /І 22, противоречие. Лемма 3.8 Пусть Г является вполне регулярным графом, в котором окрестности вершин сильно регулярны с параметрами (169,42,5,12). Зафиксируем геодезический 3-путь u}w}y}z в Г и положим 1\ = Ti(u), hb = \Т{\. Тогда hi + / четно и выполняются следующие утверждения: (1) если /І = 63; то / четно, 2 / 12 и Гз является объединением изолированных вершин и ребер; (2) если /І = 42; то / нечетно, 3 / 15; (3) если /i = 39; mo / четно, 2 / 20. Доказательство. Так как число -иА; четно, то / + / четно. Пусть /І = 63. Тогда к2 = 169-126/63 = 338, имеем 63ж0 106(169-ж0)/72, поэтому вершина из Г2 смежна не более чем с 6 вершинами из Гз. Далее, вершина из Гз смежна не менее чем с 76 вершинами из Гз. Теперь число ребер между Г2 и Гз не больше 338 6, но не меньше 76&З, поэтому / 26. Так как степень вершины в Гз не больше 25, то указанное число ребер не меньше 144/сз, поэтому / 14. Повторив указанное рассуждение несколько раз, получим / 12
Допустим, что Гз содержит 3-клику {zi,Z2,Zs}- Тогда Г2 содержит 7 вершин из [z\] П [z2\, 32 7 41, не менее 158 — 7 вершин из [z\] — [22], [2] — [z\\ и не более 22+7 вершин вне [z\\ U [ZQ\. С другой стороны, [z%\ П Г2 содержит не более 41 вершин из [z\] — [Z2], [zi] — [z\\ и не менее 76 вершин вне [z\\ U [zi], противоречие. Значит, Гз не содержит 3-клик.
Допустим, что Гз содержит геодезический 2-путь { 1, 2,}. Тогда Г2 содержит 7 вершин из [z\\ П [ з], 53 7 62, не менее 158 — 7 вершин из [z\] — [Z2], [Z2] — [z\\ и не более 22 + 7 вершин вне [z\] U [,]. С другой стороны, [z:i] Г1Г2 содержит не более 37 вершин из [z\] — [Z2], [-] — [z\] и не менее 84 вер шин вне [zi]U[z2]. Отсюда 7 = 62 и / = 5+3-57+3-84, противоречие. Значит, Гз является объединением изолированных вершин и ребер. Утверждение (1) доказано.
Пусть /І = 42. Тогда / = 169 126/42 = 507, / нечетно, имеем 42жо 127(169 — Жо)/72, поэтому вершина из Г2 смежна не более чем с 9 вершинами из Гз. Далее, вершина из Гз смежна не менее чем с 42 вершинами из Гз. Теперь число ребер между Г2 и Гз не больше 338-9, но не меньше 42&з, поэтому к% 72. Так как степень вершины в Гз не больше 71, то указанное число ребер не меньше 98&з, поэтому / 31. Повторив указанное рассуждение несколько раз, получим / 16.
Пусть /І = 39. Тогда к2 = 169-126/39 = 546, имеем 39ж0 130(169-ж0)/72, поэтому вершина из Г2 смежна не более чем с 9 вершинами из Гз. Далее, вершина из Гз смежна не менее чем с 39 вершинами из Гз. Теперь число ребер между Г2 и Гз не больше 338 9, но не меньше 39/сз, поэтому / 78. Так как степень вершины в Гз не больше 77, то указанное число ребер не меньше 92/, поэтому / 3052/92 = 33. Повторив указанное рассуждение несколько раз, получим / 20.
Лемма 3.9 Если Г — дистанционно регулярный граф, в которых окрестности вершин сильно регулярны с параметрами (169,42, 5,12); то Г имеет массив пересечений {169,126,1; 1, 42,169}.
Доказательство. Пусть Г является дистанционно регулярным графом диаметра 3, в котором окрестности вершин сильно регулярны с параметрами (169,42, 5,12). По лемме 3.3 имеем 9г 13, 03 -32.
Пусть /І = 39. Так как Ьф2 делится на /І, ТО &2 делится на 13 и 9\ 13. Если /І = 42, то / = 169-3 и либо 9\ 13, либо Г имеет массив пересечений {169,126,1; 1, 42,169} и спектр 169і, ІЗ255, -І169, -ІЗ255. Если /І = 63, то / = 169 2 и либо в\ 13, либо 6% —32, либо Ь 3. Компьютерные вычисления показывают, что допустимых массивов пересечений нет.
Докажем следствие 3. Пусть Г — дистанционно регулярный граф, в котором окрестности вершин — сильно регулярные графы с собственным значением 3 и параметрами (?/,//, 5,//). Ввиду лемм 3.6, 3.9 можно считать, что окрестности вершин в Г изоморфны треугольному графу Т(7). Согласно замечанию после леммы 4.3.10 из [2] Г — половинный граф 7-куба. Следствие доказано.
Графы, в которых окрестности вершин сильно регулярны с параметрами (169,42,5,12)
Доказательство. Пусть р = 5. Тогда А = 5ж + 4, ж Є {0,1,...,10} и степени вершин в А равны Ъу + 2, у Є {0,1, ...,7}. Далее, для любых двух вершин а, є Є А число А(а) П [е] делится на 5, если а,е смежны, сравнимо с 2 по модулю 5, если а, е не смежны.
Пусть р = 3. Тогда А = Зх + 1, ж Є {1,2,...,9} и степени вершин в А равны Зу, у Є {0,1,...,13}. Далее, для любых двух вершин а, є Є А число А(а) П [е] сравнимо с 2 по модулю 3, если а,е смежны, делится на 3, если а, е не смежны.
Пусть р = 2. Тогда А = 2х: х Є {1, 2,..., 9} и степени вершин в А равны 2у, у Є {0,1,..., 13}. Далее, для любых двух вершин а, є Є А число А(а)П[е] нечетно, если а, е смежны, четно, если а, е не смежны. Лемма и предложение 4 доказаны.
Пусть до конца главы Г — дистанционно регулярный граф с массивом пересечений {169,126,1; 1,42,169}, G = Aut(T), д — элемент простого порядка р из G и Q = Fix(g) пересекает t антиподальных классов по s вершинам. В случае р 3 имеем а (д) = 0 и любая вершина из Г — Q смежна с t вершинами из Q.
Лемма 4.6. Пусть \\ характер проекции представления ф на подпространство размерности 255 (отвечающее собственному значению в\), Х і — характер проекции представления ф на подпространство размерности 169. Тогдахі(д) = (10а0(д)+аі(д)-3аіз(д)-170)/26, х2(#) = (а0(д)+аіз(д))/4-1, Хі(д) — 255 и Xc2.{fj) — 169 делятся на р. Доказательство. Лемма 4.7. Выполняются следующие утверждения: (1) если Q — пустой граф, то либо р = 17, а\{д) = 170, либо р = 5, (i\{g) = 130/ + 40, либо р = 2, а (д) = 81, (i\{g) = 26m — 2/ — 12 и (i2{g) = 692 - 26m - 6// (2) если Q — клика, то р = 3 и \Q\ Є {2, 5,..., 14}. Доказательство. Пусть Q — пустой граф и оц(д) = pwi для і 1. Так как v = 4 170, то р равно 2, 5 или 17. Пусть р = 17. Тогда w\ + w i + w% = 40, w% = 0 и Xi(#) = 17(«ч — 10)/26. Отсюда w\ = 10. Пусть р = 5. Тогда w\ + w i + w% = 136, юз = 0и Xi(#) = 5(wi 34)/26. Отсюда w\ = 26/ + 8. Пусть р = 2. Тогда w\-\-W2+Wz = 340, X2Q?) = w /2 — 1 и число Х2{я) 255 четно. Отсюда г з = 4/, Xi(#) = C i 12/ — 85)/13 и и \ = 13m — / — 6. Пусть Q является /-кликой. Тогда р делит 3. Если / = 1, то р делит 169, противоречие. Если / 1, то s = 1 и j) = 3 делит 44 — t7 поэтому t Є {2,5,...,14}.
Лемма 4.8 [35, теорема 5.4]. Пусть Г — дистанционно регулярный граф диаметра 3 с А = /І. Через п обозначим часть натурального числа п, свободную от квадратов. Тогда (1) если к = 1 (mod А) иг четно, тор = 1 (mod 4) для любого нечетного простого числа р, делящего к ; (2) если к четно, то (—1)(г_1)/2г — квадрат по модулю р для любого нечетного простого числа р, делящего k . Лемма 4.9 Если р 7, то выполняется одно из утверждений: (1) р = 19; либо Q — дистанционно регулярный граф с массивом пересечений {17,12,1; 1,4,17}; либо t = 37; (2) р = 13, либо Q — антиподальный класс, либо Q — дистанционно регулярный граф с массивом пересечений {13,9,1; 1,3,13}; либо t = 27,40; (3) р = 11 и Q — дистанционно регулярный граф с массивом пересечений {37, 27,1; 1,9,37}.
Доказательство. Пусть р 3. Если р 41, то для вершин а,Ь Є Q с условием і(а, Ъ) 2 имеем [а] П [Ь] содержится в Q. В этом случае Q — дистанционно регулярный граф с массивом пересечений {/:-1,126,1; 1, 42,/: — 1}, поэтому t = 170, противоречие.
Пусть р = 4:1. Тогда 170 — t делится на 41 и t Є {б, 47,88,129}. Для любых двух вершин а, Ъ Є Vt таких, что d(a b) 2, число \Q(a) П [Ь]\ сравнимо с 1 по модулю 41. Вершина из Г — Q смежна с t вершинами из Г2, поэтому t = б и Q — реберно регулярный граф степени 5 с AQ = 1, противоречие.
Аналогичные противоречия получаются в случаях р = 37, 31, 29, 23. Пусть p = 19. Тогда 170 — t делится на 19 и t Є {18,37,56,...,151}. Для любых двух вершин а, Ъ Є Vt таких, что d(a,b) 2, число \Q(a) П [Ь]\ сравнимо с 4 по модулю 19. Вершина из Г — Q смежна с t вершинами из Г2, поэтому либо t = 18 и Г2 — дистанционно регулярный граф с массивом пересечений {17,12,1; 1,4,17}, либо t = 37.
Пусть р = 17. Тогда 170 — t делится на 17 и t Є {17,34, 51,..., 153}. Для любых двух вершин а, 6 Є Q таких, что d(a Ь) 2, число Q(a) П [b] сравнимо с 8 по модулю 17. Вершина из Г — Q смежна с t вершинами из Г2, поэтому t = 34. Если Ъ Є Г2(а), F — антиподальный класс, содержащий а, то Г2(&) содержит по 8 вершин, смежных с каждой вершиной из F. Поэтому Q — дистанционно регулярный граф с массивом пересечений {33, 24,1; 1,8,33}. По лемме 4 такой граф не существует.
Пусть р = 13. Тогда 170 — t делится на 13 и t Є {1,14,27,..., 157}. Для любых двух вершин а, Ъ Є Q таких, что d(a Ь) 2, число Q(a) П [b] \ сравнимо с 3 по модулю 13. Вершина из Г — Q смежна с t вершинами из Г2, поэтому t = 1,14, 27, 40. Если t = 14, то Q — дистанционно регулярный граф с массивом пересечений {13,9,1; 1,3,13}.
Пусть р = 11. Тогда 170 — t делится на 11 и t Є {5,16,27,...,159}. Для любых двух вершин а, Ъ Є Q таких, что d(a Ь) 2, число Q(a) П [b] \ сравнимо с 9 по модулю 11. Вершина из Г — Q смежна с t вершинами из Г2, поэтому t = 16,27,38. Если Ъ Є Г2(а), F — антиподальный класс, содержащий а, то Q(b) содержит по 9 вершин, смежных с каждой вершиной из F. Отсюда t = 38 и Q — дистанционно регулярный граф с массивом пересечений {37, 27,1; 1,9,37}.
Лемма 4.10. Выполняются следующие утверждения: (1) если р = 7, то t = 2,9,16, 23, 30,37; (2) если р = Ъ, то либо Q — дистанционно регулярный граф с массивом пересечений {9,6,1; 1, 2,9}; либо t = 15, 20, 25,30,35, 40; (3) если р = 3, то либо s = 4 и t = 2, 5,8,..., 41; либо s = 1 и Q является t-кликой; (4) если р = 2, то t четно и либо s = 4; t 42; либо s = 2 и t 86. Доказательство. Пустьр = 7. Тогда 170—t делится на 7 и t Є {2,9,16,..., 163}. Для любых двух вершин а, Ъ Є Г2 таких, что rf(a, 6) 2, число Г2(а)П[&] делится на 7. Вершина из Г — Q смежна с t вершинами из Г2, поэтому t = 2,9,16,23,30,37.
Пусть р = 5. Тогда 170 — t делится на 5 и t Є {5,10,..., 165}. Для любых двух вершин а, 6 Є Г2 таких, что d(a,b) 2, число Г2(а) П [&] сравнимо с 2 по модулю 5. Вершина из Г — Q смежна с t вершинами из Г2, поэтому t = 5,10,15,20,25,30,35,40. Пусть t = 10. Если Ь Є Г2(а), F — антиподальный класс, содержащий а, то Q(b) содержит по 2 вершины, смежных с каждой вершиной из F. Отсюда Q — дистанционно регулярный граф с массивом пересечений {9,6,1; 1, 2,9}.
Пусть р = 3. Тогда 170 — t делится на 3 и t Є {2, 5, 8,..., 167}. Для любых двух вершин а, Ъ Є Vt таких, что d(a,b) 2, число \Q(a) П [Ь]\ делится на 3. Если s = 4, то любая вершина из Г — Q смежна с t вершинами из Г2, поэтому t = 2, 5,8,..., 41. Если s = 1, то Г2 является -кликой.
Пусть р = 2. Тогда t четно и для любой вершины и Є Г — Q число [и] П Г2 четно. Если s = 4, то любая вершина из Г — Q смежна с t вершинами из Г2, поэтому = 2,4, б, ...,42.
Пусть s = 2. Тогда для 6 Є Г2(а) и а Є Г2ПГ3(а) имеем П(&)П([а]и[а ]) = t — 2, поэтому — четное число, не большее 86, и в случае равенства Q — дистанционно регулярный граф с массивом пересечений {85,42,1; 1, 42,85}. В этом случае Q(a) — сильно регулярный граф с параметрами (85,42,20,21). Лемма, а вместе с ней и теорема 6 доказаны.
Докажем теорему 7. Пусть Г — дистанционно регулярный граф, имеющий массив пересечений {169,126,1; 1, 42,169}, в котором окрестности вершин сильно регулярны с параметрами (169, 42, 5,12). Тогда порядок клики в Г не больше 6. Ввиду предложения 3 имеем р Є {2,3,5,7,13}. Пусть и Є Г—Q, А = и(9) и р 2.
Если А содержит геодезический 2-путь, то и смежна не более чем с 12 вершинами из Q, поэтому ввиду теоремы 2 либо р = 7 и = 2,9, либо р = 5 и Q — дистанционно регулярный граф с массивом пересечений {9, 6,1; 1, 2, 9}. Ввиду предложения 3 случай p = 7nt = 9ne возникает.
Если А является кликой, то р = 3 и либо S = 4H = 2,5, либо s = 1 и Q является 2-кликой. Если же каждая (д) -орбита на Г — Q является кокликой, то либо ot2{g) = 680 — Сїо(д), либо р = 3, s = 1 и Q является -кликой, = 2,5. В случае (У.2І9) = 680 — ао(д) имеем Xi(#) = (ао(д) -17)/13 и ввиду теоремы 6 верно одно из утверждений: