Симметрические расширения графов тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

005016189

На правах рукописи УДК 512.54+519.17

НЕГАНОВА ЕЛЕНА АЛЕКСАНДРОВНА

СИММЕТРИЧЕСКИЕ РАСШИРЕНИЯ ГРАФОВ

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

АВТОРЕФЕРАТ

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

Г* Г ч ' г- Г

СI ¿и

Екатеринбург - 2012

'Ч

005016189

Работа выполнена в отделе алгебры и топологии Федерального государственного бюджетного учреждения науки Института математики и механики Уральского отделения Российской академии наук.

Научный руководитель:

доктор физико-математических наук Владимир Иванович Трофимов

Официальные оппоненты:

доктор физико-математических наук, профессор Виссарион Викторович Беляев

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

Ведущая организация:

Челябинский государственный университет

Защита состоится 22 мая 2012 г. в 12 ч. 00 м. на заседании диссертационного совета Д 004.006.03 в Институте математики и механики УрО РАН по адресу: 620990, г. Екатеринбург, ул. С. Ковалевской, д. 16.

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

Автореферат разослан 20 апреля 2012 г.

Ученый секретарь диссертационного совета

Д 004.006.03, кандидат физ.-мат. наук

И.Н. Белоусов

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

Актуальность темы. Диссертационная работа посвящена изучению симметрических расширений графов. Пусть Г и Д — графы (под графом здесь и далее понимается неориентированный граф без петель и без кратных ребер). В соответствии с [1] связный граф Г называется симметрическим расширением графа Г посредством графа Д, если существуют такая вершинно-транзитивная группа (^автоморфизмов графа Г и такая система импримитивности а группы в на множестве У (Г) вершин графа Г, что фактор-граф Г/ст изоморфен графу Г и блоки системы а порождают в Г подграфы, изоморфные графу Д. Ясно, что симметрическое расширение графа Г посредством графа Д существует лишь для Г и Д, допускающих вершинно-транзитивные группы автоморфизмов, причем граф Г должен быть связным. Если в приведенном выше определении симметрического расширения графа Г посредством графа Д отказаться от условия связности графа Г, то получим определение обобщенного симметрического расширения графа Г посредством графа Д. Бели при этом р — изоморфизм графа Т/а на граф Г, то будем говорить, что Г — обобщенное симметрическое расширение графа Г посредством графа Д, реализуемое С, а Ч>-

Симметрические расширения графов представляют интерес в силу целого ряда причин (см. ниже). При этом часто бывает важно, чтобы (в приводимом выше определении симметрического расширения Г посредством Д) при изоморфизме Т/а на Г индуцируемая <3 группа С автоморфизмов графа Т/сг переходила в некоторую заданную группу автоморфизмов <3 графа Г. В связи с этим вводится следующее определение (см. [1]). Для графов Г, Д и вершинно-транзитивной группы автоморфизмов <3 графа Г связный граф Г называется <3-симметрическим расширением графа Г посредством графа Д, если граф Г является симметрическим расширением графа Г посредством графа Д, реализуемым такими (3, £, ¡р, что рСу?'1 = С. Бели в этом определении отказаться от условия связности графа Г, то получим определение обобщенного (3-симметрического расширения графа Г посредством графа Д (реализуемого в, а, 1р).

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

1) Понятие симметрического расширения одного графа посредством другого графа аналогично хорошо известному понятию расширения одной группы посредством другой группы. Связь между расширениями групп и симметрическими расширениями графов можно__формаяизовать следующим образом. Пусть С — группа с системой порождающих М такой, что 1 £ М = А/-1, N — нормальная подгруппа группы <3, (3 = <3/ЛГ и М = {дЫ : з^е М\ Щ. Тогда граф Кэли Г5д группы 5, построенный по системе порождающих М, является (З-симметрическим расширением графа Кэли Га,м группы построенного по системе порождающих М, на котором <3 действует естественным oбpaзoмj посредством графа Кэли группы N, построенного по множеству МпИ.Ъ связи с этим изучение симметрических расширений графов представляет интерес для теории групп.

2) Ряд известных конструкций теории графов, если их применить к вершинно-симмет-рическим (т.е. допускающих транзитивные на вершинах группы автоморфизмов) графам Г и Д, приводят к симметрическим расширениям Г посредством Д. Такими конструкциями являются, например, декартово, прямое, лексикографическое и некоторые другие про-

изведения (см. [2]). К симметрическим расширениям графов приводит также следующая известная конструкция. Если Г — связный граф, допускающий вершинпо-транзитивную группу автоморфизмов й, и если ф : 1Л(Г) —> У'(Г) — накрывающее отображение связного графа Г на граф Г такое, что соответствующая этому отображению накрывающая группа в := {д Е АЫ(Т) : фд е в-ф} группы в вершинно-транзитивна, то множество слоев а := : х € У'(Г)} есть система импримитивности <3 и ф индуцирует изоморфизм

¡р графа Т/а на Г такой, что 1рСц>~1 — вершинно-транзитивная подгруппа группы (?. Следовательно, Г является ^С^^-симметрическим расширением Г посредством Д, где Д — подграф графа Г, порожденный некоторым слоем из а.

3) Для ряда важных классов связных бесконечных локально конечных вершинно-сим-метрических графов были получены описания, имеющие, по существу, следующий вид: графы из рассматриваемого класса являются в точности С-симметрическими расширениями некоторых известных графов Г посредством конечных графов, где С — некоторые заданные группы автоморфизмов графов Г. Такого вида описания были получены, например, для графов с полиномиальным ростом (см. [3]), для графов с рекуррентным случайным блужданием (см. [4]) и для графов с вершинно-транзитивной группой ограниченных автоморфизмов (см. [5]). Изучение таких (^-симметрических расширений графов Г посредством конечных графов является, следовательно, более детальным исследованием этих классов. Определенный интерес представляет в связи с этим изучение симметрических расширений бесконечных локально конечных графов посредством конечных графов.

4) Если Г — симметрическое расширение графа Г посредством графа Д, то граф Г можно интерпретировать "кристаллографически" как граф Г, у которого вершины наделены внутренней структурой вида Д (такие наделенные внутренней структурой вершины графа Г выступают как "молекулы" вида Д), причем эти внутренние структуры вершин графа Г согласуются со структурой Г так, что вся получающаяся в результате конструкция Г симметрична (в том смысле, что граф Г допускает вершинно-транзитивную группу автоморфизмов, отображающую "молекулы" на "молекулы"). В связи с этим симметрические расширения ¿-мерных решеток кл посредством конечных графов могут представлять интерес для "молекулярной" кристаллографии.

5) В некоторых физических теориях (см., например [6]) пространство-время наряду с й "обычными размерностями" имеет несколько "компактифицированных размерностей". В качестве трансляционно-однородных дискретных аппроксимаций такого пространства-времени могут выступать Л-ц4о(А<г)-симметрические расширения ¿-мерной решетки Ай посредством конечных графов, где ЛЫ^Л?) — группа всех сдвигов, т.е. "параллельных переносов", решетки (Под трансляционной однородностью здесь понимается возможность перемещения любой вершины в любую другую вершину автоморфизмом, индуцирующим сдвиг кй, т.е. трансляцию на "обычных размерностях" пространства-времени.) В связи с этим представляют интерес Ли<о(Л.<г)-симметрические расширения ¿-мерных решеток Кл посредством конечных графов.

Таким образом, исследование симметрических расширений локально конечных графов посредством конечных графов и, в особенности, симметрических и -симметричес-

ких расширений ¿-мерных решеток посредством конечных графов актуально и представляет значительный интерес. Принципиальным вопросом при исследовании симметрических расширений локально конечного графа Г посредством конечного графа Д (или С-симметрических расширений Г посредством Д для заданной вершинно-транзитивной группы автоморфизмов в графа Г) является вопрос о конечности их числа.

Цель работы.

1. Построение примеров локально конечных графов, допускающих бесконечное число симметрических расширений посредством конечного графа.

2. Исследование вопроса о конечности числа симметрических и Аи^Л^-симметричес-ких расширений d-мерной решетки kd посредством конечного графа.

3. Построение всех Autç(Л^)-симметрических расширений d-мерной решетки kd посредством конечного графа Д для некоторых представляющих интерес ¿и Д.

Методы исследований. Основными методами исследования являются методы теории групп и теории графов.

Научная новизна. Все основные результаты диссертации являются новыми.

Теоретическая и практическая ценность. Работа носит теоретический характер. Ее результаты могут быть использованы в теории групп и теории графов. Кроме того, результаты работы могут найти применения в кристаллографии и физике.

Апробация работы. Результаты диссертации докладывались на Международной конференции, посвященной 70-летию академика Ю.Л. Ершова (Новосибирск, 2010 г.), на Международной алгебраической конференции, посвященной 70-летию A.B. Яковлева (Санкт-Петербург, 2010 г.), на Международной конференции по алгебре и геометрии, посвященной 80-летию со дня рождения А.И. Старостина (Екатеринбург, 2011 г.), на семинаре "Mathematics for structured matter: insights from graph theory and group theory" (Max Planck Institute for Chemical Physics of Solids, Dresden, Germany), на 41-й и 42-й Всероссийских молодежных школах-конференциях ИММ УрО РАН (Екатеринбург, 2010, 2011 гг.), на Международной (43-й Всероссийской) молодежной школе-конференции ИММ УрО РАН (Екатеринбург, 2012 г.). Результаты работы докладывались на алгебраическом семинаре ИММ УрО РАН. Исследования соискателя по теме диссертационной работы были поддержаны грантом РФФИ, проект № 10-01-00349, и грантом УрО РАН для молодых ученых за 2012 г., проект № A3.

Публикации. Результаты диссертации опубликованы в 3 статьях (в изданиях из списка, рекомендованного ВАК) и 7 тезисах докладов. Из них 1 статья и 1 тезисы написаны без соавторов, остальные — в нераздельном соавторстве с В.И. Трофимовым.

Структура и объем работы. Диссертационная работа состоит из введения, 4 глав и списка литературы, содержащего 20 названий. Общий объем диссертации составляет 113 страниц.

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

Во введении приводятся мотивировки рассматриваемых в диссертационной работе вопросов, и дается обзор основных полученных в ней результатов. Кроме того, во введении приводятся основные используемые в работе определения и обозначения. Помимо данных выше, в работе используются следующие определения. Для произвольного целого положительного числа q связный граф Г называется симметрическим q-расширением графа Г (соответственно, G-симметрическим q-pacuiupenu-ем графа Г, где G — группа автоморфизмов графа Г), если существуют такая вершинно-

транзитивная группа в автоморфизмов графа Г и такая система импримитивности а группы С на К(Г) с блоками порядка д, что найдется изоморфизм <р графа Г/ст на граф Г (соответственно, найдется изоморфизм ¡р графа Г/сг на граф Г, для которого ¡¿зС^-1 = (?)• При этом говорят, что Г — симметрическое (соответственно, (?-симметрическое) д-расншрение графа Г, реализуемое (3, а, <р. Если в приведенном выше определении симметрического (соответственно, (7-симметрического) д-расширения графа Г отказаться от условия связности графа Г, то получим определение обобщенного симметрического (соответственно, (?-симметрического) д-расширения графа Г (реализуемого С?, сг, <р).

Если в данном выше определении симметрического (соответственно, С-симметричес-кого) д-расширения графа Г потребовать, чтобы и можно было выбрать со следующим дополнительным свойством: для произвольной вершины х графа Г каждый блок системы импримитивности сг, смежный в графе Г/сг с х", содержит в точности одну смежную с х вершину, то получим определение накрывающего симметрического (соответственно, накрывающего С-симметрического, где в — группа автоморфизмов графа Г) д-расширения графа Г. Если же вместо этого потребовать, чтобы а можно было выбрать со следующим более слабым свойством: каждая вершина х графа Г смежна не более, чем с одной вершиной из произвольного не содержащего х блока системы импримитивности сг, то получим определение неразветвленного симметрического (соответственно, неразветвленного в-симметрического, где й — группа автоморфизмов графа Г) д-расширения графа Г. (В дальнейшем, когда говорится, что накрывающее (соответственно, неразветвленное) симметрическое (соответственно, С-симметрическое) д-расширение графа Г реализуется б, (7, ¡р, то подразумевается, что сг обладает указанным дополнительным свойством.)

Под ¿-мерной решеткой Кл, где (I — целое положительное число, понимается граф, вершинами которого являются все упорядоченные наборы (01,..., си) из с1 целых чисел, и две вершины (а'5,..., а'й) а (а",..., а^) смежны тогда и только тогда, когда

Для ¡¿-мерной решетки Л^ и 1 < 3 < /1 мы полагаем Р^ : ^Л^) —» Ъ, Рг_Д(сц,о2,.. •,о^)) = а3.

Сдвигом решетки Аа называется ее автоморфизм, который переводит произвольную вершину (а:,..., а^) в вершину (аг + кх,..., ал + к^) для некоторых фиксированных целых чисел ¿1,..., к^. Для каждого 1 < г < <2 через и обозначается сдвиг решетки Кл, для которого к{ = 1 и к^ = 0 для всех 3 € {1,..., й}\{г}. Через Аи1 о(Ла) обозначается подгруппа группы автоморфизмов решетки состоящая из всех ее сдвигов.

Если Г — обобщенное симметрическое д-расширение решетки Л"* (где (¿ид — целые положительные числа), реализуемое некоторыми С, а, ¡р, то для каждого 1 < г < <£ число «¡(Г, в, сг, ¡р) определяется как наименьшее из целых положительных чисел 5 со свойством 1° € ¡рСЗ"1^'1 (легко показать, что такое в^Г, (3, сг, ¡р) существует и не превосходит 2Й(/!). Заметим, что если Г — обобщенное у1и^(Л'г)-симметрическое д-расширение решетки реализуемое (3, сг, <р, то «1(Г, й,а,!р) = ... = ¿¿(Г, в, сг, ¡р) = 1.

Напомним, что для произвольнох'о связного графа Е через АиЬо(^) обозначается группа всех его ограниченных автоморфизмов, т. е. таких автоморфизмов д, что расстояния в графе Е между х и д(х), где х пробегает множество всех вершин графа Е, ограничены в совокупности. (Введенное выше обозначение /1ийо(Лс') согласуется с этим определением.) Согласно [5, следствие 2(1)] для связного локально конечного графа Е множество

Т(Ли/0(2)) всех его ограниченных автоморфизмов конечного порядка является (нормальной) подгруппой группы ЛиЦТ,).

Как показано в [1], если Г — Лг/г0(Л'г)-симметрическое д-расширение решетки Л? для некоторых целых положительных чисел А и д, реализуемое О, и, <р, то блоки а являются У(Ли40(Г))-орбитами на У(Г) (и, следовательно, а однозначно определена), а Г является .4и40(Л<г)-симметрическим ^-расширением решетки реализуемым АЫ0(Г), а, ¡р. В связи с этим разбиение а множества К(Г), состоящее из Г(Ли<0(Г))-орбит на У(Г), называется соответствующей Г (как АиЬ0 (Л^-симметрическому д-расширению решетки Л*) системой блоков.

В главе 1 доказывается существование связного локально конечного графа Г и конечного графа А таких, что имеется бесконечное число симметрических расширений Г посредством Д. Более того, в главе 1 строится весьма широкий класс локально конечных графов Г, имеющих бесконечное число накрывающих симметрических расширений посредством одного и того же конечного графа Д. Эта глава состоит из двух параграфов.

В параграфе 1.1 доказывается следующая теорема.

Теорема 1.1.1. Пусть А — группа с системой порождающих {а^1,... где

(1 — целое положительное число, и В — центральная подгруппа группы А. Предположим, что выполняются следующие условия:

1) ака^ £ В для всех 1 < к < д, I < I < й, к ф I, и ака1 $ В для всех 1 < к < й 1 <1<Л;

2) В — свободная абелева группа счетного ранга;

3) порядки всех конечных подгрупп группы А/В не превосходят некоторого целого положительного числа г.

Тогда граф Кэли Гв.м группы С? = А/В, построенный по системе порождающих М = имеет для каждого целого положительного числа д бесконечное число накрывающих в-симметрических (для естественного действия С на Тс,м) д-расшире-ний.

В параграфе 1.2 с использованием результатов комбинаторной теории групп показывается, что группа л и ее центральная подгруппа В с требуемыми в теореме 1.1.1 свойствами могут быть выбраны так, что А/В изоморфна произвольной свободной разрешимой группе ступени разрешимости п > 1 с А > 1 свободными порождающими (пример 1.2.1; используется [7, теорема Л]) или изоморфна определенного вида периодической группе и даже группе, все собственные подгруппы которой имеют фиксированный простой порядок (пример 1.2.2; используется [8, параграфы 25, 27, 29, 31]).

Глава 2 посвящена рассмотрению вопроса о конечности числа симметрических и Ли^Л^-симметрических д-расширений ¡¿-мерной решетки М1. Она состоит из трех параграфов.

В параграфах 2.1 и 2.2 наш подход к исследованию вопроса о конечности числа симметрических и Ли^Л^-симметрических д-расширений ¿-мерной решетки Л4 основывается на проверке выполнения для них следующего условия [щ,..., "¿¡-периодичности. Пусть Г — обобщенное симметрическое д-расширение решетки Лй, где д и д — целые положительные числа, реализуемое О, а, ¡р. Скажем, что (Г, а, кр) удовлетворяет условию [щ,..., па}-периодичности, где щ,..., т — целые положительные числа, если существуют такие <?1,... ,дл е Лг4(Г), сохраняющие разбиение <т, что [д;,®] = 1 дая всех 1 < г < ] < А и <рд?ч>~1 — для всех 1 < г < А

Как показывает следующий результат, для доказательства конечности какого-либо множества симметрических g-расширешш решетки Ad достаточно доказать, что каждое Г из этого множества может быть реализовано такими G, а, <р, что (Г, a, ip) удовлетворяет условию [rai,..., ^¡-периодичности для некоторых фиксированных целых положительных чисел П\,... ,nj..

Теорема 2.1.1. Для произвольных целых положительных чисел d, q, ni,... ,rtd > 1 существует лишь конечное число графов Г, являющихся обобщенными силшетрическими q-расширениями решетки Ad, реализуемыми такшш G, a, tp, что (Г, а. <р) удовлетворяет условию [ni,..., щ]-периодичности.

Теорема 2.1.1 используется в параграфах 2.1 и 2.2 для доказательства конечности числа (обобщенных) симметрических и Аи^Л^-симметрических g-раеширений решетки Ad в ряде представляющих интерес случаев (см. следствия 2.1.2, 2.1.3, 2.2.1, 2.2.2 ниже). Для доказательства этих последних результатов помимо теоремы 2.1.1 используется следующая теорема.

Теорема 2.1.2. Пусть Г — обобщенное симметрическое q-расширение решетки Ad для некоторых целых положительных чисел dug, реализуелюе G, а, ¡р. Предположим, что группа G имеет конечный стабилизатор Gx вершины х графа Г. Тогда (Г, a, ip) удовлетворяет условию [щ,... ^¿¡-периодичности, где щ < Si(I\G, а, :p){q\Gx\Y~'i 5; 2dd\(q\Gx\)i~x для всех 1 < г < d.

Следующие утверждения вытекают из теорем 2.1.1 и 2.1.2.

Следствие 2.1.2. Для произвольных целых положительных чисел d, q и т имеется лишь конечное число обобщенных симметрических q-расширений решетки Ad, которые могут быть реализованы такими G, a, tp, что порядок стабилизатора вершины в группе G не превосходит т.

Следствие 2.1.3. Пусть Г — неразветвленное симметрическое q-расширение решетки Ad для некоторых целых положительных чисел d и q, реализуемое G, су, ip. Тогда (Г,сг, ip) удовлетворяет условию [щ,... ^¿¡-периодичности, где П; < (2dd\)'q'~1 для всех 1 < i < d. В частности, для произвольных целых положительных чисел d и q имеется лишь конечное число неразветвленных симметрических q-расширений решетки Ad.

Основным результатом параграфа 2.2 является доказательство конечности числа Auto(Ad)-cHMMeTpii4ecKHx g-расширений решетки Ad для произвольного целого положительного числа d и произвольного простого числа q (см. следствие 2.2.2 ниже; остается, однако, открытым вопрос о конечности числа -Ди^Л^-симметрических q-расширений решетки Ad для произвольных целых положительных чисел ¿ид). Этот результат получается из следующей теоремы 2.2.1 (доказательство которой основывается на теореме 2.1.2) с использованием теоремы 2.1.1. Напомним, что группа подстановок называется квазипримитивной, если каждая ее неединичная нормальная подгруппа транзитивна.

Теорема 2.2.1. Пусть Г — Auto(Ad)-симметрическое q-расширение решетки Ad для некоторых целых положительных чисел d и q, реализуемое G, a, ip, причем стабилизатор в G блока из а индуцирует на этом блоке квазипримитивную группу. Тогда (Г, сг, ¡р) удовлетворяет условию [щ,..., п^-периодичности, где щ < (g!),_1 для всех 1 < г < d.

Из теоремы 2.2.1 с учетом теоремы 2.1.1 вытекает справедливость следующего утверждения.

Следствие 2.2.1. Для произвольных целых положительных чисел й и д имеется лишь конечное число АЫ0( А*)-симметрических д-расширений решетки АЛ, удовлетворяющих следующему условию: реализующая расширение Г вершинно-транзитивная группа О автоморфизмов Г может быть выбрана так, что стабилизатор в (? блока из соответствующей расширению Г системы блоков индуцирует на этом блоке квазипримитивную группу.

Поскольку транзитивная группа подстановок простой степени является, очевидно, квазипримитивной, то из теоремы 2.2.1 вытекает справедливость следующего утверждения.

Следствие 2.2.2. Пусть Г — Аи10(АЛ)-симметрическое д-расширение решетки Л'' для некоторого целого положительного числа й и некоторого простого числа д, реализуемое С, а, у. Тогда (Г,сг,у) удовлетворяет условию [щ,... ,пЛ]-периодичности, где щ < (д!)'-1 для всех 1 < г < (1. В частности, с учетом теоремы 2.1.1 для произвольного целого положительного числа д, и для произвольного простого числа д имеется лишь конечное число Аи1а{Л.й)-силшетрических д-расширений решетки

В параграфе 2.3 диссертации из доказательства предложения 2 работы [9] выводится, что если Г — симметрическое ^-расширение решетки Л2, реализуемое некоторыми <3, а, у, то (Г, ст. <р) удовлетворяет условиям [п^^Г, б, а, ¡р), я2(Г, в, а, ^-периодичности и [з1(Г. О, ст, V), п2я2(Г, С, <т, ^¡-периодичности для подходящих целых положительных чисел щ и п2 (см. теорему 2.3.1 ниже). На основе этого результата в параграфе 2.3 получен критерий конечности множества симметрических д-расширений решетки Л2 для целого положительного числа д (см. теорему 2.3.3 ниже). Этот критерий используется в дальнейшем для получения обобщения следствия 2.1.3 в случае 2-мерной решетки (см. следствие 2.3.1 ниже). Кроме того, этот критерий используется в главе 4 при получении описания /1и4о(Л2)-симметричсских 4-расширений решетки Л2.

Пусть Г — симметрическое д-расширение решетки Л2 для некоторого целого положительного числа д, реализуемое ¿7, а, ц>. Для каждого г е {1,2} следующим образом определим целое неотрицательное число п(Т,0,а,<р). Для произвольных целых чисел Ь < 12 положим Х,иЬ = {х £ У(Г) : ¡^(Г, О, а, р) < Рт^ф')) < (12 + 1)«ДГ, й, а,1р) кО < Ргз-г^э-")) < я3-4(Г,С,(т,¥))} (определения ,в,а,<р) и а2(Г, С, <г, см. выше), и пусть 5|ь(, = Ох,и,2 — поэлементный стабилизатор множества в группе (3. Тогда т"г(Г, С, сг, есть наименьшее из неотрицательных целых чисел г таких, что .S,:f;"¡:1'r+, =

г и "-г,г ~ для всех целых чисел Ь >г.

Теорема 2.3.1 Пусть Г — симметрическое д-расширение решетки Л2 для некоторого целого положительного числа д, реализуемое О, сг, р. Тогда (Г, <т, </>) удовлетворяет условиям [п1в1(Г,0,а,1р),е2(Г,0,а,<р)]-периодичностпи и [^(Г, С,а,ср),п2з2(Г, О, а, ^-периодичности для некоторых щ < (9!)(2г1+1)«1»2 и „3 < г£)£ г,_ гдг, С. сг, ^э) и = «¿(Г, в, сг, ф) для каждого г 6 {1,2}.

Теорема 2.3.3 (критерий конечности множества симметрических д-расширений решетки Л2). Пусть д = {Г,- : ] е 7}

— некоторое множество симметрических д-расширений решетки Л2, где д — целое положительное число. Тогда Я конечно в том и только том случае, когда для некоторого целого неотрицательного числа г и каждого / 6 / симметрическое д-расширеиие Г3- решетки Л2 может быть реализовано такими Ъ^, а,, 1р}, что г^Г.,-, < г или г2(Г^, О,. а}, щ) < г.

Следствие 2.3.1. Для произвольного целого положительного числа д имеется лишь конечное число таких графов Г, являющихся Аи10(А2)-симметрическими д-расширепия-

ми решетки Л2, что для соответствующей Г (как Аи^(А2)-симметрическому ц-расши-рению Л2) системы блоков а и для некоторых х € К(Г) и у 6 К(Г)\г'г выполняется условие \{г 6 у" : {х, г} е £(Г)}| = 1.

Глава 3 работы посвящена описанию Аи^Л^-симметрических 2-расширений решетки АЛ для произвольного целого положительного числа А Она состоит из двух параграфов.

Параграф 3.1 содержит список всех обобщенных Лг/^Л^-симметрических 2-расширений решетки К& для д, = 1 и с? = 2.

В параграфе 3.1 показывается, что обобщенные Лгг4о(Л1)-симметрические 2-расшире-ния решетки Л1 исчерпываются следующими графами Г*'2.1 < п < 4. Для каждого 1 < п < 4

= {(¿,*0 : г е 2, к £ {1,2}}.

Для каждого 1 < п < 4

Е(П'2) = Е0(Г^)иЕ1(Г^),

где для

О0 = {{(г, к), (г, /)} : г 6 к, I 6 {1, 2}, к ф г} и

= {{(¿. *).(» + 1:0} :' 6 к,I е {1,2}}

множества £о(Г*'2) = Е(Г^2)пВ0 и Ех(Г£2) = £'(Г^2)П£>1 задаются следующим образом:

п = 1 : = До, ^(Г}-2) = {{(», *:), (г + 1, Ь)} : г е 2, А; е {1,2}};

п = 2 : £7о(Г|'2) = ^(Г^2) = А;

п = 3 : Е0(Г1'2) — 0, ^(Гз'2) = Вц

» = 4 : £Ь(Г;-2) = 0, ^(Г^2) = ^(Г}'2).

Далее в параграфе 3.1 показывается, что обобщенные Ли£о(Л2)-симметрические 2-рас-ширения решетки Л2 исчерпываются следующими графами Г2'2, 1 < п < 8 . Для каждого 1 < п < 8

= ¿6 {1,2}}.

Для каждого 1 < п < 8

£(г2'2) = Я0(Г2-2) и £г(Г2-2) и Е2(Г2'2),

где для

А) = {{(г,;',/)}: ¿,^6 2, ¿,/€{1,2}, А: ф А = &),(* + 1,^'Л)} -1,3 й,ге {1,2}} и

Дг = {{(¿.Л *0, (м + 1.0} : М € М 6 {1,2}}

множества £0(Г2'2) = £(Г2-2) П Д,, А(Г2'2) = £(Г2'2) П А и £2(Г2'2) = В(Г2'2) П задаются следующим образом:

п = 1: £Ь(Г**) = Дь = + А 6 {1,2}},

^(Г?-2) = {{(¿,7, А:), (и + 1,к)} :«, j 6 2, £ £ {1,2}};

п = 2 : £0(Г2'2) = До, -Б1(Г1-2) = Е^'2),

= + ггО (тоё 2), Ь е {1,2»

и{{(г,1,1)!(гЛ-112)},{(а,2),(г,у + 1,1)} : г€ г = 1 (шос! 2)};

п = 3 £о(Г2'2) = £>о ^(Гз2'2) = Е^ТП ^(Г2'2) = А;

п = 4 £о(ГГ) = £>о Е^Г) = ои Я2(Г2'2) = Е>2]

71 = 5 Е0(Г2/) = 0, и т?) = Ег( ГГ). й(гР) = Ег(ГГ)

п = 6 Е0(ГГ) = 0, Ех{ Г2'2) = ъаГ), А(Г2'2) = Е>1\

п = 7 Ео(Г2/) = 0, Д(Г?'2) = = А, Е2(ТГ) = Е>2\

п = 8 Ео(ГГ) = 0, Ег(Т\'2) = = Г?-2), Я2(Г2'2) = Щ Г?'2).

В параграфе 3.2 с использованием результатов параграфа 3.1 дается описание всех АЫц (Л^-симметрических 2-расширений решетки Л'1 для произвольного целого числа <1 > 2 (см. теорему 3.2.1 ниже). В качестве следствия этого описания в параграфе 3.2 получена формула для числа всех Ди40(Лй)-симметрических 2-расширений решетки Ал (см. следствие 3.2.1 ниже).

Пусть Г — Яг^Л^-симметрическое 2-расширение решетки Ал, реализуемое <3, а, <р. Граф Г называется насыщенным Ли^Л^-симметрическим 2-расширением решетки Ал если блоки системы а (напомним, что сг однозначно определяется графом Г) порождают в Г подграфы, изоморфные полному графу на двух вершинах. (В общем случае для произвольного целого положительного числа д насыщенными Лш/0(Л*)-симметрическими ^-расширениями решетки Аа называются ДиЦЛ^-симметрические д-расширения решетки А* посредством полного графа на ц вершинах.) Для каждого такого графа Г обозначим через 1/(Г) граф, у которого множество вершин совпадает с множеством вершин графа Г, а множество ребер получается из множества ребер графа Г удалением всех ребер, соединяющих в Г вершины из одного и того же блока системы а.

Пусть Г — произвольное насыщенное Ди£0(Л<г)-симметрическое 2-расширение графа А<*, где <1 > 2, реализуемое в, а, <р. Для целого числа 3 < г < <1 скажем, что в графе Г относительно уз направление {¿} реализует тип Г}'2 (соответственно, Гг'2), если подграф графа Г, порожденный множеством {х 6 У(Г) : Рт^<р(х")) = 0 при 1 < э < в., $ ф г}, изоморфен (соответственно, Г^'2). Для различных целых чисел 1 < г < ] < й скажем, что в графе Г относительно ¡р пара направлений {г,реализует тип Г|'2 (соответственно, Г2'2, Г3'2 или Г4' ), если подграф графа Г, порожденный {х € У(Г) : Рск(<р(х")) = 0 при 1 < к < к <£ {г,.?}}, изоморфен Г2, (соответственно, Гг' , Г2'2 или Г2,2).

Пусть Г — насыщенное Ди^Л^-симметрическое 2-расширение решетки АЛ, где с1> 2, реализуемое (3, <т, ¡р. Предположим, что существует целое число с, 0 < с < й, такое, что для каждого целого числа г с условием 1 < г < с относительно изоморфизма в графе Г направление {г} реализует тип Г2'2, а для каждого целого числа г с условием с < г < д. относительно изоморфизма (р в графе Г направление {г} реализует тип гР Полагая V = {{¿,Л :с < * < Э < (I и относительно изоморфизма <р пара направлений {г, Л реализует тип 1\' }, скажем, что в этом случае граф Г относительно изоморфизма Ч> реализует набор (с,Р). (Ясно, что последнее определение не зависит от выбора О.) Далее, скажем, что для целого 0 < с < ¡1 (напомним, что (I — произвольное целое число, большее 1) и V С {{2,7} : с < ъ < ] < <1] граф Г, являющийся насыщенным АЫ0(АЛу симметрическим 2-расширением решетки АЛ, реализует набор (с, V), если для некоторого изоморфизма ф графа Г/ст, где а — соответствующая Г система блоков, на решетку Ай граф Г реализует набор (с,"Р) относительно <р.

Теорема 3.2.1. Для произвольного целого числа с1> 2 справедливы следующие утверждения.

1) Каждое насыщенное АЫа^А^-симметрическое 2-расширение решетки Ай реализует некоторый набор (с, V), где 0 < с < И и Р С {{»,.?} : с < г < j < ¡1}.

2) Для любых 0 < с < д. и Р С {{¿.: с < г < ) < существует единственное, с точностью до изоморфизма, насыщенное АиЬа(А'')-симметрическое 2-расширение решетки АЛ, реализующее набор (с, Р).

3) Граф, реализующий набор (с,Р), где 0 < с < ё и Р С {{г,^} : с < I < ] < й], изоморфен графу, реализующему набор (с*,Р*), где 0 < с* < ё и Р" С {{г,_?} : с* < г <

< тогда и только тогда, когда с' = с и существует подстановка на {с + 1,..., переводящая Р в Р*.

4) Пусть Г — произвольное насыщенное АЫа(А'1)-симметрическое 2-расширение решетки Аа, реализующее отличный от (О, {{г,.?'} : 1 < г < < ¿}) набор. Тогда сопоставление графу Г графа 1>(Г) есть сохраняющая отношение изоморфности биекция множества насыщенных АиЬа{АЛ)-симметрических 2-расширений решетки Ай, реализующих отличные от (О, : 1 < г < з < ¿}) наборы, на множество Аи1й{Ай)-симметрических 2-расширений решетки не являющихся насыщенными.

Отметим, что для любого целого положительного числа 6, имеется единственное (с точностью до изоморфизма) несвязное обобщенное Ли^Л^-симметрическое 2-расширение решетки А*. Это несвязное обобщенное Лийо(Лй)-симметрическое 2-расширение решетки Л^ является дизъюнктным объединением двух графов, изоморфных Ай, т.е. изоморфно у(Г), где Г — насыщенное Лгйо(Л^)-симметрическое 2-расншрение решетки Аа, реализующее набор (0, {{г,: 1 < г < у < в,}).

В качестве следствия теорема 3.2.1 позволяет получить число N¿2 (попарно неизоморфных) Ли40(Л'г)-симметрических 2-расширений решетки Л1'для произвольного целого положительного числа А Для произвольного целого положительного числа к обозначим через ЛГ* число (попарно неизоморфных) графов с к вершинами (формулу для вычисления Мк см., например, в [10, теорема 15.5]).

Следствие 3.2.1. Для произвольного целого положительного числа <1 имеем На,2 = 2(и1 + № + ... + ЛУ + 1.

При ^ < 10 следствие 3.2.1 дает приводимые ниже значения для

^1,2 = 3, Л/-6,2 = 417.

^2,2 = 7, N7,2 = 2505,

^3,2 = 15, ДГ8'2 = 27197,

= 37, N^2 = 576533,

Л^5,2 = 105, ДГад = 24586869.

Глава 4 работы посвящена описанию Ла£о(Л<г)-симметрических ^-расширений решетки Л^ для небольших ¿ид. Она состоит из трех параграфов.

Параграф 4.1 содержит список всех обобщенных Лг1г0(Л1)-симметрических 3-расшире-ний решетки Л1 (6 графов) и список всех обобщенных Ли<о(Л2)-симметрических 3-расши-рений решетки Л2 (32 графа).

Параграфы 4.2 и 4.3 посвящены описанию Аи^Л^-симметрических 4-расширений ре-1 и в, = 2. В параграфе 4.2 приводится список всех обобщенных

Л uio (Л1 )-симметрических 4-расширений решетки Л1 (34 графа) и доказывается теорема 4.2.1, которая утверждает, что если Г — ЛгЛ0(Л2)-симметрическое 4-расширение решетки Л2, реализуемое Ли40(Г) и некоторыми и, <р (как было отмечено выше, каждое Aut0(kd)-симметрическое g-расширение решетки kd реализуемо таким образом), то для г = 1 или для г = 2 имеет место равенство п(Г, Л^0(Г), а, у) = 0 (что с учетом теоремы 2.3.3 влечет конечность числа Лиг0(А2)-симмегрических 4-расширений решетки Л2). В параграфе 4.3 на основе теоремы 4.2.1 получен список всех обобщенных Лм£0(А2)-симметрических 4-расширений решетки Л2 (517 графов).

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

Основными результатами диссертациоиной работы являются следующие.

1. Построен весьма широкий класс локально конечных графов, имеющих бесконечное число симметрических расширений посредством одного и того же конечного графа.

2. Доказана конечность числа Ли(0(Ай)-симметрических д-расщирений d-мерной решетки kd для произвольного целого положительного числа d и произвольного простого числа Ч-

3. Найдены все Ли^Л^-симметрические 2-расширения d-мерной решетки kd для произвольного целого положительного числа d.

4. Найдены все Лг^Л^-симмстрические g-расширения решетки Ad для d е -fl 2} и Я £ {3,4}.

СПИСОК ЛИТЕРАТУРЫ

[1] Trofimov V.I. Symmetrical extensions of graphs and some other topics in graph theory related with group theory // Тр. Ин-та математики и механики УрО РАН. 2011 Т 17 № 4. С. 316-320.

[2j Imrich W., Klavzar S. Product Graphs: Structure and Recognition // New-York et. al.: John Wiley and Sons, Inc., 2000. 358 p.

[3] Трофимов В.И. Графы с полиномиальным ростом // Изв. АН СССР. Сер. математическая. 1985. Т. 51, № 2. С. 405-417.

[4] Woess W. Topological groups and recurrence of quasitransitive graphs // Rend. Sem Mat. Milano. 1996. Vol. 64. P. 185-213.

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

[6] Грин М., Шварц Дж., Витген Э. Теория суперструн Т. 1, 2 // Москва: Мир, 1990.

[7] Baumslag G,, Strebel R., Thomson M. On the inultiplicator of F/~/cR // Journal of Pure and Applied Algebra 1980. Vol. 16, № 2. P. 121-132.

[8] Ольшанский А.Ю. Геометрия определяющих соотношений в группа // Москва- Наука 1989. 448 с.

[9] Seifter N., Trofimov V.I. Automorphism Groups of Graphs with Quadratic Growth // J Comb. Theory. Ser. B. 1997. Vol. 71, № 2. P. 205-210.

[10] Харари Ф. Теория графов. // Москва: Мир, 1973. 302 с.

РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

[11] Неганова, Е.А. у4и<о(Л'г)-симметрические 2-расширения решеток Ad / Е.А. Неганова, В.И. Трофимов // Проблемы теоретич. и прикл. математики: тез. докл. 41-й Всерос. мол. шк.-конф. Екатеринбург: ИММ УрО РАН, 2010. С. 64-70.

[12] Неганова, Е.А. О симметрических g-распшрениях 2-мерной решетки / Е.А. Неганова,

B.И. Трофимов // Тр. Ин-та математики и механики УрО РАН. 2010. Т. 16, № 3.

C. 199-209.

[13] Неганова, Е.А. О симметрических расширениях графов / Е.А. Неганова, В.И. Трофимов // Международная конференция, посвященная 70-летию Академика Ю.Л. Ершова: тезисы докладов. Новосибирск, 2010. С. 88.

[14] Неганова, Е.А. Симметрические расширения графов / Е.А. Неганова, В.И. Трофимов // Международная алгебраическая конференция, посвященная 70-летию A.B. Яковлева: тезисы докладов. Санкт-Петербург, 2010. С. 51-53.

[15] Неганова, Е.А. О симметрических ^-расширениях решеток / Е.А. Неганова, В.И. Трофимов // Теория групп и ее приложения: труды 8-ой Международной школы-конференции по теории групп, посвященной 75-летию В.А. Белоногова. Нальчик, 2010. С. 186-189.

[16] Неганова, Е.А. Конечность числа Лг^о(Л2)-симметрических 4-расширений решетки А2 / Е.А. Неганова, В.И. Трофимов // Проблемы теоретич. и прикл. математики: тез. докл. 42-й Всерос. мол. шк.-конф. Екатеринбург: ИММ УрО РАН, 2010. С. 227-228.

[17] Неганова, Е.А. О симметрических 4-распшрениях 2-мерной решетки / Е.А. Неганова,

B.И. Трофимов // Тр. Ин-та математики и механики УрО РАН. 2011. Т. 17, № 3.

C. 242-257.

[18] Неганова, Е.А. Лк(о(Л2)-симметрические 4-расширения 2-мерной решетки Л2 / Е.А. Неганова // Тр. Ин-та математики и механики УрО РАН. 2011. Т. 17, № 4. С. 222-243.

[19] Неганова, Е.А. Аи4о(Л2)-симметрические 4-расширения 2-мерной решетки Л2 / Е.А. Неганова // Алгебра и геометрия: тез. докл. Междунар. конференции по алгебре и геометрии, посвященной 80-летию со дня рождения А.И. Старостина. Екатеринбург, 2011. С. 125-126.

[20] Неганова, Е.А. Конечность числа Ли^А^-симметрических g-расширений решетки Kd для простого д / Е.А. Неганова, В.И. Трофимов // Проблемы теоретич. и прикл. математики: тез. докл. 43-й Междунар. мол. шк.-конф. Екатеринбург: ИММ УрО РАН, 2012. С. 77-78.

Отпечатано в типографии ООО «Издательство УМЦ У ПИ» 620078, Екатеринбург, ул. Гагарина, 35а, оф. 2. тел. (343) 362-91-16,362-91-17 Заказ Тираж

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ НАУКИ ИНСТИТУТ МАТЕМАТИКИ И МЕХАНИКИ УРАЛЬСКОГО ОТДЕЛЕНИЯ РОССИЙСКОЙ АКАДЕМИИ НАУК

61 12-1/916

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

УДК 512.54+519.17 ---

ч

НЕГАНОВА ЕЛЕНА АЛЕКСАНДРОВНА СИММЕТРИЧЕСКИЕ РАСШИРЕНИЯ ГРАФОВ

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

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

Научный руководитель: д.ф.-м.н. В.И. Трофимов

ЕКАТЕРИНБУРГ 2012

Содержание

Введение 4

1 Существование локально конечных графов с бесконечным числом симметрических расширений посредством конечного графа 14

1.1 Достаточное условие существования у локально конечного графа бесконечного числа накрывающих симметрических расширений посредством одного и того же конечного графа .... 14

1.2 Примеры графов, имеющих бесконечное число накрывающих симметрических расширений посредством одного и того

же конечного графа........................ 18

2 Симметрические д-расширения решеток Аа 20

2.1 Условие периодичности для симметрических д-расширений решеток Аа............................. 20

2.2 .Аг^оСЛ^-симметрические д-расширения решеток Л^ и условие периодичности для них...................... 26

2.3 Критерий конечности множества симметрических ¿/-расширений решетки Л2 и некоторые его применения.......... 30

3 Ап^о(Асг)-симметрические 2-расширения решеток Ас1 35

3.1 Л^о(Л£г)-симметрические 2-расширения решеток А^ для (1—1

и (I = 2 ............................... 35

3.2 Аи^(Аа) -симметрические 2-расширения решеток А(1 для произвольного (1 ............................ 38

4 Аг^оСЛ^-симметрические д-расширения решеток Ал для не-

больших (I ид 50

4.1 Аи£о(Л^)-симметрические 3-расширения решеток для

(1 = 1 и & = 2............................ 50

4.2 Л^о(Л1)-симметрические 4-расширения решетки Л1 и конечность числа -симметрических 4-расширений решетки

А2 .................................. 56

4.3 Аи£о(Л2)-симметрические 4-расширения решетки Л2 ... 79

Список литературы 111

Введение

Диссертационная работа посвящена изучению симметрических расширений графов. Пусть Г и А — графы (под графом здесь и далее понимается неориентированный граф без петель и без кратных ребер). В соответствии с [1] связный граф Г называется симметрическим расширением графа Г посредством графа А, если существуют такая вершинно-транзитивная группа С автоморфизмов графа Г и такая система импримитивности а группы С на множестве У (Г) вершин графа Г, что фактор-граф Г/сг изоморфен графу Г и блоки системы и порождают в Г подграфы, изоморфные графу А. Ясно, что симметрическое расширение графа Г посредством графа А существует лишь для Г и А, допускающих вершинно-транзитивные группы автоморфизмов, причем граф Г должен быть связным. Если в приведенном выше определении симметрического расширения графа Г посредством графа А отказаться от условия связности графа Г, то получим определение обобщенного симметрического расширения графа Г посредством графа А. Если при этом (р — изоморфизм графа Г ¡а на граф Г, то будем говорить, что Г — обобщенное симметрическое расширение графа Г посредством графа А, реализуемое С, а, р.

Симметрические расширения графов представляют интерес в силу целого ряда причин (см. ниже). При этом часто бывает важно, чтобы (в приводимом выше определении симметрического расширения Г посредством А) при изоморфизме Г/сг на Г индуцируемая С группа С7 автоморфизмов графа Г/сг переходила в некоторую заданную группу автоморфизмов 6? графа Г. В связи с этим вводится следующее определение (см. [1]). Для графов Г, А и вершинно-транзитивной группы автоморфизмов С графа Г связный граф Г называется С-симметрическим расширением графа Г посредством графа А, если граф Г является симметрическим расширением графа Г посред-

ством графа А, реализуемым такими С, сг, что (рС7(р~1 = С. Если в этом определении отказаться от условия связности графа Г, то получим определение обобщенного С-симметрического расширения графа Г посредством графа А (реализуемого С, сг, <р).

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

1) Понятие симметрического расширения одного графа посредством другого графа аналогично хорошо известному понятию расширения одной группы посредством другой группы. Связь между расширениями групп и симметрическими расширениями графов можно формализовать следующим образом. Пусть С — группа с системой порождающих М такой, что 1 ф М = М-1, N — нормальная подгруппа группы С, С = С/Я и М = {дИ : д (Е М \ Щ. Тогда граф Кэли Г^^ группы С, построенный по системе порождающих М, является С-симметрическим расширением графа Кэли Гв,м группы С, построенного по системе порождающих М, на котором С действует естественным образом, посредством графа Кэли группы Л^, построенного по множеству М П N. В связи с этим изучение симметрических расширений графов представляет интерес для теории групп.

2) Ряд известных конструкций теории графов, если их применить к вер-шинно-симметрическим (т.е. допускающим транзитивные на вершинах группы автоморфизмов) графам Г и А, приводят к симметрическим расширениям Г посредством А. Такими конструкциями являются, например, декартово, прямое, лексикографическое и некоторые другие произведения (см. [2]). К симметрическим расширениям графов приводит также следующая известная конструкция. Если Г — связный граф, допускающий вершинно-транзитивную группу автоморфизмов С, и если ф : 1/(Г) У(Г) — накрывающее отображение связного графа Г на граф Г такое, что соответствующая этому отображению накрывающая группа С := {д € АЫ(Т) : фд € Сф} группы С вершинно-транзитивна, то множество слоев а :— {ф~1{х) : х Е У(Г)} есть система импримитивности Си ф индуцирует изоморфизм (р графа V/сг на Г такой, что (рС7^"1 — вершинно-транзитивная подгруппа груп-

пы С. Следовательно, Г является -симметрическим расширением Г

посредством Д, где А — подграф графа Г, порожденный некоторым слоем из а.

3) Для ряда важных классов связных бесконечных локально конечных вершинно-симметрических графов были получены описания, имеющие, по существу, следующий вид: графы из рассматриваемого класса являются в точности С-симметрическими расширениями некоторых известных графов Г посредством конечных графов, где — некоторые заданные группы автоморфизмов графов Г. Такого вида описания были получены, например, для графов с полиномиальным ростом (см. [3]), для графов с рекуррентным случайным блужданием (см. [4]) и для графов с вершинно-транзитивной группой ограниченных автоморфизмов (см. [5]). Изучение таких О-симметрических расширений графов Г посредством конечных графов является, следовательно, более детальным исследованием этих классов. Определенный интерес представляет в связи с этим изучение симметрических расширений бесконечных локально конечных графов посредством конечных графов.

4) Если Г — симметрическое расширение графа Г посредством графа Д, то граф Г можно интерпретировать "кристаллографически" как граф Г, у которого вершины наделены внутренней структурой вида Д (такие наделенные внутренней структурой вершины графа Г выступают как "молекулы" вида Д), причем эти внутренние структуры вершин графа Г согласуются со структурой Г так, что вся получающаяся в результате конструкция Г (вершины Г выступают при этом как "атомы") симметрична (т.е. граф Г допускает вершинно-транзитивную группу автоморфизмов, отображающую "молекулы" на "молекулы"). В связи с этим симметрические расширения семерных решеток Ас1 посредством конечных графов могут представлять интерес для "молекулярной" кристаллографии.

5) В некоторых физических теориях (см., например [6],) пространство-время наряду с (1 "обычными размерностями" имеет несколько "компактифицированных размерностей". В качестве трансляционно-однородных дискретных аппроксимаций такого пространства-времени могут выступать Ап^А^-симметрические расширения ¿¿-мерной решетки А<1 посредством ко-

нечных графов, где АиЬо(Асг) — группа всех сдвигов, т.е. "параллельных переносов", решетки Л°\ (Под трансляционной однородностью здесь понимается возможность перемещения любой вершины в любую другую вершину автоморфизмом, индуцирующим сдвиг Л^, т.е. трансляцию на "обычных размерностях" пространства-времени.) В связи с этим представляют интерес -симметрические расширения ¿-мерных решеток А(1, посредством конечных графов.

Таким образом, исследование симметрических расширений локально конечных графов посредством конечных графов и, в особенности, симметрических и Аи^о(Ас2)-симметрических расширений (¿-мерных решеток Л^ посредством конечных графов актуально и представляет значительный интерес. Принципиальным вопросом при исследовании симметрических расширений локально конечного графа Г посредством конечного графа А (или С-сим-метрических расширений Г посредством А для заданной вершинно-транзи-тивной группы автоморфизмов С графа Г) является вопрос о конечности их числа.

Цель диссертационной работы состоит в

- построении примеров локально конечных графов, допускающих бесконечное число симметрических расширений посредством конечного графа;

- исследовании вопроса о конечности числа симметрических и АЫо(А(1)-симметрических расширений ¿-мерной решетки посредством конечного графа;

- построении всех Лп^о(Лсг)-симметрических расширений ¿-мерной решетки посредством конечного графа А для некоторых представляющих интерес с1 и А.

Полученные в работе результаты носят теоретический характер. Они могут представлять интерес для теории групп и теории графов, а также могут быть использованы в кристаллографии и в физике (в теории струн). Основные результаты работы являются новыми. Они опубликованы в работах [11]—[20]. Работы [11]-[17], [20] выполнены в нераздельном соавторстве с В.И. Трофимовым.

Дадим обзор основных результатов диссертационной работы. Предварительно приведем необходимые для этого определения и обозначения.

Используемые в работе обозначения, в основном, стандартны. Если Г — граф и X — некоторое подмножество множества его вершин, то через {Х)т обозначается подгаф графа Г, порожденный множеством X. Для графа Г и разбиения а множества вершин графа Г через где х — вершина графа Г, обозначается подмножество из а, содержащее х. Если д — автоморфизм графа Г, сохраняющий <т, то да — автоморфизм графа Г/сг, индуцируемый д. Если д — автоморфизм графа Г и X — ^-инвариантное множество вершин графа Г, то дх — подстановка на X, индуцируемая д. Через Т(х) обозначается окрестность вершины х графа Г.

Для произвольного целого положительного числа д связный граф Г называется симметрическим д-расширением графа Г (соответственно, С-сгш-метрическим д-расширением графа Г, где (7 — группа автоморфизмов графа Г), если существуют такая вершинно-транзитивная группа С автоморфизмов графа Г и такая система импримитивности а группы С на 1/(Г) с блоками порядка д, что найдется изоморфизм ср графа Г/сг на граф Г (соответственно, найдется изоморфизм <р графа Г/сг на граф Г, для которого срС^"1 = С). При этом говорят, что Г — симметрическое (соответственно, (7-симметрическое) ^-расширение графа Г, реализуемое С, и, (р. Если в приведенном выше определении симметрического (соответственно, С-симметрического) ^-расширения графа Г отказаться от условия связности графа Г, то получим определение обобщенного симметрического (соответственно, О-симметрического) ^-расширения графа Г (реализуемого С, сг,

Ч>)-

Если в данном выше определении симметрического (соответственно, симметрического) ^-расширения графа Г потребовать, чтобы а можно было выбрать со следующим дополнительным свойством: для произвольной вершины х графа Г каждый блок системы импримитивности сг, смежный в графе Г/сг с ха, содержит в точности одну смежную с х вершину, то получим определение накрывающего симметрического (соответственно, накрывающего й-симметрического, где й — группа автоморфизмов графа Г) д-расширения графа Г. Если же вместо этого потребовать, чтобы <т можно было выбрать со следующим более слабым свойством: каждая вершина х графа Г смежна не более, чем с одной вершиной из произвольного не со-

держащего х блока системы импримитивности <т, то получим определение неразветвленного симметрического (соответственно, неразветвленного G-симметрического, где G — группа автоморфизмов графа Г) д-расширения графа Г. (Когда говорится, что накрывающее (соответственно, неразветв-ленное) симметрическое (соответственно, (^-симметрическое) д-расширение графа Г реализуется G, а, ср, то подразумевается, что а обладает указанным дополнительным свойством.)

Под ¿-мерной решеткой Ad, где d — целое положительное число, понимается граф, вершинами которого являются все упорядоченные наборы (ai,..., cid) из d целых чисел, и две вершины (а'1?..., a'd) и (а'{,..., a¿) смежны тогда и только тогда, когда

К - а!{ | + ... + | a'd- = 1.

Для d-мерной решетки Ad и 1 < j < d мы полагаем Prj : V(Ad) —Z, Pr j((ai,a2,...,ûd)) = ûj-

Сдвигом решетки Ad называется ее автоморфизм, который переводит произвольную вершину (ai,..., a¿) в вершину (ai + k\,..., a¿ + k¿) для некоторых фиксированных целых чисел ki,..., k¿. Для каждого 1 < г < d через U обозначается сдвиг решетки Ad для которого кг = 1 ж к:3 = 0 для всех j G {1,..., (¿}\{¿}. Через Auto(Ad) обозначается подгруппа группы автоморфизмов решетки Ad, состоящая из всех ее сдвигов. Для произвольного целого положительного числа g, таким образом, связный граф Г называется обобщенным симметрическим (соответственно, обобщенным AutQ(Ad)~ симметрическим) g-расширением решетки Ad, если существуют такая вер-шинно-транзитивная группа G автоморфизмов графа Г и такая система импримитивности а группы G на У(Г) с блоками порядка g, что найдется изоморфизм ip графа Т/а на решетку Ad (соответственно, найдется изоморфизм ip графа Т/а на решетку Ad, для которого <pGa(p~~l = Auto(Ad)). При этом будем говорить, что Г — симметрическое (соответственно, Autç,{Ad)~ симметрическое) g-расширение решетки Ad, реализуемое G, сг, (р.

Напомним, что для произвольного связного графа Е через AutoÇE) обозначается группа всех его ограниченных автоморфизмов, т. е. таких автоморфизмов g, что расстояния в графе Е между х и д(х), где х пробегает множество всех вершин графа Е, ограничены в совокупности. (Введен-

ное выше обозначение АиЬо(Ал) согласуется с этим определением.) Согласно [5, следствие 2(1)] для связного локально конечного графа Е множество Т(АЫо(Е)) всех его ограниченных автоморфизмов конечного порядка является (нормальной) подгруппой группы АиЬ(Е). При этом, если АиЬо(Е) — вершинно-транзитивна, то согласно [5] система импримитивности а группы АиЬ{Е) на ^(Е), состоящая из Т(А^о(Е))-орбит, имеет конечные блоки и АиЬо(Е)а = Zd для некоторого целого неотрицательного числа ¿.

Как показано в [1], если Г — Л^о(Лсг)-симметрическое ^-расширение решетки А6, для некоторых целых положительных чисел с1 и д, реализуемое С, а, (р, то блоки а являются Т(АиЬо(Г))-орбитами на У"(Г) (и, следовательно, а однозначно определена), а Г является Лг^Л^-симметрическим д-рас-ширением решетки Л^, реализуемым АиЬ0(Г), с, р. В связи с этим разбиение а множества У(Г), состоящее из Т(АиЬо(Т))-офит на У (Г), называется соответствующей Г (как Агг^о(Лсг)-симметрическому д-расширению решетки А*) системой блоков.

В главе 1 доказывается существование связного локально конечного графа Г и конечного графа А таких, что имеется бесконечное число симметрических расширений Г посредством А. Более того, в главе 1 строится весьма широкий класс локально конечных графов Г, имеющих бесконечное число накрывающих симметрических расширений посредством одного и того же конечного графа А. Для этого в параграфе 1.1 доказывается (см. теорема 1.1.1), что если А — конечно порожденная группа и В — ее центральная подгруппа, являющаяся свободной абелевой группой счетного ранга, то в случае ограниченности порядков всех конечных подгрупп группы А/В в качестве графа Г можно взять некоторый граф Кэли группы А/В. В параграфе 1.2 с использованием результатов комбинаторной теории групп показывается, что группа А и ее центральная подгруппа В с требуемыми в теореме 1.1.1 свойствами могут быть выбраны так, что А/В изоморфна произвольной свободной разрешимой группе ступени разрешимости п > 1 с й > 1 свободными порождающими (см. пример 1.2.1; используется [7, теорема А]) или изоморфна определенного вида периодической группе и даже группе, все собственные подгруппы которой имеют фиксированный простой порядок (см. пример 1.2.2; используется [8, параграфы 25, 27, 29, 31]).

Глава 2 посвящена рассмотрению вопроса о конечности числа симметрических и Аи£о(Л^)-симметрических ^-расширений ¿-мерной решетки Л^. Она состоит из трех параграфов.

В параграфах 2.1 и 2.2 наш подход к исследованию вопроса о конечности числа симметрических и Аг^о(Л^)-симметрических д-расширений ¿¿-мерной решетки А(1 основывается на проверке выполнения для них следующего условия [пь ..., п^-периодичности. Пусть Г — о�