Свойства отношения сопряжения в алгебрах инцидентности тема автореферата и диссертации по математике, 01.01.06 ВАК РФ
факультета Московского М.В.Ломоносова. Научные руководители:
государственного университета имени
доктор физико-математических наук, профессор В.Н.Латышев, доктор физико-математических наук, профессор А.В.Михалёв.
доктор физико-математических наук, профессор И.Б.Кожухов, кандидат физико-математических наук, доцент И.Н.Балаба.
Московский педагогический государственный университет
Зашита диссертации состоится "14" января 2005 года в 16 часов 15 минут на заседании диссертационного совета Д.501.001.84 в Московском государственном университете имени М.В.Ломоносова по адресу: 119992, ГСП-2, Москва, Ленинские горы, МГУ, механико-математический факультет, ауд. 14-08.
С диссертацией можно ознакомиться в библиотеке механико-математического факультета МГУ (Главное здание, 14 этаж)
Автореферат разослан "14 " декабря 2004 года.
Ученый секретарь диссертационного совета
Д.5О1.ОО1.85 в МГУ, /^/О доктор физико-математических наук,
профессор ^ / В.Н. Чубариков
ОБШДЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы. Пусть - локально конечное частично
упорядоченное множество (ЧУМ). Алгебра инцидентности локально конечного частично упорядоченного множества (Ру'й) над полем Б, обозначается 1пс,,(Р,й), была введена в рассмотрение в середине 60-х годов прошлого века как естественный инструмент комбинаторного анализа. Это направление исследований было начато циклом работ Дж.-К. Рота и его школы под общим названием «Основы комбинаторной теории»: Рота1; Рота, Муллин2; Голдман, Рота3; Дубиле, Рота, Стенли4; Дубиле5; Рота, Каха-нер и Одлизко6. На русском языке была также опубликована работа Барна-беи М., Брини А., Рота Дж.-К.7, примыкающая к этой серии.
Позднее было замечено, что алгебра инцидентности сама является интересным объектом для изучения. Начало исследований алгебраических свойств алгебр инцидентности было положено работами Дубиле, Рота и Стенли4; Баклавского8; Фаркаса9. Эти работы вызвали большой интерес и положили начало многочисленным исследованиям в этой области. Алгебры инцидентности изучались Начевым10 и Шматковым11. В работах Начева
1 Рота (Rota G.-C.) On the foundations of combinatorial theory. I: Theory of Mttbius functions. - Z. Wahrscheinlichkeitstheor. und verw. Geb. - 1964. - 2. - p. 340-368.
2 Рота, Муллин (Rota G.-C., Mullin R.) On the foundations of combinatorial theory. Ш: Theory of binomial enumerations. - Graph Theory and its Appl. -N.Y. Acad. Press. - 1970. - p.167-213.
3 Голдман, Рота (Goldman J, Rota G.-C.) On the foundations of combinatorial theory (TV): Finite Vector Spaces and Eulerian Generating Functions. - Stud. In Appl. Math. - 1970. - 49, №3. - p.239-258.
4 Дубиле, Рота, Стенли (Doubilet P., Rota G.-C., Stanley R.) On the foundations of combinatorial theory (VI): The idea of generating function. - Proceedings of the Sixth Berkely Symposium on Mathematical Statistics and Probability. - v.II. - University of California Press. - 1972. - p. 267-318. [Имеется перевод: в книге «Перечислительные задачи комбинаторного анализа», под редакцией Г.П. Гаврилова. - М.: Мир. -1979.]
5 Дубиле (Doubilet P.) On the foundations of combinatorial theory (VII): Symmetric functions through the theory of distribution and occupancy. - Studies Appl. Math. - 51.-1972. - p.377-396.
6 Рота, Каханер и Одлизко (Rota G.-C., Kahaner D. and Odlyzko A.) On the foundations of combinatorial theory VI: Finite operator calculus in "Finite operator calculus" - N.Y. Acad. Press. - 1975.
7 Барнабеи М., Брини А., Рота Дж.-К. Теория функций Мёбиуса. - Успехи мат. наук.- 1986-т.41, вып. 3(249).-с. 113-157.
8 Баклавски (Baclawski К.) Automorphism and derivations of incidence algebras. - Proc. Amer. Math. Soc.-1972.-v. 76. №2.-p.351-356.
9 Фаркас (Farkas D.R.) Radicals and primes in incidence algebras. - Discrete Math. - 10. - 1974. -p. 257-268.
10 Начев (Nacev NA) [ 1]Полиномиальные тождества в алгебрах инцидентности. - Успехи математических наук. - т.32. - 1977. - с.233-234. [2]The global dimension of incidence rings, I, П. - Plovdiv. Univ. Nauchn. Trud. -18. -1981. -p. 19-4 1,43-63.
" Шматков В. Д. Изоморфизмы алгебр инцидентности. - Дискретная математика, М.: РАН, 1991, тЗ, в. 1, с. 133-134.
ГОС. НАЦИОНАЛЬНАЯ БИБЛИОТЕКА
изучались полиномиальные тождества, глобальная размерность и другие вопросы. В работах Шматкова изучались изоморфизмы алгебр инцидентности, свойства алгебр бинарных функций и изоморфизмы алгебр бинарных функций.
В последнее время появилось много работ посвященных изучению алгебраических свойств алгебр инцидентности локально конеч-
ного частично упорядоченного множества (Р,й). Например, в книге Шпигеля и О'Доннела12 подробно рассмотрены функции Мёбиуса, редуцированные алгебры, радикалы, максимальные идеалы, минимальные простые идеалы, дифференцирования и изоморфизмы, а также кольцевые свойства алгебр инцидентности.
На алгебры инцидентности можно смотреть как на обобщение полных матричных алгебр и, поэтому, естественно переносить свойства матриц на функции инцидентности. Например, в книге Р. Стенли13 поставлен вопрос: «Есть ли разумный критерий для определения того, когда два элемента алгебры инцидентности сопряжены, (по аналогии с теорией канонической формы Жордана)?». Ответ на вопрос Стенли в настоящее время не известен и, по-видимому, для каждого частичного порядка может быть свой ответ. Например, алгебра верхних треугольных матриц над полем может рассматриваться как простейшая алгебра инцидентности конечного линейно упорядоченного множества. Для этой алгебры ответ на вопрос Стенли в настоящее время, по-видимому, не известен. В работе получен ряд результатов, отвечающих на вопрос Стенли, для произвольных алгебр инцидентности. Вопрос о сопряжённости функций инцидентности зависит от трёх факторов: структуры частично упорядоченного множества, свойств поля Ж и свойств самих функций инцидентности. Вообще говоря, аналога жордановой канонической формы для функций инцидентности не существует. Для некоторых функций инцидентности таким аналогом могут быть диагонали и функции, обозначаемые (функцию можно
считать аналогом жордановой клетки, определённой в теории матриц).
1) Исследование свойств сопряжения в алгебрах инцидентности с помощью разложений функций инцидентности в дизъюнктные суммы. Изучение функций инцидентности, сопряженных с диагональными функциями. Нахождение условий коммутируемости диагонализируемых функ-
12 Шпигель, О'Доннел (Е. Spiegel, C .J. O'Donnel) Incidence algebras. - New York, Basel, Hong Kong, 1997.
13 Стенли (Stanley R.P.) Enumerative combinatorics. - v.l. - Wadsworts, Inc. California. - 1986. [Имеется перевод: Стенли Р. Перечислительная комбинаторика. - M.: Мир, 1990].
ций инцидентности. Описание одновременно диагонализируемых семейств функций.
2)Описание функций инцидентиосш, сопряжённых с функцией Се + ¿¡<ш. Изучение сопряжения в алгебрах инцидентности 1псг(Р,<), для которых: все интервалы ЧУМ - цепи, или ЧУМ (Р,й) - линейно упорядоченное множество, или ЧУМ (Р,£) есть произведение ЧУМ длины 1 на ЧУМ, все интервалы которого согласованы с ранговой функцией.
3) Изучение ЧУМ (Р,£) для которых
^ в алгебре 1псг(Р,<) и вычисление рангов некоторых комбинаторных матриц.
4) Матричная интерпретация указанных выше результатов.
Структура диссертации. Диссертация состоит из введения, семи
параграфов и списка литературы. Параграфы разбиты на пункты. Полный объём диссертации - 102 страницы. Библиография включает 53 наименования.
Научная новизна. Основные результаты диссертации являются новыми. Решены следующие важные проблемы.
1) Доказано, что любая функция инцидентности сопряжена с дизъюнктной суммой функций, постоянных на диагонали и принадлежащих «меныним» алгебрам инцидентности. Таким образом, вопрос о сопряжении функций в алгебре можно свести к вопросу о сопряжении дизъюнктных слагаемых, постоянных на диагонали, в «меньших» алгебрах инцидентности.
2) Установлен критерий диагонализируемости для функций, являющихся диагонально 5 -выпуклыми. В частности, если значения функции на главной диагонали попарно различны, то функция сопряжена с диагональю, что является аналогом известной матричной теоремы.
Для диагонализируемых функций найдены условия коммутируемости и одновременной диагонализируемости, обобщающие известные матричные теоремы. Доказано, что для диагонально <-выпуклых функций, условия коммутируемости и одновременной диагонализируемости эквивалентны. Доказано, что семейство диагонализируемых и коммутирующих функций (состоящее из диагонально £ -выпуклых функций) является одновременно диагонализируемым семейством.
3) Для различных видов частично упорядоченных множеств найдены условия, при выполнении которых функция / сопряжена с аналогом жор-дановой клетки Се+С^- Для некоторых классов функций эти условия дают критерии сопряжённости. Доказано, что функции и сопряжены для классических частично упорядоченных множеств. Исследованы ЧУМ,
для которых функции ¿¡„. и сопряжены. Найдены контр-примеры, показывающие, что функции и сопряжены не для всех ЧУМ.
4) Даны применения полученных выше результатов к вычислению рангов некоторых комбинаторных матриц и к установлению новых свойств верхних треугольных матриц.
Основные методы исследования. В диссертации применяются как известные алгебраические и комбинаторные методы, так и новые. Например, новым является метод дизъюнктнвгх сумм, которым получены многие результаты работы.
Практическая и теоретическая ценность. Работа носит теоретический характер. Полученные в ней результаты и разработанные методы могут найти применения в алгебрах инцидентности и различных разделах комбинаторного анализа.
Апробация работы. Основные результаты работы неоднократно докладывались на алгебраических семинарах МГУ им. М.В. Ломоносова, на V Международной конференции «Алгебра и теория чисел: современные проблемы и приложения» (2003 г.), на VII и VIII международных семинарах «Дискретная математика и её приложения» (2001 г., 2004 г.), на XII Международной конференции «Проблемы теоретической кибернетики» (1999 г.).
Публикации. Основные результаты диссертации опубликованы в б работах автора. Их список приведен в конце автореферата. Работ, написанных в соавторстве, нет.
В работе используется терминология, принятая в книгах Айгнера14, Бирк-гофа15, Гретцера16, КАРыбникова17 и Стенли14.
Содержание параграфа 1.
В §1 определены и исследованы понятие выпуклой вложимости частично упорядоченных множеств и понятие частично упорядоченного множества, все интервалы которого согласованы с ранговой функцией. Также
14 Айгнер (М. Aigner) Combinatorial Theory. - Grundlehren Math. Wiss. 234, Springer - Werlag, Berlin. - 1979. [Имеется перевод: Айгнер М. Комбинаторная теория. - М.: Мир, 1982.]
15 Биркгоф (G. Birkhoff) Lattice theory. - Providence, Rhode Island. - 1967. [Имеется перевод: Биркгоф Г. Теория решёток. - М.: Наука, 1984.]
Гретцер (G. GrStzer) General lattice theory. - Akademie-Verlag Berlin. -1978. [Имеется перевод: Гретцер Г. Общая теория решеток. - М.: Мир, 1982.]
7 Рыбников К.А. Введение в комбинаторный анализ. - МГУ. -1985.
в §1 рассмотрены частично упорядоченные множества частичных порядков длины <1.
В пункте 1.1 приведены основные понятия частично упорядоченных множеств. Все результаты работы относятся к локально конечным частично упорядоченным множествам. Вместо выражения «частично упорядоченное множество (Р,й)» мы будем в дальнейшем использовать сокращение «ЧУМ (Р,<,)». В пункте 1.2 рассмотрены классические частично упорядоченные множества и их свойства, используемые в работе.
В пункте 13 вводится понятие выпуклой вложимости частично упорядоченных множеств, которое в дальнейшем играет важную роль. Пусть и (N,<) - локально конечные ЧУМ. Будем говорить, что ЧУМ (N,ü) выпукло вложимо в ЧУМ (Р,й), если существует инъекция такая, что - выпуклое подмножество в ЧУМ
В этом пункте также рассмотрены свойства выпуклой вложимости классических ЧУМ.
В пункте 1.4 вводится понятие частично упорядоченного множества, интервалы которого согласованы с ранговой функцией. Интервалы градуированного ЧУМ будем называть согласованными с ранговой функцией р, если из условий aüb, c<d, р(а) = р(с), p(b) = p