Автоморфизмы дистанционно регулярного графа с массивом пересечений {121, 90, 1; 1, 30, 121} К.С. Ефимов2 А.А. Махнев1 konstantin.s.efimov@gmail.com makhnev@imm.uran.ru 1 – ИММ УрО РАН (Екатеринбург) 2 – УрФУ (Екатеринбург) Аннотация А.А. Махнев и М.С. Самойленко выделили параметры сильно регу- лярных графов с не более чем 1000 вершинами, которые могут быть окрестностями вершин в антиподальном дистанционно регулярном графе диаметра 3 с λ = µ. Ими же предложена программа исследо- вания вершинно симметричных антиподальных дистанционно регу- лярных графов диаметра 3 с λ = µ, в которых окрестности вершин сильно регулярны с вышеуказанными параметрами. В данной ра- боте рассмотрен граф с массивом пересечений {121, 90, 1; 1, 30, 121}. Доказано, что вершинно симметричный граф с массивом пересече- ний {121, 90, 1; 1, 30, 121} является реберно симметричным с цоко- лем группы автоморфизмов, изоморфным Z2 × L2 (121). 1 Введение Мы рассматриваем неориентированные графы без петель и кратных ребер. Для вершины a графа Γ через Γi (a) обозначим i-окрестность вершины a, то есть подграф, индуцированный Γ на множестве всех вершин, находящихся на расстоянии i от a. Положим [a] = Γ1 (a), a⊥ = {a}∪[a]. Графом Тэйлора называется дистанционно регулярный граф с массивом пересечений {k, µ, 1; 1, µ, k}. Допустим, что Γ — антиподальный дистанционно регулярный граф диаметра 3 с λ = µ, в котором окрестности вершин сильно регулярны. Тогда Γ имеет массив пересечений {k, µ(r − 1), 1; 1, µ, k} и спектр √ f √ f k 1 , k , −1k , − k , где f = (k + 1)(r − 1)/2. Далее, (r − 1)k 0 = v 0 − k 0 − 1 и число (v 0 + 1)(r − 1) четно. В случае r = 2 получим граф Тэйлора, в котором k 0 = 2µ0 . Обратно, для любого сильно регулярного графа с параметрами (v 0 , 2µ0 , λ0 , µ0 ) найдется граф Тэйлора, в котором окрестности вершин сильно регулярны с соответствующими параметрами. В [1] выделены параметры сильно регулярных графов с не более чем 1000 вершинами, которые могут быть окрестностями вершин в антиподальном дистанционно регулярном графе диаметра 3 с λ = µ. В рамках проекта РНФ 14-11-00061 продолжается программа исследования вершинно симметричных антиподальных дистанционно регулярных графов диаметра 3 с λ = µ, в которых окрестности вершин сильно регулярны с параметрами из заключения предложения [1]. В данной работе рассмотрены параметры (121, 30, 11, 6). Copyright c by the paper’s authors. Copying permitted for private and academic purposes. In: A.A. Makhnev, S.F. Pravdin (eds.): Proceedings of the 47th International Youth School-conference “Modern Problems in Mathematics and its Applications”, Yekaterinburg, Russia, 02-Feb-2016, published at http://ceur-ws.org 7 Теорема 1. Пусть Γ — сильно регулярный граф с параметрами (121, 30, 11, 6), G = Aut(Γ), g — элемент простого порядка p из G и Ω = Fix(g). Тогда π(G) ⊆ {2, 3, 5, 7, 11} и выполняется одно из следующих утверждений: (1) Ω является пустым графом, p = 11 и α1 (g) = 0, 121; (2) Ω является n-кликой, либо n = 1, p = 5, α1 (g) = 55l + 30 или p = 3, α1 (g) = 33l − 3, либо n = 3t + 1, 1 6 t 6 3, p = 3 и α1 (g) = 33l − 3 − 9t, либо n = 2t + 1, 1 6 t 6 5, p = 2 и α1 (g) = 22l + 8 − 6t; (3) Ω является m-кокликой, либо m = 3t + 1, 1 6 t 6 3, p = 3 и α1 (g) = 33l − 9t − 3, либо m = 2t + 1, 1 6 t 6 5, p = 2 и α1 (g) = 22l + 8 − 6t; (4) Ω содержит ребро и является объединением s изолированных клик и либо p = 3, число вершин в максимальной клике из Ω сравнимо с 1 по модулю 3 и s сравнимо с 1 по модулю 3, либо p = 2, число вершин в максимальной клике из Ω нечетно и s нечетно; (5) если Ω содержит [a] для некоторой вершины a, то p 6 3, в случае |Ω| = 31 имеем p = 3 и α1 (g) = 33l − 60, 2 6 l 6 4; (6) Ω содержит геодезический путь, p 6 7 и в случае p = 7 подграф Ω сильно регулярен с параметрами (16, 9, 4, 6). Теорема 2. Пусть Γ — дистанционно регулярный граф с массивом пересечений {121, 90, 1; 1, 30, 121}, G = Aut(Γ), g — элемент простого порядка p из G и Ω = Fix(g) содержит по s вершин в t антиподальных классах. Тогда π(G) ⊆ {2, 3, 5, 7, 11, 13, 23, 61} и выполняются следующие утверждения: (1) если Ω — пустой граф, то p ∈ {2, 61}; (2) если Ω — антиподальный класс, то p = 11; (3) если Ω — клика, то p = 3 и t = 2, 5, 8, 11; (4) если p > 11, то либо p = 23 и Ω — дистанционно регулярный граф с массивом пересече- ний {29, 21, 1; 1, 7, 29}, либо p = 13 и Ω — дистанционно регулярный граф с массивом пересечений {17, 12, 1; 1, 4, 17}; (5) если p = 7, то t = 10, 17, 24 и в случае t = 10 подграф Ω является дистанционно регулярным с массивом пересечений {9, 6, 1; 1, 2, 9}; (6) если p = 5, то t = 2, 7, 12, 17, 22, 27 и в случае t = 7 подграф Ω является объединением четырех изолированных 7-клик; (7) если p = 3, s = 4, то t = 3l + 2, l 6 9 и в случае t = 5 подграф Ω является объединением четырех изолированных 5-клик; (8) если p = 2, s > 0, то каждая вершина из Γ − Ω смежна с четным числом вершин из Ω и либо s = 2, t 6 60, либо s = 4, t 6 30. Следствие. Вершинно симметричный дистанционно регулярный граф с массивом пересечений {121, 90, 1; 1, 30, 121} является реберно симметричным графом с группой автоморфизмов, имеющей цо- коль Z2 × L2 (121). Заметим, что ввиду границы Дельсарта [2, предложение 4.4.6] максимальный порядок клики в дистан- ционно регулярном графе с массивом пересечений {121, 90, 1; 1, 30, 121} и спектром 1211 , 11305 , −1121 , −11305 не больше 1 − k/θd = 1 + 121/11 = 12. Если C является 12-кликой из Γ, то каждая вершина вне C смежна с 0 или с b1 /(θd + 1) + 1 − k/θd = −9 + 12 = 3 вершинами из C. 2 Автоморфизмы графа с параметрами (121, 30, 11, 6) В этом параграфе Γ — сильно регулярный граф с параметрами (121, 30, 11, 6) (псевдогеометрический граф для сети pG2 (10, 2)) и спектром 301 , 830 , −390 , G = Aut(Γ), g – элемент простого порядка p из G и Ω = Fix(g). Ввиду границ Хофмана, порядок коклики в Γ не больше vm/(k + m) = 121 · 3/33 = 11, порядок клики C в Γ не больше 1 + k/m = 11 и в случае |C| = 11 каждая вершина из Γ − C смежна точно с 2 вершинами из C. Лемма 1. Пусть ψ — мономиальное представление группы G в GL(121, C), χ1 — характер проекции ψ на подпространство собственных векторов размерности 30, отвечающих собственному значению 8. Тогда χ1 (g) = (3α0 (g) + α1 (g))/11 − 3 и χ1 (g) − 30 делится на p. 8 Доказательство. Имеем   1 1 1 Q =  30 8 −3  . 90 −9 2 Поэтому χ1 (g) = (30α0 (g) + 8α1 (g) − 3α2 (g))/121. Подставляя α2 (g) = 121 − α0 (g) − α1 (g), получим χ1 (g) = (3α0 (g) + α1 (g))/11 − 3. Последнее утверждение леммы следует из [3, лемма 1]. Лемма 2. Пусть A — трехвершинный подграф из Γ, yi — число вершин из Γ − A, смежных точно с i вершинами из A. Если A — коклика, то y0 = 46 − y3 , если A — объединение изолированной вершины и ребра, то y0 = 53 − y3 , если A — геодезический путь, то y0 = 59 − y3 , а если A — клика, то y0 = 64 − y3 . Доказательство. Пусть A — коклика. Тогда y1 = 54 + 3y3 , y2 = 18 − 3y3 и y0 = 46 − y3 . Пусть A — клика. Тогда y1 = 24 + 3y3 , y2 = 30 − 3y3 и y0 = 64 − y3 . Аналогично рассматриваются оставшиеся случаи. Лемма 3. Выполняются следующие утверждения: (1) Γ не содержит собственных сильно регулярных подграфов с параметрами (v 0 , k 0 , 11, 6); (2) если Ω является пустым графом, то p = 11 и α1 (g) = 0, 121; (3) если Ω является n-кликой, то либо n = 1, p = 5, α1 (g) = 55l + 30 или p = 3, α1 (g) = 33l − 3, либо n = 3t + 1, 1 6 t 6 3, p = 3 и α1 (g) = 33l − 3 − 9t, либо n = 2t + 1, 1 6 t 6 5, p = 2 и α1 (g) = 22l + 8 − 6t; (4) если Ω является m-кокликой, либо m = 3t + 1, 1 6 t 6 3, p = 3 и α1 (g) = 33l − 9t − 3, либо m = 2t + 1, 1 6 t 6 5, p = 2 и α1 (g) = 22l + 8 − 6t; (5) если Ω содержит ребро и является объединением s изолированных клик, то либо p = 3, число вершин в максимальной клике из Ω сравнимо с 1 по модулю 3 и s сравнимо с 1 по модулю 3, либо p = 2, число вершин в максимальной клике из Ω нечетно и s нечетно. Доказательство. Пусть Γ содержит собственный сильно регулярный подграф ∆ с параметрами (v 0 , k 0 , 11, 6). Тогда n2 = 4(k 0 − 6) + 25, поэтому n = 2u + 1 и k 0 = u2 + u. Далее, ∆ имеет неглавные собственные значения u + 3, 2 − u и кратность u + 3 равна (u − 1)(u2 + u)(u2 + 2u − 2)/(6(2u + 1)). При u = 4 получим 3 · 20 · 22/54, а при u = 3 граф ∆ является полным многодольным. В любом случае имеем противоречие. Пусть Ω является пустым графом. Тогда p = 11, χ1 (g) = α1 (g))/11 − 3 и χ1 (g) − 30 делится на 11. Поэтому α1 (g) равно 0 или 121. Пусть Ω является n-кликой. Если n = 1, то p делит 30 и χ1 (g) = (α1 (g) − 30)/11. В случае p = 5 число χ1 (g) делится на 5, поэтому α1 (g) = 55l + 30. В случае p = 3 число χ1 (g) делится на 3, поэтому α1 (g) = 33l − 3. В случае p = 2 имеем α1 (g) = 0 и χ1 (g) = −3 и χ1 (g) − 30 не делится на 2, противоречие. Если n > 1, то p делит 18 и 13−n. В случае p = 3 имеем n = 3t+1, t 6 3, число χ1 (g) = (9t−30+α1 (g))/11 делится на 3 и α1 (g) = 33l − 3 − 9t. В случае p = 2 имеем n = 2t + 1, t 6 5, число χ1 (g) = (6t − 30 + α1 (g))/11 четно и α1 (g) = 22l + 8 − 6t. В случае t = 5 каждая вершина из Γ − Ω смежна с четным числом вершин из Ω, поэтому α1 (g) = 22(l − 1) = 0. Пусть Ω является m-кокликой, m > 1. Тогда p делит 6 и 67 − m. В случае p = 3 число χ1 (g) делится на 3, m = 3t + 1, t 6 3, χ1 (g) = (9t + 3 + α1 (g))/11 − 3 и α1 (g) = 33l − 9t − 3. В случае p = 2 число χ1 (g) четно, m = 2t + 1, t 6 5, χ1 (g) = (6t + 3 + α1 (g))/11 − 3 и α1 (g) = 22l + 8 − 6t. Пусть Ω содержит ребро и является объединением s изолированных клик. Тогда p делит 6 и 18. В случае p = 3 число вершин в максимальной клике из Ω сравнимо с 1 по модулю 3 и s сравнимо с 1 по модулю 3. В случае p = 2 число вершин в максимальной клике из Ω нечетно и s нечетно. Лемма 4. Пусть Ω содержит геодезический путь b, a, c. Тогда выполняются следующие утверждения: (1) p 6 11 и если α2 (g) = 0, то либо p = 7, α0 (g) = 44, либо p = 5, α0 (g) = 11, либо p = 3, α0 (g) = 22, 55, либо p = 2, α0 (g) = 11, 33, 55; (2) если Ω содержит [a] для некоторой вершины a, то p 6 3, в случае |Ω| = 31 имеем p = 3 и α1 (g) = 33l − 60, 2 6 l 6 4. Доказательство. Пусть p > 13. Тогда Ω – сильно регулярный подграф с параметрами (v 0 , k 0 , 11, 6), противоречие. Если α2 (g) = 0, то χ1 (g) = 8 + 2α0 (g)/11, причем χ1 (g) − 30 делится на p, поэтому 2α0 (g)/11 − 22 делится на p. Отсюда α0 (g) = 11w, p делит 2(11 − w) и либо p = 11, α0 (g) = 121, противоречие, либо p = 7, α0 (g) = 44, либо p = 5, α0 (g) = 11, либо p = 3, α0 (g) = 22, 55, либо p = 2, α0 (g) = 11, 33, 55. 9 Пусть Ω содержит [a] для некоторой вершины a. Тогда [u] ∩ Ω содержит 6 вершин из Ω для любой вершины u ∈ Γ − Ω. Отсюда любая hgi-орбита длины p не содержит геодезических 2-путей, в частности она является кликой или кокликой. Если p > 7, то [u] ∩ Ω является 6-кликой и для двух вершин b, c ∈ [u] ∩ Ω подграф [b] ∩ [c] содержит a, 4 вершины из [u] ∩ Ω и p верщин из hgi-орбиты, содержащей u, противоречие. В случае p = 5 подграф [u]∩Ω является кликой, иначе для двух несмежных вершин b, c ∈ [u]∩Ω подграф [b] ∩ [c] содержит a и 5 верщин из hgi-орбиты ∆, содержащей u. В этом случае [u] ∩ Ω является кокликой, противоречие с тем, что ∪b∈[u]∩Ω ([a] ∩ [b]) содержит не менее 55 вершин. Если ∆ – клика, то ∆ ∪ (Ω ∩ [u]) является 11-кликой, противоречие с тем, что a смежна с 6 вершинами этой клики. Значит, ∆ – коклика, противоречие с тем, что ∪u∈∆ ([u] − [a]) содержит не менее 120 вершин. Итак, p 6 3. Если |Ω| = 31, то χ1 (g) = (60 + α1 (g))/11 и χ1 (g) − 30 делится на p. В случае p = 3 имеем α1 (g) = 33l − 60, 2 6 l 6 4. В случае p = 2 имеем α1 (g) = 22l − 60, для вершины u, смежной с ug , подграф [u] содержит нечетное число вершин из Ω − [a], противоречие. Лемма 5. Пусть Ω содержит геодезический путь b, a, c. Тогда p 6 7 и в случае p = 7 подграф Ω сильно регулярен с параметрами (16, 9, 4, 6). Доказательство. Пусть p = 11. Тогда µΩ = 6 и для смежных вершин a, b ∈ Ω подграф Ω(a) ∩ [b] содержит 0 или 11 вершин. Далее, |Ω| = 11t, t 6 5, и степень вершины в Ω равна 8, 19. Если a – вершина степени 8 в Ω, то число ребер между Ω(a) и Ω2 (a) равно 6(11t − 9) = 18e + 7(8 − e), поэтому 6t = 10 + e и либо t = 2 = e, либо t = 3, e = 8. В любом случае имеем противоречие с тем, что для двух вершин b, c из Ω(a), смежных с 18 вершинами из Ω2 (a), подграф [b] ∩ [c] содержит не менее 12 вершин из Ω2 (a). Итак, Ω – регулярный граф степени 19 на 44 вершинах. Теперь число ребер между Ω(a) и Ω2 (a) равно 6 · 24 = 18e + 7(19 − e), поэтому e = 1. Для вершины b из Ω(a), смежной с 18 вершинами из Ω2 (a), и вершины c из Ω − (a⊥ ∪ b⊥ ) подграф [c] содержит не более 12 вершин из a⊥ ∪ b⊥ и не более 5 вершин из Ω − (a⊥ ∪ b⊥ ), противоречие. Пусть p = 7. Тогда µΩ = 6 и для смежных вершин a, b ∈ Ω подграф Ω(a) ∩ [b] содержит 4 или 11 вершин. Далее, |Ω| = 7t + 2, t 6 8, и степень вершины в Ω равна 9, 16, 23. В случае |Ω| = 58 ввиду леммы 2 каждая hgi-орбита длины 7 является кликой, α2 (g) = 0, противоречие с леммой 4. В случае |Ω| = 51 имеем χ1 (g) = (153 + α1 (g))/11 − 3 и α1 (g) = 56. Далее, ввиду леммы 2 степень вершины в hgi-орбите Σ длины 7 равна 4 или 6. Если степень вершины u в Σ равна 4, то Σ содержит трехвершинный подграф Σ0 , являющийся объединением изолированной вершины и ребра, причем Σ0 попадает в окрестности двух вершин из Σ. Таким образом, имеется восемь кликовых hgi-орбит длины 7 и две hgi-орбиты степени 4. Вершина u из кликовой hgi-орбиты Φ длины 7 смежна не более чем с 5 вершинами из Ω, иначе Φ ∪ (Ω ∩ [u]) является 13-кликой, противоречие. Теперь число ребер между Ω и Γ − Ω, деленное на 7, не больше 5 · 8 + 2 · 3 = 46. Если a – вершина степени 9 в Ω, то число ребер между Ω(a) и Ω2 (a) равно 6(7t − 8) = 18e + 11m + 4(9 − m − e), поэтому 6t = 12 + m + 2e, t 6 5. В случае t = 2 имеем m = e = 0 и Ω – сильно регулярный граф с параметрами (16,9,4,6). В случае t = 3 имеем m = 6, e = 0 и множество Σ вершин из Ω(a), смежных с 11 вершинами из Ω2 (a), индуцирует клику. Противоречие с тем, что для двух вершин b, c ∈ Σ подграф [b] ∩ [c] содержит 4 вершины из Σ и не менее 9 вершин из Ω2 (a). В случае t = 4 имеем m + 2e = 12 и e 6 1, противоречие. В случае t = 5 имеем e = 9 и для двух несмежных вершин b, c из Ω(a) подграф [b] ∩ [c] содержит a и не менее 9 вершин из Ω2 (a), противоречие. Итак, в Ω нет вершин степени 9. Если a, b – две вершины степени 23 в Ω, то либо a, b не смежны и Ω содержит a, b, 6 вершин из [a] ∩ [b], по 17 вершин из [a] − [b], [b] − [a] и еще 7t − 40 вершин, либо a, b смежны и Ω содержит a, b, δ вершин из [a] ∩ [b], по 22 − δ вершин из [a] − [b], [b] − [a] и еще 7t + δ − 44 вершин. Отсюда t > 6. Пусть z — число вершин степени 16 в Ω. Тогда число ребер между Ω и Γ − Ω, деленное на 7, равно 2z + (|Ω| − z). В случае |Ω| = 51 указанное число ребер не больше 46, противоречие. Итак, t = 6 и для двух несмежных вершин a, b степени 23 в Ω подграф Ω содержит a, b, 6 вершин из [a] ∩ [b], по 17 вершин из [a] − [b], [b] − [a] и 2 вершины вне a⊥ ∪ b⊥ . Противоречие с тем, что степень вершины c из Ω − (a⊥ ∪ b⊥ ) в графе Ω не больше 1+12. Значит, подграф Ψ на множестве вершин степени 23 в Ω является кликой. Теперь для двух вершин a, b ∈ Ψ подграф Ω содержит a, b, 11 вершин из [a] ∩ [b], по 11 вершин из [a] − [b], [b] − [a] и 9 вершин вне a⊥ ∪ b⊥ . Если a ∈ Ψ, то число ребер между Ω(a) и Ω2 (a) равно 120 = 11m + 4(23 − m), поэтому m = 4 и |Ψ| = 2, 4. Заметим, что вершина из Γ − Ω смежна не более чем с 6 вершинами из Ω, поэтому число ребер между Ω и 10 Γ − Ω, деленное на 7, не больше 66. С другой стороны, это число не меньше 40 · 2 + 4, противоречие. Лемма доказана. Из лемм 3–5 следует теорема 1. 3 Автоморфизмы графа с параметрами (121, 30, 11, 6) В этом параграфе предполагается, что Γ — дистанционно регулярный граф с массивом пересечений {121, 90, 1; 1, 30, 121} и спектром 1211 , 11183 , −1121 , −11183 , G = Aut(Γ), g — элемент простого порядка p из G и Ω = Fix(g) пересекает t антиподальных классов по s вершинам. Пусть F — антиподальный класс, содержащий вершину a ∈ Ω, F ∩ Ω = {a, a2 , ..., as }, b ∈ Ω(a). Через F (x) будем обозначать антиподальный класс, содержащий вершину x. Лемма 6. Если ψ — мономиальное представление группы G в GL(488, C), χ1 — характер проекции ψ на подпространство собственных векторов размерности 183, отвечающих собственному значению 11, χ2 — характер проекции ψ на подпространство размерности 121, то χ1 (g) = (17α0 (g)+2α1 (g)−5α3 (g))/44− 61/11, χ2 (g) = (α0 (g) + α3 (g))/4 − 1. Далее, χ1 (g) − 183 и χ2 (g) − 121 делятся на p. Доказательство. Имеем   1 1 1 1  183 183/11 −61/11 −61  Q=  . 121 −1 −1 121  183 −183/11 61/11 −61 Поэтому χ1 (g) = (3α0 (g)+3α1 (g)/11−α2 (g)/11−α3 (g))/8. Подставляя α2 (g) = 488−α0 (g)−α1 (g)−α3 (g), получим χ1 (g) = (17α0 (g) + 2α1 (g) − 5α3 (g))/44 − 61/11. Аналогично, χ2 (g) = (121α0 (g) − α1 (g) − α2 (g) + 121α3 (g))/488. Подставляя α1 (g) + α2 (g) = 488 − α0 (g) − α3 (g), получим χ2 (g) = (α0 (g) + α3 (g))/4 − 1. Остальные утверждения леммы следуют из [3, лемма 1]. Лемма доказана. Лемма 7. Выполняются следующие утверждения: (1) если Ω — пустой граф, то либо p = 61, α1 (g) = 122 и α2 (g) = 366, либо p = 2, α3 (g) = 8l, α1 (g) = 20l + 12 + 44m и α2 (g) = 476 − 28l − 44m, l 6 61 и 7l + 11m 6 119; (2) если Ω — антиподальный класс, то p = 11, α1 (g) = 22l; (3) если Ω — клика, то p = 3, t = 2, 5, 8, 11. Доказательство. Пусть Ω — пустой граф и αi (g) = pwi для i > 0. Так как v = 61 · 8, то p ∈ {2, 61}. Пусть p = 61. Тогда α3 (g) = 0 и χ1 (g) = 61(w1 − 2)/22. Отсюда w1 = 22l + 2, α1 (g) = 122 и α2 (g) = 366. Пусть p = 2. Тогда χ2 (g) = α3 (g)/4 − 1, α3 (g) = 8l и число χ1 (g) = (w1 − 10l − 61)/11 нечетно. Поэтому w1 = 10l + 6 + 22m и α1 (g) = 20l + 12 + 44m и α2 (g) = 476 − 28l − 44m. В случае α3 (g) = 488 имеем χ1 (g) = −61. Пусть Ω — антиподальный класс. Тогда p делит 121, поэтому p = 11. Далее, χ1 (g) = (α1 (g) − 88)/22 и α1 (g) = 22l. Если Ω — клика, то p = 3 делит 122 − t, поэтому t = 2, 5, 8, 11. Лемма доказана. В леммах 8–9 предполагается, что t > 1, s > 1. Лемма 8. Выполняются следующие утверждения: (1) если p > 11, то либо p = 23 и Ω — дистанционно регулярный граф с массивом пересече- ний {29, 21, 1; 1, 7, 29}, либо p = 13 и Ω — дистанционно регулярный граф с массивом пересечений {17, 12, 1; 1, 4, 17}; (2) если p = 7, то t = 10, 17, 24 и в случае t = 10 подграф Ω является дистанционно регулярным с массивом пересечений {9, 6, 1; 1, 2, 9}; (3) если p = 5, то t = 2, 7, 12, 17, 22, 27 и в случае t = 7 подграф Ω является объединением четырех изолированных 7-клик; (4) если p = 3, то t = 3l + 2, l 6 9 и в случае t = 5 подграф Ω является объединением четырех изолированных 5-клик. Доказательство. Если s = 4, то каждая вершина из Γ − Ω смежна точно с t вершинами из Ω. 11 Пусть p > 3, α1 (g) = pw1 . Тогда s = 4, α3 (g) = 0, |Ω| = 4t, Ω — регулярный граф степени t − 1 и p делит 122 − t. Если p > 29, то Ω — дистанционно регулярный граф с массивом пересечений {t − 1, t − 32, 1; 1, 30, t − 1}, противоречие. Пусть p = 29. Так как p делит 122 − t, то t = 6, подграф Ω(b) содержит 2 вершины из a⊥ и по вер- шине из [a2 ], ..., [a4 ]. Отсюда Ω — дистанционно регулярный граф с массивом пересечений {5, 3, 1; 1, 1, 5}, противоречие. Пусть p = 23. Так как p делит 122−t, то t = 7, 30, подграф Ω(b) содержит 8 вершины из a⊥ и по 7 вершин из [a2 ], ..., [a4 ]. Отсюда Ω — дистанционно регулярный граф с массивом пересечений {29, 21, 1; 1, 7, 29}. Пусть p = 19. Так как p делит 122 − t, то t = 8, 27, подграф Ω(b) содержит 12 вершин из a⊥ и по 11 вершин из [a2 ], ..., [a4 ], противоречие. Пусть p = 17. Так как p делит 122 − t, то t = 3, 20, подграф Ω(b) содержит 14 вершин из a⊥ и по 13 вершин из [a2 ], ..., [a4 ], противоречие. Пусть p = 13. Так как p делит 122−t, то t = 5, 18, подграф Ω(b) содержит 5 вершин из a⊥ и по 4 вершины из [a2 ], ..., [a4 ]. Отсюда Ω — дистанционно регулярный граф с массивом пересечений {17, 12, 1; 1, 4, 17}. Пусть p = 11. Так как p делит 122 − t, то t = 12, 23, подграф Ω(b) содержит 9 вершин из a⊥ и по 8 вершин из [a2 ], ..., [a4 ], противоречие. Пусть p = 7. Так как p делит 122 − t, то t = 3, 10, 17, 24, подграф Ω(b) содержит 3 вершины из a⊥ и по 2 вершины из [a2 ], ..., [a4 ], поэтому в случае t = 10 подграф Ω является дистанционно регулярным с массивом пересечений {9, 6, 1; 1, 2, 9}. Пусть p = 5. Так как p делит 122 − t, то t = 2, 7, 12, 17, 22, 27. В случае t = 7 подграф Ω является объединением изолированных 7-клик и, быть может, графа ∆ без треугольников. Пусть ∆(a) = {b1 , ..., b6 }. Без ограничения общности, ∆(bi ) содержит 5 вершин из [ai+1 ]. Противоречие с тем, что вершина из ∆(b1 )∩ [a2 ] должна быть смежна с 5 вершинами из ∆(a). Пусть p = 3. Тогда s = 4 и α3 (g) = 0. Так как 3 делит 122 − t, то t = 3l + 2, l 6 9. В случае t = 5 подграф Ω является объединением изолированных 5-клик и, быть может, графа ∆ без треугольников. Пусть ∆(a) = {b1 , ..., b4 }. Без ограничения общности, ∆(bi ) содержит 3 вершины из [ai+1 ]. Противоречие с тем, что вершина из ∆(b1 ) ∩ [a2 ] должна быть смежна с 3 вершинами из ∆(a). Лемма 9. Если p = 2, то каждая вершина из Γ − Ω смежна с четным числом вершин из Ω и либо s = 2, t 6 60, либо s = 4, t 6 30. Доказательство. Пусть p = 2. Тогда s ∈ {2, 4} и t четно. Заметим, что для любых двух вершин a, b ∈ Ω имеем |Ω(a) ∩ [b]| ∈ {0, 2, ..., 30}, любая вершина из Γ − Ω смежна с четным числом вершин из Ω. Так как α3 (g) = t(4 − s), то χ2 (g) = t − 1, t четно, α1 (g) + α2 (g) = 488 − 4t, число χ1 (g) = (17st + 2α1 (g)− −5t(4 − s))/44 − 61/11 = ((11st + α1 (g))/2 − 5t − 61)/11 нечетно. Если s = 2, то число ребер между Ω и Γ − Ω равно 2t(122 − t), но не больше 120(122 − t), поэтому t 6 60. Если s = 4, то t 6 30. Лемма доказана. Из лемм 7–9 следует теорема 2. 4 Вершинно симметричный случай Пусть группа G действует транзитивно на множестве вершин графа Γ. Тогда для антиподального класса F , содержащего вершину a ∈ Γ, подгруппа H = G{F } имеет индекс 122 в G и |H : Ha | = 4. Из теоремы 2 следует, что {2, 61} ⊆ π(G) ⊆ {2, 3, 5, 7, 11, 13, 23, 61} и |G| не делится на 132 и на 113 . Лемма 10. Выполняются следующие утверждения: (1) если f — элемент порядка 61 из G, g — элемент простого порядка p 6= 61 из CG (f ), то p = 2 и α3 (g) = 488; (2) S(G) = O2 (G) и |O2 (G)| делит 4; (3) цоколь T̄ группы Ḡ = G/O2 (G) изоморфен L2 (121). Доказательство. Допустим, что g — элемент простого порядка p 6= 61 из CG (f ). Так как f действует без неподвижных точек на Ω, то, ввиду теоремы 2, Ω — пустой граф, α1 (f ) = 122, p = 2 и числа α3 (g) = 8l, α1 (g) = 20l + 12 + 44m, α2 (g) = 476 − 28l − 44m делятся на 61. Если l = 0, то 3 + 11m делится на 61, противоречие. Значит, l = 61. 12 Заметим, что 236 − 1 не делится на 61. Пусть Q = O2 (G) 6= 1. Тогда порядки Q-орбит на множестве антиподальных классов делят 2. Если порядок некоторой Q-орбиты равен 1, то Q фиксирует каждый антиподальный класс и |Q| делит 4, проти- воречие с утверждением (1). Теперь подгруппа Q0 индекса 2 из Q фиксирует F и подгруппа Q1 индекса 16 из Q фиксирует F поточечно. Так как k = 121, то Q1 фиксирует вершину b из [a]. Подгруппа Q2 индекса 16 из Q1 фиксирует a, b и по 6 вершин из [b] ∩ [x] для x ∈ F . Аналогично, подгруппа Q3 индекса 16 из Q1 фиксирует a, b и по 6 вершин из [a] ∩ [y] для y ∈ F (b). Теперь любая инволюция из Q2 ∩ Q3 фиксирует не менее 2 + 6 + 36 антиподальных классов и по теореме 2 имеем Q2 ∩ Q3 = 1. Отсюда |Q| 6 36, противоречие с действием элемента порядка 61 на Q. Из утверждения (1) следует, что S(G) = O2 (G) и |O2 (G)| делит 4. Пусть T̄ — цоколь группы Ḡ = G/O2 (G). Ввиду теоремы из [4], группа T̄ изоморфна L2 (35 ), U5 (3), L2 (112 ), U6 (3). Так как T̄ содержит подгруппу индекса, делящего 122, то группа T̄ изоморфна L2 (121) (и T̄{F } — расширение группы порядка 121 с помощью группы порядка 60). Лемма доказана. Докажем следствие. Ввиду леммы 10, подгруппа T изоморфна L2 (121), SL2 (121), Z2 × L2 (121), Z2 × SL2 (121) или K × L2 (121), где |K| = 4. Пусть подгруппа H изоморфна SL2 (121) или L2 (121). Тогда наименьший индекс в H её максимальной подгруппы равен 122, поэтому H действует транзитивно на множестве антиподальных классов. Понятно, что H — нормальная подгруппа, поэтому G действует на множестве H-орбит, и, значит, H-орбиты являются изоморфными подграфами порядка не меньше 122. Есть такие варианты: 1. Четыре H-орбиты порядка 122, на которых H действует 2-транзитивно. Нетрудно понять, что это невозможно. 2. Две H-орбиты порядка 244. Стабилизатор антиподального класса H{F } и стабилизатор вершины Ha находятся однозначно с точностью до сопряжения, причём Z(H) 6 Ha . Орбиты Ha , лежащие в той же H-орбите, что и a, имеют порядки 1, 121, 121, 1. Понятно, что две неподвижные относительно Ha вершины – это пара антиподов. Поэтому окрестность a в соответствующей H-орбите либо пуста, либо содержит 121 вершину. Первое невозможно потому, что граф не двудольный. Второе невозможно потому, что граф связный. 3. H действует транзитивно. Тогда стабилизатор антиподального класса и стабилизатор вершины нахо- дятся однозначно с точностью до сопряжения (при этом Z(H) 6 Ha ) и существует единственный дистан- ционно регулярный граф с заданным массивом, допускающий H. Следствие доказано. Работа выполнена при поддержке РНФ, проект 14-11-00061 (теорема 2 и следствие) и соглашения между Министерством образования и науки Российской Федерации и Уральским федеральным университетом от 27.08.2013, № 02.A03.21.0006 (теорема 1). Список литературы [1] A. A. Makhnev, M. S. Samoilenko. On distance-regular covers of cliques with strongly regular local subgraphs. Tranzactions of 46 International school-conference, Yekaterinburg, 13–18, 2015. [2] A. E. Brouwer, A. M. Cohen, A. Neumaier. Distance-Regular Graphs. Springer-Verlag, 1989. [3] A. L. Gavrilyuk, A. A. Makhnev. On automorphisms of distance-regular graph with the intersection array {56, 45, 1; 1, 9, 56}. Doklady RAN, 432(5):300–304, 2010. [4] A. V. Zavarnitsine. Finite simple groups with narrow prime spectrum. Sibirean electr. Math. Reports, 6:1–12, 2009. 13 Automorphisms of distance-regular graph with intersection array {121, 90, 1; 1, 30, 121} Konstantin S. Efimov2 , Alexander A. Makhnev1 1 – Krasovskii Institute of Mathematics and Mechanics (Yekaterinburg, Russia) 2 – Ural Federal University (Yekaterinburg, Russia) Keywords: distance-regular graph, automorphism. A.A. Makhnev and M.S. Samoilenko determined parameters of strongly regular graphs with at most 1000 vertices, which may be local subgraphs in antipodal distance-regular graph of diameter 3 with λ = µ. They suggested the program of investigation of antipodal distance-regular graphs of diameter 3 with λ = µ, in which local subgraphs are strongly regular with at most 1000 vertices. In this paper, we consider distance-regular graph with intersection array {121, 90, 1; 1, 30, 121}. It is proved that vertex-symmetric graph with intersection array {121, 90, 1; 1, 30, 121} is arc-transitive with the socle of automorphism group isomorphic Z2 × L2 (121). 14