Об автоморфизмах сильно регулярного графа с параметрами (95, 40, 12, 20)
Автор: Махнев Александр Алексеевич, Чуксина Наталья Владимировна
Журнал: Владикавказский математический журнал @vmj-ru
Статья в выпуске: 4 т.11, 2009 года.
Бесплатный доступ
Выяснено строение подграфов неподвижных точек автоморфизмов простых порядков сильно регулярного графа с параметрами (95,40,12,20). Как следствие доказано, что точечный граф частичной геометрии pG_2(4,9) не является вершинно симметричным.
Сильно регулярный граф, автоморфизм графа, частичная геометрия.
Короткий адрес: https://sciup.org/14318592
IDR: 14318592
Текст научной статьи Об автоморфизмах сильно регулярного графа с параметрами (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 1 ,...,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, то геометрия называется обобщенным четырехугольником
-
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 2 ) = 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 2 матрицы смежности графа Г. Пусть 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 2 ). Пусть 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, 2 i X i = 20 (mm) и верно одно из утверждений:
-
(1) p = 5 и либо m = 15 и a i (g) = a i (g 2 ) = 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 2 ) > 100 и Г имеет 5-кликовую h g i -орбиту U . Противоречие с тем, что а смежна с 0 или 5 вершинами из U . Значит, a i (g) = a i (g 2 ) = 20.
Если m = 10, то a i (g) Е { 10, 70 } .
Если m = 5, то a i (g) = 60. Отсюда a i (g) + a i (g 2 ) = 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. Тогда х о + х 2 + х 4 = 90, 2x 2 + 4x 4 = 200, х 2 + 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 0 , k 0 , 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 2 = (А — +) 2 + 4(к ' — +) = 4к ' — 16 и 20 делит к ' (к 0 — 13). Поэтому к ' = 29 и n = 10. Но в этом случае 20 не делит к 0 (к 0 — 13). Противоречие.
Допустим, что р > 23. Тогда A q = 12, + q =20 и fi — сильно регулярный граф с параметрами (v ' , к ' , 12, 20). Утверждение (3) доказано.
Пусть fi — сильно регулярный граф с параметрами (v ' , к ' , 12, 20 — р). Тогда n 2 = (А — +) 2 + 4(к ' — +) = 4к ' + р 2 — 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 2 = 4к ' + 69 и 14 6 (n 2 — 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 2 = 4к ' — 3 и 14 6 (n 2 +3)/4 6 39, n нечетно. Тогда n Е { 9,11 } . При n = 9 имеем к = 21 и fi имеет собственное значение — 2, противоречие. При n = 11 имеем к ' = 31, противоречие с тем, что 7 не делит к ' (к ' — 13).
В случае р =11 имеем n 2 = 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 2 = 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 2 = 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 2 = (А — ^) 2 + 4(k ' — ^) = 4k ' + p 2 + 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 2 = 4k ' + 281 и 21 6 (n 2 — 281)/4 6 39, причем n нечетно. Противоречие.
В случае p = 7 имеем n 2 = 4k ' + 145, поэтому n = 17, k ' = 36, но нарушается условие целочисленности. В случае p = 5 имеем n 2 = 4k ' + 89, поэтому n = 15, k ' = 34 и 20 не делит k ' (k ' — 13 + p). В случае p = 3 имеем n 2 = 4k ' + 41, поэтому n = 13, k ' = 32 и 20 не делит k 0 (k 0 — 13 + p).
В случае p = 2 имеем n 2 = 4k ' + 20, 25 < n 2 /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 с А 0 = 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 0 степени 7 и Q — { b, b 0 } является объединением двух изолированных треугольников. По лемме 1.5 получим x o + P 8=3 ( i—1 )x i = 87 — (320 — 38) + (12 • 19 + 20 • 9 — 42 — 36) = 135. С другой стороны, каждая вершина вне 5-клики L из Г смежна точно с двумя вершинами из L. Поэтому х 2 = 6, х з = 54, х 4 = 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, с 0 и d, d 0 , смежные с общими тройками вершин из 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 0 ) ^ . Противоречие с тем, что Q(c) — коклика. Итак, Q — b ^ можно отождествить с множеством пар вершин из Q(b) = { c i ,..., С 4 } и Q — регулярный граф степени 4. Противоречие с тем, что Q — сильно регулярный граф с параметрами (11, 4, 0, 2).
Таким образом, если | Q | = 11, то Q содержит точно 2 вершины b, b 0 степени 10 и Q — { b, b 0 } является объединением трех изолированных треугольников. Поэтому Х 2 = 3, х 4 = 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 0 степени 7 и Q — { b, b 0 } является объединением двух изолированных треугольников. Поэтому множество вершин, смежных с их образами под действием g, совпадает с X 2 и y = 2. Пусть c Е Y o П Q, | [c] П Y — Q | = z i (c) = z i . Если c / { b,b 0 } , то ^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 0 } , то [c] П [c 0 ] содержит 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 2 +x 4 +x 6 = 88, 2x 2 +4x 4 +6x 6 = 264 и x 2 +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 2 + 6x 4 + 15x 6 = 48 + 340 — 4 = 384. Поэтому x 4 = 62 — 3x 6 , x 2 = 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 2 , 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 0 ) для некоторого t 0 < 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 0 ) для t 0 = 1 (напомним, что pG 2 (4, 3) не существует). В этом случае выполняется утверждение (1).
Если i = 3, то содержащая а связная компонента X графа fi — точечный граф частичного пространства прямых порядка (2, t 0 ) для некоторого нечетного t 0 6 9. Так как число прямых этого пространства равно | X | (t 0 + 1)/3, то либо t 0 = 5, либо | X | делится на 3.
В случае t 0 = 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 0 G X — L подграф [e] П [e 0 ] содержит не менее 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 0 ] содержит w, w g , 2 вершины из X и не менее 10 вершин из ([u] — (u g ) ^ ) U ([u g ] — u ^ ). Отсюда | Q — X | 6 5 и Q — X является кокликой. В этом случае выполняется утверждение (2).
Пусть t 0 > 3. Тогда X является реберно регулярным графом с k ^ = 2(t 0 + 1) и A v = t 0 + 1. Поэтому | X | > 3(t 0 +1) | и в случае равенства X = K ax(t 0 +1) . Отсюда Q — X является кокликой. Если Q — X содержит 2 вершины a, b, то для прямой L, содержащей 3 точки e, e 0 , e 00 из X подграф [a] П [b] содержит 2(t 0 + 1) точек из [e] — Q, лежащих на g-допустимых прямых, пересекающих X по 3 точкам. Противоречие с тем, что 6(t 0 + 1) > 20.
Пусть Q — X = { a } и прямая L содержит 3 точки e, e 0 , e" из X и ребро { u, u g } . Если [u] П [u g ] содержит y вершин из [a], то | Г — ([a] U [u] U [u g ]) | = 11 — 7. Далее, X содержит 3t 0 точек, смежных с парами вершин из { e, e 0 , e 00 } , поэтому t 0 = 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 0 > 3 имеем Q = X. Если t 0 = 9, то Q — точечный граф частичной геометрии pG 2 (2,9). Противоречие с тем, что | Q| — нечетное число. Если t 0 = 7, то | Q | G { 27, 33 } . Число прямых, пересекающих Q по 3 точкам, равно 8 | Q | /3, и объединение этих прямых содержит не менее 144 точек из Г — Q, противоречие. Если t 0 = 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 0 = 15 точек, смежных с парами вершин из { e, e 0 , e 00 } .
Таким образом, t 0 = 3. Теперь Q содержит e, e 0 , e 00 , 9 точек, смежных с парами вершин из { e, e 0 , e 00 } и еще не более 9 точек из [u] П [u g ]. Отсюда | Q | = 21, противоречие с тем, что Q — сильно регулярный граф с параметрами (21, 8,4, 2) и (4 — 2) 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 для всех 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 4 (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 4 (3), U 5 <2), Sz(8), Sz(32), 3 D 4 (2), 2 F 4 (2) 0 .
Отсюда группа G изоморфна L 2 (19), противоречие с тем, что G не содержит подгрупп индекса 95. Теорема доказана.
Список литературы Об автоморфизмах сильно регулярного графа с параметрами (95, 40, 12, 20)
- Махнев А. А. О графах, окрестности вершин которых сильно регулярны с k=2\mu//Мат. сб.-2000.-Т. 191, № 7.-C. 89-104.
- Brouwer A. E., Haemers W. H. The Gewirtz graph: an exercize in the theory of graph spectra//Europ. J. Comb.-1993.-Vol. 14.-P. 397-407.
- Махнев А. А. О расширениях частичных геометрий, содержащих малые μ-подграфы//Дискретн. анализ и исслед. опер.-1996.-Т. 3, № 3.-C. 71-83.
- Cameron P. Permutation Groups.-Cambridge: Cambridge Univ. Press, 1999.-220 p.-(London Math. Soc. Student Texts; 45).
- Brouwer A. E., Cohen A. M., Neumaier A. Distance-regular graphs.-Berlin etc: Springer-Verlag.-1989.-485 p.
- Махнев А. А., Чуксина Н. В. Об автоморфизмах сильно регулярного графа с параметрами (210,95,40,45)//Тезисы сообщений VII Международной школы-конференции по теории групп.-Челябинск: ЮУрГУ, 2008.-C. 78-80.
- Shao C., Shi W., Jiang Q. Characterization of simple K_4-groups//Front. Math. China.-2008.-Vol. 3.-P. 355-370.