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

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М.В.Ломоносова

Механико-математический факультет

Т8 ОЛ

На правах рукописи Уда 519.1

МАРЕНИЧ Евгений Евгеньевич

АЛГЕБРЫ БИНАРНЫХ ФУНКЦИЙ НА УПОРЯДОЧЕННЫХ МНОЖЕСТВАХ

/ 01.01.09 - математическая кибернетика /

АВТОРЕФЕРАТ

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

Москва - 1996

Работа выполнена на механико-математическом факультете Мо ковского государственного университета имени М.В.Ломоносова.

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

профессор К.А.Рыбников

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

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

Ведущая организация - Московский педагогический государс] венный университет.

Защита диссертации состоится 1997 года

в 16 час. 05 мин. на заседании диссертационного совета Д.053.05.05 при Московском государственном университете имени М.В.Ломоносова по адресу: 119899, Москва, ГСП, Воробьёвы горы, МГУ, механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке механико-математического факультета МГУ /Главное здание, 14 этаж/.

Автореферат разослан

199<"2года.

Учёный секретарь диссертационного совета Д.053.05.05 при МГУ, доктор физико-математических наук, профессор: ^ / В.Н.Чубариков

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность теш. Современное состояние комбинаторного анализа во многом определено циклом работ Ж.-К.Рота, его учеников и сотрудников под общим названием "Основы комбинаторной теории". Начало цикла положено в 1964г. работой Рота . Одна из основных идей Цикла состоит в том, чтобы объектом изучения в комбинаторном анализе сделать частично упорядоченные множества, а инструментом их изучения - алгебры инцидентности этих множеств. Изучение алгебр инцидентности локально конечных частично упорядоченных множеств было начато в в связи с задачей вычисления функций Мёбиуса частичного порядка. Функции Мёбиуса и обращение Мёбиуса для частичного порядка были открыты независимо Уайснероы и Ф.Холлом, исходя из задач теории групп и даны в полной общности Уордом К 1964г. было известно, что доказательства ряда далёких друг от друга результатов, например, перечисление элементарных абелевых подгрупп конечной р -группы и теоремы Дилуорса о покрытиях в конечной модулярной решётке основаны на функциях Мёбиуса. С работы Рота ^началось систематическое изучение теории функций Мёбиуса частичного порядка. Отметим по этой тематике работу . В работе Б.С.Стечкина ^ открыты теоремы вложения.

Систематическое изучение алгебр инцидентности начато в работе Дубиле, Рота и Стенли . Цель работы разработка теории производящих функций, исходя из понятия алгебры инцидентности. В работе ' Стенли доказал теорему, называемую "теорема Стенли", которая утверждает, что если изоморфны алгебры инцидентности локально конечных частично упорядоченных множеств, то изоморфны и сами частично

I/ Rota. G-.-C. On ike foundaJ-i-опл of comtiin&ictiAB ihzoty. I : tkeoztf- of HofcuA fundicru. - 2. Wahu&leui£<:ck&&itszeclincaig- u. irett<f. G&B. --t96(,.-v.l.-P.Mo-36S.

2/ IVa,id M. The авзебгсь of 'ваИСсе function*. - Okie ffaXA J -M39. - S, - P. SSI-311.

3/ Барнабеи M., Брини А., Рота Ж.-К. Теория функций Мёбиуса. - Успехи мат.наук. -1986. -т.41, вып. 3/249/. -С. II3-I57. 4/ Стечкин Б.С. Теоремы вложения для Мёбиус-функций. - Доклады АН СССР. - 1981. -т.260, 5? I. - С. 40-43.

5/ Douiie&i P., Stcudey R., Rata. С,-С. Сл. the jouhjcdcond o-f u>m^na.iozia£. ЬНеощ (v^)^. the U ел of genetatc'hp -junction . -P?ocee<U'HfS of the Sixth Bet £ sty Symposium on, НаХАете^е'слв SiaXlitiCi and PtcgagifUiy , VniStr-Utfr of Ci&fozni^ Pte44 W71. - v.lt.-p. 261 -3if.

упорядоченные множества. Теорема Стенли положила начало многочисленным исследованиям в этой области. Работы ^'^содержали и другие алгебраические результаты, например, в них была вычислена группа автоморфизмов и охарактеризовала решётка двусторонних идеалов некоторых алгебр инцидентности.

Редуцированные алгебры инцидентности локально конечных частично упорядоченных множеств были определены Дубиле, Рота и Стенли в

Применение редуцированных алгебр инцидентности к вычислению функций Мёбиуса и к решению перечислительных задач начато в работах В 1981 году Харрисон, Лонгстаф в ^и независимо Крейгл в ^ нашли простой критерий редуцированности, /в предполагалось, что простого критерия не существует./

В работах Финча Б.С.Стечкина несингулярных бинарных

отношений определены функции Мёбиуса, доказаны различные обобщения обращения Мёбиуса. Б.С.Стечкиным в 'было начато изучение алгебр бинарных функций в связи с задачей вычисления функций Мёбиуса. В 9/,I0/ПОСТрОенй те0рИЯ вычисления функций Мёбиуса несингулярных отношений с помощью операторов замыкания, связей Галуа, /т.е. теория, обобщающая известные теоремы Ф.Холла и Ж.-К.Рота /.

В данной работе найдены новые свойства отношений частичного порядка, пересечения, непересечения, накрытия и дополнения с помощью алгебр бинарных функций; т.е. работа содержит материал, относящийся к "Алгебраической комбинаторике" в современном понимании. Такой подход позволяет исследовать под одной комбинаторной "крышей" следующие задачи: I/ изучение сингулярности бинарных отношений и функций Мёбиуса несингулярных бинарных отношений; 2/ изучение алгебраических свойств различных алгебр бинарных функций; 3/ вычисление

6/ 5tan£ey R. ИгсосХиле of incidence а-вчевгал and thelb a-utonwipJiiitn atoupt. - s>u£ß. Атег. Maik. Soc. - 1910. - a 76. • P. 1236- 1239 .

7/ Halation X.L., Lohjjj-itcuff W.E. SuBdicjе£глг о/ incidence аЛ-$евга4 ¿eieznu.net ву еуистГа.£епс& геЕаХсопб . - J. Comtfin. Ткеог# . А . - 19S1. - 31. • Р.94-д?\

8/ ktieql A. A cAcbbactetiiaXcon of zeduced incidence a£$e-бгал. - Dcictete Matfi. - W1. - P.

9/ Finch P.D. On ike Hofaus - junction о/ л поп, - ¿ittfu-Ca,^ Ginaty te&x&on. - BuBB, Auttiaß-. Hath. Soc. - /770 - 3 - P ISS- 161.

Ю/Стечкин B.C. Бинарные функции на упорядоченных множествах.-Труды Математического института АН СССР.- 1977. -т.143. -С. 178-186.

рангов матриц инцидентности бинарных отношений; 4/ изучение дей- ' ствия группы на частично упорядоченном множестве; 5/ перечисление решений систем уравнений в конечных решётках; б/ перечисление дваж-дыстохастических квадратных матриц с целыми элементами. Отметим нетрадиционные "выходы" предложенного подхода на традиционные математические задачи, такие как изучение групп автоморфизмов алгебр, изучение свойств конечных р -групп и др.

Одной из основных формул для вычисления функций Мёбиуса частичного порядка является формула Ф.Холла, выражающая функцию Мёбиуса через число цепей. Б.С.Стечкиным в работе ^ было замечено, что формула Ф.Холла остаётся справедливой для функций Мёбиуса некоторых бинарных отношений, не являющихся частичным порядком, при этом суммы, встречающиеся в формуле Ф.Холла, заменяются на сумму ряда по Цуасону. В поставлен вопрос об объяснении этого явления.

Нахождение границ значений функций Мёбиуса для частичных порядков - известная комбинаторная задача, возрастающий интерес к которой обусловлен рядом причин: I/ большим значением функций Мёбиуса для комбинаторики; 2/ тем, что коэффициенты многих многочленов, например, хроматического многочлена графа, характеристического многочлена частично упорядоченного множества, выражаются через функцию Мёбиуса; 3/ тем, что многие комбинаторные величины выражаются через функцию Мёбиуса частичного порядка, например, приведённая эйлерова характеристика симплициальных комплексов, значения дзета-многочлена. Для частичнкх-порядков границы значений функций Мёбиуса начали изучаться в для решёток - в этой проблематике существует несколько гипотез, доказательства которых пока не найдены./ В работах Баклавского , Фейнберга Шматко-ва В.Д. теорема Стенли была обобщена на алгебры и кольца инцидентности бинарных отношений, не являющихся частичными порядками.

Сингулярность отношений непересечения, накрытия и их функции Мёбиуса ранее не изучались, хотя некоторые результаты, например, в

II/ Маренич Е.Е. Границы значений функций Мёбиуса.-Матем.заметки. - 1988. -т.44, в.4. - С. 469 - 48?.

12/ Scketd H. ивег die HdêiuA-ftcfiction, Un&b êota£- елЯШь&ъ HaeSotdtiLuu}. - J. Cerné. Theoztf -~ P. US-33< . 13/ Bacia.'uiifU к.. Autonwzphiàni. а/Ы. de-tiifqXioni о/ tncidenœ а£аевга&. -Ргос. Am.et. Hcdh. Soc. - /972.-v. MZ.-P. 351-3S6. 14/ FeinJSetg- /?. Fcu.ihjiti diittiSuXive hboduE&i отГег, incidence, tte^egzaé. - Pctujic. J. HcuCh. - <Я6. - iT. Cf. - P. 3415/ Шматков В.Д. Изоморфизмы алгебр инцидентности. -Дискретная математика. -1991. -т.З, в.1. - С. 133 - 144.

работах Дубиле Доулинга, Вильсона можно прочитать в терминах функций Мёбиуса этих отношений. В неявной форме в ^ вычислена Функция Мёбиуса отношения непересечения, доказано обращение Мёбиуса для отношения непересечения, доказано, например, что коэффициенты разложения симметрической функции через элементарные симметрические выражаются через функцию Мёбиуса отношения непересечения в решётке разбиений конечного множества. В неявной форме ,в вычислена функция Мёбиуса отношения накрытия и доказано обращение Мёбиуса.для отношения накрытия.

то/ то/ 20/

После работ Дембовского ; Кантора ; Кунга , стало понятным значение для комбинаторного анализа вычисление рангов матриц инцидентности для решёток. В ранги матриц инцидентности применены для доказательства теорем, характеризующих модулярные геометрические решётки через уровневые числа, в ^- для доказательства теоремы Ди-луорса о покрытиях в конечной модулярной решётке; в для изучения действия группы автоморфизмов частично упорядоченного множества; в ' ^ - для доказательства существования специальных отображений в частично упорядоченном множестве /" nwdxMii^. "/; в ^^J-для доказательства теорем экстремальной теории множеств.

Начало систематическому изучению действия группы автоморфизмов частично упорядоченного множества положено работами Дембовского Кантора Стенли ^í. - •

16/ О о и. ê¿Cet P. On, tke {oicnJaítoru of co/nêin<i£oiùci£, ikeox^ ( vu ) ; 4ymmetz¿c JunctionÁ ih-tougL o{ tke theotg. o-f dcótzíéu,-íóorv лпА Оссиралсу. - StuJce¿ ¿л. Appêced H<dhenuUcc6 - WZ -is. LI, V¿f.

17/ Po-uf&ag T. A., ШвбОП R.M- Whötftep Hcanßct úi&jua.6ct¿c¿ ■(оь ^omsf/iic ¿adUcei. - Рюс. А тег. Hatk. Soc. - -i US. - 41. -P.fo<t-fi2.

18/ OenSonfii¿ P. Fùnite $eom,etz¿ei . - ßet&fi-He¿<jeC¿e.z#'-Л/ew- Yotí ; Spungei. - 6 g.

19/ КапХоъ W. M. Oiv ¿tiuAence ma¿t¿ce¿ oj -f¿n¿te p^'eoU^e

W aflttie spiceó. - Ma¿i. 2. - /2ï.- P. 315-51&.

20/ Kufig. . - J. ObJet. - ieSS. -Z. - P. <05- HZ .

21/ FzaJikô P., M&Sofb R.M. JhteueoUon, ÜeozemA ^¿tL geoniet-

tÀc conieyu eitcei. - Com/ifuUoucA,. - i (1 í ). - Р. 357 - 5 £ s.

22/ РюлН P. Ih¿ei¿ec¿¿oh, tkeotenuL atv¿ ncd p tan,k o-f ¿hc&t-

Áóotv tnaX'uces. - J. Со mi. îhe<fty A. - iïeo. -54. - P. 85- gij '

23/ Stcudaj. P.P. Sonte а&ресХл о/ gtoap ¿uctùif on, Jcníte po¿eü>.-J. Cond. Jheozy A . - Í38Z. - 12.- Р. Ш- 16 i .

Множество орбит действия группы автоморфизмов естественным образом превращается в частично упорядоченное множество. Комбинаторный аспект рассматриваемой проблематики, выявленный работами 18/,19/, состоит в изучении свойств частично упорядоченного множества орбит.

Решение многих комбинаторных задач сводится к перечислению решений систем уравнений в конечных решётках. Для применения первой и второй теорем Ж.-К.Рота о сечении,^ нужно уметь перечислять решения некоторых систем уравнений. Для доказательства теоремы Ди-луорса о покрытиях в конечной модулярной геометрической решётке, по Райвелу и Гантеру нужно знать свойства решений некоторых систем. К перечислению решений систем уравнений приводят задачи перечисления дополнений, перечисление' независимых систем атомов в конечных решётках и т.д.

Кени Мано исследовал Н(л- ,Ъ) - число способов, которыми л-различных предметов, / ft/У /, каздый взятый t раз, / tí/V /» могут быть распределены в равных количествах между П/ лицами. Число Н(И ,t) можно также интерпретировать как число пг/ь матриц ОII с целыми неотрицательными элементами, удовлетворяющих условию: .

* л

Г 4¡ - Г ^ - . - . ш

Во'всех'последующих работах по данной тематике И (к ,t) - это число матриц указанного вида. Ананд, Дамир, Гупта в ^ выдвинули гипотезу, /гипотеза АДГ/: для данного /ь и любых t :

(&-Ü(tt-Z)/Z

= г с, ПГш) > i-0 *" /2/

где C¿ зависит только от ft , t . Гипотеза АДГ доказана Р.Стенли

и Е.Эрхартом в ^í По поблематике, связанной с гипотезой АДГ

24/ Gantet 8., ¡¡¿Иа.в 1 . 0¿¿-uJotüt'¿ cerftving -theozem job nodu.-fab ¿a&íces : & ¿¿mpie ptoof. - A foe&zet Ün¿vez¿a£¿¿. -1^73. - 3. - P.3H-350 .

25/ кпалА hj., Oumit V.C., Gupta. H. A ccm£¿naM>i¿aB ¿ióíuSuiton pío6£em . - Duñc H<dk. J. - - I/. 33,- P. 7St-770. 26/ Stan6ey R. P.^Lin^ai котодспеоси, d¿oph¿int¿n.e e^cc¿itíotvá ati¿ tna-fíc Ше&,ид<5 ¿f jzaph¿. - Dcrfe Math. J. -1973,- VAo. - p. 6oj -6 3 2.

27/ Eht-hatt E. Зиг fes слъгеб tnaa¿Que. - С. R. AcaJ. Sc¿. Pai¿6

S¿z. A . ~ i3?3. - V. 21?. - P.

и её обобщением, существует* обширная литература.

Пусть H (Т)(и ,z) - число игл матриц I/ йу |/ с целыми неотрицательными элементами, удовлетворяющих /I/, и таких, что для всех (с,/) é Т , Т - фиксированное множество мест, ¿¿j = 0. Из работы Р.Стенлиследует, что Н(Т)(л ,г) , при фиксированных Т и Л/ является многочленом от г . Отметим использование коммутативной алгебры в ^^ для доказательства этого утверждения.

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

I/ Исследование отношений частичного порядка, пересечения, непересечения, накрытия и дополнения с помощью алгебр бинарных функций, применения несингулярности и функций Мёбиуса этих отношений. 2/ Вычисление группы F -автоморфизмов алгебр инцидентности отношений, не являющихся частичными порядками.

3/ Исследование свойств редуцированных алгебр инцидентности бинар-. ных функций и их применение к изучению действия группы автоморфизмов частично упорядоченного множества, к решению перечислительных задач.

4/ Перечисление решений уравнений в конечных решётках, комбинаторные применения. ., ... 5/ Комбинаторное перечисление дваждыстохастических квадратных матриц с целыми неотрицательными элементами и его применение.

Структура диссертации. Диссертация состоит из введения, четырёх глав и списка литературы. Первая глава состоит из 3 параграфов, вторая - из 3, третья - из 5, четвёртая - из 4. Параграфы разбиты на пункты. Полный объём диссертации 219 страниц. Библиография включает 155 наименований.

Научная новизна. Все основные результаты диссертации являются новыми. Решены следующие важные проблемы:

1.Найдены точные границы значений функций Мёбиуса для частичных порядков и некоторых других отношений.

2. Вычислена группа F-автоморфизмов алгебр инцидентности отношений, не являющихся частичными порядками. Доказаны: равенство групп автоморфизмов алгебры и группоида, новые свойства групш F-автоморфизмов над частичными порядками и "квазипорядками.

3. Исследована сингулярное;'!, отношений пересечения, непсресечегля, накрытия, дополнения и даны их многочисленные приыеш-ния.

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

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

5. Разработан метод решения систем уравнений в конечных решётках, с помощью которого перечислены образующие булевой алгебры, перечислены дополнения в некоторых решётках, вычислены числа (j -Стир-линга.

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

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

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

Апробация работы. Основные результаты работы неоднократно докладывались на комбинаторном семинаре и на алгебраических семинарах МГУ им. М.В.Ломоносова, на Всесоюзных и Всероссийских семинарах и международных конференциях по дискретной математике и её приложениям, /1987 - 1996г./, на Всесоюзных и Российских международных конференциях "Современные проблемы теории чисел и её приложения", /1580 - 1996г./.

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

СОДЕРЖАНИЕ РАБОТЫ.

В главе I изучаются алгебры бинарных функций, алгебры инцидентности, группы автоморфизмов алгебр инцидентности, функции Мёбиуса. В n.I.I.I собраны основные понятия и обозначения, используемые для частично упорядоченных множеств. Для пе /У , f ft-] = ¿I,... —, ч) , (.г] = {О,..., л} . F - поле', FÍO) - поле характеристики нуль. Если (Р ,() - градуированное частично упорядоченное множество ранга л- с ранговой функцией р , то для ке (п,] : SaiK -= {sí Р, р(г)4к], í°pK = {г I г<гр, р(г)?к}, = {г|ztP,рс?)=к].

Цусть 1Г - конечное п. -элементное множество, тогда Ви&1п) = -= Ви£(и) - решётка подмножеств множества I/ . Пусть и - я--мерное векторное пространство над , тогда Ип(п. = Lin.IV)-решёт-

ка линейных подпространств пространства 1Г, Л// (п-1 } = А{{(1/) - решётка аффинных подпространств пространства и . В.п.1.1.2 собраны основные понятия и обозначения, используемые для алгебр бинарных функций 9лпр1Р) • Обозначим: - дзета-функция бинарного отношения; ру = Функция Мёбиуса несингулярного бинарного отношения Т ; е = . В п. 1.1.3 дано обобщение формулы Ф.Холла, выражающей функцию Мёбиуса частично упорядоченного множества через число цепей. Пусть Т - бинарное отношение на конечном множестве Р ,

,..., Д5 - корни минимального многочлена матрицы НХг(а>#)-е(«,ё)1и,вбР' & - их кратности.

Теорема 1.1.3.1 Цусть Т - рефлексивное отношение на Р . Если Т несингулярно на Р над £ и для ¿г СЯ » то

где последний ряд суммируем по Пуасону.

Для частичного порядка, /3/ есть формула Ф.Холла. Теорема

I.1.3.1 содержит ответ на вопрос Б.С.Стечкина

В §1.2 находятся границы значений функций Мёбиуса некоторых отношений. В п.1.2.1 райдены точные значения для. границ функций Мёбиуса частичного порядка. ^ ^

• Теорема 1.2.1.1. Для любого конечного ч.у.м. (Ь ,4) с 0 и I,

II,1 = п. + 2, ш /V , справедливы неравенства:

-РЫ) £ 10,1) £ ¿(п) , /4/

где ¿(л.) , уЗ(п) определены следующим образом: <М.П) = = пах (п.4-<)... -I), тлх берётся по к , л* таким,

что /г.,+...+й.^ = к , К - нечётно, £(*■) = тах{и-1)... (п^-1), тах берётся по К, Н,4 6/V таким, что п<+...+ пк =1 , -четно.

Числа <¿(/1) , А (а) определяются классом вычетов ил/10, которому , принадлежит и . Поэтому, для краткости, приведём только два случая из леммы 1.2.1.2.

Лемма 1.2.1.2. Пусть у(п)= 4 . Значения ¿(п.) и уЗ(п.)

определены равенствами:

I/для п= О (коЛо) , пгЮ, ¿.(п.) = ;

II/ для 1ы=0 (/■ъобю), : ■

Теорема 1.2.1.1 опубликована автором в 1988г., .В 1991году Зиглер ^нашёл точные границы для |^_<(0,1}| . Из выше доказанно1

28/ С. И. Рме& -и1с1к Но&ил -¡иисСбоп.. - У.

СатЯ. ГАесгу А . -<991. -д'6,- Р.ЫЪ-Ш.

следует, что /4/ - более точный результат, чем результат Зиглера. Самая простая часть результата Зиглера, /нахождение частично упорядоченного множества, на котором достигается максимум | ^(б,?)1 /, была анонсирована Стенли При доказательстве теоремы 1.2.1.1 использована теорема вложения Б.С.Стечкина Н В п.1.2.2 найдены точные значения для границ функции Мёбиуса градуированного частично упорядоченного множества ранга 3. В п.1.2.3 найдены точные границы значений функций Мёбиуса рефлексивного отношения, вложимого в частичный порядок.

Теорема 1.2.3.1. Пусть (Р ,Т)- конечное упорядоченное множество, Т - рефлексивное отношение, которое можно продолжить до частичного порядка на Р . Тогда - f^ 4 i i Ca.,g) < + i , где |Ео/, ilr-pl =«.+ 2, ft«^ ' -последовательность Фибоначчи.

В §1.3 изучена группа F-автоморфизмов алгебры инцидентности рефлексивно упорядоченного множества. Пусть (Р, Т) - локально конечное рефлексивное у.м., ¿¿п^1Р,Т) = . Множество Sinр (Р ,Т) относительно операции сложения и свёртки * , где

U*S)(a,i)= ST(*,e) L fla,i)f(t,f) ,

образует алгебру инцидентности }= Ben, (Р ,Т) .Обозначим У -группоид алгебры А , т.е. на ittiр (Р , Т) рассматривается только одна операция * ; Aut Sk - группа автоморфизмов алгебры Л , Aut О - группа автоморфизмов группоида 7 . Рассмотрим a ¿¿n^iP ,Т) такие, что для a., iT6 Р : clu. ,сс) - I; если а.ТтГ , то с(и,тг) 4 0; если ц.ТхгТъ/ и uTvi , то c(ec,tr)c(v = с(к,ъГ) . Определённые таким образом функции с назовём ^ подобными. Каждая подобная функция с определяет автоморфизм &(с) группоида 7 такой, что 8Cc)J = с/ для /е'&л-р (Р ,Т). Автоморфизмы 9(c) образуют группу V . Пусть "V - ассоциирующая обратимая функция из ¿¿п^ (Р , Т) такая, что t~'~ ассоциирующая функция. Отображение flz) , где является автоморфизмом t7 . Обозначим Int группу таких автоморфизмов. Каждый с из Aut(.P , Т) определяет автоморфизм 1ССг) из AutV такой, что для • ее, ire Р , (Yix)j)tu,ix) = = j(ru , ггг) . Автоморфизмы XCv) образуют• группу X .

Теорема 1.3.2.I. Пусть Т - рефлексивное отношение на Р . Справедливы утверждения: ■ .

i / Каждый автоморфизм из hid, У можно представить в виде if = = ?(r)6>(c)1>(z) , где 7(г) из Г, 9(c) из У , f(z) из IttC U/ Autl

29/Стенли Р. Перечислительная комбинаторика. - М.: Мир. - 1990.

Частными случаями теоремы 1.3.2.1 являются результаты Стенли Баклавского Фейнберга ^для алгебр инцидентности частичных порядков и квазипорядков.

Теорема 1.3.2.2. Пусть Т - рефлексивное отношение на Р . Тогда Auifi = kui У .

В п.1.3.3 - 1.3.6 даны многочисленные применения теоремы 1.3.2.1. Найдены свойства группы AcUJr , которые являются новыми даже для частичных порядков и квазипорядков. Вычислена группа Out it = Awtfi ¡IkO - группа внешних автоморфизмов алгебры £ . В случае, когда Т можно продолжить до частичного порядка, найдено каноническое разложение <gt Aui ft , аналогичное указанному в теореме 1.3.2Л, дано его применение к вычислению центра группы Auifi. Найдены новые свойства F -изоморфизмов алгебр инцидентности.

В главе II исследуется сингулярность отношений пересечения -R , непересечения - £ , накрытия - S , дополнения - С ; находятся комбинаторные следствия несингулярности этих отношений.

В §2.1 изучается сингулярность отношений R , £ , 5 , С»для несингулярных отношений вычислены функции Мёбиуса, найдены обращения Мёбиуса, рассмотрены комбинаторные применения.

В §2.2 изучаются операторы -замыкания. Найдены свойства операторов R -замыкания в атомарных решётках и описаны операторы R. -замыкания, в Bu£(U) и Lcn(U).

В §2.3 изучаются ранги комбинаторных' матриц'. Интерес к этим матрицам обусловлен работами Доулинга, Вильсона Кантора Франкла 'и др., выявивших их комбинаторное значение. Для функции / : PzF , М^, А/г с Р определим матрицу т, (j, ; f/L) = = I! ¿¿у -В п.2.3 Л и 2.3.2 изучаются ранги подмат-

риц матрицы отношения накрытия S . Обозначим /.^(5) = = \_CL\atL, .

Теорема 2.3.2.2. Пусть (L , 4) - конечная полумодулярная решётка ранга й, .Тогда для к , £ & (nl , Ki t , 1С + £ f ri' , имеем И гаккрт.{^} LFCS)nSoie , L^ntop^) = \ LFiS)fl 8otK\ . Существует инъекция f : Lp(5)060^-* L^Otop^.f,, tv<e(a) = 1 для ae LFCS)/)6otK , \LFiS)nSotK\i \ L^Otop^ \ .

Теорема 2.3.2.3. Пусть {L - конечная полумодулярная решётка ранга И . Тогда, для к , t( Сп~) , Hit К + tin. ,имеем и т.(Х£, LF(S)neotz, LF(S)f)iopn,lc) = I ¿F(S)n Sot^l .

Существует инъекция f: ^F(S)/1 SotK LF(S)nioptl_t. , a. < tfC&) для a-6 LF(S)/l8otk .

Следствием теорем п.2.3.1 и 2.3.2 являются, например, результаты Дилуорса, Грини, Доулинга, Вильсона и др. об уровневых числах геометрических решёток.

Теорема 2.3.3.2. Пусть ? - фильтр одной из решёток Butfo) , А-1{(ь -I» ?) . Тогда, для к , í'6 (ni , kiS- , кt í

i H имеем

¿/ галкт ni , ZnWr, ?/7 WR ) = I | .

Существует инъекция : fí) Щ &П W. , 4 ¿ f(¿) для a í3-f]Wr ,

Следствием теоремы 2.3.3.2 являются результаты Кантора .

В п.2.3.3 изучаются ранги подматриц матрицы отношения ¿ .

Теорема 2.3.3.3. Пусть (L , { ) --конечная полумодулярная решётка ранга it , Lj-LS) - фильтр (L , £) , для а. , Se ¿F(S), ad , интервал ([&,€]¿ , ¿ ) изоморфен Bu£(U)или Liti(U) . Тогда, для К , tí Cnl , кf"С- , к + £ ¿и. . имеем с / *япк т. С t¿ , LfCS)/¡ Wjg , LF(S)n Wt) = ILf(S)ñ Щ | .

L¿! Существует инъекция f : L/.CS)íl\^t: ¿.¡.[S)/)^ , (¿>(a) для ai L^nWyc . \LFÍS)Í}WK\ ( l LF(S)nW¿¡ .

Удобным объектом для применения указанных теорем является решётка подгрупп конечной кильпотентной группы. В п.2.3.4 предыдущие результаты применяются к изучению (Ь , í ) - решётки подгрупп конечной р -группы И . В этом случае;LpCS) - множество элементарных абелевых подгрупп группы И . Поэтому теоремы § 2.3 можно прочитать как теоремы о свойствах элементарных абелевых подгоуггп группы Н , В п.2.3.5 изучается ранговое свойство, /Стенли в ^употребляет термин "ыпрЕе"!, частично упорядоченного множества и вычисляются ранги матриц отношений < и <• .В п.2.3.6,аналогично выше изложенному, вычисляются ранги подматриц отношения R . Другие применения результатов § 2.3 даны в § 3.2.

В главе III определены и изучены редуцированные алгебры бинарных функций, решётки совместимых отношений; найдена применения редуцированных алгебр и несингулярности отношений S к исследовании действия группы на конечном частично упорядоченном множестве; редуцированные алгебры применены к перечислению маршрутов в булеане по отношениям R. , '/? ,5 ; редуцированные алгебры инцидентности применены к исследованию мультипликативных функций.■

В § 3.1 определены и исследованы редуцированные алгебры бинарных функций, решётки совместимых отношений. В п.3.1.1 вводится понятие Д -редуцированной алгебры бинарных функций Bin. р ( п , Д) , как аналог Д -редуцированных алгебр инцидентности локально конеч-

них частично упорядоченных множеств, определяются совместимые отношения А и изучаются их свойства. Совместимые отношения А на Рг над полем F образуют решётку Comp 1Р)= (comp tP), . Если IPl = h/ , то CompF(h,) = СотррСР).

Теорема 3.1.3.2. Сомрр(Р) дуально изоморфна решётке редуцированных подалгебр алгебры ВелF CP ) .

Теорема 3.1.4.1. /Критерий совместимости./ Пусть Д - отношение эквивалентности на Рг . Справедливы утверждения: ¿¿/ Д совместимо над F(0) тогда и только тогда, когда из (а/, 6) А (с ,d) следует, что существует биекция у : Р Р такая, что (а, 4) А ( с ,у(г)) , (i ,6)A(f (í) ,J) для ¿éP •

Теорема 3.1.4.1 является аналогом критерия совместимости для алгебр инцидентности локально конечного частично упорядоченного множества, известного из В п.3.1.4 с помощью критерия сов-

местимости построено семейство групп и смежных классов, характеризующее совместимое отношение Д над FC0) . В теореме 3.1.4.1 определены свойства этого семейства.

Теорема 3.1.4.2. Для не , существует вложение Comp(h,) в СоhtPq С п+ I), сохраняющее отношение покрытия.

В §3.2 исследуется действие группы G на частично упорядоченном множестве (P,¿) . Пусть Ш(Р, 4) - группа автоморфизмов С Р , ¿) , G ¿ Aut (Pi.<) • В п.3.2.1 определяется частичный порядок на oié^P"где Oíé^P - множество орбит действия G на Р . В п.3.2.2 определяются совместимые отношения á(G), определённые на Рг, над F . В п.3.2.3 построен FC 0) - гомоморфизм т/г, типа Пойя, f :' &¿h,F(o] (Р, A (G))~* &¿kF(0)(oi£c Р) . f является ¿налогом гомоморфизма, определённого Хэнлоном для алгебр инцидентности частично упорядоченного множества.-

Теорема 3.2.4.2. Пусть [L , i) - конечная^полумодулярная решётка ранга л , р - фильтр (L , £) , fr { [сь, 1)40 для ¿té f , G ¿ Áu¿(L,4), G9 = f . Тогда, для к, С i (h-1 , С , *r4+ ¿ £ £ и- имеем

L / М- Су i ) , (.fñ 6otK), ог£с (£/1 topn_K)} =

= I oz£c C?fí &ítK)\ Существует инъекция if : огё& С?Л Bot^ ) -»ог^б^&^^такая, что .Áíc(?.tÁ) для .A colé ¿(ZñSot), I слёс m iolK)\i IcnZ^m-top^l.

Теорема 3.2.4.3. Пусть (¿ , ¿) - конечная полумодулярная решётка ранга к, (а, ¿ 0 для.ai L . Тогда, для кб(п1, имеем:

с / bt**F(0) * С Г i ), огб& éote , ^ = ' 1 •

Существует инъекция f : огё.ёоС^ог^-борп_к такая, что

А <& tf № A é otß&SotK , Iotgc 6otK I ¿ loti£ top^K I . LUI \o%ê&Wi I í [ог^ I • Если G - транзитивна на , то С- транзитивна на Wi .

Следствие 3.2.4.2. Пусть (L ,é) - конечная геометрическая решётка ранга и . Тогда для ■ ке Сл.-11 > имеем ¿/ Ion¿cWr4\ < latí WK\ .

¿о/ Если & транзитивна на , то G транзитивна на Ч^ .

Следствие 3.2.4.3. Пусть (A - конечная модулярная геометрическая решётка ранга п . Тогда, для té (п."] , имеем

¡ot^U/J = lot^fl^l . /5/

Равенство /5/ для Butin), L¿ib(n ', у) было известно ранее. Теорема 3.2.4.3. Пусть ÍL ,4) - одна из решёток ВивСк), L¿n.{n,<f) , А}}1п-1,<{) , фильтр (L , , í í Ai¿t(b , , G5 = Ï . Тогда для г, te lh.~¡ , Ki t , к + £ ¿ я , имеем

с/ ълпк nt-fiXi), oxg^&nWx), crti¿&ñWt)\ =

= lotSçtfnWiU . '¿¿/ Существует инъекция if: огё^^ПЩ)-*(nß^CiFnW^) такая, что A^fí-4) для Aé огв^ (?/IWe) . U¿l l p/¡ I . Если.£ транзитивна на

?/JM/¿ » то G транзитивна на .

Для - £ = L теорема 3.2.4.3, ¿¿с / известна из Для 8u¿(k) , ? = L , доказательство t¿¿ /, или более частных утверждений, были известны ранее.

В §3.3 изучаются свойства циркулярного отношения, как элемента решётки Comp^(fc) , /свойства алгебры циркулянтов C¿t0(n.) , как элемента решётки А -редуцированных подалгебр алгебры B¿np (Р) /. В п.3.3.1 определено циркулянтное отношение AlZh) , определяющее алгебру циркулянтов, и исследован [ ^trún, » ^ÍZj] е Теорема 3,3.1.3. Справедливы утверждения: ¿ / Для Н.У, 3, решётка Comp^(Р) не градуирована.

« / Для п. г 4, решётка Сотр^ (.Р) не атомарна. .

В §3.4 определена алгебра пересечений подмножеств конечного множества и применена к перечислению маршрутов по отношениям R \ R , S в Bccâ(V), дяя IV} = п. . В §3.5 исследованы мультипликативные функции, доказаны критерии мультипликативности. Пусть (L , {) - локально конечное частично упорядоченное множество, Loa - оператор алгебры инцидентности

öc'W ¿ : -

^ ~^ ^ ъ ~ В п.3.5.1 определеш факториальные

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

Теорема 3.5.2.2. Пусть ' ^ » Я«»<0=1для

а.е Ц . Функция / является мультипликативной функцией факториального множества тогда и только тогда, когда для любой несократимой пары V) из того, что тГ не приыарен следует, что ¿о^/ (ч,^) =о •

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

В главе 1У перечисляются решения систем уравнений, связанных с изучением свойств отношений К , Ц , I , С . В §4.1 найдены общие формулы для перечисления решений систем уравнений в решётках. Пусть (А , £ ) - конечная решётка, А/£ Ь , Л'4 0 , л,ве I , т-еЛ^. Обозначим <7 (а,, £ , /у) - число решений системы: (V Х)\ла, = в'*', X £ Л/, 1Х\ = п , Теорема 4.1.3.1. Для т.е ., а,, ё е £

1 С в

Следствием теоремы 4.1.3.1 является первая теорема о сечении К.-К. Рота элементарное перечислительное доказательство теоремы Ди-луорса о покрытиях в конечной модулярной решётке Пусть ((/)-число решений системы V X =1, лХ = О, X £ Л/ , = т, . Теорема 4.1.4.1. Для ,

4 ¿0,/п (- р*<0, Г) + е1о,Т)) .

Следствием теоремы 4.1.4.1 являются формулы Крало, вторая теорема о сечении Ж.-К.Рота ^ и многие другие комбинаторные результаты.

В §4.2 перечисляются-решения-систем уравнений в Цл(Х1),где У -п. -мерное векторное пространство над ) . Следствием теорем

4.2.1.1 и 4.2.2.2 являются формулы для вычисления чисел п - Стир-

30/ Са^ееъ 3. ОВ&ь ¿¿е. АгьгаЛЗ- еггеидепЛеt Непдеп, ¿и, енА&скеа \/ек£огхамеп . - Аш. НаХА. - А/аХхсгиУС4б. Ои^гЬ. АкаА. Шм. -. - с. 11-31 .

линга - SH и результаты Циглера ^, в п.4.2.2 изу-

чается тождество Карлица. Исследуя абелевы группы, Карлиц открыл

тождество, связывающее гауссовы и биномиальные коэффициенты: m

CL = Т (г) FM ,

t=n

где F (г ,h.) заданы рекуррентным соотношением. В п.4.2.2 найдена точная формула для вычисления F(/n ,ц) . В п.4.2.3 найдены рекуррентные формулы для перечисления решений системы «/см,(илх) = Ь , dini{VAt)~ s , dt/кг =t в Lîk(W. В п 4.2.4 найдены новые свойства отношения дополнения в Ltn(V).

В §4.3 перечисляются решения систем уравнений в решётке разбиений Pazt(V), где U- конечное множество, IUI = п . В п.4.3.1 найдены формулы для перечисления образующих булевой алгебры iZv, U, и ,') где ' - операция дополнения, V - конечное множество. В п.4.3.3 перечисляются дополнения в PaVt(V).

В §4.4 комбинаторно перечисляются дваждыстохастические квадратные матрицы с- целыми неотрицательными элементами. Теорема 4.4.1.1. Для ъ ,П(т/V ,

s сг-<)... (t-i+fi

Н(Т)С*;*)= £ DJct) 1) -.

S = f

Для (T). O^IT) найдены комбинаторные интерпретации. Например, dn(TI равно рангу некоторой системы матриц перестановок. Применяя результаты Р.Стенли найдена формула для вычисления ¡¿Л(Т) > В п.4.4.2 вычисляются ранги систем матриц перестановок. В п.4.4.3 Н(Т) ( h » -t) выражено через число цепей в некотором частично упорядоченном множестве. В п.4.4.4 установлена связь Н(Т)(и,г) с перманентами (0,1) -матриц, вычислены суммы вида

где суммирование ведётся по (0,1) -матрицам m порядка ilxh , имеющих нули в предписанных местах и перманент которых равен 0, S(n) -- число единиц в т. .

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

1. Маренич Е.Е. Арифметические функции и их свойства. - Известия Воронежского гос. пед. института. - 1980. -т.201. - С. 5 - 22.

2. ?Иаренич Е.Е. Суммирование значений арифметических функций. -Ма-тем. сборник. Новая серия. - 1982. -т. II8/I60/5. - С. 50 - 73.

3. Маренич Е.Е. Об одной задаче С.Улама. - Известия высших учебных заведений. Серия: Математика. - 1983. - К0 5. - С.60.

4. Маренич Е.Е. Факториальность проективного предела факториальных колец. - Украинский математический журнал. - 1989. - т.44, К? 9.

- С. 1231 - 1234.

5. Маренич Е.Е. Критерии мультипликативности в теории чисел и комбинаторике. -Материалы всесоюзной конференции:"Теория чисел и её приложения." - Тбилиси. - Т985. - С. 153 - 155.

6. Маренич Е.Е. Мультипликативные функции локально конечных частично упорядоченных множеств. Критерии мультипликативности. -Матем. заметки. - 1990. - т.47, в.1. - С. 105 - 114.

7. Маренич Е.Е. Границы значений функций Мёбиуса. -Матем. заметки.

- 1988. - т.44, в.4. - С. 469 - 487.

8. Маренич Е.Е. Обратимость бинарных функций. -Матем. заметки.

- 1992. - т.52, в.5. - С. 78 - 82.

9. Маренич Е.Е. К -автоморфизмы алгебр бинарных функций. -Матем. заметки. - 1994. - т.55, в.6. - С. 90 - 102.

10. Маренич Е.Е. Перечисление матриц определённого вида. - Комбинаторный анализ. - 1909. -в.8. - М.: МГУ. - С. 114 - 123.

11. Маренич Ё.Е. Сравнения по простому модулю для числа (0,1) --матриц. - Дискретная математика. -1990. -т.2, в.З. - С. 153-157.

12. Маренич Е.Е. Комбинаторный подход к перечислению дваждысто-хастических матриц с целыми неотрицательными элементами. - Дискретная математика. - 1993. - т.5, в.З. - С. 90 - 101.

13. Маренич Е.Е. Ранговое свойство. - Тезисы докладов Международной конференции "Современные проблемы теории чисел и её приложения". - Тула. - 1996. - С. 97.

14. Маренич Е.Е. Действие группы автоморфизмов конечной модулярной геометрической решётки на уровнях. - Тезисы докладов на XI Международной конференции по проблемам теоретической.кибернетики. - Ульяновск. - 1996. - С.137.

15. Маренич Е.Е. Сингулрность некоторых отношений и юс комбинаторные приложения. - Дискретная математика. - 1996. - т.8,в.2. -С. 63 - 88.