Графы Кэли групп Zd и пределы конечных вершинно-примитивных графов тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

РОССИЙСКАЯ АКАДЕМИЯ НАУК УРАЛЬСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ И МЕХАНИКИ

На правах рукописи

КОСТОУСОВ КИРИЛЛ ВИКТОРОВИЧ

ГРАФЫ КЭЛИ ГРУПП ЪА И ПРЕДЕЛЫ КОНЕЧНЫХ ВЕРШИННО-ПРИМИТИВНЫХ

ГРАФОВ

01.01.06 — математическая логика, алгебра и теория чисел

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

ооз15втэе

Екатеринбург, 2007

Работа выполнена в отделе алгебры и топологии Института математики и механики УрО РАН

Научный руководитель доктор физико-математических наук

В И Трофимов

Официальные оппоненты доктор физико-математических наук,

профессор В В Беляев

Защита состоится 23 октября 2007 года в часов на заседании специализированного совета Д 004 006 03 по защите диссертаций на соискание ученой степени доктора физико-математических наук при Институте математики и механики УрО РАН по адресу 620219, г Екатеринбург, ул С Ковалевской, 16

С диссертацией можно ознакомиться в научной библиотеке Института математики и механики УрО РАН (г Екатеринбург, ул С Ковалевской,

кандидат физико-математических наук, доцент В В Кораблева

Ведущая организация Институт математики СО РАН,

г Новосибирск

16)

Автореферат разослан 13 сентября 2007 года

Ученый секретарь диссертационного совета доктор физ -мат наук

В В. Кабанов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы Один из главных подходов к изучению конечных примитивных групп подстановок основан на их реализации как групп автоморфизмов графов (каждая примитивная группа допускает такую реализацию) В связи с этим большой интерес представляет класс TV конечных связных графов, допускающих вершинно-примитивные группы автоморфизмов В алгебре и комбинаторике существенную роль играет, кроме того, подкласс j:j>e~trans класса TV, состоящий из графов с вершинно-примитивными реберно-транзитивными группами автоморфизмов Класс j?'pe~trans^ в свою очередь, содержит важный подкласс TVmn, состоящий из графов минимальной валентности для конечных вершинно-примитивных групп Связный граф Г называется графом минимальной валентности для вершинно-примитивной группы автоморфизмов G, если Г имеет Наименьшую валентность среди всех связных графов Д, таких что У(Д) ="У(Г) и G < Aut(A) Вершинно-примитивные графы минимальной валентности-для конечных примитивных групп подстановок доставляют наиболее естественные их реализации в качестве групп автоморфизмов графов

Для изучения класса TV в работах В И Трофимова1, M Гиудичи", Ч Ли, Ч Прэгер и А Сереша2 был предложен подход, связанный с изучением предельных графов для класса TV Если С — произвольный класс конечных связных вершинно-примитивных графов, то предельными для С называются бесконечные связные графы, у которых каждый шар изоморфен шару некоторого графа из С Класс предельных для С графов обозначается через lim(C) Описание lim(C) доставляет описание типичного локального строения графов из С Вопрос о строении графов из hm(TV) был поставлен В И Трофимовым3

В силу сказанного выше, также представляет интерес изучение строения графов из \im(TVe~trans) и hrn(TVmm)2 Заметим, что, как показано в работе2, строение графов из hm(TVe~tran&) во многом определяет строение произвольных графов из lim (TV)

В работе M Гиудичи, Ч Ли,Ч Прэгер, А СерешаиВИ Трофимова2

1 Трофимов В И О действии примитивных групп// Алгебра и логика 1989 Т 28 №3 с 337-369

2Giudici M , Li С H j Praeger С E , Seress A , Trofimov V On limit graphs of finite vertex-primitive graphs// J Comb Theory Ser A 2007 V 114 P 110-134

3Коуровская тетрадь Нерешенные вопросы теории групп Новосибирск Новосиб гос ун-т. 2002. вопрос 12 89

было начато систематическое изучение класса Ьш^Т) При этом была показана важность подклассов ТТна, Р"Раз> ТТра класса ТТ опреде-мых следующим образом Пусть (7 — примитивная группа подстановок на конечном множестве V и V € V Группа (3 называется примитивной группой Я А-типа, если она содержит регулярную абелеву нормальную подгруппу Группа (7 называется примитивной группой Аб'-типа, если она почти проста, те 1пп(Г) < С? < АиЬ(Т) для некоторой конечной неабелевой простой группы Т Наконец, группа в называется примитивной группой РА-типа, если (7 имеет единственную минимальную нормальную подгруппу N = Тк, где Т — некоторая конечная неабеле-ва простая группа, к > 2, и стабилизатор элемента V в N проектируется на (нетривиальные) собственные подгруппы прямых простых факторов группы N Для X € {НА, АБ, РА} через ТТх обозначается класс графов, допускающих вершинно-примитивную группу Х-типа, через обозначается подкласс класса ТТх, состоящий из графов, допускающих реберно-трянзитивную вершинно-примитивную группу X-типа, а через ТТхш обознается подкласс класса ТТе£(гаП1!, состоящий из графов минимальной валентности для вершинно-примитивных групп X-ти па

В указанной работе2 доказано, что

\Ш1(ТТ) = ЪШ{ТГна) и Ът^лз) и Ът(ГРРА), Ьт(ТТе~*гаП8) = \М.ТТенХап1 и Ьт(РР%!гапз) и Ьт{ТТе^тапз) и Ьт(^Ртп) = Ьти и Ьт

Поэтому представляющее самостоятельный интерес изучение классов графов Ьш.(ТТва), Ьт{ТТе^ап11) и 1нп{ТТн!) является, вместе с тем необходимым, этапом изучения классов графов Ьт^Т), \\ш{ТТе~гтап!1) и ЬтСЛ3™")

Кроме того, в той же работе2 показано, что каждый граф из Ьт{РТца) является графом Кэли группы Ъл для некоторого й Напомним, что графом Кэли группы соответствующим конечной системе порождающих М, такой что М = — М и 0 £ М, называется граф Гс множеством вершин У(Г= ^ и множеством ребер ~ Иа> Ь} а — Ье М} Граф назовем минимальным графом Кэли группы если множество М является орбитой наименьшей мощности на 1/ \ {0} стабилизатора вершины 0 в группе Аи^Г^м)

Класс всех графов Кэли группы 7Ld обозначим через Cay(Zd), подкласс всех реберно-транзитивных графов класса Cay(Zá) обозначим через Caye-írons(Zí2), а класс всех минимальных графов Кэли группы ЪА обозначим через Caymn(Zd) Помимо определенного самостоятельного интереса, изучение классов Caye_írans (Zd) и Caymm(Zd) представляет интерес в связи с изучением классов lim{JrVe~tTans) и hm{ТТтт), поскольку каждый граф из hm(J:Vs£^ans) (соответственно из lim^TV^™)) лежит в Gaje~tTüns(Zd) (соответственно в Caymm(Zd)) для некоторого d В - íí

связи с этим актуальными являются следующие две задачи, рассмотрению которых посвящена настоящая диссертация

1) Исследовать Caye-Íraíls (Zd) П lim{TVe£Írans) для фиксированных значений d

2) Исследовать Gaymm(Zd)nhm(J:V,jj2) для фиксированных значений

d

Заметим, что описание графов из Caye-írans(Zd) П lim^P^f™5) (соответственно из Caymm(Zd) П hm(FVf%) ) для всех d, не превосходящих некоторого положительного целого числа п, доставляет, в частности, описание класса всех графов валентности, не превосходящей 2п + 2 лежащих в \im{JcVeI¡Xans) (соответственно в \im(TV^))

Целью работы является исследование

a) графов, являющихся предельными для класса конечных графов, допускающих вершинно-примитивную реберно-транзитивную группу автоморфизмов ДА-типа, ~ -

b) графов, являющихся предельными для класса графов минимальной валентности для вершинно-примитивных групп автоморфизмов НА-типа,

c) реберно-транзитивных и минимальных графов Кэли групп Zd (в их связи с а) и Ь) )

Методы исследования В основе используемого метода исследования реберно-транзитивных и минимальных графов Кэли групп Zd лежит установленная в диссертации связь таких графов с конечными подгруппами группы GL<¡(Z), позволившая, в частности, воспользоваться для

целей работы компьютерной системой GAP4'0 Кроме того, используются методы теории групп и теории графов

Научная новизна Результаты, полученные в работе, являются новыми

Теоретическая и практическая ценность Диссертационная работа носит теоретический характер Полученные результаты могут быть использованы в теории групп и комбинаторике при изучении конечных примитивных групп и конечных вершинно-примитивных графов Разработанные методы позволяют исследовать реберно-транзитивные и минимальные графы Кэли групп

Апробация работы. Основные результаты работы докладывались на международных конференциях "Мальцевские чтения'1 (Новосибирск, 2005 г и 2006 г), на Международной школе-конференции по теории групп, посвященной 75-летию со дня рождения А И Старостина (Нальчик, 2006 г), на международной конференции "Алгебра и ее приложения", посвященной 75-летию ВП Шункова (Красноярск, 2007 г), на 36-й, 37-й и 38-й Региональных молодежных конференциях ЙММ УрО РАН (Екатеринбург, 2005-2007 гг), и на алгебраическом семинаре ИММ УрО РАН Исследования, проведенные в диссертации были поддержаны грантом РФФИ № 06-01-00378

Публикации. Основные результаты диссертации опубликованы в работах [1-7]

Структура и объем работы Диссертация состоит из введения, содержащего формулировки основных результатов, шести глав, списка литературы из 21 наименования я списка основных используемых обозначений Часть результатов технического характера вынесена в концы соответствующих глав в виде приложений Общий объем диссертации составляет 122 страницы

СОДЕРЖАНИЕ РАБОТЫ

Реализуемый в диссертации подход к исследованию задач 1) и 2) (см выше) опирается на теоремы 1 и 2 йз главы 1

4Schonert Martm et al GAP — Groups, Algorithms, and Programming Lehrstuül D fur Mathematik, Rheinisch Westfälische Technische Hochschule, Aachen, Germany, sixth edition, 1997

5The GAP Group GAP — Groups, Algorithms, and Programming, Version 4 4, Aachen, St Andrews, 2004 (http //www gap-system org)

Теорема 1 доставляет эффективный метод проверки изоморфности графов Коли групп Zd В ее формулировке группа Ъа отождествляется с множеством целочисленных вектор-строк длины d с операцией покоординатного сложения

Теорема 1 Пусть Мг — конечная система порождающих группы Iß', такая что 0 ^ М, а М, = —Мг, для г = 1,2 Тогда

(а) Графы Кэли и Г^Ма изоморфны тогда и только тогда, когда di — di и Мг = М\а для некоторой матрицы а 6 GL^Z)

(б) Каждый изоморфизм графа r2dl Ml на граф TZd2 м2 задается формулой х и- ха + у, х G Zdl, для подходящих а £ GL^Z),?/ G Zdl

В теореме 2 устанавливается связь реберно-транзитивных и минимальных графов Кэли группы Zd с конечными подгруппами группы GL<j(Z) Для ее формулировки введем следующие определения

Пусть Q1 — d-мерное векторное пространство над полем Q, элементами которого являются рациональные вектор-строки длины d Для г е {1, , d} через ed<l обозначим элемент из <Qf*, у которого на г-м месте стоит 1, а на остальных — 0 Всюду далее вместо е^,» будем писать ег, опуская первый индекс (он всегда может быть восстановлен из контекста) Для М С <Qd через (М}+ будем обозначать подгруппу аддитивной группы векторов пространства порожденную множеством М, а через (М) q будем обозначать подпространство векторного пространства на Qd, натянутое на М .

Для конечной подгруппы G группы GL^(Z) определим число

m(G) =mm{|xG| xeQd\{0}},

множества

Mz{G) ={xG x €Zd\{0},\xG\ = m(G),xG = -xG, (xG}+= Zd},

Mq{G) ={xG же Qd\{0}, \xG\ = m(G),xG = -xG, dan({xG)Q) = d} и классы графов

OGe'trans(G) ={r(lG)+ilG xe®d\{0},xG = -xG,d™((xG)q) = d}, ogmm(G) = {г(м)+,м M G

Теорема 2 Пусть G\, , Gn — все с точностью до сопряжения в GLd(Q) конечные подгруппы группы GL¿(Z), содержащие —Еа (где E¡¡ — единичная dx d-матрица) Тогда класс Caye~írans (Zd) (соответственно класс Caymm(Zd) ) совпадает с классом Це{3> >n} OQe-tTans {Gs) (соответственно с классом U»e{i, п} OQmm{Gl) )

В силу теоремы 2 для явного описания классов Caye~trans (Zd) и Caymm(Zd) требуется выбрать представителей различных изоморфных типов графов из Цб{1> ¡n} Oge~lran*{Gt) и Це{1, ,n} Ogmm{Gt) соответственно Для этого используется, в частности, теорема 1

Глава 2 диссертации посвящена изучению классов Caye~tran*(Zd) П Ът(^Ге^тапз) при d > 1

Описание класса Caye~trans (Z) П bm(FVe£][an') (а, вместе с тем, и класса Caymm(Z) П lim(^r'P™jl) ) дает следующая теорема

Теорема 3 Классы Ca,ye~traw(1) П hm(TVe£%ans) и Caymm(Z) П lim(^Тн™) совпадают и содержат единственный граф Гщг-ц

При d > 2 получен следующий результат о строении класса C&ye~trans(Zd) П hmíFPZZ™)

Теорема 4 Класс Caye~trans {Zd) П hm(FTe¿¡rans) бесконечен для каждого d> 2

При доказательстве теоремы 4 для каждого d > 2 явным образом строится счетное множество попарно не изоморфных графов Кэли группы Z¿, лежащих в

Главы 3-6 диссертации посвящены изучению классов Caymm(Zd) Г) hm^Vff1^) при d > 2 на основе теорем 1 и 2

В главе 3 получены следующие описания классов Caymm(Z2) П Ьш^на) и Caymm(Z3) n М-Л^)

Теорема 5. Caymm(Z2) = {Гр^.Г^,} С Ьш(^а), ^е М2Д = ±{еь е2}, М2,2 = ±{е2, е2, е2 + е2}

Теорема 6 Caymm(Z3) = {ГадЛ £ bm(.FP^), где Мзд = ±{е1,е2,ез}

Использование теорем 1 и 2 для описания класса Caymm(Zd) П hm^V^) при d > 4 требует больших вычислений В связи с этим

в главе 3 описана схема нахождения минимальных графов Кэли группы Zd с использованием системы GAP

Как видно из теорем 3,5 и 6, класс Caymm(Zd) Р Inn{TVh7) конечен при d < 3 Однако, как вытекает из следующей теоремы 7, доказываемой в главе 4, для d = 4 это уже не так Для ее формулировки нам понадобится следующее определение, естественно возникающее в связи с теоремой 2

Будем говорить, что конечная группа G < GL¿(Z) имеет бесконечный орбитный тип, если класс OQmm{G) бесконечен В противном случае будем говорить, что группа G имеет конечный орбитный тип Из определения легко следует, что свойство конечной подгруппы группы GLd(Z) иметь бесконечный орбитный тип инвариантно при сопряжении в GLd(<Q>)

Теорема 7 С точностью до сопряжения в GL^Q) подгруппы бесконечного орбитного типа группы GL^Z) исчерпываются группами

-1 -1\

О -1

-1 0 '

0 0/

0 -1 \

-1 -1

0 -1 ■

1 1

о о \

0 о

1 о -1 ~\)

(<3i S Z3 X Z8, G2 S Qs X Z3, G3 S G2 X Z2)

Описание класса Caym*"(Z4) П lim(^"P™!) Дает следующая теорема, доказательство которой приводится в главе 4

Теорема 8 Минимальные графи Кэли группы Z4 с точностью до изоморфизма исчерпываются графами Кэли группы Z4, соответствующими следующим системам порождающих

С?! - (hu Д2), G2 - (fu f2, h), G3 = (G2, h), где

/ 0 0 -1 ( 0 -1

0 -1 -1 -1 , h2 = 0 -1

0 0 0 -1 1 -1

V -i 1 1 1 \0 1

( -i 1 1 0 \ / 0 -1

-i 0 0 -1 h = 1 -1

-i 1 1 1 -1 0

V i 0 -1 0 V 0 1

/ -i 0 1 0 \ (-1 0

0 0 1 1 , /4 = -1 1

-1 0 0 0 -1 0

\ 1 -1 -1 -1/ V 1

М4д = ±{е1;е2>ез,е4};

М4,2 = ±{еь е3, е4, ех + е2, е2 + е3 + е4},

М4>3 = ±{еь е2, е3, е4, в! - е2, е3 - е4},

элементам из .Мг(Си) и .А4г(б?2) (все они порядка 24)

Все минимальные графы Кэли группы й4 лежат в \1т.(Т'Р™2)

В главах 5 и 6 получены, соответственно, следующие описания классов Саутт(25) П Ьт(Яр™«) и Саут!В(2б) П ШТТ^Х)

Теорема 9. Саугот(Е5) = {Гда^.Г^,} С Ьт^™«), Мь Л = ±{е/ге{1, ,5}}, М5:2 = М\ и ±{ех + е2 + е3 - е4 - е5}

Теорема 10 Саутт(1?) = {Гг5,Мбг г е {1, ,7}} С где

М6,1 = ±{ег г е {1, , 6}}, '

Мз,2 = ±{еь е2, е3, е6 в! - е4, е2 - е5, е3 - е4 + е5 - е6}, М6)3 = Мед и ±{ех - е2, е3 - е4, е5 - е6};

Мб,4 = Мед и ±{в! - е2 + е4, в! - е3 + ег, с2 - е3 + е6, е4 - е3 + е6}, Мб,5 = (в! — ез)^1 порядка 36, Мб,е = е^2 порядка 42,

Ме 7 = вх^3 поряд™, где

/ 10 11 1 -м / 0 0 0 -1 0 1\

10 0 1 1 0 0 1 1 0 0 1

0 110 0 -1 -1 0 0 0 0 0

-10 0 0 -1 1 } 1 -1 -1 0 0 0

0 0 0 0 1 0 -1 1 0 0 -1 1

\ 10 10 1 -1/ \ - -1 1 0 0 0 0 /

/0 10 0 0 0 \ /0 1 0 0 0 0\

10 0 0 0 0 0 0 0 0 0 1

_ / 0 0 1 0 0 0 0 0 1 1 0 0 \

- \ 0 1 -1 0 0 -1 5 1 0 -1 -1 0 0

0 0 0 0 1 0 0 0 0 -1 0 1

\ 1 0 -1 -1 0 0/ V1 0 -1 -1 -1 1/

-1 о о \ -1 -1 о -10 0 110 0-10 -1-11/

Полученные результаты о строении класса Саутот(2^) П Ит^Р™]1) при <1 < 6 дают следующее описание графов малой валентности из

м^тта

Следствие 1 Следующий список содержит все графы из \шх{ТТ'Т^2), валентность которых не превосходит 14

1) ^,{1,-1} валентности 2,

2) Г211±{е1,е2} валентности 4,

3) Г2г1±{е1,е2,е1+е2} валентности 6,

4) Ггз>±{еье2 е3} валентности 6,

5) Гг4,±{е1,е2,ез,е4} валентности 8,

6) Г24>±{еьез1е4А+е2>е2+ез+е4} валентности 10,

7) Г251±(е1 е2,ез,е4,е4} валентности 10,

8) Г,Е<,±{е1,еа,ез,е4,е1—еа,ез—в4} валентности 12,

9) Г251±{е1е21е3:е41е51е1+е,+ез_е4_е^ валентности 12,

Ю) Г26 ,±{еье2,ез,е4,е5,е6} валентности 12,

П) Г2а ,±{ед,е2,ез,е6,ег-е4,е2-е5,ез-е4+е5-ее} валентности 14, 12) Г271±{еье21ез,е41е51еб1е7} валентности 14

Автор выражает глубокую благодарность своему научному руководителю В И Трофимову за постановку задачи, внимание и поддержку, а также всем участникам семинара отдела алгебры и топологии ИММ УрО РАН за критические замечания и плодотворное обсуждение результатов диссертации

/ 0 0 1 0

1 0 1 0

-1 1 1 1

0 0 -1 0

0 0 0 0

\ -1 1 1 0

/0 1 о о о о

0 о

1 -1 \1 о

0 \ /1-1-1 -1 0 0-1

0 0-10

1 '000 О 0 0 0

О / V 0 —1 —1

1110 4 1110 -10 0 1 0-1-10 ^ 0 0 1-1 0 110/

Заключение

Диссертационная работа посвящена изучению графов Кэли групп являющихся предельными для класса конечных вершинно-примитивных графов Получены следующие основные результаты

1) Исследованы изоморфизмы и группы автоморфизмов графов Кэли групп Показано, в частности, что каждый изоморфизм графов Кэли групп Ъй имеет вид х ь-> ха + у, х € где а € 01^(2), у ё

2) Для каждого А > 2 построено счетное множество попарно не изоморфных реберно-транзитивных графов Кэли группы 1/, являющихся предельными для класса конечных графов, допускающих реберно-транзитивную вершинно-примитивную группу автоморфизмов

3) Разработана схема, позволяющая, в принципе, получить описание минимальных графов Кэли группы Ъ6, при произвольном наперед заданном й

4) Для каждого й < 6 эта схема реализована для описания класса минимальных графов Кэли группы Ж?, являющихся предельными дчя класса графов минимальной валентности для вершинно-примитивных групп автоморфизмов НА-тшпа При <1 = 1, 2,3,5 я 6 этот класс состоит, соответственно, из 1,2,1, 2 и 7 графов (все они явно указаны) При ё. — 4 этот класс бесконечен, но допускает весьма прозрачное описание

5) Найдены все графы валентности не более 14, являющиеся предельными для класса графов минимальной валентности для вершинно-примитивных групп автоморфизмов НА-тяпа, (соответствующий список содержит 12 графов)

Публикации по теме диссертации

1 Костоусов, К В Графы Кэли группы и пределы вершинно-примитивных графов НА-тшпе, / К В Костоусов // Проблемы теоретической и прикладной математики Труды 36-й Региональной молодежной конференции Екатеринбург УрО РАН, 2005 - С 444Г

2 Костоусов, К В Графы Кэли группы и пределы минимальных вершинно-примитивных графов ЯЛ-типа / К В Костоусов //

Проблемы теоретической и прикладной математики Труды 37-й Региональной молодежной конференции Екатеринбург УрО РАН, 2006 -С 50-52

3 Костоусов, К В Графы Кэли группы Z4 и пределы минимальных вершинно-примитивных графов if ^4-типа / К В Костоусов / / Проблемы теоретической и прикладной математики Труды 38-й Региональной молодежной конференции Екатеринбург УрО РАН, 2007 -С 40-43

4 Костоусов, К В Графы Кэли группы Zd и пределы вершинно-примитивных графов НА-типа / К В Костоусов // Сиб мат журнал - 2007 - Т 48, №3 - С 606-620

5 Костоусов, К В О графах Кэли группы Z4, являющихся предельными для множества минимальных вершинно-примитивных графов НА-типа / К В Костоусов // Труды ИММ УрО РАН - 2007 - Т 13, М-С 132-147

6 Костоусов, К В Графы Кэли групп Z5 и Z6 и пределы вершинно-примитивных графов НА-тт& / К В Костоусов // Международная конференция "Алгебра и ее приложения" Тезисы докладов -Красноярск, 2007 - С 77-79

7 Kostousov, К V Caley graphs of groups ЪА and limits of vertex-primitive graphs of HA-type / К V Kostousov // Международная алгебраическая конференция к 100-летию со дня рождения П Г Кон-торовича и 70-летию JI Н Шеврина, Екатеринбург, 29 августа - 3 сентября 2005 г тез докл — Екатеринбург Изд-во Урал ун-та, 2005-С 88-89

Отпечатано в типографии ООО «Издательство УМЦ УПИ» 620078.. Екатеринбург, ул Гагарина, 35а, оф 2 Заказ $.050 Тираж 100 экз

Введение. Формулировки основных результатов

1 Графы Кэли групп Ъй и конечные группы целочисленных матриц

1.1 Критерий изоморфности графов Кэли групп I/1: доказательство теоремы 1.

1.2 Связь графов Кэли групп Ъй с конечными группами целочисленных матриц: доказательство теоремы 2. И

1.3 О пределах вершинно-примитивных графов НА-типа.

2 Реберно-транзитивные графы Кэли групп И1 и пределы графов, допускающих реберно-транзитивную вершинно-примитивную группу автоморфизмов ЯА-типа

2.1 Реберно-транзитивные графы Кэли группы Ъ и Ит(ТТ>е1^ап8): доказательство теоремы 3.

2.2 Реберно-транзитивные графы Кэли групп с? > 2, и Ит^Р^0™): доказательство теоремы 4.

3 Минимальные графы Кэли групп Ъл и пределы графов минимальной валентности для вершинно-примитивных групп НА-типа

3.1 Графы Кэли групп наименьшей валентности как пределы минимальных вершинно-примитивных графов ЯА-типа.

3.2 Минимальные графы Кэли группы Ъ2 и доказательство теоремы 5.

3.3 Минимальные графы Кэли группы 1} и Хш^ТТ1^1])'- доказательство теоремы 6.

3.4 Графы Кэли группы Zd, соответствующие орбитам конечной группы целочисленных матриц.

3.5 Алгоритмы, позволяющие находить минимальные графы Кэли групп 7/1, соответствующие орбитам фиксированной конечной группы целочисленных матриц.

3.6 Схема нахождения минимальных графов Кэли группы Zd при d >

4 Минимальные графы Кэли группы Z4 и пределы графов минимальной валентности для вершинно-примитивных групп НА-типа

4.1 Подгруппы бесконечного орбитного типа в GL^Z): доказательство теоремы 7.

4.2 Минимальные графы Кэли группы Z4 и доказательство теоремы 8.

Всюду ниже под графом понимается неориентированный граф без петель и кратных ребер. Множество вершин графа Г обозначается через У(Г), а множество ребер — через Е(Т). Под автоморфизмами графа Г понимаются подстановки на множестве К(Г), сохраняющие отношение смежности.

Граф называется вершинно-примитивным, если он допускает группу автоморфизмов, действующую примитивно на множестве его вершин. Класс конечных связных вершинно-примитивных графов будем обозначать через ТТ (здесь и всюду ниже под классом некоторых графов понимается множество изоморфных типов этих графов). Важный в комбинаторике и алгебре подкласс класса ТТ составляют графы, допускающие вершинно-примитивную реберно-транзитивную группу автоморфизмов. Этот класс обозначается через ЯРе-'Г£Ш5. Класс в свою очередь, имеет важный подкласс ТТ™п, состоящий из графов минимальной валентности для конечных вершинно-примитивных групп. Связный граф Г называется графом минимальной валентности для вершинно-примитивной группы автоморфизмов С?, если Г имеет наименьшую валентность среди всех связных графов А, таких что У(А) = У (Г) и (3 < Аи^Д). Каждая примитивная группа подстановок может быть реализована как группа автоморфизмов некоторого связного вершинно-примитивного графа. При этом вершинно-примитивные графы минимальной валентности для заданной примитивной группы доставляют наиболее естественные ее реализации в качестве группы автоморфизмов графа.

Для изучения класса ТТ в [5] и [8] был предложен подход, связанный с изучением предельных графов для класса ТТ. Если С — произвольный класс конечных связных вершинно-примитивных графов, то предельными для С называются бесконечные связные графы, у которых каждый шар изоморфен шару некоторого графа из С. Класс предельных для С графов обозначается через Нш(С). Описание Нш(С) доставляет описание типичного локального строения графов из С. Вопрос о строении графов из Хиа^ТТ) был поставлен В.И. Трофимовым в [2, вопрос 12.89]. В силу сказанного выше, также представляет интерес изучение строения графов из Х\т{ТТ>е~1гап8) и Нт(^Г7>тгп). Заметим, что, как показано в [8], строение графов из Х\т{РРе~1гап8) во многом определяет строение произвольных графов из \\т{ТР).

В [8] М. Гиудичи, Ч. Ли, Ч. Прэгер, А. Серешем и В.И. Трофимовым было начато систематическое изучение класса \[т(ТР). При этом была показана важность подклассов ТРна, РРаб, Р'Рра класса ТР, определяемых следующим образом. Пусть (7 — примитивная группа подстановок на конечном множестве V и V £ V. Группа С? называется примитивной группой НА-типа, если она содержит регулярную абелеву нормальную подгруппу. Группа (7 называется примитивной группой АБ-типа, если она почти проста, т.е. 1пп(Т) < б? < АиЬ(Т) для некоторой конечной неабелевой простой группы Т. Наконец, группа (7 называется примитивной группой РА-типа, если С имеет единственную минимальную нормальную подгруппу N = Тк, где Т — некоторая конечная неабелева простая группа, к > 2, и стабилизатор элемента г; в ./V проектируется на (нетривиальные) собственные подгруппы прямых простых факторов группы N. Для X 6 {НА, Ав, РА} через ТРх обозначается класс графов, допускающих вершинно-примитивную группу Х-типа, через ргре-и-апв обозначается подкласс класса ТРх, состоящий из графов, допускающих реберно-транзитивную вершинно-примитивную группу Х-типа, а через гртгп обознается подкласс класса ^гре-1гапз} состоящий из графов минимальной валентности для вершинно-примитивных групп Х-типа.

Из [8, теор. 1] следует, что

Х\т(ТР) = Х\т(ТРНА) и Нт(ЯРЛ5) и Пш{ТРРА), хш{ТТе-1гапз) = Ит{ТРенТП8) и Ит{ТРе^гапз) и Нт(ТРе^гапз),

Ит{ТР™п) = Нти Нт(ТР%п) и Нт(ТР^).

Поэтому представляющее самостоятельный интерес изучение классов Нт{ТРна), Нт{РРе^апз) и Нт{ТР^а) является вместе с тем необходимым этапом изучения классов Нт(ТР), \\т(ТРе~1гап$) и Нт(ТРтЫ).

Пусть В — конечнопорожденпая абелева группа и М — конечная система порождающих группы В такая, что М = —М и 0 £ М. Графом Кэли группы В, соответствующим системе порождающих М, называется граф Тв,м с множеством вершин У(Гв,м) = В и множеством ребер Е(Тв,м) = {{а>^} : а-ЬеМ}.

Пусть й — положительное целое и Аи^Г^д^о — стабилизатор вершины 0 в группе автоморфизмов графа Кэли группы Ъй, соответствующего системе порождающих М. Граф Г^м назовем минимальным графом Кэли группы I/1, если множество М является Аи^Г^д^о-орбитой наименьшей мощности на Zíг\ {0}. Класс всех графов Кэли группы обозначим через Сау^), подкласс всех реберно-транзитивных графов класса Сау(2^) обозначим через Сауе~*гаТ15(2^), а подкласс всех минимальных графов Кэли группы Ъл класса Сауе~*гапв(2!1) обозначим через Сау™п(^).

По [8, теор. 2] каждый граф из Нт{ТТна) лежит в Сау^) для некоторого (1. При этом, поскольку каждый предельный граф для класса реберно-транзитивных графов является реберно-транзитивным (см. [8]), то каждый граф из 1\т(ТТе£дап8) лежит в С&уе~*гапа(%*) для некоторого А. Кроме того, из [8, теор. 2] и определения предельного графа следует, что каждый граф из лежит в Саутт(2^) для некоторого д. В связи с этим актуальными являются следующие две задачи, рассмотрению которых посвящена настоящая диссертация.

1) Исследовать Сауе-<гопв(йй) ПНт(^Ре£^гапз) для фиксированных значений д.

2) Исследовать Саутт(2^) П Нт(ТТ™/) для фиксированных значений <1.

Заметим, что описание графов из С&уе~1тт8 (Ъл) Г) Нт(ЯР^гапз) (соответственно из Саутш^) ПНт^Рял) ) Для всех ^ не превосходящих некоторого положительного целого числа п, доставляет, в частности, описание класса всех графов валентности, не превосходящей 2п + 2, лежащих в Нт(3:Т>е£дап8) (соответственно в Нт^^ял))■ Иллюстрацией этого замечания служит следствие 1 (см. ниже).

Реализуемый в диссертации подход к исследованию задачам 1) и 2) опирается на теоремы 1 и 2 из главы 1.

Теорема 1 доставляет эффективный метод проверки изоморфности графов Кэли групп Прежде, чем ее сформулировать, естественным образом отождествим группу Ъл с множеством целочисленных вектор-строк длины й с операцией покоординатного сложения и через СЬ^(й) обозначим группу целочисленных й х ¿-матриц с определителями ±1.

Теорема 1. Пусть Мг- — конечная система порождающих группы такая что 0 0 М{ и = -Мг, для ¿ = 1,2. Тогда a) Графы Кэли и Гй<г2,м2 изоморфны тогда и только тогда, когда ¿2 и М2 = М\а для некоторой матрицы а £ СЬ^ (Ж). b) Каждый изоморфизм графа Г^ М1 на граф м2 задается формулой х 1-+ ха + у, х 6 , для подходящих а € СЬ^(Й), у £ Zdl.

В теореме 2 устанавливается связь реберно-транзитивных и минимальных графов Кэли группы Ъ3, с конечными подгруппами группы СЬ^(Й). Перед ее формулировкой введем следующие определения.

Пусть <0^ — ¿-мерное векторное пространство над полем (О?, элементами которого являются рациональные вектор-строки длины Для г 6 {1,., й] через еф- обозначим вектор-строку длины с?, у которой на г-м месте стоит 1, а на остальных — 0. Всюду далее вместо е^ будем писать е^, опуская первый индекс (он всегда может быть восстановлен из контекста). Для М С <0? через (М)+ будем обозначать подгруппу аддитивной группы векторов пространства О1, порожденную множеством М, а через (М)о, будем обозначать подпространство векторного пространства на О6', натянутое на М. Через СЬ^А])) обозначим группу невырожденных й х «¿-матриц над <0>, а через Е^ — единичную с1х(1 матрицу.

Для конечной подгруппы й группы вЬ^Й) определим число т(в) := : а; £ \ {0}}, множества

Мъ(в) := {хв : ж € Ъй \ {0}, \хв\ = т(в),хО = -хв, {хС)+ = Ъй},

Мъ{С) := {хв : ж е О* \ {0}, \хв\ = т(С), = -хв, dim({жG>Q) = и классы графов

0де~1гапз(0) := {Т{х0)+,хС : * е 0й \ {0},хО= -хО, ¿\т((хС)®) = с*}, 0дт1п(0) := {Г(М)+)М : М €

Теорема 2. Пусть Сп,.,^ — все с точностью до сопряжения в С1^((0>) конечные подгруппы группы (^¿{Щ, содержащие —Е^. Тогда класс Сауе~*гап8(йсг) (соответственно класс Саутт(^) ) совпадает с классом иг€{1,.,п} Оде-*гапз(С{) (соответственно с классом Ц6{1,.,п} О0™п(О{) ).

В силу теоремы 2 для явного описания классов Сау6'1™™ (I/1) и Саутт(й<г) требуется выбрать представителей различных изоморфных типов графов из Цб{1,.,п}Ове~1гаП$(СЛ и Це{1 соответственно. Для этого используется, в частности, теорема 1.

Глава 2 диссертации посвящена изучению классов Сау6-*74""(ЪЛ) П

И т(ТТенАаПЗ) ПРИ ^ > 1.

Описание класса Сауе~*гатгг!(й) Г) Нт^Т^™"*) (а, вместе с тем, и класса Сау™п(й) П Нш(ТТн1а) ) Дает следующая теорема.

Теорема 3. Классы Съуе~1гапз{Ъ) П \\т{РГе£%апз) и Саутг'п(^ П Ит(ЯР^) совпадают и содержат единственный граф Г^!,-!}.

При й > 2 получен следующий результат о строении класса С&уе~1гапв {7$) П

Мт(ТТенАапВ)

Теорема 4. Класс Сще~1гаП8(Ъ6-) П Ит(РТенАаП8) бесконечен для каждого д>2.

При доказательстве теоремы 4 для каждого d > 2 явным образом строится счетное множество попарно не изоморфных графов Кэли группы Zd, лежащих в lim

Главы 3-6 диссертации посвящены изучению классов Caymm(Zd) П \im(J7'P1jjA) ПРИ d>2 на основе теорем 1 и 2.

В главе 3 получены следующие описания классов Caymm(Z2) П Нш^'РяХ) и Cay™'n(Z3)nlim(^?S).

Теорема 5. Cay™n(Z2) = {Гадд, Гад,Л С М2Д = еь е2}, М2)2 = ±{ei, е2, е\ + е2}.

Теорема 6. Caymi"(Z3) = С Um(^PSj), где Мзд - ±{ei,e2,e3}.

Использование теорем 1 и 2 для описания класса Caymw(Zd) П при d > 4 требует больших вычислений. В связи с этим в главе 3 описана схема нахождения минимальных графов Кэли группы Zd с использованием системы GAP [12].

Как видно из теорем 3, 5 и 6, класс Caymm(Zd) П lim{TV^D конечен при d < 3. Однако, как вытекает из следующей теоремы 7, доказываемой в главе 4, для d = 4 это уже не так. Для ее формулировки нам понадобится следующее определение, естественно возникающее в связи с теоремой 2.

Будем говорить, что конечная группа G Е GL^(Z) имеет бесконечный орбит-ный тип, если класс OQmm{G) бесконечен. В противном случае будем говорить, что группа G имеет конечный орбитный тип. Из определения легко следует, что свойство конечной группы из GL^(Z) иметь бесконечный орбитный тип инвариантно при сопряжении в GL^(Q).

Теорема 7. С точностью до сопряжения в GL^Q) подгруппы бесконечного орбитпого типа группы GL^Z) исчерпываются группами Gi = (/ii,/^), G2 = (/ь/2,/з>,£з = (<?2,/4>, где

0 0 -1 -п /0 -1 -1 -1)

0 -1 -1 -1 h2 = 0 -1 0 -1

0 0 0 -1 1 -1 -1 0

-1 1 1 1 У \о 1 0 0 )

-1 1 1 0 \ / 0 -1 0 -1\

-1 0 0 -1 /2 = 1 -1 -1 -1

-1 1 1 1 -1 0 0 -1

1 0 -1 0 J V 0 1 1 1 /

-1 0 1 0 \ ( 0 0 0 \

0 0 1 1 , /4 = -1 1 0 0

-1 0 0 0 -1 0 1 0

1 -1 -1 -1 / V 1 -1 -1 -1 /

С?1 ^ йз X 28, G2^¿Q8X Ъъ, Сз = X 22).

Описание класса Саутт(24) П Ит(ТТнг2) Дает следующая теорема, доказательство которой приводится в главе 4.

Теорема 8. Минимальные графы Кэли группы Ъ4- с точностью до изоморфизма исчерпываются графами Кэли группы 1}, соответствующими следующим системам порождающих: М4Д = ±{е1,е2,е3,е4}, М4)2 = ±{еь е3, е4, е\ + е2, е2 + е3 + е4}, М4)3 = ±{е1, е2, ез, е4, ех - е2, е3 - е4}, элементам из 1) (все они порядка 24).

Бее минимальные графы Кэли группы лежат в Ит(ТТн12).

В главах 5 и 6 получены, соответственно, следующие описания классов Саутг'"(25) П и Саутг'"(26) П

Теорема 9. Саутг>г(25) - {Г^д, Г^Л С где

М5)2 = Мх и ±{б! + е2 + е3 - е4 - е5}.

Теорема 10. Сау™п{Ъ6) = : % е {1,., 7}} С где

М6Д = ±{ег-:ге{1,.,6}},

М6,2 = ±{еь е2, ез, е6, ех - е4, е2 - е5, е3 - е4 + е5 - е6}, М6Д и ±{ех - е2, е3 - е4, е5 - еб}, Мед = М6д и ±{ех - е2 + е4, ех - е3 + е5, е2 - е3 + е6, е4 - е5 + еб}, Мз,5 = (б1 - 63)^1 порядка 36, -ОДз.б = порядка 42, Мб,7 = порядка 54; где

1 0 1 1 1 -1\ ( 0 0 0 -1 0 -1 \

1 0 0 1 1 0 0 1 1 0 0 -1

0 1 1 0 0 -1 -1 0 0 0 0 0

-1 0 0 0 -1 1 7 1 -1 -1 0 0 0

0 0 0 0 1 0 -1 1 0 0 -1 1

V 1 0 1 0 1 -1/ V-! 1 0 0 0 0 /

О 1

1 о о о

О 1 о о \1 о о 0

1 -1 о -1 о о о о о о о о 0

1 о о о о -1 о о

О 1 о о

0 о

1 о о о

1 о о о

0 о

1 1 -1 -1 О -1 -1 -1 о о о о о -1 о\ 1 о 0

1 1/

0 0 1 0 0 0 \ /1 -1 -1 -1 0 0\

1 0 1 0 1 -1 0 0 -1 -1 -1 0

-1 1 1 1 0 0 0 -1 0 -1 0 0

0 0 - -1 0 -1 1 > 0 0 0 1 1 0

0 0 0 0 1 0 0 0 0 0 -1 0

V -1 1 1 0 0 0 \0 -1 -1 -1 -1 1/

0 1 1 1 1 0 \

0 0 1 1 1 0

0 0 -1 0 0 1 \

0 0 0 1 -1 0

1 -1 0 0 1 -1

1 0 0 1 1 0

Полученные результаты о строении класса Саутш(Ж^)ПНт(^Р^) при ¿<6 дают следующее описание графов малой валентности из

Следствие 1. Следующий список содержит все графы из Ххт^ТТ^д), валентность которых не превосходит 14;

1) Г2,{ 1,-1} валентности 2,

2) Г22,±{еье2} валентности 4,

3) Гга,±{в1)е2,е1+е2} валентности 6,

4) ^ъ\±{еие2,ег} валентности 6,

5) Г%*,±{е1,е2,е3,е*} валентности 8,

6) Г24)±{еье3;е4)е1+е2)е2+ез+е4} валентности 10,

7) гж^±{е1,е2,е31е4,е4} валентности 10,

8) Гг«>±{е1,е2,ез,е41е1-е!1)ез-е4} валентности 12,

9) Гг» ,±{еье2,ез,е4,е5,е1+е2+ез-е4-е5} валентности 12, ю) г2. ,±{б1 ,е2,ез,е4,е5,е6} валентности 12,

11) Гр ,±{е1,е2,ез,е6,е1-е4,е2-е5,ез-е4+е5-е6} валентности 14,

12) Г2т ,±{е1,е2,ез,е4,е8>ев,е7} валентности 14.

1. Жидков, Н.П. Геометрия кристаллического пространства / Н.П. Жидков, Б.М. Щедрин // М.: изд-во Моск. Ун-та, 1988.

2. Коуровская тетрадь. Нерешенные вопросы теории групп. Новосибирск: Но-восиб. гос. ун-т., 2002.

3. Рейнгольд, Э. Комбинаторные алгоритмы. Теория и практика / Э. Рейнгольд, Ю. Нивергельт, Н. Део // М.: Мир, 1980.

4. Трофимов, В.И. Ограниченные автоморфизмы графов и одна характери-зация решеток / В.И. Трофимов // Изв. АН СССР. Сер. матем. 1983. Т. 47. т. С. 407-420.

5. Трофимов, В.И. О действии примитивных групп / В.И. Трофимов // Алг. и лог. 1989. Т. 28. №3. С. 337-369.

6. Bass, Н. The degree of polynomial growth of finitely generated nilpotent groups / H. Bass // Proc. London Math. Soc. 1972. V. 25. P. 603-614.

7. Brown, H. Crystallographic Groups of Four-Dimensional Space / H. Brown, H. Bulow, J. Neubuser, H. Wondratschek, H. Zassenhaus // New York: John Wiley, 1978.

8. Giudici, M. On limit graphs of finite vertex-primitive graphs / M. Giudici, C.H. Li, C.E. Praeger, A. Seress, V. Trofimov //J. Comb. Theory. Ser. A. 2007. V. 114. P. 110-134.

9. Opgenorth, J. Crystallographic Algorithms and Tables. / J. Opgenorth, W. Plesken, T. Schultz // Acta Cryst A. 1998. V. 54. P. 517-531.

10. Plesken, W. Counting crystallographic groups in low dimensions / W. Plesken, T. Schulz // Experimental Mathematics. 2000. V. 9. P. 407-411.

11. CARAT — Crystallographic AlgoRithms And Tables. Version 2.0 (http://wwwb.math.rwth-aachen.de/carat/).

12. The GAP Group. GAP — Groups, Algorithms, and Programming, Version 4.4, Aachen, St Andrews, 2004 (http://www.gap-system.org).

13. Maple — comprehensive computer system for advanced mathematics, Version 8 (http://www.maplesoft.com).Работы автора по теме диссертации

14. Костоусов, К.В. Графы Кэли группы Zd и пределы вершинно-примитивных графов ЯА-типа / К.В. Костоусов // Проблемы теоретической и прикладной математики. Труды 36-й региональной молодежной конференции. Екатеринбург, УрО РАН. 2005. С. 44-46.

15. Костоусов, К.В. Графы Кэли группы Zd и пределы минимальных вершинно-примитивных графов ЯА-типа / К.В. Костоусов // Проблемы теоретической и прикладной математики. Труды 37-й региональной молодежной конференции. Екатеринбург, УрО РАН. 2006. С. 50-52.

16. Костоусов, К.В. Графы Кэли группы Z4 и пределы минимальных вершинно-примитивных графов ЯА-типа / К.В. Костоусов // Проблемы теоретической и прикладной математики. Труды 38-й региональной молодежной конференции. Екатеринбург, УрО РАН. 2007. С. 40-43.

17. Костоусов, К.В. Графы Кэли группы 7Ld и пределы вершинно-примитивных графов ЯА-типа / К.В. Костоусов // Сиб. мат. журнал. 2007. Т. 48. №3. С. 606-620.

18. Костоусов, К.В. Графы Кэли группы Z4 и пределы минимальных вершинно-примитивных графов ЯА-типа / К.В. Костоусов // Алгебра и логика (в печати).

19. Костоусов, К.В. О графах Кэли группы Z4, являющихся предельными для множества минимальных вершинно-примитивных графов ЯА-типа / К.В. Костоусов // Труды ИММ УрО РАН. 2007. Т. 13. №1. С. 132-147.

20. Костоусов, К.В. Графы Кэли групп Z5 и Z6 и пределы вершинно-примитивных графов ЯА-типа / К.В. Костоусов // Международная конференция "Алгебра и ее приложения": Тезисы докладов. Красноярск. 2007. С. 77-79.