Авторефераты по всем темам >>
Авторефераты по разное
Институт математики и механики Уральского отделения РАН На правах рукописи
ПАДУЧИХ Дмитрий Викторович Локальное строение графов и их автоморфизмы (01.01.06 математическая логика, алгебра и теория чисел)
АВТОРЕФЕРАТ
диссертации на соискание ученой степени доктора физико-математических наук
Екатеринбург - 2008
Работа выполнена в отделе алгебры и топологии Института математики и механики УрО РАН
Научный консультант:
доктор физ.-мат. наук, член-корр. РАН МАХНЕВ А.А.
Официальные оппоненты:
доктор физ.-мат. наук, профессор БАРАНСКИЙ В.А.
доктор физ.-мат. наук, профессор КАЗАРИН Л.С.
доктор физ.-мат. наук, профессор РОЖКОВ А.В.
Ведущая организация:
Институт математики и механики СО РАН
Защита состоится 20 мая 2008 г. в 15 ч. 30 м. на заседании совета Д 004.006.03 по защите диссертаций на соискание ученой степени доктора наук при Институте математики и механики Уральского отделения РАН по адресу: 620219, Екатеринбург, ул. Софьи Ковалевской, д. 16.
С диссертацией можно ознакомиться в научной библиотеке Института математики и механики УрО РАН.
Автореферат разослан 2008 г.
Ученый секретарь диссертационного совета доктор физ.-мат. наук КАБАНОВ В.В.
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы. В связи с завершением классификации конечных простых групп возникла задача единого представления конечных простых групп автоморфизмами конечных геометрий. Перспективным направлением является поиск такого класса конечных геометрий, что каждая конечная простая группа действует флаг-транзитивно на некоторой геометрии и все геометрии этого класса допускают классификацию. Например, класс билдингов Титса характеризует группы Лиевского типа [1]. Позднее в этом направлении возникли задачи, не связанные с групповым действием, в частности, такой является задача классификации дистанционно регулярных графов [2].
Пусть G транзитивная группа подстановок на множестве . Если подгруппа Gp группы G, состоящая из всех подстановок, фиксирующих точку p , имеет r орбит, то говорят, что G является группой ранга r. Пусть r = 3 и соответствующие 3 орбиты это {p}, (p), (p). Тогда по группе G удается построить сильно регулярный граф , множество вершин которого и две вершины p, q смежны в , если p (q).
Д. Хигман (см. [3], [4]) развил теорию групп ранга 3. Эти группы являются группами автоморфизмов сильно регулярных графов, причем они действуют транзитивно как на множестве вершин и ребер, так и на множестве пар различных несмежных вершин. Такие графы являются дистанционно транзитивными графами диаметра 2.
В диссертации рассматриваются неориентированные графы без петель и кратных ребер.
Граф диаметра d называется дистанционно транзитивным, если для любого i {0,..., d} и для любых вершин u, v, x, y, таких что (u, v) = (x, y) = i, существует автоморфизм g графа : (u, v)g = (x, y). Дистанционно транзитивные графы диаметра (графы ранга 3) сыграли важную роль в классификации конечных простых групп. Около половины спорадических групп были построены как группы автоморфизмов графов ранга 3 [5].
Если вершины u, w находятся на расстоянии i в , то через bi(u, w) (через ci(u, w)) обозначим число вершин в пересечении i+1(u) (в пересечении i-1(u)) с [w]. Дистанционно регулярным графом называется граф, в котором параметры bi(u, w) и ci(u, w) не зависят от вершин u, w, а зависят только от расстояния на котором эти вершины находятся в графе .
Поскольку каждый дистанционно регулярный граф является вполне регулярным графом (в частности, реберно регулярным графом), то некоторые результаты об этих классах графов могут быть использованы в теории дистанционно регулярных графов.
Цель работы. В диссертации исследуются классы графов с различными условиями регулярности и наборами запрещенных подграфов, некоторые локально F-графы и автоморфизмы графов.
Методы исследований. Основными методами исследования являются теоретико-графовые методы и методы теории конечных групп, в частности метод Хигмена приложения теории характеров к выяснению порядков автоморфизмов дистанционно регулярных графов и подграфов неподвижных точек этих автоморфизмов.
Научная новизна. Все основные результаты диссертации являются новыми.
Теоретическая и практическая ценность. Работа носит теоретический характер. Ее результаты могут быть использованы в теории групп и теории графов.
Апробация работы. Основные результаты диссертации неоднократно докладывались и обсуждались на алгебраическом семинаре отдела алгебры и топологии ИММ УрО РАН, а также были представлены на следующих конференциях: Международная алгебраическая конференция, посвященная 100-летию со дня рождения П.Г. Конторовича и 70-летию Л.Н. Шеврина; Международная конференция Алгебра и ее приложения, Красноярск 2002 и 2007 гг.; Международная конференция Алгебра, логика и кибернетика, Иркутск 2004; Региональная молодежная конференция ИММ УрО РАН, Екатеринбург 2002, 20и 2008; Международная алгебраическая конференция Классы групп и алгебр, Гомель 2005; Международная алгебраическая конференция, посвященная 100-летию со дня рождения Фаддеева Д.К., Санкт-Петербург 2007.
Публикации. Материал диссертации был опубликован в цикле работ, состоящем из статей (все опубликованы в журналах из списка ВАК), и 11 тезисов докладов. Из 9 статей 2 написаны без соавторов, 2 - тремя авторами (Кабанов В.В., Махнев А.А., Падучих Д.В.), еще 1 - тремя авторами (Зюляркина Н.Д., Махнев А.А., Падучих Д.В.), остальные 4 в соавторстве с Махневым А.А. Все совместные работы написаны в нераздельном соавторстве.
Структура и объем работы. Диссертация состоит из введения, 4 глав и списка литературы, содержащего 57 названий. Общий объем диссертации составляет 137 страниц.
КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении даны основные определения и обозначения, используемые в диссертации, обсуждается общая мотивировка решаемых задач. В главе 1 получена новая оценка для числа вершин в реберно регулярных графах, улучшающая оценку из главы 1 [2]. В главе 2 изучаются графы без m-корон: графы, в которых окрестности вершин кликовые расширения решеток; графы без корон с регулярными -подграфами; локальное строение графов без 3-корон с реберно регулярными -подграфами. В главе 3 получено описание кореберно регулярных графов, в которых принимает два значения. В главе 4 с помощью метода Г. Хигмана и результатов главы 3 исследуются группы автоморфизмов графа Ашбахера (графа Мура с k = 57) и сильно регулярного графа с параметрами (85, 14, 3, 2).
Пусть простой граф. Назовем окрестностью вершины u графа подграф всех смежных с u вершин. Окрестность вершины u будем обозначать через (u) или даже через [u]. Через i(u) обозначим подграф всех вершин, находящихся на расстоянии i от u.
Регулярным графом степени k называется Граф , такой что для любой вершины u выполняется |(u)| = k. Реберно регулярным графом с параметрами (v, k, ) называется регулярный граф степени k на v вершинах, любое ребро которого лежит точно в треугольниках. Вполне регулярным графом с параметрами (v, k, , ) называется реберно регулярный граф с параметрами (v, k, ), в котором любые две вершины u, w на расстоянии 2 имеют ровно общих соседей. Сильно регулярным графом с параметрами (v, k, , ) называется реберно регулярный граф с параметрами (v, k, ), в котором любые две несмежные вершины u, w имеют ровно общих соседей.
В связи с завершением классификации конечных простых групп возникла задача единого представления конечных простых групп автоморфизмами конечных геометрий. Перспективным направлением является поиск такого класса конечных геометрий, что каждая конечная простая группа действует флаг-транзитивно на некоторой геометрии, и геометрии этого класса можно классифицировать. Например, класс билдингов Титса характеризует группы Лиевского типа [1].
Пусть G транзитивная группа подстановок на множестве . Если стабилизатор Gp точки p имеет r орбит, то говорят, что G группа ранга r. Пусть r = 3 и соответствующие 3 орбиты это {p}, 1(p), 2(p). Если 1(p) и 2(p) содержат разное число элементов, то на множестве можно построить сильно регулярный граф . Для этого положим, что точка p смежна со всеми точками из 1(p), и для каждого g G точка pg смежна со всеми точками из 1(p)g. Если вместо 1(p) здесь взять 2(p), то мы получим дополнительный сильно регулярный граф.
Д. Хигман (см. [3], [4]) развил теорию групп ранга 3. Эти группы являются группами автоморфизмов сильно регулярных графов и действуют транзитивно на множестве {(u, w) | u, w и (u, w) = i} для любого i 2. То есть, такие графы являются дистанционно транзитивными графами диаметра 2.
Граф диаметра d называется дистанционно транзитивным, если для любого i {0,..., d} группа Aut действует транзитивно на {(u, w) | u, w и (u, w) = i}.
Дистанционно регулярным графом с массивом пересечений (b0,..., bd-1; c1,..., cd) называется граф диаметра d, в котором для любых вершин u, w , находящихся на расстоянии i, подграф (w) содержит ровно bi вершин, находящихся на расстоянии i + 1 от u, и ровно ci вершин, находящихся на расстоянии i - 1 от u. Легко понять, что условие дистанционной транзитивности влечет дистанционную регулярность графа. Таким образом, результаты, полученные для дистанционно регулярных графов, применимы и к дистанционно транзитивным графам.
Заметим, что сильно регулярный граф с > 0 является дистанционно регулярным графом диаметра 2, а дистанционно регулярный граф с d 2 вполне регулярным графом с k = b0, = k - b1 - 1 и = c2.
Пусть задан класс графов F. Мы скажем, что граф является локально F-графом, если для любой вершины a имеем (a) F. Тогда можно поставить задачу описания локально F-графов. Если граф вершинно транзитивен, то окрестности всех его вершин изоморфны, и граф является локально F графом, где F состоит из графов, изоморфных некоторому графу . В этом случае назовем локально -графом. В более общем случае F может быть классом графов, удовлетворяющих некоторым условиям. Например, класс связных, реберно регулярных графов это в точности класс связных, локально регулярных графов.
Определим несколько сильно регулярных графов, которые будут фигурировать в диссертации, а также являются примерами локально графов.
Пусть M и N конечные множества порядка m и n, соответственно. Два элемента из M N будем считать смежными, если они различаются точно в одной координате. Полученный граф называется m n-решеткой; при m = n он сильно регулярен с параметрами (n2, 2(n - 1), n - 2, 2).
Треугольным графом T (n) называется граф 2-подмножеств множества порядка n, в котором две вершины смежны тогда и только тогда, когда они пересекаются в точности по одной точке. Граф T (n) также сильно регулярен и имеет параметры (n(n - 1)/2, 2(n 2), n - 2, 4). Окрестность каждой вершины в T (n) изоморфна 2 (n - 2)-решетке, т.е.
T (n) локально 2 (n - 2)-решетка.
Единственный сильно регулярный граф с параметрами (27, 16, 10, 8) называется графом Шлефли. Единственный сильно регулярный граф с параметрами (16, 10, 6, 6) называется графом Клебша. Граф Шлефли является локально графом Клебша.
В главе 1 получена новая оценка для числа вершин в реберно регулярных графах. В книге Броувера, Коэна, Ноймайера [2] доказано, что если связный неполный реберно регулярный граф с параметрами (v, k, ), в котором k 3b1, то диаметр равен 2 и выполняется неравенство kb1 > (v - k - 1)(k - 2b1 + 1).
В статье [27] были получены следующие теоремы, позволяющие уточнить этот результат.
Теорема 1.1. Пусть связный неполный реберно регулярный граф с параметрами (v, k, ), и k 3b1 - 2. Тогда выполняется одно из следующих утверждений:
(1) для любой вершины u верно неравенство |2(u)|(k - 2b1 + 2) < kb1;
(2) для любой вершины u верно неравенство |2(u)|(k - 2b1 + 2) > kb1, и либо является реберным графом графа степени 3 без треугольников (т.е. k = 4, = 1), и диаметр графа больше 2, либо является n-угольником (n 5) или графом икосаэдра;
(3) является полным многодольным графом Kr2, 3 3-решеткой, треугольным графом T (m) (m 7), графом Клебша или графом Шлефли, и для любой вершины u верно равенство |2(u)|(k - 2b1 + 2) = kb1.
Теорема 1.2. Пусть связный неполный реберно регулярный граф с параметрами (v, k, ) и k 3b1. Тогда выполняется одно из следующих утверждений:
(1) (v - k - 1)(k - 2b1 + 3) - 5 < kb1;
(2) является треугольным графом T (5), графом Клебша или графом Шлефли.
Глава 2 посвящена изучению графов без m-корон.
Граф K1,...,1,3 с m долями порядка 1 называется m-короной. При m = 1 и m = 2 будем называть m-корону 3-лапой и короной, соответственно. Понятно, что m-корона получается из (m-1)-короны добавлением одной вершины, смежной со всеми остальными вершинами.
Поэтому граф без m-корон это в точности граф локально без (m - 1)-корон.
Пусть V является n-мерным векторным пространством над полем GF (q). Два mмерных подпространства из V будем считать смежными, если они пересекаются по (m-1)мерному подпространству. Граф на множестве всех m-мерных подпространств V с такой смежностью называется графом Грассмана и обозначается через Jq(n, m). При m = 2 граф Грассмана сильно регулярен. Граф Грассмана Jq(n, m) не содержит (индуцированных) корон.
В параграфе 2.1 изучаются сильно регулярные графы, у которых окрестность каждой вершины является кликовым -расширением p q-решетки. Интерес к таким графам был вызван тем, что при изучении графов без корон, в которых -подграфы являются регулярными графами заданной положительной степени (см. [7], [20]) наибольшие трудности вызвал случай, когда окрестность каждой вершины является кликовым -расширением p q-решетки.
Предложение 2.1.1. Пусть сильно регулярный граф с отрицательным собственным значением -m, в котором окрестность каждой вершины является кликовым -расширением p q-решетки, 2 p q. Тогда выполняются следующие утверждения:
(1) число вершин в максимальной клике L графа равно 1 + q или 1 + p, и (L, B) является (v, b, r, k, )-схемой, где B множество сингулярных прямых графа , лежащих в L, k = + 1, = 1, и тройка (v, b, r) равна (1 + q, (1 + q)q/( + 1), q) или (1+p, (1+p)p/( +1), p), соответственно; в частности, +1 делит p(p-1) и q(q -1);
(2) если p < q, то число (1 + q)-клик в графе равно pv/(1 + q), и 1 + q делит p(p-1)(-p+1), а число (1+p)-клик равно qv/(1+p), и 1+p делит q(q -1)(-q +1), если p = q, то 1 + p делит 2(p - t)(p - 1, + 1)(p + 1, - 1);
(3) для двух несмежных вершин a, b любая строка (любой столбец) решетки, отвечающей [a], содержит 0 или + 1 вершин из [b], и = t( + 1), где + 1 t p;
(4) если t = + 1, то [a] [b] является t t-решеткой, и является треугольным графом T (m) (m 4), графом J(10, 5) или графом Грассмана Jt-1(n, 2), n 4;
(5) если m = p - u, то t p - u, причем равенство достигается лишь при u = 0; в частности, t = p - 1, и если t = p - 2, то m = p - 1, (2 + 1)(p - 2) = (q - 1), и + делит 2(p - 1, q);
(6) если t = p, то m = p, и (i) является псевдогеометрическим графом для pG+1(q, p - 1), и (q + p - 1)( + 1) делит p(p - 1)q(q + 1), (ii) если p < q, то является геометрическим графом, и каждый -подграф в графе прямых данной геометрии является объединением непересекающихся ( + 1) ( + 1)решеток, + 1 делит q - 1, и p + 1 делит q(q - 1)(q + 1);
(iii) если p = q, то ( + 1)2 делит p2(p + 1).
Заметим, что если псевдогеометрический граф для pG2(p, p - 1), являющийся локально p p-графом, то дополнительный граф для 4 4-решетки в случае p = 3 и граф J(8, 4) в случае p = 4 (отсюда следует изоморфизм J(8, 4) и дополнительного графа для графа Грассмана J2(4, 2)).
В теореме 2 из [8] была получена классификация сильно регулярных локально p qграфов с 2 p q и p 6. Следующая теорема распространяет этот результат на графы, в которых окрестности вершин являются кликовыми расширениями p q-решетки.
Теорема 2.1.1. Пусть сильно регулярный граф, в котором окрестность каждой вершины является кликовым -расширением p q-решетки, 2 p q. Если p 6, то выполняется одно из следующих утверждений:
(1) = p - 1, и является графом Грассмана Jp-1(n, 2);
(2) = p - 2, и либо имеет параметры второй окрестности вершины в графе Грассмана Jp-1(4, 2), либо является точечным графом частичной геометрии pGp-1((p 2)q, p - 1), p - 1 делит q - 1;
(3) = 2, и является псевдогеометрическим графом для частичной геометрии pG3(12, 5);
(4) = 1, и является либо треугольным графом T (q + 2), либо дополнительным графом для 44-решетки, графом J(8, 4) или J(10, 5), либо псевдогеометрическим графом для частичной геометрии pG2(6, 5).
В параграфе 2.2 изучаются графы Тервиллигера без корон и графы без 3-коклик с регулярными -подграфами (см. также [20]).
М. Нумата [9] получил классификацию графов без корон, в которых -подграфы являются изоморфными реберно регулярными графами диаметра 2 (естественно, не имеющими 3-лап). В связи с этим результатом представляет интерес изучение графов, в которых каждый -подграф является реберно регулярным графом без 3-лап с заданными параметрами (v, k, ).
В статье В.В.Кабанова [7] было получено следующее обобщение результата Нуматы, опирающееся на более ранние работы А.А. Махнева и В.В. Кабанова:
Связный редуцированный граф без корон, содержащий 3-коклику, в котором -подграфы регулярны заданной степени > 0 и имеют диаметр 2, является графом Грассмана, графом Джонсона или его частным, локально треугольным графом или графом Госсета.
Важным этапом в доказательстве этого результата стала лемма 2.1 [7], в которой доказано, что слабо редуцированный граф без 3-лап, содержащий 3-коклику, в котором подграфы регулярны заданной положительной степени, является редуцированным.
Предложение 2.2.1. Если связный слабо редуцированный граф без 3-коклик, в котором -подграфы регулярны степени > 0, то является редуцированным графом или пятиугольной пирамидой.
В статье А.А. Махнева и В.В. Кабанова [10] было доказано, что если связный граф Тервиллигера без 3-лап, то либо является кликовым расширением графа икосаэдра, либо подграф, индуцированный на множестве всех вершин из - с некликовыми окрестностями, является либо пустым графом, либо кликовым расширением клики или графа с = 1.
Теорема 2.2.1. Пусть связный граф Тервиллигера без корон, подграф на множестве вершин с некликовыми окрестностями. Тогда выполняется одно из следующих утверждений:
(1) не содержит 3-коклик и является кликовым расширением 2-пути, 3-пути, пятиугольника или пятиугольной пирамиды;
(2) не содержит 3-лап, но содержит 3-коклику, диаметр больше 2, и либо (i) является кликовым расширением графа икосаэдра, либо (ii) является кликой, и является кликовым расширением графа , где содержит -клику и или - 1 вершин степени 1, смежных с различными вершинами клики, либо (iii) является кликовым расширением графа с = 1;
(3) содержит 3-лапу, = 1, и окрестность любой вершины из состоит из изолированных клик.
Следствие 2.2.1. Пусть связный граф, в котором окрестности вершин являются регулярными графами Тервиллигера диаметра 2. Если окрестность некоторой вершины не содержит корон и 5-коклик, то либо является кликовым расширением пятиугольника или графа икосаэдра, либо локально граф Петерсена, т.е. граф T (7), граф Конвея-Смит на 63 вершинах диаметра 4 (это антиподальное 3-накрытие T (7)) или граф Доро на 65 вершинах диаметра 3.
Следующая теорема является аналогом результата, полученного в статье В.В. Кабанова [7] для редуцированных графов без 3-коклик.
Теорема 2.2.2. Пусть связный редуцированный граф без 3-коклик, в котором каждый -подграф регулярен заданной степени > 0. Тогда сильно регулярен, или степень любой вершины из равна k или k - 1, подграф на вершинах степени k является октаэдром, подграф на - является 6-кликой и каждая вершина из - смежна с 3-кликой из .
Обратно, если сильно регулярный граф без 3-коклик с параметрами (v, k, , ), то каждый -подграф регулярен степени = 2 + 2 - k.
Следствие 2.2.2. Пусть связный редуцированный граф без корон, в котором каждый -подграф реберно регулярен с заданными параметрами (v, k, ) и имеет диаметр 2. Тогда выполняется одно из следующих утверждений:
(1) = 0, и совпадает с октаэдром или треугольным графом T (5);
(2) > 0, не содержит 3-коклик и является сильно регулярным графом с параметрами ((s2 + 3s)2, (s2 + 2s - 1)(s2 + 3s + 1), (s + 2)(s3 + 2s2 - 1), (s2 + 2s)(s2 + 2s - 1));
(3) > 0, содержит 3-коклику и является графом Грассмана, графом Джонсона или его частным, локально треугольным графом или графом Госсета.
В параграфе 2.3 изучаются Графы без 3-корон с реберно регулярными -подграфами.
А именно, с помощью классификации графов без корон с регулярными -подграфами диаметра 2 степени > 0 (см. предыдущий пункт) в статье [31] были получены следующие две теоремы.
Теорема 2.3.1. Пусть связный граф без 3-корон, в котором любой -подграф состоит из v > 1 вершин, и |(x) (y)| = > 0 для любых смежных вершин x, y . Если окрестность некоторой вершины из является графом Тервиллигера, то является либо кликовым ( +2)-расширением mn-решетки, либо графом Тервиллигера одного из следующих типов:
(1) кликовое расширение 2-пути, 3-пути, пятиугольника или пятиугольной пирамиды;
(2) кликовое расширение графа , где является объединением -клики и или - вершин степени 1, смежных с различными вершинами этой клики;
(3) кликовое расширение графа икосаэдра или графа без 3-лап с = 1.
Теорема 2.3.2. Пусть связный граф без 3-корон, в котором каждый -подграф является реберно регулярным графом с параметрами (v, k, ) и окрестностями вершин диаметра 2. Если 0 < k - 1, то либо окрестности вершин в являются сильно регулярными графами без 3-коклик, либо локально -граф, где один из следующих графов:
(1) треугольный граф T (n) (n 6) или граф Шлефли;
(2) частное графа Джонсона J(10, 5) или половинный граф свернутого 10-куба;
s (3) граф Грассмана J2 (n, 2), где n 4.
В параграфах 2.4 и 2.5 доказано несуществование локально J(10, 5)-графов и графов, окрестности вершин которых изоморфны половинному графу свернутого 10-куба (см. [30], [34]). Таким образом, можно исключить случай (2) из теоремы 2.3.2.
В параграфе 2.6 доказано, что связные компоненты -подграфов в локально Jq(n, 2) графах являются графами Джонсона J(6, 3) или дополнительными графами к 4 4решетке. В частности, q = 2. См. также [31].
Графы знакопеременных и квадратичных форм над полем порядка 2 являются вполне регулярными локально Грассмановыми графами с = 20 (см. [11]).
В параграфе 2.7 доказано, что если вполне регулярный локально J2(n, 2) граф с = 16, то n = 4 и || = 72 (см. [32]).
Следствие 2.1. Пусть связный граф без 3-корон, в котором каждый -подграф является связным реберно регулярным графом с параметрами (v, k, ) и окрестностями вершин диаметра 2. Если > 0, то выполняется одно из следующих утверждений:
(1) либо является графом Шлефли или графом Госсета, либо граф имеет параметры ((r2 + 3r)2, r3 + 3r2 + r, 0, r2 + r) для некоторого r 1;
(2) каждый -подграф является октаэдром, и половинный граф ректаграфа с c3 = 3, являющийся локально треугольным графом;
(3) является локально Грассмановым графом, и либо (i) = 16, n = 4, и антиподальный граф диаметра 3 на 72 вершинах, либо (ii) = 20, и если для любой вершины a графа граф 2(a) является регулярным степени 15 2n-1 - 105, то имеет накрытие, являющееся графом Alt(n, 2) знакопеременных форм или графом Quad(n - 1, 2) квадратичных форм.
В параграфе 2.8 получено описание вполне регулярных локально GQ(4, 2) графов. См.
статью [16].
Обобщенным четырехугольником порядка (s, t) называется геометрия точек и прямых, в которой каждая прямая содержит s + 1 точку, каждая точка лежит на t + 1 прямой, и для любой прямой L и точки x L существует единственная прямая M, проходящая че/ рез x и пересекающая L. Обобщенный четырехугольник порядка (s, t) обозначается через GQ(s, t). Геометрия GQ(s, t) однозначно восстанавливается по своему точечному графу.
Мы будем обозначать точечный граф обобщенного четырехугольника порядка (s, t) также через GQ(s, t).
Нетрудно понять, что граф GQ(s, t) не содержит корон. Следовательно, локально GQ(s, t)-графы не содержат 3-корон. Так как -подграфы в GQ(s, t) являются (t + 1)кокликами, то в локально GQ(s, t)-графах -подграфы не содержат треугольников и, следовательно, не удовлетворяют условию теорем 2.3.1 и 2.3.2. Известна классификация локально GQ(s, t)-графов в случае s 3. Следующая теорема дает описание вполне регулярных локально GQ(4, 2)-графов.
Теорема 2.8.1. Вполне регулярный локально GQ(4, 2)-граф является одним из следующих графов:
(1) единственный сильно регулярный локально GQ(4, 2)-граф с параметрами (126, 45, 12, 18);
(2) единственный дистанционно регулярный локально GQ(4, 2)-граф на 378 вершинах с массивом пересечений (45, 32, 12, 1; 1, 6, 32, 45) (это 3-накрытие графа из пункта (1)).
В главе 3 изучаются кореберно регулярные графы с = 2, у которых каждое ребро содержится в 1 или 2 треугольниках. Сделаны уточнения результатов из [12]. См. работу [25].
Подграфы неподвижных точек автоморфизмов сильно регулярного графа с малыми значениями параметров и имеют жестко заданное строение. Так, непустой подграф неподвижных точек автоморфизма графа Мура сам является графом Мура или звездой (см. лемму 1 из [13]). Для изучения подграфов неподвижных точек автоморфизмов сильно регулярных графов с = 2 может быть полезна следующая теорема.
Теорема 3.1. Пусть граф, в котором каждое ребро содержится в 1 или 2 треугольниках, и подграф [u] [w] является 2-кокликой для любых двух несмежных вершин u, w. Тогда либо сильно регулярный граф, либо выполняются следующие утверждения:
(1) граф регулярен степени k, окрестность любой вершины в является объединением x изолированных (1 + 1)-клик и y изолированных (2 + 1)-клик, число (1 + 2)-клик в равно v(2(v - k - 1) - k(k - 2 - 1)) ;
(1 + 1)(1 + 2)(2 - 1) (2) для связной компоненты графа 1, определенного на множестве вершин графа , в котором вершины a, b смежны, только если они смежны в и |[a] [b]| = 1, выполняются утверждения:
(i) если x > 1, то является вполне регулярным графом с параметрами (v, x(1 + 1), 1, 2), (ii) если содержит геодезический 4-путь abcde, то x 4, и для u [a] - (a) имеем d(a, u) 4, (iii) если x = 2, то является (1 + 2) (1 + 2)-решеткой, а если x = 3, то является графом диаметра 3, (iv) если сильно регулярный граф, то любая связная компонента графа 1 изоморфна , граф , определенный на множестве {1,..., s} связных компонент графа 1, s = v/v, в котором вершины i и j смежны, если j = i, и некоторая вершина из i смежна с единственной вершиной из j, является сильно регулярным с параметрами (s, y(2 + 1), 2 + 2(v - k - 1), 2v);
(3) если y = 1, то либо x = 1 и является (1 + 2) (2 + 2)-решеткой, либо x > и выполняются утверждения:
(i) множество вершин графа можно представить в виде разбиения на t клик C1,..., Ct порядка 2 + 2, где t = v/(2 + 2), и граф , определенный на множестве {C1,..., Ct}, в котором клики Ci и Cj смежны, если j = i и некоторая вершина из Ci смежна с вершиной из Cj, является частичным четырехугольником с параметрами (t, k - 2 - 1, 1, 22 + 4), (ii) граф 1 является дистанционно регулярным графом диаметра 4 с массивом пересечений {x(1 + 1), (x - 1)(1 + 1), 2(2 + 1), 1; 1, 2, (x - 1)(1 + 1), x(1 + 1)}, и если 1 > 0, то 2 + 4x(1 + 1) является квадратом.
Заметим, что для связной компоненты графа 2, определенного на множестве вершин графа , в котором вершины a, b смежны, только если они смежны в и |[a][b]| = 2, выполняются утверждения, аналогичные сформулированным в теореме. В случае x = выполняется аналог утверждения (3), полученный заменой (y, 2) на (x, 1) и обратно.
Для четного натурального числа через MP () обозначим класс реберно регулярных графов с параметрами b1 = 3/2 - 3, k = 2 - 3/2, = 2 - 3 + 2, v = 2, содержащих пару непересекающихся подграфов 1 и 2, изоморфных K/2, причем любая вершина из 1 (из 2) несмежна с единственной вершиной в каждой доле из 2 (из 1), и для любого ребра {d, e} из 1 подграф - (d e) является ребром из 2. Любой граф из MP (2) состоит из двух изолированных ребер, а граф из MP (4) изоморфен графу Клебша (сильно регулярному графу с параметрами (16,10,6,6)). По аналогии с листом Мебиуса, mтрапом Мебиуса назовем граф, полученный из графа вершин и ребер боковой поверхности m-призмы, разрезанием по боковому ребру, переворачиванием правой стороны на 180 и склеивания.
В теореме 1.4.3 из [2] доказано, что если связный реберно регулярный граф с параметрами (v, k, ), в котором k + 1/2 - 2k + 2 (равносильно k b1(b1 + 3)/2 + 1), то дополнительный граф для сильно регулярного графа с 2. В следствии 2 из [12] (опирающемся на теорему 2 [12]) получено описание связных, реберно регулярных графов с k b1(b1 + 3)/2 - 2. Однако, доказательство теоремы 2 в [12] некорректно (ошибка в доказательстве леммы 27), поэтому теорема 2 и следствие 2 из [12] нуждаются в уточнении.
Скорректированная формулировка теоремы 2 из [12] имеет вид Теорема 3.2. Пусть связный реберно регулярный граф с параметрами (v, k, ), в котором (u, w) = или k - для любых вершин u, w с (u, w) = 2. Если для каждого ребра {a, b} подграф - (a b) состоит из двух смежных вершин, то выполняется одно из следующих утверждений:
(1) диаметр больше 2, и получается удалением из полного двудольного графа Kk+1,k+1 максимального паросочетания;
(2) граф сильно регулярен;
(3) для вершины u подграф {w 2(u) | (u, w) = k - } является полным многодольным графом Kys, s = b1 + 2 - , 1 b1, и для графа 1, определенного на множестве вершин графа , в котором две вершины a, b смежны, только если они несмежны в и (a, b) = , верны утверждения:
(i) если y = 1, то 1 является дистанционно регулярным графом диаметра 4 с массивом пересечений {x, x - 1, 2s, 1; 1, 2, x - 1, x}, где x = b1 + 2 - ys, множество вершин графа можно представить в виде разбиения на t коклик C1,..., Ct (антиподальных классов) порядка s+1, где t = v/(s+1), и антиподальное частное является частичным четырехугольником с параметрами (t, b1 + 2 - s, 0, 2s + 2), (ii) если 1 имеет связную компоненту диаметра 2, то каждая связная компонента графа 1 является сильно регулярным графом с параметрами ((x2 + x + 2)/2, x, 0, 2), где x = b1+2-ys = t2+1 для некоторого t не кратного 4, и граф , определенный на множестве {1,..., l} связных компонент графа 1, l = 2v/(x2 +x+2), в котором вершины i и j смежны, если j = i и некоторая вершина из i смежна с единственной вершиной из j, является сильно регулярным с параметрами (l, rs, s - 1 + x(x - 1)/2, x2 + x + 2).
Если выполняется утверждение (3i) и является полным двудольным графом, то MP (), 6, b1 = 3/2 - 3, k = 2 - 3/2, s = /2 - 1 и v = 2.
Скорректированная формулировка следствия 2 из [12] имеет вид Следствие 3.1. Пусть неполный связный реберно регулярный граф с парамет рами (v, k, ). Если k + 1/2 - 2k + 8 (равносильно 2k b2 + 3b1 - 4), то (1) граф является n-угольником, n 6, тривалентным графом без треугольников, реберным графом тривалентного графа без треугольников, графом икосаэдра, треугольным графом T (6) или графом Клебша (во всех этих графах b1 3), или (2) граф является дополнительным к сильно регулярному графу с 2, или (3) либо граф принадлежит MP (), = 6, 8, либо для графа = выполняется одно из следующих утверждений:
(i) граф разбивается дополнительными графами для 4-трапов Мебиуса 1,..., r, где r = v/8 и граф на множестве вершин {1,..., r}, в котором вершины i и j смежны, если некоторая вершина из i смежна с вершиной из j в графе , является сильно регулярным с параметрами (v/8, t2 - 9, 6, 16), и t = 12 или 36, (ii) граф можно представить в виде разбиения на 3 3-решеток 1,..., s, где s = v/9, и граф на множестве вершин {1,..., s}, в котором вершины i и j смежны, если некоторая вершина из i смежна с вершиной из j в графе , является сильно регулярным с параметрами (v/9, t2 - 7, 8, 18), и t = 7, 14 или 28, (iii) граф на множестве вершин графа , в котором вершины u, w смежны, если они смежны в и |(u) (w)| = 0, дистанционно регулярный граф диаметра 4 либо имеющий массив пересечений {136, 135, 6, 1; 1, 2, 135, 136} и являющийся антиподальным 4-накрытием сильно регулярного графа с параметрами (2432, 136, 0, 8), либо имеющий массив пересечений {x, x - 1, 4, 1; 1, 2, x - 1, x} и являющийся антиподальным 3-накрытием сильно регулярного графа с параметрами ((x + 2)(x + 3)/6, x, 0, 6).
В случае k = (b2+3b1)/2 в заключении следствия остаются n-угольник, граф икосаэдра, граф из MP (6) и дистанционно регулярный граф диаметра 4 с массивом пересечений {x, x - 1, 4, 1; 1, 2, x - 1, x}, являющийся антиподальным 3-накрытием сильно регулярного графа с параметрами ((x + 2)(x + 3)/6, x, 0, 6), подтверждающие точность границы k > b1(b1 + 3)/2, дающей сильную регулярность графа.
Глава 4 посвящена изучению автоморфизмов дистанционно регулярных графов.
В монографии П. Камерона [14] представлен метод Г. Хигмана, который дает необходимое условие существования автоморфизма дистанционно регулярного графа.
Пусть дистанционно регулярный граф диаметра d. Подстановочное представление группы G = Aut на вершинах графа дает матричное представление группы G в GL(v, C). Пространство Cv является ортогональной прямой суммой собственных подпространств W0 Wd матрицы смежности A графа . Для любого g G матрица (g) перестановочна с A, поэтому подпространство Wi является (G)-инвариантным.
Пусть i характер представления, полученного ограничением (G) на Wi. Тогда d i(g) = v-1 Qijj(g), j=где j(g) число вершин x из , таких что (x, xg) = j, а Qij зависят от параметров .
Поскольку значения характеров целые алгебраические числа, то в случае, когда значения Qij рациональны, i(g) является целым числом. Отсюда получаем условие делимости для j(g), j = 1,..., d. С помощью этого условия были получены новые ограничения для групп автоморфизмов сильно регулярных графов с параметрами (85, 14, 3, 2) (см.
[35]) и (3250, 57, 0, 1) (см. [28]). Эти результаты являются частью серии работ, посвященных изучению групп автоморфизмов сильно регулярных графов с малыми значениями и .
В параграфе 4.1 получены результаты о группе автоморфизмов сильно регулярного графа с параметрами (85, 14, 3, 2).
Наименьшим примером сильно регулярного графа с параметрами (v, k, 3, 2) является 5 5-решетка, имеющая параметры (25, 8, 3, 2). Следующим набором параметров с = 3 и = 2, для которого возможно существование сильно регулярного графа, является (85, 14, 3, 2).
Теорема 4.1.1. Пусть сильно регулярный граф с параметрами (85, 14, 3, 2). Тогда для любого автоморфизма g из Aut простого порядка p выполняется одно из следующих утверждений:
(1) p {5, 17} и Fix g пустой граф;
(2) p = 7 и Fix g является 1-кликой, или p = 5 и Fix g является 5-кликой;
(3) p = 3, Fix g является четырехугольником или 25-решеткой, и в последнем случае для шести вершин из Fix g их окрестности содержат точно две максимальных 3-клики;
(4) p = 2, окрестность каждой вершины из Fix g связна, Fix g является объединением изолированных вершин и изолированных треугольников, причем либо = 1 и {4, 6}, либо = 0 и = 5.
В параграфе 4.2 изучается группа автоморфизмов графа Мура степени 57 (графа Ашбахера).
Для регулярного графа степени k и диаметра d на v вершинах выполняется неравенство:
v 1 + k + k(k - 1) + + k(k - 1)d-1.
Графы, для которых достигается равенство, называются графами Мура. Простейшим примером графа Мура служит (2d + 1)-угольник.
Дамерелл в [6] доказал, что граф Мура степени k 3 имеет диаметр 2. В этом случае v = k2 +1, граф сильно регулярен с = 0 и = 1, а степень k равна 3 (граф Петерсена), (граф Хофмана-Синглтона) или 57. Существование графа Мура степени k = 57 неизвестно. Ашбахер в статье [15] показал, что граф Мура с k = 57 не является графом ранга 3.
Мы будем называть граф Мура с k = 57 графом Ашбахера.
Пусть граф Ашбахера, G = Aut . Ранее в работе [13] было доказано, что если G содержит инволюцию t, то G = O(G) t, и Fix t является 56-звездой. Приведенная ниже теорема (см. [28]) удаляет предположение о существовании инволюции.
Теорема 4.2.1. Пусть граф Ашбахера и G = Aut . Тогда либо (1) G содержит инволюцию t, и либо O(G) = P силовская 5-подгруппа из G порядка 125, |[P, t]| = 25, Z(P ) действует полурегулярно на , Fix (CP (t)) граф ХофманаСинглтона, и P содержит 25 подгрупп Ui порядка 5, имеющих пятиугольник в качестве подграфа неподвижных точек, либо G = Y t X, Y циклическая группа, инвертируемая t, |Y | делит 7, 19, 55, |X| делит 7, 25, 27 или 55, и если X = 1, то верно одно из утверждений:
(i) Fix X звезда, |X| = 7 и Y = 1, (ii) Fix X пятиугольник, |Y | делит 5, либо Fix x граф Хофмана-Синглтона для некоторого элемента x порядка 5 из X и |X : x | {5, 11}, либо Fix x = Fix X для любого неединичного элемента x из X и |X| делит 55, (iii) Fix X граф Петерсена, |X| делит 27, |Y | делит 5 и если Y = 1, то Fix Y является пустым графом, (iv) Fix X граф Хофмана-Синглтона, |X| делит 25, |Y | делит 5 или 7, и если |Y | = 5, то Fix Y является пустым графом или пятиугольником, а если |Y | = 7, то Fix Y является звездой на 51 или на 16 вершинах либо (2) |G| нечетен и верно одно из утверждений:
(i) 19 делит |G|, G = Ga для некоторой вершины a, и G подгруппа из группы Фробениуса порядка 3219, (ii) 13 делит |G|, либо G подгруппа из циклической группы порядка 65 и каждый неединичный элемент из G действует без неподвижных точек на , либо G группа Фробениуса порядка 39, (iii) 11 делит |G|, G расширение циклической группы порядка 11 с помощью элементарной абелевой группы U порядка, делящего 25, (iv) 7 делит |G|, либо G подгруппа прямого произведения циклической группы порядка 7 и элементарной абелевой группы U порядка, делящего 25, в случае U = 1 подграф Fix U является графом Хофмана-Синглтона, либо G группа Фробениуса порядка 21, (v) (G) {3, 5}, либо |G| делит 54, либо G подгруппа из прямого произведения группы порядка 5 и группы порядка 27, либо G группа Фробениуса порядка 75 или 543, либо |Z(G)| = 5 и G/Z(G) группа Фробениуса порядка 75.
Непустой подграф неподвижных точек подгруппы из группы автоморфизмов графа Мура является графом Мура или звездой. При доказательстве теоремы используется следующий результат о подграфах неподвижных точек автоморфизмов графа Ашбахера.
Предложение 4.2.1. Пусть граф Ашбахера, g автоморфизм простого порядка p графа , = Fix g. Тогда выполняется одно из утверждений:
(1) пустой граф и p {5, 13};
(2) звезда на вершинах и либо = 1 и p = 19, либо = 56 и p = 2, либо = 58 - 7y для некоторого y 8 и p = 7;
(3) пятиугольник и p {5, 11};
(4) граф Петерсена и p = 3;
(5) граф Хофмана-Синглтона и p = 5.
ИТЕРАТУРА 1. Tits J. Buildings of Spherical Type and finite BN-pairs, Springer Lecture Notes in Mathematics, v. 386.
2. Brouwer A.E., Cohen A.M., Neumaier A. Distance-regular graphs // Berlin etc: SpringerVerlag - 1989.
3. Higman D.G. Finite permutation groups of rank 3 // Math. Z., 1964, v. 86, 145Ц156.
4. Higman D.G. Primitive rank 3 groups with a prime subdegree // Math. Z., 1966, v. 91, 70Ц86.
5. Prager C.E., Soicher L.H. Low rank representations and graphs for sporadic groups.
Lecture series 8. Cambridge, University press, 1997.
6. Damerell R.M. On Moore graphs // Math. Proc. Cambr. Phil. Soc., 74(1973), 227Ц236.
7. Кабанов В.В. О графах без корон с регулярными -подграфами // Матем. заметки, 2000, т. 67, №6, 874Ц881.
8. Зюляркина Н.Д., Махнев А.А. О сильно регулярных локально решетчатых графах // Дискрет. матем. 1993, т. 5, 145Ц150.
9. Numata M. A characterization of Grassman and Johnson graphs // J. Comb. Theory, Ser. B, 1990, v. 48, 178Ц190.
10. Кабанов В.В., Махнев А.А. Графы без 3-лап с равномощными -подграфами // Изв. Урал. гос. ун-та, Математика и механика, 1998, №10, 44Ц68.
11. Munemasa A., Pasechnik D.V., Shpectorov S.V. A local characterization of the graphs of alternating forms and the graphs of quadratic forms over GF(2) // Finite Geometry and Comb. London Math. Soc. Lecture Note Series 191. Cambr. Univ. Press 1993, 303Ц317.
12. Махнев А.А. О сильной регулярности некоторых реберно регулярных графов // Известия РАН, серия матем. 2004, т. 68, №1, 159Ц172.
13. Махнев А.А., Падучих Д.В. Об автоморфизмах графа Ашбахера // Алгебра и логика 2001, т. 40, №2, 125Ц134.
14. Cameron P. Permutation Groups, London Math. Soc. Student Texts 45, Cambridge Univ. Press. - 1999.
15. Aschbacher M. The nonexistence of rank three permutation groups of degree 3250 and subdegree 57 // J. Algebra 1971, v. 19, №3, 538Ц540.
Работы автора по теме диссертации 16. Махнев А.А., Падучих Д.В. Расширения GQ(4, 2), вполне регулярный случай // Дискрет. матем. 2001, т. 13, №3, 91Ц109.
17. Paduchikh D.V. Non-existence of locally J(10, 5)-graphs // Укр. матем. конгресс 2001.
Тез. докл. Киев, секция 1, с. 40.
18. Кабанов В.В., Махнев А.А., Падучих Д.В. О графах без корон с регулярными подграфами // Труды 33-й молодежной конф. ИММ УрО РАН. Екатеринбург 2002, 25Ц28.
19. Кабанов В.В., Махнев А.А., Падучих Д.В. Локальное строение графов без 3-корон с реберно регулярными -подграфами // Международная конф. Алгебра и ее приложения, Красноярск 2002, 55Ц57.
20. Кабанов В.В., Махнев А.А., Падучих Д.В. О графах без корон с регулярными подграфами, II // Матем. заметки 2003, т. 74, 396Ц406.
21. Кабанов В.В., Махнев А.А., Падучих Д.В. О локально решетчатых подграфах в графах Грассмана // Алгебра, логика и кибернетика. Тез. докл. Иркутск 2004, 149Ц151.
22. Махнев А.А., Падучих Д.В. О сильной регулярности некоторых реберно регулярных графов // Алгебра, логика и кибернетика. Тез. докл. Иркутск 2004, 181Ц183.
23. Махнев А.А., Падучих Д.В. Новая оценка для числа вершин реберно регулярных графов // Труды 36-й молодежной конф. ИММ УрО РАН. Екатеринбург 2005, 52Ц54.
24. Зюляркина Н.Д., Махнев А.А., Падучих Д.В. О графах, в которых окрестности вершин являются кликовыми расширениями решеток // Межд. алгебр. конф. Тез. докл.
Екатеринбург, изд-во Урал. ун-та 2005, 178Ц179.
25. Махнев А.А., Падучих Д.В. Об одном классе кореберно регулярных графов // Известия РАН, сер. матем. 2005, т. 69, №6, 95Ц114.
26. Падучих Д.В. Об автоморфизмах сильно регулярного графа с параметрами (85,14,3,2) // Межд. алгебр. конф. Классы групп и алгебр. Тез. докл., Гомель 2005, 85Ц87.
27. Махнев А.А., Падучих Д.В. Новая оценка для числа вершин реберно регулярных графов // Сибирский матем. журнал 2007, т. 48, №4, 817Ц832.
28. Махнев А.А., Падучих Д.В. О группе автоморфизмов графа Ашбахера // Алгебра и ее приложения, Красноярск 2007. Тез. докл. 93Ц94.
29. Махнев А.А., Падучих Д.В. О локально грассмановых графах // Межд. алгебр.
конф. Санкт-Петербург 2007. Тез. докл., 54Ц55.
30. Paduchikh D.V. Non-existence of locally J(10, 5)-graphs // Proceedings of the Steklov Inst. of Math. 2007, Suppl. 1, 155Ц163.
31. Кабанов В.В., Махнев А.А., Падучих Д.В. Характеризации некоторых дистанционно регулярных графов запрещенными подграфами // Доклады Академии Наук 2007, т. 414, №5, 583Ц586.
32. Махнев А.А., Падучих Д.В. О локально грассмановых графах // Доклады Академии Наук 2007, т. 415, №4, 450Ц454.
33. Зюляркина Н.Д., Махнев А.А., Падучих Д.В. О графах, в которых окрестности вершин являются кликовыми расширениями решеток // Доклады Академии Наук 2007, т. 416, №5, 735Ц739.
34. Махнев А.А., Падучих Д.В. О графах, в которых окрестности вершин изоморфны половинному графу свернутого 10-куба // Труды 39-ой молодежной конф. ИММ УрО РАН. Екатеринбург 2008.
35. Падучих Д.В. Об автоморфизмах сильно регулярного графа с параметрами (85,14,3,2) // Дискретная математика 2008.