Операды конечных помеченных графов и решеток

• Автор: Семенова, Алена Валерьевна
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Казань
• Количество страниц: 109 с. : ил.

Оглавление
Введение
Глава 1. Операды квадратных матриц
§ 1. Операды и алгебры
§ 2. Операды квадратных матриц
Глава 2. Операды конечных помеченных графов
§1. Определение операды
§2. Разложимые и неразложимые неориентированные графы
§3. Операды гамильтоновых и трассируемых графов
§4. Операда ориентированных помеченных графов
Приложение. Таблицы неразложимых графов с числом элементов
не больше шести
Глава 3. Алгебры над некоторыми операдами конечных помеченных графов
§1. Алгебры над операдами конечных помеченных неориентированных графов
§2. Алгебры над операдами конечных помеченных ориентированных
графов
Глава 4. Операда конечных помеченных решеток
§1. Определение операды
§2. Общие факты о неразложимых и разложимых решетках
§3. Некоторые классы неразложимых решеток
Приложение. Таблица неразложимых решеток с числом элементов
не больше семи
Литература

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

ботах по теории операд эта тематика практически полностью отсутствует.
С другой стороны, в работах по теории графов, теории частично упорядоченных множеств и решеток невозможно найти упоминания об операдах. В частности, известные книги по "алгебраической"теории графов [10], [11] не содержат ничего даже отдаленно похожего. Наш подход заключается в том, что сами совокупности конечных (помеченных) графов, частично упорядоченных множеств и решеток являются операдами, т.е. алгебраическими объектами, и заслуживают подробного изучения.
Интересно отметить, что этот подход возник все-таки не совсем на пустом месте. Частный случай той операции (операдной композиции), которая превращает семейство конечных помеченных графов в операду, был давно известен как "сумма Зыкова"([12], с.36).
С другой стороны, в теории круговых турниров также давно известны понятия, являющиеся частными случаями композиции в операдах графов, частично упорядоченных множеств и решеток, а также (операдно) неразложимых элементов в этих операдах (см. [13]).
Кроме того, операдная композиция имеет определенное сходство с агассиз-суммами Плонки (определение см. в [14], с.46; [15], с.314-315).
Наконец, можно отметить (хотя это и лежит несколько в стороне от темы нашей работы), что в теории двухполюсников ([16], ч.Ш, гл.2, пар.З) встречается множество понятий и результаты, аналогичные понятиям и результатам из теории операд. В частности, семейство двухполюсников (с помеченными стрелками) образует операду относительно указанной в [16] операции подстановки, и понятия неразложимых и разложимых двухполюсников совершенно аналогичны изучаемым в нашей работе понятиям разложимых и неразложимых графов.
Таким образом, наша работа лежит на стыке теории операд, теории многообразий универсальных алгебр, теории графов и теории решеток. Изу-

Не исключается, что r{j) = j, но, по крайней мере, d(x,z) > 3. Однако из d(x,ÿi) + d(ÿi,z) > d(x,z) > 3 следует, что одно из чисел d(x, у,-), d(ÿi,z) строго больше единицы, противоречие. Допустим теперь, что г — транспозиция, т(г) = к, т(А:) = г и r(j) = j при j ф г, А:. При п > 3 такое число j существует. Сравнивая х, ÿj = ÿr(fc), = ÿr(i), = ÿr(i) с z, заключаем, что z и ÿj различаются сразу в трех компонентах: г - й, j - й и /с - й. Полученное противоречие показывает, что в ПРИ п > 3 не существует подграфа, изоморфного KPt4, удовлетворяющего условию из теоремы 2.2.3.
Пример 2.2.2. Опишем разлагающие фрагменты в деревьях. Будем называть вершину дерева Т внешней, если ее степень равна единице, и внутренней в противном случае. Гроздью в дереве Т назовем поддерево Т' с вершинами гд, V
Утверждается, что наличие гроздьев в дереве равносильно наличию разлагающих фрагментов. Точнее, если Т' — гроздь, Т* — дискретный подграф с вершинами {vi
Обратно, пусть (Т',Т*) — разлагающий фрагмент Т. Пусть v