А.А. Махнев и М.С. Самойленко выделили параметры сильно регулярных графов с не более чем 1000 вершинами, которые могут быть окрестностями вершин в антиподальном дистанционно регулярном графе диаметра 3 с = . Ими же предложена программа исследования вершинно симметричных антиподальных дистанционно регулярных графов диаметра 3 с = , в которых окрестности вершин сильно регулярны с вышеуказанными параметрами. В данной работе рассмотрен граф с массивом пересечений f121; 90; 1; 1; 30; 121g. Доказано, что вершинно симметричный граф с массивом пересечений f121; 90; 1; 1; 30; 121g является реберно симметричным с цоколем группы автоморфизмов, изоморфным Z2 L2(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
Теорема 1. Пусть сильно регулярный граф с параметрами (121; 30; 11; 6), G = Aut( ), g элемент
простого порядка p из G и = Fix(g). Тогда (G) f2; 3; 5; 7; 11g и выполняется одно из следующих
утверждений:
(1) является пустым графом, p = 11 и 1(g) = 0; 121;
(
(
(5) если содержит [a] для некоторой вершины a, то p 6 3, в случае j j = 31 имеем p = 3 и 1(g) = 33l 60, 2 6 l 6 4;
(6) содержит геодезический путь, p 6 7 и в случае p = 7 подграф сильно регулярен с параметрами (16; 9; 4; 6).
Теорема 2. Пусть дистанционно регулярный граф с массивом пересечений f121; 90; 1; 1; 30; 121g,
G = Aut( ), g элемент простого порядка p из G и = Fix(g) содержит по s вершин в t антиподальных
классах. Тогда (G) f2; 3; 5; 7; 11; 13; 23; 61g и выполняются следующие утверждения:
(1) если пустой граф, то p 2 f2; 61g;
(
(5) если p = 7, то t = 10; 17; 24 и в случае t = 10 подграф является дистанционно регулярным с массивом пересечений f9; 6; 1; 1; 2; 9g;
(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.
Следствие. Вершинно симметричный дистанционно регулярный граф с массивом пересечений f121; 90; 1; 1; 30; 121g является реберно симметричным графом с группой автоморфизмов, имеющей цоколь Z2 L2(121).
Заметим, что ввиду границы Дельсарта [2, предложение 4.4.6] максимальный порядок клики в дистанционно регулярном графе с массивом пересечений f121; 90; 1; 1; 30; 121g и спектром 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 и в случае jCj = 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. 1 8 9 Поэтому 1(g) = (30 0(g) + 8 1(g) 1(g) = (3 0(g) + 1(g))=11 3.
Последнее утверждение леммы следует из [3, лемма 1].
3 2(g))=121. Подставляя 2(g) = 121 0(g) 1(g), получим Лемма 2. Пусть A i вершинами из A. Если A ребра, то y0 = 53 y3, если A трехвершинный подграф из , yi число вершин из A, смежных точно с коклика, то y0 = 46 y3, если A объединение изолированной вершины и
геодезический путь, то y0 = 59 y3, а если A клика, то y0 = 64 y3.
Лемма 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;
(
Доказательство. Пусть p > 13. Тогда – сильно регулярный подграф с параметрами (v0; k0; 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. Пусть содержит [a] для некоторой вершины a. Тогда [u] \ содержит 6 вершин из для любой вершины u 2 . Отсюда любая hgi-орбита длины p не содержит геодезических 2-путей, в частности она является кликой или кокликой.
Если p > 7, то [u] \ является 6-кликой и для двух вершин b; c 2 [u] \ подграф [b] \ [c] содержит a, 4 вершины из [u] \ и p верщин из hgi-орбиты, содержащей u, противоречие.
В случае p = 5 подграф [u]\ является кликой, иначе для двух несмежных вершин b; c 2 [u]\ подграф [b] \ [c] содержит a и 5 верщин из hgi-орбиты , содержащей u. В этом случае [u] \ является кокликой, противоречие с тем, что [b2[u]\ ([a] \ [b]) содержит не менее 55 вершин. Если – клика, то [ ( \ [u]) является 11-кликой, противоречие с тем, что a смежна с 6 вершинами этой клики. Значит, – коклика, противоречие с тем, что [u2 ([u] [a]) содержит не менее 120 вершин. Итак, p 6 3.
Если j j = 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 2 подграф (a) \ [b] содержит 0 или 11 вершин. Далее, j j = 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 2 подграф (a) \ [b] содержит 4 или 11 вершин. Далее, j j = 7t + 2, t 6 8, и степень вершины в равна 9; 16; 23. В случае j j = 58 ввиду леммы 2 каждая hgi-орбита длины 7 является кликой, 2(g) = 0, противоречие с леммой 4. В случае j j = 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 и – сильно регулярный граф
с параметрами (
Итак, в нет вершин степени 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 + (j j z). В случае j j = 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 2 подграф содержит a; b, 11 вершин из [a] \ [b], по 11 вершин из [a] [b], [b] [a] и 9 вершин вне a? [ b?.
Если a 2 , то число ребер между (a) и 2(a) равно 120 = 11m + 4(23 m), поэтому m = 4 и j j = 2; 4. Заметим, что вершина из смежна не более чем с 6 вершинами из , поэтому число ребер между и , деленное на 7, не больше 66. С другой стороны, это число не меньше 40 2 + 4, противоречие. Лемма доказана.
Из лемм 3–5 следует теорема 1. 3 183
3(g),
0(g)
Лемма 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;
(
Пусть антиподальный класс. Тогда 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 и дистанционно регулярный граф с массивом пересечений f29; 21; 1; 1; 7; 29g, либо p = 13 и дистанционно регулярный граф с массивом пересечений f17; 12; 1; 1; 4; 17g;
(
(
(
Доказательство. Если s = 4, то каждая вершина из смежна точно с t вершинами из . Пусть p > 3, 1(g) = pw1. Тогда s = 4, 3(g) = 0, j j = 4t, регулярный граф степени t 1 и p делит 122 t.
Если p > 29, то дистанционно регулярный граф с массивом пересечений ft 1; t 32; 1; 1; 30; t 1g, противоречие.
Пусть p = 29. Так как p делит 122 t, то t = 6, подграф (b) содержит 2 вершины из a? и по вершине из [a2]; :::; [a4]. Отсюда дистанционно регулярный граф с массивом пересечений f5; 3; 1; 1; 1; 5g, противоречие.
Пусть p = 23. Так как p делит 122 t, то t = 7; 30, подграф (b) содержит 8 вершины из a? и по 7 вершин из [a2]; :::; [a4]. Отсюда дистанционно регулярный граф с массивом пересечений f29; 21; 1; 1; 7; 29g.
Пусть 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]. Отсюда дистанционно регулярный граф с массивом пересечений f17; 12; 1; 1; 4; 17g.
Пусть 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 подграф является дистанционно регулярным с массивом пересечений f9; 6; 1; 1; 2; 9g.
Пусть p = 5. Так как p делит 122 t, то t = 2; 7; 12; 17; 22; 27. В случае t = 7 подграф является объединением изолированных 7-клик и, быть может, графа без треугольников. Пусть (a) = fb1; :::; b6g. Без ограничения общности, (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) = fb1; :::; b4g. Без ограничения общности, (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 f2; 4g и t четно. Заметим, что для любых двух вершин a; b 2 имеем j (a) \ [b]j 2 f0; 2; :::; 30g, любая вершина из смежна с четным числом вершин из . Так как 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 2 , подгруппа H = GfF g имеет индекс 122 в G и jH : Haj = 4. Из теоремы 2
следует, что f2; 61g (G) f2; 3; 5; 7; 11; 13; 23; 61g и jGj не делится на 132 и на 113.
Лемма 10. Выполняются следующие утверждения:
(1) если f элемент порядка 61 из G, g элемент простого порядка p 6= 61 из CG(f ), то p = 2 и
3(g) = 488;
(
Доказательство. Допустим, что 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. Заметим, что 236 1 не делится на 61.
Пусть Q = O2(G) 6= 1. Тогда порядки Q-орбит на множестве антиподальных классов делят 2. Если порядок некоторой Q-орбиты равен 1, то Q фиксирует каждый антиподальный класс и jQj делит 4, противоречие с утверждением (1). Теперь подгруппа Q0 индекса 2 из Q фиксирует F и подгруппа Q1 индекса 16 из Q фиксирует F поточечно. Так как k = 121, то Q1 фиксирует вершину b из [a]. Подгруппа Q2 индекса 16 из Q1 фиксирует a; b и по 6 вершин из [b] \ [x] для x 2 F . Аналогично, подгруппа Q3 индекса 16 из Q1 фиксирует a; b и по 6 вершин из [a] \ [y] для y 2 F (b). Теперь любая инволюция из Q2 \ Q3 фиксирует не менее 2 + 6 + 36 антиподальных классов и по теореме 2 имеем Q2 \ Q3 = 1. Отсюда jQj 6 36, противоречие с действием элемента порядка 61 на Q. Из утверждения (1) следует, что S(G) = O2(G) и jO2(G)j делит 4.
Пусть T цоколь группы G = G=O2(G). Ввиду теоремы из [4], группа T изоморфна L2(35), U5(
Так как T содержит подгруппу индекса, делящего 122, то группа T изоморфна L2(121) (и TfF g расширение группы порядка 121 с помощью группы порядка 60). Лемма доказана.
Докажем следствие. Ввиду леммы 10, подгруппа T изоморфна L2(121), SL2(121), Z2 L2(121), Z2 SL2(121) или K L2(121), где jKj = 4.
Пусть подгруппа H изоморфна SL2(121) или L2(121). Тогда наименьший индекс в H её максимальной подгруппы равен 122, поэтому H действует транзитивно на множестве антиподальных классов. Понятно, что H нормальная подгруппа, поэтому G действует на множестве H-орбит, и, значит, H-орбиты являются изоморфными подграфами порядка не меньше 122. Есть такие варианты:
1. Четыре H-орбиты порядка 122, на которых H действует 2-транзитивно. Нетрудно понять, что это невозможно.
2. Две H-орбиты порядка 244. Стабилизатор антиподального класса HfF g и стабилизатор вершины 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. with intersection array Konstantin S. Efimov2, Alexander A. Makhnev1 1 – Krasovskii Institute of Mathematics and Mechanics (Yekaterinburg, Russia) 2 – Ural Federal University (Yekaterinburg, Russia)
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 f121; 90; 1; 1; 30; 121g. It is proved that vertex-symmetric graph with intersection array f121; 90; 1; 1; 30; 121g is arc-transitive with the socle of automorphism group isomorphic Z2 L2(121).