Автоморфизмы сильно регулярного графа с параметрами (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 < у.

• ¹    Работа выполнена при финансовой поддержке Российского научного фонда, проект 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 называется схема, D_x с миожеством точек X_x = X — {x} и миожеством блоков B_x = {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)(Л² + 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,9⁵⁶⁴², —105⁴⁹⁵. Отсюда максимальный п<зрядок коклики не больше vm/(k + m) = 6138 • 105/1302 = 495

Цветковича (см. лемму 1). Дополнительный граф к блочному графу 3-(496,40, 3) схемы назовем монстром Камерона. В [2] доказано

Предложение 3. Для монстра Камерона Г выполняются следующие утверждения:

• (1)    окрестность любой вершины в графе Г — сильно регулярный граф с параметрами (1197,156,15, 21) и спектром 1561, 9⁷⁴¹, —15⁴⁵⁵, причем порядок коклики в этом графе по больше 105:

• (2)    множеств о блоков C_x. содержат них точку x схе мы E. явяг тется 495-кокдпкой графа Г, для которой достигается равенство в границах Хофмана и Цветковича-

• (3)    подграф Г — Cx сильно рсгулярсп с параметрами (5643,1092,141, 228) я спектром 10921. 9⁵¹⁴⁸. —96⁴⁹⁴;

• (4)    для радиишых точек x. у схе мы E им сем |C_x П 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. 9⁷⁴¹. — 15⁴⁵⁵. Е(?ли 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

ψW_i                 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. Подставляя в эту формулу значение a₂(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 ) = pw_i. Так как 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] П [u^g] содержит 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) = 4s². kD = s ² + 12. D имеет неглавные собственивте 'значения s — 3. — (s + 3) ii кратноств s — 3 равна, (s + 2)(s ² + 12)(s ² + 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 ₂ = | 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 ) нзози)рфеп L₃(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