Алгебры бинарных функций на упорядоченных множествах Маренич, Евгений Евгеньевич

Введение к работе

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

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

I/ Rota. G-.-C. On ike foundcd-i-o/u of сопгйиг.ІссілВ і/іеогр I :

tkeoztf- of HofcuA functions. - Z. іШ.ис&есл&с&іеі&гесАлсоїа u.

itew. G&B. -W6 2/ Wa,id M. 7he авзебгсь of 'ЄоІІСсє f^ncUon6. - Okie /ґаЇА J -

1939. - S, - P. 5S7-371.

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

5/ DouuC&i P.j Stcvney R., Rata. С.-С. Ок. ike fouhjcdcond o-f слт.(імІогиг tkeoty (vi) : Ike idea of genetatc'hp funUtoh . -Vtoteetihf. of ike Sixtk Betiefy fynpoiicc/n он, MaUetnaicaig

Started and Picea&fUty , VniStr-Utfr of C^&foz/u^ Pie64 -

M72. ~ v. 11 . - P.26=f-3ig.

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

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

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

В работах Фннча 'и Б.С.Стечкина для несингулярных бинарных отношений определены функции Мёбиуса, доказаны различные обобщения обращения Мёбиуса. Б.С.Стечкиным в 'было начато изучение алгебр бинарных функций в связи с задачей вычисления функций Мёбиуса. В

' 'построена теория вычисления функций Мёбиуса несингулярных отношений с помощью операторов замыкания, связей Галуа, /т.е. теория, обобщающая известные теоремы Ф.Холла и Ж.-К.Рота /.

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

6/ StaMey R. Ыисс«ле о/ а-в$евг&4 and tkei-t-

automotpJU4/n otoupd . - ВиЄ. Атег. Moid. Soc. - 1910. - v. 76.

P. 1236-1239 .

7/ Ha.x'cUon. K.L.,L,ong4ta>ffW.E. SuBdbjег&А of incidence ai-

$евга4 detezminet ву fucifa.enc& teEatconi . - J. Сот&Сгь.

Тпеог#. A . - 1381. - 31. P. 34-97',

8/ ktieqt A. A сА&гасІегігяХіоп, of teJuced incidence a$e-

6tad. - Dcictete Math.. - 13S1. ~34. -P. 1И-144.

9/ FCnch P.D. Oh. ike HoSica - junction of a поп- -iittfcc&i,^

SCnaty іеЄа&оп. - GuBB'. Aeattag: Hath. Soc.-/970 -3 - P

1SS- 162..

ІО/Стечкин B.C. Бинарные функции на упорядоченных множествах.-Труды

Математического института АН СССР.- 1977. -т.143. -С. 178-186.

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

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

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

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

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

- 1988. -Т.44, в.4. - С. 469 - 48?.

12/ Sckeid Н. ивег die Ндйссб-fujvctcoiv еіпег Eota- елЯШіеіь

На.Є8ог<іиіш^. - J. Соті Ткеогр-19П.-13. - P. И5-ІИ .

ІЗ/ Bax.6a.i^6fU К.. AutonwzphcAni. а/Ы. detcifaZioru, о/ crtccderice

а^евгаб.-Ргос. . Soc.-{972.-^.^:f6_lMZ.-P.351-3S6.

14/ РеіпЯего- R. Fcuhju diittcSuXlve tnodu.e6 отГег, tnccdence.

&Є$евгаб. - Pctujcc. J. HcUth. - <Я6. -ir.6f. - P. 34- Ь5~.

15/ Шматков В.Д. Изоморфизмы алгебр инцидентности. -Дискретная математика. -1991. -т.З, в.1. - С. 133 - 144.

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

то/ TQ/ 20/

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

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

16/ ОоиіібеІ P. On, the jouJiJatiotu> of со/пеїноХогіаХ, ikeox^

( vii ) ; 4#mm.eizic fccncOotu th-tougL of ike theotg. of dobtziuu,-

Uoiv and Оссиралсу. - StcuiCei in. Applied H

-is. LI, VЬ.

17/ Рог

fob %е.оте{/гіс ZaXtCcei. - Ръос. Атег. MeuCk. Soc-i^lf. - $}. -

P.5ob-$12.

18/ OenSoitfiic, P. Finite $еот,еІ>гьеб . - Bet&ti-HectjeC&e.zft'-

Л/ew- Уог-і ; Spun^ei. - 1368.

19/ КапХоъ W. M. Oh, cnccdence maitcce6 of -finite - pbojecH-Ve

ami off cue spiced. - Mati,. 2. -/172.-/2 4.- P. 3<$-W.

20/ Kutif . -J, OtJet. - ieSS. -Z. -P. <05- m.

21/ Fzan,k& Р.₁Шс^е6он,р.М. Intersection, ikeozenu /bfitt, geomet-

їл.с Coruetfu еіьсєб. - СопіііпмЛочся,.-1 в Si.- і LI f). - P. 357 - 5 S.

22/ PzojiH P. ItdeiAectioh, tkeotanA atvd ncd p tan,k of ihc&c-

icon, irudAiCU.- J. Со/кі. Theory A. - 13во. -5

23/ Stanley. t.P. Some aspect o-f fltoap actctif on, finite poA&ti.-

J. Com. Jheozc/ A . - 1382. - 52. - P. 132-їбі .

Множество орбит действия группы автоморфизмов естественным образом превращается в частично упорядоченное множество. Комбинаторный аспект рассматриваемой проблематики, выявленный работами ^ІН'»^1У'» , состоит в изучении свойств частично упорядоченного множества орбит.

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

Кени Мано исследовал Н{к ,Ь) - число способов, которыми л-различных предметов, / Иь /У /, каждый взятый t раз, / tt/V Л могут быть распределены в равных количествах между п> лицами. Число Н(И ,Ь) можно также интерпретировать как число пхп матриц Я<2-//// ^с целыми неотрицательными элементами, удовлетворяющих условию: ^

Г 4j - І «у - . - . _л/

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

Ыо *' /2/

где Сі зависит только от ft , t . Гипотеза АДГ доказана Р.Стенли ' и Е.Эрхартом в . По поблематике, связанной с гипотезой АДГ

24/ СанХсЬ 8., Hcnta.6 1 . Oi&Wottk'A ссіГсгіпд -iheozem job nodu.-

fat ia&ccet: & AompZe. ptoj'.- Aaeta, UnivezAaloi. -1$73.- 5.

- P. 348-3SO .

25/ АплпЛ H., Oumct V.C., Gupta. H. А сотіиаМ>ійіВ

ріовЄет . - Outc Hoik. J. - ІШ. - 1/.33,- P. 757-770.

26/ Stan6ey R. P.'-Linea.^ kornovcneOLU, dcophnntcn.e еуссгіііопг a*iA

tna-fic Ше&иді of ^Zaptu. - Ог,$е Маік. J. -1973.- VAo. - P. 60? -

&SZ.

27/ Ehihatt E. Зиг es cazt&s maaioue. - C.R.Acai. Sec. PatU

Scz.A.~i373.-l/.27?.-P.65l-63~4.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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