Симметрические расширения графов Неганова, Елена Александровна

Введение к работе

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

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

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

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

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

изведения (см. [2]). К симметрическим расширениям графов приводит также следующая известная конструкция. Если Г — связный граф, допускающий вершинно-транзитивную группу автоморфизмов G, и если ф : V(T) —> V(T) — накрывающее отображение связного графа Г на граф Г такое, что соответствующая этому отображению накрывающая группа G := {д Є Aut(T) : фд Є Сф} группы G вершинно-транзитивна, то множество слоев а := {ф~¹(х) : х Є У(Г)} есть система импримитивности G и ф индуцирует изоморфизм <р графа Т/а на Г такой, что tpG^tp^-1 — вершинно-транзитивная подгруппа группы G. Следовательно, Г является ipG^ip^-1-симметрическим расширением Г посредством А, где А — подграф графа Г, порожденный некоторым слоем из о.

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

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

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

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

Цель работы.

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

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

3. Построение всех Аио(Л^)-симметрических расширений d-мерной решетки A^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 г., проект №- A3.

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

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