Автоморфизмы сильно регулярного графа с параметрами (1197, 156, 15, 21)
Автор: Биткина Виктория Васильевна, Гутнова Алина Казбековна, Махнев Александр Алексеевич
Журнал: Владикавказский математический журнал @vmj-ru
Статья в выпуске: 2 т.17, 2015 года.
Бесплатный доступ
Пусть $3$-$(V,K,\Lambda)$ схема ${\cal E}=(X,{\cal B})$ является расширением симметричной $2$-схемы. Тогда либо ${\cal E}$ является адамаровой $3$-$(4\Lambda+4,2\Lambda+2,\Lambda)$ схемой, либо $V=(\Lambda+1)(\Lambda^2+5\Lambda+5)$ и $K=(\Lambda+1)(\Lambda+2)$, либо $V=496$, $K=40$ и $\Lambda=3$. Дополнительный граф к блочному графу $3$-$(496,40,3)$ схемы сильно регулярен с параметрами $(6138,1197,156,252)$ и имеет сильно регулярные окрестности вершин с параметрами $(1197,156,15,21)$. В работе найдены автоморфизмы сильно регулярного графа с параметрами $(1197,156,15,21)$. Доказано, что указанный граф не является реберно симметричным.
Сильно регулярный граф, реберно симметричный граф, группа автоморфизмов графа
Короткий адрес: https://sciup.org/14318501
IDR: 14318501
Текст научной статьи Автоморфизмы сильно регулярного графа с параметрами (1197, 156, 15, 21)
a b — вершшты графа, Г. то ттерез d(a, b) обозначается раеетоянне между a ii b, а через ri (a) — подграф графа, Г. индуцированный множеством вершин, которые находятся в Г на расстоянии i от вершины а. Подграф Г1(a) называется окрестиостьто вершины a и обозначается через [а]. Через а± обозначаете?я подграф {a} U [а], являющийся шаром a
Граф Г назвшаетея сильно регулярным графом с параметрами (v, k, А,^). если Г содержит v вершин, является регулярным степени k. каждое ребро Г лежит точно в А треугольниках и для любых двух несмежных вершин a, b подграф [a] П [b] содержит µ
Система нинндентпостн ( X, B ) с множеством точек X и множеством блоков B называется t-(V,K, Л) ctcmoi 1. если | X | = V. каждый блок содержит ровно K точек и любые t точки лежат ровно в Л блоках. Любая 2-схема, является (V,B,R,K, Л) схемой. где B — R VR = BK
(V — 1)Л = R(K — 1). Схема, называется с 'симметричной. если B = V. Схема, называется квазисимметричной, если для любых двух блоков B,C Е B имеем | В П C | G {x,y}. Числа x, у называются числами пересечений квазисимметричной схемы, и предполагается, что x < у.
-
1 Работа выполнена при финансовой поддержке Российского научного фонда, проект 14-11-00061 (теорема), и соглашения между Министерством образования и пауки Российской Федерации и Уральским федеральным университетом, соглашение № 02.А03.21.0006 от 27.08.2013 (следствие).
Блочный граф квазисимметричной схемы (X, B) в качестве вершин имеет блоки схемы II два блока B,C Е B смежш>i. если |В П C| = у.
Предложение 1. Блочный граф квазисимметричной (V, B, R, K, Л) схемы сильно регулярен с собственными значениями k = ((R — 1)K — xB + x)/(y — x) кратности 1, k = (R — K — Л + x)/(y — x) крапюстп V — 1 ii k = —(K — x)/(y — x) крапюстп B — V.
Производной схемой для t- (V, K, Л) схемы D = (X, B) в точке x Е X называется схема, Dx с миожеством точек Xx = X — {x} и миожеством блоков Bx = {B — {x} : x Е B Е B}. Схема E называется расширением схемы D если производная схемы E в каждой точке изоморфна D. Вычетом схемы D в б.токе B называется схема, DB с множеством точек X B = X — {x} ii множеством блоков BB = {C Е B} : |В П C | = 0}. Хорошо известно, что проективная плоскость расширяема, только если ее порядок равен 2 или 4. П. Камерон [1, теорема, 1.35] описал расширения симметричных 2-схем.
Предложение 2. Пусть 3-(V, K, Л) схема E = (X, B) является расширением симметричной 2-схемы. Тогда верно одно из утверждений:
-
(1) E является адамаровой 3-(4Л + 4,2Л + 2, Л) схемой:
-
(2) V = (Л + 1)(Л2 + 5Л + 5) 1 1 K = (Л + 1)(Л + 2);
-
(3) V = 496. K = 40 ii Л = 3.
В случае (3) имеем R = V — 1 = 495. B = VR/K = 496 • 495/40 = 6138 и дополнительный граф к блочному графу схемы имеет параметры (6138,1197,156, 252) и спектр 11971,95642, —105495. Отсюда максимальный п<зрядок коклики не больше vm/(k + m) = 6138 • 105/1302 = 495
Цветковича (см. лемму 1). Дополнительный граф к блочному графу 3-(496,40, 3) схемы назовем монстром Камерона. В [2] доказано
Предложение 3. Для монстра Камерона Г выполняются следующие утверждения:
-
(1) окрестность любой вершины в графе Г — сильно регулярный граф с параметрами (1197,156,15, 21) и спектром 1561, 9741, —15455, причем порядок коклики в этом графе по больше 105:
-
(2) множеств о блоков Cx. содержат них точку x схе мы E. явяг тется 495-кокдпкой графа Г, для которой достигается равенство в границах Хофмана и Цветковича-
-
(3) подграф Г — Cx сильно рсгулярсп с параметрами (5643,1092,141, 228) я спектром 10921. 95148. —96494;
-
(4) для радиишых точек x. у схе мы E им сем |Cx П Cy | = 39. причем для коклики Cx — Cy графа Г — Cy достигается равенство в границе Хофмана.
В данной работе найдены автоморфизмы сильно регулярного графа, с параметрами (1197, 156, 15, 21)
Теорема. Пусть Г — сильно регулярный граф с параметрами (1197,156,15, 21), G = ЛиЦГ). g — элемент простого порядка p из G 11 Q = Fix(g). Тс>гда |Q| 6 171. n(G) С {2, 3, 5, 7,11,13,19} и выполняется одно из следующих утверждений:
-
(1) Q — пустой граф. либо
-
(i) p = 3 11 a1(g) = 721. либо
-
(ii) p = 7 11 a1(g) = 1681 — 21. либо
-
(iii) p = 19 1 1 ai(g) = 4561 + 171;
-
-
(2) Q явдяется n-клпкой. либо
-
(i) p = 13. n = 1 1 1 ai(g) = 3121 + 156. либо
-
(ii) p = 2. n = 9 11 a1(g) = 481 + 12 11. mi n = 11 11 a1(g) = 321 — 12. либо
-
(iii) p = 5. n = 2 11 a1(g) = 1201 + 45 11. th n = 7 11 a1(g) = 1201 — 30;
-
-
(3) Q является 3t + 1-кок.ш шой. p = 3 11 a1(g) = 721 + 12 — 45t;
-
(4) Q содержит геодезический 2-путв и p 6 13.
-
2. Автоморфизмы графа с параметрами (1197,156,15, 21)
Следствие. Сильно регулярный граф с параметрами (1197,156,15, 21) не является реберно симметричным.
Приведем некоторые вспомогательные результаты.
Лемма 1. Пусть Г является сильно регулярным гра(}>ом с параметрами (v,k,A,^) и неглавными собственными значениями r, s, s < 0. Еели D — индуцированный регулярный подграф из Г степепп d на w вершинах, то
w(k - d) s 6 d - 6 r, v-w причем одно из равенств достигается тогда и только тогда, когда каждая вершина из Г — D смежна точно с w(k — d)/(v — w) вершшшмп из D.
C Это утверждение хорошо известно (см., например. [3. §2]). B
Γ (1197, 156, 15, 21)
тром 1561. 9741. — 15455. Е(?ли D — нндупированный регулярпый подграф из Г степени d w d - 9 6 w(156 - d)/(1197 - w) 6 d + 15
CΓ
Γ-CC
Лемма 2 [4, теорема 3.2]. Пусть Г является сильно регулярным графом с параметрами (v,k,A,^) ii собственныеш значениями k. r. —m. Если g — автое юрфпзм Г и П = Fix(g), то |П| 6 v • max{A, p}/(k — r).
(1197, 156, 15, 21)|Ω|
1197/7 = 171
Доказательство теорем опирается на метод Хигмена работы с автоморфизмами сильно регулярного графа, представленный в третьей главе монографии Камерона [5]. При
Γ (X, {R0, R1, R2})X
R0 X R1Γ
R2 — отношение смежности в дополнительном графе Г. Ес ли P и Q — первая и вторая матрицы собственных значений схемы, то
/ 1 11 А
P= k rs , v-k- 1 -r- 1 -s- 1
PQ = QP = vI v k r sΓ
-
1 f v-f-1
Q
G = Aut(Γ)Γ
ψ G GL(v, C)
Cvψ(G)
W0 W1 W2 Γχi
ψWi g ∈ G
2 χi(g) = v-1 Qijαj(g), j=0
αj (g) x X d(x, xg) = j
Лемма 3. Пусть Г — сильно регулярный граф с параметрами (1197,156,15,21). G = Aut(Г), g — элемент простого порядка p in G и \1 характер, полученный при проектировании ^(G) па подпространство размерности 741. Тогда
Xi ( g ) = (5 ао ( g ) + ai ( g ) / 3 - 57) / 8 , ai ( g ) = ai ( gl )
для любого 1. не кратного р. ii 741 — Xi ( g ) л<'™т ся па р.
C Рассмотрим силык) регулярный граф Г с параметрами (1197 , 156 , 15 , 21). Тогда
/ 1 1 1 \
Q = 741 171 / 4 — 57 / 8 ,
\ 455 — 175 / 4 49 / 8
и значение характера, полученного при проектировании на. подпространство размерности 741 равно Xi(g) = (13ao(g) + 3a1(g)/4 — a2(g))/8)/21. Подставляя в эту формулу значение a2(g) = v — ao (g) — a1 (g). пола "наем Xi (g) = (5ao (g) + a1(g)/3 — 57)/8.
B
Г
(1197,156,15, 21). G = Aut(Г). g — элемент простого порядка р из G ii x i — характер, полученный при проектировании ^(G) на подпространство размерности 741.
Лемма 4. Выполняются следующие утверждения:
-
(1) если П — пустой граф. то либо
-
( i ) р = 3 11 a1 ( g ) = 721. либо
-
( ii ) р = 7 11 a1 ( g ) = 168 1 — 21. либо
-
( iii ) р = 19 с I ai ( g ) = 456 1 + 171;
-
-
(2) если П является n-кликой. то либо
-
( i ) р = 13. n = 1 с I ai ( g ) = 312 1 + 156. либо
-
( ii ) р = 2. n = 9 11 a1 ( g ) = 48 1 + 12 ii.mi n = 11 ii a1 ( g ) = 32 1 — 12. либо
-
( iii ) р = 5. n = 2 11 a1 ( g ) = 120 1 + 45 ii.th n = 7 ii a1(g) = 120 1 — 30;
-
-
(3) если П является m-кокликой. то р = 3. m = 3 t + 1 ii a1 ( g ) = 72 1 + 12 — 45 t ;
-
(4) если П является объедппеппем m (m > 2) изолирован!шх клик, то р = 3 и П — коклика.
C Пусть П — пустой граф. ai ( g ) = pwi. Так как 1197 = 9 • 7 • 19. т о р Е { 3 , 7 , 19}.
Пусть р = 3. Тогда Xi ( g ) = ( wi — 57) / 8 1i a1 ( g ) = 721.
Пусть р = 7. Тогда X1 ( g ) = (7 w1 / 3 — 57) / 8 1 i a1 ( g ) = 168 1 — 21.
Пусть р = 19. Toгда X i (g) = 19(w 1 /3 — 3)/8 1 i a1 (g) = 4561 + 171. Утверждение (1) доказано.
Пусть П является n-кликой. Если n = 1 и П = {a}, то р делит 156 и 1040, поэтому р = 2,13. В случае р = 2 для u Е Г — П подграф [u] П [ug] содержит 15 или 21 вершин, поэтому [ u ] содержит вершину из П. противоречие.
В случае р = 13 им еем Xi ( g ) = (5 + 13 wi/ 3 — 57) / 8 1 i a1 ( g ) = 312 1 + 156.
Пуств n > 2 11 a, b Е П. Так как g действует полурегулярио на [ a ] — b^ то р делит 140. 900 ii 17 — пир = 2 , 5. В случае р = 2 каждая вершина из Г — П смежна, с нечетным числом вершин из П. то n = 9 , 11 В случае n = 9 имеем xi ( g ) = (45 + 2 w1/ 3 — 57) / 8 н a1 ( g ) = 48 1 + 12. В случае n = 11 имеем х1 ( g ) = (55 + 2 w1 / 3 — 57) / 8 1 1 a1 ( g ) = 32 1 — 12. В случае р = 5 полз-шш n = 2 1 1 a1 ( g ) = 120 1 + 45 ii.th n = 7 1 1 a1 ( g ) = 120 1 — 30.
Пуств П является т-кок.ижой. 0 < t 6 34. Ели a, b Е П. то g действует по.луре- [ a ] П [ b ] [ a ] — [ b ] р р = 3 m = 3 t + 1
Х1 ( g ) = (15 t + 5 + w1 — 57) / 8 1 1 a1 ( g ) = 72 1 + 12 — 45 t.
Пусть Q является об'ьедниепием m (m > 2) изолпровапивix клик. Если a. с — несмежные вершины и:з Q. то g действует полурегулярпо на [a] П [с] 1i p делит 21.
Пусть a. b — смежные вершины из клики, лежащей в Q. Так как g действует полурегулярно на [ a ] — b ^ то p делит 140. Отетода p = 7 и порядки изолированных клик в Q равны 3 или 10. Противоречие с тем, что 7 не делит 900 — 3. B
Лемма 5. Если Q содержит геодезический путь b, а, с, то выполняются следующие утверждения:
-
(1) Г не содержит собственных сиявно регулярных подграфов D с Xd = 15 ii дд = 21;
-
(2) если Q содержит [ a ] для иекоторой вершины a € Q. то p = 2 , 5. Q = a± с i a1 ( g ) = 0;
-
(3) p 6 13.
C Пуств Г содержит собственный си.тыю регулярный подграф D с Xd = 15 1i дд = 21. Тогда 36 + 4(kD — 21) = 4s2. kD = s 2 + 12. D имеет неглавные собственивте 'значения s — 3. — (s + 3) ii кратноств s — 3 равна, (s + 2)(s 2 + 12)(s 2 + s + 15)/42s. Отетода s = 4,10 ii нарушается прямоугольное соотношение.
Если Q содержит [a] для иекоторой вершины a € Q. то p = 2, 5,13. Q = a ± 1i a 1 (g) = 0. Так как вершина из Г — Q смежна, не более нем с одной вершиной в любой орбите uhgi ДЛИНЫ p, то p = 13.
Если p > 23. то Q — сильно регулярный подграф с Xq = 15 1i +q = 21. противоречие.
Если p = 19. т о Xq = 15 11 +q = 2, 21. Да лее. | Q | = 19, 38,... , 171 ii етепеив вершины в Q равна, 42, 80,... Пу ств Q2(a) соде]зжит у вершин, смежпых с 21 вершинами из Q(a). Если степень вершины a в графе Q не меньше 80, то число ребер между Q(a) и Q2(a) не меньше 80 • 26. но не больше 90 • 21. противоречие. Итак. Q — регулярный граф степени 42. По лемме 1 имеем 33 6 114 | Q | /(1197 — | Q | ) 6 57 и 1881 6 7 | Q |, противоречие.
Если p = 17. т о Xq = 15 1 1 +q = 4,21. | Q | = 24,41,..., 160. степени вершин в Q равны 20. 54. 88. Пз -ств у — число вершин в Q2(a). смежных с 21 вершиной из Q(a). k 2 = | Q 2 (a) |. П>-ств D — регулярны!i подграф из Г степешi 16 на w вершинах. По лемме 1 имеем 43 6 w 6 210. Поэтому в Q нет вершин степени 20.
Если a — вершина (/тепепп 88 в Q. то число ребер между Q( a ) ii Q 2 ( a ) не меивше 38 • 88 21 k2 k2 6 71
Значит. Q — регулярный граф степени 54. По лемме 1 имеем неравенства 45 6 102 | Q |/ (1197 — | Q | ) 6 69 ii 2565 6 7 | Q |. противорение. B
-
3. Доказательство следствия
Пуств Г — сильно регулярный граф с параметрами (1197 , 156 , 15 , 21) 1iG = Aut(F) Г
n ( G ) С { 2 , 3 , 5 , 7 , 11 , 13 , 19}. Далее, для смежпых вершин a. b имеем |G : Ga | = 63 • 19 ii |Ga : Ga,b| = 156.
Лемма 6. Пуств f — элемемт порядка 19 из G. g — элемент простого порядка p < 19 из Cg (f). Тогда выполняется одно из следующих утверждений:
-
(1) p = 3. Q — пусто!1 граф) п a1 ( g ) = 627;
-
(2) p = 7. | Q | = 133 11 ai ( g ) = 0;
-
(3) p = 5. |Q| = 57 11 a1(g) = 1140 11.th |Q| = 152 11 a1(g) = 1201
-
(3) p = 3. |Q| = 57 11 a1(g) = 456s + 228 11.th |Q| = 114 11 a1(g) = 456s + 57 11.th |Q| =171
11 a1 ( g ) = 456 s + 342;
-
(4) p = 2. |Q| = 38 11 a1(g) = 912s + 57 11.th |Q| = 57 11 a1(g) = 798. 11.th |Q| = 95
C Пуств g — элемент простого порядка p < 19 11 з Co(f ). Тогд;1 либо p = 3. Q — пустой граф ii a1 ( g ) = 0. hi 160 | Q | = 19 t. t 6 9 ii p дел iit 63 — t. Далее. xi ( g ) = (95t + a1(g)/3 — 57)/8. Toгда p = 13, и eели p = 11, то | Q | = 152 и a1(g) = 2641 + 99 делится на 19. Отетода 1 = 2 ii a1 ( g ) = 627.
Если p = 7. т о | Q | = 133 11 a1 ( g ) = 168 1 делится на 19. Отетода a1 ( g ) = 0.
Если p = 5. то t = 3, 8. В первом случае | Q | = 57 ii 228 + a 1 (g)/3 делится на 8. Отетода a 1 (g) = 1201 + 60 делится на 19 ii a1 (g) = 1140. Во вторе>м случае | Q | = 152 и 703 + a1(g)/3 делится на 8. Отсюда a1 (g) = 1201 + 75 делится на 19, противоречие.
Если p = 3. то t = 3 , 6 , 9. В первом случае | Q | = 57 ii 228 + a1 ( g ) / 3 делится на 8. Отетода a1 ( g ) = 24 1 + 12 делится на 19 ii а1 ( g ) = 456 s + 228. Во вторе>м случае | Q | = 114 ii a1 ( g ) / 3 — 3 делится на 8. Отетода а1 ( g ) = 24 1 + 9 делится на 19 ii ai ( g ) = 456 s + 57. В третвем случае | Q | = 171 1i a1 ( g ) / 3 — 2 делится на 8. Отетода a1 ( g ) = 24 1 + 6 делится на 19 ii ai ( g ) = 456 s + 342.
Если p = 2. т о t = 1 , 3 , 5 , 7 , 9. В первом случае | Q | = 38 и число (3013 + a1 ( g ) / 3) / 8 нечетно. Отетода a1 ( g ) = 48 1 — 3 делится на 19 ii a1 ( g ) = 912 s + 57. Во втором случае | Q | = 57 ii число (5358 + a1 ( g ) / 3) / 8 нечетно. Отетода a1 ( g ) = 48 1 — 18 делится на 19 н a1 ( g ) = 798. В третвем случае | Q | = 95 ii число (8968 + a1 ( g ) / 3) / 8 нечетно. Отетода a1 ( g ) = 48 1 делится на 19 ii a1 (g) = 912. В четвергом случае | Q | = 133 ii число (12578 + a1 ( g ) / 3) / 8 нечетно. Отетода a1 ( g ) = 48 1 + 18 делится на 19 ii a1 ( g ) = 114. В пятом случае | Q | = 171 ii число (16188 + a1 ( g ) / 3) / 8 нечетно. Отетода a1 ( g ) = 48 1 — 12 делится на 19 н a1 ( g ) = 228. B
Лемма 7. Выполняются следующие утверждения:
-
(1) S ( G ) = O^G );
-
(2) ноколь T группы G = G/S ( G ) нзози)рфеп L3(7) U3 (8). L4 (7). U4 (8). HN.
C Пу< mb |S ( G ) | делится на 19 ii R — спловская 19-подгруппа из S ( G ). Toгда |Ng(R)| делится на 13, противоречие с леммой 6.
Пусть T — цоколь группы G = G/S (G). Из действия элемента порядка 19 на минимальной нормальной подгруппе N из T следует, что 19 делит |N| и T — простая неабелева группа.
Из [7, таблица 1] следует, что группа T изоморфна L3(7), U3(8), L4(7), U4(8), HN. B
Завершим доказательство следствия. Группы из(8), L4(7), U4(8), HN не содержат максимальных подгрупп индекса, делящего 19 • 63.
Если группа T изоморфна L3 (7). то
|T : Ta | = 57 , Ta = 7 2 : SL2 (7) : 2 , либо
|S(G) : S(G)a| = 7, |G : T = 3, Ga = 72 : SL2(7) : 2, либо
|S ( G ) : S ( G ) a| = 21 .
|G| B
Список литературы Автоморфизмы сильно регулярного графа с параметрами (1197, 156, 15, 21)
- Cameron P., Van Lint J. Designs, Graphs, Codes and their Links.-Cambridge: Cambridge Univ. Press, 1981.-240 p.-(London Math. Soc. Student Texts, № 22).
- Махнев А. А. Расширения симметричных 2-схем//Тез. докл. междунар. конф. "Мальцевские чтения".-Новосибирск, 2015.-С. 112.
- Brouwer A. E., Haemers W. H. The Gewirtz graph: an exercize in the theory of graph spectra//Europ. J. Comb.-1993.-Vol. 14.-P. 397-407.
- Behbahani M., Lam C. Strongly regular graphs with non-trivial automorphisms//Discrete Math.-2011.-Vol. 311, № 2-3.-P. 132-144.
- Cameron P. J. Permutation Groups.-Cambridge: Cambridge Univ. Press, 1999.-(London Math. Soc. Student Texts, № 45).
- Гаврилюк А. Л., Махнев А. А. Об автоморфизмах дистанционно регулярного графа с массивом пересечений $\{56,45,1;1,9,56\}$//Докл. АН.-2010.-Т. 432, № 5.-С. 512-515.
- Zavarnitsine A. V. Finite simple groups with narrow prime spectrum//Sib. electr. Math. Reports.-2009.-Vol. 6.-P. 1-12.