Об автоморфизмах сильно регулярного графа с параметрами (95, 40, 12, 20)

Мы рассматриваем неориентированные графы без петель и кратных ребер. Если а, b — вершины графа Г, то через d(a, b) обозначается расстояние между а и b, а через r i (а) — подграф графа Г, индуцированный множеством вершин, которые находятся в Г на расстоянии i от вершины а. Подграф Г(а) = Г 1 (а) называется окрестностью вершины а и обозначается через [а], если граф Г фиксирован. Через а ^± обозначается подграф, являющийся шаром радиуса 1 с центром a. Пусть F — семейство графов. Граф Г называется локально F -графом, если [а] G F для любой вершины а £ Г.

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

Через K m ₁ ,...,m _n обозначим полный n-дольный граф с долями порядков m 1 , . . . , m n . Если m i = ... = m n = m, то соответствующий граф обозначается через K _nxm . Если m > 2, то граф K i,_m называется m-лапой. Для подграфа А через | А | обозначим число его вершин, а через X i (А) обозначим множество вершин из Г — А, смежных точно с i вершинами из А.

Частичной геометрией pG _a (s,t) называется система инцидентности, состоящая из точек и прямых, в которой каждая прямая содержит s + 1 точку, каждая точка лежит на t + 1 прямой (две прямые пересекаются не более, чем по одной точке) и для любой точки a, не лежащей на прямой L, найдется точно α прямых, проходящих через a и пересекающих L. Если a = 1, то геометрия называется обобщенным четырехугольником

• ¹    Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований, проект № 08-01-00009, и РФФИ-БРФФИ, проект № 08-01-90006).

и обозначается GQ(s,t). Если a = t, то геометрия называется сетью. Точечным графом частичной геометрии называется граф, вершинами которого являются точки геометрии, и две различные вершины смежны, если они лежат на одной прямой. Легко понять, что точечный граф частичной геометрии pG _a (s,t) сильно регулярен с параметрами v = (s + 1)(1 + st/a), k = s(t + 1), A = (s — 1) + (a — 1)t, ^ = a(t + 1). Любой сильно регулярный граф с такими параметрами для некоторых α, s, t называется псевдогеометрическим графом для pG _a (s, t).

В [1] доказано, что связный вполне регулярный граф, окрестности вершин которого являются псевдогеометрическими графами для pG 2 (4, t), либо является графом Тэйлора, либо сильно регулярен с параметрами (210, 95,40,45) (и окрестности вершин сильно регулярны с параметрами (95,40,12, 20)). В данной работе найдены возможные автоморфизмы сильно регулярного графа с параметрами (95,40,12, 20) и определены подграфы их неподвижных точек. Для автоморфизма g через a i (g) обозначим число пар вершин (u, u ^g ) таких, что d(u, u ^g ) = i.

Теорема. Пусть Г — сильно регулярный граф с параметрами (95,40,12, 20) , g — элемент простого порядка p из Aut (Г) и Q = Fix (g) . Тогда верно одно из утверждений:

• (1)    Q — пустой граф, p = 5 , a i (g) =50 и Г имеет кликовую h g i -орбиту или p = 19 , a i (g) = 38 ;

• (2)    Q является n-кликой, p = 3 и либо n = 2 и a i (g) сравнимо с 6 по модулю 12 , либо n = 5 и a i (g) делится на 12 ;

• (3)    Q является m-кокликой и либо

• (i)    p = 5 , m = 15 , a 1 (g) = a 1 (g ² ) = 20 или m = 10 , a 1 (g) E { 10, 70 } , либо

• (ii)    p = 2 , m нечетно, m 6 17 и a i (g) — 2m — 2 делится на 12 ;

• (4)    Q содержит 2-лапу и либо

• (i)    p = 3 , a 1 (g) = 0 и | Q | E { 11,17, 23, 29 } , либо

• (ii)    p = 2 , Q не является кокликой, | Г — Q | = 2t , 27 6 t 6 43 или t = 24 , и каждая вершина из Q смежна с вершиной из Г — Q .

С помощью этой теоремы получаем

Следствие. Пусть Г — точечный граф частичной геометрии pG 2 (4, 9) . Тогда Г не является вершинно симметричным.

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

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

Лемма 1.1. Пусть Г является сильно регулярным графом с параметрами (v, k, A, ^) и неглавными собственными значениями r, s , s < 0 . Если А — индуцированный регулярный подграф из Г степени d на w вершинах, то

w(k — d) s 6 d -          6 r, v-w причем одно из равенств достигается тогда и только тогда, когда каждая вершина из Г — А смежна точно с w(k — d)/(v — w) вершинами из А.

C Это утверждение хорошо известно (см., например, § 2 из [2]). B

Пусть Г является сильно регулярным графом с параметрами (95,40,12, 20) и неглавными собственными значениями 2, — 10. Если А — индуцированный регулярный подграф из Г степени d на w вершинах, то

— 10 6 d —

w(40 — d)

95 — w

6 2.

Поэтому число вершин в коклике (клике) не больше 19 (не больше 5). Если C является 19-кокликой из Г, то любая вершина из Г — C смежна точно с 10 вершинами из C .

Лемма 1.2. Пусть Г — сильно регулярный граф, имеющий параметры (у,к, X, ц). Тогда либо к = 2ц, X = ц — 1 (так называемый половинный случай), либо неглавные собственные значения n — m, —m графа Г — целые числа, где n2 = (X — ц)2 + 4(к — ц), n — X + ц = 2m и кратность n — m равна k(m ^(k+m). Далее, если m — целое число, µn большее 1, то m — 1 делит к — X — 1 и k—X—1

n = m — 1 +

к — X — 1 m — 1

ц = X + 2 + (m — 1)--- m—1

C Это лемма 3.1 из [3]. B

Доказательство теоремы опирается на метод Хигмена работы с автоморфизмами сильно регулярного графа, представленный в третьей главе монографии Камерона [4]. При этом графу Г отвечает симметричная схема отношений (X, { R q , ..., R 2 } ), где X — множество вершин графа, R q — отношение равенства на X, Ri — отношение смежности в Г, R2 — отношение смежности в дополнительном графе Г. Если P и Q — первая и вторая матрицы собственных значений схемы, то

P= к

\ v — к — 1

r

- r -

s

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

Подстановочное представление группы G = Aut (Г) на вершинах графа Г обычным образом дает матричное представление ^ группы G в GL(v, C ). Пространство C ^v является ортогональной прямой суммой собственных '^(С)-инвариантных подпространств W q ® W 1 ® W ₂ матрицы смежности графа Г. Пусть x i — характер представления ^ w i . Тогда для любого g ∈ G получим

Xi(g) = v-1 ^Qijaj (g), j=Q где aj (g) — число точек x из X таких, что (x, xg) G Rj. Заметим, что значения характеров являются целыми алгебраическими числами, и если правая часть равенства для xi (g) — число рациональное, то xi (g) — целое число.

Лемма 1.3. Пусть Г является сильно регулярным графом с параметрами (95, 40, 12, 20) , G = Aut (Г) , g G G и x i — характер, полученный при проектировании ^(G) на подпространство размерности 75 . Тогда x i (g) = (10a Q (g) + a i (g) — 50)/12 .

C Рассмотрим сильно регулярный граф Г с параметрами (95,40,12, 20). Тогда Г имеет неглавные собственные значения n — m = 2, — m = — 10 кратностей 75, 19 и

11   1            1   1     1

P =   40 2 — 10   , Q =   75   15/4    — 25/6   ,

\ 54 —3   9/         \ 19 —19/4 19/6 / и значение характера, полученного при проектировании на подпространство размерности 75, равно Х1 (g) = (15ao(g)+3/4ai(g) — 5/6a2(g))/19. Подставляя в эту формулу значение a2(g) = v — ao(g) — ai(g), получим Xi (g) = (1Oao(g) + ai(g) — 50)/12. В частности, 2 делит ai(g). B

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

XM + ц ((N) — M ) — £ (*)) = x o + X (i - 1)X i ,

(v

-

N ) — (kN — 2M) + f

где X i = X i (A)

C Подсчитав число вершин в Г — А, число ребер между А и Г — А и число троек вида (a, { b, c } ), где a Е Г — A, b,c Е А П [a], получим равенства:

v — N = ^xt, kN — 2M = X ixi,

^{XM +} ц ^((N)—M^)— X $ = е ⁽ 2>

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

• §2. Автоморфизмы графа с параметрами (95,40,12, 20)

В этом параграфе Г — сильно регулярный граф с параметрами (95,40,12, 20), g — автоморфизм простого порядка p графа Г и Q = Fix (g).

Лемма 2.1. Если Q — пустой граф, то выполняется одно из утверждений:

• (1)    p = 5 , a i (g) =50 и Г имеет 5-кликовую h g' i -орбиту;

• (2)    p = 19 , a i (g) = 38 .

C Так как 95 = 5 • 19, то p Е { 5,19 } .

Пусть p = 5. Тогда a i (g) = 5w и 12 делит 5w — 50, откуда w = 10 и a i (g) = 50 = a i (g ² ). Пусть t — число 5-кликовых h g i -орбит. Тогда 2(50 — 5t) + 5t 6 95, откуда t >  1. В частности, Г имеет 5-кликовую h g i -орбиту.

Пусть p = 19. Тогда a i (g) = 19w. Из целочисленности X i (g) следует, что 12 делит 19w — 50, откуда w = 2 и a _i (g) = 38. B

В леммах 2.2–2.10 предполагается, что g — автоморфизм простого порядка p графа Г и Q = Fix(g) содержит вершину a. Положим X t = X t (Q) и x t = | X i | .

Лемма 2.2. Пусть Q является n-кликой. Тогда p = 3 и либо n = 2 , x o = 27, x i = 54, X 2 = 12 и a i (g) сравнимо с 6 по модулю 12 , либо n = 5 , x 2 = 90 и a i (g) делится на 12 .

C Подсчитав число ребер между Q и Г — Q, а также число треугольников с основанием в Q и вершиной в Г — Q, получим равенства ^x t = 95 — n, ^2 ix t = n(41 — n), ^ (2) x t = ( П )(14 — n).

Ввиду границы Хофмана для клик имеем n 6 5.

Пусть n = 1. Тогда p делит 40 и 54, поэтому p = 2. Пусть u Е [a]. Тогда подграф [u] П [u ^g ] является g-допустимым, содержит четное число вершин и единственную неподвижную точку, противоречие.

Пусть n = 2. Тогда p делит 12 и 27, поэтому p = 3. Из целочисленности X i (g) следует, что a i (g) сравнимо с 6 по модулю 12. Далее, X i = 0 для i >  2 и вышеуказанная система имеет единственное решение х о = 27, X i = 54, X 2 = 12.

Пусть n = 3. Тогда p делит 11 и 27. Противоречие.

Пусть n = 4. Тогда p делит 10 и 27. Противоречие.

Пусть n = 5. Тогда p делит 9 и 27, поэтому p = 3. Из целочисленности X i (g) следует, что 12 делит a _i (g). Так как для fi достигается равенство в границе Хофмана для клик, то каждая вершина из Г — fi смежна с 2 вершинами из fi, т. е. X 2 = 90. B

Лемма 2.3. Пусть fi является m-кокликой (m >  2) . Тогда ^X i =95 — m, ^ix i = 40 m,    ₂ ⁱ X i = 20 (mm) и верно одно из утверждений:

• (1)    p = 5 и либо m = 15 и a _i (g) = a _i (g ² ) = 20 , либо m = 10 и a _i (g) Е { 10, 70 } ;

• (2)    p = 2 , m нечетно, 5 6 m 6 17 , a i (g) — 2m — 2 делится на 12 , в случае m = 3 имеем х о = 32 и X 2 = 60 , а в случае m = 5 имеем х о = 15 , X 2 = 50 и X 4 = 25 .

C Уравнения для x i получим, как и в лемме 2.2. B

Для различных вершин а, b Е fi элемент g действует полурегулярно на [а] П [b], [a] — b ^ и на Г 2 (а) П Г 2 (Ь) — fi, поэтому p делит 20 и 33 — (m — 2). Отсюда либо p = 5 и m делится на 5, либо p = 2 и m нечетно. Из целочисленности X i (g) следует, что a i (g) — 2m — 2 делится на 12.

Ввиду границы Хофмана для коклик имеем m 6 19 ив случае m =19 любая вершина из Г — fi смежна точно с 10 вершинами из fi.

Пусть p = 5. Если m = 15, то a i (g) Е { 20, 80 } . Но в случае a i (g) = 80 получим a _i (g) + a _i (g ² ) > 100 и Г имеет 5-кликовую h g i -орбиту U . Противоречие с тем, что а смежна с 0 или 5 вершинами из U . Значит, a i (g) = a i (g ² ) = 20.

Если m = 10, то a _i (g) Е { 10, 70 } .

Если m = 5, то a i (g) = 60. Отсюда a i (g) + a i (g ² ) = 120 и снова Г имеет 5-кликовую h g i -орбиту U , противоречие.

Пусть p = 2. Если m = 19, то a i (g) — 4 делится на 12 и каждая вершина из Г — fi смежна с 10 вершинами из fi. Допустим, что вершины u, u g смежны. Тогда [u] П [u g ] содержит 10 вершин из fi и еще 2 вершины w, w g . Пусть а, b — различные вершины из fi — [u]. Если вершины а, w несмежны, то [а] П [b] содержит не менее 22 вершин из [u] U [u g ], противоречие. Значит, [w] содержит fi — [u] и 1 вершину из [u] П fi, и [а] П [b] содержит w, w g и по 9 вершин из [u] — [u g ], [u g ] — [u]. Теперь для вершин c, e Е fi — ([u] U { а, b } ) подграф [c] П [e] содержит по 18 вершин из ([u] — ([u g ] U [а])) U ([u] — ([u g ] U [b]) и из ([u g ] — ([u] U [а])) U ([u g ] — ([u] U [b]), противоречие. Значит, a i (g) = 0, противоречие с тем, что a _i (g) — 4 делится на 12.

Пусть m = 3. Тогда х о = 32 и X 2 = 60.

Пусть m = 5. Тогда х о + х ₂ + х ₄ = 90, 2x 2 + 4x 4 = 200, х ₂ + 6x 4 = 200. Поэтому х о = 15, х 2 = 50, х 4 = 25. B

Лемма 2.4. fi не является объединением m (m > 2) изолированных клик порядков n i ,..., n _m и n i > 2 .

C Если а, c — несмежные вершины из fi, то g действует полурегулярно на [а] П [c] и p делит 20.

Пусть n i > 2 и а, b — смежные вершины из n i -клики, лежащей в fi. Так как g действует полурегулярно на [а] — b ^± и на [а] П [b] — fi, то p делит 27 и 12 — (n _i — 2), поэтому p = 3, противоречие. B

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

• (1)    если Г содержит полный двудольный подграф K _m,n , то mn 6 100 ;

• (2)    если x Е fi, u Е Г — fi — [x] и [x] П [u] содержится в fi , то р = 2 ;

• (3)    fi не является сильно регулярным графом с параметрами (v ' , к' , 12, 20) и р 6 19 ;

• (4)    fi не является сильно регулярным графом с параметрами (v ' , к ' , 12, 20 — р) или (v ⁰ , k ⁰ , 12 — p, 20) .

C Если Г содержит полный двудольный подграф А = K m,n , то наименьшее собственное значение графа А равно — ^ mn и не меньше — 10, поэтому mn 6 100. Утверждение (1) доказано.

Пусть x Е fi и u Е Г — (fi U [x]). Если [x] П [u] С fi, то | fi П [u] | > 20 и подграф u h g i является кокликой. Отсюда | fi П [u] | = | fi П [u g ] | =20 и [u] П fi = [u g ] П fi. Заметим, что | T 2 (u) П ^(u g ) | =33 и степень x в графе ^(u) П ^(u g ) равна 20. Если р >  3, то Г 2 (u) П ^(u g ) содержит вершину u g и степень u g в графе Г 2 (u) П ^(u g ) равна 20. Противоречие с тем, что [x] П [u g ] = [u] П [u g ]. Значит, р = 2. Утверждение (2) доказано.

Пусть fi — сильно регулярный граф с параметрами (v ' , к ' , 12, 20). Тогда n ² = (А — +) ² + 4(к ' — +) = 4к ' — 16 и 20 делит к ' (к ⁰ — 13). Поэтому к ' = 29 и n = 10. Но в этом случае 20 не делит к ⁰ (к ⁰ — 13). Противоречие.

Допустим, что р >  23. Тогда A q = 12, + q =20 и fi — сильно регулярный граф с параметрами (v ' , к ' , 12, 20). Утверждение (3) доказано.

Пусть fi — сильно регулярный граф с параметрами (v ' , к ' , 12, 20 — р). Тогда n ² = (А — +) ² + 4(к ' — +) = 4к ' + р ² — 12р — 16 и 20 — р делит к ' (к ' — 13).

Допустим, что fi — полный многодольный граф К _ахь . Тогда (a — 1)b = 20 — р и (a — 2)b = 12, поэтому b = 8 — р делит 12, откуда р = 2 и fi = К 4_Хб , либо р = 5 и fi = К бхЗ .

В случае р = 19 имеем n = 15, к ' = 27 и fi имеет собственное значение — 2, противоречие.

В случае р =17 имеем n ² = 4к ' + 69 и 14 6 (n ² — 69)/4 6 39, n нечетно. Тогда n Е { 13,15 } . При n = 13 имеем к ' = 25 и fi имеет собственное значение — 2, противоречие. При n = 15 имеем к ' = 39 и fi имеет собственные значения 12, — 3, причем кратность собственного значения 12 равна 2 • 39 • 42/(15 • 3), противоречие.

В случае р =13 имеем n ² = 4к ' — 3 и 14 6 (n ² +3)/4 6 39, n нечетно. Тогда n Е { 9,11 } . При n = 9 имеем к = 21 и fi имеет собственное значение — 2, противоречие. При n = 11 имеем к ' = 31, противоречие с тем, что 7 не делит к ' (к ' — 13).

В случае р =11 имеем n ² = 4к ' — 27. Тогда n Е { 7, 9,11 } . Так как 9 делит к ' (к ' — 13), то n = 9, к ' = 27 и fi имеет собственные значения 6, — 3, причем кратность собственного значения 6 равна 20. Итак, fi имеет параметры (70, 27,12, 9). Противоречие с тем, что р = 11 не делит 40 — 27.

В случае р = 7 имеем n ² = 4к — 51; тогда n Е { 3, 5, 7, 9 } , поэтому к Е { 15, 19, 25, 33 } . Противоречие с тем, что 13 не делит к (к — 13).

В случае р = 5 имеем n2 = 4к — 51; тогда n Е {3, 5, 7, 9}, поэтому к Е {15, 19, 25, 33}. При n = 3, к' = 15 имеем к' = + и fi — полный многодольный граф Кбхз. Но по лемме 1.1, примененной к подграфу fi степени d = 15 на w = 18 вершинах, имеем противоречие с тем, что w(40 — d) — 10 6 d---------- 6 2.

95 — w

При n = 5, к ' = 19 противоречие с тем, что 15 не делит к ' (к ' — 13). В случаях n = 7, к ' = 25 и n = 7, к ' = 25 противоречие с тем, что не выполнены условия целочисленности.

В случае р = 3 имеем n ² = 4к ' — 43. Тогда n Е { 5, 7, 9 } . Так как 17 делит к ' (к ' — 13), то n = 5, к ' = 17 = +, противоречие.

В случае p = 2 имеем n2 = 4k' — 36; тогда n/2 G {3,4, 5}, поэтому k' 6 {18, 25, 34}. Так как 18 делит k1 (k1 — 13), то n = 6, k' = 18, причем k' = ^ и Q — полный многодольный граф K4X6. По лемме 1.1, примененной к подграфу Q степени d = 18 на w = 24 вершинах, имеем

— 10 6 d —

w(40 — d)

95 — w

6 2.

Противоречие с тем, что 24 • 22/71 > 36.

Пусть Q — сильно регулярный граф с параметрами (v ' , k ' , 12 — p, 20). Тогда n ² = (А — ^) ² + 4(k ' — ^) = 4k ' + p ² + 16p — 16 и 20 делит k ' (k ' — 13 + p).

Допустим сначала, что Q — полный многодольный граф K _aXb . Тогда (a — 1)b = 20 и (а — 2)b = 12 — p, поэтому b = p + 8 делит 20, откуда p = 2 и Q = К зхто . По лемме 1.1, примененной к подграфу Q степени d = 20 на w = 30 вершинах, имеем

• w(40 — d) — 10 6 d ---------- 6 2.

95 — w

Противоречие с тем, что 30 • 20/65 > 18.

В случае p =11 имеем n ² = 4k ' + 281 и 21 6 (n ² — 281)/4 6 39, причем n нечетно. Противоречие.

В случае p = 7 имеем n ² = 4k ' + 145, поэтому n = 17, k ' = 36, но нарушается условие целочисленности. В случае p = 5 имеем n ² = 4k ' + 89, поэтому n = 15, k ' = 34 и 20 не делит k ' (k ' — 13 + p). В случае p = 3 имеем n ² = 4k ' + 41, поэтому n = 13, k ' = 32 и 20 не делит k ⁰ (k ⁰ — 13 + p).

В случае p = 2 имеем n ² = 4k ' + 20, 25 < n ² /4 6 44, n/2 = 6, k ' = 31, противоречие с тем, что нарушается условие целочисленности.

Итак, Q не является сильно регулярным графом с параметрами (v ' , k' , 12 — p, 20). B

Пусть u G Г — Q. Отметим следующее свойство:

• ( * )    если и смежна с u g , то | Г — (u ^ U (u g ) ^ | =27 и | Q | не больше 39; если же и несмежна с u ^g , то | Г — (u ^ U (u g ) ^ ) | =33 и | Q | не больше 53.

Аналогично получается свойство:

• ( ** ) если орбита u hgi содержит треугольник (3-коклику), то | Q | 6 11 (соответственно | Q | 6 32).

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

• (1)    p = 19 ;

• (2)    p = 17 и p = 13 .

C Пусть p = 19. Тогда любое ребро графа Q лежит в 12 треугольниках, а для несмежных вершин a,b G Q подграф Q(a) П Q(b) содержит 1 или 20 вершин, причем ввиду леммы 2.5 обе возможности встречаются. Далее, | Г — Q | = 19t, 1 6 t 6 4. Заметим, что вершина из Q смежна с 19 или 38 вершинами из Г — Q. С другой стороны, вершина из Г — Q смежна не более чем с 12 вершинами из Q (если для вершины u из Г — Q ее ( g ) -орбита является кокликой, то каждая вершина из Г — h g i смежна точно с 10 вершинами из h g i и [u] не пересекает Q). Отсюда 19 | Q | 6 12(95 — | Q | ), | Q | 6 36, поэтому | Г — Q | = 76 и | Q | = 19. Таким образом, каждая вершина из Q смежна с 38 вершинами из Г — Q (если вершина а из Q смежна с 19 вершинами из Г — Q, то | Q(a) | = 21). Противоречие с тем, что каждая вершина из Q — а ^ смежна с единственной вершиной из Q(a) и степень вершины из Q(a) в графе Q не меньше 9.

Пусть p = 17. Тогда любое ребро графа Q лежит в 12 треугольниках, а для несмежных вершин a,b G Q подграф Q(a) П Q(b) содержит 3 или 20 вершин. Далее, | Г — Q | = 17t,

1 6 t 6 4. Заметим, что вершина из Q смежна с 17 или 34 вершинами из Г — Q. Если вершина a из Q смежна с 34 вершинами из Г — Q, то | Q(a) | = 6, противоречие. Таким образом, каждая вершина из Q смежна с 17 вершинами из Г — Q. С другой стороны, вершина из Г — Q смежна не более чем с 12 вершинами из Q и t = 4. Тогда | Q | = 27 и | Г — Q | = 68. Противоречие с тем, что для смежных вершин a, c G Q подграф Q содержит a, c, 12 вершин из [a] П [c] и по 10 вершин из [a] — е ^ и из [c] — a ^ .

Пусть p = 13. Если u G Г — Q и | [u] П Q | > 2, то [u] П Q — коклика. Если u hgi — также коклика, то по лемме 2.5 имеем | [u] n Q | 6 7. Если же u h g i содержит ребро, то | [u] П Q | 6 12. Далее, A q = 12 и для несмежных вершин a,b G Q подграф Q(a) П Q(b) содержит 7 или 20 вершин, причем ввиду леммы 2.5 обе возможности встречаются. Далее, | Г — Q | = 13t, 1 6 t 6 6. Заметим, что вершина из Q смежна с 13 или 26 вершинами из Г — Q. Поэтому 13 | Q | 6 12(95 — | Q | ), | Q | 6 45 и 4 6 t 6 6.

В случае t = 4 получим | Q | =43 и по свойству ( * ) имеем a i (g) = 0. Из целочисленности Х 1 (д) следует, что 1Oa o (g) — 50 = 380 делится на 12, противоречие.

В случае t = 6 получим | Q | = 17 и Q — сильно регулярный граф с A q = 12, ^ q = 7, противоречие. В случае t = 5 получим | Q | = 30. Для несмежных вершин a,b G Q подграф Q(a) П Q(b) содержит не более 20 вершин, поэтому | Q | > 2 + 14 + 20, противоречие. B

Лемма 2.7. Верны неравенства p = 11 и p = 7 .

C Пусть p = 11. Тогда любое ребро графа Q лежит в 1 или в 12 треугольниках, а для несмежных вершин a,b G Q подграф Q(a) П Q(b) содержит 9 или 20 вершин. Далее, | Г — Q | = 11t и по свойству ( * ) имеем 4 6 t 6 7. Заметим, что вершина из Q смежна с 11 или 22 вершинами из Г — Q (соответственно с 29 или 18 вершинами из Q). Пусть Q содержит e i вершин, смежных с 11i вершинами из Г — Q.

Пусть t = 6. Тогда | Q | =29 и Q — сильно регулярный граф степени 18 с А ⁰ = 12 и ^ 0 = 9. Противоречие с леммой 2.5.

Пусть t = 5. Тогда | Q | =40 и по свойству ( * ) имеем a i (g) = 0. Из целочисленности Х 1 (g) следует, что 10a o (g) — 50 = 350 делится на 12, противоречие.

Пусть t = 4. Тогда | Q | =51 и по свойству ( * ) имеем a i (g) = 0. Из целочисленности Х 1 (g) следует, что 10a o (g) — 50 = 460 делится на 12, противоречие.

Пусть p = 7. Тогда любая h g i -орбита длины 7 является кликой, кокликой, семиугольником или дополнительным графом к семиугольнику. Далее, любое ребро графа Q лежит в 5 или в 12 треугольниках из Q, а для несмежных вершин a,b G Q подграф Q(a) П Q(b) содержит 6, 13 или 20 вершин. По свойству ( ** ) имеем | Q | 6 32. Вершина из Q смежна с 14, 21 или 28 вершинами из Г — Q (соответственно с 26, 19 или 12 вершинами из Q).

Если | Q | > 11, то по свойству ( ** ) имеем a i (g) = 0. Из целочисленности Х 1 (g) следует, что a o (g) — 5 делится на 6, противоречие. Если же | Q | = 11, то Q — регулярный граф степени 5 на 11 вершинах, противоречие. B

Лемма 2.8. Если p = 5 , то Q является кокликой.

C Пусть p = 5 и Q не является кокликой. Тогда любая h g i -орбита длины 5 является кликой, кокликой или пятиугольником. Далее, любое ребро графа Q лежит в 2, 7 или в 12 треугольниках из Q, а для несмежных вершин a,b G Q подграф Q(a) П Q(b) содержит 0, 5, 10, 15 или 20 вершин.

По свойству ( ** ) имеем | Q | 6 32. Если | Q | > 11, то по свойству ( ** ) имеем a 1 (g) = 0. Из целочисленности X i (g) следует, что a o (g) — 5 делится на 6, противоречие.

Если же | Q | = 10, то Q(a ) — пятиугольник для некоторой вершины a из Q, и связная компонента графа Q, содержащая a, является графом икосаэдра, противоречие. B

Лемма 2.9. Если p = 3 , то либо Q является кликой, либо a i (g) = 0 , и | Q | £ { 11,17, 23, 29 } .

C Пусть p = 3 и Q не является кликой. Тогда любая h g i -орбита длины 3 является кликой или кокликой. Далее, | Q | сравнимо с 2 по модулю 3 и любое ребро графа Q лежит в 3i треугольниках из Q, i £ { 0,1,..., 4 } . Для двух несмежных вершин a, b £ Q подграф Q(a) П Q(b) содержит 2 + 3j вершин, j £ { 0,1,..., 6 } . Ввиду свойства ( ** ) имеем | Q | 6 32.

Пусть | Q | =5. Так как Q не является кликой, то Q содержит несмежные вершины a, b, 2 вершины из Q(a) П [b] и по 2 вершины из [a] — [b] и [b] — [a], противоречие.

Пусть | Q | =8. Тогда степень любой вершины из Q равна 1, 4 или 7. Если вершины a, b из Q несмежны, то Q содержит 2 вершины из [a] П [b] и степени a, b не меньше 4. Отсюда Q не содержит вершин степени 1. Если степени всех вершин в Q равны 7, то граф Q является кликой, противоречие. Если степени всех вершин в Q равны 4, то Q — сильно регулярный граф с параметрами (8, 4, 3, 2), противоречие. Пусть степень вершины a £ Q равна 4, степень вершины b £ Q равна 7. Тогда вершины a и b смежны и Q(a) П [b] является 3-кликой. Таким образом, Q содержит точно 2 вершины b, b ⁰ степени 7 и Q — { b, b ⁰ } является объединением двух изолированных треугольников. По лемме 1.5 получим x o + P 8=₃ ( i^—1 )x i = 87 — (320 — 38) + (12 • 19 + 20 • 9 — 42 — 36) = 135. С другой стороны, каждая вершина вне 5-клики L из Г смежна точно с двумя вершинами из L. Поэтому х ₂ = 6, х з = 54, х ₄ = 27.

Пусть | Q | = 11. Тогда степень любой вершины в Q равна 1, 4, 7 или 10. Если вершины a, b из Q несмежны, то Q содержит 2 вершины из [a] П [b] и степени a, b не меньше 4. Отсюда Q не содержит вершин степени 1. Пусть Q содержит 5 вершин a i ,..., a s степени 10, Q o = Q — { a i ,..., a s } . Если 5 = 3, то Q o — регулярный граф степени 4 с ^ = 2 на 8 вершинах и A(Q o ) £ { 0, 3 } . Если для b £ Q o подграф Q o (b) содержит вершину степени 3, то b ^ П Q o является 5-кликой, противоречие. Значит, Q o — сильно регулярный граф с параметрами (8, 4, 0, 2), противоречие.

Если 5 = 2, то Q o — граф со степенями вершин 2 и 5. Поэтому A(Q o ) £ { 1,4 } , +(Q o ) £ { 0,3 } . Если степень b в Q o равна 5, то подграф Q o (b) содержит вершину с степени 4 и либо Q o (b) П Q o (с) является 4-кокликой, либо b ^ П Q o является 6-кликой. В первом случае имеем противоречие с тем, что любая вершина из Q o (b) П Q o (c) смежна с 3 вершинами из Q o — a ^ . Во втором случае Q o — объединение изолированной 6-клики и треугольника, противоречие. Если же Q o не содержит вершин степени 5, то Q o — объединение трех изолированных треугольников.

Если 5 = 1, то Q o — граф со степенями вершин 3 и 6 на 10 вершинах, A(Q o ) £ { 2, 5 } , +(Q o ) £ { 1, 4 } . Если для b £ Q o подграф Q o (b) содержит вершину степени 5, то либо Q o (b) П Q o (c) является 4-лапой, либо b ^ П Q o является 7-кликой, противоречие. Таким образом, Q o содержит такую 4-коклику C, что окрестность в Q o любой вершины из C — объединение двух изолированных треугольников, противоречие. Значит, A(Q o ) = 2 и Q o (b) — шестиугольник или объединение двух изолированных треугольников для некоторой вершины b £ Q o . Поэтому Q o — b^ — треугольник, и каждая его вершина смежна с 1 или 4 вершинами из Q o (b). Противоречие с тем, что любая вершина из Q o (b), смежная с вершиной из Q o — b ^ , смежна с 3 вершинами из Q o — b ^ .

Пусть 5 = 0. Если степень вершины b в Q равна 4, то подграф Q(b) является 4-кликой или 4-кокликой. В любом случае число ребер между Q(b) и Q — b ^ равно 12. Если Q(b) — клика, то Q(b) содержит две пары вершин c, с ⁰ и d, d ⁰ , смежные с общими тройками вершин из Q — b ^± . Противоречие с тем, что Q(c) — b ^± — регулярный граф степени 1 на 3 вершинах.

Значит, Q(b) — коклика и каждая вершина из Q(b) смежна с 3 вершинами из Q — b ^± .

Если Q o — b ^ содержит две вершины d, e такие, что Q(b) П d ^ = Q(b) П e ^ , то для c,c Е Q(b) П [d] получим Q П c ^ = Q П (c ⁰ ) ^ . Противоречие с тем, что Q(c) — коклика. Итак, Q — b ^ можно отождествить с множеством пар вершин из Q(b) = { c i ,..., С 4 } и Q — регулярный граф степени 4. Противоречие с тем, что Q — сильно регулярный граф с параметрами (11, 4, 0, 2).

Таким образом, если | Q | = 11, то Q содержит точно 2 вершины b, b ⁰ степени 10 и Q — { b, b ⁰ } является объединением трех изолированных треугольников. Поэтому Х 2 = 3, х ₄ = 54, Х б = 27.

Пусть u Е Г — Q, | [u] П Q | = y, Y — множество вершин из Г — u hgi , смежных точно с i вершинами из u hgi , yi = | Y i | .

Если u h g i является кликой, то у з = 3x + y, у 2 = 33 — 9x — 3y , y i = 48 + 9x + 3y. Поэтому [u] U [u g ] U [u g ] содержит 84 + 3x вершин из Г — Q и | Q | 6 11. Допустим, что [u] П Q содержит ребро { a, b } . Тогда L = u hgi U { a, b } является 5-кликой и любая вершина из Г — L смежна точно с 2 вершинами из L. Противоречие с тем, что | Q | равно сумме 2 и степеней в Q вершин a, b.

Пусть | Q | = 11. Тогда y 6 3 и множество вершин, смежных с их образами под действием g, содержится в X 2 . Противоречие с тем, что a i (g) делится на 12.

Пусть | Q | = 8. Как показано выше, Q содержит точно 2 вершины b, b ⁰ степени 7 и Q — { b, b ⁰ } является объединением двух изолированных треугольников. Поэтому множество вершин, смежных с их образами под действием g, совпадает с X 2 и y = 2. Пусть c Е Y o П Q, | [c] П Y — Q | = z i (c) = z i . Если c / { b,b ⁰ } , то ^zi = 36, ^izi = 57. В случае Z 3 = 0 получим Z 2 = 21 + z o , а в случае Z 3 = 3 получим Z 2 = 15. Если c, c — смежные вершины из Q П Y o — { b, b ⁰ } , то [c] П [c ⁰ ] содержит 3 вершины из Q и не менее 12 вершин из Y 2 , противоречие. Итак, a i (g) = 0, t четно и | Q | нечетно. Отсюда | Q | Е { 11,17, 23, 29 } . B

Лемма 2.10. Если p = 2 и Q не является кокликой, то выполняются следующие утверждения:

• (1)    | Г — Q | = 2t и t 6 43 ;

• (2)    каждая вершина из Q смежна с вершиной из Г — Q;

• (3)    t = 24 или t > 27 .

C Пусть p = 2 и Q не является кокликой. Тогда любое ребро графа Q лежит в 2i треугольниках из Q, i Е { 0,1,..., 6 } , а для несмежных вершин a,b Е Q подграф Q(a) П Q(b) содержит 2j вершин, j Е { 0,1,..., 10 } .

Положим А = Г — Q. Тогда | А | = 2t и ввиду свойства ( * ) имеем 21 6 t 6 46. Заметим, что любая вершина из А смежна с четным числом вершин из Q. Пусть X i — число вершин из А, смежных точно с i вершинами из Q, x i = | X i | .

Заметим, что вершина из Q смежна с 2i вершинами из Г — Q (соответственно с 40 — 2i вершинами из Q). Если t сравнимо с i по модулю 3, то a i (g) сравнимо с — 4i по модулю 12.

Пусть t = 46. Тогда | Q | = 3, | А | = 92 и a i (g) = 8 + 12r. Так как Q не является кокликой, то Q содержит смежные вершины a, b, причем степени этих вершин равны 2. Противоречие с тем, что любое ребро графа Q лежит в 2i треугольниках из Q.

Пусть t = 45. Тогда |Q| = 5, |А| =90 и ai(g) = 12r. Степень любой вершины в Q равна 0, 2 или 4. Допустим, что Q содержит 2 вершины a, b степени 4. Тогда подграф Q(a) П Q(b) содержит 3 вершины, противоречие. Пусть степень вершины a в Q равна 4 и b — вершина степени 2. Тогда Q содержит вершины a, b, 3 вершины из [a] — b^ и 1 вершину из [b] — a^ противоречие. Значит, Q не содержит вершин степени 4. Так как любое ребро графа Q лежит в 2i треугольниках из Q, а для несмежных вершин a,b Е Q подграф Q(a)ПQ(b) содержит 2j вершин, то Q не является пятиугольником и не содержит треугольников. Значит, Q является объединением 4-цикла bcde и изолированной вершины а. Пусть Xi = Xi П [a], xi = |X0|. Тогда x2 + x4 = 40 и x2 + xy'4 = 80, поэтому x'2 = x4 = 20. С другой стороны, xo + x2 + x4 = 90, x2 + 2x4 = 96 и x2 + 6x4 = 48 + 120 — 4 = 164. Поэтому x4 = 17, противоречие.

Пусть t = 44. Тогда | Q | = 7, | A | =88 и a i (g) = 4 + 12r. Степень любой вершины в Q равна 0, 2, 4 или 6. Пусть Q содержит вершину а степени 6, b Е Q(a). Тогда Q содержит 2 вершины a, b, 2i вершин из [а] П [b] и 5 — 2i вершин из [а] — b ^ , противоречие с тем, что степень b в графе Q нечетна.

Если степени всех вершин в графе Q равны 4, то д о = 4 (иначе Q содержит не менее 8 вершин). В этом случае Q является полным многодольным графом, противоречие. Допустим, что Q содержит смежные вершины a, b степени 4. Тогда | Q(a) П Q(b) | = 2, | Q(a) — b ^ | = | Q(b) — a ^ | = 1 и Q — (a ^ U b ^ ) = c, причем вершина с либо изолирована в Q, либо Q(c) = Q(a) П [b]. Выберем вершину e Е Q(a) — b ^ . Тогда e смежна либо с вершиной из Q(a) П [b], либо с вершиной из Q(b) — a ^ . В последнем случае для d Е Q(a) П [b] получим | Q(e) П [d] | = 1, противоречие. Значит, Q(c) = Q(a) П [b] и | Q(c) П [e] | = 1, снова противоречие.

Допустим, что Q содержит 2 несмежные вершины a, b степени 4. Тогда Q(a) = Q(b) состоит из вершин d i степени 2 в Q и Q содержит единственную изолированную вершину с. В этом случае x o +x ₂ +x ₄ +x 6 = 88, 2x 2 +4x 4 +6x 6 = 264 и x ₂ +6x 4 +15x 6 = 96+260 — 16 = 340. Поэтому x 4 = 52 — 3x 6 , x 2 = 28 — 9x 6 и x o = 8 + 11x 6 . В случае x 6 = 2 получим x 4 = 46, x 2 = 10 и x o = 30. Если [с] не пересекает X 6 , то X 4 содержит 40 вершин из [с] и 6 вне [с]. Тогда некоторая вершина u из X o смежна не более чем с 1 вершиной из X 6 и число 2-путей с началом в u и концом в Q не больше 26 • 4 + 6 + 10 • 2, противоречие. Положим X 6 = { p,p g } и | [p] П X i | = y i . Тогда ^2yi =34 и ^iy i равно 80, если [p] не содержит a, равно 78, если [p] не содержит d i . Далее, [с] содержит по 2 вершины из X 2 , X 6 и 36 вершин из X 4 . Если u Е X o — ([p] U [p g ]), то [u] содержит не более 20 вершин из X 4 П [с], не более 10 вершин из X 4 — [с] и не более 10 вершин из X 2 . Отсюда [u] П [u g ] содержит по 10 вершин из X 2 , X 4 — [с] и 4 вершины из X 4 П [с], противоречие. Пусть u Е X o П [p] — [p g ]. Если [u] содержит 19 вершин из X 4 П [с], то число 2-путей с началом в u и концом в Q не больше 6 + 29 • 4 + 8 • 2 = 138, противоречие. Если [u] содержит не более 18 вершин, то число указанных 2-путей будет еще меньше. Значит, x 6 = 0.

В случае x 6 = 0 получим x 4 = 52, x 2 = 28 и x o = 8. Далее, число 2-путей с началом в a, концом в Q и средней вершиной в Г — Q равно 16 + 20 + 48 = 84. С другой стороны, [a] содержит не более 28 вершин из X 2 и не менее 8 вершин из X 4 , поэтому число указанных путей не меньше 8 • 4 + 28 • 2, противоречие.

Допустим, что Q содержит единственную вершину a степени 4. Тогда | Q(b i ) П [b j ] | = 1 для подходящих вершин b i , b j Е Q(a), противоречие.

Значит, Q не содержит вершин степени 4, Q — объединение изолированных вершин и многоугольников. Так как д о Е { 0, 2 } , то Q — объединение трех изолированных вершин и четырехугольника. В этом случае x o + x 2 + x 4 + x 6 = 88, 2x 2 + 4x 4 + 6x 6 = 272 и x ₂ + 6x 4 + 15x 6 = 48 + 340 — 4 = 384. Поэтому x ₄ = 62 — 3x 6 , x ₂ = 12 + 3x 6 и x o = 14 — x 6 . Пусть a — вершина степени 2 из Q и | [a] П X i | = y i . Тогда ^2yi = 38 и ^iyi = 102, поэтому y 2 + 2y 4 + 3y 6 = 51, противоречие с тем, что числа y i четны. Утверждение (1) доказано.

Если |Q| > 40, то по свойству (*) получим ai(g) = 0, следовательно, t делится на 3 и t Е {21, 24, 27}. Допустим, что Q содержит a±. Тогда для любой вершины u из A подграф [u] содержит 20 вершин из Q(a) и u несмежна с вершинами из Q — a^. Если Q — a^ содержит вершину с, то [с] С Q и [u] П Q содержится в [a] П [с]. Противоречие с тем, что любая вершина из Г — а^ смежна с 20 вершинами из [а] П [c].

Значит, fi = а ^ и t = 27. Противоречие с тем, что вершина из [а] смежна с 27 вершинами из А (число | [b] П А | четно для b Е fi). Итак, для любой вершины а Е fi подграф [а] не содержится в fi. Утверждение (2) доказано.

Пусть t = 21. Тогда | fi | =53 и для вершины u из А подграф fi содержит 20 вершин из [u] П [u g ] и 33 вершины вне u ^ U (u g ) ^ . Пусть w Е [u g ] — [u] и [w] содержит в вершин из [u] П [u g ]. Тогда [w] содержит 20 — в вершин из [u] — [u g ], 12 — в вершин из [u g ] — [u] и 7 + в вершин вне u ^ U (u g ) ^ . Противоречие с тем, что 7 + 2в = 20.

Итак, t = 24 или t >  27. B

• § 3.    Автоморфизмы точечного графа частичной геометрии pG2(4, 9)

В этом параграфе Г — точечный граф частичной геометрии pG 2 (4, 9), G — группа автоморфизмов графа Г, g — элемент простого порядка p из G и fi = Fix (g).

Лемма 3.1. Если fi содержит 2-лапу, то p = 2 , a i (g) > 0 и выполняется одно из утверждений:

• (1)    fi — точечный граф частичной геометрии pG 2 (4, 1) и каждая вершина из Г — fi смежна точно с 6 вершинами из fi ;

• (2)    fi — объединение изолированного октаэдра X и коклики C , | С | Е { 1, 3, 5 } .

C По условию окрестность любой вершины является объединением 10 максимальных 4-клик.

Если а Е fi, то g действует на множестве из 10 прямых в а ^ . Далее, для b Е fi(a) ребро { a, b } лежит на единственной прямой.

Пусть fi содержит 2-лапу. Если p = 3, то a i (g) = 0, и | fi | Е { 11,17, 23, 29 } . Если g фиксирует прямую из а ^ , то g фиксирует эту прямую поточечно, поэтому fi(a) состоит из 10 — 3t прямых. В случае t = 1 получим fi С а ^ , противоречие с тем, что fi(b) содержит вершину вне а ^ . Так как любой ^-подграф вершин из fi пересекает fi, то окрестность каждой вершины в fi является регулярным графом степени 6 на 16 вершинах. Поэтому для c Е fi(a) подграф fi содержит 6 вершин из [а] П [c], по 9 вершин из [а] — c ^ , [c] — а ^ и еще 3 вершины e 1 , e ₂ , 6 3 . Если b Е fi(a) П [c], то fi(b) содержит а, c, 7 вершин из [а] П [c], по 5 — y вершин из [а] — c ^ , [c] — а ^ и 4 + 7 вершин из { e i , 6 2 , 6 3 } , противоречие.

Если p = 2, то | Г — fi | = 2t, 27 6 t 6 43 или t = 24, и каждая вершина из fi смежна с вершиной из Г — fi. Если a i (g) = 0, то число g-допустимых прямых в b ^ равно числу g-допустимых прямых в c ^ для любых двух несмежных вершин b, c Е fi. Далее, любая g-допустимая прямая лежит в fi, поэтому fi — точечный граф частичной геометрии pG 2 (4,t ⁰ ) для некоторого t ⁰ < 9. Противоречие с тем, что | fi | Е { 41,47 } .

Значит, a i (g) > 0 и любая g-допустимая прямая содержит 1, 3 или 5 точек из fi. Легко понять, что если а ^ содержит прямую с i > 1 точками из fi, то любая g-допустимая прямая из а ^ содержит 1 или i точек из fi. Если i = 5, то fi — точечный граф частичной геометрии pG 2 (4, t ⁰ ) для t ⁰ = 1 (напомним, что pG 2 (4, 3) не существует). В этом случае выполняется утверждение (1).

Если i = 3, то содержащая а связная компонента X графа fi — точечный граф частичного пространства прямых порядка (2, t ⁰ ) для некоторого нечетного t ⁰ 6 9. Так как число прямых этого пространства равно | X | (t ⁰ + 1)/3, то либо t ⁰ = 5, либо | X | делится на 3.

В случае t ⁰ = 1 окрестности вершин в X являются четырехугольниками, поэтому X — октаэдр. Пусть L — прямая, пересекающая X по треугольнику, L — X = { u, u g } . Тогда

Q — X содержится в [u] П [u ^g ]. Если | Q n [u] n [u g ] | = 12, то для e G X — L подграф [e] содержит 2 вершины из [u] П [u g ], по 18 вершин из [u] — (u g ) \ [u g ] — u ^ и 2 вершины из Q — ([u] U [u g ]). Противоречие с тем, что для различных e, e ⁰ G X — L подграф [e] П [e ⁰ ] содержит не менее 18 вершин из ([u] — (u g ) ^± ) U ([u g ] — u ^± ). Если [u] П [u g ] — Q = { w, w g } , то для e G X — L подграф [e] содержит w, w g и 2 вершины из [u] П X. Противоречие с тем, что [e] П [e ⁰ ] содержит w, w g , 2 вершины из X и не менее 10 вершин из ([u] — (u g ) ^ ) U ([u g ] — u ^ ). Отсюда | Q — X | 6 5 и Q — X является кокликой. В этом случае выполняется утверждение (2).

Пусть t ⁰ >  3. Тогда X является реберно регулярным графом с k ^ = 2(t ⁰ + 1) и A v = t ⁰ + 1. Поэтому | X | > 3(t ⁰ +1) | и в случае равенства X = K ax(_t 0 +1) . Отсюда Q — X является кокликой. Если Q — X содержит 2 вершины a, b, то для прямой L, содержащей 3 точки e, e ⁰ , e ⁰⁰ из X подграф [a] П [b] содержит 2(t ⁰ + 1) точек из [e] — Q, лежащих на g-допустимых прямых, пересекающих X по 3 точкам. Противоречие с тем, что 6(t ⁰ + 1) > 20.

Пусть Q — X = { a } и прямая L содержит 3 точки e, e ⁰ , e" из X и ребро { u, u g } . Если [u] П [u g ] содержит y вершин из [a], то | Г — ([a] U [u] U [u g ]) | = 11 — 7. Далее, X содержит 3t ⁰ точек, смежных с парами вершин из { e, e ⁰ , e ⁰⁰ } , поэтому t ⁰ = 3, y G { 0, 2 } и | X | G { 12,18 } . В случае | X | = 12 число прямых, пересекающих X по 3 точкам, равно 16, и [a] содержит 32 точки, лежащие на этих прямых. Противоречие с тем, что [a] П [e] содержит только 8 из этих точек и | [a] — [e] | > 20. Значит, | X | = 18 и число прямых, пересекающих X по 3 точкам, равно 24. Противоречие с тем, что | [a] | > 48.

Итак, в случае t ⁰ > 3 имеем Q = X. Если t ⁰ = 9, то Q — точечный граф частичной геометрии pG 2 (2,9). Противоречие с тем, что | Q| — нечетное число. Если t ⁰ = 7, то | Q | G { 27, 33 } . Число прямых, пересекающих Q по 3 точкам, равно 8 | Q | /3, и объединение этих прямых содержит не менее 144 точек из Г — Q, противоречие. Если t ⁰ = 5, то | Q | > 19. Число прямых, пересекающих Q по 3 точкам, равно 2 | Q | , и объединение этих прямых содержит не менее 76 точек из Г — Q. Поэтому | Г — Q | = 76 и | Q | = 19. Отсюда Q П [u] П [u g ] содержит вершину a, 7 вершин из [a] и | Г — ([a] U [u] U [u g ]) | = 11 — 7• Противоречие с тем, что Q содержит 3t ⁰ = 15 точек, смежных с парами вершин из { e, e ⁰ , e ⁰⁰ } .

Таким образом, t ⁰ = 3. Теперь Q содержит e, e ⁰ , e ⁰⁰ , 9 точек, смежных с парами вершин из { e, e ⁰ , e ⁰⁰ } и еще не более 9 точек из [u] П [u g ]. Отсюда | Q | = 21, противоречие с тем, что Q — сильно регулярный граф с параметрами (21, 8,4, 2) и (4 — 2) ² + 4(8 — 2) не является квадратом. B

До конца работы будем предполагать, что G действует транзитивно на множестве вершин графа Г. Через G a обозначим стабилизатор в G вершины a. Ввиду теоремы n(G a ) С { 2, 3, 5 } и | G : G _a | =95.

Лемма 3.2. Если f — элемент порядка 19 из G , то выполняются следующие утверждения:

• (1)    C G (f) = h f i ;

• (2)    если g G N g ( ( / i ) , то либо p = 3 и Q является 5-кликой, либо p = 2 и Q является m-кокликой, m G { 3, 5 } ;

• (3)    число | N _G ( ( / i ) | равно 57 или 38 .

• <1 Допустим, что g G C _G (/). Тогда f действует без неподвижных точек на Q. Из теоремы следует, что Q — пустой граф, и p = 5. Противоречие с тем, что g действует на множестве из 38 вершин, смежных с их образами под действием f. Утверждение (1) доказано.

Пусть g G N g ( ( / i ). Тогда p делит 18 и g действует на множестве U из 38 вершин, смежных с их образами под действием f и на множестве W из 57 вершин, несмежных с их образами под действием f . Отсюда подграф Q не пуст.

Если Q является n-кликой, то ввиду теоремы p = 3 и g фиксирует каждую h f i -орбиту на U . Далее, либо n = 2 и h g i действует транзитивно на множестве h f i -орбит на W , либо n = 5 и g фиксирует каждую h f i -орбиту на W . В первом случае U совпадает с множеством вершин, смежных с их образами под действием f ⁱ для всех i , и каждая h f i -орбита на U является 19-кликой, противоречие.

Пусть Q является m-кокликой. Если p = 5, то g фиксирует каждую h f i -орбиту и m >  20, противоречие. Значит, p = 2. Если m > 5, то Q пересекает Q g i для подходящего i, противоречие с тем, что Q П Q g i попадает в Fix (f). Значит, m = 3 или m = 5.

Если Q содержит 2-лапу, то p = 2 и по лемме 3.1 либо Q — точечный граф частичной геометрии pG 2 (4,1), либо Q — объединение изолированного октаэдра X и коклики C , | C | Е { 1, 3, 5 } . В любом случае Q пересекает Q g i для подходящего i, противоречие. Утверждение (2) доказано.

Допустим, что Nq^J i ) содержит элемент g порядка 3 и инволюцию t, централизующую g. Так как Q является 5-кликой, то t фиксирует точно одну вершину из Q. Противоречие с тем, что g фиксирует 2-коклику из Fix (t).

Если Nq^J i ) содержит элемент h порядка 9, то h действует на некоторой h f i -орбите Y на U и фиксирует вершину w из Y . Тогда вершина w смежна с w ^f , с w ^{f -1} и смежна с w ^{f h} , поэтому Y является 19-кликой, противоречие.

Допустим, что Nq^J i ) = h f i . Тогда G = R h f i , где R — нормальная 19 0 -подгруппа. В этом случае h f i действует на элементарной абелевой 5-подгруппе Z . Для неединичного элемента g Е Z подграф Q является 10-кокликой или 15-кокликой, поэтому Fix (Z) — пустой граф. Отсюда каждая Z -орбита имеет длину 5. Для двух Z -орбит X 1 и X 2 найдутся подгруппы Z 1 , Z 2 индекса 5 из Z , поточечно фиксирующие X 1 , X 2 соответственно. Так как Z 1 П Z 2 поточечно фиксирует X i U X 2 , то Z i П Z 2 = 1 и | Z | делит 25, противоречие с действием f на Z . B

Лемма 3.3. G — простая неабелева группа.

C Пусть L — минимальная нормальная подгруппа из G . Если группа L абелева, то L является p-группой. Из доказательства утверждения (3) леммы 3.2 следует, что p = 5.

Пусть p = 3. Тогда каждая L-орбита имеет длину 1 или 3. Так как 95 = 19 • 5, то имеется 19 L -орбит длины 3 и 38 L -орбит длины 1. Противоречие с тем, что элемент порядка 3 фиксирует 2 или 5 точек.

Пусть p = 2. Тогда каждая L-орбита имеет длину 1, 2 или 4. Если имеется орбита длины 4, то 95 = 19 • 4 + 19 • 1, поэтому имеется 19 L-орбит длины 1. Противоречие с тем, что элемент порядка 2 фиксирует не более 17 точек.

Итак, L — неабелева группа. Из действия f на L следует, что 19 делит | L | , поэтому L — простая группа. По рассуждению Фраттини G = LN G ( h f i ), причем N l ( h f i ) = h f i . Из утверждения (3) леммы 3.2 следует, что G = L. B

Завершим доказательство теоремы. По лемме 2.3 из [7] простая группа L с | n(L) | = 4 изоморфна:

• (1)    A 7 , A 8 , A 9 , A 10 , M 11 , M 12 , J 2 ;

• (2)    L 2 (p) для некоторого простого числа p, L 2 (2 ^m ) или L 2 (3 ^m ) для подходящего m;

• (3)    L 2 (25),L 2 (49),L 2 (81), L 3 (4),L 3 (5),L 3 (7),L 3 (17), L ₄ (3), PSp 4 (q) (q Е { 4, 5, 7, 9 } ), PSp 6 (2), P Q + (2), G 2 (3), U 3 (q) (q Е { 4, 5, 7, 8, 9 } ), U ₄ (3), U 5 <2), Sz(8), Sz(32), ³ D 4 (2), ² F 4 (2) 0 .

Отсюда группа G изоморфна L 2 (19), противоречие с тем, что G не содержит подгрупп индекса 95. Теорема доказана.