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

• Семенова, Алена Валерьевна
• кандидат физико-математических наук
• 2008

Оглавление диссертации кандидат физико-математических наук Семенова, Алена Валерьевна

Введение.

Глава 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. Конечная геометрическая решетка операдно неразложима.

Список литературы диссертационного исследования кандидат физико-математических наук Семенова, Алена Валерьевна, 2008 год

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.Казанский государственный университет