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

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

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

Через K _{m x n} обозначим полный двудольный граф с m долями порядка n. Граф на множестве пар X х Y называется p х q-решеткой, если | X | = p, | Y | = q, а пары (xi,yi) и (x ₂ , y ₂ ) смежны тогда и только тогда, когда x 1 = х ₂ или y 1 = y ₂ .

Пусть Г — псевдогеометрический граф для pG 2 (5, 32), а — вершина графа Г. Тогда Г имеет собственные значения k = 165, r = 3, s = - 33 и достигается равенство во втором условии Крейна

(s + 1)(k + s + 2rs) 6 (k + s)(r + 1)2.

Поэтому [а] является сильно регулярным графом с параметрами (165, 36, 3, 9) (псевдогеометрический граф для GQ(4, 8)), и Г2(а ) — сильно регулярный граф с параметрами (320, 99,18, 36) (см. [1, теорема 8.15]). В работе найдены возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярного графа с параметрами (320, 99, 18, 36).

• (0 2013 Махнев А. А., Кагазежева А. М.

• ¹    Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований, проекты № 12-01-00012, № 12-01-91155-ГФЕН.

Теорема 1. Пусть Γ является сильно регулярным графом с параметрами (320, 99, 18, 36), G = Aut(G), g — элемент простого порядка p из G, Ω = Fix(g). Тогда π(G) ⊆ { 2, 3, 5, 7, 11 } и выполняется одно из следующих утверждений:

• (1)    Ω — пустой граф, p = 5 и α1(g) ∈ { 0, 120 } или p = 2 и α1(g) ∈ { 0, 48, 96, 144, 192, 240, 288 } ;

• (2)    Ω является одновершинным графом, p = 11 и α1 (g) = 66;

• (3)    Ω является m-кокликой, p = 3, m = 3t + 2, 3 6 t 6 14 и α1 (g) - 9m - 6 делится на 72;

• (4)    Ω — объединение l изолированных ребер, 2 6 l 6 29, p = 2 и α1 (g) - 6l делится на 48;

• (5)    p = 11 и либо

• (i)    | Ω | = 67 и α1 (g) = 33, либо

• (ii)    | Ω | = 78 и α1 (g) = 66, либо

• (iii)    | Ω | = 89 и α1(g) = 99;

• (6)    p = 7 и либо

• (i)    Q = Кз х 4 и a 1 (g) E { 84, 252 } , либо

• (ii)    | Ω | = 7s + 5 , 2 6 s 6 10 , α1(g) = 21r и s - r + 3 делится на 8 , либо

• (iii)    | Ω | = 96 и α1(g) = 0 ;

• (7)    p = 5 и либо

• (i)    | Ω | = 90 , α1 (g) = 90 , на Γ - Ω имеются 36 пятиугольных h g i -орбит и 10 кокликовых;

• (ii)    | Ω | = 85 , α1 (g) = 15 , на Γ - Ω имеются 6 пятиугольных h g i -орбит и 41 кокли-ковая;

• (iii)    | Ω | = 80 , α1 (g ) ∈ { 0, 120 } , на Γ - Ω имеются 48 пятиугольных h g i -орбит или 48 кокликовых;

• (iv)    | Ω | = 5s , 3 6 s 6 15 , α1(g) = 120r + 15s , r ∈ {- 2, - 1, 0, 1, 2 } ;

• (8)    p = 3 , | Ω | = 3t + 2 , Ω не содержит вершин степени | Ω | - 2 и либо

• (i)    Ω является объединением двух изолированных вершин и K 3 _, 3 -подграфа, α1 (g) делится на 72 , либо

• (ii)    | Ω | = 80 или | Ω | = 140 и α1 (g) = 0 , либо

• (iii)    | Ω | = 3t+2 , 3 6 t 6 25 , α1(g) = 72s+9t+54 и s ∈ {- 3, - 2,...,4 } ;

• (9)    p = 2 и либо

• (i)    Ω — куб и α1 (g)/24 — нечетное натуральное число, либо

• (ii)    α1 (g) = 0 , | Ω | = 16s , s ∈ { 1, 2, . . . , 9 } , либо

• (iii)    α1 (g) 6 = 0 , | Ω | = 2t , 5 6 t 6 70 и α1 (g) = 48r + 6t .

• 1.    Предварительные результаты

В этом параграфе приведены некоторые вспомогательные результаты.

Лемма 1. Пусть Γ — сильно регулярный граф с параметрами (v, k, λ, µ) , ∆ — индуцированный подграф с N вершинами, M ребрами и степенями вершин d1 , . . . , d N . Тогда

(v — N ) — (kN — 2M ) + AM + ^^( 2 ^ - M) - ^^ (2 ) = xo + ^^ ( 2 )x i

и ixi 6     xi     i2xi, где xi — число вершин из Γ - ∆, смежных точно с i вершинами из ∆.

C Подсчитав число вершин в Г — А, число ребер между А и Г — А и число 2-путей с концами в А и средней вершиной в Г — А, получим равенства v — N = Р X i , kN — 2M = P ix , и XM + ^(( N ) — M ) — E , ^N=1 (*) = P (2)x i .

Вычитая второе равенство из суммы первого и третьего, получим равенство из заключения леммы.

Квадратный трехчлен ^(i — x ) ² X i = P i²X i — 2x^ ix i + X² P X i неотрицателен. Поэтому дискриминант квадратного трехчлена (Р ix i ) ² — Px i Pi ² X i неположителен. B

Лемма 2 [2, лемма 2] . Пусть Г является сильно регулярным графом с целыми собственными значениями, g — автоморфизм графа Г простого порядка р, и х — характер проекции мономиального представления на подпространство размерности m собственных векторов матрицы смежности графа, отвечающих неглавному собственному значению. Тогда a i (g) = a i (g l ) для любого l, не кратного р и m — x(g), делится на р.

Лемма 3. Пусть Г является сильно регулярным графом с параметрами (320, 99,18, 36). Тогда выполняются следующие утверждения:

• (1)    порядок коклики в Г не больше 44 и порядок клики в Г не больше 4;

• (2)    если Г содержит регулярный подграф А степени d на w вершинах, то — 21 6 d — (99 — d)w/(320 — w) 6 3, причем в случае равенства каждая вершина из Г — А смежна точно с (99 — d)w/(320 — w) вершинами из А;

• (3)    значение характера, полученного при проектировании мономиального представления на подпространство размерности 44, на элементе g Е Aut(P) равно X2(g) = (3ao(g) — ai(g))/24 + 4, и 44 — X2(g) делится на р.

C Ввиду границы Цветковича [3] порядок коклики в Г не больше 44. Ввиду границы Хофмана для клик порядок клики в Г не больше 5. Пусть L является 5-кликой из Г, X i — множество вершин из Г — L, смежных точно с i вершинами из L, x i = | X i | . Тогда P X i = 315, P ix i = 475, P (2)x i = 150, поэтому x o + P (ⁱ21)x _i = — 10, противоречие.

Если Г содержит регулярный подграф А степени d на w вершинах, то по лемме 1.2 из [4] имеем — 21 6 d — (99 — d)w/(320 — w) 6 3.

По лемме 2.6 из [4] значение характера, полученного при проектировании мономиального представления на подпространство размерности 44, на элементе g Е Aut(P) равно X2(g) = (3ao(g) — ai(g))/24 + 4. По лемме 2 число 44 — Х2(g) делится на р. в

Лемма 4. Пусть Г является сильно регулярным графом с параметрами (320, 99,18, 36), U — трехвершинный подграф из Г, Y i — множество вершин из Г — U, смежных точно с i вершинами из U, y _i = | Y i | . Тогда выполняются следующие утверждения:

• (1)    для двух вершин u, w подграф Г ₂ (u) П Г ₂ (w) содержит 156 вершин, если u, w не смежны; 140 вершин, если u, w смежны;

• (2)    число у о + уз равно 128, если U является кокликой; равно 77 , если U является кликой;

• (3)    число у о + уз равно 95, если U является 2-путем; равно 112, если U — объединение изолированной вершины и ребра.

• 2.    Автоморфизмы графа с параметрами (320, 99,18,36)

C Для двух несмежных вершин u, w граф Г содержит 36 вершин из [u] П [w], по 63 вершины из [u] — [w], [w] — [u] и 156 вершин из Г2(u) П Г2(u g ). Для смежных вершин u, w граф Г содержит 18 вершин из [u] П [w], по 80 вершин из [u] — w р [w] — u ^p и 140 вершин из Г2(u) П Г2(u g ).

Если U является 3-кокликой, то Г содержит 3(36 — уз) вершин из Y2, 3(27+уз) вершин из Yi и 128 — у з вершин из Yo , поэтому уо + у з = 128. Аналогично доказывается, что уо + уз = 77, если U является кликой.

Если U является геодезическим 2-путем U1U2из, то Y2 содержит 35 — уз вершин из [ui] П [из] и по 18 — уз вершин из [u _i ] П [u ₂ ], [u ₂ ] П [из], Y _i содержит 61 + уз вершин из [и ₂ ] и по 45 + уз вершин из [ui], [из], Y0 содержит 95 — уз вершин, поэтому уо + уз = 95.

Если U объединение изолированной вершины u1 и ребра { u2 , u3 } , то Y2 содержит 18 — уз вершин из [и ₂ ] П [из] и по 36 — уз вершин из [ui] П [u ₂ ], [ui] П [из], Y _i содержит 27 + у з вершин из [ui] и по 44 + у з вершин из [и2], [из], Y o содержит 112 — у з вершин, поэтому уо + у з = 112. B

До конца работы будем предполагать, что Г является сильно регулярным графом с параметрами (320, 99,18, 36). Пусть g — автоморфизм простого порядка p графа Г и fi = Fix(g).

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

• (1)    если fi — пустой граф, то либо p = 5 и ai(g) G { 0,120 } , либо p = 2 и ai(g) 6 { 0,48, 96,144,192, 240,288 } ;

• (2)    если fi является n-кликой, то n = 1, p = 11 и ai(g) = 66;

• (3)    если fi является m-кокликой, m > 2, то p = 3, m = 3t+2, 3 6 t 6 14 и ai(g) — 9m — 6 делится на 72;

• (4)    если fi — объединение l > 2 изолированных клик, но fi не является кокликой, то p = 2, fi является объединением изолированных ребер, 1 6 29 и a _i (g) — 61 делится на 48.

• <1    Пусть fi — пустой граф. Тогда p G { 2, 5 } . Если p = 5, то по целочисленности х2(g) число ai(g) делится на 24. Но в случае ai (g) = 240 на Г возникает кликовая h g i орбита длины 5, противоречие с леммой 3.

Если p = 2, то число 44 — X2(g) = 40 + ai(g)/24 четно, поэтому a _i (g) делится на 48. Утверждение (1) доказано.

Пусть X i — множество вершин из Г — fi, смежных точно с i вершинами из fi, x i = | X i | .

Пусть fi является n-кликой. Тогда n 6 4. Если n = 1, то p делит 99 и 220, поэтому p = 11. По целочисленности X2(g) число ai(g) — 3 делится на 24, поэтому ai(g) = 99.

Если n > 2, то p делит 80 и 140, поэтому p G { 2, 5 } . Но в случае p = 5 число 18 — (n — 2) делится на 5, противоречие. Поэтому p = 2 и n G { 2,4 } . Так как каждая вершина из Г — fi смежна с четным числом вершин из fi, то n = 4. Отсюда xo + x ₂ + х ₄ = 316, x ₂ + 2x4 = 192 и x ₂ + 6x4 = 96, противоречие. Утверждение (2) доказано.

Пусть fi является m-кокликой, m > 2. Тогда p делит 36 и 63, поэтому p = 3 и m = 3t + 2. По целочисленности X2(g) число ai(g) — 9m — 6 делится на 24, поэтому ai(g) = 24r + 9m + 6, X2(g) = r + 4. По лемме 3 число 44 — X2(g) = r делится на 3. Утверждение (3) доказано.

Пусть fi содержит ребро и является объединением 1 изолированных клик, 1 > 2. Тогда p делит 80 и 36, поэтому p = 2. Если fi содержит изолированную вершину, то p делит 99, противоречие. Пусть fi содержит изолированную 4-клику L, Y i — множество вершин из Г — L, смежных точно с i вершинами из L, y i = | Y). Тогда уо + у 2 =316, 2у2 =4 • 96 = 384, у ₂ = 6 • 16 = 96, противоречие. Итак, fi является объединением 1 изолированных ребер, и по лемме 3 имеем 1 6 29. По целочисленности X2(g) число ai (g) — 61 делится на 24, поэтому ai(g) = 24r + 61, X2(g) = — r + 4. По лемме 3 число 44 — х2 (g) = 40 + r четно. B

В леммах 6-8 предполагается, что fi содержит геодезический 2-путь bac.

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

• (1)    Γ не содержит собственных сильно регулярных подграфов с λ = 18, µ = 36 и | Ω | не больше 156 (не больше 140, если α1 (g) 6 = 0);

• (2)    если p > 2 и | Ω | > 95, то α1 (g) = 0;

• (3)    если α1 (g) = 0, то α0 (g) делится на 8, а по лемме 3 число 40 - α0 (g)/8 делится на p;

• (4)    для любой вершины a ∈ Ω подграф [a] не содержится в Ω.

C Пусть Γ содержит собственный сильно регулярный подграф ∆ с параметрами (v ⁰ , k ⁰ , 18, 36). Тогда 4(k ⁰ - 36) + 18 ² = n ² для некоторого натурального числа n. Отсюда n ∈ { 18, 20, 22 } и k ⁰ ∈ { 36, 55, 76 } соответственно. Но в последнем случае 36 не делит k ⁰ (k ⁰ - 19), а во втором ∆ имеет собственные значения 1, - 19 и кратность 1 равна 18 · 55 · 74/(20 · 36), противоречие. Значит, n = 18 и ∆ = K 2_×18, получили противоречие с леммой 3. Теперь утверждение (1) следует из леммы 4.

Пусть U — трехвершинный подграф из u ^{h g i} , Y i — множество вершин из Γ - U, смежных точно с i вершинами из U, y i = | Y i | . Из леммы 4 следует, что | Ω | 6 95, если u ^{h g i} содержит геодезический 2-путь, и | Ω | 6 77, если u ^{h g i} содержит 3-клику. В случае | Ω | > 95 подграф u ^{h g i} не содержит геодезических 2-путей и является кокликой. Утверждение (2) доказано.

Пусть α1 (g) = 0. Тогда по целочисленности χ2 (g) число α0 (g) делится на 8, а по лемме 3 число 40 - α0 (g)/8 делится на p. Утверждение (3) доказано.

Пусть для некоторой вершины a ∈ Ω имеем [a] ⊂ Ω. Тогда для u ∈ Γ - Ω получим | [u] ∩ Ω | = 36 и u ^{h g i} является кокликой, поэтому α1 (g) = 0, и по утверждению (3) имеем | Ω | > 104. Теперь для b ∈ Ω - a ^⊥ подграф [b] не пересекает Γ - Ω, поэтому [u] ∩ [b] содержится в Ω и совпадает с [a] ∩ [u] = [a] ∩ [b]. Противоречие с тем, что любые две вершины из [u] ∩ (Γ - Ω) смежны с u и с 36 вершинами из [a] ∩ [b]. B

Лемма 7. Если p > 3, то | Ω | 6 max { 95, 131 - p } . Далее, p 6 17.

C Если p > 36, то Ω — сильно регулярный подграф с параметрами (v ⁰ , k ⁰ , 18, 36), противоречие с леммой 6. Если p > 17, то Ω — подграф с λΩ = 18.

Пусть p > 3. Если | Ω | > 95, то по лемме 6 любая орбита u ^{h g i} является кокликой. Поэтому для любой 3-коклики U из u ^{h g i} подграф X0 (U) ∪ X3(U) содержит Ω и p - 3 вершин из u ^{h g i} - U. Значит, | Ω | 6 128 - (p - 3).

Пусть p = 31. Тогда степень вершины в графе Ω равна 37 или 68, | Ω | ∈ { 72, 103 } и µΩ ∈ { 5, 36 } . Если | Ω | = 72, то Ω — регулярный граф степени 37 (иначе Ω содержит по крайней мере 2 вершины a, b степени 68 и | Ω(a) ∪ Ω(b) | > 72). В этом случае Ω — сильно регулярный граф с параметрами (72, 37, 18, 36), получили противоречие. Значит, | Ω | = 103. По целочисленности χ2 (g) число α1(g) - 3 делится на 24, — противоречие.

Пусть p = 29. Тогда степень вершины в графе Ω равна 41 или 70, | Ω | ∈ { 59, 88 } и µ _Ω ∈ { 7, 36 } . Если | Ω | = 59, то Ω — регулярный граф степени 41, получили противоречие. Значит, | Ω | = 88. По целочисленности χ2 (g) число α1 (g) делится на 24, противоречие.

Пусть p = 23. Тогда степень вершины в графе Ω равна 30, 53 или 76, | Ω | ∈ { 44, 67, 90 } и µΩ ∈ { 13, 36 } . Если | Ω | = 44, то Ω — сильно регулярный граф с параметрами (44, 30, 18, 13), получили противоречие с тем, что 13 не делит 30 · 11. Если | Ω | = 67, то Ω — регулярный граф степени 30 и число ребер между Ω(a) и Ω - a ^⊥ равно 30 · 11, но не меньше 36 · 13, — противоречие. Значит, | Ω | = 90. По целочисленности χ2(g) число α1 (g) - 6 делится на 24, — противоречие.

Пусть p = 19. Тогда степень вершины в графе Ω равна 23, 42, 61 или 80, | Ω | ∈

{ 54, 73, 92 } и ^ q G { 17, 36 } . Если | Q | = 54, то по целочисленности Х2(g) число ai(g) — 6 делится на 24, получили противоречие.

Если | Q | = 92, то по целочисленности Х2(g) число a i (g) — 12 делится на 24, поэтому a _i (g) = 228. Противоречие с тем, что каждая h g i -орбита длины 19 является кликой.

Пусть | Q | =73. Тогда степень каждой вершины в Q равна 23 или 42. Допустим, что Q содержит вершину а степени 23. Тогда число ребер между Q(a) и Q — а ^ не больше 23 ^ 23+18 ^ 17, но не меньше 49 - 17, — противоречие. Значит, Q — регулярный граф степени 42 на 73 вершинах. Тогда число ребер между Q(a) и Q — а ^ равно 23 • 42 = 36x + 17(30 — x). Отсюда x = 24 и Q — а ^ содержит 6 вершин степени 25. Для двух смежных вершин d, е степени 25 в Q — а ^ подграф Q(d) П [e] содержит не менее 20 вершин из Q — а ^ , — противоречие. B

Лемма 8. Верно неравенство p = 17.

C Пусть p = 17. Тогда степень вершины в графе Q равна 14, 31, 48, 65 или 82, | Q | G { 31,48, 65, 82 } , A q G { 1,18 } и _№ G { 2,19, 36 } .

Если | Q | = 31, то Q — сильно регулярный граф с параметрами (31,14,1, 2), получили противоречие с тем, что 31 • 14 • 1 не делится на 3.

Если | Q | = 48, то по целочисленности X2(g) число a _i (g) делится на 24, — противоречие.

Если | Q | = 65, то по целочисленности X2(g) число ai(g) — 3 делится на 24, поэтому a _i (g) = 51. Далее, степень вершины в Q равна 14, 31 или 48. Допустим, что Q содержит вершину а степени 14. Тогда число ребер между Q(a) и Q — а ^ равно 50, но не меньше 14 • 12, — противоречие. Значит, Q содержит вершину а степени 48. Тогда любая вершина из Q(a) имеет степень 31 в Q, и число ребер между Q(a) и Q — а ^ равно 48 • 12, но не больше 16 • 36. Поэтому степень каждой вершины из Q — а ^± в Q равна 48, получили противоречие.

Если | Q | = 82, то по целочисленности X2(g) число ai(g) — 6 делится на 24, поэтому ai(g) = 102. Далее, степень вершины в Q равна 31, 48 или 65. Допустим, что Q содержит вершину а степени 65. Тогда любая вершина из Q(a) имеет степень 31 в Q, и число ребер между Q(a) и Q — а ^ равно 65 • 12, но не больше 16 • 36, — противоречие.

Если Q — регулярный граф степени 31 на 82 вершинах, то ввиду леммы 3 имеем 31 — 68 • 82/238 6 3, получили противоречие.

Значит, Q содержит вершину а степени 48. Пусть Q — а ^± содержит вершину е, смежную точно с двумя вершинами из Q(a). Тогда [е] содержит 29 вершин из Q — а ^ , и для b G Q(a) П [е] подграф Q(b) П [е] содержит 0 или 1 вершину из [а] и от 9 до 12 вершин из Q — а ^ , — противоречие.

Пусть Qo подграф из Q, индуцированный вершинами, имеющими степень 48 в Q, A = Qo(a), B = Qo — а ^± , Ao — множество вершин из Q(a), смежных с 29 вершинами из Q — а ^ , B o — множество вершин из Q — а ^ , смежных с 36 вершинами из Q(a). Тогда Ao и Bo являются кокликами и число ребер между Q(a) и Q — а ^ равно 29x + 12(48 — x) = 36y + 19(33 — y), поэтому x = y + 3. Если c, d — две вершины из A, то Q(c) П [d] содержит от 25 до 29 вершин из Q — а^, поэтому A = Ao и Q(a) — регулярный граф степени 18, содержащий x вершин из Qo .

Покажем, что если | Q(a) П [е] | = 19 для е G Q — а ^± , то степень е в Q равна 31. В противном случае Q содержит 19 вершин из [а] П [е], по 29 вершин из [а] — [е], [е] — [а] и 3 вершины f _i , f ₂ , f3 вне а ^± U е ^± . Ясно, что [а] П [е] состоит из вершин степени 31 в Q. Пусть Q(e) содержит j вершин bi,..., b j из B. Без ограничения общности j > x. Противоречие с тем, что x = y + 3.

Итак, Qo содержит у + 3 вершин из [а] и у вершин вне а \ получили противоречие с тем, что Qo(c) содержит у + 2 вершин для c Е Qo(a). B

Лемма 9. Число p не равно 13.

C Пусть p = 13. Тогда степень вершины в графе Q равна 21, 34, 47, 60, 73 или 86, | Q | е { 34,47, 60, 73, 86,112 } , A q Е { 5,18 } и _№ Е { 10, 23, 36 } .

Если | Q | = 34, то Q — сильно регулярный граф с параметрами (34, 21,18,10), противоречие.

Пусть | Q | = 47. Тогда степень вершины в Q равна 21 или 34. По целочисленности Х2(g) число ai (g) + 3 делится на 24, поэтому ai(g) = 117. Если Q содержит вершину a степени 21, то число ребер между Q(a) и Q — а ^ равно 250 = 15x + 2(21 — x), поэтому x = 16. Пусть c _i ,... ,С 5 — вершины из Q(a), смежные с парами вершин из Q — а ^ . Так как Г не содержит 5-клик, то можно считать, что вершины ci, С2 не смежны, — противоречие с тем, что [ci] П [c ₂ ] содержит не менее 17 вершин из Q(a). Значит, Q — регулярный граф степени 34, поэтому Q — сильно регулярный граф с параметрами (47, 34,18, 23), получили противоречие.

Если | Q | = 60, то по целочисленности X2(g) число a _i (g) — 12 делится на 24, поэтому ai(g) = 156. Далее, степень вершины в Q равна 21, 34 или 47. Если Q содержит вершину а степени 47, то число ребер между Q(a) и Q — а ^± равно 94 = 36x+23y+ 10(12 — x — у), — противоречие. Если Q содержит вершину а степени 21, то число ребер между Q(a) и Q — а ^ равно 380 = 28x + 15у + 2(21 — x — у), поэтому 2x + у = 26 и 21 — x — у = x — 5. Так как Q(a) содержит x вершин степени 5, то x четно. В случае x > 9 противоречие получается как и в предыдущем абзаце. Значит, x 6 8, Q(a) содержит 13 вершин степени 18, поэтому Q(a) содержит 4-клику, получили противоречие. Значит, Q — регулярный граф степени 34, и число ребер между Q(a) и Q — а ^ равно 34 • 15 = 23x + 10(25 — x), поэтому x = 20 и Q — а ^± содержит 5 вершин степени 24, образующих клику, — противоречие.

Если | Q | = 73, то | Г — Q | = 13 • 19, по целочисленности X2(g) число a _i (g) — 3 делится на 24, поэтому ai(g) = 195. Для любой четверки индексов ii,..., i ₄ Е { 1, 2,..., 6 } найдутся три h g i -орбиты длины 13, в которых вершина u смежна с u j для j Е { i _i ,..., i ₄ } . Ввиду леммы 1.5 из [5] каждая такая орбита содержит 4-клику и не попадает в окрестность никакой вершины из Q. Так как число четверок в { 1, 2,... , 6 } равно 15, то 45 орбит вида u h g i не попадают в окрестность никакой вершины из Q. Противоречие с тем, что число h g i -орбит длины 13 равно 19.

Если | Q | = 86, то по целочисленности X2(g) число ai(g) + 6 делится на 24, поэтому ai (g) = 306, — противоречие.

Если | Q | = 112, то | Г — Q | = 13 • 16 и a _i (g) = 0. Пусть U является 3-кокликой из u h g i . Тогда Xo(U) U X3 (U) содержит 112 вершин из Q, 10 вершин из u h g i и еще 6 вершин. Пусть w Е Г — (Q U u h g i ). Если w смежна не более чем с 2 вершинами из u h g i , то Xo (U) содержит не менее 7 вершин из w ^{h g i} . Если w смежна точно с 3 вершинами из u ^{h g i} , то для U = [w] П u h g i подграф Xo (U) U X3 (U) содержит 7 вершин из w h g i . В обоих случаях имеем противоречие.

Допустим, что w смежна точно с 4 вершинами из u h g i . Тогда Xo(U) содержит вершину из w ^{h g i} . Поэтому для по крайней мере 9 орбит w ^{h g i} вершина w смежна по крайней мере с 5 вершинами из u ^{h g i} . Таким образом, число 3-лап с концевыми вершинами в u ^{h g i} и центральной вершиной в Г — (u h g i U Q) не меньше 4 • 13 • 6 + 10 • 13 • 9 = 13 • 114. Число троек вершин в u ^{h g i} равно 13 • 22, поэтому некоторая 3-коклика U из u ^{h g i} попадает в окрестности 6 вершин из Г — (u ^{h g i} U Q). Противоречие с тем, что Xo(U) содержит вершину из Г — (u h g i U Q).

Теперь каждая вершина из Γ - (u ^{h g i} ∪ Ω) смежна по крайней мере с 5 вершинами из u ^{h g i} , число 3-лап с концевыми вершинами в u ^{h g i} и центральной вершиной в Γ - (u ^{h g i} ∪ Ω) не меньше 10 · 13 · 15. Противоречие с тем, что некоторая 3-коклика U из u ^{h g i} попадает в окрестности по крайней мере 7 вершин из Γ - (u ^{h g i} ∪ Ω). B

Лемма 10. Если p = 11, то верно одно из утверждений:

• (1)    | Ω | = 67 и α1(g) = 33;

• (2)    | Ω | = 78 и α1(g) =66;

• (3)    | Ω | = 89 и α1(g) =99.

C Пусть p = 11. Тогда степень вершины в графе Ω равна 11t, t ∈ { 2, 3, . . . , 8 } , | Ω | ∈ { 34, 45, 56, 67, 78, 89 } , λΩ ∈ { 7, 18 } и µΩ ∈ { 3, 14, 25, 36 } . Заметим, что Ω не содержит вершин степени | Ω | - 1. Если Ω содержит вершину a степени | Ω | - 12, то Ω - a ^⊥ — регулярный граф степени 8 на 11 вершинах. Противоречие с тем, что Ω - a ^⊥ содержит 5-клику. Отсюда, в частности, | Ω | 6 = 34.

Пусть | Ω | = 45. По целочисленности χ2 (g) число α1 (g) + 9 делится на 24, поэтому α1 (g) = 231. Противоречие с тем, что на Γ - Ω имеется кликовая h g i -орбита.

Пусть | Ω | = 56. По целочисленности χ2 (g) число α1 (g) делится на 24, поэтому α1 (g) = 264. Противоречие с тем, что на Γ - Ω имеется кликовая h g i -орбита.

Пусть | Ω | = 67. Тогда степень вершины в Ω равна 22, 33 или 44. По целочисленности χ2 (g) число α1 (g) - 9 делится на 24, поэтому α1 (g) = 33.

Если | Ω | = 78, то по целочисленности χ2 (g) число α1 (g) + 6 делится на 24, поэтому α1 (g) = 66. Далее, степень вершины в Ω равна 22, 33, 44 или 56.

Если | Ω | = 89, то | Γ - Ω | = 11 · 23, по целочисленности χ2 (g) число α1 (g) - 3 делится на 24, поэтому α1(g) = 99. B

Лемма 11. Если p = 7, то верно одно из утверждений:

• (1)    Ω = K3 × 4 и α1(g) ∈ { 84, 252 } ;

• (2)    | Ω | = 7s + 5, 2 6 s 6 10, α1(g) = 21r и s - r + 3 делится на 8;

• (3)    | Ω | = 96 и α1(g) = 0.

• 3.    Автоморфизмы малых порядков

C Пусть p = 7. Тогда степень вершины в графе Ω равна 7t + 1, t ∈ { 1, 2, . . . , 13 } , | Ω | = 7s+5, s ∈ { 1,2,... ,11 } или s = 13, λΩ ∈ { 4, 11, 18 } и µΩ ∈ { 1, 8, 15, 22, 29, 36 } .

Пусть | Ω | = 12. Тогда любая связная компонента графа Ω является одновершинным графом или сильно регулярным графом с параметрами (v ⁰ , 8, 4, 8). Поэтому Ω = K3_×4 . По целочисленности χ2 (g) число α1 (g) - 12 делится на 24, поэтому α1(g) ∈ { 84, 252 } .

Пусть | Ω | = 96. По лемме 6 имеем α1 (g) = 0.

Пусть | Ω | = 7s + 5, 2 6 s 6 11. По целочисленности χ2 (g) число α1(g) + 3s + 9 делится на 24, поэтому α1(g) = 21r и s - r + 3 делится на 8.

Пусть | Ω | = 82. Тогда h g i -орбиты длины 7 не содержат треугольников. Далее, r = 6 и α1 (g) = 126, поэтому найдутся две h g i -орбиты длины 7, являющиеся графами степени 4. Противоречие с тем, что такая орбита содержит треугольник. B

В этом параграфе предполагается, что Γ является сильно регулярным графом с параметрами (320, 99, 18, 36), g — автоморфизм простого порядка p графа Γ, и подграф Ω = Fix(g) содержит геодезический 2-путь.

Лемма 12. Пусть p = 5 и | Ω | = 5s. Тогда выполняются следующие утверждения:

• (1)    | Ω | = 90, α1 (g) = 90, на Γ - Ω имеются 36 пятиугольных h g i -орбит и 10 кокликовых;

• (2)    | Ω | = 85, α1 (g) = 15, на Γ - Ω имеются 6 пятиугольных h g i -орбит и 41 кокликовая;

• (3)    | Q | = 80, ai(g) G { 0,120 } , на Г — Q имеются 48 пятиугольных hg'i-орбит или 48 кокликовых;

• (4)    | Q | = 5s, 3 6 s 6 15, ai(g) = 120r + 15s, r G {— 2, — 1, 0,1, 2 } .

C Пусть p = 5. Тогда степень вершины в графе Q равна 5t + 4, t G { 1, 2,..., 18 } , | Q | = 5s, s G { 3,4,... , 19 } или s = 24, A q G { 3, 8,13,18 } и ^ _Q G { 1, 6,11,16, 21, 26, 31, 36 } .

Пусть Q содержит вершину a степени 9. Тогда Q(a) содержит вершину c степени 8. Поэтому либо Q(a) — сумма 3-клики и 6-коклики, либо Q(a) П [b] — восьмиугольник или объединение двух четырехугольников.

Если | Q | = 120, то по лемме 6 имеем ai(g) = 0. Если U является 3-кокликой из u h g i , то Xo(U) U X3(U) содержит 120 вершин из Q и 2 вершины из u h g i . Пусть w G Г — (Q U u h g i ). Если [w] содержит не более 1 вершины из u h g i , то Xo(U) содержит не менее 2 вершин из w h g i . Если [w] содержит не менее 3 вершин из u h g i , то для U С [w] подграф X3 (U) содержит w. В обоих случаях имеем противоречие. Значит, [w] содержит точно 2 вершины из u h g i , граф Г — Q регулярен степени 78. По лемме 3 выполняются неравенства — 21 6 78 — 21 • 200/120 6 3, — противоречие.

Если | Q | G { 80, 85, 90, 95 } , то по лемме 6 на Г — Q нет кликовых h g i -орбит.

Пусть | Q | = 95. По целочисленности X2(g) число ai(g) + 3 делится на 24, поэтому a1(g) G { 45,165 } . Но в случае a1(g) = 165 на Г — Q найдется кликовая h g i -орбита. Значит, на Г — Q имеются 18 пятиугольных h g i -орбит и 27 кокликовых, причем ввиду леммы 4 пятиугольная орбита не попадает в окрестность никакой вершины из Q. Пусть A (B) — множество вершин из Г — Q, лежащих в пятиугольных (кликовых) h g i -орбитах. Тогда | А | = 90, | В | = 135. Для u G A имеется 95 • 36 2-путей с началом в u, концом в Q и средней вершиной в B. Поэтому | [u] П B | > 95. Противоречие с тем, что | [u] П [u^g] | содержит не менее 55 вершин из B .

Пусть | Q | = 90. По целочисленности X2(g) число a1(g) + 6 делится на 24, поэтому ai(g) = 90, на Г — Q имеются 36 пятиугольных h g i -орбит и 10 кокликовых. Ввиду леммы 4 пятиугольная орбита попадает в окрестности не более 5 вершин из Q.

Пусть | Q | = 85. По целочисленности X2(g) число a1(g) + 9 делится на 24, поэтому ai(g) = 15, на Г — Q имеются 6 пятиугольных h g i -орбит и 41 кокликовая. Ввиду леммы 4 пятиугольная орбита попадает в окрестности не более 10 вершин из Q.

Пусть | Q | = 80. По целочисленности Х2(g) число ai(g) делится на 24, поэтому ai(g) G { 0,120 } . В случае a1 (g) = 120 на Г — Q имеются 48 пятиугольных h g i -орбит, и ввиду леммы 4 пятиугольная орбита попадает в окрестности не более 15 вершин из Q.

Пусть | Q | = 5s, s 6 15. По целочисленности X2(g) число ai(g) — 15s делится на 24, поэтому a1 (g) = 120r + 15s, r G {— 2, — 1, 0,1, 2 } . B

Лемма 13. Если p = 3 и | Q | = 3t + 2, то Q не содержит вершин степени | Q | — 2 и выполняются следующие утверждения:

• (1)    Q является объединением двух изолированных вершин и Кз , з -подграфа, ai(g) делится на 72 ;

• (2)    | Q | = 80 или | Q | = 140 и a1(g) = 0;

• (3)    | q | = 3t + 2, 3 6 t 6 25, ai(g) = 72s + 9t + 54 и s G {— 3, — 2,... , 4 } .

C Пусть p = 3 и | Q | = 3t + 2. Тогда степень вершины в графе Q равна 3i, любое ребро графа Q лежит в 3j треугольниках из Q, а для любых двух вершин a, b, находящихся на расстоянии 2 в Q, имеем | Q(a) П [b] | = 31.

Если Q содержит вершину a степени | Q |— 2, то для b G Q(a) подграф Q(b) содержит a, кратное 3 число вершин из Q(a) и еще не более одной вершины, — противоречие.

Пусть |Q| = 8. Тогда степень вершины в Q равна 0 или 3, поэтому Q является объединением двух изолированных вершин и K3,3-подграфа. Далее, ai(g) = 24r и 44 — Х2(g) = 39 + r делится на 3.

Пусть t > 25. Тогда ai(g) = 0, поэтому | Q | G { 80,104 } .

Пусть | Q | = 3t+2, t 6 25. Тогда ai(g) — 9t — 6 делится на 24, поэтому ai(g) = 24r+9t+6 и r G {— 9, — 8,..., 12 } . Далее 44 — x 2 (g) = 40 + r делится на 3, поэтому r = 3s + 2. B

Лемма 14. Пусть p = 2. Тогда верны следующие утверждения:

• (1)    Q — куб и ai (g)/24 — нечетное натуральное число;

• (2)    ai(g)=0, | Q | = 16s, s G { 1, 2,..., 9 } ;

• (3)    a _i (g) = 0, | Q | = 2t, 5 6 t 6 70, и a _i (g) = 48r + 6t.

C Пусть p = 2 и | Q | = 2t. Тогда степень вершины в графе Q равна 2i + 1, любое ребро графа Q лежит в 2j треугольниках из Q, а для любых двух вершин a, b, находящихся на расстоянии 2 в Q, имеем | Q(a) П [b] | = 21.

Пусть | Q | = 6. Если Q содержит вершину a степени 5, то подграф Q(a) имеет нечетные параметры А ⁰ и ^ 0 , — противоречие. Значит, любая вершина имеет степень 1 или 3 в Q, снова получили противоречие. Пусть | Q | = 8. Если Q содержит вершину a степени 7, то подграф Q(a) имеет нечетные параметры А ⁰ и ^ 0 , — противоречие. Если любая вершина имеет степень 1 или 3 в Q, то Q получается удалением из K 4 , 4 максимального паросочетания (Q — куб). Если Q содержит вершину a степени 5, то подграф Q(a) имеет нечетные параметры А ⁰ и ^ 0 , противоречие. Далее, X2(g) =5 — a 1 (g)/24, 44 — X2(g) = 39 + ai(g)/24, поэтому ai(g)/24 — нечетное натуральное число. Утверждение (1) доказано.

Пусть ai(g) = 0. По лемме 6 имеем | Q | = 16s, s G { 1, 2,..., 9 } . Утверждение (2) доказано.

Пусть ai(g) = 0. По лемме 6 имеем | Q | 6 140. Далее, X2(g) = (6t — ai(g))/24 +4 и число 44 — х2(g) =40 — (6t — a _i (g))/24 четно. Поэтому a _i (g) = 48r + 6t. Лемма, а вместе с ней и теорема доказаны. B