Содержание к диссертации
Введение
Глава 1. Предварительные сведения
Глава 2. Расширения обобщенных четырехугольников GQ(A,t)
2.1. Локально GQ(A, 4)-графы
2.2. Вполне регулярные локально С(5(4,6)-графы
Глава 3. Расширения обобщенных четырехугольников GQ(b,3)
3.1. Вполне регулярные локально С(5(5,3)-графы
3.2. Дистанционно регулярные локально псевдо С(5(5,3)-графы
Глава 4. Автоморфизмы расширений обобщенных четырехугольников
4.1. Автоморфизмы сильно регулярнго графа с параметрами (322,96, 20,32)
4.2. Автоморфизмы сильно регулярнго графа с параметрами (322,96,20,32), в котором окрестности вершин — точечные графы для GQ(b, 3)
Литература
- Локально GQ(A, 4)-графы
- Вполне регулярные локально С(5(4,6)-графы
- Дистанционно регулярные локально псевдо С(5(5,3)-графы
- Автоморфизмы сильно регулярнго графа с параметрами (322,96,20,32), в котором окрестности вершин — точечные графы для GQ(b, 3)
Локально GQ(A, 4)-графы
Пусть Pi — матрица, в которой на месте (j,l) стоит р\-. Тогда собственные значения pi(0), ...,pi(d) матрицы Pi являются собственными значениями графа Г кратностей то = 1,...,ш . Матрицы Р и Q, у которых на месте {i,j) стоят стоят pj(і) и Qj(i) = rrijPi(j)/rii соответственно, называются первой и второй матрицей собственных значений схемы и связаны равенством PQ = QP = \Х\1.
Пусть Uj и Wj — левый и правый собственные векторы матрицы Pi, отвечающие собственному значению pi (j) и имеющие первую координату 1. Тогда кратность rrij собственного значения pi(j) равна v/(iij,Wj). Фактически, Wj являются столбцами матрицы Р и rrijUj являются строками матрицы Q.
Подстановочное представление группы G = Aut(T) на вершинах графа Г обычным образом дает матричное представление ф группы G в GL(n, C). Пространство Cv является ортогональной прямой суммой собственных G-инвариантных подпространств Wo,..., W& матрицы смежности А = А\ графа Г. Для любого д Є G матрица ф(д) перестановочна с А, поэтому подпространство W{ является (( -инвариантным. Пусть \i характер представления фціі.
Обобщенные четырехугольники GQ(A,t) имеют допустимые параметры при t Є {1,2,4,6,8,11,12,16}. Существование GQ(A,t) известно при t Є {1,2,4,6,8,16}. При t Є {11,12} неизвестно существование даже псевдогеометрических графов для GQ(A, t). При t Є {1,2,4,16} существуют единственные GQ(A,t) (для t = 16 см. [30]).
В главе 2 доказано, что вполне регулярных локально GQ(A, 4)-графов нет (теорема 2.1) и получено описание вполне регулярных локально GQ(A,6)-графов (теорема 2.2).
Подмножество Л обобщенного четырехугольника называется гиперовалом, если любая прямая пересекает Л по 0 или 2 точкам. То есть, гиперовал в GQ(s,t) — это регулярный подграф без треугольников валентности t + 1, имеющий четное число вершин. Известно (см. [7]), что /i-подграфы в локально С(5(й, )-графах являются гиперовалами. Для гиперовала А обобщенного четырехугольника прямую L назовем секущей, касательной и внешней прямой, если L П А содержит две, одну и ноль вершин соответственно; точку, смежную с ребром А, назовем реберной.
Доказательство. Пусть /І 24. Если XQ содержит ребро, то на прямой, содержащей это ребро, имеются точки из Xi,Xj,Xi и і + j -\-I = /І. Так как указанные точки лежат на внешней прямой, то каждое из чисел i,j, І не больше 8 и /І 24. Итак, XQ является кокликой. Утверждение (1) доказано.
Пусть z Є ХГ, г = /J — 24 и L - прямая, проходящая через z. Если L является секущей для Л, то L — {z} содержит две точки из Xi, Xj и по лемме 2.1 имеем i+j+r = /i — 4. Отсюда і = j = 10. Если L — внешняя прямая для Л и L пересекает Хо, то L — (Хо U {z}) содержит 3 точки из Xj, XJ, X/ и і + j + / = 24. Значит, і = j = I = 8.
Если у Є Хо, L — секущая, проходящая через z, то у смежна с единственной точкой прямой L. Так как указанная точка не попадает в Л U Хю, то у Є [z]. Лемма 2.3. Выполняются следующие утверждения: (1) если /І = 32, то XQ содержит единственную вершину а, [а] = Xg и Г — (a1- U Л) = Хю; (2) если /І = 30, то либо хо = 2,XQ = 5, 8 = 30, хю = 18, либо хо = 0, XQ = 25, Ж8 = 0, Хю = 30 и XQ является 5 х Ъ-решеткой. Доказательство. Пусть /І = 32. Тогда число секущих равно 80 и число внешних прямых равно 5. Далее, ХІ = 0 для і 8. Отсюда Хо содержит единственную вершину а, по лемме 2.2 имеем [а] = Xg и Г — (а-1 U Л) = Хю. Утверждение (1) доказано.
Пусть /І = 30. Тогда число секущих равно 75 и число внешних прямых равно 10. каждая внешняя прямая имеет тип (6,6,6,6,6) или (0,6,8,8,8), а каждая секущая имеет тип (6,10,10) или (8,8,10), в частности, Х2 = х = 0.
Так как вершина из Xg смежна с единственной вершиной из Хо и вершина из Хо смежна с 15 вершинами из Xg, то xg = 15жо, поэтому 16жо + XQ + Хю = 55 и 120жо + 6XQ + Южю = 450. Отсюда Южо + х& = 25. Если жо = 0, то XQ = 25, a g = 0, Хю = 30. В этом случае XQ является 5 х 5-решеткой. Если хо = 1, то XQ = Xg = 15, Хю = 24. В этом случае нет секущих типа (8,8,10), противоречие.
Если Хо = 2, то XQ = 5, Xg = 30, Хю = 18. Ключевую роль в доказательстве теоремы 2.1 имеет следующий результат, полученный с помощью компьютерных вычислений.
Предложение 2.1. [23]. Пусть А является гиперовалом в GQ(4,4), ХІ — число вершин вне Д, смежных точно с г вершинами из А. Тогда имеется 16 гиперовалов, попарно несопряженных относительно группы автоморфизмов GQ(A, 4) и выполняется одно из следующих утверждений:
Пусть диаметр Г не меньше 4. Выберем геодезический 4-путь uwxyz в Г. Тогда обобщенный четырехугольник [х] содержит гиперовалы [и] П [х] и [х] П [z], между которыми нет ребер. Тогда /І(М,Ж),/І(Ж, Z) 10 и [и] П [х] содержится в Хо([ж] П [z]), противоречие с тем, что по предложению 2.1 имеем Хо([ж] П [z])\ 6. Лемма доказана. Лемма 2.5. Имеем /І Є {16,34}, и диаметр Г равен 2 тогда и только тогда, когда /І = 34. Доказательство. Так как к (к — А — 1) = &2/І, где &2 = Г2(ІІ) для и Є Г, то /І делит 85 64. Отсюда /І = 10,16, 20,32 или 34. По предложению случай /І = 20 невозможен, а в случаях /І = 10 и /І = 34 диаметр Г равен 2.
Если диаметр Г равен 2, то Г является сильно регулярным графом и (А — /І)2 + 4(/С — /І) = (20 —/І)2+ 4(85— /І) является квадратом натурального числа п. Отсюда /І = 10 или /І = 34. В случае /І = 10 граф Г имеет параметры (630,85,20,10) и по [22] не существует. В случае /І = 32 граф Г имеет аффинные гиперовалы и по [18] не существует. Лемма доказана. Завершим доказательство теоремы. Компьютерные вычисления показывают, что в GQ(4,4) для данного гиперовала Л порядка 16 нет гиперовалов порядка 16, пересекающих Л по 4 изолированным ребрам. противоречие с тем, что xg = 2.
В случае гиперовала Л порядка 34 имеем хю = 51, противоречие с тем, что ввиду компьютерных вычислений найдется не более 17 гиперовалов порядка 34, пересекающих Л по 5 изолированным ребрам.
Точка х обобщенного четырехугольника GQ(s, t) называется регулярной, если \({х,у}"1)"1! = t + 1 для любой точки у ф х . Для регулярной точки X обобщенного четырехугольника S = (-Р, ) порядка (s,s) обобщенный четырехугольник P(S, х) порядка (s —1, s + 1) имеет множество точек Р = Р — х1-и множество прямых , состоящее из прямых С, не содержащих х7 и гиперболических прямых ({ж,!/}-1)"1, у ф х .
Основной результат параграфа Теорема 2.2 [27]. Пусть Г является связным вполне регулярным локально GQ(A, 6)-графом на v вершинах. Тогда v делится наЗ и выполняется одно из утверждений: (1) диаметр Г равен 2, Г имеет параметры (726,125,28,20) и спектр 1251,15225,-7500; (2) Г — дистанционно регулярный граф с массивом пересечений {125,96,1; 1,48,125} на 378 вершинах и спектром 1251,1125, 542, —20168; (3) Г — граф диаметра 3 с /І Є {20, 24, 25, ЗО, 32, 40}. Следствие 2.1. Пусть Г является дистанционно регулярным графом, в котором окрестность каждой вершины является обобщенным четырехугольником GQ(A,6). Тогда либо диаметр Г равен 2 и Г имеет параметры (726,125, 28, 20), либо Г — граф с массивом пересечений {125,96,1; 1, 48,125}.
Следствие 2.2. Пусть Г является связным вполне регулярным графом локально GQ(4,6)-графом, в котором окрестность некоторой вершины является известным обобщенным четырехугольником P(W(b),x). Тогда Г — дистанционно регулярный граф с массивом пересечений {125,96,1; 1,48,125}.
Вполне регулярные локально С(5(4,6)-графы
Доказательство. Пусть d(T) = 3. Напомним, что а\ = 20 и некоторое 9І для і 0 целое число. Если С2 = 8, то &2 = 96 75/8 = 900, ввиду лемм 3.1, 1.5 имеем &2 Є {8,16, 24} и сз Є {8,9,10,12,15,16,18, 20, 24, 25, 27,30,32,36,40,45,48, 50, 54, 60,64,72,75,80,90,96}. Имеем &2 = 24, сз = 10,30,60,80, соответственно, 6 2 = 14, #з = - 6,6 2 = 4,#з = -16 или сз = 72, &2 = 8,16,24 и 6 і = 24. В любом случае кратность не целая.
Если С2 = 12, то &2 = 96 75/12 = 600, ввиду лемм 3.1, 1.5 имеем &2 Є {4,8,12}, соответственно, 22 Є {80,76,72}. В случае &2 = 4 число 4сз делится на 12, поэтому сз Є {12,15,18, 24,30,36,45, 48,60, 72, 75, 90,96}. В случае &2 = 8 число 8сз делится на 12, поэтому снова Сз Є {12,15,18, 24,30,36,45,48, 60, 72, 75,90, 96}. В случае &2 = 12 число 0,2(0,2 - о\) = 64-44 не делится на 12, противоречие. Имеем &2 = 4,8, сз = 72 и 9\ = 24 или сз = 75, &2 = 8 и 6 2 = 6. В любом случае кратность 9 І не целая.
Если С2 = 16, то &2 = 96 75/16 = 450, ввиду лемм 3.1, 1.5 имеем &2 = 16, а.2 = 64 и сз Є {16,18,20,24,25,30,32,36,40,45,48,50,60,72,75,80,90,96}. Имеем либо сз = 60 и 6 2 = 4, либо сз = 72 и 6 і = 24, либо сз = 24 и 6 2 = 8, либо сз = 80 и 6 з = -16. В первых двух случаях кратность 9І не целая. В третьем случае кратность 92 равна 420, но р\ъ = -25. В четвертом случае число 9\ дробное, и кратность 9\ меньше 74, противоречие с леммой 1.5.
Если С2 = 18, то &2 = 96 75/18 = 400, ввиду лемм 3.1, 1.5 число &2 не больше 7 и делится на 6, поэтому Ь = 6, а = 72, 3 делит сз + 1 и Сз Є {20,32,50,80}. В этом случае целых 0І нет.
Если С2 = 20, то &2 = 96 75/20 = 360, ввиду лемм 3.1, 1.5 число &2 не больше 6 и делится на 4, поэтому &2 = 4, а.2 = 72, 5 делит сз + 2 и сз = 48. В этом случае целых 0І нет.
Если С2 = 24, то &2 = 96-75/24 = 300, ввиду лемм 3.1, 1.5 число &2 не больше 8 и делится на 8, поэтому &2 = 8, а = 64, и сз Є {24, 25,30, 32,40,48, 50, 60, 75,80,96}. Имеем сз = 60 и 02 = 4 или сз = 80 и #з = —16. В любом случае кратность 0І не целая.
Лемма 3.6. Если d(T) = 4 и /І = 8, то 48 сз 75.
Доказательство. Пусть d(T) = 4 и u,w,x,y, z — геодезический 4-путь в Г. Ввиду теоремы можно считать, что С2 = 8 и &2 = 96 75/8 = 900. Ввиду лемм 3.1, 1.5 имеем &2 Є {8,16, 24} и сз Є {8,9,10,12,15,16,18, 20, 24, 25, 27, 30}. Если w,w — две несмежные вершины из [и] ПГз(у), то [w] П [w \ содержит 5 вершин из и , поэтому сз 3 + 5 + 5.
Пусть сз = 15. Тогда кз = 900&2/15 = 60&2 и по лемме 1.5 число аз + а — а\ = 61 — &з + &4 делится на 8, поэтому 6з — 5 делится на 8, &з Є {5,13, 21} и С4 Є {16,24,32,40,48,56,64,72,80,96}. Все числа пересечений неотрицательные целые только для массивов пересечений {96, 75, 24, 5; 1,8,15, 72}, {96, 75, 24, 21; 1,8,15,16} или {96, 75, 24, 21; 1,8,15, 56}. В любом случае все неглавные собственные значения не целые и имеют дробные кратности.
Пусть сз = 16. Тогда к% = 900&2/16 = 225&2/4 и по лемме 1.5 число 63(0.3 + а —ai) = bs(60 — 63+0-4) делится на 8. Если Ь% нечетно, то С4 нечетно, А—Ь —с делится на 8 и С4 Є {21, 25, 27, 33,35,39,45, 51, 55, 57,63, 65,69, 75,81, 85,95}. Если &з сравнимо с 2 по модулю 4, то С4 сравнимо с 2 по модулю 4 и С4 Є {18,22,30,42,50,54,66,70,90}. Если Ь% делится на 4, то С4 четно и С4 Є {16,18, 20, 24, ЗО, 32,36,40, 48, 50, 54,60, 64, 72,80,90, 96}. Все числа пересечений неотрицательные целые только для массивов пересечений {96, 75, 24,16; 1,8,16, С4}, где С4 Є {16,32,48,80}. В любом случае все неглавные собственные значения не целые и имеют дробные кратности.
Пусть сз = 18. Тогда к% = 900&2/18 = 50&2 и по лемме 1.5 число Сз( 2з + а.4 —аг) = С3(58 — 63 + Q.4) делится на 8, поэтому 6з — 2 делится на 4. Отсюда с делится на 4 и С4 Є {20, 24, 28,32, 36,40,44,48, 56,60,64, 72, 80,84,88,96}. Все числа пересечений неотрицательные целые только для массивов пересечений {96, 75, 24,18; 1,8,18, С4}, где с Є {20, 36,40}. В любом случае все неглавные собственные значения не целые и имеют дробные кратности.
Пусть сз = 20. Тогда к% = 900&2/20 = 45&2 и по лемме 1.5 число Ьз(аз + а,4 — аі) = &з(56 — &з + Q.4) делится на 8, поэтому либо Ь% делится на 4, либо Ь% — 2 и С4—2 делятся на 4. Отсюда С4 Є {20, 22, 24, 28,30,32,36, 40,42,44,48, 50, 54, 56, 60,64,66, 70, 72,80,84,88, 90,96}. Все числа пересечений неотрицательные целые только для массивов пересечений {96, 75, 24, 20; 1,8, 20, С4}, где С4 Є {20, 32,40,60,72,80}, {96, 75, 24, 24; 1, 8, 20,48}, {96, 75, 24,12; 1,8, 20,60}. В любом случае все неглавные собственные значения не целые и имеют дробные кратности.
Пусть сз = 24. Тогда к% = 900&2/24 = 75&2/2 и по лемме 1.5 число Ьз(аз + а.4—аг) = 6з(52 — 63 + Q.4) делится на 8. Если Ь% нечетно, то С4 нечетно, 4 — Ь% — С4 делится на 8 и С4 Є {25, 27, 33,35,39,45, 51, 55, 57,63, 65,69, 75,81, 85,95}. Если &з сравнимо с 2 по модулю 4, то С4 сравнимо с 2 по модулю 4 и С4 Є {30,42,50,54,66,70,90}. Если Ь% делится на 4, то С4 делится на 4 и С4 Є {24,32,36,40,48,60,64,72,80,96}. Все числа пересечений неотрицательные целые только для массивов пересечений {96, 75, 24, 24; 1,8, 24, С4}, где С4 Є {24,32, 72}. В любом случае все неглавные собственные значения не целые и имеют дробные кратности.
Пусть сз = 25. Тогда кз = 900&2/25 = 36&2 и по лемме 1.5 число аз + а — а\ = 51 — Ъз + Q.4 делится на 8, поэтому Ъз — 3 делится на 8, &з Є {3,11,19} и С4 Є {32,48,64,72,88,96}. В этом случае допустимых массивов пересечений нет.
Пусть сз = 27. Тогда &2 = 24, кз = 900&2/27 = ЮО&2/З = 800 и по лемме 1.5 число аз + &4 аі = 49 — 6з + Q.4 делится на 8, поэтому &з — 1 делится на 8, Ъз Є {1,9,17} и С4 Є {32,40,48,64,72,80,96}. В этом случае допустимых массивов пересечений нет.
Пусть сз = 30. Тогда кз = 900&2/30 = 30&2 и по лемме 1.5 число Сз( 2з + &4 аі) = Сз(46 — Ъз + Q.4) делится на 8, поэтому Ъз — 2 делится на 4 и С4 делится на 4. Отсюда С4 Є {32,36,40,44,48,56,60,64,72,80,84,88,96}. Все числа пересечений неотрицательные целые только для массива пересечений {96, 75, 24, 2; 1,8,30,80}. В этом случае все неглавные собственные значения не целые и имеют дробные кратности.
Пусть сз = 32. Тогда кз = 900&2/32 = 225&2/4 и по лемме 1.5 число &з( 2з + 24 — а і) = &з(44 — Ъз + а ) делится на 8. Если Ъз нечетно, то С4 нечетно, 4 — Ъз — С4 делится на 8 и С4 Є {33,35,39,45, 51, 55, 57,63, 65,69, 75,81, 85,95}. Если Ъз сравнимо с 2 по модулю 4, то С4 сравнимо с 2 по модулю 4 и С4 Є {42, 50, 54,66, 70,90}. Если Ъз делится на 4, то С4 делится на 4 и С4 Є {32,36,40, 48,60,64,72,80,96}. В любом случае допустимых массивов пересечений нет.
Пусть сз = 36. Тогда кз = 900&2/36 = 25&2 и по лемме 1.5 число Ъз(аз + 24 — 2і) = &з(40 — Ъз + а ) делится на 8. Если Ъз сравнимо с 2 по модулю 4, то С4 сравнимо с 2 по модулю 4 и С4 Є {42, 50, 54,66, 70, 90}. Если Ъз делится на 4, то С4 делится на 4 и С4 Є {36,40,48,60,64,72,80,96}. В любом случае допустимых массивов пересечений нет.
Дистанционно регулярные локально псевдо С(5(5,3)-графы
Два последних утверждения леммы следует из леммы 2 [12]. Лемма 4.2. Пусть Г является сильно регулярным графом с параметрами (322,96,20,32), U — трехвершинный подграф из Г, Yi — множество вершин из Г - U, смежных точно с г вершинами из U, у І = \Yi\. Тогда выполняются следующие утверждения: (1) для двух вершин u,w подграф 2(11) П (ги) содержит 150 вершин, если и, w смежны, 160 вершин, если и, w не смежны; (2) число уо + уз равно 94, если U является кликой, равно 137, если U является кокликой; (3) число уо + уз, равно 106, если U является 2-путем, равно 117, если U — объединение изолированной вершины и ребра.
Доказательство. Если U является 3-кокликой, то Г содержит 3(32 - 2/з) вершин из І2, 3(уз + 32) вершин из Y\ и 137 - 2/з вершин из Уо, поэтому 2/о + 2/з = 137. Аналогично доказывается, что 2/о + 2/з = 94, если [/ является кликой; 2/0 + 2/3 = 106, если U является геодезическим 2-путем; 2/0 + 2/3 = Н7, если [/ объединение изолированной вершины и ребра.
Лемма 4.3. Пусть Г является точечным графом обобщенного четырехугольника GQ(b,3) с собственными значениями 4,-4 кратностей 45,50, G = Aut(r ), g — элемент простого порядка р из G, Q = Fix(g) и \[ и значение характера, полученного при проектировании на подпространство размерности 45 равно Xi(#) = ( а 0(д) + За[(д) — а 2(д))/32. Подставляя в эту формулу значение а 2(д) = 96 — а 0(д) — сх[(д), получим Хі(#) = { а оІ9) + а[(д))/8 — 3. Лемма доказана.
В леммах 4.4–4.7 предполагается, что Г — сильно регулярный граф с параметрами (322,96,20,32), д — автоморфизм простого порядка р графа Г и Q = Fix(g). Лемма 4.4. Выполняются следующие утверждения: (1) если Q — пустой граф, то либо р = 23 и ot\{g) = 92; либо р = 7 и ot\{g) Є {112,252}; либо р = 2 и ot\{g) Є {12, 52,92,132,172,212,252,292}; (2) если Q является п-кликой, то либо (г) р = 3; п = 1 и oti(g) = 60t + 36 или п = А и ai(g) = 60г + 108; или п = 7 и сїі(д) = 60г; либо (и) р = Ъ, п = 2 и сїі(д) = 100/ + 20 или п = 7 и ot\{g) = 100/; (3) если Q является т-кокликой (2 т 46); то р = 2 и ot\{g) = 20t + Am + 12; (4) если Q является объединением т (т 2) изолированных клик, то Q — коклика. Доказательство. Пусть Q — пустой граф. Так как 322 = 2 7 23, то р Є {2, 7, 23}. Пусть р = 23. По лемме 2.2 имеем ot\{g) = 92w и w — 1 делится на 5, поэтому ot\{g) = 92. Пусть р = 7. Ввиду леммы 2.2 имеем ot\(g) = 4(5г + 23) и Ъг + 23 делится на 7, поэтому ot\{g) Є {112,252}.
Пусть р = 2. По лемме 2.2 число Х2І9) 69 делится на 2, поэтому ot\(g) = 8w и 2w — 23 делится на 5. Отсюда ot\{g) Є {32, 72,112,152,192, 232, 272,312}. Утверждение (1) доказано. Пусть п = 1. Тогда р делит 96 и 225, поэтому р = 3 Из целочисленности Х2{д) следует, что oi\{g) = 60t + 36. Пусть п 2 и а,Ь Є Г2. Так как g действует полурегулярно на [а] — о-1, то р делит 75, поэтому р Є {3, 5}. Далее, д действует полурегулярно на [а] П [b] — Г2, поэтомур делит 22—п, р = 5 в случаяхп Є {2, 7} ир = 3 в случаяхп Є {4, 7}. Пусть р = 5. Тогда Х2(#) = (23 + п — ai(g)/4)/5, поэтому п = 2и ai( ) = 100/ + 20 или п = 7 и сїі(д) = 100/. Если р = 3, то ai(g) = 12гг , Xzig) = (п + 23 — Згу)/5, поэтому п = 4 и ai(g) = 60г + 108 или п = 7 и o?i(g) = 60г. Утверждение (2) доказано.
Для различных вершин а, Ъ Є Г2 элемент g действует полурегулярно на [а] П [6] и на Г2(а) П Г2(6) — Г2, поэтому р делит 2 и 162 — т. Отсюда р = 2 и m четно. Далее, Х2(#) = (т + 23 — ai(g)/4)/5 и 96 — Х2(#) четно, поэтому OL\(д) = 4(2гг + 1) и m + 22 — 2гг делится на 5. Отсюда а,\(д) = 20t + 4m + 12. Утверждение (3) доказано. Если а, с — несмежные вершины из Г2, то д действует полурегулярно на [а] П [с] и р = 2. Пусть а, 6 — смежные вершины из клики, лежащей в Q. Так как д действует полурегулярно на [а] — о-1, то р делит 75, противоречие. Лемма доказана. До конца параграфа будем предполагать, что Q содержит геодезический 2-путь о, а, с. Положим ot\(g) = pw. Лемма 4.5. Выполняются следующие утверждения: (1) если х Є Vt, то [х] не содержится в Q; (2) Q не является сильно регулярным графом с параметрами (г/, /сг, 20,32) и р 19. Доказательство. Пусть х Є Vt и [х] С Г2. Тогда \Q П [и]\ = 32 для любой вершины и Є Г - Q и it 5 является кокликой. Отсюда (1\{д) = О, xL = Q и р делит 225.
В случае р = 5 на Г - Q имеется 45 (д) -орбит и любая вершина и Є Г - Q смежна не более чем с одной вершиной в чужой (д)-орбите, противоречие.
В случае р = 3 на Г - Q имеется 75 (д) -орбит и любая вершина и Є Г - Q смежна с одной вершиной в 64 чужих (д)-орбитах. Пусть Yi — множество вершин из Г - и 9 , смежных точно с і вершинами из и 9\ у І = \Yi\. Тогда 2/о + 2/з = 97 + 33, противоречие с леммой 2.3. Утверждение (1) доказано.
Пусть А — сильно регулярный граф с параметрами (у , к , 20,32), к 96. Тогда п2 = (А - /І)2 + А(к - /І) = 4к + 16 и 32 делит к!{к! - 21). Поэтому к = 32 и А — полный многодольный граф, противоречие с тем, что 12 не делит 32.
Если р 20, то Q — граф с AQ = 20. В случае р = 31 имеем v Є {43,74,105} и степень вершины в Q равна 34 или 65. Если \Щ = 74, то Q — реберно регулярный граф с параметрами (74,34,20), противоречие с тем, что 74 34 20 не делится на 3. Значит, \Щ = 105, ot\{g) = 12Aw и X ig) = 21 - (31w - 23)/5, противоречие.
В случае р = 29 имеем v Є {32,61,90} и степень вершины в Q равна 38 или 67. Если \Q\ = 61, то Q — реберно регулярный граф с параметрами (61,38, 20), противоречие с тем, что 61-38-20 не делится на 3. Значит, \Q\ = 90, (У.\{д) = 116w и x ig) = 18 - (29w - 23)/5, поэтому ot\(g) = 232 и любая (д)-орбита длины 29 является кликой, противоречие.
В случае р = 23 имеем v Є {46, 69,92} и степень вершины в Q равна 27, 50 или 73. Если \Щ = 46, то Q — сильно регулярный граф с параметрами (46, 27, 20, 9), противоречие с тем, что (20 - 9)2 + 4 18 не является квадратом. Если \Q\ = 69, то ot\{g) = 92w и x ig) = 23(4 — w)/b, поэтому ot\{g) = 368, противоречие.
Значит, \Q\ = 92 и на Г — Q имеется десять (д)-орбит. Для вершины а степени 73 в Q число ребер между Q(a) и Q — а1- равно 73-6 = 32z + 9(18 — z), противоречие с тем, что Q—а1- является кликой. Итак, Q не содержит вершин степени 73. Теперь число ребер между Q и Г — Г2, деленное на 23, не меньше 184, поэтому некоторая вершина и Є Г — Q смежна по крайней мере с 19 вершинами из Q. Отсюда некоторая вершина из Г — (Q U и 9 ) смежна по крайней мере с 2 вершинами из [и] П Г2, противоречие.
Доказательство. Пусть р = 19. Тогда для двух вершин а, є Є Г2 число \Q(a) П [е] равно 1 или 20, если вершины а,е смежны, равно 13 или 32, если вершины а, е не смежны. Далее, \Q\ Є {18,37,56,75,94} и степень вершины в Q равна 20, 39, 58 или 77.
Если \Q\ = 37, то Q — сильно регулярный граф с параметрами (37, 20,1,13), противоречие. Если \Щ = 94, то x ig) = (117 — 19it )/5 и ot\(g) = 228, противоречие с тем, что каждая (д)-орбита на Г — Q является кликой.
Пусть \Щ = 56. Если степень вершины а в Q равна 39, то для любой вершины є Є Q(a) получим \ї(Ь) — а \ = 18, противоречие. Значит, Q — сильно регулярный граф с параметрами (56, 20,1,13), противоречие.
Итак, \Q\ = 75 и на Г — Q имеются тринадцать (д)-орбит. Как и выше, Q не содержит вершин степени 58. Теперь число ребер между Q и Г — Г2, деленное на 19, не меньше 225, поэтому некоторая вершина и Є Г — Q смежна по крайней мере с 18 вершинами из Q. Отсюда некоторая вершина из смежна по крайней мере с 3 вершинами из [и] П Г2, противоречие.
Автоморфизмы сильно регулярнго графа с параметрами (322,96,20,32), в котором окрестности вершин — точечные графы для GQ(b, 3)
Доказательство. Пусть р = 3 и А П Q является мельницей. Тогда для несмежных вершин 6, с Є А П Q подграф Q(b) П [с] является объединением трех изолированных ребер {а ,е }, і Є {1,2,3}, а = а\. Далее, Q(a) П [а ] является объединением трех изолированных ребер {&,& }, {с, с } и {d,d }. Так как /І = 32, то Q — связный граф. Заметим, что Q не содержит 7-клик. Иначе, можно считать, что a, Єї, 6, Ъ попадают в 7-клику L из Г2, противоречие с тем, что для любой вершины / Є L—{a, Єї, 6, b } в L должна найтись единственная вершина / со свойством f1- П Q = (f ) L П Г2. Теперь граф Г2 является кли-ковым 2-расширением вполне регулярного графа с параметрами (-и , 4,0,3), поэтому Q — кликовое 2-расширение графа, полученного удалением из К максимального паросочетания. Противоречие с тем, что Г — Q\ = 322 — 20 не делится на 3.
Лемма 4.11. Если р = 2, то Q является объединением не более б изолированных вершин и октаэдра или К -подграфа.
Доказательство. Пусть р = 2, а Є Г2 и А = [а]. Тогда 6, с Є А П Г2 и g индуцирует автоморфизм обобщенного четырехугольника [а]. Заметим, что для любых двух д-допустимых прямых K L из А, имеем ІІГ П Г2 = L П Г2. Далее, Ь1- содержит 0, 2 или 4 -допустимых прямых из А. Пусть прямая L графа А содержится в Q, а Є Q. Если а1- содержит четыре -допустимых прямых из А, то любая вершина из А - Й1 смежна с 4-кокликой из А(а), поэтому А С Q, противоречие. Значит, а1- содержит две д-допустимых прямых из А и А П Q является б х б-решеткой. В этом случае связная компонента Qo графа Г2, содержащая а, является сильно регулярным графом с параметрами (118,36,10,12), противоречие с тем, что \Q\ 112.
Пусть прямая L графа А содержит 4 вершины из Q. Если а1- содержит четыре -допустимых прямых из А, то любая вершина из А — а1- смежна с 4-кокликой из А (а), поэтому А П Q является обобщенным четырехугольником GQ(3} 3), противоречие. Значит, а1- содержит две -допустимых прямых из А и А ПГ2 является 4 х 4-решеткой. В этом случае связная компонента Qo графа Г2, содержащая а, является стандартным частным графа Джонсона J(8,4) с параметрами (35,16,6,8), противоречие с тем, что по лемме 1.6 имеем 12 35 80/287.
Пусть прямая L графа А содержит 2 вершины из Q. Тогда ДпГ2 является четырехугольником или і 4,4-подграфом. В этом случае связная компонента Qo графа Г2, содержащая а, является октаэдром или іСзх4-подграфом.
Пусть Qo является іСзх4-подграфом, и Кі,..., К± — попарно не пересекающиеся 3-клики из Г2о. Если V является 3-кликой из Q — Г2о, L — клика порядка 7 из Г, содержащая L , то вершина и Є L — V смежна с вершиной из К{. Так как [и] П [и9] — объединение 4 изолированных клик, то L попадает в окрестность вершины из К І для подходящего і, противоречие. Значит, Q является объединением 2г изолированных вершин zi, ...,Z2r и іСзх4-подграфа. Если К — клика порядка 7 из Г, содержащая К\, то вершина Zi смежна с вершинами и, и9 из КІ. Так как [и] П [и9] — объединение 4 изолированных клик, то г 3.
Пусть QQ является октаэдром, и К\,К і — не пересекающиеся 3-клики из Г2о. Если V является 3-кликой из Q — Г2о, L — клика порядка 7 из Г, содержащая L, то некоторая вершина и Є L — V смежна с 2 вершинами из К\ и с вершиной из К і. Противоречие с тем, что [и] П [и9] — объединение 4 изолированных клик. Значит, Q является объединением не более 6 изолированных вершин zi,..., Z2r и октаэдра. Лемма, а вместе с ней и теорема 4.2 доказаны.
До конца параграфа Г является сильно регулярным графом с параметрами (322,96,20,32), в котором окрестности вершин изоморфны точечному графу для GQ(b,3), и группа автоморфизмов G графа Г действует транзитивно на множестве вершин. Пусть а — вершина графа Г и Н = Ga. Тогда \G : Н\ = 322 и Н является {2,3, 5}-группой. Из теоремы 2 следует, что \G\ делит 211 З2 5 7 23.
Лемма 4.12. Выполняются следующие утверждения: (1) если g — элемент порядка 23 из G, то Сс{д) = (д); (2) если д — элемент порядка 7 из G, f — элемент простого порядка г 7 из Сс{д), то либо (і) р = 3, Q является 7-кликой, ot\{f) = 0 и ot\{g) = 252, либо (и) р = 2, Q — пустой граф и ot\{f) = 112 или Q является ІА-кокликой и ot\{f) = 168, либо Q является 28-кокликой и ot\{f) = 224; (3) G — простая неабелева группа.
Доказательство. Пусть д — элемент порядка 23 из G, / — элемент простого порядка г 23 из Сс{д) и Q = Fix(/). Тогда ot\{g) = 92. Из действия д на Q следует, что \Щ делится на 23. Ввиду теоремы 4.2 Q — пустой граф и г Є {2,7}. Если р = 7, то ot\{f) Є {112,252}. Если р = 2, то ot\{f) Є {32, 72,112,152,192, 232, 272, 312}. В любом случае имеем противоречие с действием д на множестве вершин, смежных с их образами под действием /. Утверждение (1) доказано. Пусть д — элемент порядка 7 из G, f — элемент простого порядка г 7 из Сс{д) и Q = Fix(/). Тогда ot\{g) Є {112,252}. Если р = 3, то Q является 7-кликой, ot\{f) = 0 и oi\{g) = 252. Если р = 2, то ввиду теоремы 4.2 либо Г2 — пустой граф и ot\{f) = 112, либо Г2 является 14-кокликой и ot\{f) = 168, либо Г2 является 28-кокликой и ot\{f) = 224. Утверждение (2) доказано. Допустим, что Q = 02(G) — неединичная группа. Тогда \аР\ = 2 и Qa — подгруппа из A\it(GQ(b, 3)), поэтому Qa — подгруппа из расширения эле ментарной абелевой подгруппы порядка 16 с помощью SQ. Отсюда \Q\ делит 211. Из действия элемента д порядка 23 на Q следует, что Q — элементарная абелева группа порядка 211, противоречие. Теперь 02:y(G) = 1 и цоколь Т группы G — простая группа. Так как Мт((д)) ф (д) и 23 — 1 = 2 11, то \ т{{д)) {д)\ = 2 и Т = G. Лемма доказана. Из леммы 4.12 и [14, таблицы 1-3] следует, что группа G изоморфна М23, М24, Со2 или Cos. Противоречие с тем, что \G\ не делится на 11. Следствие 4.1 доказано.
