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

УДК 512.54+519.17

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

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

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

АВТОРЕФЕРАТ

диссертации на соискание ученой степени

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

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

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

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

Официальные оппоненты: доктор физико-математических наук, профессор В.В. Беляев кандидат физико-математических наук К.В. Костоусов

Ведущая организация: Челябинский государственный университет

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

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

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

Ученый секретарь диссертационного совета Д 004.006.03, кандидат физ.-мат. наук И.Н. Белоусов

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

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

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

Если при этом — изоморфизм графа / на граф, то будем говорить, что — обобщенное симметрическое расширение графа посредством графа, реализуемое G,,.

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

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

1) Понятие симметрического расширения одного графа посредством другого графа аналогично хорошо известному понятию расширения одной группы посредством другой группы. Связь между расширениями групп и симметрическими расширениями графов можно формализовать следующим образом. Пусть G — группа с системой порождающих M такой, что 1 M = M 1, N — нормальная подгруппа группы G, G = G/N и / M = {gN : g M \ N }. Тогда граф Кэли G,M группы G, построенный по системе порождающих M, является G-симметрическим расширением графа Кэли G,M группы G, построенного по системе порождающих M, на котором G действует естественным образом, посредством графа Кэли N,M N группы N, построенного по множеству M N. В связи с этим изучение симметрических расширений графов представляет интерес для теории групп.

2) Ряд известных конструкций теории графов, если их применить к вершинно-симметрическим (т.е. допускающих транзитивные на вершинах группы автоморфизмов) графам и, приводят к симметрическим расширениям посредством. Такими конструкциями являются, например, декартово, прямое, лексикографическое и некоторые другие произведения (см. [2]). К симметрическим расширениям графов приводит также следующая известная конструкция. Если — связный граф, допускающий вершинно-транзитивную группу автоморфизмов G, и если : V () V () — накрывающее отображение связного графа на граф такое, что соответствующая этому отображению накрывающая группа G := {g Aut() : g G} группы G вершинно-транзитивна, то множество слоев := { 1 (x) : x V ()} есть система импримитивности G и индуцирует изоморфизм графа / на такой, что G 1 — вершинно-транзитивная подгруппа группы G.

Следовательно, является G 1 -симметрическим расширением посредством, где — подграф графа, порожденный некоторым слоем из.

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

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

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

5) В некоторых физических теориях (см., например [6]) пространство-время наряду с d “обычными размерностями” имеет несколько “компактифицированных размерностей”.

В качестве трансляционно-однородных дискретных аппроксимаций такого пространствавремени могут выступать Aut0 (d )-симметрические расширения d-мерной решетки d посредством конечных графов, где Aut0 (d ) — группа всех сдвигов, т.е. “параллельных переносов”, решетки d. (Под трансляционной однородностью здесь понимается возможность перемещения любой вершины в любую другую вершину автоморфизмом, индуцирующим сдвиг d, т.е. трансляцию на “обычных размерностях” пространства-времени.) В связи с этим представляют интерес Aut0 (d )-симметрические расширения d-мерных решеток d посредством конечных графов.

Таким образом, исследование симметрических расширений локально конечных графов посредством конечных графов и, в особенности, симметрических и Aut0 (d )-симметрических расширений d-мерных решеток d посредством конечных графов актуально и представляет значительный интерес. Принципиальным вопросом при исследовании симметрических расширений локально конечного графа посредством конечного графа (или G-симметрических расширений посредством для заданной вершинно-транзитивной группы автоморфизмов G графа ) является вопрос о конечности их числа.

Цель работы.

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

2. Исследование вопроса о конечности числа симметрических и Aut0 (d )-симметрических расширений d-мерной решетки d посредством конечного графа.

3. Построение всех Aut0 (d )-симметрических расширений d-мерной решетки d посредством конечного графа для некоторых представляющих интерес d и .

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

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

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

Апробация работы. Результаты диссертации докладывались на Международной конференции, посвященной 70-летию академика Ю.Л. Ершова (Новосибирск, 2010 г.), на Международной алгебраической конференции, посвященной 70-летию А.В. Яковлева (СанктПетербург, 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 г., проект № А3.

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

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

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

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

Помимо данных выше, в работе используются следующие определения.

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

Если в данном выше определении симметрического (соответственно, G-симметрического) q-расширения графа потребовать, чтобы можно было выбрать со следующим дополнительным свойством: для произвольной вершины x графа каждый блок системы импримитивности, смежный в графе / с x, содержит в точности одну смежную с x вершину, то получим определение накрывающего симметрического (соответственно, накрывающего G-симметрического, где G — группа автоморфизмов графа ) q-расширения графа. Если же вместо этого потребовать, чтобы можно было выбрать со следующим более слабым свойством: каждая вершина x графа смежна не более, чем с одной вершиной из произвольного не содержащего x блока системы импримитивности, то получим определение неразветвленного симметрического (соответственно, неразветвленного Gсимметрического, где G — группа автоморфизмов графа ) q-расширения графа. (В дальнейшем, когда говорится, что накрывающее (соответственно, неразветвленное) симметрическое (соответственно, G-симметрическое) q-расширение графа реализуется G,,, то подразумевается, что обладает указанным дополнительным свойством.) Под d-мерной решеткой d, где d — целое положительное число, понимается граф, вершинами которого являются все упорядоченные наборы (a1,..., ad ) из d целых чисел, и две вершины (a1,..., ad ) и (a,..., a ) смежны тогда и только тогда, когда Для d-мерной решетки d и 1 j d мы полагаем Prj : V (d ) Z, Prj ((a1, a2,..., ad )) = Сдвигом решетки d называется ее автоморфизм, который переводит произвольную вершину (a1,..., ad ) в вершину (a1 + k1,..., ad + kd ) для некоторых фиксированных целых чисел k1,..., kd. Для каждого 1 i d через ti обозначается сдвиг решетки d, для которого ki = 1 и kj = 0 для всех j {1,..., d}\{i}. Через Aut0 (d ) обозначается подгруппа группы автоморфизмов решетки d, состоящая из всех ее сдвигов.

Если — обобщенное симметрическое q-расширение решетки d (где d и q — целые положительные числа), реализуемое некоторыми G,,, то для каждого 1 i d число si (, G,, ) определяется как наименьшее из целых положительных чисел s со свойством ts G 1 (легко показать, что такое si (, G,, ) существует и не превосходит 2d d!).

Заметим, что если — обобщенное Aut0 (d )-симметрическое q-расширение решетки d, реализуемое G,,, то s1 (, G,, ) =... = sd (, G,, ) = 1.

Напомним, что для произвольного связного графа через Aut0 () обозначается группа всех его ограниченных автоморфизмов, т. е. таких автоморфизмов g, что расстояния в графе между x и g(x), где x пробегает множество всех вершин графа, ограничены в совокупности. (Введенное выше обозначение Aut0 (d ) согласуется с этим определением.) Согласно [5, следствие 2(i)] для связного локально конечного графа множество T (Aut0 ()) всех его ограниченных автоморфизмов конечного порядка является (нормальной) подгруппой группы Aut().

Как показано в [1], если — Aut0 (d )-симметрическое q-расширение решетки d для некоторых целых положительных чисел d и q, реализуемое G,,, то блоки являются T (Aut0 ())-орбитами на V () (и, следовательно, однозначно определена), а является Aut0 (d )-симметрическим q-расширением решетки d, реализуемым Aut0 (),,. В связи с этим разбиение множества V (), состоящее из T (Aut0 ())-орбит на V (), называется соответствующей (как Aut0 (d )-симметрическому q-расширению решетки d ) системой блоков.

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

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

Теорема 1.1.1. Пусть A — группа с системой порождающих {a±1,..., a±1 }, где d — целое положительное число, и B — центральная подгруппа группы A. Предположим, что выполняются следующие условия:

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

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

Тогда граф Кэли G,M группы G = A/B, построенный по системе порождающих M = {a±1 B,..., a±1 B}, имеет для каждого целого положительного числа q бесконечное число накрывающих G-симметрических (для естественного действия G на G,M ) q-расширений.

В параграфе 1.2 с использованием результатов комбинаторной теории групп показывается, что группа A и ее центральная подгруппа B с требуемыми в теореме 1.1.1 свойствами могут быть выбраны так, что A/B изоморфна произвольной свободной разрешимой группе ступени разрешимости n > 1 с d > 1 свободными порождающими (пример 1.2.1;

используется [7, теорема A]) или изоморфна определенного вида периодической группе и даже группе, все собственные подгруппы которой имеют фиксированный простой порядок (пример 1.2.2; используется [8, параграфы 25, 27, 29, 31]).

Глава 2 посвящена рассмотрению вопроса о конечности числа симметрических и Aut0 (d )-симметрических q-расширений d-мерной решетки d. Она состоит из трех параграфов.

В параграфах 2.1 и 2.2 наш подход к исследованию вопроса о конечности числа симметрических и Aut0 (d )-симметрических q-расширений d-мерной решетки d основывается на проверке выполнения для них следующего условия [n1,..., nd ]-периодичности.

Пусть — обобщенное симметрическое q-расширение решетки d, где d и q — целые положительные числа, реализуемое G,,. Скажем, что (,, ) удовлетворяет условию [n1,..., nd ]-периодичности, где n1,..., nd — целые положительные числа, если существуют такие g1,..., gd Aut(), сохраняющие разбиение, что [gi, gj ] = 1 для всех 1 i < j d и gi 1 = tni для всех 1 i d.

Как показывает следующий результат, для доказательства конечности какого-либо множества симметрических q-расширений решетки d достаточно доказать, что каждое из этого множества может быть реализовано такими G,,, что (,, ) удовлетворяет условию [n1,..., nd ]-периодичности для некоторых фиксированных целых положительных чисел n1,..., nd.

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

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

Теорема 2.1.2. Пусть — обобщенное симметрическое q-расширение решетки d для некоторых целых положительных чисел d и q, реализуемое G,,. Предположим, что группа G имеет конечный стабилизатор Gx вершины x графа. Тогда (,, ) удовлетворяет условию [n1,..., nd ]-периодичности, где ni si (, G,, )(q|Gx |)i 2d d!(q|Gx |)i1 для всех 1 i d.

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

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

Следствие 2.1.3. Пусть — неразветвленное симметрическое q-расширение решетки d для некоторых целых положительных чисел d и q, реализуемое G,,. Тогда (,, ) удовлетворяет условию [n1,..., nd ]-периодичности, где ni (2d d!)i q i1 для всех 1 i d. В частности, для произвольных целых положительных чисел d и q имеется лишь конечное число неразветвленных симметрических q-расширений решетки d.

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

Теорема 2.2.1. Пусть — Aut0 (d )-симметрическое q-расширение решетки d для некоторых целых положительных чисел d и q, реализуемое G,,, причем стабилизатор в G блока из индуцирует на этом блоке квазипримитивную группу. Тогда (,, ) удовлетворяет условию [n1,..., nd ]-периодичности, где ni (q!)i1 для всех 1 i d.

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

Следствие 2.2.1. Для произвольных целых положительных чисел d и q имеется лишь конечное число Aut0 (d )-симметрических q-расширений решетки d, удовлетворяющих следующему условию: реализующая расширение вершинно-транзитивная группа G автоморфизмов может быть выбрана так, что стабилизатор в G блока из соответствующей расширению системы блоков индуцирует на этом блоке квазипримитивную группу.

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

Следствие 2.2.2. Пусть — Aut0 (d )-симметрическое q-расширение решетки d для некоторого целого положительного числа d и некоторого простого числа q, реализуемое G,,. Тогда (,, ) удовлетворяет условию [n1,..., nd ]-периодичности, где ni (q!)i для всех 1 i d. В частности, с учетом теоремы 2.1.1 для произвольного целого положительного числа d и для произвольного простого числа q имеется лишь конечное число Aut0 (d )-симметрических q-расширений решетки d.

В параграфе 2.3 диссертации из доказательства предложения 2 работы [9] выводится, что если — симметрическое q-расширение решетки 2, реализуемое некоторыми G,,, то (,, ) удовлетворяет условиям [n1 s1 (, G,, ), s2 (, G,, )]-периодичности и [s1 (, G,, ), n2 s2 (, G,, )]-периодичности для подходящих целых положительных чисел n1 и n2 (см. теорему 2.3.1 ниже). На основе этого результата в параграфе 2.3 получен критерий конечности множества симметрических q-расширений решетки 2 для целого положительного числа q (см. теорему 2.3.3 ниже). Этот критерий используется в дальнейшем для получения обобщения следствия 2.1.3 в случае 2-мерной решетки (см. следствие 2.3.1 ниже). Кроме того, этот критерий используется в главе 4 при получении описания Aut0 (2 )-симметрических 4-расширений решетки 2.

Пусть — симметрическое q-расширение решетки 2 для некоторого целого положительного числа q, реализуемое G,,. Для каждого i {1, 2} следующим образом определим целое неотрицательное число ri (, G,, ). Для произвольных целых чисел l1 l положим Xl1,l2 = {x V () : l1 si (, G,, ) Pri ((x )) < (l2 + 1)si (, G,, ) и Pr3i ((x )) < s3i (, G,, )} (определения s1 (, G,, ) и s2 (, G,, ) см. выше), и пусть Sl1,l2 = GXl1,l2 — поэлементный стабилизатор множества Xl1,l2 в группе G. Тогда ri (, G,, ) есть наименьшее из неотрицательных целых чисел r таких, что Sr,r = Теорема 2.3.1 Пусть — симметрическое q-расширение решетки 2 для некоторого целого положительного числа q, реализуемое G,,. Тогда (,, ) удовлетворяет условиям [n1 s1 (, G,, ), s2 (, G,, )]-периодичности и [s1 (, G,, ), n2 s2 (, G,, )]-периодичности для некоторых n1 (q!)(2r1 +1)s1 s2 и n2 (q!)(2r2 +1)s1 s2, где ri = ri (, G,, ) и si = si (, G,, ) для каждого i {1, 2}.

Теорема 2.3.3 (критерий конечности множества симметрических q-расширений решетки 2 ). Пусть G = {j : j J} — некоторое множество симметрических q-расширений решетки 2, где q — целое положительное число. Тогда G конечно в том и только том случае, когда для некоторого целого неотрицательного числа r и каждого j J симметрическое q-расширение j решетки 2 может быть реализовано такими Gj, j, j, что Следствие 2.3.1. Для произвольного целого положительного числа q имеется лишь конечное число таких графов, являющихся Aut0 (2 )-симметрическими q-расширениями решетки 2, что для соответствующей (как Aut0 (2 )-симметрическому q-расширению 2 ) системы блоков и для некоторых x V () и y V ()\x выполняется условие |{z y : {x, z} E()}| = 1.

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

Параграф 3.1 содержит список всех обобщенных Aut0 (d )-симметрических 2-расширений решетки d для d = 1 и d = 2.

В параграфе 3.1 показывается, что обобщенные Aut0 (1 )-симметрические 2-расширения решетки 1 исчерпываются следующими графами 1,2, 1 n 4.

множества E0 (1,2 ) = E(1,2 ) D0 и E1 (1,2 ) = E(1,2 ) D1 задаются следующим образом:

n=1:

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

множества E0 (2,2 ) = E(n ) D0, E1 (2,2 ) = E(2,2 ) D1 и E2 (2,2 ) = E(2,2 ) D задаются следующим образом:

n=1:

n=2:

В параграфе 3.2 с использованием результатов параграфа 3.1 дается описание всех Aut0 (d )-симметрических 2-расширений решетки d для произвольного целого числа d 2 (см. теорему 3.2.1 ниже). В качестве следствия этого описания в параграфе 3.2 получена формула для числа всех Aut0 (d )-симметрических 2-расширений решетки d (см.

следствие 3.2.1 ниже).

Пусть — Aut0 (d )-симметрическое 2-расширение решетки d, реализуемое G,,.

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

Пусть — произвольное насыщенное Aut0 (d )-симметрическое 2-расширение графа d, где d 2, реализуемое G,,. Для целого числа 1 i d скажем, что в графе относительно направление {i} реализует тип 1,2 (соответственно, 1,2 ), если подграф графа, порожденный множеством {x V () : Prj ((x )) = 0 при 1 j d, j = i}, изоморфен 1,2 (соответственно, 1,2 ). Для различных целых чисел 1 i < j d скажем, что в графе относительно пара направлений {i, j} реализует тип 2,2 (соответственно, 2,2, 2, или 2,2 ), если подграф графа, порожденный {x V () : Prk ((x )) = 0 при 1 k d, k {i, j}}, изоморфен 2,2 (соответственно, 2,2, 2,2 или 2,2 ).

Пусть — насыщенное Aut0 (d )-симметрическое 2-расширение решетки d, где d 2, реализуемое G,,. Предположим, что существует целое число c, 0 c d, такое, что для каждого целого числа i с условием 1 i c относительно изоморфизма в графе направление {i} реализует тип 1,2, а для каждого целого числа i с условием c < i d относительно изоморфизма в графе направление {i} реализует тип 1,2. Полагая P = {{i, j} : c < i < j d и относительно изоморфизма пара направлений {i, j} реализует тип 1 }, скажем, что в этом случае граф относительно изоморфизма реализует набор (c, P). (Ясно, что последнее определение не зависит от выбора G.) Далее, скажем, что для целого 0 c d (напомним, что d — произвольное целое число, большее 1) и P {{i, j} : c < i < j d} граф, являющийся насыщенным Aut0 (d )симметрическим 2-расширением решетки d, реализует набор (c, P), если для некоторого изоморфизма графа /, где — соответствующая система блоков, на решетку d граф реализует набор (c, P) относительно.

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

1) Каждое насыщенное Aut0 (d )-симметрическое 2-расширение решетки d реализует некоторый набор (c, P), где 0 c d и P {{i, j} : c < i < j d}.

2) Для любых 0 c d и P {{i, j} : c < i < j d} существует единственное, с точностью до изоморфизма, насыщенное Aut0 (d )-симметрическое 2-расширение решетки d, реализующее набор (c, P).

3) Граф, реализующий набор (c, P), где 0 c d и P {{i, j} : c < i < j d}, изоморфен графу, реализующему набор (c, P ), где 0 c d и P {{i, j} : c < i < j d} тогда и только тогда, когда c = c и существует подстановка на {c + 1,..., d}, переводящая P в P.

4) Пусть — произвольное насыщенное Aut0 (d )-симметрическое 2-расширение решетки d, реализующее отличный от (0, {{i, j} : 1 i < j d}) набор. Тогда сопоставление графу графа () есть сохраняющая отношение изоморфности биекция множества насыщенных Aut0 (d )-симметрических 2-расширений решетки d, реализующих отличные от (0, {{i, j} : 1 i < j d}) наборы, на множество Aut0 (d )-симметрических 2-расширений решетки d, не являющихся насыщенными.

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

В качестве следствия теорема 3.2.1 позволяет получить число Nd,2 (попарно неизоморфных) Aut0 (d )-симметрических 2-расширений решетки d для произвольного целого положительного числа d. Для произвольного целого положительного числа k обозначим через Nk число (попарно неизоморфных) графов с k вершинами (формулу для вычисления Nk см., например, в [10, теорема 15.5]).

Следствие 3.2.1. Для произвольного целого положительного числа d имеем При d 10 следствие 3.2.1 дает приводимые ниже значения для Nd,2 :

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

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

Параграфы 4.2 и 4.3 посвящены описанию Aut0 (d )-симметрических 4-расширений решетки d для d = 1 и d = 2. В параграфе 4.2 приводится список всех обобщенных Aut0 (1 )-симметрических 4-расширений решетки 1 (34 графа) и доказывается теорема 4.2.1, которая утверждает, что если — Aut0 (2 )-симметрическое 4-расширение решетки 2, реализуемое Aut0 () и некоторыми, (как было отмечено выше, каждое Aut0 (d )симметрическое q-расширение решетки d реализуемо таким образом), то для i = 1 или для i = 2 имеет место равенство ri (, Aut0 (),, ) = 0 (что с учетом теоремы 2.3.3 влечет конечность числа Aut0 (2 )-симметрических 4-расширений решетки 2 ). В параграфе 4.3 на основе теоремы 4.2.1 получен список всех обобщенных Aut0 (2 )-симметрических 4-расширений решетки 2 (517 графов).

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

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

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

2. Доказана конечность числа Aut0 (d )-симметрических q-расширений d-мерной решетки d для произвольного целого положительного числа d и произвольного простого числа 3. Найдены все Aut0 (d )-симметрические 2-расширения d-мерной решетки d для произвольного целого положительного числа d.

4. Найдены все Aut0 (d )-симметрические q-расширения решетки d для d {1, 2} и q {3, 4}.

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

[1] Tromov V.I. Symmetrical extensions of graphs and some other topics in graph theory related with group theory // Тр. Ин-та математики и механики УрО РАН. 2011. Т. 17, [2] 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 reccurrence 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 multiplicator of F/c R // Journal of Pure and Applied Algebra 1980. Vol. 16, № 2. P. 121–132.

[8] Ольшанский А.Ю. Геометрия определяющих соотношений в группа // Москва: Наука, [9] Seifter N., Tromov 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] Неганова, Е.А. Aut0 (d )-симметрические 2-расширения решеток d / Е.А. Неганова, В.И. Трофимов // Проблемы теоретич. и прикл. математики: тез. докл. 41-й Всерос.

мол. шк.-конф. Екатеринбург: ИММ УрО РАН, 2010. С. 64–70.

[12] Неганова, Е.А. О симметрических q-расширениях 2-мерной решетки / Е.А. Неганова, В.И. Трофимов // Тр. Ин-та математики и механики УрО РАН. 2010. Т. 16, № 3.

С. 199–209.

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

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

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

С. 186-189.

[16] Неганова, Е.А. Конечность числа Aut0 (2 )-симметрических 4-расширений решетки / Е.А. Неганова, В.И. Трофимов // Проблемы теоретич. и прикл. математики: тез.

докл. 42-й Всерос. мол. шк.-конф. Екатеринбург: ИММ УрО РАН, 2010. С. 227–228.

[17] Неганова, Е.А. О симметрических 4-расширениях 2-мерной решетки / Е.А. Неганова, В.И. Трофимов // Тр. Ин-та математики и механики УрО РАН. 2011. Т. 17, № 3.

С. 242–257.

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

С. 222–243.

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

[20] Неганова, Е.А. Конечность числа Aut0 (d )-симметрических q-расширений решетки d для простого q / Е.А. Неганова, В.И. Трофимов // Проблемы теоретич. и прикл.

математики: тез. докл. 43-й Междунар. мол. шк.-конф. Екатеринбург: ИММ УрО РАН, 2012. С. 77–78.