Свойства отношения сопряжения в алгебрах инцидентности тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

На правах рукописи УДК512.552.7,512.562,519.1

МАРЕНИЧ Валентина Евгеньевна

СВОЙСТВА ОТНОШЕНИЯ СОПРЯЖЕНИЯ В АЛГЕБРАХ ИНЦИДЕНТНОСТИ

01.01.06 - математическая логика, алгебра и теория чисел

АВТОРЕФЕРАТ

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

Москва-2004

Работа выполнена на кафедре высшей алгебры механико-математического

факультета Московского М.В.Ломоносова. Научные руководители:

Официальные оппоненты:

Ведущая организация:

государственного университета имени

доктор физико-математических наук, профессор В.Н.Латышев, доктор физико-математических наук, профессор А.В.Михалёв.

доктор физико-математических наук, профессор И.Б.Кожухов, кандидат физико-математических наук, доцент И.Н.Балаба.

Московский педагогический государственный университет

Зашита диссертации состоится "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{d) следует, что соответствующие уровневые числа интервалов ([o,¿]s,á) и (d]s, <, ) совпадают.

Содержание параграфа 2.

В §2 изучаются свойства функций инцидентности.

В пункте 2.1 приведены основные определения и понятия теории алгебр инцидентности. Обозначим: F- поле, GF{q) - конечное поле, содержащее q элементов. Пусть incF(P,ü) - множество всех функций инцидентности, определённых на множестве РхР и принимающих значения в поле F. Обозначим символом IncF(P,¿) алгебру функций инцидентности, а символом е - единичный элемент из IncF{P,<), определённый следующим образом: е(а,Ь) = 1, если a = b\ е(а,Ь) = 0, если а^Ь.

Для конечного ЧУМ (P,¿) и функции f eincF(Pt¿)t обозначимсим-волом - матрицу, которую будем называть матри-

цей функции Для функции обозначим

ранг матрицы

Функции f,geincF(P,ü) называются сопряжёнными в алгебре IncF{P,<), пишем f ~ g , если существует функция х е incF(P,<) такая,

что x'i*f*x = g.

Если Т- бинарное отношение на множестве Р, содержащееся в частичном порядке то дзета-функция ¿¡Т отношения Т определена равенствами: £т(а,Ь) = 1,если аТЬ\ ¿¡т(а,Ь) = 0, если (а,Ь)еТ.

В пунктах 2.2 и 23 вводится и исследуется понятие дизъюнктной суммы функций инцидентности. Пусть семейство множеств {Рв\аеВ}, где В - некоторое множество индексов, образует разбиение множества Р. Рассмотрим ЧУМ (Ра,<а), где ае/) и частичный порядок <а есть сужение частичного порядка й на множество Рв. Будем говорить, что функция g е¡псг(Р,<) есть дизъюнктная сумма функций ga е¡псР(Ра,<), где аеИ, если:

g(u,v) = gll{u,v) при и,у принадлежащих одному множеству Ра\

£(и,у)=0 в остальных случаях. Пишем g = ® ga•

В пункте 2.4 вводится понятие функции инцидентности, значения которой согласованы с ранговой функцией. Пусть - локально конеч-

ное градуированное ЧУМ с ранговой функцией

Будем говорить, что значения функции / €тср(Р,й) согласованы с ранговой функцией если для любых из того, что

р(а) = р(с) и р(Ь) = р(с1) следует, что /(а,Ь) = /(с,</).

Примерами функций, значения которых согласованы с ранговой функцией, являются: е, ¿¡к, (¡<.

Содержание параграфа 3.

В §3 изучаются свойства сопряжения функций инцидентности.

В пункте 3.1 показано, что любую функцию /ешсДР,^) можно «упростить» при помощи сопряжения (теорема 3.3.1). Для функции / е ЫсР(Р,<) определены множества:

= {ге Р| /(г,г)=а} для любого а е £>(/).

Семейство множеств Рв{/), ае1){/), образует разбиение множества Р. Следующая теорема является основным результатом пункта 3.1.

Теорема 3.1.1. Любая функция /€тСр(Р,й) сопряжена в алгебре с дизъюнктной суммой некоторых функций ,

где элемент а € Щ/), и ga{z,z) = а для любого г е Ра{/). •

Функцию / ешсД/*,^) будем называть диагонально <- выпуклой, если множества Ра{/) является <■• выпуклыми для всех а е £*(/).

По теореме 3.3.1 функция /сопряжена с некоторыми функциями вида Если функция / является диагонально выпуклой, то

среди всех таких функций § можно выбрать некоторую «каноническую» функцию, как показывает следующая теорема.

Теорема 3.1.2. Пусть функция /етсДР,^) диагонально выпуклая. Тогда функция / сопряжена с дизъюнктной суммой своих сужений на частично упорядоченные множества (Ра(/),£), то есть где

функции /в - сужения функции / на ЧУМ . •

Теоремы 3.1.1 и 3.1.2 лежат в основе метода дизъюнктных сумм, используемого в дальнейшем для изучения функций инцидентности.

В пункте 3.2 показано, что не существует аналога жордановой формы матрицы для произвольной функции инцидентности. Любая функция из алгебры инцидентности конечного множества задаётся матрицей. Поэтому естественно возникает вопрос: существует ли аналог жордановой формы матрицы для произвольной функции инцидентности? Таким аналогом естественно считать некоторую функцию инцидентности, у которой вне главной диагонали расположены только нули и единицы. В лемме 3.2.1 показано, что если и не все интервалы ЧУМ (.Р,£) являются

цепями, то существуют функции / ете^Р,^), которые нельзя подобием преобразовать к функциям, имеющим вне главной диагонали только нули и единицы. Таким образом, ответ на поставленный вопрос отрицательный.

В пункте 3.3 доказано, что хотя в алгебрах инцидентности, вообще говоря, отсутствует аналог жордановой формы матрицы, тем не менее, в алгебре 1псг(Р,<I) можно указать аналог жордановой клетки. Таким аналогом является функция

Содержание параграфа 4.

В §4 изучаются функции инцидентности, сопряженные с диагональными. Пусть функция

Буцем называть / диагональной функцией (или диагональю), если /(а,Ь) = 0 для всех а#Ь.

Будем называть / диагонализируемой функцией, если она сопряжена с диагональной функцией

В пункте 4.1 доказан следующий критерий диагонализируемости.

Теорема 4.1.1. Пусть функция / е диагонально < - вы-

пуклая. Следующие утверждения равносильны.

1) Функция / диагонализируема. 2) /а= /(а,а)еа для всех аеО(/). • Друтами словами, функция / диагонализируема тогда и только тогда, когда её сужения /а на множества Ра(/)*Ра(/) являются диагоналями для любых . Таким образом, вопрос о диагонализируемости функции / б 1пср(Р,<) в алгебре 1пср(Р,£) сводится к рассмотрению сужений в меньших алгебрах инцидентности 1псР(Ра,йа). Требование диагональной й - выпуклости функции ,/ существенно. Следствием теоремы 4.1.1 является следующий результат.

Теорема 4.1.2. Пусть функция /б2). Если /(а,а)^/(Ь,Ь) для всех аФЬ, то функция / диагонализируема. •

Теорема 4.1.2 есть обобщение известной теоремы линейной алгебры: матрица порядка п, имеющая п попарно различных собственных значений, сопряжена с диагональной матрицей.

В пунктах 4.2 и 43 методом дизъюнктных сумм получены теоремы 4.2.1 и 4.3.1 - аналоги известных матричных теорем, приведённых, например, в книге Хорн, Джонсон18 (теоремы 1.3.12 и 1.3.19), для функций инцидентности и семейств функций инцидентности.

Теорема 4.2.1. Пусть функции /^втсг(Р,й) диагонализируемы. Справедливы следующие утверждения.

1)Если / и § одновременно диагонализируемы, то они коммутируют.

2) Если g диагонально < - выпуклая, а также /и § коммутируют, то / и § одновременно диагонализируемы. •

Для функций /и g, имеющих различные значения на главной диагонали, понятия коммутируемости и одновременной диагонализируемости совпадают.

Пусть семейство Сд,тсг{Р,<). Семейство б

называется

одновременно диагонализируемым семейством, если существует функция такая, что для любой функции , Функ-

ция х диагонализирует семейство О. Семейство О называется семейством коммутирующих функций, если любые две функции семейства О коммутируют.

Теорема 4.3.1. Пусть - конечное ЧУМ, О- семейство диагона-лизируемых, коммутирующих функций. Если все функции семейства О

11 Хорн, Джонсон (Horn R.A., Johnson C.R.) Matrix analysis. - Cambridge University Press. -1986. [Имеется русский перевод: Матричный анализ. - М.: Мир. -1989].

диагонально <- выпуклы, то G- одновременно диагонализируемое семейство. •

Из теоремы 4.3.1 непосредственно вьшодится следующий результат.

Следствие 43.1. Пусть (Р,£)- конечное ЧУМ, GcincF(P,<) - семейство таких функций #,что g{a,a)* g{b,b) для всех а * b .Семейство G- семейство коммутирующих функций тогда и только тогда, когда G-семейство одновременно диагонализируемых функций. •

Содержание параграфа 5.

В §5 изучаются функции инцидентности, сопряжённые с функцией Се + £"<■> где С = const. Как было отмечено в §3, в алгебрах инцидентности, вообще говоря, нет аналога нормальной жордановой формы матрицы, но есть аналог жордановой клетки. Аналогом жордановых клеток в алгебрах инцидентности являются функции Се + ¿¡<ш.

В пункте 5.1 доказана основная теорема (теорема 5.1.1), описывающая класс функций, сопряжённых с функцией Се + ¿¡к- в алгебрах инцидентности локально конечных частично упорядоченных множеств (Р,й),, удовлетворяющих некоторым условиям. Условия, наложенные на ЧУМ [Р, Ü), носят достаточно общий характер, в том смысле, что им удовлетворяют многие классические ЧУМ, играющие важную роль в алгебре и комбинаторном анализе.

Введём следующие обозначения. Пусть Ър - множество значений

ранговой функции р. Если р(а) = к, p{b) = к+п, то уровневые числа интервала ([a,6]s, 5» ) определяются следующим образом: wr(k,n)=w,(k,n) = \ {z\ze[a,b\,\p(z)-p(a)\ = r) | для г = 0,1,...,и.

Будем писать, что wr(k,n)*0 в поле F, если характеристика поля charF не делит число wr(k,n).

Значения функции f sincF(P,É) согласованы с ранговой функцией р, если для любых aib, cüd из того, что р(а) = р(с), p(b) = p(d) следует,что f{a,b) = f(c,d).

Теорема 5.1.1. Пусть (Р,<>)■• градуированное, локально конечное ЧУМ, все интервалы которого согласованы с ранговой функцией, в поле F для всех Пусть

функция обладает свойствами: для всех

а € Р\ f(a,b) * 0 для всех а<-Ь ; значения функции f согласованы с ранговой функцией. Тогда / ~ Се + ¿¡<щ в алгебре IncF (Р, S). •

Для некоторых функций инцидентности теорема 5.1.1 даёт простой критерий сопряжённости, приведённый ниже.

Следствие 5.1.1. Пусть ЧУМ (Р,й) удовлетворяет условиям теоремы 5.1.1, а функции /.^ешеДР.^) обладают свойствами: одна из функций /,£ является диагонально <, - выпуклой; значения функций /,£ согласованы с ранговой функцией; /{а,Ь)Ф0 и g(a,b)фO для всех а<-Ь. Тогда f ~ g в алгебре 1псг{Р,<?) равносильно условиям £>(/) = Г>{£) = И И Р„(/) для всех аб£.1»

Многие важные функции инцидентности сопряжены с функцией

В пункте 5.4 доказано уточнение результатов пункта 5.1 для линейно упорядоченного множества (ДУМ). •

Теорема 5.4.1. Пусть (Р,й) - локально конечное линейно упорядоченное множество; функция / обладает свойствами: /(а,а) = со/и? = С для всех аеР; /{а,Ь)Ф0 для всех а<-Ь. Тогда /~Се+в алгебре 1псе{Р,й), •

Из теоремы 5.4.1. следует критерий сопряжённости диагонально < - выпуклых функций для ЛУМ.

Следствие 5.4.1. Пусть (Р,й) - локально конечное линейно упорядоченное множество; функции обладают свойствами: одна из функций f,g является диагонально £ - выпуклой; /(а,Ь)*0 и g(a,b)*0 для всех а<-Ь. Тогда f ~g в алгебре 1псг(Р,й) равносильно ДЛ=Д£) = Д и />„(/) = Р^) ;ш всех аей. •

В пункте 5.5 доказана основная теорема (теорема 5.5.1), описывающая класс функций, сопряжённых с функцией + ^ в алгебрах инцидентности локально конечных ЧУМ где есть произведение ЧУМ длины 1 на ЧУМ, все интервалы которого согласованы с ранговой функцией. В этом случае, ЧУМ не является, вообще говоря, частично упорядоченным множеством, все интервалы которого согласованы с ранговой функцией. Поэтому результаты этого пункта не следуют из предыдущих и требуют отдельных доказательств.

Содержание параграфа 6.

В §6 изучаются частично упорядоченные множества (Р,^)), для которых функции сопряжены в алгебре

В пункте 6.1 введено понятие частично упорядоченного множества, обладающего дзета-свойством.

Будем говорить, что ЧУМ (Л<) обладает дзета-свойством над полем Г,если в алгебре IncF(P,<,).

Теорема 6.1.1. Пусть локально конечное ЧУМ (Р,<) обладает свойствами: все интервалы ЧУМ (?,<) согласованы с ранговой функцией; |J5й0, ¡^[([a^^.^j^O в поле F, для всех интервалов [a,6]ä ранга mtl. Тогда ЧУМ (Р,<;) обладает дзета-свойством над полем F. •

Из теоремы 6.1.1 следует, что многие классические решётки обладают дзета-свойством. Любое ЧУМ (Р,<), где |,Pj ^ 5» обладает дзета-свойством над любым полем F. Найдены примеры ЧУМ, не обладающих дзета-свойством. Например, ЧУМ (Л^). диаграмма Хассе которого изображена на Рис.1, не обладает дзета-свойством над любым полем F.

Рис. 1 Рис. 2

В пунктах 63 и 6.4 вычисляются ранги некоторых комбинаторных матриц. Если конечное частично упорядоченное множество (Р,£) обладает дзета-свойством над полем F, то rankF т(С< ,Р,Р) = rankF ,Р,Р).

Ранги функций С< и С<- совпадают не для всех частично упорядоченных множеств. Для ЧУМ (/*,<), диаграмма Хассе которого приведена

ни Рис.2, указанное гавенство невевно. так как 10 = rankF т{£< ,Р,Р)* rankF , Р, Р) = 11,

над любым полем F.

Содержание параграфа 7.

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

Автор выражает глубокую благодарность своим научным руководителям д.ф.-м.н. профессору Виктору Николаевичу Латышеву и д.ф.-м.н. профессору Александру Васильевичу Михалёву за всестороннюю поддержку, постоянный интерес и внимание к работе.

ПУБЛИКАЦИИ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

Основные результаты диссертации опубликованы в следующих работах автора.

1) Маренич В.Е. Отношение сопряжение в алгебрахинцидентности. - Проблемы теоретической кибернетики (тезисы докладов XII Международной конференции, ч. 2) - М.: МГУ -1999.- с. 148.

2) Маренич В.Е. Свойства отношение сопряжения функций инцидентности. - Материалы VII Международного семинара «Дискретная математика и ее приложения», ч.З - М.: МГУ - 2001. - с.384 -386.

3) Маренич В.Е. Условия диагонализируемости и коммутируемости диагонализируемых функций инцидентности. - Вестник Московского Университета, сер.1, Математика. Механика. 2003. №2 - с. 12-14.

4) Маренич В.Е. Свойства сопряжения в алгебрах инцидентности. -Фундаментальная и прикладная математика. Вып. 3. Том 9 (2003). — с. 111123.

5) Маренич В.Е. Жорданова каноническая форма некоторых функций инцидентности. - Тезисы докладов V Международной конф. «Алгебра и теория чисел: современные проблемы и приложения. - Тула - 2003. -с.153-154.

6) Маренич В.Е. О дзета-свойстве частично упорядоченных множеств. - Материалы VIII Международного семинара «Дискретная математика и ее приложения», М.: МГУ - 2004. - с.213 -216.

■ I

(

Издательство ЦПИ при механико-математическом факультете МГУ им. М.В. Ломоносова. Подписано в печать ¿5, Н. ОЦ Формат 60x90 1/16. Усл. печ. л. /,0

Тираж 100 экз. Заказ 4/

Отпечатано с оригинал-макета на типографском оборудовании механико-математического факультета

JÎ--973

Введение.

§1 Частично упорядоченные множества. п.1. Предварительные сведения о частично упорядоченных множествах. п.2. Классические частично упорядоченные множества. п.З. Выпуклая вложимость частично упорядоченных множеств. п.4. Частично упорядоченные множества, интервалы которых согласованы с ранговой функцией. п.5. Частично упорядоченные множества частичных порядков длины <1.

§2 Дизъюнктные суммы функций инцидентности. п.1. Предварительные сведения об алгебрах инцидентности. п.2. Дизъюнктные суммы. п.З. Сопряжённость дизъюнктных сумм. п.4. Функции инцидентности, значения которых согласованы с ранговой функцией.

§3 Основные свойства сопряжения в алгебрах инцидентности. п.1. Сопряжённость функций инцидентности дизъюнктной сумме. п.2. Невозможность сведения функций инцидентности подобием к функциям, у которых вне главной диагонали расположены 0 и 1. п.З. Функция Се + йкак аналог жордановой клетки.

§4 Функции инцидентности, сопряжённые с диагональными. п.1. Диагонализируемые функции инцидентности. п.2. Условие коммутируемости диагонализируемых функций инцидентности. п.З. Одновременно диагонализируемое семейство функций.

§5 Функции инцидентности, сопряжённые с Се + п.1. Основная теорема. п.2. Отношение сопряжения в алгебре IncF(P, <), где (Р, <) - локально конечное частично упорядоченное множество, все интервалы которого - цепи I. п.З Отношение сопряжения в алгебре IncF{P,<), где (Р,<) - локально конечное ЧУМ, все интервалы которого - цепи, II. п.4. Отношение сопряжения в алгебре IncF(P,<), где (Р,<) - линейно упорядоченное множество. п.5. Произведение частично упорядоченного множества длины 1 на частично упорядоченное множество, все интервалы которого согласованы с ранговой функцией.

§6 Частично упорядоченные множества (Р,<),для которых £ ~ С, в алгебре 1пср{Р,<). п.1. Дзета — свойство частично упорядоченного множества. п.2. Построение частично упорядоченных множеств, обладающих дзета - свойством. п.З. Ранги комбинаторных матриц. п.4. Частично упорядоченное множество подмножеств, мощности которых кратны числу т.

§7 Матричная интерпретация.

Пусть (Р,<) - локально конечное частично упорядоченное множество (ЧУМ). Алгебра инцидентности локально конечного частично упорядоченного множества (Р, <) над полем F, обозначается Incр (Р, <), была введена в рассмотрение в середине 60-х годов прошлого века как естественный инструмент комбинаторного анализа. Это направление исследований было начато циклом работ Дж.-К. Рота и его школы под общим названием «Основы комбинаторной теории»: Рота [1964]; Рота, Муллин [1970]; Голдман, Рота [1970]; Дубиле, Рота, Стенли [1972]; Дубиле [1972]; Рота, Каханер и Одлизко [1975]. На русском языке была также опубликована работа Барнабеи М., Брини А., Рота Дж.-К. [1986], примыкающая к этой серии.

Позднее было замечено, что алгебра инцидентности сама является интересным объектом для изучения. Начало исследований алгебраических свойств алгебр инцидентности было положено работами Дубиле, Рота и Стенли [1972]; Баклавского [1972]; Фаркаса [1974]; Лерукса и Сараилле [1981]. Эти работы вызвали большой интерес и повлекли за собой многочисленные исследования в этой области. Алгебры инцидентности изучались Начевым [1972], [1981,1], [1981,11] и Шматковым [1991], [1994, I], [1994, И]. В работах Начева проводились исследования полиномиальных тождеств, глобальной размерности и других вопросов, которые были продолжены многими авторами, например, Шпигелем [2001]. В работах Шматко-ва изучались изоморфизмы алгебр инцидентности, свойства алгебр бинарных функций и изоморфизмы алгебр бинарных функций.

В последнее время появилось много работ, посвящённых изучению алгебраических свойств алгебр инцидентности IncF(P,<) локально конечного частично упорядоченного множества (Р,<). Например в книге Шпигеля и О'Доннела [1997] подробно рассмотрены функции Мёбиуса, редуцированные алгебры, радикалы, максимальные идеалы, минимальные простые идеалы, дифференцирования и изоморфизмы, а также кольцевые свойства алгебр инцидентности.

На алгебры инцидентности можно смотреть как на обобщение полных матричных алгебр и, поэтому, естественно переносить свойства матриц на функции инцидентности. Например, в книге Р. Стенли [1986, рус. перевод, с.235] поставлен вопрос: «Есть ли разумный критерий для определения того, когда два элемента алгебры инцидентности сопряжены, (по аналогии с теорией канонической формы Жордана)?».

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

• Доказано, что любая функция инцидентности сопряжена с дизъюнктной суммой функций, постоянных на диагонали и принадлежащих «меньшим» алгебрам инцидентности (пункт 3.1, теоремы 1,2). Таким образом, вопрос о сопряжении функций в алгебре Incp (Р, <) иногда можно свести к вопросу о сопряжении дизъюнктных слагаемых, постоянных на диагонали, в «меньших» алгебрах инцидентности (пункт 3.1, замечание 1).

• Установлен критерий диагонализируемости для функций, являющихся диагонально <-выпуклыми (пункт 4.1, теорема 1). В частности, если значения функции на главной диагонали попарно различны, то функция сопряжена с диагональю, что является аналогом известной матричной теоремы (пункт 4.1, теорема 2).

• Для диагонализируемых функций, найдены условия коммутируемости и одновременной диагонализируемости, обобщающие известные матричные теоремы (пункт 4.2). Доказано, что для диагонально <-выпуклых функций, условия коммутируемости и одновременной диагонализируемости эквивалентны (пункт 4.2, теорема 1). Доказано, что семейство диагонализируемых и коммутирующих функций (состоящее из диагонально < -выпуклых функций) является одновременно диагонализируемым семейством (пункт 4.3, теорема 1).

• Для различных видов частично упорядоченных множеств найдены условия, при выполнении которых функция / сопряжена с аналогом жордановой клетки Се + для некоторых классов функций эти условия дают критерии сопряжённости (пункты 5.1-5.4). Доказано, что функции С)< и сопряжены для классических частично упорядоченных множеств (пункт 6.1). Исследованы ЧУМ, для которых функции С3< и С,<4 сопряжены. Найдены контр-примеры, показывающие, что функции С3< и сопряжены не для всех ЧУМ (пункт

6.1).

• Даны применения полученных выше результатов к вычислению рангов некоторых комбинаторных матриц и к установлению новых свойств верхних треугольных матриц (§7).

В диссертации применяются как известные алгебраические и комбинаторные методы, так и развитые автором методы работы в алгебрах инцидентности, например, метод дизъюнктных сумм, с использованием которого получены многие результаты работы.

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

Структура диссертации. Диссертация состоит из введения, семи параграфов и списка литературы. Полный объём диссертации - 102 страницы. Библиография включает 50 наименований.