Автоморфизмы монстра Камерона с параметрами (6138, 1197, 156, 252)

Мы рассматриваем неориентированные графы без петель и кратных ребер. Если a, b — вершшпт графа, Г. то ^тюрез d(a, b) обозначается расстоянне между a ii b, а через Г_i(a) — подграф графа Г. индуцированный множеством вершин, которые находятся в Г на расстоянии i от вершины a. Подграф Г1 (a) называется окрсапностъю вершины a и обозначается через [a]. Через a^ обозначаетезя подграф {a} U [a].

Гра<1> Г называется сильно регулярным графом с параметрами (v,k,X,p) если Г содержит v вершин, является регулярным степени k. каждое ребро Г лежит точно в X треугольниках и для любых двух несмежных вершин a, b подграф [a] П [b] содержит точно д вершин.

Система инцидентное тп (X, B) с множеством точек X и множеством блоков B назв!-вается t — (V, K, Л) cxc.moi "н если |X| = V. каждвш блок содержит ровно K точек и любые t точки лежат ровно в Л блоках. Любая 2-схема, является (V, B,R, K, Л) схемой. где В — число блоков, каждая точка инцидентна R блокам, и имеют место равенства VR = BK, (V — 1)Л = R(K — 1). Схема, называется с симметричной, если В = V. Схема, назвшается квазисимметричной, если для любых двух блоков В, В' Е B имеем |ВПВ'| Е {x, у}. Числа x,y называются числами пересечений квазисимметричной схемы, и предполагается, что x < у.

Блочный граф квазисимметричной схемы (X, B) в качестве вершин имеет блоки схемы ii два блока B,C Е B смежш>i. если |В П C | = у. Блочный граф квазисимметричной (V, B,R, K, Л) схемы сильно регулярен с собственными значениями k = (R — 1)(K — xB + x)/(y — x) кратности 1. (R — K — Л + x)/(y — x) кратт ioctii V — 1 ii — (K — x)/(y — x) кран ioctii В — V.

• ¹    Работа выполнена при поддержке гранта Российского научного фонда, проект № 15-11-10025 (теорема), а также соглашения между Министерством образования и пауки Российской Федерации и Уральским федеральным университетом от 27.08.2013, № 02.А03.21.0006 (следствие).

Производной схемой для t- (V, K, Л) схемы D = (X, B) в точке x G X называется схема Dx с мпожеством точек Xx = X — {x} 11 мпожеством блоков B_x = {B — {x} : x G B G B}. Cxема E называется расширением стелил D. если производная схемы E в некоторой точке изоморфна D. Хорошо известно, что проективная плоскость расширяема, только если ее порядок равен 2 или 4. П. Камерон [1, теорема 1.35] описал расширения симметричных 2-схем.

Предложение 1. Пусть 3-(V, K, Л) схема E = (X, B) является расширением симметричной 2-схемы. Тогда верно одно из утверждений:

• (1)    E является адамаровой 3-(4Л + 4, 2Л + 2, Л) схемой:

• (2)    V = (Л + 1)(Л² + 5Л + 5) 11 K = (Л + 1)(Л + 2):

• (3)    V = 496. K = 40 а Л = 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. В частности, граница Хофмана для коклик совпадает с границей Цветковича. Дополнительный граф к блочному графу 3-(496,40, 3) схемы назовем монстром Камерона. В [2] доказано, что окрестность любой вершины в монстре Камерона — сильно регулярный граф с параметрами (1197,156,15, 21). В [3] найдены возможные автоморфизмы сильно регулярного графа с параметрами (1197,156,15, 21).

Предложение 2. Пусть Г — сильно регулярный граф с параметрами (1197,156,15, 21). G = АиЦГ). g — элемент простого порядка p из G i1 П = Fix(g). Тогда |П| 6 171, n(G) С {2, 3, 5, 7,11,13,19} и выполняется одно из следующих утверждений:

• (1)    П — пустой грае}). либо p = 3 1 1 a1(g) = 721. либо p = 7 11 a1(g) = 1681 — 21. либо p = 19 1 1 a1(g) = 4561 + 171;

• (2)    П явля ется n-кликой. либо

  • (i)    p = 13. n = 1 1 1 ai(g) = 3121 + 156. либо

  • (ii)    p = 2. n = 9 1 1 ai(g) = 481 + 12 11. mi n = 11 11 ai(g) = 321 — 12, либо

  • (iii)    p = 5. n = 2 11 a1(g) = 1201 + 45 11. th n = 7 11 a1(g) = 1201 — 30;

• (3)    П является (3t + 1)-кокл икой. p = 3 11 a1 (g) = 721 + 12 — 45t:

• (4)    П содержит геодезический 2-путв пр 6 13.

• 2.    Вспомогательные результаты

Там же доказано, что сильно регулярный граф с параметрами (1197,156,15, 21) не является реберно симметричным. В данной работе найдены автоморфизмы монстра Камерона.

Лемма 1. Пусть Г является сильно регулярным графом с параметрами (v, k, А, д) и неглавными собственными значениями 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 Это утверждение хорошо известно (см., например. [4. §2]). B

Лемма 2 [5, теорема 3.2]. Пусть Г является сильно регулярным графом с параметрами (v, k, А, д) ii собственныхш значениями k, r, —m. Если g — автоморс}>пзм графа. Г и П = Fix(g). то |П| 6 v • max{A, д}/(к — r).

Из лемм 1-2 следует, что для сильно регулярного графа с параметрами (6138,1197,156,252) число вершин в коклике (клике) не больше 495 (не больше 12) и |Q| 6 6138 • 252/1188 = 31 • 42 = 1302.

Лемма 3. Пусть Г — сильно регулярный граф с параметрами (1197,156,15, 21), G — группа автоморфизмов графа Г, g — элемент порядка 11 из G и И = Fix(g). Тогда выполняются следующие утверждения:

• (1)    |И| = 11t — 2. t 6 15. степень вершины в И равна 11s + 2.2 6 s 6 10 ii a1(g) = 33(8m + 9 — 5t):

• (2)    |G| не делт itch па 121.

C Имеем |И| = 11t — 2 6 171. поэ тома^- t 6 15. Далее, степень вершины в И равна, ^11s + 2. s 6 13. Aq = 4, 15. _№ = 10,²¹

Допустим, что И содержит вершину c степени, не меньшей 123. Тогда число ребер между И(с) II И₂(с) не меньше 123 • 8. но не больше 39 • 21. противоречие.

Допустим, что И содержит вершину c степени 13. Тогда ^тшсло ребер между И(с) и И₂(с) равно 10(11t —16). но не больше 13^96. поэтому t не больше 12. Теперь И(с) содержит не более одной вершины, смежной с 96 вершинами из И₂(с), поэтому указанное число ребер не больше 13 • 85 и t не больше 11. Повторив данное рассуждение несколько раз, убедимся, что t 6 3. Теперь число ребер между И(с) и И₂(с) равно 10(11t — 16) =8 • 13 и 10t = 24. противоречие.

По [2. лемма 3] имеем xi(g) = (55t + a1 (g)/3 — 67)/8 11 a1(g) = 3(8l + 67 — 55t) делится на 11. Поэтому l = 11m + 4 ii a1(g) = 33(8m + 9 — 5t).

Допустим, что h — автоморфизм порядка 121 графа Г 1i h¹¹ = g. Toгда И — сильно регулярный граф с параметрами (11t — 2, 34,15, 21), противоречие.

Пусть U = hg, hi — подгруппа порядка 121 в группе автоморфизмов графа Г. Д = Fix(U). a Е Д. Тогда Д(а) содержит не менее двух вершин. Для вершины b Е Д(а) подграф Д(а)П[b] содержит 4 пли 15 вершин. Если Д является iсликой. то |Д| = 10. Д(а)П [b] содержит 8 вершин из Д(а) и еще 7 вершин, противоречие. Как и выше доказывается, что степень любой вершины в Д не меныпе 24, |Д| = 11e — 2.

Допустим, что для a Е Д подграф [а] не содержит U-opoиту А длины 121. Тогда для вершины u Е А подграф [u] П [а] содержит не более одной вершины из Д. противоречие с тем, что 21 и 20 не делятся на 11. Значит, А содержится в [а] для любой вершины а Е Д. Противоречие с тем. что число вершин в Д не меньше 3.

Итак, в Г ii ет U-орбит длины 121. Теперь 1197 6 |Д| + 12(163 — |Д|) 11 |Д| 6 69. Далее. 156 6 |Д(а)| + 12(35 — |Д(а)|) 1i |Д(а)| 6 24. Таким образом. Д — регулярный граф степени 24 и ввиду леммы 3 имеем |Д| > 45 • 19/7, противоречие. B

Доказательство теоремы опирается на, метод Хигмена работы с автоморфизмами сильно регулярного графа, представленный в третьей главе монографии Камерона, [6]. Если P и Q — первая и вторая матрицы собственных значений графа, то

/      1          1         1    \

P= k        r       s , v-k- 1 -r- 1 -s- 1

PQ = QP = vI. Здесь v — число вершин, k. r. s — собственные зшгчения графа, Г кратностей 1, f, v — f — 1 соответственно (указанные кратности образуют первый столбец матрицы Q).

Подстановочное представление группы G = Aut(F) на вершинах графа Г обычным образом дает мономиальное матричное представление Д группы G в GL(v, C). Простран- ство Cv является ортогональной прямой суммой собственных ф^)-инвариантных подпространств Wo. W1. W2 матрицы сме>кпостп графа, Г. Пусть xi — характер представления ^wi. Тогда для любого g Е G полупим равенство xi(g) = v-152Qj aj (g), j=0

где aj (g) — число точек x из X таких, что d(x,x^g) = j.

В леммах 4-6 предполагается, что Г — сильно регулярный граф с параметрами (6138,1197,156, 252) и спектром 11971,9⁵⁶⁴²,-105⁴⁹⁵. G = Aut(P). g — элемент простого порядка p из G 'p характер, полученииill при проектировании ^(G) на подпространство размерности 495.

Лемма 4. Имеем X2(g) = (9ao(g) — ai(g))/114 + 198/19, ai (g) = ai(g^l ) для любого 1, по кратного p. п 495 — x2(g) летит ся па p.

C Рассмотрим снлык) регулярный граф P с параметрами (6138,1197,156, 252). Тогда

/ 1         1           1     \

Q =   5642 806/19  —217/19

455 —825/19 198/19

и X2(g) = (15ao(g) — 25a1 (g)/19 + 6a2(g)/19)/186. Подставляя в эту формулу значение ^a2^(g) = v ^{— ao(g) — a}1^(g). полз-ним ^x2^(g) = ^{(9ao(g) — a}1^(g))/114 + ^198/19

B

• 3.    Автоморфизмы монстра Камерона с параметрами (6138,1197,156, 252)

Лемма 5. Выполняются следующие утверждения:

• (1)    если Q — пустой гр аф. то либо p = 31 i1 a1(g) = 31 • 78. niioo p = 11 ii a1(g) = 11(1141 — 6). .nioo p = 3 11 a1(g) = 3(1141 + 54). niioo p = 2 11 a1(g) = 2(1141 — 33);

• (2)    если Q являстоя n-кдикоп. то либо

• (i)    p = 19. n = 1 1 1 a1(g) = 19(61 + 3). либо

  • (i)    p = 13. n = 2 11 a1(g) = 6 • 13(191 — 5). либо

  • (iii)    p = 5. n = 3 11 a1(g) = 3(1901 + 25) ii.mi n = 8 1i a1(g) = 6(951 + 20). либо

  • (iv)    p = 2. n = 10 1 1 a1(g) = 6(381 + 4) ii.mi n = 12 ii a1(g) = 6(381 — 21);

• (3)    если Q являстоя m-кокликоп. то p = 3. m = 3t. t 6 70 ii a1(g) = 9(381 + 10 + 3t) или p = 7. m = 7t — 1. t 6 70 1 1 a1 (g) = 63(381 + 8 + t);

• (4)    если Q содержит ребро ii яв.тяется объединением m (m > 2) и золированных клик, то p = 2 и порядки изолированных клик в Q равны 10 или 12.

C Пуств Q — пустоii грасф. ai(g) = pwi. Так как 6138 = 9 • 22 • 31. то p Е {2, 3,11, 31}.

Пуств p = 31. Тогда x2(g) = 31(—w1 + 36)/114 11 a1(g) = 31(1141 — 36). Ес -ли 1 = 2. то a1(g) = 31 • 192 и найдется кликовая hgi-орбита длины 31, противоречие. Значит, ai(g) = 31 • 78. a2(g) = 31 • 120.

Пуств p = 11. Тогда x2(g) = 11(—w1 + 108)/114. a1 (g) = 11(1141 — 6) 11 a₂(g) = 11(192 — 1141).

Пуств p = 3. Тогда число x2(g) = (—wi +396)/38 делится на 3 11 a1(g) = 3(1141 + 54).

Пуств p = 2. Тогда число x2(g) = (—wi + 594)/57 печетno ii a1(g) = 2(1141 — 33). Утверждение (1) доказано.

Пусть Q является п-кликоп. Если п = 1. то p делит 1197 и 4940. поэтому p = 19. ^X2(g) = ^{(63 -} w^{1 )/}6, _lal ^(g) =¹⁹⁽⁶¹+³⁾.

Пусть п >  2 1i a, b E Q. Так как g действует полурегулярио на [a] — b^. то p делит 1040. 3900 II 158 — п. поэтому ii p = 2, 5,13. В случае p = 2 по предложешпо 2 имеем п = 10,12. Ес ли п = 10. то чпело x2 (g) = (213 — a1 (g)/6)/19 neneтио ii a1(g) = 6(381 + 4). Если п = 12. то чпело x2(g) = (216 — a1(g)/6)/19 пенетио ii a1(g) = 6(381 — 21).

В случае p = 5 пола ’пим п = 3. пи ело x2(g) = (405 — a1 (g)/3)/38 делится на 5 ii a1 (g) = 3(1901 + 25) ii. ян п = 8. пи ело x2 (g) = (210 — a1(g)/6)/19 делится на 5 п ai(g) = 6(951 +20).

В случае p = 13 пола"чим п = 2. x2(g) = (201 — a1 (g)/6)/19 1i a1 (g) = 6 • 13(191 — 5).

Пусть Q явля ется m-кокл! iKoii. 0 < m 6 495. Ес -ли a,b E Q. то g действует полурегу-лярио на [a] П [b]. [a] — [b] - поэтому p делит 252 ii 945. Отстода p = 3, 7. Ес -ли p = 3. то m = 3t. t 6 165. чиело x₂(g) = 3(3t + 132 — a1(g)/9)/38 делится на 3 1i a1(g) = 9(381 + 10 + 3t).

Если p = 7. то m = 7t — 1. t 6 70. x2(g) = 3(7t + 132 — a1(g)/9)/38 1i a1 (g) = 63(381 + 8 + t).

Пусть Q содержит ребро и яв.тяетея объединением m (m >  2) изолированных клик. Если a. c — несмежные вершины из Q. то g действует полурегулярпо на [a] П [c] 1i p делит 252.

Пусть a. b — смежные вершины из клики, лежащей в Q. Так как g действует полуре-гуляртю на [a] — b^. то p делит 1040. Отстода p = 2 ii порядки изолированных клик в Q равны 10 пли 12. B

Лемма 6. Если Q содержит геодезический путь b, a, c, то выполняются следующие утверждения:

• (1)    если Q содержит [a] для пекоторой вершины a E Q. то p 6 5. Q = a^ ii a1(g) = 0:

• (2)    g точно лействует па [a] для некоторого 2-путп b,a,c ii n(G) С {2, 3, 5, 7,11,13, 19, 31};

• (3)    если Q(a) не содержит геодезических 2-путей, то Q(a) — кок тика пр = 3.

C Ес ли Q содержит [a] для пекотор ой вершины a E Q. то Q = a^± 1i a1(g) = 0. Далее. x2(g) = 3(ao(g)+66)/38, и 495 — x₂(g) делится Hap. Заметим, что объединение подграфов u^± — [a] по всем вершииам u из пекетторой (g)-op6nTbi длины p содержит p(1198 — 252) вершин и 946p 6 4940, поэтому p = 5.

Можно считать, что g точно действует на [a] для некогорого 2-пути b, a, c ii з Q (в противном случае g фиксирует каждуго вершину графа Г). Теперь ввиду предложения 2 имеем n(G) С {2, 3,5, 7,11,13,19, 31}.

Пусть Q(a) не содержит геодезических 2-путей. По предложешпо 2 подграф Q(a) является кокликой ii p = 3. B

Теорема. Пусть Г — монстр Камерона с параметрами (6138,1197,156, 252), G = Aut(F). g — элемент простого порядка p из G ii Q = Fix(g). Toгда |Q| 6 171. n(G) С {2, 3, 5, 7,11,13,19, 31} и выполняется одно из следующих утверждений:

• (1)    Q — пустой гра<1>. либо p = 31 11 a1 (g) = 31 • 78. .n ioo p = 11 11 a1(g) = 11(1141 — 6). либо p = 3 1 1 a1(g) = 3(1141 + 54). hiioo p = 2 11 a1(g) = 2(1141 — 33);

• (2)    Q является п-кчикой. либо

• (i)    p = 19. п = 1 1 1 a1(g) = 19(61 + 3). либо

  • (i)    p = 13. п = 2 11 a1(g) = 6 • 13(191 — 5). либо

  • (iii)    p = 5. п = 3 11 a1(g) = 3(1901 + 25) ii. тп п = 8 11 a1(g) = 6(951 + 20). либо

  • (iv)    p = 2. п = 10 1 1 a1(g) = 6(381 + 4) ii. тп п = 12 11 a1(g) = 6(381 — 21);

• (3)    Q явдяется m-кокликой. р = 3. m = 3t. t 6 70 г i ai (g) = 9(381 +10 + 3t) ii.th р = 7. m = 7t — 1. t 6 70 1 1 a1(g) = 63(381 + 8 +t);

• (4)    Q содержит ребро и яв.тяется объединением m (m > 2) изолирова!шых клик, р = 2 и порядки изолированных клик в Q равны 10 или 12;

• (5)    Q содержит геодезический 2-путв пр 6 13.

C Доказательство теоремы следует из лемм 5-6 п предложения 2. в

До конца работы будем предполагать, что G действует транзитивно на множестве вершин графа. Г. По теореме n(G) С {2, 3, 5, 7,11,13,19, 31} ii |G : Ga | = 18 • 11 • 31.

Лемма 7. Пусть f — элемент порядка 31 из G, g — элемент простого порядка р <  31 из Cof ). Тогда либо Q — пустеш граф. р = 2 ii a1 (g) = 31 • 42. либо выполняются следующие утверждения:

• (1)    ее.тп р = 13. то |Q| = 31(13s + 3). s 6 3 ii ai(g) = 3(381 + 93(13s + 3) + 392);

• (2)    p = 11.

C Пусть f — элемезгт порядка 31 ii з G. По теореме a1(f ) = 31 • 78. a₂(f) = 31 • 120. Пусть g — элемент простого порядка р <  31 пз Co(f ). Если Q — пустой граф. то р делит 78 ii 120. поэтому р = 2, 3. В елупае р = 3 чи<зло a1(g) = 3(1141 + 54) делится на 31. поэтому 71 — 13 делится на 31 п 1 >  24. противореч!ie. В случае р = 2 число a1(g) = 2(1141 — 33) делится на 31. поэтому 51 + 1 делится на 31 и 1 = 6.

Пусть Q — непустой граф. Тогда |Q| = 31t ii р дел нт 198 — t. Далее. X2(g) = (93t + 392 — a1(g)/3)/38 1i a1(g) = 3(381 + 93t + 392) делится на р.

Если р = 13. то t = 13s + 3. ii с учетом неравенства 31(13s + 3) 6 1302 имеем s 6 3 ii 8 — 1 делится на 13.

Если р = 11. то t = 11s. Так как g фиксирует не менее десяти hf i-oponт на W = {w | d(w,w^f ) = 2}. то 10 6 s. противорение. B

Лемма 8. Имеем S(G) = 02,3(G), цоколь T группы G = G/S (G) изоморфен L2(32) и либо

• (1)    Ta — подгруппа порядка 16. V = S(G) является 3-группой. |V : Va| = 3 ii T действует неприводимо па V. либо

• (2)    Ta — подгруппа порядка 32. S(G) = VW. где V является спловской 3-полгруппой из S(G) | V : V_a| = 3 IiT действует неприводимо па V. W является спловской 2-подгруппой из S(G) |W : W_a| = 2 ii Т действует неприводимо па W.

C Из лемм 3, 7 следует, что S(G) = 02,3(G).

Пусть T — поколь группы G = G/S(G) По [8. таблипа 1] группа T пзомор(|ша L2(32) или O'N. Но в группе O'N наименьший индекс собетвешюй подгруппы равен 122760. противоречие.

Значит, Т = L2(32) и Ta — подгруппа порядка 16 или 32.

Если Ta — подгруппа порядка 16. т о V = S (G) является абелево!! 3-группой. |V : Va | = 3 11 T действует неприводимо на V.

Если Ta — подгруппа порядка 32. то S (G) = VW. где V является спловской 3-подгруппой из S(G), |V : Va| = 3 и T действует неприводимо на V, W является силовской 2-подгруппой из S (G). |W : W_a | = 2 11 T неприводимо на W. Лемма .доказана. B

Следствие. Пусть Г — сильно регулярный граф с параметрами (6138,1197,156, 252), в котором окрестности вершин сильно регулярны с параметрами (1197,156,15,21) (в частпостп. Г — монстр Камеропаб и группа G = Aut(F) действует транзитивно па множестве вершин графа Г. Тогда S(G) = 02,3(G), цоколь T группы G = G/S (G) изо-мор<1>еп L2(32) 11 либо

• (1)    Ta — полгруппа порядка 16. V = S(G) является абелевой 3-группой. |V : Va| = 3 п T действует пещшволимо па V. либо

• (2)    Ta — полгруппа порядка 32. S (G) = VW. где V является спловской 3-подгруппой из S(G) | V : Va | = 3 1 1 T действует пещшволимо па V. W является спловской 2-подгруппой из S (G). |W : Wa| = 2 iiT действует неприводимо па W.

В частности, |G| не делится на 19 и Г не является реберно симметричным графом.

• C Доказательство следует из лемм 7-8. B