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

Московский государственный университет им. М.В. Ломоносова

На правах рукописи

Андреева Татьяна Владимировна

Развитие метода граничных функционалов и его приложение к комбинаторным задачам

Специальность 01.01.09 - дискретная математика и математическая кибернетика

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

Москва - 2004

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

Научный руководитель:

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

Александр Антонович Сапоженко.

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

доктор физико-математических наук, рук. отдела ИСП РАН Николай Николаевич Кузюрин.

кандидат физико-математических наук, с.нх.ВЦРАН

Михаил Николаевич Вялый. Ведущая организация: Институт системного анализа РАН.

Защита состоится « » октября 2004 г. в 11.00 часов на

заседании диссертационного совета Д 501.001.44 в Московском государственном университете им. М.В. Ломоносова по адресу: 119992, ГСП-2, Москва, Ленинские горы, МГУ, 2-ой учебный корпус, факультет ВМиК, аудитория 685.

С диссертацией можно ознакомиться в библиотеке факультета ВМиК МГУ.

Автореферат разослан сентября 2004 г.

Ученый секретарь

диссертационного совета Трифонов Н.П. профессор

Общая характеристика работы

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

К комбинаторным методам относится классический метод производящих функций. Основные идеи метода были высказаны еще в XVIII веке в работах Лапласа по теории вероятностей. Развитию метода посвящены раборы Редфилда, Пойа, Риордана и многих других. Метод заключается в том, что на основании рекуррентных соотношений выводится функциональное уравнение, решением которого является производящая функция. Разложение производящей функции в ряд дает точные или асимптотические формулы для коэффициентов. Тем не менее, метод производящих функций оказывается неприменимым в тех случаях, когда отсутствуют достаточно хорошие рекуррентные соотношения, связывающие искомые величины.

Существенную роль играют также комбинаторно - вероятностные методы решения перечислительных задач. Основы методов были заложены в работах В.Л. Гончарова, П. Эрдёша и других. Идея вероятностного метода заключается в том, чтобы показать, что почти все объекты из рассматриваемого класса обладают некоторым свойством. Вероятностные формулировки комбинаторных задач дают возможность при отыскании асимптотических формул использовать аппарат предельных теорем.

К комбинаторно - вероятностным медодам относится метод граничных функционалов, предложенный А.А. Сапоженко. Метод разработан в процессе решения проблемы Дедекинда о числе монотонных булевых функций. Он применим к задачам перечисления таких объектов как независимые множества в двудольных графах, булевы функции ранга ноль, двоичные коды с расстоянием 2, пары подмножеств с расстоянием 2 в графах. Во всех этих задачах речь идет о нахождении числа объектов, имеющих заданную границу или заданную мощ-

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

Задача расширения области применимости метода является весьма актуальной.

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

Научная новизна. Все основные результаты диссертации являются новыми.

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

2. Получена асимптотика числа антицепей в частично упорядоченном множестве, являющемся декартовой степенью /г-звезды при к <11.

3. Получена нижняя оценка числа антицепей в трехзначной п-мерной решетке.

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

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

Публикации и апробирование. Результаты диссертации докладывались на семинарах кафедры математической кибернетики на факультете ВМиК, на семинаре мехмата МГУ "Математические вопросы кибернетики" (руководитель — академик РАН О.Б. Лупанов),

на международной конференции по проблемам теоретической кибернетики (Казань, 2002 г.), на математических школах - симпозиумах КРОМШ-ХШ (Крым, 2002 г.) и КРОМШ-Х^ (Крым, 2003 г.), на международной конференции "Дискретные модели в теории управляющих систем" (Ратмино, мая 2003 г.), а также на VIII Международном семинаре "Дискретная математика и ее приложения" (Москва, 2004 г.).

По теме диссертации опубликовано 8 работ.

Структура и объем работы. Диссертация состоит из введения, трех глав, приложения и списка литературы. Объем работы 96 страниц.

Краткое содержание диссертации

Модельной задачей, иллюстрирующей подход, связанный с методом граничных функционалов, является проблема нахождения числа независимых множеств в двудольных графах. Пусть дан двудольный граф Г = (X, Е) с долями вершин X, Z к множеством ребер Е. Границей множества АС X называется множество

д(А) = {иег-. зиеА {щу} е е}.

Подмножество С вершин графа Г называется независимым, если подграф, порожденный множеством С, не содержит ребер. Пусть 1(Г) — число независимых множеств в графе Г. Тогда

В самом деле, произвольное независимое множество С в Г может быть представлено в в С = А и В, д еА = СПХ, В = СП 2. Если выбрано множество все подмножества и

только они образуют вместе с А независимое множество в Г. Число таких подмножеств равно Отсюда следует (1).

Функционал /(А) = возникающий в (1), обладает следую-

щими свойствами:

2) /(Л) = 1 тогда и только тогда, когда А = 0;

4) /(А и В) > ${А)}{В) тогда и только тогда, когда существуют и € Аиу £ В такие, что /({и,и}) > /({«})/({«}).

Функционал / : 2х И., удовлетворяющий условиям 1-4, называется граничным. Пара I = (.X", /) называется функциональной парой.

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

Граф £7/ = (X; Е) с множеством ребер

называется графом функциональной пары I = (^^.Подмножество А С X называется связным (относительно функционала /), если подграф графа Gi, порожденный множеством А, связен. В случае описанной выше задачи о числе независимых множеств в двудольном графе Г множество Л С Л" связно относительно функционала í, если граф, порожденный множеством А и д(А), связен. Через А = .Д(/) обозначим семейство всех связных подмножеств множества X.

Если I = (X, /) — функциональная пара, V, ] — натуральные, то положим

(3)

где состоит из всех подмножеств, принадлежащих семейству В и имеющих мощность

Для подмножеств А, В С X скажем, что В является компонентой множества А, если В связно, но никакое В такое, что В С. И С А не является связным. Для В С А(1) обозначим через С(В) семейство подмножеств множества X, все компоненты которых принадлежат семейству Положим

Легко установить, что

5(В) < Т(!) = 5(Л(/)) < 5(Б)5(Л(/) \ В).

При получении оценок. сумм значений граничных функционалов мы будем иметь дело с последовательностями функциональных пар {/„}«!• Все асимптотические соотношения выводятся в предположении, что п достаточно велико. Чтобы не загромождать изложение, индексы п опускаются.

Идея получения асимптотики сумм Т(1) заключается в том, чтобы найти семейство В С .4(7), для которого выполняются следующие условия:

1) 5(Д(Л\В)~1;

2) существует простая асимптотическая формула, выражающая S(B) через суммы вида (3), вычисление которых обычно не вызывает затруднений.

Назовем характеристикой функциональной пары 1 = (X, Г) наименьшее целое такое, что выполнено условие

А.А. Сапоженко1 получил асимптотическую формулу для сумм граничных функционалов в случае, когда функциональные пары имеют характеристику Д < 2.

Функциональная пара / = (X, Г) пара называется нерегулярной, если существуют подмножества Х\ С X и Хг С X, такие, что для любых вершин выполнено соотношение

/({«}) = '(/({«}))•

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

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

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

ет характеристику 3. Условие регулярности заключается в том, что

1 Здесь в далее имеются в виду работы А.А. Сапоженко О числе антицепей в многослойных ранжированных множествах, Дискретная математика - М.: Наука, 1989, т.1, вып. 2, с. 110 - 128,

Проблема Дедекинда и метод граничных функционалов, в кн. Математические вопросы кибернетики, Вып. 9 - М.: Наука, 2000, с. 161 - 220.

любых {и}, {и} 6 В выполнено /({и}) = /({и}). Аналогичный результат получен для нерегулярных функциональных пар с характеристикой 2. Результатом главы являются теоремы 1.4.3, 1.5.2 (см. ниже), дающие асимптотику сумм 8(Б) для функциональных пар с характеристиками 3 и 2 соответственно.

В параграфе 1.1 введены основные определения. В параграфе 1.2 описан класс подмножеств множества X "типичных" для семейства В, и получены оценки сумм граничных функционалов 8(Б) через суммы граничных функционалов по типичным подмножествам. Типичным является множество, состоящее не более, чем из в компонент, где 9 = а1(В)(1 + о(1)).

Пусть даны семейство В и множество С С X, определим семейство ранга 2

В параграфе 1.3 получены оценки сумм вида

§(В)=Т,хНАМЛ) (4)

через суммы вида (3). Здесь

Суммы вида (4) являются обобщением сумм S(B). Чтобы оценить исходные суммы, выводится асимптотическая формула для функционала тт.

В параграфе 1.4 рассмотрен класс (Д, к, ординарных функциональных пар и доказано, что такие функциональные пары имеют характеристику

Для функциональной пары / = (X/), семейства А(1), вершины V 6 X и натурального т положим

= {ВеА:\В\<т,Ви{у}е Л}.

Функциональная пара / = ^^ называется (Д,/г, д, с) -ординарной, 1) для всякого выполнено

2) \Х\ < 2(д+1)"-21ой«)

3) для любых А С X и V € А

4) для всякого г» € X и любого натурального числа т-

Рассмотрим, например, функциональную пару I = (X,/), порожденную двудольным графом Г = (X, ¿Г;-Б), где X — 2 = — соответственно А:-ый и (к + 1)-ый слои тг-мерного единичного куба, О <к<(п- 1)/2, Е = {{и,т>} : и <Е Х,ь е < и} и /(А) = 2-^ для всех А С X. Нетрудно убедиться в том, что такая пара является (2 ,п — к, 1,2)-ординарной.

В пункте 1.4.3 получена асимптотическая формула, выражающая функционал тг через суммы вида (3) для функциональных пар с характеристикой 3 в случае регулярных семейств подмножеств. Подмножество В называется регулярным, если

/(М) = /({«})

для всех {и}, {и} 6 В. В результате получена асимптотика сумм 5(В) для функциональных пар с характеристикой 3 и регулярных семейств В:

Теорема 1.4.3. Пусть I = (X, /) является (3, к, д, с)-ординарной функциональной парой, семейство В С является регулярным.

Тогда

5(В) = (1 + 0(2-1^'с))ехр{Дз(В)},

где

Пг{В) = си1 (В) - -а\В) + - а^На1^1'2').

£ о

Здесь В'2', В'1'2' — семейства более высокого ранга, порожденные семейством В.

В параграфе 1.5 введено обобщение понятия ординарной функциональной пары. Получена асимптотика сумм граничных функционалов для нерегулярных функциональных пар с характеристикой 2.

Функциональная пара I = (X,/) называется (Д,{/с^лг}»<7>С)Р)~ ординарной, если < к\,

Х = Х1иХ2, ХхГ\Х2 = г,

для j = 1,2 функциональная пара Ц = (X,-,/) является (Д, ординарной, а также для любых u,v £ X таких, что {и,и} 6 Л(/)

N2/({«})-l0g2/(W)|<P.

Теорема 1.5.2. Пусть I = (X,f) является (2, {«i, /сг}, с,р)— ординарной функциональной парой, В С Л^СО- Тогда при достаточно больших «2

S(B) = (l + 0( expfam,

В главе 2 рассматривается задача о числе антицепей в частично упорядоченном множестве диаграмма которого является декартовой степенью fc-звезды, т.е. дерева с k +1 вершинами, одна из которых имеет степень к. В работах A.A. Сапожешсо получена формула, позволяющая вычислять асимптотику числа антицепей в тале называемых унимодальных ранжированных множествах и задача решена для 1 < А: < 4.

В параграфе 2.1 введены основные определения. Двудольный граф G — (X, Z\ Е) является ¿-расширителем, если для всех А С X выполнено неравенство |Л| < (1 — i)|3(A)|. Для ранжированного т-слойного множества Р = (Pi,.. . ,Pm) с порядком < и числа j, 1 < j <т обозначим через Gj = {Pj,Pj+\\Ej) двудольный граф с долями вершин Pj и Pj+i и множеством ребер

Ej = {{u, г} :uePj,ve Р,+i,i* < v}.

Через üj = (Pj, обозначим двудольный граф с долями вер-

шин Pj и Pj-1 и множеством ребер

~Ej = {{и,и} : и е Pj,v 6 Pj-ii v < и}.

Множество Р является (Д, к,q,p,г)-квазиунимодалъным, если графы Gj являются (У(к)-распшрителями при 0 < j < г — 1, графы (jj являются ¿(к)-расширител£ми при г + 1 < j < п, а функциональные пары, порожденные этими графами, являются (Д, к, q, 4р)-ординарными. Множество Р является (Д, к, ц,р,г)~унимодальным, если оно является (Д,к,д,р,г)-квазиунимодальным, и, кроме того, выполнены следующие условия:

max vgj(v) < ттсгсДи) при 0 < j < г — 1, а также (5)

max < minct^(u) при r +1 < j < n, (6)

где (Ta(v) — степень вершины v в графе G.

Из работ A.A. Сапоженко следует, задача о числе антицепей в (Д, к, q,p, г)-унимодальном множестве сводится к задаче о числе антицепей в множестве (Pr_i,Pr,Pr+i).

Пусть к — натуральное число, рассмотрим множество 54 = {-1,0,1,...,*-1} и зададим на нем отношение частичного порядка Ч следующим образом: i X -1 при i = 0,1 — 1. В параграфе 2.2 доказана унимодальность множества Положим

= {« = («1 — .в») 6 5? : £ а,- = ¿}. ' »=i

Справедлива

Теорема 2.2.3. Пусть п = (fc + 1 )т + г для некоторых целых т и г, 0 < г < к. Положим Д = pplog2(Ä + l)j — 1. Тогда при достаточно больших mu0<i<k— 1 множество S£ является (Д,п — т + 1,1,2, т,тп)-унимодальным. При г = к множество является (Д,тг — то, 1,2, то, то +1)-унимодальным.

Обозначим через il>(S%) число антицепей в S£.

Теорема 2.2.4. Пусть п = {к + 1 )т + г для некоторых целых т и г, 0 < г < к. Положим Д = [^i log2(fc +1)] - 1. Тогда при достаточно больших то u0<i<k — 1

ДО?) = (1 + 0(2-b^))^(S,Vi и S£m U 5?)ГО+1).

При достаточно больших т иг = к

«) = (1 + 0(2"log'"))(^(5tVi U Slm U S£m+1) +

Множество порождает функциональную пару 1п =

(*„,/„), где Хп = U 5^+1, для АСХп

д(А) = {В С : to G ЯЭи G A(« Ч и) V (и < и)},

/п(А) = 2-|3(А)|. в параграфе 2.3 доказано, что при 5 < к < 11 функциональные пары /„ = (Х„,/„) являются регулярными и (3,п — то, 2,3)-ординарными.

Теорема 2.3.3. Пусть 5 < к < 11, п достаточно велико и п = (к + 1)т + г для некоторых т, г, 0 < i < к, 1п — (Х„, /„) — функциональная пара, порождаемая множеством S'„»^+1)' Тогда

= 2С)4"""ехр{/2з},

где

h=ma(Q)=411Д - ¡"У*+- 42)д+

Суммы ос'р'" вычисляются аналогично введенным ранее суммам вида (3). В приложении эти суммы вычислены через параметры множества

В главе 3 рассматривается частично упорядоченное множество Щ, являющееся декартовой степенью линейного порядка мощности 3. Как и в предыдущей главе, здесь ставится задача о числе антицепей в данном множестве.

Пусть к — натуральное число, рассмотрим множество

■Et = {0,1,..., Ä — 1}

и зададим на нем отношение частичного порядка < следующим образом: г < х + 1 при X = 0,1, ...,& — 2. Положим

F(n,х, к) = {à = (ai...,о.) G Щ : £ оц = *}, ЛГ(п,i, к) = |F(n,х,к)\.

t=1

Обозначим через Ф(Щ) число антицепей в множестве Щ. В.Б. Алексеев в 1974 г. доказал, что

оп+1/2

l0g2^)< _(1 + о(1)).

В параграфе 3.1 получена асимптотика мощностей центральных слоев Положим F(n,i) = F(n,i, 3) и N(n,i) = ЛГ(п,х,3).

Теорема 3.1.1. При достаточно достаточно больших п справедливы равенства

В параграфе 3.2 рассмотрена последовательность функциональных пар /„, порожденных тремя центральными слоями решетки Щ. Множество (F(n, п -1), jF(n,n),F(n, п +1)) порождает функциональную пару 1п = (Хп, /„), где Хп = F(n, п -1) U F(n,п +1), для А С Хп

д(А) = {BÇ F(n,n) : Vu 6 ВЗи eA(u<v)V(v< u)}, '

fn{A) = Эти функциональные пары являются нерегулярны-

ми, показано, что они имеют характеристику 2. С использованием результатов главы 1 получена асимптотика сумм значений граничных функционалов по множествам малой мощности.

Теорема 3.2.1. Пусть {/„ = (Х„,/„)} — последовательность функциональных пар, порожденных соответственно множествами (F(n,n— l),F(n,n),F(n,n +1)). Тогда прип -> оо

S (M1*)) ~ ехР{^}>

-Töt-v-^

х [2 + 2-("-Л(Зп2 - Inj + ll|j2 + îofi + n - 2)]. Из теорем 2.2.3, 3.2.1 следует Теорема 3.2.2. При достаточно больших п

1>{Щ) > 2"("'п>ехр{^},

где /ig определено в предыдущей теореме.

Таким образом, улучшена нижняя оценка Замечание. Можно убедиться в том, что

В параграфе 3.3 доказана логарифмическая выпуклость мощностей слоев множества Щ.

Теорема Ъ.ЪА.. При любых к > 2, п > 2 к 2 < ! < п{к — 1)

В параграфе 3.4 доказана (3,|п/2_|, 1,2,п,п)-квазиунимодаль-

ность множества Щ, а также унимодальность частично упорядоченных множеств, состоящих из 2п/3 первых или из 2п/3 последних слоев Щ. Это позволяет свести задачу о числе антицепей в к аналогичной задаче в множестве, состоящем из 2п/3 центральных слоев Щ.

Теорема 3.4.3. Положим = ^(3,п,г), 4 = (2(п - 1)/3], к = п — \Ь/2\. При достаточно больших п множества (Щ 0, ..., Щ^) и (Е£2п_(,..., Щ^п-и Щ,2п) являются (2, «,1,2, £) -унимодальными. Функциональная пара I = (X, /) называется Д-сходящейся, если

Если для квазиунимодального множества выполнены условия (5), (6), то функциональные пары, порожденные парами его соседних слоев автоматически являются Д-сходящимися.

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

В таком случае асимптотика числа антицепей совпадает с нижней оценкой.

Основные результаты диссертации

1. Для функциональных пар с характеристикой 3 получена асимптотическая формула сумм граничных функционалов по регулярным семействам подмножеств.

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

3. Получена асимптотика числа антицепей в множеству при к <11.

4. Получена оценка отношения мощностей соседних слоев множества Щ. 5. Доказана логарифмическая выпуклость мощностей слоев множества Щ.

6. Получена нижняя оценка числа антицепей в множестве

Автор выражает признательность своему научному руководителю А.А. Сапоженко.

Работа выполнена при поддержке фонда РФФИ, проекты 01-01-00266, 04-01-00359.

Публикации по теме диссертации

1. Андреева Т.В., О мощности слоев трехзначной п-мерной решетки, Ж. вычисл. матем. и матем. физ., 2003, т. 43, N 10, с. 1560-1568.

2. Андреева Т.В., Метод граничных функционалов для нерегулярных структур, Дискретная математика, 2004, т. 16, N 1, с. 121-139.

3. Андреева Т. В., Об унимодальности декартовой степени звезд, Математические методы и алгоритмы, Сборник трудов ИСП РАН, 2004, т. 6, с. 36-49.

4. Андреева Т.В., О расширительности слоев п-мерной трехзначной решетки, ТВИМ (Таврический вестник информатики и математики), 2003, N 1, с. 25-30.

5. Андреева Т.В., Об одном обобщении метода граничных функционалов, Дискретная математика, 2004, т.16, N 3, принято в печать.

6. Андреева Т.В., Асимптотика сумм значений граничных функционалов в регулярном случае, Проблемы теоретической кибернетики, тезисы докладов XIII Международной конференции (Казань, 2731 мая 2002 г.), Часть I / Под редакцией О.Б.Лупанова - М.:Изд-во центра прикладных исследований при механико-математическом факультете МГУ, 2002, с. 12.

7. Андреева Т.В., О логарифмической выпуклости мощностей слоев к-значной п-мерной решетки, Труды V Международной конференции "Дискретные модели в теории управляющих систем" (Ратмино, 2&-2Э мая 2003 г.)-М.: Издательский отдел факультета ВМиК МГУ имени М.В.Ломоносова, 2003, с. 11-13.

8. Андреева Т.В., О числе антицепей в декартовой степени звезд, Материалы VIII Международного семинара "Дискретная математика и ее приложения" (2-6 февраля 2004 г.) - М., Издательство механико-математического факультета МГУ, 2004, с. 324-326.

Заказ №163. Объем 1 ал. Тираж 100 экз.

Отпечатано в ООО «Петроруш» г. Москва, ул. Палиха-2а, тел. 250-92-06

W159 б9

ВВЕДЕНИЕ

ГЛАВА 1. Оценки сумм граничных функционалов

1.1. Основные понятия

1.2. Асимптотики сумм граничных функционалов

1.3. Отношения между суммами граничных функционалов

1.4. Оценки сумм 5(23) для ординарных функциональных пар

1.4.1. Оценки сумм

§(В) для ординарных функциональных

1.4.2. Оценки сумм Б (В) для семейств ¿-связных множеств

1.4.3. Оценки сумм в (В) для регулярных семейств

1.5. Оценки сумм Б (В) для нерегулярных функциональных пар

ГЛАВА 2. Асимптотика числа антицепей в декартовой степени звезд

2.1.Основные понятия

2.2. Унимодальность множества

2.2.1. Расширительность пар слоев с большими к

2.2.2. Расширительность пар слоев с малыми к

2.2.3. Доказательство основного результата

2.3. Асимптотика числа антицепей в

ГЛАВА 3. Оценки числа антицепей в трехзначной п-мерной решетке

3.1. О мощности слоев множества Щ

3.2. Нижняя оценка числа антицепей в средних слоях множества Е$

3.3. Логарифмическая выпуклость мощностей слоев с-значной п-мерной решетки

3.4. Расширительность пар слоев Е$

Значительное место в математике занимают перечислительные задачи, связанные с доказательством существования, алгоритмами построения и подсчетом числа элементов данного множества, обладающих некоторыми свойствами. Речь может идти, например, о числе решений задач целочисленного линейного программирования, числе /¿ вершинных графов с определенными свойствами или о числе изомеров химических элементов. Существующие методы решения таких задач можно разделить на два типа: комбинаторные и вероятностные.

К комбинаторным методам относится классический метод производящих функций, получивший развитие в середине XX века. Использование перечислительных теорем Пойа, де Брёйна и Робинсона позволяет получать некоторые соотношения между числовыми характеристиками изучаемых объектов. Метод заключается в том, что на основании рекуррентных соотношений выводится дифференциальное уравнение, решением которого является производящая функция. Разложение производящей функции в ряд дает точные или асимптотические формулы для коэффициентов. Тем не менее, методика построения производящих функций сложна и не всегда приводит к обозримым результатам, поэтому существует класс задач, которые не могут быть решены с помощью классических методов.

Существенную роль играют комбинаторно - вероятностные методы решения перечислительных задач. В своих работах эти методы применяли Ю.Л. Васильев, В.В. Глаголев, B.JI. Гончаров, В.Ф. Колчин, A.A. Сапоженко, В.Н. Сачков, Н. Алон, Дж. Спенсер, П. Эрдёш. Идея вероятностного метода заключается в том, чтобы показать, что почти все объекты из рассматриваемого класса обладают некоторым свойством. Вероятностные формулировки комбинаторных задач дают возможность при отыскании асимптотических формул использовать аппарат предельных теорем.

Задачи, в которых речь идет о нахождении числа объектов, имеющих заданную границу или заданную мощность границы, естественно назвать перечислительными изопериметрическими задачами. Такими являются, например, задачи о числе монотонных булевых функций (так называемая проблема Дедекинда), независимых множеств в двудольных графах, булевых функций ранга ноль, двоичных кодов с расстоянием 2, пар подмножеств с расстоянием 2 в графах. Оказалось что, такие задачи сводятся к вычислению сумм специального вида, которые называются суммами граничных функционалов. Метод граничных функционалов разработан A.A. Сапоженко для решения перечислительных изопериметрических задач. Он сочетает в себе комбинаторный и вероятностный подходы и позволяет получать предельные распределения для случайных величин типа числа компонент связности. Сущность метода заключается в сведении исходной комбинаторной задачи к вычислению сумм граничных функционалов и дальнейшему аналитическому исследованию последних. Цель метода — получение оценки исходных сумм через "простейшие" суммы граничных функционалов. Это позволяет уйти от перебора и громоздких конструкций, возникающих при чисто комбинаторном подходе.

К классу перечислительных изопериметрических задач относятся задачи о числе антицепей в частично упорядоченных множествах, а, значит, и задачи о числе конечнозначных монотонных функций. Наибольшую известность среди таких задач получила упоминавшаяся выше проблема Дедекинда о числе ф(п) монотонных булевых функций или, что то же, о числе антицепей в единичном n-мерном кубе Вп.

В 1897 г. Р. Дедекинд вычислил значение ф(4). Р. Черч в 1940 г. и М. Уорд в 1946 г. получили соответственно значения ф(Ъ) и ^>(6). В 1954 г. Б. Гильберт показал, что ф(п) удовлетворяет неравенствам

2(L«/2J) < ф(п) < n(i«/2j) + 2.

B.K. Коробков в 1962 - 65 гг. показал, что ф{п) < 24'23(l»/2j), Ж. Ансель в 1968 г. улучшил верхнюю оценку до а Д. Клейтмен в 1969 г. доказал, что log2^(n)~ (lfJ2j).

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

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

Проблема вычисления мощности множеств функций п переменных из замкнутых классов исследовалась и для fc-значных логик. В 1974 г. В.Б. Алексеев получил асимптотику логарифма числа fc-значных функций, монотонных относительно произвольно заданного частичного порядка на S. В целом же асимптотик числа монотонных функций fc-значной логики при к > 2 практически нет.

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

Краткое содержание диссертации

Модельной задачей, иллюстрирующей подход, связанный с методом граничных функционалов, является проблема нахождения числа независимых множеств в двудольных графах. Пусть дан двудольный граф Г = (X,Z\ Е) с долями вершин X, Z и множеством ребер Е. Границей множества АС X называется множество д(А) — {v е Z : 3 и € Л {u,v} € Е}.

Подмножество С вершин графа Г называется независимым, если подграф, порожденный множеством С, не содержит ребер. Функция f(A) = обладает следующими свойствами:

1) 0 < f(A) < 1 для всех ЛС1;

2) f(A) = 1 тогда и только тогда, когда А = 0;

3) f(AöB)>f(A)f(B)-,

4) f(A U В) > f(A)f{B) тогда и только тогда, когда существуют и € А и v 6 В такие, что f({u,v}) > f {{и})f ({v}).

Пусть /(Г) — число независимых множеств в графе Г. Тогда

Г) = £ 2-"в<Л>1. (1) асх

В самом деле, произвольное независимое множество С в Г может быть представлено в виде С — A U В, где А = СПХ, В = С П Z. Если выбрано множество А С X, то все подмножества В С Z \ д(А) и только они образуют вместе с А независимое множество в Г. Число таких подмножеств равно Отсюда следует (1).

Из равенства (1) следует, что вопрос о числе независимых множеств сводится к вычислению сумм вида YIacx f(Á)

Функционал / : 2х —> R, удовлетворяющий условиям 1-4, называется граничным. Пара I = (X, /) называется функциональной парой. Через

T(I) = T(X,f)= £ /(Л), асх обозначим полную сумму значений граничного функционала /, в дальнейшем для краткости будем говорить о суммах граничных функционалов. Граф Gi = (X; Е) с множеством ребер

Е = {К 4 : /(М)/(М) < /({«,«})} называется графом функциональной пары I = (X,f). Подмножество АСХ называется связным (относительно функционала f), если подграф графа порожденный множеством А, связен. В случае описанной выше задачи о числе независимых множеств в двудольном графе Г множество АСХ связно относительно функционала /, если граф, порожденный множеством A U <9(А), связен. Через А = А{1) обозначим семейство всех связных подмножеств множества X.

Если I = (X,f) — функциональная пара, v, j — натуральные, В С Д(/), то положим = £(/И)Г. (2) лев где состоит из всех подмножеств, принадлежащих семейству В и имеющих мощность j.

Для подмножеств А, В С X скажем, что В является компонентой множества А, если В связно, но никакое D такое, что В С D С А не является связным. Для В С А(1) обозначим через С (В ) семейство подмножеств множества X, все компоненты которых принадлежат семейству В. Положим

5(5)= £ f(B).

В£С{В)

Справедливо утверждение о том, что

S{B) < Т{1) = S{A(I)) < S(B)S(A(I) \ В).

Идея получения асимптотики сумм Т(1) заключается в том, чтобы найти семейство В С А(1), для которого выполняются следующие условия:

1) 5(Л(/)\В)~ 1;

2) существует простая асимптотическая формула, выражающая S(B) через суммы вида (2), вычисление которых обычно не вызывает затруднений.

Назовем характеристикой функциональной пары I — (X, /) наименьшее целое А такое, что выполнено условие а\Л[А+1](1)) = о(1).

A.A. Сапоженко ([20], [23]) получил асимптотическую формулу для сумм граничных функционалов в случае, когда функциональные пары имеют характеристику А < 2.

Функциональная пара I = (X, /) пара называется нерегулярной, если существуют подмножества Х\ С X и С X такие, что для любых вершин и £ Х\ ж v G Х2 выполнено соотношение

ЯМ) = o(f({u})).

Целью данной работы является расширение области применения метода граничных функционалов на случай функциональных пар с характеристикой А > 3, а также на случай нерегулярных функциональных пар. Эта задача решается в главе 1. В главе 2 результаты первой главы применяются для получения асимптотики числа антицепей в частично упорядоченном множестве являющемся декартовой степенью А; -звезды при к < 11. Функциональные пары, порожденные парами слоев этого множества, имеют характеристику 3. В главе 3 рассматривается множество являющееся декартовой степенью линейного частичного порядка мощности 3. Функциональные пары, порожденные парами слоев этого множества, являются нерегулярными. С использованием результатов первой главы получена нижняя оценка числа антицепей в .

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

В главе 1 получена асимптотическая формула для вычисления сумм S(B) в случае, когда функциональная пара имеет характеристику 3 при условии, что для любых {и}, {г;} 6 В выполнено /({и}) = f{{v}). Кроме того, определено расширение класса функциональных пар с характеристикой 2.

В главе используются результаты из работ [19], [20] и [23]. Результатом главы являются теоремы 1.4.3, 1.5.2 (см. ниже), дающие асимптотику сумм S(B) для функциональных пар с характеристиками 3 и 2 соответственно.

В параграфе 1.1 введены основные определения.

В параграфе 1.2 описан класс подмножеств множества X "типичных" для семейства В, и получены оценки сумм граничных функционалов S(B) через суммы граничных функционалов по типичным подмножествам. Типичным является множество, состоящее не более, чем из в компонент, где в = а1 (В)(1 + о(1)).

Пусть даны семейство В и множество В С X, тогда обозначим через множество подсемейств {Ai,., А„} семейства В, удовлетворяющих следующим условиям:

1) множество Н = U Aj связно l<j<s

2) множество В U Я связно.

В параграфе 1.3 получены оценки сумм вида

S(B) = £ f(AMA) (3)

АС.Х через суммы вида (2).

Здесь п(А)= п (1 + ДЯГ1вев^

Суммы вида (3) являются обобщением сумм <!?(#)■ Для оценки исходных сумм достаточно получить асимптотическую формулу, позволяющую вычислять функционал 7Г. Дальнейшая задача состоит в оценке функционала ж для типичных множеств.

В параграфе 1.4 рассмотрен класс так называемых (Д, к, р)-ординарных функциональных пар и доказано, что такие функциональные пары имеют характеристику А.

Для функциональной пары I = (X,/), семейства А(1), вершины у 6 X и натурального т положим м.тШ = {В еА-.\в\<гп,ви {у} е Л}.

Функциональная пара / = {X,/) называется (А, к, q, с)-ординарной, если

1) для всякого V Е X выполнено f({v}) < 2-к,

2) \Х\ < 2(д+1)к-21о82«;

3) для любых А С X и V £ А

А)<ЦА\ М)/(М)2(|Л|-1)9,

4) для всякого V £ X и любого натурального числа т

АыЛ(1)\ <

Пусть I — (X, /) — функциональная пара, порожденная двудольным графом Г = (X, ; Е), где X = 2 = — соответственно &-ый и (к + 1)-ый слои га-мерного единичного куба, 0 < к < (п — 1)/2,

Е — {{и, у} \ и Е Х,у Е Z и < у} и f(A) — для всех А С X. Пара / — (X, /) является (2, п — к, 1,2)-ординарной.

В самом деле,

1) минимальная степень вершины г; 6 X в графе Г равна п — к;

3) границы любых двух вершин и,у Е. X имеют не более одной общей точки;

4) для любого т и любой вершины V Е X мощность ее окрестности порядка 2т не превосходит ((к + 1)(ге — к))т < (п — к)2т.

Если функциональная пара имеет характеристику 2, то значение функционала тг для типичных множеств асимптотически равно 1, и, следовательно, значения сумм 5(В) и 5"(<8) асимптотически равны.

В пункте 1.4.3 получена асимптотическая формула, выражающая функционал тг через суммы вида (2) для функциональных пар с характеристикой 3 в случае регулярных семейств подмножеств. Семейство В называется регулярным, если

Ы) = /({»}) для всех {и}, {г;} £ В. В результате получена асимптотика сумм Б(В) для функциональных пар с характеристикой 3 и регулярных семейств В:

Теорема 1.4.3. Пусть I — (X,/) является (3, к,д, с)-ординарной функциональной парой, семейство В С является регулярным. Тогда

МВ) = а1 (В) ~ \а\В) + \а*{В)

В параграфе 1.5 введено обобщение понятия ординарности функциональных пар, и найдена их характеристика. Получена асимптотика сумм граничных функционалов для нерегулярных функциональных пар с характеристикой 2.

Теорема 1.5.2. Пусть I = (X,/) является (2, {«!, «2}, Я., с,р)-ординарной функциональной парой, В С Тогда при достаточно больших «2

5(В) = (1 + 0(2-!10^)) ехрМВ)}, где

В главе 2 рассматривается задача о числе антицепей в частично упорядоченном множестве 5^™, диаграмма которого является декартовой степенью А;-звезды, т.е. дерева с к + 1 вершинами, одна из которых имеет степень к. В работе [20] получена формула, позволяющая вычислять асимптотику числа антицепей в так называемых унимодальных ранжированных множествах (точное определение см. в параграфе 2.1) и задача решена для 1 < к < 4.

В параграфе 2.1 введены основные определения. Двудольный граф С = (X, И; Е) является ¿-расширителем, если для всех А С X выполнено неравенство |Л| < (1 — Для ранжированного г?г-слойного множества Р = (Р1?.,Рт) с порядком ^ и числа з, 1 < э' < т обозначим через О^ — (Р^, /¿+1; Е^) двудольный граф с долями вершин Р^ и Pj+l и множеством ребер = {{и,г»} : и £ € ■< г>}. Через Сз = обозначим двудольный граф с долями вершин Pj и Р3-1 и множеством ребер Ец — {{и,г>} : и £ € V ■< V,}. Множество Р является (Д, /г, д,р, г)-квазиунимо дальним, если графы являются 5(«)-расншрителями при О <7" — 1, графы (7являются (У(Ас)-расширителями при г +1 < 3 < п, а функциональные пары, порожденные этими графами, являются (Д, /г, 4р)-ординарными. Множество Р является (А, к,д,р, г)-унимодальным, если оно является (Д, к, д,р, г)-квазиунимодальным, и, кроме того, выполнены следующие условия: тах сгоАу) < тикгс Ы) при 0 < 3 < г — 1, а также (4) г>еР7'+1 «6 Р] 1 max <tq .{v) < min oq\v,) при г + 1 < j < те, (5) vePj-i ' «ePj ' где (7g{v) — степень вершины v в графе G.

Из работ [20], [23] следует, задача о числе антицепей в (Д, к, г)-унимодальном множестве сводится к задаче о числе антицепей в множестве (-Pr-i, Рт? P+i)

Пусть к — натуральное число, рассмотрим множество Sk = {—1,0,1,. ,к — 1} и зададим на нем отношение частичного порядка ^ следующим образом: — 1 ^ г при i = 0,1,. , к — 1. В параграфе 2.2 доказана унимодальность множества . Положим

Sit = {« = ((*!., ап) е : E?=1 «i = t}.

Теорема 2.2.3. Пусть п = (к + 1)т. + г для некоторых целых т и г, 0 < г < к. Положим А = + — 1. Тогда при достаточно больших т и О < г < к — 1 множество является (А,те — т + 1,1,2,т,т)-унимодальным. При г = к множество является (А, п — т, 1, 2, т, т + 1) -унимодальным.

Обозначим через ф(3%) число антицепей в

Теорема 2.2.4. Пусть п — (к + 1)пг + г некоторых целых т и г, 0 < г < к. Положим А = —— 1 - Тогда при достаточно больших т и 0 < { < к — 1 (1 + и и 5£т+1).

При достаточно больших т и ( = к

1>№) = (1 + 0(2-'^")) и и 5Дто+1) + и и ^Дтп+г)) •

Множество порождает функциональную пару 1п = (Хп,/п), где и 5£+1, для АС Хп д{А) = {В С : Уг; £ В Зи е А (и < у) V (и ^ и)},

Л) = 2-1®(Л)1. В параграфе 2.3 доказано, что при 5 < к < 11 функциональные пары /„ = (Х„, /п) являются регулярными и (3, п — т, 2,3)-ординарными. С использованием результатов главы 1 доказана

Теорема 2.3.3. Пусть 5 < к < 11, та достаточно велико и п = (/г + 1)пг + г некоторых щ, г, 0 < I < к, 1п = (Хп, /„) — функциональная пара, порождаемая множеством (5^-1 > Тогда

2(^п-техр{Д3}, где

4й = «"(^(/п)),

Дз = Дз(Л(/п)) = 41'-1 - + ^ - + а?'»'1.

В приложении суммы а^'" вычислены через параметры множества В главе 3 рассматривается частично упорядоченное множество , являющееся декартовой степенью линейного порядка мощности 3. Как и в предыдущей главе, здесь ставится задача о числе антицепей в данном множестве.

Пусть к — натуральное число, рассмотрим множество Е^ — {0,1,., к — 1} и зададим на нем отношение частичного порядка < следующим образом: г < г + 1 при г = 0,1,., к — 2. Положим к) = {а = («1., ап) е Е% ■ 2™=1 =

Обозначим через ~ф(Е%) число антицепей в множестве Е£. Из работы В.Б. Алексеева следует [1], что отг 4-1/2

В параграфе 3.1 получена асимптотика мощностей центральных слоев Е^.

Теорема 3.1.1. При достаточно достаточно больших п справедливы равенства

•"-^Ш'-ЙЙЧ;))

•« = Ш t1-ïs; 4s)) ■

В параграфе 3.2 рассмотрены функциональные пары, порождаемые тремя центральными слоями Е£. Трехслойное множество те-1,3), F(n, те, 3), F{n, те +1,3)) порождает функциональную пару 1п — (Хп, /п), где Хп — F(n,n — l,3)liF(n,ni-l,3), для А С Хп д{А) = {В С F(n, те, 3) : Vv G В Зи 6 А {и < v) V (г; < и)}, fn{A) = Эти функциональные пары являются нерегулярными, показано, что они имеют характеристику 2. С использованием результатов главы 1 получена асимптотика сумм значений граничных функционалов по множествам малой мощности.

Теорема 3.2.1. Пусть {In = (Хп,/п)} — последовательность функциональных пар, порожденных соответственно множествами (F(n, п — 1,3), F(n, те, 3), F(n, п + 1,3)). Тогда rvpu п оо где l(n-1)/2j / \ / • \

Е (7) U - 2J - !)2(Гг"Л [2 + - + + 10|i + ^ - 2)].

Из теорем 2.2.3, 3.2.1 и [21], [23] следует Теорема 3.2.2. При достаточно больших п где определено в предыдущей теореме.

Таким образом, улучшена известная нижняя оценка ф(Е^). Замечание. Можно убедиться в том, что где с sa 1.95.

В работе H.H. Катериночкиной оценивалась величина 5(г,п, k) = N(n,i + 1, fc ) — N(n,i,k). В параграфе 3.3 доказана логарифмическая выпуклость мощностей слоев множества Е%.

Теорема 3.3.1. При любых k>2,n>2u2<i< п{к — 1) справедливо

N(n, г — 2, fc) N(n,i-l,k) N(n,i - l,fc) N(n, г, к)

В параграфе 3.4 доказана (3, \п/2 J, 1,2, п, ге)-квазиунимодальность множества Eg, а также унимодальность частично упорядоченных множеств, состоящих из 2и/3 первых или из 2тг/3 последних слоев Eg. Это позволяет свести задачу о числе антицепей в Eg к аналогичной задаче в множестве, состоящем из 2те/3 центральных слоев Eg.

Теорема 3.4.3. Положим Eg- = F(n,i, 3), t = [2(п - l)/3j, к = п- [t/2\. При достаточно больших п множества (Eg0, Egд,., Egt) и (Eg2nt, • • • ■> ^3 2«) являются (2, к, 1,2, t, t) -унимодальными.

Функциональная пара I = {X,f) называется Д-сходящейся, если выполнено

Е аЧЛмСО) = о(1). д+1

Если для квазиунимодального множества выполнены условия (4), (5), то функциональные пары, порожденные парами его соседних слоев, автоматически являются Д-сходящимися.

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

В таком случае асимптотика числа антицепей совпадает с нижней оценкой.

Основные результаты диссертации

1. Для функциональных пар с характеристикой 3 получена асимптотическая формула для вычисления сумм граничных функционалов по регулярным семействам подмножеств.

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

3. Получена асимптотика числа антицепей в множестве при к < 11.

4. Получена оценка отношения мощностей соседних слоев множества Eg.

5. Доказана логарифмическая выпуклость мощностей слоев множества

6. Получена нижняя оценка числа антицепей в множестве Eg.

1. Алексеев В.Б. О числе монотоннык /г-значных функций, Проблемы кибернетики, 1974, вып. 28, с. 5-24.

2. Андреева Т.В., О мощности слоев трехзначной n-мерной решетки, Ж. вычисл. матем. и матем. физ., 2003, т. 43, N 10, с. 1560-1568.

3. Андреева Т.В., Метод граничных функционалов для нерегулярных структур, Дискретная математика, 2004, т. 16, N 1, с. 121-139.

4. Андреева Т.В., О расширительности слоев n-мерной трехзначной решетки, Таврический Вестник Информатики и Математики, 2003, N 1, с. 25-30.

5. Андреева Т.В., Об одном обобщении метода граничных функционалов, Дискретная математика, 2004, т. 16, N 3, принято в печать.

6. Андреева Т.В., Об унимодальности декартовой степени звезд, Математические методы и алгоритмы, Сборник трудов ИСП РАН, 2004, т. 6, с. 36-49, принято в печать.

7. Андреева Т.В., О числе антицепей в декартовой степени звезд, Материалы VIII Международного семинара "Дискретная математика и ее приложения" (2-6 февраля 2004 г.) М., Издательство механико-математического факультета МГУ, 2004, с. 324-326.

8. Ж.Ансель, О числе монотонных булевых функций п переменных, Кибернетический сборник, новая серия, вып. 5 М.: Мир, 1968

9. Гаврилов Г.П., Сапоженко A.A., Задачи и упражнения по курсу дискретной математики М.: Наука, 1992.

10. Безруков С.JI., Минимизация теней множеств полурешетки частичных отображений, Методы дискретного анализа в исследовании функциональных систем Институт математики СО АН СССР, 1988, вып. 47, с. 3-18.

11. Катериночкина H.H., Некоторые соотношения для подмножеств слоев п-мер-ной k-значной решетки, Ж. вычисл. матем. и матем. физ., 1984, т. 24, N 5,с. 782-786.

12. Д.Клейтмен, О проблеме Дедекинда: число монотонных булевых функций, Кибернетический сборник М.: Мир, новая серия, вып. 7, 1970.

13. Коробков В.К., О монотонных функциях алгебры логики, Сб. Проблемы кибернетики, вып. 13 (1965) М.: Наука - с. 5-28.

14. Коршунов А.Д. О числе монотонных булевых функций, Проблемы кибернетики, вып. 38 (1980), с. 5-108.

15. Коршунов А.Д., Решение проблемы Дедекинда о числе монотонных булевых функций, Докл. АН СССР, 1977, т. 223, N4, с. 543-546.

16. Сапоженко A.A., О числе связных подмножеств с заданной мощностью границы в двудольных графах, Методы дискретного анализа в решении комбинаторных задач Новосибирск, 1987, вып. 45, с. 42-70

17. Сапоженко A.A., О числе антицепей в ранжированных частично упорядоченных множествах, Дискретная математика М.: Наука, 1989, т.1, вып. 1, в 74-93.

18. Сапоженко A.A., О числе антицепей в многослойных ранжированных множествах, Дискретная математика М.: Наука, 1989, т.1, вып. 2, в 110-128.

19. Сапоженко A.A., О предельных распределениях случайных величин, порождае-ных ограниченными последовательностями, Дискретный анализ, Труды Института математики СО АН СССР, Новосибирск, 1994, т. 27, с. 166-176.

20. Сапоженко A.A., О числе связных множеств с заданной мощностью окрестности в графе, Дискретный анализ и исследование операций, 1997, Серия 1,т. 4, N 3, с. 19-33.

21. Сапоженко A.A., Проблема Дедекинда и метод граничных функционалов, в кн. Математические вопросы кибернетики, Вып. 9 М.: Наука, 2000, с. 161-220.

22. Сачков В.Н., Вероятностные методы в комбинаторном анализе М.: Наука, 1978.

23. Сачков В.Н., Введение в комбинаторные методы дискретной математики -М.: Наука, 1982.

24. Г.М. Фихтенгольц, Основы математического анализа М.: Наука, 1968, том 1, стр. 99.

25. Феллер В., Введение в теорию вероятностей и ее приложения М.: Наука, 1967, т. 1.

26. П.Эрдёш, Дж.Спенсер, Вероятностные методы в комбинаторике М.: Map, 1976

27. Alon N, Spenser J.H., The probabilistic method with an appendix on open problem by P.Erdos, 1992, John Wiley & SONS. INC.

28. Clements G., Lindstrom В., A generalization of a combinatorial theorem of Macaulay, J. Comb. Theory, 1968, v.7, N2, p. 230-238.