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

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

003452393

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

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

Автореферат

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

о.....■>

~ ., J

Казань — 2008

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

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

доцент

Тронин Сергей Николаевич

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

профессор

Артамонов Вячеслав Александрович

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

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

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

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

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

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

А.И.Еникеев

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

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

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

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

1 Трои ил, С Н Абстрактнее клоны и операды / С Н Троннн // Сибирский математический журнал — 2002 — Т 43 — № 4 — С 924-936

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

^Мальцев, А И Структурная характеристика некоторых ллалсов алгебр / А И Мальцев // Доклад АН СССР — 1958 — Т 120 — Ka 1 — С 29-32

'Пинус, А Г Условные термы и их применение в алгебре в теории вычислений / А Г Пинус // Новосибирск НГТУ — 2002 - 239 с

вСмярнов В А Симслишальные и операдные методы в теории гюмотопий / В А Смирнов — М Изд во "Факториал Пресс" - 2002 - 272 с

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

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

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

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

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

Наконец, можно отметить (хотя это и лежит несколько в стороне от темы

6Бордоаи, Дж Гомотопически инвариантные алгебраические структуры на топологических пространствах пер с англ / Дж Бордман, Р Фогт — M Мир — 1977 — 408 с

7Мау, J Р Definitions operads, algebras and modules / J P May // Contemporary Mathematics — 1Э97 — V 202 — P 1-7

8Lemster, T Higher Operads, Higher Categories / T Leinster // London Mathematical Society Lecture Note Series, Cambridge University Press — 2003 — 3S0 p

9Markl, M Op^'ads m Algebra, Topology and Physics / M Markl, S Shnider, J Stasheff//American Mathematical Society, Mathematical Surveys and Monographs — 2002 — V 96 — 349 p

l0Biggs, 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Харари, ф Теория графов / Ф Харари — M Мир — 1973 - 301 с

13Boudabbous, Y Indecomposabihty and duality of tournaments / Y Boudabbous, J Dammak, P Ule // Discrete Mathematics - 2000 - V 223 — » 1 - P 55-82

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

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

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

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

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

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

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

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

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

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

4 Описаны дополнительные структуры (структуры И7-операд, в частности, РБеЬ или Ерг-операд) на найденных операдах

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

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

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

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

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

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

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

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

Основные результаты диссертации докладывались и обсуждались на следующих конференциях: "Международная молодежная научная школа-конференция "Лобачевские чтения — 2002" в Казанском государственном университете (г.Казань, 2002 г), "Международная летняя школа-конференция "Лобачевские чтения — 2003" в Казанском государственном университете (г Казань, 2003 г.), "Третья всероссийская молодежная научная школа-конференция "Лобачевские чтения — 2003" в Казанском государственном университете (г Казань, 2003 г.), "Международная конференция,

6

посвященная 200-летию КРУ, "Алгебра и Анализ 2004" (г.Казань, 2004 г.), на семинарах кафедры алгебры КГУ в 2000-2006 гг. (руководитель — кандидат физико-математических наук, доцент С.Н.Тронин) и итоговых конференциях кафедры алгебры Казанского государственного университета им В.И.Ульянова-Ленина

Публикации.

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

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

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

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

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

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

Пусть К — некоторое множество с выделенным элементом £ шг^ = множество всех п х к — матриц с компонентами из К Определим две операции композиции Пусть Вг £ 1 < г < гтг, Л е отт>1Ш А = (а1}), 1 < з < т Операция композиции, которую будем называть композицией 1, определяется так.

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

AB\B2 -..Brr

^ Bi a12 ... aim \ Й21 B2 ... aim

y aml am2

B„

(1)

/

АВ1В2 ... Вт — блочная («14-.-. + пт) х + -.. + кт) — матрица, разбитая на блоки размерами пг х и ач в (1) — это матрица размера пг х к}, заполненная одним и тем же элементом аг] из А, т.е. ау = где

— матрица, состоящая из единиц

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

а21 0.22 В-2

АВД.. Вт =

m

Щ. m

QmmBrj

(2)

/

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

На т(п) и Ш(п) слева действует группа подстановок n-й степени £п следующим образом Бели А = (аг;), 1 < i,j < п, аг] € К, а е Еп, то матрица а А состоит из элементов

(<т A)l} = aa-i(i),<r-'(;) (3)

Определим два семейства множеств от = {ал(п)| п = 1,2,...}, Ш — {ВД|п = 1,2,...}

Теорема 1.

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

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

3) Множество а = 1J rot^fc превращается в алгебру над операдой ал, если

n,k> 1

определить композицию по формуле (1), и в алгебру над операдой т,

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

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

В главе 3 рассматриваются операды графов с несколько иной, чем в главе 2 операдной композицией' она соответствует композиции 2 из главы 1. Оказалось, что в этом случае на операдах (б, ВггС) можно ввести структуру Ерг — операды Здесь Ерг — вербальная категория, морфизмы которой — все сюръективные отображения из конечных множеств [п] = {1,...,п} в [ттг] = {1,...,то}. Действие такого отображения / на граф Геи вершинами /Г — это некоторая разновидность стягивания вершин (с последующим отождествлением ребер) Это позволяет выразить все графы через операдную композицию двух графов Г+, Гх и описанных выше действий отображений /■

Наконец, главным результатом главы 3 является следующая теорема.

Теорема 2 Многообразие А1д{0) алгебр над операдой С рационально эквивалентно многообразию алгебр с двумя бинарными операциями сложения и умножения, и с одной константой в, приче.м должны выполняться следующие десять тождества + а2 = а 2 + 0*1, а\ ■ а2 = 0.2 ■ <21;

01 + в — а\, э

ах - в — ах;

(ах + а2) + 03 = 01 + (а2 + а3);

• а2) ■ а3 = ах • (а2 • аз);

а + а = а;

а • а - а = а ■ а\

ах ■ (а2 + аз) = 01-02 + 01- о3;

О! • о2 • а3 = 01 • а2 + а2 • аз + а1 • а3.

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

Глава 4 посвящена изучению операды конечных помеченных решеток Частично упорядоченные множества и решетки можно рассматривать как частный случай ориентированных графов. Оказывается, что если Ьо, Ьх, ...,Ьп — конечные помеченные частично упорядоченные множества (ориентированные графы), то композиция 1 из главы 1 ЬдЬх... Ьп — снова частично упорядоченное множество, а если Ьа, Ь{, . Ьп — решетки, то ЬоЬх ■ ■ ■ Ьп — также решетка Обозначим через ЬаХ операду, п — ая компонента которой ЬаЬ{п) состоит из всех конечных помеченных решеток с п элементами Во втором параграфе главы 4 доказана следующая теорема

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

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

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

Теорема 4 . Если Ьх, Ь2 — нетривиальные конечные помеченные решетки, то Ь\ х 1/2 — операдно неразложимая решетка.

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

Ю

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

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

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

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

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

Теорема С Модулярная решетка с дополнениями операдно неразложима. Существуют модулярные операдно разложимые решетки, которые пред-ставимы в виде СЬ\... Ьт, где С — цепь.

Теорема 7 Пусть Ь — конечная дистрибутивная решетка. Тогда либо Ь операдно неразложил1а, либо существует и) ^ 0,1 такой, что для любого I € I либо х < ю, либо х > т. (Т.е Ь = [0,ад] и [и>, 1], в этом случае Ь разложима, и следовательно, представима в виде СЬ\... Ьт, где С — цепь, Ьг — дистрибутивная решетка, г = I,... ,т).

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

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

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

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

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

и

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

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

- №4 - С 50-60

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

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

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

- 2002.-С 81-82.

[5j Семенова, AB Операдно неразложимые решетки / A.B. Семенова // Труды математического центра имени H И Лобачевского Т19 // Теория функций, ее приложения и смежные вопросы — Казань' Казанское математическое общество — 2003. — С 195

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

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

- С. 68-69.

Отпечатано с готового оригинал-макета в типографии Издательства Казанского государственного университета Тираж 100 экз. Заказ 87/10

420008, ул. Профессора Нужина, 1/37 тел.: 231-53-59,292-65-60

Введение.

Глава 1. Операды квадратных матриц.

§ 1. Операды и алгебры

§ 2. Операды квадратных матриц

Глава 2. Операды конечных помеченных графов.

§1. Определение операды

§2. Разложимые и неразложимые неориентированные графы

§3. Операды гамильтоновых и трассируемых графов

§4. Операда ориентированных помеченных графов

Место, которое занимает теория операд в алгебре, можно кратко охарактеризовать следующим образом. В работах [1], [2] показано, что каждое многообразие универсальных алгебр рационально эквивалентно многообразию алгебр над некоторой операдой. Точнее, в [1] было введено понятие операды над вербальной категорией, и фактически речь идет о рациональной эквивалентности данного многообразия и многообразия алгебр над FSet — операдой (т.е. операдой над вербальной категорией FSet). Традиционные операды — это симметрические операды, операды над вербальной категорией Е, являющейся подкатегорией FSet. Таким образом, в первом приближении можно сказать, что теория многообразий алгебр над опера-дами — это теория обычных многообразий алгебр "по модулю "отношения рациональной эквивалентности, введенного А.И.Мальцевым [3] (см. также

4])

Характерная черта операдного подхода состоит в том, что у рассматриваемых алгебр нет изначально выделенного небольшого количества операций, и следовательно, не имеет смысла говорить о тождествах. Все необходимые для определения свойства заключены в самой операде. В различных разделах математики можно встретить множество естественных примеров операд, алгебры над которыми невозможно или трудно описать "классическими "средствами общей (или универсальной) алгебры. В книгах [5], [6], [7], [8], [9] описаны многочисленные примеры операд, возникающих в топологии, гомологической алгебре, теории категорий и даже в физике. При этом, однако, чисто алгебраические аспекты теории операд остаются несколько в стороне.

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

С другой стороны, в работах по теории графов, теории частично упорядоченных множеств и решеток невозможно найти упоминания об операдах. В частности, известные книги по "алгебраической"теории графов [10], [11] не содержат ничего даже отдаленно похожего. Наш подход заключается в том, что сами совокупности конечных (помеченных) графов, частично упорядоченных множеств и решеток являются операдами, т.е. алгебраическими объектами, и заслуживают подробного изучения.

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

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

Кроме того, операдная композиция имеет определенное сходство с агассиз-суммами Плонки (определение см. в [14], с.46; [15], с.314-315).

Наконец, можно отметить (хотя это и лежит несколько в стороне от темы нашей работы), что в теории двухполюсников ([16], ч.Ш, гл.2, пар.З) встречается множество понятий и результаты, аналогичные понятиям и результатам из теории операд. В частности, семейство двухполюсников (с помеченными стрелками) образует операду относительно указанной в [16] операции подстановки, и понятия неразложимых и разложимых двухполюсников совершенно аналогичны изучаемым в нашей работе понятиям разложимых и неразложимых графов.

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

Теперь опишем более подробно содержание работы. Работа состоит из четырех глав. В первой главе изложены все необходимые определения и некоторое количество простых примеров из теории операд. Мы используем обобщение операд, введенное в [1], — операды над вербальными категориями. Во втором параграфе первой главы содержится первый основной результат работы: конструкция операды квадратных матриц.

Пусть К — некоторое множество с выделенным элементом е. ал „д. = тщк(К) множество всех п х к — матриц с компонентами из К. Определим две операции композиции. Пусть В{ € 1 < г < т, А £ штщт,

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

АВ1В2 • ■ • Вт В\ <212 • • • т ^ й21 В2 . а2т

1) у ат1 ат2 • • • Вт J

АВ1В2 . Вт — блочная (п1+. .+пт) х(к1+. .+кт) — матрица, разбитая на блоки размерами щ X и а^ в (1) — это матрица размера щ X заполненная одним и тем же элементом ац из А, т.е. а^ = , где матрица, состоящая из единиц.

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

Л.В1В2 . Вт ацВ\ <212 • ■ • ш ^ «21 Й22-В2 . . . 0,2т

2) 0"гп1 0"т2 • • • 0"ттВт у

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

На ж(п) и т(п) слева действует группа подстановок п-й степени £п следующим образом. Если А = (а^), 1 < г,^ < г?, ац Е К, а Е то матрица <тЛ состоит из элементов сгА)у = у) (3)

Определим два семейства множеств ж = {ял(тс)| п — 1,2,.}, ж = {ж(п)\ п = 1, 2,.}.

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

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

3) Множество ш = У жп^ превращается в алгебру над операдой ж, п,к>1 если определить композицию по формуле (1), ив алгебру над операдой ж, если определить композицию по формуле (2). При этом операды от и ж надо считать несимметрическими (т.е. исключить из их определения действия симметрических групп).

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

В главе 3 рассматриваются операды графов с несколько иной, чем в главе 2 операдной композицией: она соответствует композиции 2 из главы 1. Оказалось, что в этом случае на операдах (С, ИггС) можно ввести структуру Ерг — операды (Теорема 3.1.2.). Здесь Ер1 — вербальная категория, морфизмы которой — все сюръективные отображения из конечных множеств [п] = {1,., 7г} в [ш] = {1,., т}. Действие такого отображения / на граф Теп вершинами /Г — это некоторая разновидность стягивания вершин (с последующим отождествлением ребер). Это позволяет выразить все графы через операдную композицию двух графов Г+, Гх и описанных выше действий отображений / (Теорема З.1.З.).

Наконец, главным результатом главы 3 является следующая теорема.

Теорема 3.1.4. Многообразие А1д(О) алгебр над операдой С? рационально эквивалентно многообразию алгебр с двумя бинарными операциями сложения и умножения, и с одной константой в, причем должны выполняться следующие десять тождеств: а>\ + «2 = <22 + а\ а\ • а2 = <22 • а\ а\ -+- в = «1 а\ - в = а\ (аг + а2) + а3 = аг + (а2 + а3) («1 • а2) • аз — «1 ' («2 • «з) а + а — а а • а ' а = а • а

Q>i • («2 + аз) = <3,1 • 02 + oi • аз ai • а,2 • аз = • «2 + «2 • аз + ai • аз

Аналогичный результат справедлив для ориентированных графов (Теорема 3.2.1.), но в этом случае Гх представляет собой граф вида

1 2

Справедливы те же тождества, кроме тождества а\ ■ а,2 = а,2 • а\

Глава 4 посвящена изучению операды конечных помеченных решеток. Частично упорядоченные множества и решетки можно рассматривать как частный случай ориентированных графов. Оказывается, что если Lq, ., Ln — частично упорядоченные множества (ориентированные графы), то композиция 1 из главы 1 LoLi. Ln — снова частично упорядоченное: множество (Теорема 4.1.3), а если Lo, L\, ., Ln — решетки, то LqL\ . Ln — также решетка (Теорема 4.1.1). Обозначим через Lat операду, п — ая компонента которой Lat{n) состоит из всех конечных помеченных решеток с п элементами. Во втором параграфе главы 4 доказана следующая теорема:

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

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

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

Теорема 4.3.1. Если Ь\, ¿2 — нетривиальные решетки, то 1/1x1/2 — операдно неразложимая решетка.

Теорема 4.3.2. Атомно порожденная конечная решетка операдно неразложима.

Теорема 4.3.3. Коатомно порожденная конечная решетка операдно неразложима.

Теорема 4.3.4. Простая конечная решетка операдно неразложима.

Теорема 4.3.5. Конечная решетка с относительными дополнениями операдно неразложима.

Теорема 4.3.6. Модулярная решетка с дополнениями операдно неразложима. Существуют модулярные операдно разложимые решетки, которые представимы в виде СЬ\. Ьт, где С — цепь.

Теорема 4.3.7. Пусть Ь — конечная дистрибутивная решетка. Тогда либо Ь операдно неразложима, либо существует и) ф 0,1 такой, что для любого х € Ь либо х < ш, либо х > ги. (Т.е. Ь = [0,го] и [и*, 1], в этом случае Ь разложима, и следовательно, представима в виде СЬ\. Ьт, где С — цепь, Ь{ — дистрибутивная решетка, г = 1,., т).

Теорема 4.3.8. Конечная геометрическая решетка операдно неразложима.

1. Тронин, С.Н. Абстрактные клоны и операды / С.Н. Тронин // Сибирский математический журнал. — 2002. — Т. 43. — № 4. — С. 924-936.

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

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

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

5. Бордман, Дж. Гомотопически инвариантные алгебраические структуры на топологических пространствах: пер. с англ. / Дж. Бордман, Р. Фогт. — М.: Мир. 1977. - 408 с.

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

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

8. Leinster, Т. Higher Operads, Higher Categories / Т. 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. — 2000. — V. 223. № 1. - P. 55-82.

14. Артамонов, В.А. Универсальные алгебры / В.А. Артамонов // Итоги науки и техники. Алгебра. Топология. Геометрия. — М.: ВИНИТИ. — 1989. 27. - С. 45-124.

15. Общая алгебра / В.А. Артамонов и др.]. — М.: Наука. — 1991. — Т.2 480 с.

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

17. Smirnov, V.A. Simplicial and Operad Methods in Algebraic Topology / V.A. Smirnov // American Mathematical Society, Translations of Mathematical Monographs. 2001. - V. 198. - 235 p.

18. Локально гамильтоновы графы / Д. Катона, А. Косточка, Я. Пых, Б. Стечкин // Математические заметки. — 1989. — Т.45. — № 1. — С. 36-42.

19. Лекции по теории графов / В.А.Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич. — М.: Наука. — 1990. 384 с.

20. Гретцер, Г. Общая теория решеток / Г. Гретцер. — М.: Мир. — 1981. -456 с.

21. Биркгоф, Г. Теория решеток: пер. с англ. / Г. Биркгоф. — М.: Наука.- 1984.- 566 с.

22. Айгнер, М. Комбинаторная теория: пер. с англ. / М. Айгнер. — М.: Мир. 1982 - 558 с.

23. Харари, Ф. Перечисление графов / Ф. Харари, Э. Палмер. — М.: Мир.- 1977. 328 с.

24. Тронин, С.Н. Матричные линейные операды / С.Н. Тронин, O.A. Копп // Известия высших учебных заведений. Математика. — 2000. — № 6.- С. 53-62.

25. Тронин, С.Н. Операды в категории конвексоров. I. / С.Н. Тронин // Известия высших учебных заведений. Математика. —- 2002. f 3. -С. 42-50.

26. Тронин, С.Н. Операды конечных графов и гиперграфов / С.Н. Тронин // Труды математического центра им. Н.И.Лобачевского. Т.5. // Актуальные проблемы математики и механики. — Казань: Изд-во "Уни-пресс". 2000. - С. 207-208.

27. May, J.P. The geometry of iterated loop spaces / J.P. May // Lecture Notes in Mathematics. — 1972. — V. 271. — 175 p. (Русский перевод — в 5], С. 267-403).

28. Ginzburg, V. Koszul duality for operads / V. Ginzburg, M. Kapranov // Duke Mathematical Journal. 1994. - V. 76. - № 1. - P. 203 - 272.

29. Ginzburg, V. Erratum to "Koszul duality for operads"/ V. Ginzburg, M. Kapranov // Duke Mathematical Journal. — 1995. — V. 80. № 1. -P. 293.

30. Operads: Proceedings of Renaissance Conferences / J.-L. Loday, J.D. Stasheff and A.A. Voronov (Eds.) // Contemporary Mathematics. — 199G.- V. 202.- 443 p.

31. Kapranov, M. Operads and Algebraic Geometry / M. Kapranov // Documenta Mathematica, Extra Volume ICM II. 1998. - P. 277-286.

32. Kapranov, M. Modules and Morita Theorems for Operads / M. Kapranov, Yu.Manin // American Journal of Mathematics. — 2001. — V. 123. — №5.- P.811-838.

33. May, J.P. Operads, algebras and modules / J.P. May // Contemporary Mathematics. 1997. - V. 202. - P. 15-31.

34. Loday, J-L. La renaissance des operades / J-L. Loday // Asterisque. — 1996. V. 237. - P. 47-74.

35. Kriz, I. Operads, algebras, modules, and motives / I. Kriz, J.P. May // Asterisque. 1995. - V. 233. - P. 1-137.

36. Getzler, E. Operads, Homotopy algebra, and iterated integrals for double loop spaces / E. Getzler, J.D.S. Jones // Preprint hep-th/9403055. 1993. -70 p.

37. Артамонов, В.А. Клоны полилинейных операций / В.А. Артамонов // Успехи математических наук. — 1969. — Т. 24. — Вып. 1. — С. 47-59.

38. Кузьмин, Е.Н. Неассоциативные структуры / Е.Н. Кузьмин, И.П. Ше-стаков // Современные проблемы математики фундаментального направления. М.: ВИНИТИ. - 1990. - 57. - С. 179 - 266.

39. Levit, V.E. On hereditary properties of composition graphs / V.E. Levit, E. Mandrescu // Discussiones Mathematicae Graph Theory. — 1998. — V. 18. №. - P. 183-195.

40. Ozievich, Z. Operad of Graphs, Convolution and Hopf Algebra / Z. Ozievich // Contemporary Mathematics. — 2003. — V. 318. — P. 175197.

41. Троиин, C.H. Операды конечных помеченных графов / С.Н. Тронин, A.B. Семенова // Известия высших учебных заведений. Математика.- 2004. т. - С. 50-60.

42. Семенова, A.B. Алгебры над операдой конечных помеченных графов / A.B. Семенова // Известия высших учебных заведений. Математика.- 2006. №6. - С. 65-73.

43. Семенова, A.B. Операда конечных помеченных решеток / A.B. Семенова // Известия высших учебных заведений. Математика. — 2008. — т. С. 77-80.

44. Семенова, A.B. Операда конечных помеченных решеток /A.B. Семенова // Труды математического центра имени Н.И. Лобачевского. Т. 18 // Лобачевские чтения — 2002. — Казань: Казанское математическое общество. 2002. — С. 81-82.

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

46. Семенова, A.B. Алгебры над операдой графов / A.B. Семенова // Труды математического центра имени Н.И. Лобачевского. Т. 23. // Алгебра и анализ — 2004. — Казань: Казанское математическое общество. 2004. - С. 68-69.Казанский государственный университет