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

Семенова Алена Валерьевна

ОПЕРАДЫ КОНЕЧНЫХ ПОМЕЧЕННЫХ ГРАФОВ И

РЕШЕТОК

Специальность 01.01.06 Математическая логика, алгебра и теория чисел

Автореферат

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

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

Казань 2008

Работа выполнена на кафедре алгебры и математической логики Казанского государственного университета им. В.И. Ульянова Ленина

Научный руководитель: кандидат физико-математичских наук, доцент Тронин Сергей Николаевич

Официальные оппоненты: доктор физико-математических наук, профессор Артамонов Вячеслав Александрович кандидат физико-математических наук, старший научный сотрудник Абызов Адель Наилевич

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

Защита состоится ” 4 ” декабря 2008г. в 14.40 на заседании диссертационного совета Д 212.081.24 в конференц-зале Научной библиотеки имени Н.И. Лобачевского Казанского государственного университета по адресу:

ул.Кремлевская, 35.

С диссертацией можно ознакомиться в Научной библиотеке имени Н.И. Лобачевского Казанского государственного университета.

Автореферат разослан ” ” октября 2008 года.

Ученый секретарь диссертационного совета, кандидат физико-математических наук, доцент А.И.Еникеев

Общая характеристика работы

.

Актуальность темы.

Место, которое занимает теория операд в алгебре, можно кратко охарактеризовать следующим образом. В работах С.Н.Тронина1 показано, что каждое многообразие универсальных алгебр рационально эквивалентно многообразию алгебр над некоторой операдой. Точнее, в первой статье было введено понятие операды над вербальной категорией, и фактически речь идет о рациональной эквивалентности данного многообразия и многообразия алгебр над F Set–операдой (т.е. операдой над вербальной категорией F Set). Традиционные операды это симметрические операды, операды над вербальной категорией, являющейся подкатегорией F Set. Таким образом, в первом приближении можно сказать, что теория многообразий алгебр над операдами это теория обычных многообразий алгебр "по модулю" отношения рациональной эквивалентности, введенного А.И.Мальцевым3 (см. также книгу А.Г.Пинуса4 ).

Характерная черта операдного подхода состоит в том, что у рассматриваемых алгебр нет изначально выделенного небольшого количества операций, и следовательно, не имеет смысла говорить о тождествах. Все необходимые для определения свойства заключены в самой операде. В различных разделах математики можно встретить множество естественных примеров операд, алгебры над которыми невозможно или трудно описать "классическими" средствами общей (или универсальной) алгебры. В трудах В.А.Смирнова5, БордТронин, С.Н. Абстрактные клоны и операды / С.Н. Тронин // Сибирский математический журнал. 2002. Т. 43.

№ 4. С. 924–936.

2 Тронин, С.Н. Операды и многообразия алгебр, определяемые полилинейными тождествами / С.Н. Тронин // Сибирский математический журнал. 2006. Т. 47. № 3. С. 670 – 694.

3 Мальцев, А.И. Структурная характеристика некоторых классов алгебр / А.И. Мальцев // Доклад АН СССР. 1958.

Т. 120. № 1. С. 29 – 32.

4 Пинус, А.Г. Условные термы и их применение в алгебре и теории вычислений / А.Г. Пинус // Новосибирск: НГТУ.

2002. 239 с.

5 Смирнов, В.А. Симплициальные и операдные методы в теории гомотопий / В.А. Смирнов. М.: Изд-во "Факториал Пресс". 2002. 272 с.

мана Дж., Фогта Р.6, May J.P.7, Leinster T.8, Markl M., Shnider S., Stasheff J. описаны многочисленные примеры операд, возникающих в топологии, гомологической алгебре, теории категорий и даже в физике. При этом, однако, чисто алгебраические аспекты теории операд остаются несколько в стороне.

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

С другой стороны, в работах по теории графов, теории частично упорядоченных множеств и решеток невозможно найти упоминания об операдах. В частности, известные книги по "алгебраической" теории графов Biggs N.10, Chris D Godsil, Gordon F Royle11 не содержат ничего даже отдаленно похожего. Наш подход заключается в том, что сами совокупности конечных (помеченных) графов, частично упорядоченных множеств и решеток являются операдами, т.е. алгебраическими объектами, и заслуживают подробного изучения.

Интересно отметить, что этот подход возник все-таки не совсем на пустом месте. Частный случай той операции (операдной композиции), которая превращает семейство конечных помеченных графов в операду, был давно известен как "сумма Зыкова" (Харари Ф.12, с.36).

С другой стороны, в теории круговых турниров давно известны понятия, являющиеся частными случаями композиции в операдах графов, частично упорядоченных множеств и решеток, а также (операдно) неразложимых элементов в этих операдах (см. Boudabbous Y., Dammak J., Ille P.13 ).

Наконец, можно отметить (хотя это и лежит несколько в стороне от темы 6 Бордман, Дж. Гомотопически инвариантные алгебраические структуры на топологических пространствах: пер. с англ.

7 May, J.P. Definitions operads, algebras and modules / J.P. May // Contemporary Mathematics. 1997. V. 202. P. 1–7.

8 Leinster, T. Higher Operads, Higher Categories / T. Leinster // London Mathematical Society Lecture Note Series, Cambridge University Press. 2003. 380 p.

9 Markl, M. Operads in Algebra, Topology and Physics / M. Markl, S. Shnider, J. Stasheff // American Mathematical Society, Mathematical Surveys and Monographs. 2002. V. 96. 349 p.

10 Biggs, N. Algebraic graph theory / N. Biggs. Cambridge University Press. 1994. 213 p.

11 Chris D Godsil Algebraic graph theory / Chris D Godsil, Gordon F Royle // Springer. 2001. 439 p.

12 Харари, Ф. Теория графов / Ф. Харари. М.: Мир. 1973. – 301 с.

13 Boudabbous, Y. Indecomposability and duality of tournaments / Y. Boudabbous, J. Dammak, P. Ille // Discrete Mathematics.

нашей работы), что в теории двухполюсников (Яблонский С.В.14, ч.III, гл.2, пар.3) встречается множество понятий и результаты, аналогичные понятиям и результатам из теории операд. В частности, семейство двухполюсников (с помеченными стрелками) образует операду относительно указанной в данной книге операции подстановки, и понятия неразложимых и разложимых двухполюсников совершенно аналогичны изучаемым в нашей работе понятиям разложимых и неразложимых графов.

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

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

Методы исследования.

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

Научная новизна.

1. Найдены новые примеры операд. В частности, найдены операдные структуры на множествах известных классических объектов.

2. Получены критерии разложимости элементов найденных операд, в частности, графов, или неразложимости в операдную композицию.

14 Яблонский, С.В. Введение в дискретную математику / С.В. Яблонский. М.: Высшая школа. 2002. 384 с.

3. Выделены неразложимые (в операдном смысле) ("простые") элементы операд (графы, решетки и т.д.).

4. Описаны дополнительные структуры (структуры W –операд, в частности, F Set или Epi–операд) на найденных операдах.

5. Вычислены (с точностью до рациональной эквивалентности) многообразия алгебр над найденными операдами.

Теоретическая и практическая ценность.

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

Основные положения, выносимые на защиту.

1. Построены новые примеры операд, элементы которых можно интерпретировать как конечные помеченные графы (неориентированные и ориентированные).

2. Получены критерии разложимости и неразложимости элементов построенных операд в операдную композицию.

3. Найден явный вид многообразия алгебр над двумя из построенных операд, т.е. найдены системы операций и определяющие тождества.

Апробация работы.

Основные результаты диссертации докладывались и обсуждались на следующих конференциях: "Международная молодежная научная школаконференция "Лобачевские чтения 2002" в Казанском государственном университете (г.Казань, 2002 г.), "Международная летняя школа– конференция "Лобачевские чтения 2003" в Казанском государственном университете (г.Казань, 2003 г.), "Третья всероссийская молодежная научная школа–конференция "Лобачевские чтения 2003" в Казанском государственном университете (г.Казань, 2003 г.), "Международная конференция, посвященная 200–летию КГУ, "Алгебра и Анализ 2004" (г.Казань, 2004 г.), на семинарах кафедры алгебры КГУ в 2000–2006 гг. (руководитель кандидат физико–математических наук, доцент С.Н.Тронин) и итоговых конференциях кафедры алгебры Казанского государственного университета им.

В.И.Ульянова-Ленина.

Публикации.

По теме диссертации опубликовано 7 работ, их список помещен в конце автореферата. Результаты, полученные в совместной с научным руководителем работе, принадлежат авторам в равной мере.

Структура и объем работы.

Диссертационная работа изложена на 109 страницах и состоит из введения, четырех глав, библиографического списка использованных источников, включающего 41 наименование, и списка публикаций автора по теме диссертации из 7 наименований.

Содержание работы.

Во введении обоснована актуальность работы и формулируются основные утверждения диссертации.

В первой главе изложены все необходимые определения и некоторое количество простых примеров из теории операд. Мы используем обобщение операд, введенное С.Н.Трониным15, операды над вербальными категориями.

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

A = (aij ), 1 j m. Операция композиции, которую будем называть композицией 1, определяется так:

15 Тронин, С.Н. Абстрактные клоны и операды / С.Н. Тронин // Сибирский математический журнал. 2002. Т. 43.

№ 4. С. 924–936.

заполненная одним и тем же элементом aij из A, т.е. aij = aij Jni,kj, где Jni,kj матрица, состоящая из единиц.

Пусть теперь K моноид с единицей. Операция композиции, которую будем называть композицией 2, определяется так:

Соглашения здесь те же самые, что и выше.

дующим образом. Если A = (aij ), 1 i, j n, aij K, n, то матрица A состоит из элементов {M(n)| n = 1, 2,...}.

Теорема 1.

1) Семейство с операцией композиции 1 и действием симметрических групп (3) становится операдой.

2) Семейство с операцией композиции 2 и действием симметрических групп (3) становится операдой.

если определить композицию по формуле (2). При этом операды и надо считать несимметрическими (т.е. исключить из их определения действия симметрических групп).

В главе 2 некоторые подоперады описанных выше операд квадратных матриц интерпретируются таким образом, что их элементами можно считать конечные помеченные графы (тех или иных видов). Это достигается соответствием графу его матрице инцидентности A(), которое в случае, если вершины снабжены метками (числами 1,..., n), является взаимно однозначным. В этой главе исследовалась разложимость и неразложимость элементов операды графов (ориентированных и неориентированных) в операдную композицию. Построены новые примеры операд.

В главе 3 рассматриваются операды графов с несколько иной, чем в главе 2 операдной композицией: она соответствует композиции 2 из главы 1. Оказалось, что в этом случае на операдах (G, DirG) можно ввести структуру Epi операды. Здесь Epi вербальная категория, морфизмы которой все сюръективные отображения из конечных множеств [n] = {1,..., n} в [m] = {1,..., m}. Действие такого отображения f на граф с n вершинами f это некоторая разновидность стягивания вершин (с последующим отождествлением ребер). Это позволяет выразить все графы через операдную композицию двух графов +, и описанных выше действий отображений Наконец, главным результатом главы 3 является следующая теорема.

Теорема 2. Многообразие Alg(G) алгебр над операдой G рационально эквивалентно многообразию алгебр с двумя бинарными операциями сложения и умножения, и с одной константой, причем должны выполняться следующие десять тождеств:

Аналогичный результат справедлив для ориентированных графов (выполняются те же тождества, за исключением a1 · a2 = a2 · a1 ).

Глава 4 посвящена изучению операды конечных помеченных решеток.

Частично упорядоченные множества и решетки можно рассматривать как частный случай ориентированных графов. Оказывается, что если L0, L1,...,Ln конечные помеченные частично упорядоченные множества (ориентированные графы), то композиция 1 из главы 1 L0 L1... Ln снова частично упорядоченное множество, а если L0, L1,..., Ln решетки, то L0 L1... Ln также решетка. Обозначим через Lat операду, n ая компонента которой Lat(n) состоит из всех конечных помеченных решеток с n элементами. Во втором параграфе главы 4 доказана следующая теорема:

Теорема 3. Конечная решетка операдно разложима тогда и только тогда, когда в ней существует операдно разлагающий интервал.

Эта теорема дает инструмент для изучения разложимости и неразложимости в Lat.

Основная цель главы 4 описание большого количества неразложимых решеток.

Теорема 4. Если L1, L2 нетривиальные конечные помеченные решетки, то L1 L2 операдно неразложимая решетка.

Теорема 5. Операдно неразложимыми являются следующие классы конечных помеченных решеток:

1) Атомно порожденная решетка;

2) Коатомно порожденная решетка;

3) Простая решетка;

4) Решетка с относительными дополнениями;

5) Геометрическая решетка.

Теорема 6. Модулярная решетка с дополнениями операдно неразложима.

Существуют модулярные операдно разложимые решетки, которые представимы в виде CL1... Lm, где C цепь.

Теорема 7. Пусть L конечная дистрибутивная решетка. Тогда либо L операдно неразложима, либо существует w = 0, 1 такой, что для любого x L либо x w, либо x w. (Т.е. L = [0, w] [w, 1], в этом случае L разложима, и следовательно, представима в виде CL1... Lm, где C цепь, Li дистрибутивная решетка, i = 1,..., m).

Основные выводы.

1. Построены новые примеры операд, элементы которых можно интерпретировать как конечные помеченные графы (неориентированные и ориентированные).

2. Получены критерии разложимости и неразложимости элементов построенных операд в операдную композицию.

3. Найден явный вид многообразия алгебр над двумя из построенных операд, т.е. найдены системы операций и определяющие тождества.

Автор выражает глубокую благодарность своему научному руководителю Сергею Николаевичу Тронину за постоянное внимание к работе, терпение и поддержку, а также за постановку задачи.

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

[1] Тронин, C.Н. Операды конечных помеченных графов / С.Н. Тронин, А.В.

Семенова // Известия высших учебных заведений. Математика. 2004.

[2] Семенова, А.В. Алгебры над операдой конечных помеченных графов / А.В. Семенова // Известия высших учебных заведений. Математика.

[3] Семенова, А.В. Операда конечных помеченных решеток / А.В. Семенова // Известия высших учебных заведений. Математика. 2008. №2.

С. 77–80.

[4] Семенова, А.В. Операда конечных помеченных решеток / А.В. Семенова // Труды математического центра имени Н.И. Лобачевского. Т. 18 // Лобачевские чтения 2002. Казань: Казанское математическое общество.

[5] Семенова, А.В. Операдно неразложимые решетки / А.В. Семенова // Труды математического центра имени Н.И. Лобачевского. Т.19 // Теория функций, ее приложения и смежные вопросы. Казань: Казанское математическое общество. 2003. С. 195.

[6] Семенова, А.В. Операдная неразложимость атомно и коатомно порожденных решеток / А.В. Семенова // Труды математического центра имени Н.И. Лобачевского. Т. 21. // Лобачевские чтения 2003. Казань: Казанское математическое общество. 2003. С. 196–198.

[7] Семенова, А.В. Алгебры над операдой графов / А.В. Семенова // Труды математического центра имени Н.И. Лобачевского. Т. 23. // Алгебра и анализ 2004. Казань: Казанское математическое общество. 2004.