Об автоморфизмах сильно регулярного графа с параметрами (117,36,15,9)

• 1.    Введение

  Мы рассматриваем неориентированные графы без петель и кратных ребер. Для вершины a графа Г через ^(a) 06031 галим i-окрестпость вершины a. т. е. подграф. индуцированный Г на множестве всех вершин, находящихся на расстоянии i от a. Положим [a] = Г₁(a). a^ = {a} U [a].

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

Степенью вершины называется число вершин в ее окрестности. Граф Г называется регулярным степени k, если степень любой вершины из Г равна k. Граф Г назовем реберно регулярным с параметрами (v, k, А), если он содержит v вершин, регулярен степени k, и каждое его ребро лежит в А треугольниках. Граф Г — вполне регулярный граф с параметрами (v, k, А, д), если он реберно регулярен с соответствующими параметрами, и [a] П [b] содержит д вершин для любых двух вершин a, b, находящихся на расстоянии 2 в Г. Вполне регулярный граф диаметра 2 называется сильно регулярным графом.

В работах А. А. Махнева и А. К. Гутновой [1-3] найдены массивы пересечений дистанционно регулярных графов, в которых окрестности вершин являются псевдогеометрическими графамии для pGs-3(s,t). В частности, локально псевдо pG2(5, 2)-граф является сильно регулярным графом с параметрами (117, 36,15, 9).

В данной работе найдены возможные автоморфизмы для сильно регулярного графа с параметрами (117, 36,15, 9). Этот граф имеет спектр 361,926, -390. Порядок клики в Г не превосходит 1 + 36/3 = 13, порядок коклики в Г не превосходит 117 • 3/39 = 9.

Лемма 1. Пусть Г — дистанционно регулярный граф с параметрами (117, 36,15, 9), G = Aut(F). Ес ли g Е G, xi — характер проект щи представления ф на подпространство размерности 26. то ai(g) = ai (gl) для любого пат орального числа 1. взаимно простого с IgV Xi(g) = (ao(g) + a1 (g)/3 — 13)/4. E<-ли |g| = p — простое число, то Xi (g) — 26 делится па p. E<-ли |g| = p². p — простое число, то p² де. hit Xi(g^p) — 26.

• <1 Имеем

Q =   26   13/2 —13/4.

90 —15/29/4

Поэтому Xi(g) = (8ao(g)+2ai(g) — a2(g))/36. Полетавляя «2(g) = 117 — ao(g) — ai(g). получим Xi(g) = (ao(g) + ai(g)/3 — 13)/4.

Остальные утверждения леммы следуют из [5, лемма 1]. >

Лемма 2. Пусть Г — дистанционно регулярный граф с параметрами (117, 36,15, 9), A — трехвершшшый подграф из Г. yi — число всршпп из Г — A. смежных точно с i вершинами из A. Если A — коклика, то yo = 33—уз, если A — объединение изолированной вершины и ребра, то yo =40 — уз, если A — геодезический путь, то yo =47 — уз, а если A — клика, то yo = 54 — уз.

• < Пу отв A — коклика. Тогда у1 = 54 + 3уз. у₂ = 27 — 3уз 1i yo = 33 — 3уз- Пу отв A — клика. Тогда у1 = 18 + 3уз, у₂ =42 — 3уз и yo = 54 — 3уз. Аналогично рассматриваются оставшиеся случаи. >

Пусть до конца работы Г — сильно регулярный граф с параметрами (117, 36,15, 9), G = Aut(P). g — элемент простого порядка p из G 11 Q = Fix(g). Заметим, что если a. b — две bcj шшы it;: Qii p > 13. to [a] П [b] C Q.

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

• (1)    в Г нет собственных сильно регулярных подграфов с параметрами (V , k', 15, 9):

• (2)    если Q — пустой грае}), то p = 13. ai (g) = 39 ii a₂(g) = 78 и hi p = 3. a1(g) = 361 — 9 и a₂(g) = 126 — 361:

• (3)    если Q явля ется n-кликон. то n >  1 илnoop = 5. n = 2, 7,12. ai(g) = 601 + 75 — 15n и a₂(g) = 42 + 14n — 601. либо p = 2. n = 5, 7, 9,11,13. a1(g) = 241 + 39 — 3n и a₂(g) = 78 + 2n — 241:

• (4)    если Q ле является кликой или пустым графом, то Q содержит геодезический 2-путв и p ^ 13.

• <    Пуотв А — сильно регулярный трах]) с параметрами (v', k', 15, 9). Так как n² = 36 + 4(k' — 9). то n = 2u, k' = u² 11 А имеет собстветшые 'значения u + 3. —(u — 3). Кратность u + 3 равна, (u — 4)u(u² + u — 3)/18. поэтому u ф 6.

Пусть Q — пустой гра<]>. Так как 117 = 13 • 9. то p Е {3,13}. Пош>жпм ai(g) = pwi-Пусть p = 13. Тогда Xi(g) = 13(wi/3 — 1)/4. поэтому ai(g) = 39 11 a2(g) = 78. Пусть p = 3. Тогда Xi(g) = (wi — 13)/4 сравнимо с 2 по аюдулто 3. поэтому ai(g) = 361 — 9 ii a2(g) = 126 — 361.

Пусть Q является n-кликой, a — верш ина из Q. Ес ли n = 1, т op делит 36 и 80, поэтому p = 2. противоречие с теэк что для вершины u Е Г — a^. подграф [u] П [u^g] пересекает Q.

Если n >  1. т о p делит 2 0. 50 и 17 — n. поэтому либо p = 5 iin = 2, 7,12. ni ибо p = 2 ii n = 3, 5,... , 13. В лтобоэi случае Xi(g) = (n + pw_i/3 — 13)/4.

В случае p = 5 iim

ai(g) = 601 + 75 — 15n ii a2(g) = 42 + 14n — 601. В случае p = 2 число (n + 2wi/3 — 13)/4 четно, поэтому ai(g) = 241 + 39 — 3n ii a2(g) = 78 + 2n — 241. Если n = 3. то некоторая вершина it; Г — Q нс смежна e вершинами it;: Q. противоречие.

Пусть Q является m-кликой, m >  1. Toгда p делит 9 и 26, противоречие.

Пусть Q содержит ребро и яв.ляетея объединением t ^ 2 изолпрованивix клик. Тогда p делит 9 и 20, противоречие.

Пусть Q содержит геодезический 2-путь. Если p >  13, то Q — сильно регулярный гра<1> с А = 15 1i Д = 9. противоречие с утверждепием (1). >

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

• (1)    если Q содержит вершину a степепп 36. то .либо p = 3 ii ao(g) = 45. hii6o p = 2. 37 C ao(g) C 63 и hi шло ao(g) + ai(g)/3 — 13 делится па 8:

• (2)    p ne ooлыпе 7:

• (3)    eo th p = 7. to Q — сильно регулярный граф с параметрами (26,15,8,9) п ai(g) = 24.

• <1    Пуств Q содержит вершину a степени 36. Ввиду леммы 2 любая (д)-орбита длины p не содержит 3-коклик. Так как любая вершина из Г — a^ смежна с 9 вершинами из [a], то любая (д)-орбита длины p не содержит геодезических 2-путей. Если p >  2. то любая (д)-орбита длины p является кликой ii p C 7. В этом случае

xi(g) = (a0(g) + (117 — a0(g))/3 — 13)/4, поэтому ao(g) = 61 + 3 д, ля p > 3 1i ao(g) = 181 + 9 д, ля p = 3. Оте -года p = 3 1i ao(g) = 45. Если p = 2, то число Xi (g) = (ao(g)+ai(g)/3 —13)/4 четно. Утверждение (1) доказано. Пусть p = 13. Тогда Ад = 2,15. Дд = 9. |Q| = 13, 26, 39, 52 и степени вершин в Q равны 10, 23. Ес -ли |Q| = 13. то Q — сильно регулярный граф с параметрами (13,10, 2, 9). противоречие.

Пусть |Q| = 26. Если Q содержит вершину a степени 23. то ни ело ребер между Q(a) ii Q2(a) равно 18, но не меньше 23 • 7, противоречие. Значит, Q — сильно регулярный граф с параметрами (26,10, 2, 9). противоречие.

Пуств |Q| = 39. Если Q содержит вершину a степени 10. то ни ело ребер между Q(a) и Q2(a) равно 28 • 9, но не больше 20 • 10, противоречие. Значит, Q — регулярный граф степени 23, противоречие.

Пусть |Q| = 52. Если Q содержит вершину a степени 10. то ни ело ребер между Q(a) и Q2(a) равно 41 • 9, но не больше 10 • 21, противоречие. Значит, Q — регулярный граф степени 23, и число ребер между Q(a) и Q2(a) равно 28 • 9 = 20у + 7(23 — у), поэтому у = 13. Но если b,c — две вершины степени 2 в графе Q(a), то [b]П[c] содержит 13 вершин из [a] — Q и не менее 12 вершин из Q2(a), противоречие.

Пусть p = 11. Тогда Ад = 4,15. Дд = 9. |Q| = 18, 29,40, 51 и степени вершин в Q равны 14, 25. Если Q содержит вершину a степени 14. то ни ело ребер между Q(a) ii Q2(a) не меньше 14 • 9. равно 9(|Q| — 15). но не больше 14 • 20. поэтому |Q| = 40 и указанное число равно 9 • 25 = 20у + 9(14 — у). у = 9. Но если b,c — две Bq:шиты из П(а). смежные о 20 вершинами из П2Д). то [b] П [c] соде]зжит a и но менее 15 вершин it; П2Д). противоречие.

Значит. П — регулярный граф степени 25. |П| = 40 и число ребер между П(а) ii П2Д) равно 14 • 9, но не меньше 9 • 25, противоречие.

Пусть p = 7. Тогда Aq = 1, 8,15. ^q = 2, 9. |П| = 19, 26, 33,40,47, 54 и степени вершин в П равны 8,15, 22, 29. Ес ли |П| > 33, то любая (д)-орбита длины 7 не содержит 3-кок.лик. Далее. xi(g) = (ao(g) + a1(g)/3 — 13)/4 и в е. лунае ao(g) = 40 иск хм a1(g) = 63. В этом случае на Г — П имеется 5 кликовых (д)-орбит и 6 орбит степени 4. Противоречие с тем, что для ребра и изолированной от него вершины из (д)-орбиты степени 4, подграф, состоящий из вершин, смежных с 0 или 3 вершинами из этой тройки, содержит 40 вершин it:: П ii 2 всршш ibi из этой (д)-орбиты. против*>речие. В случае ao(g) = 47 имеем ai(g) = 42. В этом случае для геодезического 2-пути из (д)-орбиты подграф, состоящий из вершин, смежных с 0 или 3 вершинами из этой тройки, содержит 47 вершин из Пи 2 вершины из этой (д)-орбиты. против*>речие. В случае ao(g) = 54 им*хм ai(g) = 63 ii X1(g) = (41 + 21)/4. противоречие.

Значит. |П| ^ 33. Если П содержит вершину a степени 8. то ни*-ло ребер между П(а) и П2Д) не меньше 8 • 6 и равно 2(|П| — 9), поэтому |П| = 33 и П — сильно регулярный граф с параметрами (33, 8,1, 2). В этом случае П имеет собствештые значения 2. —3 и кратность 2 равна, 2 • 8 • 11/10. противоречие.

Если П содержит вершину а степени 22. то ни ело ребер между П(а) и П2Д) не меньше 22 • 6 ii не больше 10 • 9. противоречие. Значит. П — регулярный граф степени 15. |П| = 26 и число ребер между П(а) и П2(а) равно 15 • 6 = 10 • 9. Отсюда П — сильно регулярный граф с параметрами (26,15, 8, 9) 1i Xi(g) = (13 + a1(g)/3)/4. поэтому a1(g) = 24. >

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

• (1)    чи(по p не р явно 5:

• (2)    ее.ти p = 3. то |П| < 33 и.тп |П| = 45:

• (3)    ее.тп p = 2. то |П| < 63.

• <1 Пусть p = 5. Тогда Aq = 0, 5,10,15. № = 4, 9. |П| = 12,17, 22, 27, 32, 37,42,47, 52. степени вершин в П равны 6,11,16, 21, 26, 31 1i Х1(д) = (ao(g) + a1(g)/3 — 13)/4.

Пусть Y — множеств о вершин it; П2Д). смежных с 9 вершинами из П(а). у = |Y |. Тогда число ребер между П(а) и П2Д) равно 6|П(а)| + 5x. С другой стороны, указанное число ребер равно 9у + 4(|П2(а) | — у) и делится на 5, противоречие.

Пусть p = 3. Тогда Aq = 0, 3,..., 15. ^q = 0, 3, 6, 9. |П| =6, 9,..., 54 и степени вершин в П равны 0,3,6,..., 36 11 xi(g) = (ao(g)+ a1 (g)/3 —13)/4. поэтому (ao(g)+ a1 (g)/3 —13)/4 сравнимо c 2 по модулю 3.

Если |П| > 33. то ввиду лезыы 2 любая (g)-op6iiTa длины 3 является кликой. ai(g) = 117 — ao(g) ii (2ao(g)/3 + 26)/4 сравнимо с 2 по моду.лто 3. Поэтому ao(g) = 45 ii ai(g) = 72.

Пусть p = 2. Тогда Aq = 1, 3,..., 15. ^q = 1, 3,... , 9. |П| = 5, 7,..., 65 и степени вершин в П равны 0, 2,4,..., 36 1i Xi(g) = (ao(g) + ai(g)/3 — 13)/4. поэтому (ao(g) + ai(g)/3 — 13)/4 четно.

Если |П| > 63. то лтобая (g)-op6iiTa длины 2 является кликой. ai(g) = 117 — ao(g) = 52

• ¹¹ Xi(g) = (65 + 52/3 — 13)/4. противоренне. >

Лемма 6. Пусть Г является сильно регулярным графом с параметрами (117, 36,15, 9) п группа G = Aut(F) действует транзитивно па множество вершин графа Г. Пл'сть f — элемент порядка 13 iiз G. g — элемент простого порядка p < 13 iiз Cg(/). Тогда |CG(f)| делит 26 и если штволтоция g Е G централизует f. то Fix(g) является 13-кокликой и ai(g) = 0.

• <1 |G| делится на 9 • 13. По те*>реме 1 n(G) С {2, 3, 5, 7,13}.

• 3.    Основной результат

Пусть G содержит подгруппу (h) пор>:дка 13p. p — простое пиело, меньшее 11. g = h¹³. f = h^p. Ввиду тсорсмы 1 Fix (f) — пусто й граф. p = 2 ii л ибо |Q| = 13 11 ai(g) = 241 делится шi 13. либо |Q| = 39. В послед:хем случае Xi(g) = (ai(g)/3 + 26)/4. число (ai(g)/3 + 26)/4 nonio ii ai(g) = 3(81 — 26) делится на 13. прогиворсине. Из действия g на. Ui = {u Е Г : d(u,u^f i ) = 1} еледует. что Q = Fix (g) персе екает Ui для лтобого i. не кратного 13, поэтому Q является 13-кокликой.

Пусть V — подгруппа, порядка. 4 из CGf )- Так как Xi(g) - 26 нс делитея на. 4. то V — элементарная абелева группа. Из действия V на U = {u Е Г : d(u,u^f ) = 1} следует, что Q = Fix (g) содержитея в U для любой инволюции g Е V. противоречие с действием V на W = {w Е Г : d(w,w^f ) = 2}. >

Теорема 1. Пусть Г — сильно регулярный граф с параметрами (117,36,15,9), G = Aut(F). g — элемент из G простого порядка pi xQ = Fix(g). Тогда n(G) С {2, 3, 5, 7,13} и выполняется одно из следующих утверждений:

• (1)    Q — пустой граф. p = 13. a1(g) = 39 ii a₂(g) = 78 ii.th p = 3. a1(g) = 361 — 9 и a₂(g) = 126 — 361;

• (2)    Q является n-клпкой. и либо p = 5. n = 2, 7,12. ai(g) = 601 + 75 — 15n п a₂(g) = 42 + 14n — 601. либо p = 2. n = 5, 7, 9,11,13. a1(g) = 241 + 39 — 3n и a₂(g) = 78 + 2n — 241;

• (3)    Q содержит геодезический 2-путь и либо

• (4)    p = 7. Q — сильно регулярных! граф с параметрами (26,15, 8, 9) 11 ai(g) = 24. либо

• (ii)    p = 3. |Q| < 33 ii.th |Q| = 45. либо

• (iii)    p = 2 11 |Q| ^ 63.

• < Доказательство теоремы опирается на метод Хигмена работы с автоморфизмами дистанционно регулярного графа, представленный в третьей главе монографии Камерона [4]. При этом граф Г рассматривается как симметричная схема отношений (X, R) с d классами, где X — множество вершин графа. Ro — отношение равенства, на. X хх для i ^ 1 класс Ri состоит из пар (u, w) таких. что d(u, w) = i. Для u Е Г поло жим ki = |Гi(u)|. v = |Г|, Кл;гссу Ri отвечает граф Г на миожестве вершин X. в котором вершины u,w смежны, если (u, w) Е Ri- Пусть Ai — матрица, емежиоетч графа. Pi д,ля i >  0 11 Ao = I — единичная матрица. Тогда AiAj = ^2 pij Al для чисел пересечений pij.

Пусть Pi — матрица, в которой на месте (j, 1) сто пт pij. Тогда собственные значения pi(0),..., pi(d) матушпы Pi являются собственны ми зиаиеинями графа. Г кратностей mo = 1,...,md. Матрипы P ii Q. у которвьг на месте (i,j) стоят стоят pj (i) и qj (i) = mjpi(j)/ki соответственно, называются первой и второй матрицей собственных значений схемы и связаны равенством PQ = QP = vI.

Пусть uj и wj — левый и правый собственные векторы матрицы Pi, отвечающие собственному значению pi(j) и имеющие первую координату 1. Тогда wj являются столбцами матрицы P и mjuj являются строками матрицы Q.

Подстановочное представление группы G = Аи1(Г) на вершинах графа Г обычным образом дает матричное представление ф группы G в GL(v, C). Пространство C^v является ортогональной прямой суммой собственных G-инвариантных подпространств

W0,..., Wd матрицы с'межпости A = Ai граa Г. Для лтобого g Е G матрица ^(g) перестановочна с A. поэтому подпространство Wi является ^(G)-niiBapnanTiшм. Пусть Xi — характер представления ^wi. Тогда (см. [4, §3.7]) для g Е G получим

d

Xi⁽g) = v ¹ ^2Qij ^aj ⁽g), j =0

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

Утверждения 1)-2) следуют из леммы 3. Доказательство утверждения 3) следует из лемм 3-5. >

Следствие 1. Если группа G автоморфизмов сильно регулярного графа с параметрами (117, 36,15, 9) действует транзитивно па мпожестве вершин, то поколь T группы G изоморфен либо L3(3) и Ta = GL2(3) — подгруппа индекса 117, либо T = L4(3) и Ta = U4(2)Z — подгруппа индекса 117.

• <1 Ввиду .теммы 6 имеем S (G) = 03(G). Плтть G = G/O3(G). T — поколь группы G. Из действия подгруппы порядка 13 на минимальной нормальной подгруппе N из G следует, что |N| делится на 13. Отсюда T — простая неабелева группа и ввиду [6, таблица 1]

группа T изоморфна L3(3). L2(25). Us(4). PSp4(5). L4(3). ^(2)’. L2<13). L2<27). G2(3).

³D4(2). Sz(8)_L2(64). ^(5). L3(9). PSp6(3). P ^(3). £2(4). PSp4(8). P Q+(3).

Так как T содержит максимальную п<дгруппу индекса, делящего 13 • 9. то либо T = L3(3) и Ta = GL2(3) — подгруппа индекса 117, либо T = L4(3) и Ta = U4(2)Z — подгруппа индекса 117.

В любом случае 03(G) = 1. >