=Paper=
{{Paper
|id=Vol-1662/alg4
|storemode=property
|title=Автоморфизмы дистанционно регулярного графа с массивом пересечений {121, 100, 1; 1, 20, 121}(Automorphisms of distance-regular graph with intersection array {121, 100, 1; 1, 20, 121})
|pdfUrl=https://ceur-ws.org/Vol-1662/alg4.pdf
|volume=Vol-1662
|authors=Alexander A. Makhnev,Mikhail S. Samoilenko
}}
==Автоморфизмы дистанционно регулярного графа с массивом пересечений {121, 100, 1; 1, 20, 121}(Automorphisms of distance-regular graph with intersection array {121, 100, 1; 1, 20, 121})==
https://ceur-ws.org/Vol-1662/alg4.pdf
Автоморфизмы дистанционно регулярного графа
с массивом пересечений {121, 100, 1; 1, 20, 121}
А.А. Махнев1 М.С. Самойленко2
makhnev@imm.uran.ru ghost1212@mail.ru
1 – ИММ УрО РАН (Екатеринбург) 2 – УрФУ (Екатеринбург)
Аннотация
А.А. Махнев и М.С. Самойленко выделили параметры сильно регу-
лярных графов с не более чем 1000 вершинами, которые могут быть
окрестностями вершин в антиподальном дистанционно регулярном
графе диаметра 3 с λ = µ. Ими же предложена программа исследо-
вания вершинно симметричных антиподальных дистанционно регу-
лярных графов диаметра 3 с λ = µ, в которых окрестности вершин
сильно регулярны с вышеуказанными параметрами. В данной рабо-
те рассмотрен граф с массивом пересечений {121, 100, 1; 1, 20, 121}.
Доказано, что вершинно симметричный граф с массивом пересече-
ний {121, 100, 1; 1, 20, 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 с λ = µ.
Продолжается программа исследования вершинно симметричных антиподальных дистанционно ре-
гулярных графов диаметра 3 с λ = µ, в которых окрестности вершин сильно регулярны с пара-
метрами из заключения предложения [1]. В данной работе рассмотрен граф с массивом пересечений
{121, 100, 1; 1, 20, 121}.
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
21
Теорема. Пусть Γ — дистанционно регулярный граф с массивом пересечений {121, 100, 1; 1, 20, 121},
G = Aut(Γ), g — элемент простого порядка p из G и Ω = Fix(g) содержит по s вершин в t антиподальных
классах. Тогда π(G) ⊆ {2, 3, 5, 11, 61} и выполняются следующие утверждения:
(1) если Ω — пустой граф и p ∈ {2, 3, 61};
(2) если p > 7, то p = 11, Ω — антиподальный класс и α1 (g) = 22l;
(3) если p = 5, то либо (1) s = 1, Ω является t-кликой, t = 2, 7, 12, либо s = 6, t = 2, Ω является
объединением шести изолированных ребер или t = 7, Ω является объединением шести изолированных
7-клик, или t = 12;
(4) если p = 3, то t = 3l + 2 и либо s = 6, 14 6 t 6 20, причем в случае t = 14 граф Ω является
дистанционно регулярным с массивом пересечений {13, 10, 1; 1, 2, 13}, либо s = 3, 8 6 t 6 38, причем в
случае t = 8 граф Ω является дистанционно регулярным с массивом пересечений {7, 4, 1; 1, 2, 7};
(5) если p = 2, то каждая вершина из Γ − Ω смежна с четным числом вершин из Ω и либо s = 6,
t = 2, 4, ..., 20, либо s = 4, 2 6 t 6 30, либо s = 2, 2 6 t 6 42, причем в случае t = 42 граф Ω дистанционно
регулярен с массивом пересечений {41, 20, 1; 1, 20, 41}.
Следствие. Вершинно симметричный дистанционно регулярный граф с массивом пересечений
{121, 100, 1; 1, 20, 121} является реберно симметричных графом с группой автоморфизмов, имеющей цо-
коль Z2 × L2 (121).
2 Автоморфизмы графа с массивом пересечений {121, 100, 1; 1, 20, 121}
В этом параграфе Γ — дистанционно регулярный граф с массивом пересечений {121, 100, 1; 1, 20, 121} и
спекром 1211 , 11305 , −1121 , −11305 , G = Aut(Γ) и g ∈ G.
Заметим, что ввиду границы Дельсарта (предложение 4.4.6 [2]) максимальный порядок клики в дистан-
ционно регулярном графе с массивом пересечений {121, 100, 1; 1, 20, 121} не больше 1 − k/θd = 1 + 121/11 =
12. Если C является 12-кликой из Γ, то каждая вершина вне C смежна с 0 или с b1 /(θd + 1) + 1 − k/θd =
−10 + 12 = 2 вершинами из C.
Лемма 1. Пусть ψ — мономиальное представление группы G в GL(732, C), χ1 — характер проекции
ψ на подпространство собственных векторов размерности 305, отвечающих собственному значению 11,
χ2 — характер проекции ψ на подпространство размерности 121, тогда χ1 (g) = (28α0 (g) + 3α1 (g) −
5α3 (g))/66 − 61/11, χ2 (g) = (α0 (g) + α3 (g))/6 − 1. Если |g| = p — простое число, то χ1 (g) − 305 и χ2 (g) − 121
делятся на p.
Доказательство. Имеем
1 1 1 1
305 305/11 −61/11 −61
Q= .
121 −1 −1 121
305 −305/11 61/11 −61
Поэтому χ1 (g) = (5α0 (g)+5α1 (g)/11−α2 (g)/11−α3 (g))/12. Подставляя α2 (g) = 732−α0 (g)−α1 (g)−α3 (g),
получим χ1 (g) = (28α0 (g) + 3α1 (g) − 5α3 (g))/66 − 61/11.
Аналогично, χ2 (g) = (121α0 (g) − α1 (g) − α2 (g) + 121α3 (g))/732. Подставляя α1 (g) + α2 (g) = 732 − α0 (g) −
α3 (g), получим χ2 (g) = (α0 (g) + α3 (g))/6 − 1.
Остальные утверждения леммы следуют из леммы 1 [3]. Лемма доказана.
Лемма 2. Если Ω — пустой граф, то либо p = 61, α1 (g) = 122 и α2 (g) = 610, либо p = 3, α3 (g) = 18l −6,
α1 (g) = 30l + 90 + 66m, α2 (g) = 612 − 48l − 66m, l 6 41 и 8l + 11m 6 102, либо p = 2, α3 (g) = 12l,
α1 (g) = 20l + 12 + 44m и α2 (g) = 720 − 32l − 44m, l 6 61 и 8l + 11m 6 180.
Доказательство. Пусть Ω — пустой граф и αi (g) = pwi для i > 0. Так как v = 61 · 12, то p ∈ {2, 3, 61}.
Пусть p = 61. Тогда α3 (g) = 0 и χ1 (g) = 61(w1 − 2)/22. Отсюда w1 = 22l + 2, α1 (g) = 122 и α2 (g) = 610.
Пусть p = 3. Тогда χ2 (g) = α3 (g)/6 − 1 сравнимо с 1 по модулю 3. Отсюда α3 (g) = 18l − 6. Далее,
χ1 (g) = (3w1 −5(6l−2)−122)/22 сравнимо с 2 по модулю 3, поэтому w1 = 10l+30+22m, α1 (g) = 30l+90+66m
и α2 (g) = 612 − 48l − 66m, l 6 41 и 8l + 11m 6 102.
Пусть p = 2. Тогда χ2 (g) = α3 (g)/6 − 1, α3 (g) = 12l и число χ1 (g) = (w1 − 10l − 61)/11 нечетно. Поэтому
w1 = 10l + 6 + 22m и α1 (g) = 20l + 12 + 44m и α2 (g) = 720 − 32l − 44m.
22
В леммах 3–6 предполагается, что a ∈ Ω, F — антиподальный класс, содержащий вершину a, F ∩ Ω =
= {a, a2 , ..., as }, b ∈ Ω(a). Черех F (x) будем обозначать антиподальный класс, содержащий вершину x.
Лемма 3. Если число p больше 5, то p = 11, Ω — антиподальный класс и α1 (g) = 22l.
Доказательство. Если s = 6, то каждая вершина из Γ − Ω смежна точно с t вершинами из Ω.
Пусть p > 5, α1 (g) = pw1 . Тогда s = 6, α3 (g) = 0, |Ω| = 6t, Ω — регулярный граф степени t − 1 и p делит
122 − t.
Если p > 19, то Ω — дистанционно регулярный граф с массивом пересечений {t − 1, t − 22, 1; 1, 20, t − 1},
противоречие.
Пусть p = 19. Так как p делит 122 − t, то t = 8, подграф Ω(b) содержит 2 вершины из a⊥ и по вершине из
[a2 ], ..., [a6 ], поэтому Ω – дистанционно регулярный граф с массивом пересечений {7, 5, 1; 1, 1, 7}, окрестность
вершины в Ω – объединение изолированных ребер, противоречие.
Пусть p = 17. Так как p делит 122 − t, то t = 3, 20. Для вершины b ∈ Ω(a) подграф Ω(b) содержит
4 вершины из a⊥ и по 3 вершины из [a2 ], ..., [a6 ], поэтому Ω дистанционно регулярный граф с массивом
пересечений {19, 15, 1; 1, 3, 19}. Так как t = 20, то каждая hgi-орбита длины 17 является кокликой. Поэтому
χ1 (g) = (28 · 20 − 204 − 61)/11, противоречие.
Пусть p = 13. Так как p делит 122 − t, то t = 5, 18. Для вершины b ∈ Ω(a) подграф Ω(b) содержит 8
вершин из a⊥ и по 7 вершин из [a2 ], ..., [a6 ], противоречие.
Пусть p = 11. Так как p делит 122 − t, то t = 1, 12. В случае t = 12 подграф Ω(b) содержит 10 вершин
из a⊥ и по 9 вершин из [a2 ], ..., [a6 ], противоречие. В случае t = 1 имеем χ1 (g) = (28 + α1 (g)/2 − 61)/11 и
α1 (g) = 22l.
Пусть p = 7. Так как p делит 122 − t, то t = 3, 10, 17. Для вершины b ∈ Ω(a) подграф Ω(b) содержит 7
вершин из a⊥ и по 6 вершин из [a2 ], ..., [a6 ], противоречие.
Лемма 4. Если p = 5, то либо
(1) s = 1, Ω является t-кликой, t = 2, 7, 12, либо
(2) s = 6, t = 2, Ω является объединением шести изолированных ребер или t = 7, Ω является объеди-
нением шести изолированных 7-клик, или t = 12.
Доказательство. Пусть p = 5. Тогда s = 1, 6. Так как p делит 122 − t, то t = 2, 7, 12, 17.
Если s = 1, то Ω является t-кликой, t = 2, 7, 12.
Пусть s = 6. В случае t = 2 граф Ω является объединением шести изолированных ребер.
В случае t = 7 граф Ω является объединением изолированных 7-клик и, быть может, графа ∆ без
треугольников. Пусть ∆(a) = {b1 , ..., b6 }. Без ограничения общности, ∆(bi ) содержит 5 вершин из [ai+1 ].
Противоречие с тем, что вершина из ∆(b1 ) ∩ [a2 ] должна быть смежна с 5 вершинами из ∆(a).
Лемма 5. Если p = 3, то t = 3l + 2 и либо
(1) s = 6, 14 6 t 6 20, причем в случае t = 14 граф Ω является дистанционно регулярным с массивом
пересечений {13, 10, 1; 1, 2, 13}, либо
(2) s = 3, 8 6 t 6 38, причем в случае t = 8 граф Ω является дистанционно регулярным с массивом
пересечений {7, 4, 1; 1, 2, 7}.
Доказательство. Пусть p = 3. Так как 3 делит 122 − t, то t = 3l + 2. Далее, s = 3, 6. Для вершины
b ∈ Ω(a) подграф Ω(b) содержит от 3 до 21 вершин из a⊥ и от 2 до 20 вершин из [ai ] для i > 2.
Если t = 2, то Ω — объединение трех или шести изолированных ребер. Противоречие с тем, что λ = 20
не делится на 3.
Пусть t > 5. Если s = 6, то 14 6 t 6 20, причем в случае t = 14 граф Ω является дистанционно
регулярным с массивом пересечений {13, 10, 1; 1, 2, 13}.
Если s = 3, то число ребер между Ω и Γ − Ω равно 3t(122 − t), но не больше 6(122 − t)20, поэтому
8 6 t 6 38, причем в случае t = 8 граф Ω является дистанционно регулярным с массивом пересечений
{7, 4, 1; 1, 2, 7}.
Лемма 6. Если p = 2, то каждая вершина из Γ − Ω смежна с четным числом вершин из Ω и либо
(1) s = 6, t = 2, 4, ..., 20, либо
(2) s = 4, 2 6 t 6 30, либо
(3) s = 2, 2 6 t 6 42, причем в случае t = 42 граф Ω дистанционно регулярен с массивом пересечений
{41, 20, 1; 1, 20, 41}.
23
Доказательство. Пусть p = 2. Тогда s ∈ {2, 4, 6} и t четно. Заметим, что для любых двух вершин
a, b ∈ Ω имеем |Ω(a) ∩ [b]| ∈ {0, 2, ..., 20}, любая вершина из Γ − Ω смежна с четным числом вершин из Ω.
Так как α3 (g) = t(6 − s), то χ2 (g) = t − 1, t четно, α1 (g) + α2 (g) = 122 − t и χ1 (g) = (11st/2 + α1 (g)/2 −
5t − 61)/11 и α1 (g) + t − 1 делится на 11.
Если s = 6, то t = 2, 4, ..., 20.
Если s = 4, то число ребер между Ω и Γ − Ω равно 4t(122 − t), но не больше 6(122 − t)20, поэтому
2 6 t 6 30.
Если s = 2, то число ребер между Ω и Γ − Ω равно 2t(122 − t), но не больше 6(122 − t)20, поэтому
2 6 t 6 60. С другой стороны, Ω(b) содержит не более 21 вершины из a⊥ и не более 20 вершин из [a2 ],
поэтому t 6 42, причем в случае t = 42 подграф Ω является графом Тэйлора с массивом пересечений
{41, 20, 1; 1, 20, 41} и Ω(b) – сильно регулярный граф с параметрами (41,20,9,10). Лемма, а вместе с ней и
теорема доказаны.
3 Вершинно симметричный случай {121, 100, 1; 1, 20, 121}
Пусть группа G действует транзитивно на множестве вершин графа Γ. Тогда подгруппа G{F } имеет
индекс 122 в G. Из теоремы следует, что {2, 3, 61} ⊆ π(G) ⊆ {2, 3, 5, 11, 61} и |G| не делится на 113 .
Лемма 7. Выполняются следующие утверждения:
(1) если f — элемент порядка 61 из G, то CG (f ) = hf i;
(2) S(G) = O2 (G) и в G нет подгрупп порядка 3, полурегулярных на каждом антиподальном классе;
(3) цоколь T̄ группы Ḡ = G/O2 (G) изоморфен L2 (35 ), L2 (112 ).
Доказательство. Допустим, что g — элемент простого порядка p 6= 61 из CG (f ). Тогда α1 (f ) = 122 и
α2 (f ) = 610. Так как f действует без неподвижных точек на Ω, то ввиду теоремы Ω — пустой граф, p = 2
и числа α3 (g) = 12l, α1 (g) = 20l + 12 + 44m, α2 (g) = 720 − 32l − 44m делятся на 61. Отсюда 12 + 44m и
720 − 44m делятся на 61, противоречие.
Пусть Q = Op (G) 6= 1. Если p = 3, то каждый элемент порядка 3 из Q действует без неподвижных точек
на любом антиподальном классе. Противоречие с тем, что 3 не делит 122.
Теперь ввиду утверждения (1) число p не равно 61 и S(G) является 2-группой.
Пусть T̄ — цоколь группы Ḡ = G/O2 (G). Так как 113 не делит |G|, то ввиду теоремы 1 [4] группа T̄
изоморфна L2 (35 ), L2 (112 ). Лемма доказана.
Докажем следствие. Так как T̄ содержит подгруппу индекса, делящего 122, то группа T̄ изоморфна
L2 (121) (и T̄{F } — расширение группы порядка 121 с помощью группы порядка 60). Отсюда |S(G)| делит 2.
Компьютерные вычисления в GAP показывают, что цоколь группы G изоморфен Z2 ×L2 (121) и Γ является
реберно симметричным графом. Следствие доказано.
Работа выполнена при поддержке РНФ (проект 14-11-00061).
Список литературы
[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.
24
Automorphisms of distance-regular graph with intersection array
{121, 100, 1; 1, 20, 121}
Alexandr A. Makhnev1 , Mikhail S. Samoilenko2
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 graph 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, 100, 1; 1, 20, 121}. It is proved that vertex-symmetric graph with intersection array
{121, 100, 1; 1, 20, 121} is arc-transitive with the socle of automorphism group isomorphic Z2 × L2 (121).
25